Direkt zum Inhalt

Lexikon der Mathematik: Lanczos-Verfahren

ursprünglich ein Verfahren zur Transformation einer symmetrischen Matrix auf Tridiagonalgestalt.

Kombiniert mit einer Methode zur Bestimmung von Eigenwerten und Eigenvektoren symmetrischer Tridiagonalmatrizen ist es ein geeignetes Verfahren zur Lösung des symmetrischen Eigenwert-problems für große sparse Matrizen.

Für eine gegebene symmetrische Matix A ∈ ℝn×n und einen gegebenen Vektor q1, ||q1||2 = 1, berechnet das Lanczos-Verfahren eine orthogonale Matrix Q ∈ ℝn×n, QTQ = I, deren erste Spalte Qe1 = q1 ist, sodaß A auf symmetrische Tridiagonalgestalt transformiert wird, d. h. \begin{eqnarray}{Q}^{T}AQ={T}_{n}=\left(\begin{array}{cccc}{\alpha }_{1} & {\beta }_{1} & & \\ {\beta }_{1} & {\alpha }_{2} & \ddots & \\ & \ddots & \ddots & {\beta }_{n-1}\\ & & {\beta }_{n-1} & {\alpha }_{n}\end{array}\right).\end{eqnarray}

Setzt man Q = (q1, q2, …, qn) mit qj ∈ ℝn, so berechnet das Lanczos-Verfahren die Spalten von Q sukzessive aus der Gleichung AQ = QTn. Dies führt auf die 3-Term-Rekursion für die qj \begin{eqnarray}A{q}_{j}={\beta }_{j-1}{q}_{j-1}+{\alpha }_{j}{q}_{j}+{\beta }_{j}{q}_{j+1},\end{eqnarray}

wobei β0q0 = 0.

Aus der Orthonormalität der qi folgt dann \({\alpha }_{j}={q}_{j}^{T}A{q}_{j}\) und, wenn \begin{eqnarray}{r}_{j}=(A-{\alpha }_{j}I){q}_{j}-{\beta }_{j-1}{q}_{j-1}\end{eqnarray}

ungleich Null ist, qj+1 = rjj mit βj = ||rj||2.

Zur Berechnung der nächsten Spalte qj+1 von Q benötigt man also lediglich die beiden vorhergehenden Spalten qj und qj−1. Da bei den Berechnungen zudem nur das Produkt von A mit einem Vektor benötigt wird, d. h. A selbst nicht verändert wird, verwendet man das Lanczos-Verfahren häufig zur näherungsweisen Berechnung einiger Eigenwerte und Eigenvektoren großer, sparser Matrizen. Dabei reduziert man A nicht vollständig zu der Tridiagonalmatrix Tn, sondern stoppt bei einem Tj, j < n. Man berechnet also nur die ersten j Spalten Qj = (q1, q2, …, qj) von Q, so daß \begin{eqnarray}A{Q}_{j}={Q}_{j}{T}_{j}+{r}_{j}{e}_{j}^{T}.\end{eqnarray}

Nun berechnet man die Eigenwerte \begin{eqnarray}{\lambda }_{1},\ldots, {\lambda }_{j}\in {\mathbb{R}}\end{eqnarray}

und orthonormalen Eigenvektoren \begin{eqnarray}{s}_{1},\ldots, {s}_{j}\in {{\mathbb{R}}}^{j}\end{eqnarray}

von Tj, d. h. \begin{eqnarray}{T}_{j}={S}_{j}{D}_{j}{S}_{j}^{T},\end{eqnarray}

mit Sj = (s1, …, sj), \({S}_{j}^{T}{S}_{j}=I\), und Dj = diag (λ1, …, λj). Ist rj = 0, dann sind die Eigenwerte λk, k = 1, …, j, der berechneten j-ten Hauptabschnittsmatrix Tj der Tridiagonalmatrix Tn Eigenwerte von A. Für rj ≠ 0, ist jedes λi eine gute Näherung an einen Eigenwert von A, für welches |βjsji| genügend klein ist (hierbei bezeichnet sji den letzten Eintrag des i-ten Eigenvektors si von Tj). Zugehöriger approximativer Eigenvektor von A ist dann yi = Qjsi. Auf diese Art und Weise approximiert man die extremalen Eigenwerte von A.

