Newtons metod

Newtons metod (eller Newton-Raphsons metod som den också kallas) är en av de mest populära numeriska metoderna för att lösa ekvationer och ekvationssystem.

Idén är att approximera en funktion $f$ med dess tangentlinje, dvs att titta på funktionens första ordningens Taylorutveckling:

Vi vill hitta ett nollställe till $f$, dvs ett tal $z^*$, sådant att $f(z^*) = 0$. Ovanstående approximation leder till ”ekvationen”

Newtons metod är att utgå från en startpunkt $z_0$ och därefter bilda en talföljd enligt ovan, dvs

med förhoppningen att följden $(z_k)$ konvergerar mot ett nollställe till $f$.

Man kan visa att om man startar “tillräckligt nära” ett nollställe $z^*$, så konvergerar följden mot $z^*$ (under rimliga antaganden på funktionen $f$). Vad som händer om startpunkten $z_0$ inte ligger “tillräckligt nära” $z^*$ är svårare att förutse. Betrakta som ett exempel funktionen $f(z) = z^3-1$, som har tre nollställen: $z=1$, $z=e^{2\pi i/3}$ och $z = e^{-2\pi i/3}$, markerade med grönt, blått respektive orange i nedanstående bild:

Kontrollera att talföljden $(z_k)$ verkar konvergera mot $z=1$ om du väljer $z_0$ i närheten av den gröna punkten, och motsvarande för de andra två nollställena. Vad händer om du flyttar startpunkten? Kommer följden alltid att konvergera mot det nollställe som ligger närmast $z_0$? (Välj till exempel $z_0 = 0.58+1.13i$. Andra intressanta startpunkter är bland andra $z_0 = 0.26+0.60i$ och de flesta punkter i närheten av origo.)

Genom att färglägga punkter utifrån vilket nollställe som följden konvergerar mot får man en aning om hur komplicerat Newtons metod faktiskt uppför sig. I figuren nedan har vi gjort just det. Ju mörkare färgen är, desto fler steg krävs för konvergens, och punkter som är svarta motsvarar att följden inte har konvergerat alls (efter 15 steg).

Figurer av detta slag kallas ibland Newtonfraktaler.