Newtonin iteraatio ja kaoottisuus

 

Yhtälön $f(x) = 0$ ratkaiseminen Newtonin iteraatiolla

Jos yhtälön $f(x) = 0$ ratkaiseminen ei onnistu algebrallisella manipuloinnilla, voi yrittää ratkaisun likarvon etsimistä jollakin numeerisella menettelyllä. Toisen asteen yhtälön ratkaiseminen algebrallisesti tunnetusti onnistuu, kolmas aste on jo vaikeampi (vaikkei mahdoton). Ehkä tunnetuin numeerinen menetelmä on Newtonin iteraatio, jossa lähdetään jostakin ratkaisun $x^*$ likiarvosta $x_0$ ja tarkennetaan tätä askel askeleelta. Periaatteena on asettaa käyrälle $y = f(x)$ tangentti pisteeseen $(x_0,f(x_0))$ ja etsiä tarkempi likiarvo tangentin ja x-akselin leikkauspisteestä $x_1$. Toistamalla askel uudesta likiarvosta $x_1$ lähtien saadaan seuraava likiarvo $x_2$ jne. Tuloksena on lukujono $x_0,\ x_1,\ x_2,\ \dots$, joka suppenee kohden ratkaisua $x^*$, jos alkuarvo $x_0$ on ollut riittävän lähellä.

Iteraatiokaavaksi, jolla seuraava likiarvo lasketaan edellisestä, saadaan
$$x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$$
muodostamalla edellä mainitun tangentin yhtälö.

Lukija voi kokeilla vaikkapa yhtälön $x^4 - 2 = 0$ ratkaisemista eri alkuarvoista $x_0$ lähtien.

Newtonin menetelmä voidaan monella tavoin yleistää. Periaatteessa samalla idealla voidaan ratkaista esimerkiksi kahden tuntemattoman yhtälöpari $f(x,y) = 0,\ g(x,y) = 0$ tai etsiä kompleksilukuratkaisu yhtälölle $f(z) = 0$. Jälkimmäisessä tapauksessa toimii sama iteraatiokaava kuin edellä, vaikka sen johtamisessa ei voidakaan käyttää samaa tangentti-ideaa.

Jos yhtälöllä on useita ratkaisuja, saadaan yleensä tietty ratkaisu aloittamalla riittävän lähellä olevasta likiarvosta. Newtonin menetelmän ominaisuus kuitenkin on, että suppeneva jono saadaan aloittamalla melkein mistä tahansa pisteestä, mutta ei ole niinkään helppoa sanoa, mitä ratkaisua kohden jono suppenee.

Yhtälöllä $z^3 - 1 = 0$ on kompleksitasossa kolme ratkaisua: $z = 1$, $z = -\frac{1}{2}(1-i\sqrt{3})$ ja $z = -\frac{1}{2}(1+i\sqrt{3})$. Aloittamalla Newtonin iteraatio jostakin kompleksitason pisteestä saadaan melkein aina jono, joka suppenee kohden jotakin ratkaisua. Mikä näistä on kyseessä, vaihtelee kuitenkin kaoottisella tavalla. Jos ratkaisuja em. järjestyksessä kutsutaan punaiseksi, vihreäksi ja siniseksi ratkaisuksi ja aloituspiste väritetään sen mukaan, mitä ratkaisua kohden jono suppenee, saadaan oheinen kuva. Mitä vaaleampi värisävy, sitä nopeammin jono on supennut.

Suppenemisalueet erivärisiin juuriin

Moni on varmaankin nähnyt kuvan, sillä se on julkaistu lukemattomia kertoja niin painetuissa kuin verkkodokumenteissakin. Oheinen on tehty Takashi Kanamarun vapaasti jakamalla ohjelmalla. Kyseessä on esimerkki kaoottisesta käyttäytymisestä tai fraktaaleista: tietyissä kohdissa pienikin muutos aloituspisteessä muuttaa suppenemisen kohdetta; rakenne toistuu periaatteessa samanlaisena yhä pienemmissä mittakaavoissa.

Osasuurennos edellisestä kuvasta

Suppeneminen ei välttämättä tapahdu kovin suoraviivaisesti, vaan heilahtelua saattaa olla, kuten alla oleva kuva osoittaa. Laskenta ja animointi on tehty Mathematicalla. Animaatiosta on saatavissa myös video, jossa aloituspiste liikkuu hitaasti punaisen aloitusympyrän sisällä ja likiarvopisteiden muodostama jono heilahtelee voimakkaasti. Eräänlainen epäjatkuvuusilmiö tämäkin.

Ratkaisua $z^*$ lähestyvä likiarvojono, kun alkupisteenä on $z_0$