QR-Algorithmus

Der QR-Algorithmus i​st ein numerisches Verfahren z​ur Berechnung a​ller Eigenwerte u​nd eventuell d​er Eigenvektoren e​iner quadratischen Matrix. Das a​uch QR-Verfahren o​der QR-Iteration genannte Verfahren basiert a​uf der QR-Zerlegung u​nd wurde i​m Jahre 1961–1962 unabhängig voneinander v​on John G. F. Francis u​nd Wera Nikolajewna Kublanowskaja eingeführt. Ein Vorläufer w​ar der LR-Algorithmus v​on Heinz Rutishauser (1958), d​er aber weniger stabil i​st und a​uf der LR-Zerlegung basiert. Oft konvergieren d​ie Iterierten a​us dem QR-Algorithmus g​egen die Schur-Form d​er Matrix. Das originale Verfahren i​st recht aufwendig u​nd damit – selbst a​uf heutigen Rechnern – für Matrizen m​it hunderttausenden Zeilen u​nd Spalten n​icht praktikabel.

Abgeleitete Varianten w​ie das Multishift-Verfahren v​on Z. Bai u​nd James Demmel 1989 u​nd die numerisch stabilere Variante v​on K. Braman, R. Byers u​nd R. Mathias 2002 h​aben praktische Laufzeiten, d​ie kubisch i​n der Größe d​er Matrix sind. Letzteres Verfahren i​st in d​er numerischen Softwarebibliothek LAPACK implementiert, d​ie wiederum i​n vielen Computeralgebrasystemen (CAS) für d​ie numerischen Matrixalgorithmen verwendet wird.

Beschreibung des QR-Algorithmus

Ziel des Rechenverfahrens

Ausgehend von einer reellen oder komplexen Matrix ${\displaystyle A\in \mathbb {R} ^{n\times n}}$ bzw. ${\displaystyle A\in \mathbb {C} ^{n\times n}}$ wird eine Folge orthogonaler oder unitärer Matrizen ${\displaystyle Q_{1},Q_{2},\dots ,}$ bestimmt, so dass die rekursive Matrixfolge ${\displaystyle A_{1}=A,\,A_{2}=Q_{1}^{-1}A_{1}Q_{1},\dots ,A_{k+1}=Q_{k}^{-1}A_{k}Q_{k},\dots }$ weitestgehend gegen eine obere Dreiecksmatrix konvergiert. Da alle Umformungen in der Rekursion Ähnlichkeitstransformationen sind, haben alle Matrizen der Matrixfolge ${\displaystyle A_{1},A_{2},\dots ,}$ dieselben Eigenwerte mit denselben Vielfachheiten.

Wird im Grenzwert eine obere Dreiecksmatrix erreicht, eine Schurform von ${\displaystyle A}$, so lassen sich die Eigenwerte aus den Diagonalelementen ablesen. Im Falle einer reellen Matrix mit orthogonalen Umformungen kann es jedoch auch komplexe Eigenwerte geben. Dann ist das Ergebnis des Verfahrens eine obere Blockdreiecksmatrix, deren Diagonalblöcke die Größe ${\displaystyle 1}$ für die reellen Eigenwerte oder die Größe ${\displaystyle 2}$ für komplexe Eigenwerte haben. Einem Eigenwert ${\displaystyle \lambda =a+ib}$ und seinem konjugiert komplexen Eigenwert entspricht dabei der Diagonalblock der entsprechenden Drehstreckung ${\displaystyle \left({\begin{smallmatrix}a&-b\\b&a\end{smallmatrix}}\right)}$.

Allgemeines Schema des Verfahrens

Ausgehend von einer Matrix ${\displaystyle A_{1}=A\in \mathbb {R} ^{n\times n}}$ (bzw. ${\displaystyle A\in \mathbb {C} ^{n\times n}}$) wird eine Folge von Matrizen ${\displaystyle A_{i}}$ nach folgender Vorschrift bestimmt:

