Matematika | Analízis » Numerikus analízis I. jegyzet

Numerikus analízis I. El®adásjegyzet esti programozó matematikusoknak László Lajos el®adásai nyomán 2004/2005 tavaszi félév A jegyzet a Numerikus Analízis . tárgy els® félévének (2005 tavaszi félév) anyagát tartalmazza, László Lajos el®adásain készített kézzel írott jegyzetek alapján. Minthogy a tárgy heti 1 × 45 per gyakor- latban volt meghirdetve, így nem jutott id® minden bizonyításra. Néhány érdekesebb megtalálható a jegyzetben, más m¶vekb®l beemelve (ld. Irodalomjegyzék), a megfelel® helyre beszúrva Tartalomjegyzék 1. Lineáris egyenletrendszerek direkt megoldása Gauss-eliminá ió, LU felbontás . 2 1.2 Gauss-Jordan eliminá ió, m¶veletigény, invertálás . 4 1.3 Egziszten ia és uni itás . 5 1.4 Tridiagonális mátrix LU -felbontása, Cholesky-faktorizá ió . 5 7 1.5 Invariáns tulajdonságok, S

hur-komplementer . 1.6 Diagonális dominan ia, irredu ibilitás . 9 1.7 Ortogonális-trianguláris (QR) felbontás . 13 2. Iterá iós módszerek 1. 1 1.1 14 2.1 Vektornormák és mátrixnormák . 15 2.2 A Bana h-féle xpont-tétel alkalmazása 21 2.3 Ja obi módszer . 25 2.4 Gauss-Seidel módszer . 25 2.5 Ri hardson iterá ió . 25 2.6 A Ja obi és a Gauss-Seidel iterá ió kap solata . 27 2.7 Relaxá iós módszerek . 27 2.8 Gradiens-módszer . 28 . Lineáris egyenletrendszerek direkt megoldása Megjegyzés. Cél: Ax = b megoldása, ahol A ∈ Rn×n , b ∈ Rn , x ∈ Rn ∃A−1 ⇔ |A| 6= 0,

∃A−1 ⇔ {az Ax = 0-nak sak x = 0 a megoldása}, és ∃A−1 ⇔ {A-nak nin s 0 ∈ C sajátértéke}. 1 1.1 Gauss-eliminá ió, LU felbontás Megjegyzés. LU felbontást próbálgatjuk el®ször. Az ún. Ennek az a lényege, hogy A mátri- xot felbontjuk egy L és egy U mátrixra, ahol L alsóháromszög-mátrix: lij = 0, i < j , U pedig egy 2 fels®háromszög-mátrix: uij = 0, i > j . Itt szabadságfokunk n + n lenne, hiszen az átlót kétszer számoljuk, ezért az uni itáshoz az egyik mátrix f®átlóját (általában L-ét) rögzítjük A Gauss-eliminá iónak nevezett módszer pedig a következ®képp szemléltethet®:  0  0 0 (2) a22 6= 0 − (1) tfh. a11 6= 0 − Egy másik interpretá ióban: a11 x1 + . = b1 0 0 0  0 0 (3) a33 6= 0 − x1 = − 0 0 0 0 0 0  (4) = U , mivel ∃A−1 , így a44 6= 0 b1 − a12 x2 − . − a1n xn a11 Az els® sor alkalmas konstansszorosát hozzáadom a 2., , n sorhoz, így az els® oszlop (a11

kivételével) 0 (k) (1) (2) lesz. Jelöljük A -gyel A-t (az eredeti mátrixot), a többi: A , ., A(n) lesz, A(k) elemeit pedig aij -val (k) (k) aik · akj (k+1) (k) aij = aij − , ha i > k, j ≥ k (k) akk (k) Inkább nem, bár ellen®rizhetjük, hogy aik = 0 teljesül-e: írjunk j helyett k -t. Akkor: Állítás. Biz.: (k) aik − (k) (k) aik · akk (k) akk =0 (1) Így A − A(2) − . − A(n) = U lesz Kérdés: A(k+1) kifejezhet®-e A(k) -val? (k+1) Hogyne, méghozzá: A = Lk (v (k) ) · A(k) (k) Az iménti állításban szerepl® Lk (v ) ∈ Rn×n mátrix az egységmátrixtól Állítás. Dení ió. sak a k -dik oszlopban különbözik, méghozzá úgy, hogy a k -dik oszlopban a v vektor áll, aholis feltesszük, hogy vi = 0, 1 ≤ i ≤ k . Dení ió. Az fogalmak felhasználásával jelöljük: L := {L ∈ Rn×n |lij = 0 : i < j} alsóháromszög-mátrixok halmaza, U := {U ∈ Rn×n |uij = 0 : i > j} fels®háromszög-mátrixok halmaza, és L ⊃ L1 :=

{L ∈ L : a f®átlóban supa 1-esek vannak} Következmény. Lk (v ) alsóháromszög-mátrix, a f®átlóban egyesekkel: Lk (v(k) ) ∈ L1 Állítás. Belátható, hogy: (k) i) L′ , L′′ ∈ L =⇒ L′ · L′′ ∈ L ii) L ∈ L és ∃L−1 =⇒ L−1 ∈ L, e kett® hasonlóan teljesül U -ra is, továbbá iii) L ∈ L1 =⇒ ∃L−1 ∈ L1 , s®t: iv) Lk (v)−1 = Lk (−v) 2 Állítás. Reprezentá ió: Lk (v) = I + veTk , ahol ek a k-dik egységvektor Nyilván ebben a diádban (veTk )ij = vi (ek )j T T T T A reprezentá ió felhasználásával a korábbi állítás iv) pontja így hangzik: I = I + vek − vek − vek vek , T T T T ugyanis az utolsó összeadandóban átzárójelezve: v(ek v)ek = v0ek = 0, mert ek v = vk = 0. Már sak azt kellene kideríteni, hogy egy Li (v)Lj (v), i 6= j szorzatról nem mondhatunk-e valami jót. Dení ió. Az Li (v)Lj (v), i 6= j mátrixok szépen szorozhatók, ha a szorzat a két vektor bemásolásával adódik Lemma.

Az Li (v)Lj (v), i < j szépen szorozható, és egy ilyen mátrix inverze is szép: i) Li (u) · Lj (v) szépen szorozható, és ii) Li (u)−1 = Li (−u) Példa. Vegyünk két ilyen mátrixot, és szorozzuk össze ®ket:  1  5   6 7 1 0 1 0 0   1   0 ·   0 1 0 1 2 1 3 0   1   5 1 =   6 2 1 7 3 1 0 1     Megjegyzés. Most azt fogjuk bizonygatni, hogy a Gauss-eliminá ió lényegében az LU -felbontással egyezik meg. Állítás. U = A(n) = Ln−1(v(n−1) )Ln−2 (v(n−2) ) · · · L1 (v(1) ) · A = Ln−1 Ln−2 · · · L1 A Biz.: Ennek jobboldali része teljes induk ióval igazolható Ami az U -val való egyez®séget illeti: U L−1 n−1
U −1 −1 L1 L2 · · · L−1 n−1 U
= A(n) = Ln−1 Ln−2 · · · L1 A = Ln−2 · · · L1 A = A −1 −1 L−1 1 L2 · · · Ln−1 =: L. Itt a korábbi lemmáknak köszönhet®en (1) −1 (2) −1 L = L1 (v ) L2 (v ) · · · Ln−1

(v (n−1) )−1 = L1 (−v (1) )L2 (−v (2) ) · · · Ln−1 (−v (n−1) ), melyek szépen Akkor szorozhatók. Megjegyzés. Praktikus módszer L kiszámítására: 1) Kezdetben: L := I 2) Az illet® szorzót (vmelyik sor vhányszorosát hozzáadom vhova.) beírjuk az adott pozí ióba NEGATÍV el®jellel! (k) aik (k+1) (k) (k) = aij − (k) Emlékeztet®: aij · akj , ahol a tört a szorzó. akk Akkor oldjunk meg egy feladatot: Példa.  3 0 A= 6 1 −3 3  −2 −3  , 9 3   7 b =  18  9   3 0 −2 7  6 1 −3 18  − −3 3 9 9 A U I b b̃ b̂ = x  3 0  0 1 0 3    −2 7 3 4  −  0 1 0 7 16 1 0 L1 =  2 1 −1 0 =⇒  1 0 L= 2 1 −1 3   0 1 0 0  −  2 1 1 −1 3 3 0  0 1 0 0  −2 7 1 4  1 1  utolsó sort 3 0 −  0 1 0 0  0 0  = L1 · L2 1 (szépen szorzódik)  0 0  1  Most jön x keresése. Az utolsó sort kapásból elosztom

4-gyel   0 −2 7 1 1 4  0 4 4 0 0 1 3 0 , U = 0 1 0 0  −2 1  4   9 1 3  −  0 1 0 0 0 1 0 0 1 hozzáadogatom a  3 3  1 (:3) felette lév®höz   3 b̂ =  3  = x 1 =⇒ 1.2 Gauss-Jordan eliminá ió, m¶veletigény, invertálás A módosított eliminá ió a következ®: 1) 1. sor vhányszorosát hozzáadom az alatta lév® sorokhoz 2) 2. sor vhányszorosát hozzáadom az alatta lév® sorokhoz, meg még a felette lév® sorhoz is k) k. sor vhányszorosát hozzáadom az alatta lév® sorokhoz, meg még a felette lév® sorokhoz is Ennek eredményeképp nem egy fels®háromszög-mátrix, hanem egy diagonális mátrix alakul ki, jobboldalt pedig megjelenik az eredmény. Megjegyzés. A lineáris algebra tipikus m¶velete a skalárszorzat: legyen egy összeadás/kivonás/szorzás/osztás. Állítás. Gauss-eliminá ió m¶veletigénye: n2 + (n − 1)2 + (n − 2)2 + . + 1 = Így T (G) = P ai bi , ennek megfelel®en 1

ag n(n + 1)(2n + 1) 6 1 3 2 3 n + O(n ) Állítás. Gauss-Jordan eliminá ió m¶veletigénye: n2 + n(n − 2) + n(n − 2) + . + n · 1 = n(n + (n − 1) + + 1) = n · Így T (G − J) = n2 (n + 1) n(n + 1) = 2 2 1 3 2 2 n + O(n ) rosszabb, mint a Gauss-eliminá ió m¶veletigénye. 4 Állítás. Mátrix inverzének kiszámolása: Mindkét megközelítéssel kiszámolható A−1 , supán b helyett az In -nel indulunk:   AX = I ⇐⇒  1 ··· 0 . . . n×n . . . . . 0 . 1 1.3 Egziszten ia és uni itás    Megjegyzés. 1) (k) akk 6= 0, (k = 1, ., n − 1) − gond: az algoritmus k -dik lépése is kell hozzá. 2) Az eredeti mátrixszal vajon ez megfogalmazható-e? Állítás. Legyen AK az A mátrix balfels® K × K -as részmátrixa: AK := (aij )j=1K i=1.K Akkor: |AK | 6= 0 (K = 1, . , n − 1) Biz.: Persze ez (k) ⇐⇒ akk = 0 (k = 1, ., n − 1) sak elvi jelent®ség¶, hiszen a determináns kiszámolása lényegesen

