Mo Logo [Home] [Lexikon] [Aufgaben] [Tests] [Kurse] [Begleitmaterial] [Hinweise] [Mitwirkende] [Publikationen] 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.


(Inhalt vorübergehend nicht verfügbar)

[Zurück]

  automatisch erstellt am 19.  8. 2013