Niutono metodu galima rasti realiuosius funkcijos nulius. Šis algoritmas kartais vadinamas Niutono–Rafsono metodu, pavadintu sero Izaoko Niutono ir Džozefo Rafsono garbei.

Metodas naudoja funkcijos išvestinę f′, kad iteratyviai artėtų prie šaknies. Reikia pasirinkti pradinį spėjimą x0. Iš vieno spėjimo gaunamas kitas pagal formulę:

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})}}}

Čia xn yra esamas spėjimas, o xn+1 — kitas spėjimas. Funkcija f turi turėti išvestinę f′ (bent jau toje srityje, kur ruošiame iteracijas).

Kaip metodas veikia (geometriškai)

Grafiškai Niutono metodas remiasi liestine: prie f taške xn nubrėžiama liestinė (tiesa, turint f′(xn)). Šios liestinės sankirtos su x ašimi x‑koordinatė yra naujas spėjimas xn+1. Kartojant procesą, spėjimai gali artėti prie funkcijos nulio.

Iteracijos žingsniai (paprasta algoritmo forma)

  • Pasirinkite pradinį spėjimą x0 ir toleranciją tol (pvz., 1e‑8).
  • Skaičiuokite xn+1 = xn − f(xn) / f′(xn).
  • Tikrinkite stabdymo sąlygas: pvz., |xn+1 − xn| < tol arba |f(xn+1)| < tol arba pasiektas maksimalus iteracijų skaičius.
  • Jei sąlygos neįvykdytos, imkite n ← n+1 ir kartokite.

Sąlygos ir savybės

  • Greitis: kai f yra pakankamai glotni ir f′(r) ≠ 0 (r — tikroji šaknis), Niutono metodas turi kvadratinį konvergencijos greitį. Tai reiškia, kad skaičiaus skaitmenų dvigubėjimas gali įvykti per kiekvieną iteraciją artėjant prie šaknies.
  • Pradinio spėjimo reikšmė: convergencija priklauso nuo pradinio spėjimo. Blogas pradinio taško pasirinkimas gali lemti lėtą artėjimą arba diverguoti.
  • Išvestinės reikšmė: jei f′(xn) yra arti nulio arba lygi nuliui, formulė gali duoti didelius žingsnius arba būti nesprendžiama (padalijimas iš nulio).
  • Stabilumas: funkcijos su keliomis šaknimis ar su mazgais (multiplicity > 1) gali sukelti lėtesnę konvergenciją arba reikalauti modifikacijų.
  • Taikymo sritis: nors dažniausiai minima realių funkcijų kontekste, metodas veikia ir kompleksiems kintamiesiems.

Pavyzdys: šaknies radimas f(x) = x² − 2 (sqrt(2))

Imkime f(x) = x² − 2, todėl f′(x) = 2x. Jaučiame, kad teigiama šaknis yra √2 ≈ 1.41421356. Pažiūrėkime keletą iteracijų su pradiniu spėjimu x0 = 1:

  • x1 = 1 − (1² − 2) / (2·1) = 1 − (−1)/2 = 1.5
  • x2 = 1.5 − (1.5² − 2) / (2·1.5) = 1.5 − 0.25/3 = 1.4166666667
  • x3 = 1.4166666667 − (1.4166666667² − 2) / (2·1.4166666667) ≈ 1.4142156863
  • x4 ≈ 1.4142135624 (jau labai arti √2)

Matome greitą artėjimą prie tikslios vertės — tipinė kvadratinės konvergencijos iliustracija.

Trūkumai ir apsauga nuo nuokrypių

  • Reikalinga f′: jei išvestinė sunkiai apskaičiuojama ar triukšminga, tai didina skaičiavimo kaštus arba klaidų riziką.
  • Gali diverguoti arba įstrigti cikle, jei pradinė tiesė patenka į sritį, kur metodas nepriartėja prie norimos šaknies.
  • Sprendimai: naudoti atšaldymą (damped Newton), linijinę paiešką (line search) arba patikimumo regiono (trust-region) metodus; jei išvestinė nežinoma, naudoti sekantinį metodą arba apytiksles išvestines skaitiniais skirtumais.

Praktinės pastabos

  • Parinkite toleranciją pagal reikalingą tikslumą ir skaičiavimo sąnaudas.
  • Apribokite iteracijų skaičių, kad išvengtumėte begalinio ciklo.
  • Stebėkite f′(xn) reikšmes; jeigu jos smarkiai mažėja, verta pereiti prie stabilesnės strategijos.
  • Niutono metodas dažnai naudojamas kaip pagrindinė pakopa daugelio optimizacijos algoritmų viduje, nes pasižymi greitu artėjimu prie sprendinio.

Apibendrinant: Niutono–Rafsono metodas yra galingas ir greitas šaknų radimo būdas, kai funkcija yra glotni ir turima jos išvestinė; tačiau reikia atsižvelgti į pradinį spėjimą, išvestinės elgesį bei galimas modifikacijas, kad būtų užtikrinta stabilumas praktiniuose skaičiavimuose.