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)}=\frac{b_i}{a_{ii}}-\sum _{l=1}^{(i-1)}\frac{a_{il}}{a_{ii}}{x}_l^{(k+1)}-\sum _{l=i+1}^{(n)}\frac{a_{il}}{a_{ii}}{x}_l^{(k)}$

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

$\left(\begin{array}{cc}{a}_{11}& a_{12}\\ a_{21}& a_{22}\end{array}\right)(\genfrac{}{}{0ex}{}{x_1}{x_2})=(\genfrac{}{}{0ex}{}{b_1}{b_2})$

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

$\{\begin{array}{c}{a}_{11}{x}_1+a_{12}{x}_2=b_1\\ a_{21}{x}_1+a_{22}{x}_2=b_2\end{array}$

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

$x_1=-\frac{a_{12}}{a_{11}}{x}_2+\frac{b_1}{a_{11}}$,

$x_2=-\frac{a_{21}}{a_{22}}{x}_1+\frac{b_2}{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)}=-\frac{a_{12}}{a_{11}}{x}_2^{(k-1)}+\frac{b_1}{a_{11}}$,

$x_2^{(k)}=-\frac{a_{21}}{a_{22}}{x}_1^{(k-1)}+\frac{b_2}{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)}=-\frac{a_{12}}{a_{11}}{x}_2^{(k-1)}+\frac{b_1}{a_{11}}$

$x_2^{(k)}=-\frac{a_{21}}{a_{22}}{x}_1^{(k)}+\frac{b_2}{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)}=G{x}^{(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 \Vert x^{(k)}-x\Vert =0⟺\rho (G)<1$ , $x$a megoldásvektor.

Általánosabban tárgyalva a problémát, feladatunk a $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

• Sablon:Fordítás

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