Direkt zum Inhalt

Lexikon der Mathematik: QR-Algorithmus

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 e1 = (1,0, …,0)T ∈ ℝn. 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 β1,β2 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.

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