m¶veletigényesebb. Háromszögmátrixokról lévén szó, könnyen látható, hogy AK = LK · UK . Most |AK | = |LK | · |UK | = 1 · |UK | = |UK |, mivel LK f®átlója supa 1-esb®l áll. UK viszont fels®háromszög(1) (k) mátrix, így determinánsa a f®átlóbeli elemek szorzata: |UK | = a11 · · · akk . Ennek megfelel®en: ) (1) (k) |AK | = a11 · · · akk |AK | (k) = akk =⇒ (1) (k−1) |AK−1 | |AK−1 | = a11 · · · a(k−1)(k−1) mint az eliminá ió. Tétel. Ha |AK | 6= 0, (K = 1, , n), akkor az egziszten ia és uni itás egyaránt igaz Bizonyítás: Az uni itást látjuk be. L 1 U1 = A = L 2 U2 /Ha |An | 6= 0 |L1 U1 | = |A| = |L2 U2 | 6= 0 |L1 ||U1 | = |L2 ||U2 | 6= 0 −1 −1 −1 −1 Ezért |L1 |, |U1 |, |L2 |, |U2 | 6= 0, így ∃L1 , L2 , U1 , U2 . Akkor viszont: −1 / · L−1 1 , ·L2 L 1 U1 = L 2 U2 −1 L−1 2 L 1 = U2 U2 , ahol a baloldalon alsó-, jobboldalon fels®háromszög-mátrix áll, így mindkett® sak az egységmátrix lehet,

amib®l L1 = L2 , U1 = U2 következik. 1.4 Tridiagonális mátrix LU -felbontása, Cholesky-faktorizá ió Legyenek y(a) =: ya és y(b) =: yb rögzített konstansok, a = x0 < x1 < . < xn = b egy ekvidisztans felosztás: xi+1 − xi = h = b−a n . Közelítjük a második deriváltat: ′′ y (xi ) =  y(xi+1 ) − y(xi ) y(xi ) − y(xi−1 ) − h h  · 1 y(xi+1 ) − 2y(xi ) + y(xi−1 ) = ≈ f (xi ) h h2 2 Vezessük be az yi := y(xi ) jelölést. Akkor most yi+1 − 2yi + yi−1 = h f (xi ), 5 1 ≤ i ≤ n − 1. y0 − 2y1 y1 + − y2 2y2 + = = y3 . h2 f (x1 ) h2 f (x2 ) . . . . yn−2 − 2yn−1 + yn = / · (−1) h2 f (xn ) Megjegyzés. Próbáljuk meg alkalmazni az eddig tanultakat Tegyük fel, hogy az y ′′ (x) = f (x), [a, b] egyenletet szeretnénk megoldani.  −1 2 −1  −1 2 −1   −1 2 −1   .  . x∈     y0 −h2 f (x1 )   y1   −h2 f (x2 )     

  y2   −h2 f (x3 )   =    .   .  .   .   . −1 yn −h2 f (xn−1 ) −1 2 Nyilván a baloldalon álló oszlopvektor n + 1 elem¶, míg a jobboldalon álló vektor n − 1 elem¶. Ebb®l viszont következik, hogy a baloldalon álló mátrix (n − 1) × (n + 1) -es. Mi viszont sak n × n -es mátrixszal tudunk mit kezdeni, ezért a mátrix els® oszlopában álló y0 és utolsó oszlopában álló yn elemet egy vektorba foglalva átvisszük a jobboldalra:  2 −1  −1 2 −1   −1 2 −1   .  . A kérdés         y0 −h2 f (x1 ) y0 −h2 f (x1 ) + ya 2   y1       −h2 f (x2 )       0   −h2 f (x2 )  2   y2        −h f (x ) 0 −h f (x ) 3 + 3  = =    .      .  .  . .  .  .        2 . . . . 2 2 −1

yn −h f (xn−1 ) yn −h f (xn−1 ) + yb supán az, hogy itt a baloldali mátrixnak létezik-e inverze. A baloldali mátrixra ezentúl tridiag(−1, 2, −1) ∈ R(n−1)×(n−1) jelöléssel hivatkozunk. Determinánsa (teljes induk ióval igazolható):   2 3 n+1 · ··· = n + 1 > 0, |tridiag(−1, 2, −1)| = (1 · 1 · 1 · · · 1) · 1 2 n tehát invertálható. Megjegyzés. A = AT a szimmetria miatt, de sajnos ebb®l még nem következik, hogy A LU T T felbontásában U = L volna. Az viszont igazolható, hogy ha A = A és ∃LU = A felbontás, akkor ∃D T e felbontást diagonális mátrix, melyre A = LDL . Az LU felbontásból mindig el®állíthatunk egy LD U e e úgy, hogy az LU -felbontásban U diagonálisát kiemeljük U -ból U = D U módon. Ekkor U f®átlójában 1-esek lesznek. Így újrafogalmazva a megjegyzést: belátható, hogy amennyiben A = AT és e felbontás, akkor ∃A = LU = LDU L = UT . Állítás. Az egziszten ia és uni itás

feltétele, hogy |AK | 6= 0, (K = 1, , n) Megjegyzés. Tegyük fel, hogy A = LDU úgy, hogy dii = ±1 és uii = lii Akkor: i) A = LDU =⇒ AT = U T DLT . Az uni itás tétele miatt L = U T és U = LT teljesül ii) Ha A = AT szimmetrikus és pozitív denit, akkor D-re teljesül, hogy ∀i = 1, ., n : dii > 0 Ezt inkább nem bizonyítjuk. Megjegyzés. Ha A szimmetrikus pozitív denit, akkor A = LDLT felbontás√létezik, és benne D √ is pozitív denit, azaz minden f®átlóbeli eleme pozitív. √ √ D = ( dii )ni=1 . Akkor viszont: Akkor viszont amennyiben √ √ √ √ A = LDU = L D DU = (L D)( DU ) 6 D = D D jogos felírás, az úgynevezett Cholesky-felbontás. Mint mondottuk volt, U = LT , így a szimmetrikus pozitív denit A mátrix Cholesky-felbontása: √ √ √ √ √ √ A = (L D)( DU ) = (L D)( DLT ) = (L D)(L D)T Állítás. Kiegészítés [1℄ m¶véb®l Cholesky-felbontása sak szimmetrikus mátrixnak létezhet Biz.: Ugyanis: AT = (LLT )T

= LT L = LLT = A Állítás. Kiegészítés [1℄ m¶véb®l A szimmetrikus pozitív denit A mátrix Cholesky-felbontása: A = L · LT alakban írható, ahol L alsóháromszög-mátrix, melynek f®átlója szigorúan pozitív, de nem feltétlenül 1. Továbbá a felbontásban szerepl® L mátrix elemei valósak lesznek Biz.: A mátrix méretére vonatkozó teljes induk ióval bizonyítunk Tegyük fel, hogy (n − 1) × (n − 1)-es szimmetrikus pozitív denit mátrixra már bizonyítottuk az állítást. Akkor tekintsük az A szimmetrikus pozitív denit mátrix egy partí ióját:  An =  An−1 b T ann b   Minthogy An szimmetrikus pozitív denit, így szükségképpen An−1 is az. T megfelel® alsóháromszög-mátrix, melyre Ln−1 Ln−1 = An−1 . Most (det Ln−1 )2 = det An−1 6= 0 ⇒ Ezért létezik olyan Ln−1 Ln−1 nem szinguláris = b egyenletrendszer megoldható, tegyük is fel, hogy ennek c ∈ Rn−1 egy megoldása, vagyis Ln − 1c = b.

Most tetsz®leges x ∈ R mellett:   T     Ln−1 c An−1 b Ln−1 0 · =   T T T 2 c x 0 x b c c+x Akkor viszont az Ln−1 x Ezek szerint ann = c T c + x2 megadja x értékét. A kérdés sak az: mindig valós lesz-e x? Ha most vesszük az iménti egyenlet bal- és jobboldalának determinánsát, akkor: det   Ln−1 c T 0 x   · LTn−1 c 0 x    = (det Ln−1 )2 x2 = det An = det  b An−1 b T T 2 c c+x  >0 2 Ebb®l akkor x > 0 is következik, tehát megfelel® választással elérhet®, hogy x > 0, x ∈ R legyen. Megjegyzés. Kiegészítés [1℄ m¶véb®l Ha az A mátrix szimmetrikus ugyan, de nem pozitív denit, akkor a Cholesky-felbontás nem feltétlenül lehetséges. Pl: A=  0 1 1 0  Megjegyzés. Kiegészítés [1℄ m¶véb®l Valós, nem szinguláris L alsóháromszög-mátrix esetén LLT mindig pozitív denit lesz: (LLT x)T = xT LLT x = (LT x)T (LT x) =

(LT x)2 > 0 1.5 Invariáns tulajdonságok, S hur-komplementer Állítás. A Gauss-eliminá ió f®bb jellemz®i 7 i) Szimmetrikus mátrix esetén az eliminá ió munkamátrixa mindvégig szimmetrikus marad ii) Szimmetrikus pozitív denit mátrix esetén az eliminá ió munkamátrixa mindvégig szimmetrikus pozitív denit marad Biz.: (1) (1) (1) i) Az els® lépést elvégezve: a(2) ij = aij − szimmetrikus. Tudjuk, hogy ai1 a1j a11 (1) aij (1) ai1 (1) a1j igaz a jobbalsó részre. Azt kell belátni, hogy ez (1) = = = aji (1) a1i (1) aj1 mivel az eredeti mátrix szimmetrikus volt. Innen triviális ii) Egy A mátrix akkor szimmetrikus pozitív denit, ha ∀x 6= 0 : xT Ax > 0. Az állítást viszont nem bizonyítjuk. Emlékeztet®. LU egziszten iájának feltétele, hogy |AK | 6= 0 minden K = 1, , n esetére teljesüljön Ugyanakkor elképzelhet®, hogy A mátrix esetében ez sak a sorok megfelel® átrendezésével teljesülne, a11 = 0 esetén. Ezért

