Numerick´a matematika
1
Obsah ˇ sen´ı neline´ 1 Reˇ arn´ıch rovnic 1.1 Metoda p˚ ulen´ı intervalu . . 1.2 Metoda jednoduch´e iterace 1.3 Newtonova metoda . . . . . 1.4 Metoda seˇcen . . . . . . . . 1.5 Metoda regula fasci . . . . . 1.5.1 Pˇr´ıklad . . . . . . . 1.6 N´asobn´e koˇreny . . . . . . . 1.7 Aitken˚ uv δ 2 -proces . . . . . 1.8 Soustavy rovnic . . . . . . . 1.8.1 Newtonova metoda . 1.8.2 Pˇr´ıklad . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
3 3 4 4 5 5 6 7 7 7 7 8
Numerick´a matematika
2
Numerick´a matematika
1
3
ˇ sen´ı neline´ Reˇ arn´ıch rovnic
Cel´a ˇrada rovnic, kter´e se vyskytuj´ı v matematice a fyzice je analyticky neˇreˇsiteln´a. Polynomi´aln´ı rovnice jsou napˇr´ıklad ˇreˇsiteln´e jen do ˇctvrt´eho stupnˇe. V t´eto kapitole si uk´aˇzeme metody jak takov´eto rovnice ˇreˇsit alespoˇ n pˇribliˇznˇe. Budeme hledat koˇreny algebraick´e rovnice f (x) = 0
(1)
Koˇren budeme hledat iteraˇcn´ımi metodami. Zaˇcneme s pˇribliˇzn´ ym odhadem koˇrene x0 a tento odhad budeme postupnˇe upˇresˇ novat x1 ,x2 ,. . . . Nov´ y odhad vypoˇc´ıt´ame z nˇekolika odhad˚ u pˇredchoz´ıch. Tyto iteraˇcn´ı metody maj´ı tedy tvar xi+1 = Fi (xi , xi−1 , . . . , xi−n+1 )
(2)
Chyba i-t´e aproximace εi je rozd´ıl naˇseho odhadu xi a pˇresn´eho ˇreˇsen´ı x εi ≡ xi − x
(3)
Podobnˇe jako u jin´ ych u ´loh numerick´e matematiky i u metod na hled´an´ı koˇrene ˇ zav´ad´ıme ˇr´ad metody. Rekneme, ˇze metoda je ˇr´adu p, pokud plat´ı |εi+1 | =C i→∞ |εi |p lim
kde
0
(4)
Pro pochopen´ı metod jsou nejd˚ uleˇzitˇejˇs´ı dva pˇr´ıpady - ˇr´ad 1 a ˇr´ad 2. Pro metody prvn´ıho ˇr´adu v limitˇe plat´ı, ˇze |εi+1 | = C|εi |
(5)
1 Pokud by bylo napˇr C = 10 klesla by chyba v kaˇzd´em kroku 10-kr´at. V kaˇzd´em kroku bychom tedy z´ıskali jednu platnou ˇc´ıslici v´ ysledku. Pro metody druh´eho ˇr´adu v limitˇe plat´ı, ˇze
|εi+1 | ≈ |εi |2
(6)
Nov´a chyba je tedy mocninou pˇredchoz´ı chyby, napˇr. εi = 0.1, 0.01, 0.0001, 0.000001. Poˇcet platn´ ych ˇc´ıslic v´ ysledku se tedy v kaˇzd´em kroku zdvojn´asobuje.
1.1
Metoda p˚ ulen´ı intervalu
Nejz´akladnˇejˇs´ı metodou je metoda p˚ ulen´ı intervalu. Do cel´eho algoritmu a pot´e i do kaˇzd´e iterace vstupuj´ı dva body x1 a x2 ve kter´ ych funkce nab´ yv´a opaˇcn´ ych znam´enek, t.j. mus´ı platit f (x1 )f (x2 ) < 0
(7)
V kaˇzd´e iteraci sestroj´ıme prostˇredn´ı bod x3 . Tu z dvojic x1 ,x3 a x3 ,x2 , kter´a splˇ nuje podm´ınku (7) pouˇzijeme do dalˇs´ı iterace.
Numerick´a matematika
4
Obr´azek 1: Metoda p˚ ulen´ı intervalu.
x3 = (x1 + x2 )/2 f (x1 )f (x3 ) < 0 x3 → x2 f (x1 )f (x3 ) > 0 x3 → x1
(8) (9) (10)
Tato metoda je vˇzdy kovergentn´ı, je ale pouze 1. ˇr´adu. Konstanta C ve vztahu (4) je rovna 12 . Na kaˇzdou iteraci se tedy odhad koˇrene zpˇresn´ı o jednu bin´arn´ı ˇc´ıslici.
1.2
Metoda jednoduch´ e iterace
ˇ senou rovnici f (x) = 0 vhodn´ Reˇ ym zp˚ usobem uprav´ıme do tvaru g(x) = x
(11)
xi+1 = g(xi )
(12)
Potom prov´ad´ıme iterace
Tento proces je kovergentn´ı pouze pokud plat´ı |g 0 (x)| < 1
1.3
(13)
Newtonova metoda
Newtonova metoda se t´eˇz naz´ yv´a metoda teˇcen. Zaˇcneme s odhadem koˇrene x0 . V tomto bodˇe sestroj´ıme teˇcnu ke grafu funkce f . Pr˚ useˇc´ık t´eto teˇcny s x-ovou osou pouˇzijeme jako dalˇs´ı odhad koˇrene. xi+1 = xi −
f (xi ) f 0 (xi )
(14)
Numerick´a matematika
5
Obr´azek 2: Newtonova metoda.
Pokud tato metoda koverguje, konverguje velice rychle. Je to metoda 2. ˇr´adu, poˇcet platn´ ych desetinn´ ych m´ıst v´ ysledku se v kaˇzd´e iteraci zdvojn´asobuje. Bohuˇzel tato metoda nen´ı glob´alnˇe konvergentn´ı. Pro hladkou funkci vˇsak vˇzdy existuje okol´ı koˇrene ve kter´em metoda konvergentn´ı je. Dalˇs´ı nev´ yhodou je potˇreba v´ ypoˇctu derivace funkce. Tato metoda se vˇetˇsinou pouˇz´ıv´a v kombinaci s jinou metodou zaruˇcuj´ıc´ı konvergenci.
1.4
Metoda seˇ cen
Metoda seˇcen vych´az´ı z Newtonovy metody. Pouˇz´ıv´ame vˇsak dva odhady koˇrene a na m´ısto teˇcny pouˇz´ıv´ame seˇcnu proch´azej´ıc´ı tˇemito body. Starˇs´ı odhad koˇrene nahrad´ıme pr˚ useˇc´ıkem seˇcny a osy x. xi+2 = xi −
xi+1 − xi f (xi ) f (xi+1 ) − f (xi )
ˇ ad t´eto metody je (1 + Tato metoda nen´ı glob´alnˇe konvergentn´ı. R´ 1.618.
1.5
(15) √
5)/2 ≈
Metoda regula fasci
Jinou variantou je metoda regula fasci. Je t´emˇeˇr stejn´a jako metoda p˚ ulen´ı intervalu. Rozd´ıl spoˇc´ıv´a v tom, ˇze nov´ y bod nen´ı uprostˇred pˇredchoz´ıch odhad˚ u, ale je to pr˚ useˇc´ık seˇcny proch´azej´ıc´ı tˇemito body. f (x0 )f (x1 ) < 0 x1 − x0 x2 = x0 − f (x0 ) f (x1 ) − f (x0 )
(16) (17)
Tato metoda je vˇzdy konvergentn´ı, ke koˇreni vˇsak konverguje pouze jeden odhad, ˇ ad t´eto metody je 1. druh´ y z˚ ust´av´a konstantn´ı. R´
Numerick´a matematika
6
Obr´azek 3: Metoda seˇcen.
1.5.1
Pˇ r´ıklad
ˇ sme rovnici Reˇ x + sin x −
1 2
=0
(18)
tato rovnice m´a koˇren x = 0.251318624524097. V tabulce 1.5.1 je srovn´an´ı metody p˚ ulen´ı intervalu a Newtonovy metody. k 0 1 2 3 4 5 6 7 8 9 10 11 12 13
(k)
x1 0.000000 0.250000 0.250000 0.250000 0.250000 0.250000 0.250000 0.250000 0.250000 0.250977 0.250977 0.251221 0.251221 0.251282
(k)
x2 0.500000 0.500000 0.375000 0.312500 0.281250 0.265625 0.257812 0.253906 0.251953 0.251953 0.251465 0.251465 0.251343 0.251343
(k)
x − x3 0.001319 -0.123681 -0.061181 -0.029931 -0.014306 -0.006494 -0.002588 -0.000634 0.000342 -0.000146 0.000098 -0.000024 0.000037 0.000006
x(k) 1.5000000 -0.3655323 0.2668466 0.2513027 0.2513186
x − x(k) -1.2486813 0.6168510 -0.0155280 0.0000159 0.0000000
Tabulka 1: Srovn´an´ı p˚ ulen´ı intervalu (vlevo) a Newtonovy metody (vpravo).
Numerick´a matematika
1.6
7
N´ asobn´ e koˇ reny
Pˇripomeˇ nme definici n-n´asobn´eho koˇrene rovnice f (x) = 0 f (i) = 0
i = 0, 1, . . . , n − 1 f (n) 6= 0
(19) (20)
V pˇr´ıpadˇe, ˇze hledan´e koˇreny jsou v´ıcen´asobn´e, vˇetˇsina metod selh´av´a. Jednou moˇznost´ı je vyuˇzit´ı toho, ˇze jestliˇze f (x) = 0 m´a v´ıcen´asobn´ y koˇren potom rovnice u(x) = 0, kde u(x) = ff0(x) , m´ a jednon´ a sobn´ y koˇ r en. Jinou moˇznost´ı je (x) n´asleduj´ıc´ı modifikace Newtonovy metody xi+1 = xi − n
1.7
f (xi ) f 0 (xi )
(21)
Aitken˚ uv δ 2 -proces
Pro metody prvn´ıho ˇr´adu existuje moˇznost urychlen´ı, zvan´a Aitken˚ uv δ 2 -proces. Oznaˇcme α ˇreˇsen´ı naˇs´ı rovnice. Pro metodu prvn´ıho ˇr´adu plat´ı α − xi+1 = Ci (α − xi )
(22)
Pˇredpokl´adejme, ˇze konstanty Ci se jiˇz pˇr´ıliˇs nemˇen´ı Ci ≈ C, potom α − xi+2 α − xi+1 ≈ α − xi+1 α − xi
(23)
Z t´eto rovnice m˚ uˇzeme urˇcit nov´ y odhad koˇrene α≈
xi xi+2 − x2i+1 (∆xi+1 )2 = xi+2 − xi+2 − 2xi+1 + xi ∆2 xi
(24)
Odhady vypoˇc´ıtan´e z tohoto vztahu konverguj´ı rychleji neˇz p˚ uvodn´ı iterace xi .
1.8
Soustavy rovnic
Budeme nyn´ı ˇreˇsit soustavu n rovnic o n nezn´am´ ych Fi (x1 , x2 , . . . , xn ) = 0 1.8.1
i = 1, 2, . . . , n
(25)
Newtonova metoda
Z´akladn´ı metodou je zobecnˇen´ı Newtonovy metody. Nejprve rozvineme funkce lev´ ych stran do ˇrady Fi (x + δx) = Fi (x) +
n X ∂Fi j=1
∂xj
+ O(δx2 )
(26)
Numerick´a matematika
8
Zavedeme matici derivac´ı - Jacobi´ an Jij Jij ≡
∂Fi ∂xj
F (x + δx) = F (x) + J · δx + O(δx2 )
(27) (28)
Budeme uvaˇzovat iteraˇcn´ı proces x(i+1) = x(i) + δx. Naˇs´ım c´ılem je zvolit δx tak, aby F (x+δx) = 0. Z rovnice (28) po zanedb´an´ı posledn´ıho ˇclenu dost´av´ame podm´ınku J · δx = −F . Cel´ y iteraˇcn´ı proces tedy je x(i+1) = x(i) − J −1 (xi ) · F (xi )
(29)
Dostali jsme tedy vztah podobn´ y p˚ uvodn´ı Newtonovˇe metodˇe. Nam´ısto dˇelen´ı derivac´ı nyn´ı vˇsak mus´ıme n´asobit inverzn´ım Jacobi´anem. Metoda nen´ı glob´alnˇe konvergentn´ı, pokud vˇsak m´ame dostateˇcnˇe dobr´ y odhad koˇrene, metoda konverguje rychle. V kaˇzd´em kroku je tˇreba vypoˇc´ıtat Jacobi´an a ˇreˇsit soustavu line´arn´ıch rovnic. 1.8.2
Pˇ r´ıklad
ˇ s´ıme soustavu rovnic Reˇ 2x3 − y 2 − 1 = 0 3
xy − y − 4 = 0 Vypoˇc´ıt´ame parci´aln´ı derivace a sestav´ıme Jakobi´an t´eto soustavy · ¸ 6x2 −2y J= y 3 3xy 2 − 1
(30) (31)
(32)
V kaˇzd´em kroku metody je tˇreba nejprve vyˇreˇsit soustavu line´arn´ıch rovnic · ¸· ¸ · ¸ 6x2 −2y dx 2x3 − y 2 − 1 = (33) y 3 3xy 2 − 1 dy xy 3 − y − 4 a pot´e vypoˇc´ıtat novou aproximaci ˇreˇsen´ı x ← x − dx
y ← y − dy
(34)
V´ ysledky tohoto postupu jsou v tabulce 1.8.2. V´ ysledky v posledn´ım ˇr´adku jsou platn´e na pln´ y poˇcet ˇc´ıslic. Vid´ıme, ˇze metoda konverguje velice rychle.
Numerick´a matematika
k 0 1 2 3 4 5 6 7
x(k) 1.00000000000000 1.57142857142857 1.38455347014689 1.27276925577104 1.23740148731123 1.23429695463203 1.23427448529044 1.23427448411448
9
y (k) 1.00000000000000 2.71428571428571 2.09253530359103 1.76850431820878 1.67018786017900 1.66158901065441 1.66152647008248 1.66152646679593
ˇ sen´ı soustavy rovnic Newtonovou metodou. Tabulka 2: Reˇ
