Krylow-Unterraum-Verfahren

Die Verfahrensklasse

Gegeben ist das lineare Gleichungssystem Ax = b mit der Matrix . Zu einer beliebigen Näherungslösung x₀ für x und dem Residuum r₀ = b - Ax₀ ist der m-te Krylow-Unterraum der von den Vektoren r₀ , Ar₀ , ..., A^m-1 r₀ aufgespannte Untervektorraum.

Fast alle Verfahren finden nun eine bessere Näherungslösung mit der Bedingung, dass der Vektor b - Ax_m orthogonal zu allen Vektoren eines Unterraumes steht, eine sogenannte Projektion. 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 , 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 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 und es ist für symmetrische, positiv definite Matrizen gedacht.

Man erhält so eine Vielfalt an Verfahren. Viel wichtiger als die Auswahl der speziellen Krylow-Unterraummethode ist die Wahl des Vorkonditionierers. Dieser formt das lineare Gleichungssystem äquivalent um, so dass die Lösung unverändert bleibt, sich aber günstigere Eigenschaften für die Konvergenz ergeben. Hier sind entscheidende Geschwindigkeitsgewinne zu erzielen, die dazu führen, dass selbst Systeme mit Millionen Unbekannten in wenigen Dutzend Schritten zufriedenstellend gelöst werden können.

Copyright- und Lizenzinformationen: Diese Seite basiert auf dem Artikel Krylow-Unterraum-Verfahren aus der freien Enzyklοpädιe Wιkιpedιa und steht unter der Lizenz Creative Commons CC-BY-SA 3.0 Unported (Kurzfassung). Liste der Autoren

Anbieterkennzeichnung