Mo Logo [Home] [Lexikon] [Aufgaben] [Tests] [Kurse] [Begleitmaterial] [Hinweise] [Mitwirkende] [Publikationen] [Suche] Englische Flagge
Mathematik-Online-Lexikon: Erläuterung zu

Implementierung der QR-Iteration

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z Übersicht
Ein Schritt $ A \mapsto B$ der tridiagonalen $ QR$-Iteration mit Shift $ \lambda$ berechnet eine $ QR$-Faktorisierung,

$\displaystyle A-\lambda E = QR, $

die die tridiagonale Form erhält und bildet

$\displaystyle B=RQ +\lambda E =Q^{\operatorname t} A Q \,. $

Sie kann folgendermaßen implementiert werden. Zuerst wird eine Givens-Rotation $ Q_1^{\operatorname t} $, basierend auf dem Vektor $ (a_{1,1} - \lambda ,\, a_{2,1})^{\operatorname t}$, auf die ersten beiden Zeilen von links und $ Q_1$ auf die ersten beiden Spalten von rechts angewendet. Dadurch entsteht ein Eintrag in $ (3,1)$, der die tridiagonale Form von $ A$ zerstört. Nun werden Givens-Rotationen $ Q_i^{\operatorname t},\, i=2, \hdots ,n-1$ sukzessive auf die Zeilen $ i$ und $ i+1$ angewendet und ihre Transponierten $ Q_i$ auf die entsprechenden Spalten:

$\displaystyle B= Q_{n-1}^{\operatorname t} \cdots Q_{1}^{\operatorname t} A Q_1 \cdots Q_{n-1} \,. $

Die Transformation $ Q_i^{\operatorname t}$ basiert auf dem Vektor der aktuellen Einträge in den Positionen $ (i:i+1,i-1)$. Folglich stellt die Ähnlichkeitstransformation mit $ Q_i$ die tridiagonale Form bis zur Spalte $ i-1$ wieder her. Dieser Prozess wird nachstehend schematisch illustriert.

$\displaystyle \left( \begin{array}{c} {\mbox{\includegraphics[width=0.2\linewidth,bb=125 619 214 708,clip]{Num_18_2_Bild1}}} \end{array} \right)$ $\displaystyle \stackrel{Q_1}{\longrightarrow} \left( \begin{array}{c} {\mbox... ...8,clip]{Num_18_2_Bild2}}} \end{array} \right) \stackrel{Q_2}{\longrightarrow}$    
$\displaystyle \left( \begin{array}{c} {\mbox{\includegraphics[width=0.2\linewidth,bb=125 619 214 708,clip]{Num_18_2_Bild3}}} \end{array} \right)$ $\displaystyle \stackrel{Q_3}{\longrightarrow} \left( \begin{array}{c} {\mbox... ...214 708,clip]{Num_18_2_Bild4}}} \end{array} \right) \longrightarrow \cdots$    

Änderungen in den Einträgen sind durch verschiedene Symbole gekennzeichnet. Darüber hinaus werden die Einträge, die die folgende Givens-Rotation bestimmen, hervorgehoben. Diese Transformation annulliert den Eintrag in der eingekreisten Position.

Falls zufällig beide Einträge in Position $ (i:i+1,i-1)$ Null sind, kann die $ i$-te Transformation entfallen. In diesem Fall ist der Nebendiagonaleintrag $ b_{i,i-1}$ Null, und die Dimension des Eigenwertproblems kann reduziert werden.

Es muss gezeigt werden, dass die Implementierung der Ähnlichkeitstransformation mit den Formeln

$\displaystyle A-\lambda E=QR \,, \quad B=Q^{\operatorname t} A Q $

konsistent ist. Dazu wird die Givens-Transformation zur Konstruktion der QR-Faktorisierung mit $ Q_i$ bezeichnet,

$\displaystyle Q^{\operatorname t} = Q_{n-1}^{\operatorname t} \cdots Q_1^{\operatorname t}, $

und die in der Implementierung benutzten Transformationen mit $ \widetilde{Q}_i$. Nach Konstruktion ist $ \widetilde{Q}_1^{\operatorname t}= Q_1^{\operatorname t}$. Die anderen Transformationen stimmen auch überein. Dies folgt aus der Eindeutigkeit der QR-Faktorisierung mit Givens-Transformationen bei von Null verschiedenen Nebendiagonaleinträgen und der Tatsache, dass die tridiagonale Form erhalten bleibt. In der Tat, falls nicht beide Einträge in den Positionen $ (i:i+1,i-1)$ Null sind, wird $ \widetilde{Q}_i^{\operatorname t}$ eindeutig durch die Forderung bestimmt, dass die tridiagonale Form wiederhergestellt werden muss.

Es müssen lediglich noch die Ausnahmefälle diskutiert werden. Falls ein Nebendiagonaleintrag $ a_{i,i-1}$ Null ist, kann die Dimension des Eigenwertproblems reduziert werden:

$\displaystyle \det (A-\lambda E)= \det (A(1,i-1,1:i-1) - \lambda E_{i-1}) \cdot \det (A(i:n,i:n)-\lambda E_{n-i+1}) $

mit $ E_k$ der $ k \times k$ Einheitsmatrix.

Eine Reduktion ist auch möglich, falls die Einträge $ (i:i+1,i-1)$, die $ \widetilde{Q}_i^t$ bestimmen, Null sind. Für beliebiges $ \widetilde{Q}_i^t$ generiert die Ähnlichkeitstransformation dann eine Null in Position $ (i,i-1)$.

(Autoren: Höllig/E. Höllig)
[Zurück zur Aussage]
  automatisch erstellt am 7.  5. 2007