Newtonin menetelmä (Newton–Raphson): määritelmä ja kaava
Helppo-opas Newtonin menetelmään (Newton–Raphson): määritelmä, kaava ja vaiheittainen esimerkki derivaatan avulla funktion nollakohtien löytämiseen.
Newtonin menetelmä tarjoaa tehokkaan tavan löytää funktion reaaliset nollakohdat. Tätä iteratiivistä algoritmia kutsutaan usein Newton–Raphson-menetelmäksi (tai yksinkertaisesti Newtonin menetelmäksi) ja se on nimetty Sir Isaac Newtonin ja Joseph Raphsonin mukaan.
Perusidea ja kaava
Menetelmä käyttää funktion derivaattaa juuren löytämiseen. Valitaan alkuarvaus x0 ja lasketaan peräkkäisiä arvioita kaavalla
Tässä xn on nykyinen arvio ja xn+1 seuraava arvio. Perusajatuksena on korvata funktio sen tangentilla kohdassa xn ja käyttää tangenttisuoran ja x-akselin leikkauspistettä seuraavana arviona:
- lasketaan f(xn) ja f′(xn),
- päivitetään xn+1 = xn − f(xn)/f′(xn).
Kuinka menetelmä etenee käytännössä
Toistamalla yllä olevan askeleen saadaan jono {x0, x1, x2, ...}. Jos arvioiden arvo lähestyy juurta r, menetelmää sanotaan konvergoivan kohti r:ää. Lopetusehdoksi käytetään yleensä jotakin seuraavista:
- |f(xn)| < tol (funktion arvon toleranssi),
- |xn+1 − xn| < tol (muutoksen toleranssi),
- suoritettujen iteraatioiden määrä ylittää ennalta asetetun maksimin.
Yksinkertainen esimerkki
Etsitään funktion f(x) = x² − 2 nollakohta (eli sqrt(2)). Valitaan x0 = 1:
- x1 = 1 − (1² − 2)/(2·1) = 1.5
- x2 = 1.5 − (1.5² − 2)/(2·1.5) ≈ 1.4166666667
- x3 ≈ 1.4142156863
Jo muutamalla iteraatiolla saavutetaan hyvin tarkka likiarvo sqrt(2) ≈ 1.41421356.
Konvergenssi ja vaatimukset
- Quadratic-konnevgenssi: Kun alkuarvaus on riittävän lähellä yksinkertaista juurta (f(r) = 0 ja f′(r) ≠ 0) ja f on riittävän sileä, Newtonin menetelmä on toisen kertaluvun (kvadraattinen) konvergoiva. Tämä tarkoittaa, että virhe pienenee likimäärin toisen potenssin mukaan: e_{n+1} ≈ C·e_n².
- Derivaatan ei-nolla vaatimus: Jos f′(r) = 0 (juuri on moninkertainen) konvergenssi voi olla hitaampaa tai menetelmä epäonnistuu.
- Alkuarvauksen merkitys: Jos x0 on kaukana juuresta, iterointi voi hajota, ajautua toiseen juureen tai joutua sykliin. Hyvä alkuarvaus parantaa todennäköisyyttä onnistua.
Mahdolliset ongelmat ja käytännön vinkkejä
- Jos f′(xn) = 0 tai hyvin lähellä nollaa, kaavan jako ei ole luotettava — käytä vaihtoehtoja kuten sekanttimenetelmää tai muokattua Newton-menetelmää.
- Jos iterointi käyttäytyy epästabiilisti, voidaan käyttää vaimennettua (damped) Newtonin askelta: xn+1 = xn − λ·f(xn)/f′(xn), missä 0 < λ ≤ 1 säädetään esim. line search -menetelmällä.
- Numerisessa toteutuksessa on hyvä tarkistaa maksimimäärä iteraatioita ja käyttää järkeviä toleransseja.
- Jos derivaattaa ei ole helposti saatavilla analyyttisesti, voi käyttää numeerista derivaatan approksimaatiota tai sekanttimenetelmää, joka ei tarvitse derivaattaa.
Laajennuksia
- Monimuuttujaiset järjestelmät: Newtonin menetelmä laajenee vektoriarvoisiin funktioihin käyttämällä Jacobin matriisia J(x): x_{n+1} = x_n − J(x_n)^{-1}·F(x_n), missä F on vektori. Tämä vaatii Jacobian käänteisen laskemista tai lineaarisen yhtälöryhmän ratkaisemista.
- Moninkertaiset juuret: Jos juuri on moninkertainen, voidaan käyttää muokattuja versioita, jotka parantavat konvergenssia.
Yhteenveto
Newtonin menetelmä on tehokas ja nopeasti konvergoiva tapa löytää funktioiden nollakohtia, kunhan derivaatta on käytettävissä ja alkuarvaus on riittävän lähellä juurta. Käytännössä kannattaa huomioida mahdolliset ongelmat (derivaatan nollakohta, huono alkuarvaus) ja käyttää tarvittaessa stabilointimenetelmiä tai vaihtoehtoisia numeerisia menetelmiä.
Funktiota (sininen) käytetään laskemaan tangenttisuoran (punainen) kaltevuus kohdassa x .n
Newtonin menetelmän ongelmat
Newtonin menetelmä voi löytää ratkaisun nopeasti, jos arvausarvo alkaa riittävän läheltä haluttua juurta. Kun alkuarvoitusarvo ei kuitenkaan ole lähellä, ja funktiosta riippuen Newtonin menetelmä voi löytää vastauksen hitaasti tai ei ollenkaan.
Aiheeseen liittyvät sivut
- Kantorovitšin lause (Leonid Kantorovitšin löytämä väite Newtonin menetelmän konvergenssista).
Kysymyksiä ja vastauksia
K: Mikä on Newtonin menetelmä?
V: Newtonin menetelmä on algoritmi funktion reaalisten nollakohtien löytämiseksi. Se käyttää funktion derivaattaa sen juurien laskemiseen ja vaatii nollan sijainnille alkuarvion.
K: Kuka kehitti tämän menetelmän?
V: Sir Isaac Newton ja Joseph Raphson kehittivät menetelmän, minkä vuoksi sitä kutsutaan joskus Newton-Raphson-menetelmäksi.
K: Miten tämä algoritmi toimii?
V: Tämä algoritmi toimii soveltamalla toistuvasti kaavaa, joka ottaa alkuarvion (xn) ja laskee uuden arvion (xn+1). Toistamalla tätä prosessia arvaukset lähestyvät funktion nollaa.
K: Mitä tämän algoritmin käyttäminen edellyttää?
V: Jotta voit käyttää tätä algoritmia, sinulla on oltava nollan sijaintia koskeva alkuperäinen "arvausarvo" sekä tieto annetun funktion derivaatasta.
K: Miten Newtonin menetelmä voidaan selittää graafisesti?
V: Voimme selittää Newtonin menetelmän graafisesti tarkastelemalla tangenttisuorien ja x-akselin leikkauspisteitä. Ensin lasketaan f:n tangenttisuoraa xn:ssä. Seuraavaksi etsitään tämän tangenttisuoran ja x-akselin leikkauspiste ja kirjataan sen x-paikka seuraavaksi arvioksi - xn+1.
Kysymys: Onko Newtonin menetelmää käytettäessä rajoituksia?
V: Kyllä, jos arvion alkuarvo on liian kaukana todellisesta juuresta, se voi kestää kauemmin tai jopa epäonnistua konvergoitumisessa kohti juurta, koska se heilahtaa sen ympärillä tai poikkeaa siitä.
Etsiä