QR-Zerlegung - LinkFang.de





QR-Zerlegung


Die QR-Zerlegung oder QR-Faktorisierung ist ein Begriff aus den mathematischen Teilgebieten der linearen Algebra und Numerik. Man bezeichnet damit die Zerlegung einer Matrix [math]A[/math] in das Produkt

[math] A = Q\cdot R[/math]

zweier anderer Matrizen, wobei [math]Q[/math] eine orthogonale ([math]QQ^T=I[/math]) bzw. unitäre Matrix ([math]QQ^{\ast}=I[/math]) und [math]R[/math] eine obere Dreiecksmatrix ist. Die QR-Zerlegung ist ein Spezialfall der Iwasawa-Zerlegung.

Eine solche Zerlegung existiert stets und kann mit verschiedenen Algorithmen berechnet werden. Die bekanntesten davon sind

Das letztere wird üblicherweise in der linearen Algebra benutzt, ist aber in seiner Standardform numerisch instabil. Man kann das Verfahren aber erweitern und numerisch stabilisieren.

Definition

Eine Matrix [math]A \in \R^{m\times n}[/math], [math]m \geq n[/math] besitzt eine (fast – siehe weiter unten) eindeutige reduzierte QR-Zerlegung

[math]A=\hat{Q}\cdot\hat{R}[/math]

als Produkt einer in den Spalten orthogonalen Matrix [math]\hat{Q} \in \R^{m\times n}[/math] und einer oberen Dreiecksmatrix [math]\hat{R} \in \R^{n\times n}.[/math]

Diese Lösung ist erweiterbar zu einer vollständigen QR-Zerlegung

[math]A = Q\cdot R[/math],

indem man [math]\hat{Q}[/math] mit weiteren orthogonalen Spalten [math]\tilde{Q}[/math] zu einer quadratischen [math]m \times m[/math]-Matrix erweitert, und an [math]\hat{R}[/math] unten Nullen anfügt, so dass eine [math]m\times n[/math]-Matrix entsteht:

[math] Q\cdot R = \begin{pmatrix} \hat{Q} & \tilde{Q} \end{pmatrix} \cdot \begin{pmatrix} \hat{R} \\ 0 \end{pmatrix} = \hat{Q}\cdot\hat{R} [/math]

Die QR-Zerlegung ist eindeutig für [math]m \geq n[/math] und [math]\operatorname{Rang}(A)=n[/math], wenn man die Vorzeichen der Diagonalelemente von [math]R, \hat{R}[/math] vorgibt – üblicherweise wählt man alle positiv.

Anwendung

Die QR-Zerlegung spielt in vielen Verfahren der numerischen Mathematik eine wichtige Rolle, beispielsweise um eine orthogonale oder unitäre Basis zu bestimmen oder um lineare Ausgleichsprobleme zu behandeln. Sie ist integraler Bestandteil des QR-Algorithmus zur Berechnung aller Eigenwerte einer Matrix.

Lösung regulärer oder überbestimmter Gleichungssysteme

Um die Lösung [math]x\in\R^n[/math] eines linearen Gleichungssystems mit Matrix [math]A\in\R^{m\times n},\ m\ge n[/math],

[math]Ax = b[/math] von vollem Rang zu bestimmen, sind folgende drei Schritte durchzuführen:
  1. Bestimme eine QR-Zerlegung der Matrix [math]A[/math].
  2. Berechne [math]z = Q^Tb\in\R^n[/math], üblicherweise unter Benutzung der Faktorisierung von [math]Q[/math] aus Schritt 1.
  3. Löse [math]Rx = z[/math] durch Rückwärtseinsetzen.

Für [math]m=n[/math] ist dies eine Alternative zur LR-Zerlegung, sie hat den doppelten Aufwand der LR-Zerlegung, ist aber möglicherweise numerisch stabiler.

Im Fall [math]m\gtn[/math] gibt es im Gleichungssystem mehr Gleichungen als Variablen und es liegt ein überbestimmtes Gleichungssystem vor. Hier wird [math]x[/math] durch Lösung des Ausgleichproblems nach der Methode der kleinsten Quadrate (s. auch Regressionsanalyse) bestimmt:

Minimiere [math]\|Ax-b\|^2=\sum_{j=1}^m\left(\sum_{k=1}^n a_{jk}x_k-b_j\right)^2[/math].

In diesem Fall ist [math]A^+=R^{+}Q^T[/math] die Moore-Penrose-Pseudoinverse von [math]A[/math] und für die berechnete Kleinste-Quadrate-Lösung [math]x[/math] gilt die Beziehung [math]x=A^+b[/math], die die übliche Darstellung [math]x=A^{-1}b[/math] des regulären Falls [math]m=n[/math] verallgemeinert.

Lösung unterbestimmter Gleichungssysteme

Für [math]m\ltn[/math] hat die Matrix [math]A[/math] einen nichttrivialen Kern. Bei vollem Rang von [math]A[/math] bilden die Lösungen des Gleichungssystems [math]Ax=b[/math] daher einen affinen Unterraum. Diejenige Lösung mit kleinster Norm liegt im orthogonalen Komplement des Kerns und man bekommt sie mit Hilfe einer QR-Zerlegung von [math]A^T[/math]:

  1. Bestimme eine QR-Zerlegung der Matrix [math]A^T=QR[/math].
  2. Löse [math]R^T z = b\in\R^m[/math] durch Vorwärtseinsetzen.
  3. Berechne [math]x = Qz\in\R^n[/math].

Auch hier ist wieder [math]A^+=Q(R^T)^{+}[/math] die Moore-Penrose-Pseudoinverse von [math]A[/math] und für die berechnete Lösung kleinster Norm gilt die Beziehung [math]x=A^+b[/math].

Weblinks


Kategorien: Keine Kategorien vorhanden!

Quelle: Wikipedia - http://de.wikipedia.org/wiki/QR-Zerlegung (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.