imported>Alex Writer WEH: /* growthexperiments-addlink-summary-summary:1|0|0 */

2025-06-21T16:18:18Z

growthexperiments-addlink-summary-summary:1|0|0

Neue Seite

{{Dieser Artikel|behandelt ein Verfahren, das nicht im Zusammenhang mit der Erzeugung des mit derselben Abkürzung benannten [[QR-Code]]s steht.}}
Der '''QR-Algorithmus''' ist ein [[Numerische Mathematik|numerisches]] Verfahren zur Berechnung aller [[Eigenwert]]e und eventuell der Eigenvektoren einer quadratischen [[Matrix (Mathematik)|Matrix]]. Das auch QR-Verfahren oder QR-Iteration genannte Verfahren basiert auf der [[QR-Zerlegung]] und wurde in den Jahren 1961 und 1962 unabhängig voneinander von [[John G. F. Francis]] und [[Wera Nikolajewna Kublanowskaja]] eingeführt. Ein Vorläufer war der [[LR-Algorithmus]] von [[Heinz Rutishauser]] (1958), der aber weniger stabil ist und auf der [[Gaußsches Eliminationsverfahren|LR-Zerlegung]] basiert. Oft konvergieren die Iterierten aus dem QR-Algorithmus gegen die [[Schur-Zerlegung|Schur-Form]] der Matrix. Das originale Verfahren ist recht aufwendig und damit – selbst auf heutigen Rechnern – für Matrizen mit hunderttausenden Zeilen und Spalten nicht praktikabel.

Abgeleitete Varianten wie das Multishift-Verfahren von Z. Bai und [[James Demmel]] 1989 und die numerisch stabilere Variante von K. Braman, R. Byers und R. Mathias 2002 haben praktische Laufzeiten, die kubisch in der Größe der Matrix sind. Letzteres Verfahren ist in der numerischen Softwarebibliothek [[LAPACK]] implementiert, die wiederum in vielen Computeralgebrasystemen (CAS) für die numerischen Matrixalgorithmen verwendet wird.

== Beschreibung des QR-Algorithmus ==
=== Ziel des Rechenverfahrens ===

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

Wird im Grenzwert eine obere Dreiecksmatrix erreicht, eine [[Schurform]] von <math>A</math>, 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 <math>1</math> für die reellen Eigenwerte oder die Größe <math>2</math> für komplexe Eigenwerte haben. Einem Eigenwert <math>\lambda=a+\mathrm{i} b</math> und seinem konjugiert komplexen Eigenwert entspricht dabei der Diagonalblock der entsprechenden Drehstreckung <math>\left(\begin{smallmatrix}a&-b\\b&a\end{smallmatrix}\right)</math>.

=== Allgemeines Schema des Verfahrens ===
Ausgehend von einer Matrix <math>A_1=A\in\R^{n\times n}</math> (bzw. <math>A\in\mathbb{C}^{n\times n}</math>) wird eine Folge von Matrizen <math>A_i</math> nach folgender Vorschrift bestimmt:

# for <math>i\in\mathbb{N}</math> do
# Bestimme ein [[Polynom]] <math>p_i</math> und werte es in der Matrix <math>A_i</math> aus.
# Berechne die [[QR-Zerlegung]] von <math>p_i(A_i)=Q_iR_i</math>.
# Berechne die neue Iterierte: <math>A_{i+1}=Q_i^{-1}A_iQ_i</math>.
# end for

In dieser allgemeinen Form können auch die Varianten mit (impliziten) Shifts (engl. für Verschiebung) und Mehrfach-Shifts dargestellt und analysiert werden.

Die Matrixfunktion <math>p_i</math> 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 <math>p_i(A_i)=A_i-\kappa_iI</math> hat. Der Algorithmus vereinfacht sich in diesem Fall auf die ''klassische Version'' (mit Einfach-Shift):

# for <math>i\in\mathbb{N}</math> do
# Bestimme eine geeignete Zahl <math>\kappa_i</math>
# Berechne die [[QR-Zerlegung]] von <math>A_i-\kappa_iI=Q_iR_i</math>
# Berechne die neue Iterierte: <math>A_{i+1}=Q_i^{-1}A_iQ_i=Q_i^{-1}(Q_iR_i+\kappa_iI)Q_i=R_iQ_i+\kappa_iI</math>
# end for

Wird in jedem Iterationsschritt <math>\kappa_i=0</math> 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 <math>A_i</math> angepasst werden. Es gibt auch Versuche, für <math>p_i</math> rationale Matrixfunktionen zu verwenden, d. h. Funktionen der Form <math>p(A)=h(A)^{-1}g(A)</math> mit Polynomen <math>g</math> und <math>h</math>.