1. for ${\displaystyle i\in \mathbb {N} }$ do
2. Bestimme ein Polynom ${\displaystyle p_{i}}$ und werte es in der Matrix ${\displaystyle A_{i}}$ aus.
3. Berechne die QR-Zerlegung von ${\displaystyle p_{i}(A_{i})=Q_{i}R_{i}}$.
4. Berechne die neue Iterierte: ${\displaystyle A_{i+1}=Q_{i}^{-1}A_{i}Q_{i}}$.
5. end for

In dieser allgemeinen Form können a​uch die Varianten m​it (impliziten) Shifts (engl. für Verschiebung) u​nd Mehrfach-Shifts dargestellt u​nd analysiert werden.

Die Matrixfunktion ${\displaystyle p_{i}}$ ist oft ein Polynom (hier also eine Linearkombination von Matrixpotenzen) mit reellen (bzw. komplexen) Koeffizienten. Im einfachsten Fall wird ein lineares Polynom gewählt, das dann die Gestalt ${\displaystyle p_{i}(A_{i})=A_{i}-\kappa _{i}I}$ hat. Der Algorithmus vereinfacht sich in diesem Fall auf die klassische Version (mit Einfach-Shift):

1. for ${\displaystyle i\in \mathbb {N} }$ do
2. Bestimme eine geeignete Zahl ${\displaystyle \kappa _{i}}$
3. Berechne die QR-Zerlegung von ${\displaystyle A_{i}-\kappa _{i}I=Q_{i}R_{i}}$
4. Berechne die neue Iterierte: ${\displaystyle A_{i+1}=Q_{i}^{-1}A_{i}Q_{i}=Q_{i}^{-1}(Q_{i}R_{i}+\kappa _{i}I)Q_{i}=R_{i}Q_{i}+\kappa _{i}I}$
5. end for

Wird in jedem Iterationsschritt ${\displaystyle \kappa _{i}=0}$ gesetzt, so stimmt das Verfahren mit der auf Unterräume (hier den vollen Vektorraum) erweiterten Potenzmethode überein.

Das die QR-Zerlegung steuernde Polynom kann von Anfang an fixiert sein oder dynamisch in jedem Iterationsschritt der aktuellen Matrix ${\displaystyle A_{i}}$ angepasst werden. Es gibt auch Versuche, für ${\displaystyle p_{i}}$ rationale Matrixfunktionen zu verwenden, d. h. Funktionen der Form ${\displaystyle p(A)=h(A)^{-1}g(A)}$ mit Polynomen ${\displaystyle g}$ und ${\displaystyle h}$.

Deflation

Ergibt es sich in einem Iterationsschritt, dass ein linksunterer Block aus den Spalten ${\displaystyle 1,\dots ,i}$ und deren Zeilen ${\displaystyle i+1,\dots ,n}$ in den Beträgen aller seiner Komponenten eine vorher bestimmte Schwelle unterschreitet, so wird das Verfahren auf den zwei diagonalen quadratischen Teilblöcken der Zeilen/Spalten ${\displaystyle 1,\dots ,i}$ sowie ${\displaystyle i+1,\dots ,n}$ separat fortgesetzt. Sind die durch Teilung entstandenen Matrizen klein genug, so kann die Bestimmung der Eigenwerte z. B. mittels Berechnung des charakteristischen Polynoms und dessen Nullstellen beendet werden.

Transformation auf Hessenberg-Form

Das Ziel des QR-Algorithmus ist es, eine obere Dreiecksform, oder eine Block-Dreiecksform herzustellen, in der Blöcke der Größe ${\displaystyle 2}$ komplexen Eigenwerten entsprechen. Das kann nahezu auf einfache Weise durch eine Ähnlichkeitstransformation auf Hessenberg-Form, d. h. auf eine Matrix mit nur einer (nicht identisch verschwindenden) unteren Nebendiagonalen, erreicht werden.

• Setze ${\displaystyle {\tilde {A}}=A}$
• für k=1 bis n-1 führe aus

