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 LU 1 1.1 Gauss-eliminá ió, felbontás . 2 1.2 Gauss-Jordan eliminá ió, m¶veletigény, invertálás . 4 1.3 Egziszten ia és uni itás 1.4 Tridiagonális mátrix . LU -felbontása, 5 Cholesky-faktorizá ió . 5 7 1.5 Invariáns

tulajdonságok, S hur-komplementer . 1.6 Diagonális dominan ia, irredu ibilitás 1.7 Ortogonális-trianguláris (QR) felbontás . 9 . 13 2. Iterá iós módszerek 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 1. . Lineáris egyenletrendszerek direkt megoldása Megjegyzés. −1 Cél: Ax = b megoldása, ahol A ∈ Rn×n , b ∈ Rn , x ∈ Rn . ∃A ⇔

|A| 6= 0, ∃A−1 ⇔ {az Ax = 0-nak sak x = 0 a megoldása}, ∃A−1 ⇔ {A-nak nin s 0 ∈ C sajátértéke}. és 1 1.1 Gauss-eliminá ió, LU felbontás Megjegyzés. LU felbontást próbálgatjuk el®ször. Ennek az a lényege, hogy A mátriU 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 Az ún. xot felbontjuk egy L és egy nevezett módszer pedig a következ®képp szemléltethet®:  0  0 0 (2) a22 6= 0 − tfh. (1) a11 6= 0 0 0 0  0 0 (3) a33 6= 0 − Egy másik interpretá ióban: a11 x1 + . = b1 − x1 = − 0 0 0 0 0 0  = U , mivel ∃A−1 , így (4) a44 6= 0 b1 − a12 x2 − . − a1n xn a11 2., , n sorhoz, így az els® oszlop (a11 kivételével) 0 (k) (2) a többi: A , ., A(n)

lesz, A(k) elemeit pedig aij -val Az els® sor alkalmas konstansszorosát hozzáadom a lesz. Jelöljük (1) A -gyel A-t (az eredeti mátrixot), (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 = Állítás. Biz.: (k) 0 teljesül-e: írjunk (k) aik − j helyett k -t. Akkor: (k) aik · akk (k) akk =0 A(1) − A(2) − . − A(n) = U lesz Kérdés: A(k+1) kifejezhet®-e A(k) -val? Állítás. Hogyne, méghozzá: A(k+1) = Lk (v(k) ) · A(k) Dení ió. Az iménti állításban szerepl® Lk (v(k) ) ∈ Rn×n mátrix az egységmátrixtól 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 . Így Dení ió. Az fogalmak felhasználásával jelöljük: L := {L ∈ Rn×n |lij = 0 : i < j} U := {U ∈ Rn×n |uij = 0 : i > j} L ⊃ L1 := {L ∈ L : alsóháromszög-mátrixok halmaza,

fels®háromszög-mátrixok halmaza, és a f®átlóban supa 1-esek vannak} Következmény. Lk (v ) alsóháromszög-mátrix, a f®átlóban egyesekkel: Állítás. Belátható, hogy: (k) i) L′ , L′′ ∈ L =⇒ L′ · L′′ ∈ L Lk (v (k) ) ∈ L1 . 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. T Reprezentá ió: Lk (v) = I + vek , ahol ek a k -dik egységvektor. Nyilván ebben a diádban T (vek )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ó. Li (v)Lj (v), i 6= j Az 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 i) Li (u) · Lj (v) szépen szorozható, és egy ilyen mátrix inverze is szép: szépen szorozható, és ii) Li (u)−1 = Li (−u) Példa. Vegyünk két ilyen mátrixot, és szorozzuk össze ®ket:  Megjegyzés. 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     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 = A(n) = Ln−1 Ln−2 · · · L1 A −1 Ln−1
U = Ln−2 · · · L1 A −1 −1 L−1 L · · · L = A n−1 U
1 2 −1 −1 −1 Akkor L1 L2 · · · Ln−1 =: L. Itt a korábbi lemmáknak

köszönhet®en L = L1 (v (1) )−1 L2 (v (2) )−1 · · · Ln−1 (v (n−1) )−1 = L1 (−v (1) )L2 (−v (2) ) · · · Ln−1 (−v (n−1) ), melyek szépen 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! Emlékeztet®: Példa. (k+1) aij (k) = aij − (k) aik (k) akk (k) · akj , ahol a tört a szorzó. Akkor oldjunk meg egy feladatot:  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 =⇒ x keresése. Az utolsó   3 0 −2 7  0 1 1 4  0 0 1 1 Most jön   1 0 L= 2 1 −1 3   0 1 0 0  −  2 1 1 −1 3  3 0 −  0 1 0 0  0 0  = L1 · L2 1

(szépen szorzódik)  0 0  1  sort kapásból elosztom 4-gyel. utolsó sort  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 P ai b i , ennek megfelel®en 1 ag n(n + 1)(2n + 1) 6 T (G) = 13 n3 + O(n2 ) Á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) = 21 n3 + O(n2 ) n2 (n + 1) n(n + 1) = 2 2 rosszabb, mint a Gauss-eliminá ió m¶veletigénye. 4 Állítás. Mátrix inverzének kiszámolása: az In -nel Mindkét megközelítéssel kiszámolható indulunk:  1 ··· 0  AX = I ⇐⇒  . . . n×n . . . . . 0 . 1 1.3 Egziszten ia és uni itás A−1 , supán b helyett    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 |AK | 6= 0 (K = 1, . , n − 1) Biz.: Persze ez részmátrixa: (k) ⇐⇒ akk = 0 AK := (aij )j=1.K i=1.K Akkor:

