Metoda navadne iteracije

Iz Wikipedije, proste enciklopedije
Skoči na: navigacija, iskanje

Metóda navádne iterácije 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[uredi | uredi kodo]

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[uredi | uredi kodo]

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[uredi | uredi kodo]

Iskanje ničel funkcije[uredi | uredi kodo]

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)[uredi | uredi kodo]

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[uredi | uredi kodo]