Krylow-Unterraum-Verfahren

Krylow-Unterraum-Verfahren sind iterative Verfahren zum Lösen von großen, dünnbesetzten linearen Gleichungssystemen, wie sie bei der Diskretisierung von partiellen Differentialgleichungen entstehen oder von Eigenwertproblemen. Sie sind benannt nach dem russischen Mathematiker Nikolai Mitrofanowitsch Krylow, der die Krylow-Unterräume definierte. Mit dem hier beschriebenen Verfahren hat er nichts zu tun. Die Verfahren sind sogenannte Black-Box-Verfahren, die sich durch einfache Implementierung und Robustheit auszeichnen, weshalb sie in der Industrie und den Universitäten vielfach verwandt werden.

Die Verfahren sind Spezialfälle von Projektions-Verfahren.

Wir betrachten das lineare Gleichungssystem $\mathbf{A}x=b$ .

Mit einer (beliebigen) Näherungslösung $x 0$ für $x$ bilden wir das Residuum $r_0=b-\mathbf{A}x_0$ .

Der zugehörige m-te Krylow-Unterraum ${\mathcal K}_m$ ist dann der von den Vektoren $r_0, \mathbf{A}r_0, ..., \mathbf{A}^{m-1}r_0$ aufgespannte Untervektorraum.

Eine bessere Näherungslösung $x_{m} \in x_{0}+{\mathcal K}_m$ erhält man mit der Bedingung, dass der Vektor $b-\mathbf{A} x_{m}$ orthogonal zu allen Vektoren eines Unterraumes ${\mathcal L}_m$ steht. Diese Bedingung heißt Galerkin-Bedingung.

Damit ist das Problem auf ein m-dimensionales lineares Gleichungssystem reduziert. Das Ganze wird zu einem Iterativen Lösungsverfahren, wenn man die Dimension in jedem Schritt um eins erhöht.

Spezielle Lösungsverfahren ergeben sich durch die konkrete Wahl des Raumes ${\mathcal L}_m$ , sowie durch Ausnutzen von speziellen Eigenschaften der Matrix $A$ , was das Verfahren beschleunigt, aber die Anwendbarkeit auch einschränkt. Die einfachste Variante ist, für ${\mathcal L}_m$ einfach wieder den Krylow-Unterraum selbst zu wählen. Das besondere an den Verfahren ist, dass sie nur Matrix-Vektor-Multiplikationen sowie Skalarprodukte benötigen. Ist die Matrix dünnbesetzt, so ist das Matrix-Vektor-Produkt schnell ausrechenbar und der Algorithmus praktikabel.

Ein Beispiel ist das Verfahren der Konjugierten Gradienten (CG-Verfahren). Hierbei ist ${\mathcal L}_m={\mathcal K}_m$ und es ist für symmetrische, positiv definite Matrizen gedacht.

Man erhält so einen großen Zoo an Verfahren. Viel wichtiger als die Auswahl der speziellen Krylov-Unterraummethode ist die Wahl des Vorkonditionierers. Dieser formt das lineare Gleichungssystem äquivalent um, um das Verfahren zu beschleunigen. Hier sind entscheidende Geschwindigkeitsgewinne zu erzielen, die dazu führen, dass selbst Systeme mit Millionen Unbekannten in wenigen Schritten zufriedenstellend gelöst werden können.

Geschichte

Das erste Krylow-Unterraumverfahren war das CG-Verfahren, dass 1952 von Hestenes und Stiefel veröffentlicht wurde. Jenes ist sogar ein direkter Löser, der nach n Schritten bei exakter Arithmetik die exakte Lösung produziert. Allerdings ist das Verfahren als direkter Löser ungeeignet. Der Nutzen als iterativer Löser wurde damals noch nicht erkannt und so verschwand das Verfahren in der Schublade. Ende der 1970er wurde der Nutzen dann erkannt und eine Vielzahl an Verfahren wie GMRES oder BiCGSTAB wurde entwickelt.

Literatur

A. Meister: Numerik linearer Gleichungssysteme, Vieweg 1999, ISBN 3-528-03135-2

Y. Saad: Iterative Methods for Sparse Linear Systems, 2nd edition, SIAM Society for Industrial & Applied Mathematics 2003, ISBN 0-898-71534-2

Y. Saad: Iterative Methods for Sparse Linear Systems, 1st edition, PWS 1996

Templates for the Solution of Linear Systems

Krylow-Unterraum-Verfahren

Geschichte

Literatur

See also: Krylow-Unterraum-Verfahren, 1952, 1970er, Diskretisierung, Eigenwertproblem, Iterationsverfahren, Lineares Gleichungssystem, Nikolai Mitrofanowitsch Krylow, Partielle Differentialgleichung, Skalarprodukt