Lucrarea 05 - Rezolvarea Numerica a Ecuatiilor Algebrice

8/17/2019 Lucrarea 05 - Rezolvarea Numerica a Ecuatiilor Algebrice

1/14

METODE MUMERICE – LUCRĂRI DE LABORATOR #05

63

LUCRAREA #05

REZOLVAREA NUMERICĂ A ECUAŢIIILOR ALGEBRICE

REZUMATUL ŞI SCOPUL LUCRĂRII

În această lucrare de laborator se prezintă o serie de metode pentru rezolvareaecuaţiilor algebrice, polinomiale şi transcendente.

Există multe metode special concepute pentru a rezolva ecuaţii algebrice. Metodele de găsire a soluţiei sunt de obicei metode iterative. Aceste metode

furnizează un şir de aproximaţii, care tinde la x*, în anumite condiţii. O metodă iterativă presupune 3 aspecte importante:

Alegerea unei condiţii iniţiale pentru soluţia ecuaţiei; Relaţia de iteraţie ce stă la baza calculului şirului de aproximaţii; Condiţii de oprire a procesului iterativ de calcul.

Lucrarea are drept scop elaborarea unor funcţii MatLab pentru metodelerezolvare a ecuaţiilor algebrice şi transcendente:

metoda înjumătăţirii intervalului (metoda bisecţiei); metoda falsei poziţii; metoda lui Newton (metoda tangentei);

metoda secantei.

Însuşirea metodelor se va face pe exemple concrete de ecuaţii prin realizareaaplicaţiilor specifice.

Pentru ecuaţiile polinomiale se prezintă funcţiile predefinite în MatLab, care se potaplica direct.

CUPRINSUL LUCRĂRII

1. Consideraţii introductive 2. Metoda înjumătăţirii intervalului (metoda bisecţiei) 3. Metoda falsei poziţii4. Metoda Newton-Raphson (metoda tangentei)5. Metoda secantei6. Rezolvarea ecuaţiilor polinomiale 7. Aplicaţii de laborator


2/14

#05 Rezolvarea numerică a ecuaţiilor algebrice

64

1. Consideraţii introductive

Se consideră f(x)=0, cu x[a,b]., în care f(x) este o funcţie continuă, f(x):[a,b] →R. Se presupune că ecuaţia admite o soluţie reală x*, izolată pe acest interval şi se

doreşte găsirea ei. Dacă f(x) ar fi o funcţie liniară, problema este banală şi admite o soluţie analitică. Să presupunem că f(x) este neliniară. Dacă f este un polinom, atunci ecuaţia se

numeşte polinomială, dacă nu, ecuaţia se numeşte transcendentă. Metodele de găsire a soluţiei sunt de obicei metode iterative. Aceste metode

furnizează un şir de aproximaţii, care tinde la x*, în anumite condiţii. O metodă iterativă presupune 3 aspecte importante:

Alegerea unei condiţii iniţiale pentru soluţia ecuaţiei; Relaţia de iteraţie ce stă la baza calculului şirului de aproximaţii;

Condiţii de oprire a procesului iterativ de calcul. Se vor studia 4 metode iterative de rezolvare a ecuaţiilor şi anume: 1. Metoda bisecţiei sau metoda înjumătăţirii intervalului; 2. Metoda falsei poziţii; 3. Metoda lui Newton sau metoda tangentei.4. Metoda secantei

2. Metoda înjumătăţirii intervalului (metoda bisecţiei)

Se consideră ecuaţia f(x)=0, f : R →R continuă. Să presupunem că s-a găsit uninterval [a,b] R, pentru care: ( ) ( ) 0 f a f b , adică, există cel puţin o soluţie în acestinterval.

Găsirea acesteia folosind metoda bisecţiei presupune aproximarea succesivă a

rădăcinii ecuaţiei prin mijlocul intervalului [a,b] prin2

a b x

(fig. 5.1).

Dacă f(x)=0, atunci x este rădăcină pentru ecuaţie. În caz contrar, se calculeazăprodusul f(a)f(x). Dacă acesta este negativ atunci rădăcina se află în continuare înintervalul [a,x], altfel rădăcina se găseşte în cealaltă jumătate a intervalului iniţial [x,b].Calculele se reiau pentru noul interval.

