Uvažujme následující problém. Máme funkci f a chceme najít bod, ve kterém je hodnota f rovna dané hodnotě. Ukážeme dvě metody. Metoda bisekce je obecnější, hledá body, které splňují určitou vlastnost (a ta nemusí být nutně vázána na nějakou funkci, ale s funkcí je to ta nejpřirozenější situace). Na druhou stranu Newtonova metoda funguje jen na speciální případ "problému hodnoty", jmenovitě hledá bod, kde je daná funkce nulová.
Tato metoda se používá v mnoha situacích k nalezení čísla s určitou
vlastností. Používá vlastně dvě posloupnosti, ne jen jednu, a hned uvidíme
proč. Hlavní idea bisekce je následující: Nějak najdeme (třeba uhádnutím) dvě
čísla
Protože se v každém kroku členy vzniklých dvou posloupností přiblíží na polovinu předchozí vzdálenosti, tak nakonec vymezí hledané číslo s libovolnou přesností.
Teď tuto myšlenku aplikujeme na hledání druhé odmocniny daného kladného čísla
A.
Začneme tím, že uhádneme dvě kladná čísla
Teď definujeme obecný rekurzivní krok. Je-li dán pár
V další části ukážeme, jak se metoda bisekce používá k hledání kořenů funkcí. Metoda bisekce je obecně dost pomalá při získávání nutné přesnosti (v každém kroku se možná chyba pouze zmenší na polovinu), ale je značně spolehlivá; stačí jen najít nějaké vymezení hledaného čísla k nastartování procedury a metoda funguje. Všimněte si, že metoda pro nalezení druhé odmocniny vysvětlená níže zmenšuje chybu mnohem rychleji.
Poslední poznámka se týká volby středu. Jsou modifikace bisekčního algoritmu, které fungují rychleji díky tomu, že se nevolí střed, ale nějaký bod, od kterého se čeká lepší fungování. Jsou-li dány xn a yn, tak v určitém kroku testujeme, jak se blíží ke splnění dané podmínky, v našem příkladě jak se jejich druhá mocnina blíží k A. Je přirozené očekávat, že pokud by bylo řekněme yn2 mnohem blíž k A než xn2, pak skutečná druhá odmocnina z A bude blíž k yn než k xn. Takže místo zkoušení středu mn bychom v dalším kroku zkoušeli číslo poněkud blíže k yn. Přesná volba se obvykle dělá proporčně, podle toho, jak relativně blízko jsou yn a xn k hledané vlastnosti.
Jednou z častých otázek v analýze je hledání kořene dané funkce. Přesně
řečeno, je dán vzorec pro
Jedna možnost je aplikovat již probranou metodu bisekce. Fungovalo by to následovně:
Předpokládejme, že máme funkci
Definujeme posloupnosti
Jsou-li dány xn a yn
takové, že
Jestliže
Jestliže
Jestliže
Všimněte si, že jestliže má f rozdílné znaménko v
xn a yn a jestliže
Jak už jsme poznamenali, tato metoda je spolehlivá, ale pomalá. Jedním z nejpopulárnějších nástrojů k hledání kořene je Newtonova metoda. Předokládá, že daná funkce má derivaci.
Newtonova metoda.
Vybereme nějakou počáteční hodnotu x0. Pak definujeme
rekurzivně
(1)
Jestliže tato posloupnost konverguje, pak její limita r splňuje
Jak jsme dostali vzorec pro Newtonovu metodu? Je to vlastně docela snadné pomocí elementární geometrie, pokud vás to zajímá, klikněte sem. Najdete tam také jednoduchý příklad, u kterého tato metoda selže, což se může snadno stát. To je hlavní nevýhoda Newtonovy metody. Na druhou stranu, pokud funguje, pak velice rychle dosáhne žádané přesnosti. V další části ukážeme jednu užitečnou aplikaci.
Máte kladné reálné číslo A. Jak najdete jeho druhou odmocninu? Pokud zrovna nemáte ohromné štěstí, tak odpovědí asi nebude celé číslo. Součástí otázky je tedy další důležitá informace: Jak přesně se chce odpověď.
Poznamenejme, že v matematice lze odpovědět zcela přesně. Nakreslí se srandovní šibenice nad A a řekne se: Tady je ta odmocnina. A to je také správná odpověď. Nicméně v reálném světě (a v matematice, když se začne aplikovat) je potřeba znát odpověď v desetinném tvaru. Účel, pro který tuto odmocninu hledáme, také rozhodne, jaká je žádaná přesnost. Pokud si tu odmocninu chcete zaznačit na reálné ose, nemá smysl žádat o víc než dvě desetinná místa, hrot vaší tužky je stejně tlustší. Na druhou stranu je možné, že chcete tuto odmocninu použít ve složitějším výpočtu (například v inženýrství), kde je třeba pěti desetinných míst. Možná jste dokonce výrobce kalkulaček, pak potřebujete znát odpověď na řekněme 13 míst.
Takže zpátky k otázce: jak najdeme druhou odmocninu z A? Existuje
algoritmus pro "tužku a papír" k hledání odmocnin, který jste se asi naučili
na střední škole (a zase už zapomněli), ten ale není zrovna nejvhodnější pro
počítače. Zkusíme na to použít Newtonovu
metodu, a to trikem: budeme hledat kořen funkce
Definujeme rekurzivně
(0)
(1)
Dá se dokázat, že tato posloupnost konverguje a její limita je přesně druhá odmocnina z A (podobné posloupnosti jsou i pro další odmocniny). Tento algoritmus se snadno naprogramuje do počítače a najde odmocninu dost rychle.
Například moje kalkulačka říká, že odmocnina ze dvou je asi 1.4142136.
Zkusíme naši posloupnost:
Jak vidíte, funguje to docela dobře. Dá se dokázat, že každá iterace této
procedury zhruba zdvojnásobí počet desetinných míst, kteé jsou správně.