Mo Logo [Home] [Lexikon] [Aufgaben] [Tests] [Kurse] [Begleitmaterial] [Hinweise] [Mitwirkende] [Publikationen] Englische Flagge

Mathematik-Online-Lexikon:

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

Die QR-Iteration approximiert einen Eigenwert einer Matrix $ A$ in Hessenbergform mit Hilfe einer Folge orthogonaler Ähnlichkeitstransformationen

$\displaystyle A_\ell \mapsto A_{\ell+1} = Q_{\ell +1}^t A_\ell Q_{\ell+1} \,, \quad
A_0=A\,.
$

Die Matrix $ Q_{\ell+1}$ wird durch die QR-Zerlegung

$\displaystyle A_\ell - \lambda_\ell E = Q_{\ell +1} R_{\ell +1}
$

definiert. Dabei ist der Shift $ \lambda_\ell$ der am nächsten bei $ A_\ell(n,n)$ gelegene Eigenwert der $ 2\times2$ Untermatrix $ A_\ell(n-1:n,n-1:n)$:

$\displaystyle \lambda_\ell = \frac{d_+}{2} + \frac{\sigma }{2}
\sqrt{d_-^2+4 A_\ell \left(n,n-1\right) A_\ell \left( n-1,n \right)}
$

mit

$\displaystyle d_\pm$ $\displaystyle = A_\ell \left( n,n \right) \pm 
 A_\ell \left( n-1,n-1 \right)$    
$\displaystyle \sigma$ $\displaystyle = 
 \left\{ 
 \begin{array}{cl}
 \mbox{sign} \left( d_- \right) \...
...\mbox{für } d_- \neq 0 \\ 
 1 \,, & \mbox{für } d_-=0 \,.
 \end{array}
 \right.$    

Null-Diagonalen der Hessenbergform bleiben erhalten. Insbesondere sind für eine symmetrische Matrix $ A$ alle Matrizen $ A_\ell$ tridiagonal.

Für $ \ell\to\infty$ geht der nebendiagonale Eintrag $ A_\ell ( n,n-1)$ gegen 0, und folglich nähert sich $ A_\ell(n,n)$ einem Eigenwert $ \lambda$ von $ A$. Für symmetrisches $ A$ ist die Konvergenz lokal kubisch.

Hat die Iteration konvergiert, d.h. ist der letzte nebendiagonale Eintrag von $ A_\ell$ innerhalb der Toleranz Null, so wird das Verfahren auf die Untermatrix $ A_\ell (1:n-1,1:n-1)$ angewandt. Somit werden schließlich alle Eigenwerte berechnet.


[Beispiele] [Verweise]

  automatisch erstellt am 19.  8. 2013