(k = 1, ., n − 1) sak elvi jelent®ség¶, hiszen a determináns kiszámolása lényegesen m¶veletigényesebb. mint az eliminá ió. Háromszögmátrixokról lévén szó, könnyen látható, hogy |AK | = |LK | · |UK | = 1 · |UK | = |UK |, (1) |AK | = |AK−1 | = Tétel. Ha Bizonyítás: |AK | 6= 0, (K = 1, ., n), LK AK = LK · UK . Most 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: mivel f®átlója (k) a11 · · · akk (1) (k−1) a11 · · · a(k−1)(k−1) ) =⇒ |AK | (k) = akk |AK−1 | akkor az egziszten ia és uni itás egyaránt igaz. 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 Ezért |L1 |, |U1 |, |L2 |, |U2 | 6= −1 −1 −1 0, így ∃L−1 1 , 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® amib®l L 1 = L 2 , U1 = U2 sak az egységmátrix lehet, következik. 1.4 Tridiagonális mátrix LU -felbontása, Cholesky-faktorizá ió y(a) =: ya és y(b) =: yb rögzített konstansok, a = x0 < x1 < . < xn = b egy ekvidisztans felosztás: xi+1 − xi = h = Legyenek b−a n . Közelítjük a második deriváltat: ′′ y (xi ) = Vezessük be az  y(xi+1 ) − y(xi ) y(xi ) − y(xi−1 ) − h h yi := y(xi ) jelölést. Akkor most  · 1 y(xi+1 ) − 2y(xi ) + y(xi−1 ) = ≈ f (xi ) h h2 yi+1 − 2yi + yi−1 = h2 f (xi ), 5 1 ≤ i ≤ n − 1. y0 − 2y1 y1 + − y2 2y2 + = = y3 . [a, b] / · (−1) . . . . yn−2 Megjegyzés. h2 f (x1 ) h2 f (x2 ) − 2yn−1 + yn = h2 f (xn ) Próbáljuk meg alkalmazni az eddig tanultakat. Tegyük fel, hogy az y ′′ (x) = f (x), egyenletet szeretnénk megoldani.        −1  2

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

   y0 0 0 . . . yn        =     supán az, hogy itt a baloldali mátrixnak létezik-e inverze. tridiag(−1, 2, −1) ∈ R(n−1)×(n−1)  −h2 f (x1 ) + ya −h2 f (x2 ) −h2 f (x3 ) . . . −h2 f (xn−1 ) + yb        A baloldali mátrixra ezentúl jelöléssel hivatkozunk. Determinánsa (teljes induk ióval igazolható): |tridiag(−1, 2, −1)| = (1 · 1 · 1 · · · 1) ·  2 3 n+1 · ··· 1 2 n  = n + 1 > 0, 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 ∃A = LU = LDU felbontás, akkor 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 . ii) Ha A = AT Az uni itás tétele miatt szimmetrikus és pozitív denit, akkor D-re L = UT és U = LT teljesül, hogy teljesül. ∀i = 1, ., n : dii > 0 Ezt inkább nem bizonyítjuk. Megjegyzés. Ha A szimmetrikus pozitív denit, akkor is pozitív denit, azaz minden f®átlóbeli eleme pozitív. √ √ D = ( dii )ni=1 . Akkor viszont: amennyiben A = LDLT √ √ √ √ A = LDU = L D DU = (L D)( DU ) 6 felbontás létezik, és benne Akkor viszont D = √ √ 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 Biz.: Cholesky-felbontása sak szimmetrikus mátrixnak létezhet. AT = (LLT )T = LT L = LLT = A Ugyanis: Á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 · 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 LT alakban írható, ahol pozitív denit mátrix egy partí ióját:  Minthogy An An =  An−1 b T ann b   szimmetrikus pozitív denit, így szükségképpen An−1 is az. Ln−1 LTn−1 = An−1 . Most Ezért létezik olyan Ln−1 megfelel®

alsóháromszög-mátrix, melyre (det Ln−1 )2 = det An−1 6= 0 ⇒ Ln−1 nem szinguláris Ln−1 x = b egyenletrendszer megoldható, tegyük is fel, hogy 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 megoldása, Ezek szerint ann = cT c + x2 megadja x értékét. A kérdés ennek c ∈ Rn−1 sak az: mindig valós lesz-e x? egy Ha most vesszük az iménti egyenlet bal- és jobboldalának determinánsát, akkor: det   Ln−1 Ebb®l akkor c T 0 x x2 > 0   · LTn−1 c 0 x    = (det Ln−1 )2 x2 = det An = det  is következik, tehát megfelel® választással elérhet®, hogy Megjegyzés. Kiegészítés [1℄ m¶véb®l Ha az A b An−1 b T T 2 c c+x x > 0, x ∈ R  >0 legyen. mátrix szimmetrikus ugyan, de nem pozitív denit, akkor a Cholesky-felbontás nem

feltétlenül lehetséges. Pl: A= Megjegyzés. Kiegészítés [1℄ m¶véb®l  0 1 1 0  Valós, nem szinguláris L alsóháromszög-mátrix esetén 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 LLT i) ii) Szimmetrikus mátrix esetén az eliminá ió munkamátrixa mindvégig szimmetrikus marad Szimmetrikus pozitív denit mátrix esetén az eliminá ió munkamátrixa mindvégig szimmetrikus pozitív denit marad Biz.: (1) (1) i) Az els® lépést elvégezve: (2) (1) aij = 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 bizonyítjuk. Emlékeztet®. LU egziszten iájának feltétele,

