Next: Rješavanje sustava jednadžbi Up: Numerička matematika Previous: Uvod Contents Index
Subsections

- Metoda polovljenja
- Metoda iteracije
- Newtonova metoda
  - Modifikacije Newtonove metode
    - Whittakerova metoda.
    - Metoda `Regula falsi' ili metoda sekante.

#
Rješavanje jednadžbi

Razmotrit ćemo nekoliko iterativnih postupaka za rješavanje jednadžbe

| (3.1)

uz opću pretpostavku da je neprekidna funkcija. Pretpostavimo da su i u domeni funkcije takvi da je

| (3.2)

Zbog neprekidnosti funkcije, prema Bolzanovom teoremu (neprekidnost funkcije na segmentu, v. [8, Teorem 4, str. 31]), postoji barem jedno rješenje jednadžbe (3.1) u segmentu Iterativni postupak je postupak, kojim nalazimo niz brojeva tako, da je

Član niza se zove -ta aproksimacija rješenja Naravno, možemo naći samo konačno mnogo članova niza. Tako se moramo zadovoljiti s približnim rješenjem. Koja će aproksimacija biti dovoljno dobra ovisi o tome kolika je greška dozvoljiva. Prema tome bit će nam važno znati ocijeniti grešku koju činimo kad pravo rješenje zamjenimo s -tom aproksimacijom

##
Metoda polovljenja

Metoda polovljenja se sastoji u tome da se segment na kojem je ispunjen uvjet raspolovi, tj. nađe polovište Ako je onda je U protivnom se ponovi operacija na onom od segmenata ili na kojem je ispunjen uvjet (3.2), itd. Tako imamo sljedeći algoritam.

Algoritam 3 , Za računamo

ako je

ako je

s tim da je

Ovaj algoritam omogućava sljedeći program u programskom paketu 'Mathematica'.

Mathematica program 1 (Metoda polovljenja)

    f[t_]=; (* funkcija *)
    a=;
    b=;     (* pocetni interval *)
    x=(a+b)/2.;
    n=0;
    Print[{n,a,x,b}];
            While[
            N[f[x]]!=0.,
            Print["   ",N[f[a]],"  ",N[f[x]],"   ",N[f[b]]];
                    If[
                    f[b]f[x]<0,
                    a=x;x=(x+b)/2,
                    b=x;x=(a+x)/2
                    ];
            n=n+1;
            If[n>100,Break[]  (* prekid petlje nakon 100 koraka *)
            ];
    Print[{n,a,x,b}]]

Metoda uvijek konvergira, ali vrlo sporo. Očito je

Tako za -tu aproksimaciju imamo ocjenu greške

| (3.3)

Ova ocjena se zove apriorna, jer se može izračunati prije nego smo postupak iteracije uopće započeli. Naravno, ova ocjena nam ne kaže kolika je greška, već samo to da greška nije veća od tog broja.

Primjer 3.1 Riješiti metodom polovljenja jednadžbu

Rješenje. Računanjem vrijednosti polinoma na skupu cijelih brojeva, dobivamo da je a Tako na segmentu postoji bar jedno rješenje. Ako na ovaj problem primijenimo gornji program, dobivamo sljedeću tablicu.

0 |  |  |  |  |  |

Računalo je tek u pedesetoj aproksimaciji došlo do granica svoje točnosti. Točnost ispisanih rezultata (pet znamanaka) se postiže u sedamnaestoj aproksimaciji, što se moglo unaprijed izračunati. Budući da je greška -te aproksimacije nije veća od pa zbog

rješenje na pet decimala točno se postiže u sedamnaestoj aproksimaciji.

Zadatak iz primjera 3.1 se može doduše egzaktno riješiti pomoću Cardanovih formula. Ipak te formule nisu tako jednostavne kao formula za rješenje kvadratne jednadžbe, pa se algebarske jednadžbe trećeg stupnja često rješavaju približnim metodama. U sljedećem primjeru se rješava jednadžba koju ne možemo egzaktno riješiti.

Primjer 3.2 Naći najmanje pozitivno rješenje jednadžbe (v. 2.19)

metodom polovljenja.

Rješenje. Iz slike 2.7 se vidi da se traženo rješenje nalazi u intervalu Neka je

Imamo

Prema tome, za početni segment možemo uzeti segment

Izračunajmo sada koju aproksimaciju treba izračunati da bi se dobila točnost na četiri decimale. Iz formule (3.3) slijedi da treba naći tako da bude

Odatle slijedi pa treba izračunati šesnaestu aproksimaciju. Koristeći program 1 dobivamo

0 |  |  |  |  |  |

Dakle rješenje, na četiri decimale točno, je

##
Metoda iteracije

Napišimo jednadžbu (3.1) u obliku

| (3.4)

Riješiti jednadžbu sada znači naći takav da vrijedi Geometrijski to znači da tražimo presjek grafa funkcije i pravca

Imamo sljedeći algoritam

Algoritam 4 (Metoda iteracije) Izaberemo i računamo niz za po formuli

| (3.5)

Ako je za neki onda je U protivnom nastavljamo računanje daljnih članova niza.

Ovaj algoritam dobro opisuje sljedeća slika.

Imamo sljedeći program za metodu iteracije

Mathematica program 2 (Metoda iteracije)

    varphi[t_]=; (* funkcija *)
    x=;          (* pocetna aproksimacija *)
    n=0;
       While[
       N[f[x]]!=x,
       x=varphi[x];
       n=n+1;
       If[n>100,Break[]]; (* prekid procesa nakon 100 iteracija *)
       Print[N[x]]
       ]

Može se dogoditi da ne postoji rješenje,

da postoji ali da ga ne možemo dostići ovom metodom,
ili da postoji i da nam je dostupno.
Evo još nekoliko slika, koje pokazuju različito ponašanje iteracijskog niza.

Da bi ova metoda funkcionirala, moraju brojevi biti u za bilo koju početnu aproksimaciju. To će svakako biti ispunjeno, ako je A kako je funkcija još i neprekidna, onda postoji bar jedna točka presjeka.

Teorem 23 Neka je

1.
  funkcija klase na
2.
  za svaki
3.

Tada za proizvoljan niz definiran algoritmom (3.5) konvergira k jedinstvenom rješenju jednadžbe

Dokaz. Dokažimo najprije da postoji barem jedno rješenje. Stavimo Prema uvjetima teorema, i Budući da je neprekidna funkcija na segmentu slijedi da postoji bar jedan takav da je tj. dakle je rješenje.
Dokažimo sada da ne postoji više od jednog rješenja. Pretpostavimo da su i dva međusobno različita rješenja. Tada, prema Lagrangeovom teoremu srednje vrijednosti,

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

Odatle

Budući da je slijedi

pa je prema tome

tj.

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

slijedi

Za proizvoljni prirodni broj imamo

Iz gornje nejednakosti slijedi

Zbog

po formuli za sumu geometrijskog reda. Tako je

Desna strana ove nejednakosti ne ovisi o pa prema tome

Dakle apriorna ocjena greške -te aproksimacije je

| (3.6)

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

| (3.7)

Doista,

Tako je

Primjer 3.3 Riješiti metodom iteracije jednadžbu u primjeru 3.1.

Rješenje. Iz

slijedi

Tako je

Rješenje postoji na segmentu (v. primjer 3.1). je pozitivna, pa funkcija raste.

Osim toga raste na pozitivna je, pa najveću vrijednost ima u i to

Ova diskusija pokazuje da su uvjeti teorema 23 ispunjeni, pa će iteracijski proces konvergirati bez obzira na to koji broj iz uzmemo kao početnu aproksimaciju. Ujedno nam ocjena

može poslužiti da bismo apriorno ocijenili grešku -te aproksimacije.

Imamo na pr.

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

Ako želimo rješenje točno na pet decimala, izlazi da mora biti dakle trinaesta aproksimacija daje traženu točnost. Pomoću programa 2 nalazimo da je

Primjer 3.4 Riješiti zadatak u primjeru 3.2 metodom iteracije.

Rješenje. Jednadžbu treba napisati u obliku

Ako stavimo

onda je

pa je

za svaki

To ne odgovara uvjetima teorema 23. Jednadžbu možemo i drukčije napisati

Tada je

pa je

za svaki

Specijalno, samo za Domena od je Budući da je funkcija pada na svakom od intervala Nas interesiraju samo pozitivna rješenja, pa nam je interesantan samo interval Na tom intervalu

Dakle preslikava na Također

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

To znači da će metoda iteracije konvergirati uzmemo li bilo koji broj iz segmenta kao početnu aproksimaciju. Pomoću programa 2 nalazimo da je zaokruženo na šest decimala, uz

i dalje se ovaj broj ponavlja.

##
Newtonova metoda

Neka je klase na Želimo riješiti jednadžbu

Newtonova metoda, koja se često zove Newton-Raphsonova metoda ili metoda tangente, sastoji se u tome da se -va aproksimacija odredi kao sjecište tangente na graf funkcije u točki s apscisom s osi

Jednadžba tangente na graf funkcije u točki je

Kad stavimo dobijemo njezino sjecište s osi

Dakle -va aproksimacija se računa po formuli

Time smo dobili sljedeći algoritam.

Algoritam 5 (Newtonova metoda) Izaberemo i računamo niz za po formuli

| (3.8)

Ako je za neki onda je U protivnom nastavljamo računanje daljnih članova niza.

Mathematica program 3 (Newtonova metoda)

    f[t_]=; (* funkcija *)
    x=;     (* pocetna aproksimacija *)
    n=0;
       While[
       N[f[x]]!=0.,
       x=x-f[x]/f'[x];
       n=n+1;
       If[n>100,Break[]]; (* prekid nakon 100 iteracija *)
       Print[N[x]]
       ]

Primjer 3.5 Newtonovom metodom riješiti jednadžbu iz primjera 3.1.

Rješenje. Pomoću programa 3 s početnom aproksimacijom dobivamo

i to je sve, jer se nakon 10 iteracija postiže strojna točnost. To pokazuje da Newtonova metoda iteracije u ovom slučaju vrlo brzo konvergira.

Primjer 3.6 Riješiti problem iz primjera 3.2 Newtonovom metodom.

Rješenje. Pomoću programa 3 s početnom aproksimacijom dobivamo

Program je napravljen tako da ponavlja iteracije 100 puta ili završava postupak kad postigne strojnu točnost. Ovo pokazuje da je u ovom primjeru strojna točnost postignuta već u četvrtoj aproksimaciji.

S druge strane ako s istim programom (Newtonovom metodom) pokušamo riješiti jednadžbu

počevši s dobivamo To pokazuje da konvergencija nije uvijek tako brza kao u prethodnim primjerima. Dapače, ako pokušamo na isti način riješiti jednadžbu

počevši s dobivamo redom itd. Aproksimacije se sve više udaljavaju od rješenja koje je očito Sljedeći teorem je jedan od mnogih koji daju dovoljne uvjete da Newtonova metoda konvergira. Uvjerite se da su uvjeti teorema ispunjeni za primjer 3.5 na segmentu

Teorem 24 Neka je klase i neka vrijedi

1.
2.
  za svaki
3.
  ili za svaki
4.
  ako je ona rubna točka segmenta u kojoj je manji, onda je

Tada Newtonova metoda konvergira k rješenju jednadžbe za bilo koju početnu aproksimaciju

Dokaz. Kombinirajući uvjete iz teorema, mogli bismo promatrati razne slučajeve, no može se pokazati da se svaki od njih, uzimajući umjesto i/ili umjesto može svesti na slučaj

Iz 2. uvjeta i neprekidnosti funkcije slijedi ili za svaki Prema tome funkcija na segmentu raste ili pada. Kako je funkcija raste. Osim toga iz slijedi da je konkavna. Dakle graf funkcije izgleda kao na slici
Osim toga za proizvoljan vrijedi

pa je

| (3.9)

tj. tangenta u bilo kojoj točki se nalazi iznad grafa funkcije
Razmotrimo najprije slučaj gdje je jedinstveno rješenje jednadžbe Za takav je i Prema tome je

Iz (3.9) slijedi da je

pa je Polazeći od na isti način možemo zaključiti da je odnosno Nastavljajući tako vidimo da je Tako smo dobili rastući niz aproksimacija odozgo ograničen. Takav niz ima limes

Zbog neprekidnosti funkcije i njezine derivacije imamo

Odatle slijedi pa je tako
Neka je sada Za imamo

Ako je onda iz

i (3.9) slijedi

Prema tome tangenta u točki prolazi iznad točke pa se njezino sjecište s osi nalazi lijevo od Tako je

Sada smo u situaciji iz prvog dijela dokaza, pa dalje dokaz ide kao tamo.

Primjer 3.7 Neka je prirodan broj, i neka je Nađimo, pomoću Newtonove metode, približnu vrijednost pozitivnog -tog korijena iz

Rješenje. Izračunati -ti korijen iz broja znači riješiti po jednadžbu

Ovdje je pa Newtonova metoda daje

odnosno

Što se tiče izbora početne aproksimacije i konvergencije, primijetimo sljedeće. Za imamo Zatim, zbog za svaki je i Na kraju, iz pozitivnosti funkcije slijedi rast funkcije pa je onaj rub segmenta u kojem ima manju vrijednost. Da bi vrijedilo

mora biti

Dakle za tako veliki ispunjeni su svi uvjeti teorema 24. Kako smijemo uzeti još veći, i kako može biti bilo koji broj veći od i manji od slijedi da postupak konvergira za svaki

Specijalno kad je imamo formulu za približno računanje drugog korijena

| (3.10)

U programskom paketu Mathematica se ovaj postupak programira vrlo jednostavno

Mathematica program 4 (-ti korijen)

    Map[Nest[((k-1) # + c/#^(k-1))/k&,x0,#1]&,Range[p]]//N

gdje je `p` broj aproksimacija koje želimo, a broj `x0` je početna aproksimacija. Naravno `k` je broj korijena koji se vadi.

Uvjerite se na primjerima kako je formula za računanje drugog korijena efikasna.

Primjer 3.8 Za dani pozitivan broj naći približnu vrijednost njemu recipročnog broja bez dijeljenja.

Rješenje. To je isto kao približno riješiti jednadžbu

Newtonova metoda daje

U ovoj formuli nema dijeljenja, i mi smo riješili zadatak, ako postoji interval u kojem možemo birati početnu aproksimaciju tako da ovaj postupak konvergira. Ispitajmo uvjete teorema 24 u ovom slučaju.

Neka su sada takvi da je Time je uvjet ispunjen. Iz pozitivnosti slijedi da raste. No ima negativne vrijednosti, pa iz rasta slijedi da pada. Tako prima manju vrijednost u rubnoj točki

pa određujemo iz kvadratne nejednadžbe

Izlazi da se mora nalaziti između

i

Budući da možemo uzeti po volji malen, slijedi da se za može uzeti bilo koji broj manji od Tako se za početnu aproksimaciju može uzeti bilo koji takav da je

Ako želimo ocijeniti grešku, primijetimo da je Newtonova metoda zapravo metoda iteracije, ako stavimo

Tada je

Neka je

Tada je apriorna ocjena greške dana formulom (3.6), a aposteriorna formulom (3.7).

Primjer 3.9 Naći u slučaju približnog računanja drugog korijena po formuli (3.10).

Rješenje. Treba naći približnu vrijednost od Neka je

Prirodno je početnu aproksimaciju uzeti u segmentu Tada je

U ovom slučaju je

pa je

Odavde se vidi da je uvijek

### Modifikacije Newtonove metode

#### Whittakerova metoda.

Jedan od problema u Newtonovoj metodi je potreba računanja derivacije u svakom koraku. Najjednostavniji način da se to izbjegne je da se umjesto derivacije u formulu algoritma uvrsti konstanta

Ovisno o broju ova korekcija Newtonove metode može usporiti konvergenciju. Zato se ona radije koristi nakon što se s nekoliko koraka Newtonovom metodom stiglo blizu rješenja.

####
Metoda `Regula falsi' ili metoda sekante.