felmerül a kérdés: mi van akkor, ha a Gauss-eliminá iót nem egy skalárra, hanem egy egész blokkra képzeljük el? Tekintsük az A mátrix egy olyan   A11 A12 , A= A21 A22 pl. partí ióját, ahol A11 négyzetes mátrix és determinánsa nem nulla. Ekkor nyilván A22 is négyzetes. Parti ionáljuk ennek megfelel®en a megoldandó egyenletrendszer mátrix reprezentá ióját is:  ahol A11 ∈ R k×k A11 A21 A12 A22  x1 x2  =  b1 b2  , , A22 ∈ R(n−k)×(n−k) . Kibontva: A11 x1 A21 x1 + + A12 x2 A22 x2 = b1 = b2 −1 Kiküszöböljük x1 -et az inverzzel: x1 = A11 (b1 − A12 y2 ), amit behelyettesítve a második egyenletbe: A21 (A−1 11 (b1 − A12 x2 )) + A22 x2 = b2 /kif ejezzk : −1 (A22 − A21 A−1 11 A12 )x2 = b2 − A12 A11 b1 Dení ió. S hur-komplementer: Az imént el®állított partí ióban szerepl® A11 mátrix eredeti A mátrixra vonatkozó S hur-komplemensének nevezzük, és így jelöljük a következ® mátrixot: A/A11 =

A22 − A21 A−1 11 A12 Megjegyzés. A jelölés oka: |A| = A11 A21 A12 A22 = A11 0 A12 A/A11 = |A11 | · |A/A11 | |A| = |A/A11 | valóban. |A11 | Állítás. Ha A szimmetrikus pozitív denit, akkor A/A11 is az Biz.: A/A11 = A22 − A21 A−1 11 A12 8 Szimmetria: A = AT ⇔ A11 = AT11 és A22 = AT22 , valamint A12 = AT21 .Ha A11 szimmetrikus és invertálható, −1 akkor A11 is az, és: −1 T T −1 T T (A21 A−1 11 A12 ) = A21 (A21 ) A21 = A21 A11 A12 szimetrikus, akkor A/A11 is szimmetrikus kell, hogy legyen. Poz.def: Ha A poz n−k n T def., akkor A11 és A22 is az ∀x ∈ R , x 6= 0 : x Ax > 0 Akkor kellene, hogy T , x2 6= 0 : x2 Ax2 > 0 legyen. Adott x2 -höz választhatunk alkalmas x1 -et, melyre ∀x2 ∈ R A11 x1 + A12 x2 = 0 1.6 Diagonális dominan ia, irredu ibilitás Dení ió. Diagonális dominan ia: A ∈ Rn×n mátrix i) szigorúan diagonálisan domináns, ha ∀i = 1, ., n : |aii | > ii) gyengén diagonálisan domináns, ha

általában sak {1, 2, ., n}, ahol szigorúan teljesül az egyenl®tlenség n X j6=i j=1 |aij | ≥-re teljesül, de létezik legalább egy i ∈ Megjegyzés. Az iménti dení ió sorirányban deniálja a diagonális dominan iát Lehet oszlopirányban is deniálni Állítás. Ha A diagonálisan domináns, akkor a Gauss-eliminá ió munkamátrixa az eliminá ió során mindvégig diagonálisan domináns marad. Biz.: A(1) := A Akkor az új A(2) mátrix elemei: (2) aij = aij − ai1 a1j a11 aij − ai1 a1j = , a11 a11 i, j = 1, ., n n Elég [a11 aij − ai1 a1j ]i,j=2 mátrixra belátni a diagonális dominan iát: |a11 aij − ai1 a1j | > X j=1 j6=i |a11 aij − ai1 a1j | Állítás. Ha A tridiagonális mátrix, akkor az el®z® állítás úgy is teljesül, ha nem írunk el® szigorú diagonális dominan iát, hanem megelégszünk a gyenge dominan iával, supán azt írjuk el®, hogy legyen legalább egy olyan sor, melyre szigorúan teljesül a dominan ia. Ez

az állítás viszont sak tridiagonális mátrixokra lesz igaz, általános diagonálisan domináns mátrixokra nem.> Biz.:  a1   c1 A=   b1 a2 . . . . . . cn−1   1 0     l1 =   bn−1   an 0 . . . . ai 1 . . ln−1 1 Vizsgáljuk az Ax = d egyenletrendszert: ci−1 bi = li−1 9 0 · ui−1 0 0       ·     vi−1 ui 0 u1 v1 u2 0 0 vi ui+1 . . . .      vn−1  un   ci−1 ⇒ ai  bi   li−1 ui−1 ci   li−1 vi−1 + ui ai+1 és   vi bi+1 = = =  = li u i  = li vi + ui+1  = vi+1 Nyilván a1 = u1 , b1 = v1 . Mivel |a1 | > |b1 | ⇒ |u1 | > |v1 | Kell, hogy |ui | > |vi | teljesüljön (i = 1, , n) Induk ióval okoskodunk: Tegyük fel, hogy |ui | > |vi |, akkor: |ui+1 | = |ai+1 − li vi | ≥ |ai+1 | − |li | · |vi | = |ai+1 | − |vi | · |ui | · |li | > |ui | >

|ai+1 | − |ui | · |li | = |ai+1 | − |ci | ≥ |bi+1 | = |vi+1 | Következmény. Ekkor a mátrix invertálható Következmény. Sávjelleg: Az n × n-es A mátrix (k, l) típusú, ha: aij = 0, ha i < j + k vagy i > j − l Például a tridiagonális mátrix (1, 1) típusú sávmátrix. Megjegyzés. Van prolmátrix is, de azt sokáig tart lerajzolni Mindenesetre a felbontás proltartó, bár feltölt®dés el®fordulhat. Megjegyzés. Passage (Progonka) módszer: Tridiagonális mátrixszal reprezentálható egyenletrendszer megoldására jó.  Akkor az i-edik sor: a1   c1    b1 a2 . . . . . . cn−1 ci−1 ai      x1 d1    d2    x2    · .  =  .    .   .   . . bn−1  x d n n an bi
  xi−1  xi  = di xi+1 ci−1 xi−1 + ai xi + bi xi+1 = di Gauss-eliminá ióval: a1 x1 + b1 x2 = d1 a1 x1 + a2 x2 + b2 x3 = d2 − x1 = f1 x2 + g1 − x2 = f2

