QR-Zerlegung

Matrix-Zerlegung in ein Produkt zweier spezieller Matrizen

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

zweier anderer Matrizen, wobei eine orthogonale () bzw. unitäre Matrix () und 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.

DefinitionBearbeiten

Eine Matrix  ,   besitzt eine (fast – siehe weiter unten) eindeutige reduzierte QR-Zerlegung

 

als Produkt einer in den Spalten orthogonalen Matrix   und einer oberen Dreiecksmatrix  

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

 ,

indem man   mit weiteren orthogonalen Spalten   zu einer quadratischen  -Matrix erweitert, und an   unten Nullzeilen anfügt, so dass als Produkt eine  -Matrix entsteht:

 

Die QR-Zerlegung ist eindeutig für   und  , wenn man die Vorzeichen der Diagonalelemente von   vorgibt – üblicherweise wählt man alle positiv.

AnwendungBearbeiten

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 GleichungssystemeBearbeiten

Um die Lösung   eines linearen Gleichungssystems mit Matrix  ,

  von vollem Rang zu bestimmen, sind folgende drei Schritte durchzuführen:
  1. Bestimme eine QR-Zerlegung der Matrix  .
  2. Berechne  , üblicherweise unter Benutzung der Faktorisierung von   aus Schritt 1.
  3. Löse   durch Rückwärtseinsetzen.

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

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

Minimiere  .

In diesem Fall ist   die Moore-Penrose-Pseudoinverse von   und für die berechnete Kleinste-Quadrate-Lösung   gilt die Beziehung  , die die übliche Darstellung   des regulären Falls   verallgemeinert.

Lösung unterbestimmter GleichungssystemeBearbeiten

Für   hat die Matrix   einen nichttrivialen Kern. Bei vollem Rang von   bilden die Lösungen des Gleichungssystems   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  :

  1. Bestimme eine QR-Zerlegung der Matrix  .
  2. Löse   durch Vorwärtseinsetzen.
  3. Berechne  .

Auch hier ist wieder   die Moore-Penrose-Pseudoinverse von   und für die berechnete Lösung kleinster Norm gilt die Beziehung  .

WeblinksBearbeiten