imported>Horst Gräbner: willkürlicher Wikilink

2024-09-16T16:09:20Z

willkürlicher Wikilink

Neue Seite

Das '''Lanczos-Verfahren'''<ref name="An Iteration Method for the Solution of the Eigenvalue Problem of Linear
Differential and Integral Operators">https://www2.cs.duke.edu/courses/fall06/cps258/references/Krylov-space/Lanczos-original.pdf Lanczos, C. (1950). An Iteration Method for the Solution of the Eigenvalue Problem of Linear
Differential and Integral Operators. ''Journal of research of the National Bureau of Standards, 45'', 255–282.</ref> (nach [[Cornelius Lanczos]]) ist sowohl ein [[Iteration|iterativer]] [[Algorithmus]] zur Bestimmung einiger [[Eigenwertproblem|Eigenwerte]] und eventuell der zugehörigen [[Eigenwertproblem|Eigenvektoren]] einer [[Matrix (Mathematik)|Matrix]] als auch ein iterativer Algorithmus zur approximativen Lösung eines [[Lineares Gleichungssystem|linearen Gleichungssystems]]. Der Algorithmus für Eigenwerte [[Konvergenz (Mathematik)|konvergiert]] am schnellsten gegen die gut von den anderen Eigenwerten separierten, meist gegen die betragsgrößten Eigenwerte. Der Algorithmus für lineare Gleichungssysteme ist im allgemeinen Fall dem [[BiCG-Verfahren]] und für spezielle Matrizen dem [[CG-Verfahren]] mathematisch äquivalent.

== Allgemeines ==
Das Verfahren der minimierten Iterierten, wie Lanczos es in seinen Originalarbeiten aus den Jahren 1950 (Eigenwerte) und 1952 (lineare Gleichungssysteme) nannte, basiert auf [[Projektion (lineare Algebra)|Projektionen]] auf [[Krylow-Unterraum-Verfahren|Krylow-Unterräume]]. Je nach den Eigenschaften der Matrix, deren Eigenwerte berechnet werden sollen, werden ein oder zwei Krylow-Unterräume aufgespannt. Das generelle Verfahren basiert auf zwei Krylow-Unterräumen <math>\mathcal{K}=\mathcal{K}(A,q)</math> und <math>\hat{\mathcal{K}}=\mathcal{K}(A^H,\hat{q})</math>, wobei die zwei Startvektoren <math>q\in\mathbb{C}^n</math> und <math>\hat{q}\in\mathbb{C}^n</math> [[Biorthogonalität|biorthogonal]] zueinander gewählt werden, also <math>\hat{q}^Hq=1</math>. Die Basen der Krylow-Räume werden gegeneinander mittels einer zweiseitigen Variante des [[Gram-Schmidtsches Orthogonalisierungsverfahren|Verfahrens von Gram-Schmidt]] biorthogonalisiert.

== Eigenwertnäherung ==
Zur Eigenwertnäherung werden die beiden obengenannten Basen und die schiefe Projektion der gegebenen Matrix, meist auf eine [[Tridiagonalmatrix]], herangezogen.
Das resultierende [[Unsymmetrisches Lanczos-Verfahren|unsymmetrische Lanczos-Verfahren]] ist nicht immer mittels einer Kurztermrekursion durchführbar. Einen Ausweg stellen die aufgrund der Verbindung zu den formal [[Orthogonale Polynome|orthogonalen Polynomen]] (FOPs) konstruierten Look-ahead-Varianten dar.

Wenn die Matrix <math>A\in\mathbb{C}^{n\times n}</math> [[Hermitesche Matrix|hermitesch]] oder gar reell [[Symmetrische Matrix|symmetrisch]] ist, erzwingt die Wahl von normalisiertem <math>\hat{q}=q</math> eine Übereinstimmung der beiden Krylow-Räume und verhindert einen Zusammenbruch der Biorthogonalisierung, welche jetzt eine Orthogonalisierung darstellt. In diesem speziellen Fall ist das resultierende [[Symmetrisches Lanczos-Verfahren|symmetrische Lanczos-Verfahren]] dem [[Arnoldi-Verfahren|Verfahren von Arnoldi]] mathematisch äquivalent, die (einzige) Basis ist eine Orthogonalbasis und die resultierende [[Orthogonalprojektion|orthogonale Projektion]] der Matrix ist (in aller Regel) eine hermitesche Tridiagonalmatrix. Gravierende Unterschiede zwischen dem Arnoldi-Verfahren und dem symmetrischen Lanczos-Verfahren werden erst bei der Ausführung in endlicher Genauigkeit, also unter Einfluss von [[Rundungsfehler]]n deutlich.

== Varianten ==
Es existieren auch andere Varianten des Lanczos-Verfahrens, unter anderem eine Variante für das [[Eigenwertproblem]] für [[Symplektische Matrix|symplektische Matrizen]], welches diese auf sogenannte Butterfly-Form abbildet und eine Variante für komplexe symmetrische Matrizen.

