Direkt zum Inhalt

Lexikon der Mathematik: QR-Zerlegung

Zerlegung einer Matrix A ∈ ℝm×n in ein Produkt A = QR, wobei Q ∈ ℝm×m orthogonal und R ∈ ℝm×n eine obere Dreiecksmatrix ist.

Hat A vollen Spaltenrang, also Rang(A) = n, so existiert eine QR-Zerlegung A = QR mit rii > 0. Diese Zerlegung ist eindeutig.

Das Ergebnis einer Orthonormalisierung von n gegebenen Vektoren xj ∈ ℝm kann als QR-Zerlegung der Matrix X = (x1, x2, …, xn) ∈ ℝm×n interpretiert werden.

Eine häufig verwendete Möglichkeit der Berechnung einer QR-Zerlegung besteht in der Verwendung von Householder-Matrizen \begin{eqnarray}Q=I-2v{v}^{T}\end{eqnarray}

mit vT v = 1.

Mit Hilfe der Householder-Matrizen kann man eine Matrix A = (a1, …, an) ∈ ℝm×n in eine obere Dreiecksmatrix transformieren, indem sukzessive die Elemente unterhalb der Diagonalen eliminiert werden. Im ersten Schritt werden die Elemente der ersten Spalte von A unterhalb des Diagonalelementes a11 eliminiert gemäß \begin{eqnarray}{A}^{(1)}:={Q}^{(1)}A=\left(\begin{array}{llll}{\alpha }_{1} & & & \\ 0 & & & \\ \vdots & {\alpha }_{2}^{(k)} & \cdots & {\alpha }_{n}^{(k)}\\ 0 & & & \end{array}\right),\end{eqnarray}

wobei \({Q}^{(1)}=I-2{v}_{1}{v}_{1}^{T}\) mit \begin{eqnarray}{v}_{1}=\frac{1}{{\Vert {a}_{1}-{\lambda }_{1}{e}_{1}\Vert }_{2}}.({a}_{1}-{\lambda }_{1}{e}_{1})\end{eqnarray}

und λ1 = −sgn(a11)∥a12, falls a11 ≠ 0, sonst λ1 = −∥a12. Im zweiten Schritt werden nun ganz analog die Elemente der zweiten Spalte von A(1) unterhalb des Diagonalelementes a22 eliminiert: \begin{eqnarray}\begin{array}{lll}{A}^{(2)} & := & {Q}^{(2)}{A}^{(1)}\\ & = & \left(\begin{array}{lllll}{\alpha }_{1} & {\alpha }_{2} & & & \\ 0 & {\alpha }_{3} & & & \\ 0 & 0 & & & \\ \vdots & \vdots & {a}_{3}^{(k+1)} & \cdots & {a}_{n}^{(k+1)}\\ 0 & 0 & & & \end{array}\right)\end{array}.\end{eqnarray}

Nach dem k-ten Schritt hat man somit die Ausgangsmatrix A bis auf eine Restmatrix T(k+1) ∈ ℝ(mk)×(nk) auf obere Dreiecksgestalt gebracht, \begin{eqnarray}{A}^{(k)}=\left(\begin{array}{lllll}* & \cdots & \cdots & \cdots & * \\ & \ddots & & & \vdots \\ & & * & \cdots & * \\ & & 0 & & \\ & & \vdots & {T}^{(k+1)} & \\ & & 0 & & \end{array}\right).\end{eqnarray}

Bildet man nun die orthogonale Matrix

Abbildung 1 zum Lexikonartikel QR-Zerlegung
© Springer-Verlag GmbH Deutschland 2017
 Bild vergrößern

wobei \({\overline{Q}}^{(k+1)}\in {{\mathbb{R}}}^{(m-k)\times (m-k)}\) wie im ersten Schritt mit T(k+1) anstelle von A konstruiert wird, so kann man die nächste Subspalte unterhalb der Diagonalen eliminieren. Insgesamt erhält man so nach p = min(m − 1, n) Schritten die obere Dreiecksmatrix \begin{eqnarray}R={Q}^{(p)}\cdots {Q}^{(1)}A,\end{eqnarray}

und daher wegen (Q(j))2 = I die Zerlegung \begin{eqnarray}\begin{array}{ccc}A=QR & \,\text{f}{\rm\ddot{u}}\text{r}\, & Q={Q}^{(1)}\cdots {Q}^{(p)}.\end{array}\end{eqnarray}