Metoda este simplă şi necesită doar o evaluare de funcţie pentru fiecare iteraţie.

Să studiem cele 3 aspecte importante:a) condiţii iniţiale: se calculează f(a) şi f(b) in eventualitatea că a sau b sunt

soluţii ale ecuaţiei.b) Relaţia de iteraţie: la fiecare pas soluţia se aproximează cu jumătatea

intervalului rămas la pasul anterior, adică2

i i

i

a b x

(5.1)

c) Condiţii de oprire a procesului: b a tol sau ( ) f x tol pentru x [a,b].

Variabila tol reprezintă toleranţa cu care se calculează soluţia ecuaţiei.

Sfârşitul procesului se poate face şi la depăşirea unui număr maxim deiteraţii. Calculul numărului maxim de iteraţii se face astfel: după un număr


3/14


65

m de iteraţii, intervalul de căutare devine( )

2mb a

. Numărul de iteraţii va fi

dat de relaţia:( )

2mb a

tol

. În acest fel rezultă:

2 ( )log b am tol

(5.2)

a=a0

b=b0x0f(x)

f(a)=f(a0)

f(b)=f(b0)

0 00 2

a b x

a1

b1

x1

f(a1)

f(b1)

1 11 2

a b x

y

x

f(x0)*f(a0)


4/14


66

atunci Exit

sfarsit daca

5: Calculează sol=(a+b)/2 err=abs(b-a)

val=f(c)

6: afişează valorile obţinute

Rezolvarea în MatLab:În cele ce urmează se propune o soluţie de implementare a metodei bisecţiei în

limbajul de programare MatLab.Pentru a avea generalitate, adică pentru a putea fi folosit la orice ecuaţie algebrică,

se implementează, după algoritmul de mai sus, o funcţie care poate fi adăugată celorlaltefuncţii MatLab. Se mai face încă o data observaţia, ca pentru a funcţiona, aceasta trebuiesalvată într-un folder, a cărui cale a fost setată cu opţiunea Set path....

Codul de program MatLab pentru metoda bisecţiei poate fi următorul; acesta afost scris folosind multe comentarii pentru a putea fi înţeles mai uşor.

f unct i on [ sol ut i e, val , eroare]=mbi sect( f , a, b, t ol )echo of f ;%f unct i e pent r u r ezol var ea ecuat i i l or al gebr i ce pr i n met oda bi sect i ei%sau met oda i nj umat at i r i i i nt er val ul ui% I nt r ar i% f numel e f uncti ei descr i sa i nt r - un f i si er f uncti e% a l i mi t a st anga a i nt er val ul ui% b l i mi t a dr eapt a a i nt er val ul ui% t ol t ot er ant a de cacl ul% I esi r i% sol ut i e Sol ut i a ecuat i ei pe i nt erval ul stabi l i t% val Val oar ea f uncti ei i n "sol ut i e"

% er oar e Er oarea est i mat a pent r u sol ut i eya=f eval ( f , a) ;yb=f eval ( f , b) ;i f ya*yb0b=sol ut i e;yb=val ;

el sea=sol ut i e;ya=val ;

endi f b- a


5/14


67

sol ut i e=( a+b) / 2;val =f eval ( f , sol ut i e) ;er oar e=abs( b- a) / 2;

O dată scrisă şi salvată într-o cale definită, funcţia poate fi apelată pentru diverse

ecuaţii şi pentru diverse intervale.

Practic, pentru a calcula soluţiile unei ecuaţii folosind această metodă, respectivaceastă funcţie definită mai sus, se parcurg următoarele etape:

1. se defineşte într-un fişier function, funcţia matematică ce defineşte ecuaţia; 2. se reprezintă grafic funcţia, până când se descoperă intervalele pe care ecuaţia

are soluţii izolate. Citirea acestor date se poate face interactiv folosind funcţia MatLab ginput;

3. se apelează funcţia mbisect de tot atâtea ori, câte intervale s-au descoperit lapasul anterior.

Exemplul 5.1. Să se rezolve ecuaţia 3 3 1 0 x x .Se defineşte un fişier funcţie cu următorul conţinut:

f unct i on y = ex5_1( x)y = x. 3̂- 3*x+1

Se reprezintă grafic funcţia folosind funcţia fplot, astfel:

f pl ot ( ‘ ex5_1’ , [ - 2, 2] )gri d

