Ogled vira 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 [[matematika|matematiki]] preprosta in učinkovita [[numerična metoda]] za določanje [[negibna točka|negibnih točk]] [[funkcija|funkcije]]. Negibna (fiksna) točka funkcije ''g'' je [[Točka (geometrija)|točka]], v kateri je vrednost funkcije enaka podatku, torej:

: <math> x=g(x) \,\! . </math>

== Potek postopka ==

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

* Najprej si izberemo začetni približek <math>x_0\,\!</math>.
* Ta približek vstavimo v funkcijo in dobimo naslednji približek <math>x_1=g(x_0)\,\!</math>.
* Na enak način izračunamo še nadaljnje približke: <math>x_2=g(x_1),~ x_3=g(x_2),~\ldots,~x_n=g(x_{n-1})\,\!</math>.
* Postopek končamo, ko smo zadovoljni z natančnostjo dobljenega približka.

Tako dobljeno zaporedje približkov [[konvergenca|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 <math>x= \cos x\,\!</math> (kjer je ''x'' [[kot]] v [[radian]]ih). 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:

: <math> x_0=1\,\! </math>
: <math> x_1=0,54030\,\! </math>
: <math> x_2=0,85755\,\! </math>
: <math> x_3=0,65429\,\! </math>
: <math> x_4=0,79348\,\! </math>
: <math> x_5=0,70137\,\! </math>

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

: <math> x_{20}=0,73918\,\! </math>
: <math> x_{21}=0,73901\,\! </math>

Iz tega sklepamo, da so prve tri decimalke pravilne rešitve enake <math>x=0,739\,\!</math>. Če želimo izračunati [[rešitev enačbe|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čla funkcije|ničel]] poljubne [[funkcija|funkcije]] ''f'', če enačbo ''f''(''x'')&nbsp;=&nbsp;0 najprej preoblikujemo v obliko ''x''&nbsp;=&nbsp;''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 [[polinom]]a <math>p(x)=x^3-3x+5\,\!</math>.
<ul>
<li>
Polinom lahko preoblikujemo po naslednejm postopku:

: <math> 0=x^3-3x+5\,\! </math>
: <math> 3x=x^3+5\,\! </math>
: <math> x=\frac{x^3+5}{3} </math>

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

: <math> x^3-3x+5=0\,\! </math>
: <math> x^3=3x-5\,\! </math>
: <math> x=\sqrt[3]{3x-5} </math>

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

: <math> x=-2,279018786\,\! . </math>
</li>
</ul>

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

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

: <math>x=h^{-1}(k(x))\,\! </math>
: <math>x=k^{-1}(h(x))\,\! </math>

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 ==

{{refbegin|1}}
* {{citat|last1= Stöcker|first1= Horst|authorlink1= Horst Stöcker|title= Matematični priročnik z osnovami računalništva|date= 2006|publisher= [[Tehniška založba Slovenije]]|location= Ljubljana|isbn= 86-365-0587-9|cobiss= 229576192|oclc= 449201276|pages= 51}}
{{refend}}

[[Kategorija:Numerična analiza]]