Farkas, Frage im Beweis < Sonstiges < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
Hallo
ich habe hier eine Frage zum Beweis des
Satz: Sei [mm] A\in \mathbb{R}^{m\times n}, b\in \mathbb{R}^m. [/mm] Dann gilt:
[mm] \exists x\in \mathhb{R}^n: Ax\le [/mm] b [mm] \gdw y^Tb\ge [/mm] 0 [mm] \forall y\in\mathbb{R}^m [/mm] mit [mm] y\ge [/mm] 0, [mm] y^{T}A=0.
[/mm]
Beweis: (Man benutzt die bereits vorher bewiesene Version vom Lemma von Farkas, s.u.)
Es sei A'=[I,A,-A]. Dann besitzt [mm] Ax\le [/mm] b eine Lösung [mm] \gdw [/mm] A'x'=b eine Lösung [mm] x'\ge [/mm] 0 besitzt.
Die Behauptung folgt durch Anwendung von Farkas auf das zuletzt genannte System.
Q.e.D.
Die vorher bewiesene Version vom Lemma von Farkas lautet:
Sei [mm] A\in \mathbb{R}^{m\times n}, b\in \mathbb{R}^m. [/mm] Dann gilt:
[mm] \exists x\in \mathhb{R}^n [/mm] , [mm] x\ge [/mm] 0, Ax=b [mm] \gdw y^Tb\ge [/mm] 0 [mm] \forall y\in\mathbb{R}^m [/mm] mit [mm] y^TA\ge [/mm] 0.
1.Frage ist nun, wieso das erste genau dann wenn im Beweis gilt, also wieso gilt Dann besitzt [mm] Ax\le [/mm] b eine Lösung [mm] \gdw [/mm] A'x'=b eine Lösung [mm] x'\ge [/mm] 0 besitzt.
2.Frage: Wenn man Fakas anwendet auf das zuletzt genannte System, dh
A'x'=b besitzt eine Lösung [mm] x'\ge [/mm] 0 [mm] \gdw y^{T}b\ge [/mm] 0 [mm] \forall [/mm] y mit [mm] y^{T}A'\ge [/mm] 0.
Dann kommt man bestimmt in dem man wie bei Frage 1 vorgeht hier die Behauptung oder?
Liebe Grüße
|
|
| |
|
Hallo,
> Hallo
> ich habe hier eine Frage zum Beweis des
> Satz: Sei [mm]A\in \mathbb{R}^{m\times n}, b\in \mathbb{R}^m.[/mm]
> Dann gilt:
> [mm]\exists x\in \mathhb{R}^n: Ax\le[/mm] b [mm]\gdw y^Tb\ge[/mm] 0 [mm]\forall y\in\mathbb{R}^m[/mm]
> mit [mm]y\ge[/mm] 0, [mm]y^{T}A=0.[/mm]
>
> Beweis: (Man benutzt die bereits vorher bewiesene Version
> vom Lemma von Farkas, s.u.)
> Es sei A'=[I,A,-A]. Dann besitzt [mm]Ax\le[/mm] b eine Lösung [mm]\gdw[/mm]
> A'x'=b eine Lösung [mm]x'\ge[/mm] 0 besitzt.
> Die Behauptung folgt durch Anwendung von Farkas auf das
> zuletzt genannte System.
> Q.e.D.
> Die vorher bewiesene Version vom Lemma von Farkas lautet:
> Sei [mm]A\in \mathbb{R}^{m\times n}, b\in \mathbb{R}^m.[/mm] Dann
> gilt:
> [mm]\exists x\in \mathhb{R}^n[/mm] , [mm]x\ge[/mm] 0, Ax=b [mm]\gdw y^Tb\ge[/mm] 0
> [mm]\forall y\in\mathbb{R}^m[/mm] mit [mm]y^TA\ge[/mm] 0.
> 1.Frage ist nun, wieso das erste genau dann wenn im Beweis
> gilt, also wieso gilt Dann besitzt [mm]Ax\le[/mm] b eine Lösung
> [mm]\gdw[/mm] A'x'=b eine Lösung [mm]x'\ge[/mm] 0 besitzt.
Schreibe dazu $x' = [mm] \vektor{x_1\\x_2\\x_3}$. [/mm] Dann erfüllt eine Lösung von $A' x' = b$ mit $x' [mm] \ge [/mm] 0$ :
[mm] $x_1 [/mm] + A [mm] x_2 [/mm] - A [mm] x_3 [/mm] = b$
also
[mm] $A*(x_2 [/mm] - [mm] x_3) [/mm] = b - [mm] x_1$.
[/mm]
Begründe nun, warum $x = [mm] x_2 [/mm] - [mm] x_3$ [/mm] eine Lösung der Gleichung $Ax [mm] \le [/mm] b$ ist.
Andersherum: Wenn du eine Lösung von $Ax [mm] \le [/mm] b$ hast, wie kommst du dann an $x'$, d.h. wie sind [mm] $x_1,x_2,x_3$ [/mm] zu definieren?
> 2.Frage: Wenn man Fakas anwendet auf das zuletzt genannte
> System, dh
> A'x'=b besitzt eine Lösung [mm]x'\ge[/mm] 0 [mm]\gdw y^{T}b\ge[/mm] 0
> [mm]\forall[/mm] y mit [mm]y^{T}A'\ge[/mm] 0.
> Dann kommt man bestimmt in dem man wie bei Frage 1 vorgeht
> hier die Behauptung oder?
Ich weiß nicht genau was du damit meinst, "wie in Frage 1 vorzugehen".
Natürlich ist wieder eine Äquivalenz zu zeigen.
Für die Ungleichung [mm] $y^{T} [/mm] A' [mm] \ge [/mm] 0$ gilt:
[mm] $y^{T} [/mm] A' [mm] \ge [/mm] 0 [mm] \gdw y_1^{T} [/mm] + [mm] y_2^{T}A [/mm] - [mm] y_3^{T}A \ge [/mm] 0 [mm] \gdw (y_2^{T} [/mm] - [mm] y_3^{T}) [/mm] A [mm] \ge [/mm] - [mm] y_1^{T}$.
[/mm]
---
Ist nun $y [mm] \in \IR^{m}$ [/mm] mit $y [mm] \ge [/mm] 0$ und [mm] $y^{T}A [/mm] = 0$,
so können wir [mm] $y_1 [/mm] = 0$, [mm] $y_2 [/mm] = y$ und [mm] $y_3 [/mm] = 0$ wählen.
Dann ist [mm] $(y_1^{T},y_2^{T},y_3^{T}) [/mm] A' = [mm] y^{T}A [/mm] = 0$, also [mm] $y^{T}b \ge [/mm] 0$.
Damit ist eine Richtung gezeigt. Versuche nun die andere Richtung.
Viele Grüße,
Stefan
|
|
|
| |
|
Hi, danke für deine Antwort.
[mm] x=x_2-x_3 [/mm] ist eine Lösung von [mm] Ax\le [/mm] b, da wegen [mm] x_1\ge [/mm] 0
[mm] A(x_2-x_3)=b-x_1\le [/mm] b ist.
Andersherum: Für x' = [mm] \vektor{x_1\\x_2\\x_3} [/mm] mit [mm] A'x'=x_1+Ax_2-Ax_3=x_1+A(x_2-x_3)=b [/mm] soll jetzt [mm] x'\ge [/mm] 0 gelten und nach Voraussetzung gilt [mm] Ax\le [/mm] b für ein [mm] x\in \mathbb{R}^n. [/mm] Deswegen dachte ich auch hier soll wieder [mm] x_1\ge [/mm] 0 gelten, somit [mm] x_1+A(x_2-x_3)=b\ge A(x_2-x_3) [/mm] mit [mm] x=x_2-x_3. [/mm] Reicht es jetzt aus zu sagen [mm] x_2, x_3 [/mm] sollen [mm] \ge [/mm] 0 sein und muss man fordern, dass [mm] x_2-x_3\ge [/mm] 0 (ich glaube nicht, bin mir nicht sicher)?
Zu der einen Richtung zu 2. die du vorgeführt hast, habe ich eine Frage zu der letzten Zeile , also zu [mm] (y_1^{T},y_2^{T},y_3^{T}) [/mm] A' = [mm] y^{T}A [/mm] = 0
sd. [mm] y^{T}b\ge [/mm] 0 ist.
Eigentlich soll ja [mm] y^{T}A'\ge [/mm] 0 sein, ist das dann kein Problem wenn man sich y so definiert, dass aber [mm] y^{T}A' [/mm] nur =0 ist und man so [mm] y^{T}b\ge [/mm] 0 bekommt?
Liebe Grüße
|
|
|
| |
|
Hallo,
> Hi, danke für deine Antwort.
>
> [mm]x=x_2-x_3[/mm] ist eine Lösung von [mm]Ax\le[/mm] b, da wegen [mm]x_1\ge[/mm] 0
> [mm]A(x_2-x_3)=b-x_1\le[/mm] b ist.
So ist es ! ![[ok]](/images/smileys/ok.gif "[ok]")
> Andersherum: Für x' = [mm]\vektor{x_1\\x_2\\x_3}[/mm] mit
> [mm]A'x'=x_1+Ax_2-Ax_3=x_1+A(x_2-x_3)=b[/mm] soll jetzt [mm]x'\ge[/mm] 0
> gelten und nach Voraussetzung gilt [mm]Ax\le[/mm] b für ein [mm]x\in \mathbb{R}^n.[/mm]
> Deswegen dachte ich auch hier soll wieder [mm]x_1\ge[/mm] 0 gelten,
> somit [mm]x_1+A(x_2-x_3)=b\ge A(x_2-x_3)[/mm] mit [mm]x=x_2-x_3.[/mm] Reicht
> es jetzt aus zu sagen [mm]x_2, x_3[/mm] sollen [mm]\ge[/mm] 0 sein
> und muss
> man fordern, dass [mm]x_2-x_3\ge[/mm] 0 (ich glaube nicht, bin mir
> nicht sicher)?
Nein, es muss nur [mm] $x_2, x_3 \ge [/mm] 0$ sein. [mm] $x_2 [/mm] - [mm] x_3$ [/mm] kann einen beliebigen reellen Wert annehmen.
Du hast durch obigen Text aber noch nicht die Aussage bewiesen. Ich hatte so etwas erwartet:
Als erstes definieren wir [mm] $x_1 [/mm] := b - Ax [mm] \ge [/mm] 0$.
Dann wählen wir [mm] $x_2, x_3 \ge [/mm] 0$ so, dass $x = [mm] x_2 [/mm] - [mm] x_3$ [/mm] (das ist immer möglich; wenn zum Beispiel $x [mm] \ge [/mm] 0$ wählt man [mm] $x_3 [/mm] = 0$ und [mm] $x_2 [/mm] := x$; für $x [mm] \le [/mm] 0$ geht es ähnlich).
Damit ist
$A' x' = [mm] x_1+A(x_2-x_3) [/mm] = (b-Ax) + Ax = b$.
----
> Zu der einen Richtung zu 2. die du vorgeführt hast, habe
> ich eine Frage zu der letzten Zeile ,
Es wäre leichter, wenn du meine Antwort (also die gesamte) zitierst. So muss ich immer zwei Fenster aufhaben 
> also zu
> [mm](y_1^{T},y_2^{T},y_3^{T})[/mm] A' = [mm]y^{T}A[/mm] = 0
> sd. [mm]y^{T}b\ge[/mm] 0 ist.
> Eigentlich soll ja [mm]y^{T}A'\ge[/mm] 0 sein, ist das dann kein
> Problem wenn man sich y so definiert, dass aber [mm]y^{T}A'[/mm] nur
> =0 ist und man so [mm]y^{T}b\ge[/mm] 0 bekommt?
Ich hatte mich bei meiner letzten Antwort ein bisschen mit den Dimensionen vertan, sorry.
Zu zeigen ist folgende Äquivalenz: $(1) [mm] \gdw [/mm] (2)$ mit
(1) [mm] $\Big(\forall [/mm] y [mm] \in \IR^{m}: [/mm] y [mm] \ge [/mm] 0, [mm] y^{T}A [/mm] = 0 [mm] \Rightarrow y^{T}b \ge 0\Big)$
[/mm]
(2) [mm] $\Big(\forall [/mm] y' [mm] \in \IR^{m}: y^{'T} [/mm] A' [mm] \ge [/mm] 0 [mm] \Rightarrow y^{'T}b \ge 0\Big)$.
[/mm]
Wenn ich jetzt also die Richtung $(1) [mm] \Leftarrow [/mm] (2)$ zeigen möchte, nehme ich mir ein beliebiges $y [mm] \in \IR^{m}$ [/mm] mit den Eigenschaften $y [mm] \ge [/mm] 0, [mm] y^{T}A [/mm] = 0$ und muss [mm] $y^{T}b \ge [/mm] 0$ zeigen.
Dazu nutzt man die Eigenschaft (2). Ich kann hier ein beliebiges $y'$ nehmen, was die Eigenschaften [mm] $y^{'T} [/mm] A' [mm] \ge [/mm] 0$ erfüllt und erhalte dann aus (2): [mm] $y^{'T}b \ge [/mm] 0$.
Wenn ich nun $y'$ wähle, so ist sicher [mm] $y^{'T}A' [/mm] = [mm] (y^{T}, y^{T}A, -y^{T}A) [/mm] = [mm] (y^{T},0,0) \ge [/mm] 0$. Damit ist die Voraussetzung erfüllt. Wir erhalten [mm] $y^{T} \ge [/mm] b$.
Nun kannst du die andere Richtung versuchen!
Viele Grüße,
Stefan
|
|
|
|
