Kaczmarz-Methode

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 bessere Konvergenz im Falle überbestimmter Gleichungssysteme als andere iterative Lösungsverfahren.

Der ursprüngliche Algorithmus

Gegeben ist eine reelle oder komplexe m x n Matrix A (m >= n) von vollem Rang, 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:

$x_{k+1} = x_{k} + \frac{b_{i} - \langle a_{i},x_{k} \rangle}{\lVert a_{i} \rVert^2} a_{i}$ , wobei $i = (k \, \bmod \, m) + 1$

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.

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 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 $\lVert a_{i} \rVert ^2$ für jede Iteration.

Quellen

• S. Kaczmarz: Angenäherte Auflösung von Systemen linearer Gleichungen. Bull. Internat. Acad. Polon. Sci. Lettres A, pages 355-357, 1937.
• 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, pages 202-203

Einzelnachweis

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