Rezultă graficul din figura 5.2.

-2 -1. 5 -1 -0. 5 0 0. 5 1 1. 5 2

-1

-0.5

0

0.5

1

1.5

2

2.5

3

Fig. 5. 2 Reprezentarea grafică a funcţiei din exemplul 5.1.

De pe grafic se observă că ecuaţia prezintă soluţii pe intervalele [-2;-1,5], [0;0,5],

[1,5;2].Deci se aplică funcţia mbisect de 3 ori astfel:


6/14


68

[ sol ut i e1, val 1, er oar e1] =mbi sect ( ' ex5_1' , - 2, - 1. 5, 0. 0001)[ sol ut i e2, val 2, er oar e2] =mbi sect ( ' ex5_1' , 0, 0. 5, 0. 0001)[ sol ut i e3, val 3, er oar e3] =mbi sect ( ' ex5_1' , 1. 5, 2, 0. 0001)

rezultând soluţiile şi erorile de calcul:

sout i e1 =- 1. 8794

val 1 =1. 6125e- 004

er oar e1 =3. 0518e- 005

sol ut i e2 =0. 3473

val 2 =- 6. 3846e- 005

er oar e2 =

3. 0518e- 005

sol ut i e3 =1. 5321

val 3 =- 6. 0270e- 005

er oar e3 =3. 0518e- 005

Se vor scrie astfel de funcţii pentru diferite ecuaţii şi se vor experimenta la ora delaborator.

În Matlab este, de asemenea, implementată pentru ecuaţii de forma f(x)=0 o variantă ametodei bisecţiei prin funcţia fzero, cu sintaxa următoare (în forma cea mai simplă):

x = f zer o( ’ f unct ’ , x0)x = f zer o( ’ f unct ’ , x0, t ol )x = f zer o( ’ f unct ’ , x0, t ol , t r ace)

unde funct reprezintă numele dat de utilizator funcţiei f(x) a cărei expresie poatefi particular transcendentă, x0 este o aproximare iniţială a soluţiei ecuaţiei, x reprezintăsoluţia de aproximare a ecuaţiei dată de funcţia Matlab, tol toleranţa de calcul, iar variabilatrace controlează afişarea rezultatelor intermediare pe ecran.

Exemplul 5.2. Să se rezolve ecuaţia sin( ) 3 xe x .Se defineşte fişierul function cu definiţia ecuaţiei astfel:

f unct i on y1=ex5_2(x)y1=exp( x) - si n( pi *x) - 3

Se reprezintă grafic funcţia cu:

f pl ot ( ' ex5_2' , [ 0. 5, 1. 5])


7/14


69

0. 5 0. 6 0.7 0.8 0. 9 1 1. 1 1. 2 1.3 1. 4 1.5-2.5

-2

-1.5

-1

-0.5

0

0.5

1

1.5

2

2.5

Fig. 5. 3 Reprezentarea grafică a funcţiei din exemplul 5.2.

Se observă că soluţia se află în intervalul [1;1,1]. Oricare din aceste două valoripoate fi folosită pentru a afla soluţia ecuaţiei cu funcţia fzero:

x=f zer o( ' ex5_2' , 1)x =

1. 0476

Rezultatele pentru apelarea funcţiei cu celelalte două sintaxe se vor vizualiza încadrul orei de laborator.

3. Metoda falsei poziţii

Se consideră ecuaţia f(x)=0, f:R →R continua şi presupunem că s-a găsit un interval[a,b] R, pentru care: ( ) ( ) 0 f a f b , adică, există cel puţin o soluţie în acest interval.

Metoda calculului rădăcinii aproximative se face prin interpolarea liniară afuncţiei f (x) cunoscând 2 puncte (a, f (a)) şi (b, f (b)).

Cu alte cuvinte se împarte intervalul în două părţi prin intersecţia lui cudreapta ce trece prin punctele specificate mai sus (fig. 5.4).

Avem în acest caz: ( )( ) ( )

i i i

i i i i

x a f ab a f b f a

, de unde rezultă formula de iteraţie:

( ) ( )

( ) ( )i i i i

i

i i

a f b b f a x

f b f a

(5.3)

Concluzionând, se poate observa că regula falsei poziţii este asemănătoare curegula bisecţiei, prin împărţirea intervalului în 2 subintervale, pentru care punctul de

