Kaczmarz–Steinhaus-módszer

A Wikipédiából, a szabad enciklopédiából
Ugrás a navigációhoz Ugrás a kereséshez

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[szerkesztés]

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[szerkesztés]

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:

ahol és 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[szerkesztés]

Vegyük az egyenletrendszer mátrixos alakáját:

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 illetve alakot használjuk. jelölje az első egyenesre való vetítést. jelölje a második egyenesre való vetítést. egy kezdeti pont, ahonnan indul az iteráció. A Kaczmarz–Steinhaus-módszer értelmében a következő ismétlődést kapjuk:

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: (adottak: tehát: )

(adottak: tehát: )

képlet alapján:

ismételve:

folytatva:

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

Az újabb változatú algoritmus[szerkesztés]

E[1] 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[szerkesztés]

  • 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

Jegyzetek[szerkesztés]

  1. Thomas Strohmer and Roman Vershynin, A randomized solver for linear systems with exponential convergence [1] Archiválva 2006. november 18-i dátummal a Wayback Machine-ben

Fordítás[szerkeszté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.

További információk[szerkesztés]