x3 + g2 . . . xi−1 = fi−1 xi + gi−1 xi = fi xi+1 + gi ci−1 [fi−1 xi + gi−1 ] + ai xi + bi xi+1 = di / xi (ai + ci−1 fi−1 ) + bi xi+1 = di − ci−1 gi−1 / xi = −bi di − ci−1 gi−1 · xi+1 + ai + ci−1 fi−1 ai + ci−1 fi−1 −bi di − ci gi−1 = fi és = gi ai + ci−1 fi−1 ai + ci−1 fi−1 xi = fi xi+1 + gi 10 / Így a megoldás során a, b, c vektorunk van, f -et rekurzióval (el®re haladva) kiszámoljuk, utána g -t visszafele haladva. Következmény: O(n) m¶velettel megoldható a feladat n×n Az A ∈ K -es mátrixot irredu ibilisnek Dení ió. Kiegészítés [2℄ m¶véb®l Irredu ibilis mátrix: nevezzük, ha vagy n = 1, vagy n > 1 és a W = {1, 2, ., n} halmaz bármely két nemüres diszjunkt S és T részhalmazra bontása esetén létezik olyan i ∈ S és j ∈ T , hogy aij 6= 0. Ha A nem irredu ibilis, akkor redu ibilisnek mondjuk. Megjegyzés. Kiegészítés [2℄ m¶véb®l Mint a következ® tétel mutatja, a

redu ibilitás azt jelentené, hogy egy egyenletrendszernek létezik olyan részrendszere, mely a többi egyenlett®l függetlenül is megoldható lenne. Megjegyzés. Kiegészítés [2℄ m¶véb®l Permutálómátrixnak nevezzük a P négyzetes mátrixot, ha minden sorában és minden oszlopában pontosan egy darab zérustól különböz® elem van, és ez az egyes. Minden P permutálómátrixnak megfeleltethetünk egy σ : {1, ., n} {1, , n} bijek iót úgy, hogy pij = 1 ⇔ σ(i) = j Algebrából tudjuk, hogy a permutá iók invertálhatók. Könnyen látható, hogy P permutálómátrix inverzére egyszer¶en: P −1 = P T Állítás. Kiegészítés [2℄ m¶véb®l Az A mátrix akkor és sak akkor irredu ibilis, ha NEM létezik olyan P permutálómátrix, amellyel P −1 AP =  F 0 G H  alakú, melyben F és H négyzetes mátrixok. Biz.: Tfh A irredu ibilis és mégis létezik ilyen P permutálómátrix Akkor most tfh F mátrix p × p-es, és S := {1, 2, ., p},

és T := {1, 2, , n}S Ekkor azonban létezne olyan i ∈ S és j ∈ T , hogy aij 6= 0, hiszen A irredu ibilis, viszont a felbontásban aij = 0 szerepel. Tehát ha A irredu ibilis, akkor ilyen P permutálómátrix nem létezik. Ha viszont A redu ibilis, akkor van ilyen permutálómátrix. Ekkor létezik ugyanis olyan W = S+T partí ió, ahol ∀i ∈ S, ∀j ∈ T : aij = 0, dení ió szerint. P -t úgy kell megválasztanunk, hogy az S -ben −1 szerepl® sorokat és oszlopokat P AP megfelel® soraiba és oszlopaiba transzformálja. Ha nin s ilyen P mátrix, akkor A irredu ibilis. Állítás. Kiegészítés [2℄ m¶véb®l Egy n × n-es A mátrix (n > 1), akkor és sak akkor irredu ibilis, ha két tetsz®leges i, j ∈ {1, 2, ., n} esetén vagy aij 6= 0, vagy létezik olyan i1 , , is sorozat, melyre aii1 ai1 2i2 · · · ais j 6= 0 Biz.: Ha tetsz®leges S + T = W partí ió mellett i ∈ S , j ∈ T mellett aij 6= 0 vagy létezik i1 , , is sorozat, melyre aii1 ai1 i2 · ·

· ais j 6= 0, akkor az el®bbi esetben közvetlenül látszik, hogy A irredu ibilis (dení ió szerint), az utóbbi esetben pedig meg kell gondolnunk, hogy ha a szorzat nem nulla, akkor egyik tényez®je sem nulla, márpedig van benne olyan elem, melynek egyik indexe S -b®l, a másik T -b®l való. Ha A irredu ibilis, és n > 1, akkor ∀i = 1, ., n esetén Xi halmaz álljon azokból a számokból, melyekre vagy aij 6= 0, vagy létezik olyan i1 , ., is sorozat, hogy aii1 ai1 i2 · · · ais j 6= 0 Megmutatjuk, hogy Xi = W {i}. Legyenek ugyanis S1 := {i} és T1 := W {i} Minthogy A irredu ibilis, létezik olyan i1 ∈ T1 , melyre aii1 6= 0, vagyis i1 ∈ Xi . Ha n = 2, akkor Xi = W i így teljesül Ha n > 2, akkor S2 := {i, i1 } és T2 := W S2 . Ekkor A irredu ibilitása miatt létezik olyan i2 ∈ T2 , melyre vagy aii2 6= 0 vagy ai1 i2 6= 0 Ekkor viszont vagy aii2 6= 0 vagy aii1 aii2 6= 0, tehát i2 ∈ Xi . Teljes induk ióval megmutatható, hogy általában is igaz az

Xi = W {i} összefüggés, és még a tételt is beláttuk. Tétel. Kiegészítés [2℄ m¶véb®l Ha A irredu ibilis gyenge diagonálisan domináns mátrix, akkor detA 6= 0, és a diagonális elemek egyike sem zérus. 11 Biz.: Ha a mátrix rendjére n = 1, akkor a gyenge diagonális dominan ia miatt a11 6= 0, így detA 6= 0 is Tfh. n > 1, és valamelyik i-re aii = 0 Ekkor a gyenge diagonális dominan ia miatt az i-dik sor supa 0, így a mátrix nem lehetne irredu ibilis, ami ellentmondás. Ugyanis ha S := {i}, T := W S választással élünk, akkor ∀j ∈ T : aij = 0. Ezzel a tétel f®átlóra vonatkozó részét beláttuk Ismeretes, hogyha detA = 0, akkor az Au = 0 homogén lineáris egyenletrendszernek létezik 0-tól külön- böz® megoldása. Azt már tudjuk, hogy aii 6= 0 minden i = 1, , n-re, ezért egy ilyen u 6= 0 megoldás esetén ui kifejezhet® az i-dik egyenletb®l: ui = n X bij uj i = 1, ., n j=1 aij ha i 6= j . A gyenge diagonális dominan ia

dení iója és bij ezen képletének aii felhasználásával adódik, hogy minden i-re: ahol bii = 0, és bij = − n X j=1 |bij | = n X i=1 n X |aij | aij |aii | i=1 − = ≤ =1 aii |aii | aii és ∃i : n X j=1 |bij | < 1 Legyen M := max |ui |. Most u 6= 0 miatt M > 0 Nyilván ∃k : uk = M Ekkor i n X M = |uk | = Akkor egyrészt M > M · n X j=1 |bij | = n X j=1 j=1 bkj uj ≤ n X j=1 |bij |M , másrészt M ≤ n X j=1 |bkj ||uj | X j = 1n |bkj ||uj |, amib®l |bkj |(|uj | − M ) következik. Ugyanakkor |uj | ≤ M is igaz, ami azt jelenti, hogy valahányszor |bij | 6= 0, mindannyiszor |uj | = M is teljesül, másképp az összeg negatív lenne. Ugyanakkor A irredu ibilis, vagyis az iménti állítás 6= 0, vagy létezik olyan i1 , ., is sorozat, hogy aki1 · · · ais j 6= 0 Tehát vagy bkj 6= 0, vagy bki1 , ., bis j 6= 0 Mindkét esetben |uj | = M adódik Ez viszont azt jelenti, szerint minden j 6= k esetén vagy akj hogy ∀i = 1, ., n :

Másrészt ha i ∗ ∈ {1, ., n} olyan, hogy ami ellentmondás. Tehát u = 0 lehet n X j=1 |uj | = M |bij | < 1, akkor M = |ui∗ | ≤ n X |bi∗ j |M 1≤ n X |bi∗ j | j=1 j=1 / sak, amib®l következik, hogy az Au = 0 egyenletnek a megoldása, így detA 6= 0. 12 sakis u = 0 1.7 Ortogonális-trianguláris (QR) felbontás Megjegyzés. Egy A mátrix ortogonális felbontása: QQT = I = QT Q A = QR , Q ortogonális ⇔ ∀ sor ⊥ ∀ sor ∀ sor ⊥ ∀ oszlop 2 Reméljük, hogy az ortogonális mátrix n /2 paraméterrel paraméterezhet®, ugyanis R trianguláris mátrix, 2 így a szabadságfok n /2-vel sökken. Gram-S hmidt ortogonalizá iós eljárás. Itt az eljárás a mátrix oszlopvektor-rendszerére vonatkon zik. Adott egy (xi )i=1 lineárisan független vektorrendszer (xi )ni=1 − LF (yi )ni=1 − tehát megoldható.  zi := yi ||yi ||2 OG ON (ortogonális) (ortonormált) Ha y1 , ., yn már mer®legesek, akkor yk = xk + k), azaz:

< yk , yi >= 0, (zi )ni=1  k−1 X αi xi , ahol α1 , ., αk−1 isperetlenek és yk ⊥ yi (i < i=1 1 ≤ i ≤ k − 1. Ez elvileg k − 1 ismeretlent és ugyanennyi egyenletet jelent, A QR felbontás meghatározására két módszer van: 1.: Q−1 A = R − Ja obi- és Householder transzformá ió. Lényegében: addig szorozgatjuk A mátrixot egy ortogonális mátrixszal, míg trianguláris nem lesz. 2.: AR−1 = Q − Gram-S hmidt eljárás áll mögötte. Lényegében: addig szorozgatjuk A mátrixot egy trianguláris mátrixszal, míg ortogonális nem lesz. Ha Q1 , ., Qm ortogonális mátrixok, akkor szorzatuk is az, pl m = 2-re: (Q1 Q2 )T Q1 Q2 = QT2 QT1 Q1 Q2 = QT2 (QT1 Q1 )Q2 = QT2 IQ2 = I Elemi ortogonális mátrixok azok a mátrixok, melyek kevés paraméter¶ek: i) Ja obi: 1 paraméteres ii) Householder: n paraméteres Ja obi mátrix.     Uij (ϕ) =     1 c s . . s −c 1   ← i     ← j Itt

i 6= j , a f®átlóban az (i, i) és (j, j) helyeket leszámítva 1-esek állnak, a többi elem 0, illetve: Uii = cos ϕ Uij = sin ϕ Uji = sin ϕ Ujj = cosϕ 13 =: c =: c =: c =: −c Az ortogonalitás ellen®rzéséhez elég az értékes elemekb®l álló részmátrixokat összeszorozni:  Householder mátrix. ahol ||v|| = 1, azaz v T c s s −c  c s s −c  =  1 0 0 1  H = H(v) = I − 2vv T , v = 1. Ez pedig ortogonális, ugyanis: H T H = H 2 = (I − 2vv T )(I − 2vv T ) = I − 2vv T − 2vv T + 4vv T vv T = I − 4vv T + 4v(v T v)v T = I Másik alakban is megadható: H := I − 2 vv T vv T = I − T , ahol v 6= 0 2 ||v|| v v Ha A = [a1 , ., an ] oszlopvektor-partí iója, akkor ak = A·ek alakban írható, ahol ek a k -dik egységvektor Most a := Ae1 . Akkor keressük azt a Q = H(v) spe iális alakú ortogonális mátrixot, mely t · e1 alakba viszi a-t. Tehát keressük v vektort és t skalárt, melyekre: H(v)a = t · e1 Tudjuk, hogy |t| =

||a||, ugyanis ha Q ortogonális mátrix, a pedig tetsz®leges vektor, akkor invarian ia): (unitér ||Qa||2 = (Qa)T (Qa) = aT QT Qa = aT (QT Q)a = aT a = ||a||2 A v vektort pedig így határozhatjuk meg: H(v)a = (I − 2vv T )a = a − 2v(v T a) = te1 Nyilván v= v = a − te1 a − te1 , vagy: v = , mert ||v|| = 1 kell, hogy teljesüljön. T 2v a ||a − te1 || a − te1 esetén t = ±||a|| valóban megfelel®. ||a − te1 || Ortogonális mátrixok általános alakjáról. következ®: n=2:  a −b b a  A 2 × 2-es ortogonális mártixok általános alakja a 1 , majd osszunk le a normával: U = √ 2 a + b2 Ez utóbbi már valós ortonormált mátrix. Ellen®rzésképp:  a b −b a    1 1 1 1 1 1 −1 −1   1  n=4: 1 −1  2  1 −1 1 −1 −1 1   U U Általában: ha U ortogonális, akkor is az. U −U 2. Iterá iós módszerek Az iterá iós módszerek lényege (szemben a direkt módszerekkel), hogy: Ax = b és t.fh ∃A−1

⇐⇒ x = M x + v átírással: x0 ∈ Rn , xk+1 = M xk + v ahol M elég ki si. 14 2.1 Vektornormák és mátrixnormák Dení ió. Vektornorma: Legyen x ∈ Rn Akkor |||| norma, ha |||| : Rn R leképezés, melyre: i) ||x|| ≥ 0 és ||x|| = 0 ⇔ x = 0 ii) ||λx|| = |λ| · ||x||, azaz pozitív homogén iii) ∀x, y : ||x + y|| ≤ ||x|| + ||y||, azaz teljesül a háromszög-egyenl®tlenség Példák. v u n uX p p ||x||p = t xi a három legfontosabb: p = 1, 2, ∞ i=1 ||x||1 = X |xi | , ||x||2 = qX |xi |2 , ||x||∞ = max |xi | i n Itt a 2-es norma esetén |xi |-re azért van szükség, mert így a norma C esetén is értelmes. Természetesen R2 -ben például ||x|| = |x1 | + |x2 | módon deniált leképezésr®l is belátható, hogy norma. x ∈ Rn , akkor ||x|| = limp∞ ||x||p Állítás. Biz.: Az általánosság sorbítása nélkül feltehetjük, hogy x = (x1 , ., xn ) vektor legnagyobb eleme x1 Ekkor: p p p 1/p (|x1 | + |x2 | + . + |xn | )

ugyanis xi ≤ 1, x1 1/p  x2 xn + . + − |x1 |, = |x1 | 1 + x1 x1 p∞ i > 1. Megjegyzés. Egységgömbök R2 -ben: ||.||1 : rombusz , ||.||2 : kör , ||.||∞ : négyzet Állítás. Kiegészítés [1℄ m¶véb®l Mindenx x ∈ Rn vektorra: i) ||x||∞ ≤ ||x||1 ≤ n · ||x||∞ √ ii) ||x||∞ ≤ ||x||2 ≤ n · ||x||∞ √ iii) ||x||2 ≤ ||x||1 ≤ n · ||x||2 Biz.: iii) Tudjuk, hogy ||x||2 = mely szerint pP x2i ≤ P X |xi | = ||x||1 . Másrészt ismeretes a Cau hy-egyenl®tlenség, |xi ||yi | ≤ x2i qX qX yi2 T Ennek felhasználásával, spe iálisan y = (1, 1, ., 1) választással: ||x||1 = √ n||x||2 . Megjegyzend®, hogy spe iálisan az e = (1, 1, , 1)T vektorra P |xi | ≤ pP x2 P 2 1 = iii) állítás mindkét egyen- l®tlensége egyenl®ségra teljesül. Állítás. Kiegészítés [1℄ m¶véb®l Legyen |||| tetsz®leges vektornorma Akkor a ϕ : Rn R : ϕ(x1 , ., xn ) := ||x|| 15 n függvény folytonos leképezés R

-b®l R-be. T ∗ ∗ ∗ T n Legyenek x = (x1 , ., xn ) és x = (x1 , , xn ) tetsz®leges vektorok Ha e1 , , en bázis R -ben, Biz.: akkor X x= xi ei és x∗ = X x∗i ei ∗ ∗ ∗ ∗ Másrészt |ϕ(x1 , ., xn ) − ϕ(x1 , , xn )| = |||x|| − ||x ||| ≤ ||x − x || Ugyanakkor X X (xi − x∗i )ei ≤ |xi − x∗i | · ||ei || ||x − x∗ || = ∗ ∗ Ezek szerint a |ϕ(x1 , ., xn )−ϕ(x1 , , xn )| eltérés tetsz®legesen ki sivé tehet®, ha a megfelel® koordináták elérése elegend®en ki si. Dení ió. Normák ekvivalen iája ( [1℄-b®l idézve): Az ||||(1) és ||||(2) normákat ekvivalenseknek ne- vezzük, ha ∃m, M ∈ R : ∀x ∈ Rn : m||x||(1) ≤ ||x||(2) ≤ M ||x||(1) Megjegyzés. A dení ió jogos, a relá ió valóban ekvivalen ia Ugyanis: belátható, hogy reexív, szimmetrikus és tranzitív. ||x||(2) ≤ M ||x||(1) , akkor A reexivitás az m = M = 1 választással adódik. (1) Ha most m||x|| ≤ 1 1 ||x||(2) ≤ ||x||(1)

≤ ||x||(2) M m vagyis a szimmetria is teljesül. Még tranzitív is, hiszen tegyük fel, hogy m1 ||x||(1) ≤ ||x||(2) ≤ M1 ||x||(1) m2 ||x||(2) ≤ ||x||(3) ≤ M2 ||x||(2) és Akkor a második egyenl®tlenség bal oldalára kon entrálva: ||x||(2) ≤ ||x||(3) · 1 m2 ⇒ m1 ||x||(1) ≤ ||x||(2) ≤ ||x||(3) · 1 m2 / m1 m2 ||x||(1) ≤ ||x||(3) Hasonlóan a másik oldal is belátható. Állítás. Kiegészítés [1℄ m¶véb®l Rn -ben minden norma ekvivalens Biz.: Most megmutatjuk, hogy tetsz®leges Rn -beli vektornorma ekvivalens ||||2 euklideszi normával T n n Legyen x = (x1 , x2 , ., xn ) tetsz®leges R -beli vektor Mint tudjuk, a norma folytonos függvény R ben, így a ϕ(x1 , , xn ) halmazt: := ||x|| folytonos tetsz®leges ||.|| norma esetén Jelöljük G-vel a következ® G := {x ∈ Rn : ||x||2 = 1} n Ekkor G korlátos és zárt R -ben. Akkor viszont ϕ felveszi maximumát és minimumát G-n: ∃m, M ∈ R : 0 < m ≤ ϕ(x1 , ., xn ) ≤ M <

∞ (x ∈ G) n Tekintsünk most egy tetsz®leges x 6= 0, x ∈ R vektort. (x∗1 , ., x∗n )T vektorra ||x∗ ||2 = 1 Akkor viszont Legyen még ; σ := ||x||2 > 0. x∗ := σ1 x = m ≤ ϕ(x∗1 , ., x∗n ) = ||x∗ || ≤ M 1 ∗ ||x|| = Viszont ||x || = σ 1 ||x||, így aztán ||x||2 m||x||2 ≤ ||x|| ≤ M ||x||2 n esetén is fennáll, vagyis minden x ∈ R -re beláttuk. n×n n×n Legyen A ∈ R , akkor ||.|| : R R leképezés, melyre: Ugyanez az egyenl®tlenség x = 0, x ∈ R Dení ió. Mátrixnorma: n 16 i) ||A|| ≥ 0 és ||A|| = 0 ⇔ A = 0 ii) ||λA|| = |λ| · ||A||, azaz pozitív homogén iii) ∀A, B : ||A + B|| ≤ ||A|| + ||B||, azaz teljesül a háromszög-egyenl®tlenség iv) ∀A, B : ||A · B|| ≤ ||A|| · ||B||, azaz teljesül a szubmultiplikativitás Példák. 1) Kinyújtjuk a mátrixot: A ∈ Rn×n − a ∈ Rn 2 átalakítással élünk, a mátrixot egy vektorba nyújtjuk ki, oszlop- vagy sorfolytonosan, majd a mátrix normáját