împărţire se calculează cu relaţia de mai sus şi păstrarea subintrevalului pentru carefuncţia schimbă semnul. După fiecare partiţionare a intervalului se reactualizează nunumai capetele intervalului, ci şi valorile corespunzătoare ale funcţiei, f (ai) şi f (bi).


8/14


70

La final se va obţine un şir de aproximaţii ale soluţiei ecuaţiei, care converge cătresoluţia exactă a ecuaţiei.

y

xai

bi

f(ai)

f(bi)

f(x)

xi

f(xi)

Fig. 5. 4 Împărţirea intervalului de căutare la metoda falsei poziţii

Să studiem şi în acest caz cele 3 aspecte importante: a) condiţii iniţiale: se calculează f(a) şi f(b) in eventualitatea că a sau b sunt

soluţii ale ecuaţiei.b) Relaţia de iteraţie: la fiecare pas soluţia se aproximează cu

( ) ( )

( ) ( )i i i i

i

i i

a f b b f a x

f b f a

c) Condiţii de oprire a procesului: în ipoteza unei toleranţe de calcul tol se

consideră că 1n x este o soluţie a ecuaţiei dacă 1n n x x tol sau 1( )n f x tol

pentru x[a,b].

După cele spuse mai sus se poate construi algoritmul de rezolvare al unei ecuaţiicu metoda falsei poziţii, folosind algoritmul descris la metoda bisecţiei. Acest lucrurămâne ca exerciţiu pentru studenţi.

4. Metoda Newton-Raphson (metoda tangentei)

Se consideră ecuaţia f(x)=0, f : R →R continua şi presupunem că s-a găsit uninterval [a,b] R, pentru care: ( ) ( ) 0 f a f b , adică, există cel puţin o soluţie în acestinterval.

Ipotezele pentru funcţia f(x) sunt următoarele: f este continuă pe intervalul [a,b]; f este derivabilă de 2 ori pe intervalul [a,b] şi derivata a doua păstrează

semn constant pe [a,b];

derivata I nu se anulează pe intervalul specificat. Metoda constă în aproximarea soluţiei ecuaţiei cu punctul de intersecţie al

tangentei la curba graficului, în punctele corespunzătoare soluţiei anterioare, cu axa Ox(fig. 5.5).


9/14


71

y

xx

...xn-1 xi x0

f(x0)

f(xi)

f(xn-1)

...

Fig. 5. 5 Metoda lui Newton

Metoda este cea mai eficientă datorită convergenţei rapide a şirului de aproximaţiicătre soluţia ecuaţiei.

Să studiem şi în acest caz cele 3 aspecte importante: a) condiţii iniţiale: este nevoie să se aleagă o soluţie iniţială a ecuaţiei. O bună

metodă ar fi alegerea lui x0 astfel încât: 0''( ) ( ) 0 f x f x , pentru x0 [a,b].Pentru uşurinţă se alege unul din capetele intervalului, care respectă această

relaţie;b) Relaţia de iteraţie: la fiecare pas soluţia se aproximează cu

1

( )

'( )i

i i

i

f x x x

f x (5.4)

c) Condiţii de oprire a procesului: în ipoteza unei toleranţe de calcul tol seconsideră că 1n x este o soluţie a ecuaţiei dacă 1n n x x tol . De asemenea, se

impune un număr maxim de iteraţii, iar funcţia ar trebui să spună dacăcondiţia de mai sus este îndeplinită după depăşirea numărului de iteraţii.

Avantajele metodei constau în evaluarea funcţiei într-un singur punct şi eficienţa

ei şi convergenţa rapidă spre soluţia ecuaţiei. Metoda are şi dezavantaje: necesită cunoaşterea în prealabil a derivatei I a funcţieişi rezultatele sunt eficiente doar pentru o aproximaţie iniţială x0 foarte apropiată de soluţiaexactă a ecuaţiei, altfel se poate întâmpla ca între soluţia exactă şi x0 funcţia să prezinte unpunct de extrem, caz în care se întrerupe şirul de calcule. De asemenea din condiţiainiţială, ar trebui să se cunoască chiar şi derivata a II-a.

Să scriem, conform celor spuse mai sus algoritmul metodei lui Newton:

Date de intrare:

