Die Potenzmethode

Die dominante Richtung durch wiederholtes Multiplizieren finden

Ein charakteristisches Polynom zu lösen ist für eine $1000\times1000$-Matrix aussichtslos, und oft will man nur das größte Eigenpaar, etwa die erste Hauptkomponente. Die Potenzmethode findet es allein mit Matrix-Vektor-Produkten. Starten Sie mit einem beliebigen Vektor $\mathbf x_0$ und wiederholen Sie $\mathbf x_{k+1}=A\mathbf x_k/\lVert A\mathbf x_k\rVert$. Jede Multiplikation streckt die Komponente entlang des dominanten Eigenvektors stärker als alle anderen, sodass der Vektor nach genug Schritten in diese Richtung zeigt.

Schreiben Sie $\mathbf x_0=c_1\mathbf v_1+c_2\mathbf v_2+\cdots$ in Eigenvektoren. Nach $k$ Schritten sind die Koeffizienten mit $\lambda_i^k$ multipliziert, das Verhältnis des zweiten zum ersten ist also $(\lambda_2/\lambda_1)^k$. Das Verfahren konvergiert, wenn $|\lambda_1|>|\lambda_2|$ gilt und der Startvektor eine Komponente entlang $\mathbf v_1$ hat, und die Geschwindigkeit bestimmt $|\lambda_2/\lambda_1|$: Nahe beieinanderliegende Eigenwerte bedeuten langsame Konvergenz. Die Normierung verhindert nur einen Überlauf; auf die Richtung kommt es an. Der Eigenwertschätzer ist der Rayleigh-Quotient. Für das nächste Eigenpaar zieht man $\lambda_1\mathbf v_1\mathbf v_1^{T}$ von einer symmetrischen Matrix $A$ ab und wiederholt, das heißt Deflation.

• Update: mit $A$ multiplizieren, durch die Norm teilen, wiederholen; jeder Schritt kostet ein Matrix-Vektor-Produkt.
• Geschwindigkeit: Der Fehler fällt wie $|\lambda_2/\lambda_1|^k$, dicht beieinanderliegende größte Eigenwerte konvergieren also langsam.
• Voraussetzungen: eine Lücke $|\lambda_1|>|\lambda_2|$ und ein Startvektor, der nicht orthogonal zu $\mathbf v_1$ ist.

Lab: Was bewertet wird

• Wogegen sie konvergiert15 Pkt.
• Ein Rayleigh-Quotient20 Pkt.
• Das Konvergenzverhältnis10 Pkt.
• Wie viele Iterationen15 Pkt.
• Der Algorithmus in Reihenfolge15 Pkt.
• Wann sie langsam ist oder versagt15 Pkt.
• Warum normieren10 Pkt.