www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Vorhilfe
  Status Geisteswiss.
    Status Erdkunde
    Status Geschichte
    Status Jura
    Status Musik/Kunst
    Status Pädagogik
    Status Philosophie
    Status Politik/Wirtschaft
    Status Psychologie
    Status Religion
    Status Sozialwissenschaften
  Status Informatik
    Status Schule
    Status Hochschule
    Status Info-Training
    Status Wettbewerbe
    Status Praxis
    Status Internes IR
  Status Ingenieurwiss.
    Status Bauingenieurwesen
    Status Elektrotechnik
    Status Maschinenbau
    Status Materialwissenschaft
    Status Regelungstechnik
    Status Signaltheorie
    Status Sonstiges
    Status Technik
  Status Mathe
    Status Schulmathe
    Status Hochschulmathe
    Status Mathe-Vorkurse
    Status Mathe-Software
  Status Naturwiss.
    Status Astronomie
    Status Biologie
    Status Chemie
    Status Geowissenschaften
    Status Medizin
    Status Physik
    Status Sport
  Status Sonstiges / Diverses
  Status Sprachen
    Status Deutsch
    Status Englisch
    Status Französisch
    Status Griechisch
    Status Latein
    Status Russisch
    Status Spanisch
    Status Vorkurse
    Status Sonstiges (Sprachen)
  Status Neuerdings
  Status Internes VH
    Status Café VH
    Status Verbesserungen
    Status Benutzerbetreuung
    Status Plenum
    Status Datenbank-Forum
    Status Test-Forum
    Status Fragwürdige Inhalte
    Status VH e.V.

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:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
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.vorhilfe.de