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

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

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

Jeżeli układ jest niesprzeczny, to tak otrzymany ciąg ${\displaystyle (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].