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
StartseiteMatheForenUni-Lineare AlgebraQR-Zerlegung
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Deutsch • Englisch • Französisch • Latein • Spanisch • Russisch • Griechisch
Forum "Uni-Lineare Algebra" - QR-Zerlegung
QR-Zerlegung < Lineare Algebra < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Uni-Lineare Algebra"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

QR-Zerlegung: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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! :)

        
Bezug
QR-Zerlegung: Antwort
Status: (Antwort) fertig Status 
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

Bezug
                
Bezug
QR-Zerlegung: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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.

Bezug
        
Bezug
QR-Zerlegung: Antwort
Status: (Antwort) fertig Status 
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

Bezug
                
Bezug
QR-Zerlegung: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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?

Bezug
                        
Bezug
QR-Zerlegung: Antwort
Status: (Antwort) fertig Status 
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

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


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