Iterative Methoden

Eigenwertalgorithmen

Eigenwerte können (bei Dimension größer als vier) nur iterativ berechnet werden. Dabei wird typischerweise wie folgt vorgegangen:

Ähnlichkeitstransformation der Matrix auf eine Matrix einfacher Struktur (z.B. Hessenberg-Matrix, Tridiagonalmatrix)
Iterationsverfahren zur Transformation auf obere Dreiecksmatrix (im Limes) bzw. Transformation von Vektoren, die gegen Eigenvektoren konvergieren.

Transformation auf Hessenberg-Form

Eine Matrix $A in R^{m × n}$ mit $A_{jk} = 0$ für alle heißt Hessenberg-Matrix. Eine beliebige Matrix kann mit Hilfe der Householder-Transformation, bei der mit passenden Householder-Matrizen von links multipliziert wird, auf Hessenberg-Form gebracht werden.

Störungstheorie für Eigenwertprobleme

Im Folgenden bezeichne die Menge der Eigenwerte von .

Eine Matrix $A in R^{n × n}$ heißt diagonalisierbar, wenn eine reguläre Matrix $T in C^{n × n}$ existiert, so dass gilt: $T^{-1}AT = {diag}\,}(lambda_1,\,...,\,lambda_n) in C^{n × n}$ .

Nach dem Satz von Bauer und Fike gilt für eine diagonalisierbare Matrix $A in R^{n × n}$ mit wie oben und beliebiges ${Delta}A in R^{n × n}$

$\max_{µ in sigma(A + {Delta}A)} \; \min_{lambda in \......}_{p}(T) * \Vert{Delta}A\Vert _{p}$

wobei beliebig und ${cond}_{p}(T) := \Vert T\Vert _{p}* \Vert T^{-1}\Vert _{p}$ , wobei $\Vert.\Vert _{p}$ die Matrixnorm zur Vektornorm in $l^{p}$ bezeichne.

Für allgemeine reelle Matrizen gilt:

