Gauss–Seidel-módszer

A Gauss–Seidel néven ismert eljárás egy iteratív módszer, alkalmas a nagyobb méretű, nem feltétlenül ritka együttható-mátrixú lineáris egyenletrendszerek megoldására. Indirekt módszer, amely – a direkt módszerekkel ellentétben – nem véges, előre meghatározott számú lépés után téríti vissza a keresett megoldásvektort tökéletesen pontosan (ha a kerekítési hibáktól eltekintünk), hanem az eljárás során az iterációs lépéseket addig ismételjük, míg egy általunk meghatározott pontosságig az ismeretleneket meg nem határozzuk, tehát akkor állunk meg a lépesekkel, mikor már két egymás utáni lépésben kapott ismeretlen értékek különbsége kisebb egy általunk meghatározott értéknél (vagyis, ha hiba elhanyagolható).

A Gauss–Seidel-módszer hasonlít a Jacobi-módszerhez. Mindkét módszer ugyanahhoz a megoldáshoz konvergál, de a Gauss–Seidel-módszer konvergenciája gyorsabb, mert a következő $x_{n}$ ismeretlen kiszámításához felhasználja az ugyanabban a ciklusban már kiszámolt $x_{n-1},x_{n-2}....$ stb. ismeretlenek értékeit. Ez azt jelenti, hogy ugyanolyan pontosság eléréséhez ezzel a módszerrel kevesebb iterációt kell végrehajtanunk.

Leírás

A Gauss–Seidel-módszer esetében az iterációs képlet a következő lesz:

$x_{i}^{(k+1)}={b_{i} \over a_{ii}}-\sum _{l=1}^{(i-1)}{a_{il} \over a_{ii}}x_{l}^{(k+1)}-\sum _{l=i+1}^{(n)}{{a_{il} \over a_{ii}}x_{l}^{(k)}}$

A módszer elvének megértése érdekében tekintsünk egy példát:

${\begin{pmatrix}a_{11}&a_{12}\\a_{21}&a_{22}\end{pmatrix}}{x_{1} \choose x_{2}}={b_{1} \choose b_{2}}$

Az áttekinthetőség kedvéért átírjuk egyenletek formájába:

${\begin{cases}a_{11}x_{1}+a_{12}x_{2}=b_{1}\\a_{21}x_{1}+a_{22}x_{2}=b_{2}\end{cases}}$

Innen kifejezhető az x₁ és x₂ ismeretlen, így a következő egyenleteket kapjuk:

$x_{1}=-{a_{12} \over a_{11}}x_{2}+{b_{1} \over a_{11}}$,

$x_{2}=-{a_{21} \over a_{22}}x_{1}+{b_{2} \over a_{22}}$

Az így kapott egyenletrendszert úgy oldhatjuk meg, hogy kezdetben kiindulunk az $x_{1}^{(0)}$, illetve az $x_{2}^{(0)}$ legjobb becslésünkből, vagy az egyszerűség kedvéért indulhatunk 0-ból is. Ezután felhasználva az

$x_{1}^{(k)}=-{a_{12} \over a_{11}}x_{2}^{(k-1)}+{b_{1} \over a_{11}}$,

$x_{2}^{(k)}=-{a_{21} \over a_{22}}x_{1}^{(k-1)}+{b_{2} \over a_{22}}$

lépéseket, eljuthatunk egy jobb közelítő értékig.

Az $x_{2}$ kiszámítására már használhatjuk az $x_{1}$ új értékét is. Vagyis:

$x_{1}^{(k)}=-{a_{12} \over a_{11}}x_{2}^{(k-1)}+{b_{1} \over a_{11}}$

$x_{2}^{(k)}=-{a_{21} \over a_{22}}x_{1}^{(k)}+{b_{2} \over a_{22}}$

Ebben az esetben a Gauss–Seidel-féle iterációs módszert kapjuk eredményül.

Konvergencia

A módszer konvergenciája függ az $A$ mátrixtól, vagyis iterációs eljárással eljutunk a megoldásig, ha:

• $A$ szigorúan diagonálisan domináns
• $A$ szimmetrikus pozitív-definit

Egy általános, $x^{(k)}=Gx^{(k-1)}+c$ alakú iterációs képlet akkor konvergál bármely kezdeti $x^{(0)}$vektor esetén, ha a $G$ mátrix spektrálsugara kisebb, mint $1$:

$\lim \|x^{(k)}-x\|=0\Longleftrightarrow \rho (G)<1$ , $x$a megoldásvektor.

Általánosabban tárgyalva a problémát, feladatunk a ${\textstyle Ax=b}$ alakú egyenletrendszer megoldása. Így a fentebb tárgyalt iterációs képlet mátrix-alakban a következő:

$$x^{(k)}=(I-Q^{-1}A)x^{(k-1)}+Q^{-1}b$$

ahol a $Q$ mátrix $A$ főátlóját és a főátló alatti elemeit tartalmazza. Ez olyan, mintha a fenti egyenletrendszerünkben az összes egyenletből kifejeztük volna a változókat. Bizonyított, hogy a $(I-Q^{-1}A)$ mátrix sugara kisebb, mint $1$, ha az A mátrix szigorúan diagonálisan domináns, tehát a módszer konvergálni fog ilyen esetben.

Algoritmus

A Jacobi-algoritmusban az y segédtömb arra szolgál, hogy az x értékeit ne írjuk felül, amielőtt kiszámítottuk volna az összes új értéket. A Gauss–Seidel-módszer algoritmusában egyszerűbb a helyzet, mert azonnal felülírhatjuk a régi értékeket, ezzel gyorsítva az algoritmust. Kezdetben a megoldást tartalmazó x tömb a becslést tartalmazza.

Input: A(n,n) , b(n), x(n), iter_max
Output: x(n)

function Jacobi:
      for k = 1 to iter_max do
          for i = 1 to n do
              y[i] = b[i]  
              for j = 1 to n do
                  if j != i then
                      y[i] ← y[i] − A[i][j]*x[j]
                  end if
              end for
             x[i] ← y[i]/A[i][i]
         end for
     end for
     return x
 end function

Input: A(n,n), b(n), x(n), iter_max
Output: x(n)

function Gauss_Seidel:
      for k = 1 to iter_max do
          for i = 1 to n do
              x[i] = b[i]  
              for j = 1 to n do
                  if j != i then
                      x[i] ← x[i] − A[i][j]*x[j]
                  end if
              end for
             x[i] ← x[i]/A[i][i]
         end for
     end for
     return x
 end function

Fordítás

• Ez a szócikk részben vagy egészben a Gauss–Seidel method című angol Wikipédia-szócikk ezen változatának 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.

Források

• Lázár Zsolt, Lázár József, Járai-Szabó Ferenc: Numerikus módszerek, egyetemi jegyzet, 2008
• Iterációs módszerek:Jacobi és Gauss-Seidel iteráció
• Jaan Kiusaalas: Numerical Methods in Engineering with Python

Kapcsolódó szócikkek

• Numerikus analízis
• Lineáris egyenletrendszer
• Mátrix sajátértéke
• Konvergencia