Newtonova metóda umožňuje nájsť reálne nuly funkcie. Tento algoritmus sa niekedy nazýva Newtonova-Raphsonova metóda, pomenovaná podľa sira Isaaca Newtona a Josepha Raphsona.

Metóda využíva deriváciu funkcie na nájdenie jej koreňov. Je potrebné odhadnúť počiatočnú pozičnú hodnotu nuly (tzv. počiatočný odhad). Z tejto hodnoty sa vypočíta nový odhad podľa tohto vzorca:

x n + 1 = x n - f ( x n ) f ′ ( x n ) {\displaystyle x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}} {\displaystyle x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}}

Tu xn je aktuálny odhad a xn+1 je ďalší odhad. Funkcia f (ktorej nula sa rieši) má deriváciu f'.

Základný princíp

Opakovaným použitím tohto vzorca na vygenerované odhady (t. j. nastavením hodnoty xn na výstup vzorca a opätovným výpočtom) sa hodnota odhadov často rýchlo priblíži k reálnej nule funkcie. Geometricky sa to dá vysvetliť pomocou priesečníkov dotyčnice s osou x: v bode xn sa sestrojí dotyčnica grafu funkcie, nájde sa jej priesečník s osou x a jeho x-ová súradnica je xn+1.

Algoritmus (krok za krokom)

  • Zvoľte počiatočný odhad x0.
  • Opakujte krok: xn+1 = xn − f(xn)/f'(xn).
  • Skontrolujte kritérium zastavenia, napr. |f(xn+1)| < tol alebo |xn+1 − xn| < tol alebo dosiahnutie maximálneho počtu iterácií.

Podmienky konvergencie a vlastnosti

  • Lokálna kvadratická konvergencia: Ak je koreň r jednoduchý (t.j. f(r) = 0 a f'(r) ≠ 0) a počiatočný odhad je dostatočne blízko k r, Newtonova metóda konverguje kvadraticky — počet správnych číslic sa približne zdvojnásobí pri každej iterácii.
  • Citlivosť na počiatočný odhad: Ak je počiatočný odhad príliš vzdialený, metóda nemusí konvergovať alebo sa môže dostať k inému koreňu. Oblasť bodov, z ktorých sa metóda konverguje k danému koreňu, sa nazýva basin of attraction a môže byť zložitá.
  • Problém s nulovou deriváciou: Ak pre nejaké xn platí f'(xn) = 0 (alebo je veľmi malá), iterácia nie je definovaná alebo môže viesť k veľkým krokom a nestabilite.
  • Opakované koreňe: Ak koreň má násobnosť m > 1, konvergencia je len lineárna (pomalšia). Existuje modifikovaná Newtonova metóda: xn+1 = xn − m·f(xn)/f'(xn) na zlepšenie rýchlosti, ak je m známa.

Praktické úpravy a alternatívy

  • Damping (preriedenie) kroku: Použitie parametra 0 < λ ≤ 1 a náhrada kroku xn+1 = xn − λ·f(xn)/f'(xn) pomáha predísť preskočeniu a zlepšiť globálnu stabilitu.
  • Secant metóda: Ak nie je k dispozícii derivácia, secant metóda aproximuje deriváciu a vyžaduje len hodnoty f; má superlineárnu (ale nie kvadratickú) konvergenciu.
  • Hybridné metódy: Kombinácie bisekcie (garantovaná konvergencia) a Newtona (rýchlosť) sú bežné v knižniciach numerických metód.
  • Kontrola krokov a obmedzenia: V praxi sa zväčša kontroluje veľkosť kroku a ak je príliš veľký, zmenší sa alebo zvolí alternatívna stratégia.

Kritériá zastavenia

  • |f(xn)| < tolerance — zodpovednosť funkcie blízko nule.
  • |xn+1 − xn| < tolerance — zmena medzi iteráciami je malá.
  • Dosiahnutie maximálneho počtu iterácií — bezpečnostné opatrenie.

Príklad

Riešime f(x) = x² − 2 (hľadáme sqrt(2)). Zvoľme x0 = 1.

  • f'(x) = 2x
  • x1 = 1 − (1² − 2)/(2·1) = 1.5
  • x2 = 1.5 − (1.5² − 2)/(2·1.5) ≈ 1.4166667
  • x3 ≈ 1.4142157, atď. — približne po niekoľkých iteráciách získame hodnotu 1.41421356…

Výhody a nevýhody

  • Výhody: veľmi rýchla lokálna konvergencia (kvadratická), jednoduchá implementácia ak je k dispozícii derivácia.
  • Nevýhody: potreba derivácie, citlivosť na počiatočný odhad, problémy pri nulových alebo malých deriváciách, menej spoľahlivá bez doplnkových opatrení.

Newtonova metóda je v numerickom výpočte veľmi užitočná vďaka svojej rýchlosti pri dobrom počiatočnom odhade, avšak pri praktickej implementácii je dôležité doplniť ju o kontrolné mechanizmy (damping, overenie derivácie, heuristiky pre zmenu stratégie), aby bola robustná aj pre náročnejšie prípady.