Pozn´amky k pˇredn´aˇsce1
Numerick´e metody I Jaro 2010 ˇ aˇcek Tom´aˇs Rih´
Obsah 1 Normy vektor˚ u a matic
1
2 Neline´ arn´ı rovnice 2.1 Metoda bisekce (p˚ ulen´ı intervalu) . . . . . . 2.2 Iteraˇcn´ı metody . . . . . . . . . . . . . . . . 2.2.1 Metoda prost´e iterace . . . . . . . . 2.2.2 Newtonova metoda (metoda teˇcen) . 2.2.3 Metoda seˇcen . . . . . . . . . . . . . 2.2.4 Metoda regula falsi . . . . . . . . . . 2.2.5 Quasi Newtonova metoda . . . . . . 2.3 Urychlen´ı konvergence - Aitkenova metoda . 2.3.1 Seffensenova metoda . . . . . . . . . 2.4 Hled´an´ı koˇren˚ u n´ asobnosti M > 1 . . . . . .
. . . . . . . . . .
3 3 3 3 4 5 5 5 6 6 7
3 Syst´ emy neline´ arn´ıch rovnic 3.1 Metoda prost´e iterace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Seidelova metoda . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Newtonova metoda . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8 8 9 9
4 Polynomy 4.1 Newtonova metoda . . . . . . . . . . 4.1.1 Hornerovo sch´ema . . . . . . 4.2 Zdvojen´ a Newtonova metoda . . . . 4.3 Newtonova-Mahleyova metoda . . . 4.4 Bairstowova metoda . . . . . . . . . 4.4.1 Zobecnˇen´e Hornerovo sch´ema
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
10 10 11 11 11 12 13
5 Soustavy line´ arn´ıch rovnic 5.1 Pˇr´ım´e metody . . . . . . . . . . . . . . . . . 5.1.1 Gaussova eliminaˇcn´ı metoda . . . . . 5.1.2 LU rozklad . . . . . . . . . . . . . . 5.1.3 Cholesk´eho metoda . . . . . . . . . . 5.1.4 Croutova metoda . . . . . . . . . . . 5.2 Iteraˇcn´ı metody . . . . . . . . . . . . . . . . 5.2.1 Jacobiho metoda . . . . . . . . . . . 5.2.2 Gaussova-Seidelova iteraˇcn´ı metoda
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
14 14 14 15 15 15 16 17 18
Literatura
1
. . . . . .
. . . . . .
. . . . . .
19
Jedn´ a se o pˇrehled z´ akladn´ı teorie podle [1], obsahem zhruba odpov´ıdaj´ıc´ı pˇredn´ aˇsce k pˇredmˇetu M4180 - Numerick´e metody 1, ovˇsem bez pˇr´ıklad˚ u, d˚ ukaz˚ u a ˇrady dalˇs´ıch pozn´ amek. Rovnˇeˇz jsou vynech´ any nˇekter´e okrajov´e kapitoly (napˇr. chyb´ı relaxaˇcn´ı metody ˇreˇsen´ı syst´emu line´ arn´ıch rovnic). M´ a slouˇzit jako pˇrehled teorie potˇrebn´e ke zkouˇsce, ze kter´eho si lze znalosti zopakovat, popˇr. ucelit. Pˇri prvn´ım ˇcten´ı doporuˇcuji ˇc´ıst spoleˇcnˇe s [1]. Upozornˇen´ı na veˇsker´e nedostatky uv´ıt´ am na adrese
[email protected].
1
Normy vektor˚ u a matic
Definice (Norma vektoru). Norma vektoru x ∈ Cn je funkce k · k : Cn → R, kter´a m´a n´asleduj´ıc´ı vlastnosti: 1. kxk ≥ 0, pˇriˇcemˇz kxk = 0 ⇔ x = 0 2. kαxk = |α|kxk,
∀α ∈ C,
(nez´apornost)
∀x ∈ Cn
(homogenita)
∀x, y ∈ Cn
3. kx + yk ≤ kxk + kyk,
(troj´ uheln´ıkov´a nerovnost)
Pozn´ amka. Norma k · k indukuje metriku ρ(x, y) = kx − yk. Pˇ r´ıklad. 1. kxk1 = 2. kxk2 =
Pn
i=1 |xi |
Pn
(oktaedrick´ a norma)
2 i=1 |xi |
1
(eukleidovsk´a norma)
2
3. kxk∞ = max1≤i≤n |xi |
(krychlov´a norma)
Oznaˇ cen´ı. Oznaˇcme Mn tˇr´ıdu matic typu n × n nad R nebo nad C. Definice (Norma matice). Norma matice je funkce k · k : Mn → R s n´asleduj´ıc´ımi vlastnostmi: 1. kAk ≥ 0, pˇriˇcemˇz kAk = 0 ⇔ A = O, kde O je nulov´a matice. 2. kαAk = |α|kAk,
∀α ∈ R,
3. kA + Bk ≤ kAk + kBk, 4. kABk ≤ kAk kBk,
∀A ∈ Mn
A, B ∈ Mn
A, B ∈ Mn
(multiplikativnost)
ˇ Definice (Souhlasn´ a norma). Rekneme, ˇze maticov´a norma k · k je souhlasn´ a s danou vektorovou normou k · kϕ , jestliˇze kAxkϕ ≤ kAkkxkϕ , ∀x ∈ Cn , ∀A ∈ Mn . Vˇ eta 1.1 (Pˇridruˇzen´ a maticov´ a norma). Necht’ k · kϕ je vektorov´ a norma na Cn . Pak ˇc´ıslo kAkϕ = max kAxkϕ kxkϕ =1
je maticov´ a norma souhlasn´ a s danou vektorovou normou k·kϕ . Naz´yv´ a se pˇridruˇzen´a maticov´ a norma k dan´e vektorov´e normˇe. Vˇ eta 1.2. Pro pˇridruˇzen´e maticov´e normy k pˇr´ısluˇsn´ym vektorov´ym norm´ am plat´ı: Pn (sloupcov´ a norma) 1. kAk1 = max1≤j≤n i=1 |aij | Pn 2. kAk∞ = max1≤i≤n j=1 |aij | (ˇr´ adkov´ a norma) p 3. kAk2 = ρ(A∗ A), ρ(A∗ A) je spektr´ aln´ı polomˇer A∗ A, kde A∗ = A¯T , pro re´ aln´e matice je ∗ T A =A (spektr´ aln´ı norma). Definice (Frobeniova norma). Definujeme Frobeniovu normu jako p kAkF = tr(A∗ A). Vˇ eta 1.3 (Ekvivalentnost norem). Pro maticov´e normy plat´ı: √ 1 √ kAk∞ ≤ kAk2 ≤ nkAk∞ , n √ kAk2 ≤ kAkF ≤ nkAk2 , √ 1 √ kAk1 ≤ kAk2 ≤ nkAk1 . n 1
Vˇ eta 1.4. Pˇridruˇzen´ a maticov´ a norma je nejv´yˇse rovna libovoln´e souhlasn´e maticov´e normˇe. D˚ usledek. Pro souhlasn´e normy plat´ı kEk ≥ 1 = kEkϕ . Vˇ eta 1.5. Necht’ k·k je souhlasn´ a maticov´ a norma s danou vektorovou normou k·kϕ . Pak pro vˇsechna nenulov´ a vlastn´ı ˇc´ısla λ matice A plat´ı: |λ| ≤ kAk, neboli ρ(A) ≤ kAk.
2
2
Neline´ arn´ı rovnice
ˇ s´ıme rovnici Reˇ f (x) = 0. Obecnˇe ˇreˇsen´ı dˇel´ıme na dva kroky: 1. Separace koˇren˚ u, tj. nalezen´ı interval˚ u, ve kter´ ych leˇz´ı pr´avˇe jeden koˇren. 2. Zpˇresnˇen´ı koˇren˚ u.
2.1
Metoda bisekce (p˚ ulen´ı intervalu)
Tato metoda se op´ır´ a o n´ asleduj´ıc´ı Vˇ eta 2.1 (Bolzano). Necht’ f ∈ C[a, b]. Pak f nab´yv´ a na intervalu [a, b] vˇsech hodnot mezi svou nejvˇetˇs´ı a nejmenˇs´ı hodnotou. Nejvˇetˇs´ı a nejmenˇs´ı hodnota f na [a, b] existuje podle Weierstrassovy vˇety. Postup v´ypoˇctu: ai +bi i Interval [ai , bi ] dˇel´ıme na dva podintervaly [ai , ai +b s´ım dˇelen´ı pokraˇcujeme pˇriˇra2 ] a [ 2 , bi ]. V dalˇ ai +bi ai +bi zen´ım ai+1 = ai , bi+1 = 2 , nebo ai+1 = 2 , bi+1 = bi tak, aby f (ai+1 )f (bi+1 ) < 0. Tato metoda je vˇzdy konvergentn´ı.
2.2
Iteraˇ cn´ı metody
ˇ s´ıme ekvivalentn´ı u Necht’ ξ je koˇrenem rovnice f (x) = 0. Reˇ ´lohu – hled´an´ı pevn´eho bodu, tj. hled´ an´ı ˇreˇsen´ı rovnice x = g(x). 2.2.1
Metoda prost´ e iterace
Metoda prost´e iterace je jednokrokov´ a iteraˇcn´ı metoda, kde pro zvolenou poˇc´ ateˇcn´ı aproximaci x0 poˇc´ıt´ame d´ale podle vztahu xk+1 = g(xk ) Vˇ eta 2.2 (Z´akladn´ı vˇeta). Necht’ g ∈ C[a, b], g : [a, b] → [a, b] , tedy g zobrazuje interval I = [a, b] na sebe. Pak g m´ a v intervalu [a, b] pevn´ y bod. Splˇ nuje-li g nav´ıc Lipschitzovu podm´ınku s konstantou q, 0 ≤ q < 0 |g(x) − g(y)| ≤ q|x − y|, ∀x, y ∈ I, tj. g je kontrakce, pak je tento pevn´y bod jedin´ y. D˚ usledek. Necht’ g ∈ C 1 [a, b], g : [a, b] → [a, b] a |g 0 (x)| ≤ q < 1,
∀x ∈ [a, b].
Pak m´ a g na intervalu [a, b] jedin´y pevn´y bod. Vˇ eta 2.3 (o konvergenci). Necht’ jsou splnˇeny pˇredpoklady z´ akladn´ı vˇety, tj. g(I) ⊆ I a g je kontrakce. k k k−1 Pak je posloupnost {x }, x = g(x ), k = 1, 2, . . . , konvergentn´ı pro libovolnou poˇc´ ateˇcn´ı aproximaci x0 ∈ I a plat´ı limk→∞ xk = ξ, kde ξ je pevn´y bod funkce g. Definice (Pˇritahuj´ıc´ı a odpuzuj´ıc´ı pevn´ y bod). Pevn´ y bod ξ funkce g ∈ C[a, b] se naz´ yv´a 1. pˇritahuj´ıc´ı (atraktivn´ı), jestliˇze existuje takov´e okol´ı V bodu ξ, ˇze pro kaˇzdou poˇc´ateˇcn´ı aproximaci x0 ∈ V posloupnost {xk }, xk+1 = g(xk ), konverguje k bodu ξ. 2. odpuzuj´ıc´ı (repulzivn´ı), jestliˇze existuje takov´e okol´ı U bodu ξ, ˇze pro kaˇzdou poˇc´ateˇcn´ı aproximaci x0 ∈ U , x0 6= ξ existuje takov´e k, ˇze xk ∈ / U. 3
Vˇ eta 2.4. Plat´ı: g(x) − g(ξ) < 1 nebo |g 0 (ξ)| < 1, pak ξ je 1. Jestliˇze v okol´ı bodu ξ plat´ı pro vˇsechna x 6= ξ: x−ξ pˇritahuj´ıc´ı pevn´y bod. g(x) − g(ξ) > nebo |g 0 (ξ)| > 1, pak ξ je 2. Jestliˇze v okol´ı bodu ξ plat´ı pro vˇsechna x 6= ξ: x−ξ odpuzuj´ıc´ı pevn´y bod. ˇ ad metody). Oznaˇcme ek = xk − ξ chybu k-t´e iterace. Existuje-li nez´aporn´e ˇc´ıslo p ≥ 0 Definice (R´ takov´e, ˇze |ek+1 | |xk+1 − ξ| = lim lim = C 6≡ 0, k p k→∞ |ek |p k→∞ |x − ξ| pak ˇr´ık´ame, ˇze iteraˇcn´ı metoda je ˇr´ adu p. Vˇ eta 2.5. Necht’ funkce g m´ a v okol´ı O(ξ) bodu ξ spojit´e derivace aˇz do ˇr´ adu p vˇcetnˇe, p ≥ 1. Iteraˇcn´ı metoda xk+1 = g(xk ) je ˇra ´du p pr´ avˇe tehdy, kdyˇz plat´ı ξ = g(ξ),
g (j) (ξ) = 0,
j = 1, . . . , p − 1,
g (p) (ξ) 6= 0.
ˇ Definice (Cyklus). Necht’ g : [a, b] → [a, b], ξ je pevn´ y bod, ξ ∈ [a, b]. Rekneme, ˇze poˇc´ateˇcn´ı apro0 0 N j 0 ximace x ∈ [a, b] generuje cyklus ˇr´ adu N , jestliˇze x = x , x 6= x pro j = 1, . . . , N − 1. Bod x0 naz´ yv´ame bod cyklu ˇr´ adu N . Pozn´ amka. Pro zastaven´ı iteraˇcn´ıho procesu m˚ uˇzeme pouˇz´ıt nˇekter´e z n´asleduj´ıc´ıch krit´eri´ı: • |xk+1 − xk | < ε, • |f (xk )| < ε, •
|xk+1 − xk | < ε, |xk |
kde ε je poˇzadovan´ a pˇresnost. 2.2.2
Newtonova metoda (metoda teˇ cen)
Iteraˇcn´ı funkci vol´ıme ve tvaru g = x −
f (x) . Pak f 0 (x) xk+1 = xk −
f (xk ) . f 0 (xk )
Vˇ eta 2.6. Necht’ f ∈ C 2 [a, b], necht’ ξ ∈ [a, b] je koˇren rovnice f (x) = 0 a necht’ f 0 (ξ) 6= 0. Pak existuje δ > 0, [ξ − δ, ξ + δ] ⊆ [a, b] takov´e, ˇze pro kaˇzdou poˇc´ ateˇcn´ı aproximaci x0 ∈ [ξ − δ, ξ + δ] posloupnost generovan´ a Newtonovou metodou konverguje k bodu ξ. Pokud je nav´ıc koˇren ξ jednoduch´y, pak je Newtonova metoda ˇr´ adu 2. Vˇ eta 2.7. Necht’ jsou splnˇeny pˇredpoklady pˇredchoz´ı vˇety. Pak pro posloupnost {xk } generovanou Newtonovou metodou plat´ı: 1. |xk+1 − ξ| ≤
M k 2m (x
2. |xk+1 − xk | ≤
− ξ)2 ,
M k+1 2m (x
− xk )2 ,
kde M = maxI |f 00 (x)|, m = minI |f 0 (x)| > 0, I = [ξ − δ, ξ + δ]. Vˇ eta 2.8 (Fourierovy podm´ınky). Necht’ f ∈ C 2 [a, b], ξ je jedin´y koˇren rovnice f (x) = 0 na [a, b], necht’ f 0 ani f 00 nemˇen´ı znam´enko na [a, b], pˇriˇcemˇz f 0 (x) 6= 0, ∀x ∈ [a, b]. Jestliˇze za poˇc´ ateˇcn´ı aproximaci x0 zvol´ıme ten z krajn´ıch bod˚ u intervalu [a, b] v nˇemˇz znam´enko funkce je stejn´e jako znam´enko f 00 na [a, b], tj. f (x0 )f 00 (x0 ) > 0, pak posloupnost {xk } generovan´ a Newtonovou metodou konverguje monot´ onnˇe k bodu ξ. 4
2.2.3
Metoda seˇ cen
Derivaci f 0 (xk ) aproximujeme diferenˇcn´ı derivac´ı f0 ≈
f (xk ) − f (xk−1 ) , xk − xk−1
k = 1, 2, . . .
Pak je formule pro iteraˇcn´ı proces ve tvaru xk+1 = xk −
xk − xk−1 f (xk ), f (xk ) − f (xk−1 )
jedn´a se tedy o dvoukrokovou metodu. Vˇ eta 2.9. Necht’ rovnice f (x) = 0 m´ a koˇren ξ a necht’ derivace f 0 , f 00 jsou spojit´e v okol´ı bodu ξ, 0 pˇriˇcemˇz f (ξ) 6= 0. Posloupnost generovan´ a metodou seˇcen konverguje ke koˇrenu ξ, pokud poˇc´ ateˇcn´ı √ 1+ 5 0 1 aproximace x , x jsou dostateˇcnˇe bl´ızko ξ a ˇr´ ad metody je 2 ≈ 1,618. 2.2.4
Metoda regula falsi
Pokud f (a)f (b) < 0, pak xk+1 = xk −
xk − xs f (xk ), f (xk ) − f (xs )
kde s je nejvˇetˇs´ı index takov´ y, ˇze plat´ı f (xk )f (xs ) < 0, tj. ξ leˇz´ı v intervalu s krajn´ımi body xk , xs . Vˇ eta 2.10. Necht’ f ∈ C[a, b], f (a)f (b) < 0 a necht’ ξ je jedin´y koˇren v [a, b]. Pak posloupnost {xk } generovan´ a metodou regula falsi konverguje pro kaˇzd´e dvˇe poˇc´ ateˇcn´ı aproximace x0 , x1 ∈ [a, b], f (x0 )f (x1 ) < 0, ke koˇrenu ξ ∈ (a, b). Metoda je ˇr´ adu 1. Z´ avˇ er. Vˇsechny seˇcny vych´ azej´ı z bodu, v nˇemˇz je znam´enko funkce stejn´e jako znam´enko druh´e derivace na intervalu [a, b]. Posloupnost generovan´a touto metodou konverguje monot´onnˇe ke ξ. Pozn´ amka. Za v´ yˇse uveden´ ych pˇredpoklad˚ u m˚ uˇze b´ yt metoda regula falsi zaps´ana jako jednokrokov´ a iteraˇcn´ı metoda. 2.2.5
Quasi Newtonova metoda
Derivaci f 0 v Newtonovˇe metodˇe aproximujeme v´ yrazem f0 ≈
f (xk ) − f (xk ± f (xk )) f (xk ) − f (xk ± f (xk )) = . k k k x − (x ± f (x )) ∓f (xk )
Tedy teˇcnu pouˇzitou v Newtonovˇe metodˇe nahrad´ıme seˇcnou vedenou body [xk , f (xk )], [xk + f (xk ), f (xk + f (xk ))], respektive body [xk , f (xk )], [xk − f (xk ), f (xk − f (xk ))]. Pˇritom pokud je bod xk bl´ızko hledan´eho koˇrene ξ, pak je hodnota f (xk ) bl´ızk´a nule a seˇcna je bl´ızk´ a k teˇcnˇe veden´e bodem x . Jedn´ a se tedy o metodu bl´ızkou metodˇe Newtonovˇe. Pak xk+1 = xk ±
f 2 (xk ) . f (xk ) − f (xk ± f (xk ))
Vˇ eta 2.11. Necht’ f ∈ C 1 [a, b], ξ ∈ [a, b], f 0 (ξ) 6= 0. Pak existuje ε > 0 tak, ˇze posloupnost generovan´ a 0 quasi Newtonovou metodou konverguje k bodu ξ pro kaˇzdou poˇc´ ateˇcn´ı aproximaci x ∈ [ξ − ε, ξ + ε] ∩ [a, b]. Pokud f m´ a v okol´ı bodu ξ spojitou druhou derivaci, je ˇra ´d metody alespoˇ n 2. 5
2.3
Urychlen´ı konvergence - Aitkenova metoda
Posloupnost {xk } nahrad´ıme posloupnost´ı {ˆ xk }, kter´a konverguje rychleji. Definice (Aitkenova metoda). Aitkenova metoda pro urychlen´ı konvergence je posloupnost ve tvaru x ˆ k = xk −
(xk+1 − xk )2 . xk+2 − 2xk+1 + xk
Vˇ eta 2.12. Necht’ je d´ ana posloupnost {xk }, limk→∞ xk = ξ, xk 6= ξ a necht’ tato posloupnost splˇ nuje podm´ınky xk+1 − ξ = (C + γk )(xk − ξ), k = 0, 1, 2, . . . |C| < 1, lim γk = 0. k→∞
{ˆ xk }
Pak posloupnost z pˇredchoz´ı definice je definov´ ana pro dostateˇcnˇe velk´ a k a konverguje k limitˇe k ξ rychleji neˇz posloupnost {x }, tj. x ˆk − ξ lim k = 0. k→∞ x − ξ Pozn´ amka (Geometrick´ y v´ yznam Aitkenovy metody). Definujeme funkci chyby ε takto: ε(xk ) = xk − xk+1 ,
ε(xk+1 ) = xk+1 − xk+2 .
Chceme sestrojit takovou posloupnost, kter´a by konvergovala rychleji k bodu ξ. Body o souˇradnic´ıch [xk , ε(xk )], [xk+1 , ε(xk+1 )] vedeme pˇr´ımku a jej´ı pr˚ useˇc´ık s osou x vezmeme jako dalˇs´ı aproximaci bodu ξ, tj. provedeme extrapolaci“. ” 2.3.1
Seffensenova metoda
Aplikace Aitkenovy metody na metodu prost´e iterace. Oznaˇcme y k = g(xk ),
z k = g(y k ).
Pak iteraˇcn´ı pˇredpis je tvaru x ˆ k = xk −
(y k − xk )2 . z k − 2y k + xk
Vˇ eta 2.13. Steffensenovu metodu lze zapsat jako jednokrokovou iteraˇcn´ı metodu s iteraˇcn´ı funkc´ı ϕ tvaru xg(g(x)) − (g(x))2 ϕ(x) = . g(g(x)) − 2g(x) + x D´ ale plat´ı: 1. ϕ(ξ) = ξ
⇒
g(ξ) = ξ,
2. g(ξ) = ξ, g 0 (ξ) 6= 1
⇒
ϕ(ξ) = ξ
Vˇ eta 2.14. Necht’ funkce g m´ a spojit´e derivace aˇz do ˇr´ adu p + 1 vˇcetnˇe v okol´ı bodu ξ. Necht’ iteraˇcn´ı k+1 k metoda x = g(x ) je ˇr´ adu p pro bod ξ. Pak pro p > 1 je iteraˇcn´ı metoda xk+1 = ϕ(xk ) ˇra ´du 2p − 1. Pro p = 1 je tato metoda ˇr´ adu alespoˇ n 2 za pˇredpokladu g 0 (ξ) 6= 1.
6
2.4
Hled´ an´ı koˇ ren˚ u n´ asobnosti M > 1
Necht’ ξ je koˇrenem funkce f n´ asobnosti M > 1, tj. f (x) = (x − ξ)M ϕ(x),
ϕ(ξ) 6= 0,
f 0 (x) = M (x − ξ)M −1 ϕ(x) + (x − ξ)M ϕ0 (x). Nezn´ame-li n´asobnost koˇrene, zavedeme funkci u(x) =
f (x) , f 0 (x)
kter´a m´a koˇreny stejn´e jako f , vˇsechny vˇsak jednoduch´e. Z´ avˇ er. Newtonova metoda pro n´ asobn´ y koˇren je ˇr´adu 1. Modifikace Newtonovy metody pro M n´asobn´ y koˇren je tvaru f (xk ) xk+1 = xk − M 0 k f (x ) a je ˇr´adu 2.
7
3
Syst´ emy neline´ arn´ıch rovnic
ˇ s´ıme soustavu neline´ Reˇ arn´ıch rovnic tvaru f1 (x1 , . . . , xm ) = 0, .. . fm (x1 , . . . , xm ) = 0, ve vektorov´em tvaru potom F (x) = 0,
x ∈ Rm ,
0 = (0, . . . , 0)T ∈ Rm ,
kde F : Rm → Rm . Necht’ vektor ξ = (ξ1 , . . . , ξm )T ∈ Rm je jej´ım koˇrenem, tedy plat´ı F (ξ) = 0. Nav´ıc v Rm definujeme metriku ρ(x, y) = max |xi − yi |. 1≤i≤m
3.1
Metoda prost´ e iterace
Z´akladn´ı soustavu pˇrevedeme do tvaru x = G(x), kde G : Rm → Rm , pak ˇreˇs´ıme opˇet probl´em pevn´eho bodu x1 = g1 (x1 , . . . , xm ), .. . xm = gm (x1 , . . . , xm ). Vˇ eta 3.1. Necht’ zobrazen´ı G : Rm → Rm je kontrakce na Rm , tj. ∀x, y ∈ Rm ,
ρ(G(x), G(y)) ≤ qρ(x, y),
0 ≤ q < 1.
Pak posloupnost {xk }, xk = G(xk−1 ), k = 1, 2, . . . , konverguje pro kaˇzdou poˇc´ ateˇcn´ı aproximaci x0 ∈ Rm k pevn´emu bodu ξ zobrazen´ı G, pˇriˇcemˇz tento pevn´y bod je jedin´y. Vˇ eta 3.2. Necht’ ξ ∈ Rn je pevn´y bod zobrazen´ı G. Necht’ funkce gi , i = 1, . . . , m, maj´ı spojit´e parci´ aln´ı derivace na mnoˇzinˇe Ω(ξ, r) = {x ∈ Rm |ρ(x, ξ) ≤ r} a necht’ pro tyto derivace plat´ı ∂gi (x) q ∂xj ≤ m , 0 ≤ q < 1, i, j = 1, . . . , m, ∀x ∈ Ω(ξ, r) a necht’ x0 ∈ Ω(ξ, r). Pak posloupnost {xk }, xk+1 = G(xk ), k = 0, 1, . . . , konverguje a limk→∞ xk = ξ, pˇriˇcemˇz xk ∈ Ω(ξ, r) pro vˇsechna k. Pozn´ amka. Podm´ınky na parci´ aln´ı derivace v pˇredchoz´ı vˇetˇe lze nahradit pˇredpokladem m X ∂gi (x) max ∂xj ≤ q < 1. 1≤i≤m j=1
Iteraˇcn´ı proces tedy m´ ame ve tvaru xk+1 = g1 (xk1 , xk2 , . . . , xkm ), 1 xk+1 = g2 (xk1 , xk2 , . . . , xkm ), 2 .. . k k k xk+1 m = gm (x1 , x2 , . . . , xm ).
8
3.2
Seidelova metoda
Na rozd´ıl od metody prost´e iterace vyuˇzijeme k v´ ypoˇctu xk+1 jiˇz vypoˇcten´e hodnoty xk+1 i i−s , s = 1, . . . , i − 1. Iteraˇcn´ı rovnice jsou pak xk+1 = g1 (xk1 , xk2 , . . . , xkm ), 1 k k xk+1 = g2 (xk+1 2 1 , x2 , . . . , xm ), .. . k+1 k+1 k xk+1 m = gm (x1 , . . . , xm−1 , xm ).
3.3
Newtonova metoda
Iteraˇcn´ı rovnice je v analogii a klasickou Newtonovou metodou xk+1 = xk − JF−1 (xk )F (xk ), kde JF je Jacobiho matice zobrazen´ı F (je tedy nutn´e, aby JF byla regul´arn´ı). Pro v´ ypoˇcet je vhodn´e pˇrev´est iteraˇcn´ı rovnici do tvaru JF (xk )dk = −F (xk ), kde dk = xk+1 − xk je vektor oprav. Vˇ eta 3.3. Necht’ ξ je koˇrenem soustavy rovnic F (x) = 0 a necht arn´ı matice se
’ JF (x) je regul´ ale spojit´ymi prvky v okol´ı O(ξ) bodu ξ, pˇriˇcemˇz na tomto okol´ı JF−1 (x) ∞ ≤ K, K = konst. Necht’ d´ funkce fi , i = 1, . . . , m, maj´ı spojit´e druh´e parci´ aln´ı derivace v O(ξ). Posloupnost {xk } generovan´ a Newtonovou metodou konverguje ke koˇrenu ξ za pˇredpokladu, ˇze poˇca ´0 teˇcn´ı aproximace x leˇz´ı dostateˇcnˇe bl´ızko ξ. Tato metoda je ˇr´ adu 2. Pozn´ amka. Pro zastaven´ı v´ ypoˇctu ˇcasto pouˇz´ıv´ame podm´ınku
k+1
x − xk ≤ ε, kxk k kde ε je pˇredem dan´ a pˇresnost.
9
4
Polynomy
Necht’ P je polynom tvaru P (x) = a0 xn + a1 xn−1 + · · · + an−1 x + an . D´ale oznaˇcme A = max{|a1 |, . . . , |an |}, B = max{|a0 |, . . . , |an−1 |}. Vˇ eta 4.1. Pro vˇsechny koˇreny polynomu P plat´ı 1 A ≤ |ξk | ≤ +1 . B |a0 | 1 + |an | Definice (Znam´enkov´ a zmˇena). Necht’ {cn }, ci 6= 0 ∀i = 1, . . . , n, je posloupnost re´aln´ ych ˇc´ısel r˚ uzn´ ych od nuly. ˇ Rekneme, ˇze pro dvojici ˇc´ısel ck , ck+1 nast´ av´ a znam´enkov´ a zmˇena, jestliˇze ck ck+1 < 0. ˇ Rekneme, ˇze dvojice ck , ck+1 zachov´ av´ a znam´enko, jestliˇze ck ck+1 > 0. ˇ Definice (Sturmova posloupnost). Rekneme, ˇze posloupnost polynom˚ u {P = P0 , P1 , . . . , Pm } je Sturmovou posloupnost´ı pˇr´ısluˇsnou polynomu P , jestliˇze plat´ı: 1. Vˇsechny re´ aln´e koˇreny polynomu P0 jsou jednoduch´e. 2. Je-li ξ re´aln´ y koˇren polynomu P0 , pak sign P00 (ξ) = −sign P1 (ξ). 3. Je-li α re´aln´ y koˇren polynomu Pi , i = 1, . . . , m − 1, pak Pi−1 (α)Pi+1 (α) < 0. 4. Posledn´ı polynom Pm nem´ a re´ aln´e koˇreny. Pozn´ amka. Nejvˇetˇs´ı spoleˇcn´ y dˇelitel P a P 0 je polynom, kter´ y m´a stejn´e koˇreny jako P , ale vˇsechny jednoduch´e. Lemma 4.2 (Konstrukce Sturmovy posloupnosti). Necht’ vˇsechny re´ aln´e koˇreny polynomu P jsou jednoduch´e. Pak lze k polynomu P zkonstruovat Sturmovu posloupnost n´ asleduj´ıc´ım postupem: P0 (x) = P (x), P1 (x) = −P00 (x), Pi−1 (x) = Pi (x)Qi (x) − ci Pi+1 (x), Pm−1 (x) = Pm (x)Qm (x),
i = 1, . . . , m − 1,
ci > 0.
Vˇ eta 4.3 (Sturm). Poˇcet re´ aln´ ych koˇren˚ u polynomu P na intervalu [a, b) je roven W (b) − W (a), kde W (x) je poˇcet znam´enkov´ych zmˇen ve Sturmovˇe posloupnosti v bodˇe x (z n´ıˇz jsou vyˇskrtnuty nuly). Vˇ eta 4.4 (Descartes). Poˇcet kladn´ych koˇren˚ u polynomu P (poˇc´ıt´ ano s n´ asobnost´ı) je roven poˇctu znam´enkov´ych zmˇen v posloupnosti koeficient˚ u a0 , . . . , an nebo o sud´e ˇc´ıslo menˇs´ı. Jsou-li vˇsechny koeficienty a0 , . . . , an r˚ uzn´e od nuly, pak poˇcet z´ aporn´ych koˇren˚ u (poˇc´ıt´ ano s n´ asobnost´ı) je roven poˇctu zachov´ an´ı znam´enek v posloupnosti koeficient˚ u nebo o sud´e ˇc´ıslo menˇs´ı.
4.1
Newtonova metoda
Pˇripomeˇ nme, ˇze Newtonova metoda je iteraˇcn´ı proces tvaru xk+1 = xk −
P (xk ) . P 0 (xk )
Hodnoty P (xk ) a P 0 (xk ) lze snadno spoˇc´ıtat Hornerov´ ym sch´ematem. 10
4.1.1
Hornerovo sch´ ema
Vhodn´e pro v´ ypoˇcet hodnot polynom˚ u, hodnot derivac´ı a dˇelen´ı line´arn´ım polynomem. Mˇejme polynom q ve tvaru Q(x) = b0 xn−1 + b1 xn−2 + · · · + bn−2 x + bn−1 a necht’ α ∈ R. Pak lze polynom P a jeho derivaci P 0 zapsat ve tvaru P (x) = (x − α)Q(x) + P (α), P 0 (x) = Q(x) + (x − α)Q0 (x), tedy P 0 (α) = Q(α). V´ ypoˇcet lze uspoˇr´ adat do n´asleduj´ıc´ı tabulky: a0 α b0 α c0
4.2
a1
a2
...
an−1
an
αb0
αb1
...
αbn−2
αbn−1
b1
b2
...
bn−1
bn = P (α)
αc0
αc1
...
αcn−2
c1
c2
...
cn−1 = Q(α) = P 0 (α)
Zdvojen´ a Newtonova metoda
Zdvojen´a Newtonova metoda je iteraˇcn´ı proces tvaru xk+1 = xk − 2
P (xk ) , P 0 (xk )
za pˇredpokladu f (x0 )f (xk ) > 0. Pokud najdeme index j takov´ y, ˇze f (x0 )f (xj ) < 0, d´ale pokraˇcujeme standardn´ı Newtonovou metodou. Vˇ eta 4.5. Necht’ polynom P (x) = a0 xn + · · · + an m´ a vˇsechny koˇreny ξi , i = 1, . . . , n re´ aln´e a ξ1 ≥ ξ2 ≥ · · · ≥ ξn a necht’ α1 je nejvˇetˇs´ı koˇren P 0 , ξ1 ≥ α1 ≥ ξ2 . Pro n = 2 pˇredpokl´ adejme ξ1 > ξ2 . Pak pro kaˇzd´e z > ξ1 jsou ˇc´ısla z0 = z −
P (z) , P 0 (z)
y =z−2
P (z) , P 0 (z)
y0 = y −
P (y) P 0 (y)
definov´ ana a plat´ı α1 < y, ξ1 ≤ y 0 ≤ z 0 .
4.3
Newtonova-Mahleyova metoda
Pˇredpokl´adejme, ˇze jsme jiˇz nalezli aproximaci ξ˜1 nejvˇetˇs´ıho koˇrene ξ1 polynomu P a hled´ame ξ˜2 . Jeden zp˚ usob je zaveden´ı polynomu P (x) P1 = , x − ξ˜1 kter´ y je stupnˇe n − 1 a m´ a nejvˇetˇs´ı koˇren ξ2 . Pak bychom opˇet mohli Newtonovou metodou hledat nejvˇetˇs´ı koˇren. Tato metoda se naz´ yv´ a metoda sniˇzov´ an´ı stupnˇe. V praxi ovˇsem nepˇresnost s jakou jsme nalezli pˇredch´ azej´ıc´ı koˇreny se pˇren´ aˇs´ı na koˇreny n´asleduj´ıc´ı, kter´e mohou b´ yt nalezeny jiˇz zcela nepˇresnˇe. Proto zav´ ad´ıme Mahleyovu metodu, kter´a spoˇc´ıv´a ve vhodn´em vyj´adˇren´ı derivace P1 :
11
P 0 (x) P (x) − , ˜ x − ξ1 (x − ξ˜1 )2
P10 (x) =
jehoˇz dosazen´ım do Newtonovy metody dost´av´ame xk+1 = xk −
P1 (xk ) P (xk ) k = x − k) . P10 (xk ) P 0 (xk ) − xPk(x −ξ˜ 1
Obecnˇe, pokud jsme jiˇz nalezli aproximace koˇren˚ u ξ˜1 , . . . , ξ˜j a hled´ame ξ˜j+1 , dostaneme stejn´ ym zp˚ usobem vztah xk+1 = xk −
4.4
P (xk ) P P 0 (xk ) − ij=1
P (xk ) xk −ξj
.
Bairstowova metoda
Tato metoda slouˇz´ı k v´ ypoˇctu komplexn´ıch koˇren˚ u polynomu. Hledejme tedy dvojici z, z¯, z = u + iv komplexnˇe zdruˇzen´ ych koˇren˚ u polynomu P . Necht’ jsou z, z¯ koˇreny polynomu D(x) = x2 + px + q, kde 2 2 p = −2u a q = u + v . Mus´ıme tedy naj´ıt ˇc´ısla p, q tak, aby polynom D dˇelil polynom P . Form´ alnˇe tedy P (x) = D(x)Q(x) + Ax + B, kde D(x) = x2 + px + q, je polynom stupnˇe n − 2,
Q(x) = Q(x, p, q) A = A(p, q), B = B(p, q). Nyn´ı je tˇreba urˇcit p, q tak, aby A(p, q) = 0,
B(p, q) = 0,
coˇz je syst´em neline´ arn´ıch rovnic, kter´ y ˇreˇs´ıme Newtonovou metodou. Povaˇzujeme-li polynom D(x) = x2 +px+q za aproximaci dˇelitele, dostaneme dalˇs´ı aproximaci D1 (x) = x2 +p1 x+q1 , p1 = p+h, q1 = q + k ˇreˇsen´ım soustavy ∂A ∂A h A(p, q) ∂p ∂q = − . ∂B ∂B k B(p, q) ∂p ∂q Tato soustava se d´ a po dalˇs´ıch u ´prav´ ach a oznaˇcen´ı a = −
∂A ∂B ,b=− zapsat takto: ∂q ∂q
(ap − b)h − ak + A = 0, aqh − bk + B = 0. Jej´ım vyˇreˇsen´ım dost´ av´ ame ˇc´ısla h, k a kvadratick´ y trojˇclen D1 (x), jehoˇz koˇreny jsou aproximac´ı koˇren˚ u , z¯ polynomu P . Postup opakujeme. Jako krit´erium pro zastaven´ı v´ ypoˇctu lze zvolit: |h| < ε|p|, |k| < ε|q|, kde ε je poˇzadovan´ a pˇresnost. Hodnoty A, B, a, b lze spoˇc´ıtat zobecnˇen´ ym Hornerov´ ym sch´ematem.
12
4.4.1
Zobecnˇ en´ e Hornerovo sch´ ema
Mˇejme nyn´ı polynomy Q a R ve tvaru Q(x) = b0 xn−2 + b1 xn−3 + · · · + bn−3 x + bn−2 R(x) = c0 xn−4 + c1 xn−5 + · · · + cn−5 x + cn−4 . Pak lze polynomy P a Q zapsat ve tvaru P (x) = Q(x)D(x) + Ax + B, Q(x) = R(x)D(x) + ax + b. V´ ypoˇcet m˚ uˇzeme opˇet zapsat do tabulky: a0 −p
a1
a2
...
an−3
an−2
an−1
−pb0
−pb1
...
−pbn−4
−pbn−3
−pbn−2
−qb0
...
−qbn−5
−qbn−4
−qbn−3
−qbn−2
b1
b2
...
bn−3
bn−2
A
B
−pc0
−pc1
...
−pcn−4
−qc0
...
−qcn−5
−qcn−4
c2
...
a
b
−q b0 −p −q c0
c1
13
an
5
Soustavy line´ arn´ıch rovnic
ˇ s´ıme soustavu line´ Reˇ arn´ıch rovnic tvaru Ax = b.
5.1
Pˇ r´ım´ e metody
5.1.1
Gaussova eliminaˇ cn´ı metoda
Matici soustavy A uprav´ıme na horn´ı troj´ uheln´ıkov´ y tvar, kter´ y oznaˇc´ıme jako matici U , tj. matici soustavy A uprav´ıme na horn´ı troj´ uheln´ıkov´ y tvar, kter´ y oznaˇc´ıme jako matici U , tj. u11 u12 . . . . . . u1n 0 u22 . . . . . . u2n . .. .. . U = . . 0 . . . . . .. . . . . . . . 0 0 . . . 0 unn T´ım rovnici ax = b pˇrevedeme na tvar U x = c, coˇz lze snadno ˇreˇsit od posledn´ı rovnice smˇerem k prvn´ı. Definice (Frobeniova matice). Definujeme Frobeniovu matici Gi jako matici realizuj´ıc´ı vynulov´ an´ı i-t´eho sloupce pod diagon´ alou. Frobeniova matice pˇr´ısluˇsn´a prvn´ımu napˇr. sloupci je tvaru 1 0 . . . . . . 0 −l21 1 . . . . . . 0 .. .. G1 = −l31 0 . . , . . . . . .. . . .. . −ln1 0 . . . 0 1 kde li1 =
a ¯i1 . Matice A¯ vznikla z matice A v´ ymˇenou prvn´ıho a r-t´eho ˇr´adku tak, aby a ¯11 6= 0. a ¯11
Definice (Permutaˇcn´ı matice). Definujeme permutaˇcn´ı matici Pi jako matici realizuj´ıc´ı v´ ymˇenu dvou ˇr´adk˚ u (index matice se vztahuje ke kroku v GEM). Permutaˇcn´ı matice pˇr´ısluˇsn´a v´ ymˇenˇe r-t´eho a s-t´eho ˇr´adku odpov´ıd´ a jednotkov´e matici s vymˇenˇen´ ym r-t´ ym a s-t´ ym ˇr´adkem. Vˇ eta 5.1. Jestliˇze Gaussova eliminaˇcn´ı metoda (GEM) je realizov´ ana bez v´ymˇeny ˇr´ adku, pak GEM definuje rozklad A = LU , kde L je doln´ı troj´ uheln´ıkov´ a matice a U je horn´ı troj´ uheln´ıkov´ a matice. Pozn´ amka. Matice L z pˇredchoz´ı vˇety je souˇcin vˇsech Frobeniov´ ych matic vznikl´ ych bˇehem GEM, −1 tj. L = G−1 . . . G , coˇ z ihned plyne z U = G . . . G G A. n−1 2 1 1 n−1 GEM s ˇ c´ asteˇ cn´ ym v´ ybˇ erem hlavn´ıho prvku V k-t´em kroku vyb´ır´ame v k-t´em sloupci maxim´aln´ı prvek v absolutn´ı hodnotˇe. Necht’ je to napˇr. ark . Vymˇen´ıme r-t´ y a k-t´ y ˇr´adek a vynulujeme poˇzadovan´ y sloupec pod diagon´ alou (tj. pod pivotem a ¯kk ). Tedy (k)
(k)
|apk | = max |aik |, k≤i≤n
(k)
kde apk je hlavn´ı prvek k-t´eho kroku.
14
(k)
GEM s u ´ pln´ ym v´ ybˇ erem hlavn´ıho prvku V kaˇzd´em kroku vyb´ır´ame v dan´e submatici Akk maxim´aln´ı v absolutn´ı hodnotˇe. Necht’ je to napˇr. ars . Vymˇen´ıme r-t´ y a k-t´ y ˇr´adek a vynulujeme s-t´ y sloupec pod diagon´ alou. 5.1.2
LU rozklad
Rozloˇz´ıme matici soustavy na souˇcin A = LU , kde L, resp. U je doln´ı, resp. horn´ı (s jedniˇckami na hlavn´ı diagon´ale) troj´ uheln´ıkov´ a matice. M´ame tedy soustavu line´arn´ıch rovnic ve tvaru LU x = b. Odtud m´ame dvˇe snadno ˇreˇsiteln´e rovnice U x = y, Ly = b. Vˇ eta 5.2. Jestliˇze vˇsechny hlavn´ı minory matice A jsou nenulov´e, pak lze A rozloˇzit na souˇcin A = LU . 5.1.3
Cholesk´ eho metoda
Necht’ A je v t´eto ˇc´ asti symetrick´ a matice. Pak lze aplikovat Cholesk´eho metodu podle n´asleduj´ıc´ı vˇety. Vˇ eta 5.3 (Cholesk´eho metoda). Necht’ A je symetrick´ a matice splˇ nuj´ıc´ı pˇredpoklady vˇety 5.2 (tj. vˇsechny jej´ı minory jsou nenulov´e). Pak existuje horn´ı troj´ uheln´ıkov´ a matice T takov´ a, ˇze A = T T T . D˚ usledek (konstrukce matice T ). Matice T = (tij ) z pˇredchoz´ı vˇety m´ a prvky tvaru: √ t11 = a11 a1j t1j = , j = 2, . . . , n t11 v u i−1 X u tii = taii − t2 , i = 2, . . . , n ki
k=1
1 tij = tii
aij −
i−1 X
! tki tkj
tij = 0 5.1.4
pro j > i,
k=1
pro j < i.
Croutova metoda
Tato metoda je aplikace LU rozkladu na tridiagon´aln´ı matice. Hled´ame tedy matice tvaru l 0 . . . . . . 0 11 l21 l22 0 ... 0 .. .. L = 0 l32 l33 . . , . . .. . .. ... . 0 . 0 . . . 0 ln,n−1 lnn 0 u11 u12 0 . . . .. 0 u22 u23 . . . . . . . . . . U = . . . 0 0 . . .. .. .. . . . . un−1,n . 0 0 ... 0 unn 15
Rozeps´an´ım takto vznikl´ ych rovnic dostaneme: a11 = l11 ai,i−1 = li,i−1 ,
i = 2, . . . , n
aii = li,i−1 ui−1,i + lii ,
i = 2, . . . , n i = 1, . . . , n − 1.
ai,i+1 = lii ui,i+1 ,
Vˇ eta 5.4. Necht’ A je tridiagon´ aln´ı matice s vlastnostmi: ai,i−1 ai,i+1 6= 0,
i = 2, . . . , n − 1,
|a11 | > |a12 |, |aii | ≥ |ai,i−1 | + |ai,i+1 |,
i = 2, . . . , n − 1,
|ann | > |an,n−1 |. Pak matice A je regul´ arn´ı a prvky lii matice L jsou r˚ uzn´e od nuly. Matici A pak lze rozloˇzit na souˇcin A = LU . Pozn´ amka. Prvn´ı podm´ınka v pˇredchoz´ı vˇetˇe znamen´a, ˇze na soubˇeˇzn´ ych diagon´al´ach se nevyskytuj´ı nuly. Dalˇs´ı tˇri podm´ınky znamenaj´ı, ˇze A je ˇr´adkovˇe diagon´alnˇe dominantn´ı.
5.2
Iteraˇ cn´ı metody
D´ale oznaˇcme matici soustavy A jako A = E − T a vektor b jako b = g. Pak lze soustavu rovnic pˇrepsat na tvar x = (E − T )−1 g, ˇc´ımˇz dost´av´ame ekvivalentn´ı tvar syst´emu rovnic x = T x + g. Iteraˇcn´ı posloupnost je pak generov´ ana vztahem xk+1 = T xk + g Z´aroveˇ n oznaˇcme x∗ pˇresn´e ˇreˇsen´ı t´eto soustavy. ˇ Definice. Rekneme, ˇze matice H ∈ Mn je konvergentn´ı, jestliˇze lim H k = O,
k→∞
kde O je nulov´a matice. ˇ Rekneme, ˇze matice H ∈ Mm je semikonvergentn´ı, jesliˇze limk→∞ H k existuje. Lemma 5.5. N´ asleduj´ıc´ı tvrzen´ı jsou ekvivalentn´ı: 1. H je konvergentn´ı. 2. ρ(H) < 1, kde ρ(H) ≡ max{|λ(H)|} je spektr´ aln´ı polomˇer matice H. 3. limk→∞ kH k k = 0 pro nˇejakou pˇridruˇzenou maticovou normu. 4. limk→∞ H k x = 0
∀x ∈ Rn .
Lemma 5.6. Necht’ kT k = 1 (k · k je souhlasn´ a s danou vektorovou normou). Pak matice E − T je regul´ arn´ı a plat´ı: kEk . k(E − T )−1 k ≤ 1 − kT k 16
D˚ usledek. Je-li ρ(T ) < 1, pak E − T je regul´ arn´ı. D˚ usledek. Necht’ ρ(T ) < 1, pak (E − T )−1 = E + T + T 2 + · · · . Vˇ eta 5.7 (Hlavn´ı vˇeta t´eto kapitoly). Posloupnost {xk } generovan´ a iteraˇcn´ım procesem xk = T xk−1 + g,
k = 1, 2, . . .
konverguje pro kaˇzdou poˇc´ ateˇcn´ı aproximaci x0 ∈ Rn pr´ avˇe tehdy, kdyˇz ρ(T ) < 1, pˇriˇcemˇz lim xk = x∗ ,
k→∞ ∗
x = T x∗ + g. D˚ usledek. Necht’ pro nˇejakou pˇridruˇzenou maticovou normu plat´ı kT k < 1. Pak posloupnost {xk } generovan´ a iteraˇcn´ım procesem xk = T xk−1 + g, k = 1, 2, . . . konverguje pro kaˇzdou poˇc´ ateˇcn´ı apro0 n ∗ ximaci x ∈ R k x . N´asleduj´ıc´ı metody dost´ av´ ame konkr´etn´ı volbou iteraˇcn´ı matice. 5.2.1
Jacobiho metoda
Zavedeme oznaˇcen´ı A = D − L − U , kde L, resp. U je doln´ı, resp. horn´ı troj´ uheln´ıkov´a matice a D diagon´aln´ı matice. Pak soustavu Ax = b pˇrep´ıˇseme Dx = (L + U )x + b, odkud x = D−1 (L + U )x + D−1 b. Pak zˇrejmˇe TJ = D−1 (L + U ) a g = D−1 b a iteraˇcn´ı proces je xk+1 = TJ xk + g = D−1 (L + U )xk + D−1 b. Vˇ eta 5.8 (o konvergenci). Posloupnost {xk } generovan´ a Jacobiho metodou konverguje pro libovolnou poˇc´ ateˇcn´ı aproximaci x0 ∈ Rn pr´ avˇe tehdy, kdyˇz ρ(TJ ) < 1. Vˇ eta 5.9 (Sumaˇcn´ı krit´eria). Plat´ı: 1. Siln´e ˇr´adkov´e sumaˇcn´ı krit´erium: Necht’ A je ryze ˇr´ adkovˇe diagon´ alnˇe dominantn´ı matice, tj. |aii | >
n X
|aij |,
i = 1, . . . , n.
j=1,j6=i
Pak Jacobiho iteraˇcn´ı metoda konverguje pro kaˇzdou poˇc´ ateˇcn´ı aproximaci x0 ∈ Rn . 2. Siln´e sloupcov´e sumaˇcn´ı krit´erium: Necht’ matice A je ryze sloupcovˇe diagon´ alnˇe dominantn´ı, tj. X |aii | > |aji |, i = 1, . . . , n. j=1,j6=i
Pak Jacobiho iteraˇcn´ı metoda konverguje pro kaˇzdou poˇc´ ateˇcn´ı aproximaci x0 ∈ Rn .
17
5.2.2
Gaussova-Seidelova iteraˇ cn´ı metoda
Opˇet pˇri oznaˇcen´e A = D − L − U soustavu pˇrevedeme do tvaru (D − L)x = U x + b, odkud x = (D − L)−1 U x + (D − L)−1 b. Pˇri oznaˇcen´ı TG = (D − L)−1 U a g = (D − L)−1 b a iteraˇcn´ı proces je xk+1 = TG xk + g = (D − L)−1 U xk + (D − L)−1 b. Vˇ eta 5.10 (Krit´eria konvergence). Plat´ı: 1. Gaussova-Seidelova metoda konverguje pro libovolnou poˇca ´teˇcn´ı aproximaci x0 ∈ Rn pr´ avˇe tehdy, kdyˇz ρ(TG ) < 1. 2. Necht’ kTG k < 1, pak Gaussova-Seidelova metoda konverguje pro libovolnou poˇc´ ateˇcn´ı aproximaci x0 ∈ Rn . 3. Siln´e ˇr´ adkov´e sumaˇcn´ı krit´erium. 4. Siln´e sloupcov´e sumaˇcn´ı krit´erium. Vˇ eta 5.11 (Stein-Rosenberg). Necht’ pro prvky matice A plat´ı aij ≤ 0 pro vˇsechna i 6= j a aii > 0, i = 1, . . . , n. Pak plat´ı pr´ avˇe jedno z n´ asleduj´ıc´ıch tvrzen´ı: 1. 0 < ρ(TG ) < ρ(TJ ) < 1 2. 1 < ρ(TJ ) < ρ(TG ) 3. ρ(TJ ) = ρ(TG ) = 0 4. ρ(TJ ) = ρ(TG ) = 1. To znamen´ a, ˇze konverguj´ı-li obˇe metody, Gaussova-Seidelova metoda konverguje rychleji. Vˇ eta 5.12. Necht’ A je pozitivnˇe definitn´ı matice. Pak Gaussova-Seidelova metoda konverguje pro kaˇzdou poˇc´ ateˇcn´ı aproximaci.
18
Reference [1] Horov´a, I., Zelinka, J.: Numerick´e metody, 2. rozˇs´ıˇren´e vyd´an´ı, Masarykova univerzita, Brno, 2004, ISBN 80–210–3317–7.
19
