C l 2Cursul 2Rezolvarea numeric aRezolvarea numeric a

ecuaiilor algebrice

Rezolvarea numeric a ecuaiilor algebrice

metoda injumtirii intervaluluimetoda injumtirii intervaluluimetoda aproximrilor succesive

t d l i N tmetoda lui Newton

Rezolvarea numeric a ecuaiilor algebrice

Fie dat funcia f: RR. Se dorete determinarea uneia sau mai multor rdcini ale ecuaiei f(x)=0.

Exist cazul simplu pentru care se poate exprima o soluie a ecuaiei pornind de la exprima o soluie a ecuaiei pornind de la funcie, de exemplu cazul cazul ecuaiei de gradul 2:de g aduax2 + bx + c =0 pentru care soluia este:

4bb 2 sau2a

4ac-b-b- 2

2a4ac-b+b- 2

Rezolvarea numeric a ecuaiilor algebrice

Pentru diferitele metode vom presupune cf este o funcie continu i c exist un interval [a, b] unde ecuaia are o singur rdcin pe care o vom nota .

Pentru a alege intervalul [a b] se poate:Pentru a alege intervalul [a,b] se poate: fie utiliza metoda grafic (trasarea

curbei) i poziionarea soluiei de unde curbei) i poziionarea soluiei de unde alegerea lui [a,b],

fie utiliza metoda algebric: metoda gseparrii rdcinilor utiliznd teorema valorilor intermediare.

Definitie

f(x) admite o rdcin separat n [a,b]dac i numai dac este unicdac i numai dac este unic.

De asemenea, a separa rdcinile lui f( ) 0" d t i f(x)=0" nseamn determinarea intervalelor [a,b] n care fiecare

rdcin este unic.Pentru aceasta se poate utiliza teorema Pentru aceasta se poate utiliza teorema

valorilor intermediare.

Teorema valorilor intermediare:

Dac f este continu n [a,b] i f(a)*f(b) < 0 i f(a)*f(b) < 0 atunci [a,b] astfel nct f() = 0.i n plus dac f este monoton pe [a,b]

atunci este unic n [a,b].[ , ]

Teorema valorilor intermediare:Exemplul 1:Separai rdcinile ecuaiei x3 3x +1 = 0 n intervalul [3 , 3].1 Metoda algebric: f(x) = x3 3x +1 este o funcie polinomial, deci ea este continu n [3 , 3]. f(-3) = -17 < 0 , f(3) = 19 > 0 deci f(-3)f(3) < 0 de asemenea, dup teorema

valorilor intermediare, exist cel puin o rdcin a lui f(x) = 0 n [3 , 3]. Pentru a verifica unicitatea rdcinii studiem monotonia acesteia:f(x) = x3 3x +1 ;f (x) = 3x2 3 = 3(x-1)(x+1)

-3 -1 1 33 3_____________________________f (x) + + 0 - 0 +

_____________________________ 3 19 este unic n [ 3 1] cci f 3 19

f(x)

-17 -1

1 este unic n [-3 ,-1] cci f este monoton i f(-3).f(-1) < 02 este unic n [-1 , 1] cci f este monoton i f(-1).f(1) < 0 ( ) ( )3 este unic n [1 , 3] cci f este monoton i f(1).f(3)

Teorema valorilor intermediare:2 Metoda grafic:

Teorema valorilor intermediare:n acest caz rdcinile lui f(x) = 0 reprezint punctele interseciilor

graficului lui f cu axa xOx - deci e suficient s se traseze graficul lui f i s se determine punctele interseciilor. Acestea fcute vom avea intervalele de unde separarea rdcinilor intervalele, de unde separarea rdcinilor.

n cazul n care f este complicat, trebuie s se transforme ecuaia f(x)=0 intr-o ecuaie echivalent g(x) = h(x) cu f i g dou funcii mai simple Punctele interseciilor graficelor lui f i g sunt atunci mai simple. Punctele interseciilor graficelor lui f i g sunt atunci regsite.

Pentru exemplul nostru am fi putut transforma f(x) = 0 n dou funcii mai simple.

ntr-adevr x3 3x +1 =0 x3 = 3x - 1 h(x) = x3 i g(x) = 3x 1

