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.Szablon: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-⟨a_i,x^k⟩}{\Vert a_i{\Vert }^2}{a}_i$

gdzie $i=kmodm,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].