QR-Zerlegung - de.LinkFang.org

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 A in das Produkt

A = Q\cdot R

zweier anderer Matrizen, wobei Q eine orthogonale ({\displaystyle Q^{T}Q=I}) bzw. unitäre Matrix ({\displaystyle Q^{\ast }Q=I}) und R 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.

Inhaltsverzeichnis

Definition


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

A=\hat{Q}\cdot\hat{R}

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

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

A = Q\cdot R,

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

{\displaystyle Q\cdot R={\begin{pmatrix}{\hat {Q}}&{\tilde {Q}}\end{pmatrix}}\cdot {\begin{pmatrix}{\hat {R}}\\0\end{pmatrix}}={\hat {Q}}\cdot {\hat {R}}.}

Die QR-Zerlegung ist eindeutig für m\geq n und \operatorname{Rang}(A)=n, wenn man die Vorzeichen der Diagonalelemente von R, \hat{R} 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 und der Unterraumiteration zur Berechnung von Eigenwerten einer Matrix.

Lösung regulärer oder überbestimmter Gleichungssysteme

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

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

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

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

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

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

Lösung unterbestimmter Gleichungssysteme

Für m<n hat die Matrix A einen nichttrivialen Kern. Bei vollem Rang von A bilden die Lösungen des Gleichungssystems Ax=b 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 A^{T}:

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

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

Weblinks





Kategorien: Numerische lineare Algebra



Quelle: Wikipedia - https://de.wikipedia.org/wiki/QR-Zerlegung (Autoren [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Veränderungen: Alle Bilder und die meisten Designelemente, die mit ihnen in Verbindung stehen, wurden entfernt. Icons wurden teilweise durch FontAwesome-Icons ersetzt. Einige Vorlagen wurden entfernt (wie „Lesenswerter Artikel“, „Exzellenter Artikel“) oder umgeschrieben. CSS-Klassen wurden zum Großteil entfernt oder vereinheitlicht.
Wikipedia spezifische Links, die nicht zu Artikeln oder Kategorien führen (wie „Redlink“, „Bearbeiten-Links“, „Portal-Links“) wurden entfernt. Alle externen Links haben ein zusätzliches FontAwesome Icon erhalten. Neben weiteren kleinen Designanpassungen wurden Media-Container, Karten, Navigationsboxen, gesprochene Versionen & Geo-Mikroformate entfernt.


Stand der Informationen: 21.10.2019 09:39:18 CEST - Wichtiger Hinweis Da die gegebenen Inhalte zum angegebenen Zeitpunkt maschinell von Wikipedia übernommen wurden, war und ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.org nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein oder Fehler in der Darstellung vorliegen, bitten wir Sie darum uns per zu kontaktieren: E-Mail.
Beachten Sie auch : Impressum & Datenschutzerklärung.