fastpunktsmetode

Fastpunktsmetoden, eller fastpunktsiteration, är en numerisk metod för att lösa ekvationer f(x) = 0 genom att skriva om problemet som x = g(x) och upprepa x_{n+1} = g(x_n). Lösningen är då en fast punkt x* som uppfyller x* = g(x*). Metoden används när man kan omvandla f till en lämplig g och när g är enkel att iterera.

Convergensvillkor för metoden följer vanligtvis kontraktionsprincipen: om det finns ett intervall I där g kartlägger I in i sig själv och det råder ett konstant k < 1 så att |g'(x)| ≤ k för alla x i I, så konvergerar x_n till den unika fastpunkten x* i I oavsett startvärdet x0 i I. Felet minskar linjärt enligt |x_{n+1} − x*| ≤ k |x_n − x*|, så därmed även |x_n − x*| ≤ k^n |x_0 − x*|.

I lokala termer gäller kallnade för konvergens: om x* är en fast punkt och g är differentierbar nära x*, samt |g'(x*)| < 1, så finns en neighborhood där serien convergerar mot x*. Konvergens hastighet är då ungefär proportionell mot |g'(x*)| och är linjär.

Praktiska överväganden: valet av g är avgörande. En lämplig g gör att deriveringen vid lösningen är mindre än 1 i absolut värde. Om derivatan är nära 1 eller större än 1 kan metoden konvergera mycket långsamt eller inte alls. Ibland används olika former av relaxation som x_{n+1} = x_n + λ (g(x_n) − x_n) för att förbättra konvergensen.

Exempelvis kan ekvationen x = cos x lösas med g(x) = cos x; fastpunkten är Dottie-talet ≈ 0,739085. Metoden är enkel att implementera och används i grundläggande numeriska lösningar där en enkel, konstant-derivatan iteration är tillräcklig.