de unde graficul i soluiile: g intersecia a dou curbe 3 intersecii, 3 soluii, 3 intervale

Metoda injumtirii intervalului:I.1 Condiiile de convergen ale metodei:

Metoda njumtirii intervalului converge dac :j g1. f este continu n [a,b]2. f(a)f(b) < 03. separat n [a, b].

d d f l n aceast metod se definesc seriile urmtoare:(an)nN , (bn)nN (xn)nN pana cand (xn)nN converge ctre .Pentru aceasta se pune: a = a b = b i se calculeaz

b+ax 00=a0 = a, b0 = b, i se calculeaz

Dac f(a0).f( x0)

Metoda injumtirii intervalului:Estimarea erorilor metodei:

a (b a)/ 2nan- (b-a)/ 2nbn- (b-a)/ 2nxn- (b-a)/ 2n+1

Pentru calcularea aproximrilor unei rdcini ( [a,b]) a unei ecuaii f(x)=0 prin metoda njumtirii intervalului, pentru o estimare dat se utilizeaz: pentru o estimare dat se utilizeaz: xn- (b-a) / 2n+1 (b-a) / 2n+1 n L .

O dat ce L a fost gsit se calculeaz x1 , x2 ,.., xL pornind de la x gsit n [a b] Se spune atunci c x este de la x0 gsit n [a,b]. Se spune atunci c xL este aproximarea lui cu estimarea dat.

Metoda aproximrilor succesive:

Aceast metod const n a scrie ecuaia f(x)=0 sub forma echivalent x=g(x) f(x)=0 sub forma echivalent x=g(x) cu g o funcie continu:f( ) 0 ( ) [ b] f(x)=0 x=g(x), x[a,b]

Aceasta revine la a construi o serie

[ ]

