MASARYKOVA UNIVERZITA PRÍRODOVEDECKÁ FAKULTA Funkcionální analýza a numerické metody Diplomová práce Bc. Karel Suites Vedoucí diplomové práce: prof. RNDr. Ivanka Horová, CSc. Brno 2007 Prohlašuji, že jsem tuto diplomovou práci vypracoval samostatně na základě konzultací s vedoucí a s užitím literatury uvedené v seznamu. 6.5.2007 Děkuji vedoucí této práce prof. RNDr. Ivance Horové, CSc. za cenné rady, doporučení literatury a také za pečlivé přečtení celého textu. Úvod Cílem této diplomové práce je užít nástrojů funkcionální analýzy ke konstrukci obecných numerických algoritmů. Text je členěn do tří kapitol. První slouží jako úvod pro zavedení symboliky a obsahuje formulaci a důkaz obecné věty o pevném bodě, na kterou se v dalším textu odkazuji. V závěrečné části první kapitoly jsou popsány konvergenční faktory. Druhá kapitola se věnuje Newtonově metodě pro hledání kořenů operátorových rovnic. Zde je dokázána věta o lokální kovergenci spolu s existenčním tvrzením Kantorovičovy věty, jejíž předpoklady nezávisí na kořeni rovnice. Poslední kapitola obsahuje návrh algoritmu užívajícího Newtonovu metodu pro hledání kořenů systémů rovnic v prostoru W1 . Tohoto algoritmu je v závěrečné části užito k vyřešení okrajové úlohy diferenciálních rovnic. Obsah 1 Iterační proces 2 1.1 Pseudometrické prostory 2 1.2 Iterační proces 4 1.3 Věta o pevném bodě 5 1.4 Rychlost konvergence 12 1.5 Vztahy a vlastnosti konvergenčních faktorů 17 1.6 Rychlost konvergence při změně normy 21 2 Newtonowa metoda 24 2.1 Diferenciální počet pro nelineární operátory 24 2.2 Newtonova metoda 26 2.3 Aplikace Newtonovy metody 32 3 Implementace Newtonovy metody 36 3.1 Základní algoritmus 36 3.2 Způsoby hledání Newtonova kroku 38 3.3 Implementace Newtonovy metody 39 3.4 Numerické řešení okrajového problému 42 Kapitola 1 Iterační proces 1.1 Pseudometrické prostory V úvodu je definován pseudometrický prostor, konvergence v pseudometrickém prostoru a další pojmy, které užijeme zejména v při formulaci a důkazu věty o pevném bodě. Více podrobností lze najít například v [5]. Definice 1. Množina H se nazývá částečně uspořádaná, je-li na ní definovaná relace <, splňující 1. h < h pro libovolné h E H. 2. Jestliže je / < g a g < h, pak je i / < h. 3. Jestliže je / < g a g < h, pak je i g = f. Tato relace nemusí být definovaná pro libovolné dva prvky z H. Pokud je H vektorový prostor nad polem K, pak požadujme, aby relace < navíc splňovala 1. Je-li 6H < h, pak pro libovolné a E K větší jak 9K, je 6H < oih 2. Pokud h\ < k\ & fi2 < k2, pak h\ + h,2 < k\ + fo, kde symbolem 9V označujeme nulový prvek ve vektorovém prostoru V. Definice 2. Prostor U nazveme pseudometrickým, je-li každé dvojici u,v E U přiřazena pseudometrika g(u, v) , která je prvkem lineárního částečně uspořádaného prostoru H nad polem K. Navíc na g(u,v), klademe následující podmínky : 1. Platí Q(U,V) = 9H pro u = v. 2. Pro libovolné u,v,w E U platí Q(U,V) < g(u,w) + Q(V,W). 2 Dále označujme pseudometrický prostor písmenem U, pseudometriku g a písmenem H příslušný částečně uspořádaný lineární prostor, který vzhledem k jeho účelu, budeme nazývat prostor pseudovzdáleností. Následující věta nám zaručuje symetrii g a v jistém smyslu nezápornost. Věta 1.1.1. Pro libovolné dva u,v E U platí 1. g(v,u) = g(u,v). 2. g(u,v) > 9HDůkaz. 1. Položme u = w, pak z trojúhelníkové nerovnosti dostaneme g(u,v) < g(u,u) + g(v,u), odtud je vidět, že g(u,v) < g(v,u). Dále položme v = w, pak g{v,u) < g(v,v) + g{u,v), tedy g(v,u) < g(u,v). A to dokazuje g(v,u) = g(u,v). 2. Z v = w dostáváme g(u,u) < g(u,v) + g(u,v) = 2g(u,v), odtud 9H = g(u,u) < 2g(u,v). D Následující definice umožní definovat konvergenci v pseudometrickém pro­ storu. Definice 3. Řekneme, že posloupnost {/„} prvků z H konverguje k /, značíme fn —• /, jestliže splňuje následující podmínky 1. Platí-li \/n fn = g, pak / = g. 2. Jestliže /„ —• /, pak pro libovolnou vybranou posloupnost fnm platí Jrim * I- 3. Pokud fn -• / a gn -• g, pak fn + gn -^ f + g. 4. Pokud / „ ^ / a c ^ ^ c , kde cn, c E K, pak cnfn -^ cf. 5. Pokud fn^> f a fn> 9H, pak / > 9H- 6. Jestliže 9H < fn < gn a gn -^ 9H, pak fn -^ 9H. Definice 4. Řekneme, že posloupnost {un} E U konverguje k prvku u E U, konverguje-li posloupnost vzdáleností g(un,u) k prvku OH E H. Značíme un —• u. Pro vektorový prostor U, navíc požadujme 1. Pokud un ^ u a vn ^ v, pak un + vn —• tí + v. 2. Jestliže M„ -> u a c„ -> c, kde cn, c E K, pak cratíra —• ctí. Definice 5. Posloupnost {un} nazveme cauchyovskou, jestliže platí lim g(un,um) = 9H- (1.1) n,m—>oo Definice 6. Nechť T je operátor, definovaný T : H —• S", kde i í i S* jsou částečně uspořádané prostory. Řekneme, že T je pozitivní, jestliže platí f>eH implikuje Tf>6s. (1.2) 1.2 Iterační proces Nechť ř7 je úplný pseudometrický prostor a nechť T je operátor definovaný na neprázdné podmnožině D C U. Budeme se zabývat řešením operátorové rovnice u = Tu, (1.3) které označíme u* a nazveme pevný bod operátoru T. Definice 7. Vhodnou numerickou metodou řešení rovnice (1.3) je metoda tzv. postupných aproximací un+i = Tun, n = 0,l,2,..., (1.4) kde pro UQ E D dostáváme prvky U\,U2, • • • • Tyto prvky se nazývají iterace a postup, pomocí kterého je vytváříme, se nazývá iterační proces. Iterační proces budeme označovat stejně jako příslušný operátor T. V této kapitole budeme sledovat, za jakých podmínek lze iterační proces provést bez omezení a kdy bude posloupnost {un} konvergovat kn*. To obecně závisí na volbě počátečního prvku u0, proto množinu všech prvků, pro které odpovídající posloupnost {un} konverguje k u* nazveme počátečním oborem u*. 4 Definice 8. Označujme C(T, u*) množinu všech iteračních posloupností procesu T konvergujících k pevnému bodu u*. Poznámka. Definice 7 je speciální případ obecnějšího přístupu k iteračním procesům. Neobsáhne například proces, který k výpočtu následující iterace potřebuje více než jednu iteraci předchozí, popřípadě proces, u kterého se tento počet mění. My však vystačíme s výše uvedenou definicí, která bývá v literatuře označována jako jednokroková stacionární metoda. 1.3 Věta o pevném bodě V této části je formulována a dokázána obecná věta o pevném bodě, zároveň je zde uveden její speciální případ, který budeme v textu užívat pro důkazy dalších tvrzení. Nechť U je pseudometrický prostor. Věta 1.3.1 (Obecná věta o pevném bodě). Nechť definiční obor D operátora T leží v úplném pseudometrickém prostoru U s příslušným lineárním částečně uspořádaným prostorem H. 1. Necht k operátoru T existuje spojitý, pozitivní operátor P definovaný na H a pevně daný prvek z E U tak, že pro libovolné dva prvky v,w E D platí Q(TV, TW) < P(Q(V,W) + g(v, Z)) — PQ(V, Z) (1.5) 2. Nechť pro metriky g, g ,a,a z H splňujcí 9H < Q < Q a OH < o < a , kde OH je nulový prvek v H, platí OH g(iiQ,z), <7i > <7o + g(u0,ui). (1.8) 4- Existuje prvek 7 E H tak, že\/u E H platí Sv = Pľ + j . (1.9) 5 5. Předpokládejme, že an konverguje k a. Ze spojitosti P a z (1.9) plyne spojitost operátoru S. A tedy i a = Sa. (1.10) 6. Nechť koule K prvků v, splňujících K = {v, g(v,u\) < a — aj, pak průnik definičního oboru D s uzavřenou koulí Kj, která je definována vztahem Kj = {v, Q(V, UJ) < Uj - aj}. (1.13) obsahuje nejvýše jeden pevný bodu* operátoru T. Speciálně, koule K definovaná v (1.11) obsahuje právě jeden pevný bod. Důkaz. Důkaz věty je rozdělen do šesti bodů, kde v prvních pěti je ukázána existence pevného bodu a v posledním jednoznačnost. 1. Indukcí ukážeme, že prvky an (n = 1, 2, 3,...) tvoří neklesající posloupnost. Tedy, že platí on < an+l (ra>0). (1.14) Podle (1.8) platí (1.14) pro n = 0. Předpokládejme, že (1.14) platí až do n, pak pro n + 1 z (1.9) a z (1.7) máme Cra+2 — Cri+l = ^ r a + l — San = Pan+\ — 7 — Pan + 7 > QuZ pátého předpokladu a z první, druhé a páté podmínky konvergence v definici (3) plyne &H ^i CTQ < ai < • • • < a. 6 2. Ukážeme, že operátor T zobrazuje kouli K do sebe. Tedy, že pro v E T platí g(u\,Tv) < a — o\. (1-15) Z trojúhelníkové nerovnosti a z (1.8) platí Q(UO,V) < Q(UO,UI) + Q(UI,V) < o\ — a0 + (T — o\ < a — a0. (1-16) Potom z (1.5), (1.16) a (1.9) dostáváme Q(UI,TV) = Q(TU0, TV) < P(Q(UO,V) + g(u0, z)) - Pg(u0, z) < P (a - a0- o"o) - P((?o) = S (a) - 7 - S(a0) + 7 = o - o\. Tedy platí (1.15), a proto Tv E K. 3. Nyní ukážeme platnost nerovností g(um,un) < an — am pro 0 < m < n, kde n = 0 , 1 , . . . (1-17) a g(un,z)<(Tn pro n = 0,1,2... (1-18) Dokážme nejpve (1.17) indukcí. Pro n = 0 a n = 1 platí (1.17) z (1.8). Nechť (1.17) platí do n > 0, ukážeme, že platí i pro n + 1. Požadujme navíc, aby 1 < m < n + 1, kde platnost pro m = 0 ukážeme následně. Podle iteračního předpokladu platí g(un,um_i) < an — om_\. Předpokládejme ještě, že platí g(um_i,z) < (tí0, Z)) - P^(«0, -2) + Ol < P((Ti - (To + (To) - P((T0) + (Ti = S{ m z (1.17) a trojúhelníkové nerovnosti dostaneme, že platí g(u*,um) < g(u*,un) + g(um,un) < g(u*,un) + (Tri (Tra- (1.20) Nechť n —• oo, pak ttn -^- tt*, j . Pak pro n + 1 máme g(w*,un+i) = g(Tw*,Tun) < P(g(w*,un) + g(un, z)) - Pg(un,z). Dále užitím indukčního předpokladu dostáváme g(w*,un+i) = P{yn - an + an) - Pan = Svn - San = un+x - an+í. Tedy (1.23) platí. Pro n —• oo máme un -^ u*, un -^ a a an -^ a, a tedy z předchozího g(w*,u*) < a — a = Qu- A proto z definice pseudovzdálenosti dostáváme, že u* = w*. Pokud navíc zvolíme vj = a, potom pro j'• = 1 dostaneme kouli K z vztahu (1.11). Protože z pátého předpokladu této věty plyne, že K C D dostáváme, že K obsahuje právě jeden pevný bod. D 9 K užití předchozí věty bylo potřeba ověřit všech šest, respektive sedm předpokladů zajišťujících existenci, respektive jednoznačnost pevného bodu. Často však vystačíme pouze s jejím speciálním případem, kdy prostor U je Banachův a operátor P je lineární. Získáme tak následující větu. Věta 1.3.2 (Banachova věta o pevném bodě). Předpokládejme, že K je neprázdná množina v Banachově prostoru U a že T : K —• K je kontraktivní zobrazení s konstantou 0 < a < 1. Pak existuje u* E K splňující rovnici u = T (u) a zároveň pro libovolné UQ E K posloupnost definovaná vztahem un+\ = T{un) prv n = 0,1,2,... konverguje k u*. Prv odhad chyby platí an Q(um,un)<- g(ui,u0). (1.24) l — a Důkaz. Ukážeme, že jsou splněny předpoklady věty 1.3.1. 1. Definujme Px := ax. Vzhledem k tomu, že násobení reálným nezáporným číslem a představuje spojitý, lineární a pozitivní operátor. A protože platí g(Tu, Tw) < ag(u, w) = a(g(u, w) + g(v, z)) — ag(v, z). Dostáváme, že je splněn první předpoklad věty 1.3.1, který platí pro libovolné z E U. Volme dále z = u0. 2. Zřejmě pro 9H < Q < Q a 9H < & < g platí OH < OL{Q + a) — aa < a(g + a ) — a . Tedy je splněn i druhý předpoklad. 3. Definujme operátor S následovně S Q = ag + 7, kde 7 = Q(UQ, U\). Volme navíc UQ = 9H- Pak platí g(u0,z) < do a <7i = S (To = acr0 + 7 = 0H + Q(UO , «1), tedy o\ > ao + g{uo,ui). 10 4. Plyne přímo z volby S. 5. Z definice S dostáváme, že <7i = Cü(7o + 7 (72 = CÜ(CÜ(7O + 7) + 7Platí tedy an = YľjZo a ^l- Vzhledem k tomu, že 0 < a < 1 tato řada konverguje, a proto {an} konverguje. 6. Šestá podmínka ve větě 1.3.1 zaručuje, že prvky un leží v kouli K. Vzhledem k tomu, že operátor T je zobrazení z K do K, není potřeba ji ověřovat. Pokud bychom na operátoru T tuto podmínku nepožadovali, pak by bylo nutné navíc předpokládat, že K je koule prvků v, pro které platí OL Q(V,UI) < Q(UQ,UQ). I — a Pak platí OL Q(V,UI) < g(u0,ui) l — a = (1 - a) 1 Q(U0,UI) - Q(U0,UI). Navíc víme, že řada YľjLo °^x konverguje \/x E E, proto platí 00 (1 — CÜ)- 1 7 = y , aJ 1> kde 7 = Q(UQ, U\). 3=0 Podrobnosti lze najít v [5, strana 93]. Nakonec platí g(v,ui) < (1 - a)~X Q{u0,ui) - g(u0,ui) 00 = (1 — CÜ)- 1 7 — 7 = / ^ 7 — 7 = er — <7i. i=o Tím jsme dokázali existenci. Jednoznačnost pak vyplývá z poznámky na konci důkazu 1.3.1. Zbývá ukázat platnost (1.24). Protože T je kontraktivní zobrazení, dostáváme g(un+1,un) < ag(un,un-i) <••• < an g(ui,uo). A tedy platí m—ri—1 „ ^—\ OL g(um,un) < 2_^ g(un+j+i,un+j) < g(ui,u0). j=o D 11 1.4 Rychlost konvergence V následujícím jsou uvedeny tzv. konvergenční faktory, které jsou do jisté míry měřítkem kvality metody. Nechť U je normovaný prostor s pevně zvolenou normou ||-|| a nechť / značí interval / = (l,oo) C R. Definice 9. Mějme {uk} C U posloupnost konvergující k u* a nechť je p E I, pak čislo ílimsupfc^Jlufc-u*!^ p r o p = l tip\Uk\ = < i [limsupfc^^Htífc — u*\\p p r o p > l . nazýváme R-faktorem posloupnosti {«&}. Definice 10. Mějme iterační proces un+\ = Tun s pevným bodem u*, číslo Rp(T,u*) = su.p{Pup{uk}, {uk} e C (T, u*)}, kde C (T, u*) je definované v definici 8, nazýváme R-faktorem iteračního procesu T v bodě u*. Uvažujme {uk}, posloupnost z C(T,u*), pak existuje index fc0 takový, že pro všechna k > fco je 0 < ||tífc — u*\\ < 1. Pak zřejmě platí 0 < Rp{uk} < l,a tedy i 0 < Rp(T,u*) < 1 pro všechna p E I. Věta 1.4.1. Mějme iterační proces T s pevným bodem u*. Pak platí právě jedno z následujících tvrzení 1. Rp(T,u*) = 0 Vpel. 2. Rp(T,u*) = 1 Vpel. 3. Existuje po E I tak, že VpElí, platí Rp(T,u*) = i i = 0,1, (1.24) kde I0 = (l,Po) a h = (p0, oo). Důkaz. Důkaz rozdělíme do tří kroků. 1. Ukážeme, že pro libovolnou posloupnost {uk} platí, že pokud existuje Po E I tak, že 0 < Rp{uk} < 1, pak platí pro pel: p < po RP{uk} = 0 pro pel: p > po Rp{uk} = 1. 12 Mějme tedy libovolně, ale pevně, posloupnost {uk} a p 0 G / takové, že 0 < Rp{uk} < 1. Označme sk = \\uk — u*\\. Předpokládejme, že po > 1, ukážeme, že \/q < po platí Rq{uk} = 0. (1-25) Nechť e > 0 je takové kladné číslo, že RP0{uk} + e = r k0 platí i ef < r. (1.27) Proto pro q = 1 platí Rq{uk} = lim sup(e^) = lim sup(e^0 ) p ° < lim r k = 0 fc—>oo fc—>oo fc—>oo a pro l < g < p 0 j e e > l a platí i -Rg{«fc} = lim sup(e^! ) = limsup(e^°) p o < lim r^' = 0. fc—>oo fc—>oo fc—>oo Tím jsme dokázali (1.25). Zbývá ukázat, že pro po < g je i?g{t(fc} = 1. Nechť je e > 0 takové kladné číslo, že platí 0 < RP0{uk}-e = r < 1. (1.28) Vzhledem k definici 9 a (1.28) bude pro libovolný index fc0 existovat index k\ > k0 takový, že platí £fc° ^ r Po > 1 -fc! Pro po = 1 platí PO 1 £fcí > r po = 1. i i x _ ^ -Rg{t(fc} = lim sup(si ) = lim sup(e£) fc > lim sup r «fc = 1 fc—>oo fc—>oo fc—>oo 13 a pro po > 0, je — < 1, proto platí Rq{uk} = limsup(e^ ) = limsup(e^°) p o > lim sup r( i> = 1 . k—>oo k—>oo k—>oo 2. Nyní ukážeme, že pokud neplatí 1. ani 2. tvrzení věty, pak platí 3. tvrzení. Označme Po=mí{peI,Rp(T,u*) = 1}.' (1.29) ukážeme, že platí následující Rp(T, u*) = 1 Vp > po J RP (T,M*) = 0 V p < p 0 . Předpokládejme opak 3p >po : Rp(T,u*) < 1, odtud platí -Rp-ftífc} < 1 Vtífc G C(T,u*). Z definice číslap0 plyne existence q G (po,p) takového, že Rq(T, u*) = 1. Pak existuje {vk} tak, že -Rg{wfc} > 0. Odtud vzhledem k q < p a první části důkazu dostáváme, že Rp{vk} = 1, ale to je spor s (1.30). Podobně by se ukázalo tvrzení i pro p < po- 3. Nyní ukážeme, že platí právě jedno z uvedených tvrzení věty. Už víme, že 1. a 2. neplatí právě tehdy když, platí 3. Předpokládejme tedy, že neplatí 1. a 3., odtud z neplatnosi 1. máme 3po : Rp0(T, u*) > 0. To vzhledem na první část důkazu dává Rp0(T, u*) = 1, protože jinak by platilo 3. Provede-li se stejná úvaha pro libovolné p E I, dostaneme 2. Zřejmě naopak z platnosti 2. dostáváme neplatnost 1. i 3. Stejně se ukáže ekvivalence neplatnosti 2. a 3. a platností 1. D Uvažujme dva iterační procesy un+1 = Tiun (1-31) un+i = T2un, (1-32) se stejným pevným bodem u*. 1.30 14 Definice 11. Řekneme, že iterační proces (1.31) je R-rychlejší v u*, než (1.32), jestliže existuje po E I takové, že Rp0(Ti,u*) < i?Po(T2,t(*). i Věta 1.4.1 nám zaručuje, že nenastane si- T tuace, kdy by jeden iterační proces byl Rrychlejší, než druhý a zároveň by platil opak. T ~2 Toho si můžeme všimnout na obrázku 1.1, —\ m ' 1 Po kdy neexistuje p\ E / takové, že by platilo Rpl(Tl}u*) > Rpl(T2,u*), proto předchozí de- Obrázek l.l: finice dává smysl. Definice 12. Mějme iterační proces un+\ = Tun, s pevným bodem u*. Pak číslo O (Tu*) = {°0) jestliže Rp(T,u*) = 0 Vp E I 1 ,U ' |inf{p G I,Rp(T,u*) = 1} jinak, (1.33) nazveme R-řádem iteračního procesu T v u*. Zřejmě proces (1.31) je R-rychlejší než (1.32) v u* právě tehdy, když QR(T1,U*)>QR(T2,U*). Dále definujeme Q-faktor, resp. Q-řád, jejichž vlastnosti budou podobné Rfaktorům, resp. R-řádům. Definice 13. Nechť {uk} je konvergentní posloupnost s limitou u* a p G /. Pak číslo {0, jestliže Uk = u* pro Vfc > ko limsup^^ ľfc+ _^~JjJ , je-li Uk ^ u* Vfc a navíc je tato limita vlastní oo ve všech ostatních případech (1.34) nazveme Q-faktorem posloupnosti {u*}. Poznamenejme, že Q-faktor {tífc} nabude hodnoty oo jednak pokud neexistuje příslušná vlastní limita, nebo pokud existují indexy k0 a k\ takové, že ko < k\, Uk0 = u* a zároveň Ukx ^ u*. Definice 14. Je-li T iterační proces s pevným bodem u* a p G /, pak číslo Qp(T,u*) = sup{Qp{uk},{uk} G C(T,u*)} (1.35) nazveme Q-faktorem iteračního procesu T v bodě u*.15 Podobně jako pro R-faktory platí následující věta. Věta 1.4.2. Mějme iterační proces T s pevným bodem u*. Pak platí právě jedno z následujících tvrzení 1. Qp(T,u*) = 0 Vpel. 2. QP(T,u*) = oo Vpel. 3. Existuje po E I tak, že Wp E li, platí Qp(T,u*) = i i = {0,oo} (1.36) kde I0 = (l,Po) a 1^ = (p0, 00). Důkaz. Důkaz se provede podobně jako v 1.4.1. D Můžeme tedy zavést následující definice. Definice 15. Řekneme, že iterační proces (1.31) je Q-rychlejší v u* než (1.32), jestliže existuje po E I takové, že Qp(T\,u*) < Qp(T2,u*). Podobně jako u R faktorů věta 1.4.2 nám 21 zaručuje, že předchozí definice dává smysl (viz obrázek 1.2). 21 0 aa T2 0 3C —\ H 4 - 1 Po Obrázek 1.2: Definice 16. Mějme iterační proces un+\ = Tun, s pevným bodem u*. Pak číslo Q (T u*) = / ° ° ' jestliže QP(T,u*) = 0 Vp E I 1 inf{p E I,Qp(T, u*) = 00} jinak (1.37) nazveme Q-řádem iteračního procesu T v u*. Podobně jako u R-řádů je proces (1.31) Q-rychlejší než (1.32) v u* právě tehdy, když QQ(T1,u*)>QQ(T2,u*). 16 1.5 Vztahy a vlastnosti konvergenčních fak­ torů Věta 1.5.1. Nechť {uk} C U je posloupnost, která konverguje k u*, pak Ri{uk} < Qi{uk}. (1.38) Pokud T je iterační proces s pevným bodem u*, pak Ri{T,u*) 0 je libovolné. Z definice limity bude pro dané e > 0 existovat k0 : k > k0, platí Qi{uk}\ < e. K - i ~u * Odtud dostáváme Uk-u < e + Qi{uk\ = a.\\Uk-l -u*u Proto n *n \\Uk — u*\\ „.. „.. £fc = Mfc - u \\ = —\\Uk-i - u \\ < a\\Uk-i -u \\ = ask-i\\Uk-l - u*\\ Užitím indukce a vhodnou volbou k0 dostaneme £k < aek-i <•• < ak ~ko eko Vfc > k0, tedy R\{uk] = lim sup el k—>oo = limsup(cüfc ——)k < Cülimsup(—-^-)k k—>oo CY fc—>oo CY = a = Qi{uk} + e. Protože e bylo libovolné, platí (1.38) D Věta 1.5.2. Nechť T je iterační proces s pevným bodem u*. Pak platí QQ(T,u*)c 0 1 Důkaz. Na obrázku 1.3 je vidět, že pokud QQ(T, U*) = 1, pak vzhledem k předchozí větě platí QR(T, U*) > 1, a tedy je splněno (1.40). O b r á z e k 1.3: Nechť p > 1 ukážeme, že platí QP{uk} < oo implikuje Rp{uk} < 1. (1-41) Položme, podobně jako v důkau předchozí věty, Sk = \\uk — u*\\ \/k a a = QP{uk} + £, pro libovolné e > 0. Následně, z definice limity, opět dospějeme k tomu, že Ve > 0 3fc0, takové, že \/k > ko platí Sk < aeU < a^ef_2 <•••< a ^ + - ^ - ^ £f;k \ odtud plyne 1 l +p+^ +pk-kQ-1 -±Pro k > ko dostáváme l + p + - + p f c ~ f c ° + 1 p fc-fc0 _1 1 pf c -f c O-l x / p f c - f c O - l s a pk = a p _ 1 pfc = a (p-1 )?*1 = (CÜP1 7 1 ) pfc . Vzhedem k tomu, že k > ko, platí pk-ko _ i i pk pko ' proto dostáváme — — - J - i ev k < a{ ° elo°, kde a\ = max(l, ap111 ). i Zřejmě lze ko zvolit tak, aby platilo (a\£k0)pko < 1, tedy -Rp{«fc} = lim sup e^ < limsup(cüiefc0)pfc ° < 1. k—>oo fc—>oo To dokazuje implikaci (1-41) a tedy i (1-40) D Na následujícím příkladě je vidět, že existuje proces, u kterého je Q řád ostře menší, než R řád. 18 Příklad. Uvažujme iterační proces T : sloupnost {uk} definovanou předpisem i, který generuje jedinou po- uk (ÍT pro k — sudé, pro k — liché, (1.42) kde 0 < c u < l a l < g < p . Zřejmě platí Rp{uk} = limsupfc_ Odtud, vzhledem k větě 1.4.1, je Spočítáme dále IK+i - o| £\^fc ai)p — 0||pfc = ai, kde 0 < a? < 1. (1.43) \uk - Oil« QR(T,0)=p. (f/+i (^\pk -+0 pro fc liché, pro k sudé. (aV* \ 2P J1 /r-1-1 -+0 pro fc liché, pro k sudé. Zřejmě tedy Qg(T,0) = oo, a proto QQ(T,0) < q. Přestože R a Q řády popisují chování procesů pro dostatečně velká k, je možné nahlédnout na jejich rozdíly a vlastnosti při zobrazení konečného počtu prvků posloupnosti (1.42). « ' » » » • ; ' ; . "•*.. " * * + + + . ••*-.09 « ' » » » • ; ' ; . "•*.. " * * + + + . ••*-. * 099 0 5^ •1= 1= 1 01,p=1 04 1 Ol.p-1D8 08 « ' » » » • ; ' ; . "•*.. " * * + + + . ••*-. 0.7 \ • 0.6 * '_ 05 0.4 ;. . • 0.3 . *, • 0.2 + • 01 '..* > ± ± * * * 4 •+ •K 0.7 0.B 05 0.4 0.3 0 2 - 01 cf-^D S9.q^1 1 ,p^1 11 o^0.99.q=1+10-10 .p=1 11 0 10 20 30 40 50 60 70 80 90 100 0 10 20 30 40 50 60 70 Obrázek 1.4: Obrázek 1.5: Na obrázku 1.4 je vidět, že zvýšení hodnoty p, která podle (1.43) znamená zvýšení R řádu, způsobilo zrychlení konvergence. Dá se říci, že R řád vyjadřuje celkovou rychlost zmenšování chyby. 19 Naproti tomu Q řád vyjadřuje závislost chyby iterace na iteraci předchozí. Obrázek 1.5 tuto situaci vystihuje, zároveň je možné dojít ke stejnému závěru z definice Q řádů posloupností, kde v příslušné limitě vystupuje poměr následující iterace k mocnině iterace předchozí. Na závěr je zde uvedeno vhodné kritérium, na určování řádů. Věta 1.5.3. NechiT je iterační proces s pevným bodem u*. Předpokládejme, že existuje p E I a konstanta ß taková, že pro všechny posloupnosti {uk} E C (T, u*) platí IK+i -u*\\< ß\\uk - u*\\p Vfc > fc0, (1.44) kde ko závisí na {uk}. Pak QR(T,u*)>QQ(T,u*)>p. (1.45) Jestliže navíc existuje konstanta a > 0 a posloupnost {uk} E C(T, u*) taková, že platí \\uk+i-u*\\>a\\uk-u*\\p >0 \/k > k0, (1.46) pak QQ(T,U*) < QR(T,U*) < p. Odtud také plyne, že pokud (1.44) a (1.46) platí současně, pak se oba řády rovnají číslu p. Důkaz. Pokud 3fc0 : Uk0 = u*, pak by muselo vzhledem k (1.44) platit Uk = u* pro \/k > ko- Proto by Qp{uk} = 0. Nechť uk ŕ u* Vfc, pak " ^ " ^ J 1 < ß, tedy i QP(T,u*) E (0,ß). Proto vzhledem k větě 1.4.2 dostáváme (1.45). Přepokládejme, že (1.46) platí pro nějakou posloupnost {uk} E C(T,u*), pak platí £k = ||tífc — ti* || > 0 Vfc > fcoZ (1.46) také dostáváme, že ek+i > a1+p+ -+pk -ko eCko+ \ p > 1, Vfc > fco a Sk+i > ak -k0+1 ek k;k0+1 , p=l fc>fc0. Nechť je nyní p = 1, pak P^iuk} > lim (ak -k0+1 ek k;k0+1 )^ = aeko > 0. Nechť p > 1, pak podobně jako v důkazu věty (1.5.2) platí Rp{uk} = lim sup e ^ 1 > limsup(o;^TT+ ^+ '"+ ?<ÍTT efc P o fco ) k—>oo k—>oo i i 1 fcn 1 kn > lim (imii{l} ap^1 )si ) = min(l, Q,p=I )sl > 0. 20 Protože pro p > 1 i p = 1 platí Rp{uk} > 0, je i Rp(T,u*) > 0, a tedy QR(T,U*) 0 : — n— > a hk-0\\P a tím splnit podmínku (1.46). Takové a je rovno m m i i A , — OÍP J V 2 1.6 Rychlost konvergence při změně normy Na začátku předchozího paragrafu jsme uvedli, že normu, se kterou budeme pracovat, máme pevně zvolenou. Tím jsme se vyhnuli úvahám o tom, jestli definované charakteristiky iteračních procesů budou mít stejnou hodnotu i při změně normy. V této části ukážeme, že pro ekvivalentní normy mají Q, respektive R řády stejnou hodnotu a také, že Q-faktory posloupností se obecně v různých normách nerovnají. Věta 1.6.1. Nechť {uk} C U je konvergentní posloupnost s limitou u*. Pak pro libovolné p E (1, oo) je Rp{uk} nezávislý na volbě normy v U. Důkaz. Uvažujme ekvivalentní normy ||-|| a ||-|| . Nechť tedy existují konstanty C2 > c\ > 0, takové že . . . . / M M M M ; / \ ci||tí|| < ||tt|| < C2||tí|| (1-47) Pak pro p = 1 dostáváme -Ri{t(fc}||.|| = limsup(||tífc — t(*||)s < limsup(c2||t(fc — u*\\ ) s k—>oo k—>oo < lim SUp ||ttfc — U* || k = i?i{tífc}|i M/. k—>oo Podobně se ukáže Ri{uk}\\.\\ > i?i{ufc}||.|ľ a tedy, že pro p = 1 platí tvrzení věty. Dále pro p > 1 je postup důkazu téměř stejný. D 21 Důsledkem předchozí věty je, že R faktory a R řády iteračních procesů zachovávají hodnotu při ekvivalentních normách. Příklad. V E2 uvažujme posloupnost Uk a současně dvě normy (l)fc (l)fc 2 0 1 1 pro k — liché, pro k — sudé, \u\ max \Ui i=l,2 Zřejmě u* tedy Qi{ufc}|| w 2 - El Ví=l,2 a pro Qiiuk}».»^ dostáváme \Uk+l — U ||oo \\Uk - U*\\ oo (l)fc+1 = 1 (|)fc 2 6 (|)f c + 1 2 2 (Dfc 3 pro k — liché pro fc — sudé, | . Dále pro Qi{tífc}||.||2 platí \uk+i -u \\2 \\Uk - u*\\2 ( ( l)2fc+2( 2 ) ) l/2 ( ( I) 2f c ( 4 ) ) l/2 ( ( l)2fc+2( 4 ) ) l/2 ((i)2fc(2))l/2 y^2 6 y^2 3 pro k — liché pro k — sudé, tedy Qi{uk}\\ V2 3 " Odud je vidět, že analogie věty 1.6.1 se nám pro Q faktory posloupností nepovede dokázat. Lze ale ukázat následující. Věta 1.6.2. Uvažujme Qp(T,u*), pak relace Qp(T,u*) = 0 0 < Qp(T,u*) < oo a Qp(T,u*) = oo jsou zachovány v ekvivalentních normách. Důkaz. Uvažujme dvě ekvivalentní normy s vlastností (1-47) a posloupnost {«k} konvergující k u*. Pokud Uk = u* pro nejaké k, pak Qp{uk} = 0, nebo Qp{uk} = oo v libovolné 22 normě. Nechť tedy u\. ^ u* \/k. Platí Qp{uk\\\-\\ = lim sup k—>oo \\Uk U || C2\\Uk+l - U*\\ _ O2 fc^oo CiH^ífc ^ || ^1 ^ lim sup - 3 ^ ^ ^ r = -^QP{uk}\\.\\' (1-48) Podobně se ukáže QP{uk}\u\> < ^rQp{uk}\\-\\- 1. Pokud Qp(T, u*)||.|| = 0, pak V{u*} G C(T, u*) je Qp{«fc}|HI = 0. Proto Qp{M||.|ľ = °. a t e d y QP(T >U *)||.||' = °- 2. Jestliže 0 < Qp(T,u*)\\.\\ < 00, pak existuje {uk} G C(T, u*) taková, že QP{uk}\\-\\ > 0, proto Qp{ttfc}||.||' > 0, a tedy Qp(T,u*)H> > 0. Zároveň existuje číslo K takové, že QP{uk}\\.\\ < K pro V{tífc} G C(T, M*). Odtud je Qp{uk}M> < f XproV{ufc} G C(T, M*), a tedy Qp{T,u*)M> < 00. 3. Nechť Qp(T, u*)\\.\\ = 00, pak pro libovolné číslo K existuje posloupnost p {uk} G C(T, u*) taková, že QP{uk}\\.\\ > ^rK. Zřejmě pak z (1.48) platí ď ď —QP{uk}\\.\\' > Qp{uk}\\-\\ > K—, C2 c 2 tedy Qp{uk}n.\\' > K, a tedy Qp (T, «*),,,,/ = 00. D Důsledek 1. Z předchozí věty vyplývá, že Q řády iteračních procesů jsou zachovány v ekvivalentních normách. 23 Kapitola 2 Newtonowa metoda 2.1 Diferenciální počet pro nelineární operá­ tory V celé této kapitole se budeme věnovat Newtnově metodě v Banachových prostorech. K tomu účelu jsou v této úvodní části sepsány definice a jejich vlastnosti, na které se v dalším textu odkazuji. Většina důkazů zde uvedena není, ale vždy je odkázáno na příslušnou literaturu. Nechť F je operátor mezi Banachovými prostory U a V, a nechť C(U,V) označuje množinu všech ohraničených lineárních operátorů z U do V. Definice. Nechť X je otevřená podmnožina v U. Řekneme, že F je diferencovatelný v Fréchetově smyslu v bodě u0, jestliže existuje ohraničený lineární operátor A E C(U, V) tak, že F(uo + h)-F(u0) = AUoh + o(\\h\\) h^O. Pak AUo se nazývá F-derivace, resp. silná derivace v bodě UQ. Definice. Nechť X je otevřená podmnožina v U. Operátor F se nazývá diferencovatelný v Gateauxově smyslu v bodě UQ E X, jestliže existuje ohraničený lineární operátor A E C(U, V) tak, že F(u0 + th)-F(u0) = yheVAM = 1_ Í^O t Pak A se nazývá Gateauxovou resp. slabou derivací F v u0. Platí, že pokud operátor F má silnou derivaci v UQ, pak má i slabou derivaci v tomto bodě. Opak obecně neplatí, aby tomu tak bylo, musí být 24 slabá derivace v u0 spojitá v u. Označme / = («o,«o + Au) := {Atío + (1 — A)(tto + Att)|A G [0,1]} úsečku v U. Věta 2.1.1. Nechť X C U je otevřená množina. Nechť platí I = (uo,uo+ Au) C X a F : U —• V má G-derivaci \/u G I. Pak platí \\F(UQ)-F(UQ + AU)\\ < sup {||F'(uo + i>Au)||||Au||}. Důkaz. Důkaz je uveden v [8, strany 519- 520]. D Nechť je nyní U reálná osa a V Banachův prostor. Pak F : U —• V se nazývá abstraktní funkce. Je-li F definována na intervalu (a, b), pak definujme integrál F přes (a, b) následovně / b n ~1 F(t)dt :=\im^2F(0(tk+1-tk), "" fc=o kde a = to < t\ < • • • < tn-\ < tn = b £ G (ífc, ífc+i) a ö = maxfc=i...n_i|ífc+i - tk\. Zobecníme-li úvahy pro funkce nabývající skalárních hodnot, ukazuje se, že integrál z abstraktní funkce existuje a že má podobné vlastnosti jako Riemanův integrál. Například platí nerovnost F{ť)dt\\ < í \\F(t)\\dt. (2.1) Nechť jsou U, V Banachovy prostory a nechť BCuv značí množinu všech spojitých ohraničených zobrazení z U do V. Uvažujme úsečku / = («o,«o + Au) C U a F : / C U —• BCuv, pak pro pevné Au je F(u0 + tAu) Au abstraktní funkcí z [0,1] do V. Můžeme tedy definovat integrál abstraktní funkce přes úsečku. Proto j F(u)du:= / F(u0 + tAu)Audt. Věta 2.1.2 (Newton-Leibnitz). Mějme F : U -• V a I = (u0,u0 + Au) a nechť F (u) existuje na I a je spojitá vzhledem k u. Pak zřejmě F (u) G C(U, V) C BCuv tzn. F' : / -»• BCUVA platí F'(u)du = F(u0 + Au) - F(u0). 25 Důkaz. Důkaz lze najít v [8, strany 524-525]. D Dále užijeme následující větu. Věta 2.1.3 (Věta o poruchách). Nechť U a W jsou normované prostory, z nichž alespoň jeden je Banachův. Nechť A E C(V,W) má ohraničenou inverzi, tedy nechť ||A_1 || < a. Jestliže \\A — B|| < ß a ßa < 1, pak B je bijekce a platí IIA-1 » < a n. (2.2) 11 " - 1 - aß y ' Důkaz. Důkaz lze najít v [12, strana 45]. D 2.2 Newtonova metoda V této části se budeme věnovat Newtonově metodě pro hledání řešení operátorové rovnice F(u) = 0. (2.3) Je zde uvedena věta o lokální konvergenci spolu s Kantorovičovou větou, která má význam zejména pro další rozbor. Motivace pro vznik Newtonovy metody Uvažujme dostatečně hladké zobrazení F(x) : W1 —• Era , se souřadnicemi F(x) = (fi(x)). Jedním ze způsobů, jak odvodit předpis pro Newtonovu metodu, je geometrický náhled na hledání kořene rovnice F(x) = 0 pomocí tečných nadrovin1 . My však využijeme rozvoje Taylorova polynomu funkcí fi(x) v okolí bodu XQ, který je dostatečně blízko jejího kořene x*. Označujme x(i), i tou souřadnici vektoru x. Nechť je x* = x0 + e0, (2.4) pak dfi(xo) dfi(xo)e o(i) + • • • H—^ •fi(x0 + £0) - fi(x0) + - ^ e0(i) H 1- QX £0(n) 1 Tento náhled je pro funkci jedné proměnné znám a je zobrazen na obrázku 3.1 v poslední kapitole. Máme-li zobrazení v Rn , pak za následující aproximaci volíme průnik tečných nadrovin funkcí z = f i a nadroviny z = 0. 26 a tedy O = fi{x0 + e0) ~ fi{xo) + -^ e0(i) H K -^ eQ { n ) , v maticovém zápisu pak 0«F(xo) + F'(xo)eo, kde F (xn) je Jacobiho matice standardně definovaná (F\x))h3 = J|(*). Za předpokladu, že v potřebných bodech je F (x) regulární, lze e0 odhadnout pomocí £o ~ -[F'ixo^Fixo), z (2.4) dostáváme, že x\ = XQ — [F (XO)]~1 F(XO) je bod, který je blíž ke kořenu x*. Opakováním postupu pak dostaneme předpis pro Newonovu metodu xn+i = xn- [F'(xn)]~1 F(xn). (2.5) Dále zobecníme tuto metodu pro operátorové rovnice a najdeme podmínky, za kterých uvedená metoda konverguje. Newtonova metoda pro operátory Definice 17. Nechť F : U —• V je operátor mezi Banachovými prostory U, V, diferencovatelný ve Fréchetově smyslu a nechť UQ E U. Pak iterační proces Un+i = un- [F\un)]~l F{un)} (2.6) se nazývá Newtonova metoda a {un} se nazývá Newtonova posloupnost. Následující věta zaručuje lokální konvergenci Newtonovy metody v okolí řešení rovnice F(x) = 0. Toto je ale současně její nedostatek, protože předpoklady závisí na kořenu, který neznáme. Věta 2.2.1 (Věta o lokální konvergenci). Nechť u* je kořen rovnice (2.3) a nechť [F (w)]-1 existuje na okolí N(u*) a v u* je spojitý lineární operátor z V do U. Předpokládejme, že F (u) je lipschitzovsky spojitá v u*, tedy \\F\U)-F\V)\\ O konstanta. Pak existuje 8 > 0 takové, že pro u0 splňující \\u0 — u*\\ < 8 je Newtonova posloupnost definována a konverguje k u*. Zároveň pro nejakou konstantu M platí IK+i -u*\\ < M\\un-u*\\z (2.8) un-u* < , / . (2.9) II n || _ M K J Důkaz. Definici N(u*) uvedeme později. Označme Co = supueW-(u*)||[F (tí)]_1 || < oo. Definujme T(u) :=u- [F^u^F^u), V« G N(U*). (2.10) Z F(u*) = 0 dostaneme, že ti* je pevným bodem T(u), odtud pro u G N (u*) máme T(u) - T(u*) = u - [F^u^F^u) - u* = [F'iu^F'iuXu - u*) - [F'iu^Fiu) = [F'(u)]-1 {F(u*) - F (u) - F'{u){u - u*)). Podle věty 2.1.2 a z definice abstraktní funkce je předchozí rovno [F\U)}-\ í F\U + t(u* - u))(u* - u)dt - F'(u)(u - u*)) (2.11) Jo = [F'iu)}-1 í [F'(u + t(u* - u)) - F'(u)} dt(u - u*). Jo Podle nerovnosti (2.1) pro normu vektoru \\T(u) — T(u*)\\ platí \\T(u)-T(u*)\\ < \\[F'(u)}-1 ]] í \\[F'(u + t(u*-u))-F'(u)]\\dt\\u-u*\\, Jo (2.12) odtud z podmínky (2.7) dostaneme, že předchozí je menší nebo rovno || [F (M)]-1 || / L\\u + tu — tu* — u\\ dt\\u — u*\\ Jo = || [F (M)]-1 || / Lt\\u — u*\\ dt\\u — tt*||, Jo odtud pak vzhledem k ||[F (tí)]-1 || < Co máme \\T(u)-T(u*)\\QQ(T,U*)> 2. Jak bylo uvedeno výše, nedostatky předchozí věty odstraňuje Kantorovičova věta, jejíchž předpoklady nezávisí na u*. Věta 2.2.2 (Kantorovič). Předpokládejme, že operátor F : D(F) cV^U je diferencovatelný na otevřené konvexní množině D(F) a že je zde lipschitzovsky spojitý, tzn. \\F\U)-F\V)\\ \\[F (tío)]_1 ]|| o, /^iifF'Mr^Mii. Označme ť _ l - ( l - 2 / Q 1 / 2 ; r _ 1 + (1 - 2fe)V^ aL ' aL Předpokládejme, že S := {tt|||tt —tto|| < ť} C D (F). Pak Newtonova posloupnost {un} utvořená podle (2.6) je dobře definovaná, leží v S a konverguje k řešení u* E S. Toto řešení je jediné v D(F) n {u\ \\u — u0\\ < ť*}. Navíc, je-li h < \, pak posloupnost konverguje kvadraticky. Kompletní důkaz Kantorovičovy věty lze najít v [1]. Zde je ukázána pouze existence v kouli B(uo,t*) C D (F) a pro přehlednost je užito následujících tří lemat. 29 Lemma 2.2.3. Nechť {vk} je posloupnost v U a nechť tk je posloupnost reálných nezáporných čísel takových, že \\vk+i -vk\\ < ífc+i -tk k = 0,1,2,... (2.16) atk^ť < oo. Pak existuje v* E U takové, že Vk —• v* a \\v* - vk\\ < ť - tk k = 1,2,... (2.17) Posloupnost {tk} se nazývá majoranta posloupnosti {vk}. Důkaz. Zřejmě z (2.16) je tk neklesající posloupnost. Platí \\vk+p -vk\\ = \\vk+p - Vk+p-i + Vk+p-i vk+i + vk+i - vk\\ (2.18) P p — / Jl^fc+i — ffc+i-lH < 2_^(tk+i — tk+i-l) = tk+p — tkí=l í=l Odtud dostáváme, že Vk je cauchyovská, tedy konverguje ke své limitě a (2.17) vyplývá z platnosti (2.18) pro libovolné p. D Nechť pro následující dvě lemata platí předpoklady Kantorovičovy věty. Lemma 2.2.4. Uvažujmeu E Q := {tt|||tt —tt0|| < -^}DD(F), pak [F'(U)]'1 existuje pro všechna u E V a platí \\[F (u)]-1 ]] < , . (2.19) 1 — aL\\u — «oil Zároveň pokud u a T{u) := u — [F'(u)]~1 F(u) náleží do Q, pak linrM)-rM||<ía ^;-r( ^„. (2.20) 21 — aL\\uo — i {u)\\ Důkaz. Zřejmě pro \/u E Q platí 1|F (u) - F (tío)ll < L\\u - t(o|| < a Odtud, vzhledem k větě o poruchách 2.1.3, dostaneme, že [F (u)] l existuje pro V« E V a platí (2.19). Dále uvažujme normu \\T(T(u)) - T(u)\\ = \\T(u) - [F'(T(u))]-l F(T(u)) - T(u)\\, (2.21) 30 to vzhledem k (2.19) je menší nebo rovno než a \\T(T(u) 1 — CuL||tío — T [u) a protože F (u) — F (u) (T (u) — u) = 0, dostáváme \\T(T(u))-T(u)\\ < a \\F(T(u))-F(u)-F'(u)(T(u)-u)\\. 1 — aL\\uo — 1 (u)\\ (2.22) Podobně jako v (2.11) a (2.12) bude platit \\F(w) - F (v) - F'(w- V)\\ < || / [F\tw + (1 - ť)v) - F'(v)](w - v)dt\\ Jo <\\w-v\\ L\\(tw + (1 - ť)v) - v\\dt Jo L u „2 < —\\w — v\\ .- 2 n n Odtud a z (2.22) dostaneme (2.20). D Lemma 2.2.5. Newtonova posloupnost {uk} je dobře definovaná a je majorizovaná posloupností tk+l =tk- { ^]t }~ tk +ß fc = 0,l,... ío = 0. (2.23) aLtk — 1 Navíc {tk} monotone konverguje kť, které je definované v (2.15). Důkaz. Je vidět, že {tk} je Newtonova posloupnost pro polynom {q ^-)t\ — tk + ß s kořeny ť a ť* a počáteční aproximací ío = 0. Pro h < \ jsou ť a ť* různé a tedy podle Fourierových podmínek, uvedených například v [6][ strana 35] konverguje {tk} monotone a Q řád konvergence je větší nebo roven dvěma. Poznamenejme, že Fourierovy podmínky lze odvodit nezávisle na předchozím a že v případě h = \ bude {tk} konvergovat také, ale rychlost konvergence bude pomalejší. Dále budeme pokračovat indukcí. Pro k = 1, podobně jako v (2.21), dostáváme \U\ — UQ\ \[F'{uQ)]-l F{uQ) a to je podle předpokladů menší nebo rovno ß, které se z (2.23) rovná t\. Celkově tedy ||tti — tto|| < t\ — to < ť a odtud u\ E S. Předpokládejme, že U\.. .Uk existuje, náleží do S a ||ttj — ttj_i|| < U — íj_i 31 pro i = 1, 2 ... k. Zřejmě S C Q & tedy podle věty 2.2.4 pro k + 1 platí n n iiTVTV ^ TV ^u ^ 1 oiL\\uk-i — T(uk-i) IK+i - Uk\\ = \\T{T{uk-i)) - T(ufc_i)|| <2 1 - aL\\u0 - T(uk-i)\\ < 1 aL{tk - tk_xf = 1 aU\ - tk + ß - 2 1 - «Life 2 1 - aLtk k+l k ' Vzhledem k větě 2.2.5 je {tk} majorantou posloupnosti {«&}, jejíž limita je u* e S D Důkaz Kantorovičovy věty. Důkaz. Lemmata 2.2.3 a 2.2.5 ukazují, že existuje u* E S takové, že u^ —• u*. Ukážeme, že je i řešením (2.3). Ze vztahu F{uk) = F'{uk)uk+i - F'(uk)uk, dostáváme \\F(uk)\\ = \\F'(uk)(uk+1 - uk)\\ < [\\F'(uo)\\ + | | ^ M - F'(uk)\\]\\uk - uk+1\ <[\\F'(u0)\\+Lť}\\uk-uk+1\\. Vzhledem k tomu, že je posloupnost {un} cauchyovská a operátor F (u0) ohraničený dostáváme, že F (u*) = 0. Z rychlosti konvergence {tk} a z (2.17) plyne, že {un} konverguje alespoň kvadraticky pro h < \. D Závěrem shrnujeme, že předchozí věta tvrdí, že za předpokladů kladených na operátor F(u) bude Newtonova metoda konvergovat jednoznačně v kouli B(u0,ť) a u* je jediný kořen F v kouli B(u0,ť*). 2.3 Aplikace Newtonovy metody Newtonova metoda nebo její modifikace nacházejí uplatnění při řešení velké škály problémů, ve kterých je zapotřebí najít kořen operátorových rovnic. Jak je vidět na následujícím obecném postupu, v prostoru Era lze průběh výpočtu jednotlivých iterací do značné míry zjednodušit. Uvažujme Newtonovu metodu pro zobrazení F z motivační části, tedy Xn+i = xn- [F\xn)]-l F(xn). (2.24) 32 Předpokládáme, že [F (xn)]~l existuje pro xn. Zároveň vzhledem k tomu, že F (xn) lze v Era vyjádřit jako matici, můžeme pro každý krok převést rovnici (2.24) na systém lineárních rovnic F'(xn)8n+i = -F(xn), kde ón+í = xn+í - xn. (2.25) Vektor 5n+\ se nazývá Newtonův krok. Analogii tohoto postupu nyní užijeme na následujícím příkladě řešení nelineárních integrálních rovnic. Nelineární integrální rovnice Nechť u G U = C[0,1] a k G C([0,1] x [0.1] x E) je funkce, spojitá v poslední proměnné. Uvažujme integrálni rovnici u(t) = / k(t,s,u(s))ds (2.26) Jo a definujme operátor -i F(u(t)) := u(t) - k(t,s,u(s))ds, (2.27) Jo rovnici (2.26) lze přepsat ve tvaru F(u(t)) = 0. Abychom mohli užít Newtonovy metody, je zapotřebí určit F : U x U —• U. Proto F'(u,v)(t) = lim -[F(u + hv)(t) - F (u) (ť)] h^o n, 1 f1 = lim — [u{t) — hv(t) — u{t) — I [k(t,s,u(s) + hv(s)) — k(t, s,u(s))]ds] h^o h J0 ŕk(t,s,u(s) + hv(s))-k(t,s,u(s)) = v (t — lim / —— v{s)\ds h^oJ0 hv(s) = v{t) - ľ dk{t >6 >u{s) K(s)ds. Jo ou Odtud, podobě jako v (2.25) dostaneme F (un)ôn+1 =-F(un), ôn+1 = un+1 - un, 33 tedy - f1 dkCt, s, un(s)) f1 • £(Era ,Era ) je lipchitzovsky spojitá. Při volbě počáteční aproximace jsme tedy omezeni na okolí \\x — x*\\ < 8, které může být obtížné určit. Na následujícím příkladě je vidět, co se stane, zvolíme li počáteční aproximaci libovolně. Příklad. Uvažujme funkci f(x) := x1 ^3 a volme počáteční aproximaci XQ = 10. Pak Newtonův krok má délku l0 i/3 5Í = xx - x0 = 10 - , = -20. (3.3) glO Zřejmě se další iterace nepoměrně vzdálí od kořene, přestože směr kroku je správný. Uvažme, že místo kroku délky s určeného v (3.3) užijeme krok stejného směru, ale potřebně kratší, aby se přiblížil ke kořenu F. Metody, které tímto způsobem upravují krok jsou tzv. line search metody, jelikož hledáme iteraci na přímce [xn, xn + s\. Pro další účely definujme Newtonův směr d předpisem d = -F'(xn)F(xn). (3.4) Konkrétní metodou je například tzv. Armijovo pravidlo, při kterém se v prvním kroku určí Newtonův směr d a poté nejmenší přirozené číslo m = 0,1..., takové, že platí \\F(xn + 2-m d)\\ < (l-a2-m )\\F(xn)\\. (3.5) Následně za Newtonův krok zvolíme vektor s = 2~m d. Konstanta a je parametrizací podmínky (3.5) a standardně se volí 10~4 . Ukončení iterace. Na základě věty 2.2.1 o lokální konvergenci, lze odhadnout chybu iterace výrazem (2.9). Přesnost takového odhadu je závislá na volbě poloměru 8, a tedy klade nároky na přibližnou znalost hodnoty kořene. Výhodnější způsob ukončování iterace, založený na heuristických metodách, je ukončit iteraci při splnění podmínky 11^)11 ^ X r l l F ^ H + X a , (3-6) kde Xr je parametr relativní chyby a \a je parametr chyby absolutní. Uvážímeli případ, kdy je počáteční iterace blízko kořene x*, pak volbou \a = 0 je téměř nemožné splnit podmínku 3.6. Proto je vhodné nevynechávat absolutní chybu. 37 3.2 Způsoby hledání Newtonova kroku Newtonův krok lze určit různými způsoby, nejjednodušší pro implementaci je přímo pomocí Jacobiho matice. Tento výpočet, i přes výhody stability, je náročný na pamětové prostředky a výkon počítače, kdy při každé iteraci vyhodnocujeme Jacobiho matici, případně ji aproximujeme pomocí diferencí. Následně je nutné vyřešit systém lineárních rovnic k určení Newtonova směru. Pro složitější problémy můžeme použít méně náročné algoritmy. Modifikovaná Newtonova metoda. Jedním ze způsobů jak určit Newtonův krok, je určit Jacobiho matici v počáteční iteraci xo a užít tento výsledek i pro další iterace. Za předpokladu, že počáteční aproximace je dostatečně blízko kořenu x*, bude Q řád této metody roven jedné. Broydens method Tato metoda vedle iterací posloupnosti {xn} vytváří i iteraci Jacobiho matic Bn. Její tvar je Xn+l Xn AnJDn f \XnJ, kde Xn je úpravou délky kroku pro směr Dále se pak určí iterace Jacobiho matice _ (y - Bns)sT -Dra+l — -Dra 7 , ST 'S kde y = F(xn+i) - F(xn) a s = xn+í - xn = \ndn. Jestliže existuje ôB > 0 takové, že \\B0 — F (x*) \\ < 5B a zároveň jsou splněny předpoklady lokální konvergence, pak je posloupnost {xn} dobře definovaná a platí hm — r— = U. n^oo \\X„ — X*\\ Newtonova-Krylova metoda Tato metoda patří do skupiny tzv. neexaktních metod, které výpočet Jacobiho matice obcházejí a za Newtonův krok užijí vektor splňující podmínku \\F'(xn)s + F(xn)\\ ||F(:z)|| + \a —• \ Pokud \\F{xn)\\ >x, pak 1. Urči F (x). 2. Vyřeš F (x)d = —F(x) pomocí Gausovy eliminace. 3. Najdi Newtonův krok užitím Armijova pravidla. 4. Urči následující iteraci. Konec pokud. Části výpočtu Jacobiho matice F (x) je určena pomocí diferencí. Toto řešení je vhodné i pro problémy, kde není explicitně určena funkce /. Gausova eliminace pro nalezení Newtonova směru je řešena užitím rozkladu Jacobiho matice J na horní a dolní trojúhelníkovou matici L a U a řešením systému Lx = —F(x) Ud = x, kde LU = J. (3.9) Výhodou tohoto postupu je ušetření počtu operací, kdy k rozkladu je zapotřebí ^- + 0(N3 ) operací a k vyřešení rovnic N2 + 0(N2 ). Ne vždy je rozklad na trojúhelníkové matice možný, pak lze matici J rozložit na J = PLIJ, kde P je tzv. pertrubační matice. Rozklad je v algoritmu řešen pomocí příkazu [L, U] = lu(J), implementovaného v Matlabu, kdy případná pertrubační matice je obsažena v matici L. 39 Více o rozkladech matic lze najít v [6] [strany 77-93]. Zdrojový kód funkce Newton function [ r e s e n i . h i s t ] = n e w t o n ( x , f , c h y b a , p a r ) ; 7. 7o Určí kořen funkce F s počáteční aproximací x. 7. 7o Jacobiho matice J je určována pomocí diferencí a 7o systém nelineárních rovnic pro určení Newtonova 7o směru je řešen rozkladem J na L,U matice. 7o Při určování Newtonova kroku je užito Line search 7o metody - Armijo rule. 7. 7oVstupní parametry 7o ř e š e n í . . . aproximace kořene 7o hist historie iterací 7. 70Výstupní parametry 7. POVINNÉ 7o x...Vektor počáteční aproximace 7o f . . . Funkce 7. NEPOVINE 7o chyba. . .Vektor tolerancí chyby 7o chyba(l) ... absolutní chyba-implicitně=l .d-6 7o chyba(2) .. .relativní chyba-implicitne=l .d-6 7o par. . . Vektor parametrů 7o par(1) .. .maximální počet iterací implicitně=10 7o par(2) .. .parametr alfa při Armijo rule 7o implicitně=l .d-4 7o par(3) .. .Maximální počet iterací Armijo rule. 7o implicitně=10 7, Inicializace °/0 if nargin==2 chyba=[l.d-6,l.d-6] ; par=[10,l.d-4,10]; end; if nargin==3 par=[10,l.d-4,10]; end; n=length(x); iterace=0; maxiter=par(l); h=eye(n)*l.d-7; 40 if nargout==2 hist=[] ; end; if size(x,l)==l x=x.'; end; 7o Kontrola vstupních parametrů/o if maxiter <=0 error('Chyba end; if length(chyba)~=2 error('Chyba end; if length(par)~=3 error('Chyba end; /oUrčení chyby °/0 fx=feval(f,x); tol=chyba(2)*norm(fx) + chyba(l); if nargout==2 hist=[hist';[x]']'; end; '/oUrčení iterací'/o while norm(fx) > tol & iterace < maxiter °/o Inicializace °/0 fx=feval(f,x) ; iterace=iterace+l; 7oVýpočet Jacobiho matice pomocí diferencí/o J=zeros(n,n); for i=l:n; xl=x; xl=x+h(:,i); fl=feval(f,xl); J(:)i)=(fl-fx)*h(i,i)"-l; end; 7oNalezení rozkladu Jacobiho matice/o Počet iterací musí být větší jak 0.') Vektor chyb, musi obsahovat dve hodnoty.') Vektor parametrů musí mít tři složky.') 41 [L,U]=lu(J); 7oUrčení Newtonova směru °/0 y = - LAfx; d = U\y; °/0Armijo r u l e °/0 m=0; while n o r m ( f e v a l ( f , x + d.*2~-m))>=norm((l-par(2)*2~-m)*fx) & ms ) = g(3 2 + 2 x 3 - y(x >s )y(x > s ))> kde l < x < 3 , y(l,s) = 17, y'(x,s) = s. (3.11) 42 Na obrázku 3.1 je zobrazena funkce chyby F(s) = y(3, s) — 14 a iterace algoritmu newton, určené s počáteční aproximací So = 10. Posloupnost iterací a Newtonových kroků je vidět na následující tabulce. n Sn Sn 0 10.0000 — 1 -18.7795 -28.7795 2 -13.5726 5.2069223 3 -12.8511 0.7214852 4 -12.8413 0.9758908e - 2 5 -12.8413 0.1709421e- 5 Na obrázku 3.2 jsou vidět řešení rovnice (3.11), pro příslušná s. Přibližným řešením úlohy (3.10) je řešení rovnice (3.11) pro hodnotu parametru s = - 12.8413. Funkce chyby Teěny Newtonovy jnetody s =-12.8413 10 15 20 25 Obrázek 3.1: 43 1 1.2 1.4 1.6 2.2 2.4 2.B 2.8 Obrázek 3.2: 44 Literatura [1] Ioannis K. Argyros, A Newton Kantorovich theorem for equations involving m-Fréchet differentiable operators and applications in radiative transfer, Journal of Computational and Applied Mathematics Volume 131, Issues 1-2 , 1 June 2001, Pages 149-159 Kendall E. Aktinson, An introduction to numerical analysis, John Wiley & Sons, New York 1978 Kendall E. Aktinson, Weimin Han Theoretical numerical analysis, Springer-Verlag, New York 2001 Richard L.Burden, J.Douglas Faires Numerial analysis (third edition). Prindle, Weber & Schmidt, Boston, 1984 Collatz Lothar Funkcionální analýza a numerická matematika, SNTL, Praha 1970 Ivana Horová, Numerické metody, Skriptum, MU, Brno 1999 C. T. Kelley, Solving Nonlinear Equations with Newton s Method, Siam 2003 A. N. Kolmogorov, S. V Formin, Základy teorie funkcí a funkcionální analýzy, SNTL, Praha 1975 Karel Najzar, Jan Zítko Numerické metody funkcionální analýzy I, Skriptum,Uk, Praha 1984 Karel Najzar, Jan Zítko Numerické metody funkcionální analýzy II, Skriptum,Uk, Praha 1984 J.M.Ortega The Newton-Kantorovich Theorem, The American Mathematical Monthly, Vol. 75,No 6. ( Jun.-Jul.,1968),pp.658-660 45 [12] J.M.Ortega, W. C. Rheinboldt Iterative solution of nonlinear equations in several variables. Werner Rheinboldt University of Maryland, 1970 [13] J.Stoer, R.Bulirsch Introduction to Numerical Analysis. SpringerVerlag, New York Heidelberg, Berlin, 1970 46