Fixpunktsiteration

Fixpunktsiteration är ett, vanligtvis ineffektivt, sätt att lösa ekvationer på. Iden är emellertid enkel. Antag att vi vill lösa andragradsekvationen

$$x(x+2) =8.$$

Vi börjar då med att skriva om ekvationen så att vi få r ett $x$ i vänsterledet, genom att dividera med $(x+2)$

$$x = \frac{8}{x+2}.$$

Ekvationen har nu formen

$$x = g(x),$$

där $g(x) = 8/(x+2)$. Om $x^*$ betecknar den exakta lösningen till $x(x+2)=8$ har vi tydligen $x^*=g(x^*)$.

Nästa steg är att gissa en approximation till $x^*$, t.ex. $x_0=4$ och evaluera $g(x_0)=g(4)$. Vi får då

$$g(x_0)=g(4)=\frac{8}{2+x_0}=\frac{4}{3}=1.75.$$

Förhoppningen är nu att detta värde, som vi fortsättningsvis kallar $x_1$ skall vara en bättre approximation till $x^*$ än $x_0$. Det finns inget som styrker att detta antagande är sant just nu, men om det är så, så borde ju $x_2=g(x_1)$ vara en ännu bättre approximation till $x^*$. Alltså, låt oss också räkna ut $g(x_1)$. Vi får

$$g(x_1)=g(4/3)=\frac{8}{2+x_1}=2.40,$$

som vi kallar $x_2$, och tror är den bästa approximation till $x^*$ som vi hittils räknat ut.

Håller vi nu på så här genereras en sekvens med tal,

$$x_1 = g(x_0), \quad x_2 = g(x_1), \quad x_3 = g(x_2), \quad x_4 = g(x_3), \ldots$$

som vi hoppas konvergerar mot $x^*$ om $n$ är stort. Detta kallas fixpunktsiteration.