Iteraatioesimerkki

Insinöörimatematiikassa törmätään usein tilanteeseen, jossa jokin yhtälö pitää ratkaista iteroimalla, koska yhtälölle ei ole suoraa ratkaisukaavaa. Iteroinnissa aluksi arvataan yhtälön juurelle (ratkaisulle) jokin arvo. Tämän jälkeen arvaus sijoitetaan sopivaan lausekkeeseen ja näin saatua arvoa käytetään parempana arvauksena. Se sijoitetaan edelleen lausekkeeseen, jolloin saadaan vielä parempi arvaus ja niin edelleen, kunnes arvaus on riittävän lähellä oikeaa arvoa. Aina arvaus ei parane joka kierroksella, mutta jos iterointimenetelmä on oikein valittu, yleensä saadut arvaukset vähitellen lähenevät oikeaa ratkaisua.

Tarkastellaan esimerkkinä käyttäjän antaman luvun x neliöjuuren laskemista Newtonin iteraatiolla. Neliöjuuren laskemista varten Python-kirjastoon on kirjoitettu valmiiksi oma funktio, joten esimerkkiohjelmamme ei ole sen vuoksi mitenkään välttämätön. Se on tässä valittu kuitenkin esimerkiksi iteroinnista yksinkertaisuutensa vuoksi.

Haluamme siis löytää luvun \(y\) siten, että \(y = \sqrt{x}\). Toisin sanoen on etsittävä funktion \(f(y) = y^2 - x\) nollakohta. Newtonin iteraatio perustuu yleisesti siihen, että jos meillä on funktion \(f(y)\) nollakohdalle arvaus \(y_n\), niin parempi arvaus \(y_{n+1}\) saadaan kaavalla

\[y_{n+1} = y_n - \frac{f(y_n)}{f'(y_n)}\]

missä \(f'(y)\) tarkoittaa funktion f derivaattaa muuttujan \(y\) suhteen. Kaava on saatu siitä, että tarkastellaan funktion \(f(y)\) tangenttia kohdassa \(y_n\) ja on laskettu, missä kohdassa tangenttisuora leikkaa x-akselin.

Kun annettuun kaavaan sijoitetaan funktio \(f(y) = y^2 - x\), ja sievennetään saatu lauseke, saadaan iterointikaavaksi

\[y_{n+1} = \frac{1}{2} (y_n + \frac{x}{y_n})\]

Tämän perusteella voidaan siis laskea muuttujan \(x\) neliöjuurelle parempi arvaus \(y_{n+1}\), kun vanha arvaus on \(y_n\). Iteraatiossa lähdetään liikkeelle mistä tahansa positiivisesta alkuarvauksesta, esimerkiksi ykkösestä.

Ohjelma tarvitsee vielä tiedon siitä, koska saatu arvaus on riittävän hyvä eli koska iterointi pitää lopettaa. Yksi yleinen menetelmä on tarkastella kahden perättäisen arvauksen välistä eroa ja lopettaa silloin, kun tämä ero on tarpeeksi pieni. Menetelmä toimii vain silloin, kun arvaus joka kierroksella lähenee oikeaa arvausta. Jos arvaukset voivat lähentyä jotain paikallista maksimia tai minimiä, joka ei ole kuitenkaan oikean ratkaisun lähellä, tällä kriteerillä saatu tulos voi olla kaukana oikeasta. Neliöjuuren hakemiseen tämä kriteeri kuitenkin sopii.

Kun tutkitaan, kuinka lähellä uusi arvaus on lähellä edellistä arvausta, on kätevää käyttää apuna itseisarvon laskemista. Etukäteen ei ole tietoa siitä, onko uusi arvaus suurempi vai pienempi kuin edellinen arvaus. Tämän vuoksi on helpointa tehdä niin, että lasketaan kahden peräkkäisen luvun välinen erotus ja otetaan siitä itseisarvo. Itseisarvon laskemiseen Pythonissa valmiina funktio abs. Luvun arvo itseisarvo voidaan laskea kirjoittamalla abs(arvo).

Neliöjuuren laskeva ohjelma on alla. Koska neliöjuurta ei ole määritelty negatiivisille luvuille, ohjelma tarkistaa ensin, että käyttäjän antama luku ei ole negatiivinen, ja laskee neliöjuuren vain ei-negatiivisille luvuille.

def main():
    TARKKUUS  = 0.0001
    rivi = input("Minka luvun neliojuuri lasketaan? ")
    x = float(rivi)
    if x < 0:
        print("Neliojuurta ei ole maaritelty negatiivisille luvuille")
    else:
        arvaus = 1.0
        uusi_arvaus = 0.5 * (arvaus + x / arvaus)
        while abs(uusi_arvaus - arvaus) > TARKKUUS:
            arvaus = uusi_arvaus
            uusi_arvaus = 0.5 * (arvaus + x / arvaus)
        print("Luvun", x, "neliojuuri on", uusi_arvaus)

main()

Esimerkki ohjelman suorituksesta:

Minka luvun neliojuuri lasketaan? 57.0
Luvun 57.0 neliojuuri on 7.54983443527

Toinen esimerkki:

Minka luvun neliojuuri lasketaan? -9.0
Neliojuurta ei ole maaritelty negatiivisille luvuille

Seuraavan animaation avulla voit vielä tutkia ohjelman suoritusta tarkemmin (animaatiossa tarkkuutta on muutettu, jotta kierrosten määrä pysyisi tarpeeksi pienenä):