1. Bilde das Spaltensegment ${\displaystyle u={\tilde {A}}_{k+1:n,\,k}}$
2. Bestimme die Householder-Spiegelung ${\displaystyle {\tilde {P}}_{k}=I-2vv^{T}}$, die ${\displaystyle u}$ auf den ersten kanonischen Basisvektor abbildet,
3. Führe mit der Blockmatrix ${\displaystyle P_{k}=\left({\begin{smallmatrix}I_{k}&0\\0&{\tilde {P}}_{k}\end{smallmatrix}}\right)}$ die Ersetzung von ${\displaystyle {\tilde {A}}}$ durch die ähnliche Matrix ${\displaystyle P_{k}^{-1}{\tilde {A}}P_{k}=P_{k}{\tilde {A}}P_{k}}$ durch.

• Vermerke die Gesamttransformationsmatrix ${\displaystyle Q_{0}=P_{1}P_{2}\cdots P_{n-1}}$.
• ${\displaystyle A_{1}={\tilde {A}}=Q_{0}^{-1}AQ_{0}}$ befindet sich nun in Hessenberg-Form.

Durch d​ie Hessenberg-Form w​ird die Bestimmung d​er charakteristischen Polynome v​on Teilmatrizen erleichtert. Die Hessenberg-Form e​iner symmetrischen Matrix i​st eine Tridiagonalform, w​as weitere Rechnungen wesentlich beschleunigt.

Weiterhin w​ird in j​edem Schritt d​es QR-Algorithmus d​ie Hessenberg-Form erhalten. Grundlage hierfür i​st die Arithmetik verallgemeinerter Dreiecksmatrizen, b​ei denen a​lle Einträge unterhalb e​iner unteren Nebendiagonalen verschwinden. Eine Hessenberg-Matrix i​st demnach e​ine verallgemeinerte Dreiecksmatrix m​it einer Nebendiagonalen. Unter Multiplikation addieren s​ich die Anzahlen nichtverschwindender Nebendiagonalen, b​ei Addition bleibt m​eist die größere Anzahl erhalten.

Daher haben ${\displaystyle p_{i}(A_{i})}$ wie auch die orthogonale Matrix ${\displaystyle Q_{i}=p_{i}(A_{i})R_{i}^{-1}}$ die Anzahl von ${\displaystyle m=\deg p_{i}}$ unteren Nebendiagonalen. Nun gilt, wegen ${\displaystyle A_{i+1}=Q_{i}^{-1}A_{i}Q_{i}}$, auch

${\displaystyle p_{i}(A_{i+1})=Q_{i}^{-1}p_{i}(A_{i})Q_{i}=R_{i}Q_{i}}$,

und letzteres Produkt hat ebenfalls ${\displaystyle m}$ Nebendiagonalen. Das ist im Allgemeinen nur möglich, wenn ${\displaystyle A_{i+1}}$ genau eine Nebendiagonale aufweist, also wieder in Hessenbergform ist. Aus der Zerlegung von ${\displaystyle P-i(x)}$ in Linearfaktoren folgt (s. unten), dass dies immer der Fall ist.

Man kann darauf aufbauend zeigen (Francis 1962 nach Bai/Demmel), dass schon die erste Spalte ${\displaystyle x}$ von ${\displaystyle p_{i}(A_{i})}$, die auch proportional zur ersten Spalte von ${\displaystyle Q_{i}}$ ist, die nachfolgende Matrix ${\displaystyle A_{i+1}=Q_{i}^{-1}A_{i}Q_{i}}$ vollständig bestimmt. Genauer, ist ${\displaystyle U}$ eine orthogonale Matrix, deren erste Spalte proportional zu ${\displaystyle x}$ ist, so entsteht ${\displaystyle A_{i+1}}$, indem die transformierte Matrix ${\displaystyle U^{-1}A_{i}U}$ wieder in Hessenbergform gebracht wird. Da in ${\displaystyle x}$ nur die Komponenten der Zeilen ${\displaystyle 1,\ldots ,m+1}$ von Null verschieden sind, kann ${\displaystyle U}$ als eine Modifikation der Einheitsmatrix im linksoberen ${\displaystyle s\times s}$-Block sein, mit einem ${\displaystyle s>m}$.

Varianten des QR-Algorithmus

Einfache QR-Iteration

