lgs - polytop < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:16 Mo 30.08.2004 | | Autor: | andreas |
hi
in "numerische mathematik" von jochen werner findet sich folgendes lemma
Die Menge [m] M := \{ x \in \mathbb{R}^n: x \geq 0, \, Ax = b \} [/m] sei nichtleer. $M$ ist genau dann unbeschränkt, wenn es kein $d [mm] \in \mathbb{R}^n \setminus \{ 0 \} [/mm] $ mit $d [mm] \geq [/mm] 0$ und $Ad = 0$ gibt.
tippfehler ausgebessert. in dem lemma soll beschränkt stehen und nicht unbeschränkt
hierbei sind die vektorungleichungen immer komponentenweise zu verstehen, also [m] x, \, y \in \mathbb{R}^n. \; x \geq y \; : \Longleftrightarrow \; \forall \, i \in \{1, ..., n \}: x_i \geq y_i [/m], sowie [m] A \in \mathbb{R}^{m \times n}, \; b \in \mathbb{R}^m [/m].
die eine richtung des beweises ist mir klar. die andere richtung nicht:
Ist umgekehrt $M$ nicht beschränkt, so gibt es eine Folge [m] \{x^k\} \subset M[/m] mit [m] \|x^k\|_2 \longrightarrow \infty [/m]. Aus [m] d^k := x^k / \|x^k\|_2 [/m] lässt sich eine gegen ein $d [mm] \not= [/mm] 0$ konvergente Teilfolge auswählen.
soweit ist es mir klar, da die [mm] $d^k$ [/mm] aus einer kompakten menge sind. jedoch ist mir folgendes überhaupt nicht klar:
Offenbar ist [m] d \geq 0 [/m] und [m] Ad = 0 [/m].
warum denn das?
ich würde mich über tipps, wie man das sehen soll freuen!
grüße
andreas
|
|
| |
|
Hallo andreas,
[mm]Ax^k=b \Rightarrow Ad^k=\bruch {b}{||x^k||}[/mm]
und [mm]\bruch {b}{||x^k||}\rightarrow 0[/mm]
[mm]||d^x||=\bruch {||x^k||}{||x^k||}=1 \Rightarrow ||d||=1[/mm]
Das müsste eigentlich so gehen.
gruß
mathemaduenn
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:09 Mo 30.08.2004 | | Autor: | andreas |
hi mathemaduenn und stefan
danke erstmal. das mit [m] Ad = 0 [/m] ist mir nun soweit klar, aber warum soll [m] d \geq 0 [/m] gelten, also warum soll jede koordinate von [mm] $d^k$ [/mm] gößer als null sein, und das bei beliebiger wahl der unbeschränkten folge [mm] $x^k$?
[/mm]
andreas
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:22 Mo 30.08.2004 | | Autor: | Marc |
Hallo Andreas!
> danke erstmal. das mit [m]Ad = 0[/m] ist mir nun soweit klar, aber
> warum soll [m]d \geq 0[/m] gelten, also warum soll jede koordinate
> von [mm]d^k[/mm] gößer als null sein, und das bei beliebiger wahl
> der unbeschränkten folge [mm]x^k[/mm]?
Die einzelnen Folgenglieder haben doch alle nicht-negative Komponenten, [mm] d^k [/mm] dann ebenfalls und der Grenzwert der [mm] d^k [/mm] dann auch, oder?
Viele Grüße,
Marc
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:28 Mo 30.08.2004 | | Autor: | andreas |
hi
> Die einzelnen Folgenglieder haben doch alle nicht-negative
> Komponenten, [mm]d^k[/mm] dann ebenfalls und der Grenzwert der [mm]d^k[/mm]
> dann auch, oder?
genau das ist mir ja unklar: warum haben die [mm] $x^k$ [/mm] nur nicht-negative komponenten?
andreas
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 16:31 Mo 30.08.2004 | | Autor: | Marc |
Hallo Andreas!
> genau das ist mir ja unklar: warum kaben die [mm]x^k[/mm] nur
> nicht-negative komponenten?
Sie sind doch aus der Menge M, in der alle Vektoren nicht-negative Komponenten haben.
Viele Grüße,
Marc
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:35 Mo 30.08.2004 | | Autor: | andreas |
danke. das ist überzeugend.
das ist ja schon fast peinlich an solchen trivialitäten zu scheitern.
grüße
andreas
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:48 Mo 30.08.2004 | | Autor: | Marc |
Hallo Andreas!
> das ist ja schon fast peinlich an solchen trivialitäten zu
> scheitern.
In etwas abgewandelter Form kenne ich das aus eigener Erfahrung: "das ist ja schon fast peinlich schon an solchen trivialitäten zu scheitern." Deswegen solltest du froh sein 
Viele Grüße,
Marc
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:05 Mo 30.08.2004 | | Autor: | Stefan |
Lieber Andreas!
Ja, es geht so, wie mathemaduenn schreibt.
Beachte bitte, dass aus
[mm] $\lim\limits_{k \to \infty} \Vert d^k-d\Vert_2 [/mm] =0$
insbesondere
[mm] $\lim\limits_{k \to \infty} \vert d_i^k [/mm] - [mm] d_i\vert [/mm] =0$
für alle $i [mm] \in \{1,\ldots,n\}$ [/mm] folgt, also wegen [mm] $d_i^k \ge [/mm] 0$ für alle $k [mm] \in \IN$ [/mm] und alle $i [mm] \in \{1,\ldots,n\}$ [/mm] auch
[mm] $d_i \ge [/mm] 0$
und damit [mm] $d\ge [/mm] 0$.
Die andere Beziehung folgt so:
Es gilt:
$0 [mm] \le \Vert [/mm] A [mm] d\Vert_2$
[/mm]
[mm] $\le \Vert Ad^k [/mm] - [mm] Ad\Vert_2 [/mm] + [mm] \Vert Ad^k \Vert_2$
[/mm]
[mm] $\le \Vert [/mm] A [mm] \Vert_{2,2} \cdot \Vert d^k [/mm] - [mm] d\Vert_2 [/mm] + [mm] \frac{1}{\Vert x^k \Vert_2} \cdot \Vert [/mm] b [mm] \Vert_2$.
[/mm]
Aus
[mm] $\lim\limits_{k \to \infty} \left( \Vert A \Vert_{2,2} \cdot \Vert d^k - d\Vert_2 + \frac{1}{\Vert x^k \Vert_2} \cdot \Vert b \Vert_2 \right)=0$
[/mm]
folgt:
[mm] $\Vert Ad\Vert_2 [/mm] =0$
und damit $Ad=0$.
Liebe Grüße
Stefan
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:17 Mo 30.08.2004 | | Autor: | Marc |
Hallo zusammen,
> Die Menge [m]M := \{ x \in \mathbb{R}^n: x \geq 0, \, Ax = b \}[/m]
> sei nichtleer. [mm]M[/mm] ist genau dann unbeschränkt, wenn es kein
> [mm]d \in \mathbb{R}^n \setminus \{ 0 \}[/mm] mit [mm]d \geq 0[/mm] und [mm]Ad = 0[/mm]
> gibt.
> Ist umgekehrt [mm]M[/mm] nicht beschränkt, so gibt es eine Folge
> [m]\{x^k\} \subset M[/m] mit [m]\|x^k\|_2 \longrightarrow \infty [/m].
> Aus [m]d^k := x^k / \|x^k\|_2[/m] lässt sich eine gegen ein [mm]d \not= 0[/mm]
> konvergente Teilfolge auswählen.
> soweit ist es mir klar, da die [mm]d^k[/mm] aus einer kompakten
> menge sind. jedoch ist mir folgendes überhaupt nicht
> klar:
>
> Offenbar ist [m]d \geq 0[/m] und [m]Ad = 0 [/m].
> warum denn das?
Meine Frage: Widerlegt das jetzt nicht die eigentliche Aussage? M ist unbeschränkt, und es wurde ein [mm]d \in \mathbb{R}^n \setminus \{ 0 \}[/mm] mit [mm]d \geq 0[/mm] und [mm]Ad = 0[/mm] gefunden.
Was übersehe ich da?
Viele Grüße,
Marc
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:25 Mo 30.08.2004 | | Autor: | andreas |
hi
das war ein absolut unnötiger tippfehler es sollte natürlich beschränkt heißen.
hier der nächste versuch:
Die Menge [m] M := \{ x \in \mathbb{R}^n: x \geq 0, \, Ax = b \} [/m] sei nichtleer. $M$ ist genau dann beschränkt, wenn es kein $d [mm] \in \mathbb{R}^n \setminus \{ 0 \} [/mm] $ mit $d [mm] \geq [/mm] 0$ und $Ad = 0$ gibt.
sorry
andreas
|
|
|
|
