Metode
numerice - Aplicatii
Lucrarea 8.
Ecuatii neliniare: metode de partitionare si metode de aproximatii succesive
Index:
Tema A - Metode de partitionare
A.1. Metoda bisectiei
<----------- algoritm
A.2. Metoda secantei
<----------- algoritm
Tema B - Metode de aproximatii
succesive
B.1. Metoda contractiei
<----------- algoritm
B.2. Metoda Newton
<----------- algoritm
Orice ecuatie care nu are forma a * x+b=0 se numeste neliniara si
se exprima sintetic:
f(x) = 0
Daca functia f(x) are forma
unui polinom sau poate fi adusa la aceasta forma, ecuatia se numeste algebrica.
In caz contrar - cand f(x) are o forma oarecare - ecuatia
se numeste transcendenta. De exemplu functiile:
genereaza ecuatii algebrice,
in timp ce functiile:
genereaza ecuatii transcendente.
Un punct
din intervalul de definitie al lui f(x) cu proprietatea
f( )=0
se
numeste zerou al functiei f(x) sau radacina
a ecuatiei f(x)=0.
Metodele de rezolvare a ecuatiilor neliniare au toate caracter iterativ
si se impart in doua mari categorii: metode de partitionare
si metode de aproximatii succesive.
Pentru metodele de partitionare,
folosind principiul partitionarii, intervalul de lucru este micsorat progresiv,
pana la o deschidere suficient de mica pentru a satisface precizia impusa.
Metodele din aceasta categorie (metoda bisectiei
sau metoda secantei)
sunt metode sigure - in sensul in care radacina este intotdeauna izolata
intr-un interval suficient de ingust - dar se caracterizeaza printr-o convergenta
lenta.
Metodele de aproximatii succesive
pornesc de la o aproximatie initiala, pe care o imbunatatesc
in pasi succesivi si, in anumite conditii, converg catre solutia exacta.
Metoda contractiei
si metoda Newton
sunt principalele metode de acest tip, dar exista o
gama larga de variante ale lor, concepute in scopul imbunatatirii performantelor.
Metodele de aproximatii succesive sunt, de regula, mai rapide decat metodele
de partitionare, dar prezinta riscul divergentei atunci cand in vecinatatea
zeroului cautat, functia f(x) are o comportate specifica.
Tema
A - Metode de partitionare
Dupa incadrarea unei solutii exacte, se pot aplica o serie de metode iterative
care permit determinarea unei solutii aproximative in limita preciziei
impuse. Dintre acestea, metodele de partitionare actioneaza
direct asupra intervalului in care a fost incadrata solutia, urmarind "comprimarea"
acestuia pana la limita impusa de criteriul de oprire. Din aceasta categorie
fac parte metoda bisectiei,
metoda secantei si
metoda
cautarii cu pas variabil. Deoarece la fiecare iteratie, intervalul
de lucru incadreaza permanent solutia exacta, convergenta acestor metode
este garantata. Din pacate, ele se caracterizeaza printr-un numar mare
de iteratii necesare atingerii preciziei impuse, deci prin timpi de calcul
mari.
Inapoi la index
Metoda bisectiei
Metoda bisectiei, numita uneori si metoda dihotomiei sau
a injumatatirii intervalelor, este cea mai simpla dintre
metodele de rezolvare a ecuatiilor algebrice si transcendente. Se considera
ca, printr-un procedeu oarecare, s-a reusit localizarea radacinii exacte
a ecuatiei f(x)=0 in intervalul [,].
In ipoteza in care functia f(x) este continua, iar radacina
este singurul zerou al lui f(x) in [,],
la extremitatile intervalului functia ia valori de semne contrare: f()
* f()<0.
Determinarea aproximatiei '
a radacinii exacte
cu o precizie
folosind metoda bisectiei foloseste urmatoarea schema (vezi si figura
de mai sus): intervalul [,]
se injumatateste prin punctul m=(+)/2
si
se calculeaza produsul f(m) * f().
Daca f(m) * f()
este
pozitiv, radacina
se gaseste intre si
m.In acest caz, se retine valoarea lui m ca extremitatea dreapta
a intervalului (<--
m)
si se reia procedeul. Daca f(m) * f()
este
negativ, radacina
se gaseste intre m si .
De aceasta data, se modifica extremitatea stanga a intervalului (<--
m)
si se reia procedeul. Aceasta schema se aplica in mod repetat pana cand
lungimea intervalului [,]
- modificat de la o iteratie la alta - scade sub valoarea limita 2*,
adica -
< 2*. Daca,
in acest moment, se considera ca radacina aproximativa
'=(+)/2,
acesta nu se indeparteaza de solutia exacta
cu mai mult de .
Desigur, intr-un caz banal, este posibil ca, in cursul injumatatirii
intervalelor succesive [,],
punctul m sa coincida cu radacina exacta .
Aceasta situatie se recunoaste prin anularea produsului f(m) * f(),
caz in care schema de calcul se intrerupe, dispunand in acest caz chiar
de radacina exacta '=m=.
Algoritmul
1 - Ecuatii neliniare - Metoda bisectiei
- Definirea functiei f(x), a intervalului de lucru
[,],
a preciziei si
a numarului maxim de iteratii Nmax.
- Procesul iterativ:
- Initializarea procesului iterativ: It <-- 0;
- Daca s-a atins precizia doritta (-
< 2*)
sau numarul maxim de iteratii Nmax se incheie bucla iterativa si se trece
la pasul 3.
- Se trece la o noua iteratie: It <-- It+1;
- Injumatatirea intervalului curent:
m <-- (+)/2
;
- Stabilirea noului interval de lucru:
- Daca f(m) * f()<0,
radacina se gaseste in [m , ];
se actualizeaza limita stanga: <--
m si se trece la pasul 2.vi;
- Daca f(m) * f()>0,
radacina se gaseste in [ , m];
se actualizeaza limita dreapta: <--
m si se trece la pasul 2.vi;
- Daca f(m) * f()=0,
radacina este m; se actualizeaza ambele limite: <--
m,<-- m
si se trece la pasul 2.vi;
- Se revine la pasul 2.ii;
- Calculul radacinii aproximative:
x <-- (+)/2.
Inapoi la index
Metoda secantei
Metoda secantei, numita si metoda partilor proportionale,
restrange intervalul [,]
ce incadreaza solutia exacta in iteratia curenta prin raportarea la valorile
functiei la extremitatile intervalului. Astfel, daca noua aproximatie x
se alege astfel incat solutia exacta sa se gaseasca in intervalul [,
x], valoarea lui x rezulta din egalitatea proportiilor:
Interpretarea geometrica a acestei relatii corespunde constructiei din
figura. Astfel, pe intervalul [,]
curba y=f(x) este aproximata prin dreapta ce trece prin cele doua puncte
A
si B de la extremitatile intervalului. In aceste
conditii, solutia exacta () urmeaza
a fi aproximata prin abscisa punctului de intersectie a dreptei AB
cu axa OX, notata cu x. Noua aproximatie x
se determina impunand conditia ca in ecuatia dreptei AB :
punctul (x,y) sa se gaseasca
pe axa OX, adica y=0:
In continuare, dintre intervalele
[, x ] si
[ x ,] se
retine acela ce incadreaza solutia
- acel interval la extremitatile caruia functia f(x) ia valori de
semne contrare. Aplicand o relatie asemenatoare noului interval se obtine
o noua aproximatie a solutiei exacte si procesul continua pana la satisfacerea
unui criteriu de oprire.
Algoritmul
2 - Ecuatii neliniare - Metoda secantei
- Definirea functiei f(x),
a intervalului de lucru [,
],
a preciziei si
a numarului maxim de iteratii Nmax.
- Procesul iterativ:
- Initializarea procesului iterativ: It <-- 0;
- Daca s-a atins precizia dorita (-
< 2*) sau
numarul maxim de iteratii Nmax se incheie bucla iterativa si se trece
la pasul 3.
- Se trece la o noua iteratie: It <-- It+1;
- Calculul noii aproximatii:
- Stabilirea noului interval de lucru:
- Daca f(m) * f()<0,
radacina se gaseste in [ x,];
se actualizeaza limita stanga:<--
x si se revine la pasul 2.ii.
- Daca f(m) * f()>0,
radacina se gaseste in [,x];
se actualizeaza limita dreapta:<--
x si se revine la pasul 2.ii.
- Daca f(m) * f()=0,
radacina este x; se actualizeaza ambele limite:
<-- x,
<-- x
si se revine la pasul 2.ii.
- Calculul radacinii aproximative: x <--
(+
)/2.
Inapoi la index
Tema
B - Metode de aproximatii succesive
Dupa cum reiese si din numele lor, metodele de aproximatii succesive
determina o solutie aproximativa a unei ecuatii neliniare prin construirea
unui sir de aproximatii succesive care, in anumite conditii, converge catre
solutia exacta. De aceasta data nu se mai actioneaza asupra intervalului
in care a fost izolata solutia exacta. Acest interval este folosit numai
pentru stabilirea aproximatiei initiale, care poate fi aleasa, in
principiu, oriunde in interiorul acestuia. Din categoria metodelor de aproximatii
succesive fac parte metoda contractiei
si metoda Newton.
O caracteristica a metodelor de aproximatii succesive se refera la
interpretarea geo- metrica ce se asociaza procesului iterativ. Pentru
metodele de partitionare, rezolvarea ecuatiei f(x)=0 se face prin
determinarea din aproape in aproape, pana la o precizie impusa, a punc- tului
de intersectie a curbei y=f(x) cu axa absciselor. Metodele de aproximatii
succesive inlocuiesc ecuatia sub forma implicita f(x)=0 cu o ecuatie
echivalenta exprimata insa explicit:
a carei rezolvare presupune determinarea
punctului de intersectie a curbelor; y=(x) si
y=g(x). Din considerente de simplificare a calculelor, se cauta ca
expresiile functiilor (x)
si g(x) sa aiba o complexitate cat mai redusa posibil. In acest
sens, cele mai raspandite metode utilizeaza un caz particular al ecuatiei
explicite, si anume, acela pentru care curba y = (x)
se reduce la o dreapta, iar ecuatia explicita capata forma:
Determinarea radacinii aproximative se face pornind de la o aproximatie
initiala x_0, corectata apoi succesiv folosind o formula de recurenta
de forma:
Daca sirul aproximatiilor succesive este convergent, el tinde catre solutia
exacta a ecuatiilor
echivalente f(x)=0, respectiv x=g(x). Diferitele metode
de aproximatii succesive folosite in practica se deosebesc prin modul de
construire a ecuatiei explicite, in particular, prin alegerea functiei
g(x),
alegere care determina si conditiile specifice de convergenta.
In comparatie cu metodele de partitionare, convergenta metodelor de aproximatii
succesive este, de regula, mai rapida, dar din pacate nu intotdeauna asigurata.
Inapoi la index
Metoda contractiei
Inlocuirea ecuatiei f(x)=0 printr-o ecuatie explicita x=g(x)
se poate realiza, de regula, pe mai multe cai. Cea mai simpla dintre acestea
determina functia g(x) sub forma:
g(x) = x + f(x)
In continuare, vom considera ca metoda
contractiei, numita uneori impropriu si metoda aproximatiilor succesive,
este generata de functia g(x) de aceasta forma. Sirul aproximatiilor
succesive este generat pornind de la aproximatia initiala x_0 ,
cu relatia de recurenta:
Se poate arata ca intre erorile de aproximare in doua iteratii succesive
e_n
si e_(n+1) exista relatia :
care permite stabilirea unei forme
primare a conditiei de convergenta. Astfel, pentru ca sirul aproximatiilor
succesive sa fie convergent, eroarea de aproximare trebuie sa scada
intre doua iteratii consecutive, adica |e_(n+1)| <
|e_n|, ceea ce conduce la |g'()|
< 1. Aceasta reprezinta o conditie necesara, dar nu si suficienta pentru
asigurarea convergentei. O valoare subunitara in modul a derivatei g'()
garanteaza existenta unui interval [,],
in jurul solutiei exacte ,
in care poate fi aleasa aproximatia initiala x_0, astfel incat procesul
iterativ sa fie convergent. De fapt, o conditie de forma |g'(x)|
< 1 trebuie satisfacuta in intregul interval [,].
Chiar daca conditia |g'()|
< 1 este satisfacuta, dar aproximatia initiala este aleasa departe de
solutia exacta ,
structura functiei g(x) poate conduce la un proces divergent.
Convergenta procesului iterativ este guvernata de o teorema de punct
fix care, in principiu, impune urmatoarele conditii: pentru
un interval [,],
oricat de larg, alegerea unei aproximatii initiale x_0 in
interiorul acestuia, care sa asigure convergenta, este arbitrara
daca si numai daca functia g(x) este o aplicatie strict
contractanta pe acel interval (vezi figura de mai jos).
Interpretarea geometrica a notiunii
de "aplicatie strict contractanta". (a) Functia g(x) este o aplicatie
strict contractanta pe un anumit interval daca proiectia acestui interval
pe axa Oy, prin curba y = g(x) se contracta. (b) In
caz contrar, cand proiectia intervalului respectiv pe axa Oy,
prin curba y = g(x) se dilata, g(x) nu mai este o aplicatie
strict contractanta.
Evolutia
unor procese iterative convergente sau divergente este ilustrata in figura
de mai jos. In functie de semnul derivatei g' in vecinatatea solutiei ,
convergenta poate fi monotona (cazurile a
si b), pentru g'()>0,
sau oscilanta (cazurile c si d),
pentru g'()<0.
De asemenea, in cazurile e si f
sunt prezentate doua procese divergente, unul monoton si celalalt oscilant.
Cazul |g'()|=1
este deosebit de sensibil deoarece, in functie de forma curbei y=g(x),
se poate obtine atat convergenta (cazul g),
cat si divergenta (cazul
h) sirului aproximatiilor
succesive.
Convergenta monotona
Inapoi
Convergenta oscilanta
Inapoi
Divergenta
Inapoi
Cazul
|g'()|=1
Inapoi
Verificarea conditiilor teoremei de punct fix este insa o sarcina mult
prea neproductiva din punctul de vedere al timpului de calcul si al complexitatii
calculelor pentru a fi si practica. Se prefera verificarea, cel mult, a
unei conditii de forma |g'()|
< 1 si localizarea stricta a solutiei ,
iar cel mai frecvent se impune un numar maxim de iteratii la epuizarea
carora procesul iterativ este intrerupt fortat.
Algoritmul
3 - Ecuatii neliniare - Metoda contractiei
- Definirea functiei f(x), a aproximatiei initiale x, a
preciziei Eps si a numarului maxim de iteratii Nmax.
- Construirea functiei g(x) = x + f(x).
- Procesul iterativ:
- Initializarea procesului iterativ: It <-- 0;
- Daca s-a atins precizia dorita (|f(x)|<Eps) sau numarul
maxim de iteratii (It=Nmax) se intrerupe bucla iterativa si se trece la
pasul 4.
- Se trece la o noua iteratie: It <-- It+1;
- Calculul noii aproximatii: x <-- g(x)
- Se revine la pasul 3.2.
- Stabilirea conditiilor de iesire din bucla iterativa:
- Daca |f(x)|<Eps - proces convergent - solutia aproximativa
este x.
- Daca |f(x)|>=Eps si It=Nmax, se afiseaza mesajul
"Depasire numar maxim iteratii".
Inapoi la index
Metoda Newton
Una dintre cele mai cunoscute si mai folosite tehnici de rezolvare a ecuatiilor
neliniare este metoda Newton, denumita uneori si metoda
Newton-Raphson sau metoda tangentelor. Ea se deosebeste
de alte metode de aproximatii succesive prin faptul ca pentru fiecare punct
din sirul aproximatiilor este necesara atat evaluarea functiei f(x)
ce defineste ecuatia, cat si a derivatei acesteia f '(x).
Valoarea aproximativa a radacinii exacte
se calculeaza folosind un sir de aproximatii succesive {x_0, x_1, x_2,
... } construit dupa urmatorul model. Pornind de la aproximatia x_0,
curba y=f(x) este aproximata in punctul de coordonate (x_0, f(x_0))
prin tangenta la ea. Noua aproximatie x_1 se obtine la intersectia
acestei tangente cu axa absciselor. Folosind pe x_1 ca aproximatie
initiala, se reia procedeul, determinandu-se o noua aproximatie x_2
s.a.m.d. pana cand abaterea intre doua iteratii succesive scade sub o valoare
prag impusa: |x_(n+1) - x_n| <.
Alegerea aproximatiei initiale influenteaza
in buna masura procesul iterativ. (a) Daca aproximatia initiala este prea
departe de solutia exacta, este posibil ca, datorita unei forme aparte
a curbei y = f(x), noile aproximatii sa fie aruncate spre infinit.
(b) Intr-o situatie mai fericita, procesul ramane convergent, dar sirul
aproximatiilor succesive se indreapta catre o alta radacina decat cea cautata.
Din
punct de vedere formal, metoda Newton foloseste formula de recurenta (iterare):
Conditiile de convergenta ale metodei Newton sunt relativ complexe ca forma
si se refera nu numai la functia f(x), ci si la primele sale doua
derivate, f '(x) si f ''(x).
Marele avantaj al metodei Newton este rata mare de convergenta. In apropierea
solutiei exacte, se asigura practic dublarea numarului de cifre exacte
ale solutiei calculate la fiecare iteratie. Aceasta proprietate remarcabila
este "cartea de vizita" ce recomanda metoda Newton ca fiind cea mai eficienta
cale de rezolvare a unei ecuatii neliniare pentru care este posibila evaluarea
derivatei f '(x). Remarcati totusi precizarea din fraza anterioara
("In apropierea solutiei exacte...") si nu uitati conditiile de convergenta
atat de alambicate, care se refera atat la functia f(x), cat si
la primele sale doua derivate. Din aceste cauze, despre metoda Newton se
spune ca are proprietati locale de convergenta foarte bune, dar se poate
comporta lamentabil la nivel global. In situatiile din urma metoda Newton
poate fi aplicata ca o procedura terminala, pentru rafinarea eficienta
si foarte rapida a unei aproximatii obtinute prin aplicarea, in prima faza,
a unei alte metode, mai putin sensibile din punctul de vedere al convergentei
dar, in principiu, mai lenta.
Algoritmul
4 - Ecuatii neliniare - Metoda Newton
- Definirea functiei f(x), a derivatei f '(x), a aproximatiei
initiale x, a preciziei Eps si a numarului maxim de iteratii
Nmax.
- Initializarea procesului iterativ: It <-- 0;
- Procesul iterativ:
- Se trece la o noua iteratie: It <-- It+1;
- Calculul corectiei: dx <-- - f(x) / f '(x)
- Calculul noii aproximatii: x <-- x + dx
- Daca s-a atins precizia dorita (|dx| <= Eps) sau
numarul maxim de iteratii (It=Nmax) se intrerupe bucla iterativa si se
trece la pasul 4.
- Se revine la pasul 3.1.
- Stabilirea conditiilor de iesire din bucla iterativa:
- Daca |dx|<Eps - proces convergent - solutia aproximativa
este x.
- Daca |dx|>=Eps si It=Nmax, se afiseaza mesajul "Depasire
numar maxim iteratii".
Inapoi la index
Pentru detalii suplimenatare privind
metodele de rezolvare a ecuatiilor neliniare, se poate consulta cartea
"Calcul numeric cu aplicatii in Turbo Pascal".
Aplicatii - Lista lucrarilor de laborator