az így kapott vektor normájával azonosítjuk. Ekkor viszont sajnos a szubmultiplikativitás nem fog teljesülni, úgyhogy ez a fajta leképezés nem lesz mátrixnorma. 2) Indukált mátrixnorma: ||A|| = sup  ||Ax|| x 6= 0 ||x||  ≡ sup { ||Ax|| | ||x|| ≤ 1} ≡ sup { ||Ax|| | ||x|| = 1} Mivel véges dimenziós a vaktrotér, a halmaz Weierstrass szerint a maximumát is felveszi, ezért felesleges a sup. 3) Praktikus dení ió: ||A|| := min{K > 0 | Ax ≤ K x ∀x ∈ Rn } XX |aij | · |xj | = Példák indukált mátrixnormára. 1) ||.||1 által indukált ||A||1 mátrixnorma: ||Ax||1 = n X n X i=1 j=1 Legyen K := maxj aij xj ≤ P XX i j |aij | · |xj | = j i X j |xj | X i |aij | i |aij |, ekkor ||Ax||1 ≤ K||x||1 Lemma. A következ® mátrixnormák a megfelel® vektornormából indukálhatók: i) ||A||1 = ||A||osz ≡ maxk P ii) ||A||∞ = ||A||sor ≡ maxi p iii) ||A||2 = r(AT A) i |aik | oszlopnorma P k |aik | sornorma Biz.:

Kiegészítés [1℄ m¶véb®l i) ||Ax||1 = n X n X i=1 k=1 ≤ n X k=1 n X n n n X X X |aik ||xk | = |aik ||xk | = |xk | |aik | ≤ i=1 k=1 i=1 i=1 k=1 k=1 ! n n X X max |aik | = ||x||1 max |aik | aik xk ≤ |xk | · k n X n X k i=1 Tehát ||A||1 ||x||1 ≤ ||Ax||1 ≤ ||x||1 maxk Pn i=1 |aik | ||A||1 ≤ max k 17 i=1 / : ||x||1 6= 0 n X i=1 |aik | Másrészt ∃m ∈ N : 1 ≤ m ≤ n, melyre n X i=1 |aim | = max k Ha most em egységvektor, akkor ||Aem ||1 = n X i=1 n X i=1 |aik | |aim | = max k ||A||1 ≥ max k n X i=1 n X i=1 |aik |. De ||em ||1 = 1, ezért |aik | A két eredmény összevetéséb®l adódik az állítás. ii) A bizonyítás nagyban hasonlít az el®z®re. ||Ax||∞ = max i n X k=1 aik xk ≤ max i ≤ max |xk | max i k Tehát ||A||∞ ≤ maxi n X k=1 n X k=1 |aik | = ||x||∞ max i Pn k=1 |aik |. Nyilván ∃j ∈ {1, , n} : xT0 := (sgn(aj1 ), ., sgn(ajn )) ||Ax0 ||∞ ≥ n X ajk xk = k=1 |aik ||xk | ≤

n X k=1 n X k=1 ⇒ n X k=1 |aik | |ajk | = max i n X k=1 |aik |. Legyen most ||x0 ||∞ = 1 |ajk | = max i n X k=1 |aik | A két eredményt összevetve adódik az állítás. iii) Tetsz®leges A ∈ Rn×n esetén AT A szimmetrikus pozitív denit lesz. Ugyanis (AT A)T = AT · (AT )T = AT A T T T T T 2 Másrészt x (A A)x = (x A )(Ax) = (Ax) (Ax) = ||Ax||2 pozitív denit is. Ismeretes, hogy ≥ 0 tetsz®leges x ∈ Rn -re, tehát - szimmetrikus mátrixok sajátértékei mindig valósak - szimmetrikus mátrixoknak mindig van n darab páronként ortogonális sajátvektoruk - szimmetrikus mátrixok sajátvektoraiból kiválasztható R n egy ortogonális bázisa - szimmetrikus pozitív denit mátrix sajátértékei nemnegatívok T a most v1 , ., vn az A A különböz® sajátvektorai (tegyük fel, hogy már normáltuk ®ket, tehát ||vi || = 1, i = 1, ., n), a vonatkozó sajátértékekre pedig λ1 ≥ ≥ λn ≥ 0 teljesül, akkor tetsz®leges x ∈ Rn

esetén ∃!α1 , ., αn ∈ R : x = α1 v1 + + αn vn 18 Akkor viszont: ||Ax||22 = (Ax)T Ax = xT AT Ax = xT (AT Ax) = n n n X n n X X X X T T = αk vk · αm λm vm = αk αm λm vk vm = α2k λk ≤ m=1 k=1 ≤ λ1 n X k=1 k=1 m=1 k=1 α2k = λ1 ||x||22 √ λ1 . Ugyanakkor x = v1 esetén: ||Av1 ||22 = v1T (AT Av1 ) = v1T λ1 v1 = λ1 v1T v1 = λ1 , Tehát ||A|| ≤ hiszen ||v1 || = 1 volt. Következmények. Kiegészítés [1℄ m¶véb®l i) A szimmetrikus ii) ||A||∞ = ||AT ||1 AT A = A2 ⇒ ⇒ ||A||2 = r(A) iii) ||A||22 ≤ ||A||1 ||A||∞ , ugyanis ||A||22 = r(AT A) ≤ ||AT A||1 ≤ ||AT ||1 ||A||1 = ||A||∞ ||A||1 Dení ió. Frobenius-norma: A ∈ Cn×n , akkor ||A||F = sX X i j |aij |2 Dení ió. Az ||||M mátrixnorma illeszkedik a ||||v vektornormához, ha ∀A ∈ Rn×n , ∀x ∈ Rn : ||Ax||M ≤ ||A||M · ||x||v Lemma. Létezik olyan vektornorma, melyhez a Frobenius-norma illeszkedik, de nin s olyan vektronorma, mely a Frobenius-normát