== Approximative Lösung von Gleichungssystemen ==
Lanczos’ Verfahren zur approximativen Lösung von Gleichungssystemen wird selten in der ursprünglichen Form verwendet, stattdessen wird es als [[BiCG-Verfahren]] oder als [[CG-Verfahren]] eingesetzt.

== Verwandtschaften und geschichtlicher Kontext ==
Die beiden von Lanczos veröffentlichten Verfahren sind [[Krylow-Unterraum-Verfahren]]. Dieser Sachverhalt, besser, diese Verwandtschaft, wurde bereits vor der ersten Veröffentlichung von [[Alexander Markowitsch Ostrowski]] Lanczos kundgetan, wovon eine Fußnote auf der ersten Seite der ersten Veröffentlichung von Lanczos zeugt. Dort steht im Originalartikel:

{{Zitat
|Text=The literature available to the author showed no evidence that the methods and results of the present investigation have been found before. However, A. M. Ostrowski of the University of Basle and the Institute for Numerical Analysis informed the author that his method parallels the earlier work of some Russian scientists: the references given by Ostrowski are: A. Krylov, Izv. Akad. Nauk SSSR 7, 491 to 539 (1931); N. Luzin, Izv. Akad. Nauk. SSSR 7, 903 to 958 (1931). On the basis of the reviews of these papers in the Zentralblatt, the author believes that the two methods coincide only in the point of departure. The author has not, however, read these Russian papers.
|Übersetzung=In der dem Autor zugänglichen Literatur fand sich kein Hinweis darauf, dass die Methoden und Resultate dieser Untersuchung bereits zuvor entdeckt worden waren. Allerdings unterrichtete A. M. Ostrowski von der Universität Basel vom Institut für Numerische Analysis den Autor darüber, dass seine Methode den früheren Arbeiten einiger russischer Wissenschaftler entspricht. Die von Ostrowski gegebenen Referenzen sind: A. Krylov, Izv. Akad. Nauk SSSR 7, 491 bis 539 (1931); N. Luzin, Izv. Akad. Nauk. SSSR 7, 903 bis 958 (1931). Aufgrund der Besprechungen dieser Artikel im Zentralblatt glaubt der Autor, dass die beiden Methoden nur im Ausgangspunkt übereinstimmen. Der Autor hat diese russischen Veröffentlichungen selbst allerdings nie gelesen.
|Sprache=en}}

Eine Darstellung von dem von Krylow entwickelten Verfahren findet sich im Buch von Faddejew und Faddejewa ''Numerische Methoden der linearen Algebra''.

Wenn die Matrix selbstadjungiert (symmetrisch reell oder hermitesch) ist, ist die berechnete Basis orthogonal. Aufbauend auf Lanczos' Arbeit brachte das [[Walter Edwin Arnoldi]] auf die Idee, ''immer'' eine orthogonale Basis zu erzwingen, was zur Folge hat, dass die projizierte Matrix keine Tridiagonalmatrix mehr, sondern nur noch eine obere [[Hessenbergmatrix]] ist. Der resultierende Algorithmus ist das [[1951]] veröffentlichte [[Arnoldi-Verfahren]].

Das Verfahren ist im allgemeinen Fall dem [[BiCG-Verfahren]] und im Falle einer symmetrischen reellen (nicht notwendig positiv definiten) oder hermiteschen (ebenfalls nicht notwendig positiv definiten) Matrix dem kurz darauf veröffentlichten [[CG-Verfahren]] von [[Magnus Rudolph Hestenes]] und [[Eduard Stiefel]] äquivalent. Die Verwandtschaft mit dem CG-Verfahren war auch den beiden Autoren bereits bekannt. Auf Seite 410 (der zweiten Seite) ihrer Veröffentlichung schreiben sie:

{{Zitat
|Text=Recently, C. Lanczos developed a closely related routine based on his earlier paper on eigenvalue problem.
|Übersetzung=Kürzlich entwickelte C. Lanczos ein eng [mit dem CG-Verfahren] verwandtes, auf seiner früheren Veröffentlichung über das Eigenwertproblem basierendes Verfahren.
|Sprache=en}}

