Kaczmarz–Steinhaus-módszer

A Kaczmarz–Steinhaus-módszer egy matematikai módszer bonyolultabb egyenletrendszerek számítógép segítségével történő megoldásához.

A módszer

A Kaczmarz módszer a lengyel származású Stefan Kaczmarz professzor munkáján alapszik. A módszer az Ax = b alakú lineáris egyenlet (vagy lineáris egyenletrendszer) megoldására szolgál. Ez egy ismétlődő algoritmus, melyet számos alkalmazási terület, köztük az orvosi képalkotás (computer tomography) és a digitális jelfeldolgozás (digital signal processing), alkalmaz.

A módszerhez szükségünk van egy invertálható A mátrixra (invertálható mátrix). Ellentétben más lineáris megoldó módszerekkel, nem szükséges, hogy ez a mátrix pozitív definit legyen. Ezen tulajdonsága miatt hasznos a felhasználási területeken. Ennek ellenére a többi ismétlődő algoritmus speciális esetekben jóval gyorsabb, mint a Kaczmarz-módszer.

Napjainkban a Kaczmarz-módszer egy változatát többismeretlenes, lineáris rendszereknél használnak, s mely módszert Thomas Strohmer és Roman Vershynin fejlesztett ki. Ezen megoldó nem függ az egyenlőség konstansaitól és felülmúl minden korábban ismert módszert. Egyszerűbb esetekben gyorsabb konvergenciára képes, mint a konjugált gradiens módszer.

Az általános (nem változtatott) algoritmus

Adjunk meg valós vagy komplex, m × n -es (n ≤ m) A mátrixot és egy valós vagy komplex b vektort. A következő iteráció jobb közelítésben kiszámolja x értékét:

$x_{k+1}=x_k+\frac{b_i-⟨a_i,x_k⟩}{\Vert a_i{\Vert }^2}{a}_i^{*}$

ahol $i\equiv k(\mathrm{mod}m)+1$ és $a_i$ az A mátrix i-edik sorbeli transzponáltja (transzponálás).

Kicsiny x a konvergencia szempontjából elhanyagolható, habár az a jobb, ha egy közelítő értéket választunk. A formula megadja a értékét. A teljes iterációt m -szer kell ismételni.

Szemléltetés és példák

Vegyük az egyenletrendszer mátrixos alakját:

$\left[\begin{array}{cccc}{a}_{11}& a_{12}& \dots & a_{1n}\\ a_{21}& a_{22}& \dots & a_{2n}\\ ⋮& ⋮& \ddots & ⋮\\ a_{m1}& a_{m2}& \dots & a_{mn}\end{array}\right]\cdot \left[\begin{array}{c}{x}_1\\ x_2\\ .\\ .\\ .\\ x_m\end{array}\right]=\left[\begin{array}{c}{b}_1\\ b_2\\ .\\ .\\ .\\ b_m\end{array}\right]$

A megoldás ezen hipersíkok metszete. Geometriailag a Kaczmarz módszer többszörös egymás utáni leképezést jelent sorrendben végighaladva az egyenletrendszer sorain. Például egy 2×1 –es mátrixra: Ax = b alak helyett $⟨a_1,x⟩=b_1$ illetve $⟨a_2,x,⟩=b_2$ alakot használjuk. $V_1$ jelölje az első egyenesre való vetítést. $V_2$ jelölje a második egyenesre való vetítést. $x_0$ egy kezdeti pont, ahonnan indul az iteráció. A Kaczmarz–Steinhaus-módszer értelmében a következő ismétlődést kapjuk:

$x_0,V_1(x_0),V_2(V_1(x_0)),V_1(V_2(V_1(x_0))),...$

Számszerű példa:

Adott két egyenes, melyek ax+by=c alakban vannak megadva. Adott egy kezdeti pont: (3,0). A kérdés a két egyenes metszéspontjának helye.

Megoldás: $a_{1}x+b_{1}y=c_1$ (adottak: $a_1=1,b_1=-1,c_1=0$ tehát: $x-y=0$)

$a_{2}x+b_{2}y=c_2$ (adottak: $a_2=1,b_2=0,c_2=1$ tehát: $x=1$)

képlet alapján:

$x_1=\frac{[b_1(b_1{x}_0-a_1{y}_0)+a_1{c}_1]}{a_1^2+b_1^2}=0,5$

$y_1=\frac{[b_1{c}_1-a_1(b_1{x}_0-a_1{y}_0)]}{a_1^2+b_1^2}=0,5$

ismételve:

$x_2=\frac{[b_2(b_2{x}_1-a_2{y}_1)+a_2{c}_2]}{a_2^2+b_2^2}=0,75$

$y_2=\frac{[b_2{c}_2-a_2(b_2{x}_1-a_2{y}_1)]}{a_2^2+b_2^2}=0,75$

folytatva: $x_n=0,999999...$

$y_n=0,999999...$

Tehát az x = 1 és y = 1 megoldásai az egyenlet rendszernek.

Az újabb változatú algoritmus

E link alatt található bővebb leírás. Ha i értéket véletlenszerűen választjuk, akkor jelentősen gyorsabb az algoritmus.

Források

• S. Kaczmarz. Angenäherte Auflösung von Systemen linearer Gleichungen. Bull. Internat. Acad. Polon.Sci. Lettres A, pages 335-357, 1937.
• W. Hackbusch Iterative Lösung großer schwachbesetzter Gleichungssysteme Teubner Studienbücher, 1993, pages 202-203
• Stachó László: Bevezetés a numerikus matematikába fizikusoknak című előadása és gyakorlata Az előadó honlapja

Fordítás

• Sablon:Fordítás