Gauss–Seidel-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 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ő ismeretlen kiszámításához felhasználja az ugyanabban a ciklusban már kiszámolt 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[szerkesztés]

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

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

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

Innen kifejezhető az x1 és x2 ismeretlen, így a következő egyenleteket kapjuk:

,

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

,

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

Az kiszámítására már használhatjuk az új értékét is. Vagyis:

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

Konvergencia[szerkesztés]

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

Egy általános, alakú iterációs képlet akkor konvergál bármely kezdeti vektor esetén, ha a mátrix spektrálsugara kisebb, mint :

, a megoldásvektor.

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

ahol a mátrix 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 mátrix sugara kisebb, mint , ha az A mátrix szigorúan diagonálisan domináns, tehát a módszer konvergálni fog ilyen esetben.[2]

Algoritmus[szerkesztés]

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

  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[szerkeszté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.

Források[szerkesztés]

Kapcsolódó szócikkek[szerkesztés]