7.3. Die QR-Iteration

Zum Abschluss wollen wir noch kurz ein Verfahren diskutieren, das alle Eigenwerte einer Matrix auf einmal berechnen kann. Hierbei wollen wir \(A\) durch Transformationen auf obere Dreicksstruktur oder zumindest Blockdreickstruktur bringen, um die Eigenwerte von der Diagonale ablesen zu können. Grundidee dabei ist, dass orthogonale Ähnlichkeitstransformationen die Eigenwerte einer Matrix unverändert lassen. Gilt \(A x = \lambda x\), so folgt für \(y=Qx\) auch

\[\begin{aligned} QAQ^Ty = \lambda y \end{aligned}\]

wegen \(Q^T Q = I\). Es ist also naheliegend einen Zusammenhang zur QR-Zerlegung einer Matrix zu nutzen, die wir stabil mit dem Householder-Verfahren berechnen können. Haben wir eine QR-Zerlegung \(A=QR\) gegeben, so folgt

\[\begin{aligned} Q^T A Q = Q^T (QR) Q = RQ \end{aligned}\]

was auf den QR-Algorithmus führt.

Algorithmus 7.2

Wir starten mit \(A^0 = A\) mit einer gegebenen Matrix \(A\in\C^{n\times n}\). Im \(k\)-ten Schritt berechnen wir die QR-Zerlegung \(A^{(k)} = Q^{(k)} R^{(k)}\) und setzten dann

\[\begin{aligned} A^{(k+1)} &:= R^{(k)} Q^{(k)} = Q^{(k)} A^{(k)} Q^{(k)}. \end{aligned}\]

Unter gewissen Voraussetzungen lässt sich zeigen, dass die QR-Iteration das gewünschte Ergebniss liefert. Der Beweis ist relativ technisch, weshalb wir hier auf die Literatur verweisen.

Satz 7.2

Es sei \(A\in\C^{n\times n}\) eine diagonalisierbare Matrix mit \(A=V \Lambda V^{-1}\) und Eigenwerten \(\abs{\lambda_1} > \abs{\lambda_2} > \ldots \abs{\lambda_n} > 0\). Weiterhin existiere für \(V^{-1}\) eine LR-Zerlegung. Dann konvergiert die Folge \(A^{(k)}\) aus der QR-Iteration Algorithmus 7.2 gegen eine obere Dreicksmatrix, deren Diagonaleinträge die Eigenwerte von \(A\) sind.

Proof. Siehe z.B. [MS19]. ◻

Beispiel 7.4

Wir betrachten als Beispiel die Matrix

\[\begin{aligned} A = \begin{pmatrix} 8 & 1 & 9\\ 1 & 3 & 5\\ 9 & 5 & 4 \end{pmatrix} \end{aligned}\]

und wenden die QR-Iteration darauf an. Nach 10 Iterationen erhalten wir die Matrix

\[\begin{aligned} A^{(10)} \approx \begin{pmatrix} 16.4074456& 0.00006& 0.000009\\ 0.00006& -4.58988353& 1.14034769\\ 0.000009& 1.14034769& 3.18243789 \end{pmatrix} \end{aligned}\]

und nach 50 Iterationen die Matrix

\[\begin{aligned} A^{(50)} \approx \begin{pmatrix} 16.4074456 & 0. & 0.\\ 0. & -4.75373985 & 0.\\ 0. & 0. & 3.34629421 \end{pmatrix} \end{aligned}\]

wobei die Werte auf den Diagonalen approximativ den Eigenwerten von \(A\) entsprechen. Wir konvergieren hier gegen eine Diagonalmatrix, da \(A\) symmetrisch ist.

Falls \(A\in\R^{n\times n}\) eine reelle Matrix ist und wir damit auch reelle QR-Zerlegungen durchführen, \(A\) allerdings auch komplexe Eigenwerte \(\lambda\in\C\) hat, so erhalten wir eine Blockdreickstruktur, wie folgendes Beispiel illustriert.

Beispiel 7.5

Wir wenden nun die QR-Iteration auf die Matrix

\[\begin{aligned} A = \begin{pmatrix} 8&10&9\\ 1&3&5\\ 9&5&4 \end{pmatrix} \end{aligned}\]

an welche auch komplexe Eigenwerte hat. Nach 50 Iterationen erhalten wir die Matrix

\[\begin{aligned} A^{(50)} \approx \begin{pmatrix} 18.0 &-4.5 &-5.7\\ 0. & -1.78 & 4.3\\ 0. &-0.87 &-1.2 \end{pmatrix} \end{aligned}\]

welche keine echte Dreicksstruktur hat. Der obere rechte Eintrag enthält den reellen Eigenwert \(\lambda_1=18\) von \(A\). Der linke untere Block enthält nun die komplexen Eigenwerte von \(A\), in dem Sinne, dass die Submatrix

\[\begin{aligned} \tilde A^{(50)} \approx \begin{pmatrix} -1.78 & 4.3\\ -0.87 &-1.2 \end{pmatrix} \end{aligned}\]

die Eigenwerte \(\lambda_2 \approx -1.5 + 1.9 i, \lambda_3 \approx -1.5 - 1.9 i\) enthält was den komplexen Eigenwerten von \(A\) entspricht. Hat eine Matrix also komplexe Eigenwerte liefert die QR-Iteration jeweils \(2\times 2\)-Blöcke in welche diese Eigenwerte beinhalten.