Es wird ${\displaystyle p_{i}(A)=A}$ gewählt. Das Verfahren kann dann kurz als QR-Zerlegung ${\displaystyle A_{i}=Q_{i}R_{i}}$ gefolgt vom Zusammenmultiplizieren ${\displaystyle A_{i+1}=R_{i}Q_{i}}$ in umgekehrter Reihenfolge angegeben werden. Dieses Verfahren ist die direkte Verallgemeinerung der simultanen Potenzmethode zur Bestimmung der ersten ${\displaystyle k}$ Eigenwerte einer Matrix. Dieser Zusammenhang wird bei der Unterraumiteration hergeleitet. Indirekt wird auch eine simultane inverse Potenzmethode ausgeführt.

QR-Algorithmus mit einfachen Shifts

Es wird ${\displaystyle p_{i}(A)=A-\kappa _{i}I}$ gesetzt. Damit kann das Verfahren alternativ auch als QR-Zerlegung ${\displaystyle A_{i}-\kappa _{i}I=Q_{i}R_{i}}$ gefolgt vom um den Shift korrigierten Zusammenmultiplizieren ${\displaystyle A_{i+1}=R_{i}Q_{i}+\kappa _{i}I}$ dargestellt werden. Üblicherweise wird versucht, mit dem Shift ${\displaystyle \kappa _{i}}$ den betragskleinsten Eigenwert zu approximieren. Dazu kann das letzte Diagonalelement ${\displaystyle \kappa _{i}=(A_{i})_{n,n}}$ gewählt werden. Die einfache QR-Iteration ergibt sich, indem alle Shifts zu Null gesetzt werden.

Besitzt ${\displaystyle A_{i}}$ Hessenberg-Form, so muss ${\displaystyle Q_{i}=(A_{i}-\kappa _{i}I)R_{i}^{-1}}$ als Produkt einer Matrix mit und einer Matrix ohne Nebendiagonalen ebenfalls Hessenberg-Form besitzen. Desgleichen gilt daher auch für ${\displaystyle A_{i+1}=R_{i}Q_{i}+\kappa _{i}I}$. Wird also in Vorbereitung des QR-Algorithmus in ${\displaystyle A_{1}=Q_{0}^{-1}AQ_{0}}$ auf Hessenberg-Form gebracht, so bleibt dies während des gesamten Algorithmus erhalten.

Einfache Shifts für symmetrische Matrizen

Eine symmetrische reelle Matrix ${\displaystyle A_{1}=A}$ hat ausschließlich reelle Eigenwerte. Die Symmetrie bleibt während des QR-Algorithmus in allen ${\displaystyle A_{i}}$ erhalten. Für symmetrische Matrizen schlug Wilkinson (1965) vor, denjenigen Eigenwert der rechtsuntersten ${\displaystyle 2\times 2}$-Teilmatrix

${\displaystyle {\begin{pmatrix}a_{n-1,n-1}&a_{n-1,n}\\a_{n,n-1}&a_{n,n}\end{pmatrix}}}$

als Shift zu wählen, der näher an ${\displaystyle a_{n,n}}$ liegt. Wilkinson zeigte, dass die so bestimmte Matrixfolge ${\displaystyle (A_{i})_{i\in \mathbb {N} }}$ gegen eine Diagonalmatrix konvergiert, deren Diagonalelemente die Eigenwerte von ${\displaystyle A=A_{1}}$ sind. Die Konvergenzgeschwindigkeit ist dabei quadratisch.

QR-Algorithmus mit doppelten Shifts

Es k​ann ein Paar v​on einfachen Shifts i​n einem Iterationsschritt zusammengefasst werden. In d​er Konsequenz bedeutet dies, d​ass für reelle Matrizen a​uf komplexe Shifts verzichtet werden kann. In d​er oben angegebenen Notation ist

${\displaystyle (A_{1}-\kappa _{2}I)(A_{1}-\kappa _{1}I)=(A_{1}-\kappa _{2}I)Q_{1}R_{1}=Q_{1}(A_{2}-\kappa _{2}I)R_{1}=Q_{1}Q_{2}R_{2}R_{1}}$

