QR-Zerlegung < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:22 Sa 19.06.2004 | | Autor: | Flux |
Hi, ich bin mal wieder (ausnahmsweise *g*) planlos.
Und zwar sollte ich irgendwann mal eine QR-Zerlegung mit Hilfe von Rotationen berechnen. Irgendwie hab ich dann aber wohl verdrängt, dass es nicht klappte *g*.
Die Matrix, zu der die QR-Zerlegung berechnet , nennen wir mal A mit A = QR.
dann erhalte ich [mm] A_1 [/mm] = [mm] Q_1 [/mm] * A , [mm] A_2 [/mm] = [mm] Q_2 [/mm] * [mm] A_1 [/mm] , ...
Die Qs kriege ich auch noch alle halbwegs gut hin und das Gesamt-Q berechnet sich dann aus
[mm] \produkt_{i=1}^{n} Q_i^T
[/mm]
Bekomme ich jetzt R = [mm] Q^{-1} [/mm] * A? Ist Q überhaupt invertierbar? Außerdem habe ich leider auch keine Ahnung, was mir das überhaupt bringt, diese Zerlegung zu machen.
Bei der Suche im Netz habe ich irgendwas von Givens-Rotationen gefunden, aber die haben wir nie behandelt.
Irgendwo stand auch was vom Gram-Schmidtschen Orthonormalisierungsverfahren, aber ich habe noch nicht rausgefunden, wie mir das dabei helfen sollte.
Ich hoffe, das war nicht zu wirr. Würde mich super über ne Antwort freuen, falls jemand ne Idee hat.
Danke schonmal im Voraus! :)
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 12:53 Sa 19.06.2004 | | Autor: | Paulus |
Hallo Flux
Ich beantworte den Teile deiner Aufgabe, zu dem mit etwas einfällt, für den Rest müssen wohl hochkarätige Mathematiker her! 
>
> Bekomme ich jetzt R = [mm]Q^{-1}[/mm] * A? Ist Q überhaupt
> invertierbar? Außerdem habe ich leider auch keine Ahnung,
> was mir das überhaupt bringt, diese Zerlegung zu machen.
>
Lineare Gleichungssysteme können in Form einer Matrixgleichung geschrieben werden. Diese können für Dreiecksmatrizen besonders leicht gelöst werden.
Diesen Vorteil können wir ausnutzen, wenn wir die Matrix der Gleichung in ein Produkt einer orthogonalen Matrix und einer Dreiecksmatrix zerlegen können.
Die orthogonale Matrix ist immer invertierbar, daher können wir die Gleichung mit ihrem Inversen multiplizieren und es bleibt nur die Dreiecksmatrix auf der linken Seite der Gleichung übrig:
$A*v=b$
[mm] $\Leftrightarrow [/mm] Q*R*v=b$
[mm] $\Leftrightarrow R*v=Q^{-1}*b$
[/mm]
Mit lieben Grüssen
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:58 Sa 19.06.2004 | | Autor: | Flux |
Hi Paulus!
Dank dir sehr für die Antwort!
Nur irgendwie ist das Verfahren ja sehr viel Aufwendiger, als z.B. das Gausssche Eliminationsverfahren, darum ist mir der direkte Nutzen so nicht klar.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:53 So 20.06.2004 | | Autor: | Stefan |
Hallo Flux!
Studieren wir doch einmal den Fehlereinfluss bei der Lösung linearer Gleichungssysteme!
Es sind also Abschätzungen für eine Norm [mm] $\Vert \delta [/mm] x [mm] \Vert$ [/mm] der Störung [mm] $\delta [/mm] x$ der Lösung $x$ eines linearen Gleichungssystems $Ax=b$ herzuleiten, wenn Fehler [mm] $\delta [/mm] A$ und [mm] $\delta [/mm] b$ in den Eingangsdaten vorliegen. Es gelte:
$(A + [mm] \delta [/mm] A)(x + [mm] \delta [/mm] x ) = b + [mm] \delta [/mm] b$,
und aus $Ax=b$ folgt zunächst:
$(A + [mm] \delta [/mm] A) [mm] \delta [/mm] x = [mm] \delta [/mm] b - [mm] (\delta [/mm] A)x$.
Wenn $A + [mm] \delta [/mm] A$ invertierbar ist, ergibt sich:
[mm] $\delta [/mm] x = (A + [mm] \delta A)^{-1} (\delta [/mm] b - [mm] (\delta [/mm] A)x)$
und
[mm] $\Vert \delta [/mm] x [mm] \Vert \le \Vert [/mm] (A + [mm] \delta A)^{-1}\Vert (\Vert \delta b\Vert [/mm] + [mm] \Vert \delta [/mm] A [mm] \Vert \cdot \Vert [/mm] x [mm] \Vert)$.
[/mm]
Geht man unter der Voraussetzung $b [mm] \ne [/mm] 0$ zum relativen Fehler über, hat man
(*) [mm]\frac{\Vert \delta x \Vert}{\Vert x \Vert} \le \Vert (A + \delta A)^{-1} \Vert \Cdot \Vert A \Vert \left( \frac{\Vert \delta b\Vert}{\Vert A \Vert \cdot \Vert x \Vert} + \frac{\Vert \delta A\Vert}{\Vert A \Vert} \right)[/mm]
[mm]\le \Vert (A + \delta A)^{-1} \Vert \cdot \Vert A \Vert \left( \frac{\Vert \delta b \Vert}{\Vert b \Vert} + \frac{\Vert \delta A \Vert}{\Vert A \Vert} \right)[/mm]
wegen
[mm] $\Vert [/mm] b [mm] \Vert [/mm] = [mm] \Vert [/mm] A [mm] \Vert \le \Vert [/mm] A [mm] \Vert \cdot \Vert [/mm] x [mm] \Vert$.
[/mm]
Der relative Fehler der Lösung besetht also aus der Summe der relativen Fehler der Daten $A$ und $b$ vergrößert um einen gewissen Faktor, der noch näher zu untersuchen ist.
Satz (hier ohne Beweis)
Ist $A$ eine nichtsinguläre $n [mm] \times [/mm] n$-Matrix und [mm] $\delta [/mm] A$ eine $n [mm] \times [/mm] n$-Störungsmatrix, für die in irgendeiner zu einer Vektornorm zugeordneten Matrixnorm die Abschätzung
[mm] $\Vert A^{-1} \Vert \cdot \Vert \delta A\Vert [/mm] < 1$
gilt, so ist $A + [mm] \delta [/mm] A$ nichtsingulär, und es gilt:
[mm] $\Vert [/mm] (A + [mm] \delta A)^{-1} \Vert \le \frac{\Vert A^{-1} \Vert}{1 - \Vert A^{-1} \Vert \Vert \delta A\Vert}$.
[/mm]
Der Vergrößerungsfaktor [mm] $\Vert [/mm] (A + [mm] \delta A)^{-1} \Vert \cdot \Vert [/mm] A [mm] \Vert$ [/mm] für den relativen Fehler in (*) ist damit abschätzbar durch
[mm] $\frac{\Vert A^{ -1} \Vert \cdot \Vert A \Vert}{1 - \Vert A^{-1} \Vert \cdot \Vert A \Vert ( \Vert \delta A \Vert / \Vert A \Vert )} [/mm] = [mm] \kappa(A) \left( 1 - \kappa(A) \frac{\Vert \delta A \Vert}{\Vert A \Vert} \right)^{-1}$,
[/mm]
wenn man die Konditionszahl
[mm] $\kappa(A):= \Vert [/mm] A [mm] \Vert \cdot \Vert A^{-1} \Vert$
[/mm]
der Matrix $A$ bezüglich der gewählten Matrixnorm einführt.
Satz
Unter den Voraussetzungen $b [mm] \ne [/mm] 0$ und [mm] $\Vert A^{-1} \Vert \cdot \Vert \delta [/mm] A [mm] \Vert [/mm] < 1$ genügt jede Lösung $x + [mm] \delta [/mm] x$ des gestörten Systems $(A + [mm] \delta [/mm] A) (x + [mm] \delta [/mm] x) = b + [mm] \delta [/mm] b$der Abschätzung
[mm] $\frac{\Vert \delta x \Vert}{\Vert x \Vert} \le \kappa(A) \cdot \left( 1 - \kappa(A) \frac{\Vert \delta A \Vert}{\Vert A \Vert} \right)^{-1} \left( \frac{\Vert \delta A \Vert}{\Vert A \Vert} + \frac{\Vert \delta b \Vert}{\Vert b \Vert} \right)$.
[/mm]
Die Kondition des Problems ein $x [mm] \in \IR^n$ [/mm] ,ot $Ax=b$ zu bestimmen, ist gleich dem Vergrößerungsfaktor für die relativen Eingangsfehler beim "Durchschlagen" auf die Lösung, und deshalb im Wesentlichen die Kondition [mm] $\kappa(A)$ [/mm] der Matrix $A$. Dies gilt unter der Voraussetzung [mm] $\kappa(A) \cdot \frac{\Vert \delta A\Vert}{\Vert A \Vert} [/mm] < 1$. Ist sie nicht erfüllt, so ist das gestörte Gleichungssystem eventuell überhaupt nicht mehr auflösbar. Der relative Eingangsfehler [mm] $\Vert \delta A\Vert/\Vert [/mm] A [mm] \Vert$ [/mm] ist mindestens so groß wie die Maschinengenauigkeit eps anzusetzen, und deshalb sind Gleichungssysteme mit [mm] $\kappa(A) [/mm] > 1/eps$ durch kein Verfahren auf einer Maschine mit Genauigkeit eps zuverlässig lösbar.
Um die Kondition eines linearen Gleichungssystems nicht zu verschlechtern, wird statt der LR-Zerlegung die QR-Zerlegung einer Matrix $A$ in eine Orthogonalmatrix $Q$ und eine obere Dreiecksmatrix $R$ behandelt. Mit dieser Methode kann man auch singuläre und überbestimmte Systeme sowie Probleme der linearen Ausgleichsrechnung behandeln.
Bei der LR-Zerlegung wird die gegebene Matrix $A$ durch Linksmultiplikation mit normierten unteren Dreiecksmatrizen verändert. Da man im Allgemeinen nur
[mm] $\kappa(L \cdot [/mm] A) = [mm] \Vert [/mm] L [mm] \cdot A\Vert \cdot \Vert [/mm] ( L [mm] \cdot A)^{-1} \Vert \le \kappa(L) \cdot \kappa(A)$
[/mm]
hat, aber wegen [mm] $\kappa(L) \ge [/mm] 1$ mit [mm] $\kappa(LA) [/mm] > [mm] \kappa(A)$ [/mm] rechnen muss, wird sich die Kondition beim Übergang von $A$ zu $LA$ in der Regel verschlechtern. Deshalb ist man an Transformationen interessiert, unter denen die Kondition einer Matrix unverändert bleibt.
Satz
Die Kondition einer $n [mm] \times [/mm] bn$-Matrix bezüglich der Spektralnorm ändert sich nicht unter orthogonalen Transformationen.
BEWEIS. Ist $Q$ eine orthogonale Matrix (d.h. [mm] $Q^T [/mm] = [mm] Q^{-1}$), [/mm] so gilt:
[mm] $(QA)^T [/mm] (QA) = [mm] A^T Q^T [/mm] Q A = [mm] A^T [/mm] A$, und deshalb ist die Spaktralnorm invariant unter Orthogonaltransformationen. Das überträgt sich auf die Konditionszahlen.
Auf Grund dieses Satzes wird man versuchen eine gegebene $n [mm] \times [/mm] n$-Matrix $A$ durch Orthogonaltransformationen in eine obere Dreiecksmatrix $R$ zu transformieren. Dem entspricht dann die Zerlegung
$A = Q [mm] \cdot [/mm] R$
von $A$ in eine orthogonale Matrix $Q$ und eine obere Dreiecksmatrix $R$. Sie besitzt wegen des obigen Satzes bei numerischer Rechnung die größere Stabilität.
Liebe Grüße
Stefan
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:19 Di 22.06.2004 | | Autor: | Flux |
Hallo Stefan!
Erstmal danke!!!!, dass du dir die Mühe gemacht hast, eine solch umfangreiche Antwort zu schreiben!
Leider kann ich jedoch bis auf den Beweis ganz am Ende nicht ganz folgen...
Was genau ist denn überhaupt die Störung?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:31 Di 22.06.2004 | | Autor: | Stefan |
Hallo Flux!
Naja, normalerweise, und das weiß ich gerade als Berufsstatistiker, stecken in der Matrix $A$ und dem Vektor $b$ der rechten Seite Daten. Die Zahlen in den Matrizen und den "rechten Seiten" fallen ja, wenn man sich außerhalb des mathematischen Uni-Elfenbeinturmes bewegt, nicht vom Himmel, sondern werden bei praktisch relevanten Problemen durch Experimente oder Beobachtungen gegeben. Diese Daten können aber gestört sein, zum Beispiel durch Messfehler. Die Frage ist doch jetzt: Wenn meine Daten nicht die exakten Daten sind, sondern gestört, wie weit weicht dann meine gestörte Lösung von der tatsächlichen Lösung ab? Wie sensitiv reagiert mein Lösungsverfahren also auf Fehler in den Daten?
Und diese Abweichung hat man bei der QR-Zerlegung besser unter Kontrolle als bei der LR-Zerlegung, aus den genannten Gründen.
Liebe Grüße
Stefan
|
|
|
|