hogy Ugyanakkor elképzelhet®, hogy pl. a11 = 0 A ∀x 6= 0 : xT Ax > 0. |AK | 6= 0 mátrix esetében ez minden Az állítást viszont nem K = 1, ., n esetére teljesüljön. sak a sorok megfelel® átrendezésével teljesülne, 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= partí ióját, ahol A11  A mátrix egy olyan A12 A22 A11 A21  , 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 A21 A11 ∈ Rk×k , A22 ∈ R(n−k)×(n−k) . A12 A22 x1 -et az inverzzel: x1 x2  =  b1 b2 + + A12 x2 A22 x2 , x1 = A−1 11 (b1 − A12 y2 ), = b1 = b2 amit behelyettesítve a második egyenletbe: A21 (A−1 11 (b1 − A12 x2 )) + A22 x2 = b2 (A22 − Dení ió. S hur-komplementer:  Kibontva: A11 x1

A21 x1 Kiküszöböljük  A21 A−1 11 A12 )x2 /kif ejezzk : = b2 − A12 A−1 11 b1 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: Megjegyzés. A/A11 = A22 − A21 A−1 11 A12 A jelölés oka: |A| = Állítás. Ha A A11 A21 A12 A22 = A11 0 A12 A/A11 |A| = |A/A11 | |A11 | szimmetrikus pozitív denit, akkor Biz.: A/A11 = A22 − A21 A−1 11 A12 valóban. A/A11 8 = |A11 | · |A/A11 | is az. Szimmetria: A = AT ⇔ A11 = AT11 és −1 akkor A11 is az, és: szimetrikus, akkor Poz.def: A22 = AT22 , A12 = AT21 .Ha A11 valamint szimmetrikus és invertálható, −1 T T −1 T T (A21 A−1 11 A12 ) = A21 (A21 ) A21 = A21 A11 A12 A/A11 is szimmetrikus kell, hogy legyen. A poz. def, akkor A11 és A22 ∀x2 ∈ Rn−k , x2 6= 0 : xT2 Ax2 > 0 A11 x1 + A12 x2 = 0 Ha is az. legyen. ∀x ∈ Rn , x 6= 0 : xT Ax > 0. Akkor

kellene, hogy Adott x2 -höz választhatunk alkalmas x1 -et, melyre 1.6 Diagonális dominan ia, irredu ibilitás Dení ió. Diagonális dominan ia: i) ii) A ∈ Rn×n szigorúan diagonálisan domináns, ha mátrix ∀i = 1, ., n : |aii | > gyengén diagonálisan domináns, ha általában {1, 2, ., n}, Megjegyzés. sak ahol szigorúan teljesül az egyenl®tlenség. n X j6=i j=1 ≥-re |aij | teljesül, de létezik legalább egy i ∈ Az iménti dení ió sorirányban deniálja a diagonális dominan iát. Lehet oszlopirány- ban 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. A(1) := A. Akkor az új A(2) mátrix elemei: Biz.: (2) aij = aij − Elég [a11 aij − ai1 a1j ]ni,j=2 ai1 a1j a11 aij − ai1 a1j = , a11 a11 mátrixra belátni a diagonális dominan iát: |a11 aij − ai1 a1j | > Állítás. Ha A i, j = 1, ., n X j=1

j6=i |a11 aij − ai1 a1j | 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=   Vizsgáljuk az Ax = d  b1 a2 . . . . . . cn−1 bn−1 an  1     l1 =     0 0 . . . . . . ln−1 1       ·     u1 u2 0 egyenletrendszert: ci−1 ai bi = li−1 1 9 0 · ui−1 0 0 vi−1 ui 0 0 vi ui+1  v1 . . . . vn−1 un      Nyilván   ci−1 ⇒ ai  bi a1 = u1 , b1 = v1 . Mivel Induk ióval okoskodunk: Tegyük fel, hogy |ui | > |vi |,  li−1 ui−1  li−1

vi−1 + ui  vi = = =   és  |a1 | > |b1 | ⇒ |u1 | > |v1 |. ci ai+1 bi+1  = li u i  = li vi + ui+1  = vi+1 Kell, hogy |ui | > |vi | teljesüljön (i = 1, ., n) 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, Például a tridiagonális mátrix Megjegyzés. (1, 1) i<j+k ha vagy i>j−l típusú sávmátrix. 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: megoldására jó. Akkor az i-edik  sor: a1   c1    Tridiagonális mátrixszal reprezentálható egyenletrendszer      x1 d1    d2  

 x2    · .  =  .    .   .   . .  xn dn b1 a2 . . . . . . cn−1 ci−1 ai bn−1 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 = fi ai + ci−1 fi−1 és di − ci gi−1 = gi ai + ci−1 fi−1 xi = fi xi+1 + gi 10 / Így a megoldás során a, b, c vektorunk van, visszafele haladva. Következmény: O(n) f -et rekurzióval (el®re haladva) kiszámoljuk, utána g -t 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 és T n = 1, vagy n>1 és a W = {1, 2, ., n} halmaz bármely két nemüres diszjunkt S i ∈ S és j ∈ T , hogy aij 6= 0. Ha A nem irredu ibilis, részhalmazra bontása esetén létezik olyan redu ibilisnek akkor 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 pij = 1 ⇔ σ : {1, ., n} {1, , n} bijek iót úgy, hogy σ(i) = j Algebrából tudjuk, hogy a permutá iók invertálhatók. Könnyen látható, hogy P permutálómátrix in- verzére egyszer¶en: P −1 =

