\
Hallo und Herzlich Willkommen auf dem Matheplaneten,

als erstes ein formaler Hinweis. Dein Beitrag lässte sich leichter lesen, wenn die Formeln lesbarer sind. Dafür gibt es hier den ''Optimath-fedgeo Formeleditor''. Klicke beim Verfassen eines Beitrags mal auf die Links unterhalb des Fensters ''fed Bereich einfügen'' und ''Optimath-fedgeo Formeleditor''. Wenn Du sehen willst, wie andere ihre Beiträge formatieren (wenn sie denn mit dem Formeleditor erstellt wurden), dann klicke einfach auf den Text und es öffnet sich ein Fenster mit dem Quelltext.

Nun zur Frage. a) lässt sich sehr leicht erledigen auch völlig unabhängig von b) Man benötigt lediglich die Ungleichung norm(Ax_(ls)-b)_2 <= norm(Ax_(ch)-b)_2 (warum gilt diese Ungleichung?) und den angegebenen Hinweis.

Zu b):
Sei v_1:=-r_ls/norm(r_ls)_1. 
Dann ist A^T*v_1=-A^T*r_ls/norm(r_ls)_1 =(-A^T*(b-A*x_ls))/norm(r_ls)_1. Wenn Du hier x_ls einsetzt, soltest Du etwas sehen.

Eine weitere Frage war ja, wie man minimiere norm(Ax-b)_Max als LOP umschreibt. Das geht so:
minimiere v 
u.d.N:   -v<=A_i*x-b_i<=v für alle i,
wobei A_i die i\-te Zeile von A ist.
Die Bedingung -v<=A_i*x-b_i<=v kann man dann noch umformulieren:
A_i*x-v<=b_i
A_i*x+v<=b_i

Schau mal, ob Du damit weiterkommst.

Kitaktus

Danke Kitaktus, 
das hat mir schonmal weiter geholfen.

a) norm(Ax_ls -b)_Max <= norm(Ax_ls -b)_2 <= norm(Ax_ch -b)_2 <= sqrt(m) norm(Ax_ch -b)_Max

Ich denke die Ungleichung norm(Ax_ls -b)_2 <= norm(Ax_ch -b)_2 gilt, da nach Angabe x_ls = armin norm(Ax-b)_2 gilt, und x_ls somit norm(Ax-b)_2 minimiert.


b) Hier bin ich mir noch unsicher auf was du hinaus wolltest.

A^T v_1 = (-A^T (b-A(A^T A)^(-1) A^T b))/norm(r_ls)_1 = (-A^T (b-Xb))/norm(r_ls)_1
Wobei X eine reguläre und idempotente Matrix darstellt.

Da A^T v_1 =0 gelten soll, folgt, dass (b-Xb)=0 gilt. Aber das kann ja nicht sein, da nach Angabe r_ls != 0 gilt.

Oder meintest du ich soll x_ls = armin norm(Ax-b)_2 einsetzen, aber das sagt mir auch nichts

Gruß Jan

\
Sieh Dir 
A^T v_1 = (-A^T (b-A(A^T A)^(-1) A^T b))/norm(r_ls)_1 = ...

nochmal scharf an und multipliziere mal aus.

Kitaktus

Ah, also gilt

A^T v_1 = (-A^T b + A^T A (A^T A)^(-1) A^T b)/norm(r_ls)_1 = (-A^T b +A^T b)/norm(r_ls)_1 = 0

Und da A^T v_1 = -A^T v_2 , gilt das also für beide.
Somit ist gezeigt, dass sowohl v_1 als auch v_2 in b^T v möglich sind.

Sehr gut, dann soll ich jetzt noch zeigen welche dieser beiden unteren Schranken b^T v_1 und b^T v_2 die bessere ist (also die größere). Wie mache ich das? Dazu müsste ich ja b^T v_1 und b^T v_2 miteinander vergleichen, aber ich hab ja keine Ahnung wie b aussieht.


Und wie wirken diese Schranken im Vergleich zu der in Teil a)?
Wenn ich mich nicht irre, denke ich dass die Schranke aus Teil a), nämlich sqrt(m) norm(Ax_ch -b)_Max eine obere Schranke für norm(Ax_ls -b)_Max ist, während die in Teil b) untere Schranken sind, oder???

Gruß Jan

Ich hab mal versucht b^T v_1 und b^T v_2 so umzuformen, dass ich sie vergleichen kann und bin so weit gekommen:

b^T v_1 = (-abs(b)^2 +b^T Xb)/norm(r_lx)_1
b^T v_2 = (abs(b)^2 -b^T Xb)/norm(r_lx)_1
Wobei X= A(A^T A)^(-1) A^T eine idempotente Matrix ist. Da alle Eigenwerte von idempotenten Matrizen 0 oder 1 sind, ist X postitiv semidefinit und es gilt: b^T Xb >= 0

Somit bleibt nur noch die Frage was größer ist, abs(b)^2 oder b^T Xb ???

Ich hab jetzt noch folgendes gefunden.
b^T v_1=(-b^T r_ls )/((norm(r_ls)_1)  
=(-(Ax_ls -b)^T r_ls)/(norm(r_ls)_1 
= - norm(r_ls)_2^2/norm(r_ls)_1

und b^T v_2 = -b^T v_1
Da b^T v_1 >= 0 und b^T v_2 <= 0 gilt b^T v_1 >= b^T v_2 und somit ist b^T v_1 die bessere, weil größere, Schranke.

Weiter kann man (norm(r_ls)_2^2)/(norm(r_ls)_1) >= (norm(r_ls)_Max^2)/(norm(r_ls)_1) = (norm(r_ls)_Max)/(norm(r_ls)_1) norm(r_ls)_Max >= x_Max/(m*x_Max) norm(r_ls)_Max = 1/m norm(r_ls)_Max >= 1/(sqrt(m)) norm(r_ls)_Max

Jetzt hab ich noch zwei Fragen dazu.
Wieso gilt b^T = (Ax_ls -b)^T ???

Und wie wirken diese Schranken (von b) verglichen mit der in Teil a) erhalten Schranke?

Dann hät ich alles geschnallt, denke ich.
Gruß Jan

\
''Wieso gilt b^T = (Ax_ls -b)^T ?''

Wie kommst Du auf diese Gleichung? Sie ist mit ziemlichr Sicherheit falsch. Wäre sie richtig, so würde gelten:
b^T = (Ax_ls -b)^T
b = (Ax_ls -b)
2b = A*x_ls
b = A*(x_ls)/2

Die optimale Lösung der Gleichung Ax=b wäre dann (x_ls)/2 und nicht x_ls, was (für b!=0) ein Widerspruch ist.

Kitaktus

Die Aussage gilt, da man wegen dem Beweis A^T v_1 =0 sagen kann, dass A^T r_ls =0.

Und dann gilt: -b^T r_ls = x_ls^T *0-b^T r_ls = x_ls ^T A^T r_ls -b^T r_ls = (Ax_ls -b)^T r_ls = r_ls ^T r_ls = norm(r_ls)_2 ^2

Und das ist natürlich positiv, die Norm im Nenner auch, also kann ich schließen, dass: b^T v_1 >= b^T v_2
Und somit ist b^T v_1 die bessere weil größere untere Schranke.

Aufgabe gelöst!!!

Dankeschön für deine Hilfe,
Gruß Jan