Newton-Raphsonova metoda: iterativni algoritem za iskanje ničel funkcij
Newton-Raphsonova metoda: iterativni algoritem za hitro iskanje ničel funkcij. Razlaga formule, grafična interpretacija, primeri in nasveti za zanesljivo konvergenco.
Newtonova metoda omogoča iskanje realnih ničel funkcije. Ta algoritem se včasih imenuje Newton-Raphsonova metoda, poimenovana po siru Isaacu Newtonu in Josephu Raphsonu. Metoda je učinkovita in pogosto zelo hitra, vendar zahteva, da je funkcija odvedljiva in da je izbran primeren začetni približek.
Metoda za iskanje korenov funkcije uporablja derivat funkcije. Na začetku je treba "uganiti vrednost" lokacije ničle. Iz te vrednosti se izračuna nova domneva po tej formuli:
x n + 1 = x n - f ( x n ) f ′ ( x n ) {\displaystyle x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}} 
Pri tem je xn začetna domneva, xn+1 pa naslednja domneva. Funkcija f (katere ničlo se rešuje) ima derivativ f'.
Princip delovanja
Z večkratno uporabo te formule za ustvarjene domneve (tj. z nastavitvijo vrednosti xn na izhod formule in ponovnim izračunom) se bo vrednost domnev približala ničli funkcije, če so izpolnjeni ustrezni pogoji. Newtonovo metodo je mogoče razložiti grafično, tako da si ogledate presečišča tangentnih premic z osjo x. Najprej se izračuna premica, ki je tangenta na f pri xn. Nato se poišče presečišče te tangente z osjo x. Nazadnje se x-pozicija tega presečišča zapiše kot naslednja domneva, xn+1.
Pogoji in lastnosti konvergence
- Diferencibilnost: f mora biti odvedljiva v okolici ničle, saj metoda uporablja f'.
- f'(x) ≠ 0: Če je f' blizu nič ali enak nič pri trenutnem približku, se iteracija lahko zruši ali postane nestabilna.
- Začetni približek: Izberemo xn blizu prave ničle; slaba izbira lahko vodi v divergentno zaporedje ali v konvergenco proti drugi ničli.
- Red konvergence: Če je ničla enostavna (multipliciteta 1) in f ima dovolj gladkosti, je Newtonova metoda kvadratno konvergentna — število pravilnih decimalk približno podvoji s posamezno iteracijo.
- Večkratne ničle: Če ima ničla multiplicitet ≥ 2, hitrost konvergence se običajno zmanjša (običajno linearna) razen če uporabimo prilagojeno formulo.
Praktični napotki in kriteriji zaustavitve
- Najpogostejši kriteriji zaustavitve:
- |x_{n+1} − x_n| < tol (absolutna sprememba manjša od tolerance)
- |f(x_n)| < tol (residual blizu nič)
- dosežen maksimalno število iteracij
- Če je izračun prvega odvodka težaven, lahko uporabimo numerične aproksimacije (npr. diference), vendar to vpliva na natančnost in konvergenco.
- V praksi se pogosto uporablja amortizacija (damped Newton): x_{n+1} = x_n − λ * f(x_n)/f'(x_n) z 0 < λ ≤ 1, da se prepreči preskoke ali divergence.
- Za večdimenzionalne probleme (sistem nenačelnih enačb) se Newtonova metoda razširi z Jacobijevo matriko J(x): rešujemo linearni sistem J(x_n) Δx = −F(x_n) in nastavimo x_{n+1} = x_n + Δx.
Primer
Za funkcijo f(x) = x^2 − 2 je odvod f'(x) = 2x. Iteracijska formula postane x_{n+1} = x_n − (x_n^2 − 2)/(2x_n) = (x_n + 2/x_n)/2, kar je znana iteracija za kvadratni koren. Če začnemo z x0 = 1, dobimo zaporedje, ki hitro konvergira proti sqrt(2).
Omejitve in alternative
- Newtonova metoda ni globalno konvergentna — brez dodatnih ukrepov se lahko oddalji od iskane ničle.
- Če f' v bližini približka postane zelo majhen, se lahko pojavi divergenča ali kroženje.
- Alternativne metode, kadar f' ni znan ali je draga za izračun:
- Secant metoda — približek odvoda z dvema prejšnjima vrednostma; običajno konvergenca superlinearno, a ni kvadratna.
- Modificirane Newtonove metode za večkratne ničle ali za stabilnejšo obnašanje (porazdeljena ali damped Newton).
- Halleyjeva metoda — višji red konvergence (kubična) z uporabo drugega odvoda.
Newtonova metoda je zato v numerični analizi zelo uporabna zaradi svoje hitrosti in enostavne oblike, vendar zahteva previdnost pri izbiri začetnega približka, pri obnašanju odvoda in pri oceni, ali so pogoji za varno kvadratno konvergenco izpolnjeni.
Funkcija (modra) se uporablja za izračun naklona tangentne premice (rdeča) na xn.
Težave z Newtonovo metodo
Newtonova metoda lahko hitro najde rešitev, če se ugibana vrednost začne dovolj blizu želenega korena. Kadar začetna ugibana vrednost ni blizu, pa lahko Newtonova metoda, odvisno od funkcije, rešitev najde počasi ali pa je sploh ne najde.
Nadaljnje branje
- Fernández, J. A. E., & Verón, M. Á. H. (2017). Newtonova metoda: Kantorovičeva teorija: posodobljen pristop. Birkhäuser.
- Peter Deuflhard, Newtonove metode za nelinearne probleme. Affine Invariance and Adaptive Algorithms, druga tiskana izdaja. Serija Computational Mathematics 35, Springer (2006)
- Yamamoto, T. (2001). "Zgodovinski razvoj na področju analize konvergence Newtonovih in Newtonu podobnih metod". In Brezinski, C.; Wuytack, L. (ur.). Numerical Analysis : Historical Developments in the 20th Century (Numerična analiza : zgodovinski razvoj v 20. stoletju). North-Holland, str. 241-263.
Oglejte si tudi
- Kantorovičev izrek (Izrek o konvergenci Newtonove metode, ki ga je ugotovil Leonid Kantorovič)
| Nadzor organa |
|
Vprašanja in odgovori
V: Kaj je Newtonova metoda?
O: Newtonova metoda je algoritem za iskanje realnih ničel funkcije. Za izračun korenov funkcije uporablja njeno izpeljanko, za lokacijo ničle pa zahteva začetno ugibanje vrednosti.
V: Kdo je razvil to metodo?
O: Metodo sta razvila sir Isaac Newton in Joseph Raphson, zato jo včasih imenujemo Newton-Raphsonova metoda.
V: Kako deluje ta algoritem?
O: Ta algoritem deluje tako, da večkrat uporabi formulo, ki prevzame začetno ugibano vrednost (xn) in izračuna novo ugibano vrednost (xn+1). S ponavljanjem tega postopka se ugibanja približajo ničli funkcije.
V: Kaj je potrebno za uporabo tega algoritma?
O: Za uporabo tega algoritma morate imeti začetno "domnevno vrednost" za lokacijo ničle in znanje o odvodniku dane funkcije.
V: Kako lahko Newtonovo metodo razložimo grafično?
O: Newtonovo metodo lahko grafično razložimo tako, da si ogledamo presečišča tangentnih premic z osjo x. Najprej izračunamo premico, ki je tangenta na f pri xn. Nato poiščemo presečišče te tangentne črte z osjo x in zapišemo njeno lego x kot našo naslednjo domnevo - xn+1.
V: Ali obstaja kakšna omejitev pri uporabi Newtonove metode?
O: Da, če je začetna vrednost domneve preveč oddaljena od dejanskega korena, lahko traja dlje časa ali celo ne konvergira proti korenu zaradi nihanja okoli njega ali odstopanja od njega.
Iskati