Für den Aufwand gilt bei dieser Methode

a) ∼ 2n2m Multiplikationen, falls mn,

b) \(\sim\frac{2}{3}{n}^{3}\) Multiplikationen, falls mn.

Eine andere Möglichkeit zur Berechnung einer QR-Zerlegung von A besteht in der Anwendung von Givens-Matrizen (Jacobi-Rotationsmatrix) Gkℓ zur sukzessiven spaltenweisen Elimination der Einträge unterhalb der Diagonalen von A. Dabei wird Gkℓ so gewählt, daß in GkℓA ein gewisses Element in der k-ten Zeile zu Null wird. Am Beispiel einer vollbesetzten (5 × 4)-Matrix läßt sich der Algorithmus wie folgt veranschaulichen (die Indexpaare (k,ℓ) über den Pfeilen geben die Indizes der ausgeführten Givens-Rotation Gkℓ an): \begin{eqnarray}A=\left(\begin{array}{llll}* & * & * & * \\ * & * & * & * \\ * & * & * & * \\ * & * & * & * \\ * & * & * & * \end{array}\right)\mathop{\to }\limits^{(5,4)}\left(\begin{array}{llll}* & * & * & * \\ * & * & * & * \\ * & * & * & * \\ * & * & * & * \\ 0 & * & * & * \end{array}\right)\end{eqnarray}\begin{eqnarray}\mathop{\to }\limits^{(4,3)}\left(\begin{array}{llll}* & * & * & * \\ * & * & * & * \\ * & * & * & * \\ 0 & * & * & * \\ 0 & * & * & * \end{array}\right)\mathop{\to }\limits^{(3,2)}\ldots \mathop{\to }\limits^{(2,1)}\left(\begin{array}{llll}* & * & * & * \\ 0 & * & * & * \\ 0 & * & * & * \\ 0 & * & * & * \\ 0 & * & * & * \end{array}\right)\end{eqnarray}\begin{eqnarray}\mathop{\to }\limits^{(5,4)}\left(\begin{array}{llll}* & * & * & * \\ 0 & * & * & * \\ 0 & * & * & * \\ 0 & * & * & * \\ 0 & 0 & * & * \end{array}\right)\mathop{\to }\limits^{(4,3)}\ldots \mathop{\to }\limits^{(5,4)}\left(\begin{array}{llll}* & * & * & * \\ 0 & * & * & * \\ 0 & 0 & * & * \\ 0 & 0 & 0 & * \\ 0 & 0 & 0 & 0\end{array}\right).\end{eqnarray}

Allgemein erhält man

Für k = 1, …, n

Für = m, m − 1, …, k + 1

Berechne Gℓ,ℓ−1 so daß (Gℓ,ℓ−1A), k = 0.

Berechne A := Gℓ,ℓ−1A.

Ende Für

Ende Für

Setze QT = Gm, m−1Gm−1, m−2Gm, m−1.

Dies berechnet \begin{eqnarray}\begin{array}{ccc}{Q}^{T}A=\left(\begin{array}{c}R\\ 0\end{array}\right) & \text{und} & {Q}^{T}Q=I.\end{array}\end{eqnarray}

In der Praxis werden nicht die (m × m)-Matrizen Gℓ,ℓ−1 aufgestellt, sondern nur die entsprechenden Umformungen der Elemente von A in der -ten und ( − 1)-ten Zeile vorgenommen.

Als Aufwand für die QR-Zerlegung einer vollbesetzten Ausgangsmatrix A ∈ ℝm×n erhält man hier

a) ∼ mn Quadratwurzeln und ∼ 2mn2 Multiplikationen, falls mn,

b) ∼ n2 /2 Quadratwurzeln und ∼ 4n3 /3 Multiplikationen, falls mn.

Für Matrizen A ∈ ℂ m×n existiert ebenfalls eine QR-Zerlegung A = QR, wobei Q ∈ ℂm×m unitär und R ∈ ℂm×n eine obere Dreiecksmatrix ist. Sie wird analog zum obigen Vorgehen berechnet. Man verwendet die komplexen Varianten der Householderoder Givens-Matrizen.

Die QR-Zerlegung kann zur direkten Lösung linearer Gleichungssysteme Ax = b verwendet werden. Sie hat große Bedeutung bei der Lösung des linearen Ausgleichsproblems ||Axb||2 mittels der Methode der kleinsten Quadrate und des Eigenwertproblems Ax = λx mittels des QR-Algorithmus’.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos