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}-\langle a_{i},x_{k}\rangle }{\lVert a_{i}\rVert ^{2}}}a_{i}^{*}$

ahol $i\equiv k{\pmod {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:

${\begin{bmatrix}a_{11}&a_{12}&\dots &a_{1n}\\a_{21}&a_{22}&\dots &a_{2n}\\\vdots &\vdots &\ddots &\vdots \\a_{m1}&a_{m2}&\dots &a_{mn}\end{bmatrix}}\cdot {\begin{bmatrix}x_{1}\\x_{2}\\.\\.\\.\\x_{m}\end{bmatrix}}={\begin{bmatrix}b_{1}\\b_{2}\\.\\.\\.\\b_{m}\end{bmatrix}}$

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 $\langle a_{1},x\rangle =b_{1}$ illetve $\langle a_{2},x,\rangle =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}={[b_{1}(b_{1}x_{0}-a_{1}y_{0})+a_{1}c_{1}] \over a_{1}^{2}+b_{1}^{2}}=0,5$

$y_{1}={[b_{1}c_{1}-a_{1}(b_{1}x_{0}-a_{1}y_{0})] \over a_{1}^{2}+b_{1}^{2}}=0,5$

ismételve:

$x_{2}={[b_{2}(b_{2}x_{1}-a_{2}y_{1})+a_{2}c_{2}] \over a_{2}^{2}+b_{2}^{2}}=0,75$

$y_{2}={[b_{2}c_{2}-a_{2}(b_{2}x_{1}-a_{2}y_{1})] \over 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

• Ez a szócikk részben vagy egészben a Kaczmarz method című angol Wikipédia-szócikk fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.