Kaczmarz-Methode

aus Wikipedia, der freien Enzyklopädie

Die auf der Arbeit des polnischen Mathematikers Stefan Kaczmarz basierte Kaczmarz-Methode dient der iterativen Lösung linearer Gleichungssysteme der Form Ax = b, wobei A eine lösbare und u.U. überdefinierte Matrix, b die gegebene Lösung 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 nur eine invertierbare, nicht aber positiv-definite, Matrix A. 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 größere Konvergenz im Falle überbestimmter Gleichungssysteme als andere iterative Lösungsverfahren.

Inhaltsverzeichnis 1 Der ursprüngliche Algorithmus 2 Randomisierter Algorithmus 3 Quellen 4 Einzelnachweis

[Bearbeiten] Der ursprüngliche Algorithmus

Gegeben ist eine reelle oder komplexe invertierbare m x n Matrix A (m <= n), sowie ein Lösungsvektor b für die Gleichung (Ax = b). Die folgende Iterationsformel verbessert bei jedem Durchlauf die Annäherung an die Lösung:

, wobei

Dabei ist mit a_i die i - te transponierte Zeile der Matrix A gemeint.

Der Startwert kann zufällig gewählt werden, sollte aber, falls eine einfache Abschätzung bzgl. der Lösung getroffen werden kann, möglichst nahe an der Lösung gewählt werden.

[Bearbeiten] Randomisierter Algorithmus

Wie bereits weiter oben erwähnt, gibt es eine Variante des Verfahrens, die im Falle überbestimmter Gleichungssysteme wesentlich schneller konvergiert.^[1] Dabei wird größere Konvergenz nicht nur für das Lösen hochgradig überbestimmter Gleichungssyteme 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.

[Bearbeiten] Quellen

• S. Kaczmarz. Angenäherte Auflösung von Systemen linearer Gleichungen. Bull. Internat. Acad. Polon.Sci. Lettres A, pages 335-357, 1937.
• A randomized solver for linear systems with exponential convergence Thomas Strohmer and Roman Vershynin
• W. Hackbusch Iterative Lösung großer schwachbesetzter Gleichungssysteme Teubner Studienbücher, 1993, pages 202-203

[Bearbeiten] Einzelnachweis

1. ↑ A randomized solver for linear systems with exponential convergence Thomas Strohmer und Roman Vershynin(pdf)