eine QR-Zerlegung für das quadratische Polynom ${\displaystyle p_{1}(x)=x^{2}-(\kappa _{1}+\kappa _{2})x+\kappa _{1}\kappa _{2}}$, ausgewertet in ${\displaystyle A_{1}}$. Die Koeffizienten dieses Polynoms sind auch für ein konjugiertes Paar komplexer Shifts reell. Somit können auch komplexe Eigenwerte reeller Matrizen approximiert werden, ohne dass in der Rechnung komplexe Zahlen auftauchen.

Eine übliche Wahl für diesen Doppelshift besteht aus den Eigenwerten der rechtsuntersten ${\displaystyle 2\times 2}$-Teilmatrix, d. h. das quadratische Polynom ist das charakteristische dieses Blocks,

${\displaystyle p_{i}(x)=x^{2}-(a_{n-1,n-1}+a_{n,n})x+a_{n-1,n-1}a_{n,n}-a_{n-1,n}a_{n,n-1}}$.

QR-Algorithmus mit multiplen Shifts

Es wird eine Zahl ${\displaystyle m}$ größer ${\displaystyle 2}$, aber wesentlich kleiner als die Größe ${\displaystyle n}$ der Matrix ${\displaystyle A}$ festgelegt. Das Polynom ${\displaystyle p_{i}(x)}$ kann als das charakteristische Polynom der rechtsuntersten quadratischen ${\displaystyle m\times m}$-Teilmatrix der aktuellen Matrix ${\displaystyle A_{i}}$ gewählt werden. Eine andere Strategie besteht darin, die ${\displaystyle s>m}$ Eigenwerte der rechtsuntersten ${\displaystyle s\times s}$-Teilmatrix zu bestimmen und die ${\displaystyle m}$ betragskleinsten Eigenwerte ${\displaystyle s_{1},\dots ,s_{m}}$ darunter auszuwählen. Mit diesen wird dann eine QR-Zerlegung von

${\displaystyle p_{i}(A_{i})=(A_{i}-s_{1}I)(A_{i}-s_{2}I)\cdots (A_{i}-s_{m}I)=Q_{i}R_{i}}$ und ${\displaystyle A_{i+1}=Q_{i}^{-1}A_{i}Q_{i}}$

bestimmt.

Mit einem Multishift-Verfahren wird oft erreicht, dass die Komponenten des linksunteren ${\displaystyle (n-m+1,\dots ,n)\times (1,\dots ,n-m)}$-Blocks in der Folge der iterierten Matrizen besonders schnell klein werden und somit eine Aufspaltung des Eigenwertproblems erreicht wird.

Implizite Multishift-Iteration

Das Zusammenfassen mehrfacher Shifts in der allgemeinen Form ist sehr aufwendig. Wie oben angesprochen, kann der Aufwand dadurch verringert werden, dass in einem vorbereitenden Schritt in ${\displaystyle A_{1}=Q_{0}^{-1}AQ_{0}}$ die Hessenberg-Form hergestellt wird. Da jeder Multishift-Schritt aus einzelnen (auch komplexen) Shifts zusammengesetzt werden kann, bleibt die Hessenberg-Form während des gesamten Algorithmus erhalten.

Dadurch k​ann der QR-Algorithmus i​n einen „Bulge-chasing“-Algorithmus umgewandelt werden, d​er eine Delle i​n der Hessenbergform a​m oberen Diagonalenende erzeugt u​nd diese d​ann die Diagonale herunter u​nd am unteren Ende a​us der Matrix „jagt“.

1. for ${\displaystyle j\in \mathbb {N} _{0}}$ do
2. Berechne das Polynom ${\displaystyle p(x)}$ nach einer der angegebenen Varianten,
3. Bestimme den Vektor ${\displaystyle x=p(A_{j})e_{1}}$.
4. Bestimme eine Spiegelung von ${\displaystyle x}$ auf den ersten Einheitsvektor. Da in ${\displaystyle x}$ nur die ersten ${\displaystyle m+1}$ Komponenten nicht verschwinden, hat diese Spiegelung eine einfache Blockgestalt.
5. Bilde die Matrix ${\displaystyle {\tilde {A}}=U^{-1}A_{j}U}$ und transformiere sie so, dass ${\displaystyle A_{j+1}=Q^{-1}U^{-1}A_{j}UQ}$ wieder in Hessenberg-Form ist.
6. end for