indukálná Biz.: Belátható, hogy ||||F illeszkedik ||||2 -höz Ezt most nem látjuk be Ugyanakkor ha ||||i egy indukált mátrixnorma, akkor ||In ||i = sup  ||Ix|| , x 6= 0 ||x||  = 1, de ||In ||F = √ n 6= 1, ha n > 1 Dení ió. Spektrálsugár: Egy A ∈ Cn×n mátrix spektrálsugara a sajátértékek abszolútértékének a maximuma: r(A) = max |λi (A)| i ahol n {λi (A)}i=1 az A mátrix sajátértékei. Megjegyzés. Nyilván az imént deniált spektrálsugár általában nem norma Például A = mátrix spektrálsugara 0, normája viszont nem, hiszen nem a nullmátrixról van szó.  0 0 1 0  Ugyanakkor ha A mátrix szimmetrikus, akkor korábbi állításunk értelmében ||A||2 = q p r(AT A) = r(A2 )
2 λi (A) , így a maximumra is: ||A||2 = maxi |λi (A)| = r(A). Ha még A pozitív denit is, akkor a sajátértékei mind nemnegatívok, így ||A||2 = max λi (A). T 2 Szimmetrikus mátrix esetén igaz, hogy λi (A A) = λi (A ) = 19

Állítás. Kiegészítés [1℄ m¶véb®l Minden |||| mátrixnormára és minden A ∈ Rn×n mátrixra r(A) ≤ ||A||. Biz.: Legyen λ az A egy sajátértéke, v a hozzá tartozó sajátvektor Ekkor Av = λv, v 6= 0 Most ||v|| · |λ| = ||λv|| = ||Av|| ≤ ||A|| · ||v|| ahol az utolsó egyenl®tlenségben kihasználtuk, hogy a mátrixnorma illeszkedik a vektornormához. Osztva ||v|| 6= 0-val, |λ| ≤ ||A|| adódik minden egyes sajátértékre. Akkor a legnagyobbra is teljesül, tehát való- ban r(A) ≤ ||A||. Dení ió. Kondí iószám: Az A mátrix kondí iószáma: κ(A) = ||A|| · ||A−1 || Nyilván függ a választott mátrixnormától. Ennek megfelel®en az kondí iószámát így jelöljük: A mátrix ||.||p normához tartozó κp (A) = ||A||p · ||A−1 ||p Megjegyzés. Adott az Ax = b egyenletrendszer, és perturbáljuk a jobboldalt: b megváltozik ⇒ x is megváltozik: b − b + ∆b x − x + ∆x  Ax = b A(x + ∆x) = b + ∆b Az A

együtthatómátrix annál jobban kondi ionált, minél inkább teljesül, hogy a b kis megváltozására x is sak ki sit változik meg. Ezt a normák relatív nagyságával mérjük: δx := ||∆x|| ||x|| δb := ||∆b|| ||b|| Állítás. Adott Ax = b egyenletrendszer esetén, ha ∃A−1 : 1 δb ≤ δx ≤ κ(A)δb κ(A) Biz.: Ax = b, A∆x = ∆b, x = A−1 b, ∆x = A−1 ∆b Ha ez igaz, akkor a normáikra is igaz: ||Ax|| = ||b||, ||A∆x|| = ||∆b||, ||x|| = ||A−1 b||, ||∆x|| = ||A−1 ∆b||. Vegyünk illeszked® normákat, vagyis: ||Ax|| ≤ ||A|| · ||x||. Akkor átrendezve: 1 ||∆b|| ||∆x|| ||A|| ||A−1 || · ||∆b|| ≤ ≤ ||b|| · ||A−1 || ||A|| ||x|| ||b|| 1 −1 vagyis tényleg függ (valami) ||A|| · ||A || értékét®l. Állítás. ∀A mátrixra: κ(A) ≥ 1 Biz.: I = A · A−1 , 1 = ||I|| = ||A · A−1 || ≤ ||A|| · ||A−1 || = κ(A) valóban Ezek szerint a mátrix kondí iószáma alulról korlátos, mi pedig azt szeretnénk, ha minél

kisebb lenne. Kérdés: elérhet®-e, hogy κ(A) = 1 legyen? Állítás. Unitér (valós esetben: ortogonális) mátrix kondí iószáma: κ2 (U ) = 1 Persze κ1 () és κ∞ () esetében ez nem feltétlenül teljesül. Állítás. A kondí iószám invariáns a konstanssal való szorzásra, vagyis: ∀λ ∈ R : κ(λA) = κ(A) 1 ||A−1 || = κ(A) Biz.: κ(λA) = ||λA|| · ||(λA)−1 || = |λ|||A|| · |λ| 20 2.2 A Bana h-féle xpont-tétel alkalmazása Az iterá iós módszerek lényege, hogy Ax = b, A ∈ R n×n , b ∈ Rn . Ezt átírjuk: x = M x + v, M ∈ Rn×n , v ∈ Rn ∗ Kérdés: létezik-e olyan (xk ) sorozat, melyre limk∞ xk létezik és véges. Ha igen, ezt jelöljük x -gal, és ∗ ∗ ∗ ekkor x = M x + v , azaz Ax = b. (Am ) : N Rn×n módon értelmezett sorozatot Dení ió. Mátrixsorozat: Kiegészítés [1℄ m¶véb®l mátrixsorozatnak nevezzük. Dení ió. Mátrixsorozat konvergen iája: Kiegészítés [1℄ m¶véb®l Az (Am ) sorozatot

konvergensnek nevezzük, ha (m) ∃A ∈ Rn×n : ∀i, k : aik aik Jelölés: (Am ) A Tétel. Kiegészítés [1℄ m¶véb®l (Am ) A Bizonyítás: ⇐⇒ (m ∞) ||Am − A|| 0 (m ∞) ⇐: Ha (Am ) A, akkor Bm := Am − A 0 (m ∞). Ha B elemeit bik -val jelöljük, akkor (m) (m) bik = aik − aik 0 (m ∞). Most |||| folytonos leképezés, így (m) ||Am − A|| = ||Bm || = Ψ(b11 , ., b(m) nn ) Ψ(0, ., 0) = 0 ⇒: Tegyük fel, hogy ||Am − A|| 0, de Am − A =: Bm 9 0. Akkor a Bolzano-Weierstrass-féle kiválasztási tétel miatt létezik olyan Bm1 , ., Bmp , monoton részsorozat, mely konvergens:
lim Bmp = B 6= 0 p∞ Ha B 6= 0, akkor ||B|| 6= 0 is. Ugyanakkor viszont ||Bmp || = ||Amp − A|| ||B|| = 0 is teljesül, amib®l a már bizonyított másik irány miatt B = 0, és ez ellentmondás. Állítás. Kiegészítés [1℄ m¶véb®l Ha (Am ) A és (Bm ) B konvergens mátrixsorozatok, akkor (m ∞): i) (Am + Bm ) A + B ii) (Am Bm ) AB iii) T

−1 AT T −1 AT Biz.: i) 0 ≤ ||Am + Bm − (A + B)|| = ||(Am − A) + (Bm − B)|| ≤ ||Am − A|| + ||Bm − B|| = 0 + 0 = 0 ii) 0 ≤ ||Am Bm − AB|| = ||Am (Bm − B) + B(Am − A)|| ≤ ||Am ||||Bm − B|| + ||B||||Am − A|| = 0 iii) 0 ≤ ||T −1 Am T || = ||T −1 (Am − A)T || ≤ ||T −1 ||||Am − A||||T || = 0 Tétel. Kiegészítés [1℄ m¶véb®l Az I + B + B 2 + + B m + mátrixsor akkor és sak akkor konvergens, ha r(B)<1, azaz a mátrix spektrálsugara 1-nél kisebb. Bizonyítás: El®bb segédtételeket látunk be. Segédtétel. Az I + B + + B m + mátrixsor akkor és sak akkor konvergens, ha B m 0, és ekkor I + B + B 2 + . + B m + = (I − B)−1 21 Biz.: Az egyik irányba rendben van, B m 0 szükséges feltétel A másik irányba: (I − B)(I + B + . + B m ) = I − B m+1 Most kihasználjuk azt a tényt (ami következménye az 1.6 fejezet végén bebizonyított tételnek), hogy a szigorúan diagonális domináns mátrix sosem lehet

szinguláris. Ennek felhasználásával ugyanis (lévén B m+1 0) I − B m+1 elég nagy m-re diagonálisan domináns lesz. szinguláris. Az iménti egyenlet felhasználásával: Akkor viszont I − B sem lehet I + B + . + B m = (I − B)−1 (I − B m+1 ) = (I − B)−1 − (I − B)−1 B m+1 0, így (I − B)−1 B m+1 0 is teljesül (m ∞), tehát a feltétel elégséges, és még a −1 bizonyítandó egyenl®ség is igaz lesz, mivel (I − B) − (I − B)−1 B m+1 m Segédtétel. Belátható, hogy B 0 akkor és sak akkor, ha B sajátértékei abszolút értékben kisebbek Mivel B m+1 1-nél. Biz.: Jordan-féle normálalak felhasználásával bizonyítunk Minden B mátrixhoz létezik ugyanis olyan −1 BT már Jordan-normálalakú. Itt J mátrix a J1 , , Jk rendre n1 × n1 , ., nk × nk -as Jordan-blokkokból áll, n1 + n2 + + nk = n Akkor viszont egyszer¶en az m-dik hatványra emelve: J m = T −1 B m T . Tehát B m sak akkor tarthat 0-hoz, ha J m 0 is

teljesül m Ha viszont J -t a J1 , ., Jk Jordan-blokkokból áll, akkor Ji 0, (i = 1, .k); m ∞ is szükséges Hatványozzuk a Ji Jordan-blokkot:  2  λi 2λi 1 0 ··· 0 0 0  0 λ2i 2λi 1 ··· 0 0 0     . . . . .  . . . . . . .   . . . . . . . .  Ji2 =   .  . . 2  . . λi 2λi 1     0 0 0 0 ··· 0 λ2i 2λi  0 0 0 0 ··· 0 0 λ2i nem szinguláris T mátrix, hogy J = T Általában pedig az m > ni -edik hatványra emelve:     Ji2 =   
. . . . . . 0 0 0 0 m 1
m m−2 2 λi
m m−1 1 λi . . . λm i λm−1 i m Innen pedig már látható, hogy Ji 0 λm i ··· ··· ··· . .   m λm−ni +1  ni −1  i m m−ni +2 ni −2 λi      .  .  . λm i sak akkor teljesül, ha |λi | < 1 minden i = 1, ., k esetén Tétel. Bana h-féle xpont-tétel Legyen X egy Bana h-tér, Φ : X X kontrak ió, azaz: ∀x, y ∈ X : ||Φ(x) − Φ(y)||

≤ K||x − y|| , ahol K < 1 Akkor teljesül, hogy: i) ∃!x∗ ∈ X : Φ(x∗ ) = x∗ ii) ∀x0 ∈ X : xk+1 := Φ(xk )-ra ∃ limk∞ (xk ) ∈ X , és ha x∗ := limk∞ (xk ), akkor x∗ xpontja Φ-nek. iii) ||xk+1 − x∗ || ≤ K1−K ||xj+1 − xj ||, k−j j = 0, 1, ., k 22 Megjegyzés. Hibafajták: Kk ||x1 − x0 || el®zetes hiba (a priori) 1−K K ||xk+1 − xk || utólagos hiba (a posteriori) j = k esetén: ||xk+1 − x∗ || ≤ 1−K Általában az a posteriori kisebb, mint az a priori, viszont ez sak k lépés végrehajtása után derül ki. j = 0 esetén: ||xk+1 − x∗ || ≤ Mindenesetre az a priori hibával (adott határ mellett) be sülhet® a szükséges iterá iók maximális száma. Alkalmazás. A Bana h-tételt alkalmazzuk spe iálisan X = Rn , Φ(x) = M x + v esetre Kérdés: mikor lesz kontrak ió a Φ leképezés? Kontrak ió akkor, ha: ||Φ(x) − Φ(y)|| = ||(M x + v) − (M y + v)|| = ||M (x − y)|| Keressünk egy illeszked®

