REZOLVAREA NUMERICĂ A ECUAŢIILOR ALGEBRICE ŞI TRANSCENDENTE (Metoda bisectiei, Metoda secantei,...

8/7/2019 REZOLVAREA NUMERIC A ECUAIILOR ALGEBRICE I TRANSCENDENTE (Metoda bisectiei, Metoda secantei, Metoda

1/7

Carmen-Sanda Georgescu, Tudor Petrovici, Radu PopaMetode numerice. Fisa de laborator nr. 7:REZOLVAREA NUMERIC A ECUAIILOR

ALGEBRICE I TRANSCENDENTE (Metoda bisectiei, Metoda secantei,Metoda substitutiilor successive, Metoda lui Newton)

4. REZOLVAREA NUMERIC A ECUAIILORALGEBRICE I TRANSCENDENTEn aceast fi de laborator se prezint cteva metode pentru rezolvarea (determinarea rdcinilor)

unei ecuaii de forma f(x) = 0, dac f : X R R. Cnd f(x) este un polinom, sau poate fi adus, printransformri adecvate, la forma polinomial, ecuaia se numete algebric(de exemplu: f(x) = x3-3x+1=

0). n caz contrar, cnd f(x) conine expresii trigonometrice, logaritmi, exponeniale etc, ecuaia se

numete transcendent(de exemplu: f(x)= cosx-x= 0).

n principiu, rezolvarea ecuaiei f(x) = 0implic parcurgerea a dou etape:

separarea rdcinilor ecuaiei, prin precizarea intervalului n care se gsete fiecare rdcinreal a ecuaiei;

determinarea aproximativ (numeric) a fiecrei rdcini realei evaluarea erorii.Pentru cazul ecuaiei algebrice, n care f(x) se poate exprima ntotdeauna sub forma:

, (7.1)( ) 1axaaxaxaxaxf 0n

0k

knkn1n

1n1

n0 ==++++=

=

unde,K

exist metode specifice de determinare a rdcinilor reale. Exist metode adecvate i pentru probleme mai

speciale, ca ecuaiile polinomiale cu rdcini complexe, ecuaiile de variabil complex etc. n cele ce

urmeaz, se vor detalia acele metode care sunt uor de programat, n vederea rezolvrii problemelor

concrete.

4.1. METODE CU PROPRIETI DE CONVERGEN LINIAR

4.1.1. METODA BISECIEI

Metoda bisecieise mai numete i metoda njumtirii intervalului.

Fie funcia continuf: [a,b] Ri ecuaia f(x) = 0, algebric sau transcendent. Se admite ipo ezai, n acest caz, f(x) are pe [a,b] un numr impar de rdcini reale (cel puin una).

Principiul metodeiconst n njumtirea succes va intervalului de analiz, determinarea semnului

produsului valorilor funciei corespunztoare capetelor intervalului i adoptarea unei decizii adecvate. Se

noteaz cu

t

i

( ) ( ) 0bfaf

feroarea maxim admisibil corespunztoare valorii funciei. Algoritmul de calcul iterativeste

urmtorul:Pas 1: Fie c1 =(a+b)/2 mijlocul intervalului (a,b). Se calculeaza f(c1). Daca f(c1)=0, c1 este radacina

cautata, daca f(c1)0 atunci se calculeaza produsele f(a)* f(c1) si f(b)* f(c1) si se pastreaza pentru

calculele urmatoare acel interval (a, c1) sau (c1,b) pentru care produsul functiei la capete este negativPas 2: Presupunem ca acel interval este (a, c1). Fie c2=(a+ c1)/2 mijlocul intervalului (a, c1). Se calculeaza

f(c2). Daca f(c2)=0, c2 este radacina cautata, daca f(c2)0 atunci se calculeaza produsele f(a)* f(c2) sif(c2)* f(c1) si se pastreaza pentru calculele urmatoare acel interval (a, c2) sau (c2, c1) pentru care

produsul functiei la capete este negativ

Pas 3: Se continua procedeul si se obtine sirul c1, c2, . . ., cn , . . pana cand | ck+1- ck|x sau |f(ck)| f


2/7

unde kspecific ordinul iteraiei, iar x este abaterea impus asupra diferenei soluiilor aproximative dinsirul solutiilor la dou iteraii succesive (k-1) i k. Erorile admisibile f i/sau x sunt impuse de ctreutilizator !

Metoda biseciei este evident extrem de simpl, dar are cele mai slabe proprieti de convergen.

Dac n prealabil s-au separat rdcinile, metoda se poate aplica separat pe fiecare subinterval care

conine cte o rdcin a ecuaiei.Functie Octave pentru implementarea metodei bisectiei

Exemplul 1. Sa se determine radacina reala a ecuatiei f(x)=x^3-x-2=0, situata in intervalul (1,2) prinmetoda bisectiei si folosind 4 iteratii.Pas0: Pentru ca f(1)*f(2) function y=f(x), y=x.^3-x-3; endfunction

octave#2> [radacina,eabsoluta,valoare]=bisectie("f",1,2,0.0001,100)Rezulta: radacina = 1.5214, eabsoluta = 6.1035e-05, valoare = 1.4649e-06

4.1.2. METODA SECANTEIFie funcia continuf: [a,b] Ri ecuaia f(x) = 0, algebric sau transcendent. Se admite

ipoteza i, n acest caz, f(x) are pe [a,b] un numr impar de rdcini reale (cel puin una).

Principiul metodei: . Algoritmul de calcul i erativeste urmtorul (presupunem ca functia este convexa):

( ) ( ) 0bfaf t

octave#1>[radacina,eabsoluta,k,valoare]=bisectie(f,a,b,delta,max)# f=numele functiei; [a,b]=intervalul radacinii; delta=eroare;max=nr.iteratiiya=feval("f",a);yb=feval("f",b);for k=1:max

c=(a+b)/2;yc=feval("f",c);if yc==0

a=c;b=c;

elseif yb*yc>0b=c;yb=yc;

elsea=c;ya=yc;

endifif b-a < delta, break,endif

endforradacina=(a+b)/2;eabsoluta=abs(b-a);valoare=feval("f",c);endfunction


3/7

Pas 1: Se scrie ecuatia dreptei AB, unde A(a,f(a)) si B(b,f(b)) si se intersecteaza AB cu axa Ox . Fie C1(c1 ,0)

punctul de intersectie. Se calculeaza f(c1). Daca f(c1)=0, c1 este radacina cautata, daca f(c1)0 atuncise calculeaza produsele f(a)* f(c1) si f(b)* f(c1) si se pastreaza pentru calculele urmatoare acel interval

(a, c1) sau (c1,b) pentru care produsul functiei la capete este negativ; presupunem ca acel interval este

(a, c1).

Pas 2: Se scrie ecuatia dreptei AB1, unde A(a,f(a)) si B1(c1, f(c1)) si se intersecteaza AB1 cu axa Ox . FieC2(c2 ,0) punctul de intersectie. Se calculeaza f(c2). Daca f(c2)=0, c2 este radacina cautata, daca f(c2)0atunci se calculeaza produsele f(a)* f(c2) si f(c2)* f(c1) si se pastreaza pentru calculele urmatoare acel

interval (a, c2) sau (c2, c1) pentru care produsul functiei la capete este negativ;

Pas 3: Se continua procedeul si se obtine sirul c1, c2, . . ., cn , . . pana cand | ck+1- ck|x sau |f(ck)| funde kspecific ordinul iteraiei, iar x este abaterea impus asupra diferenei soluiilor aproximative

din sirul solutiilor la dou iteraii succesive (k-1) i k. Erorile admisibile fi/sau x sunt impuse dectre utilizator !

Functie Octave pentru implementarea metodei secantei

octave#1> function [radacina,eabsoluta,k,valoare]=secanta(f,p0,p1,delta,epsilon,max)# f=numele functiei; [p0,p1]=intervalul radacinii; delta=eroare absoluta admisa; epsilon=eroare

# admisa pentru functie; max=nr. iteratiifor k=1:maxp2=p1-feval("f",p1)*(p1-p0)/(feval("f",p1)-feval("f",p0));eabsoluta=abs(p2-p1);p0=p1;p1=p2;radacina=p1;valoare=feval("f",p1);if (eabsoluta


4/7

Bineneles c ecuaia iniial poate fi adus la forma (7.4) i prin alte artificii de calcul. n orice caz, se

constat c dac este rdcina ecuaiei iniiale, adic f() = 0, atunci aceasta va fi rdcini pentru

ecuaia (7.4), adic = F(). Fie x0[a,b] o valoare iniial, aproximativ, pentru rdcina exact .Metoda iterativ se definete prin rul de iteraii succesive:i

( ) ( )K

,, 1201 xFxxFx == , ( )k1k xFx =+ . (7.5)Condiia de convergen: Presupunnd cF(x) este derivabil pe [a,b], irul de iteraii succesive

(7.5) converge ctre dac:

( ) 1xF 1, respectiv ( ) 1xF > , irul iterativ (7.5) diverge. Gradul de convergen al metodei este

linear, deci eroarea de la iteraia (k+1) este proporional cu eroarea de la iteraia k.

Dac = F(), atunci este valabil i relaia: ( ) ( )+= F1 , unde < 1, care

sugereaz urmtoarea formuliterativ:( ) ( ) ( )kkk1k xxFx1x =+=+ . (7.7)

n acest caz, condiia de convergen: ( ) 1x


5/7

(METODA NEW TANGENTEI)

Aceast metod este cel mai frecvent utiliza pentru determinarea aproximativ a soluiei unei

ecuaii

TON-RAPHSON, SAU METODA

t

algebrice sau transcendente de forma f(x) = 0. Se admite c f(x) = 0 are n intervalul [a,b] o

singur rdcin real . n plus, se accept c derivatele ( )xf i ( )xf sunt funcii continue i

pstreaz semn constant pe intervalul [a,b]. Formula iterativa lui Newtoneste:

( )( )k

kk1k

xf

xfKK ,,,,, n210k=xx

=+ , unde (7.9)

n cadrul metodei lui Newton, condiia alegerii punctului de pornire x0este urmtoarea:

( ) ( ) 0xfx >f 00 , (7.10)

1 a,b].

pn la ndeplinirea condiiei:

aceasta asigurnd apartenena x[Metoda lui Newton se aplic iterativ

xk1k xx , (+ 7.11)

unde xeste o eroarea admisibil impus de ctre utilizator.cris astfel: plecnd din punctul de

coordonat

tangent intersecteaz axa Oxn care n mod uzual reprezint o estimare mbuntit a rdcinii

fa de estimarea precedent ocedeul se repet plecnd din punctul definit de coordonatele

Metoda lui Newton este mai rapid convergent dect metoda substituiilor succesive. Din acest

motiv,

ve pentru implementarea metodei Newton

ermine radacina reala a ecuatiei f(x)=x^3-x-2=0, situata in intervalul (1,2) folosind

ion

00001,50)

Din punct de vedere grafic, aceast metod poate fi des

e ( ){ }xfx , , se traseaz o tangent la curba f(x), panta tangentei fiind ( )xf . Aceastkk k

1kx +

kx . Pr

( ){ }1k1k xfx ++ , .

metoda lui Newton este preferat altor metode numerice de rezolvare a ecuaiilor algebrice i

transcendente, cu condiia ca forma funciei f(x) s fie precizat analitic, iar derivata ei s nu fie prea

complicat.

Functie Octa

octave#1> function [p0,err,k,y]=newton(f,df,p0,delta,epsilon,max)

0-f /df(p0);

err


6/7

4.2.2. METODA LUI NEWTON PENTRU DETERMINAREA RDCINII

Fie ecuaia:

UNEI ECUAII DE VARIABIL COMPLEX

( ) ( ) ( ) 0yxvyxuzf =+= ,i, , (7.12)

funciile u(x,y) i v(x,y) sunt

maginar a fu

Expresia (7.9) se poate generaliza pentru cazul complex, prin urmtoarele dou relaii:

de variabil complex ( )yxz i+= , unde precizate i reprezint parteareal, respectiv partea i nciei complexe f(z).

( kk yx )

k1kyxx

uy

vxx

,

+

+=+ , pentru22

uuuu

KK ,,,,, n210k=

(kk

yx

22

k1ky

u

x

u

y

uu

x

uvyy

,

+

+=+)

, (7.13)

unde expresiile funciilor i( )kk yxuu ,= ( )kk yxvv ,= , respectiv ale derivatelor u/xi u/y, din

lueaz pentru yk. Relaiile (7parantezele drepte, se eva xki .13) sunt formulele lui Newton pentru cazul

ecuaiilor de variabilcomplexi permit determinarea rdcinii ( )kkk yxz i+= .

Calculul iterativ continu pn la ndeplinirea simultan a condiiilor:

xk1k xx + i yk1ky + y (7.14)

impuse de ctre ilizator (aceste erori admisibile se pot ale ).undexiysunt erorile admisibile ut ge egaleFunctii Octave pentru rezolvarea ecuatiilor algebrice si transcendente

v= roots(p) .Rezolvarea ecuatiilor polinomiale de tip p(x)=a *x^n+a0 1*x^(n-1)++an-1*x+an.Intrari: p=vectorul care contine coeficientii functiei polinomiale .Iesiri: v=vectorul care contineradacinile ecuatiei polinomiale P(x)=0------------------------------------------------------------------------------------------------------------------ [x, fx, info] = fzero (fcn, approx, options) fcn(x,p1,p2,...).

out derivatives" (1971)Brent, R. P. "Algorithms for minimization with------------------------------------------------------ ------------------------------------------------------------

[x, info, msg] = fsolve (fcn, x0)Calculeaza solutia ecuatiei algebrice sau transcendente, pornind de la solutia de start x0. Remarcam

tiei este sensibil la valoarea de startca procesul iterativ de cautare a soluIntrari: Daca fcn, contine numai numele functiei f(x) si x0 este valoarea de start a solutiei, fsolve ,rezolva ecuatia /sistemul f(x) = 0. Daca fcn este un tablou de doua elemente, primul element estenumele functiei f iar al doilea element este jacobianul j(x)

df_ijac(i,j) = ----dx_j

aDe remarcat c se poate folosi si functia fsolve_options care poate contine un set de parametriientru fsolve


7/7

APLICAII DE LABORATOR

Problema 1. S se gseasc soluia aproximativ a ecuaiei , pentru , prin

metoda biseciei i n= 4pai de algoritm. S se compare rezultatul cu soluia exact= 1

03x4x2 =+ [ 520x ,; ]

Sa se determine radacinile ecuatiei folosind functia Octave roots

Problema 2. Aflai cu metoda biseciei valoarea lui4 3 , cu 3zecimale exacte pe intervalul [1, 2].

Sa se afle valoarea lui4 3 , cu 6 zecimale exacte folosind functia Octave fzero

Problema 3. S se analizeze i s se rezolve ecuaia ( ) 01x3xxf 3 =+= , folosind metoda

substituiilor succesive, cele trei soluii aflndu-se n intervalele: [ ]121 -, , i

. Sa se determine radacinile ecuatiei folosind functia Octave roots

[ 102 , ]

][ 213 ,

Problema 4. S se gseasc soluia ecuaiei ( ) 01x3xxf 3 =+= , pentru [ 10x , ] , prin metoda luiNewton, cu 4zecimale exacte. Sa se determine radacinile ecuatiei folosind functia Octave roots

S se gseasc soluia ecuaiei cu 8 zecimale exacte folosind functia Octave

fzero

( ) 01x3xxf 3 =+=

Problema 5 .Gsii soluia nenul a ecuaiei , cu metoda lui Newton i 4zecimale exacte.x21x

= eSa se gaseasca de asemenea aceisi solutie cu 10 zecimale exacte folosind functia Octave fzero

Problema 6.S se gseasc soluia ecuaiei de variabil complex ( ) 02z2zzf 2 =+= , cu metoda

lui Newton, plecnd de la aproximaia initial 75,050yxz 000 i,i +=+= .

Sa se verifice radacinile obtinute folosind functia Octave roots

REZOLVAREA NUMERICĂ A ECUAŢIILOR ALGEBRICE ŞI TRANSCENDENTE (Metoda bisectiei, Metoda secantei,...

Documents

Transcript of REZOLVAREA NUMERICĂ A ECUAŢIILOR ALGEBRICE ŞI TRANSCENDENTE (Metoda bisectiei, Metoda secantei,...