Newton: k čemu je tečna dobrá
Rovnice se ve škole řeší vzorcem. V praxi vzorec skoro nikdy není — a u polynomu pátého stupně prokazatelně neexistuje (Abelova věta). Řeší se to numericky, a nejrychlejší způsob stojí přesně na tom, čemu se věnovala kapitola 1.
- najdi x, kde f(x) = 0
Vyřešit rovnici znamená najít, kde křivka protne osu. U většiny rovnic to vzorcem nejde — u polynomu pátého stupně to prokazatelně nejde.
- f(x) ≈ f(x₀) + f′(x₀)(x − x₀)
Kapitola 1: tečna je nejlepší přímková náhrada. Křivku vyřešit neumíme, přímku ano — tak vyřešíme tu.
- x₁ = x₀ − f(x₀) / f′(x₀)
Tečna protne osu jinde než křivka — ale blíž ke kořeni. Celá metoda je tenhle jeden řádek.
- x₂ = 1,426890
Z nového bodu totéž. Počet správných číslic se každým krokem zhruba zdvojnásobí — čtyři, osm, šestnáct. Tomu se říká kvadratická konvergence a testy v repu ji měří.
- f′(x) ≈ 0 → krok uletí
Dělí se derivací, takže plochá tečna vystřelí odhad do nekonečna. Newton není zaručený — je rychlý, když funguje. Solver v téhle labce hlásí „diverged“ nebo „flat“ místo toho, aby vrátil číslo.
Křivku vyřešit neumíme, přímku ano. Tak funkci nahradíme tečnou, tu vyřešíme, a z výsledku uděláme nový odhad. Opakovat.
Kvadratická konvergence
Počet správných číslic se každým krokem zhruba zdvojnásobí. Testy v repu to měří na √2: chyby jdou 4·10⁻¹ → 9·10⁻² → 2·10⁻³ → 2·10⁻⁶ → 2·10⁻¹². Šest kroků z odhadu 1 na strojovou přesnost. Žádná jiná obecná metoda tohle neumí.
A kdy selže
Dělí se derivací, takže:
- Plochá tečna vystřelí odhad kamsi pryč. U x² + 1 ze startu 0 je
derivace nulová a metoda nemá kam jít — solver hlásí
flat. - Špatný start může způsobit, že se odhady rozkmitají nebo utečou. Učebnicový příklad je arctan: ze startu 0,5 doběhne, ze startu 5 diverguje. Obojí je v testech.
- Násobný kořen konvergenci degraduje z kvadratické na lineární.
Proto se v praxi kombinuje. Robustní řešiče střídají Newtona s bezpečnou, pomalou metodou (bisekce), která nemůže utéct: když Newtonův krok vypadne z intervalu, použije se půlení. Rychlost Newtona tam, kde funguje, jistota bisekce tam, kde ne. Táž úvaha stojí za tlumenými metodami v OptiLabu a za tlumenými nejmenšími čtverci v KineLabu.