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})}}} {\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.