matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenLineare Algebra SonstigesFarkas, Frage im Beweis
Foren für weitere Studienfächer findest Du auf www.vorhilfe.de z.B. Astronomie • Medizin • Elektrotechnik • Maschinenbau • Bauingenieurwesen • Jura • Psychologie • Geowissenschaften
Forum "Lineare Algebra Sonstiges" - Farkas, Frage im Beweis
Farkas, Frage im Beweis < Sonstiges < Lineare Algebra < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Lineare Algebra Sonstiges"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Farkas, Frage im Beweis: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 17:57 Mi 02.10.2013
Autor: Schachtel5

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


        
Bezug
Farkas, Frage im Beweis: Antwort
Status: (Antwort) fertig Status 
Datum: 02:18 Do 03.10.2013
Autor: steppenhahn

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

Bezug
                
Bezug
Farkas, Frage im Beweis: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 19:44 Do 03.10.2013
Autor: Schachtel5

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



Bezug
                        
Bezug
Farkas, Frage im Beweis: Antwort
Status: (Antwort) fertig Status 
Datum: 00:42 Fr 04.10.2013
Autor: steppenhahn

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]

> 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

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Lineare Algebra Sonstiges"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]