Metoda polovičnog dijeljenja(druga imena: metoda bisekcije, metoda dihotomije) za rješavanje jednačine f(x) = 0 je kako slijedi. Neka bude poznato da je funkcija kontinuirana i da zauzima krajeve segmenta
[a, b] vrijednosti različitih predznaka, tada je korijen sadržan u intervalu ( a, b). Podijelimo interval na dvije polovice i onda ćemo razmotriti polovinu na čijim krajevima funkcija poprima vrijednosti različitih predznaka. Ponovo dijelimo ovaj novi segment na dva jednaka dijela i odabiremo onaj koji sadrži korijen. Ovaj proces se nastavlja sve dok dužina sljedećeg segmenta ne postane manja od tražene vrijednosti greške. Rigorozniji prikaz algoritma za metodu bisekcije:
1) Hajde da izračunamo x = (a+ b)/2; izračunajmo f(x);
2) Ako f(x) = 0, zatim idite na korak 5;
3) Ako f(x)∙f(a) < 0, то b = x, inače a = x;
4) Ako | b – a| > ε, idi na tačku 1;
5) Iznesite vrijednost x;
Primjer 2.4. Koristeći metodu bisekcije, precizirajte korijen jednadžbe ( x– 1) 3 = 0, koji pripada segmentu .
Rješenje u programu Excel:
1) U ćelijama A 1:F 4 uvodimo notaciju, početne vrijednosti i formule, kao što je prikazano u tabeli 2.3.
2) Svaku formulu kopirajte u donje ćelije sa markerom za popunjavanje do desetog reda, tj. B 4 - do B 10, C 4 - do C 10, D 3 - do D 10, E 4 - do E 10, F 3 - do F 10.
Tabela 2.3
| A | B | C | D | E | F | |
| f(a)= | =(1-B3)^3 | |||||
| k | a | x | f(x) | b | b-a | |
| 0,95 | =(B3+E3)/2 | =(1-C3)^3 | 1,1 | =E3-B3 | ||
| =IF(D3=0,C3; IF(C$1*D3<0;B3;C3)) | =IF(C$1*D3>0; E3;C3) |
Rezultati proračuna dati su u tabeli. 2.4. U koloni F provjera vrijednosti dužine intervala b – a. Ako je vrijednost manja od 0,01, tada se u ovom redu nalazi približna vrijednost korijena s navedenom greškom. Bilo je potrebno 5 iteracija da bi se postigla potrebna tačnost. Približna vrijednost korijena s tačnošću od 0,01 nakon zaokruživanja na tri decimale je 1,0015625 ≈ 1,00.
Tabela 2.4
| A | B | C | D | E | F | |
| f(a)= | 0,000125 | |||||
| k | a | x | f(x) | b | b-a | |
| 0,95 | 1,025 | -2E-05 | 1,1 | 0,15 | ||
| 0,95 | 0,9875 | 2E-06 | 1,025 | 0,075 | ||
| 0,9875 | 1,00625 | -2E-07 | 1,025 | 0,0375 | ||
| 0,9875 | 0,996875 | 3.1E-08 | 1,00625 | 0,0187 | ||
| 0,996875 | 1,0015625 | -4E-09 | 1,00625 | 0,0094 | ||
| 0,996875 | 0,9992188 | 4.8E-10 | 1,0015625 | 0,0047 | ||
| 0,99921875 | 1,0003906 | -6E-11 | 1,0015625 | 0,0023 | ||
| 0,99921875 | 0,9998047 | 7.5E-12 | 1,000390625 | 0,0012 |
Dati algoritam uzima u obzir mogući slučaj“udaranje u korijen”, tj. jednakost f(x) nula u sljedećoj fazi. Ako u primjeru 2.3 uzmemo segment , tada na samom prvom koraku dolazimo do korijena x= 1. Zaista, hajde da upišemo u ćeliju B 3 vrijednost 0,9. Tada će tabela rezultata imati oblik 2.5 (date su samo 2 iteracije).
Tabela 2.5
| A | B | C | D | E | F | |
| f(a)= | 0,001 | |||||
| k | a | x | f(x) | b | b-a | |
| 0,9 | 1,1 | 0,2 | ||||
Kreirajmo ga u programu Excel prilagođene funkcije f(x) i bisect(a, b, eps) za rješavanje jednadžbi metodom bisect koristeći ugrađeni jezik Visual basic. Njihovi opisi su dati u nastavku:
Funkcija f(Byval x)
Funkcija bisect (a, b, eps)
1 x = (a + b) / 2
Ako je f(x) = 0, onda idite na 5
Ako je f(x) * f(a)< 0 Then
Ako Abs(a - b) > eps Onda idite na 1
Funkcija f(x) određuje lijeva strana jednadžbe i funkcije
bisect(a, b, eps) izračunava korijen jednadžbe koristeći bisect metodu f(x) = 0. Imajte na umu da funkcija bisect(a, b, eps) koristi pristup funkciji f(x). Evo algoritma za kreiranje prilagođene funkcije:
1) Izvršite naredbu menija “Alati - Makro - Editor Visual basic" Prozor " Microsoft Visual Basic" Ako u ovaj fajl programe Excel makroi ili korisničke funkcije ili procedure još nisu kreirane, ovaj prozor će izgledati kao na slici 2.4.
2) Izvršiti naredbu menija “Insert - Module” i unijeti tekstove funkcija programa, kao što je prikazano na slici 2.5.
Sada u ćelijama lista programa Excel Možete koristiti kreirane funkcije u formulama. Na primjer, uđimo u ćeliju D 18 formula
Bisect(0,95;1;0,00001),
tada dobijamo vrijednost 0,999993896.
Da biste riješili drugu jednačinu (sa drugom lijevom stranom) potrebno je da odete u prozor uređivača pomoću naredbe „Alati - Makro - Editor Visual basic” i jednostavno prepišite opis funkcije f(x). Na primjer, pronađimo, s točnošću od 0,001, korijen jednadžbe sin5 x + x 2 – 1 = 0, koji pripada intervalu (0,4; 0,5). Da bismo to učinili, promijenimo opis funkcije
za novi opis
f = Sin(5 * x) + x^2 - 1
Onda u ćeliju D 18 dobijamo vrijednost 0,441009521 (uporedite ovaj rezultat sa vrijednošću korijena intervala (0,4; 0,5) pronađenog u primjeru 2.3!).
Za rješavanje jednadžbe koristeći metodu poludijeljenja u programu Mathcad napravimo funkciju potprograma bisec(f, a, b, ε), gdje je:
f- naziv funkcije koji odgovara lijevoj strani jednadžbe f(x) = 0;
a, b- lijevi i desni krajevi segmenta [ a, b];
ε - tačnost približne vrijednosti korijena.
Rješenje primjera u programu Mathcad:
1) Pokrenite program Mathcad. Hajde da uvedemo definiciju funkcije bisec(f, a, b, ε). Da biste to učinili, koristeći tastaturu i alatnu traku "Grčki simboli", otkucajte bisec(f, a, b, ε):=. Nakon znaka zadatka “:=” na alatnoj traci “Programiranje”, pomoću pokazivača miša kliknite lijevom tipkom miša na “Dodaj liniju”. Nakon znaka zadatka pojavit će se okomita linija. Zatim unesite programski tekst prikazan ispod, koristeći alatnu traku “Programiranje” da unesete znak “←”, operator petlje dok, operater break i uslovni operator ako je drugačije.
2) Hajde da uvedemo definiciju funkcije f(x):=sin(5*x)+x^2–1, a zatim izračunajte vrijednost korijena pomoću funkcije bisec na datim vrijednostima:
bisec(f, –0,8,–0,7,0,0001)=. Nakon znaka “=” automatski će se pojaviti korijenska vrijednost koju je program izračunao –0,7266601563. Izračunajmo preostale korijene na isti način.
Ispod je list Mathcad sa definicijom funkcije bisec(f, a, b, ε) i proračuni:
Hajde da damo program na jeziku C++ za rješavanje jednačine f(x) = 0 metodom prepolovljenja:
#include
#include
duplo f(dvostruko x);
typedef double (*PF)(double);
dupla bisec(PF f,double a, double b,double eps);
dupli a, b, x, eps;PF pf;
cout<< "\n a = "; cin >> a;
cout<< "\n b = "; cin >>b;
cout<< "\n eps = "; cin >> eps;
x = bisec(pf,a,b,eps); cout<< "\n x = " << x;
cout<< "\n Press any key & Enter "; cin >> a;
duplo f(dvostruko x)(
r = sin(5*x)+x*x-1;
duplo bisec (PF f, duplo a, duplo b, duplo eps)(
do( x = (a + b)/2;
ako (f(x) == 0) prekid;
ako (f(x)*f(a)<0) b = x;
)while (fabs(b-a) > eps);
Program ima funkciju f(x) je definirana za rješavanje jednačine
sin5 x + x 2 – 1 = 0
iz primjera 2.3. Rezultat programa za određivanje korena intervala (0,4; 0,5) sa tačnošću od 0,00001 je prikazan u nastavku (ekran računara):
Pritisnite bilo koji taster & Enter
Zadnji red je potreban za organiziranje pauze za pregled rezultata.
Nelinearne jednačine se mogu podijeliti u 2 klase - algebarske i transcendentalne. Algebarske jednadžbe nazivaju se jednadžbe koje sadrže samo algebarske funkcije (cijelobrojne, racionalne, iracionalne). Konkretno, polinom je cijela algebarska funkcija. Jednačine koje sadrže druge funkcije (trigonometrijske, eksponencijalne, logaritamske, itd.) se nazivaju transcendentalno.
Metode za rješavanje nelinearnih jednačina podijeljene su u dvije grupe:
- preciznim metodama ;
- iterativne metode .
Tačne metode omogućavaju zapisivanje korijena u obliku neke konačne relacije (formule). Iz školskog kursa algebre poznate su takve metode za rješavanje trigonometrijskih, logaritamskih, eksponencijalnih, kao i jednostavnih algebarskih jednačina.
Kao što je poznato, mnoge jednačine i sistemi jednačina nemaju analitička rješenja. Ovo se prvenstveno odnosi na većinu transcendentalnih jednačina. Takođe je dokazano da je nemoguće konstruisati formulu koja bi se mogla koristiti za rešavanje proizvoljne algebarske jednačine stepena većeg od četiri. Osim toga, u nekim slučajevima jednadžba sadrži koeficijente koji su poznati samo približno, pa samim tim i sam zadatak preciznog određivanja korijena jednadžbe gubi smisao. Za njihovo rješavanje koristimo se iterativne metode sa datim stepenom tačnosti.
Neka je data jednadžba
- Funkcija f(x) je kontinuiran na intervalu [ a, b] zajedno sa njegovim derivatima 1. i 2. reda.
- Vrijednosti f(x) na krajevima segmenta imaju različite predznake ( f(a) * f(b) < 0).
- Prvi i drugi derivati f"(x) I f""(x) zadržavaju određeni znak u cijelom segmentu.
Uslovi 1) i 2) garantuju da na intervalu [ a, b] postoji barem jedan korijen, a iz 3) slijedi da f(x) je monotona na ovom intervalu i stoga će korijen biti jedinstven.
Riješi jednačinu (1) iterativni metod znači utvrditi ima li korijena, koliko korijena i pronaći vrijednosti korijena sa potrebnom tačnošću.
Bilo koja vrijednost koja preokreće funkciju f(x) na nulu, tj. takav da:
pozvao root jednačine(1) ili nula funkcije f(x).
Problem nalaženja korijena jednadžbe f(x) = 0 iterativnom metodom sastoji se od dvije faze:
- odvajanje korena - pronalaženje približne vrijednosti korijena ili segmenta koji ga sadrži;
- preciziranje približnih korijena - dovođenje do određenog stepena tačnosti.
Proces odvajanja korijena počinje određivanjem znakova funkcije f(x) u granici x=a I x=b tačke u regionu svog postojanja.
Primjer 1 . Odvojite korijene jednadžbe:
|
f( x) є x 3 - 6x + 2 = 0. |
Napravimo približan dijagram:
Prema tome, jednadžba (2) ima tri realna korijena koja leže u intervalima [-3, -1] i .
Približne vrijednosti korijena ( početne aproksimacije) može biti poznato i iz fizičkog značenja problema, iz rješavanja sličnog problema s različitim početnim podacima, ili se može pronaći grafički.
Uobičajeno u inženjerskoj praksi grafička metoda određivanje približnih korijena.
Uzimajući u obzir da su pravi korijeni jednadžbe (1) presječne točke grafa funkcije f(x) sa x-osom, dovoljno je iscrtati funkciju f(x) i označite raskrsnice f(x) sa osovinom Oh, ili oznaka na osi Oh segmenti koji sadrže jedan korijen. Konstrukcija grafova se često može znatno pojednostaviti zamjenom jednačine (1) ekvivalentan njega sa jednačinom:
Jednačina (4) se može prikladno prepisati kao jednakost:
Iz ovoga je jasno da se korijeni jednadžbe (4) mogu naći kao apscise presječnih točaka logaritamske krive y= log x i hiperbole y = . Nakon što smo konstruisali ove krive, približno ćemo pronaći jedini korijen jednačine (4) ili odrediti segment koji ga sadrži.
Iterativni proces se sastoji od sekvencijalnog preciziranja početne aproksimacije X 0 . Svaki takav korak se zove iteracija. Kao rezultat iteracija, pronađen je niz približnih vrijednosti korijena X 1 , X 2 , ..., xn. Ako ove vrijednosti rastu sa povećanjem broja iteracija n pristupiti pravoj vrijednosti korijena, onda kažemo da je iterativni proces konvergira.
Da bismo pronašli korijen jednadžbe (1) koji pripada segmentu [ a, b], podijelite ovaj segment na pola. Ako f= 0, tada je x = je korijen jednadžbe. Ako f nije jednako 0 (što je u praksi najvjerovatnije), tada biramo onu od polovica ili na čijim krajevima je funkcija f(x) ima suprotne predznake. Novi suženi segment [ A 1 , b 1] ponovo podijelite na pola i izvršite iste radnje.
Metoda polovina je praktično zgodna za korištenje za grubo pronalaženje korijena date jednačine. Metoda je jednostavna i pouzdana i uvijek konvergira.
Primjer 3. Koristite metodu prepolovljenja da razjasnite korijen jednačine
f( x) = x 4 + 2 x 3 - x - 1 = 0
leži na segmentu [0, 1] .
Konzistentno imamo:
f(0) = - 1; f(1) = 1; f(0,5) = 0,06 + 0,25 - 0,5 - 1 = - 1,19;
f(0,75) = 0,32 + 0,84 - 0,75 - 1 = - 0,59;
f(0,875) = 0,59 + 1,34 - 0,88 - 1 = + 0,05;
f(0,8125) = 0,436 + 1,072 - 0,812 - 1 = - 0,304;
f(0,8438) = 0,507 + 1,202 - 0,844 - 1 = - 0,135;
f(0,8594) = 0,546 + 1,270 - 0,859 - 1 = - 0,043, itd.
Može se prihvatiti
x = (0,859 + 0,875) = 0,867
U ovoj metodi, proces iteracije se sastoji u tome da se sljedeće vrijednosti uzimaju kao aproksimacije korijenu jednadžbe (1): X 1 , X 2 , ..., x n tačke preseka tetive AB sa x-osom (slika 3). Prvo napišemo jednačinu tetive AB:
.
Za tačku presjeka tetive AB sa x-osom ( x = x 1 ,y = 0) dobijamo jednačinu:
Neka za sigurnost f""(x) > 0 at a x b(dešava se f""(x) < 0 se svodi na naše ako zapišemo jednačinu u obliku - f(x) = 0). Zatim kriva at = f(x) će biti konveksan prema dolje i, stoga, smješten ispod svoje tetive AB. Postoje dva moguća slučaja: 1) f(A) > 0 (slika 3, A) i 2) f(b) < 0 (Рисунок 3, b).
Slika 3, a, b.
U prvom slučaju kraj A nepomične i uzastopne aproksimacije: x 0 = b;x , gdje je funkcija f (X) ima predznak suprotan predznaku njegove druge derivacije f""(X).
Iterativni proces se nastavlja sve dok se to ne pronađe
| x i - x i - 1 |< e ,
gdje je e specificirana maksimalna apsolutna greška.
Primjer 4. Pronađite pozitivan korijen jednadžbe
f( x) = x 3 - 0,2 x 2 - 0,2 X - 1,2 = 0
sa tačnošću od e = 0,01.
Prije svega, odvajamo korijen. Jer
f(1) = -0,6< 0 и f (2) = 5,6 > 0,
tada traženi korijen x leži u intervalu . Dobijeni interval je velik, pa ga dijelimo na pola. Jer
f (1,5) = 1,425 > 0, zatim 1< x < 1,5.
Jer f""(x) = 6 x- 0,4 > 0 na 1< X < 1,5 и f(1.5) > 0, tada koristimo formulu (5) da riješimo problem:
= 1,15;
| x 1-x 0 | = 0,15 > e,
stoga nastavljamo sa proračunima;
f ( X 1) = -0,173;
= 1,190;
|x 2-x 1 | = 0,04 > e,
f (X 2) = -0,036;
= 1,198;
| x 3-x 2 | = 0,008 < e .
Dakle, možemo uzeti x = 1,198 sa tačnošću od e = 0,01.
Imajte na umu da je tačan korijen jednačine x = 1,2.
Neka f(x) – kontinuirana funkcija na [ a; b], .
Newtonova metoda (tangentna metoda)
Neka f(x)
je dvostruko kontinuirano diferencirana funkcija na intervalu [ a;
b],
,
I 
ne mijenjaj znak u [ a;
b].
Označimo sa 
onaj kraj segmenta gdje se nalaze znakovi 
I 
podudaraju se. Uzastopne aproksimacije do tačnog korijena c pronađite po formuli
Za 
.
Onda 
je tačan korijen jednačine (1).
Računarski proces se obično zaustavlja kada 
ispada da je tačnost manja od navedene ε
. Međutim, ovaj uvjet ne može striktno jamčiti da je navedena preciznost postignuta. Za potpunu sigurnost, možete izvršiti provjeru tačnosti kao što je navedeno na početku ovog odjeljka. Ako se ne postigne tačnost, potrebno je ponoviti iteracije još nekoliko puta.
Sekantna metoda
Neka postoji neka početna aproksimacija 
. Dobijamo još jedan bod koristeći formulu 
, Gdje h– mali broj. Pretpostavit ćemo da smo završili nekoliko koraka metode i u ovom trenutku imamo dvije uzastopne aproksimacije 
I 
do tačnog korijena (u početnoj fazi to je 
I 
). Zatim pronalazimo sljedeću aproksimaciju koristeći formulu
,
Proces se zaustavlja prema istom kriteriju kao u Newtonovom metodu.
Metoda iteracije
U metodi iteracije, originalna jednačina (1) se transformira u ekvivalentnu jednačinu 
. Odabrana je početna aproksimacija 
. Svaka sljedeća aproksimacija dobiva se formulom 
,
Proces se zaustavlja prema istom kriteriju kao u Newtonovom metodu. Metoda će konvergirati, tj. limit 
jednaka je tačnoj vrijednosti korijena ako nejednakost vrijedi u susjedstvu korijena 
a početna aproksimacija je prilično blizu korijenu.
Prednosti i nedostaci metoda
Metoda bisekcije zahtijeva da se korijen odvoji, a funkcija se mora evaluirati mnogo puta da bi se postigla visoka preciznost. Zagarantovano je postizanje navedene tačnosti u ovoj metodi.
Newtonova metoda ima vrlo brzu konvergenciju (kvadratna konvergencija), tj.
,
Gdje c– tačna vrijednost korijena; M– neke konstante ovisno o funkciji. Grubo govoreći, počevši od određene iteracije, broj tačnih decimalnih mjesta će se udvostručiti na svakoj iteraciji.
Da bi se garantovala konvergencija Newtonove metode, mora biti ispunjeno dosta uslova. Uopšteno govoreći, možete započeti proračune koristeći Newtonov metod bez provjere ovih uvjeta, ali tada se konvergencija možda neće primijetiti.
Metoda sekante obezbjeđuje za glatke funkcije stopu konvergencije blisku stopi konvergencije Newtonove metode. Ne zahtijeva izračunavanje derivacije funkcije. Ako se početna tačka uzme daleko od korijena, onda možda neće biti konvergencije.
Metoda iteracije daje stopu konvergencije znatno nižu od Newtonove metode. Ako postoji konvergencija, primjenjuje se procjena 
, Gdje 
– brojevi, 
,
;c– tačna vrijednost korijena. Količine M,
q ovise o funkciji i ne ovise o broju iteracije. Ako 
je tada blizu 1 q je također blizu 1 i konvergencija metode će biti spora. Proračun korištenjem metode iteracije može se započeti bez provjere uslova uključenih 
I 
. U tom slučaju proces može postati divergentan, a onda odgovor neće biti primljen.
Postoji mnogo metoda za pronalaženje korijena nelinearne jednadžbe osim onih koje su navedene. U MATHCAD-u, root funkcija je u formatu 
koristi metodu sekante, a ako ne dovede do željenih rezultata onda Mullerovu metodu. U potonjem, za razliku od metode sekante, u svakom koraku se uzimaju dvije dodatne točke, graf funkcije zamjenjuje se parabolom koja prolazi kroz tri tačke, a točka presjeka parabole sa osom se uzima kao sledeća aproksimacija Ox. U root funkciji u formatu root( f(x),
x,
a,
b) Koriste se Ridder i Brent metode. Za pronalaženje korijena polinoma u MATHCAD-u koristi se Laguerreova metoda.
Metoda dihotomije ima ime od starogrčke reči, što u prevodu znači deljenje na dvoje. Zato ova metoda ima i drugo ime: metoda prepolovljenja. Često ga koristimo. Recimo igranje igre "Pogodi broj", gdje jedan igrač pogađa broj od 1 do 100, a drugi pokušava da ga pogodi, vođen tragovima "više od" ili "manje od". Logično je pretpostaviti da će se prvi broj zvati 50, a drugi ako je manji - 25, ako je više - 75. Dakle, u svakoj fazi (iteraciji) nesigurnost nepoznate se smanjuje za 2 puta. One. čak i najnesrećnija osoba na svijetu će pogoditi skriveni broj u ovom rasponu u 7 pogađanja umjesto u 100 nasumičnih izjava.
Metoda poludijeljenja u rješavanju jednadžbe
Ispravno rješenje jednadžbe metodom polovina moguće je samo ako je poznato da na datom intervalu postoji korijen i da je jedinstven. To uopće ne znači da se metoda dihotomije može koristiti samo za rješavanje linearnih jednadžbi. Da biste pronašli korijene jednadžbi višeg reda korištenjem metode bisekcije, prvo morate razdvojiti korijene u segmente. Proces odvajanja korijena izvodi se pronalaženjem prvog i drugog izvoda funkcije i izjednačavanjem ih sa nulom f"(x)=0 i f""(x)=0. Zatim, predznaci f(x) u kritičnim i graničnim tačkama određuju se intervali u kojima funkcija mijenja predznak |a,b|, gdje je f(a)*f(b).< 0.
Algoritam metode dihotomije
Algoritam metode dihotomije je vrlo jednostavan. Razmotrimo segment |a,b| unutar kojeg se nalazi jedan korijen x 1
U prvoj fazi izračunava se x 0 =(a+b)/2
Zatim se određuje vrijednost funkcije u ovoj tački: ako je f(x 0)< 0, то , если наоборот, то ,т.е происходит сужение интервала. Таким образом в результате формируется последовательность x i , где i - номер иттерации.
Proračun se zaustavlja kada je razlika b-a manja od tražene greške.
Kao primjer korištenja metode polovičnog dijeljenja, korijen ćemo pronaći na intervalu jednačine x 3 -3*x+1=0 sa tačnošću od 10 -3
Kao što se može vidjeti iz tabele, korijen je 0,347. Broj iteracija je 10. Uslov završetka: a-b=0,0009< 10 -3
Metoda polovina ili metoda dihotomije je najjednostavniji za rješavanje jednadžbe pomoću numeričkih metoda.
Skinuti:
Rješavanje jednadžbe metodom dihotomije - Rješavanje jednadžbe metodom bisekcije u Pascalu.
Naziva se i metodom dihotomije. Ova metoda rješavanja jednadžbi razlikuje se od metoda o kojima se raspravljalo gore po tome što ne zahtijeva ispunjenje uvjeta da prvi i drugi izvod zadrže svoj predznak na intervalu. Metoda bisekcije konvergira za sve kontinuirane funkcije f(x), uključujući one koje se ne diferenciraju.
Podijelite segment na pola tačkom. Ako (što je praktično najvjerovatnije), onda su moguća dva slučaja: ili f(x) mijenja predznak na segmentu (Sl. 3.8), ili na segmentu (Sl. 3.9)
Odabirom u svakom slučaju segmenta na kojem funkcija mijenja predznak i nastavljajući proces daljeg prepolovljenja, može se doći do proizvoljno malog segmenta koji sadrži korijen jednačine.
Primjer 4. Jednačina 5x - 6x -3 = 0 ima jedan korijen na intervalu. Riješite ovu jednačinu koristeći metodu poludijeljenja.
Rješenje: Pascal program bi mogao izgledati ovako:
funkcija f(x: real): realna;
f:=exp(x*ln(5))-6*x-3;
a, b, e, c, x: realno;
dok abs(b-a)>e radi
ako je f(a)*f(c)<0 then
writeln("x=",x:3:3," f(x)=",f(x):4:4);
Rezultat izvođenja programa:
e=0,001 x=1,562 f(x)=-0,0047
20.Algoritam metode dijeljenja na polovine.
1. Odredite novu korijensku aproksimaciju X u sredini segmenta [a,b]: x=(a+b)/2.
2. Pronađite vrijednosti funkcije u tačkama A I X: F(a) I F(x).
3.Provjerite stanje F(a)*F(x)< 0 . Ako je uvjet ispunjen, tada se korijen nalazi na segmentu [Oh] b pređite na tačku x (b=x). Ako uvjet nije ispunjen, tada se korijen nalazi na segmentu [x,b]. U ovom slučaju, potreban vam je bod A pređite na tačku x (a=x).
4. Idite na korak 1 i ponovo podijelite segment na pola. Algoritam se nastavlja sve dok se ne ispuni uvjet /F(x)/< e (navedena tačnost).
21. Jednostavna metoda iteracije za pronalaženje korijena. Geometrijska interpretacija.
Originalna jednadžba f(x)=0 reducira se ekvivalentnim transformacijama na oblik sa odabranom nepoznatom na lijevoj strani, to jest, x=φ(x), gdje je φ(x) neka funkcija povezana s originalnom funkcijom f (x). Ovaj oblik pisanja jednadžbe omogućava, s obzirom na početnu aproksimaciju x 0, da dobijemo sljedeću, prvu aproksimaciju x 1 =φ(x 0), zatim dobijemo drugu aproksimaciju x 2 =φ(x 1) i tako dalje x n +1 =φ(x n)… . Niz (x n )= x 0, x 1, x 2, …, x n,… naziva se niz iteracija ili aproksimacija sa početnom vrijednošću x 0. Ako funkcija φ(x) nije kontinuirana i postoji granica ξ = lim x n kao n→∞, zatim, prelazeći na granicu u jednakosti x n +1 =φ(x n), nalazimo da je kao n→ ∞: lim x n +1 =lim φ(x n)=φ(lim x n ), odnosno, ξ=φ(ξ) Prema tome, ako niz aproksimacija konvergira, onda konvergira do korijena jednačine (2), a time i jednačine (1). Zbog konvergencije iterativnog procesa, ovaj korijen se može izračunati za dovoljno veliku n sa bilo kojom zadatom tačnošću. Međutim, potrebno je odrediti pod kojim uslovima će niz (x n) biti konvergentan. Dobijmo vezu između grešaka dve susedne aproksimacije - ε n i ε n +1: x n =ξ+ε n, x n +1 =ξ+ε n +1. Zamenimo ove reprezentacije u x n +1 =φ(x n) i proširimo funkciju u Taylorov red u blizini korena:ξ+ε n +1 =φ(ξ+ε n)=φ(ξ)+ε n φ'(ξ)+ (ε n 2 /2!)φ''(η), gdje je η O [ξ; ξ+ε n ] M Pošto je ξ korijen, onda je ξ=φ(ξ) , dobijamo: ε n +1 =ε n φ'(ξ)+(φ''(η)/2)ε n 2. Pošto je ε<1, то ε n 2 <<ε n . Поэтому если φ’(ξ) ¹ 0,то основной вклад в погрешность дает первое слагаемое, а слагаемым (φ’’(η)/2)ε n 2 можно пренебречь, то есть ε n +1 » ε n φ’(ξ).Это означает, что погрешность будет уменьшаться на каждом последующем шаге, если |φ’(ξ)|<1, тогда для любого n|ε n +1 |<|ε n |. Сформулируем теорему о сходимости метода простых итераций, дающую достаточные условия сходимости.
Teorema o konvergenciji jednostavne iteracijske metode. Neka je ξ korijen jednadžbe x=φ(x), funkcija φ(x) je definirana i diferencibilna na intervalu, a za x O sve vrijednosti funkcije φ (x) O . Zatim, ako postoji takav pozitivan broj q<1, что при x Î выполняется неравенство |φ’(ξ)|≤q<1, то на отрезке уравнение x=φ(x) имеет единственный корень x=ξ и процесс итераций, выраженный формулой x n +1 =φ(x n), где n=1,2,3… , сходится к этому корню независимо от выбора начального приближения x 0 Î .Таким образом, последовательность {x n },начинающаяся с любого x 0 Î , сходится к корню ξ со скоростью геометрической прогрессии, причем скорость сходимости тем выше, чем меньше величина q Î (1;0).Если функция φ(х) монотонно возрастает и 0<φ’(х)<1, то все приближения лежат по одну сторону от корня - такую сходимость называют монотонной (или ступенчатой) – рис.1. Если функция φ(х) монотонно убывает и 0>φ'(x)>-1, tada susjedne aproksimacije leže na suprotnim stranama korijena - takva konvergencija se naziva dvosmjerna (ili spiralna) - slika 2. Pošto je u ovom slučaju koren sadržan u intervalu, čiji su krajevi susedne aproksimacije – ξÎ(x n ,x n +1), onda je ispunjenje uslova |x n +1 -x n |<ε обеспечивает выполнение условия |ξ-x n +1 |<ε.
Da bismo mogli da uporedimo iterativne metode u smislu brzine konvergencije, uvode se sledeći koncepti:
Definicija 1: Konvergencija niza (x n) u ξ se naziva linearno(prema tome, iterativni proces je linearno konvergentno), ako postoji konstanta CO(0,1) i broj n 0 takvi da su nejednakosti |ξ-x n +1 |≤C|ξ-x n | za n≥n 0.
Za greške uvedene ranije to znači |ε n+1 |≤C|ε n |. U metodi jednostavne iteracije, konstanta C je vrijednost q, odnosno metoda konvergira linearno.
2. definicija: Niz aproksimacija (x n ) konvergira na ξ sa najmanje R reda (prema tome, iterativni proces ima najmanje str-ti red), ako postoje takve konstante C>0, str≥1 i n 0 , da su za sve n≥n 0 uslovi |ξ-x n +1 |≤C|ξ-x n | p (ili u drugim notacijama |ε n+1 |≤C|ε n | p).
