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 nichtsinguläre 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 × n Matrix A (m ≥ n) von vollem Rang, sowie ein Vektor b. Die folgende Iterationsformel verbessert bei jedem Durchlauf die Annäherung an die Lösung x der Gleichung Ax = b:

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 transponierte i-te Zeile der Matrix A gemeint.

${\lVert a_{i}\rVert ^{2}}$ ist die quadrierte euklidische Norm von $a_{i}$ , die Summe der quadrierten Einträge von $a_{i}$ bzw. das Skalarprodukt $\langle a_{i},a_{i}\rangle$ .

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: 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.)
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

Einzelnachweis

Thomas Strohmer, Roman Vershynin: A randomized solver for linear systems with exponential convergence. (PDF; 155 kB)

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.

[1] Thomas Strohmer, Roman Vershynin: A randomized solver for linear systems with exponential convergence. (PDF; 155 kB)