Numerische Eigenwertverfahren: Potenzmethode und QR-Verfahren

Auf der Seite Eigenwerte und Eigenvektoren bestimmst du Eigenwerte als Nullstellen des charakteristischen Polynoms $\det (A-\lambda E)$. Das funktioniert für $2\times 2$- und $3\times 3$-Matrizen von Hand. Für große Matrizen ist es keine Option: Das Aufstellen des Polynoms ist teuer, seine Nullstellen reagieren extrem empfindlich auf kleine Fehler in den Koeffizienten, und ab Grad 5 gibt es nach dem Satz von Abel und Ruffini keine allgemeine Lösungsformel mit Wurzeln. Praktische Verfahren arbeiten deshalb direkt mit der Matrix und erzeugen die Eigenwerte als Grenzwert einer Iteration.

Diese Seite stellt die wichtigsten Verfahren vor: Die Potenzmethode findet den betragsgrößten Eigenwert, die inverse Iteration einen beliebigen, die Gerschgorin-Kreise liefern Schranken, und das QR-Verfahren berechnet alle Eigenwerte. Sie bauen auf Skalarprodukt und Orthogonalität (QR-Zerlegung, Spektralsatz) und Numerische Lineare Algebra auf.

Die Potenzmethode

Die Idee ist so einfach wie wirksam: Multipliziert man einen Vektor immer wieder mit $A$, setzt sich die Richtung des stärksten Eigenvektors durch, so wie bei einer Folge von Zahlen die größte Wachstumsrate gewinnt.

Beweis. Es ist $A^k{x}^{(0)}=\sum _{i=1}^n{c}_i{\lambda }_i^k{v}_i$ $={\lambda }_1^k(c_1{v}_1+\sum _{i=2}^n{c}_i{\left(\frac{{\lambda }_i}{{\lambda }_1}\right)}^k{v}_i)$. Wegen $\left|\frac{{\lambda }_i}{{\lambda }_1}\right|<1$ gehen alle Terme der Summe gegen 0, am langsamsten der zu ${\lambda }_2$. Die Normierung ändert nur die Länge, nicht die Richtung.

Die Potenzmethode braucht pro Schritt nur ein Matrix-Vektor-Produkt, ist also für sehr große dünnbesetzte Matrizen geeignet. Ihre Nachteile: Sie liefert nur den betragsgrößten Eigenwert, und sie ist langsam, wenn ${\lambda }_2$ nahe bei ${\lambda }_1$ liegt. Bei $\frac{\left|{\lambda }_2\right|}{\left|{\lambda }_1\right|}=\mathrm{0,99}$ braucht man etwa 230 Schritte für den Fehlerabfall um den Faktor 10. Gilt $\left|{\lambda }_1\right|=\left|{\lambda }_2\right|$ (zum Beispiel ${\lambda }_2=-{\lambda }_1$), konvergiert das Verfahren nicht. Ist $c_1=0$, bleibt es theoretisch bei den anderen Eigenvektoren hängen, im Rechner schaffen es die Rundungsfehler aber meist, $v_1$ wieder zuzulassen.

Der Rayleigh-Quotient

Für eine Näherung $x$ eines Eigenvektors ist der Eigenwert am besten durch den Rayleigh-Quotienten $R(x)=\frac{x^{\top }Ax}{x^{\top }x}$ angenähert: Er minimiert $\Vert Ax-\lambda x{\Vert }_2$ über alle $\lambda$. Ist $x$ ein exakter Eigenvektor, gilt $R(x)=\lambda$.

Beweis. Mit dem Spektralsatz ist $x^{\top }Ax=\sum {\lambda }_i{c}_i^2$ und $x^{\top }x=\sum c_i^2$. Für den Fehler gilt ${\lambda }_1-R(x)=\frac{\sum _{i\ge 2}({\lambda }_1-{\lambda }_i)c_i^2}{\sum c_i^2}$. Ist der Winkel zwischen $x$ und $v_1$ von der Größe $\epsilon$, sind die $c_i$ mit $i\ge 2$ von der Größe $\epsilon$ und ihre Quadrate von der Größe ${\epsilon }^2$.

Das zeigt die Tabelle: Der Vektor verbessert sich pro Schritt um den Faktor $\frac{1}{3}$, der Rayleigh-Quotient um den Faktor $\frac{1}{9}$. Aus dem Fehler $\mathrm{0,2}$ nach Schritt 1 wird $\mathrm{0,0244}$, dann $\mathrm{0,0027}$, dann $\mathrm{0,0003}$.