Wird ${\displaystyle Q}$ aus Householder-Spiegelungen zusammengesetzt, ${\displaystyle Q=P_{1}P_{2}\cdots P_{n-1}}$, so haben diese Blockdiagonalgestalt ${\displaystyle P_{k}=\mathrm {diag} (I_{k},{\tilde {P}}_{k},I_{\max(0,n-k-m)})}$.

Anmerkungen zur Funktionsweise

Ähnlichkeitstransformationen

Die im QR-Algorithmus berechneten Matrizen sind zueinander unitär ähnlich, da aufgrund von ${\displaystyle A_{i}-\kappa _{i}I=Q_{i}R_{i}\quad \Leftrightarrow \quad R_{i}=Q_{i}^{H}(A_{i}-\kappa _{i}I)}$

${\displaystyle A_{i+1}=R_{i}Q_{i}+\kappa _{i}I=Q_{i}^{H}(A_{i}-\kappa _{i}I)Q_{i}+\kappa _{i}I=Q_{i}^{H}A_{i}Q_{i}-\kappa _{i}Q_{i}^{H}Q_{i}+\kappa _{i}I=Q_{i}^{H}A_{i}Q_{i}}$

gilt. Damit haben alle Matrizen ${\displaystyle A_{i}}$ dieselben Eigenwerte (mit der algebraischen und geometrischen Vielfachheit gezählt).

Wahl der Shifts, Konvergenz

Eine einfache, aber nicht sehr effektive Wahl ist die Wahl von Shifts identisch Null. Die Iterierten ${\displaystyle A_{i}}$ des resultierenden Algorithmus, des QR-Algorithmus in der Grundform, konvergieren teilweise, wenn sich alle Eigenwerte dem Betrage nach unterscheiden, gegen eine obere Dreiecksmatrix mit den Eigenwerten auf der Diagonalen. Teilweise Konvergenz bedeutet hier, dass die Elemente des unteren Dreiecks von ${\displaystyle A_{i}}$ gegen Null gehen und die Diagonalelemente gegen die Eigenwerte. Über die Elemente im oberen Dreieck wird also nichts ausgesagt.

Werden die Shifts als das Matrixelement unten rechts der aktuellen Iterierten gewählt, also ${\displaystyle \kappa _{i}=a_{nn}^{(i)}}$, so konvergiert der Algorithmus unter geeigneten Umständen quadratisch oder sogar kubisch. Dieser Shift ist als Rayleigh-Quotienten-Shift bekannt, da er über die Inverse Iteration mit einem Rayleigh-Quotienten im Zusammenhang steht.

Bei der Rechnung im Reellen (${\displaystyle A\in \mathbb {R} ^{n\times n}}$) möchte man die reelle Schur-Form berechnen und trotzdem mit konjugiert komplexen Eigenwerten arbeiten können. Dazu gibt es verschiedene Shift-Strategien.

Eine Erweiterung von einfachen Shifts ist der nach James Hardy Wilkinson benannte Wilkinson-Shift. Für den Wilkinson-Shift wird der näher am letzten Matrixelement liegende Eigenwert der letzten ${\displaystyle 2\times 2}$ Hauptunterabschnittsmatrix

${\displaystyle {\begin{pmatrix}a_{n-1,n-1}^{(i)}&a_{n-1,n}^{(i)}\\a_{n,n-1}^{(i)}&a_{n,n}^{(i)}\end{pmatrix}}}$

verwendet.

Der QR-Algorithmus als Erweiterung der Potenzmethode

