Numerikus Analízis Király Balázs 2014.
2
Tartalomjegyzék 1. A hibaszámítás elemei 1.1. A matematika modellezés folyamata és a hibaforrások megjelenése . . 1.2. Lebegőpontos számábrázolás . . . . . . . . . . . . . . . . . . . . . . . 1.3. Hibaszámítás . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2. Lineáris egyenletrendszerek direkt megoldási módszerei 2.1. Lineáris algebrából tanult tételek . . . . . . . . . . . . . . 2.2. LER megoldása Gauss-eliminációval (GE) . . . . . . . . . 2.2.1. GE műveletigénye . . . . . . . . . . . . . . . . . . . 2.2.2. GE alkalmazásai . . . . . . . . . . . . . . . . . . . 2.2.3. GE felírása mátrix szorzásokkal . . . . . . . . . . . 2.3. LU -felbontás (Trianguláris-felbontás) . . . . . . . . . . . . 2.3.1. L és U elemeinek meghatározása: . . . . . . . . . . 2.3.2. Az LU -felbontás műveletigénye . . . . . . . . . . . 2.3.3. Megmaradási tételek . . . . . . . . . . . . . . . . . 2.4. Az LDU -felbontás . . . . . . . . . . . . . . . . . . . . . . 2.5. Az Cholesky-felbontás . . . . . . . . . . . . . . . . . . . . 2.5.1. A Cholesky-felbontás előállítása . . . . . . . . . . . 2.6. QR-felbontás (Ortogonális felbontás) . . . . . . . . . . . . 2.6.1. QR-felbontás alkalmazása LER megoldására . . . . 2.6.2. Gram-Schmidt ortogonalizáció . . . . . . . . . . . . 2.6.3. QR-felbontás Householder transzformációval . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
7 7 7 9 11 11 12 14 14 15 15 16 17 17 18 18 19 19 19 19 21
3. Mátrix- és vektornormák
25
4. Lineáris egyenletrendszer érzékenysége (kondícionáltsága)
29
5. Lineáris egyenletrendszer megoldásának iterációs módszerei 5.1. Speciális iterációs módszerek . . . . . . . . . . . . . . . . . . . . 5.1.1. Jacobi-iteráció: J (1) . . . . . . . . . . . . . . . . . . . . 5.1.2. Csillapított Jacobi-iteráció:J (ω) . . . . . . . . . . . . . 5.1.3. Gauss-Seidel iteráció:S(1) . . . . . . . . . . . . . . . . . 5.1.4. Gauss-Seidel relaxáció: S(ω) . . . . . . . . . . . . . . . . 5.1.5. Richardson-típusú iteráció: . . . . . . . . . . . . . . . . . 5.2. A kerekítési hibák hatása az iterációkra . . . . . . . . . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
31 33 33 34 35 35 37 38
6. Nemlineáris egyenletek megoldása 39 6.1. Az intervallum-felezési eljárás . . . . . . . . . . . . . . . . . . . . . . 39 6.2. Egyszerű iteráció . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 3
4
TARTALOMJEGYZÉK 6.3. 6.4. 6.5. 6.6. 6.7.
Newton-módszer . . . . . . . Húrmódszer . . . . . . . . . . Szelőmódszer . . . . . . . . . Polinomegyenletek megoldása Horner algoritmus . . . . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
7. Interpoláció 7.1. Lagrange-interpoláció . . . . . . . . . . . . . . . 7.2. Newton-interpoláció . . . . . . . . . . . . . . . . 7.3. A Csebisev polinomok . . . . . . . . . . . . . . 7.4. Inverz interpoláció . . . . . . . . . . . . . . . . 7.5. Hermite interpoláció . . . . . . . . . . . . . . . 7.5.1. Az Hermite-interpoláció speciális esetei . 7.5.2. Az Hermite interpolációs polinom felírása 7.6. Spline függvények . . . . . . . . . . . . . . . . . 7.6.1. Spline függvények előállítás . . . . . . . 8. Általánosított inverz 8.1. Az általánosított inverz előállítása 8.1.1. Rang-faktorizáció . . . . . 8.1.2. Általánosított megoldás . 8.1.3. Szinguláris felbontás . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . . .
. . . . . . . . .
. . . .
. . . . .
. . . . . . . . .
. . . .
. . . . .
. . . . . . . . .
. . . .
. . . . .
. . . . . . . . .
. . . .
. . . . .
. . . . . . . . .
. . . .
. . . . .
. . . . . . . . .
. . . .
. . . . .
. . . . . . . . .
. . . .
. . . . .
. . . . . . . . .
. . . .
. . . . .
. . . . . . . . .
. . . .
. . . . .
. . . . . . . . .
. . . .
. . . . .
. . . . . . . . .
. . . .
. . . . .
42 44 45 46 46
. . . . . . . . .
47 47 50 51 53 54 55 56 56 56
. . . .
65 66 66 67 69
9. Legkisebb négyzetek módszere 71 9.1. Legkisebb négyzetek módszerének bevezetése többváltozós szélsőérték feladatként . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 9.2. Approximáció Hilbert-térben . . . . . . . . . . . . . . . . . . . . . . . 73 10.Numerikus integrálás 10.1. Interpolációs kvadratúra formulák . . . . . . 10.1.1. Newton-Cotes formulák . . . . . . . . 10.2. Klasszikus kvadratúra-formulák . . . . . . . 10.3. Csebisev-típusú kvadratúrák . . . . . . . . . 10.4. Gauss-típusú kvadratúrák . . . . . . . . . . 10.4.1. Gauss-típusú kvadratúrák előállítása
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
77 78 78 80 83 84 85
11.Vizsgakérdések 87 11.1. Definíciók, Tételek . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 11.2. Bizonyítások, Algoritmusok, Levezetések . . . . . . . . . . . . . . . . 91 12.Vizsgakérdések, Numerikus analízis 2. 93 12.1. Definíciók, Tételek . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 12.2. Bizonyítások, Algoritmusok, Levezetések . . . . . . . . . . . . . . . . 95
Előszó Jelen jegyzet a Programtervező Informatikus BSc képzés Numerikus Analízis tárgyának tematikáját öleli fel. A jegyzet fejezetei megfelelnek egy-egy előadás anyagának. A tantárgy tematikája és a jegyzet is Dr. Krebsz Anna tanárnő által tartott kétféléves numerikus analízis tárgy alapján készült.
Várható menetrend 1.ea 2.ea 3.ea 4.ea 5.ea 6.ea 7.ea 8.ea 9.ea 10.ea 11.ea 12.ea 13.ea 14.ea
A hibaszámítás elemei A LER-ek direkt megoldási módszerei A Vektor- és mátrix normák A LER-ek iterációs megoldási módszerei I. A LER-ek iterációs megoldási módszerei II. Nem-lineáris egyenletek Gyakorlás Polinom interpoláció Hermite-interpoláció, Inverz-interploáció Spline-függvények Legkisebb négyzetek módszere Numerikus integrálás Csebisev-típusú kvadratúrák Gyakorlás
1.gyak 2.gyak 3.gyak 4.gyak 5.gyak 6.gyak 7.gyak 8.gyak 9.gyak 10.gyak 11.gyak 12.gyak 13.gyak 14.gyak
5
A hibaszámítás elemei A LER-ek direkt megoldási módszerei Vektor- és mátrix normák LER-ek iterációs megoldási módszerei I. A LER-ek iterációs megoldási módszerei II. Nem-lineáris egyenletek I. Zárthelyi Dolgozat Elmarad (nemzeti ünn.) Interpoláció Spline-függvények Spline-függvények II. Legkisebb négyzetek módszere Numerikus integrálás II. Zárthelyi Dolgozat
6
TARTALOMJEGYZÉK
1. fejezet A hibaszámítás elemei 1.1. A matematika modellezés folyamata és a hibaforrások megjelenése ¶ A valóság egy részét vizsgálva igyekszünk a jelenséget matematikailag leírni, egy lehetséges matematikai modellt megalkotni. Ez általában a természettudományokban dolgozó szakember feladata a rendelkezésre álló törvények, elvek felhasználásával. ⇒ modellhiba: a valóságot csak közelíteni tudjuk. · A modell pontos megoldása gyakran nem állítható elő véges lépésben, közelítő módszerekre van szükségünk. ⇒ képlethiba: a végtelen eljárást véges sok lépés után leállítjuk. ¸ A model bemenő paraméterei általában mérési adatok, azaz pontatlanok. ⇒ mérési (vagy öröklött) hiba ¹ A közelítő módszer bemenő illetve kimenő adatait véges aritmetikában ábrázoljuk. ⇒ input hiba º A véges aritmetikában való számolás során kerekítés, túl- illetve alulcsordulás léphet fel ⇒ műveleti (kerekítési) hiba » A megvalósított közelítő módszert teszteljük, majd elvégezzük a konkrét számolást. Ha a kapott eredmény nem felel meg a valóságnak, akkor kezdjük előről a modell finomításával. 1. Definíció. A numerikus algoritmus aritmetikai és logikai műveletek véges sorozata. Definíció. A numerikus algoritmus stabil, ha a bemenő adatok kis változtatása a megoldásban is csak kis változást okoz.
1.2. Lebegőpontos számábrázolás 2. Definíció. Legyen m=
t X
mi · 2−i ,
i=1
7
(*)
8
1. FEJEZET. A HIBASZÁMÍTÁS ELEMEI
ahol t ∈ N, m1 = 1 és mi ∈ {0; 1}, (i = 2,3, . . . ). Ekkor az a = ±m · 2k , k ∈ Z alakú számot normalizált lebegőpontos számnak nevezzük. m: a szám mantisszája, melynek hossza t, k : a a szám karakterisztikája, k − ≤ k ≤ k + korlátokkal Jelölés: M = M (t, k − , k + ) = {a = ±m · 2k |k − ≤ k ≤ k + , k ∈ Z és m : mint (i)}
Következmények : ¬
1 2
≤m<1
M a 0-ra szimmetrikus ® M -ben a legnagyobb szám M∞ = +[11 . . . 1|k + ] = (1 − 2−t ) · 2k
+
¯ M -ben a legkisebb pozitív szám ε0 = +[10 . . . 0|k − ] =
1 k− − · 2 = 2k −1 2
° Az egynél nagyobb legkisebb gépi szám és az egy különbsége ε1 = [10 . . . 01|1] − [10 . . . 0|1] = 2−t · 2 = 2−t+1 A gép relatív pontosságát mutatja, gépi epszilonnak is szokás nevezni. Definíció. Az f l : R 7→ M függvényt kerekítésnek, vagy input függvénynek nevezzük, ha , ha|x| ≥ M0 Nem értelmezett, vagy ∞ 0 , ha|x| ≤ ε0 f l(x) = az x-hez legközelebbi gépi szám , haε0 ≤ |x| ≤ M0 Tétel. ∀x ∈ R, |x| < M∞ esetén |x − f l(x)| ≤
ε0 ,ha |x| < ε0 −t |x|2 ,ha |x| ≥ ε0
a relatív hibára pedig |x − f l(x)| 1 ≤ 2−t = ε1 , |x| 2 azaz csak a mantissza hosszától függ. Megjegyzés : Az M -beli alapműveletek is más tulajdonságúak. ⊕, A normalizált számokat a nagyobb karakterisztikájunak megfelelően átalakítjuk. Az egyező karakterisztika mellett a mantisszákat összeadjuk/kivonjuk. Átmenetileg nem normalizált számot kapunk. Normalizálunk.
1.3. HIBASZÁMÍTÁS
9
Furcsaságok : ¬ a⊕b = a
[1100| 1] ⊕ [1000| − 3] → [0000|1] [1100| 1]
(a ⊕ b) ⊕ c 6= a ⊕ (b ⊕ c) a = [1100| 1] b = c = [1000| − 3] i) a ⊕ b = a ⇒ (a ⊕ b) ⊕ c = a ⊕ b = a b⊕b
ii)
a ⊕ (b ⊕ b)
[1000| − 3] ⊕ [1000| − 3] 1 [0000| − 3] = [1000| − 2]
[1000| 1] ⊕ [1000| − 2] → [0001|1] [1001| 1]
® Kivonási jegyveszteség: (Közeli számok kivonása esetén a relatív pontosság rosszabb lesz.) [11011|2] ⊕ [11000|2] [00011|2] = [11000| − 1] Az 5 jegyből csak 2 értékes tizedes jegy, a többi csak helytöltő 0. √ ¯ A részeredmény nem ábrázolható, de az eredmény igen. a2 + b2 , ahol S = = max{|a|, |b|} nagy. Ekkor s 2 2 a b + S· S S alakban számolunk.
1.3. Hibaszámítás Definíció. Legyen A, B pontos érték; a, b a megfelelő közelítő értékek. ∆a = A − a: a közelítő érték hibája, |∆a| = |A − a|: a közelítő érték abszolút hibája, ∆a ≥ |∆a|: az a egy abszolút hiba korlátja, δa = ∆a ≈ ∆a : az a relatív hibája, A a δa ≥ |δa|: az a egy relatív hiba korlátja. Tétel. Az alapműveletek abszolút és relatív hibakorlátjaira: ∆a±b = ∆a + ∆b ∆a·b = |b|· ∆a + |a|· ∆b
∆ ab = ab · =
∆a |a| |b|·∆a +|a|∆b b2
+ ∆|b|b =
|a| |b| δa±b = |a±b| δa + |a±b| δb δa·b = δa + δb
δ ab = δa + δb
10
1. FEJEZET. A HIBASZÁMÍTÁS ELEMEI
Bizonyítás. Kivonás és szorzás esetén az állításokat igazoljuk, a többi állítást az olvasóra bízzuk. Kivonás: Tegyük fel, hogy A, B azonos előjelű. ∆(a − b) = (A − B) − (a − b) = (A − a) + (B − b) = ∆a + ∆b |∆(a − b)| = |∆a + ∆b| ≤ |∆a| + |∆b| ≤ ∆a + ∆b = ∆a−b ∆a ∆b a · δa b · δb ∆(a − b) = + = + a−b a−b a−b a−b a−b |a| |b| |∆(a − b)| |a||δa| |b||δb| ≤ + ≤ δa + δb = δa−b |a − b| |a − b| |a − b| |a − b| |a − b| Ha a − b kicsi, akkor a relatív hiba nagy lehet. Szorzás: Tegyük fel, hogy A, B azonos nagyságrendűek. ∆(a · b) = A · B − a · b = A · B − A · b + A · b − a · b = A(B − b) + b(A − a) = = (a + ∆a) · ∆b + b · ∆a ≈ a · ∆b + b · ∆a mert ∆a · ∆b kicsi |∆(a · b)| ≤ |a| · |∆b| + |b| · |∆a| ≤ |a| · ∆b + |b| · ∆a = ∆a·b ∆(a · b) a · ∆b + b · ∆a ∆b ∆a ≈ = + = δa + δb a·b a·b b a |∆(a · b)| ≤ |δa| + |δb| ≤ δa + δb = δa·b |a · b| Tétel. Ha f ∈ C 1 (k(a)), akkor ∆f (a) = M1 · ∆a , ahol M1 = max{|f 0 (ξ)| : ξ ∈ k(a)}. Bizonyítás. A Lagrange-féle középérték tétel segítségével: ∆f (a) = f (A) − f (a) = f 0 (ξ) · (A − a) = f 0 (ξ) · ∆a ξ ∈ k(a) |∆f (a)| = |f 0 (ξ)| · |∆a| ≤ M1 · ∆a = ∆f (a)
Tétel. Ha f ∈ C 2 (k(a)), akkor ∆f (a) = |f 0 (a)| · ∆a + M22 · ∆2a , ahol M2 = max{|f 00 (ξ)| : ξ ∈ k(a)}. Bizonyítás. A Taylor-formulából f 00 (ξ) f (A) = f (a) + f (a)(A − a) + (A − a)2 2 f 00 (ξ) ∆f (a) = f (A) − f (a) = f 0 (a)∆a + (A − a)2 2 M2 M2 2 |∆f (a)| ≤ |f 0 (a)||∆a| + |∆a|2 ≤ |f 0 (a)|∆a + ∆ 2 2 a 0
Következmény : A függvényérték relatív hibája ∆f (a) |f 0 (a)| · ∆a |a| · |f 0 (a)| ≈ = · δa = δf (a) . f (a) |f (a)| |f (a)| Definíció. A c(f, a) = ciószámának nevezzük.
|a| · |f 0 (a)| mennyiséget az f függvény a pontbeli kondí|f (a)|
11. fejezet Vizsgakérdések 11.1. Definíciók, Tételek 1. Írja le a matematikai modellezés (kör)folyamatát és a megjelenő hibákat! 5p 2. Definiálja a numerikus algoritmus fogalmát! 1p 3. Definiálja a normalizált lebegőpontos számot! 3p 4. Definiálja az input-függvényt! 2p 5. Mondja ki a lebegőpontos szám abszolút és relatív hibájára vonatkozó tételt! 2p 6. Mondja ki az összeadás abszolút hibájára vonatkozó tételt! 1p 7. Mondja ki a kivonás abszolút hibájára vonatkozó tételt! 1p 8. Mondja ki a szorzásás abszolút hibájára vonatkozó tételt! 1p 9. Mondja ki az osztás abszolút hibájára vonatkozó tételt! 1p 10. Mondja ki az összeadás relatív hibájára vonatkozó tételt! 1p 11. Mondja ki a kivonás relatív hibájára vonatkozó tételt! 1p 12. Mondja ki a szorzásás relatív hibájára vonatkozó tételt! 1p 13. Mondja ki az osztás relatív hibájára vonatkozó tételt! 1p 14. Mondja ki az alapműveletek abszolút hibáira vonatkozó tételt! 4p 15. Mondja ki az alapműveletek relatív hibáira vonatkozó tételt! 4p 16. Mondja ki a függvényérték abszolút hibájáról szóló tételeket (2db)! 4p 17. Mondja ki a függvényérték relatív hibájáról szóló tételt (következmény)! 2p 18. Definiálja az intervallumfelezési eljárást, írja le hibabecslést is! 1p 19. Írja le Gauss-elimináció során a k-adik mátrix kiszámításának képletét! 4p 20. Írja le Gauss-elimináció során a „visszahelyettesítés” képletét! 2p 87
88
11. FEJEZET. VIZSGAKÉRDÉSEK
21. Definiálja a Részleges- és a teljes főelem kiválasztás módszerét! 2p 22. LU -felbontás során L és U mátrixok elemeinek meghatározása (képlet elég). 4p 23. LU -felbontás során választható számolási sorrendek (nem csak az elnevezés). 3p 24. Definiálja a mátrix Schur-komplementerét! 2p 25. Mondja ki a GE-ra ill. az LU -felbontásra vonatkozó megmaradási tételeket! 5p 26. Cholesky-felbontás. 1p 27. Tétel a Cholesky-felbontás létezéséről. 1p 28. Ortogonális mátrix definíciója. 1p 29. Ortogonális mátrix tulajdonságai.(4db) 2p 30. Householder-mátrix definíciója. 1p 31. Householder-mátrix tulajdonságai.(4db) 2p 32. Vektornorma definíciója. 2p 33. Példák vektornormára.(3db) 1p 34. Vektornormák ekvivalenciája. 1p 35. Mátrixnorma definíciója. 2p 36. Példák mátrixnormára.(3db) 1p 37. Indukált mátrixnorma definíciója. 1p 38. Az 1-es, 2-es és ∞ vektornorma által indukált mátrixnorma előállítása. 3p 39. Froebenius mátrixnorma definíciója. 1p 40. LER-ek érzékenységéről szóló két tétel. 4p 41. Mondja ki a fixpont tételt Rn -ben! 3p 42. Kontrakció fogalma. 1p 43. LER iterációs megoldása során a konvergencia elégséges feltétele. 1p 44. LER iterációs megoldása során a konvergencia szükséges és elégséges feltétele. 1p 45. Jacobi-iteráció vektoros és koordinátás alakja. 3p 46. Tétel a Jacobi-iteráció konvergenciájáról. 1p 47. Csillapított Jacobi-iteráció vektoros és koordinátás alakja. 3p 48. Tétel a csillapított Jacobi-iteráció konvergenciájáról. 1p 49. Gauss-Seidel-iteráció vektoros és koordinátás alakja. 3p
11.1. DEFINÍCIÓK, TÉTELEK
89
50. Gauss-Seidel-relaxáció vektoros és koordinátás alakja. 3p 51. Tétel a Gauss-Seidel-relaxáció és a Gauss-Seidel-iteráció konvergenciájénak kapcsolatáról. 1p 52. Tétel a Gauss-Seidel-relaxáció optimális paraméteréről. 2p 53. Richardson-iteráció vektoros alakja. 1p 54. Tétel a Richardson-iteráció konvergenciájáról. 3p 55. Mondja ki a Banach-féle fixpont tételt R-ben! 3p 56. Írja le a Newton-módszer rekurzióját! 2p 57. Mondja ki a Newton módszer monoton konvergencia tételét! 2p 58. Mondja ki a Newton módszer lokális konvergencia tételét! 2p 59. Írja le a húr-módszer rekurzióját! 2p 60. Írja le a szelő-módszer rekurzióját! 2p 61. Mondja ki a szelő-módszer konvergencia tételét! 2p 62. Mondja ki a Polinomok gyökeinek becslésére tanult tételt! 2p 63. Írja fel a Horner-algoritmust és azt is mire alkalmazható! 3p 64. Definiálja az interpoláció alapfeladatát! 3p 65. Definiálja a Lagrange-féle alappolinomokat! 2p 66. Mondja ki a Lagrange-féle alappolinomok tlajdonságairól szóló tételt! 3p 67. Mondja ki a Lagrange-interpoláció hibájáról szóló tételt! 2p 68. Definiálja az osztott differenciákat! 3p 69. Mondja ki a Newton-interpoláció hibájáról szóló tételt! 2p 70. Írja le az inverz interpoláció módszerét és azt is, mire alkalmazható! 3p 71. Definiálja az Hermite-interpoláció alapfeladatát! 3p 72. Mondja ki az Hermite-interpoláció hibájáról szóló tételt! 2p 73. Definiálja az azonos alappontokhoz tartozó osztott differenciákat! 2p 74. Definiálja az `-edfokú spline-függvényt! 2p 75. Írja fel a lineáris B-spline függvényt! 2p 76. Írja fel a kvadratikus B-spline függvényt! 2p 77. Írja fel a köbös B-spline függvényt! 2p
90
11. FEJEZET. VIZSGAKÉRDÉSEK
78. Mondja ki az interpolációs köbös spline hibájáról szóló tételt! 3p 79. Definiálja a Moore-Penrose-féle általánosított inverzet! 2p 80. Sorolja fel az általánosított inverz tulajdonságait! (8 db) 4p 81. Írja le, hogyan lehet kiszámítani a Moore-Penrose-féle általánosított inverzet alulhatározott teljesrangú esetben! 2p 82. Írja le, hogyan lehet kiszámítani a Moore-Penrose-féle általánosított inverzet túlhatározott teljesrangú esetben! 2p 83. Mit ért rangfaktorizáció alatt? 2p 84. Írja le, hogyan lehet kiszámítani a Moore-Penrose-féle általánosított inverzet nemteljesrangú esetben! 2p 85. Definiálja a LER általánosított megoldását! 2p 86. Mondja ki a LER általánosított megoldásának approximációs tulajdonságáról szóló tételt! 3p 87. Definiálja a legkisebb négyzetek módszerének alapfeladatát! 3p 88. Írja fel a hogyan számíthatók ki a négyzetesen legjobban közelítő polinom együtthatói! 3p 89. Írja fel, hogyan állítható elő az altérre vett merőleges vetület az altér egy ortonormált bázisának ismeretében! 2p 90. Írja fel, hogyan állítható elő az altérre vett merőleges vetület az altér egy tetszőleges bázisának ismeretében! 2p 91. Az altérre vett merőleges vetület minimum tulajdonsága! 2p 92. Mit ért kvadratúra formula alatt? 1p 93. Mit ért interpolációs típusú kvadratúra formula alatt? 2p 94. Mondja ki a Newton-Cotes együtthatók tulajdonságairól szóló tételt! 2p 95. Írja fel a téglalap formulát! 2p 96. Írja fel a trapéz formulát! 2p 97. Írja fel a Simpson formulát! 2p 98. Írja fel az összetett téglalap formulát! 2p 99. Írja fel az összetett trapéz formulát! 2p 100. Írja fel az összetett Simpson formulát! 2p 101. Mondja ki a klasszikus kvadratúra formulák hibatételeit! 3p 102. Mondja ki a klasszikus összetett formulák hibatételeit! 3p
11.2. BIZONYÍTÁSOK, ALGORITMUSOK, LEVEZETÉSEK
91
103. Definiálja a Csebisev-típusú kvadratúra formulát! 2p 104. Definiálja a Gauss-típusú kvadratúra formulát! 2p 105. Mondja ki a Gauss-típusú kvadratúra formulhibatételét! 3p
11.2. Bizonyítások, Algoritmusok, Levezetések 1. Mondja ki a lebegőpontos szám abszolút és relatív hibájára vonatkozó tételt! 6p 2. Mondja ki és bizonyítsa az összeadás abszolút hibájára vonatkozó tételt! 6p 3. Mondja ki és bizonyítsa a kivonás abszolút hibájára vonatkozó tételt! 6p 4. Mondja ki és bizonyítsa a szorzásás abszolút hibájára vonatkozó tételt! 6p 5. Mondja ki és bizonyítsa az osztás abszolút hibájára vonatkozó tételt! 6p 6. Mondja ki és bizonyítsa az összeadás relatív hibájára vonatkozó tételt! 6p 7. Mondja ki és bizonyítsa a kivonás relatív hibájára vonatkozó tételt! 6p 8. Mondja ki és bizonyítsa a szorzásás relatív hibájára vonatkozó tételt! 6p 9. Mondja ki és bizonyítsa az osztás relatív hibájára vonatkozó tételt! 6p 10. Mondja ki és bizonyítsa a GE műveletigényét! 6p 11. LU -felbontás GE segítségével (Li mátrixok használata). 8p 12. Mondja ki és bizonyítsa az LU -felbontás egyértelműségéről szóló tételt! 6p 13. Mondja ki és bizonyítsa a LU -felbontás műveletigényét! 4p 14. LDU -felbontás levezetése az LU -felbontás ismeretében. 4p 15. Cholesky-felbontás levezetése az LDU -felbontás ismeretében. 4p 16. Cholesky-felbontás mátrixainak közvetlen számolása. 3p 17. QR-felbontás mátrixainak számolása Gramm-Schmidt ortogonalizációval. 5p 18. Householder-mátrix tulajdonságainak bizonyítása.(4db) 4p 19. Householder-algoritmus. 3p 20. LER megoldása Householder-transzformációval. 2p 21. Az indukált mátrixnormáról szóló tétel bizonyítása. 3p 22. Igazolja az 1-es mátrixnorma előállítását! 5p 23. Igazolja a 2-es mátrixnorma előállítását! 8p 24. Igazolja a ∞ mátrixnorma előállítását! 5p
92
11. FEJEZET. VIZSGAKÉRDÉSEK
25. LER-ek érzékenységéről szóló tétel bizonyítása. 8p 26. LER iterációs megoldása során a konvergencia elégséges feltételének bizonyítása. 3p 27. Jacobi-iteráció vektoros alakjának levezetése. 5p 28. Jacobi-iteráció koordinátás alakjának levezetése. 5p 29. Csillapított Jacobi-iteráció vektoros alakjának levezetése. 5p 30. Gauss-Seidel-iteráció vektoros alakjának levezetése. 5p 31. Gauss-Seidel-iteráció koordinátás alakjának levezetése. 5p 32. Gauss-Seidel-relaxáció vektoros alakjának levezetése. 5p 33. A Richardson-iteráció konvergenciájáról szóló tétel bizonyítása. 3p 34. A kerekítési hibák hatása az iterációkra (levezetés). 4p 35. Definiálja az intervallumfelezési eljárást, írja le hibabecslést is! 4p 36. Mondja ki és bizonyítsa a tanult elégséges feltételt arra, hogy egy ϕ leképezés kontrakció! 4p 37. Mondja ki és bizonyítsa a tanult tételt arra, hogy egy egyszerű iteráció medrendben konvergens! 6p 38. Vezesse le a Newton-módszer rekurzióját a geometriai megközelítés alapján! 6p 39. Bizonyítsa a Newton módszer monoton konvergencia tételét! 6p 40. Vezesse le a húr-módszer rekurzióját a geometriai megközelítés alapján! 4p 41. Mondja ki és bizonyítsa a Polinomok gyökeinek becslésére tanult tételt! 6p 42. Bizonyítsa az interpolációs polinom unicitását! 3p 43. Mondja ki és bizonyítsa a Lagrange-féle alappolinomok tlajdonságairól szóló tételt! 5p 44. Írja fel a Csebisev-polinomok rekurzióját! 2p 45. Mondja ki és bizonyítsa a LER általánosított megoldásának approximációs tulajdonságáról szóló tételt! 6p 46. Mondja ki és bizonyítsa az interpolációs típusú kvadratúra formula pontosságáról szóló tételt! 5p 47. Mondja ki és bizonyítsa a tételt, amely az interpolációs típusú kvadratúra formula pontossági rendjének maximumáról szól! 5p 48. Mondja ki és bizonyítsa a Gauss-típusú kvadratúra formulák előállítási tételét! 6p
12. fejezet Vizsgakérdések, Numerikus analízis 2. 12.1. Definíciók, Tételek 1. Mit ért egy mátrix sajátértékén és sajátvektorán? 3p 2. Definiálja az A négyzetes mátrix spektrumát! 1p 3. Definiálja az A négyzetes karakterisztikus polinomját! 1p 4. Mi a kapcsolat a mátrix karakterisztikus polinomja és sajátértékei között? 5. Mit ért a mátrix sajátalterén? 2p 6. Definiálja a mátrix sajátértékének algebrai és geometria multiplicitását? 2p 7. Mikor mondjuk, hogy két mátrix hasonló? 2p 8. Mi a kapcsolat hasonló mátrixok sajátértékei között? 1p 9. Mikor nevezünk egy mátrixot diagonalizálhatónak? 1p 10. Mit tud a nem szinguláris mátrix inverzének sajátértékeiről és sajátvektorairól? 2p 11. Mit tud az A mátrix Ak hatványának sajátértékeiről és sajátvektorairól? 2p 12. Mondja ki a Schur-tételt! 2p 13. Mikor nevezünk egy mátrixot normálisnak? 1p 14. Mondja ki a normális mátrix diagonalizálhatóságáról szóló tételt! 2p 15. Mondja ki a Gersgorin-tételt! 2p 16. Mondja ki az általánosított Gersgorin-tételt! 2p 17. A Gersgorin tétel javítása diagonális hasonlósági transzformációval. 2p 18. A sajátérték probléma érzékenysége. Becslés a reziduális hibával. 3p 93
94
12. FEJEZET. VIZSGAKÉRDÉSEK, NUMERIKUS ANALÍZIS 2.
19. Mondja ki a Bauer-Fike tételt! 2p 20. Írja fel a tridiagonális mátrix karakterisztikus polinomját előállító rekurziót! 2p 21. Definiálja a hatvány-módszert (von Mises algoritmus) és mondja ki a tételt a konvergenciáról! 3p 22. Definiálja a inverz iterációt mondja ki a tételt a konvergenciáról!3p 23. Mit mondhatunk az A − pI mátrix sajátértékeiről és sajátvektorairól ha az A mátrix sajátértékeit és sajátvektorait ismerjük? 2p 24. Mondja ki a rangszámcsökkentés módszerének alapját adó tételt! 3p 25. Mondja ki a tételt, amely az affin-transzformációk felírására alkalmas! 2p 26. Írja fel az x tengelyre való tükrözés mátrixát! 2p 27. Írja fel az y tengelyre való tükrözés mátrixát! 2p 28. Írja fel az y = x egyenesre való tükrözés mátrixát! 2p 29. Írja fel az origón átmenő tetszőleges egyenesre való tükrözés mátrixát! 4p 30. Írja fel az origó körüli ϕ ∈ [0, 2π) szöggel való forgatás mátrixát! 4p 31. Írja fel a forgatva nyújtás mátrixát! 2p 32. Írja fel a nyírás mátrixát, melynek a tengely az x-tengely! 3p 33. Mit értünk egy pont homogén koordinátái alatt? 2p 34. Mit értünk egy pont normalizált homogén koordinátái alatt? 2p 35. Ismertesse a sík pontjainak homogén koordinátás alakja esetén használható affin transzformációs mátrix részeit és szerepüket! 3p 36. Írja fel a közönséges elsőrendű explicit kezdetiérték probléma általános alakját! 2p 37. Mondja ki a fokozatos közelítések módszerének alapjául szolgáló tételt! 3p 38. Mondja ki a Taylor-sor módszer alapjául szolgáló tételt! 3p 39. Írja fel az egylépéses Euler-módszer által meghatározott rekurziót! 2p 40. Írja fel a Runge-Kutta módszerek általános alakját, ismertesse a paramétereket és elnevezésüket! 4p 41. Írjon fel egy maximális pontossági rendű m=1 szintes Runge-Kutta módszert! 2p 42. Írjon fel egy maximális pontossági rendű m=2 szintes Runge-Kutta módszert! 2p
12.2. BIZONYÍTÁSOK, ALGORITMUSOK, LEVEZETÉSEK
95
43. Írjon fel egy maximális pontossági rendű m=3 szintes Runge-Kutta módszert! 2p 44. Írjon fel egy maximális pontossági rendű m=4 szintes Runge-Kutta módszert! 2p
12.2. Bizonyítások, Algoritmusok, Levezetések 1. Igazolja, hogy a mátrix adott sajátértékéhez tartozó sajátvektorok a nullvektorral kiegészítve alteret alkotnak! 6p 2. Igazolja, hogy a karakterisztikus polinom invariáns a hasonlósági transzformációra! 4p 3. Igazolja, hogy szimmetrikus mátrix sajátértékei valósak! 3p 4. Mondja ki és igazolja a Schur-tételt! 6p 5. Mondja ki és igazolja a normális mátrix diagonalizálhatóságáról szóló tételt! 6p 6. Mondja ki és igazolja a Gersgorin-tételt! 6p 7. Igazolja, hogy a Fagyejev-féle trace módszer helyes! 4p 8. Igazolja a hatvány-módszer konvergenciájáról szóló tételt! 3p 9. Igazolja a rangszámcsökkentés módszerének alapját adó tételt! 6p 10. Ismertesse a Jacobi-módszert és nevezze meg a leggyakoribb változatait! 5p 11. Igazolja, hogy a Jacobi-módszer során előállított mátrix-sorozat diagonális mátrixhoz konvergál! 4p 12. Ismertesse az LU-algoritmust és írja le azt is, mire alkalmazható! 4p 13. Ismertesse az QR-algoritmust és írja le azt is, mire alkalmazható! 4p 14. Vezesse le az egylépéses Euler-módszert! 4p 15. Ismertesse a többlépéses Euler-módszert! 4p
96
12. FEJEZET. VIZSGAKÉRDÉSEK, NUMERIKUS ANALÍZIS 2.
Irodalomjegyzék [1] Gergó L.: Numerikus módszerek, ELTE 2000. [2] Krebsz A.: Numerikus analízis jegyzet http://numanal.inf.elte.hu/ krebsz/ [3] Móricz F.: Numerikus módszerek az algebrában és analízisben, Polygon, 1997. [4] Sövegjártó A.: Numerikus Analízis, http://numanal.inf.elte.hu/ soveg/ [5] E. Suli, D. F. Mayers: An Introduction to Numerical Analysis, Cambridge University Press 2003. [6] Virágh J.: Numerikus matematika, JATEPress, 1997.
97
