Newtonova metoda
Newtonova metoda
Teoretické minimum
Uvažujme rovnici @bf(x)=0,@b kde @if@i je nějaká funkce, o níž budeme předpokládat, že je spojitá a má potřebný počet derivací. Naším cílem je určit řešení (kořen) této rovnice, tzv. nulový bod funkce. Některé rovnice (např. lineární,
kvadratické, exponenciální) umíme řešit analyticky, ale už například pro nalezení kořenů polynomu řádu vyššího než
čtyři neexistuje obecná formule. Naprostou většinu rovnic musíme řešit přibližně některou numerickou metodou.
Myšlenka Newtonovy metody je jednoduchá. Na počátku musíme nalézt vhodný interval, ve kterém bude ležet právě jeden kořen @i\alpha@i. Takový interval @i[a,b]@i nazýváme separačním intervalem. Je to vlastně takový náš první odhad kořene @i\alpha@i. Teď
už tedy víme, že @ia<\alpha<b.@i Pokud tento interval bude splňovat předpoklady Newtonovy metody, které si uvedeme za chvíli, vybereme vhodný z bodů @ia,b@i, označme ho @ix_0@i. Sestrojíme tečnu ke grafu funkce @if@i v bodě @i\big(x_0,f(x_0)\big)@i.
Průsečík této tečny s osou @ix@i leží uvnitř separačního intervalu, nazvěme ho @ix_1.@i Když opět sestrojíme tečnu ke grafu funkce @if@i v bodě @i\big(x_1,f(x_1)\big)@i a najdeme její průsečík s osou @ix@i, obdržíme další bod @ix_2@i. Když budeme takto
postupovat dále, budeme se s průsečíky @ix_n@i tečen a osy @ix@i stále více přibližovat ke kořeni @i\alpha@i. Na obrázku níže můžeme celý postup vidět až do odhadu @ix_2@i.
Newtonova metoda je tedy ideově poměrně jasná a je zřejmé, proč se jí také říká metoda tečen. Zbývají nám dvě otázky.
1. Jak poznám, že vybraný interval je skutečně separační?
2. Jaké jsou předpoklady pro použití Newtonovy metody a jak numericky spočítat odhady kořene @ix_n,\,n=1,2,\ldots@i?
Začněme s první otázkou. Uvedeme si předpoklady, za jejichž platnosti je daný interval separační.
Jestliže jsou pro funkci @if@i a interval @i[\,a,b\,]@i splněny následující podmínky:
- @if@i je spojitá na @i[\,a,b\,]@i,
- @if(a)\cdot f(b)<0@i,
- @if'(x)\neq0@i pro všechna @ix\in(a,b)@i,
potom je interval @i[\,a,b\,]@i separačním intervalem rovnice @if(x)=0@i.
Užitečná poznámka: První dvě podmínky nám zaručí, že v intervalu @i[\,a,b\,]@i se skutečně nachází kořen, ta třetí pak spolu s nimi, že ten kořen je jediný. Funkce nemění monotonii na intervalu @i[\,a,b\,]@i, buď roste nebo klesá.
Nyní už zbývá zformulovat podmínky pro použití Newtonovy metody:
Předpokládejme, že platí předchozí body 1.-3. Navíc předpokládejme, že
@if''(x)\neq0@i pro všechna @i x\in[\,a,b\,].@i
Pak můžeme
- zvolit nultou aproximaci kořene @i\alpha@i jako takový bod @ix_0\in\{a,b\}@i, že @bf(x_0)\cdot f''(x_0)>0,@b
- a určit @in@i-tou aproximaci @ix_n@i kořene @i\alpha@i z rekurentního vzorce
@bx_n=x_{n-1}-\frac{f(x_{n-1})}{f'(x_{n-1})}.@b
Takto získaná posloupnost @i\{x_n\}@i postupných aproximací kořene @i\alpha@i konverguje ke kořeni @i\alpha@i pro @in\to\infty.@i
Užitečná poznámka: Za nultou aproximaci kořene @ix_0@i lze volit jakýkoliv bod uvnitř separačního intervalu splňující podmínku @if(x_0)\cdot f''(x_0)>0@i. Stejně tak separační interval může mít různou šířku. Záleží na tom, jak dobře jsme pro zvolený interval schopni ověřit, že se skutečně jedná o separační interval a předpoklady Newtonovy metody. Samozřejmě, čím bude separační interval užší, tím bližší se dá předpokládat první aproximace skutečné hodnotě kořene @i\alpha@i a dá se také předpokládat i rychlejší konvergence algoritmu.
Související
Derivace funkce, tečna ke grafu funkce.
Řešené příklady
1. Určete počet kořenů rovnice @ix^3=x^2-2x+1@i. Najděte separační intervaly pro všechny kořeny a pomocí Newtonovy metody zvolte nultou aproximaci těchto kořenů a vypočtěte jejich první aproximaci.
Pro určení počtu kořenů v úlohách na Newtonovu metodu je nejlepší zvolit grafické řešení. Pak hledání kořenů této rovnice odpovídá hledání @ix@i-ových souřadnic průsečíků grafů funkcí @ig_1(x)=x^3@i a @ig_2(x)=x^2-2x+1.@i Na následujícím obrázku vidíme grafy obou funkcí:
Je vidět, že daná rovnice má jediný kořen @i\alpha@i. Z obrázku je zřejmé, že @i\alpha\in[0,1].@i Pokusme se dokázat, že interval @i[0,1]@i je separačním intervalem rovnice @ix^3-x^2+2x-1=0@i. Označme @if(x)=x^3-x^2+2x-1@i.
- Funkce @if(x)=x^3-x^2+2x-1@i je zřejmě spojitá na intervalu @i[0,1].@i
- @if(0)\cdot f(1)=-1\cdot1=-1<0.@i Kořen @i\alpha@i tedy skutečně leží v tomto intervalu.
- Musíme ověřit, že první derivace funkce @if@i je na intervalu @i(0,1)@i dobře definovaná a nenulová. První derivace @if'(x)=3x^2-2x+2 @i je definovaná pro všechna @ix\in\mathbb R@i. Jedná se o kvadratickou funkci, tudíž jsme schopni spočítat její
nulové body. Neboť diskriminant rovnice @i3x^2-2x+2=0@i je záporný, platí @if'(x)\neq0@i dokonce pro všechna reálná @ix@i.
Interval @i[0,1]@i je tedy separačním. Nyní je třeba ověřit poslední předpoklad Newtonovy metody. Druhá derivace funkce @if@i je @if''(x)=6x-2@i pro všechna @ix\in\mathbb R@i. Je třeba ověřit, že tato derivace je nenulová na separačním intervalu. Vzhledem k tomu, že druhá derivace je lineární funkce, můžeme přesně určit její nulové body:
@bf''(x)=0\quad \Longleftrightarrow\quad x=\frac{1}{3}\in[0,1].@b
Na intervalu @i[0,1]@i tedy není splněn poslední předpoklad Newtonovy metody. Nicméně, separační interval lze zúžit na interval neobsahující bod @i\frac{1}{3}@i. Pro kořen @i\alpha@i platí jedna z následujících nerovností: @i0<\alpha<\frac{1}{3}@i nebo @i\frac{1}{3}<\alpha<1.@i Zkusme zvolit za nový levý krajní bod separačního intervalu bod @i\frac{1}{2}@i. Protože platí @bf\left(\frac{1}{2}\right)\cdot f(1)=-\frac{1}{8}\cdot1<0,@b je interval @i\Big[\frac{1}{2},1\Big]@i separačním intervalem dané rovnice. Je zřejmé, že @if''(x)=6x-2>0@i pro @ix\in\Big[\frac{1}{2},1\Big]@i, tedy nový separační interval splňuje poslední předpoklad Newtonovy metody. Protože na intervalu @i\Big[\frac{1}{2},1\Big]@i je druhá derivace kladná, zvolíme za nultou aproximace @ix_0=1@i, neboť @if(1)=1>0@i, tj. @if(x_0)\cdot f''(x_0)>0.@i První aproximace kořene @i\alpha@i je potom
@bx_1=x_0-\frac{f(x_0)}{f'(x_0)}=1-\frac{1}{3}=\frac{2}{3}.@b
Užitečná poznámka: Základní kontrolou toho, že jsme Newtonovu metodu použili správně, je fakt, že každá @in@i-tá aproximace leží uvnitř separačního intervalu. Pokud tomu tak není, je jisté, že je někde chyba. Je to bohužel pouze nutná, nikoliv postačující podmínka.
2. Rozhodněte, kolik řešení má rovnice @i\dfrac{1}{x^3}-\sin x=0.@i Dokažte, že interval @i\Big[\frac{\pi}{6},\frac{\pi}{2}\Big]@i je separačním intervalem pro nejmenší kladný kořen této rovnice a že jsou na něm splněny předpoklady Newtonovy metody. Zvolte nultou aproximaci tohoto kořene a nalezněte jeho první aproximaci.
Počet kořenů opět určíme graficky. Rovnice @b\frac{1}{x^3}-\sin x=0@b je ekvivalentní s rovnicí
@b\frac{1}{x^3}=\sin x.@b
Hledané kořeny @ix@i jsou @ix@i-ové souřadnice průsečíků grafů funkcí @i\,g_1(x)=\dfrac{1}{x^3}\,@i a @i\,g_2(x)=\sin x@i. Na následujícím obrázku jsou zakresleny čtyři průsečíky:
Z periodicity funkce sinus plyne, že daná rovnice má nekonečně mnoho kořenů. Nyní je třeba ověřit, že interval @i\Big[\frac{\pi}{6},\frac{\pi}{2}\Big]@i je separační:
- Funkce @if(x)=\dfrac{1}{x^3}-\sin x@i je zřejmě spojitá na intervalu @i[\frac{\pi}{6},\frac{\pi}{2}]@i.
- @if(\frac{\pi}{6})\cdot f(\frac{\pi}{2})=\left(\frac{216}{\pi^3}-\frac{1}{2}\right)\left(\frac{8}{\pi^3}-1\right)<0.@i Čternář snadno nahlédne, že první činitel je kladný a druhý záporný. Tedy druhá podmínka je splněna.
- @if'(x)=-\dfrac{3}{x^4}-\cos x,\ x\neq0@i. Vzhledem k tomu, že funkce kosinus je na intervalu @i\Big(0,\frac \pi 2\Big)@i kladná a funkce @i\frac{3}{x^4}@i také, platí @if'(x)<0@i pro všechna @ix\in\Big(\frac{\pi}{6},\frac{\pi}{2}\Big)@i.
Interval @i\Big[\frac{\pi}{6},\frac{\pi}{2}\Big]@i je tedy separačním a nám zbývá už jen ověřit poslední předpoklad Newtonovy metody:
@bf''(x)=\frac{12}{x^5}+\sin x,\ x\neq 0.@b
Oba sčítance jsou na separačním intervalu kladné, tedy @if''(x)>0@i pro všechna @ix\in\Big[\frac{\pi}{6},\frac{\pi}{2}\Big]@i, čímž jsme ukázali, že je poslední podmínka Newtonovy metody splněna. Nyní můžeme určit nultou aproximaci
kořene. Vzhledem k tomu, že je druhá derivace na intervalu @i\Big[\frac{\pi}{6},\frac{\pi}{2}\Big]@i kladná, volíme za @ix_0@i ten z krajních bodů separačního intervalu, ve kterém je funkční hodnota funkce @if@i kladná, neboť pak je splněna podmínka
@if(x_0)\cdot f''(x_0)>0.@i Tímto bodem je bod @ix_0=\frac{\pi}{6}.@i První aproximace nejmenšího kladného kořene je
@bx_1=\frac{\pi}{6}-\frac{\frac{216}{\pi^3}-\frac{1}{2}}{-\frac{3\,888}{\pi^4}-\frac{\sqrt{3}}{2}}\:\bigl(\doteq 0,\!68216\bigr)@b
Neřešené příklady
- Graficky zjistěte počet reálných kořenů rovnice @bx^3-x^2+1=0.@b Pro nejmenší kořen této rovnice stanovte separační interval délky @i1@i, ověřte na něm předpoklady Newtonovy metody. Zvolte nultou aproximaci tohoto kořene a vypočtěte jeho první aproximaci.
- Graficky zjistěte počet reálných kořenů rovnice @b{\rm e}^{-x}-x^2+1=0.@b Pro největší kořen této rovnice stanovte separační interval délky @i1@i, ověřte na něm předpoklady Newtonovy metody. Zvolte nultou aproximaci tohoto kořene a vypočtěte jeho první aproximaci.
- Uvažujme rovnici @b\ln|x|+\frac{1}{2}x=1.@b Graficky zjistěte počet reálných kořenů této rovnice. Určete separační intervaly délky jedna všech kořenů. Pro největší kořen ověřte předpoklady Newtonovy metody a nalezněte nultou a první aproximaci tohoto kořene.
