Simo K. Kivelä, 28.8.2009

Kaoottinen Newtonin iteraatio

Muotoa f(x)=0 oleva yhtälö voidaan yleensä ratkaista Newtonin iteraatiolla

(Subscript[x, n+1])=(Subscript[x, n])-((f((Subscript[x, n])))/(f'((Subscript[x, n])))),

kunhan aloitusarvo (Subscript[x, 0]) valitaan kyllin läheltä etsittävää ratkaisua. Iteraatiokaava johdetaan yleensä vain reaalialueella, mutta se toimii paljon yleisemminkin: kyseessä voi esimerkiksi olla derivoituva kompleksifunktio f, jonka kompleksisia nollakohtia etsitään.

Miten iteraatio sitten toimii, jos aloitetaan mielivaltaisesta pisteestä, joka ei välttämättä ole lähellä mitään yhtälön ratkaisua?

Alla oleva esimerkki käsittelee polynomiyhtälöä (z^3)-1=0 kompleksitasossa. Tällä on kolme juurta: (Subscript[z, 1])=1, (Subscript[z, 2])=-(1/2)(1+i (Sqrt[3])), (Subscript[z, 3])=-(1/2)(1-i (Sqrt[3])). Nämä on merkitty punaisilla pisteillä. Iteraation aloituspiste on merkitty punaisella symbolilla ⊗, ja sitä voidaan siirtää hiirellä. Vaihtoehtoisesti aloituspisteen koordinaatteja voidaan muuttaa liukusäätimillä tai niiden alla olevilla painikkeilla. Koordinaatit voidaan myös antaa syöttökenttiin numeerisesti; tämä ei toimi Mathematica Playerissa. Iteraation peräkkäiset approksimaatiot — iteraatit — on esitetty pienenevillä mustilla pisteillä, jotka järjestyksen osoittamiseksi on yhdistetty murtoviivalla. Aloituspisteen sijainnista riippuen iteraatit poukkoilevat yllättävilläkin tavoilla.

Esitettävien iteraattien määrä ja kuva-alueen koko voidaan valita painikkeilla. Kuvan yläpuolella olevassa taulussa esitetään aloituspiste kompleksilukuna, samoin 20. iteraatti. (Enempää ei lasketa eikä määrää voida muuttaa.)

Lukija siirrelköön aloituspistettä ja tutkikoon iteraatioprosessin kaoottisuutta!

Tehtäviä

1) Määritä suurin piirtein ne juuria (punaiset pisteet) ympäröivät alueet, joista lähdettäessä iteraatio nopeasti suppenee kohden kyseistä juurta.

2) Paina näyttöpaneelin oikeassa ylänurkassa olevaa plusmerkkiä ja valitse avautuvasta valikosta init1, init2 tai init3. Näihin on valmiiksi määritelty aloituspiste. Huomio?

3) Tasossa on alueita, joissa hyvinkin lähellä toisiaan olevista aloituspisteistä lähdettäessä iteraatio suppenee kohden eri juuria. Missä tällaisia alueita on?

4) Jos aloituspiste on reaaliakselilla, kaikki iteraatit ovat reaaliakselilla ja ainakin näyttävät suppenevan kohti reaalista juurta z=1. Löytyykö kahden muun juuren tapauksissa reaaliakselia vastaavaa suoraa, jolla kaikki iteraatit ovat?

5) Suppeneeko iteraatio aina kohden jotakin juurta aloituspisteestä riippumatta?

6) Kokeile valmiiksi määriteltyjä vaihtoehtoja init4 ja init5. Mitä tapahtuu?