Es existieren zahlreiche Varianten des beschriebenen Lanczos-Verfahrens. Bei der numerischen Berechnung ist es z. B. erforderlich, die theoretisch gegebene Orthonormalität der Vektoren qi explizit zu erzwingen.

Zur Bestimmung der Eigenwerte der symmetrischen Tridiagonalmatrizen Tj ist der QR-Algorithmus gut geeignet, da man i. allg. an allen Eigenwerten von Tj interessiert ist.

Das Lanczos-Verfahren kann auch interpretiert werden als Methode zur Berechnung einer orthogonalen Basis {q1, q2, …, qn} für den Krylow-Raum \begin{eqnarray}\{{q}_{1},A{q}_{1},{A}^{2}{q}_{1},\ldots, {A}^{n-1}{q}_{1}\},\end{eqnarray}

bzw. als Methode zur Berechnung einer der Krylow-Matrix \begin{eqnarray}\begin{array}{lll}K(A,{q}_{1},n) & = & ({q}_{1},A{q}_{1},{A}^{2}{q}_{1},\ldots, {A}^{n-1}{q}_{1})\\ & = & ({q}_{1},{q}_{2},\ldots, {q}_{n})R=QR.\end{array}\end{eqnarray}

Diese Eigenschaft nutzt das konjugierte Gradientenverfahren aus, um ein lineares Gleichungssystem Ax = b mit symmetrischer positiv definiter Matrix A zu lösen.

Es existieren Verallgemeinerungen des Lanczos-Verfahren für nichtsymmetrische Matrizen A ∈ ℝn×n. In dem Falle wird eine nichtsinguläre Matrix X berechnet, welche die Matrix A auf (nichtsymmetrische) Tridiagonalgestalt \({\tilde{T}}_{n}=XA{X}^{-1}\) transformiert. Hierzu setzt man Y = X−T und berechnet, ausgehend von zwei gegebenen Vektoren y1, x1 mit \({y}_{1}^{T}{x}_{1}=1\), die Matrizen X = (x1, x2, …, xn) und Y = (y1, y2, …, yn) spaltenweise, so daß \begin{eqnarray}\begin{array}{rll}AX & = & X{\tilde{T}}_{n}\\ {A}^{T}Y & = & Y{\tilde{T}}_{n}^{T}\\ {Y}^{T}X & = & I\end{array}\end{eqnarray}

mit \begin{eqnarray}{\tilde{T}}_{n}=\left(\begin{array}{ccccc}{\alpha }_{1} & {\beta }_{1} & & & \\ {\gamma }_{1} & {\alpha }_{2} & {\beta }_{2} & & \\ & {\gamma }_{2} & \ddots & \ddots & \\ & & \ddots & \ddots & {\beta }_{n-1}\\ & & & {\gamma }_{n-1} & {\alpha }_{n}\end{array}\right)\end{eqnarray}

gilt. Wie beim symmetrischen Lanczos-Verfahren reduziert man A nicht vollständig zur Tridiagonal-matrix \({\tilde{T}}_{n}\), sondern stoppt bei einem \({\tilde{T}}_{j}\), j < n, und betrachtet die Eigenwerte von \({\tilde{T}}_{j}\) als Näherungen an die Eigenwerte von A. Im Gegensatz zum Lanczos-Verfahren für symmetrische Matrizen kann es hier vorkommen, daß die Berechnungen nicht durchgeführt werden können (da einer der Parameter, durch die dividiert wird, Null werden kann). Das Verfahren bricht dann zusammen, ohne relevante Informationen über Eigenwerte und Eigenvektoren zu liefern. In der Literatur existieren zahlreiche Vorschläge, wie dieses Problem umgangen werden kann.

Stets anwendbar ist in diesem Fall das Arnoldi-Verfahren, welches die Matrix A statt auf Tridiagonalgestalt auf obere Hessenberg-Form reduziert.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos