Matematika | Analízis » Eitner Bea - Lineáris algebrai egyenletrendszerek iterációs megoldásai

http://www.doksihu Szakdolgozat Lineáris algebrai egyenletrendszerek iterá iós megoldásai Eitner Bea Matematikai elemz® szakirány Témavezet®: Faragó István, tanszékvezet® egyetemi do ens Alkalmazott Analízis és Számításmatematikai Tanszék Eötvös Loránd Tudományegyetem, Természettudományi Kar Eötvös Loránd Tudományegyetem Természettudományi Kar 2009 http://www.doksihu Tartalomjegyzék 1. Bevezetés 3 2. Direkt módszerek 6 2.1 2.2 2.3 2.4 Gauss-eliminá ió . F®elemkiválasztás . LU-felbontás . Cholesky-felbontás . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3. Iterá iós megoldási módszerek 3.1 A sta ionárius iterá ió 3.11 Ja obi-iterá ió, Gauss-Seidel iterá ió 3.12 A SOR-módszer 3.13 Az egyszer¶

iterá ió 3.2 A sta ionárius iterá ió konvergen iája szimmetrikus, szigorúan pozitív denit (szpd) mátrixok esetén 3.21 A Ja obi-iterá ió konvergen iája 3.22 A SOR-módszer konvergen iája 3.23 Az egyszer¶ iterá ió konvergen iája 3.3 A Csebisev-iterá ió 3.31 A Csebisev polinomok 3.32 A Csebisev-iterá ió paramétere 3.4 Iterá iós eljárások M-mátrixok esetén 4. Összefoglalás 6 7 8 9 11 13 15 18 18 19 22 23 24 26 26 28 32 35 2 http://www.doksihu 1. fejezet Bevezetés Lineáris algebrai egyenletrendszernek nevezzük az a11 x1 + a12 x2 + . + a1n xm = b1 a21 x1 + a22 x2 + . + a2n xm = b2 . . an1 x1 + an2 x2 + . + anm xm = bm (1.1) egyenletrendszert, ahol aij , bi (i = 1, ., n, j = 1, , m) adott valós számok, xi (i = 1, ., n) ismeretlen valós számok Az aij számokat az (11) egyenletrendszer együtthatóinak

nevezzük és bi az i-edik egyenlet szabad tagja Az (1.1) egyenletrendszert homogénnek nevezzük, ha b1 = = bm = 0, ellenkez® esetben inhomogénnek mondjuk. Az (11) egyenletrendszert szabályosnak nevezzük, ha m = n, azaz az egyenletek és az ismeretlenek száma egyenl®. Jelölje   az együtthatómátrixot a11  . A :=  . an1    b :=   b1 a22 . an2  b2   , .  .  . a1n . anm  bm 3   x :=   x1    x2   .  .  xm http://www.doksihu az oszlopvektorokat. Ekkor az (1.1) rendszer tömören Ax = b alakban írható fel. Lineáris algebrai egyenletrendszerek a modellezés számos területén keletkeznek, például a me hanikában, a villamosságtanban, a gazdasági elemzések során stb. A matematikában is gyakran találkozunk olyan problémával, amely ilyen rendszer megoldására vezethet® vissza ( például: nem lineáris egyenletrendszerek, dieren iálegyenletek numerikus megoldása,

interpolá iós és approximá iós feladatok). 1. Tétel Tegyük fel, hogy A ∈ Rn×n és b ∈ Rn Ekkor a megoldás pontosan egyértelm¶, ha det(A) 6= 0, azaz létezik A−1 (A mátrix reguláris). Egy lehetséges megoldási módszer a Cramer-szabály: Jelölje Aj azt a mátrixot, amelyet a reguláris A mátrixból úgy kapunk, hogy a j -edik oszlop helyére a b oszlopvektort tesszük. Ekkor xj = det(Aj ) , det(A) j = 1, ., n Gyakorlati szempontból az eljárás alig alkalmazható, mert nagy m¶veletigény¶, kizárólag kis méret¶ mátrixok esetén érdemes használni. A Cramerszabály numerikusan nem stabilis, azaz a bemen® adatoktól a megoldás nem függ folytonosan. Alapkövetelmény egy megoldási módszerrel szemben, hogy adott pontosságú közelít® megoldás minél kevesebb m¶velettel legyen meghatározható (a numerikus módszer hatékonysága). 4 http://www.doksihu A lineáris algebrai egyenletrendszereket megoldó eljárások két nagy soportba

sorolhatók: direkt és iterá iós módszerek. A megoldási módszer kiválasztása leginkább az adott mátrixtól függ A szakdolgozat élja részben bemutatni a direkt módszereket és részletesen ismertetni az iterá iós megoldási lehet®ségeket, valamint rávilágítani el®nyeire és esetleges hátrányaira a direkt módszerekkel összehasonlítva. 5 http://www.doksihu 2. fejezet Direkt módszerek Ide tartozik a Gauss-eliminá ió, a teljes- és részleges f®elemkiválasztás, LU-felbontás és a Cholesky-felbontás. A direkt módszerek alkalmazásával pontos adatokat feltételezve, a számításokat pontosan elvégezve, véges sok m¶velettel a pontos megoldás meghatározható (a kerekítési hibákat gyelmen kívül hagyva). 2.1 Gauss-eliminá ió Az Ax = b rendszer, ahol A ∈ Rn×n adott mátrix, b ∈ Rn , x ∈ Rn esetén az eliminá iós módszer a következ®képpen jár el. Ha a11 6= 0, akkor az els® egyenlet li1 := aa11i1 -szeresét kivonjuk az i-edik

(i > 1) egyenletb®l. Ez a kiküszöbölési eljárás. Jelölje az A mátrix elemeit aij = a(1) ij , a kivonás során (2) i > 1 esetben létrejöv® új elemeket pedig aij , ahol (2) (1) (2) (1) (1) aij := aij − li1 a1j , j = 1, ., n (1) bi := bi − li1 b1 , j = 2, ., n Az els® lépés után a következ® egyenletrendszert kapjuk (1) (1) (1) (1) a11 x1 + a12 x2 + . + a1n xn = b1 (2) (2) (2) a22 x2 + . + a2n xn = b2 6 http://www.doksihu . . (2) (2) an2 x2 + . + a(2) nn xn = bn . Második lépésben feltesszük, hogy a(2) 22 6= 0. Majd hasonlóan járunk el az els® sor alatti (n − 1) × (n − 1)-es egyenletrendszerrel. Folytatva az eliminá iót az alábbi rendszerhez jutunk feltéve, hogy a(k) kk 6= 0 minden k = 3, ., n − 1-re (1) (1) (1) (1) a11 x1 + a12 x2 + . + a1n xn = b1 (2) (2) (2) a22 x2 + . + a2n xn = b2 . . (n) a(n) nn xn = bn Ha az utolsó egyenletben a(n) nn 6= 0, akkor xn értékét könnyen megadhatjuk az (n) bn

