Newtoni meetod ehk Newton–Raphsoni algoritm juurte leidmiseks
Newtoni meetod (Newton–Raphson) – kiire ja täpne algoritm funktsiooni reaaljuurte leidmiseks, kasutades tuletist ja iteratsiooni. Selged sammud ja graafiline selgitus.
Newtoni meetod annab võimaluse funktsiooni reaalnullide leidmiseks. Seda algoritmi nimetatakse sageli Newtoni–Raphsoni meetodiks, mis on nime saanud Sir Isaac Newtoni ja Joseph Raphsoni järgi. Meetod põhineb funktsiooni lineaarse lähenduse — puutuja — kasutamisel, et järjest lähemale liikuda funktsiooni nullpunktile.
Meetod kasutab funktsiooni tuletist, et leida selle juured. Nullpunkti asukoha jaoks tuleb teha esialgne "arvatav väärtus". Selle väärtuse põhjal arvutatakse selle valemi abil uus arvutus:
x n + 1 = x n - f ( x n ) f ′ ( x n ) {\displaystyle x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}} 
Siin xn on praegune ligikaudne väärtus ja xn+1 järgmine ligikaudne väärtus. Funktsioonil f (mille nulli otsitakse) on tuletis f'. Kui valemit korduvalt rakendada (iga kord asendada xn eelneva sammuga), võivad arvamised lähendada funktsiooni reaalsesse nulli, eeldusel, et käivituspunkt on sobiv ja teatud tingimused on täidetud.
Kuidas meetod töötab (geomeetriline seletus)
Graafiliselt seletatuna leitakse punktis xn funktsiooni f puutuja (sirge, mille kalle on f'(xn)) ning leitakse selle puutuja lõikepunkt x-teljega. Selle lõikepunkti x-koordinaat on järgmine ligikaudne väärtus xn+1. See protsess kordub, kuni jõutakse soovitud täpsuseni.
Konvergentsi omadused ja piirangud
- Kvadraatne konvergents: Kui funktsioon on piisavalt siledal kujul (tavaline tingimus: f on kaks korda diferentseeruv lähedal juurele) ja algusligikaudus on piisavalt lähedal reaalsetele nullidele ning f'(r) ≠ 0, siis Newtoni meetod konvergeerub lõpuks kvadraatkiirusega — vigade hulk väheneb ligikaudu ruuduna igas sammus.
- Tuletis null: Kui f'(xn) = 0 või on väga väike, siis samm võib muutuda väga suureks või määramatus tekkida. Sellisel juhul meetod ebaõnnestub või konvergents aeglustub.
- Mitmikkorrutus: Kui juur on mitmekordne (multiplicity m > 1), siis tavaline Newtoni meetod üldjuhul konvergeerub ainult lineaarselt. Sellisel juhul saab meetodit modifitseerida: xn+1 = xn - m·f(xn)/f'(xn), eeldusel et m on teada.
- Globaalne käitumine ja basseinid: Newtoni meetodi lähtepunkt võib määrata, millisele juurele see lõpuks konvergeerub; mõnikord tekivad tsüklid või divergents. Seetõttu ei ole meetod alati "globaalne" — algväärtuse valik on oluline.
Praktilised parendused ja alternatiivid
- Hõlmamismeetodite kombinatsioon: Kui on vaja globaalset kindlust, võib alguses kasutada bisection- või regula falsi-meetodit kuni läheduseni ning seejärel üle minna Newtonile, et saada kiire kvadraatne konvergents.
- Hämmastamine / damping: Kui sammud on liiga suured, kasutatakse kahanemistegurit λ (0 < λ ≤ 1): xn+1 = xn - λ·f(xn)/f'(xn). See võib parandada stabiilsust.
- Kui tuletist pole kättesaadav: Kasutada saab sekantmeetodit, mis lähtub kahest eelmise iteratsiooni väärtusest ja ei vaja analüütilist tuletist (konvergents kvasi‑kulgneb vähem kiiresti kui Newton).
- Systemid: Newtoni meetod üldistub süsteemidele: lahendatakse iga sammu juures lineaarvõrrandisüsteem J(xn) Δx = −F(xn), kus J on Jakobiaan ja Δx = xn+1 − xn.
Pehmesed punktid ja parandusmeetmed
- Kontrolli, et f'(xn) ei oleks väga väike enne jagamist; vajadusel kasuta piiratud sammupikkust või dampimist.
- Sea lõppkriteerium: kas |f(xn)| < tol, või |xn+1 − xn| < tol, või maksimaalne iteratsioonide arv.
- Kui meetod hakkab ebaõnnestuma (väga suur samm või korduvad väärtused), proovi teist algväärtust või üleminekut robustsemale meetodile.
Lihtne näide
Leia √2, st lahendada f(x)=x²−2=0. Valime x₀=1.
- x₁ = x₀ − f(x₀)/f'(x₀) = 1 − (1−2)/(2·1) = 1.5
- x₂ ≈ 1.4166667
- x₃ ≈ 1.4142157 (juba väga lähedal täpsusele 1.41421356...)
Rakendused
Newtoni meetodit kasutatakse laialdaselt numbrilises analüüsis ning inseneri- ja teadusrakendustes: juurte leidmine, optimeerimine (Newtoni meetod optimeerimises lahendab gradienti võrdseks nulliga), mitmemõõtmelised süsteemid, füüsikalis-matemaatilised mudelid jpm. Selle populaarsuse põhjuseks on iteratsiooni kiire lokaalne konvergents ja üldine lihtsus, juhul kui tuletis või Jakobiaan on kättesaadav ning liidetud.
Kokkuvõte
Newtoni meetod on võimas ja tõhus iteratiivne meetod funktsioonide nullide leidmiseks. Selle edu sõltub eelkõige algväärtusest, funktsiooni omadustest (eriti tuletise käitumisest) ja vajadusel kasutatavatest parendustest (dampimine, kombineerimine teiste meetoditega, modifitseeritud sammud mitmikkordsete juurte korral). Praktikas kombineeritakse Newtoni meetodit sageli teiste robustsemate meetoditega, et saavutada nii globaalne kui ka lokaalselt kiire konvergents.
Funktsiooni (sinine) kasutatakse puutujajoone (punane) tõusu arvutamiseks xn juures.
Probleemid Newtoni meetodiga
Newtoni meetod võib leida lahenduse kiiresti, kui arvatav väärtus algab piisavalt lähedal soovitud juurele. Kui aga esialgne arvutusväärtus ei ole lähedane ja sõltuvalt funktsioonist, võib Newtoni meetod leida lahenduse aeglaselt või üldse mitte.
Edasine lugemine
- Fernández, J. A. E., & Verón, M. Á. H. (2017). Newtoni meetod: Kantorovitši teooria ajakohastatud käsitlus. Birkhäuser.
- Peter Deuflhard, Newtoni meetodid mittelineaarsete probleemide lahendamiseks. Affine Invariance and Adaptive Algorithms, teine trükitud väljaanne. Sari Computational Mathematics 35, Springer (2006).
- Yamamoto, T. (2001). "Ajaloolised arengud Newtoni ja Newtoni-sarnaste meetodite lähenemisanalüüsis". In Brezinski, C.; Wuytack, L. (eds.). Numerical Analysis : Historical Developments in the 20th Century. North-Holland. pp. 241-263.
Vt ka
- Kantorovitši teoreem (Leonid Kantorovitši poolt leitud väide Newtoni meetodi konvergentsi kohta)
| Ametiasutuste kontroll |
|
Küsimused ja vastused
K: Mis on Newtoni meetod?
V: Newtoni meetod on algoritm funktsiooni reaalnullide leidmiseks. See kasutab funktsiooni juurte arvutamiseks funktsiooni tuletist ja nõuab nullpunkti asukoha algset arvutusväärtust.
K: Kes töötas selle meetodi välja?
V: Meetodi töötasid välja Sir Isaac Newton ja Joseph Raphson, seetõttu nimetatakse seda mõnikord Newtoni-Raphsoni meetodiks.
K: Kuidas see algoritm töötab?
V: See algoritm töötab, rakendades korduvalt valemit, mis võtab esialgse arvutusväärtuse (xn) ja arvutab uue arvutusväärtuse (xn+1). Seda protsessi korrates läheneb arvutusfunktsiooni nullile.
K: Mida on selle algoritmi kasutamiseks vaja?
V: Selle algoritmi kasutamiseks peab teil olema algne "arvamisväärtus" nulli asukoha kohta ning teadmised antud funktsiooni tuletise kohta.
K: Kuidas saab Newtoni meetodit graafiliselt selgitada?
V: Me saame Newtoni meetodit graafiliselt selgitada, vaadeldes puutujajoonte ja x-telje lõikepunkte. Kõigepealt arvutatakse sirge, mis puutub f'ile xn juures. Seejärel leiame selle puutujajoone ja x-telje lõikepunkti ja registreerime selle x-positsiooni järgmise arvutusena - xn+1.
K: Kas Newtoni meetodi kasutamisel on mingeid piiranguid?
V: Jah, kui teie esialgne arvutusväärtus on tegelikust juurest liiga kaugel, siis võib see võtta kauem aega või isegi mitte konvergeeruda juure suunas, kuna see võngub selle ümber või kaldub sellest eemale.
Otsige