Niutono–Rafsono metodas: šaknų radimas, formulė ir pavyzdžiai
Niutono–Rafsono metodas: aiškus formulės paaiškinimas, žingsnis po žingsnio pavyzdžiai ir grafinės iliustracijos, kaip greitai ir tiksliai rasti funkcijos šaknis.
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})}}}} 
Č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.
Funkcija (mėlyna) naudojama liestinės (raudona) tiesės (xn) nuolydžiui apskaičiuoti.
Niutono metodo problemos
Niutono metodu galima greitai rasti sprendinį, jei spėjamoji vertė prasideda pakankamai arti norimos šaknies. Tačiau kai pradinė spėjimo reikšmė nėra arti, priklausomai nuo funkcijos, Niutono metodas gali rasti atsakymą lėtai arba iš viso nerasti atsakymo.
Tolesnis skaitymas
- Fernández, J. A. E., & Verón, M. Á. H. (2017). Niutono metodas: Kantorovičiaus teorijos atnaujintas požiūris. Birkhäuser.
- Peter Deuflhard, Newton Methods for Nonlinear Problems. Affine Invariance and Adaptive Algorithms, Antrasis spausdintas leidimas. Serija Computational Mathematics 35, Springer (2006)
- Yamamoto, T. (2001). "Istorinė Niutono ir panašių į Niutoną metodų konvergencijos analizės raida". In Brezinski, C.; Wuytack, L. (red.). Numerical Analysis : Historical Developments in the 20th Century (Skaitmeninė analizė : istorinė raida XX amžiuje). North-Holland. p. 241-263.
Taip pat žr.
- Kantorovičiaus teorema (Leonido Kantorovičiaus teiginys apie Niutono metodo konvergavimą)
| Valdžios institucijų kontrolė |
|
Klausimai ir atsakymai
K: Kas yra Niutono metodas?
A: Niutono metodas - tai algoritmas, skirtas rasti realiuosius funkcijos nulius. Jis naudoja funkcijos išvestinę jos šaknims apskaičiuoti ir reikalauja pradinės nulinės vietos spėjamosios vertės.
K: Kas sukūrė šį metodą?
A: Šį metodą sukūrė seras Izaokas Niutonas ir Džozefas Rafsonas, todėl kartais jis vadinamas Niutono-Rafsono metodu.
K: Kaip veikia šis algoritmas?
A: Šis algoritmas veikia pakartotinai taikant formulę, pagal kurią imama pradinė spėjamoji vertė (xn) ir apskaičiuojama nauja spėjamoji vertė (xn+1). Kartojant šį procesą, spėjimai artėja prie funkcijos nulio.
Klausimas: Ko reikia, norint naudoti šį algoritmą?
A: Norėdami naudoti šį algoritmą, turite turėti pradinę "spėjamąją vertę" nulio vietai nustatyti ir žinių apie duotosios funkcijos išvestinę.
K: Kaip Niutono metodą paaiškinti grafiškai?
A: Niutono metodą galime paaiškinti grafiškai, žiūrėdami į liestinių linijų susikirtimus su x ašimi. Pirmiausia apskaičiuojama tiesė, liečianti f tiesę xn. Tada surandame šios liestinės tiesės susikirtimą su x ašimi ir užrašome jos x padėtį kaip kitą spėjimą - xn+1.
Klausimas: Ar yra kokių nors apribojimų naudojant Niutono metodą?
A: Taip, jei pradinė spėjimo reikšmė yra per daug nutolusi nuo tikrosios šaknies, gali prireikti daugiau laiko arba net nepavykti konverguoti į šaknį dėl svyravimų aplink ją arba nutolimo nuo jos.
Ieškoti