mátrixnormát. Ha találunk ilyet, akkor: ||Φ(x) − Φ(y)|| = ||M (x − y)|| = ||M || · ||x − y|| Magyarul Φ akkor lesz kontrak ió, ha ||M || < 1 biztosítható (elégséges feltétel). Állítás. A Bana h-tételben szerepl® (xk ) sorozat konvergen iájának szükséges és elégséges feltétele, hogy r(M ) < 1 legyen (azaz az iterá iós mátrix spektrálsugara 1-nél kisebb legyen). Állítás. r(M ) ≤ ||M || teljesül Biz.: M xi = λi xi , i = 1, ., n, λi ∈ C az algebra alaptétele szerint |λi | · ||xi || = ||λi · xi || = ||M xi || ≤ ||M || · ||xi || /sajátvektor nem lehet nullvektor |λi | ≤ ||M || Állítás. r(M ) = inf{||M ||}, ahol |||| mátrixnorma Megjegyzés. Ha ez igaz (mint ahogyan az, de nem bizonyítjuk), akkor: alkalmas normaválasztással tetsz®legesen közel kerülhetünk r(M )-hez: ∀ε ∈ R : ∃||.||, hogy ||M || < r(M ) + ε Ha r(M ) ismert, és r(M ) < 1, akkor ε := 1 − r(M ) választással ∃||.|| : ||M ||

< 1, és a Bana h-féle xpont-tétel garantálja a konvergen iát. A konvergen ia független v és x0 választásától. Ismeretes a négyzetes mátrixon ún. S hur-felbontása: A = U RU ∗ , ahol U U ∗ = I unitér, és R fels®háromszög-mátrix. Ezt a Jordan-normálalak és a QR-felbontás segítségével láthatjuk be: A = XΛX −1, ahol Λ egy Jordan-blokk (???), mely viszont fels®háromszög-mátrix. Másrészt X -re alkal∗ mazva a QR-felbontást: QQ = I , akkor A = QRΛ(QR)−1 = Q(RΛR−1 )Q∗ ahol RΛR−1 fels®háromszög-mátrix lesz, Q pedig unitér mátrix. zonyítható a tétel. n Állítólag a S hur-felbontással bi- o Lemma. r(M ) = inf ||M k ||1/k |k ∈ N = lim ||M k ||1/k k∞ Tétel. r(M ) < 1 ⇐⇒ a sorozat konvergens Bizonyítás: ⇐: n = 1 esetén: xk+1 = mxk + v, x0 ∈ R és ∃x∗ = lim (xk ) : x3∗ = mx∗ + v . Vezessünk be egy ∗ hibasorozatot: ek := xk − x , amire k∞ lim ek = 0. Erre a hibasorozatra: k∞

ek+1 = xk+1 − x∗ = mxk + v − x∗ = (mxk + v) − (mx∗ + v) = m(xk − x∗ ) = mek Vagyis az iterá ió során a hibasorozat ek+1 = mek módon transzformálódik, így tosításához |m| < 1 szükséges. 23 lim ek = 0 biz- k∞ Ha n > 1, akkor a Jordan-felbontás szerint M = SΛS −1 , ahol S a sajátvektorokból álló mátrix, Λ pedig Jordan-normálalakú. Tegyük fel, hogy Λ ténylegesen diagonális Például ha M szimmetrikus, vagy a sajátértékei mind különböz®k, akkor ez teljesül is Most a felbontást behelyettesítve az iterá ióba: xk+1 = SΛS −1 xk + v / · S −1 balról S −1 xk+1 = ΛS −1 xk + S −1 v =: Λyk + w / yk+1 = Λyk + w (k+1) (k) ⇐⇒ y (k+1) = Λy (k) + w, ennek j -dik koordinátája: yj = λj yj + wj , ahol  λ1 0   . Λ= . Ez viszont már az 1 × 1-es eset, azzal pedig foglalkoztunk . 0 λn Ha viszont ez j = 1, ., n esetén konvergens, akkor ∀λj : |λj | < 1 ⇒ max{|λj |} < 1 ⇒ r(M )

< 1 ahol Λ diagonális  j ⇒: Ha r(M ) < 1, akkor ∃||.|| : r(M ) ≤ ||M || < 1 Ekkor M választással a Bana h-tétel garantálja a konvergen iát. Összefoglaló. 1) Ezek szerint feladatunk az Ax = b egyenletrensdszer megoldása. Ezt minden további nélkül átírhatjuk x = M x + v alakba, megfelel® M és v választás mellett. 2) Spe iálisan erre alkalmazva a Bana h-tételt, azt találjuk, hogy ha M mátrix megfelel®, akkor: i) Létezik olyan (xk ) sorozat, melynek határértéke az eredeti egyenlet megoldása ii) A megoldás egyértelm¶ iii) A konvergen ia sebessége be sülhet® 3) M mátrix pontosan akkor megfelel®, ha spektrálsugara kisebb, mint 1. 4) Mivel a spektrálsugár a normák inmuma, így ∀ε > 0-ra létezik olyan norma, hogy ||M || − r(M ) < ε, vagyis valóban elég, ha a spektrálsugár kerül 1 alá, utána már sak rajtunk múlik, megtaláljuk-e a megfelel® mátrixnormát. Akkor már sak alkalmas x = M x + v

