Mathematik lernen · Studium

Numerische Eigenwertverfahren: Potenzmethode und QR-Verfahren

Das charakteristische Polynom taugt nur für kleine Matrizen. Für große berechnet man Eigenwerte iterativ. Du lernst die Potenzmethode, den Rayleigh-Quotienten, die inverse Iteration, die Gerschgorin-Kreise und das QR-Verfahren.

8 Min. Lesezeit Lernpfad Studium und Selbststudium, Schritt 61 von 70

Auf der Seite Eigenwerte und Eigenvektoren bestimmst du Eigenwerte als Nullstellen des charakteristischen Polynoms $\det (A - λ 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} λ_{i}^{k} v_{i}$ $= λ_{1}^{k} (c_{1} v_{1} + \sum_{i = 2}^{n} c_{i} {(\frac{λ_{i}}{λ_{1}})}^{k} v_{i})$ . Wegen $| \frac{λ_{i}}{λ_{1}} | < 1$ gehen alle Terme der Summe gegen 0, am langsamsten der zu $λ_{2}$ . Die Normierung ändert nur die Länge, nicht die Richtung.

Beispiel 1: Eine 2×2-Matrix

Sei $A = (\begin{matrix} 2 & 1 \\ 1 & 2 \end{matrix})$ mit den Eigenwerten $λ_{1} = 3$ (Eigenvektor $(1, 1)$ ) und $λ_{2} = 1$ (Eigenvektor $(1, - 1)$ ), und $x^{(0)} = {(1, 0)}^{⊤}$ . Teilt man jeweils durch die größte Komponente, erhält man:

Potenzmethode für $A = (\begin{matrix} 2 & 1 \\ 1 & 2 \end{matrix})$
Schritt $k$	$A x^{(k - 1)}$ vor der Normierung	$x^{(k)}$	Rayleigh-Quotient
1	$(2, 1)$	$(1; 0,5)$	$2,800$
2	$(2,5; 2)$	$(1; 0,8)$	$2,976$
3	$(2,8; 2,6)$	$(1; 0,9286)$	$2,9973$
4	$(2,9286; 2,8571)$	$(1; 0,9756)$	$2,9997$