$\max_{µ in sigma(A + {Delta}A)} \; \min_{lambda in \......ath{\Vert{Delta}A\Vert _2^{\frac1n )$

wobei die Konstante von der Schur-Zerlegung von abhängt.

Die Eigenwerte einer Matrix hängen stetig von ihren Koeffizienten ab: Hat nämlich $A in R^{n × n}$ die Eigenwerte $lambda_1,\,...,\,lambda_n$ , so existiert zu jedem ein , sodass für jede Matrix ${Delta}A in R^{n × n}$ mit $\Vert{Delta}A\Vert < delta$ eine Nummerierung der Eigenwerte $µ_1,\,...,\,µ_n$ von existiert mit

$\max_{j=1}^n |lambda_j - µ_j| < eps$

Der Satz von Gerschgorin liefert eine Aussage über die Lage der Eigenwerte: Sei $A in R^{n × n}$ gegeben und für $j=1,\,...,\,n$ definiert als

$G_j := \{ z in C\Biggm\ver......<= sum_{k=1}\atop{k <> j}^n | A_{jk}| \}$

Dann gilt: $sigma(A) \subseteq G_1 \cup G_2 \cup ... \cup G_n$ .

Variationsformulierung für symmetrische Matrizen

Ist $A in R^{n × n}$ symmetrisch und , so bezeichnet man den Ausdruck

$R_A(x) := \frac{x^TAx}{x^Tx}$

als Rayleigh-Quotienten.

Diesen kann man zur Berechnung der Eigenwerte einer symmetrischen Matrix $A in R^{n × n}$ verwenden, wie der Satz von Courant-Fischer besagt: Sind die Eigenwerte von , so gilt für $j=1,\,2,\,...,\,n-1$ :

$lambda_{j+1} & = & \min_{y_1,\,...,\,y_j in \ensurem......\{y_1,\,...,\,y_j\}^{\perp} \ \{0\} \; R_A(x)$

Speziell gilt nach dem Satz von Rayleigh-Ritz:

$lambda_1 = \max_{x <> 0} R_A(x) {bzw.} lambda_n = \min_{x <> 0} R_A(x)$

Schließlich gilt nach dem Störungssatz für symmetrische Matrizen für symmetrisches $A, {Delta}A in R^{n × n}$ und $j=1,\,...,\,n$ :

$lambda_j(A) + lambda_n({Delta}A) <= lambda_j(A + {Delta}A) <= lambda_j(A) + lambda_1({Delta}A)$

bzw.

$|lambda_j(A + {Delta}A) - lambda_j(A)| <= \Vert{Delta}A\Vert _2$

Vektoriterationen

Für $B in R^{n × n}$ und $z^{(0)} in R^n\ \{0\}$ heißt die durch

$z^{(j+1)} := Bz^{(j)} = B^{j+1}z^{(0)} {für} \; j=0,\,1,\,2,\,...$

definierte Folge die Folge der Iterierten (mit Iterationsmatrix und Startvektor $z^{(0)}$ ).

Ist nun eine diagonalisierbare Matrix mit den Eigenwerten $lambda_1\,\,...,\,lambda_n in C$ , wobei $lambda_1 = ... = lambda_{r}$ und $|lambda_{r}| > |lambda_{r+1}| >= ... >= |lambda_n|$ für ein $r in \{0,\,1,\,...,\,n-1\}$ , und $z^{(0)} in R^n\ \{0\}$ so gewählt, dass $z^{(0)} \notin \ker(B-lambda_{r+1}1) \oplus ... \oplus \ker(B-lambda_n1)$ , so gilt:

$\frac{\Vert z^{(j+1)}\Vert {\en......1| + O(q^j) {für} \; j –> infinity$

wobei $q := \frac{|lambda_{r+1}|}{|lambda_1|} < 1$ und $\Vert.\Vert$ eine beliebige Vektornorm darstellt.

Möchte man den Betrag des dominanten Eigenwertes von berechnen, so bietet sich zum Beispiel folgende Wahl von an:

Von-Mises-Iteration:
inverse Iteration nach Wielandt: $B = (A - µ * 1)^{-1}$ für ein $µ in R\ sigma(A)$

Ist unter obigen Voraussetzungen zusätzlich symmetrisch, so gilt

$r_j := \frac{z^{(j+1)} \,\begin{picture}(2,2) \put(1,1){\......{picture}\,z^{(j)} = R_B(z^{(j)}) = lambda_1 + O(q^{2j})$

QR-Algorithmus

Unter gewissen Bedingungen liefert das QR-Verfahren (siehe Anhang D.1) eine Approximation für die Eigenwerte einer Matrix: Sei diagonalisierbar mit betragsmäßig einfachen, reellen Eigenwerten $lambda_1,\,...,\,lambda_n$ mit . bezeichne die Matrix der Eigenvektoren zu $lambda_1,\,...,\,lambda_n$ . Schließlich besitze $T^{-1}$ eine LR-Zerlegung ohne Pivotisierung. Dann gilt:

$A^{(j)} = S_jUS_j + O(q^j)$

für $q := \max_{j=1}^{n-1} | \frac{lambda_{j+1}{lambda_j | < 1$ und $S_j := {diag}\,}(sigma_1^{(j)},\,...,\,sigma_n^{(j)})$ mit $sigma_k^{(j)} = \pm 1$ und rechter oberer Dreiecksmatrix mit $U_{jj} = lambda_j$ für $j=1,\,...,\,n$ .

Durch Durchführung eines (geeigneten) Shifts (siehe Anhang D.2) in jedem Schritt kann die Konvergenz deutlich verbessert werden (in diesem Fall von linear auf kubisch).

Oft lässt sich ein Problem auch durch Deflation vereinfachen. Diese tritt dann auf, wenn eine Iterationsmatrix $A^{(j)}$ die Gestalt $A^{(j)} = {diag}\,}(A_{u}^{(j)},A_l^{(j)})$ hat. Dann können nämlich die beiden Matrizen $A_{u}^{(j)}$ bzw. $A_l^{(j)}$ (jeweils kleinerer Dimension) getrennt betrachtet werden.

Wird das QR-Verfahren mit nur $m \ll n$ vielen Spaltenvektoren durchgeführt, so erhält man die Subspace-Iteration.

Direkte Berechnung

Die direkte Berechnung der Eigenwerte (über das charakteristische Polynom) ist nur für Tridiagonalmatrizen zu empfehlen. In diesem Fall erhält man nämlich das charakteristische Polynom mit Hilfe von einfachen Rekursionsformeln, und dessen Nullstellen können anschließend mit Hilfe von Polynomnullstellenberechnungsverfahren (wie z.B. Newton-Verfahren oder Bisektionsverfahren) zumindest approximativ berechnet werden.