átírást kell találnunk. Erre nézve 2 lényegesen eltér® stratégia lehetséges. Közös vonásuk, hogy a következ® felbontáson alapulnak: A=L+D+U ahol    aij ha i = j dij : dij = 0 különben    aij ha i > j L = lij : lij = 0 különben D = diag(A) = Most A := S − T , akkor Sx = T x + b / · S −1 s = S −1 T x + S −1 b Azaz: M = S −1 T és v = S −1 b 24 2.3 Ja obi módszer Megjegyzés. A=S −T akkor S := D (D + L + U )x = b Azaz: M := MJac := −D −1 − Dx = x = −(L + U )x + b −D−1 (L + U )x + D−1 b (L + U ) és vJac := D−1 b Állítás. A Ja obi iterá ió konvergen iájának elégséges feltétele, hogy a kiindulási A mátrix (sorirányban) szigorúan diagonálisan domináns legyen Biz.: MJac sornormája kisebb, mint 1: ( 0 aij − aii |mij | < 1 ⇐⇒ mij = X j ha i = j ha i 6= j X i6=j j=1 |aij | < |aii | Állítás. Az iménti állítás oszlopirányban deniált szigorú diagonális dominan ia

mellett is igaz Megjegyzés. Kiegészítés [1℄ m¶véb®l Az iterá iós formulából nyerjük (B := −D−1 (L + U ) és a := D−1 b választás mellett): x(m+1) = Bx(m) + a = B(Bx(m−1) + a) + a = . = B m+1 x(0) + (B m + B m−1 + + B + I)a (0) (m+1) Ha az x kezd®vektort történetesen a-nak választjuk, akkor x = (B m+1 +B m +B m−1 +.+B+I)a lesz, a jobboldalon álló mátrixsorozat pedig akkor és sak akkor konvergens (az iménti fejezet egyik tétele szerint), ha B valamennyi sajátértéke abszolútértékben egynél kisebb. 2.4 Gauss-Seidel módszer Megjegyzés. A=S −T akkor S := D + L (D + L + U )x = b − (D + L)x = x = −U x + b −(D + L)−1 U x + (D + L)−1 b −1 Azaz: M := MGS := −(D + L) U és vGS := (D + L)−1 b Állítás. A Gauss-Seidel iterá ió konvergen iájának elégséges feltétele, hogy a kiindulási A mátrix (sorirányban vagy oszlopirányban) szigorúan diagonálisan domináns legyen. 2.5 Ri hardson iterá ió Megjegyzés. A

Ri hardson-iterá ió kizárólag szimmetrikus pozitív denit mátrixokra használható. Ax (pA)x Ix + (pA)x x = = = = b pb Ix + pb (I − pA)x + pb / / ·p > 0, p ∈ R +x = Ix Abban bízunk, hogy találunk olyan p > 0 valós számot, melyre r(I − pA) < 1 teljesül a spektrálsugárra. Kérdések: - egyáltalán milyen p értékekre lesz konvergens az iterá ió? 25 - létezik-e optimális p paraméter (amely mellett a leggyorsabb a konvergen ia)? Állítás. Ha λi (p) jelöli az (I − pA) mátrix sajátértékeit, λi pedig az A mátrix sajátértékeit, akkor λi (p) = 1 − p · λi Biz.: A · si = λi si , ahol si az A mátrix sajátvektora Akkor: (1 − pA) · si = Isi − p(Asi ) = si − pλi si = si (1 − pλi ) Állítás. Ri hardson konvergens ⇐⇒ 0 < p < 2 r(A) Biz.: El®szöris az állítás nem tartalmaz ellentmondást, minthogy A szimmetrikus pozitív denit, így minden sajátértéke pozitív. Tegyük most fel, hogy λ1 ≥

λ2 ≥ . ≥ λn > 0 az A sajátértékei. Célunk: −1 < 1 − pλi < 1 , p>0 Ebb®l −1 < 1 − pλi pλi < 2 p< 2 λi ∀i = 1, ., n Akkor ez i = 1-re is teljesül, ami ebben az esetben pont r(A)-t jelenti. Tehát: 0 < p < Megjegyzés. A Bana h-féle xpont-tétel szerint: Lk ||x1 − x0 || 1−L ||xk − x∗ || ≤ aholis L := ||M ||. 2 r(A) Ugyanakkor tudjuk, hogy sokféle norma van - vegyük ezek inmumát, az r(M ) spektrálsugarat, hiszen létezik olyan norma, mely tetsz®legesen közel kerülhet r(M )-hez. Akkor viszont élszer¶ a konvergen ia sebességét a ||xk − x∗ || ≤ γ · r(M )k módon mérni, ahol γ valamilyen konstans. Állítás. A Ri hardson-iterá ió optimális p értéke: p= λ1 −1 λi − λn cond(M ) − 1 = λλn1 = λi + λn cond(M ) + 1 λ +1 n Biz.: Jelöljük M(p) -vel az I − pA mátrixot Ennek sajátértékei: 1 − pλi , vagyis spektrálsugara: r(M(p) ) = max |1 − pλi | 1≤i≤n Nyilván

max |1 − pλi | értéke 1≤i≤n sak |1 − pλ1 | és |1 − pλn | értékét®l függ. Továbbá (tekintettel az ab- szolútértékre) akkor járunk a legjobban, ha a 0-t megpróbáljuk a két érték közé, középre elhelyezni. Vagyis: 1 − pλ1 = −(1 − pλn ) ⇐⇒ p := popt = 2 λ1 + λn A bizonyítandó álítás többi része azonos átalakítással megy, gyelembe véve, hogy a pozitív denit mátrix kondí iószáma éppen a legnagyobb és a legkisebb sajátértékének a hányadosa (és a hányados létezik és pozitív, mert a pozitív szemidenit mátrix minden sajátértéke pozitív). 26 2.6 A Ja obi és a Gauss-Seidel iterá ió kap solata Állítás. A Ja obi iterá ió lényegében a következ® (3 × 3-as mátrixon szemléltetve): (k+1) Ax = b − a11 x1 (k) a21 x1 (k) a31 x1 + + + (k) a12 x2 (k+1) a22 x2 (k) a32 x2 + + + (k) a13 x3 (k) a23 x3 (k+1) a33 x3 = b1 = b2 = b3 (k+1) vagyis: Dx + (L + U )x(k) = b Állítás. A

Gauss-Seidel iterá ió lényegében a következ® (3 × 3-as mátrixon szemléltetve): (k+1) Ax = b − a11 x1 (k+1) a21 x1 (k+1) a31 x1 + + + (k) a12 x2 (k+1) a22 x2 (k+1) a32 x2 + + + (k) a13 x3 (k) a23 x3 (k+1) a33 x3 = b1 = b2 = b3 (k+1) vagyis: (D + L)x + U x(k) = b Állítás. Mindkét iterá ió magadható koordinátánkénti alakban is (még sak invertálni sem kell):  Ja : bi −  G-S: bi −  X 1 (k) aij xj  · , 1 ≤ i≤ n aii X X j6=i (k+1) aij xj j<i −  1 (k) aij xj  · , 1 ≤ i≤ n aii j>i 2.7 Relaxá iós módszerek Probléma. Tegyük fel, hogy sem a Ja obi, sem a Gauss-Seidel iterá ió sem konvergens Akkor be kell vezetnünk az iteráviós mátrix valamiféle módosítását. Ja : Dx(k+1) = −(L + U )x(k) + b ·ω Dx(k+1) = Dx(k) / sta ionárius iterá ió, ·(1 − ω) Dx(k+1) = ((1 − ω)D − ω(L + U ))x(k) + ωb / · D−1 x(k+1) = ((1 − ω)I − ωD−1 (L + U ))x(k) + ωD−1 b MJac (ω) :=

((1 − ω)I − ωD−1 (L + U )) bJac (ω) := ωD−1 G-S: (D + L)x(k+1) = −U x(k) + b ·ω Dx(k+1) = Dx(k) / sta ionárius iterá ió, ·(1 − ω) (D + ωL)x(k+1) = ((1 − ω)D − ωU )x(k) + ωb / · D−1 x(k+1) = (D + ωL)−1 ((1 − ω)D − ωU )x(k) + ω(D + ωL)(−1) b MG−S (ω) := . bG−S (ω) := . Ilyenkor egyébként MJac (1) = MJac teljesül, vagyis ω = 1 nem jelent változást az eredeti Ja obi iterá ióhoz képest. Állítás. Ha az eredeti Ja obi iterá ió konvergens, akkor a relaxált iterá ió is konvergens Biz.: Jelöljük most a relaxálatlan mátrix sajátértékeit λi -vel 27 Az eredeti iterá ió konvergens, tehát |λi | < 1, 1 ≤ i ≤ n. Jelöljük a relaxált mátrix sajátértékeit λi (MJac )-kal Akkor λi = λi (MJac ) Az eredeti iterá ió konvergens, tehát: |λi (MJac (ω))| ≤ |1 − ω| + |ω||λi | < |1 − ω| + |ω| Tétel. Ha a relaxált G-S konvergens, akkor az eredeti is az Tétel. Ha A szimmetrikus

pozitív denit, akkor ∀0 < ω < 2 esetén a relaxált G-S konvergens lesz Emlékeztet®. Ha λi = λi (A), 1 ≤ i ≤ n, akkor: i) Prni=1 λi = det A ii) Pn i=1 = tr A = Pn i=1 aii , a mátrix nyoma 2.8 Gradiens-módszer A gradiens-módszer szintén iteratív eljárás. Ax = b, x =? kérdésre keressük továbbra is a választ. Keresünk mindehhez egy ϕ : Rn R leképezést, majd a ϕ min Itt f : R n ⇔ f = 0 feladatot kapjuk, ahol f (x) = Ax − b Rn leképezés. Ha Ax∗ = b, ϕ(x∗ ≤ ϕ(x)), akkor: f := ϕ′ és f ϕ := f 2 ≥ 0 mindenhol 2 minimuma jó helyen van. −1 Most n ≥ 1 esetén ha adott egy f (x) = Ax − b és ∃A , akkor lehetne ϕ(x) helyett az ||Ax − b||22 = X (Ax − b)2i = (Ax − b)T (Ax − b) T T Ennek f®tagja: x A Ax. Kifejezve az utolsó szorzatot: (Ax − b)T (Ax − b) = xT AT Ax − bT Ax − (Ax)T b + bT b Ha még A mátrix szimmetrikus pozitív denit, akkor a két közbüls® összeadandó egyenl® is.

ÉrdekességT −1 képp tudjuk ám még azt is, hogy A A pozitív szemidenit minden A mátrix esetén, ha viszont ∃A , T akkor ráadásul pozitív denit is. Ennek megfeléel®en (egy kisebb logikai ugrással) itt A A mátrixot jelölhetjük akár A-val is, és feltehetjük, hogy szimmetrikus pozitív denit, ha ugyanis nem ilyen volna, akkor könnyen ilyen alakra tudnánk hozni, és ugyanott tartanánk. Akkor viszont: ϕ(x) =  1 T 1 x Ax − bT x + bT A−1 b 2 2 ϕ′ (x) = Ax − (bT x)′ + 0 = Ax − b ′ 1 T x Ax = Ax 2 /′ (Ax − b)′ = A (szimmetrikus pozitív denit) Geometriai interpretá ió Ha xk -ban vagyunk, akkor ϕ′ (xk ) irányában n® a legmeredekebben a ϕ függvény, tehát −ϕ(xk ) irányban steepest des ent). söken a leginkább ( xk+1 = xk − αk · rk 28 ′ + ahol rk = Axk − b, hiszen pont ϕ (x) = Ax − b volt korábban, és αk ∈ R . Kérdés: mekkora xk ? A gradiens irányában elmetszve a teret, parabolát kapunk, annak

meg ismerjük a minimumát. Ψ(α) = ϕ(xk − α · rk ) : RR 1 1 (xk − αrk )T A(xk − αrk ) − bT (xk − αrk ) + bT A−1 b = 2 2 ez α-ra másodfokú polinom: Ψ ∈ P [α]   1 T 1 T 2 T T /′ = rk Ark · α − (rk Axk + xk Ark ) − b rk + konstans 2 2 Ψ(α) = rkT Ark · α = xTk Ark − bT rk = (xTk A − bT )rk = (Axk − rk )T rk = rkT rk = ||rk ||22 hiszen: T A = AT miatt xTk A = (AT xTk )T = (Axk )T Akkor végül: α =: αk = rkT rk >0 rkT Ark T T ahol rk rk = rk Irk , és I szimmetrikus pozitív denit mátrix. Ennek megfelel®en a gradiens-módszer: xk+1 = xk − rkT rk rk rkT Ark Dení ió. Rayleigh-hányados: A pozitív denit mátrix Akkor a Rayleigh-hányados: xT Ax xT x Lemma. ϕ(xk+1 ) ≤ ϕ(xk ) − 1 ||rk ||4 · , vagyis a (xk ) sorozat sökken, de nem biztos, hogy a 0-hoz tart. 2 rkT Ark Állítás. Ha 0 < m ≤ αi ≤ M < +∞, akkor amib®l következik a konvergen ia.   m ϕ(xk ) ϕ(xk+1 ) ≤ 1 − M Állítás. A

tétel nomítható Kantorovi s egyenl®tlenségével: ha A pozitív denit, akkor rT Ar · rT A−1 r ≤ m+M ||r||4 4mM 1 T −1 b A b tagra: 2 1 1 1 ϕ(x) = xT Ax − bT x + bT A−1 b = rT A−1 r 2 2 2 Állítás. A korábban elhangzott ahol r = Ax − b Hivatkozások [1℄ Móri z, Feren , Numerikus Analízis II. - Kézirat, Nemzeti Tankönyvkiadó, Budapest, 1999 Nagy lineáris rendszerek, M¶szaki Könyvkiadó, Budapest, 1979; eredeti m¶: Iterative Solution of Large Linear Systems, A ademi Press, New York, 1971 [2℄ Young, D.M, 29