Ero sivun ”Newtonin menetelmä” versioiden välillä

Wikipediasta
Siirry navigaatioon Siirry hakuun
[arvioimaton versio][arvioimaton versio]
Poistettu sisältö Lisätty sisältö
Kasirbot (keskustelu | muokkaukset)
p r2.7.1) (Botti lisäsi: fa:روش نیوتن
p Botti poisti 27 Wikidatan sivulle d:q374195 siirrettyä kielilinkkiä
Rivi 100: Rivi 100:
{{Link GA|de}}
{{Link GA|de}}
{{Link GA|ru}}
{{Link GA|ru}}

[[af:Newton-Raphson metode]]
[[ar:طريقة نيوتن]]
[[id:Metode Newton]]
[[bg:Метод на Нютон]]
[[ca:Mètode de Newton]]
[[cs:Metoda tečen]]
[[da:Newtons metode]]
[[de:Newton-Verfahren]]
[[el:Μέθοδος Νιούτον]]
[[en:Newton's method]]
[[es:Método de Newton]]
[[fa:روش نیوتن]]
[[fr:Méthode de Newton]]
[[ko:뉴턴의 방법]]
[[it:Metodo delle tangenti]]
[[he:שיטת ניוטון-רפסון]]
[[hu:Newton-módszer]]
[[nl:Methode van Newton-Raphson]]
[[ja:ニュートン法]]
[[pl:Metoda Newtona]]
[[pt:Método de Newton]]
[[ru:Метод Ньютона]]
[[simple:Newton's method]]
[[sl:Newtonova metoda]]
[[sv:Newtons metod]]
[[uk:Метод Ньютона]]
[[zh:牛顿法]]

Versio 15. maaliskuuta 2013 kello 22.58

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. 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 xn. Siitä saadaan parempi likiarvo xn+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

.

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

.

Iterointi aloitetaan valitsemalla jokin näennäisen satunnainen alkuarvo x0 (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 xn on päästy arvoa x lähempänä olevaan arvoon xn+1.

Kuva Newtonin menetelmän yhdestä iteraatiosta. Tästä nähdään, että on funktion nollakohdalle parempi likiarvo kuin

Esimerkki

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

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

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 xn, 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 xn. 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

ja

muualla.

Tällöin

ja

muualla.

Juuren missä tahansa ympäristössä derivaatta muuttaa merkkiään, kun x lähestyy nollaa oikealta (tai vasemmalta) samalla kun kaikille

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

Tällöin

ja

paitsi kun , jossa se ei ole määritelty. Kun valitaan , , joka on noin 4/3 kertaa niin tarkka kuin . 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

Tällöin ja . Näin ollen suppenemisnopeus ei ole verrannollinen toiseen potenssiin, vaikka funktion onkin äärettömän monta kertaa derivoituva kaikkialla.

Aiheesta muualla

Malline:Link GA Malline:Link GA