=== Deflation ===
Ergibt es sich in einem Iterationsschritt, dass ein linksunterer Block aus den Spalten <math>1,\dots,i</math> und deren Zeilen <math>i+1,\dots,n</math> 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 <math>1,\dots,i</math> sowie <math>i+1,\dots,n</math> separat fortgesetzt. Sind die durch Teilung entstandenen Matrizen klein genug, so kann die Bestimmung der Eigenwerte z. B. mittels Berechnung des [[Charakteristisches Polynom|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 <math>2</math> komplexen Eigenwerten entsprechen. Das kann nahezu auf einfache Weise durch eine Ähnlichkeitstransformation auf [[Hessenbergform|Hessenberg-Form]], d. h. auf eine Matrix mit nur einer (nicht identisch verschwindenden) unteren Nebendiagonalen, erreicht werden.

* Setze <math>\tilde A=A</math>
* für <math>k=1</math> bis <math>n-1</math> führe aus
:# Bilde das Spaltensegment <math>u=\tilde A_{k+1:n,\,k}</math>
:# Bestimme die Householder-Spiegelung <math>\tilde P_k=I-2vv^\mathrm{T}</math>, die <math>u</math> auf den ersten kanonischen Basisvektor abbildet
:# Führe mit der [[Blockmatrix]] <math>P_k=\left(\begin{smallmatrix}I_k&0\\0& \tilde P_k\end{smallmatrix}\right)</math> die Ersetzung von <math>\tilde A</math> durch die ähnliche Matrix <math>P_k^{-1}\tilde AP_k=P_k\tilde AP_k</math> durch.
* Vermerke die Gesamttransformationsmatrix <math>Q_0=P_1P_2\cdots P_{n-1}</math>.
* <math>A_1=\tilde A=Q_0^{-1}AQ_0</math> befindet sich nun in Hessenberg-Form.

Durch die Hessenberg-Form wird die Bestimmung der charakteristischen Polynome von [[Teilmatrix|Teilmatrizen]] erleichtert. Die Hessenberg-Form einer [[Symmetrische Matrix|symmetrischen Matrix]] hat eine [[Tridiagonalmatrix|Tridiagonalform]], was weitere Rechnungen wesentlich beschleunigt.

Weiterhin wird in jedem Schritt des QR-Algorithmus die Hessenberg-Form erhalten. Grundlage hierfür ist die Arithmetik verallgemeinerter Dreiecksmatrizen, bei denen alle Einträge unterhalb einer unteren Nebendiagonalen verschwinden. Eine Hessenberg-Matrix ist demnach eine verallgemeinerte Dreiecksmatrix mit einer Nebendiagonalen. Unter Multiplikation addieren sich die Anzahlen nichtverschwindender Nebendiagonalen, bei Addition bleibt meist die größere Anzahl erhalten.

Daher haben <math>p_i(A_i)</math> sowie die orthogonale Matrix <math>Q_i=p_i(A_i)R_i^{-1}</math> die Anzahl von <math>m=\deg p_i</math> unteren Nebendiagonalen. Nun gilt wegen <math>A_{i+1}=Q_i^{-1}A_iQ_i</math> auch
:<math>p_i(A_{i+1})=Q_i^{-1}p_i(A_i)Q_i=R_iQ_i</math>,
und letzteres Produkt hat ebenfalls <math>m</math> Nebendiagonalen. Das ist im Allgemeinen nur möglich, wenn <math>A_{i+1}</math> genau eine Nebendiagonale aufweist, also wieder in Hessenbergform ist. Aus der Zerlegung von <math>p_i</math> 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 <math>x</math> von <math>p_i(A_i)</math>, die auch proportional zur ersten Spalte von <math>Q_i</math> ist, die nachfolgende Matrix <math>A_{i+1}=Q_i^{-1}A_iQ_i</math> vollständig bestimmt. Genauer: Ist <math>U</math> eine [[orthogonale Matrix]], deren erste Spalte proportional zu <math>x</math> ist, so entsteht <math>A_{i+1}</math>, indem die transformierte Matrix <math>U^{-1}A_iU</math> wieder in Hessenbergform gebracht wird. Da in <math>x</math> nur die Komponenten der Zeilen <math>1, \ldots ,m+1</math> von Null verschieden sind, kann <math>U</math> als eine Modifikation der [[Einheitsmatrix]] im linksoberen <math>s\times s</math>-Block sein, mit einem <math>s > m</math>.

== Varianten des QR-Algorithmus ==
=== Einfache QR-Iteration ===
Es wird <math>p_i(A)=A</math> gewählt. Das Verfahren kann dann kurz als QR-Zerlegung <math>A_i=Q_iR_i</math> gefolgt vom Zusammenmultiplizieren <math>A_{i+1}=R_iQ_i</math> in umgekehrter Reihenfolge angegeben werden. Dieses Verfahren ist die direkte Verallgemeinerung der simultanen Potenzmethode zur Bestimmung der ersten <math>k</math> 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 <math>p_i(A)=A-\kappa_iI</math> gesetzt. Damit kann das Verfahren alternativ auch als QR-Zerlegung <math>A_i-\kappa_iI=Q_iR_i</math> gefolgt vom um den Shift korrigierten Zusammenmultiplizieren <math>A_{i+1}=R_iQ_i+\kappa_iI</math> dargestellt werden. Üblicherweise wird versucht, mit dem Shift <math>\kappa_i</math> den betragskleinsten Eigenwert zu approximieren. Dazu kann das letzte Diagonalelement <math>\kappa_i=(A_i)_{n,n}</math> gewählt werden. Die einfache QR-Iteration ergibt sich, indem alle Shifts zu Null gesetzt werden.

Besitzt <math>A_i</math> Hessenberg-Form, so muss <math>Q_i=(A_i-\kappa_iI)R_i^{-1}</math> als [[Matrizenprodukt|Produkt]] einer Matrix mit und einer Matrix ohne [[Nebendiagonale]]n ebenfalls Hessenberg-Form besitzen. Das Gleiche gilt daher auch für <math>A_{i+1}=R_iQ_i+\kappa_iI</math>. Wird also in Vorbereitung des QR-Algorithmus in <math>A_1=Q_0^{-1}AQ_0</math> auf Hessenberg-Form gebracht, so bleibt dies während des gesamten Algorithmus erhalten.

=== Einfache Shifts für symmetrische Matrizen ===
Eine symmetrische reelle Matrix <math>A_1=A</math> hat ausschließlich reelle Eigenwerte. Die Symmetrie bleibt während des QR-Algorithmus in allen <math>A_i</math> erhalten. Für symmetrische Matrizen schlug Wilkinson (1965) vor, denjenigen Eigenwert der rechtsuntersten <math>2\times2</math>-Teilmatrix
:<math>
\begin{pmatrix}
a_{n-1,n-1}&a_{n-1,n}\\a_{n,n-1}&a_{n,n}
\end{pmatrix}
</math>
als Shift zu wählen, der näher an <math>a_{n,n}</math> liegt. Wilkinson zeigte, dass die so bestimmte Matrixfolge <math>(A_i)_{i\in\N}</math> gegen eine [[Diagonalmatrix]] konvergiert, deren Diagonalelemente die Eigenwerte von <math>A=A_1</math> sind. Die [[Konvergenzgeschwindigkeit]] ist dabei quadratisch.

=== QR-Algorithmus mit doppelten Shifts ===
Es kann ein Paar von einfachen Shifts in einem Iterationsschritt zusammengefasst werden. In der Konsequenz bedeutet dies, dass für reelle Matrizen auf komplexe Shifts verzichtet werden kann. In der oben angegebenen Notation ist
:<math>(A_1-\kappa_2I)(A_1-\kappa_1I)=(A_1-\kappa_2I)Q_1R_1=Q_1(A_2-\kappa_2I)R_1=Q_1Q_2R_2R_1</math>
eine QR-Zerlegung für das quadratische Polynom <math>p_1(x)=x^2-(\kappa_1+\kappa_2)x+\kappa_1\kappa_2</math>, ausgewertet in <math>A_1</math>. 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 <math>2\times2</math>-Teilmatrix, d. h., das quadratische Polynom ist das charakteristische Polynom dieses Blocks,
:<math>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}</math>.

=== QR-Algorithmus mit multiplen Shifts ===

Es wird eine Zahl <math>m</math> größer <math>2</math>, aber wesentlich kleiner als die Größe <math>n</math> der Matrix <math>A</math> festgelegt. Das Polynom <math>p_i(x)</math> kann als das charakteristische Polynom der rechtsuntersten quadratischen <math>m\times m</math>-Teilmatrix der aktuellen Matrix <math>A_i</math> gewählt werden. Eine andere Strategie besteht darin, die <math>s > m</math> Eigenwerte der rechtsuntersten <math>s\times s</math>-Teilmatrix zu bestimmen und die <math>m</math> betragskleinsten Eigenwerte <math>s_1,\dots,s_m</math> darunter auszuwählen. Mit diesen wird dann eine QR-Zerlegung von
:<math>p_i(A_i)=(A_i-s_1I)(A_i-s_2I)\cdots(A_i-s_mI)=Q_iR_i</math> und <math>A_{i+1}=Q_i^{-1}A_iQ_i</math>
bestimmt.

Mit einem Multishift-Verfahren wird oft erreicht, dass die Komponenten des linksunteren <math>(n-m+1,\dots,n)\times(1,\dots,n-m)</math>-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 <math>A_1=Q_0^{-1}AQ_0</math> 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 kann der QR-Algorithmus in einen ''„Bulge-chasing“''-Algorithmus umgewandelt werden, der eine Delle in der Hessenbergform am oberen Diagonalenende erzeugt und diese dann die Diagonale herunter und am unteren Ende aus der Matrix „jagt“.

# for <math>j\in\mathbb{N}_0</math> do
# Berechne das Polynom <math>p(x)</math> nach einer der angegebenen Varianten,
# Bestimme den Vektor <math>x=p(A_j)e_1</math>.
# Bestimme eine Spiegelung von <math>x</math> auf den ersten Einheitsvektor. Da in <math>x</math> nur die ersten <math>m+1</math> Komponenten nicht verschwinden, hat diese Spiegelung eine einfache Blockgestalt.
# Bilde die Matrix <math>\tilde A=U^{-1}A_jU</math> und transformiere sie so, dass <math>A_{j+1}=Q^{-1}U^{-1}A_jUQ</math> wieder in Hessenberg-Form ist.
# end for

Wird <math>Q</math> aus Householder-Spiegelungen zusammengesetzt, <math>Q=P_1P_2\cdots P_{n-1}</math>, so haben diese Blockdiagonalgestalt <math>P_k=\mathrm{diag}(I_k,\tilde P_k,I_{\max(0,n-k-m)})</math>.

== Anmerkungen zur Funktionsweise ==
=== Ähnlichkeitstransformationen ===
Die im QR-Algorithmus berechneten Matrizen sind zueinander unitär ähnlich, da
aufgrund von <math>A_i-\kappa_iI=Q_iR_i\quad\Leftrightarrow\quad R_i=Q_i^H(A_i-\kappa_iI)</math>

:<math>A_{i+1}=R_iQ_i+\kappa_iI
=Q_i^H(A_i-\kappa_iI)Q_i+\kappa_iI
=Q_i^HA_iQ_i-\kappa_iQ_i^HQ_i+\kappa_iI
=Q_i^HA_iQ_i</math>

gilt. Damit haben alle Matrizen <math>A_i</math> 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 <math>A_i</math> 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 <math>A_i</math> 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 <math>\kappa_i=a_{nn}^{(i)}</math>, 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-Quotient]]en im Zusammenhang steht.

