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ő ${\displaystyle x_{n}}$ ismeretlen kiszámításához felhasználja az ugyanabban a ciklusban már kiszámolt ${\displaystyle 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:

${\displaystyle 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:

${\displaystyle {\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:

${\displaystyle {\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:

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

${\displaystyle 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 ${\displaystyle x_{1}^{(0)}}$, illetve az ${\displaystyle 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

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

${\displaystyle 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 ${\displaystyle x_{2}}$ kiszámítására már használhatjuk az ${\displaystyle x_{1}}$ új értékét is. Vagyis:

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

${\displaystyle 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 ${\displaystyle A}$ mátrixtól, vagyis iterációs eljárással eljutunk a megoldásig, ha:

• ${\displaystyle A}$ szigorúan diagonálisan domináns
• ${\displaystyle A}$ szimmetrikus pozitív-definit^[1]

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

${\displaystyle \lim \|x^{(k)}-x\|=0\Longleftrightarrow \rho (G)<1}$ , ${\displaystyle 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ő:

$${\displaystyle x^{(k)}=(I-Q^{-1}A)x^{(k-1)}+Q^{-1}b}$$ ahol a ${\displaystyle Q}$ mátrix ${\displaystyle 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 ${\displaystyle (I-Q^{-1}A)}$ mátrix sugara kisebb, mint ${\displaystyle 1}$, ha az A mátrix szigorúan diagonálisan domináns, tehát a módszer konvergálni fog ilyen esetben.^[2]

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

Jegyzetek

1. Golub, Gene H.; Van Loan, Charles F. (1996), Matrix Computations (3rd ed.), Baltimore: Johns Hopkins, ISBN 978-0-8018-5414-9.
2. EW Cheney, DR Kincaid, Numerical analysis – Mathematics of Scientific Computing. ISBN 0-534-13014-3

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