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