Metoda Kaczmarza

Metoda Kaczmarza (lub algorytm Kaczmarza) – iteracyjny algorytm przybliżonego rozwiązywania układów równań liniowych. Po raz pierwszy została odkryta przez polskiego matematyka Stefana Kaczmarza i opublikowana w 1937 roku. Ponownie została odkryta w kontekście rekonstrukcji obrazu przez Richarda Gordona, Roberta Bendera i Gabora Hermana w 1970 r.

Niech $Ax=b$ będzie układem równań liniowych, $m$ liczbą wierszy $A,$ $a_{i}$ zaś $i$-tym wierszem macierzy $A,$ oraz niech $x^{0}$ będzie dowolnym, początkowym przybliżeniem rozwiązania układu $Ax=b.$ Dla $k=0,1,\dots$ niech:

$x^{k+1}=x^{k}+{\frac {b_{i}-\langle a_{i},x^{k}\rangle }{\|a_{i}\|^{2}}}a_{i}$

gdzie $i=k{\bmod {m}},i=1,2,\dots ,m.$

Jeżeli układ jest niesprzeczny, to tak otrzymany ciąg $(x^{k})$ ma granicę, która jest rozwiązaniem wyjściowego układu.

Metoda Kaczmarza znalazła zastosowanie m.in. w tomografii komputerowej oraz cyfrowym przetwarzaniu sygnałów.

Bibliografia

• S. Kaczmarz, Przybliżone rozwiązywanie układów równań liniowych – Angenäherte Auflösung von Systemen linearer Gleichungen, Bull. Int. Acad. Polon. Sci., Cl. Sci. Math., Ser. A, Sci. Nat., s. 22–24, 1937.
• R. Gabor, R. Bender, G.T. Herman, Algebraic reconstruction techniques (ART) for three-dimensional electron microscopy and x-ray photography, J. Theor. Biol. 29, s. 471–481, 1970.
• Y. Censor, S.A. Zenios, Parallel optimization: theory, algorithms, and applications, New York: Oxford University Press, 1997.
• R. Aster, B. Borchers, C. Thurber, Parameter Estimation and Inverse Problems, Elsevier, 2004.

Linki zewnętrzne

• Opis metody oraz oryginalny artykuł Kaczmarza, blog beta-iks.pl, 17 marca 2021 [dostęp 2021-08-18].