Bei der Rechnung im Reellen (<math>A\in\mathbb{R}^{n\times n}</math>) 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 <math>2\times 2</math> Hauptunterabschnittsmatrix

:<math>\begin{pmatrix}
a_{n-1,n-1}^{(i)} & a_{n-1,n}^{(i)} \\
a_{n,n-1}^{(i)} & a_{n,n}^{(i)}
\end{pmatrix}</math>

verwendet.

=== Der QR-Algorithmus als Erweiterung der Potenzmethode ===
Zur Analyse des Algorithmus werden die zusätzlichen Matrixfolgen der kumulierten Produkte <math>\tilde Q_k=Q_1Q_2\cdots Q_k</math> und <math>\tilde R_k=R_kR_{k-1}\cdots R_2R_1</math>, <math>k\in\N</math> definiert. Dabei sind die Produkte <math>\tilde Q_k</math> von orthogonalen bzw. unitären Matrizen wieder orthogonale bzw. unitäre Matrizen, genauso sind die Produkte <math>\tilde R_k</math> von rechtsoberen Dreiecksmatrizen wieder rechtsobere Dreiecksmatrizen. Die Matrizen der QR-Iteration ergeben sich durch Ähnlichkeitstransformationen aus <math>A</math>, denn
:<math>
A_1=A,\;
A_2=R_1Q_1=Q_1^{-1}A_1Q_1,\;
A_3=Q_2^{-1}A_2Q_2=\tilde Q_2^{-1}A\tilde Q_2,
\dots,\;
A_k=\tilde Q_k^{-1}A\tilde Q_k,
\dots
</math>.

