6.13 Newtonova metoda

K numerickému řešení rovnic typu \(f(x) = 0\) existuje mnoho metod. My zatím známe jen metodu půlení intervalu (viz větu č. 5.41). V této kapitole si ukážeme Newtonovu metodu ( Sir Isaac Newton anglický fyzik a matematik, 1642 – 1727). Newtonův přístup podrobně prozkoumáme na následujícím příkladu.

Zamyslete se, jak tento problém vyřešit, máme-li k dispozici kalkulátor umožňující pouze sčítat, odčítat, násobit a dělit čísla. Tedy operace, které může provádět stroj i člověk (s pomocí papíru). Tato otázka může vyvstat v praxi: máme-li zjistit jak velký má být poloměr kulového tankeru o daném objemu \(V\), dostáváme \(r = \sqrt[3]{\frac{3}{4\pi} V}\). Pro krychli dostaneme délku hrany rovnou \(a = \sqrt[3]{V}\). Vedle toho třetí odmocnina je jistě sama o sobě zajímavá funkce, jejíž funkční hodnotu je občas potřeba umět vyhodnotit.

Buď \(c>0\). Označme hledanou třetí odmocninu symbolem \(x\), tj. \(x = \sqrt[3]{c}\) (toto je ale jen symbolický zápis, jakou hodnotu \(x\) pro zadané \(c\) má?). Ekvivalentně to znamená řešit rovnici \(x^3 = c\) s neznámou \(c\). Označíme-li \(f(x) \ceq x^3 - c\), je námi hledané číslo \(x\) řešením rovnice \begin{equation*} f(x) = 0.\end{equation*} Tuto úlohu bychom se mohli pokusit řešit nám již známou metodou půlení intervalu (jaké dva počáteční body byste zvolili?). Nyní si však ukážeme další způsob, tzv. Newtonovu metodu.

Myšlenka Newtonovy metody spočívá v konstrukci posloupnosti \((x_n)_{n=1}^\infty\) aproximující řešení rovnice \(f(x) = 0\). Konstrukce posloupnosti je následující:

1. Je dáno \(x_n\).
2. Sestroj tečnu funkce \(f\) v bodě \(x_n\): \(\displaystyle\color{red} y = f(x_n) + f'(x_n) \cdot (x-x_n)\).
3. Průsečík této tečny s osou \(x\) nechť je další člen posloupnosti, tj. \(\displaystyle x_{n+1} \ceq x_n - \frac{f(x_n)}{f'(x_n)}\).
4. Opakuj s \(x_{n+1}\) místo \(x_{n}\).

Obrázek 6.24: Dvě iterace Newtonovy metody.

Z předchozího obrázku se může zdát, že vše je jasné. Ihned se však nabízí následující otázky:

• Jak zvolit první člen posloupnosti? Závisí výsledek metody na této volbě?
• Má rovnice \(f(x) = 0\) vůbec řešení?
• Konverguje takto zkonstruovaná posloupnost \((x_n)_{n=1}^\infty\)?
• Co když \(f'(x_n) = 0\) pro nějaké \(n\in\mathbb{N}\)?

Odpovědí na tyto otázky se v obecném případě nebudeme zabývat. Vraťme se k našemu konkrétnímu případu s třetí odmocninou, kde uvidíme jak na některé z nich odpovědět.

Shrňme si dosavadní výsledky. Je dáno \(c>0\) a funkce \(f(x) = x^3 - c\). Newtonova metoda nám dává rekurentní vztah \begin{equation*} x_{n+1} \ceq x_n - \frac{f(x_n)}{f'(x_n)} = x_n - \frac{x_n^3 - c}{3x_n^2} = \frac{2}{3} x_n +\frac{c}{3x_n^2}.\end{equation*} V našem případě si lze snadno všimnout, že:

• Funkce \(f\) je prostá, \(f\big((0,+\infty)\big) = (-c,+\infty)\) a tudíž existuje právě jedno kladné řešení rovnice \(f(x) = 0\). (Tj. vyšetřili jsme průběh funkce \(f\) a zjistili jsme, že rovnice má právě jedno řešení.)
• Konverguje-li posloupnost \((x_n)_{n=1}^\infty\) ke konečné kladné limitě \(a\), tedy platí \(a = \lim_{n\to\infty} x_{n}\) a současně \(a = \lim_{n\to\infty} x_{n+1} = \lim_{n\to\infty} \left( \frac{2}{3} x_n + \frac{c}{3x_n^2} \right) = \frac{2}{3} a + \frac{c}{3a^2}\). Tudíž \(a\) je hledané řešení, \(a^3 = c\), nebo-li \(f(a) = 0\).

Nyní si tedy zbývá rozmyslet, jestli naše posloupnost \((x_n)_{n=1}^\infty\) skutečně konverguje.

Nyní víme, že posloupnost konverguje nezávisle na volbě první aproximace. To je dobré, ale k praktickému použití nedostatečné. Kdy máme iteraci zastavit? Je potřeba odhadnout chybu mezi členy posloupnosti a skutečnou (neznámou) hodnotou hledané třetí odmocniny.

Shrňme si vlastnosti Newtonovy metody aplikované na problém hledání třetí odmocniny. Posloupnost \((x_n)_{n=1}^\infty\) zadaná rekurentně vztahem \begin{equation*} x_{n+1} = \frac{2}{3} x_n + \frac{c}{3x_n^2}, \quad n\in\mathbb{N},\end{equation*} konverguje pro libovolně zvolené \(x_1 > 0\) k číslu \(\sqrt[3]{c}\). Chybu mezi \(x_n\) a skutečnou hodnotou \(\sqrt[3]{c}\) lze odhadnout pomocí posledních dvou vypočtených členů: \begin{equation*} 0 < x_{n+1} - \sqrt[3]{c} < 2(x_n - x_{n+1}), \quad n=2,3,\ldots.\end{equation*} Tato informace nám umožňuje výpočet zastavit po dosažení požadované přesnosti.

Jako ukázku použití metody uvádíme tabulku 6.2 s výpočtem třetí odmocniny z čísla \(7\). Jako první iteraci volíme číslo \(7\) samotné. To není optimální volba.

Na výpočtu v tabulce 6.2 lze pozorovat, že od 6. iterace se počet správných cifer přibližně zdvojnásobuje. Tento efekt nazýváme kvadratickou konvergencí a přesně ho pro naši posloupnost formulujeme níže.

Je-li tedy chyba \(n\)-tého členu například \(10^{{\color{red}-5}}\), pak chyba dalšího členu je již pouze \(10^{{\color{red}-10}}\)!

6.13.1 Newtonova metoda: záludnosti

Rekurentní posloupnost pocházející z Newtonovy metody se pro „špatně“ zvolenou počáteční podmínku může chovat neočekávaně. Například může oscilovat (tj. posloupnost vůbec nebude mít limitu), nebo může divergovat do nekonečna.

Obrázek 6.25: Patologické chování posloupnosti aproximací generovaných Newtonovou metodou. Problém zřejmě spočívá ve špatné volbě počáteční aproximace.