Főmenü megnyitása

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ásSzerkeszté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.

KonvergenciaSzerkeszté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]

AlgoritmusSzerkeszté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

JegyzetekSzerkeszté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ásSzerkeszté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ásokSzerkesztés

Kapcsolódó szócikkekSzerkesztés