Direkt (Gauss, Gauss-Jordan módszer, LU felbontás) és iterációs módszerek (szükséges és elégséges feltételek a konvergenciára, Jacobi-, Gauss-Siedel iteráció).

Kiindulás: Adott egy lineáris egyenletrendszer, mely mely mátrixos alakba is írható.

Ha az A n-ed rendű négyzetes mátrix reguláris (rangja n, ill. det(A)<>0), akkor a fenti egyenletrendszer egyértelműen megoldható, melyre kétféle numerikus módszer létezik:

Direkt eljárás, mely az egyenletrendszert elemi átalakításokkal olyan alakra hozza, ahonnan a megoldások közvetlenül leolvashatók.

Iterációs eljárás, amely adott kezdeti értékekből kiindulva a közelítő megoldások olyan sorozatát adja, amely (1) megoldásához konvergál.

Direkt eljárások

Gauss elimináció: Az egyenletrendszert elemi átalakításokkal (sorok felcserélése, egy sor szorzása nullától különböző számmal, egyik sor hozzáadása egy másik sorhoz) úgynevezett lépcsős egyenletrendszer alakjára hozzuk:

Az eljárás n-1 eliminációs lépésben történik. Ha a11<>0 (ellenkező esetben sort cserélünk), az A együtthatómátrix i-edik sorából kivonjuk az első sor -szeresét (i2,3,…,n), majd az első sort változatlanul hagyva az eljárást folytatjuk a többi sorra.

Az ekvivalens átalakításokból adódóan (2) és (3) megoldása ugyan az, amelyet visszafelé haladva -ből helyettesítéssel mind megkaphatunk:

,	(i=n-1, n-2,…,1)

Megjegyzés: A Gauss elimináció hatékonysága növelhető, ha minden lépés előtt az együtthatómátrix oszlopait úgy rendezzük, hogy a legnagyobb abszolút értékű elemmel kelljen osztani. Ha ezt sorokra is alkalmazzuk, teljes főelemkiválasztásról beszélünk.

A Gauss elimináció determinánsok kiszámítására is kiválóan alkalmas, inverz meghatározására pedig az AX=B lineáris mátrixegyenlet megoldásával.

(Ha B-nek az egységmátrixot választjuk, X nyilván A inverzét szolgáltatja.)

Gauss-Jordan módszer

Az egyenlet A mátrixának első sorát elosztjuk a11-gyel (a110 (ellenkező esetben sort cserélünk), majd ai1-szeresét kivonjuk az i-edik sorból (i= 2, 3,…, n). Az eljárást az összes sorra el kell végezni. A Gauss-féle eliminációval szemben, az i-edik lépésnél az előző sorok is változnak. Az n-1-edik lépés után az egységmátrixhoz jutunk, amiről a megoldásvektor sorban könnyedén leolvasható.

Háromszög-faktorizáció (LU-felbontás)

Az előző két eljárásból adódik, hogy minden reguláris mátrixra alkalmazható az úgynevezett háromszög-, vagy LU-faktorizáció:

PA=LU, ahol és

Felső ill. alsó háromszögmátrix (upper ill. lower triangular matrix), a P pedig egy olyan permutációs mátrix, melynek minden sorában és minden oszlopában pontosan egy elem 1, a többi mind 0. P írja le az A sorcseréit.

Ennek segítségével a (2) egyenletrendszer megoldását három lépésben írhatjuk le:

: A háromszög-faktorizáció végrehajtása

: Az y meghatáozása

: Az x megoldás meghatározása visszafelé helyettesítéssel.

Ha a lineáris egyenletrendszer megoldásánál (A,b) kibővített együttható mátrixra a Gauss-algoritmust alkalmazzuk, az L alsó háromszögmátrixot nem használjuk. L-t hatásosan alkalmazhatjuk akkor, amikor egyszerre több olyan lin. egyenletrsz.-t kell megoldanunk, melyeknek ugyanaz az A együttható mátrixa, de a b jobb oldalak különböző vektorok.

Iterációs eljárások

Jacobi-eljárás

Tegyük fel, hogy az (1) egyenletrendszer együttható mátrixában a főátlóbeli elemek mindegyike nullától különböző. Ekkor az i-edik sorban az xi ismeretlent kifejezhetjük, amiből a következő iterációs formula adódik ( az iterációs index):

(i=1, 2, …, n)

( =0, 1, 2,…; kezdeti értékek).

Ezt az eljárást teljeslépés eljárásnak is nevezik,, mert az új x(+1) vektor valamennyi komponensét x() vektor komponenseiből számítjuk. A Jacobi-eljárás tetszőleges kezdeti vektor esetén akkor konvergál, ha:

oszlopösszeg-feltétel

vagy a

sorösszeg-feltétel teljesül.

Gauss-Siedel-eljárás

Ez az eljárás annyiban tér el az előzőtől, hogy az új x(+1) az i-edik komponens kiszámításához a már ebben az iterációs lépésben nyert értékeket is felhasználjuk, és csak az i-nél nagyobb komponensek esetében használjuk a x() i-nél nagyobb komponensei értékét. Az első komponenst a Jacobi eljárással határozzuk meg. Formálisan:

(i=1, 2, …, n)

( =0, 1, 2,…; kezdeti értékek).

Ezt egyenkénti lépések módszerének is nevezik, az előző eljárásnál valamivel gyorsabban konvergál.

Relaxációs módszerek

Ha a Gauss-Siedel iterációs eljárást a következő hibajavító alakban írjuk fel:

, azaz

(i=1, 2, …, n;  =0, 1, 2,…)

Egy megfelelő  relaxációs paraméter választásával tovább javítható:

Megmutatható, hogy konvergencia csak 0<<2 esetén lehetséges. =1 estén kapjuk a Gauss-Siedel eljárást. Ezt általában akkor használjuk, ha A főátlóbeli elemei a többi elemnél lényegesen nagyobbak, vagy a mátrix ilyen alakra hozható.

16. Tétel: Lineáris egyenletrendszerek megoldása	4

Direkt (Gauss, Gauss-Jordan módszer, LU felbontás) és iterációs

Anna

2002-06-25T09:48:00

Peter Szamoskozi