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),\dots ,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

• Predloga:Citat