Matematika | Analízis » Hevér Lőrinc - Numerikus matematika

El®adók: Virágh János, Dombi József, Csendes Tibor Numerikus Matematika I v 0.8 1999/2000-es tanév I. félév ABSOLUTE NO WARRANTY! szerkesztgeti: Hevér L®rinc heverl@freemail.hu Special thanx: Bodor Gábor, Lukács Andrea, K®vágó Tamás Tartalomjegyzék 1 2 3 4 5 6 1.1 Bevezetés 1.2 Hibaszámítás 1.3 Speciális alakú mátrixok 2.1 2.2 2.3 2.4 Eliminációs módszerek . Gauss-elimináció . Részleges f®elemkiválasztásos Gauss-elimináció Teljes f®elemkiválasztásos Gauss-elimináció . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1 3.2 3.3 3.4 Jordan-elimináció (f®elemkiválasztás

nélküli) Mátrix invertálás . Elimináció formális leírása . F®elemkiválasztás formális leírása . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1 Számolás partícionált mátrixokkal 4.2 Frobénius-féle mátrix invertálás 4.3 LR-felbontás 5.1 5.2 5.3 5.4 Az LR algoritmus . Az LR felbontás felhasználási lehet®ségei LR felbontás speciális alakú mátrixokra . Az RT R Cholesky-felbontás . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . Cholesky-felbontás (eddig tanultak összefoglalása) Cholesky-felbontás folytatása . QR ortogonális-trianguláris felbontás . QR felbontás kiszámítása . 6.41 Gram-Schmidt-féle ortogonalizáció 6.5 QR-felbontás alkalmazásai . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.1 6.2 6.3 6.4 7 Sajátértékszámítás 8 . . . . . . . . 8.1 Mátrixok speciális alakra transzformálása 1 2 2 2 3 5 5 7 8 8 9 9 9 10 12 14 14 15 16 19 19 21 22 23 27 27 28 30 31 31 32 33 36 36 2 9 Vektornormák, mátrixnormák 9.1 9.2 9.3 9.4 Vektornormák .

Mátrixnormák Rn×n -ben . A spektrálsugár és a mátrixnormák kapcsolata Normák ekvivalenciája . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 Vektorsorozatok és mátrixsorozatok 10.1 Vektorsorozatok 10.2 Mátrixsorozatok 10.3 Sajátértékek korlátai; Gersgorin-tétel 11 12 13 14 11.1 Hatvány módszer 11.2 Mátrixok speciális alakra transzformálása 11.21 LR-transzformáció 11.22 QR-transzformáció 11.23 RT R-transzformáció . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12.1 Iterációs módszerek bevezetése 12.2 Reguláris szétvágások 12.21 Jacobbi-iteráció (J-módszer) 12.22 (Gauss-)Seidel-iteráció (S-módszer) 12.23 Jacobbi-féle túlrelaxációs módszer (J(ω)-módszer) 12.24 Szukszecesszív túlrelaxációs módszer (S(ω)-módszer) 12.3 A Jacobbi- és a Seidel-módszer konvergenciája . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13.1 Az iterációs módszerek konvergenciája diagonális domináns A együtthatómátrixok esetén 13.2 II/14-es tétel

13.3 A 4 módszer konvergenciája pozitív denit mátrixok esetén 14.1 14.2 14.3 14.4 Utóiteráció . Kerekítési hiba az iterációs módszereknél Kondíciószám . Perturbáció . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 41 42 45 45 47 47 48 49 51 52 53 54 54 54 56 56 58 58 59 59 59 59 61 61 62 63 65 65 66 67 68 Fejezet 1 1.1 Bevezetés 1. Közelít® módszerek 2. Eektív (algoritmikus) módszerek Miért van szükség numerikus módszerekre? 1. A klasszikus módszerekkel nem oldható meg a probléma 2. Gauss-elimináció ⇔ Cramer-szabály 3. Stabilitás, hiba n × n-es 1.1 Tétel valós együtthatós lineáris

egyenletrendszer: Ax = a a11 x1 + a12 x2 + · · · + a1n xn a21 x1 + a22 x2 + · · · + a2n xn = a1,n+1 = a2,n+1 an1 x1 + an2 x2 + · · · + ann xn = an,n+1 . . egyértelm¶en megoldható ⇔ det(A) 6= 0 Ekkor a Cramer-szabály szerint: xi = det(Ai ) det(A) i = 1, . , n n+1 db determináns kell. 1.2 Hibaszámítás Hiba fajták: 1. Öröklött hiba: ha az adatok mérések, kísérlétek eredményei, akkor az öröklött hiba elkerülhetetlen Sokszor ide számítják az adott számítógépre vitelkor alkalmazott konverziók által eredményezett hibákat is. 2. Képlet hiba: a numerikus módszerek általában csak közelít® megoldást adnak, jó eseben olyan korlátot is ami felülr®l becsli a pontos megoldástól való eltérést. 3. Kerekítése hiba: az alkalmazott eszközök véges pontosságú számábrázolása, az alapm¶veletek eredményein végzett kerekítés, a beépített függvények kiértékelésekor fellép® hibája miatt adódik. 3 SPECIÁLIS

ALAKÚ MÁTRIXOK 4 1.2 Deníció Legyen a a pontos érték és a∗ a közelít® értéke Ekkor az a − a∗ értéket a közelítés hibájának nevezzük, az |a − a∗ | pedig az abszolút hibának nevezzük. |a − a∗ | ≤ M az abszolút hibakorlát 1.3 Példa Legyen a, b a pontos érték, a∗ , b∗ a közelít® érték Ma , Mb fels® korlátok, az összeg abszolút hibakorlátja így alakul: |a + b − (a∗ + b∗ )| = |(a − a∗ ) + (b − b∗ )| ≤ |a − a∗ | + |b − b∗ | ≤ Ma + Mb 1.4 Deníció |a−a∗ | |a∗ | ≤ δ, a relatív hibakorlát, ahol |a∗ | 6= 0 1.5 Példa |ab − a∗ b∗ | |a∗ b∗ | |(ab − a∗ b) + (a∗ b − a∗ b∗ )| |b||a − a∗ | |a∗ ||b − b∗ | ≤ + ∗ ∗ |a ||b | |a∗ ||b∗ | |a∗ ||b∗ | |b| 1 Ma Mb ≤ Ma ∗ ∗ + M b ∗ ≈ ∗ + ∗ = δ a + δ b |a ||b | |b | |a | |b | = Dierenciálható f (x) függvénynek az argomentumok pontosságából ered® hibája a Lagrange-tétellel

becsülhet®: ha f (x) dierenciálható az a és a∗ által kifeszített intervallumban, akkor létezik ebben az intervallumban olyan ξ közbüls® hely, amelyre f (a) − f (a∗ ) = f 0 (ξ)(a − a∗ ). Abszolút értékeket véve: |f (a) − f (a∗ )| = |f 0 (ξ)||a − a∗ | ≤ |f 0 (ξ)|Ma ≤ K1 Ma , fetléve, hogy f 0 (x) korlátos is az el®bb említett intervallumon, és ugyanitt K1 abszolút értékeinek is fels®korlátja. 1.3 Speciális alakú mátrixok Következzék itt néhány speciális alakú mátrix, a könnyebb ábrázolhatóság kedvéért 5 × 5-s formában: Fels® trianguláris egy R mátrix, ha rij = 0 akkor, ha i > j  r11 0  0  0 0 r12 r22 0 0 0 r13 r23 r33 0 0 r14 r24 r34 r44 0  r15 r25   r35   r45  r55 Alsó trianguláris egy L mátrix, ha lij = 0 akkor, ha i < j  l11 l21  l31  l41 l51 0 l22 l32 l42 l52 0 0 l33 l43 l53 0 0 0 l44 l54 0 0 0 0       l55

Megjegyzés. A kés®bbi fejezetekben az alsó trianguláris mátrixon, az ehhez hasonló olyan mátrixot értik amelynek a f®átlójában csupa 1-ek vannak Diagonális egy D mátrix, ha dij = 0 akkor, ha i 6= j  d11  0   0   0 0 0 d22 0 0 0 0 0 d33 0 0 0 0 0 d44 0  0 0   0   0  d55 SPECIÁLIS ALAKÚ MÁTRIXOK 5 Fels® Hessenberg egy H mátrix, ha hij = 0 akkor, ha i > j + 1  h11 h21   0   0 0 h12 h22 h32 0 0 h13 h23 h33 h43 0 h14 h24 h34 h44 h54  h15 h25   h35   h45  h55 Alsó Hessenberg egy G mátrix, ha lij = 0 akkor, ha i < j + 1  g11 g21  g31  g41 g51 g12 g22 g32 g42 g52 0 g23 g33 g43 g53 0 0 g34 g44 g54  0 0   0   g45  g55 Egy x vektort mindig oszlopvektornak tekintünk:   x1  x2    x= .   .  xn xT = (x1 x2 . xn ) Fejezet 2 2.1 Lineáris egyenletrendszerek megoldása (eliminációs módszerekkel) 2.1 Feladat

Adott az Ax = a (A ∈ Rn×n ; a ∈ Rn ) reguláris együtthatómátrixú egyenletrendszer, határozzuk meg az x-et. 2.2 Deníció A reguláris, ha det(A) 6= 0 A feladatot eleve úgy t¶ztük ki, hogy adott a reguláris együtthatómátrixú lineáris egyenletrendszer, ez azért van mert ekkor a feladatnak egyértelm¶ megoldása létezik. 2.3 Tétel Az Ax = a rendszernek pontosan akkor létezik egyértelm¶ megoldása, ha A reguláris Ezt nem nagy dolog bebizonyítani, hiszen ez a mátrix alakban felírt egyenletrendszer olyasmit jelent, hogy keresünk olyan xi valós számokat, hogy az A oszlopvektor rendszerének egy alkalmas lineáris kombinációjával el®állítsuk a jobboldali konstans vektort. Ez nyilván akkor fog sikerülni, hogy ha benne van ezek által kifeszített altérben1 az a és biztos benne lesznek, akkor ha ezek bázist2 alkotnak, s®t ha ezek bázist alkotnak, akkor az el®állítás egyértelm¶ lesz. Tehát egyetlen egy ilyen x létezik Mit mondhatunk a

homogén rendszerekr®l? Ebb®l a tételb®l az következik, hogy a homogén rendszereknek pontosan akkor van nem triviális megoldása, hogy ha az A mátrix nem reguláris. 2.4 Következmény Az Ax = 0 homogén rendszernek, pontosan akkor létezik nem triviális x megoldása ha A szinguláris.3 Azzal a kikötéssel, hogy A reguláris gondok lehetnek numerikus értelemben, mivel annak az ellen®rzésehez, hogy A determinánsa nulla vagy nem nulla körülbelül annyit kell számolni mintha megoldanánk a rendszert. Szóval ha azt a kikötést elhagyjuk, hogy A reguláris, akkor innent®l kényelmetlenebbé válnak a dolgok, hogy lássuk azt, hogy vannak olyan mátrixok amikor könnyebb ezt a kérdést megválaszolni mutatunk egy speciális mátrix osztályt. 2.5 Deníció A diagonális domináns, ha |aii | > Pnj=1,j6=i |aij | (i = 1, . , n) Tehát abszolút értékben a diagonális elemek határozottan nagyobbak, mint a sorukban lév® összes többi elem abszolút értékes

összege. 2.6 Példa A következ® mátrix diagonális domináns:   −5 1 1  0 2 −1 3 3 −7 2.7 Tétel Ha A diagonális domináns, akkor altér: egy számtest feletti vektortér nemüres részlhalmaza, amely maga is vektorteret alkot a számtest felett bázis: lineárisan független egyenletrendszer mivel ha det(A) = 0 (azaz a szinguláris), akkor a 2.3 tétel szerint nem létezik egyértelm¶ megoldás az egyenletrendszerre, tehát a triviális megoldáson kívül léteznie még legalább egy megoldásnak. 1 2 3 6 ELIMINÁCIÓS MÓDSZEREK (i) 7 aii 6= 0 i = 1, . , n (ii) A reguláris Bizonyítás. (i) Ez a denícióban lév®, határozottan nagyobb jelb®l következik (ii) Minden diagonális domináns mátrix reguláris. Ezt indirekt úton bizonyítjuk. Tegyük fel, hogy A diagonális domináns de szinguláris Ha az A szinguláris és veszzük az Ax = 0 homogén renszert, akkor van A-nak nem triviális megoldása. Ekkor van olyan x∗ ∈ Rn , hogy x∗

6= 0 (tehát nem triviális megoldás) és Ax∗ = 0. Itt csak azt írtuk fel, hogy ennek a homogén rendszernek van nem triviális megoldása. Tehát ha ez nem triviális megoldás, akkor vannak benne nem 0 komponensek is, válaszunk ki ezek közül egy maximális abszolút érték¶t (több ilyen is lehet). Legyen |x∗k | = max1≤i≤n |x∗i |. Vegyük az egyenletrendszerünkb®l a k-adik egyenletet Ez úgy néz ki, hogy venni kell a mátrixunk k-adik sorát és végig kell szorozni a megoldás komponensekkel. ak1 x∗1 + ak2 x∗2 + · · · + akk x∗k + · · · + akn x∗n = 0 akk x∗k = − n X akj x∗j j=1 j6=k Vegyük mindkét oldal abszolút értékét: |akk x∗k | = − n X akj x∗j ≤ j=1 j6=k n X |akj | x∗j ≤ n X j=1 j6=k |akj | |x∗k | j=1 j6=k Ez utolsó egyenl®tlenségnél mindegyik megoldás komponens abszolút értéke helyére a maximális komponens abszolút értékét írtuk. Ekkor x∗k -al lehet egyszer¶síteni (hiszen nem 0) |akk |

≤ n X |akj | j=1 j6=k Ez viszont ellentmond annak, hogy A diagonális domináns. Annak eldöntése, hogy egy mátrix diagonális domináns-e, viszonylag könnyen elérhet®. Durván számolva a sorösszegeket kell kiszámolni és csinálni kell n db összehasonlítást, ami n2 m¶velettel eldönthet®. Mikor ekvivalens két egyenletrendszer? Akkor ha ugyanaz mindkett®nek a megoldáshalmaza. A megoldáshalmaz itt vektoroknak a halmaza. Mondjuk mindig feltesszük azt, hogy egyértelm¶ a megoldás, ekkor két egyenletrendszer ekvivalenciája azt jelenti, hogy ugyanaz a megoldás vektora. 2.8 Feladat Van a kiindulási egyenletrendszerünk és ehhez kell konstruálni vele ekvivalens egyenletrendszereket, amiknek ugyanaz a megoldása és amiket már könnyen meg tudunk oldani A1 x = a1 ⇔ A2 x = a2 ⇔ · · · ⇔ Al x = al 1. Gauss-elimináció, ekkor Al = R (fels® trianguláris) 2. Jordan-elimináció, ekkor Al = I (egységmátrix) Elemi átalakítások 1. tetsz®leges

egyenletet beszorzunk, valamilyen nem 0 konstanssal 2. hozzáadjuk egyik sort a másikhoz Két egyenlet sorrendjének a megváltoztatása sem változtat az eredményen, de ez bizonyos értelemben nem nevezhet® elemi átalakításnak. A két elemi átalakítást kombinálni szokták, ekkor valamelyik sor konstansszorosát adjuk hozzá egy másik sorhoz A numerikus algoritmusoknál szigorúan meghatározott az átalakítások sorrendje. GAUSS-ELIMINÁCIÓ 8 2.2 Gauss-elimináció Csak a b®vített mátrixot fogjuk kezelni: Â = ( A| a) ∈ Rn×(n+1) n-1 lépésben hajtjuk végre az átalakítást, hogy a végén fels® trianguláris alakot kapjunk. j-dik lépés: (j = 1, 2, . , n−1) kiküszöböljük az xj ismeretlent a j-dik alatti összes (tehát a j +1, j +2, , n-ik) egyenletb®l A j-dik egyenlet alkalmas konstans szorosait hozzáadjuk az egyenletekhez (j+1-dikhez, j+2-dikhez stb.) A fels® indexek azt jelölik, hogy hányadik lépésnél tartunk: a011  a021 

Â0 =  .  . a0n1  a012 a022 . . a01n a02n a0n2 . a0nn . . .  a01,n+1 a02,n+1   .  .  a0n,n+1 Az els® lépésben Â0 -b®l az a011 alatti elemeket kell kinullázni, ekkor fogjuk Â1 -et kapni. A j-dik lépésnél viszont már a következ®k állnak fenn: Âj−1  j−1 a11  0    0    0 =   0   0   .  . 0 aj−1 12 aj−1 22 . . aj−1 1j aj−1 2j 0 . aj−1 1,j−1 aj−1 2,j−1 0 0 0 0 0 0 aj−1 j−1,j−1 0 0 aj−1 j,j aj−1 j+1,j 0 0 0 aj−1 n,j . . . . . . . . . . . . . .  . .   .  .  .  .   .   .   .  . . Tegyük fel, hogy az 6= 0, ekkor a j-dik sor alkalmas konstansszorosát, adjuk hozzá az alattalév®khöz. Mik ezek az alkalmas konstansok? aj−1 jj lij = aj−1 ij aj−1 jj (i = j + 1, . , n) Most már megtudjuk mondani, hogy az j-dik egyenletnek hányszorosát kell az i-dikhez hozzáadni, hogy 0-t

kapjunk. j−1 ajik = aj−1 ik − lij ajk (k = j + 1, . , n + 1) Az oszlopindex azaz a k csak a j + 1-dik oszloptól megy mivel a j-dikben úgyis 0-k állnak tehát azzal nem kell tör®dni, a többi elem azonban kell a következ® lépésekhez és azért tart n+1-ig mert összevont mátrixról van szó. Ha a aj−1 jj 6= 0 feltétel nem teljesül, akkor módosítani kell az algoritmust (lsd lentebb). 2.9 Állítás Ha a A diagonális domináns, akkor az Ax = a megoldható a Gauss-eliminációval Költségelemzés Helyigény Mindig ugyanazon a mátrixon hajtjuk végre a m¶veleteket. Így a helyigénye körülbelül n2 , ezt precízen megfogalmazva o(n2 ) (egészen pontosan n2 + n) 2.10 Deníció an = o(bn ), ha van olyan K ∈ R+ , hogy |an | ≤ K |bn | majdnem minden n-re (azaz van egy küszöbszám ami után teljesül). RÉSZLEGES FŽELEMKIVÁLASZTÁSOS GAUSS-ELIMINÁCIÓ 2.11 Példa an = n2 n+1 = n2 −1+1 n+1 = (n−1)(n+1)+1 n+1 =n−1+ 1 n+1 9 = n

− 1 + o( n1 ) M¶veletigény Adott j-re: (n-j) osztást (n-j)(n-j+1) kivonást (n-j)(n-j+1) szorzást kell elvégezni. Minden m¶veletet azonos súllyal veszünk. M (n) = n−1 X (n − j) + 2(n − j)(n − j + 1) = j=1 = n−1 X 4 2 (n − j)(1 + 2(n − j + 1)) j=1 (n − j)(2(n − j) + 3) = j=1 = n−1 X n−1 X l(2l + 3) = 2 l=1 n−1 X l2 + 3 l=1 n−1 X l l=1 (n − 1)n(2(n − 1) + 1) (n − 1) + 1 2 + 3(n − 1) = n3 + o(n2 ) 6 2 3 A Visszahelyettesítés m¶veletigénye n2 + O(n), ami az elimináció futási idejéhez képest elhanyagolható. 2.3 Részleges f®elemkiválasztásos Gauss-elimináció Egyszer¶en az a feladat, hogy a f®átlóban és az alatta lév® elemek közül kiválasztjuk a maximális abszolút érték¶t. Legyen ez az elem a f®elem, azaz "cseréljük fel" az aktuális sort a f®elem sorával (ez algoritmikus szempontból nem hatékony, érdemes a sorokra mutató pointereket használni és azokat megcserélni, a

f®elem kiválasztása o(n) összehasonlítást jelent). 2.12 Deníció A j -dik lépésnél használt f®elem legyen az aj−1 := max |aij |, határozzunk meg ilyen k -t. kj j≤i≤n Cseréljük fel az Âj−1 -ban a k-dik és j-dik sort. Ez már csak akkor lehet 0, ha a f®átlóban 0 áll és az alatt lév® elemek is mind 0-k, ekkor viszont a determináns is 0 (azért mert ekkor szorozni kell egymással a diagonális elemeket a j-dik sorig és venni a fennmaradó rész determinánsát, a fennmaradó rész determinánsa viszont biztos, hogy 0 mivel van egy teljesen 0 oszlopa). 2.13 Állítás Tetsz®leges reguláris együtthatómátrixú Ax = a egyenletrendszer megoldható részleges f®elemkiválasztással Azt szokták mondani, hogy a részleges f®elemkiválasztásos Gauss-eliminációnak ugyanannyi a m¶veletigénye, mint a f®elemkiválasztás nélkülinek. 2.4 Teljes f®elemkiválasztásos Gauss-elimináció A teljes f®elemkiválasztásnál úgy módosítjuk az

algoritmust, hogy a f®elemet a j -ik lépésnél nem csak a j -ik oszlopból keressük hanem az egész fönnmaradó részmátrixból, és azt visszük fel a f®elem helyére. 2.14 Deníció aj−1 = max |aip | kl j≤i,p≤n Cseréljük fel a j-ik és a k-ik sort a Âj−1 mátrixban, utána pedig cseréljük fel a j-ik és az l-ik oszlopot (az oszlopcserét viszont el kell tárolni). Bizonyos esetekben, a teljes f®elemkiválasztással jobb eredményt érhetünk el, mint a részlegessel. A kritikus része az algoritmusnak az amikor leosztunk a f®elemmel, ha nagyon kicsi lenne a f®elem, akkor kerekítési problémák adódhatnak és ezen módosítani tud a teljes f®elemkiválasztás. 4 felhasználjuk az els® n négyzetszám összegét, ami n(n+1)(2n+1) 6 és az els® n egész szám összegét, ami n(n+1) 2 Fejezet 3 3.1 Jordan-elimináció (f®elemkiválasztás nélküli) 3.1 Feladat A = A1 ⇔ A2 ⇔ · · · ⇔ An = I Ix = an ⇔ x = an Ekkor nem kell vissza

helyettesíteni, az algoritmushoz n lépés kell. 3.2 Deníció Jordan-elimináció A j-dik egyenletet leosztjuk a f®elemmel, hogy a f®elem egy legyen ajj 6= 0 ajk := ajk ajj Ha (k = j + 1, . , n + 1) az így módosított j-dik egyenlettel kiküszöböljük az xj ismeretlent az összes többi egyenletb®l:1 aik := aik − aij ajk M (n) = O(n3 ) (i = 1, . , n i 6= j) (n3 + O(n2 ))† A f®elemekiválasztások hasonlóak, mint a Gauss-eliminációnál 3.2 Mátrix invertálás 3.3 Feladat Hogyan lehet egyszerre több egyenletrendszert megoldani? Tegyük föl, hogy olyan egyenletrenszereink vannak, amelyeknek ugyanaz az együtthatómátrixa de más a jobboldala.  Ax = a1     Ax = a2  . m db .   Ax = am  Ezeket egyszerre is meglehet oldani, úgy hogy veszük az együttható mátrixot és leírjuk egymás mellé a jobb oldalakat. A b®vített mátrix most a következ®: Â = (Aa1 a2 . am ) ∈ Rn×(n+m) k = .n + m A mátrix k = .n

+ m azt jelenti, hogy az oszlopindex n + m-ig fog elmenni. invertálás ennek a feladatnak a speciális esete. 1 nyilván a a -at kell kivonni az egyes elmekb®l mivel a -t kapjuk a j-dik egyenlet f®elemmel való leosztása után, ami ahhoz ij jk jk kell, hogy a f®elem 1 legyen, ezt a pedig szorozni kell az aktuális sor j-dik oszlopában lév® elemmel, hogy a kivonás után 0 eredményt kapjunk a j-dik oszlopban. † (n-j+1)osztást, (n-1)(n-j+1) szorzást és (n-1)(n-j+1) kivonást kell elvégeznünk 10 ELIMINÁCIÓ FORMÁLIS LEÍRÁSA AX = I 11 (ahol X = A−1 ∈ Rn×m és X = (x1 , . , xn )) ez pontosan, akkor teljesül ha Ax1 Ax2 = e1 = e2 Axn = en . . Jordan-elmiminációt alkalmazunk úgy, hogy m = n tehát k = . 2n és Ân = x1 x2 I Ha azonban így csináljuk, akkor az még messze nem optimális mivel a kiegészít® résznek speciális tulajdonságai vannak. Az oszlop indexel elég csak n + j -ig elmenni. A kiindulásnál generálni kellene az n2

