Newtonova metoda

Newtonova metóda ali tangéntna metóda je v matematiki in še posebej numerični analizi numerična metoda za iskanje ničel funkcije. Ker je sorodna z metodo navadne iteracije, le da je po navadi dosti hitrejša, se imenuje tudi metóda pospéšene iterácije.

Za avtorja metode šteje Isaac Newton, ki jo je opisal v delu De analysi per aequationes numero terminorum infinitas (napisano 1669, izdano 1711). Ker se je s to metodo ukvarjal tudi Joseph Raphson v delu Analysis aequationum universalis (1690), se jo včasih zasledi tudi pod imenom Newton-Raphsonova metoda.

Zamisel metode

Prvi trije približki ($x_{0},x_{1},x_{2}\!\,$) ničel funkcije $f(x)\!\,$ po Newtonovi metodi

Funkcija $f(x)\!\,$ je prikazana v modri, tangenta pa v rdeči barvi. Vidi se, da je $x_{n+1}\!\,$ boljši približek kot $x_{n}\!\,$ za ničlo $x\!\,$ funkcije $f(x)\!\,$.

Osnovna zamisel te metode je naslednja:

• število $x_{0}\!\,$ naj bo približek za ničlo funkcije $f(x)\!\,$.
• v točki $x_{0}\!\,$ se postavi tangento na graf funkcije $f(x)\!\,$ in pogleda, kje je ničla tangente.
• ker je tangenta dobra aproksimacija za funkcijo, se sklepa, da je ničla tangente dober približek za ničlo funkcije $f(x)\!\,$. Ničlo tangente se vzame torej za naslednji približek $x_{1}\!\,$.
• postopek se nadaljuje na enak način in tako se iz $x_{1}\!\,$ dobi nov približek $x_{2}\!\,$, itd.
• dobljeno zaporedje približkov praviloma hitro konvergira k ničli funkcije $f(x)\!\,$.

Opis in praktična izvedba

Če za funkcijo veljajo ustrezni privzetki in, če je začetni približek blizu, potem je:

$x_{1}=x_{0}-{\frac {f(x_{0})}{f'(x_{0})}}\!\,$

boljši približek ničle funkcije kot $x_{0}\!\,$. Geometrijsko je točka $(x_{1},0)\!\,$ presečišče abscise in tangente grafa funkcije v točki $x_{0},f(x_{0})\!\,$ – izboljšani približek je edina ničla linearne aproksimacije v začetni točki. Formula iteracijskega koraka, po kateri se iz približka $x_{n}\!\,$ izračuna naslednji približek $x_{n+1}\!\,$, je zelo preprosta:

$x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}\!\,.$

V formuli nastopata vrednost funkcije $f(x)\!\,$ in vrednost prvega odvoda $f'(x)(\mathrm {d} f(x)/\mathrm {d} x)\!\,$ (tj. vrednost smernega koeficienta tangente).

Uspešnost in raba metode

Izkaže se, da je Newtonova metoda uspešna za iskanje ničel prve stopnje. Pri takih ničlah zaporedje približkov vedno vodi k ničli, če je le začetni približek primerno izbran. V ničlah višje stopnje je tangenta vodoravna, kar otežuje (ali celo onemogoča) uporabo Newtonove metode.

Newtonovo metodo se najpogosteje uporablja pri iskanju ničel polinomov, vendar pa ni omejena samo na polinome: uporabi se jo lahko tudi na drugih odvedljivih funkcijah. Uporabna je celo za iskanje ničel v kompleksnem, če se izbere primeren (nerealnen) začetni približek. Lahko se uporabi tudi pri reševanju sistemov enačb. Metoda je prva v vrsti razreda Householderjevih metod, algoritmov iskanja ničel. Druga v vrsti je Halleyjeva metoda.

Zgodovina

Ime metode izhaja iz Newtonovega opisa posebnega primera metode v delu O analizi z enačbami z neskončnim številom členov (De analysi per aequationes numero terminorum infinitas), ki ga je Newton napisal leta 1669 in izdal leta 1711 William Jones, ter v delu O metodi fluksij in neskončnih vrstah (De metodis fluxionum et serierum infinitarum), napisanem leta 1671, ki ga je prevedel in izdal z naslovom Metoda fluksij (Method of Fluxions) leta 1736 John Colson). Newtonova metoda se precej razlikuje od sodobne različice, podane zgoraj. Uporabil jo je le za polinome, začel z začetnim približkom ničle in izbral zaporedje popravkov napake. Vsak popravek je vzel za ponovni zapis polinoma s členi preostale napake, nato pa rešil za nov popravek in pri tem zanemaril člene višjih redov. Eksplicitno ni povezal metode z odvodi ali s sodobno splošno formulo. Uporabil jo je tako za numerične kot za algebrajske probleme, kar je v kasnejšem primeru dalo Taylorjevo vrsto.

