Fikspunktiterasjon

Siden fikspunktiterasjon løser likningen \( x=f(x) \), må man først skrive om likningen man vil løse til denne formen.

Deretter bytter vi ut x-en på høyre side av likningen med \( x_{n+1} \), dette er for at notasjonen skal gi mer mening.

Deretter velger vi en startverdi for x, \(x_0\). Det lønner seg å velge en verdi som er så nærme som mulig løsningen på likningen, men verdien trenger i de fleste tilfeller ikke være kjempenærme. Etter vi har valgt en \( x_0 \) settes denne verdien inn i høyre side av likningen, og vi bruker likningen til å finne hva \(x_1\) er ved å løse for \(x_{n+1}\). Når vi har funnet en verdi for \(x_1\), setter vi denne verdien inn på høyre side av likningen for å finne \(x_2\). Denne prosessen gjentas mange ganger, og hvis du har gjort alt riktig vil hver nye \(x_n\) du finner være nærmere løsningen på likningen, slik at man til slutt får en \(x_n\) som er «presis nok».

Eksempel: Løs likningen \(2x+\sin(x) = \cos(x) \) ved hjelp av fikspunktiterasjon.

1. Først må vi skrive om likningen til formen \(x = f(x)\). Da ender vi opp med: \(x = 0.5(\cos(x)-\sin(x))\)
2. Vi velger startverdi \(x_0 = 0.5\). Deretter starter vi med iterasjoner:

Iterasjon 1: Vi setter inn \(x_0\) på høyre side av likningen og får:

\[x_1 = f(x_0) = 0.5(\cos(0.5)-\sin(0.5)) \approx 0.199 \]

Iterasjon 2: Vi setter inn verdien vi fant for \(x_1\) for å finne \(x_2\):

\[x_2 = f(x_1) = 0.5(\cos(0.199)-\sin(0.199)) \approx 0.391 \]

Iterasjon 3: Forhåpentligvis begynner du å forstå greia:

\[x_3 = f(x_2) = 0.5(\cos(0.391)-\sin(0.391)) \approx 0.272 \]

Når man bruker fikspunktiterasjon, må man ofte bruke mange iterasjoner for å få et godt svar. Da blir det ekstremt tungvint å regne alle iterasjonene slik vi har gjort til nå. Derfor skriver man ofte (alltid) et Python-script som gjør jobben for deg. Ved å kjøre 10000000 iterasjoner (overkill) med fikspunktiterasjon på likningen i Python, fant jeg at \(x=0.318366\).

Dersom du prøver å løse en likning \(x=f(x)\) med fikspunktiterasjon, vil det ikke fungere hvis \(|f’(x)| > 1\) for de x-verdiene der løsningen ligger. Dersom \(|f’(x)| > 1\) vil verdien du får for x komme lengere og lengere unna den faktiske løsningen for hver iterasjon, og \(x_n\) vil aldri konvergere.

Hva gjør man dersom \(|f’(x)| > 1\)? Et «triks» er å invertere \(f(x)\), og deretter bruke den inverterte versjonen istedenfor den originale. Dette fungerer fordi \(f(x)\) og \(f^{-1}(x)\) er speilet om linjen \(y=x\), og vil derfor ha samme krysningspunkter med denne linjen. Når man løser likningen \(x=f(x)\) finner man krysningspunktet mellom \(y=x\) og \(f(x)\), så om man bruker \(f^{-1}(x)\) istedenfor \(f(x)\), vil man få likt svar. I tillegg vil den \(|\frac{\delta}{\delta x} f^{-1}(x_1)|<1\) dersom \(|f’(x)| > 1\).

Man kan også unngå problemet ved å benytte seg av en annen metode for numerisk likningsløsning, for eksempel Newtons metode.