Kaczmarz-Methode

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

Die auf der Arbeit des polnischen Mathematikers Stefan Kaczmarz basierte Kaczmarz-Methode dient der iterativen Lösung linearer Gleichungssysteme der Form , wobei eine, evtl. nicht-quadratische, Matrix, b die gegebene rechte Seite und x der gesuchte Lösungsvektor ist. Es handelt sich dabei um einen iterativen Algorithmus, der unter anderem Einzug in die Computertomographie und digitale Signalverarbeitung gefunden hat.

Im Gegensatz zu den meisten anderen iterativen Lösungsverfahren, wie zum Beispiel dem Gauß-Seidel-Verfahren, benötigt der Kaczmarz-Algorithmus keine invertierbare Matrix A. Insbesondere im unter-bestimmten Fall mit lässt sich damit die Lösung kleinster Norm zur Pseudoinversen berechnen. Aus diesem Grund kann das Verfahren für praktisch alle Anwendungen problemlos eingesetzt werden, obwohl Verfahren für spezielle Problemstellungen wesentlich schneller sein können. Allerdings zeigt eine randomisierte Variante des Kaczmarz-Verfahrens wesentlich bessere Konvergenz im Falle überbestimmter Gleichungssysteme als andere iterative Lösungsverfahren.

Der ursprüngliche Algorithmus

[Bearbeiten | Quelltext bearbeiten]

Gegeben ist eine reelle (oder auch komplexe) m × n Matrix von vollem Rang, sowie ein Vektor . Die folgende Iterationsformel verbessert bei jedem Durchlauf die Annäherung an eine Lösung x der Gleichung Ax = b:

,

Bei der deterministischen Variante wird der Index i zyklisch gewählt,

und ist ein positiver Relaxationsparameter, der in der ursprünglichen Version gleich eins war. Dabei ist mit die transponierte i-te Zeile der Matrix A gemeint, ist die quadrierte euklidische Norm von , die Summe der quadrierten Einträge von bzw. das Skalarprodukt . Das Verfahren ist besonders effizient bei dünn-besetzter Matrix, wenn die Vektoren nur wenige nichttriviale Elemente besitzen.

Geometrisch projiziert der einzelne Iterationsschritt den aktuellen Näherungsvektor orthogonal auf die i-te Hyperebene, es gilt

Mit dem Startwert konvergiert die Iteration im unterbestimmten Fall gegen die Lösung kleinster Norm zur Pseudoinversen . Im überbestimmten, inkonsistenten Fall springen die Iterierten am Ende allerdings zwischen den Hyperebenen hin und her, und man bekommt nur bei starker Unter-Relaxation mit eine brauchbare Näherung an die Kleinste-Quadrate-Lösung .

Querverbindung zu anderen Iterationsverfahren

[Bearbeiten | Quelltext bearbeiten]

Im unterbestimmten Fall mit vollem Rang von A liegt die Lösung minimaler Norm im orthogonalen Komplement des Kerns/Nullraums , der mit dem Bildraum der transponierten Matrix übereinstimmt. Daher lässt sich darstellen als . Somit ist die eindeutige Lösung des Gleichungssystems

mit positiv definiter Matrix . Wenn man die Iteration mit dem Startwert beginnt, liegen offensichtlich auch alle Iterierten im Bildraum von . Daher hat jede Iterierte eine eindeutige Darstellung . Mit dieser wird der Iterationsschritt zu

wobei den i-ten Einheitsvektor bezeichnet. Da A vollen Rang besitzt, bedeutet das

Dies ist aber genau der Teilschritt in einer einzelnen Komponente für das Einzelschritt-/Gauß-Seidel-Verfahren () beziehungsweise mit allgemeinem das SOR-Verfahren zum System , deren wohlbekannte Konvergenzaussagen sich also auf die Kaczmarz-Iteration übertragen. Z.B. konvergiert diese für festes .

Randomisierter Algorithmus

[Bearbeiten | Quelltext bearbeiten]

Wie bereits weiter oben erwähnt, gibt es eine Variante des Verfahrens, die im Falle überbestimmter Gleichungssysteme wesentlich schneller konvergiert.[1] Dabei wird bessere Konvergenz nicht nur für das Lösen hochgradig überbestimmter Gleichungssysteme erreicht, sondern bspw. auch beim Lösen von Systemen mit 10 % mehr Gleichungen als Unbekannten. Hierzu muss bei der obigen Iterationsgleichung das i nicht abhängig von k, sondern zufällig (daher der Name der Methode) gewählt werden. Die Wahrscheinlichkeit für ein bestimmtes i ist hierbei proportional zu für jede Iteration.

Ungleichungssysteme

[Bearbeiten | Quelltext bearbeiten]

Eine einfache Modifikation des Verfahrens kann zulässige Lösungen für Ungleichungssysteme , berechnen. Beim Schritt

wird eine Änderung nur durchgeführt, wenn ist, also die i-te Ungleichung verletzt ist. Dann wird von außen auf den i-ten Halbraum projiziert.

Auf diese Weise lassen sich mit dem Verfahren sogar Lineare Programme lösen über die Äquivalenz von Optimierungs- und Zulässigkeitsproblemen.

  • S. Kaczmarz: Przyblizone rozwiazywanie ukladów równan liniowych. – Angenäherte Auflösung von Systemen linearer Gleichungen. Bulletin International de l’Académie Polonaise des Sciences et des Lettres. Classe des Sciences Mathématiques et Naturelles. Série A, Sciences Mathématiques, S. 355–357, 1937. (Achtung: Dieser Artikel wird sehr verbreitet mit der falschen Seitenangabe 335–357 zitiert.)
  • M. Hanke-Bourgeois; W. Niethammer: On the acceleration of Kaczmarz's method for inconsistent linear systems; Linear Algebra Applcs 130 (1990), 83–98
  • A.Björck, T. Elfving: Accelerated projection methods for computing pseudoinverse solutions of systems of linear equations, BIT 19 (1979), 145–163
  • T. Strohmer, R. Vershynin: A randomized Kaczmarz algorithm with exponential convergence, J. Fourier Anal. Appl. 15(1), 262–278, 2009
  • W. Hackbusch: Iterative Lösung großer schwachbesetzter Gleichungssysteme. Teubner Studienbücher, 1993, S. 202–203
  1. Thomas Strohmer, Roman Vershynin: A randomized solver for linear systems with exponential convergence. (PDF; 155 kB)