a, b unul din capetele intervalului, care va fi prima aproximaţie f – funcţia continuă şi derivabilă de 2 ori

f’ – prima derivateă tol – pr ecizia determinării soluţiei nr_iteraţii – numărul de iteraţii


10/14


72

Date de ieşire: soluţie – soluţia ecuaţiei val – valoarea funcţiei în “soluţie” eroare – eroarea de calcul

nr_it – numărul de iteraţii după care s-a găsit soluţia

pentru i=1 până la max_iteratii Calculează xi=x i-1-f(x i-1)/f’(x i-1)dacă abs(x i-x i-1)


11/14


73

f unct i on y1 = ex5_3_1( x)y1 = x. 3̂- 3*x+1

f unct i on y2 = ex5_3_2( x)y2 = 3*x. 2̂- 3

f unct i on y3 = ex5_3_3( x)y3 = 6*x

Graficul funcţiei este cel din fig. 5.2. Deci, intervalele de căutare sunt cele de pegraficul respectiv.

Apelul funcţiei se face astfel:

[ sol ut i e1, val 1, er oar e1, nr _i t 1] =mnewt on( ' ex5_3_1' , ’ ex5_3_2’ , - 1. 5, 20, 0. 0001)[ sol ut i e2, val 2, er oar e2, nr _i t 2] =mnewt on( ' ex5_3_1' , ’ ex5_3_2’ , 0. 5, 20, 0. 0001)[ sol ut i e3, val 3, er oar e3, nr _i t 3] =mnewt on( ' ex5_3_1' , ’ ex5_3_2’ , 1. 5, 20, 0. 0001)

sol ut i e1 =- 1. 8794val 1 =- 3. 9968e- 014

eroare1 =8. 3097e- 008

nr _i t 1 =5

sol ut i e2 =0. 3473

val 2 =5. 7248e- 009

eroare2 =7. 4131e- 005

nr _i t 2 =3

sol ut i e3 =1. 5321

val 3 =1. 4189e- 011

eroare3 =1. 7570e- 006

nr _i t 3 =3

Comparaţi rezultatele obţinute cu metoda newton şi metoda bisecţiei.

5. Metoda secantei

Se consideră ecuaţia f(x)=0, f:R →R continua şi presupunem că s-a găsit un interval[a,b] R, pentru care: ( ) ( ) 0 f a f b , adică, există cel puţin o soluţie în acest interval.

Ipotezele pentru funcţia f(x) sunt următoarele: f este continuă pe intervalul [a,b]; f este derivabilă de 2 ori pe intervalul [a,b] şi derivata a doua păstrează

semn constant pe [a,b];

derivata I nu se anulează pe intervalul specificat.


12/14


74

Metoda secantei este asemănătoare cu metoda lui Newton, cu deosebirea că primaderivată a funcţiei este aproximată cu diferenţe finite. Vom vedea în continuare acestlucru.

Să studiem şi în acest caz cele 3 aspecte importante: a) condiţii iniţiale: este nevoie să se aleagă o soluţie iniţială a ecuaţiei. Ca şi la

metoda lui Newton, o bună metodă ar fi alegerea lui x0 astfel încât:

0''( ) ( ) 0 f x f x , pentru x0[a,b]. Pentru uşurinţă se alege unul din capeteleintervalului, care respectă această relaţie;

b) Relaţia de iteraţie: la fiecare pas soluţia se aproximează cu

1 00

( )( )

( ) ( )i

i i n

i

f x x x x x

f x f x

(5.5)

c) Condiţii de oprire a procesului: în ipoteza unei toleranţe de calcul tol seconsideră că 1n x este o soluţie a ecuaţiei dacă 1n n x x tol . De asemenea, se

impune un număr maxim de iteraţii, iar funcţia ar trebui să spună dacăcondiţia de mai sus este îndeplinită după depăşirea numărului de iteraţii.

Din compararea relaţiilor de iterare al celor două metode se obţine:

00

( ) ( )( )

'( ) ( ) ( )i i

i i i

i i

f x f x x x x x

f x f x f x

(5.6)

de unde rezultă că aproximarea cu diferenţe finite a derivatei este:

0

0

( ) ( )'( )

( )

ii

i

f x f x f x

x x

(5.7)

