Lanczos-Verfahren

Lanczos-Verfahren

Das Lanczos-Verfahren[1] (nach Cornelius Lanczos) ist sowohl ein iterativer Algorithmus zur Bestimmung einiger Eigenwerte und eventuell der zugehörigen Eigenvektoren einer Matrix, als auch ein iterativer Algorithmus zur approximativen Lösung eines linearen Gleichungssystems. Der Algorithmus für Eigenwerte 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.

Inhaltsverzeichnis

Allgemeines

Das Verfahren der minimierten Iterierten, wie Lanczos es in seinen Originalarbeiten aus den Jahren 1950 (Eigenwerte) und 1952 (lineare Gleichungssysteme) nannte, basiert auf Projektionen auf 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 \mathcal{K}=\mathcal{K}(A,q) und \hat{\mathcal{K}}=\mathcal{K}(A^H,\hat{q}), wobei die zwei Startvektoren q\in\mathbb{C}^n und \hat{q}\in\mathbb{C}^n biorthogonal zueinander gewählt werden, also \hat{q}^Hq=1. Die Basen der Krylow-Räume werden gegeneinander mittels einer zweiseitigen Variante des 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 unsymmetrische Lanczos-Verfahren ist nicht immer mittels einer Kurztermrekursion durchführbar. Einen Ausweg stellen die aufgrund der Verbindung zu den formal orthogonalen Polynomen (FOPs) konstruierten Look-ahead-Varianten dar.

Wenn die Matrix A\in\mathbb{C}^{n\times n} hermitesch oder gar reell symmetrisch ist, erzwingt die Wahl von normalisiertem \hat{q}=q 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 symmetrische Lanczos-Verfahren dem Verfahren von Arnoldi mathematisch äquivalent, die (einzige) Basis ist eine Orthogonalbasis und die resultierende 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 Rundungsfehlern deutlich.

Varianten

Es existieren auch andere Varianten des Lanczos-Verfahrens, unter anderem eine Variante für das Eigenwertproblem für 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, statt dessen 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:

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.

Ins Deutsche übersetzt also in etwa:

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 Autoren 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.

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:

Recently, C. Lanczos developed a closely related routine based on his earlier paper on eigenvalue problem.

Ins Deutsche übersetzt also etwa:

Kürzlich entwickelte C. Lanczos ein eng [mit dem CG-Verfahren] verwandtes, auf seiner früheren Veröffentlichung über das Eigenwertproblem basierendes Verfahren.

Einzelnachweise

  1. http://www.cs.duke.edu/courses/fall06/cps258/references/Krylov-space/Lanczos-original.pdf Lanczos, C. (1951). 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.

Wikimedia Foundation.

Игры ⚽ Нужно сделать НИР?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Unsymmetrisches Lanczos-Verfahren — In der numerischen Mathematik ist das unsymmetrische Lanczos Verfahren einerseits ein iteratives Verfahren zur näherungsweisen Bestimmung einiger Eigenwerte und evtl. derer Eigenvektoren einer Matrix. Andererseits ist es aber auch die Grundlage… …   Deutsch Wikipedia

  • Symmetrisches Lanczos-Verfahren — In der numerischen Mathematik ist das symmetrische Lanczos Verfahren ein Verfahren zur Lösung von Eigenwertproblemen für symmetrische Matrizen . Es stellt sowohl einen Spezialfall des unsymmetrischen Lanczos Verfahrens, als auch des Arnoldi… …   Deutsch Wikipedia

  • Lanczos-Prozess — Das Lanczos Verfahren[1] (nach Cornelius Lanczos) ist sowohl ein iterativer Algorithmus zur Bestimmung einiger Eigenwerte und eventuell der zugehörigen Eigenvektoren einer Matrix, als auch ein iterativer Algorithmus zur approximativen Lösung… …   Deutsch Wikipedia

  • Lanczos — Cornelius Lanczos ([ˈlaːntsoʃ]; auch Kornél Löwy, Kornél Lánczos), (* 2. Februar 1893 in Székesfehérvár, Österreich Ungarn; † 25. Juni 1974 in Budapest) war ein ungarischer Mathematiker und Physiker. Inhaltsverzeichnis 1 Leben 2 Werk …   Deutsch Wikipedia

  • Lanczos-type product methods — Die Abkürzung LTPM steht für die englische Bezeichnung Lanczos type product methods, welche eine Klasse von auf dem (unsymmetrischen) Lanczos Verfahren basierenden Verfahren zur Lösung von linearen Gleichungssystemen Ax = b mit großen,… …   Deutsch Wikipedia

  • Cornelius Lanczos — ([ˈlaːntsoʃ]; auch Kornél Löwy, Kornél Lánczos; * 2. Februar 1893 in Székesfehérvár, Österreich Ungarn; † 25. Juni 1974 in Budapest) war ein ungarischer Mathematiker und Physiker. Inhaltsverzeichnis 1 Leben 2 Werk …   Deutsch Wikipedia

  • Krylov-Unterraum-Verfahren — Krylow Unterraum Verfahren sind iterative Verfahren zum Lösen großer, dünnbesetzter linearer Gleichungssysteme, wie sie bei der Diskretisierung von partiellen Differentialgleichungen entstehen oder von Eigenwertproblemen. Sie sind benannt nach… …   Deutsch Wikipedia

  • Krylow-Unterraum-Verfahren — sind iterative Verfahren zum Lösen großer, dünnbesetzter linearer Gleichungssysteme, wie sie bei der Diskretisierung von partiellen Differentialgleichungen entstehen oder von Eigenwertproblemen. Sie sind benannt nach dem russischen… …   Deutsch Wikipedia

  • Numerische Verfahren — Die Liste numerischer Verfahren führt Verfahren der numerischen Mathematik nach Anwendungsgebieten auf. Inhaltsverzeichnis 1 Lineare Gleichungssysteme 2 Nichtlineare Gleichungssysteme 3 Numerische Integration 4 Approximation und Interpolation …   Deutsch Wikipedia

  • CG-Verfahren — Ein Vergleich des einfachen Gradientenverfahren mit optimaler Schrittlänge (in grün) mit dem CG Verfahren (in rot) für die Minimierung der quadratischen Form eines gegebenen linearen Gleichungssystems. CG konvergiert nach 2 Schritten, die Größe… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”