Zur Analyse des Algorithmus werden die zusätzlichen Matrixfolgen der kumulierten Produkte ${\displaystyle {\tilde {Q}}_{k}=Q_{1}Q_{2}\cdots Q_{k}}$ und ${\displaystyle {\tilde {R}}_{k}=R_{k}R_{k-1}\cdots R_{2}R_{1}}$, ${\displaystyle k\in \mathbb {N} }$ definiert. Dabei sind die Produkte ${\displaystyle {\tilde {Q}}_{k}}$ von orthogonalen bzw. unitären Matrizen wieder orthogonale bzw. unitäre Matrizen, genauso sind die Produkte ${\displaystyle {\tilde {R}}_{k}}$ von rechtsoberen Dreiecksmatrizen wieder rechtsobere Dreiecksmatrizen. Die Matrizen der QR-Iteration ergeben sich durch Ähnlichkeitstransformationen aus ${\displaystyle A}$, denn

${\displaystyle A_{1}=A,\;A_{2}=R_{1}Q_{1}=Q_{1}^{-1}A_{1}Q_{1},\;A_{3}=Q_{2}^{-1}A_{2}Q_{2}={\tilde {Q}}_{2}^{-1}A{\tilde {Q}}_{2},\dots ,\;A_{k}={\tilde {Q}}_{k}^{-1}A{\tilde {Q}}_{k},\dots }$.

Daraus folgert man auf QR-Zerlegungen der Potenzen von ${\displaystyle A}$:

${\displaystyle {\begin{aligned}A=&&&Q_{1}R_{1}&=&{\tilde {Q}}_{1}{\tilde {R}}_{1}\\A^{2}=&AQ_{1}R_{1}=Q_{1}A_{2}R_{1}&=&Q_{1}Q_{2}R_{2}R_{1}&=&{\tilde {Q}}_{2}{\tilde {R}}_{2}\\\vdots &\\A^{k}=&A{\tilde {Q}}_{k-1}{\tilde {R}}_{k-1}={\tilde {Q}}_{k-1}A_{k}{\tilde {R}}_{k-1}&=&{\tilde {Q}}_{k-1}Q_{k}R_{k}{\tilde {R}}_{k-1}&=&{\tilde {Q}}_{k}{\tilde {R}}_{k}\end{aligned}}}$

Es werden also im Verlaufe des Algorithmus implizit QR-Zerlegungen der Potenzen der Matrix ${\displaystyle A}$ bestimmt. Aufgrund der Form dieser Zerlegungen gilt, dass für jedes ${\displaystyle j=1,2,\ldots ,n}$ die ersten ${\displaystyle j}$ Spalten der Matrix ${\displaystyle A^{k}}$ denselben Unterraum aufspannen wie die ersten ${\displaystyle j}$ Spalten der Matrix ${\displaystyle {\tilde {Q}}_{k}}$; zusätzlich sind die Spalten von ${\displaystyle {\tilde {Q}}_{k}}$ orthonormal zueinander. Dieses jedoch ist genau die Situation nach dem ${\displaystyle k}$-ten Schritt einer simultanen Potenziteration. Die Diagonalelemente von ${\displaystyle R_{k}}$ sind wegen ${\displaystyle A{\tilde {Q}}_{k-1}={\tilde {Q}}_{k}R_{k}}$ die Approximationen der Eigenwerte von ${\displaystyle A}$. Daher lassen sich die Konvergenzeigenschaften der Potenziteration übertragen:

Der einfache QR-Algorithmus konvergiert nur, w​enn alle Eigenwerte i​n ihren Beträgen voneinander verschieden sind. Sind d​ie Eigenwerte nach

${\displaystyle |\lambda _{1}|<|\lambda _{2}|<\dots <|\lambda _{n}|}$

sortiert, so ist die Konvergenzgeschwindigkeit linear mit einem Kontraktionsfaktor, der dem Minimum der Quotienten ${\displaystyle {\tfrac {|\lambda _{k}|}{|\lambda _{k+1}|}}}$ entspricht.

Insbesondere für reelle Matrizen k​ann dieser Algorithmus n​ur konvergieren, w​enn alle Eigenwerte r​eell sind (da s​onst konjugiert komplexe Paare m​it gleichem Betrag existieren würden). Diese Situation i​st für a​lle symmetrischen Matrizen gegeben.

Der QR-Algorithmus als simultane inverse Potenziteration

Es gilt, falls ${\displaystyle A}$ invertierbar ist, für die Transponierte (für komplexe Matrizen die hermitesch Adjungierte) der Inversen von ${\displaystyle A}$ und alle ihre Potenzen