P T Állítás. Kiegészítés [2℄ m¶véb®l P Az A mátrix akkor és permutálómátrix, amellyel P −1 AP =  sak akkor irredu ibilis, ha NEM létezik olyan F 0 G H  F és H négyzetes mátrixok. 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 alakú, melyben Biz.: Tfh. permutálómátrix nem létezik. redu ibilis, akkor van ilyen permutálómátrix. Ekkor létezik ugyanis olyan W = S + T ∀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 Ha viszont A partí ió, ahol aii1 ai1 2i2 · · · ais j 6= 0 Biz.: S + T = W partí ió mellett i ∈ S , j ∈ T mellett aij 6= 0 vagy létezik i1 , ., is aii1 ai1 i2 · · · ais j 6= 0, akkor az el®bbi esetben közvetlenül látszik, hogy A irredu ibilis Ha tetsz®leges sorozat, melyre (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ó. irredu ibilis, és n > 1, akkor ∀i = 1, ., n esetén Xi halmaz álljon azokból a számokból, melyekre 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. Ha A vagy 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. 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önbö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: Tfh. ui = n X bij uj i = 1, ., n j=1 ahol bii = 0, és bij = − aij aii ha i 6= j . A gyenge diagonális dominan ia dení iója és felhasználásával adódik, hogy minden n X j=1 Legyen |bij | = M := max |ui |. i n X i=1 Most miatt n X i=1 M >M· n X j=1 |bij | = n X j=1 |uj | ≤ M |aii | =1 aii és ∃i : Nyilván ∃k : uk = M . n X bkj uj ≤ n X j=1 |bij |M , j=1 |uj | = M ≤ M > 0. n X következik. Ugyanakkor |aij | |aii | M = |uk | = Akkor egyrészt ezen képletének i-re: aij − = aii u 6= 0 bij másrészt j=1 M≤ n X j=1 |bij | < 1 Ekkor |bkj ||uj | X j = 1n |bkj ||uj |, amib®l |bkj |(|uj | − M ) is igaz, ami azt jelenti,

hogy valahányszor |bij | 6= 0, mindannyiszor is teljesül, másképp az összeg negatív lenne. Ugyanakkor A irredu ibilis, vagyis az iménti állítás j 6= k esetén vagy akj 6= 0, vagy létezik olyan i1 , ., is bkj = 6 0, vagy bki1 , ., bis j 6= 0 Mindkét esetben |uj | = M aki1 · · · ais j 6= 0. szerint minden sorozat, hogy Tehát vagy adódik. Ez viszont azt jelenti, hogy ∀i = 1, ., n : Másrészt ha i∗ ∈ {1, ., n} u=0 6= 0. ami ellentmondás. Tehát a megoldása, így detA olyan, hogy n X j=1 lehet |bij | < 1, |uj | = M akkor M = |ui∗ | ≤ n X |bi∗ j |M 1≤ n X |bi∗ j | j=1 j=1 / sak, amib®l következik, hogy az 12 Au = 0 egyenletnek 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 Reméljük, hogy az ortogonális mátrix n n2 /2-vel sökken. 2 sor sor ⊥∀ ⊥∀ sor oszlop /2 paraméterrel

paraméterezhet®, ugyanis R trianguláris mátrix, így a szabadságfok Gram-S hmidt ortogonalizá iós eljárás. zik. Adott egy (xi )ni=1 (xi )ni=1 (yi )ni=1 − LF y1 , ., yn Ha k), azaz: már mer®legesek, akkor < yk , yi >= 0, tehát megoldható. A QR (zi )ni=1 −  zi := yi ||yi ||2 OG ON (ortogonális) (ortonormált) yk = xk + 1≤i≤k− k−1 X αi xi , i=1 1. Ez elvileg ahol k−1 α1 , ., αk−1  isperetlenek és yk ⊥ yi (i < ismeretlent és ugyanennyi egyenletet jelent, felbontás meghatározására két módszer van: Q−1 A = R 1.: Itt az eljárás a mátrix oszlopvektor-rendszerére vonatko- lineárisan független vektorrendszer. − 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. AR−1 = Q 2.: − 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) ii) Ja obi: 1 paraméteres Householder: n paraméteres Ja obi mátrix. Itt i 6= j , a f®átlóban az  (i, i)    Uij (ϕ) =    és (j, j)  1 c s . . s −c 1   ← i     ← 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 v = 1. c s s −c  c s s −c  =  1 0 0 1  H = H(v) = I − 2vv T , 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 2 ||v|| v v , ahol v 6= 0 A = [a1 , ., an ] oszlopvektor-partí iója, akkor ak = A·ek alakban írható, ahol ek a k -dik egységvektor 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: Ha Most H(v)a = t · e1 Tudjuk, hogy invarian ia): A v |t| = ||a||, ugyanis ha Q ortogonális mátrix, a pedig tetsz®leges vektor, akkor (unitér ||Qa||2 = (Qa)T (Qa) = aT QT Qa = aT (QT Q)a = aT a = ||a||2 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 || a − te1 , 2v T a esetén v = vagy: t = ±||a|| a − te1 , ||a − te1 || mert n=2:  a −b b a  2. U ortogonális, A 2 × 2-es Ellen®rzésképp: ortogonális mártixok általános alakja a , majd osszunk le a

normával: Ez utóbbi már valós ortonormált mátrix. Általában: ha kell, hogy teljesüljön. valóban megfelel®. Ortogonális mátrixok általános alakjáról. következ®: ||v|| = 1 1 U= √ 2 a + b2  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 akkor is az. U −U Iterá iós módszerek Az iterá iós módszerek lényege (szemben a direkt módszerekkel), hogy: Ax = b ahol M és t.fh ∃A−1 ⇐⇒ x = Mx + v elég ki si. 14 átírással: x0 ∈ Rn , xk+1 = M xk + v 2.1 Vektornormák és mátrixnormák Dení ió. Vektornorma: Legyen x ∈ Rn . Akkor i) ||x|| ≥ 0 és ||x|| = 0 ⇔ x = 0 ||.|| norma, ha ||.|| : Rn R leképezés, melyre: 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: i=1 ||x||1 = X |xi | ,

||x||2 = qX |xi |2 , p = 1, 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 Megjegyzés. 1/p  x2 xn + . + − |x1 |, = |x1 | 1 + x1 x1 p∞ i > 1. Egységgömbök R2 -ben: ||.||1 : , rombusz Állítás. Kiegészítés [1℄ m¶véb®l Mindenx i) ||x||∞ ≤ ||x||1 ≤ n · ||x||∞ ||.||2 : x ∈ Rn , kör ||.||∞ : négyzet vektorra: √ ii) ||x||∞ ≤ ||x||2 ≤ n · ||x||∞ √ iii) ||x||2 ≤ ||x||1 ≤ n · ||x||2 Biz.: iii) Tudjuk, hogy mely szerint ||x||2 = pP x2i ≤ P X Ennek felhasználásával,

