See on masintõlge ja ingliskeelne tekst on originaal. Loe originaali
Newtoni meetod võib iga sammuga oma vea kahekordistada, kuigi vastus oli vaid 0,01 kaugusel
Alustage lahendist 0,01 kaugusel. Kakskümmend sammu hiljem olete väärtuse juures −5242,88 ning iga samm arvutati õigesti.
Lahendage x³ − x − 2 = 0. Puudub meelespidamist vääriv lihtne valem, seega tehke nõnda, nagu teeb iga numeeriline tarkvara: pakkuge alglähend ja laske Newtoni meetodil seda korrigeerida.
Alustage väärtusest 1,5. Kolm iteratsiooni hiljem on tulemuseks 1,52138 ning funktsiooni väärtus selles punktis on 5,89387 × 10⁻⁷ — vähem kui miljondiku kaugusel nullist. Kolm sammu. Iga samm umbes kahekordistab õigete numbrite arvu, mis ongi põhjus, miks see meetod sisaldub teie taskuarvutis, CAD-tarkvaras ja tabelarvuti võrrandilahendajas.
Nüüd küsige selle käest midagi lihtsamat. Lahendage ∛x = 0.
Te teate vastust. See on null ja see on ainus lahend. Alustage väärtusest 0,01 — mis on juba sajandiku piires — ja vaadake:
0,01 → −0,02 → 0,04 → −0,08 → 0,16 → −0,32 → 0,64 → −1,28 → 2,56 → …
Pärast kahtekümmet iteratsiooni on hinnanguks −5242,88. Jääk, mis algas väärtuselt 0,215, on nüüd 17,37. Meetod ei ole takkerdunud ega ekslema läinud; see on eemaldunud vastusest täiesti loogilist sirgjoont pidi, kahekordistades vea ja vahetades märki igal sammul.
Midagi ei läinud valesti
Tekib kiusatus otsida viga programmikoodist. Kuid viga pole, ja see arvutus tasub ise läbi teha, sest see on nõnda 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 hinnang on x − 3x = −2x. Mitte ligikaudselt, vaid täpselt. Iga iteratsioon korrutab hinnangut arvuga −2, mistahes algpunktist alates ja igavesti. Sealt pärinebki −5242,88 — see on 0,01 × (−2)19, ja te võite kogu geomeetrilise jada välja lugeda iteratsioonitabelist tööriistas Newton's Method Explorer selle eelseadistuse diverge alt.
Kuupjuur on murdnud eelduse, millele meetod tugineb. Newtoni meetod asendab kõvera selle puutujasirgega ning hüppab kohta, kus see sirge lõikab nulli. Lahendi lähedal on see suurepärane lähendus — see on Taylori rea esimene liige ja eiratud liikmed kahanevad kvadraatselt, mis ongi täpne põhjus, miks numbrite arv kahekordistub. Kuid funktsioonil ∛x on nullis vertikaalne puutuja. Selle tuletis ei muutu seal mitte pelgalt väikeseks, vaid muutub lõpmatuks, ning kõver ei ole ühegi suurenduse all lokaalselt sirge. Puutujasirged nulli lähedal suunduvad peaaegu otse üles, mistõttu koht, kus need telge lõikavad, on algpunktist peaaegu kolm korda kaugemal kui koht, kust alustasite.
Jälgige tabelis kahte kõrvuti asetsevat veergu: f(x) kasvab, samal ajal kui f′(x) kahaneb väärtuse 0,001 suunas. Samm on nende jagatis, seega kasvab see kahekordselt.
Teine ebaõnnestumine on hullem, sest see näeb välja nagu õnnestumine
Hajumine vähemalt annab endast märku. Siin on aga juhtum, mis seda ei tee.
Võtkem f(x) = x³ − x, mille nullkohad on −1, 0 ja +1. Alustage väärtusest 0,57. Meetod koondub puhtalt, kolmteist iteratsiooni, jääk 2,3 × 10⁻¹¹ — ning lahend, mille see tagasi annab, on −1.
Vaadake, kus 0,57 paikneb. See on 0,43 kaugusel väärtusest +1 ja 1,57 kaugusel väärtusest −1. Samuti on see vaid 0,57 kaugusel nullis asuvast lahendist. Newtoni meetod tagastab lahendi, mis on kõige kaugemal, sõites otse mööda kahest lähemast lahendist, ning teatab täielikust õnnestumisest üheteistkümne õige komakohaga.
Nüüd alustage hoopis väärtusest 0,58. Viisteist iteratsiooni ja vastus on +1.
Vaid sajandikuline muutus alglähendis, ja lahendaja maandub funktsiooni täiesti teises otsas. Nende kahe algpunkti 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ähenege sellele punktile kummalt poolt tahes ja esimene samm on hiiglaslik, vastassuundades. Kõvera iga lame koht on stardipadi, ja piirkond, kuhu see teid paiskab, ei ole kuidagi seotud vahetu lähedusega.
See ongi omadus, mis teeb küsimusest "millise lahendi ma saan?" üldjuhul vastamatu küsimuse. Komplekssarvude hulgal määratud polünoomide puhul nimetatakse iga lahendini viivate algpunktide hulki tõmbebasseinideks ning nende piirid on fraktaalsed: suvaliselt lähedal punktile, mis koondub ühte lahendisse, paikneb punkt, mis koondub teise. Hubbard, Schleicher ja Sutherland näitasid 2001. aastal, et sellest hoolimata on võimalik konstrueerida algpunktide lõplik hulk, mis garanteerib antud polünoomi iga lahendi leidmise — see on märkimisväärne tulemus ning näitab, kui palju tööd soovitus "kasuta lihtsalt Newtoni meetodit" vaikimisi enda taha peidab.
Mida see muudab selle kasutamisel
Siit tuleneb kolm praktilist järeldust ning need kõik kolm on sellel lehel nähtavad.
Esiteks ei ole väike jääk veel garantii. Ülaltoodud käivituses diverge on jääk 17,37 ja kasvab, nii et see ebaõnnestumine on ilmselge. Kuid käivituses 0,57 on jääk 2 × 10⁻¹¹ ning vastus on täiesti sobiv lahend — lihtsalt mitte see, mida keegi küsis. Koonduvuskontrollid võivad teile öelda, et olete leidnud ühe lahendi. Mitte miski selles meetodis ei saa aga öelda, et see on see ainus õige lahend.
Teiseks on iteratsioonide piirarvud kandva tähtsusega. Uurija peatub vaikimisi kahekümne juures, mis on ainus põhjus, miks hajuval käivitusel on lõpp, mitte arvuline ületäitumine. Praktilises tarkvaras kasutatavad lahendajad teevad sama ning see arv ei ole suvaline: korrektselt toimiv Newtoni iteratsioon hästikäituval funktsioonil saavutab masintäpsuse viie kuni kümne sammuga, seega mis tahes arvutus, mis veel kahekümne juures töötab, ei koondu mitte aeglaselt, vaid ei koondu üldse.
Kolmandaks ei ole halva alglähendi paranduseks tavaliselt mitte parem algoritm, vaid eraldusvahemik. Lõigu poolitamise meetod ei saa hajuda — kui funktsioon muudab lõigul märki, ei saa keskpunkti reegel sellest väljuda — ega saa valida valet lahendit, sest vahemiku sees on vaid üks lahend. See on lihtsalt aeglane, võites ühe biti sammu kohta, selle asemel et kahekordistada numbrite arvu. Enamik reaalseid võrrandilahendajaid kasutab seetõttu hübriidmetoodikat: poolitatakse lõiku seni, kuni hinnang on tõestatavalt lähedal, ning lastakse siis Newtoni meetodil kolme sammuga lõpetada. Te saate kiiruse seal, kus eeldused kehtivad, ja garantii seal, kus need ei kehti.
Nime kohta on veel üks märkus. Newtoni enda meetod umbes 1669. aastast ei kasutanud tuletisi ja oli kirjutatud polünoomide jaoks substitutsioonide jada kujul; Raphson lihtsustas seda 1690. aastal; täna õpetatav kuju koos tuletisega f′ ja suvalise diferentseeruva funktsiooniga f pärineb Simpsonilt 1740. aastast. Ypma kaardistas kogu selle kujunemisloo 1995. aastal. See asi, mis kuupjuure puhul nii õpetlikult ebaõnnestub, on üheksateistkümnenda sajandi viimistlus seitsmeteistkümnenda sajandi retseptist ja see on olnud igas numeerilises tööriistakastis sellest ajast peale — mis ongi põhjus teada täpselt, kus see katki läheb.