baindatx0n , )g(xx n 1+n =

[ ] ba,in dat x0

Metoda aproximrilor succesive:

II.1 Condiiile de convergen ale metodei:

Metoda converge ctre soluia dac:1. g este contractant n [a,b], de verificat:P i d fi ii t t t t [ b] Prin definiie: g este contractant pe [a,b]

dac 0

Metoda aproximrilor succesive:

II.1 Condiiile de convergen ale metodei:

2. [a,b] Interval de stabilitate pentru g g([a,b]) [a,b]

C l l l l i f([ b]) Calculul lui f([a,b]) :Dac f este cresctoare f([a,b])= [f(a),f(b)]Dac f este descresctoare f([a,b])= [f(b),f(a)]Dac f este descresctoare f([a,b]) [f(b),f(a)]

Metoda aproximrilor succesive:

II 2 Estimarea erorilor metodei:II.2 Estimarea erorilor metodei:nk-x

01n x-x k)-(1

x

k

n1n 1n x-x k)-(1

-x+

+

cu k = constant de contracie.

Metoda aproximrilor succesive:

Pentru a crea o serie pornind de la f(x)=0 , se pot considera exemplele urmtoare.

1 / f( ) 2 3 41 / f(x) = x2 - 3x - 4f(x) = 0 x2 - 3x - 4 =0 x2 = 3x + 4 x= de unde:f(x) = 0 Xn+1 = g(Xn ) cu n [ 0 , 4 ]4 3x )( +=xg

2 / f(x) = x - Ln(x+1) - 0.2f(x) = 0 x = Ln(x+1) + 0.2 de undef(x) = 0 X = g(X ) cu g(x) = Ln(x+1) + 0 2 n [ 0 5 ]f(x) = 0 Xn+1 = g(Xn ) cu g(x) = Ln(x+1) + 0.2 n [ 0 , 5 ]

3 / f(x) = x - e-x

f(x) = 0 x = e-x de unde:f(x) = 0 Xn+1 = g(Xn ) cu g(x) = e-x n [ 0 , 5]

Metoda aproximrilor succesive:

Exemplul 2:

Folositi metoda aproximarilor succesive pentru functia:

f(x)=cos(x)-x n intervalul [0 1]f(x)=cos(x) x n intervalul [0, 1].

Metoda aproximrilor succesive:Construirea seriei numerice:f(x)=0 cos(x)-x = 0 x = cos(x) de unde seria xn+1 = cos(xn); de unde

g(x)=cos(x) Se considera h(x) = xg(x)=cos(x). Se considera h(x) = x. Cercetarea grafic a intervalului [a,b] pentru care procesul iterativ xn+1

= g(xn) converge ctre soluie a ecuaiei x - g(x) =0 x [a,b] .

1 : curba funciei y = x ;1 : curba funciei y = x ;2 : curba funciei y= cos(x) .1 2 este soluia lui g(x) - x = 0 , deci dup traseul curbei [a,b] = [0 ,1]

[0 ,1] [0 ,1]

Metoda aproximrilor succesive:g este contractant pe [0,1]?Utilizm teorema pentru a verifica:g'(x) = sin(x) g'(x) =sin(x) x [0 1] g (x) = -sin(x) g (x) =sin(x) x [0,1] maxg'(x) = max ( sin(x) ) < 1 x [0,1] deci g este contractant pe

[0,1].

intervalul [0,1] este stabil ? x [0,1] g(x) este descresctoare g( [a,b]) = [g(b), g(a)] g([0 1]) = [g(1) g(0)]= [cos(1) cos(0)]=[cos(1) 1] [0 1] de unde [0 1] g([0,1]) = [g(1),g(0)]= [cos(1),cos(0)]=[cos(1),1] [0,1] de unde [0,1]

este stabil.Condiiile de convergen fiind verificate, procesul iterativ xn+1 = g(xn )

converge ctre soluie a lui cos(x) - x =0 , adic a lui f(x) = 0.converge ctre soluie a lui cos(x) x 0 , adic a lui f(x) 0.

Metoda aproximrilor succesive:

Exemplul 3:

Folositi metoda aproximarilor succesive pentru functia:

f(x) = x2 3x 4 in intervalul [3/2, 9/2 ].

Metoda aproximrilor succesive: Construirea seriei numerice:f(x) = 0 x2 = 3x + 4 de unde seriacu

=+=+

0 x 4 x x

0n1n4 3x +=x

43x)( +=xgcu Cercetarea grafic a intervalului [a,b] pentru care procesul iterativ

xn+1=g(xn) converge ctre soluie a ecuaiei x - g(x) =0 x [a,b] .f(x) = x2 3x 4

43x )( +=xg

f(x) = x 3x 4f (x) = 2x 3

-3/2 0 3/2 9/2_____________________________f (x) - 0 + _____________________________

+11/4 11/4+11/4 11/4f(x) -4

-25/4 S d i il dSepararea rdcinilor ne d :1 soluie unic in [-3/2 ,3/2 ] i2 soluie unic n [3/2 , 9/2 ]

Metoda aproximrilor succesive:g este contractant pe [3/2 , 9/2 ]?g(x) = < 1 deci g este contractant pe [3/2 , 9/2 ] sik(constanta de contracie) =3/4 k(constanta de contracie) =3/4 .

intervalul [3/2 , 9/2 ] este stabil?g([3/2 9/2 ]) [g(3/2) g(9/2) ] [ ] [3/2 9/2 ] deci 35/22/17g([3/2 , 9/2 ]) = [g(3/2),g(9/2) ] = [ ] [3/2 , 9/2 ] deci

intervalul [3/2 , 9/2 ]este stabil.

Condiiile de convergen fiind verificate procesul iterativ x = g(x )

35/2 , 2/17

Condiiile de convergen fiind verificate, procesul iterativ xn+1 = g(xn ) converge ctre soluie a lui x2 3x 4 = 0 n [3/2 , 9/2 ] x0 [3/2 , 9/2 ].

Metoda lui Newton:

Aceast metod const n a crea o serie x = g(x) pornind de la ecuaia f(x) = 0 x = g(x) pornind de la ecuaia f(x) = 0. Aceast serie este sub forma :

)(x' f)f(x - x x

n

nn1n =+

cu x dat n [a b]cu x0 dat n [a,b],deci g(x) = x f(x) /f (x).

Metoda lui Newton:III.1 Condiii de convergen:Pentru a trata convergena procesului lui Newton se

poate utiliza metoda aproximrilor succesivepoate utiliza metoda aproximrilor succesive(punctul fix), ceea ce revine la a verifica:1/ este g contractant ? t d t ti d i bil d i C2ntr-adevr g este continuu derivabil deci g C2 ;g(x) = 1 ((f (x))2 f(x). f (x)) / (f (x))2 = = f(x) f (x)/(f (x))2 . ( ) ( )/( ( ))Exist un interval [a,b] apropiat de n care| g(x) |

Teorema lui Newton:Condiii de convergen local:Fie f(x)=0 dac f verific ipotezele urmtoare: 1/ f de clas C2 n [a b] 1/ f de clas C2 n [a,b] (de dou ori derivabil i f " continu)2/ f(a) f(b)

Teorema lui Newton:Condiii de convergen global:In plus peste cele patru ipoteze ale

convergenei locale f verific o a cincea ipotez care este:

/ f ( ) / f ( ) b5/ | f (c) / f (c) | b-a pentruc=a dac | f (a) | | f (b) |c=b dac | f (b) | | f (a) |

atunci x [a,b] procesul lui Newton converge ctre soluia .

Metoda lui Newton:III 2 Estimarea erorii:III.2 Estimarea erorii:Pentru metoda lui Newton exist estimrile

erorilor urmtoare:erorilor urmtoare:

1/)f(x

x nn 1 /

2/ 21nnn xx|Mx

mn

2 /

3/ cu

1nnn 2m2n

0n x2M

M2mx

3 / cu

m = min | f (x) | x [ a,b ] i

0n 2mM

| ( ) | [ , ] M = max | f (x) | x [ a,b ].

Metoda lui Newton:E empl l 4Exemplul 4:

3 /Fie ecuaia x3 + x 1 =0 n [1/2 , 1].

S t i t l t d i l i N t t S se arate c ipotezele metodei lui Newton sunt satisfcute n [1/2 , 1].

Metoda lui Newton:Teorema lui Newton local :Teorema lui Newton local :f(x)= x3 + x 1 1/ f este de clas C2 cci este o funcie polinomial2/ f(1/2) f(1) 02/ f(1/2) . f(1) 03/ f (x) = 3x2 + 1 > 0 x [1/2 , 1] deci f (x) 0 x [1/2 , 1]4/ f (x) = 6.x > 0 x [1/2 , 1] deci f (x) conserv semnul constant n

[1/2 1] deci ipotezele lui Newton locale sunt satisfcute i x[1/2 [1/2 , 1] , deci ipotezele lui Newton locale sunt satisfcute i x[1/2 , 1] astfel c

f(x0).f (x0) >0 procesul converge.

pentru x0 = 1 , procesul converge cci f(x0).f (x0) >0 dimpotriv, pentru x0 = 1/2 , nu se poate nimic spune cci f(x0).f (x0) < 0.

Metoda lui Newton:Teorema lui Newton global:Teorema lui Newton global:Primele patru ipoteze sunt satisfcute;Se verific dac | f (c) / f (c) | ba pentru c=a daca | f (a) | | f (b) |

c b daca | f (b) | | f (a) |c=b daca | f (b) | | f (a) |

f(x)= x3 + x 1f ( ) 3 2 1 0 t t d i f (1/2) f (1) d i 1/2f (x) = 3x2 + 1 >0 este cresctoare deci f (1/2)< f (1) deci c =1/2.S verificm c | f (c) / f (c) | b a :ntr-adevr | f () / f () | = 3/8 = 3/14

/7/4

i b a = 1 1/2 = iar 3/14 < 1/2 atunci ipotezele teoremei lui N t l b l t ti f t d i 0 [1/2 1] I i Newton globale sunt satisfcute deci x0 [1/2 , 1]. In consecin procesul de Newton converge ctre soluia lui f(x) = 0

Metoda lui Newton:Remarc: Remarc: Pentru alegerea intervalului se poate utiliza de exemplu metoda grafic:A se trasa 1 curba funciei y = x3 ;A se trasa 2 curba funciei y 1 x A se trasa 2 curba funciei y = 1- x .Soluia va fi 1 2 . Se remarc, dup graficul de mai jos c soluia se

situeaz n [ [1/2 , 1].1.5

1

0.5g x( )

h x( )

1 20

0 0.5 1 1.50.5

x