spe iálisan √ n||x||2 . Megjegyzend®, hogy spe l®tlensége egyenl®ségra teljesül. Állítás. Kiegészítés [1℄ m¶véb®l Legyen |xi | = ||x||1 . |xi ||yi | ≤ Másrészt ismeretes a Cau hy-egyenl®tlenség, qX x2i qX yi2 pP P P x2 12 = y = (1, 1, ., 1)T választással: ||x||1 = |xi | ≤ T iálisan az e = (1, 1, ., 1) vektorra iii) állítás mindkét egyen|||| ϕ : Rn R tetsz®leges vektornorma. Akkor a : ϕ(x1 , ., xn ) := ||x|| 15 Rn -b®l R-be. x = (x1 , ., xn )T és x∗ = (x∗1 , , x∗n )T tetsz®leges vektorok X X x= xi ei és x∗ = x∗i ei függvény folytonos leképezés Biz.: Legyenek akkor Másrészt |ϕ(x1 , ., xn ) − ϕ(x∗1 , , x∗n )| = |||x|| − ||x∗ ||| ≤ ||x − x∗ || e1 , ., en bázis Rn -ben, Ugyanakkor X X (xi − x∗i )ei ≤ |xi − x∗i | · ||ei || ||x − x∗ || = Ezek szerint a Ha |ϕ(x1 , ., xn )−ϕ(x∗1 , , x∗n )| 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 vezzük, ha Megjegyzés. ||.||(1) és ||.||(2) normákat ekvivalenseknek ne- ∃m, M ∈ R : ∀x ∈ Rn : m||x||(1) ≤ ||x||(2) ≤ M ||x||(1) A dení ió jogos, a relá ió valóban ekvivalen ia. szimmetrikus és tranzitív. ||x||(2) ≤ M ||x||(1) , akkor A reexivitás az m = M = 1 Ugyanis: belátható, hogy reexív, (1) Ha most m||x|| ≤ választással adódik. 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 és m1 ||x||(1) ≤ ||x||(2) ≤ M1 ||x||(1) m2 ||x||(2) ≤ ||x||(3) ≤ M2 ||x||(2) 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ó. Rn -ben minden norma ekvivalens. n Most megmutatjuk, hogy tetsz®leges

R -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 - Állítás. Kiegészítés [1℄ m¶véb®l Biz.: ben, így a halmazt: Ekkor G ϕ(x1 , ., xn ) := ||x|| korlátos és zárt Rn -ben. folytonos tetsz®leges ||.|| norma esetén. Jelöljük G-vel G := {x ∈ Rn : ||x||2 = 1} Akkor viszont ϕ felveszi maximumát és minimumát a következ® 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∗ := m ≤ ϕ(x∗1 , ., x∗n ) = ||x∗ || ≤ M Viszont ||x∗ || = 1 1 ||x|| = ||x||, σ ||x||2 így aztán m||x||2 ≤ ||x|| ≤ M ||x||2 x = 0, x ∈ Rn esetén is fennáll, vagyis minden x ∈ Rn -re beláttuk. Mátrixnorma: Legyen A ∈ Rn×n , akkor ||.|| : Rn×n R

leképezés, melyre: Ugyanez az egyenl®tlenség Dení ió. 16 1 σx = 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) 2 A ∈ Rn×n − a ∈ Rn Kinyújtjuk a mátrixot: á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 3) sup. 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 ||Ax||1 = Legyen Lemma. ||A||1 mátrixnorma: n X n X i=1 j=1 K := maxj P i aij xj ≤ |aij |, ekkor XX i j |aij | · |xj | = j i X j |xj | X i |aij | ||Ax||1 ≤ K||x||1 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 P |aik | k oszlopnorma |aik | sornorma Biz.: Kiegészítés [1℄ m¶véb®l i) ||Ax||1 = i=1 k=1 ≤ Tehát n X n X 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 ||A||1 ||x||1 ≤ ||Ax||1 ≤ ||x||1 maxk Pn i=1 i=1 |aik | / : ||x||1 6= 0 ||A||1 ≤ max k 17 n X i=1 |aik | Másrészt ∃m ∈ N : 1 ≤ m ≤ n, melyre n X i=1 Ha most

em egységvektor, akkor |aim | = max k n X ||Aem ||1 = 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 Pn k=1 |aik |. Nyilván n X k=1 n X k=1 i ∃j ∈ {1, ., n} : ajk xk = k=1 |aik ||xk | ≤ |aik | = ||x||∞ max xT0 := (sgn(aj1 ), ., sgn(ajn )) ||Ax0 ||∞ ≥ n X 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 Másrészt xT (AT A)x = (xT AT )(Ax) = (Ax)T (Ax) = ||Ax||22 ≥ 0 pozitív denit is. Ismeretes, hogy

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ó Rn egy ortogonális bázisa - szimmetrikus pozitív denit mátrix sajátértékei nemnegatívok v1 , ., vn az AT 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 a most 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 α2k k=1 m=1 k=1 λ1 ||x||22 = k=1 √ ||A|| ≤ λ1 . Ugyanakkor x = v1 hiszen ||v1 || = 1 volt. Tehát esetén: ||Av1 ||22 = v1T (AT Av1 ) = v1T λ1 v1 = λ1 v1T v1 = λ1 ,

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 = Dení ió. ||.||M Az mátrixnorma illeszkedik a sX X i ||.||v j |aij |2 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 vektro- norma, mely a Frobenius-normát indukálná. Biz.: Belátható, hogy ||.||F illeszkedik indukált mátrixnorma, akkor ||In ||i = sup Dení ió. Spektrálsugár: Egy maximuma:  ||Ix|| , x 6= 0 ||x|| A ∈ Cn×n r(A) = max |λi (A)| i Megjegyzés. ||.||2 -höz  Ezt most nem látjuk be. = 1, de ||In ||F = √ n 6= 1, ha Ugyanakkor ha mátrix spektrálsugara a sajátértékek abszolútértékének a ahol