Inverse Iteration

Hat $A$ die Eigenwerte ${\lambda }_i$, so hat ${(A-\mu E)}^{-1}$ die Eigenwerte $\frac{1}{{\lambda }_i-\mu }$ zu denselben Eigenvektoren (für $\mu$ kein Eigenwert). Der betragsgrößte unter ihnen gehört zu dem ${\lambda }_i$, das $\mu$ am nächsten liegt. Wendet man die Potenzmethode auf ${(A-\mu E)}^{-1}$ an, findet man genau diesen Eigenwert. In jedem Schritt löst man das System $(A-\mu E)y=x^{(k)}$ mit einer einmal berechneten LR-Zerlegung (siehe Numerische Lineare Algebra).

Gerschgorin-Kreise

Bevor man iteriert, möchte man wissen, wo die Eigenwerte liegen. Dafür genügt ein Blick auf die Einträge.

Beweis. Sei $Ax=\lambda x$ mit $x\ne 0$ und $\left|x_i\right|$ maximal. Die $i$-te Gleichung lautet $(\lambda -a_{ii})x_i=\sum _{j\ne i}{a}_{ij}{x}_j$. Nimmt man Beträge und teilt durch $\left|x_i\right|$, folgt $|\lambda -a_{ii}|\le \sum _{j\ne i}\left|a_{ij}\right|\frac{\left|x_j\right|}{\left|x_i\right|}\le \sum _{j\ne i}\left|a_{ij}\right|$.

Das QR-Verfahren

Alle Eigenwerte gleichzeitig berechnet das QR-Verfahren. Es nutzt die QR-Zerlegung $A=QR$ mit einer orthogonalen Matrix $Q$ und einer oberen Dreiecksmatrix $R$ (Gram-Schmidt, siehe Skalarprodukt und Orthogonalität).

Die Ähnlichkeit folgt aus $R_k=Q_k^{\top }{A}_k$, also $A_{k+1}=R_k{Q}_k=Q_k^{\top }{A}_k{Q}_k$. Das Verfahren ist eine Potenzmethode für alle Eigenvektoren zugleich, die Spalten von $Q$ halten sie orthogonal. Bei symmetrischen Matrizen strebt $A_k$ gegen eine Diagonalmatrix.

In der Praxis wird das Verfahren stark beschleunigt. Man bringt $A$ zuerst durch Ähnlichkeitstransformationen auf Hessenberg-Form (bei symmetrischen Matrizen auf Tridiagonalform), was jeden Schritt billiger macht. Mit Shifts, also der Zerlegung von $A_k-{\mu }_{k}E$, konvergiert das Verfahren quadratisch oder sogar kubisch. Hat die Matrix komplexe Eigenwerte, bleiben im reellen Verfahren $2\times 2$-Blöcke auf der Diagonale. Das ist der Standardalgorithmus in numerischen Bibliotheken und in der Eigenwertfunktion von MATLAB und NumPy.

Typische Fehler

Übungen

Geschichte: von der Mechanik zur Suchmaschine

Die Potenzmethode wird meist Richard von Mises und Hilda Pollaczek-Geiringer zugeschrieben, die 1929 in einem Beitrag über „Praktische Verfahren der Gleichungsauflösung“ Verfahren zur Berechnung von Eigenwerten und Eigenvektoren darstellten. Vorläufer gab es in der Mechanik, wo Schwingungsfrequenzen von Bauwerken iterativ bestimmt wurden (Vianello 1898, Stodola 1904). Die Gerschgorin-Kreise stammen aus einer Arbeit von Semjon Aronowitsch Gerschgorin von 1931. Heinz Rutishauser entwickelte 1958 den LR-Algorithmus, aus dem John Francis und Vera Kublanovskaya 1961/1962 das stabile QR-Verfahren machten. Die Potenzmethode ist auch der Kern von PageRank, dem ursprünglichen Rangordnungsverfahren der Suchmaschine Google.

Häufige Fragen

Quellen und weiterführende Literatur

• Wikipedia: Potenzmethode
• Wikipedia: QR-Algorithmus
• Wikipedia: Gerschgorin-Kreise
• Lloyd N. Trefethen, David Bau: Numerical Linear Algebra, SIAM, Philadelphia.
• Gene H. Golub, Charles F. Van Loan: Matrix Computations, Johns Hopkins University Press, Baltimore.
• Richard von Mises, Hilda Pollaczek-Geiringer: Praktische Verfahren der Gleichungsauflösung, Zeitschrift für Angewandte Mathematik und Mechanik 9 (1929).