Newtonin menetelmä

Newtonin menetelmä (tunnettu myös nimillä Newtonin–Raphsonin menetelmä tai Newtonin–Fourier'n menetelmä) on numeerisessa analyysissä tehokas algoritmi funktion nollakohtien likiarvojen löytämiseksi. Sitä voidaan käyttää myös funktion ääriarvojen etsimiseen soveltamalla menetelmää funktion ensimmäiseen derivaattaan.

Menetelmän kuvaus

Aloitetaan nollakohdan etsiminen tekemällä tuntemattomalle alkuarvaus mieluiten mahdollisimman läheltä haluttua nollakohtaa. Korvataan funktio tangentillaan, mikä voidaan tehdä lukiomatematiikan keinoin^selvennä. Tämän jälkeen lasketaan kyseisen tangentin nollakohta. Yleensä tämä nollakohta on parempi likiarvo funktion nollakohdalle. Otetaan tämä uudeksi arvoksi ja toistetaan iterointi riittävän usein haluttuun tarkkuuteen pääsemiseksi.

Oletetaan, että f : [a, b] → R on derivoituva funktio, joka on määritelty välillä [a, b] ja sen arvojoukko koostuu reaaliluvuista R. Nollakohta löydetään seuraavasti. Oletetaan, että tiedossa oleva likiarvo on x_n. Siitä saadaan parempi likiarvo x_n+1 alla olevan diagrammin mukaisesti. Derivaatan määritelmästä tunnetaan, että derivaatan arvo missä tahansa pisteessä on kyseiseen pisteeseen piirretyn tangentin kulmakerroin.

Tällöin

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

Tässä f ' tarkoittaa funktion f derivaattaa. Tästä päädytään sieventämällä muotoon

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

Iterointi aloitetaan valitsemalla jokin näennäisen satunnainen alkuarvo x₀ (mitä lähempää todellista nollakohtaa tämä valitaan, yleensä sitä parempi). Menetelmä yleensä suppenee, mikäli valittu alkuarvo on riittävän lähellä nollakohtaa. Karkeasti voidaan todeta, että nollakohdan ympäristössä saadun likiarvon oikeiden desimaalien lukumäärä vähintään kaksinkertaistuu jokaisessa iteraatiossa.

Iteroimalla arvolla x_n on päästy arvoa x lähempänä olevaan arvoon x_n+1.

Kuva Newtonin menetelmän yhdestä iteraatiosta. Tästä nähdään, että $x_{n+1}$ on funktion $f$ nollakohdalle parempi likiarvo kuin $x_{n}$

Esimerkki

Etsi yhtälön cos(x) = x³ positiivinen ratkaisu. Muutetaan tehtävä funktion f(x) = cos(x) − x³ nollakohdan löytämiseksi. Derivoidaan funktio: f '(x) = −sin(x) − 3x². Koska cos(x) ≤ 1 kaikille x:n arvoille ja x³ > 1, kun x > 1, tiedämme, että nollakohta on välillä ]0,1[. Otetaan alkuarvoksi x₀ = 0,5.

${\begin{matrix}x_{1}&=&x_{0}-{\frac {f(x_{0})}{f'(x_{0})}}&=&0{,}5-{\frac {\cos(0{,}5)-0{,}5^{3}}{-\sin(0{,}5)-3\times 0{,}5^{2}}}&=&1{,}112141637097\\x_{2}&=&x_{1}-{\frac {f(x_{1})}{f'(x_{1})}}&&\vdots &=&{\underline {0}}{,}909672693736\\x_{3}&&\vdots &&\vdots &=&{\underline {0{,}86}}7263818209\\x_{4}&&\vdots &&\vdots &=&{\underline {0{,}86547}}7135298\\x_{5}&&\vdots &&\vdots &=&{\underline {0{,}8654740331}}11\\x_{6}&&\vdots &&\vdots &=&{\underline {0{,}865474033102}}\end{matrix}}$

Oikeat desimaalit on yllä olevassa esimerkissä alleviivattu. x₆:n kaikki merkityt desimaalit ovat oikeita. Voidaan huomata, että pilkun jälkeisten oikeiden desimaalien lukumäärä kasvaa x₃:n kahdesta viiteen ja sitten kymmeneen.

Newtonin menetelmää esittelevässä animaatiossa toistetaan algoritmia viisi kertaa. Tulos on lähellä oikeaa nollakohtaa.

Historia

Newtonin menetelmän kuvasi Isaac Newton teoksissaan De analysi per aequationes numero terminorum infinitas (kirjoitettu 1669, julkaistu 1711) ja De metodis fluxionum et serierum infinitarum (kirjoitettu 1671, julkaistu nimellä Method of Fluxions 1736) Näissä teoksissa esitetty kuvaus eroaa kuitenkin nykyisestä, yllä esitetystä menetelmästä: Newton sovelsi menetelmää ainoastaan polynomeihin. Hän ei myöskään laskenut peräkkäisiä likiarvoja x_n, vaan polynomijonoja päätyen vasta lopussa nollakohdan likiarvoon. Lisäksi Newton piti menetelmää puhtaasti algebrallisena eikä havainnut sen yhteyttä differentiaalilaskentaan. Isaac Newton luultavasti johti menetelmänsä samankaltaisesta mutta epätarkemmasta François Viète'n menetelmästä. Viète'n menetelmän perusta löytyy persialaisen matemaatikon Sharaf al-Din al-Tusin työstä.

Heron Aleksandrialainen käytti samankaltaista menetelmää kirjassa 1, luvussa 8 teoksessaan Metrica määrittääkseen luvun 720 neliöjuurta.

Newtonin menetelmän julkaisi ensimmäisenä John Wallis vuonna 1685 teoksessa A Treatise of Algebra both Historical and Practical. Joseph Raphson julkaisi yksinkertaistetun kuvauksen menetelmästä vuonna 1690 teoksessa Analysis aequationum universalis. Myös hän piti menetelmän puhtaasti algebrallisena rajoittaen sen käytön polynomeihin, mutta otti käyttöön peräkkäiset approksimaatiot likiarvoille x_n. Ensimmäisenä Newtonin menetelmän kuvasi iteratiivisessa muodossa Thomas Simpson vuonna 1740.

Käytännön huomioita

Yleisesti ottaen Newtonin menetelmän virheen suuruus korottuu toiseen potenssiin joka askeleen jälkeen. Tämä tarkoittaa sitä, että tarkkojen desimaalien lukumäärä kaksinkertaistuu joka askeleella. Tämä ei kuitenkaan toimi joissakin tapauksissa. Ensinnäkin, Newtonin menetelmä vaatii derivaatan laskemista. Joissain tilanteissa sekanttimenetelmä on tehokkaampi. Toiseksi, jos alkuarvo on liian kaukana nollakohdasta, Newtonin menetelmä saattaa hajaantua. Kolmanneksi, jos etsitty nollakohta on moninkertainen, suppenemisnopeus on vain lineaarinen.

Vastaesimerkkejä

Näissä esimerkeissä etsitty juuri on nolla yksinkertaisuuden takia. Se voisi olla mikä tahansa muukin.

• Jos derivaatta ei ole jatkuva nollakohdassa, suppenemista ei välttämättä tapahdu.

Olkoon

$f(0)=0\!$

ja

$f(x)=x+x^{2}\sin(2/x)\!$

muualla.

Tällöin

$f'(0)=1\!$

ja

$f'(x)=1+2x\sin(2/x)-2\cos(2/x)\!$

muualla.

Juuren missä tahansa ympäristössä derivaatta muuttaa merkkiään, kun x lähestyy nollaa oikealta (tai vasemmalta) samalla kun $f(x)\geq x-x^{2}>0\!$ kaikille $0<x<1\!.$

Näin ollen Newtonin menetelmä ei suppene, vaikka funktio on kaikkialla derivoituva.

• Jos nollakohdassa ei ole toista derivaattaa, suppenemisnopeus ei ole verrannollinen toiseen potenssiin.

Olkoon

$f(x)=x+x^{4/3}\!$

Tällöin

$f'(x)=1+(4/3)x^{1/3}\!$

ja

$f''(x)=(4/9)x^{-2/3}\!$

paitsi kun $x=0\!$, jossa se ei ole määritelty. Kun valitaan $x_{n}\!$, $x_{n+1}=x_{n}-f(x_{n})/f'(x_{n})=(1/3)x_{n}^{4/3}/(1+(4/3)x_{n}^{1/3})\!$, joka on noin 4/3 kertaa niin tarkka kuin $x_{n}\!$. Tämä on vähemmän kuin kaksinkertainen tarkkuus.

Näin ollen Newtonin menetelmän suppenemisnopeus ei ole verrannollinen toiseen potenssiin, vaikka funktio onkin derivoituva kaikkialla.

• Jos funktion ensimmäinen derivaatta nollakohdassa on nolla, suppenemisnopeus ei ole verrannollinen toiseen potenssiin.

Olkoon

$f(x)=x^{2}\!$

Tällöin $f'(x)=2x\!$ ja $x-f(x)/f'(x)=x/2\!$. Näin ollen suppenemisnopeus ei ole verrannollinen toiseen potenssiin, vaikka funktion onkin äärettömän monta kertaa derivoituva kaikkialla.

Kirjallisuutta

• Kaleva, Osmo: Numeerinen analyysi. Opintomoniste 163. Tampere: TTKK, 1993. ISBN 951-721-941-5.

Aiheesta muualla

• Newton's method on Wolfram.com (englanniksi)
• Animations for Newton's method (englanniksi)
• Newton's method on the Mathcad Application Server (with animation) (englanniksi)
• Newton-Raphson Method Notes, PPT, Mathcad, Maple, Matlab, Mathematica at Holistic Numerical Methods Institute (englanniksi)
• Worked example (englanniksi)