n {λi (A)}i=1 az A mátrix sajátértékei. mátrix spektrálsugara 0, normája viszont nem, hiszen nem a nullmátrixról van szó. A egy n>1 Nyilván az imént deniált spektrálsugár általában nem norma. Például Ugyanakkor ha ||.||i A=  0 0 1 0  mátrix szimmetrikus, akkor korábbi állításunk értelmében ||A||2 = Szimmetrikus mátrix esetén igaz, hogy maxi |λi (A)| = r(A). max λi (A). Ha még A q p r(AT A) = r(A2 )
2 λi (AT A) = λi (A2 ) = λi (A) , így a maximumra is: pozitív denit is, akkor a sajátértékei mind nemnegatívok, így 19 ||A||2 = ||A||2 = Állítás. Kiegészítés [1℄ m¶véb®l ||A||. Biz.: Legyen λ az A Minden egy sajátértéke, v ||.|| mátrixnormára és minden a hozzá tartozó sajátvektor. Ekkor A ∈ Rn×n mátrixra Av = λv , v 6= 0. r(A) ≤ 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|| r(A) ≤ ||A||. adódik minden egyes sajátértékre. Akkor a legnagyobbra is teljesül, tehát való- ban 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 A mátrix kondí iószámát így jelöljük: Megjegyzés. ||.||p κp (A) = ||A||p · ||A−1 ||p Adott az Ax = b egyenletrendszer, és perturbáljuk a jobboldalt: megváltozik: b − b + ∆b x − x + ∆x  A is sak ki sit változik meg. Ezt a normák relatív nagyságával mérjük: együtthatómátrix annál jobban kondi ionált, minél inkább teljesül, hogy a δx := Adott Ax = b b megváltozik ⇒x is Ax = b A(x + ∆x) = b + ∆b Az Állítás. normához tartozó ||∆x|| ||x|| egyenletrendszer esetén, ha δb := b kis megváltozására x ||∆b|| ||b|| ∃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: ||b||, ||A∆x|| = ||∆b||, ||x|| = ||A−1 b||, ||∆x|| = ||A−1 ∆b||. Vegyünk illeszked® normákat, vagyis: ||Ax|| ≤ ||A|| · ||x||. ||Ax|| = Akkor átrendezve: 1 ||∆b|| ||∆x|| ||A|| ||A−1 || · ||∆b|| ≤ ≤ ||b|| · ||A−1 || ||A|| ||x|| ||b|| 1 ||A|| · ||A−1 || é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) vagyis tényleg függ (valami) 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 Állítás. κ(A) = 1 legyen? 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: 1 −1 || = κ(A) |λ| ||A Biz.: κ(λA) =

