Metoda iteracije

Napišimo jednadžbu (#eq:jednul#7679>) u obliku

#math2135#
#tex2html_wrap_indisplay35814# (3.4)

Riješiti jednadžbu sada znači naći takav #math2136##tex2html_wrap_inline35816# da vrijedi #math2137##tex2html_wrap_inline35818# Geometrijski to znači da tražimo presjek grafa funkcije i pravca #tex2html_wrap_inline35820#
#math2138##tex2html_wrap24576#
Imamo sljedeći algoritam

Algoritam 2   <#11928#>(Metoda iteracije)<#11928#> Izaberemo #math2139##tex2html_wrap_inline35824# i računamo niz #tex2html_wrap_inline35826# za #math2140##tex2html_wrap_inline35828# po formuli

#math2141#
#tex2html_wrap_indisplay35830# (3.5)

Ako je #math2142##tex2html_wrap_inline35832# za neki #tex2html_wrap_inline35834# onda je #tex2html_wrap_inline35836# U protivnom nastavljamo računanje daljnih članova niza.

Ovaj algoritam dobro opisuje sljedeća slika.
#math2143##tex2html_wrap24580#
Imamo sljedeći program za metodu iteracije

Mathematica program 2   (Metoda iteracije)
verbatim170#

Može se dogoditi da ne postoji rješenje,
#math2144##tex2html_wrap24582#
da postoji ali da ga ne možemo dostići ovom metodom,
#math2145##tex2html_wrap24584#
ili da postoji i da nam je dostupno.
#math2146##tex2html_wrap24586#
Evo još nekoliko slika, koje pokazuju različito ponašanje iteracijskog niza. #math2147##tex2html_wrap24588# #math2148##tex2html_wrap24590# #math2149##tex2html_wrap24592# #math2150##tex2html_wrap24594# #math2151##tex2html_wrap24596# #math2152##tex2html_wrap24598# Da bi ova metoda funkcionirala, moraju brojevi #math2153##tex2html_wrap_inline35849# biti u #tex2html_wrap_inline35851# za bilo koju početnu aproksimaciju. To će svakako biti ispunjeno, ako je #math2154##tex2html_wrap_inline35853# A kako je funkcija #tex2html_wrap_inline35855# još i neprekidna, onda postoji bar jedna točka presjeka.

Teorem 23   Neka je
<#35869#>1.<#35869#>
#math2155##tex2html_wrap_inline35858# funkcija klase #tex2html_wrap_inline35860# na #tex2html_wrap_inline35862#
<#35870#>2.<#35870#>
#math2156##tex2html_wrap_inline35864# za svaki #math2157##tex2html_wrap_inline35866#
<#35871#>3.<#35871#>
#math2158##tex2html_wrap_inline35868#
Tada za proizvoljan #math2159##tex2html_wrap_inline35873# niz #tex2html_wrap_inline35875# definiran algoritmom (#eq:alg1#7733>) konvergira k jedinstvenom rješenju jednadžbe #math2160##tex2html_wrap_inline35877#
<#12278#>Dokaz. Dokažimo najprije da postoji barem jedno rješenje. Stavimo #math2161##tex2html_wrap_inline35879# Prema uvjetima teorema, #math2162##tex2html_wrap_inline35881# i #math2163##tex2html_wrap_inline35883# Budući da je #tex2html_wrap_inline35885# neprekidna funkcija na segmentu #tex2html_wrap_inline35887# slijedi da postoji bar jedan #math2164##tex2html_wrap_inline35889# takav da je #tex2html_wrap_inline35891# tj. #math2165##tex2html_wrap_inline35893# dakle #tex2html_wrap_inline35895# je rješenje.
Dokažimo sada da ne postoji više od jednog rješenja. Pretpostavimo da su #tex2html_wrap_inline35897# i #tex2html_wrap_inline35899# dva međusobno različita rješenja. Tada, prema Lagrangeovom teoremu srednje vrijednosti,
#math2166#

#tex2html_wrap_indisplay35901#

što je kontradikcija. Dakle problem ima jedno i samo jedno rješenje #tex2html_wrap_inline35903#
Preostaje dokazati da za bilo koju početnu aproksimaciju #tex2html_wrap_inline35905# niz #tex2html_wrap_inline35907# konvergira k rješenju #tex2html_wrap_inline35909# Imamo
#math2167#

#tex2html_wrap_indisplay35911#

Odatle #math2168#

#tex2html_wrap_indisplay35913#

Budući da je #math2169##tex2html_wrap_inline35915# slijedi #math2170#

#tex2html_wrap_indisplay35917#

pa je prema tome #math2171#

#tex2html_wrap_indisplay35919#

tj. #math2172#

#tex2html_wrap_indisplay35921#

#math2173##tex2html_wrap_inline35923#<#12278#>

Apriornu ocjenu greške dobivamo na sljedeći način. Iz #math2174#

#tex2html_wrap_indisplay35925#

slijedi #math2175#

#tex2html_wrap_indisplay35927#

#math2176#

#tex2html_wrap_indisplay35929#

Za proizvoljni prirodni broj #tex2html_wrap_inline35931# imamo #math2177#

#tex2html_wrap_indisplay35933#

Iz gornje nejednakosti slijedi #math2178#

#tex2html_wrap_indisplay35935#

Zbog #tex2html_wrap_inline35937# #math2179#

#tex2html_wrap_indisplay35939#

#math2180#

#tex2html_wrap_indisplay35941#

po formuli za sumu geometrijskog reda. Tako je #math2181#

#tex2html_wrap_indisplay35943#

Desna strana ove nejednakosti ne ovisi o #tex2html_wrap_inline35945# pa prema tome #math2182#

#tex2html_wrap_indisplay35947#

Dakle apriorna ocjena greške #tex2html_wrap_inline35949#-te aproksimacije je

#math2183#
#tex2html_wrap_indisplay35951# (3.6)

Aposteriorna ocjena greške je ocjena koja se računa pomoću dobivenih aproksimacija. U ovom slučaju ona je

#math2184#
#tex2html_wrap_indisplay35953# (3.7)

Doista, #math2185#

#tex2html_wrap_indisplay35955#

#math2186#

#tex2html_wrap_indisplay35957#

#math2187#

#tex2html_wrap_indisplay35959#

#math2188#

#tex2html_wrap_indisplay35961#

#math2189#

#tex2html_wrap_indisplay35963#

#math2190#

#tex2html_wrap_indisplay35965#

Tako je #math2191#

#tex2html_wrap_indisplay35967#

Primjer 3.3   Riješiti metodom iteracije jednadžbu u primjeru #pr:kubna#7858>. Rješenje. Iz #math2192#

#tex2html_wrap_indisplay35970#

slijedi #math2193#

#tex2html_wrap_indisplay35972#

Tako je #math2194#

#tex2html_wrap_indisplay35974#

Rješenje postoji na segmentu #tex2html_wrap_inline35976# (v. primjer #pr:kubna#7865>). #tex2html_wrap_inline35978# je pozitivna, pa funkcija #tex2html_wrap_inline35980# raste. #math2195#

#tex2html_wrap_indisplay35982#

Osim toga #tex2html_wrap_inline35984# raste na #tex2html_wrap_inline35986# pozitivna je, pa najveću vrijednost ima u #tex2html_wrap_inline35988# i to #math2196#

#tex2html_wrap_indisplay35990#

Ova diskusija pokazuje da su uvjeti teorema #tm:iter#7874> ispunjeni, pa će iteracijski proces konvergirati bez obzira na to koji broj iz #tex2html_wrap_inline35992# uzmemo kao početnu aproksimaciju. Ujedno nam ocjena #math2197#

#tex2html_wrap_indisplay35994#

može poslužiti da bismo apriorno ocijenili grešku #tex2html_wrap_inline35996#-te aproksimacije. Imamo na pr. #math2198#

#tex2html_wrap_indisplay35998#

pa greška #tex2html_wrap_inline36000#-te aproksimacije nije veća od #math2199#

#tex2html_wrap_indisplay36002#

Ako želimo rješenje točno na pet decimala, izlazi da mora biti #tex2html_wrap_inline36004# dakle trinaesta aproksimacija daje traženu točnost. Pomoću programa #prg:metiter#7888> nalazimo da je #math2200#

#tex2html_wrap_indisplay36006#

Primjer 3.4   Riješiti zadatak u primjeru #pr:transc#7892> metodom iteracije. Rješenje. Jednadžbu treba napisati u obliku #math2201#

#tex2html_wrap_indisplay36009#

Ako stavimo #math2202#

#tex2html_wrap_indisplay36011#

onda je #math2203#

#tex2html_wrap_indisplay36013#

#math2204#

#tex2html_wrap_indisplay36015#

pa je #math2205#

#tex2html_wrap_indisplay36017#;SPMnbsp; ;SPMnbsp;<#1#>za svaki <#1#>#tex2html_wrap_indisplay36018#

To ne odgovara uvjetima teorema #tm:iter#7903>. Jednadžbu možemo i drukčije napisati #math2206#

#tex2html_wrap_indisplay36020#

Tada je #math2207#

#tex2html_wrap_indisplay36022#

#math2208#

#tex2html_wrap_indisplay36024#

pa je #math2209#

#tex2html_wrap_indisplay36026#;SPMnbsp; ;SPMnbsp;<#1#>za svaki <#1#>#tex2html_wrap_indisplay36027#

Specijalno, #math2210##tex2html_wrap_inline36029# samo za #math2211##tex2html_wrap_inline36031# Domena od #tex2html_wrap_inline36033# je #math2212##tex2html_wrap_inline36035# Budući da je #math2213##tex2html_wrap_inline36037# funkcija pada na svakom od intervala #math2214##tex2html_wrap_inline36039# #math2215##tex2html_wrap_inline36041# Nas interesiraju samo pozitivna rješenja, pa nam je interesantan samo interval #math2216##tex2html_wrap_inline36043# Na tom intervalu #math2217#

#tex2html_wrap_indisplay36045#

Dakle #tex2html_wrap_inline36047# preslikava #math2218##tex2html_wrap_inline36049# na #math2219##tex2html_wrap_inline36051# Također #math2220#

#tex2html_wrap_indisplay36053#

pa #tex2html_wrap_inline36055# preslikava segment #math2221##tex2html_wrap_inline36057# u samog sebe. Apsolutna vrijednost derivacije je najveća na lijevom rubu. Tako možemo staviti #math2222#

#tex2html_wrap_indisplay36059#

To znači da će metoda iteracije konvergirati uzmemo li bilo koji broj iz segmenta #math2223##tex2html_wrap_inline36061# kao početnu aproksimaciju. Pomoću programa #prg:metiter#7955> nalazimo da je zaokruženo na šest decimala, uz #tex2html_wrap_inline36063# #math2224#

#tex2html_wrap_indisplay36065#

#math2225#

#tex2html_wrap_indisplay36067#

i dalje se ovaj broj ponavlja.