Die Vektoren nähern sich $(1, 1)$ . Der Abstand der zweiten Komponente zu 1 sinkt jedes Mal ungefähr um den Faktor $\frac{λ_{2}}{λ_{1}} = \frac{1}{3}$ . Der Normierungsfaktor (größte Komponente von $A x^{(k)}$ ) geht gegen $λ_{1} = 3$ .

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 $λ_{2}$ nahe bei $λ_{1}$ liegt. Bei $\frac{| λ_{2} |}{| λ_{1} |} = 0,99$ braucht man etwa 230 Schritte für den Fehlerabfall um den Faktor 10. Gilt $| λ_{1} | = | λ_{2} |$ (zum Beispiel $λ_{2} = - λ_{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^{⊤} A x}{x^{⊤} x}$ angenähert: Er minimiert $‖ A x - λ x ‖_{2}$ über alle $λ$ . Ist $x$ ein exakter Eigenvektor, gilt $R (x) = λ$ .

Beweis. Mit dem Spektralsatz ist $x^{⊤} A x = \sum λ_{i} c_{i}^{2}$ und $x^{⊤} x = \sum c_{i}^{2}$ . Für den Fehler gilt $λ_{1} - R (x) = \frac{\sum_{i \geq 2} (λ_{1} - λ_{i}) c_{i}^{2}}{\sum c_{i}^{2}}$ . Ist der Winkel zwischen $x$ und $v_{1}$ von der Größe $ε$ , sind die $c_{i}$ mit $i \geq 2$ von der Größe $ε$ und ihre Quadrate von der Größe $ε^{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 $0,2$ nach Schritt 1 wird $0,0244$ , dann $0,0027$ , dann $0,0003$ .

Inverse Iteration

Hat $A$ die Eigenwerte $λ_{i}$ , so hat ${(A - μ E)}^{- 1}$ die Eigenwerte $\frac{1}{λ_{i} - μ}$ zu denselben Eigenvektoren (für $μ$ kein Eigenwert). Der betragsgrößte unter ihnen gehört zu dem $λ_{i}$ , das $μ$ am nächsten liegt. Wendet man die Potenzmethode auf ${(A - μ E)}^{- 1}$ an, findet man genau diesen Eigenwert. In jedem Schritt löst man das System $(A - μ 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 $A x = λ x$ mit $x \neq 0$ und $| x_{i} |$ maximal. Die $i$ -te Gleichung lautet $(λ - a_{i i}) x_{i} = \sum_{j \neq i} a_{i j} x_{j}$ . Nimmt man Beträge und teilt durch $| x_{i} |$ , folgt $| λ - a_{i i} | \leq \sum_{j \neq i} | a_{i j} | \frac{| x_{j} |}{| x_{i} |} \leq \sum_{j \neq i} | a_{i j} |$ .

Das QR-Verfahren

Alle Eigenwerte gleichzeitig berechnet das QR-Verfahren. Es nutzt die QR-Zerlegung $A = Q R$ 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}^{⊤} A_{k}$ , also $A_{k + 1} = R_{k} Q_{k} = Q_{k}^{⊤} 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} - μ_{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

Nicht normieren: Ohne Normierung wachsen die Komponenten wie $λ_{1}^{k}$ und laufen über den Zahlenbereich.
Startvektor orthogonal zum Eigenvektor: Dann fehlt die Komponente $c_{1}$ . Man wählt den Startvektor zufällig.
Betragsgleiche Eigenwerte: Bei $λ_{2} = - λ_{1}$ oder komplexen Paaren gleichen Betrags konvergiert die einfache Potenzmethode nicht.
Rayleigh-Quotient bei nicht symmetrischen Matrizen: Die schnelle quadratische Konvergenz gilt nur für symmetrische Matrizen.
Eigenwert aus dem charakteristischen Polynom berechnen: Das ist numerisch instabil, schon bei Grad 20 verändern winzige Fehler in den Koeffizienten die Nullstellen völlig.
Gerschgorin überinterpretieren: Der Satz sagt, dass die Eigenwerte in der Vereinigung der Kreise liegen, nicht, dass in jedem Kreis genau einer liegt. Das gilt nur für Kreise, die von den anderen getrennt sind.

Ü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

Wie berechnet ein Programm Eigenwerte?

Fast immer mit dem QR-Verfahren in verbesserter Form (Hessenberg-Reduktion, Shifts). Die Potenzmethode und ihre Verwandten (Lanczos, Arnoldi) verwendet man, wenn die Matrix riesig und dünnbesetzt ist und man nur wenige Eigenwerte braucht.

Warum konvergiert die Potenzmethode so langsam?

Weil die Rate $\frac{| λ_{2} |}{| λ_{1} |}$ bei dicht beieinanderliegenden Eigenwerten nahe 1 ist. Mit einem Shift oder mit der inversen Iteration lässt sich das beheben.

Wozu braucht man Eigenwerte in der Praxis?

Für Schwingungen von Brücken und Molekülen, für die Stabilität von Differentialgleichungssystemen, für die Hauptkomponentenanalyse in der Statistik, für Suchmaschinen und für Bildkompression (Singulärwertzerlegung).

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).

Fehler entdeckt oder einen Wunsch? Schreib uns eine kurze Nachricht, wir kümmern uns darum.

Die Potenzmethode

Der Rayleigh-Quotient

Inverse Iteration

Gerschgorin-Kreise

Das QR-Verfahren

Typische Fehler

Übungen

Geschichte: von der Mechanik zur Suchmaschine

Häufige Fragen

Quellen und weiterführende Literatur

Weiterlesen

Eigenwerte und Eigenvektoren

Skalarprodukt, Orthogonalität und Spektralsatz

Numerische Lineare Algebra: LR-Zerlegung, Cholesky, Jacobi-Verfahren

Übergangsmatrizen und Markow-Ketten

Numerik-Grundlagen: Gleitkommazahlen, Rundungs­fehler und Kondition

Jordan-Normalform und Satz von Cayley-Hamilton

Numerik-Grundlagen: Gleitkommazahlen, Rundungsfehler und Kondition