||λA|| · ||(λA)−1 || = |λ|||A|| · 20 ∀λ ∈ R : κ(λA) = κ(A) κ∞ (.) 2.2 A Bana h-féle xpont-tétel alkalmazása Az iterá iós módszerek lényege, hogy Ax = b, A ∈ Rn×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 ∗ ∗ ∗ ekkor x = M x + v , azaz Ax = b. limk∞ xk Dení ió. Mátrixsorozat: Kiegészítés [1℄ m¶véb®l mátrixsorozatnak nevezzük. létezik és véges. Ha igen, ezt jelöljük (Am ) : N Rn×n Dení ió. Mátrixsorozat konvergen iája: Kiegészítés [1℄ m¶véb®l Az x∗ -gal, és módon értelmezett sorozatot (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 Bizonyítás: ⇐: Ha (Am ) A, akkor (m) (m) bik = aik − aik 0 (Am ) A ⇐⇒ (m ∞) ||Am − A|| 0 (m ∞) Bm := Am − A 0 (m ∞). Ha B elemeit bik -val (m ∞). Most ||||

folytonos leképezés, így jelöljük, akkor (m) ||Am − A|| = ||Bm || = Ψ(b11 , ., b(m) nn ) Ψ(0, ., 0) = 0 ⇒: Tegyük fel, hogy ||Am − A|| 0, kiválasztási tétel miatt létezik olyan Am − A =: Bm 9 0. Bm1 , ., Bmp , monoton
lim Bmp = B 6= 0 de Akkor a Bolzano-Weierstrass-féle részsorozat, mely konvergens: p∞ Ha B 6= 0, akkor ||B|| 6= 0 is. Ugyanakkor viszont amib®l a már bizonyított másik irány miatt Állítás. Kiegészítés [1℄ m¶véb®l (m ∞): Ha B = 0, (Am ) A és ||Bmp || = ||Amp − A|| ||B|| = 0 is teljesül, és ez ellentmondás. (Bm ) B konvergens mátrixsorozatok, akkor 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 ha r(B)<1, Bizonyítás: Az I + B + B 2 + . + B m + mátrixsor akkor és sak akkor konvergens, azaz a mátrix spektrálsugara 1-nél kisebb. El®bb segédtételeket látunk be. m Az I + B + . + B + . mátrixsor akkor és Segédtétel. sak akkor konvergens, ha I + B + B 2 + . + B m + = (I − B)−1 21 B m 0, és ekkor Biz.: Az egyik irányba rendben van, Bm 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. Akkor viszont szinguláris. Az iménti egyenlet felhasználásával: I−B sem lehet I + B + . + B m = (I − B)−1 (I − B m+1 ) = (I − B)−1 −

(I − B)−1 B m+1 (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 0, így 1-nél. Biz.: Jordan-féle normálalak felhasználásával bizonyítunk. Minden B mátrixhoz létezik ugyanis olyan T mátrix, hogy J = T −1 BT már Jordan-normálalakú. Itt J mátrix a J1 , , Jk rendre nem szinguláris 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 Általában pedig az m > ni -edik  λm  i   0 Ji2 =   . .  . 0 Innen pedig már látható, hogy hatványra emelve: m 1
Jim 0 Tétel. Bana h-féle xpont-tétel Legyen
··· . . . m m−2 2 λi
m m−1 1 λi . . . 0 0 ··· λm−1 i λm i ··· . .   m λm−ni +1  ni −1  i m m−ni +2 ni −2 λi . . . m λi        |λi | < 1 minden i = 1, ., k Φ : X X kontrak ió, azaz: sak akkor teljesül, ha X egy Bana h-tér, ∀x, y ∈ X : ||Φ(x) − Φ(y)|| ≤ K||x − y|| , ahol esetén. K<1 Akkor teljesül, hogy: i) ∃!x∗ ∈ X : Φ(x∗ ) = x∗ ii) ∀x0 ∈ X : xk+1 := Φ(xk )-ra ∃ limk∞ (xk ) ∈ X , Φ-nek. iii) ||xk+1 − x∗ || ≤ K k−j 1−K ||xj+1 − xj ||, j = 0, 1, ., k 22 és ha x∗ := limk∞ (xk ),

akkor x∗ xpontja Megjegyzés. j=0 esetén: j=k esetén: Hibafajták: Kk ||x1 − x0 || el®zetes hiba (a priori) 1−K K ||xk+1 − xk || utólagos hiba (a posteriori) ||xk+1 − x∗ || ≤ 1−K a posteriori kisebb, mint az a priori, viszont ez sak k lépés végrehajtása ||xk+1 − x∗ || ≤ Általában az Mindenesetre az Alkalmazás. a priori hibával (adott határ mellett) be után derül ki. sülhet® a szükséges iterá iók maximális száma. n A Bana h-tételt alkalmazzuk spe iálisan X = R , Φ(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 Állítás. hogy Φ akkor lesz kontrak ió, ha A Bana h-tételben szerepl® r(M ) < 1 Állítás. ||M || < 1 biztosítható (elégséges

feltétel). (xk ) sorozat konvergen iájának szükséges és elégséges feltétele, legyen (azaz az iterá iós mátrix spektrálsugara 1-nél kisebb legyen). r(M ) ≤ ||M || teljesül. i = 1, ., n, λi ∈ C Biz.: M xi = λi xi , 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 r(M )-hez: ∀ε ∈ R : ∃||.||, hogy ||M || < r(M ) + ε r(M ) < 1, akkor ε := 1 − r(M ) választással ∃||.|| : ||M || < 1, tetsz®legesen közel kerülhetünk Ha r(M ) ismert, és é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 UU∗ = 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 Q fels®háromszög-mátrix lesz, zonyítható a tétel. n pedig unitér mátrix. Á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: hibasorozatot: xk+1 = mxk + v, ∗ ek := xk − x x0 ∈ R , amire és ∃x∗ = lim (xk ) : x3∗ = mx∗ + v . lim ek = k∞ k∞ 0. Erre a hibasorozatra: Vezessünk be egy ek+1 = xk+1 − x∗ = mxk + v − x∗ = (mxk + v) − (mx∗ + v) = m(xk − x∗ ) = mek Vagyis az iterá ió során a hibasorozat tosításához |m| < 1 ek+1 = mek szükséges. 23 módon transzformálódik, így

lim ek = 0 k∞ biz- Ha n > 1, M = SΛS −1 , ahol S a sajátvektorokból álló mátrix, Λ hogy Λ ténylegesen diagonális. Például ha M szimmetri- akkor a Jordan-felbontás szerint pedig Jordan-normálalakú. Tegyük fel, kus, 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 xk+1 = ΛS −1 xk + S −1 / · S −1 balról v =: Λyk + w / yk+1 = Λyk + w (k+1) (k) Λ diagonális ⇐⇒ 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 j ⇒: Ha r(M ) < 1, akkor konvergen iát. ∃||.|| : r(M ) ≤ ||M || < 1 Ekkor M választással a Bana h-tétel garantálja a Összefoglaló. Ax = b 1)

Ezek szerint feladatunk az átírhatjuk x = Mx + v egyenletrensdszer megoldása. alakba, megfelel® M és v 2) Spe iálisan erre alkalmazva a Bana h-tételt, azt találjuk, hogy ha i) ii) iii) 3) M Létezik olyan (xk ) Ezt minden további nélkül választás mellett. M mátrix megfelel®, akkor: sorozat, melynek határértéke az eredeti egyenlet megoldása A megoldás egyértelm¶ A konvergen ia sebessége be sülhet® mátrix pontosan akkor megfelel®, ha spektrálsugara kisebb, mint 1. ∀ε > 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 4) Mivel a spektrálsugár a normák inmuma, így a megfelel® mátrixnormát. Akkor már sak alkalmas x = Mx + 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 (L + U ) Állítás. és − Dx = x = −(L + U )x + b −D−1 (L + U )x + D−1 b vJac := D−1 b A Ja obi iterá ió konvergen iájának elégséges feltétele, hogy a kiindulási A mátrix (sorirány- ban) szigorúan diagonálisan domináns legyen. Biz.: MJac sornormája kisebb, mint 1: mij = X j ( |mij | < 1 0 aij − aii ha ha i=j 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 D−1 b a := 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 Ha az x(0) kezd®vektort történetesen a-nak választjuk, akkor x(m+1) = (B m+1 +B m +B m−1 +.+B+I)a lesz, a jobboldalon álló mátrixsorozat pedig akkor és szerint), ha B sak akkor konvergens (az iménti fejezet egyik tétele 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 = Azaz: M := MGS := −(D + L)−1 U Állítás. és −U x + b −(D + L)−1 U x + (D + L)−1 b vGS := (D + L)−1 b 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 Abban bízunk, hogy találunk olyan = = = = p>0 b pb Ix

+ pb (I − pA)x + pb valós számot, melyre Kérdések: - egyáltalán milyen p / / r(I − pA) < 1 értékekre lesz konvergens az iterá ió? 25 ·p > 0, p ∈ R +x = Ix teljesül a spektrálsugárra. - létezik-e optimális Állítás. Ha λi (p) p paraméter (amely mellett a leggyorsabb a konvergen ia)? jelöli az (I − pA) λi mátrix sajátértékeit, 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. Biz.: Ri hardson konvergens ⇐⇒ 0 < p < 2 r(A) 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< Akkor

ez i = 1-re Megjegyzés. 2 λi ∀i = 1, ., n is teljesül, ami ebben az esetben pont jelenti. Tehát: 0<p< 2 r(A) A Bana h-féle xpont-tétel szerint: Lk ||x1 − x0 || 1−L ||xk − x∗ || ≤ aholis r(A)-t L := ||M ||. Ugyanakkor tudjuk, hogy sokféle norma van - vegyük ezek inmumát, az spektrálsugarat, hiszen létezik olyan norma, mely tetsz®legesen közel kerülhet r(M )-hez. r(M ) Akkor viszont élszer¶ a konvergen ia sebességét a ||xk − x∗ || ≤ γ · r(M )k módon mérni, ahol Állítás. γ valamilyen konstans. A Ri hardson-iterá ió optimális p= Biz.: Jelöljük M(p) -vel az I − pA p értéke: λi − λn = λi + λn λ1 λn λ1 λn −1 +1 = cond(M ) − 1 cond(M ) + 1 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 | 1≤i≤n értéke 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 (k+1) Ax = b vagyis: − a11 x1 (k) a21 x1 (k) a31 x1 mátrixon szemléltetve): (k) a12 x2 (k+1) a22 x2 (k) a32 x2 (k) + + + a13 x3 (k) a23 x3 (k+1) a33 x3 = b1 = b2 = b3 Dx(k+1) + (L + U )x(k) = b Állítás. A Gauss-Seidel iterá ió lényegében a következ® (3 (k+1) Ax = b vagyis: + + + × 3-as − a11 x1 (k+1) a21 x1 (k+1)

a31 x1 + + + × 3-as (k) a12 x2 (k+1) a22 x2 (k+1) a32 x2 + + + mátrixon szemléltetve): (k) a13 x3 (k) a23 x3 (k+1) a33 x3 = b1 = b2 = b3 (D + L)x(k+1) + U x(k) = b Állítás. Mindkét iterá ió magadható koordinátánkénti alakban is (még  Ja : bi −  G-S: bi − X j6=i X sak invertálni sem kell):  1 (k) aij xj  · , 1 ≤ i≤ n aii (k+1) aij xj j<i − X  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. Biz.: Ha az eredeti Ja obi iterá ió konvergens, akkor a relaxált iterá ió is konvergens. Jelöljük most a relaxálatlan mátrix sajátértékeit 27 λi -vel. 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 : Rn Rn leképezés. Ha ⇔ f =0 Ax∗ = b, ϕ(x∗ ≤ ϕ(x)), f := ϕ′ és f2 Most feladatot kapjuk, ahol f (x) = Ax − b akkor: ϕ := f 2 ≥ 0 mindenhol minimuma jó helyen van. n≥1 f (x) = Ax − b és ∃A−1 , akkor lehetne ϕ(x) X ||Ax − b||22 = (Ax − b)2i = (Ax − b)T (Ax − b) esetén ha adott egy Ennek f®tagja: xT AT Ax. helyett az Kifejezve az utolsó szorzatot: (Ax − b)T (Ax − b) = xT AT Ax − bT Ax − (Ax)T b + bT b A mátrix szimmetrikus pozitív denit, akkor a két közbüls® összeadandó egyenl® is. ÉrdekességAT A pozitív szemidenit minden A mátrix esetén, ha viszont ∃A−1 , 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, Ha még képp tudjuk ám még azt is, hogy akkor könnyen ilyen alakra tudnánk hozni, és ugyanott tartanánk. Akkor viszont: ϕ(x) =  ϕ′ (x) = Ax − (bT x)′ + 0 = Ax − b ′ 1 T x Ax = Ax 2 Geometriai interpretá ió függvény, tehát −ϕ(xk ) 1 T 1 x Ax − bT x + bT A−1 b 2 2 Ha irányban (Ax − b)′ = A xk -ban /′ (szimmetrikus pozitív denit) vagyunk, akkor ϕ′ (xk ) irányában n® a legmeredekebben a steepest des ent). söken a leginkább ( xk+1 = xk − αk · rk 28 ϕ ahol rk = Axk − b, ϕ′ (x) = Ax − b hiszen pont 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: A = AT miatt T xTk A = (AT xTk )T = (Axk )T Akkor végül: α =: αk = ahol rkT rk = rkT Irk , és I rkT rk >0 rkT Ark szimmetrikus pozitív denit mátrix. Ennek megfelel®en a gradiens-módszer: xk+1 = xk − Dení ió. Rayleigh-hányados: A rkT rk rk rkT Ark pozitív denit mátrix. Akkor a Rayleigh-hányados: xT Ax xT x 1 ||rk ||4 ϕ(xk+1 ) ≤ ϕ(xk ) − · T , vagyis a (xk ) sorozat 2 rk Ark Lemma. Állítás. Ha 0 < m ≤ αi ≤ M < +∞, amib®l következik a konvergen ia. Állítás. akkor   m ϕ(xk ) ϕ(xk+1 ) ≤ 1 − M A tétel nomítható Kantorovi s egyenl®tlenségével: ha rT Ar · rT A−1 r ≤ Állítás. ahol

sökken, de nem biztos, hogy a 0-hoz tart. A pozitív denit, akkor 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 A korábban elhangzott 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