Ideja metode je da se -va aproksimacija odredi kao sjecište osi i sekante kroz točke na grafu funkcije čije apscise su prethodne aproksimacije takve, da su vrijednosti funkcije u njima različitog znaka. Dakle, možemo koristiti Newtonovu metodu u kojoj zamjenimo s koeficijentom sekante

Tako imamo formulu postupka

Pri tom uzimamo pa izračunamo iz formule. Da bismo izračunali stavimo u formulu umjesto a umjesto stavimo onaj od brojeva u kojem funkcija prima vrijednost suprotnog znaka od onog u točki Tako nastavljamo dalje. Da bismo izračunali trebamo uzeti i kao uzeti onaj između i u kojem funkcija ima suprotan znak nego u

Tako imamo sljedeći algoritam.

Algoritam 6 Stavimo i Zatim računamo niz po formuli

gdje je

Mathematica program 5 Metoda sekante

      f[t_]=; (* funkcija *)
    a=;
    b=;   (* pocetni interval (zadati kao realne brojeve) *)
    If[f[a]f[b]<=0,
    x=(a f[b]-b f[a])/(f[b]-f[a]);
    n=0;
    Print[{"   ",n,N[a],N[x],N[b]}];
            While[
            N[f[x]]!=0.,
            Print[N[f[a]],"  ",N[f[x]],"   ",N[f[b]]];
                    If[
                    f[b]f[x]<0,
                    a=x;x=N[(x f[b]-b f[x])/(f[b]-f[x])],
                    b=x;x=N[(a f[x]-x f[a])/(f[x]-f[a])]
                    ];
            n=n+1;
            If[n>100,Break[]
            ];
    Print[{"   ",n,N[a],N[x],N[b]}]
    ],"Na odabranom segmentu nije ispunjen nuzan uvjet postojanja rjesenja
    "]

Metoda uvijek konvergira. Konvergencija je brža nego kod metode polovljenja, ali sporija nego kod Newtonove metode.

Next: Rješavanje sustava jednadžbi Up: Numerička matematika Previous: Uvod Contents Index