Daraus folgert man auf QR-Zerlegungen der Potenzen von <math>A</math>:
:<math>\begin{align}
A=&&&Q_1R_1&=&\tilde Q_1\tilde R_1\\
A^2=&AQ_1R_1=Q_1A_2R_1&=&Q_1Q_2R_2R_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{align}
</math>

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

Der einfache QR-Algorithmus konvergiert nur, wenn alle Eigenwerte in ihren Beträgen voneinander verschieden sind. Sind die Eigenwerte nach
:<math>|\lambda_1|<|\lambda_2|<\dots<|\lambda_n|</math>
sortiert, so ist die Konvergenzgeschwindigkeit linear mit einem Kontraktionsfaktor, der dem Minimum der Quotienten <math>\tfrac{|\lambda_k|}{|\lambda_{k+1}|}</math> entspricht.

Insbesondere für reelle Matrizen kann dieser Algorithmus nur konvergieren, wenn alle Eigenwerte reell sind (da sonst konjugiert komplexe Paare mit gleichem Betrag existieren würden). Diese Situation ist für alle symmetrischen Matrizen gegeben.

== Der QR-Algorithmus als simultane inverse Potenziteration ==

Falls <math>A</math> invertierbar ist, gilt für die [[Transponierte]] (für komplexe Matrizen die hermitesch [[Adjungierte]]) der Inversen von <math>A</math> und alle ihre Potenzen
:<math>(A^{-T})^k=(A^k)^{-T}=(\tilde R_k^{-1}\tilde Q_k^{-1})^T=\tilde Q_k\tilde R_k^{-T}</math>
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 <math>A^{-T}</math>. Aus der Form dieser Zerlegung ist klar, dass für jedes <math>j=1,2, \ldots ,n</math> die letzten <math>j</math> Spalten von <math>\tilde Q_k</math> denselben Unterraum aufspannen wie die letzten <math>j</math> Spalten von <math>(A^{-T})^k</math>. In der letzten Spalte von <math>\tilde Q_k</math> wird somit eine inverse Potenziteration für <math>A^T</math> durchgeführt, diese Spalte konvergiert also gegen den dualen Eigenvektor zum kleinsten Eigenwert von <math>A</math>. Im Produkt <math>\tilde Q_k^T A \tilde Q_k=A_k</math> ist also die linke untere Komponente <math>(A_k)_{nn}</math> der sog. [[Rayleigh-Quotient]] der inversen Potenziteration. Die Konvergenzeigenschaften sind analog zum oben angegebenen.

