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 r_ii > 0. Diese Zerlegung ist eindeutig.

Das Ergebnis einer Orthonormalisierung von n gegebenen Vektoren x_j ∈ ℝ^m kann als QR-Zerlegung der Matrix X = (x₁, x₂, …, x_n) ∈ ℝ^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 v^T v = 1.

Mit Hilfe der Householder-Matrizen kann man eine Matrix A = (a₁, …, a_n) ∈ ℝ^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 a₁₁ 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 λ₁ = −sgn(a₁₁)∥a₁∥₂, falls a₁₁ ≠ 0, sonst λ₁ = −∥a₁∥₂. Im zweiten Schritt werden nun ganz analog die Elemente der zweiten Spalte von A⁽¹⁾ unterhalb des Diagonalelementes a₂₂ 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) ∈ ℝ^{(m−k)×(n−k)} 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

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))² = 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) ∼ 2n²m Multiplikationen, falls m ≫ n,

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

Eine andere Möglichkeit zur Berechnung einer QR-Zerlegung von A besteht in der Anwendung von Givens-Matrizen (Jacobi-Rotationsmatrix) G_kℓ zur sukzessiven spaltenweisen Elimination der Einträge unterhalb der Diagonalen von A. Dabei wird G_kℓ so gewählt, daß in G_kℓ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 G_kℓ 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 Q^T = G_{m, m−1} …G_{m−1, m−2}G_{m, 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 ∼ 2mn² Multiplikationen, falls m ≫ n,

b) ∼ n² /2 Quadratwurzeln und ∼ 4n³ /3 Multiplikationen, falls m ≈ n.

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 GleichungssystemeAx = b verwendet werden. Sie hat große Bedeutung bei der Lösung des linearen Ausgleichsproblems ||Ax − b||₂ mittels der Methode der kleinsten Quadrate und des Eigenwertproblems Ax = λx mittels des QR-Algorithmus’.