Metoda navadne iteracije

Enačbo oblike x = g(x) rešimo po metodi navadne iteracije z naslednjim postopkom:

• Najprej si izberemo začetni približek ${\displaystyle x_{0}\,\!}$ .
• Ta približek vstavimo v funkcijo in dobimo naslednji približek ${\displaystyle x_{1}=g(x_{0})\,\!}$ .
• Na enak način izračunamo še nadaljnje približke: ${\displaystyle x_{2}=g(x_{1}),~x_{3}=g(x_{2}),~\ldots ,~x_{n}=g(x_{n-1})\,\!}$ .
• Postopek končamo, ko smo zadovoljni z natančnostjo dobljenega približka.

Tako dobljeno zaporedje približkov konvergira k fiksni točki, če je v neki okolici fiksne točke odvod funkcije g po absolutni vrednosti manjši od 1 in če začetni približek leži v tej okolici.

Rešimo enačbo ${\displaystyle x=\cos x\,\!}$  (kjer je x kot v radianih). Ker odvod funkcije po absolutni vrednosti nikoli ni večji od 1, je izbira začetnega približka precej poljubna. Izberimo npr. začetni približek 1. Po večkratnem izvajanju funkcije kosinus dobimo naslednje približke:

${\displaystyle x_{0}=1\,\!}$ 

${\displaystyle x_{1}=0,54030\,\!}$ 

${\displaystyle x_{2}=0,85755\,\!}$ 

${\displaystyle x_{3}=0,65429\,\!}$ 

${\displaystyle x_{4}=0,79348\,\!}$ 

${\displaystyle x_{5}=0,70137\,\!}$ 

Vidimo, da se razlika med zaporednima približkoma manjša, kar je znak, da zaporedje konvergira. Po večjem številu korakov dobimo približek:

${\displaystyle x_{20}=0,73918\,\!}$ 

${\displaystyle x_{21}=0,73901\,\!}$ 

Iz tega sklepamo, da so prve tri decimalke pravilne rešitve enake ${\displaystyle x=0,739\,\!}$ . Če želimo izračunati rešitev na več decimalk natančno, postopek nadaljujemo.

Metodo navadne iteracije lahko uporabimo za iskanje ničel poljubne funkcije f, če enačbo f(x) = 0 najprej preoblikujemo v obliko x = g(x). To je po navadi možno na več načinov, vendar pa vsa preoblikovanja niso enako uspešna.

Zgled: Poiščimo ničle polinoma ${\displaystyle p(x)=x^{3}-3x+5\,\!}$ .

• Polinom lahko preoblikujemo po naslednejm postopku:

  ${\displaystyle 0=x^{3}-3x+5\,\!}$ 

  ${\displaystyle 3x=x^{3}+5\,\!}$ 

  ${\displaystyle x={\frac {x^{3}+5}{3}}}$ 

  V dobljeno iteracijsko funkcijo ${\displaystyle g(x)={\frac {x^{3}+5}{3}}}$  vstavljamo različne začetne približke in opazimo, da dobljeno zaporedje nikoli ne konvergira.
• Isti polinom lahko preoblikujemo tudi drugače:

  ${\displaystyle x^{3}-3x+5=0\,\!}$ 

  ${\displaystyle x^{3}=3x-5\,\!}$ 

  ${\displaystyle x={\sqrt[{3}]{3x-5}}}$ 

  Tako dobljena iteracijska funkcija :${\displaystyle g(x)={\sqrt[{3}]{3x-5}}}$  je uspešnejša. Pri različnih izbirah začetneg približka dobimo že po nekaj korakih ničlo na več decimalk natančno:

  ${\displaystyle x=-2,279018786\,\!.}$ 

Splošno enačbo oblike h(x) = k(x) lahko preoblikujemo z uporabo inverza funkcije h ali k (če obstajata). Tako dobimo dve obliki:

${\displaystyle x=h^{-1}(k(x))\,\!}$ 

${\displaystyle x=k^{-1}(h(x))\,\!}$ 

Praviloma vsaj ena od teh dveh metod (ob izbiri primernega začetnega približka) vodi k rešitvi.

• metoda pospešene iteracije (Newtonova ali tangentna metoda)