== Weblinks ==
* [http://lp.uni-goettingen.de/get/text/2035 LP: QR-Verfahren für allgemeine EWP], Georg-August-Universität Göttingen

== Literatur ==
* {{Literatur |Titel=Numerik-Algorithmen|Autor=Gisela Engeln-Müllges, Klaus Niederdrenk, Reinhard Wodicka|Verlag=Springer-Verlag|Ort=Berlin, Heidelberg|Auflage=10|Datum=2011|ISBN=978-3-642-13472-2|Kapitel=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; ([http://comjnl.oxfordjournals.org/content/4/4/332.abstract online])
* David S. Watkins (1982): ''Understanding the QR algorithm'', SIAM Review, Vol. 24, S. 427–440 ([http://links.jstor.org/sici?sici=0036-1445%28198210%2924%3A4%3C427%3AUTA%3E2.0.CO%3B2-N 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 [http://wwwuser.gwdg.de/~parallel/parallelrechner/scalapack/lawns/index.html LAPACK Working Notes])
* A. A. Dubrulle; G. H. Golub (1994): [http://citeseer.ist.psu.edu/dubrulle94multishift.html ''A multishift QR iteration without computation of the shifts'']. Numerical Algorithms, Vol 7, S. 173–181
* K. Braman; R. Byers; R. Mathias (2002): [http://www.mcs.sdsmt.edu/kbraman/Research/QR-I.pdf ''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): [http://www.mcs.sdsmt.edu/kbraman/Research/QR-II.pdf ''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 : [http://www.math.wsu.edu/faculty/watkins/pdfiles/qrevisit.pdf ''The QR algorithm revisited''] (PDF; 417 kB) , SIAM Review, Vol. 50, No. 1, S. 133–145
* [[Martin Hermann (Mathematiker)|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.

{{DEFAULTSORT:Qr-Algorithmus}}
[[Kategorie:Numerische lineare Algebra]]

QR-Algorithmus - Versionsgeschichte

imported>Alex Writer WEH: /* growthexperiments-addlink-summary-summary:1|0|0 */