Deci, se poate spune că metoda secantei are marele avantaj că nu trebuie ştiută dela început care este derivata I a funcţiei, aceasta fiind exprimată prin relaţia de mai sus.

Se va scrie algoritmul de rezolvare în MatLab folosind algoritmul descris la

metoda lui Newton.

6. Rezolvarea ecuaţiilor polinomiale

Dacă în particular funcţia f(x) este un polinom de gradul n, de forma: 1

1 1 0( ) ...n n

n n f x a x a x a x a (5.8)

atunci rezolvarea ecuaţiei f(x)=0 este mult mai simplă, pentru că MatLab arepredefinită o funcţie în acest scop: roots.

Funcţia roots, poate fi apelată cu sintaxa:

r = roots( c )

unde c reprezintă un vector care conţine coeficienţii polinomului în ordinedescrescătoare a puterilor variabilei, adică:

c=[an an-1 ... a1 a0]


13/14


75

Exemplu 5.4. Să se determine rădăcinile ecuaţiei polinomiale: 8 5 4 23 10 3 0 x x x x .

Vectorul coeficienţilor este: c=[1 0 0 1 3 0-10 0 -3].

» c=[ 1 0 0 1 3 0 - 10 0 - 3]c =

1 0 0 1 3 0 - 10 0 - 3» r =r oot s( c)r =

0. 9409 + 1. 3396i0. 9409 - 1. 3396i

- 0. 8786 + 1. 1968i- 0. 8786 - 1. 1968i- 1. 42261. 2915

0. 0033 + 0. 5257i0. 0033 - 0. 5257i

Mai mult, MatLab mai are predefinită o funcţie, poly, prin intermediul căreia se potdetermina coeficienţii unei ecuaţii polinomiale, dacă se cunosc rădăcinile acesteia.

Sintaxa de apelare:

c = poly ( r )

Roots şi poly sunt funcţii inverse.

Se verifică exemplul de mai sus:

» c=pol y( r )c =

Col umns 1 t hrough 71. 0000 - 0. 0000 0. 0000 1. 0000 3. 0000 - 0. 0000 - 10. 0000

Col umns 8 t hrough 9- 0. 0000 -3. 0000

7. Aplicaţii de laborator

Aplicaţia 5.1. Să se rezolve ecuaţia cos(x)-x=0, folosind metodele descrise.

Indicaţii: Se scrie un fişier funcţie, care conţine definiţia funcţiei:

f unct i on y = apl i c5_1( x)y = cos( x) - x

Se reprezintă grafic funcţia folosind funcţia fplot, astfel:

f pl ot ( ‘ apl i c5_1’ , [ - 2, 2] )gri d

Rezultă graficul din figura 5.6.


14/14


76

-2 -1.5 -1 -0. 5 0 0. 5 1 1. 5 2

-2.5

-2

-1.5

-1

-0.5

0

0.5

1

1.5

2

Fig. 5. 6 Reprezentarea grafică a funcţiei din aplicaţia 5.1.

Se observă că ecuaţia admite o soluţie pe intervalul [0,5;1]. Deci, se apelează funcţia mbisectastfel:

[ sol ut i e, val , er oar e] =mbi sect( ' apl i c5_1' , 0. 5, 1, 0. 0001)

Care generează următorul rezultat:

sol ut i e =0. 7391

val =- 3. 3625e- 005

eroare =3. 0518e- 005

Folosirea funcţiei mNewton, implică scrierea a încă două fişiere function cu definiţiileprimelor derivate, astfel:

f unct i on y = apl i c5_1_1( x)y = - si n( x) - 1

f unct i on y = apl i c5_1_2( x)y = - cos( x)

Se alege ca soluţie iniţială capătul din dreapta al intervalului, adică x0=1 şi se apeleazăfuncţia mNewton astfel:

[ sol ut i e, val , er oar e, nr _i t ] =mnewt on( ' apl i c5_1' , ' apl i c5_1_1' , 1, 100, 0. 0001)

car e generează următorul rezultat: sol ut i e =

0. 7391val =- 2. 8472e- 010

eroare =2. 7758e- 005

Nr _i t =3

Lucrarea 05 - Rezolvarea Numerica a Ecuatiilor Algebrice

Documents

Transcript of Lucrarea 05 - Rezolvarea Numerica a Ecuatiilor Algebrice