== Ablauf des Lanczos-Verfahrens bei hermiteschen Matrizen ==
Obwohl das Lanczos-Verfahren das geringfügig ältere Verfahren ist, lohnt sich im interessantesten, dem hermiteschen Fall der Vergleich als Spezialfall des [[Arnoldi-Verfahren]]s. Das Arnoldi-Verfahren berechnet bei einer Matrix <math>A\in\Complex^{n\times n}</math> nach <math>m</math> Schritten eine [[Orthonormalbasis]] <math>Q_m=(q_1,\ldots,q_m)\in\Complex^{n\times m}</math> eines [[Krylow-Unterraum]]s, für welche gilt
:<math>AQ_m=Q_mH_m+h_{m+1,m}q_{m+1}e_m^T.</math>
Dabei ist <math>H_m=Q_m^H AQ_m</math> eine [[Hessenbergmatrix]].
Im hermiteschen Fall mit <math>A^H=A</math> ist dann aber auch <math>H_m^H=Q_m^H A^H Q_m=Q_m^H AQ_m=H_m</math> hermitesch, also sogar eine hermitesche [[Tridiagonalmatrix]]
:<math> H_m=T_m=\begin{pmatrix}
\alpha_1 & \beta_1 & 0 & \ldots & 0 & \\
\beta_1 & \alpha_2 & \beta_2 & \ddots & \vdots \\
0 & \ddots & \ddots & \ddots & 0 \\
\vdots & \ddots & \beta_{m-2} & \ddots & \beta_{m-1} \\
0 & \dots & 0 & \beta_{m-1} & \alpha_m
\end{pmatrix}.</math>
Betrachtet man nun mit dieser Information die <math>k</math>-te Spalte <math>Aq_k</math> von <math>AQ_m</math>, erhält man die einfache Beziehung
:<math> Aq_k=\beta_{k-1}q_{k-1}+\alpha_kq_k+\beta_kq_{k+1}.</math>
Wegen <math>\alpha_k=q_k^H Aq_k</math> kann man diese nach den einzigen Unbekannten <math>r_k:=\beta_kq_{k+1}</math> auflösen, wobei <math>\beta_k</math> wegen <math>\|q_{k+1}\|_2=1</math> die Norm von <math>r_k</math> ist. Damit vereinfacht sich der Algorithmus aus dem Artikel [[Arnoldi-Verfahren]] mit einem nichttrivialen Startvektor <math>r_0\in\Complex^n</math> zum hermiteschen (symmetrischen) Lanczos-Verfahren
:<math>q_0\leftarrow 0,\beta_0\leftarrow 1,</math>
:for <math>k\in\mathbb{N}</math> and <math>r_{k-1}\not=0</math> do
::<math>\beta_{k-1}\leftarrow \|r_{k-1}\|</math>
::<math>q_k\leftarrow r_{k-1}/\beta_{k-1}</math>
::<math>r_k\leftarrow Aq_k</math>
:: <math>\alpha_{k}\leftarrow q_k^H r_k</math>
:: <math>r_k\leftarrow r_k-q_k\alpha_k-q_{k-1}\beta_{k-1}</math>
: end for
Im Vergleich zum [[Arnoldi-Verfahren]] (für beliebige quadratische Matrizen geeignet), welches bis zum Schritt <math>m\le n</math> einen quadratisch wachsenden Aufwand von <math>O(m^2\cdot n)</math> Operationen alleine für die Orthogonalisierung benötigt, braucht dieser Algorithmus (für hermitesche oder symmetrische Matrizen) zusätzlich zu den <math>m</math> Matrix-Vektor-Multiplikationen nur <math>O(m\cdot n)</math> Operationen, ist also erheblich effizienter. Auch die Berechnung aller Eigenwerte von <math>T_m</math> als Approximation an die von <math>A</math> kostet wegen der schnellen Konvergenz des [[QR-Algorithmus]] nur wenig Aufwand.

Allerdings gelten die Aussagen nur bei exakter Rechnung, der Algorithmus ist anfällig gegen Rundungsfehler. Denn obwohl eine Orthogonalisierung von <math>q_{k+1}</math> im Lanczos-Verfahren nur gegen den vorherigen Basivektor <math>q_k</math> erfolgt, sind in der Theorie dennoch alle Basisvektoren paarweise orthogonal. Bei Rechnung mit endlicher Genauigkeit geht diese Orthogonalität allerdings oft verloren, da sich sozusagen große Eigenwerte von <math>A</math>, die schon in einer Matrix <math>T_k</math> repräsentiert sind, über Rundungsfehler nochmal einschleichen und in Matrizen <math>T_m,\ m\gg k,</math> dann für falsche Geister-Eigenwerte sorgen. Diesen Problemen begegnet man mit Re-Orthogonalisierungen. Um den Aufwand dabei in Grenzen zu halten, verwendet man eine selektive Re-Orthogonalisierung gegen einige, schon berechnete, Näherungs-Eigenvektoren.

== Einzelnachweise ==
<references />
== Literatur ==
* Martin Hanke-Bourgeois: ''Grundlagen der Numerischen Mathematik und des Wissenschaftlichen Rechnens.'' 3. Auflage, Vieweg+Teubner, Wiesbaden 2009.
* Gene H. Golub, Charles F. Van Loan: ''Matrix Computations.'' 3. Auflage. The Johns Hopkins University Press, 1996, ISBN 0-8018-5414-8.
[[Kategorie:Numerische lineare Algebra]]

Lanczos-Verfahren - Versionsgeschichte

imported>Horst Gräbner: willkürlicher Wikilink