Mo Logo [Home] [Lexikon] [Aufgaben] [Tests] [Kurse] [Begleitmaterial] [Hinweise] [Mitwirkende] [Publikationen] Englische Flagge
Mathematik-Online-Lexikon:

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.

Erläuterung:

[Downloads] [Verweise]
  automatisch erstellt am 19.  8. 2013