Newton je morda izpeljal svojo metodo iz podobne vendar manj točne Viètove metode. Bistvo Viètove metode se lahko najde v delu perzijskega matematika Šarafa Al Dina Al Tusija, medtem ko je njegov naslednik Džamšid Al Kaši rabil različico Newtonove metode za reševanje korenov $N\!\,$ enačb oblike $x^{P}-N=0\!\,$.. Posebni primer Newtonove metode za računanje kvadratnih korenov je bil znan od davnine in se pogosto imenuje babilonska metoda.

Newtonovo metodo je rabil japonski matematik Seki Kova za reševanje enačb z eno spremenljivko, čeprav ni bilo povezave z infinitezimalnim računom.

Newtonovo metodo je prvi objavil John Wallis leta 1685 v delu Razprava o algebri tako zgodovinska kot praktična (A Treatise of Algebra both Historical and Practical). Joseph Raphson je leta 1690 v delu Analiza splošnih enačb (Analysis aequationum universalis) objavil poenostavljeni opis metode. Raphson je uporabil metodo le za polinome, izognil pa se je Newtonovemu dolgotrajnemu prepisovalnemu procesu z uzpisom vsakega zaporednega popravka iz izvirnega polinoma. To mu je omogočilo izpeljavo ponovno uporabnega iterativnega izraza za vsak problem. Končno je leta 1740 Thomas Simpson opisal Newtonovo metodo kot iterativno metodo za reševanje splošnih nelinearnih enačb s pomočjo infinetizimalnega računa, ter dejansko podal zgornji opis. V isti publikaciji je Simpson dal posplošitev na sistem dveh enačb in omenil, da se lahko Newtonova metoda uporabi za reševanje optimizacijskih problemov z nastavkom ničelnega prirastka.

Arthur Cayley je leta 1879 v članku The Newton–Fourier imaginary problem prvi opazil težave pri posploševanju Newtonove metode na kompleksne ničle polinomov stopnje večje od 2 in kompleksne začetne vrednosti. To je odprlo pot raziskovanju teorije iteracij racionalnih funkcij.

Zgled

Po Newtonovi metodi naj se izračuna ničlo funkcije $f(x)=x^{2}-612\!\,$. Odvod te funkcije je $f'(x)=2x\!\,$. Za začetni približek se izbere število 10. Dobi se zaporedje približkov:

${\begin{matrix}x_{0}&=&10&&&&\\x_{1}&=&x_{0}-{\frac {f(x_{0})}{f'(x_{0})}}&=&10-{\frac {10^{2}-612}{2\cdot 10}}&=&35,6\\x_{2}&=&x_{1}-{\frac {f(x_{1})}{f'(x_{1})}}&=&35,6-{\frac {35,6^{2}-612}{2\cdot 35,6}}&=&{\underline {2}}6,395\ 5056\\x_{3}&=&\vdots &=&\vdots &=&{\underline {24,7}}90\ 6355\\x_{4}&=&\vdots &=&\vdots &=&{\underline {24,7386\ }}883\\x_{5}&=&\vdots &=&\vdots &=&{\underline {24,738\ 633\ 8}}\end{matrix}}$

Vidi se, da zaporedje približkov hitro konvergira.

Končni rezultat je seveda enak ${\sqrt {612}}\!\,$. Na tem mestu naj se poudari, da se je med samim izvajanjem Newtonove metode uporabljalo samo osnovne računske operacije (plus, minus, krat, deljeno). Newtonova metoda je tako lahko tudi način za poenostavljeno izračunavanje vrednosti bolj kompliciranih funkcij, na primer drugih elementarnih in specialnih funkcij.

Praktični premisleki

Newtonova metoda je močna tehnika – v splošnem je stopnja konvergence kvadratična: ker metoda konvergira za ničlo, je razlika med ničlo in približkom kvadrirana. Število točnih števk se v vsakem koraku v grobem podvoji. Vendar pri metodi obstaja več težav.

Težavno računanje odvoda funkcije

Newtonova metoda zahteva, da se odvod izračuna neposredno. Analitični izraz za odvod mogoče ni lahko najti ali pa bi bil prezahteven za določitev vrednost. V teh razmerah je primerno najti približek odvoda s pomočjo naklona premice skozi dve bližnji točki na funkciji. Z rabo takšnega približka se dobi nekaj podobnega kot sekantna metoda, ki konvergira počasneje kot Newtonova metoda.

Neuspeh metode pri konvergenci k ničli

Pomembno je pregledati dokaz kvadratne konvergence Newtonove metode pred njeno uporabo. Še posebej je treba pregledati predpostavke uporabljene v dokazu. Za razmere kjer metoda odpove pri konvergenci je krivo to, da se predpostavke iz dokaza niso preverile.

Zgrešitev