xn = (n) összefüggésb®l. Majd fordított sorrendben haladva a visszahelyetann tesítéssel xn−1 , ., x1 is ugyanígy adódik A kiküszöbölési eljárást tipikusan (i) aii = 1 formában hajtjuk végre. 2. Tétel A Gauss-eliminá ió pontosan akkor végezhet® el, ha az (11) egyenletrendszer A mátrixában az összes bal fels® f®minor nemzérus  a11  . det  . ak1 . . . a1k akk    6= 0, k = 1, ., n Az els® n − 1 feltétel biztosítja a Gauss-eliminá ió kiküszöbölési részének végrehajthatóságát, az utolsó pedig a visszahelyettesítés beindítását. 2.2 F®elemkiválasztás Az eliminá ió során f®elemnek nevezzük azt a f®átlóbeli elemet amelyikkel éppen elosztjuk az aktuális sort. Az eliminá ió stabilis, ha ez a legnagyobb abszolút érték¶ elem a mátrixban. Részleges f®elemkiválasztást végzünk, ha 7 http://www.doksihu sak az aktuális sorból, vagy sak az aktuális oszlopból választjuk ki a legnagyobb

abszolút érték¶t. Teljes f®elemkiválasztás esetén az egész mátrixban keressük a legnagyobb elemet. Ahhoz, hogy a kiválasztott elem a f®átlóba kerüljön sor és oszlop seréket hajtunk végre a mátrixban. Mindkétfajta (részleges, teljes) f®elemkiválasztásnál a szóba jöhet® elemek olyan oszlopban és sorban állnak, amelyeket az eliminá ió még nem normált le, vagy nullázott ki. Megfelel®en nagy számot választva szorzónak bármelyik sor eleméb®l lehet f®elem 2.3 LU-felbontás Az LU-felbontás során az Ax = b lineáris egyenletrendszerben szerepl® A mátrixot felbontjuk A = LU szorzatra, ahol L alsó háromszög, U pedig egy fels® háromszög mátrixot jelöl. 3. Tétel Az A ∈ Rn×n mátrixnak pontosan akkor létezik egyértelm¶ LU- felbontása, ha det(Ai ) 6= 0, 1 0 l  21 L =  .  . 1  ln1 . . . lnn−1 (i = 1, ., n − 1) 0   .  . u11 u12 0 u22 0 .   U =   0 1 . . . . 0

u1n . .     un−1n  unn L és U mátrix elemeinek kiszámítása a következ® képletek segítségével tör- ténik uij = aij − i−1 X lik ukj k=1 " # j−1 X 1 lij = aij − lik ukj ujj k=1 8 i≤j i>j j = i, ., n i = j + 1, ., n http://www.doksihu Az LU-felbontás segítségével Ax = LU x = L(U x) = b megoldásához Ly = b, U x = y megoldására van szükség. E két egyenletrendszer megoldása triviális Az Ly = b megoldása yi = bi − i−1 X i = 1, ., n lik yk k=1 Majd U x = y egyenletrendszer megoldása " # n X 1 xi = yi − uik xk uii k=i+1 i = n, ., 1 Ha a Gauss-eliminá ió kiküszöbölési része során meg®rizzük az lik szorzókat, akkor az eljárás végén megkapjuk L és U mátrixot, tehát az LU-felbontást is. Ilyen értelemben az LU-felbontás ekvivalens a Gauss-eliminá ió kiküszöbölési részével. 2.4 Cholesky-felbontás A Cholesky-felbontás abban az esetben létezik, ha az A mátrix szimmetrikus,

pozitív denit. Dení ió. Az A ∈ Rn×n mátrix pozitív denit, ha xT Ax > 0 teljesül minden x ∈ Rn , x 6= 0 vektor esetén Ha A szimmetrikus, pozitív denit mátrix, akkor felírható A = L̃L̃T alakban. Ez a mátrix Cholesky-felbontása Az L̃ mátrixot az LU-felbontásból kaphatjuk meg A = LU, L̃ = LD, √ ahol D = diag( uii ). A Cholesky-felbontás megadható az LU-felbontás nélkül is, ha egyenként számoljuk ki az A = L̃L̃T mátrix elemeit √ l˜11 = a11 , v u i−1 X u t 2 ˜ lii = aii − l˜ik , aij − l˜i j = k=1 9 Pi−1 ˜ ˜ k=1 lik ljk , l˜jj j = 1, ., i−1 http://www.doksihu Látható, hogy f®ként kis vagy közepes méret¶ mátrixok, illetve teli mátrixok esetén érdemes a direkt eljárást választani. A másik nagy, lineáris egyenletrendszereket megoldó módszer salád az iterá iós megoldási módszerek 10 http://www.doksihu 3. fejezet Iterá iós megoldási módszerek A gyakorlati feladatoknál, ami legtöbbször

nagyméret¶, ritka mátrixú egyenletrendszereket jelent, a direkt módszer f® problémája a nagy tárigény. Meg kell gondolni érdemes-e a pontos megoldást kiszámítani (kerekítési hibáktól eltekintve), hiszen általában a mátrix és a jobboldali vektor is hibás. Azt jelenséget, amikor a direkt eljárás során olyan helyen keletkezik nemzérus elem, ahol eredetileg nulla állt, feltölt®désnek nevezzük. A direkt módszerek általában feltölt®dést eredményeznek. Ez problémát jelent, növeli a tárigényt, hiszen a nulla elemeket nem tároljuk, vagyis helyet kell biztosítani az újonnan keletkezett elemeknek. Kivéve a sávmátrixokat, ahol a f®átló körüli diagonális sávon kívül nulla elemek állnak és a direkt módszerek alkalmazása során a sávszélesség megmarad. Az iterá iós eljárások legf®bb el®nye a nagyméret¶ rendszerekre történ® alkalmazhatóságuk Ritka mátrixok esetén is iterá iót használunk. Ritka mátrixról beszélünk,

ha a nemzérus elemek aránya (egyes szerz®knél kb 20 százalék) ki si n2 -hez képest, ahol n az A mátrix rendjét jelöli. Az Ax = b egyenletrendszer megoldása során a tárigényt sökkentjük azáltal, hogy A nem nulla elemeit nem tároljuk Az iterá iós módszer hátránya lehet az esetleges lassú konvergen ia, ugyanis egy olyan vektorsorozat el®állítását jelenti, amely a pontos megoldáshoz konvergál. Az egylépéses iterá iós módszerek általános alakja x(m+1) = Sm x(m) + f, 11 m = 0, 1, ., (3.1) http://www.doksihu ahol Sm ∈ Rn×n , f ∈ Rn . A kezdetben adott, tetsz®leges x(0) vektorból kiindulva határozzuk meg a soron következ® x(m) értékét és ezek segítségével -elvárásaink szerint- egyre jobban megközelítjük az Ax = b egyenletrendszer megoldását. Felmerül® kérdések: • Hogyan válasszuk meg az x(0) kezdeti vektort? • Mikor hagyjuk abba az iterá iót, mi a leállás kritériuma? • Konvergens-e az iterá ió? Ha igen, hova

tart, mikor tart az Ax = b egyenletrendszer megoldásához? Gyakorlatban kezdeti vektornak a nullvektort választják és így x(1) = f . (Általában nem érdemes a kezdeti vektor kiszámításába több munkát fektetni, mint amennyibe egy iterá iós lépés kerül.) Fontos elméleti kérdés a konvergen ia Ehhez szükség van el®ször két másik fogalom tisztázására és a (31) iterá ió sta ionárius alakjára x(m+1) = Sx(m) + f, (3.2) ahol (3.1) képletben szerepl® Sm mátrix nem változik, minden iterá iós lépésnél S marad Dení ió. Az X lineáris teret lineáris normált térnek nevezzük, ha létezik d : X R leképezés, úgynevezett norma • d(x) ≥ 0 minden x ∈ X -re, • d(x) = 0 ⇔ x = 0, • d(αx) = |α| d(x), • d(x + y) ≤ d(x) + d(y). Dení ió. (Bana h-tér) Egy X normált teret Bana h-térnek nevezünk, ha teljes, azaz minden X -beli Cau hy-sorozatnak létezik határértéke X -ben. 12 http://www.doksihu Tegyük fel, hogy az iterá ió

az X Bana h-térben adott, azaz f, x(0) ∈ X és S az X -et saját magába képezi le. Dení ió. A (32) sta ionárius iterá ió adott x(0) kezdeti vektor mellett konvergál, ha az {x(m) } sorozat konvergens az X Bana h-tér k·k normájában (a normált tér dení iójában d(x)). Ha ez tetsz®leges x(0) -ra teljesül, akkor az iterá iós eljárást konvergensnek nevezzük. A konvergen ia elégséges feltételét adja a következ® tétel: 4. Tétel Legyen X Bana h-tér, S : X X leképezés minden x1 , x2 ∈ X esetén eleget tesz a kSx1 − Sx2 k ≤ q kx1 − x2 k feltételnek, ahol q ∈ [0, 1) rögzített konstans. ª Ekkor az x(m+1) = Sx(m) +f iterá ióval el®állított x(m) sorozat konvergens. A tétel levezetése az [1℄-es irodalomban, mint az 1.17 Tétel bizonyítása szerepel. Következmény. Ha x(m) x∗ , akkor nyilván x∗ = Sx∗ + f, azaz x∗ az (I − S)x = f egyenlet megoldása. Ezért, ha I − S = A, akkor x(m) az Ax = f feladat megoldásához

tart. 3.1 A sta ionárius iterá ió Az egylépéses iterá iók általános alakja Bm+1 x(m+1) − x(m) + Ax(m) = b, τm+1 13 http://www.doksihu ahol Bm+1 , A ∈ Rn×n és b ∈ Rn adottak, Bm+1 mátrix reguláris és τm+1 ∈ R paraméterek sorozata. Az iterá ió sta ionárius, ha Bm+1 = B és τm+1 = τ , vagyis B független m értékét®l x(m+1) − x(m) B + Ax(m) = b. τ (3.3) A (3.3) iterá ió felírható x(m+1) = (I − B −1 Aτ )x(m) + τ B −1 b alakban. Ekkor S = I − B −1 Aτ f = τ B −1 b. Így, ha a (3.3) iterá ió konvergens, akkor A = I − S = B −1 Aτ f = τ B −1 b miatt a B −1 Aτ x = τ B −1 b Ax = f egyenletrendszer megoldásához tart. A konvergen ia szükséges és elégséges feltétele: 5. Tétel A sta ionárius iterá iós eljárás pontosan akkor konvergens, ha ρ(S) = max |λ(S)| < 1, azaz ρ(I − B −1 Aτ ) < 1. A ρ(S) kifejezéssel az S mátrix spektrálsugarát jelöljük. Ez a tétel gyakorlati szempontból

fontos, hiszen viszonylag könnyen ellen®rizhet® feltételt ad a konvergen iára. A (3.2) sta ionárius iterá ióban szerepl® S mátrix és az f vektor megadására egy általános lehet®ség a következ®: 14 http://www.doksihu A = K − Q, ahol a K reguláris mátrix. Ekkor b = Ax = Kx − Qx, Kx = Qx + b így Kx(m+1) = Qx(m) + b illetve x(m+1) = Sx(m) + f, S := K −1 Q, f := K −1 b 6. Állítás Ha kSk < 1 (ez elégséges feltétele az 5 tételben szerepl® állításnak), akkor x(m+1) = Sx(m) + f iterá ió konvergens Ez a Bana h-xpont tétel következménye, hiszen x = ϕ(x) alakú az egyenlet, ϕ : Rn Rn és ϕ(x) = Sx + f kontrak ió kϕ(x) − ϕ(y)k = kS(x) − S(y)k = kS(x − y)k ≤ kSk kx − yk . Az iterá iót K(x(m+1) − x(m) ) + Ax(m) = b alakban is felírhatjuk, K -t prekondi ionálási mátrixnak nevezzük. A K −1 mátrixot általában nem számítjuk ki, helyette vesszük a K LU -, vagy LDU -felbontását. Utóbbi esetben L az A mátrix

alsó, U a fels® háromszög része a diagonális nélkül, D := diag(A). A K = D a Ja obi-iterá iót, K = L+D eset pedig a Gauss-Seidel iterá iót adja. 3.11 Ja obi-iterá ió, Gauss-Seidel iterá ió Feltesszük, hogy A invertálható (detA 6= 0) és létezik P , úgynevezett permutáló mátrix, hogy P Ax = P b. Legyen P A = à és P b = b̃ Ekkor elérhet®, hogy à diagonálisában ne szerepeljen nulla elem, vagyis aii 6= 0, minden i = 1, ., n esetén ai1 x1 +ai2 x2 +. +aii−1 xi−1 +aii xi +aii+1 xi+1 + +ain xn = bi i = 1, ., n (3.4) 15 http://www.doksihu Ekkor aii 6= 0 miatt a (3.4) egyenletb®l xi kifejezhet® 1 aii xi = à − i−1 X j=1 aij xj − n X aij xj + bi j=i+1 ! . Felépíthet® egy iterá ió, ahol x(m) az i-edik ismeretlen m-edik közelítése. A i legkézenfekv®bb iterá ió (m+1) xi 1 = aii à − i−1 X j=1 (m) aij xj − n X (m) aij xj + bi j=i+1 ! i = 1, ., n Ez a Ja obi-iterá ió koordinátás alakja, az x(0)

kezd®vektor tetsz®leges, rögi zített. A mátrixos alak meghatározásához A = L + D + U felbontásra lesz szükség. Ax = b felírható (L + D + U )x = b alakban, innen Dx = −Lx − U x + b-t kapjuk, mivel D invertálható (hiszen A diagonálisából áll) ezért x kifejezhet® x = −D−1 Lx − D−1 U x + D−1 b. Ekkor a Ja obi-iterá ió mátrixos alakja x(m+1) = −D−1 Lx(m) − D−1 U x(m) + D−1 b, Dx(m+1) + (L + U )x(m) = b, D(x(m+1) − x(m) ) + Dx(m) + (L + U )x(m) = b, D(x(m+1) − x(m) ) + Ax(m) = b. A Gauss-Seidel iterá ió mátrixos alakja (D + L)x(m+1) + U x(m) = b, amely átrendezve (D + L)(x(m+1) − x(m) ) + (D + L + U )x(m) = b. Az iterá ió így felírható (D + L)(x(m+1) − x(m) ) + Ax(m) = b 16 http://www.doksihu alakban. Látható, hogy a két módszer a (33) sta ionárius iterá ió spe iális esete, Bm+1 = D, τm+1 = 1 választással a Ja obi, Bm+1 = L + D, τ = 1-re pedig a Gauss-Seidel iterá iót kapjuk. Numerikus példa:

Megvizsgáljuk, hogy a Ja obi vagy a Gauss-Seidel iterá ió közelít-e gyorsabban az Ax = b egyenletrendszer pontos megoldásához. Legyen  5 −2 3 0 2 1   1 3 −1 1    A :=  ,  2 −1 6 2  Ekkor a pontos megoldás 1 3   7 4   b :=   9 6   1 1   x :=   1 1 Az els® iterá iós lépés utáni eredmény: (1) xjacobi  1.400   1.333    = ,  1.500  x(1) gauss  1.400   0.866    =   1.177  0.925 2.000 Látható, hogy a Gauss-Seidel iterá ió egy lépés után jobban közelíti a pontos megoldást. A negyedik iterá iós lépést tekintve: (4) xjacobi  0.846   0.876    = ,  0.825  0.808 x(4) gauss  1.009   1.025    =   1.016  0.980 Míg a Ja obi módszer esetében két tizedesnyi eltérés tapasztalható, addig a Gauss-Seidel iterá iónál az

eltérés századokban mérhet® és a hetedik iteráiós lépés után ezredes pontossággal közelíti meg a megoldást, míg a Ja obi módszer még ekkor is századokkal eltér. Tehát a Gauss-Seidel iterá ió ebben az esetben gyorsabban konvergál az Ax = b egyenletrendszer megoldásához. 17 http://www.doksihu 3.12 A SOR-módszer A Gauss-Seidel módszer (D + L)(x(m+1) − x(m) ) + Ax(m) = b algoritmusa egy ω paraméter bevezetésével álatalánosítható (D + ωL) x(m+1) − x(m) + Ax(m) = b. ω (3.5) A (3.5) iterá iót SOR-módszernek nevezzük (ω = 1 eset pont a Gauss-Seidel módszert adja). A mátrixos és a koordinátás alak megadása (D + ωL)x(m+1) − (D + ωL)x(m) + ω(L + D + U )x(m) = ωb, (D + ωL)x(m+1) − (Dx(m) − ωDx(m) ) + ωU x(m) = ωb, (D + ωL)x(m+1) = [(1 − ω)D − ωU ] x(m) + ωb. A (D + ωL) mátrix invertálható, mert alsó háromszög mátrix és a diagonálisában nem nulla elemek állnak. Ezért x(m+1) kifejezhet® £ ¤ (E +

ωD−1 L)x(m+1) = (1 − ω)E − ωD−1 U x(m) + ωD−1 b, azaz (m+1) xi ω (m) = (1 − ω)xi + aii à − i−1 X j=1 (m+1) aij xj − n X (m) aij xj j=i+1 + bi ! , i = 1, ., n m = 0, 1, Itt is, akár a Gauss-Seidel iterá iónál szükség van aii 6= 0 teljesülésére tetsz®leges i-re. 3.13 Az egyszer¶ iterá ió Az iterá ió egyszer¶, ha x(0) adott és Ax = b egyenletrendszer megoldását x(m+1) − x(m) + Ax(m) = b m = 0, 1. τ 18 http://www.doksihu alakban keressük. Az eljárást relaxált Ja obi módszernek is hívják, mert A = D−1 A és b = D−1 b helyettesítéssel, τ = 1 esetén éppen a Ja obi iterá iót kapjuk. A konvergen ia sebessége növelhet® τ optimális megválasztásával, ha az A mátrix spe iális alakú. 7. Tétel(Az egyszer¶ iterá ió optimális paramétere) Legyen 0 < a ≤ λ(A) ≤ b és A mátrix szimmetrikus, szigorúan pozitív denit. Ekkor az iterá iónak van egyértelm¶en meghatározott optimális

paramétere, segítségével az egyszer¶ iterá ió a lehet® leggyorsabban konvergál a pontos megoldáshoz, amikor τ= 2 . a+b 3.2 A sta ionárius iterá ió konvergen iája szimmetrikus, szigorúan pozitív denit (szpd) mátrixok esetén Dení ió. A ∈ Rn×n szigorúan pozitív denit (szpd), ha létezik olyan δ > 0, hogy (Ax, x) ≥ δ(x, x) teljesül minden x ∈ Rn -re (x 6= 0). Megmutatható, hogy reguláris mátrixok esetén a pozitív denitség és szpd fogalmai egybeesnek. Ha A szpd mátrix, akkor A > 0 jelölést használjuk B x(m+1) − x(m) + Ax(m) = b τ (3.6) lim em = 0. (3.7) Jelölje x∗ az Ax = b lineáris egyenletrendszer megoldását. Az em = x(m) − x∗ vektorsorozatot hibavektornak hívjuk. A (36) iterá ió konvergál az Ax = b egyenletrendszer megoldásához, ha m∞ 8. Állítás Tegyük fel, hogy A szimmetrikus, szpd mátrix Ha B − 0.5τ A > 0, 19 (3.8) http://www.doksihu akkor a (3.6) iterá ió konvergens Bizonyítás.

Legyen Jm := (Aem , em ), ekkor Jm ≥ 0, mert A szpd mátrix. B em+1 − em + Aem = 0 m = 1, 2, . τ (3.9) A (3.9)-as egyenlet el®áll B x(m+1) − x(m) + Ax(m) = b τ x ∗ − x∗ + Ax∗ = b B τ (3.10) (3.11) (3.10) és (311) különbségeként Ebb®l következik, hogy Bm+1 = (B − τ A)em , em+1 = (E − τ B −1 A)em , Aem+1 = (A − τ AB −1 A)em , ¢ ¡ (Aem+1 , em+1 ) = (A − τ AB −1 A)em , (E − τ B −1 A)em , (Aem+1 , em+1 ) = (Aem , em )−τ (AB −1 Aem , em )−τ (Aem , B −1 Aem )+τ 2 (AB −1 Aem , B −1 Aem ). Mivel A mátrix szimmetrikus, ezért (AB −1 Aem , em ) = (B −1 Aem , Aem ) = (Aem , B −1 Aem ) Jm+1 = Jm − 2τ (Aem , B −1 Aem ) + τ 2 (AB −1 Aem , B −1 Aem ) ym := B −1 Aem em := A−1 Bym Jm+1 = Jm −2τ (Aem , ym )+τ 2 (Aym , ym ) = Jm −2τ (AA−1 Bym , ym )+τ 2 (Aym , ym ) Jm+1 = Jm − 2τ (Bym , ym ) + τ 2 (Aym , ym ) = Jm − 2τ ((B − 0.5τ A)ym , ym ) A B − 0.5τ A > 0, így a skaláris

szorzat ((B − 05τ A)ym , ym ) ≥ 0 Ekkor Jm+1 ≤ Jm , a (Jm ) sorozat monoton sökken és Jm ≥ 0, ezért létezik határértéke lim Jm = J. m∞ 20 http://www.doksihu A Jm+1 = Jm − 2τ ((B − 0.5τ A)ym , ym ) összefüggésben tudjuk, hogy Jm+1 és Jm egyaránt tart J -hez. Ezért lim ((B − 0.5τ A)ym , ym ) = 0 m∞ Másrészt, a közrefogási tételt alkalmazva lim kym ||2 = 0, m∞ hiszen a következ® be slés igaz rá ((B − 0.5τ A), ym ) ≥ δ kym k2 ≥ 0 Alkalmazva a rend®r-elvet, az em = A−1 Bym elemre érvényes a ° ° 0 ≤ kem k ≤ °A−1 B ° kym k be slés, ahol kym k-r®l tudjuk, hogy tart nullához. A hibavektorok sorozatának határértéke lim em = 0, m∞ tehát a (3.6) iterá ió a dení ió szerint konvergál az Ax = b egyenletrendszer megoldásához.¤ 21 http://www.doksihu 3.21 A Ja obi-iterá ió konvergen iája 9. Állítás Legyen A ∈ Rn×n mátrix szimmetrikus és szigorúan diagonálisan domináns, azaz n X aii

> |aij | j=1,j6=i (3.12) ∀i = 1, ., n Ekkor a Ja obi-módszer konvergens. Bizonyítás. Belátandó (3.8) alapján a D−05A > 0 egyenl®tlenség, mert a Ja obi-iterá ió esetén B = D és τ = 1. Mivel D − 0.5A > 0 a 2D > A feltételt jelenti, ezért (2Dx, x) ≥ (Ax, x) kell teljesüljön minden x-re. A továbbiakhoz szükség van a következ® be slésre 1 1 aij xi xj ≤ |aij | |xi | |xj | ≤ |aij | (|xi |2 + |xj |2 ) = |aij | (x2i + x2j ). 2 2 Ekkor (Ax, x) = n X i,j=1 aij xi xj ≤ n n 1X 1X 1 |aij | x2i + |aij | x2j = |aij | (x2i +x2j ) = 2 2 2 i,j=1 i,j=1 i,j=1 n X n n 1X 1X 2 = |aij | xi + |aji | x2i . 2 i,j=1 2 i,j=1 Az A mátrix szimmetriája miatt (aij = aji ) n n n X 1X 1X 2 2 = |aij | xi + |aij | xi = |aij | x2i = 2 i,j=1 2 i,j=1 i,j=1 = Ã n n X X i=1 j=1 = n X |aij | x2i x2i i=1 = n X i=1 ! = |aij | = n X |aij | . x2i i=1 Ã x2i |aij | n X Ã n X n X |aii | + Ã aii + j=1,j6=i j=1,j6=i 22 j=1 ! ! ! =

http://www.doksihu Az (3.12) szerint: n X i=1 x2i à n X aii + =2 j=1,j6=i n X ! |aij | ≤ n X x2i (aii + aii ) = i=1 aii x2i = 2(Dx, x) = (2Dx, x) i=1 Így 2D > A, ahol (Dx, x) = 3.22 P i aii x2i .¤ A SOR-módszer konvergen iája 10. Tétel (Cahan) Legyen A szimmetrikus, szpd mátrix Ekkor ω ∈ (0, 2) esetén a SOR-módszer konvergens. Bizonyítás. B = D + ωL, τ = ω, A=L+D+U Mivel A szimmetrikus U = LT . Ekkor B − 0.5τ A = (D + ωL) − 05ωA > 0 igazolása a él (Ax, x) = ((L + D + U )x, x) = (Lx, x) + (Dx, x) + (U x, x) = = (Lx, x) + (Dx, x) + (x, Lx) = 2(Lx, x) + (Dx, x) ((B − 0.5τ A)x, x) = ((D + ωL)x, x) − 05ω(Ax, x) = = (Dx, x) + ω(Lx, x) − 0.5ω (2(Lx, x) + (Dx, x)) = = (Dx, x) + ω(Lx, x) − ω(Lx, x) − 0.5ω(Dx, x) = (1 − 05ω)(Dx, x) > 0 Ugyanis, ha ω ∈ (0, 2), akkor 1−0.5ω > 0, így igaz lesz, hogy B−05τ A > 0¤ Következmény. A Gauss-Seidel-iterá ió szpd mátrixokra, ω = 1 választás esetén

konvergens. 23 http://www.doksihu 3.23 Az egyszer¶ iterá ió konvergen iája Az egyszer¶ iterá ió x(m+1) − x(m) + Ax(m) = b τ (3.13) alakban írható fel. 11. Állítás Ha az A mátrix szpd mátrix, akkor a τ < 2 λmax feltétel teljesülése esetén a (3.13) iterá ió konvergens Bizonyítás. A (3.8) összefüggés szerint, a B − 05τ A > 0 feltétel ellen®rzésére lesz szükség Most B = E , tehát valójában E − 05τ A > 0-t kell belátni A feltétel, hogy az E − 0.5τ A mátrix sajátértékei nagyobbak legyenek nullánál Legyenek A mátrix sajátértékei a következ®k 0 < λ1 (A) ≤ λ2 (A) ≤ . ≤ λn (A) Mind pozitívak, mert A szigorúan pozitív denit mátrix. Jelölje G az E − 0.5τ A mátrixot, ekkor G mátrix sajátértékei λi (G) = 1 − 0.5τ λi (A) i = 1, , n Az algebrai m¶velet átvihet®, mert a fenti mátrixok sajátvektorai megegyeznek. Ekkor elég igazolni, hogy min λi (G) > 0, azaz min λi (G) = 1

− 0.5 max λi (A) = 1 − 05λmax , ahol λmax = λn (A). A (314) összefüggést átrendezve kapjuk 0.5τ λmax < 1, vagyis τ< 2 λmax Így az állítást beláttuk.¤ 24 . (3.14) http://www.doksihu 12. Állítás A τ < 2 λmax feltétel szükséges feltétel is. Bizonyítás. Legyen Aµn = λn µn és válasszuk kezdeti vektornak az x(0) := x∗ −µn vektort. Megmutatjuk, hogy ekkor a x(m+1) − x(m) + Ax(m) = b τ (3.15) iterá ió divergens. Korábban beláttuk, hogy em = x∗ − x(m) hibára em+1 − em + Aem = 0. τ (3.16) Az x(0) megválasztása miatt e0 = x∗ − x(0) = µn . Ekkor (3.16) átrendezésével em = (E−τ A)em−1 = (E−τ A)(E−τ A)em−2 = (E−τ A)2 em−2 = (E−τ A)m e0 em = (E − τ A)m µn . A (3.15) iterá ió pontosan akkor konvergens, ha a (37) feltételnek eleget tesz. (E − τ A)µn = µn − τ Aµn = µn − τ λn µn = (1 − τ λn )µn (E − τ A)2 µn = (E − τ A)(E − τ A)µn = (E − τ A) ((1 −

τ λn )µn ) = = (1 − τ λn )(E − τ A)µn = (1 − τ λn )(1 − τ λn )µn = (1 − τ λn )2 µn Ekkor látható, hogy (E − τ A)m µn = (1 − τ λn )m µn em = (1 − τ λn )m µn . Tehát limm∞ em = 0 ⇐⇒ |1 − τ λn | < 1. 2 Mivel λn > 0 ezért 1 − τ λn > −1 feltétel τ ≥ λmax esetén nem teljesül, így a 2 τ < λmax valóban szükséges feltétele a konvergen iának.¤ 25 http://www.doksihu 3.3 A Csebisev-iterá ió A Csebisev iterá ió olyan nem sta ionárius iterá iós eljárás, amely az egyszer¶ iterá ióval m lépést hajt végre és minden lépésben más iterá iós paramétert használ x(m+1) − x(m) + Ax(m) = b. τm (3.17) A (3.17) iterá iót kizárólag szimmetrikus, szigorúan pozitív denit mátrixok esetén alkalmazzuk. 3.31 A Csebisev polinomok A Csebisev polinom gyökeivel x1 , x2 , ., xm alappontokat határozunk meg, amelyeket interpolálva Lm (x) interpolá iós polinom maximális hibája a lehet®

legkisebb. Az f (x) függvényt szeretnénk interpolá ióval közelíteni Lm (xi ) = f (xi ), · ¸ min max |f (x) − Lm (x)| , [−1,1] (3.18) ahol Lm (x) a Lagrange interpolá iós polinom. Olyan m-ed fokú polinomokat keresünk, amelyeknek a nullától való eltérése minimális. Megvizsgáljuk, hogy létezik-e ilyen polinom Jelölje Rm (x) a következ® polinomot: Rm (x) := cos(m arccos x) Ha α := arccos x, akkor cos((m + 1)α) + cos((m − 1)α) = = (cos(mα) cos α − sin(mα) sin α) + (cos(mα) cos α + sin(mα) sin α) = = 2 cos(mα) cos α. Vagyis az Rm+1 (x)+Rm−1 (x) = 2xRm (x) összefüggés alapján Rm (x) valóban polinom. 26 http://www.doksihu Mivel R0 (x) = 1, R1 (x) = x, ezért R2 (x) = 2x2 − 1, . Rm (x) polinomban xm együtthatója 2m−1 lesz. Dení ió. Ekkor a Tm (x) = Rm (x) 1 = m−1 cos(m arccos x) = 21−m cos(m arccos x) m−1 2 2 polinomot Csebisev polinomnak nevezzük. Adjuk meg Csebisev polinom gyökeit a [−1, 1] intervallumon Tm (x) =

0 ⇐⇒ 1 2m−1 cos(m arccos x) = 0 2k + 1 m arccos x = π 2 ¶ µ 2k + 1 π k = 0, 1, ., m − 1 xk = cos 2m (3.19) A következ® állítás bizonyítása során belátjuk, hogy a Csebisev polinom eleget tesz a (3.18) képletben meghatározott feltételnek 13. Állítás Legyen Q ∈ Pm tetsz®leges polinom Ekkor max |Qm (x)| ≥ max |Tm (x)| = [−1,1] [−1,1] 1 2m−1 , (3.20) azaz Tm (x) tér el a legkevésbé a nullától. Bizonyítás. Indirekt tegyük fel, hogy: max |Qm (x)| < max |Tm (x)| = [−1,1] [−1,1] 1 2m−1 Tekintsük a Hm (x) = Tm (x) − Qm (x) polinomot. Ekkor Hm (x) ∈ Pm−1 , tehát legfeljebb m − 1-ed fokú polinom. sgnHm (x`k ) = sgn(Tm (x`k )−Qm (x`k )) = sgn((−1)k 1 2m−1 −Qm (x`k )) = sgn(−1)k A Hm (x) polinom a [−1, 1] intervallumon m-szer vált el®jelet, ami éppen azt jelenti, hogy m darab gyöke van. Ez ellentmondás, hiszen Hm (x) ∈ Pm−1 ¤ 27 http://www.doksihu Tegyük fel, hogy a polinom nem [−1,

1]-en, hanem egy tetsz®leges [a, b] intervallumon van értelmezve. Tekintsük a következ® transzformáltat t= µ 2 b−a ¶ x− b+a . b−a Ekkor a Tm (t) polinom az [a, b] intervallumot [−1, 1]-re képezi le. µ µ ¶¶ 2x − (b + a) 1 (b − a)m cos m arccos = Tm (t) = m−1 2 2m b−a µ µ ¶¶ (b − a)m 2x − (b + a) = 2m−1 cos m arccos 2 b−a A Csebisev polinom gyökei, ahol Tm (t) a [−1, 1]-en értelmezett polinomokat jelöl µ ¶ x= tehát a+b b−a xk = + cos 2 2 b−a 2 µ t+ 2k + 1 π 2m a+b 2 ¶ k = 0, ., m − 1 Ekkor a Csebisev polinom nullhelyei megegyeznek az interpolá iós polinom mérési pontjainak helyeivel. 3.32 A Csebisev-iterá ió paramétere A (3.17) iterá ió hibaegyenletére megadható a következ® iterá iós képlet e1 = (I − τ1 A)e0 . . em = (I − τm A)em−1 em = (I − τm A)(I − τm−1 A) . (I − τ1 A)e0 = pm (A)e0 Q Legyen pm (λ) := m i=1 (1 − τi λ). A pm (λ) teljesíti a p(0) = 1 normalizá iós

feltételt. Tegyük fel, hogy minden λ = λ(A) sajátérték valós, illetve ismertek a sajátértékek határai a ≤ λ ≤ b. 28 http://www.doksihu Vegyük észre, hogy pm (λ) a pm (A) mátrix sajátértéke. Ekkor a pm (A) mátrix spektrálsugár be slése ρ(pm (A)) = max |pm (λ)| ≤ max |pm (λ)| . a≤λ≤b λ=λ(A) A pm (λ) polinom egyértelm¶en meghatározott m darab gyöke és a pm (0) = 1 normalizá iós feltétel által. A módszer konvergens, ha a (37) feltételt teljesíti. Ezért az összes m-ed fokú polinom közül keressük azt, amelyre min pm ∈Pm µ ¶ (3.21) max |pm (λ)| , a≤λ≤b ahol Pm a legfeljebb m-ed fokú polinomok osztálya. A (321) minimalizálását a τi megfelel® megválasztásával tudjuk elérni. A (321) feladat megoldása Rm (x) polinom segítségével történik pm (λ) = ahol Rm (x) = (x + √ Rm ¡ b+a−2λ ¢ Rm (3.22) b+a ¡ b+a ¢ , b−a x2 − 1)m (x − 2 √ x2 − 1)m . (3.23) Ekkor Rm

argumentumában x= b + a − 2λ b−a leképezés az [a, b] intervallumot [−1, 1]-re képezi le. A (3.23) képlet részletes levezetése: A három tagú rekurziók egy általános alakja pm+1 = (αm x − βm )pm − γm pm−1 . Most legyen αm = α, βm = β, γm = γ minden m-re. A rekurzió megoldását pm = cρm alakban szeretnénk megkapni. Ekkor ρ-ra felírható másodfokú egyenlet ρ2 − (αx − β)ρ + γ = 0. 29 http://www.doksihu Innen a gyökök ρ1,2 = ´ p 1³ αx − β ± (αx − β)2 − 4γ . 2 (3.24) Általában α 6= 0 és ρ1 6= ρ2 , a Viéte-formula alapján ρ2 = ργ1 . A másodfokú m rekurzió megoldása megadható c1 ρm 1 és c2 ρ2 lineáris kombiná iójaként (3.25) m p m = c 1 ρm 1 + c 2 ρ2 . Az m = 0, m = 1 eseteket tekintve p0 = c1 + c2 , p 1 = c 1 ρ1 + c 2 ρ2 . Innen kifejezhet®k a c1 , c2 konstansok c1 = p 0 γ − p 1 ρ1 , γ − ρ21 c2 = p1 ρ1 − ρ21 po . γ − ρ21 Megmutattuk, hogy Rm (x) polinomra teljesül

R0 (x) = 1, R1 (x) = x, R2 (x) = 2x2 , . és emellett Rm+1 (x) = 2xRm (x) − Rm−1 (x) (m ≥ 1). Mivel Rm (x) f®együtthatója 2m−1 , a (3.24) egyenlet szerint ρ1 = x + √ x2 − 1, ρ2 = 1 . ρ1 Ez alapján a konstansok Ekkor √ √ 1 − x(x + x2 − 1) 1 − x(x + x2 − 1) 1 √ √ c1 = = = . 2 1 − x(x + x2 − 1)2 2(1 − x2 − x x2 − 1) R0 (x) = c1 + c2 = 1, 1 c2 = . 2 A (3.25) kifejezés gyelembevételével adódik a keresett kifejezés Rm (x) = (x + √ x2 − 1)m (x − 2 30 √ x2 − 1)m . http://www.doksihu Az optimális τm paraméterek meghatározásához szükség van a pm (λ) polinom gyökhelyeinek megadására. Rögzített m esetén, (3.19) alapján Rm (x) polinom gyökei xk = cos µ 2k + 1 π 2m ¶ k = 0, 1, ., m − 1 Innen már könnyen megkapjuk a megfelel® λi -ket, xi = b + a − 2λi b−a egyenletet kell megoldanunk. Kifejezhet®k azok a λi számok (rögzített m mellett), amelyek mellett a pm (λ) nulla értéket

vesz fel. El®állítottuk az azonosan nulla függvényt legjobban approximáló pm (λ) polinomot A továbbiQ akban még igazolni, kell hogy a pm (λ) = m i=1 (1−τi λ) polinom azonos (3.22) polinommal. Ehhez elégséges megkövetelni a két polinom gyökeinek egybeesését, illetve a polinomok normáltságát Mivel a pm (λ) polinom gyökei már Q ismertek és λi -vel egyenl®ek, a m i=1 (1 − τi λ) polinom pedig lineáris tényez®k Q λ szorzataként adott, így τi = λ1i választása esetén a m i=1 (1 − λi ) polinomot kapjuk, amelynek gyökei egybeesnek a pm (λ) polinommal. A két polinom Q λ értéke megegyezik a λ = 0 helyen is. Ez azt jelenti, hogy a m i=1 (1 − λi ) teljesen egybeesik a pm (λ) polinommal, gyökei a λ = λi pontokban vannak. Q A pm (λ) = m i=1 (1 − τi λ) szorzat tényez®it nullával egyenl®vé téve a τi paraméterek egyszer¶en meghatározhatók τi = 2 2 ¡ ¢ = b + a − (b − a)xk π b + a − (b − a) cos 2k+1 2i Ezek a

Csebisev-iterá ió optimális paraméterei τi = 31 1 λi i = 1, ., m esetén. http://www.doksihu 3.4 Iterá iós eljárások M-mátrixok esetén A lineáris egyenletrendszerek iteratív megoldásánál fontos szerepet kap az M-mátrixok osztálya. Dení ió. Azt mondjuk, hogy A mátrix nemnegatív mátrix, ha aij ≥ 0 minden i, j -re. Jelölés: A ≥ 0 Dení ió. Az A mátrix "nagyobb vagy egyenl®", mint a B mátrix ha A − B ≥ 0, azaz A ≥ B . Dení ió. Az A ∈ Rn×n mátrixot M-mátrixnak nevezzük, ha aij ≤ 0 minden i, j -re (i 6= j), létezik olyan g ∈ Rn vektor, hogy g > 0 és Ag > 0. Egy új fogalom bevezetésére van szükség ahhoz, hogy az iterá iós eljárások konvergen iáját M-mátrixok esetén tanulmányozzuk: Dení ió. Legyen A = P − Q, ahol P reguláris és P −1 ≥ 0, Q ≥ 0 A P − Q mátrix az A mátrix reguláris felbontása, ha ρ(P −1 Q) < 1 feltétel teljesül. Ha A-nak P − Q reguláris felbontása, akkor

az 5.tétel alapján a (32) képletben szerepl® sta ionárius iterá ió konvergens. 14. Tétel (Reguláris felbontás létezése) Legyen az A mátrix M-mátrix Ekkor A reguláris és létezik inverze. A tétel bizonyítása az [1℄-es irodalomban található, az 1.7 lemma levezetéseként 15. Tétel (Reguláris felbontás létezése) Legyen az A mátrixban aij ≤ 0 minden i, j -re (i 6= j). Az A mátrixnak pontosan akkor létezik reguláris felbontása, ha A egy M-mátrix. A tétel levezetése az [1℄-es irodalomban, mint az 1.20 Lemma bizonyítása szerepel. 16. Tétel (M-mátrixok reguláris felbontása) Legyen A egy M-mátrix, A = P − Q, P reguláris és P −1 ≥ 0, Q ≥ 0. Ekkor P − Q az A mátrix reguláris felbontása. Bizonyítás. Azt kell belátni, hogy a P −1 Q mátrixra a ρ(P −1 Q) < 1 feltétel teljesül. 32 http://www.doksihu Legyen e := (1, ., 1)T Mivel A egy M-mátrix, ezért g > 0 esetén Ag > 0 Jelölje G := diag(gi ), ekkor P Ge =

P g > Qg = Qge ≥ 0 e > G−1 P −1 QGe ≥ 0. Innen következik, hogy ° ° ° ° 1 > °G−1 P −1 QGe°(∞) = °G−1 P −1 QG°(∞) ≥ ρ(G−1 P −1 QG) = ρ(P −1 Q). Tehát ρ(P −1 Q) < 1, ezzel a tételt beláttuk.¤ 17. Tétel A Gauss-Seidel iterá ió minden M-mátrixra konvergens Bizonyítás. Ha A egy M-mátrix, akkor létezik olyan g , hogy g > 0 és Ag > 0. A mátrixot A = L + D + U alakba írva, L + D mátrix is M-mátrix lesz (L + D)g ≥ Ag > 0, U ≤ 0. Ekkor a mátrixokat a következ®képpen választjuk meg A = P − Q, P = L + D, Q = −U, ahol P −1 = (L + D)−1 ≥ 0, Q = −U ≥ 0. Innen következik az állítás a 15. Tétel segítségével¤ 18. Tétel Ha A mátrix M-mátrix és 0 < ω ≤ 1, akkor a SOR-módszer (D + ωL) x(m+1) − x(m) + Ax(m) = b ω konvergens. 33 http://www.doksihu Bizonyítás. A SOR-módszer mátrixos alakja: (D + ωL)(x(m+1) − x(m) ) + ωAx(m) = ωb := f vagyis P x(m+1) = Qx(m)

+ f ahol P := D + ωL Q := D(1 − ω) − ωU. (3.26) Azt kell belátni, hogy P −1 ≥ 0 komponensenként, ha 0 < ω ≤ 1. Ekkor Q nemnegativitása látható a (3.26) képletb®l A P ezekre az ω értékekre M-mátrix. Ha A M-mátrix és aij ≤ pij ≤ 0, (i 6= j) 0 < aii < pii , akkor P is M-mátrix. Ugyanis P mátrix el®jeleloszlása megfelel® Tudjuk, hogy P ≥ A és g > 0 esetén Ag > 0, ebb®l következik, hogy P g ≥ Ag > 0. Mivel P − Q = ωA, ez pozitív ω -ra M-mátrix, ezért az állítás 15. Tételb®l következik.¤ Az M-mátrixok osztálya spe iális mátrixosztály. Legyen A mátrix reguláris és inverze nemnegatív, akkor Ag = e megoldása pozitív. Ha g vektornak lenne nulla komponense, akkor A−1 tartalmazna egy supa nulla sort. Ekkor ha A el®jeleloszlása megegyezik az M-mátrixokéval, akkor A valóban M-mátrix. A-val együtt AT is M-mátrix. Hasznos tulajdonsága e mátrixoknak, hogy létezik LU-felbontása és ez

Gauss-eliminá ióval el®állítható. 34 http://www.doksihu 4. fejezet Összefoglalás A lineáris algebrai egyenletrendszerek megoldása direkt és iterá iós módszerekkel egyaránt lehetséges. Az iterá iós eljárások el®nye látható az olyan Ax = b lineáris egyenletrendszerek megoldásánál, amelyeknek mátrixa nagyméret¶, ritka. Ekkor a direkt módszereknél a nagy tárigény jelent problémát A gyakorlati feladatok megoldása legtöbbször nagyméret¶, ritka mátrixokkal való számolást igényel. Az iterá iók hátránya általában a lassú konvergen ia, hiszen a módszer során olyan vektorsorozatot állítunk el®, amely a pontos megoldáshoz konvergál. A legegyszer¶bb esetben az iterá iós eljárás x(m+1) = Sx(m) + f, m = 0, 1, . alakban adható meg. E képlet és a kezdetben adott, tetsz®leges x(0) kezdeti vektor segítségével meghatározzuk x(m) értékét, egyre jobban közelítve az Ax = b egyenletrendszer megoldását. Az S mátrix iterá

iós paramétert is tartalmazhat, amelyet megfelel®en megválasztva az iterá ió gyorsítható. 35 http://www.doksihu Irodalomjegyzék [1℄ Stoyan Gisbert, Takó Galina: Numerikus módszerek I. Typotex, Budapest (2005) [2℄ G. I Mar suk: A gépi matematika numerikus módszerei szaki Könyvkiadó, Budapest (1976) M¶- [3℄ Faragó István: Alkalmazott Analízis I. ELTE kézirat [4℄ A. Berman, R J Plemmons: Nonnegative matri es in the mathemati al s ien es A ademi Press, New York (1979) [5℄ Ri hard S. Varga: Matrix iterative analysis Prenti e Hall, Englewood Clis (1962) 36