stabiles Verfahren zur Lösung des Eigenwertproblems Ax = λx für A ∈ ℝ^n×n.

Die Matrix A wird dabei iterativ mittels Ähnlichkeitstransformationen auf obere Dreiecksform S gebracht. Von der Diagonalen von S lassen sich dann die Eigenwerte von A ablesen, das Produkt aller verwendeten Ähnlichkeitstransformationen enthält die Informationen über die zugehörigen Eigenvektoren bzw. invarianten Unterräume.

Der auf Francis (1961) und Kublanovskaja (1961) zurückgehende QR-Algorithmus basiert auf der QR-Zerlegung, d. h. auf der Zerlegung einer Matrix A in das Produkt einer orthogonalen Matrix Q und einer oberen Dreiecksmatrix R. Er berechnet in einem ersten Schritt die Reduktion von A auf eine obere Hessenberg-Form

\begin{eqnarray}{A}^{(k)}\mathop{\to }\limits^{{\beta }_{1}}{A}^{(k+1)}\mathop{\to }\limits^{{\beta }_{2}}{A}^{(k+2)}\end{eqnarray}

nicht explizit, sondern faßt die Berechnungen zusammen und berechnet den Übergang \begin{eqnarray}{A}^{(k)}\mathop{\to }\limits^{{\beta }_{1},{\beta }_{2}}{A}^{(k+2)}\end{eqnarray}

implizit ohne komplexe Zwischenrechnung, denn mit A^(k) ist auch A^(k+2) wieder reell. Dazu nutzt man die folgenden beiden Beobachtungen aus. Es gilt \begin{eqnarray}{A}^{(k+2)}\text{}=\text{}{({Q}^{(k+1)})}^{T}{({Q}^{(k)})}^{T}{A}^{(k)}{Q}^{(k)}{Q}^{(k+1)}\end{eqnarray}

und \begin{eqnarray}{Q}^{(k)}{Q}^{(k+1)}{R}^{(k+1)}{R}^{(k)}\text{}=\text{}({A}^{(k)}\text{}\cdot {\beta }_{2}I)({A}^{(k)}\text{}.\text{}{\beta }_{1}I).\end{eqnarray}

Daraus folgt \begin{eqnarray}\begin{array}{c}(Q^{(k+1)})^{T}(Q^{(k)})^{T}(A^{(k)}\text{}-\beta_{2}I)(A^{(k)}\text{}-\beta_{1}I)e_{1}\\ ={r}_{11}^{(k+1)}{r}_{11}^{(k)}{e}_{1}\end{array}\end{eqnarray} \begin{eqnarray}\end{eqnarray}

mit e₁ = (1,0, …,0)^T ∈ ℝⁿ. In der Praxis berechnet man nun eine orthogonale Matrix \(\tilde{Q}\), welche die erste Spalte von \begin{eqnarray}({A}^{(k)}- \text{}{\beta }_{2}I)({A}^{(k)}\text{}- \text{}{\beta }_{1}I)\end{eqnarray}

auf ein Vielfaches des ersten Einheitsvektors transformiert: \begin{eqnarray}{\tilde{Q}}^{T}({A}^{(k)}\text{}- \text{}{\beta }_{2}I)({A}^{(k)}- {\beta }_{1}I){e}_{1}\text{}=\text{}\alpha {e}_{1},\text{}\alpha \in \text{}{\mathbb{R}}.\end{eqnarray}

Die gegebene obere Hessenberg-Matrix A^(k) wird dann in einem ersten Teilschritt mit der Matrix \(\tilde{Q}\) durch \begin{eqnarray}B={\tilde{Q}}^{T}{A}^{(k)}\tilde{Q}\end{eqnarray}

einer Ähnlichkeitstransformation unterworfen. Anschließend wird B mittels einer orthogonalen Matrix \(\widehat{Q}\) wieder auf Hessenberg-Form \begin{eqnarray}C={\widehat{Q}}^{T}B\widehat{Q}\end{eqnarray}

gebracht. C stimmt im wesentlichen mit A^(k+2) überein, beide unterscheiden sich nur durch eine Ähnlichkeitstransformation mit einer Diagonalmatrix D. Für den QR-Algorithmus ist dies ohne Bedeutung, man setzt daher \({A}^{(k+2)}={\widehat{Q}}^{T}B\widehat{Q}\). In der Praxis verwendet man einen solchen impliziten Doppelschritt auch dann, wenn die (2 × 2)-Matrix in (1) nur reelle Eigenwerte β₁,β₂ hat.

Die Reduktion auf Hessenberg-Form wird wie unter Hessenberg-Form beschrieben durchgeführt. Dabei ist zu beachten, daß aufgrund der Reduktion auf obere Hessenberg-Form im ersten Schritt des QR-Algorithmus jede Iterierte wieder Hessenberg-Form hat. Daher ist die Matrix B keine vollbesetzte Matrix, sie unterscheidet sich nur in zwei Positionen von einer oberen Hessenberg-Matrix: \begin{eqnarray}B=\left(\begin{array}{lllllll}x & x & x & x & \cdots. & x & x\\ x & x & x & x & \cdots & x & x\\ \oplus & x & x & x & \cdots & x & x\\ \oplus & & x & x & \cdots & x & x\\ & & & x & \cdots & x & x\\ & & & & \ddots & \vdots & \vdots \\ & & & & & x & x\end{array}\right).\end{eqnarray}

Die Berechnungen vereinfachen sich daher. Die anfängliche Reduktion auf obere Hessenberg-Form dient der Reduktion des Rechenaufwands pro Iterationsschritt. Abhängig davon, ob man sich bei den Berechnungen zur Reduktion auf Hessenberg-Form auf Householder-Matrizen oder auf Givens-Matrizen stützt, spricht man vom Householderschen QR-Algorithmus oder vom Givensschen QR-Algorithmus.

Der QR-Algorithmus ist auch für komplexe Matrizen A durchführbar. In diesem Falle werden unitäre anstelle der orthogonalen Ähnlichkeitstransformationen verwendet. Die Folge der Iterierten konvergiert dann i. allg. gegen eine obere Dreiecksmatrix.