elemb®l álló egységmátrixot (Â0 = (A|I) ), valójában erre sincs szükség. Szét kell szedni egy kicsit a képleteket és a megfelel® résznél azokat alkalmazni Az n+1-t®l a következ® képleteket alkalmazzuk: ajk := a1 jj valamint aik := −aij ajk . A m¶veletigényre már meglehet mutatni, hogy így is O(n3 ) de a helyigény az 2n2 . A helyigényen úgy lehet javítani, hogy helyben invertálunk, tehát az els® lépésnél az els® oszloppal már úgy sem foglalkoznánk, így oda tárolhatjuk a kiegészít® rész els® oszlopát és így tovább (mod n számoljuk az oszlopokat), így a helyigény leszorítható n2 -re. Megjegyzés (A Jordan eliminációval való mátrixinvertálás összefoglalása). ben: Â0 = (AI) ∈ Rn×(2n) , def a j-dik lépés- (i) a j-dik egyenlet leosztása a(j−1) f®elemmel jj (j−1) (j) ajk = ajk (j−1) k = j + 1, j + 2, . , n + j ajj (ii) az xj ismeretlen kiküszöbölése a megfelel® egyenletekb®l: (j) (j−1) aik =

aik (j−1) (j) ajk − aij k = j + 1, . , n + j i = 1, . , n i 6= j Hogyan lehetne formálisan leírni ezeket az algoritmusokat, lineáris algebrában alkalmazott eszközökkel? 3.3 Elimináció formális leírása 3.4 Példa Van egy B mátrixunk amib®l csinálni akarunk egy olyan mátrixot ami ®t®le csak abban különbözik, hogy a j -dik sora le van osztva az diagonális elemmel a bjj -vel. Ekkor balról szorozni a következ® diganodális mátrixal:   1   .      Dj =                1 1 b jj 1 . 1 eTi A, ekkor az A mátrix i-dik sora lesz az eredmény Aek , ekkor az A mátrix k-dik oszlopa lesz az eredmény eTi Aek ekkor az aik elem lesz az eredmény ELIMINÁCIÓ FORMÁLIS LEÍRÁSA 12 Vektor szorzatok 1. skalár szorzat (bels® szorzat) 2. diadikus szorzat (küls® szorzat)  T n c, d ∈ RP n T c d = i=1 ci di ∈ R  c1 d  cdT = G = (d1 c . dn c) =  c1 d1 c1

