Metoda navadne iteracije

algoritem za iskanje korena

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:

Potek postopka

uredi

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

  • Najprej si izberemo začetni približek  .
  • Ta približek vstavimo v funkcijo in dobimo naslednji približek  .
  • Na enak način izračunamo še nadaljnje približke:  .
  • 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

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

 
 
 
 
 
 

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

 
 

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

Drugi načini uporabe

uredi

Iskanje ničel funkcije

uredi

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  .

  • Polinom lahko preoblikujemo po naslednejm postopku:
     
     
     
    V dobljeno iteracijsko funkcijo   vstavljamo različne začetne približke in opazimo, da dobljeno zaporedje nikoli ne konvergira.
  • Isti polinom lahko preoblikujemo tudi drugače:
     
     
     
    Tako dobljena iteracijska funkcija :  je uspešnejša. Pri različnih izbirah začetneg približka dobimo že po nekaj korakih ničlo na več decimalk natančno:
     

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

uredi

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

 
 

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

Glej tudi

uredi
  • 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