Metoda navadne iteracije

Metóda navádne iterácije (navádna iterácijska metóda in redkeje metóda negíbne tóčke) je v matematiki preprosta in učinkovita numerična metoda za določanje negibnih točk funkcije. Negibna (fiksna) točka funkcije g je točka, v kateri je vrednost funkcije enaka podatku, torej:

$x=g(x)\,\!.$

Potek postopka

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

• Najprej si izberemo začetni približek $x_{0}\,\!$.
• Ta približek vstavimo v funkcijo in dobimo naslednji približek $x_{1}=g(x_{0})\,\!$.
• Na enak način izračunamo še nadaljnje približke: $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.

Zgled

Rešimo enačbo $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:

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

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

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

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

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

$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:

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

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

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

Drugi načini uporabe

Iskanje ničel funkcije

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 $p(x)=x^{3}-3x+5\,\!$.

• Polinom lahko preoblikujemo po naslednejm postopku:

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

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

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

  V dobljeno iteracijsko funkcijo $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:

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

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

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

  Tako dobljena iteracijska funkcija :$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:

  $x=-2,279018786\,\!.$

Reševanje enačbe oblike h(x) = k(x)

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

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

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

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

Glej tudi

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

Viri

• Stöcker, Horst (2006), Matematični priročnik z osnovami računalništva, Ljubljana: Tehniška založba Slovenije, str. 51, COBISS 229576192, ISBN 86-365-0587-9, OCLC 449201276