Tegemist on masintõlkega; ingliskeelne tekst on originaal. Loe originaali
Newtoni meetod võib oma viga igal sammul kahekordistada, ja lahend oli 0,01 kaugusel
Alusta lahendist 0,01 kaugusel. Kakskümmend sammu hiljem oled kohal −5242,88, ja iga samm arvutati õigesti.
Lahenda x³ − x − 2 = 0. Siin pole meeldejätmist väärt kena valemit, seega tee seda, mida teeb iga arvutustarkvara: paku väärtus ja lase siis Newtoni meetodil seda parandada.
Alusta väärtusest 1,5. Kolm iteratsiooni hiljem on sul 1,52138 ning funktsiooni väärtus selles punktis on 5,89387 × 10⁻⁷, vähem kui miljondiku kaugusel nullist. Kolm sammu. Iga samm ligikaudu kahekordistab õigete numbrite arvu, mistõttu on see meetod sinu taskuarvutis, sinu CAD-tarkvaras ja sinu tabelarvutusprogrammi lahendajas.
Nüüd küsi sellelt midagi lihtsamat. Lahenda ∛x = 0.
Sa tead vastust. See on null, ja see on ainus. Alusta väärtusest 0,01 — juba sajandiku kaugusel — ja vaata:
0,01 → −0,02 → 0,04 → −0,08 → 0,16 → −0,32 → 0,64 → −1,28 → 2,56 → …
Pärast kahtekümmet iteratsiooni on lähend −5242,88. Jääk, mis algas väärtuselt 0,215, on nüüd 17,37. Meetod ei ole takerdunud ega ekslema läinud; see on eemaldunud lahendist täiesti sirgjoonelise loogikaga, kahekordistades vea ja vahetades märki igal üksikul sammul.
Midagi ei läinud valesti
Tekib kiusatus otsida viga. Seda pole, ja see arvutus tasub läbi teha, sest see on nii lühike.
Newtoni samm on x − f(x)/f′(x). Funktsiooni f(x) = x1/3 korral on tuletis (1/3)x−2/3, seega
f(x)/f′(x) = x1/3 ÷ ⅓x−2/3 = 3x
ja järgmine lähend on x − 3x = −2x. Mitte ligikaudselt: täpselt. Iga iteratsioon korrutab lähendit arvuga −2 mistahes alguspunktist, igavesti. Sealt tulebki −5242,88: see on 0,01 × (−2)19, ja kogu geomeetrilist jada saab vaadata iteratsioonitabelist tööriistas Newton's Method Explorer selle eelseadistuse diverge alt.
Kuupjuur on rikkunud eelduse, millel meetod põhineb. Newtoni meetod asendab kõvera selle puutujaga ning hüppab kohta, kus see sirge lõikab nulli. Nullkoha lähedal on see suurepärane lähendus: see on Taylori rea esimene liige ning kõrvalejäetud liikmed kahanevad ruutudena, mis ongi täpselt põhjus, miks numbrite arv kahekordistub. Kuid funktsioonil ∛x on nullis vertikaalne puutuja. Selle tuletis ei muutu seal pelgalt väikeseks, vaid muutub lõpmatuks, ning kõver ei ole üheski suurenduses lokaalselt sirge. Nulli lähedal osutavad puutujad peaaegu otse üles ning telje lõikepunkt satub ikkagi kohale −2x: kaks korda kaugemale nullkohast kui alguses, teisel pool telge.
Vaata tabelis kahte kõrvuti asuvat veergu: f(x) kasvab, samal ajal kui f′(x) kahaneb väärtuse 0,001 suunas. Samm on nende suhe, seega kasvab see kahekordselt.
Teine nurjumine on hullem, sest see näeb välja nagu õnnestumine
Hajumine annab endast vähemalt märku.
Võtame f(x) = x³ − x, mille nullkohad on −1, 0 ja +1. Alusta väärtusest 0,57. Meetod koondub puhtalt, kolmteist iteratsiooni, jääk 2,3 × 10⁻¹¹ — ja lahend, mille see tagastab, on −1.
Vaata, kus 0,57 asub. See on 0,43 kaugusel väärtusest +1 ja 1,57 kaugusel väärtusest −1. Samuti on see vaid 0,57 kaugusel nullis asuvast nullkohast. Newtoni meetod tagastab neist kõige kaugema, purjetades otse mööda kahest lähemal asuvast nullkohast, ja teatab täielikust edust üheteistkümne õige kümnendkohaga.
Alusta nüüd selle asemel väärtusest 0,58. Viisteist iteratsiooni, ja vastus on +1.
Algse pakkumise muutmine vaid ühe sajandiku võrra, ja lahendaja maandub funktsiooni vastasotsas. Nende kahe alguspunkti vahel on 1/√3 ≈ 0,5774, kus funktsiooni x³ − x tuletis on null. Puutuja on seal horisontaalne ega lõika telge kuskil läheduses; lähene sellele punktile kummalt poolt tahes ja esimene samm on hiiglaslik, vastassuundades. Iga lame koht kõveral on stardiplatvorm, ning piirkonnal, kuhu see sind lennutab, pole lähedusega mingit pistmist.
Just see omadus teeb küsimusest „millise lahendi ma saan?“ üldjuhul vastamatu küsimuse. Kompleksarvude vallas nimetatakse iga lahendini viivate alguspunktide hulki atraktori basseinideks ning nende piirid on fraktaalsed: kuitahes lähedal punktile, mis koondub ühe lahendi poole, asub punkt, mis koondub teise poole. Hubbard, Schleicher ja Sutherland näitasid 2001. aastal, et sellest hoolimata on võimalik konstrueerida lõplik alguspunktide hulk, mis tagab antud polünoomi iga juure leidmise. Tõeline saavutus ning mõõt sellele, kui palju tööd peidab endas vaikselt soovitus „kasuta lihtsalt Newtoni meetodit“.
Mida see muudab meetodi kasutamisel
Siit järeldub kolm praktilist tagajärge, ja kaks esimest on näha siinsamas lehel.
Esiteks, väike jääk ei ole garantiikiri. Ülaltoodud diverge katses on jääk 17,37 ja kasvab, seega see juhtum tabatakse. Kuid katses väärtusega 0,57 on jääk 2 × 10⁻¹¹ ja vastus on täiesti korrektne lahend, lihtsalt mitte see, mida keegi küsimust esitades soovis. Koonduvustestid saavad öelda, et oled leidnud ühe lahenduse. Mitte miski selles meetodis ei saa öelda, et see on see õige lahendus.
Teiseks on iteratsioonide arvu piirangud kriitilise tähtsusega. Tööriist peatub vaikimisi kahekümne juures, mis on ainus põhjus, miks hajuval katsel on lõpp, mitte ületäitumine. Tööstuslikud lahendajad teevad sama, ja see arv pole suvaline: terve Newtoni iteratsioon hästikäituval funktsioonil saavutab masintäpsuse viie kuni kümne sammuga, seega kõik, mis veel kahekümne juures töötab, ei koondu aeglaselt, vaid ei koondu üldse.
Kolmandaks ei ole halva alguspunkti lahenduseks tavaliselt parem algoritm, vaid lahendi eraldamine vahemikuga. Lõigu poolitamine ei saa hajuda — kui funktsioon muudab vahemikus märki, ei saa keskpunkti reegel sealt väljuda — ja see ei saa valida valet lahendit, sest vahemikus on ainult üks lahend. See on kõigest aeglane, võites ühe biti sammu kohta, selle asemel et numbreid kahekordistada. Enamik tegelikke lahendajaid kasutab seetõttu hübriidi: poolitavad lõiku seni, kuni lähend on tõestatavalt lähedal, ja lasevad siis Newtoni meetodil töö kolme sammuga lõpetada. Sa saad kiiruse seal, kus eeldused kehtivad, ja garantii seal, kus need ei kehti.
Nime kohta on üks märkus. Newtoni enda meetod umbes 1669. aastast ei kasutanud tuletisi ning oli kirjutatud polünoomide jaoks asenduste jadana; Raphson lihtsustas seda 1690. aastal; tänapäeval õpetatav kuju, kus on f′ ja suvaline diferentseeruv f, pärineb Simpsonilt 1740. aastast. Ypma kaardistas kogu selle kujunemisloo 1995. aastal. See, mis kuupjuure korral nii õpetlikult ebaõnnestub, on 17. sajandi retsepti 18. sajandi viimistlus, ning see on kuulunud sestsaadik igasse numbrilisse tööriistakasti — mis ongi põhjus teada täpselt, kus see murdub.