d2 . c1 d n cn d1 cn d2 . cn dn  . .  .  =  cn dT lehet kevesebb, ha legalább az egyik 0 vektor). 3.5 Deníció (j) gj Gj = 0. . .  .  .  Ekkor G rangja legfeljebb 1 (akkor eliminációs mátrix , ha felírható Gj = I + gj eTj alakban, ahol gj j -dik komponense 0, Ekkor Gj a következ®képpen néz ki:  1       Gj =       (j) .  g1 . . (j) 1 gj−1 1 (j) gj+1 1 . . . (j) gn             1 Ezekkel a mátrixokkal tudunk majd eliminálni egy oszlopot. Például úgy kapjuk a Gauss-eliminációt, hogy gi -k helyére beiírjuk az lij -et, ez azonban még úgy módosul, hogy a j-dik oszlopban 1 felett is 0-k vannak. 3.6 Állítás Legyen Gj tetsz®leges eliminációs mátrix, ekkor (i) B = Gj A olyan mátrix, sorának gi(j) -szeresét.(A melyben az i-dik sor úgy áll el®, hogy az A i-dik sorához hozzádadjuk A j-dik soraihoz hozzáadogatjuk a gi -ben

lév® konstansszorosait a j-dik sornak) (ii) C = AGj olyan mátrix, melynek a j-dik oszlopát úgy kapjuk, hogy A j-dik oszlopához hozzáadjuk A els® oszlopának g1(j) -szeresét., A n-dik oszlopának gn(j) -szeresét Bizonyítás. (i) nézzük meg B i-dik sorának k-dik elemét bik = eTi Bek = eTi (Gj A)ek = eTi ((I + g j eTj )A)ek = eTi (A + g j eTj A)ek = eTi Aek + eTi g j (eTj Aek ) (j) = aik + (eTi g j )ajk = aik + gi ajk ahol gi(j) a gj vektor i-dik eleme. 3.7 Példa  1  0 G3 A =  0 0 G3 A 4 × 4-es mátrixok esetén:  (3) 0 g1 0 a11 a12 a13  (3) a a22 a23 1 g2 0  21  0 1 0 a31 a32 a33 (3) a41 a42 a43 0 g 1 4   (3) a11 + g1 a31 a14  (3) a24  a + g2 a31 =  21  a34  a31 (3) a44 a41 + g a31 4 (3) a12 + g1 a32 (3) a22 + g2 a32 a32 (3) a42 + g4 a32 (3) a13 + g1 a33 (3) a23 + g2 a33 a33 (3) a43 + g4 a33  (3) a14 + g1 a34  (3) a24 + g2 a34    a34 (3) a44 + g4 a34 Tehát a B mátrixnak az

i-dik sorát úgy kapjuk, hogy A i-dik sorához hozzáadjuk A j-dik sorának megfelel® konstansszorosát és az egyes eliminációs módszereknél csak ezeket a konstansokat kell megváltoztatni. FŽELEMKIVÁLASZTÁS FORMÁLIS LEÍRÁSA 13 3.4 F®elemkiválasztás formális leírása 3.8 Deníció Legyen 1 ≤ i, j ≤ n, i 6= j tetsz®leges. A Pij elemi permutációs értjük, amelyet az I egységmátrixból az i-dik és j-dik sor fölcserélésével kapunk. 3.9 Példa Ha n = 3, i = 1, j = 2, akkor P12 = mátrixon azt a mátrixot 0 1 0 100 001 3.10 Deníció P permutációs mátrix , ha el®áll az I egységmátrix sorainak alkalmas permutálásával 3.11 Állítás Tetsz®leges A mátrixot a Pij elemi permutációs mátrixszal szorozva: (i) B = Pij A-t úgy kapjuk, hogy fölcseréljük A i-dik és j-dik sorát. (ii) C = APij -t úgy kapjuk, hogy fölcseréljük A i-dik és j-dik oszlopát. Bizonyítás. (i) Válasszuk ki B -nek egy tetsz®leges elemét: bkl = eTk

Bel = eTk (Pij A)el = (eTk Pij )(Ael ) (a) Ha a kiválasztott elem olyan volt, hogy az eredeti A mátrixban nem érintette a sorcsere, vagyis k 6= i és k 6= j , akkor eTk Pij = eTk (hiszen ekkor eTk "kiválasztja" Pij k -dik sorát, de mivel k 6= i és k 6= j ezért ebben az esetben az egység mátrixnak tekinthet® Pij ), ezért bkl = eTk Ael = akl . (b) Ha k = i, akkor eTk Pij = eTi Pij = eTj , ezért bil = eTj Ael = ajl . (c) Ha k = j , akkor eTk Pij = eTj Pij = eTi , ezért bjl = eTi Ael = ail Ha részleges f®elemkiválasztást kell csinálni, akkor az azt jelenti, hogy balról kell szorozni a mindenkori "A" mátrixot. Ha teljes kiválasztást akarunk, akkor balról is szorozni kell és jobbról is szorozni kell valamilyen hasonló permutációs mátrixszal. F®elemkiválasztás nélküli Gauss-elimináció A j-dik lépésben adott Âj−1 , amib®l Âj = Gj Âj−1 ahol  0   .   .     0     gj =   0 

−lj+1,j     .   .  −ln,j R = An−1 = Gn−1 · · · G2 G1 A0 | {z } A1 | | {z A2 {z An−1 } } Az eliminációs mátrix inverze a következ®képpen adódik: 3.12 Állítás Bizonyítás. T G−1 j = I − g j ej T T T T Gj G−1 j = (I + g j ej )(I − g j ej ) = I − g j (ej g j ) ej = I | {z } 0 eTj g j esetén eTj éppen a j -dik komponenst választja ki gj -ben ami 0. FŽELEMKIVÁLASZTÁS FORMÁLIS LEÍRÁSA 14 Az elimináció végeredménye: G−1 n−1 / R = Gn−1 · · · G2 G1 A0 G−1 n−1 R −1 −1 −1 G1 G2 · · · Gn−1 R = Gn−2 · · · G2 G1 A0 | {z = A0 } L Ekkor A0 a kiindulási együttható mátrix, R a Gauss-elimináció végerdménye a G-k eliminációs mátrixok, és az inverzek miatt + szerepel bennük. Tehát L a következ®képpen néz ki:  1  l21   L=  l31  .  . ln1 0 1 0 l32 1 . . ln,n−1 n2 . . .  0   .  .   0 1 A lik a

Gauss-elimináció során deniált konstans. L alsó egység trianguláris mátrix 3.13 Tétel Ha A-ra végrehajtható a f®elemkiválasztás nélküli Gauss- elimináció, akkor A-nak létezik A = LR trianguláris felbontása. Részleges f®elemkiválasztásos Gauss-elimináció Âj = Gj Pjπ(j) Âj−1 j ≤ π(j) ≤ n π(j) ∈ N El®ször megcserélük a j-dik és a π(j)-dik sort. An−1 = Gn−1 Pn−1,π(n−1) · · · G1 P1π(1) A0 P A = L∗ R∗ Fejezet 4 4.1 Számolás partícionált mátrixokkal Egy mátrix partíconálása azt jelenti, hogy valamilyen módon feldaraboljuk a sorait, oszlopatit (nem feltétlenül ugyanolyan módon). Így részmátrixok keletkeznek, amiket blokkok nak is szoktak nevezni Egy valós n × m-es A mátrix i sorra és s oszlopra való partícionálása a következ®képpen néz ki:  A11  A21   .  . Ai1 l1 A12 A22 . . Ai2 l2  A1s A2s   .  .  . Ais . ls . . m1 m2 n = mi m = . . Pi j=1

mj Ps j=1 lj Az ilyen felbontás azért jó, mert egy szintel feljebb lehet vinni a mátrix algebra szokásos számolási szabályait. A mátrixok vonatkozóan összeadni, skalárral szorozni lehet úgy ezeket a m¶veleteket lehet általánosítani blokkokra Ha van egy szintén n × m-es mátrixunk amely ugyanúgy van praticionálva, mint A:  B11  B21  B= .  . Bi1 B12 B22 . . Bi2 . . . .  B1s B2s   .  .  Bis akkor a C összegmátrix a megfelel® blokkok összegeként áll el®:  C11  C21  C =A+B .  . Ci1 C12 C22 . . Ci2 Cpq . . .  C1s C2s   .  .  Cis Cpq = Apq + Bpq . A skalárszorzat értelemszer¶en:  G11  G21  G = αA  .  . Gi1 G12 G22 . . Gi2 Gpq . . .  G1s G2s   .  .  Gis Gpq = αApq A mátrix szorzásnál plussz feltétel is bejön mivel a blokkoknak külön-külön összeszorozhatónak kell lenniük, ez pedig akkor teljesül, ha a szorzandó mátrix oszlopat

annyi darabra bontottuk, mint a szorzó mátrix sorait. Csak egy speciális estet fogunk alkalmazni, amikor a mátrix 4 darabra van partícionálva és ekkor az els® partícó méreti egyértelm¶en meg fogják határozni a többi partíció méretét  A= A11 A21 A12 A22  és van egy ugyanígy partícionált B = 15  B11 B21 B12 B22  FROBÉNIUS-FÉLE MÁTRIX INVERTÁLÁS 16 akkor a C szorzatmátrix a következ®képpen áll el®:  C = AB A11 B11 + A12 B21 A21 B11 + A22 B21 A11 B12 + A12 B22 A21 B12 + A22 B22  4.2 Frobénius-féle mátrix invertálás Mátrix invertálásnál X-re keressük a megoldást a következ® egyenletrendszerben:  A11 A21 A12 A22  I11 012 021 I22 X11 X21 = = = = X12 X22   = I11 021 012 I22  A11 X11 + A12 X21 A11 X21 + A12 X22 A21 X11 + A22 X21 A21 X12 + A22 X22 (4.1) (4.2) (4.3) (4.4) A leosztások helyett itt mátrix inverzekkel kell dolgozni és még arra kell vigyázni, hogy itt már nem kommutatív −1 a

szorzás. Tegyük fel, hogy A−1 és A−1 11 létezik. Szorzzuk balról az (41)-es egyenletet A11 -el, majd szintén balról −A21 -el. Ekkor az els® és a harmadik egyenlet így néz ki: −A21 A−1 = −A21 X11 + −A21 A−1 11 11 A12 X21 0 = A21 X11 + A22 X21 Majd a két egyenletet összeadjuk és az eredményt rendezzük. −A21 A−1 11 −A21 A−1 11 = −A21 A−1 11 A12 X21 + A22 X21 = (A22 − A21 A−1 A12 ) X21 | {z 11 } B X21 = −B −1 A21 A−1 11 Majd visszahelyettesítjük az így kapott egyenletet az els®be, azt egy kicsit átalakítva megkapjuk X11 -et: A11 X11 X11 = I11 − A12 X21 = A−1 11 (I11 − A12 X21 ) Ezután vesszük a második egyenletet (4.2) és beszorozzuk −A21 A−1 11 -el balról. Ezután a második és a negyedik egyenlet a következ®képpen néz ki: = −A21 X21 − A21 A−1 11 A12 X22 = A21 X12 + A22 X22 0 I22 Majd szintén összeadjuk a két egyenletet és átalakítjuk: I22 I22 = A22 X22 − A21 A−1 11 A12 X22 −1 =

(A22 − A21 A11 A12 ) X22 {z } | B X22 = B −1 Ezt visszahelyettesítjük az átalakítoot második (4.2) egyenletbe: A11 X21 X21 = −A12 X22 = −A−1 11 A12 X22 LR-FELBONTÁS 17 Meg kell még mutatni, hogy a B = A22 − A21 A−1 11 A12 mátrixnak van inverze. Ehhez tekintsük a következ® mátrixokat:  I11 −A21 A−1 11 | {z 012 I22  A11 A21 }| G A12 A22 {z A   = } | A11 021 A12 B {z  } C Ekkor a determináns szorzástétele alapján det(c) = det(G) det(A). A-nak tudjuk, hogy nem 0 a determinánsa (ez volt a feltétel), G-r®l látszik, hogy 1 a determinánsa, mivel egy alsó egységtrianguláris mátrix, tehát C -nek nem lehet 0 a determinánsa és a következ®képpen fejezhet® ki: det(A11 ) det(B) ebb®l pedig következik, hogy B -nek sem lehet 0 a determinánsa. Megjegyzés. Több féle úton is el lehet jutni a megoldásokhoz Lehetne lépésenként ellen®rizni, hogy a szorzások tényleg evégezhet®ek-e és amit eredményül kapunk az

olyan dimenziós-e, hogy össze lehesen adni, ez azonban minden lépésnél teljesül. Az Frobénius-invertálásnak O(n3 ) a m¶veletigénye. Speciális esetekben érdemes ezt a módszert használni, példaul ha a mátrix kvázi trianguláris  A11 0 A12 A22  vagy kvázi diagonális  A11 0 0 A22  mivel ilyenkor a képletek jelent®sen leegyszer¶södnek. Akkor is hasznos lehet ez a módszer, ha olyan nagy mátrixal dolgozunk, amely nem fér be a memóriába. 4.3 LR-felbontás 4.1 Deníció A = LR az A trianguláris felbontása, ha L alsó egység trianguláris, R pedig fels® trianguláris 4.2 Tétel (LR unicitása) Ha A reguláris, akkor az A = LR felbontás egyértelm¶ (legfeljebb 1 db felbontás létezhet). Bizonyítás. Indirekt módon Tegyük fel, hogy létezik két különböz® felbontás: A = L1 R1 = L2 R2 (tehát vagy az L1 különbözik az L2 -t®l vagy az R1 különbözik az R2 -t®l). Mivel A reguláris volt, így a többi mátrixnak is regulárisnak

kell lennie, így lehet manipulálni az inverzekkel. L−1 2 / L1 R1 L−1 2 L1 R1 L−1 2 L1 = L2 R2 = R2 /R1−1 = R2 R1−1 Ezzel már ellentmondásra is jutottunk. Miért nem állhat fenn ez az egyenl®ség? Mivel a bal oldalon alsó egység trianguláris mátrix van (hiszen egy alsó egység trianguláris mátrix inverze is alsó egység trianguláris és két alsó egység trianguláris mátrix szorzata is alsó egység trianguláris) a jobb oldalon fels® trianguláris mátrix van ami csak úgy lehetséges ha mindkett® diagonális ez a digonális viszont csak az egységmátrix lehet. Ekkor viszont −1 azt kapnánk, hogy I = L−1 2 L1 és I = R2 R1 , amib®l viszont L2 = L1 , R1 = R2 -t kapnán. Err®l viszont már egyértelm¶en látszik, hogy ellentmond a feltételünknek. Abból, hogy A reguláris még nem következik, hogy létezik is a felbontás. Tehát következ® kérdés az egzisztencia, azaz mikor létezik ez a felbontás 4.3 Tétel (LR egzisztenciája) Az A

reguláris mátrixnak, pontosan akkor létezik A = LR felbontása, ha det(Akk ) 6= 0 k = 1, . , n (∃A = LR ⇔ det(Akk ) 6= 0) 4.4 Segédtétel Ha létezik az A = LR felbontás, akkor a det(Akk ) = r11 · · · rkk = (r11 r22 · · · rk−1,k−1 )rkk = det(Ak−1,k−1 )rkk (det(A00 ) deníció szerint 1). LR-FELBONTÁS 18    E 0 H J Bizonyítás. Tekintsük a következ®képpen partícionált mátrixot = Ekkor F G 0 K Akk = EH , ha ez igaz akkor a determinánsát a követekez®képpen lehet felírni det(Akk ) = det(E) det(H). det(E) = 1 mivel E alsó egység trianguláris, H viszont fels® trianguláris, tehát det(Akk ) = 1 det(H) = r11 · · · rkk . Akk C B D   Bizonyítás. (i) (A reguláris és ∃A = LR ⇒ det(Akk ) 6= 0) Tegyük fel, hogy létezik a felbontás, mivel A reguláris, akkor az elöz® segédtétel alapján 0 6= det(A) = det(Ann ) = r11 · · · rnn . Ebb®l az következik, hogy semelyik rii (1 ≤ i ≤ n) sem lehet 0, tehát mindegy, hogy

az r-ek közül mennyit szorzunk össze mindig 0 különböz® leszt det(Akk ). (ii) (A reguláris és det(Akk ) 6= 0 ⇒ ∃A = LR ) Legyen det(Akk ) 6= 0 k = 1, . , n, megmutatjuk a mátrix rendje szerinti indukcióval, hogy létezik a felbontás. (a) n=1 0 6= det(Akk ) ekkor A = |{z} 1 |{z} A L √ R (b) tegyük fel, hogy az állítás igaz bármely a tétel feltételeit teljesít® n-1-ed rend¶ mátrixra. Legyen A a feltételeket teljesít® n-ed rend¶ mátrix, keressük így a felbontását (az utolsó sora és oszlopa el®tt partícionálunk):  A= A-t An−1,n−1 cT  b ann  = Ln−1,n−1 yT 0 1  Rn−1,n−1 0T x z  ismerjük. Mikor lenne igaz ez a felbontás? An−1,n−1 b T c ann = Ln−1,n−1 Rn−1,n−1 = Ln−1,n−1 x = y T Rn−1,n−1 = yT x + z (4.5) (4.6) (4.7) (4.8) (4.5) az indukciós feltevés miatt egyértelm¶en létezik (46) az x-re vonatkozóan egy lineáris egyenletrendszernek tekinthet® A rendszer az x-re vonatkozóan

egyértelm¶en megoldható, mivel az együtthatómátrixa reguláris (47) az elöz® eset transzponáltja, tehát ilyen yT is egyértelm¶en létezik z is egyértelm¶en kifejezhet® (4.8)-ból, hiszen yT x egy skalár szorzat, amit már ismerünk és ann adott volt. A tétel bizonyítása során adódik egy rekurzív algoritmus az LR felbontásra, azonban nem ezt érdemes használni, van direkt algoritmus is. 4.5 Állítás Ha A diagonális domináns, akkor egyértelm¶en létezik az A = LR felbontás Ez azért igaz, mert ha A diagonálisan domimáns, akkor Akk is diagonálisan domináns tehát det(Akk ) 6= 0 a diagonális dominancia tulajdonsága miatt. Alkalmazások A = LR-re Mindig felteszzük, hogy A reguláris (1) determináns számítás det(A) = det(L) det(R) = det(R) | {z } 1 (2) mátrix invertálás A = LR ⇔ A −1 = L−1 R−1 LR-FELBONTÁS 19 (3) lineáris egyenletrendszer megoldása  Ax = a ⇔ LRx = a ⇔ Ly = a Rx = y "el®re" helyettesítés

O(n2 ) visszahelyettesítés O(n2 ) Fejezet 5 5.1 Az LR algoritmus 5.1 Példa Az LR algoritmus végrehajtásánál, a mátrixszorzáshoz hasonló m¶veletr®l van szó A kiindulási mátrix jelen esetben a 3 × 3-s A mátrix. A 2-al keretezett elemeket keressük L 1 l21 0 1 0 0 r11 0 0 2 4 l31 2. l32 4. 1 2 R r12 r22 0 1 5 r13 r23 r33 2 5 7 5 1. 3. 5. A A mátrix szorzás szabálya szerint felírhatók az ismeretlenekre vonatkozó egyenletek amib®l el®ször R els® sorát tudjuk meghatározni: 1 · r11 + 0 · 0 + 0 · 0 r11 1 · r12 + 0 · r22 + 0 · 0 r12 1 · r13 + 0 · r23 + 0 · r33 r13 = = = = = = 2 2 1 1 2 2 = = = = = = 4 4 2 2 2 1 A 2. lépésben L els® oszlopát tudjuk meghatározni: l21 · r11 + 1 · 0 + 0 · 0 l21 · 2 l21 l31 · r11 + l32 · 0 + 1 · 0 l31 · 2 l31 3. lépésben R második sorát tudjuk kiszámolni: l21 · r12 + 1 · r22 + 0 · 0 2 · 1 + 1 · r22 r22 l21 · r13 + 1 · r23 + 0 · r33 2 · 2 + 1 · r23 r23 20 = = = = = = 5 5 3

5 5 1 AZ LR ALGORITMUS 21 Végül L második oszlopát és R harmadik sorát: l31 · r12 + l32 · r22 + 1 · 0 1 · 1 + l32 · 3 l32 l31 · r13 + l32 · r23 + 1 · r33 1 · 2 + 2 · 1 + r33 r33 = = = = = = 7 7 2 5 5 1 1 3 0  2 1 1 Tehát L és R a következ®képpen alakul:  1 L = 2 1 0 1 2  0 0 1  2 R = 0 0 Minden lépés egyértelm¶en meghatározott volt és nem volt olyan lépés ahol ne tudtuk volna folytatni az eljárást. Az eredeti A mátrix egy bizonyos elemére támaszkodunk és abból az elemb®l kivonjuk a megfelel®en összeszorzott számpárokat amelyeket már korábban megismertünk és így kapjuk R megfelel® értékét. rjk = ajk − j−1 X ljp rpk k = j, j + 1, . , n (5.1) p=1 L megfele® elemének kiszámításánál rjj -vel még osztanunk kell és ez az osztás a kritikus m¶velet az eljárásban. Ha rjj 0 lenne akkor ezt nem tudnánk végrehajtani j−1 lij = X 1 (aij − lip rpj ) i = j + 1, j + 2, . , n rjj

p=1 j = 1, 2, . , n (5.2) M¶veletigény A m¶veletigényt két részletben fogjuk számolni. Az egyik számítás az lesz, hogy mennyi m¶velet kell az R elemeinek a kiszámításához, ez lesz M1 érték és a kés®biekben meghatározzuk az L elemeihez tartozó m¶veletigényt is. (51)-ben j − 1 darab összevonás (ami összeadást és/vagy kivonást jelent) és j − 1 szorzás van1 M1 (n) = n X 2(j − 1)(n − j + 1) = j=2 = n−1 X l=1 n X 2(j − 1)(n − (j − 1)) j=2 2l(n − l) = n−1 X l=1 2ln − 2l2 = 2n n−1 X l=1 +2 n−1 X l2 l=1 (n − 1)n) (n − 1)n(2(n − 1) + 1) 2n3 − 3n2 + n = 2n −2 = n3 − n2 − 2 6 3 1 3 2 = n + O(n ) 3 Megjegyzés. Érdemes m¶veletigény els® sorát megvizsgálni. Azt állítottuk, hogy j − 1 darab összevonás és Pj−1 miatt) (5.1) kiszámításánál ezért szerepel a m¶veletigényben j − 1 darab szorzás kell a minden lépésben ( p=1 P P 2(j − 1), egészen pontosan a -as részben eggyel

kevesebb összeadás szerepel, mint szorzás de a el®t ott 1 ez a könyv a szorzást és az összeadást már egyenrangúnak veszi hiszen egy korszer¶ processzor 1 órajel alatt végzi el mind az összeadást mind a kivonást (szemben a régiekkel, ahol a szorzás ideje többszöröse volt az összeadásénak) AZ LR FELBONTÁS FELHASZNÁLÁSI LEHETŽSÉGEI 22 van még egy kivonás is. A vizsgált sorban j elemt®l mindegyik elemre (k = j, , n) kell a m¶veleteket végrehajtani R-ben ezért jön be az (n − j + 1)-es szorzó. Ezzel megkaptuk R egy sorának a kiszámításához szükséges m¶veletigényt. P Mivel ezt minden sorra végre kell hajtani ezért jön be a , pontosabban az els® sorra nem kell végrehajtani mivel P j = 1 esetén a (5.2)-es képlet r1k = a1k bemásolásra redukálódik, ezért indul j = 2-r®l az indexelés ( nj=2 ). Az els® sorról a másodikra úgy jutunk, hogy l = j − 1-et behejetettesítünk, majd a második sorról a harmadikra úgy, hogy

felhasználjuk az els® n egész szám és az els® n négyzetszám összegének a már ismert ), csak itt most n − 1-re alakalmazzuk ®ket. Huh, azt hiszem ezt egy kicsit képleteit ( 21 n(n + 1) és n(n+1)(2n+1) 3 túlmagyaráztam, a rövidebb változat megtalálható a könyv 50. oldalán (A szerkesztget®) Az O (ejtsd ordó) egy nagyságrendet mutató kifejezés. Jelen esetben az utolsó sor azt mutatja, hogy az A n × n mátrix n rendjét®l milyen módon függ a m¶veletigény, ez egy polinomiális függés lesz, a legnagyobb fokú tag az n3 aminek az együtthatója 13 (nyilván ez a rész lesz a domináns) és a mögötte lév® O(n2 ) azt jelenti, hogy vannak további tagok melyek együtthatói legfeljebb másod fokúak és ezekkel már nem foglalkozunk. Az L mátrixbeli értékek meghatározásához egy hasonló értéket fogunk kapni. A különbség az elöz®höz képest az, hogy bejön még egy plusz osztás és soronként eggyel kevesebb elemre kell végrehajtani, ez

azonban a m¶veletigényt nem fogja jelent®sen befolyásolni. M2 (n) = n X (2(j − 1) + 1)(n − j) = j=2 1 3 n + O(n2 ) 3 A teljes m¶veletigény a müveletigények összege: M (n) = M1 (n) + M2 (n) = 2 3 n + O(n2 ) 3 Ez a m¶veletigény hasonló a Gauss-elimináció m¶veletigényéhez. Nem véletlenül, hiszen a felbontás ekvivalens az elimináció megoldásával. 5.2 Az LR felbontás felhasználási lehet®ségei 1. Determináns számítás det(A) = det(L) · det(R) = 1 · det(R) A determinások szorzástételét használjuk itt ki. Mivel L alsó egység trianguláris ezért a determinánsa 0. Mivel R fels® trianguláris ezért a determinánsa könnyen számítható, a f®átlójában lév® elemek szorzataként. 2. Egyenletrendszer megoldásához  Ax = a ⇔ LRx = a ⇔ Ly = a Rx = y "el®re" helyettesítés O(n2 ) visszahelyettesítés O(n2 ) Ax = a-t vele ekvivalens problémává alakítjuk. Ez el®rehelyettesítésnél egy "fordított"

vissza helyettesítésr®l van szó, hogy mivel L speciális alakú ezért az y vektor komponensei az elöz® sor segítségével egyértelm¶en kifejezhet®k, az els® komponens pedig triviálisan kifejezhet®. Ha már y ismerlyük akkor azt be tudjuk helyettesíteni a második egyenl®tlenségbe amit egy egyszer¶ visszahelyettesítéssel meg tudunk oldani. Mindkét egyenletrendszer megoldásánál O(n2 ) m¶veletigény szükséges. 3. Mátrix inverzének a meghatározása A−1 = R−1 L−1 Egyszer¶bb R-nek és L-nek az inverzét meghatározni. R inverze is fels® tranguláris lesz és L inverze is alsó tranguláris lesz. LR FELBONTÁS SPECIÁLIS ALAKÚ MÁTRIXOKRA 5.3 LR 23 felbontás speciális alakú mátrixokra 5.2 Következmény Ha az A mátrix diaginiálisan domináns, akkor az A = LR felbontás egyértelm¶en létezik Bizonyítás. Itt arról van szó, hogy a (52) képletben lév® osztás során nem fordulhat el®, hogy 0 szerepel az osztóban, mivel a

f®minorok mind pozitívak lesznek. A bizonyitás a (43)-as tételb®l következik, a diagonális dominencia tulajdonsága miatt. • Hessenberg mátrix: lásd 1. el®adás tridiagonális mátrix: a f®átló és a két mellékátló csak a 0-tól különböz®. • bidiagonális mátrix : a f®átló és az egyik mellékátlója csak a 0-tól különböz®. 5.3 Segédtétel Ha a H reguláris fels® Hessenberg mátrixnak létezik H = LR felbontása, akkor L alsó egység • bidiagoniális mátrix. Bizonyítás. A regularitási feltételb®l következik, hogy rjj 6= 0 Az lij = 0 ha i > j + 1 egyenl®tlenségeket az oszlopok szerinti indukcióval bizonyítjuk. j = 1 (az els® oszlopra)2 teljesül az állítás, li1 = hi1 /r11 = 0 mivel hi1 ha i > 2. Tegyük fel, hogy az 1, 2, , j − 1 oszlopokra beláttuk az állítást Ekkor j−1 lij = X 1 1 (hij − lip rpj ) = (0 − 0) = 0, rjj r jj p=1 Mivel hij = 0 és az összeg is 0 az indukciós feltétel miatt. 5.4

Segédtétel Ha a G reguláris alsó Hessenberg mátrixnak létezik G = LR felbontása, akkor R fesl® bidiagoniális mátrix Bizonyítás. Transzponálással visszavezetjük az elöz® esetre: 1 z }| { −1 −1 −1 G = R L = (R diag(r11 , r22 , . , rnn ))(diag(r11 , r22 , . , rnn ) LT ) = L∗ R∗ T T T T Mivel a levezetés végén a GT fels® Hessenber-mátrix felbontása áll, L∗ az elöz® segédtétel alapján csak alsó −1 −1 −1 egység bidiagonális mátrix lehet, mivel L∗ -ot L∗ = RT diag(r11 , r22 , . , rnn ) módon adódik és denicóból látszok, hogy R fels® bidiagoniális mátrix kell, hogy legyen. Az elöz® két segédtételb®l következik a következ®: 5.5 Segédtétel Ha a T reguláris tridiagoniális mátrixnak létezik T = LR felbontása, akkor L alsó egységbidiagoniális, R pedig fels® bidiagoniális mátrix. 5.6 Következmény Ha létezik a reguláris A mátrix A = LR felbontása és (i) A (fels® vagy alsó) Hessenberg-mátrix,

akkor a felbontás m¶veletigénye O(n2 ) (ii) A tridiagoniális mátrix, akkor a felbontás m¶veletigénye O(n). A probléma az algoritmus végrehajtása során akkor adódhat, ha rjj = 0 valamely j -re, azaz a mátrix valamelyi f®minora3 0. Ez viszont kezelhet® egy a f®elemkiválasztáshoz hasónló módszerrel 5.7 Példa ( 01 12 ) ebben az esetben az algoritmus közvetlenül nem végrehajtható Jelen példánknál annyit kellene csinálni, hogy a két sort meg kellene cserélni. Egy permutációs mátrixot fogunk használni. A G eliminácóban használt sor-oszlop cserélgetést írja le a permutációs mátrix 5.8 Deníció P A = LR az A ∈ Rn×n mátrix általánosított tranguláris felbontása, ha P permutációs R fels® tragnuláris, L alsó egység-tranguláris mátrix. -ben az egyes lépések sorokra, L-ben oszlopokra vonatkozi a j index. a f®minor fogalom alatt átalában aldeterminánst értenek 2R 3 AZ RT R CHOLESKY-FELBONTÁS 24 Az ötlet az, hogy ha az

adot pozicióba nem tudunk egy nullától eltér® elemet becserélni, akkor az aktulás oszlopban teljesen egészében 0-k kellenek, hogy legyenek, ha viszont ez áll fenn akkor a mátrix nem lehet reguláris. Megfordítva a dolgot, mivel csak reguláris mátrix esetén van ennek a felbontásnak értelme ilyenkor ezt a trükköt pedig mindig meg tudjuk csinálni. 5.9 Segédtétel Tetsz®leges A reguláris mátrixhoz megadható olyan P permutációs mátrix, hogy a B = P A mátrixra det(Bkk ) 6= 0 Bizonyítás. B mátrix rendje szerinti indukcióval bizonyítjuk Ha n=1, akkor az állítás triviálisan igaz mert 1×1- es mátrix esetén nincs mit cserélni. Tegyük fel, hogy az n − 1 rend¶ mátrixokra az állítás igaz! Vegyünk egy tesz®leges n-ed rend¶ A mátrixot, fejtsük ki A-t az utolsó oszlopa szerint, azaz határozzuk meg A determinánsát, az utolsó oszlop elemei és az adjungált aldeterminánsok segítségével mindenütt a megfelel® el®jelet gyelembe véve. 0

6= det(A) = (−1)2n ann det(Ann ) − an−1n det(An−1,n ) ± · · · + (−1)n a1n det(A1n ) Mivel ez az összeg nem 0 (hiszen A reguláris) ezért léteznie kell legaláb egy olyan j indexnek, hogy det(Ajn ) 6= 0. Legyen j egy ilyen rögzített index és tekintsük azt a P1 permutációs mátrixot, amivel A balról szorozva Ajn sorai felkerülnek A els® n − 1 sorába. Mivel Ajn n − 1-ed rend¶ reguláris mátrix ezért az indukciós feltevés szerint már van olyan P2 n − 1-ed rend¶ permutációs mátrix, hogy a  B=  0 P1 A 1 P2 0T mátrix f®minorai n − 1-ed rendig nem 0-k. Persze det(B) = ± det(A) 6= 0 is igaz, ezért  P = P2 0T  0 P1 1 mátrixszal való szorzás a kívánt B mátrixot adja. Megjegyzés. P1 -nek az a szerepe, hogy n − 1-ig reguláris legyen A, P2 az indukciós feltételeben szerepl® P , tehát A sorait úgy cserélgeti n − 1-dik sorig, hogy a f®minorok ne legyenek 0-k. Ez a segédtétel lényegében már bizonyítja a következ®

tételt is. 5.10 Tétel Egy tetsz®leges A reguláris mátrixnak létezik P A = LR felbontása Ez bizonytható algoritmikus úton is (végighaladva az algoritmus lépésein) annak a felhasználásával, hogy a részleges f®elemkiválasztásos Gauss-elimináció tetsz®leges reguláris mátrixra végrehajtható. 5.4 Az RT R Cholesky-felbontás Szimmetrikus A esetén szeretnénk egy speciális LR felbontás alkalmazni úgy, hogy két azonos mátrixra bontsuk fel A-t. 5.11 Példa A 2-al keretezett elemeket keressük RT felesleges feljegyezni, hiszen az értékek megegyeznek az R értékeivel. R RT r11 r12 r13 0 r22 r23 0 0 r33 r11 0 0 4 2 4 r12 r22 0 2 10 5 r13 r23 r33 4 5 6 1. 2. 3. A AZ RT R CHOLESKY-FELBONTÁS 25 r11 · r11 r11 r11 · r12 r12 r11 · r13 r13 r12 · r12 + r22 · r22 r22 r12 · r13 + r22 · r23 1 · 2 + 3 · r23 r33 r13 · r13 + r23 · r23 + r33 · r33 r33 Tehát = 4 = 2 = 2 = 1 = 4 = 2 = 10 = 3 = 5 = 5 = 1 = 6 = 1  2 1 2 R = 0 3 1 0 0 1 

Megjegyzés. Eddigi észrevételeim alapján a Cholesky felbontás valahogy így m¶ködik • Elég csak az R mátrixszal foglalkozni. • Sorra kitöltjük R sorait felülr®l lefelé haladva. • Egy soron belül balról jobbra haladunk, természetesen csak a f®lóban lév® elemt®l. • Adott sor f®átlóban lév® elemét úgy kapjuk, hogy vesszük a megfelel® f®átlóbeli elemet A-ból, majd kivonjuk R-ben a meghatározandó elem feletti elemek négyzetének összegét (kivéve az els® sort, mert akkor ez a lépés kimarad) és az így kapott összegb®l négyzetgyököt vonunk. (Csak a pozitív el®jel¶ gyököt vesszük gyelembe.)   r11 0  0  . . Tehát r33 a következ®képpen kapható meg: r12 r22 0 . . r13 r23 r33 . . r14 r24 r34 . . . .   .   . q 2 + r2 ) r33 = + a33 − (r13 23 • Egy f®átlótól jobbra lév® elemet úgy számítunk, hogy vesszük R-ben sorra a f®átló feletti és az adott elem feletti elemek

szorzatát (csak az azonos sorban lév®ket szorozzuk össze) és kivonjuk a számítandó elemnek megfelel® A beli elemb®l ®ket. Végül leosztjuk az aktuális R-beli f®átlóbeli elemmel (az els® sorban csak a f®tlóbeli elemmel kell leosztani a megfelel® A beli elemet). Például r34 a következ® módon kapható meg: r34 = • a34 − r13 · r14 − r23 · r24 r33 Ha tévedtem, akkor majd kiigazít valaki (A szerkesztget®) AZ RT R CHOLESKY-FELBONTÁS 26 5.12 Segédtétel Ha az A reguláris mátrixnak (nem feltétlenül szimmetrikus) létezik az LR felbontása, akkor egyértelm¶en létezik olyan trianguláris. LDS felbontása, ahol D diagonális, L alsó egység-trianguláris és S fels® egység- Lényegében arról van szó, hogy az R mátrixot átalakítjuk úgy, hogy a f®átlóbeli elemeket kigyüjtük a D mátrixba. S -t úgy kapjuk, hogy R-t elosztjuk D-vel Diagonális mátrixnak egyszer¶en számolható az inverze, a f®átlóbeli elemek reciproka.

5.13 Segédtétel Ha az A szimmetrikus mátrixnak létezik LR felbontása, akkor létezik RT R Cholesky-felbontása is. Bizonyítás. Mivel A szimmetrikus mátrix ezért A = AT és az elöz® segédtételben leírt felbontás létezik Az egyértelm¶ség csak akkor lehet felírható az LDS = A = AT = (LDS)T = S T DLT √ igaz, ha az L = S T -vel. Tehát D-t véve (a f®átlóban lév® elemek gyöke) √ √ √ √ √ √ A = S T DS = S T D DS = (S T ( D)T )( DS) = ( DS)T ( DS) √ amelyb®l az R def = DS denicóval látható az A = RT R Cholesky-felbontás. Ha a R diagonálisában negatív elemek is el®fordulnak, akkor a D mátrix megfelel® elemei tiszta képzetes számok lesznek, ekkor a Cholesky felbontás komplex mátrixot eredményez. 5.14 Tétel Csak szimmetrikus mátrixnak létezik Cholesky felbontása Bizonyítás. Mivel ha létezik az A = RT R, akkor AT = (RT R)T = RT (RT )T = RT R = A Cholesky-felbontás egyértem¶sége 5.15 Állítás Ha adott az A = RT R

Cholesky felbontás, akkor tetsz®leges olyan diagonális mátrixot véve, amelyre D2 = I , az A = (RT DT )(DR) is érvényes. Lenyegében ugyan ezt fogalmazza meg a következ® tétel. 5.16 Tétel Tetsz®leges A ∈ Rn×n szimmetrikus reguláris mátrix A = RT R felbontása R sorainak el®jelét®l eltekintve egyértelm¶. Bizonyítás. Legyen A = R1T R1 = R2T R2 az A két különböz® felbontása! Mivel a felbontásban szerepl® minden mátrix reguláris: (R2T )−1 R1T = R2 (R1 )−1 Így a bal oldal alsó a jobb oldal fels® trianguláris, ami csak úgy lehetséges, ha D = (R2T )−1 R1T = R2 (R1 )−1 | {z } | {z } B Ekkor viszont B J J z }| { z }| { D2 = DDT = (R2T )−1 R1T ( R2 (R1 )−1 )T = (R2T )−1 R1T (R1T )−1 R2T = I | {z } I | {z } I vagyis djj = ±1. Tehát R2 = DR1 AZ RT R CHOLESKY-FELBONTÁS 27 5.17 Tétel Ha létezik az A valós mátrix A = RT R felbontása, akkor 2 2 2 2 det(Ak k) = det(Ak−1,k−1 )rkk = r11 r22 · · · rnn Bizonyítás. A

(44)-es segédtételhez hasonló particionálással4 Az eddigi eredményeket foglalja össze a következ® tétel: 5.18 Tétel Tetsz®leges valós, szimmetrikus, reguláris A mátrixra a következ® két állítás ekvivalens: (i) Létezik az A = RT R Cholesky-felbontás. (ii) det(Akk ) 6= 0 bármely 1 ≤ k ≤ n-re. Bizonyítás. Az el®z® tételek felhasználásával bizonyítható: (i) ⇒ (ii) (ii) ⇒ (i) Az el®z® segédtétel alapján bizonyítható. Az 5.13 segédtétel és a 43 tétel alapján bizonyítható Megjegyzés. Ezt az el®adást dr Csendes Tibor tartotta 19991014-én Az el®adás nagy mértékben a könyvre támaszkodott. 4 a könyvben is csak a korábbi 4.14-es segédtételre van hivatkozás Fejezet 6 6.1 Cholesky-felbontás (eddig tanultak összefoglalása) 6.1 Feladat A kérdés az, hogy ha egy A mátrixot fel tudunk bontani LR alakra és ha ez az A mátrix szimetrikus nem tudjuk-e egyszer¶síteni a felbontást két "azonos" mátrix

szorzatára? Erre a kérdésre a Cholesky-felbontás a válasz. Cholesky felbontás arról szól, hogy az A mátrix RT R alakban felbontható-e (azaz két azonos mátrix szorzatára), és szimmetrikus mátrixok esetében nem tudnánk-e ezt az egész felbontást egyszer¶síteni 1. Ha A reguláris mátrix és ennek az A-nak létezik (és ezt tudjuk, hogy létezik) egy LR felbontása, akkor létezik az A-nak egy olyan felbontása amit úgy tudunk felírni, hogy LDS . Ahol D digaonális L alsó S fels® egység trianguláris mátrix tehát az R-ben lév® diagonális elemeket egy D mátrixba rakjuk be. 2. A legyen szimmetrikus, tehát AT = A-val, és reguláris mátrix A-nak ekkor létezik A = LR felbontása, azonban ekkor A-nak létezik Cholesky-féle felbontása √ is azaz A el®áll RT R el®állításával. A bizonyításban √ az az érdekes, hogy R DS formában áll el®, ahol a D a diagoniálisokból vont négyzetgyök. 3. Csak szimmetrikus mátrixoknak létezik Cholesky-féle

felbontása Ez azért van mert, ha A-t feltudom bontani A = RT R alakban és megnézem, hogy igazából mivel egyenl® AT , akkor azt kapom, hogy A-val egyenl®. AT = (RT R)T = RT (RT )T = RT R = A Így csak szimmetrikus mátrixok esetén van annak értelme, hogy Cholesky féle felbontásról beszéljünk. 4. Legyen a D egy olyan mátrix, amelyre D2 = I Ilyen D több létezik hiszen, ha csak egyesek vannak a f®átlóban és az egyesek el®jelét változtatgatva D-t önmagával megszorozva mindig egység mátrixot kapunk. Tehát D2 = I -nek több megoldása van Ekkor A = RT R = RT IR = RT D2 R = (RT DT )(DR) Mivel D-nek ±1 lehet az el®jele látszik, hogy ez a felbontás nem lehet egyértelm¶, mégpedig az történik, hogy ahol + és - van ott a megfelel® sorok megváltoztatják az el®jelüket. Tehát az lehet kimondani, hogy a Cholesky felbontás R sorainak el®jelét®l eltekintve egyértelm¶. 5. R sorainak el®jelét®l függetlenül meghatározható 6. Ha az A mátrixnak

létezik Cholesky féle felbontása, akkor az Akk aldetermináns úgy határozható meg, 2 hogy veszem az aldetermináns Ak−1,k−1 -et és megszorzom rkk -el, ebb® a rekurzív denícóból az is következik, hogy det(Akk ) úgy határozható meg, hogy veszem az r-ek produktumát. 2 det(Akk ) = det(Ak−1,k−1 )rkk = k Y 2 rii i=1 7. Az A = RT R Cholesky felbontás, akkor és csak akkor létezik, ha det(Akk ) 6= 0 Ha az RT R felbontás létezik, akkor a 6-ik megfontolás alapján azt modhatjuk, hogy det(Akk ) nem 0, mivel ez nem más, mint négyzetszámok szorzata. A másik irány az LR-ra vontatkozó tétel1 valamint a "Ha A szimmetrikus 1 A reguláris mátrixra a következ® két állítás ekvivalens: (i) egyértelm¶en létezik az A = LR felbontás (ii) det(Akk ) 6= 0 minden 1 ≤ k ≤ n-re. 28 CHOLESKY-FELBONTÁS FOLYTATÁSA 29 mátrixnak létezik LR-felbontása, akkor létezik Cholesky-felbontása is." segédtétel alapján, tehát a 2-ik megfontolás

alapján mondhatjuk azt, hogy det(Akk ) 6= 0 következik a az A = RT R Cholesky felbontás létezése. 6.2 Cholesky-felbontás folytatása 6.2 Következmény (426) Ha A diagonális domináns és szimmetrikus (a digagonális domináns mátrixokról elmondhatjuk, hogy nem elfajulóak, 27 tétel), akkor A-nak létezik Cholesky felbontása (az elöz® tételb®l következ®en). A 2-es megfontolás esetén azt mondtuk, hogy ha AT = A-val, A-nak létezik LR felbontása, akkor A√-nak létezik Cholesky felbontása és az R-et konstruktív módon állítottuk el®, méghozzá azt mondtuk, hogy ez DS lesz. Ez a D nem más, mint az R-nek a f®átlójában lév® elemei Ez nem biztos, hogy pozitív el®jel¶, ha nem pozitív el®jelü, akkor negatív számból kell gyököt vonni, ami azt jelenti, hogy képzetes számok is el®jönnek a Cholesky féle felbontásnál. Tehát ha az A-ról csak azt tudom, hogy ® szimmetrikus és létezik az LR felbontása, ez még nem garantálja azt, hogy

valós aritmetikával meg tudom oldani. A következ® tétel erre vonatkozik 6.3 Tétel (428) Ha az A-nak létezik A = RT R Cholesky-féle felbontása, akkor R bármely sora vagy valós vagy tiszta képzetes elemekb®l áll. √ A D-vel való szorzás azt jelenti, hogy a f®átló elemei vagy képzetes vagy valós számok (attól függ®en, hogy a f®átlóban pozitív vagy negatív elem volt) és ez azt jelenti, hogy ha megszorzom a mátrixot, akkor a képzetesek éppen a sorokra terjednek ki és a megfelel® oszlopokra. Bizonyítás. Tehát A-t A = RT R módon tudom felírni Az RT R felbontás egy tesz®leges ajk elemre nézve a következ®t jelenti: ajk = j X (6.1) rlj rlk l=1 Ez jelenti azt, hogy a transzponáltal szorzom meg az R mátrixot. Ha k = j -vel: ajj = r1j r1j + r2j r2j + · · · + rj−1,j−1 rj−1,j−1 +rjj rjj | {z } Pj−1 l=1 2 (a) rjj = ajj − j−1 X 2 rlj 2 rlj l=1 Ha k 6= j -vel: (b) rjj rjk = ajk − j−1 X rlj rlk l=1 vagy valós

vagy tiszta képzetes lesz a szerint, hogy az (a) képlet jobb oldalán pozitív vagy negatív számjön ki. Ezután vizsgáljuk a (b) képletet, itt rjj Kell-e komplex aritmetikát használni? Az állításunk az, hogy nem szükséges, mert az A = RT R helyett az A = S T D2 S -t fogjuk használni, ahol a D2 az valós szám lesz és a D nem más, mint az R-eknek a diagonálisában lév® elemei. A kérdés továbbiakban az, ha már van ilyen felbontásunk, akkor mit tudunk mondani az egyértelm¶ségr®l? Mikor tudnák biztosítani a Cholesky féle felbontás egyértelm¶ségét? Arra már választ kaptunk, hogy a felbontás el®jelt®l függ®. Ezért, hogy az egyértelm¶séget biztosítsuk, be kell vezetni a kanonikus felbontásnak a fogalmát 6.4 Deníció Ha A egy n × n-es szimmetrikus mátrix, az A = RT R Cholesky féle felbontást, akkor nevezzük kanonikusnak, ha R valós mátrix, továbbá a f®átl®jában lév® elemek mind pozitívak. CHOLESKY-FELBONTÁS

FOLYTATÁSA 30 A következ® tétel a kanonikus felbontás egzisztenciájára és unicitására ad feltételt. 6.5 Tétel Ha A szimmetrikus valós mátrix, akkor a következ® két állítás ekvivalens: (i) egyérelm¶en létezik a Cholesky féle kanonikus felbontás (ii) az aldeterminánsok mind pozitívak (det(Akk ) > 0 bármely 1 ≤ k ≤ n-re). Bizonyítás. (i) ⇒ (ii) Mivel a det(Ann )-r®l tudjuk, hogy az nagyobb, mint nulla, mivel r2 -ek szorzata Innen következik, hogy det(Akk ) > 0, tehát nem fajul el. Gyakorlatilag az egyik lépést elintéztük, a másik lépés az sokkal érdekesebb. Ha det(Akk ) > 0,akkor miért mondhatjuk azt, hogy az A = RT R kanonikus felbontás létezik és egyértelm¶? (ii) ⇒ (i)A bizonyítást teljes indukcióval fogjuk végezni. Felvesszük az A mátrixot és felbontjuk A = RT R szorzatra a következ® módon:  A= An−1,n−1 bT  b ann  = T Rn−1,n−1 rT   Rn−1,n−1 · rnn 0T 0 r  rnn Ahonnan a megfelel®

elemekre a következ®k teljesülnek: An−1,n−1 T = Rn−1,n−1 Rn−1,n−1 b = T = = b ann T Rn−1,n−1 r T r Rn−1,n−1 2 rT r + rnn (az elöz® transzponáltja) (6.2) (6.3) (6.4) (6.5) Az indukciós feltevés miatt egyértelm¶en létezik a (6.1)-et kielégít® valós reguláris Rn−1,n−1 mátrix Ekkor viszont a (6.2) lineáris egyenletrendszert az r ismeretlenre megoldva már egyértelm¶en adódik a valós r vektor is, ami kielégíti a (6.3)-at is Meg kellene oldani az r-re és meg kellene nézni, hogy az r vektor milyen ispMert annak kellene teljesülnie, hogy ez egy valós szám. (64)-b®l rnn -t kifejezve a következ®t kapjuk rnn = + ann − rT r Be kell látnunk, hogy rnn valós és nagyobb egyenl® min 0. Az A determinánsról tudjuk, hogy határozottan nagyobb, mint 0 és a determinánsok szorzástételét kihasználva: T 2 0 < det(A) = det(Rn−1,n−1 )rnn det(Rn−1,n−1 )rnn = det(Rn−1,n−1 )2 rnn Mivel mátrix és transzponáltjának

determinánsa ugyan az. A kifejezésb®l látszik, hogy nem lehetséges, hogy rnn kisebb legyen, mint 0. Ezzel azt láttuk, hogy a kanonikus felbontás segít nekünk abban, hogy az egyértelm¶séget biztosíthassuk. A következ®kben általánosabb dolgokkal foglalkozunk. Megvizsgáljuk a Cholesky féle felbontás denitséggel szemidenitséggel való kapcsolatát. 6.6 Segédtétel Tekintsünk egy S valós n × m-es mátrixot (1 ≤ m ≤ n) és ez a mátrix legyen oszlopreguláris (tehát lineáris kombinációkkal az egyik oszlop nem fejezhet® ki a többiek segítségével) ezután képezzük A = S T S mátrixot, ez már m × m-es mátrix lesz, ez a mátrix pozitív denit. Bizonyítás. Az els® megfontolás az, hogy az így kapott A mátrix az szimmetrikus Ez elég egyszer¶ mert csak azt kell megnézni, hogy AT = A? AT = (S T S)T = S T (S T )T = S T S = A Az mondható, hogy az S T S az mindig szimmetrikus. A pozitív denitséghez azt kell megnézni, hogy az xT Ax

nagyobb-e, mint 0? xT Ax = xT (S T S)x = (xT S T )(Sx) = (Sx)T (Sx) = y T y = kyk22 ≥ 0 Egy vektort kaptunk (y), azért mert egy mátrixot szorzotunk vektrorral. Ahhoz, hogy belátsuk a pozitív denitséget be kell látni, hogy y = 0 csak akkor lehetséges, ha x = 0. Az y vektor nem más, mint az Sx Az Sx-r®l azt mondtuk, hogy oszlopreguláris, azaz ez egy olyan egyenletrendszer amelyiknek van megoldása. Mivel az egy nem elfajuló mátrix az ilyennek a 0 megoldása csak akkor léphet fel, ha a másik oldal 0. Ezzel be is fejeztük a bizonyítást mert itt használtuk ki az oszlopregularitásnak a lényegét. QR ORTOGONÁLIS-TRIANGULÁRIS FELBONTÁS 31 6.7 Következmény Ha az A = RT R valós Cholesky felbontás létezik, akkor A pozitív szemidenit 6.8 Tétel Tetsz®leges A szimmetrikus mátrixra a következ® állítások ekvivalensek: (i) A pozitív denit (ii) Akk pozitív denit (iii) det(Akk ) ≥ 0 (iv) (a Cholesky-felbontás egyértelm¶sége) az A = RT R kanonikus

és egyértelm¶ (v) A = S T S , ahol S reguláris mátrix Bizonyítás. (i)⇒(ii) A-ról azt mondjuk, hogy pozitív denit, ekkor xT Ax > 0-nak kell teljesülnie. Ha most tekintünk egy z vektort és a z T Akk z -t, ekkor z T Akk z = y T Ay > 0, az a kérdés, hogy hogyan válaszuk meg ezt az y -t? ( yi = zi ha i ≤ k 0 ha i > k (ii)⇒(iii) Akk -ról tudjuk, hogy pozitív denit minden k-ra, akkor be kell látni, hogy det(Akk ) > 0. Ha Ak k pozitív denit, akkor azt mondhatjuk az ® sajátérékeir®l, hogy mind pozitív. A determinánsát pedig úgy lehet kiszámítani sajátértékei segítségével, hogy vesszük a sajátértékek szorzatát. Ebb®l következ®en A determinánsának nagyobbnak kell lennie, mint 0. det(Akk ) = k Y λj (Akk ) > 0 j=1 (iii)⇒(iv) Ha det(Akk ) > 0, akkor egyértelm¶en létezik az A = RT R kanonikus felbontás. Ezt viszont már bizonyítottuk a 6.5 tételben (iv)⇒(v) választható például S = R (v)⇒(i) 6.6

segédtétel következménye, ugyanis ha S reguláris, akkor oszlopreguláris is 6.3 QR ortogonális-trianguláris felbontás Az R szokás szerint fels®trianguláris mátrix aminek a f®átlója alatt 0-k szerepelnek. Q egy ortogonális mátrix, transzponáltja éppen az inverzet adja (QT = Q−1 ). A különböz® felbontások összefügnek azzal, hogy a különböz® lineáris egyenletrendszerek hogyan oldhatók meg. Ha a mátrixban egy kis értéket megváltoztatunk, akkor a megoldások hogyan viselkednek? Szemléletesen a lineáris egyenletrendszerek megoldása nem más, mint egyenesek metszéspontjának a megkeresése. Ha az egyenesek közel párhuzamosak és egy kicsit megmozgatjuk ®ket, akkor a megoldásokban nagyon nagy változások lehetnek. A mátrixokat jó lenne jellemezni, hogy mennyire stabilak a felbontásokra, az egyenletrendszerek megoldására vonatkozólag. Ha ortogonális triangulizációt végzünk el, akkor a stabilitás nagyon nagy fokú szemben a másik

esetekkel. 6.9 Deníció Az A = QR felbontásokat nevezzük ortogonális-trianguláris felbontásoknak Az egzisztencia nagyon könnyen bizonyítható. 6.10 Tétel (Egzisztencia-tétel) Ha A reguláris, akkor létezik a QR-felbontás Bizonyítás. Vegyünk egy A reguláris mátrixot és deniáljuk a B mátrixot B def = AT A. AT A szimmetrikus és pozitív denit, tehát B -nek létezik Cholesky-felbonátsa azaz B = R R. Legyen Q = AR−1 Az a kérdés, hogy Q ortogonális-e? Q ortogonalitásához azt kell igazolni, hogy Q−1 = QT azaz QT Q = I . Tehát ki kell számítanunk QT Q-t. T QT Q = T (AR−1 )T (AR−1 ) = (R−1 )T |A{z A} R−1 = B = (R−1 )T BR−1 = (R−1 )T (RT R)R−1 = = ((R−1 )T RT )(RR−1 ) = II = I QR FELBONTÁS KISZÁMÍTÁSA 32 A bizonyítás konstruktív, hiszen megadja hogyan kell ezt a felbontás elkészíteni. Vesszük az A mátrixot, megszorozzuk a transzponáltjával és erre csinálunk egy Cholesky felbontást. A felbontás alapján

R-nek képezzük az inverzét amivel A megszorzozzuk és "máris" megkapjuk Q-t. Ez azonban eszméletlen sok m¶veletet igényelne tehát keresni kell egy másik fajta megoldást. El®bb azonban bebizonyítjuk, hogy egyértelm¶ a felbontás 6.11 Tétel (Unicitás) Tetsz®leges A reguláris mátrix QR felbontása Q oszlopainak és R sorainak el®jelét®l eltekintve egyértelm¶en meghatározható. Bizonyítás. Indirekt módon bizonyítjuk Tegyük fel, hogy A = Q1 R1 Q−1 2 Q1 QT2 Q1 = Q2 R2 = R2 R1−1 = R2 R1−1 a bal oldal ortogonális a jobb oldal fels® trianguláris, ez csak úgy lehetséges, ha V diagonális V = QT2 Q1 = R2 R1−1 Vizsgáljuk V 2 -et: V 2 = V V T = (QT2 Q1 )(QT2 Q1 )T = QT2 Q1 QT1 Q2 = QT2 Q2 = I | {z } | {z } I I hiszen az ortogonális mátrix transzponáltja megegyezik az inverzével. Tehát vjj = ±1 és Q2 = Q1 V , R2 = V R1 . 6.4 QR felbontás kiszámítása Az utosó téma, amivel foglalkozunk az el®adás alatt, hogy hogyan lehet

más módon megcsinálni a felbontást, mint a bizonyításban. Ez a módszer a 6.41 Gram-Schmidt-féle ortogonalizáció Legyen A egy reguláris mátrix. Jelöljük A oszlopvektorait a1 , , an -el Mivel ortogonális trianguláris felbontást akarunk végezni, ezét egy QR felbontást kell kapnunk, ahol Q oszlopait jelöljük (q1 , . , qn )-el, R pedig fels® trianguláris azaz:  r11  0 (a1 , a2 , . , an ) = (q 1 , q 2 , , q n )   .  . 0 r12 . r22 . . 0 . r1n   r2n   .   rnn Tehát A mátrix megfelel® elemeit úgy kapjuk, hogy Q-val megszorozzuk ezt az R mátrixot. Írjuk fel ezeket az egyenleteket a szorzás szabályai alapján. a1 a2 = r11 q 1 = r12 q 1 + r22 q 2 . . ak = r1k q 1 + r2k q 2 + · · · + rkk q k . . an = r1n q 1 + r2n q 2 + · · · + rkn q k + · · · + rnn q n Ezekben az egyenletekben az r-ek és a q-k az ismeretlenek q vektorokról viszont tudjuk, hogy ortogonálisak. QR-FELBONTÁS

ALKALMAZÁSAI 33 Az 1. és a 2 egyenlet megoldása Nézzük meg mivel egyenl® az aT1 a1 .Az els® egyenlet alapján: 2 T aT1 a1 = r11 q1 q1 2 mivel Q ortogonális ezért qT1 q1 = 1, tehát ha azt ortonormáltságot is hozzávesszük: aT1 a1 = r11 . Innen p T T r11 = + a1 a1 . a1 a1 mindig pozitív, mert a komponensek négyzetösszegével egyenl® Ekkor q 1 kifejezhet® az egyenletb®l: q1 = 1 a r11 1 Tehát eddig megvan r11 és q1 , a kérdés az, hogy hogyan tudunk továbbhaladni? A második egyenletben nem ismerjük r12 -t, r22 -t és q2 -t. De ha az egyenletet beszorozzuk qT1 -al, akkor mivel q T1 q 2 = 0 az ortonormáltság miatt q T1 q 1 = 1 szintén az ortonormáltság miatt, ezért az egyenlet a következ®képpen alakul: q T1 a2 = r12 , azaz r12 meghatározható. q2 meghatározásához el®ször határozzuk meg a b2 def = a2 − r12 q 1 vektort. Ekkor b2 = r22 q 2 , q 2 = r122 b2 . q 2 ebb®l az els® egyenletnél látottakhoz hasonlóan adódik, hogy bT2 b2 = r22 ,

így r22 = + bT2 b2 és A k. egyenlet megoldása Feltéve, hogy az el®z® egyenletek meg lettek oldva, azaz 1 ≤ i ≤ j < k-ra qj -t illetve rij -t már kiszámoltuk. Ekkor i = 1, 2, . , k − 1-re az egyenletet balról qTi -al szorozva az összes q elt¶nik, kivéve az rik -val való szorzást, tehát innen az rik meghatározható Azaz rik = q Ti ak qk i = 1, 2, . , k − 1 meghatározásához képezek egy bk vektort: bk = ak − (r1k q 1 + r2k q 2 + · · · + rk−1,k q k−1 ) Felhasználva a bk = rkk qk összefüggést a k-dik egyenlet alapján könnyen igazolható. De ekkor az els® q 1 2 egyenlethez hasonlóan bTk bk = rkk . Így rkk = bTk bk és qk = rkk bk . Ezzel az eljárással meghatározható a QR felbontás. A m¶veletigény n db gyökvonás és O(n3 ) aritmetikai m¶velet. 6.5 QR-felbontás alkalmazásai Vajon hogyan tudunk QR felbontás segítségével lineáris egyenleteket megoldani? Egy lineáris egyenletrendszert akarunk megoldani, azaz egy Ax = a

egyenletrendszert. Tudjuk, hogy A-t felbonthatjuk QR alakra azaz (QR)x = a. Az asszociativitás miatt vehetjük a Q(Rx) = a egyenletet Jelöljük Rx-et y -al, ekkor a Qy = a Rx = y egyenletekhez jutottunk. Mivel QT = Q−1 ezért az y meghatározható y = QT a egyenlet alapján Ezek után Rx = y egyenletrendszer visszahelyettesítéssel megoldható. Ha az A mátrix inverzeit akarjuk meghatározni, akkor az A−1 = R−1 QT képlet alapján csak egy felülr®l trianguláris mátrix inverzét kell meghatározni, azonban ez nem ad jelent®s m¶veletcsökkentést a standard algoritmushoz képest. Másik jelent®s felhasználás a sajátérték illetve sajátvektor számításnál van. Megjegyzés. Ezt az el®adást dr Dombi József tartotta 19991021-én Az el®adás nagy mértékben a könyvre támaszkodott. Fejezet 7 Sajátértékszámítás Adott A ∈ Cn×n mátrix. Meghatározandó az összes olyan λ ∈ C, amelyekhez van olyan x 6= 0, x ∈ Cn , hogy (7.1) Ax = λx 7.1

Deníció Az ilyen λ számokat A sajátértékeinek nevezzük; sajátvektoroknak nevezzük. Ax − λx = (A − λI)x = a λ-hoz tartozó x-eket a λ-hoz tartozó (7.2) (7.3) 0 0 (A−λI)x = 0 homogén lineáris egyenletrendszer x-re nézve ⇔ van (nem triviális) megoldása ha det(A−λI) = 0. Ebb®l következik, hogy λ akkor és csak akkor sajátérték, ha det(A − λI) = 0 (A − λI olyan diagonális mátrix melynek a f®átlójában a diagonális elemekb®l kivonjuk λ-t). 7.2 Deníció def PA (λ) = det(A − λI) thatós polinom). A az A mátrix karakterisztikus polinomja (n-ed fokú komplex együt- sajátértékei a PA (λ) = 0 egyenletnek a megoldásai lesznek. 7.3 Példa A = ( 10 11 ) 1 2 2 (A − λI) = ( 1−λ 0 1−λ ) PA (λ) = (1 − λ) = λ − 2λ + 1 det(A − λI) = PA (λ) =  a11 − λ   a21 det   .  . an1 a12 a22 − λ . . . . . an,n−1 a1n . . an−1,n ann − λ     = (−1)n λn + . 

 (−1)n (λn − α1 λn−1 − α2 λn−2 − · · · − αn−1 λ − αn ) (7.4) (7.5) A karakterisztikus polinom gyöktényez®s alakja a következ®képpen néz ki: PA (λ) = (−1)n (λ − λ1 )(λ − λ2 ) · · · (λ − λn ) PA (0) = (−1)2n λ1 λ2 · · · λn = det(A) β0 λn + β1 λn−1 + · · · + βn β0 (λ − λ1 )(λ − λ2 ) · · · (λ − λn ) β0 λn + · · · + β0 (−1)n λ1 λn {z } | βn 34 (7.6) (7.7) 35 7.4 Állítás Tetsz®leges A mátrixra (i) n P i=1 aii = α1 = n P λj j=1 (ii) (−1)n+1 αn = det(A) = Bizonyítás. (i) λn−1 Qn j=1 λj együtthatjójának (7.5) (74) és (76)-beli kifejtéséb®l adódik: (−1)n (−α1 ) = (−1)n+1 n X aii = (−1)n (−1) i=1 n X λj j=1 Ezt még szorozzuk (−1)n+1 -el és kész is vagyunk. (ii) (7.5) (74) és (76)-ben λ = 0-t helyettesítve: PA (0) = det(A − 0I) = det(A) = (−1)n λ1 λ2 · · · λn 7.5 Deníció Mátrix nyomán a f®átlójában lév®

elemek összegét értjük, jele:tr (trace) tr(A) = Pnj=1 ajj Egy mátrix akkor és csak akkor szinguláris, ha a sajátértéke 0. A PA (λ) = 0 egyenletre egzakt megoldást nem tudunk adni. Viszont ha egy mátrix trianguláris, akkor a f®átlóbeli elemei a sajátértékei. Homogén lineáris egyenletrendszerek megoldásai alteret alkotnak, ha van egy nemtriviális megoldásuk, akkor végtelen sok van. A sajátérték multiplicitása: algebrailag: a karakterisztikus polinom hányszoros gyöke; geometriailag: a hozzá tartozó saját altér hány dimenziós. Szimmetrikus valós mátrixoknak valós sajátértékei vannak. 7.6 Deníció Tetsz®leges T reguláris mátrix esetén az A 7 T −1 AT transzformációt hasonlósági transzformációnak nevezzük (lehet A 7 T AT −1 is) 7.7 Állítás A A 7 T −1 AT hasonlósági transzformáció meg®rzi a sajátértékeket Bizonyítás. Legyen B = T −1 AT PA (λ) = det(A − λI) I PB (λ) z }| { = det(B − λI) = det(T −1 AT

− λ T −1 T ) = det(T −1 (A − λI)T ) = det(T −1 ) det(A − λI) det(T ) | {z } PA (λ) = −1 det(T ) det(T ) PA (λ) {z } | I = PA (λ) 7.8 Deníció Két mátrix hasonló, ha az egyik hasonlósági transzformációval átvihet® a másikba Minden mátrix hasonló önmagával. Ha két mátrix hasonló, akkor sajátértékeik ugyan azok s a karakterisztikus polinomjaik is, de a fordítottja nem igaz. 7.9 Példa A = ( 10 11 ) B = ( 10 01 ) Mindkett®nek a sajátértéke 1 dupla multiplicitással (n=2) mégsem hasonlók 7.10 Deníció A diagonizálható, ha hasonló egy diagonális mátrixhoz 7.11 Deníció A triangulizálható, ha hasonló egy trianguláris mátrixhoz 36 7.12 Állítás (i) Nem minden mátrixot lehet diagonizálni. Pl: ( 10 11 ) (ii) A pontosan akkor diagonizálható, ha van n db lineárisan független sajátvektora (nem elfajuló) Bizonyítás. Ha az A sajátértékei λ1 , λ2 , , λn , és egy-egy sajátvektora x1 , x2 , , xn ekkor:

Ax = λ1 x1 , Ax2 = λ2 x2 , . , Axn = λn xn | 1 {z } AX=XD ahol  λ1   X = (x1 , x2 , . xn ) D =    λ2     . λn AX = XD ⇔ X −1 AX = D Ha minden sajátértéke A-nak különböz®, akkor diagonizálható, akkor van n db. lineárisan független sajátvektora. 7.13 Állítás A különböz® sajátértékeihez lineárisan független sajátvektorok tartoznak Bizonyítás. Indukcióval bizonyítjuk Ha k = 1, akkor az állítás triviális Tegyük fel, hogy k-ra igaz az állítás vizsgáluk k + 1-re: λ1 , λ 2 , . , λ n x1 , x2 , . , xn Lineárisan függetlenek lesznek-e? (Lineárisan független, ha csak a triviális lineáris kombinációval állítható el® a 0 vektor.) A/ α1 x1 + α2 x2 + · · · + αk xk + αk+1 xk+1 α1 Ax1 + α2 Ax2 + · · · + αk Axk + αk+1 Axk+1 α1 λ1 x1 + α2 λ2 x2 + · · · + αk λk xk + αk+1 λk+1 xk+1 = = = 0 0 0 α1 λk+1 x1 + α2 λk+1 x2 + · · · + αk λk+1 xk + αk+1 λk+1 xk+1 =

(7.8) Tekintsük a következ® egyenletet: (7.9) 0 Vonjuk ki a (7.7)-b®l (78)-at α1 (λ1 − λk+1 )x1 + α2 (λ2 − λk+1 )x2 + · · · + αk (λk − λk+1 )xk = 0 (7.10) Így már csak az els® k vektor szerepel az egyenletben. Mivel a sajátértékekr®l feltettük, hogy különböz®ek ezért λi − λk+1 nem adhatják ki a 0-t. Tehát a jobb oldal csak akkor lehet 0, ha α1 = α2 = · · · = αk = 0 7.14 Állítás (iii) Ha A minden sajátértéke különböz®, akkor diagoniziálható. 7.15 Állítás Tetsz®leges A mátrix triangulizálható 7.16 Deníció 7.17 Deníció Tetsz®leges A mátrixra a C = AH Az U mátrix unitér konjugált transzponált mátrix elemeire cik = āki mátrix, ha U H U = I . Fejezet 8 8.1 Mátrixok speciális alakra transzformálása A következ® tételben azt fogjuk igazolni, hogy tetsz®leges A mátrix hasonlósági transzformációval fels® trianguláris alakra hozható (trangulizálható). Azaz ennél többet

bizonyítunk mégpedig azt, hogy tetsz®leges unitér transzformációval triangulizálható A (az unitér hasonlósági transzformáció stabilabb, a kerekítési hibák jobban alakulnak). 8.1 Tétel (Schur-féle normálforma) Tetsz®leges A ∈ Cn×n -hez van olyan U ∈ Cn×n unitér és R ∈ Cn×n fels®trinaguláris mátrix, hogy U H AU = R Bizonyítás. A rendje szerinti teljes indukcióval bizonyítjuk A rendet n-el szoktuk jelölni (i) n = 1 ebben az esetben triviálisan 1A1 = R, ahol A és R 1 × 1-es mátrix (azon azonban el lehetne gondolkodni, hogy miben különbözik egy 1 × 1-es mátrix és egy komplex szám). (ii) tegyük fel, hogy az állítás minden n−1-ed rend¶ mátrixra igaz. Legyen A tesz®leges n-ed rend¶ mátrix A feladat az, hogy visszavezessük az elöz®re. Nyilván valamilyen partícionálással lehet visszavezetni Legyen 1 λ1 A-nak valamelyik sajátértéke, x1 olyan sajátvektor, p amelyre ||x1 ||2 = 1 (komplex vektor esetén a kettes H H nomrát a

következ®képpen értelmezzük: ||x1 ||2 = x1 x1 ahol x1 konjugált transzponáltat jelent). Ekkor a következ®ket mondhatjuk, van a Cn n dimenziós komplex vektortér. Ha vesszük az el®bbi x1 et, akkor ki lehet egészíteni bázissá, s®t többet is lehet mondani: ki lehet egészíteni ortogonális bázissá (páronként mer®legesek a vektorok). Valós vektortérben ezt már tudjuk, hiszen ha veszünk egy nem 0 vektort, akkor azt másik n − 1 darabbal alkalmas módon ki lehet egészíteni n elem¶ vektorrendszerré, ami bázisa Rn -nek, a helyzet ugyan ez Cn -re is. Tehát vesszük az x1 -et, ekkor ehhez lehet mondani további n − 1 darab vektort, hogy kapjak egy n elem¶ vektorrendszert, ami ortogonális vektorokból áll és bázisa a Cn térnek. Van olyan x1 , . , xn , hogy Cn ortonormált bázisa (lineárisan függetlenek és páronként mer®legesek), ekkor a következ® teljesül xH i xj = δij (tehát a skalárszorzat 0 ha i 6= j és 1 ha i = j ). Konstruáljuk meg

Q(x1 , . , xn ) mátrixot, ahol x1 , , xn oszlopvektorok Mit jelent az, hogy ennek a mátrixnak az oszlopvektorai ortonormált rendszert alkotnak? Ez pontosan azt jelenti, hogy QH Q = I . Ez viszont megegyezik azzal, hogy a Q mátrix unitér. Visszakanyarodva a bizonyításhoz, azt modhatjuk, hogy ha vesszük egy tetsz®leges sajátértékét A-nak, megy egy hozzá tartozó normált x1 sajátvektort, akkor ehhez lehet mondani n − 1 olyan további vektort, hogy ha ezeket összerakjuk, akkor kapunk egy unitér mátrixot. Mire jó ez? Számítsuk ki a QH AQ-t, pontosabban ennek az els® oszlopvektorát: QH A Qe1 = QH Ax1 = QH λ1 x1 = λ1 QH x1 = λ1 e1 |{z} | {z } x1 e1 ilyet lehet választani hiszen ha van egy sajátvektorunk akkor azt tetsz®leges nullától különböz® értékkel beszorozva újra sajátvektort kapunk. Ha ez az eredetileg vett sajátvektorra nem teljesült, akkor az ® hosszának a reciprokával kell beszorozni (ami valós konstans), hogy olyan sajátvektort

kapjunk, hogy ez teljesüljön. x̃1 := ||x1|| x1 (x1 irányába mutató egységnyi hosszúságú vektor) 1 1 37 2 MÁTRIXOK SPECIÁLIS ALAKRA TRANSZFORMÁLÁSA 38 Tehát azt kapjuk, hogy a mátrix els® oszlopában legfelül λ1 van alatta pedig csupa 0, tehát megadható ilyen alakban:    QH AQ =   λ1 bT 0 B    B ∈ C(n−1)×(n−1) és erre a B -re már tudjuk alkalmazni az indukciós feltevést. Az indukciós feltevésb®l következ®en, van olyan S ∈ C(n−1)×(n−1) unitér mátrix és V ∈ C(n−1)×(n−1) fels® trianguláris mátrix, hogy igaz S H BS = V . Hogyan lehetne ezzel befejezni a bizonyítást? B -re már tudjuk, hogy igaz, de n dimenzós mátrixokkal kellene dolgozni, ekkor ezeket "felfújjuk" csinálunk bel®le n dimenziósakat. S helyett és V helyett tekintjük   W =  1 0 0T   S     P =  1 0 0T  V    P is fels®tianguláris és W is unitér lesz.

Eddig volt egy hasonlósági transzformációnk Q-val, amivel idáig eljutottunk, alkamazunk még egy hasonlósági transzformációt a W unitér mátrixszal: 1 0T  W H QH AQW =   0 H  S  λ1    0 bT  B    0 1 0T  S    Ha most a particionált szorzást elvégezzük akkor az eredmény csak hasonló lehet:  λ1    0 .  S H BS    ez már Schur normálalak. Megjegyzés. Ez nem konstruktív bizonyítás, mivel abból indulunk ki, hogy ismerünk egy sajátértéket Rangszám csökkentésre alkalmazható ha ismerjük λ1 -et. A másik bizonyítás azt mondja ki, hogy elemi hasonlósági transzformációkkal triangulizálható egy mátrix. 8.2 Deníció elemi hasonlósági transzformáció, ha T egy elemi permutációs mátrix (T = Pij ) vagy eliminációs mátrix ( Gj amit egy egységmátrixból úgy kapunk, hogy a j -ik oszlopába eliminációs konstansokat írunk). T

−1 AT 8.3 Tétel Tetsz®leges A ∈ Cn×n elemi hasonlósági transzformációval triangulizálható Tehát lehet mondani véges sok permutációs vagy eliminációs mátrixokat, hogy ezekkel egymás után hasonlósági transzformációkat csinálunk és a végén fels®rianguláris mátrixot kapunk. Persze az is igaz, hogy amit a végén kapunk fels® trianguláris mátrixot ahhoz A hasonló, tehát a f®átlójában sajátértékek lesznek. Bizonyítás. Megint a mátrix rendje szerinti indukcióval bizonyítunk (i) ha n=1 akkor triviálisan igaz MÁTRIXOK SPECIÁLIS ALAKRA TRANSZFORMÁLÁSA 39 (ii) tegyük fel, hogy az állítás igaz tetsz®leges n − 1-ed rend¶ mátrixra. Legyen A tetsz®leges n-ed rend¶ mátrix, λ1 a sajátértéke és x1 olyan hozzátartozó sajátvektor, hogy max |xi | = |xm |.† Az ötlet az, hogy 1≤i≤n a sajátvektor komponenseit rendezük át és küszöböljük ki ahelyett, hogy A-t transzformálnánk. Ha az m-dik komponens maximális

abszolút érték¶, akkor P1m x1 esetén egy olyan vektort kapunk amiben fel van cserélve az els® és az m-ik komponens, vagyis a maximális abszolútérték¶ komponens felkerül az els® helyére. Most küszöböljük ki a másodiktól az összes komponenst egy eliminációs mátrixszal   1 0   G1 P1m x1 = e1 =  .  | {z }  .  w1 0 Mit kell ebbe a G1 -be írni? A bal fels® sarkába 1-et alá pedig a w1 -ben lév® komponensek −1 szereseit, mert így lesznek a szorzatban 0-k.Egy Gi eliminációs mátrix inverze úgyan úgy néz ki, mint önmaga csak az i-dik oszlopban az elemek el®jelét kell ez ellentetjére változtatni. Nézzük meg, mi történik, ha ezekkel a mátrixokkal A-n végzünk hasonlósági transzformációt. Permutációs mátrix inverze önmaga. G1 P1m AP1m G−1 1 {z } | C Jelöljük ezt a mátrixot C -vel. Most is azt kell kihozni, hogy az els® oszlop elemei: λ1 és alatta 0-k Ha elemi hasonlósági transzformáció, akkor T AT

−1 is az. T −1 AT Ce1 = G1 P1m AP1m G−1 G1 P1m x1 | 1{z } I = G1 P1m A P1m P1m x1 = G1 P1m Ax1 | {z } I = G1 P1m λ1 x1 = λ1 G1 P1m x1 = λe1 Tehát most már lehet alkalmazni az indukciót. Megint levágjuk az els® sort és az els® oszlopot és amit kapunk arra alkalmazzuk az indukciós feltevést. C -t állítsuk el® a következ® formában: λ1 dT   C=  0 F     F ∈ C(n−1)×(n−1) Erre az F -re alkalmazhatjuk az indukciós feltevést, tehát van hozzá véges sok trianguláris transzformáció ami ®t fels® trianguláris alakra hozza. Így ha F helyett a Ts−1 . T2−1 T1−1 F T1 T2 Ts alkalmazzuk, akkor egy fels® trianguláris W mátrixot kapunk. Legyen 1 0T   K=  0 T      1  K −1 CK =   0 0T T −1  λ1    0 dT  F    0 1 0T  T  =  † ezt el lehet érni hiszen ha nem teljesül a feltétel, akkor itt

is lehet normálni. Megkeressük a maximális abszolút érték¶ komponensét és ennek az értéknek a reciprokával megszorozzuk a vektor összes komponensét és akkor már olyan vektort kapunk amire ez a feltétel teljesül. Ez az eredetinek (egy nem 0) konstansszorosa, tehát sajátvektor marad MÁTRIXOK SPECIÁLIS ALAKRA TRANSZFORMÁLÁSA   =  λ1 0 40 .  W   = K −1 G1 P1m AP1m G−1 K 1  Ezzel a transzformáció sorozattal most egy fels® trianguláris mátrixot kaptunk. Az indukció megmutatta, hogy kaphatunk egy fels® triangulárist, de több volt az állításban, az volt, hogy véges sok elemi hasonlósági transzformációval kell kapni fels® trianguláris mátrixot. Azonban, ha veszünk egy P elemi permutációs T mátrixot vagy egy eliminációs mátrixot és a következ® módon kiegészítjük: ( 10 0P ) akkor újra permutációs vagy eliminációs mátrixot kapunk. 8.4 Deníció A ∈ Cn×n hermetikus mátrix, ha AH = A (a

szimmetria kiterjesztése komplex esetekre) 8.5 Következmény Ha A ∈ Cn×n hermetikus, akkor A összes sajátértéke valós Bizonyítás. A Schur-normálforma alapján U H AU = R, ha még azt is tudjuk, hogy A hermetikus akkor RH = (U H AU )H = U H AH (U H )H = U H AU = R. Azt kaptuk hogy RH = R, R az fels® trianguláris mátrix volt, RH viszont alsó trianguláris, tehát az a kett® csak úgy egyezhet meg ha R diagonális. De még van további kitétel is hiszen RH f®átlójában R f®átlójában lév® elemek konjugáltjai vannak azaz a f®átlóban lév® elemek meg kell, hogy egyezzenek a konjugáltjaikkal azaz a f®átlóban csak valós számok lehetnek (azt meg tudjuk, hogy a f®átlóban a sajátértékek vannak). 8.6 Következmény Minden hermetikus mátrix diagonizálható és választható olyan sajátvektor rendszere, hogy az egy ortonormált vektorrendszer legyen Cn -ben. Mikor igaz, hogy van egy valós szimmetrikus mátrix és a sajátértékei pozitívak?

Akkor és csak akkor ha pozitív denit. 8.7 Deníció Az A mátrix pozitív denit, xT Ax > 0 tetsz®leges x 6= 0 x ∈ Rn -re és A szimmetrikus 8.8 Állítás Az A ∈ Cn×n szimmetrikus mátrix akkor és csak akkor pozitív denit ha minden sajátértéke nagyobb, mint 0. Bizonyítás. Ennek teljesülnie kell speciálisan akkor is ha mi sajátvektorokat írunk Legyen λj sajátérték, xj a hozzá tartozó sajátvektor, akkor annak igaznak kell lenni, hogy az 0 < xTj Axj = xTj λj xj = λj xTj xj . | {z } >0 Ebb®l már következik, hogy λj > 0, tehát ha az A pozitív denit akkor minden sajátértéke pozitív. Megfordítva ha azt tudjuk, hogy az A szimmetrikus mátrix és minden sajátértéke pozitív, akkor ® pozitív denit. Ezt, hogy lehetne megcsinálni? Vissza kell térnünk a Schur normálforma tételhez, tudjuk, hogy U H AU = D. Ezt az algebrában F®tengelyT tételként szokták tisztelni és a következ®képpen szokták felírni:QT AQ = D, ebb®l √

A-t fejezükk ki, A = QDQ T T vektorra irhatjuk: x tekintsük D -t a következ®képpen D = és ha behehettesítünk, tesz®leges x QDQ x √ √ √ √ D D amit megkaphatunk a diaginálisban lév® elemek négyzetgyökeként. xT QDQT x = xT Q D DQT x = | {z } | {z } yT y y y > 0 hiszen y 6= 0, mivel x 6= 0 volt a Q ortonormált mátrix volt ami mellesleg reguláris is és ha egy reguláris √ mátrixal szorzok egy nem 0 vektort akkor nyilván csak nem 0 eredmény lehet és persze D is reguláris. T Megjegyzés. Most már tudunk néhány ekvivalens állítást a pozitív denit mátrixokra: • Az A az pozitív denit, ha minden sajátértéke pozitív. • Az A az pozitív denit, akkor és csak akkor ha van neki valós Cholesky felbontása. Olyan valós Cholesky felbontása, hogy a f®átlóban pozitív számok vannak. MÁTRIXOK SPECIÁLIS ALAKRA TRANSZFORMÁLÁSA • 41 Az A akkor és csak akkor pozitív denit ha minden f®minora pozitív. A sajátérték

számításnál szeretnénk valamilyen hasonlósági transzformációkkal A1 ∼ A2 ∼ · · · ∼ Ak egyszer¶bb alakra hozni az A-t, úgy hogy a végén Ak valamilyen egyszer¶bb mátrix lenne. Ha az eddigieket arra akarnánk használni, hogy meghatározzuk a sajátértékeket akkor baj van, ha viszont ismerjük a sajátértékeket akkor lehet véges sok transzformációt csinálni úgy, hogy a végén vagy diagonális vagy fels® trianguláris mátrixot kapunk. A gyakorlati sajátérték számítások úgy néznek ki, hogy végtelen sorozatát képezzük a mátrixoknak és határértéknek kell lenni valamilyen egyszer¶ mátrixnak. Fejezet 9 Vektornormák, mátrixnormák Tulajdonképpen két lehet®ség van az egyik az amelyiket most követünk, hogy vektornormákat deniálunk el®ször és majd azok segítségével különböz® mátrixnormákat, de lehetne fordítva is. A mátrixoknál be fogunk vezetni egy plusz tulajdonságot a mátrixok szorzatára, ami nem minden

könyvben szerepel. Vektornormák szorzatára nem érdemes tulajdonságot bevezetni, mivel szorzatként már nem vektort kapunk eredményül (vektoron oszlopvektort értve). 9.1 Vektornormák 9.1 Deníció |||| vektornorma egy olyan leképezés, amely Rn R képezi le, ha tetsz®leges x, y ∈ Rn -re és α ∈ R-re teljesülnek a következ®k: (i) ||x|| > 0, ha x nem a 0 vetktor (ii) ||αx|| = |α| ||x|| (iii) ||x + y|| ≤ ||x|| + ||y|| (háromszög egyenl®tlenség) Megjegyzés. Van egy másik háromszög egyenl®tlenség is, ami úgy szól, hogy két odal különbsége mindig kisebb, mint a harmadik ennek vektoros megfelel®je: (iv) | ||x|| − ||y|| | ≤ ||x − y|| (a "másik" háromszög egyenl®tlenség) (iv) következik (iii)-ból: ||x|| = ||(x − y) + y|| ≤ ||x − y|| + ||y|| Az elejét és a végét tekintve: ||x|| − ||y|| ≤ ||x − y|| ||y|| = ||(y − x) + x|| ≤ ||y − x|| + ||x|| ||y|| − ||x|| ≤ ||y − x|| = ||x − y|| (9.1) és

(9.2)-b®l következik: | ||x|| − ||y|| | ≤ ||x − y|| Megjegyzés. A 0 vektor normája a 0 szám (mivel (ii) alapján ||00|| = |0| ||0|| = 0) 42 (9.1) (9.2) MÁTRIXNORMÁK RN ×N -BEN 43 Megjegyzés. A (iii)-ban megadott egyenl®tlenséget lehet általánosítani véges sok tag összegére is indkucióval: || n X xj || ≤ j=1 n X ||xj || tetsz®leges n ∈ N-re j=1 Az üres összeget, n = 0, általában 0-nak vesszük. A következ® lépés az, hogy deniálunk különféle vektornormákat. Végtelen sokat tudnánk deniálni Deniálunk egy norma családot a következ®képpen: 9.2 Deníció tetsz®leges p ≥ 1 valós számra az ||x||p def = nevezzük. Kitüntetett értékek: p = 1 : ||x||1 = Pn p = 2 : ||x||2 = pPn i=1 p Pn p i=1 |xi |p számot az x vektor p-normájának |xi | i=1 |xi |2 p = ∞ : ||x||∞ = max1≤i≤n |xi | Megjegyzés. • ||.||1 -át szokták Manhattan-normának is nevezni, amikor a komponenseket összeadogatjuk

abszolult érték- ben az szemléletesen az a távolság fogalom amikor két dimenzóban csak függ®legesen és vízszintesen mozoghatánk úgy mint ha egy négyzetrácsos utcahálózaton jutnánk el valahova. a valós euklídészi térben a vektor hossza vagy más néven két pont távolsága (a kezd® és a végpont távolsága) • ||.||2 • ||x||∞ = limp∞ ||x||p (ezt azonban be kellene bizonyítani), úgy kell értelmezni, hogy ha az x vektor rögzítjük és vesszük p-knek olyan sorozatát, ami végtelenhez tart és minden egyes p-re kiszámoljuk az x vektornak a p-normáját, akkor valós számok egy sorozatát kapjuk és a végtelen norma ennek a valós számsorozatnak a határértékével lesz egyenl®. valóban vektornorma. Ahol gond lehet az a háromszög egyenl®tlenség1 (az els® két tuladonság igazolása elég triviális), például a ||||2 -nál a Cauchy-Bunyakovszkij-Schwarz-féle egyenl®tlenség kell az igazolásához. Amikor már adott egy vektornorma,

akkor abból még lehet újabb normákat konstruálni a következ® módon: Megjegyzés. ||.||p 9.3 Deníció = ||T x|| normát Ha adott a ||.|| vektornorma és a T reguláris mátrix, akkor deniáljuk ||x||T def (és ez tényleg vektornorma). Ezzel már egyetlen egy vektornormából is lehetne végtelen sok vektornormát csinálni attól függ®en, hogy milyen milyen mátrixokat veszünk, ha különböz® mátrixokat veszünk, akkor különböz® normák lesznek. Mikor különböz® két norma? Akkor különböz®, ha van legalább egy olyan vektor, amelyben az egyiknek a normája nem ugyan olyan, mint a másiké. Megjegyzés. Amit idáig leírtunk az a komlex vektorok esetén is igaz Hogyan vezethetünk be mátrixnormákat? 9.2 Mátrixnormák Rn×n-ben 9.4 Deníció |||| mátrixnorma egy olyan leképezés, amely Rn×n R képezi le, ha tetsz®leges A, B ∈ Rn×n - re és α ∈ R-re teljesülnek a következ®k: 1 A ||.||p normákq(iii)-dik tulajdonságát qP a

Minkowski-egyenl®tlenség igazolja: Pn n p P P i=1 |xi yi | ≤ i=1 |xi | + i=1 |yi | (A szerkesztget®) p Pn p p p MÁTRIXNORMÁK RN ×N -BEN 44 (i) ||A|| > 0, ha A nem a 0 mátrix (ii) ||αA|| = |α| ||A|| (iii) ||A + B|| ≤ ||A|| + ||B|| (háromszög egyenl®tlenség) (iv) ||AB|| ≤ ||A|| ||B|| Megjegyzés. A (ii)-es a kakukk tojás, mivel ha azt mondjuk, hogy mátrixokról beszélünk úgy mint mátrix gy¶r¶r®l, akkor tulajdonképpen ilyen m¶velet nincs. Ha a mátrixokat mint lineáris tér elemeit tekintjük, akkor van skalárral való szorzás. Persze értelmezni ezt tudjuk hiszen az αA megfelel annak, hogy A minden komponensét megszorozzuk α-val, csak ha valaki ezt nagyon szigorúan veszi, akkor ez nem gy¶r¶ m¶velet. A skalárszorzás megfeleltethet® annak ha veszünk egy diagonális mátrixot és a f®átlójába végig α-t írunk és ezzel a diagonális mátrixszal szorzunk, így már gy¶r¶ m¶veletr®l beszélhetünk. Ahogy a háromszög

egyenl®tlenségb®l a vektoroknál levezettük a másik háromszög egyenl®tlenséget úgy most is újra le lehetne vezetni. Hogy ne kelljen ezeket megismételni, ahhoz lehetne csinálni egy huszárvágást Ezek az n×n-es mátrixokat úgy tekintjük, mint a mátrixgy¶r¶ elemit, de ha azt csináljuk, hogy az A mátrixhoz hozzárendelünk egy n2 komponens¶ vektort úgy, hogy leírjuk a komponenseit valamilyen rögzített sorrendben például sorfolytonosan, akkor ezzel kölcsönösen egyértelem¶ módon hozzá lehet egy n × n mátrixhoz rendelni az n2 dimenziós lineáris tér egy elemét. 9.5 Példa Ha n = 2 és ( aa1121 aa1222 ) ehhez hozzárendeljük a (a11 , a12 , a21 , a22 )T , akkor az ilyen fajta hozzárendelés kölcsönössen egyértelm¶ hozzárendelés az összes n × n-es mátrix és az összes n2 komponens¶ vektort között. Ha mátrixnormákkal szeretnénk foglalkozni tulajdonképpen vissza lehet játszani a vektornormákra, ha azt mondjuk, hogy ha van egy

mátrixnormánk n × n-es mátrixgy¶r¶ben, akkor az n2 lineáris térben vektornorma lesz, úgy értve, hogy értve, hogy a példában szerepl® vektornak a normáját úgy értelmezzük, mint a hozzá tartozó mátrixnak a normáját. Mivel az (i) − (iii) feltételek mátrixok és vektorok esetében ugyanúgy nézett ki azért, ha van egy mátrinormánk akkor az vektornorma lesz az n2 dimenziós lineáris téren is, ezért nem kell mindent újra bizonyítani. Tesz®leges mátrixnorma vektornorma is lesz Visszafelé már nem igaz, tetsz®leges vektornorma nem lesz mátrixnorma, a (iv)-k tulajdonság miatt. Mátrix normákat más módon deniálunk, mint vektornormákat. Megmutatjuk, hogy viszonylag egyszer¶en, hogy lehet mátrixnormákat gyártani vektor normákból. Származtatott mátrixnormák 9.6 Deníció Adott vektornorma esetén a bel®le származtatott mátrixnormát A ∈ Rn×n mátrixra: def ||A|| = sup x6=0 így deniáljuk: tetsz®leges ||Ax|| ||x|| Az hogy ez

tényleg mátrixnorma be kellene bizonyítani, most csak kijelentjük, hogy ezt tényleg mátrixnorma. 9.7 Állítás A 96 denícióban valóban mátrixnormát kapunk 9.8 Állítás ||A|| = sup x6=0 ||Ax|| 1. ||Ax|| 2. = max = max ||Ax|| x6=0 ||x|| ||x|| ||x||=1 Az, hogy az 1. egyenl®ség igaz nem olyan triviális Itt arról van szó, hogy van a valós számoknak egy részhalmaza ami ilyen hányadosokként kijön, azt állítottuk, hogy van supremuma2 . Attól hogy van supremuma egy számhalmaznak nem olyan biztos, hogy van maximuma, ha van maximum, akkor az a supremum. A 2 egyenl®séget is bizonyítani kell. Miért szokták operátor normaként is emlegetni ezt a deníciót? Azért mert ha vesszük a n dimenziós lineáris teret, akkor tetsz®leges rögzített mátrixra mondhatjuk, hogy az egy leképezést indukál (x Ax), ilyen értelemben operátor az A. Leképezés normája valami olyasmi, hogy maximálisan hányszorosára tud megnyújtani egy leképezés egy nem 0 vektort.

2 supremum, legkisebb fels® korlát: ha A felülr®l korlátos számhalmaz, akkor fels® korlátai között létezik legkisebb. MÁTRIXNORMÁK RN ×N -BEN 45 Hogy lehet egy adott vektor irányába mutató egységvektort megadni? Van valamilyen x vektor, akkor x 1 vektorhoz hozzá lehet rendelni az ® irányába mutató egységvektort xe = ||x|| ||x||, az igaz, hogy egységvektor mivel ebben a normában 1 a normája (||xe || = 1). A hagyományos értelemben vett egységvektorok esetén, ei -k is minden normában 1 lesz. 9.9 Állítás 1. ||A||1 = max 1≤j≤n 2. ||A||∞ = max 1≤i≤n n X i=1 n X |aij | "oszlopnorma" |aij | "sornorma" j=1 Az 1.-t úgy számoljuk, hogy veszünk valamilyen rögzített j -t, rögzített j mellett a j -ik oszlop elemeinek abszolultértékes összegét vesszük, és az oszlop összegeknek vesszük a maximumát. A 2-nál megcseréljük a sorok oszlopok szerepét (sor összegek maximuma). 9.10 Deníció %(A)

= max |λi | 1≤i≤n az A mátrix spektrálsugara. Tehát a spektrálsugár a sajátértékek abszolút értékének a maximuma. λi -k (a sajátértékek) a karakterisztikus polinom gyökei a komplex számsíkon Azért nevezik spektrálsugárnak a 910 denícióban megadott fogalmat, mivel szemléletesen megfelel a legkisebb sugarú olyan körnek a komplex számsíkon amely tartalmazza az összes sajátértéket. ||A||2 √ = AT A "spektrálnorma" Ezt nem lehet minden esetben számítani. Mi van akkor ha A szimmetrikus mátrix? Akkor az összes sajátértéke valós. AT A = A2 , A2 mátrix sajátértékei az A sajátértékeinek a négyzetei. Ha A szimmetrikus, akkor ||A||2 = %(A) 9.11 Deníció A következ® mátrixnormák nem származtatottak: (i) ||A||F = s X |aij |2 Frobénius-norma 1≤i,j≤n (ii) ||A||M = n max |aij | 1≤i,j≤n Be lehet látni direkt számolással, hogy mindkett® mátrixnorma és azt is be lehet látni, hogy egyik sem

származtatott. Minden származtatott normánál az egység mátrix normája 1 Itt látszik, hogy nem 1 az egységmátrix normája. (i)-nél az összes négyzetösszegének a négyzetgyökét kell venni, ami egységmátrik esetén √ n , (ii)-nél pedig az n-es szorzó miatt nem lesz az egységmátrix 1 (kivéve az egy dimenziós esetet). Meglehetne még ezeket a normákat is sokszorozni. Ha van egy reguláris mátrixnormánk és egy reguláris mátrixunk, akkor hogyan lehet az ahhoz tartozó újabb normát deniálni? 9.12 Kérdés T Mi lesz az ||A||T = supx6=0 ||Ax|| ||x||T =? Ez az a T norma amit a vektormáknál deniáltunk. Egy másik fajta kapcsolatot is deniálunk egy vektornorma és egy mátrixnorma között (egyik fajta kapcsolat volt a származtatás). Egy másik kapcsolat a kompatibilitás A kompatbilitás jó lesz arra, hogy különböz® egyenl®tlenségeket becsléseket tudjunk manipulálni. 9.13 Deníció A ||.||v vektornorma és az ||||m mátrixnorma

kompatibilis, ha tetsz®leges x-re és A-ra ||Ax||v ≤ ||A||m ||x||v A SPEKTRÁLSUGÁR ÉS A MÁTRIXNORMÁK KAPCSOLATA 46 Egy kicsit hasonlít a (iv) negyedik tulajdonságra, de ez nem annak a következménye. 9.14 Példa A ||||2 vektornorma kompatibilis a ||||F mátrixnormával (i) Minden vektornorma kompatibilis a bel®le származtatott mátrixnormával. ||Ax|| ||Ax|| = ||x|| ≤ ||x||  ||Ax|| max x6=0 ||x||  ||x|| = ||A|| ||x|| Ennek a következménye, hogy minden vektornormához megadható vele kompatibilis mátrixnorma (például amit bel® le származtatunk, de lehet több ilyen is). (ii) Tetsz®leges mátrixnormához megadható vele kompatibilis vektornorma. Deniáljunk a következ®képpen egy vektornormát: ||x||v def = ||x 0 . 0} ||m , be lehet bizonyítani, hogy így tényleg vektornormát kapunk | .{z n-1 db 9.3 A spektrálsugár és a mátrixnormák kapcsolata Az el®z®ek segítségével be lehet bizonyítani a spektrál sugárra egy fels® korlátot.

Mátrix norma végtelen sok van, bebizonyítjuk, hogy tetsz®leges mátrixnak a spektrálsugara kisebb vagy egyenl®, mint tetsz®leges normája. 9.15 Állítás Tetsz®leges A-ra és ||||m -ra igaz a %(A) ≤ ||A||m egyenl®tlenség 9.16 Példa Legyen A = ( 10 21 ) %(A) ≤ %(A) ≤ %(A) ≤ ||A||∞ = 3 ||A||1 = 3 √ ||A||F = 6 Ez a példa nem túl jó (hiszen jelen esetben ismerjük a sajátértékeket mivel fels® trianguláris mátrixról van szó), ahhoz képest, hogy %(A) = 1 ezek nem túl jó korlátok. Bizonyítás. Legyen adott A és legyen adott ||.||m , legyen ||λl || = %(A) (1 ≤ l ≤ n) (azaz λl a legnagyobb abszolút érték¶ sajátérték) és Axl = λl xl (tehát a λl -hez tartozó egyik sajátvektor az xl ). Most vegyünk ezzel a mátrixnormával kompatibilis vektornormát, legyen ||.||v az adott mátrixnormával kompatibilis vektornorma, ekkor a következ®t lehet csinálni: |λl | ||xl ||v = ||λl xl ||v = ||Axl ||v ≤ ||A||m ||xl ||v Ha a két

szélét nézzük és leosztunk ||xl ||v -val (megtehetjük mivel ||xl || > 0), akkor megkapjuk, hogy |λl | ≤ amib®l már következik a tétel. ||A||m , 9.4 Normák ekvivalenciája 9.17 Deníció γ∗ , δ∗ A ||.|| és ||||∗ vektornormák kostansok, hogy tetsz®leges x ∈ R-re ekvivalensek , ha léteznek olyan csak a két normától függ® γ∗ ||x||∗ ≤ ||x|| ≤ δ∗ ||x||∗ 9.18 Állítás A vektornormák ekvivalenciája ekvivalencia reláció Tehát reexív, szimmetrikus, tranzitív. Minden norma ekvivalens sajátmagával, fel lehet cserélni a két normát. 9.19 Állítás Bármely két vektornorma ekvivalens NORMÁK EKVIVALENCIÁJA 47 Elég belátni, hogy tetsz®leges vektornorma, ekvivalens egy darab rögzítt vektornormával (például ||.||1 -val) 9.20 Deníció γ∗ , δ∗ A ||.|| és ||||∗ mátrixnormák kostansok, hogy tetsz®leges A ∈ Rn×n -re ekvivalensek, ha léteznek olyan csak a két normától függ® γ∗ ||A||∗ ≤

||A|| ≤ δ∗ ||A||∗ 9.21 Állítás A mátrixnormák ekvivalenciája ekvivalencia reláció 9.22 Állítás Bármely két mátrixnorma ekvivalens Legközelebb folytatjuk azzal, hogy ez az ekvivalencia miért jó, akkor amikor a határértékeket vizsgáljuk. Fejezet 10 Vektorsorozatok és mátrixsorozatok 10.1 Vektorsorozatok = x∗i 10.1 Deníció Az {xk } vektorsorozat konvergens , ha megadható olyan vektor, amellyel limk∞ x(k) i teljesül bármely 1 ≤ i ≤ n-re Röviden, akkor mondjuk egy vektors sorozatra, hogy konvergens, ha komponensenként konvergens. Ha ez a határérték létezik, akkor egyértelm¶. A vektornormák segítségével is lehet a konvergenciát deniálni. 10.2 Deníció Az {xk } vektorsorozat konvergens, ha van olyan x∗ amelyre limk∞ ||x∗ − xk || = 0 (Ez a deníció független a választott vektornormától a normák ekvivalenciája miatt.) 10.3 Állítás A konvergencia két deníciója ekvivalens A vektorsorozat deníciója

általánosítása a valós számsorozatoknak, hiszen amikor n = 1 (egy dimenziós a tér), akkor számsorozatokat kapunk. A két deníció tulajdonképpen a xk x∗ ⇔ |xk −x∗ | 0 ekvivalenciából adódik, csak az abszolút érték helyett normák vannak. Bizonyítás. Az állítást elegend® a végtelen normára bizonyítani Azt kellene belátni, hogy: ∀1 ≤ i ≤ n (k) lim xi k∞ = x∗i ⇔ (k) lim max |x∗i − xi | = 0 k∞ m (k) lim |x∗i − xi | = 0 k∞ Ezután az állítás után már mindegy, hogy melyik deníciót használjuk. Bizonyos értelemben a második a kényelmesebb, mivel az els®nél a vektorsorozat konvergenciáját n db valós szám sorozat konvergenciájára vezettük vissza. A másodiknál 1 db valós számsorozatot kell csak nézni 10.4 Állítás (i) Ha az xk x∗ és yk y∗ , akkor xk + yk x∗ + y∗ (ii) Ha az xk x∗ és αk α∗ , akkor αk xk α∗ x∗ Bizonyítás. (i) szükséges és elegend® azt megmutatni,

hogy ||x∗ + y∗ − (xk + yk )|| 0 0 ≤ ||(x∗ − xk ) + (y ∗ − y k )|| ≤ ||x∗ − xk || + ||y ∗ − y k || 0 | {z } | {z } ↓ 0 48 ↓ 0 MÁTRIXSOROZATOK 49 (ii) 0 ≤ ||α∗ x∗ − (αk xk )|| = ||(α∗ x∗ − α∗ xk ) + (α∗ xk − αk xk )|| ≤ |α∗ | ||x∗ − xk || + |α∗ − αk | ||xk || 0 | {z } | {z } | {z } ↓ 0 ↓ 0 korlátos 10.5 Következmény Ha xk x∗ , akkor ||xk || ||x∗ || Bizonyítás. Felhasználva a második háromszög egyenl®tlenséget ((iv)-es tulajdonság): Ha ∗ ||xk − x || 0 de xk x∗ , akkor 0 ≤ | ||xk || − ||x∗ || | ≤ ||xk − x∗ || 0 | {z } m ||xk || ||x∗ || 10.6 Alkalmazás Lineáris egyenletrendszerek közelít® megoldásinál, közelít® megoldások sorozatát fogjuk képezni és az lesz a kérdés, hogy ez a sorozat konvergál-e a megoldáshoz. 10.2 Mátrixsorozatok 10.7 Deníció (k) limk∞ aij Az {Ak } ∈ Rn×n mátrixsorozat konvergens, ha megadható olyan A∗

mátrix, amellyel = a∗ij teljesül bármely rögzített 1 ≤ i, j ≤ n-re Tehát konvergens egy mátrixsorozat, ha komponensenként konvergens. Így tulajdonképpen n2 darab valós számsorozat konvergenciáját vizsgáljuk. 10.8 Deníció Az {Ak } mátrixsorozat konvergens, ha van olyan A∗ mátrix amelyre limk∞ ||A∗ −Ak || = 0 (Ez a deníció is független a választott mátrixnormától a normák ekvivalenciája miatt.) Kölcsönösen egyértelm¶ leképéezés lehet megadni Rn×n ⇔ Rn között, úgy hogy valamilyen x sorrendben lírjuk az n2 komponenst. Az látszik, hogy ha tekintünk egy mátrixsorozatot az akkor és csak akkor lesz konvergens, ha mint vektorsorozat konvergens. Ez alapján a két deníció a mátrixsorozatoknál is ekvivalens Viszont a mátrix gy¶r¶ben vannak olyan m¶veletek melyek a vektorok esetében nem voltak. 2 10.9 Állítás Tetsz®leges {Ak }, {Bk } mátrixsorozatra és α valós számra (i) Ha az Ak A∗ és Bk B ∗ , akkor Ak +

Bk A∗ + B ∗ (ii) Ha az Ak A∗ , akkor αk Ak α∗ A∗ (iii) Ha az Ak A∗ és Bk B ∗ , akkor Ak Bk A∗ B ∗ Bizonyítás. (i) szükséges és elegend® azt megmutatni, hogy ||A∗ + B ∗ − (Ak + Bk )|| 0 0 ≤ ||(A∗ − Ak ) + (B ∗ − Bk )|| ≤ ||A∗ − Ak || + ||B ∗ − Bk || 0 | {z } | {z } ↓ 0 ↓ 0 (iii) szükséges és elegend® azt megmutatni, hogy ||A∗ B ∗ − Ak Bk || 0 0 ≤ ||Ak Bk − A∗ B ∗ || = ||(Ak Bk − Ak B ∗ ) + (Ak B ∗ − A∗ B ∗ )|| ≤ ||Ak Bk − Ak B ∗ || + ||Ak B ∗ − A∗ B ∗ || = ||Ak (Bk − B ∗ )|| + ||(Ak − A∗ )B ∗ || ≤ ||B ∗ || ||A∗ − Ak || + ||B ∗ − B k || ||Ak || 0 | {z } | {z } | {z } ↓ 0 ↓ 0 korlátos SAJÁTÉRTÉKEK KORLÁTAI; GERSGORIN-TÉTEL 50 (iii) ⇒(ii) αk helyett vehetünk egy olyan diagonális mátrixot melynek a f®átlójában végig αk komponensek szerepelnek. 10.10 Állítás Tetsz®leges {Ak } és {Tk } mátrixsorozatra (iv) ha Ak A∗ -hoz

és A∗ reguláris (tehát A∗ létezik), akkor (Ak )−1 (A∗ )−1 (v) ha Ak A∗ -hoz, akkor det(Ak ) det(A∗ ) (vi) (a) ha Ak A∗ és T reguláris, akkor T −1 Ak T T −1 A∗ T (b) ha Ak A∗ , Tk T ∗ és T ∗ reguláris, akkor Tk−1 Ak Tk (T ∗ )−1 A∗ T ∗ . Ez az állítás az el®z®ekb®l következik. (vii) Ha Ak A∗ , akkor tetsz®leges l ∈ N-re (Ak )l (A∗ )l −1 10.3 Sajátértékek korlátai; Gersgorin-tétel 10.11 Állítás Ha A sajátértékei λ1 , λ2 , , λn akkor (i) (ii) (iii) sajátértékei λl1 , λl2 , . , λln αA sajátértékei αλ1 , αλ2 , . , αλn P (A) sajátértékei P (λ1 ), P (λ2 ), . , P (λn ) Al valamilyen l-ed fokú polinom, azt jelenti, hogy α0 xl + α1 xl−1 + · · · + αl−1 x + αl tetsz®leges P (x) polinom esetén az x-ek helyére be kell helyettesíteni az A mátrixot, így P (A) P (A) = α0 Al + α1 Al−1 + · · · + αl−1 A + αl I Az így számított P (A) egy mátrix lesz.

Tehát (iii) arra vonatkozik, hogy ha veszünk egy tetsz®leges valós együtthatós polinomot és kiszámoljuk a P (A) polinomot, akkor P (A) sajátértékeit úgy kapjuk meg, hogy ugyanabba a P polinomba behelyettesítjük a sajátértékeket. Ez a legáltalánosabb állítás, a többi ennek speciális esete (iii)-t lehet fokszám szerinti teljes indukcióval bizonyítani úgy, hogy kétfeléválasztjuk P (A)-t P (A) = α0 Al + (α1 Al−1 + · · · + αl−1 A + αl I) és innen az els® két állítás segítségével adódik a bizonyítás. Ehhez azonban be kell bizonyítani (i)-t és (ii)-t Bizonyítás. (i)-t l szerinti teljes indukcióval bizonyítjuk. Ha feltesszük, hogy l − 1-re igaz, akkor l−1 l−1 l Al xj = A(Al−1 xj ) = A(λl−1 j xj ) = λj Axj = λj λj xj = λj xj (ii) α(Axj ) = αλj xj 10.12 Állítás ha A sajátértékei λ1 , λ2 , , λn és λj 6= 0 (magyarul a 0 nem sajátérték), akkor (iv) A−1 sajátértékei 1 1 1 λ1 , λ2 , . ,

λn . Azt könnyen lehet látni, hogy egy A mátrixnak a 0 pontosan, akkor lesz sajátértéke ha A szinguláris (det(A) a sajátértékek szorzata). Bizonyítás. (iv) Axj = λj xj ⇔ xj = λj A−1 xj ⇔ 1 x = A−1 xj λj j amit már lehet úgy olvasni, hogy az A−1 mátrixnak a sajátvektora az xj és a hozzá tartozó sajátérték 1 λj SAJÁTÉRTÉKEK KORLÁTAI; GERSGORIN-TÉTEL 51 Ha A reguláris mátrixra feltesszük, hogy A−l def = (A−1 )l , akkor mondhatjuk, hogy A−l sajátértékei λl1 , λl2 , . , λln Már bizonyítottuk, hogy tetsz®leges A-ra és tetsz®leges mátrixnormára %(A) ≤ ||A||. Ehhez kapcsolódó tételeket veszünk. 10.13 Tétel Ak 0 ⇔ ||A|| < 1 Ak 0 ⇔ %(A) < 1 El®ször azt fogjuk bizonyítani, hogy a két állítás ekvivalens egymással. 10.14 Állítás %(A) < 1 akkor és csak akkor, ha van olyan normája az A-nak, hogy ||A|| < 1. A 10.14 állítás bizonyításához vesszük a következ® tételt 10.15

Állítás Tetsz®leges A mátrixhoz és  > 0 megadható olyan (A-tól és -t®l függ®) |||| mátrixnorma, amelyre %(A) ≤ ||A|| ≤ %(A) +  | {z } 77. oldal %(A) ≤ ||A||-t pedig már bizonyítottuk. A 10.15 állításból a 1014 már triviálisan következik hiszen, ha az ||A|| < 1 akkor a %(A) < 1 is Másik irányba, ha a %(A) < 1, akkor lehet úgy választani azt a  > 0-t, hogy %(A) +  is kisebb legyen mint 1. Bizonyítás. A 1013-es tétel bizonyítása: Ha Ak 0, akkor . (ez a nehezebbik fele Jordan-normával kellene bizonyítani vagy macerásan a Schurnormálformával) Ha ||A|| < 1, akkor Ak 0. Ez a fele a bizonyításnak sokkal könnyebb hiszen rögtön lehet azt csinálni, hogy: 0 ≤ ||Ak || ≤ ||A||k 0 Ezzel már készen is vagyunk hiszen qk 0 akkor és csak akkor teljesül, ha q < 1, itt viszont A-ra eleve kikötöttük, hogy ||A|| < 1. 10.16 Tétel (Gersgorin-tétel) Tetsz®leges A mátrix esetén A összes sajátértéke

benne van az Sni=1 ki halmazban, ahol ki = {x : |x − aii | ≤ n X |aij |} j=1 j6=i sugár | {z } 10.17 Példa   −2 1 3 A =  1 1 −5 −2 1 3 A tétel köröket deniál a komplex síkon. A diagonális elemek lesznek a körök középpontjai (x = −2, x = 1, x = 3)és a diagonálison kívül lev® elemek abszolút értékes összege lesz a kör sugara (−2 körül 4, 1 körül 6, 3 körül 3 sugarú kört kapunk). A tétel az állítja, hogy az összes sajátérték benne van a körök egyesítésében Bizonyítás. Legyen λj tetsz®leges sajátérték, az hogy benne van ebben az egyesítésben úgy is kifejezhet®, hogy tetsz®leges j -hez van olyan i, hogy a λj benne van a ki -ben. Ekkor a Bj def = A − λj I mátrix szinguláris (ez a sajátérték deníciója). A diagonális dominanciánál bebizonyítottuk, hogy ha egy mátrix diagonális domináns, akkor reguláris. Ezt az állítást meg is lehet fordítani azaz ha egy mátrix szinguláris akkor

nem diagonális domináns. Ezért Bj nem diagonális domináns Azaz van olyan i (1 ≤ i ≤ n) hogy: |bii | ≤ n X j=1 j6=i |bij | ⇔ |aii − λj | ≤ n X j=1 j6=i |aij | Fejezet 11 Tetsz®leges A mátrixnak van Schur-normálalakja. Tehát tetsz®leges A mátrixhoz van olyan Q unitér mátrix hogy:   λ1 r12 . r1n  .   0 λ2 . .  H   Q AQ = R =  . . . . rn−1,n   .  0 . 0 λn Bizonyos esetekben lehet olyat is csinálni, hogy:  λ1  0 T −1 AT = D =  .  . 0 0 λ2 . 0  .  .  . . . 0  0 λn Ilyet akkor és csak akkor lehet csinálni, ha az A mátrixnak van egy nem elfajult sajátvektor rendszere, tehát van n darab lineárisan független sajátvektora. Ha numerikusan akarunk sajátértékeket meghatározni, akkor a valamilyen el®bb említett formát kellene elérni A baj az, hogy ezek bizonyításánál felhasználtuk a sajátértékeket Azért sem sikerülhet, hogy tesz®leges

mátrixra véges sok hasonlósági transzformációval a fent említett két alak valamelyikét elérjük, mert a sajátértékek megoldása az algebrai egyenletek meghatározásával ekvivalens feladat amir®l pedig tudjuk, hogy algoritmikus úton nem meghatározható. Tehát valamilyen közelít® sajátérték számítást csinálunk, de a minta ez lenne. Két irányba lehet általánosítani, az egyik az lenne, hogy nem pont ilyen alakokat próbálnánk elérni, hanem ehhez hasonlót, ilyen lehet a fels® Hessenberg alak. Tehát valami ilyesmit próbálunk, hogy:  h11 h21   T −1 AT = H =   0  .  . 0 h12 h22 . . . . . . . 0 hn,n−1 . . .  h1n h2n   .  .   .  .  hnn Kérdés lehet, hogy tesz®leges A mátrixot tudunk-e ilyen alakra hozni (a sajátértékek ismerete nélkül véges sok lépésben)? Ilyet tudunk csinálni. Miért akarnánk Hessenberg alakra hozni hiszen a H -nak semmit sem tudunk a sajátértékeir®l

csak azt, hogy ugyan azok a H és az A sajátértékei? Azért szokták Hessenberg alakra hozni a mátrixot mivel, ilyen alakra a kés®bbi algoritmusok könnyebben alkalmazhatók. Egy másik lehet®ség lesz az, hogy megpróbáljuk az A mátrixot tridiagonális alakra hozni szintén hasonlósági 52 HATVÁNY MÓDSZER 53 transzformációval.  s11  s21   −1 T AT = S =  0   .  . 0 s12 s22 0 . . . . . . 0 . . sn,n−1 0  . .     0    sn−1,n  snn A tridiagonális alakra hozást csak akkor szokták ajánlani, ha az A mátrix szimmetrikus volt és ilyenkor meg lehet mutatni, hogy S szimmetrikus lesz. Ennek is csak annyi az el®nye, hogy egy ilyen mátrixra mégkönnyebb alkalmazni a kés®bb bemutatandó algoritmusokat. Egy régi algoritmus a következ® 11.1 Hatvány módszer A hátvány módszernél és az el®z® alapgondolaton alapuló módszereknél úgy határozzuk meg a sajátértékeket, hogy

vektorsorozatokat számolunk és majd azokkal manipulálunk. A többi algoritmusnál mátrix sorozatokat számolunk, tehát a fent említett alakokakat végtelen mátrixsorozatokkal közelítjük. Van egy A mátrixunk és ennek a sajátértékeit szeretnénk meghatározni. A sajátértékeket indexezzük meg olyan módon, hogy |λ1 | ≥ |λ2 | ≥ · · · ≥ |λn |. Választunk egy tetsz®leges v0 kezd®vektort utánna pedig számoljuk a következ® iterációs sorozatot: def v k+1 = Av k ebb®l kapunk egy vektorsorozatot {v0 , v1 , v2 , . , vk } 11.1 Állítás v k = Ak v 0 tetsz®leges k ∈ N-re. Bizonyítás. k-szerinti teljes indukcióval bizonyítjuk k + 1-re: k = 1-re igaz, tegyük fel, hogy k-ra igaz és vizsgáluk v k+1 = A(v k ) = A(Ak v 0 ) = Ak+1 v 0 Legyen A szimmetrikus, ekkor van ortonormált sajátvektor rendszere {x1 , x2 , . , xk } Mivel ez egy ortonormált rendszer ezért bázist is alkot a vektortérben térben úgy hogy akármilyen kezd®vektorból

indultunk ki azt fel lehet írni ezek lineáris kombinációjaként. v0 vk = α1 x1 + · · · + αn xn = Ak v 0 = α1 Ak x1 + · · · αn Ak xn = α1 λk1 x1 + · · · + αn λkn xn Tudjuk azt, hogy a vk -t így fel lehet írni, de nem ismerjük se az α-t se a λ-t se az x-t. A vicc az benne, hogy nem is kell ismerni mivel abból, hogy van egy ilyen el®állítása lehet valamit kihozni a sajátértékekre pusztán úgy, hogy a v sorozatot nézzük. Vegyük a v Tk v k = (α1 λk1 x1 + · · · + αn λkn xn )T (α1 λk1 x1 + · · · + αn λkn xn )-t. Tudjuk azt, hogy az xi -k ortonormált rendszert alkottak. Két n tagú összeg van ezért mindent mindennel össze kellene szorozni, de mivel ortonormált rendszert alkottak ezért ha különböz® index¶eket veszünk ki az els®b®l, mint a másodikból akkor mindig 0-t kapunk. Vagyis ténylegesen csak a következ® szorzatokat kell felírni T 2 2k T = α12 λ2k 1 x1 x1 + · · · + αn λn xn xn | {z } | {z } 1 1

MÁTRIXOK SPECIÁLIS ALAKRA TRANSZFORMÁLÁSA 54 Ha képezzük a vektorsorozatot, akkor szimetrikus mátrix esetén az el®z® alakban felírható a vTk vk szorzat. Ne csak ezt képezzük hanem vegyünk egy olyan hányadost, hogy: v Tk+1 v k+1 v Tk v k α12 λ2k+2 + · · · + αn2 λn2k+2 α12 λ2k + · · · + αn2 λ2k n  2k+2  2k+2 + · · · + αn2 λλn1 ) λ2k+2 (α12 + α22 λλ12 1 =  2k  2k 2 2 λ2 + · · · + αn2 λλn1 ) λ2k 1 (α1 + α2 λ1  2k+2  2k+2 + · · · + αn2 λλn1 α12 + α22 λλ12 2 = λ21  2k  2k λ1 λ2 λ 2 2 n α1 + α2 λ1 + · · · + αn2 λ1 = ha |λ1 | > |λ2 | és α1 6= 0. Tehát a hatvány módszernél a legnagyobb abszolút érték¶ sajátértékere kapunk egy ilyen képletet. 11.2 Mátrixok speciális alakra transzformálása hasonlósági transzformációkkal Alapvet®en két módszer van, az egyik a Gauss-eliminációra hasonlít a másik az QR ortogonális trianguláris felbontásra (err®l nem fogunk beszélni).

A Gauss elminiációból ismer®s elemi permutációs és elminációs mátrixokat használjuk fel most is. Az algoritmus lépései: j = 1, 2, . , n − 2 és a j -dik lépésben a j -dik oszlopot hozzuk Hessenberg alakra Ha adott az Aj−1 akkor el®ször választanikell f®elemet de nem a f®átlóba hanem a f®átló alá (részleges f®elemkiválasztással fog dolgozni az algoritmus). j = 1-re A1 = G1 Pπ(1),2 A0 Pπ(1),2 G−1 1 Azért kell a G1 Pπ(1),2 inverzével jobbról is szorozni mivel itt hasonlósági transzformációval dolgozunk (Pπ(1),2 nek saját maga az inverze). G1 Pπ(1),2 A0 -ról már a Gauss elminációnál beláttuk, hogy a kívánt formát hozza létere (jelen setben az els® oszlopban a második sortól kinulláz minden elemet), azt kell még belátni, hogy Pπ(1),2 G−1 1 -vel való jobbról szorzás nem rontja el az eddigi eredményt.Ha jobbról szorzunk a Pπ(1),2 permutációs mátrixszal, akkor két oszlopot cserél meg, pontosabban a π(1) index¶t

a másodikkal, viszont π(1) értéke kett® vagy annál nagyobb tehát semmi baj sem lesz az els® oszlopra nézve. Ha balról szorzunk G1 -el az azt jelenti, hogy egy bizonyos sor konstansszorosait hozzáadjuk a többi sorhoz, G1 inverzét pedig úgy kapjuk, hogy egy oszlopban az elemek el®jelét meg kell változtatni. Ha G1 -el jobbról szorzunk, akkor egy bizonyos oszlophoz adjuk hozzá a többi oszlop konstansszorosait, jelen esetben a másodikhoz, tehát az els® oszlop még mindig Hessenberg alakú marad. Lehetne ilyet csinálni ortogonális mátrixokkal is, csak azzal az a baj, hogy satbilabb algoritmus, de több a m¶velet igénye. A másik módszer, hogy hasonló mátrixok sorozatát generáljuk úgy, hogy reménykedünk abban, hogy a határértéke az el®adás elején említett R vagy D. A következ® {Ak } mátrix sorozatot képezzük (i) amenyiben adott az Ak mátrixunk akkor azt bontsuk fel Ak = Mk Rk alakra, ahol Rk fels® trianguláris, Mk reguláris (ii) Ak+1 def = R

k Mk Meg lehet mutatni, hogy ez hasonló mátrixok sorozata lesz. 11.2 Állítás (i) Ak hasonló A1 -hez. MÁTRIXOK SPECIÁLIS ALAKRA TRANSZFORMÁLÁSA (ii) 55 −1 Ak = (M1 M2 . Mk−1 )−1 A1 (M1 M2 Mk−1 ) = Tk−1 A1 Tk−1 | {z } Tk−1 (iii) Ak1 = Tk Uk ahol Uk a megfelel® R-ek szorzata (R1 R2 . Rk ) Bizonyítás. (ii) ⇒ (i) (ii)-t k szerinti indukcióval lehet bizonyítani Ha feltételezzük, hogy állítás: Ak -ra igaz az Ak+1 = Mk−1 Ak Mk = Mk−1 (M1 M2 . Mk−1 )A1 (M1 M2 Mk−1 )Mk A (iii)-t is be lehet látni k szerinti indukicóval, de ett®l most eltekintünk. 11.21 LR-transzformáció (i) Ak−1 = Lk−1 Rk−1 (ii) Ak = Rk−1 Lk−1 Kérdés az, hogy ez a sorozat létezik-e minden k-ra és egyértelm¶-e? Ha az A1 reguláris, akkor az LR felbontása egyértelm¶ tehát utánna is mind egyértelm¶ lesz, így az egyértelm¶séggel nincs baj (hiszen hasonlo mátrixokat csinálunk). Az egzisztenciával baj van mivel nem tudjuk azt

garantálni, hogy minden k-ra létezni fog ilyen felbontás. Magára az A1 -re lehetne ilyen feltételt mondani, ha A1 minden f®minora 0-tól különböz® akkor létezik neki LR felbontása, de nincs olyan értélmes feltétel ami az egzisztenciát garantálná, még reguláris A1 mellet is bármely k-nál megszakadhat a felbontás. Elegend® feltételt lehet mondani arra, hogy az Ak kovergens legyen és a határértéke fels®trianguláris legyen. Elegend® feltétel a következ®: 11.3 Tétel Ha A1 sajátértékeire |λ1 | > |λ2 | · · · |λn | > 01 , létezik minden k-ra Ak , az felírásban szerepl® X −1 és mátrixok mindegyikének létezik LR felbontása, akkor Ak olyan fels®trianguláris mátrixhoz konvergál melynek a f®átlójában A1 sajátértékei állnak. X Ha minden sajátérték különböz® akkor diagonizálható. 11.22 QR-transzformáció (i) Ak−1 = Qk−1 Rk−1 (ii) Ak = Rk−1 Qk−1 Az els® el®nye a QR transzformációnak, hogy mindig

alkalmazható, mivel tetsz®leges mátrixnak létezik QR felbontása (mi a bizonyításánál feltettük, hogy a kiindulási mátrix reguláris). Másik el®nye, hogy a szimmetriát meg®rzi: Ak = Q−1 Ak−1 Qk−1 = QTk−1 Ak−1 Qk−1 Ebb®l pedig már lehet indukcióval bizonyítani a szimmetria meg®rzését. A konvergenciához is viszonylag egyszer¶bb feltételek kellenek, és a numerikus stabilitása is jobb (a kerekítési hiba nem annyira vészes). 11.23 RT R-transzformáció T (i) Ak−1 = Rk−1 Rk−1 T (ii) Ak = Rk−1 Rk−1 1 ez a feltétel azt is jelenti, hogy A -nek van n darab különböz® sajátértéke s®t azt is, hogy A reguláris, mivel a legkisebb 1 1 abszolútérték¶ sajátérték is nagyobb mint 0 MÁTRIXOK SPECIÁLIS ALAKRA TRANSZFORMÁLÁSA 56 Ez a felbontás csak szimmetrikus mátrixoknál jöhet szóba. Csak akkor érdemes alkalmazni, ha valós a Choleskyfelbontás, ez pedig akkor teljesül, ha A1 pozitív denit és ekkor minden Ak

pozitív denit lesz Ha az A1 pozitív denit, akkor diagonális domináns mátrixhoz konvergál a sorozat (tehát a f®átlóban a sajátértékeket tartalmazza). Egy egy lépés számítása O(n3 ) mindhárom módszernél, ha viszont el®tte tridiagonális alakra hozzuk a mátrixot akkor már csak O(n) a m¶veletigény, fels® Hessenbergnél O(n2 ). Tehát ezeknél az algoritmus családoknál érdemes el®tte speciális alakra hozni a mátrixot Fejezet 12 12.1 Iterációs módszerek bevezetése Ax = a (12.1) reguláris, a ∈ R. Legyen x∗ ∈ R a 121-es rendszer egyértelm¶en létez® megoldása (Ax∗ = a) Hogyan lehetne a 12.1 egyenletrendszert nem eliminációs módszerrel megoldani? Úgy lehetne, hogy olyan vektorsorozatot konstruálnánk ami ehhez a megoldáshoz konvergál Hogyan lehetne olyan xk közelít® megoldásokat konstruálni, hogy xk x∗ ? Alakítsuk át a 12.1-es egyenletrendszert a következ® alakra: A ∈ Rn×n x = Bx + b (12.2) úgy, hogy 12.1⇔122

(A legtriviálisabb megoldás az lenne, ha mindkét oldalhoz hozzáadnánk az x vektort a-t pedig átvinnénk a másik oldalra. Az erdmény ekkor: x = (A + I)x − a) Ha ekvivalens átalakítások alapján felírtuk a 12.2-es rendszert, akkor ennek alapján tudunk kostruálni egy xk sorozatot rekurzióval. Válasszunk egy tetsz®leges x0 kezd®vektort (xk ∈ Rn ) és képezzük: xk+1 = Bxk + b (12.3) képletnek megfelel® xk iterációs vektorsorozatot. B az iterációs mátrix, xk+1 = Bxk +b-el számolt sorozat a iterációs sorozat, 12.3 az iterációs módszer Egyújabb lépés kiszámolása O(n2 ) m¶veletet jelent Addig éri meg számolni amíg k < n. A kérdés az, hogy mikor lesz igaz, hogy a vektorsorozat a megoldáshoz konvergál? Nyilván akkor ha a hiba 0-hoz tart. 12.1 Deníció ek = xk − x∗ vektort hibavektornak nevezzük ( a k-dik közelítés hibája) 12.2 Állítás xk x∗ ⇔ ek 0 A konvergencia vizsgálatánál azt fogjuk nézni, hogy ek mikor tart

0-hoz (mármint a 0 vektorhoz). ek 0, ha ||ek || 0 (többnyire majd ezt fogjuk vizsgálni). Ha könnyítünk egy kicsit a feltételeken és csak elegend® feltételt mondunk, máris könnyebb helyzetben vagyunk: hiszen van egy számsorozat és hogy az 0-hoz tart-e, ennek az igazolásához fels® korlátokat kell megadni, olyan fels® korlátokat, hogy a fels® korlátok 0-hoz tartsanak. 12.3 Állítás ek = B k e0 Bizonyítás. k szerinti teljes indukcióval k = 0-ra (12.4) teljesül, tegyük fel, hogy k-ra igaz és vizsgáljuk k + 1-re: xk+1 x∗ = Bxk + b = Bx∗ + b 57 ITERÁCIÓS MÓDSZEREK BEVEZETÉSE 58 egyenletekb®l következik (amelyek a (12.2)-es egyenletb®l következnek), hogy ek+1 = xk+1 − x∗ = B(xk − x∗ ) = Bek = B(B k e0 ) = B k+1 e0 12.4 Állítás Tetsz®leges x0 mellet akkor és csak akkor teljesül xk x∗ , ha %(B) < 1 (Másként: a 12.3 módszer akkor és csak akkor globálisan konvergens, ha %(B) < 1) Bizonyítás. ⇐ Legyen

%(B) < 1, ekkor biztosan van olyan k.k mátrixnorma, amelyre ||B|| < 1 (124) alapján bármely x0 kezd®vektor mellett a következ® teljesül: kek k = kB k e0 k ≤ kB k kke0 || ≤ kBkk ke0 || 0 | {z } 0 kBkk 0-hoz tart hiszen B 1-nél kisebb. Ezzel csináltunk egy olyan fels®korlátját a hibavektornak, amely 0-hoz tart. ⇒ Ha globálisan konvergens az iteráció, akkor %(B)-nek kissebbnek kell lennie, mint 1. Ennek az igazolásához indirekt bizonyítást alkalmazunk Tegyük fel hogy, 123 módszer globálisan konvergens, de van olyan λ sajátértéke B -nek, hogy |λ| > 1. Mivel feltettük, hogy globálisan konvergens a módszer ezért mindegy, hogy milyen értéket választunk kezd®értéknek mindig konvergálni fog. Válasszuk úgy a kezd®rtéket, hogy a kezd® hiba (e0 ) pontosan egy λ-hoz tartozó sajátvektor legyen. Ekkor viszont ellentmondáshoz jutunk: 0 ← kek k = kB k e0 k = kλk e0 k = |λ|k ke0 k 9 0 Ezzel ellentmondásra jutottunk. %(B) akkor és

csak akkor kisebb, mint egy ha van olyan ||.|| mátrixnormája ami kisebb, mint 1 12.5 Állítás a 123-as iterációs módszerre a következ® három állítás ekvivalens: (i) 12.3 módszer globálisan konvergens (ii) %(B) < 1 (iii) létezik olyan ||.|| mátrixnorma maelyben ||B|| < 1 Gyöngébben fogalmazva: ha tudunk mondani egy olyan mátrixnormát amiben a ||B|| < 1, akkor a 12.3-as módszer globálisan konvergens. 12.6 Következmény Ha a |||| mátrixnomában ||B|| < 1, akkor 123 globálisan konvergens 12.7 Példa 1 xk+1 = 4 1 8 1 8 | Mivel ||B||∞ < 1 ezért az iteráció konvergens1 0 1 4 1 4 − 81  xk  +b 0 0 {z } B 12.8 Tétel legyen ||B|| < 1, ekkor tetsz®leges x0 -ra igaz: (i) (ii) (iii) xk x∗ kek k ≤ kBkk ke0 || kek k ≤ kBk 1−kBk kxk−1 − xk || mátrixok végtelen normája úgy számítható, hogy soronként összeadjuk a komponenseket és az így keletkezett összegek közül a legnagyobbat vesszük. 1

REGULÁRIS SZÉTVÁGÁSOK (iv) kek k ≤ kBkk 1−kBk kx0 59 − x1 || (iii)-at és (iv)-et eektíven ki lehet számolni. Mivel mindegy, hogy milyen x0 -ból indulunk ezért kényelmesebb ha b-t választjuk x0 -nak (v) kek k ≤ kBkk 1−kBk kbk Ha olyan esetre nézzük (v)-t amikor ||B|| < 1, akkor ez egy jó fesl® hibakorlát lesz mivel 0-hoz tart. Végig igaz volt, hogy a vizsgált vektornorma és mátrixnorma kompatibilis volt egymással. Egy iterációs módszert egyértelm¶en meghatároz a B iterációs mátrix és a b iterációs vektor. Hogyan lehet ilyen iterációs módszert csinálni? Reguláris szétvágással több iterációs módszert is el® lehet állítani. 12.2 Reguláris szétvágások 12.9 Deníció A=T −S az A mátrix reguláris szétvágása, ha T reguláris. Nyilván egy adott A mátrixnak végtelen sok reguláris szétvágása van és ha egyet veszünk ezek közül, akkor a következ®képpen csinálhatunk ekvivalens átalakításokka a

12.3-hez hasonló iterációt: −1 −1 Ax = a ⇔ (T − S)x = a ⇔ T x = Sx + a ⇔ x = T a. | {z S} x + T | {z } B b Tehát minden reguláris szétvágás esetén tudunk csinálni egy iterációs módszert. Mik a legyakrabban használt reguláris szétvágások? Vegyük az A = D − L − R reguláris szétvágását:  a11   0 D=  .  . 0 0 . a22 . . 0 . 0   0 0  .   .   L = −  a22 0   . .  . 0  ann an1 . . . . an,n−1   0 0 a12  .   .  R = − 0 0  . .  . 0 0 0 . . . . 0 a1n  . .     an−1,n  0 Továbbiakban mindig tegyük fel, hogy D reguláris és a f®átlójában nincsenek 0-k. 12.10 Deníció A er®sen reguláris, ha A reguláris és aii 6= 0 i = 1, 2 , n 12.11 Példa A diagonális domináns és a pozitív denit mátrixok er®sen regulárisak Ez azért fontos mert er®sen reguláris A mátrixok esetén nyugodtan lehet

csinálni a reguláris szétvágásokat. Négy fontos reguláris szétvágás 12.21 Jacobbi-iteráció (J-módszer) T = D , S = L + R, ekkor: BJ −1 −1 = T −1 S = D−1 (L + R) = D | {z R} | {z L} + D L̂ bJ xk+1 R̂ = T −1 a = D−1 a = BJ xk + bJ deníció szerint: D−1 L, R̂ deníció szerint: D−1 R Ez az iteráció akkor és csak akkor konvergál a megoldáshoz, ha BJ spektrálsugara kisebb, mint 1 vagy ||BJ || < 1. L̂ A JACOBBI- ÉS A SEIDEL-MÓDSZER KONVERGENCIÁJA 60 12.22 (Gauss-)Seidel-iteráció (S-módszer) T = D − L, S = R, ekkor: BS bS xk+1 = T −1 S = (D − L)−1 R = (D(I − D−1 L))−1 R = (I − L̂)−1 D−1 R = T −1 a = (D − L)−1 a = BS xk + bS is reguláris mátrix. A gyakorlatban nem így kell majd számolni A harmadik és negyedik módszer ismertetéséhez bevezetünk egy ω paramétert. Legyen ω > 0 való rögzített paraméter. T A=D−L−R= 1 1 D − (L + R + ( − 1)D) ω ω Miért jó, hogy ω-t

behoztuk? Az ω paraméter különböz® választásaival befolyásolni tudjuk az iterációs mátrix spektrálsugarát, hogy milyen gyors legyen a konvergencia. Az egy dolog, hogy a módszer akkor és csak akkor konvergál, ha %(B) < 1 de nyilván, ha a következ® hibaképletekre gondolunk: ||ek || ≤ ||B||k ||e0 || látható, hogy minél kisebb a %(B) annál gyorsabb a konvergencia. 12.23 Jacobbi-féle túlrelaxációs módszer (J(ω)-módszer) Legyen T = ω1 D S = L + R + ( ω1 − 1)D Az ω-t relaxációs paraméternek nevezik ezért hívják az ilyen módszereket relaxációs módszereknek. Amikor ω > 1 túlrelaxációról beszélünk. BJ(ω) bJ(ω) = T −1 S = ωD−1 (L + R + ( 1 − 1)D) = ω(L̂ + R̂) + (1 − ω)I ω = T −1 a = ωD−1 a Ha az ω paramétert 1-nek választjuk, akkor éppen a Jacobbi-iterációt kapjuk, tulajdonképpen a Jacobbimódszer a J(ω)-módszer speciális esete. 12.24 Szukszecesszív túlrelaxációs módszer (S(ω)-módszer) Legyen

T = ω1 D − L, S = R + ( ω1 − 1)D BS(ω) bS(ω) xk+1 1 1 = T −1 S = ( D − L)−1 (R + ( − 1)D) ω ω 1 −1 1 −1 = (I − ω L̂) ( D) (R + ( − 1)D) = (I − ω L̂)−1 (ω R̂ + (1 − ω)I) ω ω 1 −1 −1 = T a = ( D − L) a ω = BS(ω) xk + bS(ω) A B mátrixot kiszámolni meglehet®sen költséges ezért a kiindulási A mátrixra célszer¶ feltételeket mondani: ha az A mátrixra ilyen és olyan feltétel teljesül, akkor az iterációs módszer (úgy értve, hogy a 4 közül valamelyik) konvergens. 12.3 A Jacobbi- és a Seidel-módszer konvergenciája 12.12 Tétel Ha ||L̂ + R̂|| < 1 valamilyen mátrixnormában, akkor a Jacobbi-módszer konvergens Ez egy triviális következménye annak, hogy ha az iterációs mátrix valamilyen nomrája kisebb mint 1, akkor a módszer konvergens. Hogyan kaphatjuk meg az L̂ + R̂ mátrixot? Úgy, hogy A-ban a f®átlóbeli elemek helyére 0-t írunk, a többi elemnek a (−1) szeresét vesszük és minden sort

leosztunk a diagonális elemmel (mármint az eredetivel). A 12.12 tétel jó a Jacobbi-iterációra, ha azonban ezen egy kicsit er®sítünk, akkor a Seidel-módszerre is tudunk valamit mondani. A JACOBBI- ÉS A SEIDEL-MÓDSZER KONVERGENCIÁJA 61 12.13 Állítás Ha ||L̂|| + ||R̂|| < 1, akkor a Seidel-módszer is konvergens Bizonyítás. Meg kell nézni hogyan alakul a hiba a Seidel-iterációnál xk+1 = BS xk + bS = (I − L̂)−1 R̂xk + bS Ha behelyettesítjük a pontos megoldást, akkor x∗ = (I − L̂)−1 R̂x∗ + bS Az el®zö két egyenlet különbségének segítségével számítjuk a k + 1-ik közelítés hibáját: ek+1 (I − L̂)ek+1 ek+1 = (I − L̂)−1 R̂ek = R̂ek = L̂ek+1 + R̂ek Felhasználva a háromszög egyenl®tlenséget: ||ek+1 || = ||L̂ek+1 + R̂ek || ≤ ||L̂ek+1 || + ||R̂ek || ≤ ||L̂|| ||ek+1 || + ||R̂|| ||ek || Az el®zö egyenl®tlenségek elejét és a végét tekintve: (1 − ||L̂||) ||ek+1 || ||ek+1 || ≤ ||R̂||

||ek || ≤ ||R̂|| 1 − ||L̂|| ||ek || Az ||L̂|| + ||R̂|| < 1 feltételb®l következik, hogy ||ek || szorzója 1-nél kisebb szám, tehát a hiba 0-hoz tart. Fejezet 13 13.1 Tétel Ha a J-módszer konvergens, akkor a J(ω)-módszer is konvergens, tetsz®leges 0 ≤ ω ≤ 1-re Bizonyítás. BJ a J-módszer tartozó iterációs mátrix, a J-módszer konvergens pontosan akkor ha BJ spektrálsugara kisebb mint 1 (%(BJ ) < 1). Legyenek BJ sajátértékei λ1 , λ2 , . , λn és tudjuk, hogy %(BJ ) < 1 A J(ω)-módszerhez tartozó iterációs mátrix a BJ(ω) , a két módszer között a következ® összefüggés vehet® észre: BJ(ω) = ωBJ + (1 − w)I Ha a J-módszerr®l tudjuk, hogy konvergál a megoldáshoz akkor, hogy jön ki, hogy a J(ω)-módszer is konvergál? Jelöljük a J(ω)-módszer sajátértékeit µ1 , µ2 , . , µn -el Mikor igaz, hogy %(BJ ) < max1≤i≤n |µi | < 1? Tekintsük a P (x) def = ωx + 1 − ω -t, ekkor P (BJ ) = BJ(ω)

és µ1 = P (λ1 ), µ2 = P (λ2 ), . , µn = P (λn ) λi -re van fels®korlátunk, mit tudunk ez alapján µi -kr®l? |µi | = |p(λi )| = |ωλi + 1 − ω| ≤ |ωλi | + |1 − ω| 1. = |ω| |λi | + |1 − ω| = ω |λi | + 1 − ω < ω1 + 1 − ω = 1 1. azért lehetséges mivel ω-ra kiötöttük, hogy 0 és 1 közé esik ezért 1 − ω pozitív lesz ezért elhagyhatjuk az abszolút értéket. Olyan tételeket mondunk ki, hogy ha az eredeti mátrix ilyen és ilyen tulajdonságú, akkor biztosak lehetünk benne, hogy ez és ez a módszer konvergens. 13.1 Az iterációs módszerek konvergenciája diagonális domináns A együtthatómátrixok esetén 13.2 Tétel Ha A diagonális domináns, akkor mind a J-módszer mind az S-módszer konvergens A tétel bizonyításához el®ször megnézzük, hogy az iterációnál használt fogalmakkal mikor lesz lesz egy mátrix diagonális domináns. 13.3 Állítás A akkor és csak akkor diagonális domináns, ha ||BJ ||∞ < 1

||BJ ||∞ = ||L̂ + R̂||∞ = ||D−1 L + D−1 R||∞ < 1 Bizonyítás. A BJ mátrixot úgy kapjuk, hogy A-ban a f®átló beli elemek helyére 0-t írunk Majd az eredeti megfelel® diagonális elemekkel leosztjuk a sorokat. Tehát ||BJ ||∞ < 1 részletesebben kifejezve: n X aij | |<1 1≤i≤n aii j=1 max j6=i 62 (13.1) II/14-ES TÉTEL 63 a diagonális dominancia deníciója pedig: |aii | > n X (13.2) |aij | j=1 j6=i (13.1) ekvivalens (132)-vel, hiszen ha (132)-t leosztjuk |aii |-vel, akkor megkapjuk (131)-t1 Az ekvivalenciából látszik, hogy ha az A diagonális domináns, akkor ||BJ ||∞ < 1 és ha ||BJ ||∞ < 1, akkor A diagonális domináns. Bizonyítás. (132 tétel bizonyítása) J-módszerre az el®z® állítás miatt igaz a tétel S-módszerre: a 12.13-as tételben levezettük, hogy ek+1 = L̂ek+1 + R̂ek Az i-dik komponens abszolút értéke a háromszög egyenl®tlenség után: (k+1) |ei |≤ i−1 X (k+1) |bij ||ej j=1

i = m-et rögzítjük ||ek+1 ||∞ = |ek+1 m |≤ n X |+ (k) |bij ||ej | j=i+1 m−1 X (k+1) |bmj ||ej j=1 n X |+ (k) |bmj ||ej | j=m+1 vegyük a maximális komponenst i-nek: ||ek+1 ||∞ ≤ m−1 X |bmj | ke(k+1) k∞ + j=1 | n X {z δm |bmj | ke(k) ||∞ j=m+1 } | {z γm } A diagonális dominancia miatt: δm + γm < 1 ||ek+1 ||∞ ≤ δm ||e(k+1) ||∞ + γm ||e(k) ||∞ ||ek+1 ||∞ − δm ||e(k+1) ||∞ ≤ γm ||e(k) ||∞ ||ek+1 ||∞ (1 − δm ) ≤ γm ||e(k) ||∞ γm ||e(k) ||∞ ||ek+1 ||∞ ≤ 1 − δm | {z } <1 Tehát a hibavektor 0-hoz konvergál. 13.4 Következmény Ha A diagonális domináns, akkor a J(ω)-módszer is konvergál bármely 0 < ω < 1-re Hogyan kell az ω-t választani? 13.2 II/14-es tétel 13.5 Tétel Mind a J(ω) mind az S(ω)-módszernél a konvergencia szükséges feltétele 0 < ω < 2 Bizonyítás. J(ω) estén elég annyit bizonyítani, hogy |1 − ω| ≤ %(BJ(ω) ) , hiszen %(BJ(ω) ) <

1 kell ahhoz, hogy a módszer konvergens legyen tehát |1 − ω| < 1 feltételhez jutottunk amir®l látszik, hogy ω 0 és 2 közé kell, hogy essen. 1 ehhez persze a max-t el kell mismásolni. A 4 MÓDSZER KONVERGENCIÁJA POZITÍV DEFINIT MÁTRIXOK ESETÉN 64 Alkalmazzuk azt az ismert azonosságot, hogy a mátrix nyoma megegyezik a sajátértékek összegével. BJ(ω) sajátértékeit jelöljük µi -vel. BJ(ω) f®átlójában végig 1 − ω van, ami a BJ(ω) deníciójából következik (BJ(ω) = ω(L̂ + R̂) + (1 − ωI)) n X µi = tr(BJ(ω) ) = n(1 − ω) i=1 n(1 − ω) = n X µi i=1 ⇓ n|1 − ω| ≤ n X |µi | ≤ n%(BJ(ω) ) i=1 |1 − ω| ≤ %(BJ(ω) ) S(ω) esetén az állítás a következ®: jelelölje λ1 , λ2 , . , λn a BS(ω) sajátértékeit |1 − ω| ≤ %(BS(ω) )-t kell bizonyítani. PB (λ) = det(BS(ω) − λI) BS(ω) z }| { −1 = det((I − ω L̂) (ω R̂ + (1 − ω)I) −λI) = det((I − ω L̂)−1 ) det(ω R̂ +

(1 − ω)I − λ(I − ω L̂)) {z } | 1 mivel a I − ωL̂-t vizsgálva láthajuk, hogy L̂ szigorúan alsótrianguláris (a f®tlójában 0-k vannak), I − ωL̂ egy alsótrianguláris mátrix amelynek a f®átlójában csupa 1-es áll. Az invertálás után is csupa 1-es áll a f®tlóban, így a determinánsa egy lesz. A sajátértékek szorzata megegyezik a determináns értékével. A λ = 0 értéket behelyettesítve a baloldalnál azt kapjuk, hogy a sajátértékek szorzata. n Y λi = (1 − ω)n ⇒ |1 − ω|n = i=1 n Y n |λi | ≤ %(BS(ω) ) i=1 13.3 A 4 módszer konvergenciája pozitív denit mátrixok esetén 13.6 Segédtétel Ha mind A, mind az A − H T AH pozitív denit, akkor a %(H) < 1 Bizonyítás. Legyen λ a H mátrix tetsz®leges sajátértéke az u ∈ Cn sajátvektorral. u (A − H AH)u > 0 (⇒ uH Au > uH H T AHu) egyenl®tlenségek felhasználásával: H T Az uH Au > 0 és az uH Au > uH H T AHu = (λu)H A(λu) = |λ2 |uH Au Ha

két szélét leosztjuk uH Au-val, akkor 1 > |λ2 |-t kapunk. Tehát van egy pozitív denit mátrixunk az A, veszünk valamilyen H mátrixot és kiszámoljuk az új mátrixot Ha A még mindig pozitív denit marad, akkor ez valami olyasmit jelent, hogy a H az kicsi. A − H T AH -t. 13.7 Deníció denit. Tetsz®leges A-ra az A = T − S p-reguláris szétvágás, ha T reguláris és T T + S pozitív 13.8 Segédtétel Ha A pozitív denit és A = T − S p-reguláris szétvágás, akkor %(B) = %(T −1 S) < 1 (tehát az iteráció konvergens) A 4 MÓDSZER KONVERGENCIÁJA POZITÍV DEFINIT MÁTRIXOK ESETÉN 65 Bizonyítás. Az el®z®ek alapján elég belátni, hogy az A − B T AB is pozitív denit (hiszen akkor %(B) < 1 ) Ekkor S = T − A és B = T −1 S = T −1 (T − A) = I − T −1 A: A − B T AB = = = = = = A − (I − T −1 A)T A(I − T −1 A) = A − (I − A(T −1 )T )(A − AT −1 A) A − (A − A(T −1 )T A − AT −1 A + A(T −1 )T

AT −1 A) A(T −1 )T A + AT −1 A − A(T −1 )T AT −1 A (T −1 A)T A + AT −1 A − (T −1 A)T AT −1 A (T −1 A)T (A + T T T −1 A − AT −1 A) (T −1 A)T (T + T T − A)T −1 A) = (T −1 A)T (T T + T − A )(T −1 A) | {z } S = (T −1 T T A) (T + S)(T −1 A) Ha A pozitív denit, akkor tetsz®leges Z reguláris mátrixra B = Z T AZ is pozitív denit lesz és ez teljesül mivel A = T − S p-reguláris szétvágás volt. 13.9 Tétel (Konvergencia-tétel) Ha az A mátrix pozitív denit (i) (ii) (iii) (iv) a J-módszer konvergenciájához elegend®, ha a 2D − A mátrix is pozitív denit. a J(ω)-módszer konvergenciájához elegend®, ha a ω2 D − A mátrix is pozitív denit. az S-módszer mindig konvergens. az S(ω)-módszer tetsz®leges 0 < ω < 2-re konvergens A bizonyítás annyit jelent, hogy felírjuk rá a 4 módszerhez tartozó iterációs mátrixot és felírjuk rá a második segédtételt. Bizonyítás. (i) mivel T T + S = DT +

D − A = 2D − A ezért, ha 2D − A pozitív denit, akkor T T + S is pozitív denit tehát A = T − S p-reguláris szétvágás és az el®z® segédtétel miatt az iteráció konvergens. (ii) T T + S = ( ω1 D)T + ω1 D − A = ω2 D − A A (iii) S z }| { z }| { T T T + S = (D − L) + (D − L) − A = 2D − LT − L − (D − L − LT ) = D ez mindig az (ha az A mátrix pozitív denit akkor a f®átlójában pozitív számok vannak). pozitív denit, ha A (iv) T T + S = ( ω1 D − L)T + ( ω1 D − L) − A = ω2 D − LT − L − (D − L − LT ) = ( ω2 − 1)D ez pedig bármely 0 < ω < 2 esetén pozitív denit lesz. Fejezet 14 14.1 Tétel Ha egy mátrix szimmetrikus, aii > 0 és diagonális domináns, akkor pozitív denit xk+1 ek ||ek ||-ra = Bxk + b Ax = a = xk − x∗ keresünk fels® korlátot. Axk rk ≈ a = a − Axk 14.1 Utóiteráció Legyen Â−1 = A−1 xk+1 = xk + Â−1 rk Ha például az A = LR felbontással oldottuk meg a

rendszert, akkor  = L̂R̂ xk+1 Â−1 = R̂−1 L̂−1 = xk + R̂−1 L̂−1 (a − Axk ) Ezeket a képleteket ilyen alakban érdemes felírni, hogy: L̂z k R̂uk xk+1 = rk = zk = xk + uk Ha így számoljuk, akkor egy-egy lépéshez csak O(n2 ) m¶velet kell és így az egészhez is csak O(n2 ) m¶velet kell. kiszámításához tulajdonképpen egy el®rehelyettesítést kell csinálni és uk kiszámításához visszahelyettesítés kell. Lehet más fajta iterációt is el®állítani: zk xk+1 = xk + D−1 rk A D−1 jelentsen valamilyen diagonális mátrixot. A következ® közelítés legyen olyan, hogy vesszük az xk -t és adjunk hozzá korrekciót, azaz vesszük az rk vektor komponenseit és megszorozzuk egy-egy számmal ®ket, ezt jelenti a D−1 rk kifejezés. Ilyen értelemben próbálnánk csökkenteni a hibát Olyat csinálhatnánk, hogy ahol rk -ban nagy volt a hiba ott D-ben egy nagy szorzót vennénk és akkor azt a komponensét a hibának ilyen módon 66

KEREKÍTÉSI HIBA AZ ITERÁCIÓS MÓDSZEREKNÉL 67 csökkentenénk. Ha azt mondanánk, hogy ez a D legyen az A mátrix diagonálisában lév® elemekb®l álló mátrix, akkor a J-módszert kapnánk más formában. xk+1 = D−1 (L + R)xk + D−1 a = xk − D−1 (Axk − a) = xk + D−1 rk A=D−L−R A J(ω)-módszert is meglehet hasonló módon adni. xk+1 = xk + ωD−1 rk Ez nem más, mint a J(ω)-módszer. Tehát látszik, hogy a reziduum1 fogalomból kiindulva, le lehet vezetni többféle iterációs módszert, részben a korábban megismerteket is. Amit mi felírunk az iterációs módszereknél az csak elméletben igaz. A gyakorlatban itt is történik kerekítési hiba 14.2 Kerekítési hiba az iterációs módszereknél elmélet: xk+1 = Bxk + b gyakorlat: z k+1 = Bz k + b + dk tehát a gyakorlat úgy néz ki, mint ha az eredeti formulával számolnánk csak minden lépésben rárakódik valamilyen kerekítési hiba (jelen esetben dk ). Tegyük fel, hogy ||dk || < δ

minden k-ra. A kiindulási feltételünk legyen ugyanaz: z0 = x0 A kerekítési hiba hatásánál a z k − xk különbségre vagyunk kíváncsiak (méginkább egy fels® korlátjára): ||fk || f k+1 def = = ||z k − xk || <? z k+1 − xk+1 = Bf k + dk A 0. lépésnél mindkett® megegyezik Az els® lépésnél (majd rekurzióval folytatva): f1 f k+1 = z 1 − x1 = d1 = Bf k + dk Úgy lehetne egyszer¶síteni a dolgokat, ha azt mondanánk, hogy a d-knél az indext®l szabaduljunk meg. Mondjuk azt, hogy ezekre a kerekítési hibavektorokra van valamilyen k-tól független globális hibakorlátunk. Erre szolgál a ||dk || < δ feltétel az eszmefuttatás elején. Így már mondhatjuk a következ®ket: ||f 1 || ≤ δ ||f k+1 || ≤ ||B|| ||f k || + δ ||f 2 || ≤ ||B||δ + δ ||f k || ≤ (||B||k + ||B||k−1 + · · · + ||B|| + 1)δ ||f k || ≤ ||B||k+1 1 − ||B||k+1 δ= δ ||B|| − 1 1 − ||B|| 1 Bakos bácsi szerint maradékot jelent, a Matematikai

kislexion már érdekesebb véleményen van: valamely f komplex függvény egy z0 izolált szinguláris pontjához tartozó1 ésR res[f, z0 ]-lal jelölt reziduumán az f függvény "z0 körüli" Laurent sorában a −1-edik hatvány együtthatóját, vagyis a c−1 = 2πi c f (ζ)d(ζ) komplex számot értjük, ahol a C görbén és annak belsejében z0 -on kívül minden pont f reguláris pontja (a szerk.) KONDÍCIÓSZÁM 68 Abban az esetben, ha vesszük az elméleti iterációt és tudjuk, hogy B normája kisebb mint 1, akkor már elméletben iterálna. A gyakorlati konvergenciához azt kellene nézni, hogy: ||z k − x∗ || = || (z k − xk ) + (xk − x∗ ) || | {z } | {z } ek fk ≤ ||f k || + ||ek || ≤ 1 − ||B||k+1 ||B||k+1 δ+ ||b|| 1 − ||B|| 1 − ||B|| Tehát a gyakorlatban számolt zk sorozatra ilyen korlátot lehet adni. 14.3 Kondíciószám 14.2 Deníció Tetsz®leges reguláris T mátrix esetén a k(T ) def = ||T || ||T ||−1 -t a T

vonatkozó) kondíciószámnak nevezzük. Ha T nem reguláris legyen k(T ) = ∞ mátrix (||.|| normára Mindig olyan normát használunk, ami nekünk kényelmes (1-es, 2-es, végtelen, Frobénius norma). Általában minden egyes norma esetén más-más szám lesz. De látszik a képletekb®l, hogy bizonyos értélemben jellemzi a lienáris algebrai problémákat az, hogy ez a szám mekkora. Tekintsük a következ® problémákat: Ax = a Ax = I (A − λI)x = 0 mind a három feladatosztálynál meg lehet mutatni, hogy az A mátrix kondíciószáma a dönt®. Mi inkább csak az els®r®l fogunk beszélni, de el®bb a kondíciószám tulajdonságait vizsgálgatjuk. 14.3 Állítás Ha |||| norma származtatott norma, akkor a kondíciószám nagyobb egyenl® mint 1 (1 ≤ k(T )) Bizonyítás. Itt reguláris mátrixról beszéltünk Felírjuk az egységmátrixot: 1 = ||I|| = ||T T −1 || ≤ ||T || ||T −1 || = k(T ) A sajátértékekr®l is érdemes szót ejteni, mivel láttuk, hogy

a lineáris egyenletrendszereknél konvergenciánál is komoly szerepe van. Lehet különböz® becsléseket megadni a kondíciószámra melyekben sajátértékek szerepelnek 14.4 Állítás max |λi | k(T ) ≥ 1≤i≤n min |λi | 1≤i≤n ahol T sajátértékei λ1 , λ2 , . , λn , T −1 sajátértékei λ1 1 , λ1 2 , , λ1 1 Bizonyítás. Azt már tudjuk, hogy ||T || ≥ %(T ), ezt lehet alkalmazni egy kicsit trükkös módon k(T ) = ||T || ||T −1 || ≥ %(T )%(T −1 ) = max |λi | max | 1≤i≤n 1≤i≤n max |λi | 1 1≤i≤n |= λi min |λi | 1≤i≤n Úgy lehet ezt az állítást olvasni, hogy ha van egy olyan T mátrixunk aminek vannak nagyon nagy és nagyon kicsi abszolút érték¶ sajátértékei, akkor annak a kondíciószáma is nagy lesz. Minél nagyobb a kondíciószám annál gyengébben meghatározott a feladat, annál jobban elbillenhet különböz® hibaforrások hatására. Következ® kérdés az lenne, ha valamilyen transzformációt

hajtunk végre a T mátrixon, akkor hogyan változik a kondíciószám. Ha kettes normával dolgozunk és ortogonális transzformációt csinálunk, akkor nem romlik a helyzet. Ugyan ez a helyzet ortogonális hasonlósági transzformáció esetén PERTURBÁCIÓ 69 14.5 Állítás A kettes norma esetén a legegyszer¶bb belátni a következ®ket: (i) k(QT ) = k(T ) (ii) k(QT QT ) = k(T ) Bizonyítás. Ha a Q ortogonális mátrix, akkor a kettes normája 1 (i) ||C||2 = p %(C T C) q q = ||QT ||2 ||T T QT ||2 = %((T T QT )(QT )) %((T T QT )T (T T QT )) q q = %(T T T ) %((T T QT )T (T T QT )) q q = ||T ||2 %((QT )(T T QT )) = ||T ||2 %((T T QT )(QT )) k2 (QT ) = k2 (T ) (ii) mivel ||C||2 = ||C T ||2 és az (i)-t is felhasználva: k(QT T Q) = k(T Q) = k((T Q)T ) = k(QT T T ) = k(T T ) = k(T ) Tehát ortogonális transzformációk esetén a kondíciószám nem változik. 14.4 Perturbáció Van egy lineáris egyenletrendszerünk és valahogy megváltoztatjuk, akkor hogyan

változik a megoldása. Gyengén meghatározott egy egyenletrendszer, ha csak egy kicsit változtatunk rajta, akkor nagyon megváltozik a megoldás. Legyen x∗ az eredeti egyenletrendszer megoldása x̃ a perturbált egyenletrendszer megoldása. Ax∗ = a (A + F )x̃ = a + g (eredeti egyenletrendszer) (perturbált egyenletrendszer) Az abszolút hibára ||x∗ − x̃|| <? és a relatív hibára mind az F reguláris az inverzekkel átszorozhatunk. ||x∗ −x̃|| ||x∗ || <? lennénk kíváncsiak. Feltéve, hogy mind az A x∗ − x̃ = A−1 a − (A + F )−1 (a + g) = (A + F )−1 ((A + F )A−1 a − a − g) = (A + F )−1 (F A−1 a − g) = (A + F )−1 (F x∗ − g) Tehát a következ®höz jutottunk: ||x∗ − x̃|| ≤ ||(A + F )−1 || (||F || ||x∗ || + ||g||) (14.1) Ezzel még sehol sem vagyunk, mivel a jobb oldalon szerepel az x∗ . Valami olyat fels® korlátot kell produkálni, ahol a jobb oldalon már ismert mennyiségek szerepelnek. Megnézzük,

hogy milyen esetekben létezik az (A + F )−1 és ilyen esetekben hogy lehet a (14.1)-re fels® korlátokat adni. 14.6 Állítás Ha valamely származtatott mátrixnormában ||A|| < 1, akkor az (I + A)−1 létezik és ||(I + A)−1 || ≤ 1 1 − ||A|| PERTURBÁCIÓ 70 Bizonyítás. Legyen x 6= 0 tetsz®leges vektor Ekkor ||(I + A)x|| = ||x − (−Ax)|| ≥ | ||x|| − ||Ax|| | ≥ ||x|| − ||Ax|| ≥ ||x|| − ||A|| ||x|| = (1 − ||A||) ||x|| > 0 Tehát (I + A)x 6= 0, vagyis I + A reguláris. Legyen C def = (I + A)−1 . Mivel 1 = ||I|| = ||(I + A)C|| = ||C − AC|| ≥ ||C|| − ||A|| ||C|| = (1 − ||A||)||C|| = (1 − ||A||)||(I + A)−1 || ezzel beláttuk az inverz normájára vonatkozó egyenl®tlenséget is. 14.7 Állítás Ha valamely származtatott mátrixnormában az ||A|| ||F || < 1, akkor az (A + F )−1 létezik és az ||(A + F )−1 || ≤ ||A−1 || 1 − ||A−1 || ||F || Bizonyítás. ||(A + F )−1 || = ||(A(I + A−1 F ))−1 || = ||(I +

A−1 F )−1 A−1 || ≤ ||(I + A−1 F )−1 || ||A−1 || ||A−1 || 1 ||A−1 || ≤ ≤ −1 1 − ||A F || 1 − ||A−1 || ||F || Ott hagytuk abba, hogy: ||x∗ − x̃|| ≤ ||(A + F )−1 || (||F || ||x∗ || + ||g||) Következ®t lehet csinálni: ||x∗ − x̃|| ||x∗ || ≤ = = ||A−1 || 1 − ||A−1 || ||F ||    ||g|| ||g|| ||A|| ||A−1 || = ||F || + ∗ ||F || + ||x || 1 − ||A−1 || ||F || ||a||     −1 −1 ||F || ||g|| ||A || ||A|| ||A || ||A|| ||F || ||g|| + + = || 1 − ||A−1 || ||F || ||A|| ||a|| ||A|| ||a|| 1 − ||A|| ||A−1 || ||F ||A||   ||F || ||g|| k(A) + 1 − k(A) ||F || ||A|| ||a|| ||A||  Tárgymutató k -dik közelítés tr, 34 hibája, 56 iterációs módszer, 56 iterációs sorozat, 56 iterációs vektorsorozat, 56 általánosított trianguláris felbontás, 22 elemi hasonlósági transzformáció, 37 J(ω)-módszer, 59 J-módszer, 58 Jacobbi-féle túlrelaxációs módszer, 59 Jacobbi-iteráció, 58

Jordan-elimináció, 9 abszolút hiba, 3 abszolút hibakorlát, 3 alsó Hessenberg mátrix, 4 alsó tringuláris mátrix, 3 közelítés hibája, 3 küls® szorzat, 11 kanonikus felbontás, 28 karakterisztikus polinom, 33 kompatibilis (norma), 44 kondíciószám, 67 konjugált transzponált mátrix, 35 konvergencia (mátrixsorozatoké), 48 konvergencia (vektorsorozatoké), 47 kvázi diagonális, 16 kvázi trianguláris, 16 bels® szorzat, 11 bidiagonális mátrix, 22 blokk, 14 diadikus szorzat, 11 diagonális dominancia, 5 diagonális mátrix, 3 diagonizálható (mátrix), 34 egyenletrendszerek ekvivalenciája, 6 ekvivalencia (vektornormáké), 45 elemi hasonlósági transzformációval triangula rizálás, 37 elemi mátrix átalakítások, 6 elemi permutációs mátrix, 12 eliminációs mátrix, 11 er®sen reguláris (mátrix), 58 LR algoritmus, 19 LR alkalmazásai, 21 LR egzisztenciája, 16 LR unicitása, 16 LR-felbontás, 16 f®elem, 8 F®tengely-tétel, 39 fels® Hessenberg

mátrix, 4 fels® trianguláris mátrix, 3 mátrix invertálás (Frobénius-féle), 15 mátrix invertálás (Jordan-féle), 9 mátrix nyoma, 34 mátrixnorma, 42 Gauss-elimináció, 7 Gauss-elimináció m¶veletigénye, 8 Gersgorin-tétel, 50 gyöktényez®s alak (karakterisztikus polinom), 33 oszlopnorma, 44 p-norma, 42 p-reguláris szétvágás, 63 partícionálás, 14 permutációs mátrix, 12 pozitiv denit, 39 preturbáció, 68 hasonló (két mátrix), 34 hasonlósági transzformáció, 34 hatvány módszer, 52 hermetikus mátrix, 39 hibavektor, 56 homogén rendszer, 5 reguláris szétvágás, 58 relatív hibakorlát, 3 S(ω)-módszer, 59 iterációs mátrix, 56 71 PERTURBÁCIÓ S-módszer, 59 sajátérték, 33 sajátérték multiplicitása, 34 sajátvektor, 33 Schur-féle normálforma, 36 Seidel-iteráció, 59 skalár szorzat, 11 sornorma, 44 spektrálnorma, 44 spektrálsugár, 44 származtatott mátrixnorma, 43 Szukszecesszív túlrelaxációs módszer, 59 trace, 34

triangulizálható, 34 tridiagonális mátrix, 22 unitér mátrix, 35 vektornorma, 41 72