QR-Zerlegung < Numerik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Sei A [mm] \in M^{mxn} [/mm] mit m [mm] \ge [/mm] n, b [mm] \in \IR^m [/mm] und Rang(A)=n. Sei A=QR die QR-Zerlegung von A.
begründen Sie, wie Sie mit Hilfe dieser Zerlegung das Minimierungsproblem
[mm] min_{x \in \IR^n}\parallel [/mm] Ax - b [mm] \parallel^2
[/mm]
lösen können. |
Hi,
kann mir jemand vielleicht bei dieser Aufgabe helfen?
Weiß gerade nicht, wie ich da anfagen soll.
Also ich weiß:
a) Falls die Lösung des Gleichungssystems Ax=b nicht eindeutig ist, wird das Minimierungsproblem der Form [mm] \parallel [/mm] Ax-b [mm] \parallel^2 [/mm] → min gelöst.
b) Besitzt das Minimierungsproblem keine eindeutige Lösung, so wird die kleinste Lösung von [mm] \parallel [/mm] Ax-b [mm] \parallel^2 [/mm] → min berechnet.
bei Wikipedia habe ich dann noch gefunden:
Lösung des Minimierungsproblems (http://de.wikipedia.org/wiki/Methode_der_kleinsten_Quadrate)
reicht diese Begründung schon aus?? Oder sollte man da noch was erwähnen?
Danke schon mal für Hilfe.
Gruß
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 14:28 Do 03.06.2010 | | Autor: | max3000 |
Hallo.
Du musst natürlich die Eigenschaftn der Matrizen Q (Orthogonalität) und R (Dreiecksform) irgendwie ausnutzen.
Außerdem gehe ich mal davon aus dass hier die euklidische Norm gemeint ist.
Dann kannst du die Norm mit Skalarprodukt ausdrücken:
[mm] \|Ax-b\|=\|QRx-b\|=(QRx-b)^T(QRx-b)=x^TR^TQ^TQRx-2b^TQRx-b^Tb
[/mm]
Nun ist folgendes zu berücksichtigen:
- [mm] b^T*b [/mm] ist ein konstanter Term und ist bei der Minimierung irrelevant weil der immer auftritt, also lassen wir ihn weg.
[mm] -Q^T*Q=I [/mm] die Identität, weil Q orthogonal ist.
Übrig bleibt nur noch:
$x^TR^TRx-2b^TQRx$
Nun würde ich substituieren: y=Rx
Beachte [mm] x^TR^T=(Rx)^T=y^T
[/mm]
Damit folgt:
[mm] $F(y):=y^Ty-2b^TQy\rightarrow [/mm] min$
Jetzt haben wir ein simples quadratisches Optimierungsproblem. Dieses ist konvex, weil [mm] y^T*y=y^T*I*y [/mm] und I positiv definit ist. Darum ist notwendige Optimalitätsbedingung auch gleichzeitig hinreichende.
Also muss der Gradient dieser Funktion F verschwinden.
[mm] $grad(F)(y)=2y-2b^T*Q=0$
[/mm]
Die 2en verschwinden und da Q orthogonal ist gilt: [mm] y=b^T*Q
[/mm]
b und Q sind gegeben und damit erhälst du y.
Oben haben wir y definiert durch y=R*x und das ist jetzt nur noch ein Dreieckssystem, was recht einfach zu lösen geht.
Ich muss dazu sagen dass ich jetzt nicht sehr lange darüber nachgedacht hab wie der Gradient von F aussieht (also [mm] b^T*Q [/mm] könnte evtl. auch [mm] Q^T*b [/mm] oder Q*b sein) und wie die genauen theoretischen Begründungen zum Optimum sind. Also das solltest du vielleicht nochmal überprüfen.
Ansonsten hoffe ich dass ich dir etwas helfen konnte.
Grüße
Max
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:22 So 06.06.2010 | | Autor: | jaruleking |
danke dir erstmal für die erklärung!!
Gruß
|
|
|
|