${\displaystyle (A^{-T})^{k}=(A^{k})^{-T}=({\tilde {R}}_{k}^{-1}{\tilde {Q}}_{k}^{-1})^{T}={\tilde {Q}}_{k}{\tilde {R}}_{k}^{-T}}$

Die Inverse einer rechtsoberen Dreiecksmatrix ist wieder eine rechtsobere Dreiecksmatrix, deren Transponierte eine linksuntere Dreiecksmatrix. Damit bestimmt der QR-Algorithmus auch eine QL-Zerlegung der Potenzen von ${\displaystyle A^{-T}}$. Aus der Form dieser Zerlegung erhellt, dass für jedes ${\displaystyle j=1,2,\ldots ,n}$ die letzten ${\displaystyle j}$ Spalten von ${\displaystyle {\tilde {Q}}_{k}}$ denselben Unterraum aufspannen wie die letzten ${\displaystyle j}$ Spalten von ${\displaystyle (A^{-T})^{k}}$. In der letzten Spalte von ${\displaystyle {\tilde {Q}}_{k}}$ wird somit eine inverse Potenziteration für ${\displaystyle A^{T}}$ durchgeführt, diese Spalte konvergiert also gegen den dualen Eigenvektor zum kleinsten Eigenwert von ${\displaystyle A}$. Im Produkt ${\displaystyle {\tilde {Q}}_{k}^{T}A{\tilde {Q}}_{k}=A_{k}}$ ist also die linke untere Komponente ${\displaystyle (A_{k})_{nn}}$ der sog. Rayleigh-Quotient der inversen Potenziteration. Die Konvergenzeigenschaften sind analog zum oben angegebenen.

Weblinks

• LP: QR-Verfahren für allgemeine EWP, Georg-August-Universität Göttingen

Literatur

• Gisela Engeln-Müllges, Klaus Niederdrenk, Reinhard Wodicka: Numerik-Algorithmen. 10. Auflage. Springer-Verlag, Berlin, Heidelberg 2011, ISBN 978-3-642-13472-2, Abschnitt 7.6 'Bestimmung der Eigenwerte positiv definiter, symmetrischer, tridiagonaler Matrizen mit Hilfe des QD-Algorithmus' und 7.7 'Transformationen auf Hessenbergform, LR- und QR-Verfahren'.
• J. G. F. Francis (1961): The QR Transformation: A Unitary Analogue to the LR Transformation—Part 1. The Computer Journal Vol. 4(3), S. 265–271. doi:10.1093/comjnl/4.3.265
• J. G. F. Francis (1962): The QR Transformation—Part 2. The Computer Journal 1962 4(4):332-345; (online)
• David S. Watkins (1982): Understanding the QR algorithm, SIAM Review, Vol. 24, S. 427–440 (JSTOR)
• Z. Bai; J. Demmel (1989): On a block implementation of Hessenberg multishift QR iteration, International Journal of High Speed Computing, Vol. 1(1), S. 97–112. (siehe LAPACK Working Notes)
• A. A. Dubrulle; G. H. Golub (1994): A multishift QR iteration without computation of the shifts. Numerical Algorithms, Vol 7, S. 173–181
• K. Braman; R. Byers; R. Mathias (2002): The Multishift QR Algorithm. Part I: Maintaining Well-Focused Shifts and Level 3 Performance (PDF; 224 kB). SIAM Journal on Matrix Analysis and Applications, Vol. 23, No. 4, S. 929–947
• K. Braman; R. Byers; R. Mathias (2002): The Multishift QR Algorithm. Part II: Aggressive Early Deflation (PDF; 265 kB). SIAM Journal on Matrix Analysis and Applications, Vol. 23, No. 4, S. 948–989
• David S. Watkins : The QR algorithm revisited (PDF; 417 kB) , SIAM Review, Vol. 50, No. 1, S. 133–145
• M. Hermann: Numerische Mathematik, Band 1: Algebraische Probleme. 4., überarbeitete und erweiterte Auflage. Walter de Gruyter Verlag, Berlin und Boston 2020. ISBN 978-3-11-065665-7.