Če se prvi odvod ne obnaša dobro v okolici določene ničle, lahko metoda zgreši in v tej točki divergira. Zgled funkcije z eno ničlo, za katero se odvod v njeni okolici ne obnaša dobro, je na primer potenčna funkcija absolutne vrednosti:

$f(x)=|x|^{a},\qquad (0<a<{\tfrac {1}{2}})\!\,,$

za katero bo ničla zgrešena in bo zaporedje približkov $x_{n}\!\,$ divergiralo. Za $a={\frac {1}{2}}\!\,$ bo ničla še vedno zgrešena, zaporedje pa bo osciliralo med dvema vrednostima. Za ${\frac {1}{2}}<a<1\!\,$ bo ničla zgrešena, zaporedje pa bo konvergiralo, in za $a\geq 1\!\,$ ničla ne bo zgrešena.

V nekaterih primerih se lahko Newtonova metoda uravnoteži s pomočjo metode zaporedne prerelaksacije, ali pa se stopnja konvergence poveča z enako metodo.

Stacionarna točka

Če se sreča stacionarna točka funkcije, je njen odvod enak nič, in metoda zaradi deljenja z ničlo ne bo delovala.

Slaba začetna ocena

Velika napaka v začetni oceni lahko pripomore k nekonvergenci algoritma. Da bi se premagalo ta problem, se lahko velikokrat linearizira funkcijo, ki se jo optimira s pomočjo infinitezimalnega računa, diferenciali ali celo z uporabo evolucijskih algoritmov, kot je na primer stohastično tuneliranje. Dobre začetne ocene ležijo blizu končne globalne optimalne parametrične ocene. V nelinearni regresiji je vsota kvadratičnih napak (SSE) »blizu« paraboličnosti območja končnih parametričnih ocen. Začetne ocene, najdene tukaj, bodo omogočile, da Newton-Rapsonova metoda hitro konvergira. Le tu je Hessejeva matrika vsote SSS pozitivna, prvi odvod vsote SSE pa je blizu nič.

Blažitev nekonvergence

V grobi implementaciji Newtonove metode je običajno omejiti število iteracij, povezati rešitev na interval, za katerega se ve, da vsebuje ničlo, in kombinirati metodo z bolj grobo metodo iskanja ničle.

Počasne konvergence za ničle multiplikativnosti večje od 1

Če ima iskana ničla multiplikativnost večjo od ena, je stopnja konvergence zgolj linearna – napake, zmanjšane s konstantnim množiteljem v vsakem koraku, dokler niso narejeni posebni koraki. Kadar sta dve ali več ničel, ki so blizu skupaj, se lahko naredi mnogo iteracij preden iterati pridejo dovolj blizu k eni od njih, da postane konvergenca očitna. Če pa je vendar multiplikativnost $m\!\,$ ničle znana, naslednji algoritem ohranja kvadratično stopnjo konvergence:

$x_{n+1}=x_{n}-m{\frac {f(x_{n})}{f'(x_{n})}}\!\,.$

To je enakovredno rabi zaporedne prerelaksacije. Na drugi strani, če multiplikativnost $m\!\,$ ničle ni znana, je možno oceniti $m\!\,$ po izvedbi ene ali dveh iteracij, in potem uporabiti to vrednost za povečanje stopnje konvergence.

Če je multiplikativnost $m\!\,$ ničle končna, po tem bo imela funkcija $g(x)=f(x)/f'(x)\!\,$ ničlo na istem mestu z multiplikativnostjo 1. Uporaba Newtonove metode za iskanje ničle funkcije $g(x)\!\,$ povrne kvadratično konvergenco v mnogih primerih, čeprav v splošnem vključuje druge odvode od funkcije $f(x)\!\,$. V posebej preprostem primeru, če je funkcija enaka potenčni oblike $f(x)=x^{m}\!\,$, je $g(x)=x/m\!\,$ , Newtonova metoda najde ničlo v eni samiiteraciji z nastavkom itarecijskega koraka:

$x_{n+1}=x_{n}-{\frac {g(x_{n})}{g'(x_{n})}}=x_{n}-{\frac {x_{n}/m}{1/m}}=0\!\,.$

Viri

• Raphson, Joseph (1697), Analysis Æequationum Universalis (v latinščini) (2. izd.), London: Thomas Bradyll, doi:10.3931/e-rara-13516
• Stöcker, Horst (2006), Matematični priročnik z osnovami računalništva, Ljubljana: Tehniška založba Slovenije, str. 50, 451, COBISS 229576192, ISBN 86-365-0587-9, OCLC 449201276
• Wallis, John (1685), A Treatise of Algebra, both Historical and Practical, Oxford: Richard Davis, doi:10.3931/e-rara-8842
• Ypma, Tjalling Johannes (1995), »Historical development of the Newton–Raphson method«, SIAM Review, 37 (4): 531–551, doi:10.1137/1037125