Power Iteration
Die Potenziteration multipliziert die Matrix wiederholt mit einem Vektor, v_{k+1}=Av_k/||Av_k||, und konvergiert gegen den Eigenvektor zum betragsgrößten Eigenwert.
Zweck
Den dominierenden Eigenwert und Eigenvektor effizient approximieren, eingesetzt in PageRank und PCA.
Mechanismus
v konvergiert gegen den Haupt-Eigenvektor, und der Quotient ||Av_k||/||v_k|| konvergiert gegen den Haupt-Eigenwert. Die Konvergenzgeschwindigkeit hängt von |λ_1/λ_2| ab. Beschleunigungen: der Rayleigh-Quotient, die Shift-Iteration und der QR-Algorithmus.
Anwendungsfälle
- PageRank-Berechnung
- PCA-Approximation
- Spektralanalyse