Metode numerice

18

CAPITOLUL II REZOLVAREA NUMERIC A ECUAIILOR ALGEBRICE I TRANSCENDENTE

Pentru rezolvarea aproximativ a unei ecuaii de forma f(x)=0, f:AR, AR se pun dou probleme: a) Separarea rdcinilor reale ale ecuaiei. Prin anumite procedee se afl intervale de forma (r,R), respectiv ( R

_

, r_), care conin rdcinile reale pozitive, respectiv negative ale ecuaiei f(x)=0. Folosind alte metode se stabilete numrul de rdcini reale ale ecuaiei pe aceste intervale. Se determin apoi , pentru fiecare rdcin, cte un interval (a,b) de lungime mic ce conine doar acea rdcin. Dac pentru fiecare rdcin real s-a gsit un astfel de interval, spunem c am separat rdcinile reale ale ecuaiei f(x)=0. b) calculul fiecreia din rdcinile reale cu precizia dorit (eroarea absolut a rdcinii determinate s nu depeasc o valoare dat!) n cele ce urmeaz vom aborda rezolvarea numeric a ecuaiilor

1. algebrice, care au forma f(x)=0, unde f este un polinom oarecare de grad n cu coeficieni reali, nN, n2, n fiind gradul ecuaiei;

2. transcendente, care sunt ecuaii ce nu pot fi reduse la ecuaii algebrice folosind operaiile de adunare, nmulire, ridicare la putere,. De exemplu, ecuaiile: (x-2)2-lnx=0, cosx-x+0,5=0, ex-(x-1)2=0

sunt transcendente. Ecuaia iraional 06x5xx 4 3 =++ este o ecuaie algebric, deoarece, prin ridicarea la puterea

a patra, se scrie x4 =x3+5x+6 sau x4 -x3-5x-6=0. 2.1 Aflarea limitelor rdcinilor reale ale unei ecuaii algebrice. Pentru determinarea intervalelor care conin rdcinile reale ale ecuaiei algebrice de gradul n

P(x)=a0xn+ a1xn-1+ a2xn-2++ akxn-k++ an-2x2+ an-1x+ an=0, a00, an0, akR, n,0k = , (2.1.1) se cunosc mai multe metode dintre care prezentm dou, considerate mai eficiente.

a) Metoda lui Lagrange. Teorema 2.1.1 (Lagrange) Dac a0>0, iar ak (k1) este primul dintre coeficienii negativi ai polinomului

P(x), atunci rdcinile pozitive ale ecuaiei (2.1.1) sunt mai mici dect k0a

B1+ , adic

k0

pa

B1x +< , (2.1.2)

unde B este cel mai mare dintre modulele coeficienilor negativi. Demonstraie. Fie x>1. Minorm polinomul P(x), eliminnd termenii cu coeficieni pozitivi cu excepia lui

a0xn i nlocuind coeficienii negativi cu -B, obinem

( )1x

1xBxa1x...xxBxa)x(P1kn

n0

1knknn0

=+++++

.

Minorm n continuare P(x), folosind i x>x-1 xk-1(x-1)>(x-1)k

[ ] [ ]B)1x(a1x

xB)1x(xa1x

x

1xxBxa)x(P k0

1kn1k

01kn1kn

n0

>

=

+

++

.

Dac 0B)1x(a k0 , adic 0

ka

B)1x( sau k0a

B1x , rezult c pentru k0a

B1x + avem P(x)>0 ceea ce

Joseph Louis Lagrange (1736-1813)

Metode Numerice- Siclovan I., Heljiu M.

19

nseamn c P(x) nu se poate anula n puncte k0a

B1x + , deci rdcinile pozitive xp ale ecuaiei verific (2.1.2).

Observaia 2.1.1 Numrul k0a

B1R += este, prin definiie , o limit superioar a rdcinilor pozitive ale

ecuaiei (2.1.1) cu semnificaia c rdcinile pozitive ale acestei ecuaii sunt situate pe axa ox la stnga lui R.

Cu substituia y1

x = , teorema 2.1.1 ne d o limit inferioar a rdcinilor pozitive ale ecuaiei (2.1.1) pe care

o notm cu r. ntr-adevr, dup efectuarea substituiei se afl ecuaia algebric n y , nmulind eventual cu -1 pentru a

obine coeficientul lui yn pozitiv. Se aplic teorema 2.1.1 care ne d yp , de unde rezult c

rdcinile pozitive ale ecuaiei (2.1.1) sunt mai mari dect r. Am aflat astfel c (r,R) este intervalul rdcinilor pozitive pentru ecuaia (2.1.1). Cu substituia x= -z se afl o limit inferioar R

_

a rdcinilor negative ale ecuaiei (2.1.1), iar cu substituia

u

1z = se afl o limit superioar r

_

a rdcinilor negative. Astfel, (R_

, r_

) este intervalul rdcinilor negative pentru

ecuaia (2.1.1). b) Metoda sumelor alternate pentru determinarea limitei superioare a rdcinilor pozitive ale unei ecuaii algebrice. Fie polinomul P(x)=a0xn+ a1xn-1+ a2xn-2++ akxn-k++ an-2x2+ an-1x+ an, a0>0, an0, aiR.

Scriem P(x) sub forma unor sume de termeni cu semne alternate

P(x) = Q1(x) - Q2(x) + Q3(x) - Q4(x) ++ Q2m-1(x) - Q2m(x)= [ ] =

n

1j j21j2)x(Q)x(Q ,

unde Q1(x) este suma termenilor consecutivi ai polinomului P(x) cu coeficieni pozitivi , ncepnd cu a0xn, -Q2(x) este suma termenilor consecutivi ai lui P(x) cu coeficieni negativi , care urmeaz imediat dup termenii lui Q1(x), Q3(x) este suma termenilor consecutivi ai lui P(x) cu coeficieni pozitivi care urmeaz imediat dup termenii lui -Q2(x), .a.m.d., ultima sum -Q2m(x) fiind format din termenii consecutivi ai lui P(x) cu coeficieni negativi sau identic nul.

Notm cu cj, m,1j = numerele pozitive pentru care .0)c(Q)c(Q jj2j1j2 Putem lua ca limit superioar a rdcinilor pozitive ale ecuaiei (2.1.1) R=max{ c1,c2,,cm}. (2.1.3) ntr-adevr, punnd

++++++=

+++

+

++ 1)qp(jn)j(

qp1pjn)j(

2ppjn)j(

1p1pjn)j(

p1jn)j(

2jn)j(

12j1-2j xb...xbxbxb...xbxb(x)Q -(x)Q

unde 0b )j(s , s=1,2,,p+q, 0b)j(

1 > , putem scrie pentru x>0

++++++=

+++

+

q

)j(qp

2

)j(2p

)j(1p)j(

p2p)j(

21p)j(

11pjn

2j1-2jx

b...

x

bx

bb...xbxbx(x)Q -(x)Q . (2.1.4)

Se observ din (2.1.4) c funciile )x(Q)x(Q j21j2 , m,1j = cresc cnd x crete. Deci pentru x>cj>0

avem 0)c(Q)c(Q)x(Q)x(Q jj2j1j2j21j2 > .

Atunci pentru x>R (vezi 2.1.3), toate funciile din (2.1.4) sunt pozitive deci i suma lor, astfel c

[ ] 0)x(Q)x(Q)x(P m1j j21j2

> ==

, iar de aici rezult c P(x) se poate anula numai pentru valori mai mici dect R.


20

Aadar rdcinile pozitive xp ale ecuaiei (2.1.1) verific xp+

+0, deci c=0,5 , de unde zp

21

Fig. 2.2.1

y

f(b)

0

f(a)

a

A

x1

B

bx

y

f(a)

0f(b)

A

Bxa

x

x x1

2 3

b

pentru care cutm limita superioar a rdcinilor pozitive.

Cu metoda lui Lagrange ak = a1 = - 6, k = 1, a0 = 4, B=max{| - 6|, | - 5|, | - 2|, | - 3|} = 6 25

231

461

a

B1u k0

p =+=+=+< . Atunci

52

x52

z 25

z

1u p

pp >>

22

Se afl cte o singur rdcin real a ecuaiei f(x)=0 n acela din intervalele (-,x1),( x1,x2),, (xk,xk+1),,(xn,+)

(a,x1),( x1,x2),, (xk,xk+1),,(xn,b) la capetele creia funcia f are valori de semne contrare. n felul acesta numrul rdcinilor reale ale ecuaiei f(x)=0 pe intervalul (-,) sau (a,b) este egal cu numrul schimbrilor de semn din irul lui Rolle, dac f(xk)0, n,1k = . Dac unul din termenii irului lui Rolle este nul, de exemplu dac f(xk)=0, cum i 0)x( f k = rezult c xk este rdcin dubl n cazul 0)x( f k , respectiv tripl dac 0)x( f k = iar 0)x( f k .a.m.d. n aplicaii, metoda irului lui Rolle (care se utilizeaz pentru ecuaii algebrice i transcendente) are dezavantajul c ea necesit rezolvarea ecuaiei 0)x( f = care poate fi la fel de dificil ca i rezolvarea ecuaiei f(x)=0. 2. Metoda irului lui Sturm Fie funcia f: R, derivabil ( interval inclus n R). Definiia 2.2.2 Se numete ir Sturm asociat funciei f, irul finit de funcii continue

(S) f0(x), f1(x), f2(x),, fm(x) (2.2.3) ai crui termeni ndeplinesc condiiile:

10 f0(x)=f(x); 20 fm(x)0, x; 30 dac exist c i 1mk1 . a. fk(c)=0, atunci fk-1(c) fk+1(c) .

Teorema 2.2.1 Dac este un interval al axei reale, iar )(Cf 1 admite un ir Sturm (S), atunci oricare ar fi a,b, a

23

Avem:

10 P0(x)=P(x) (s-a luat P0=P); 20 Pm(x)0 (Pm(x)=Pm= constant nenul cum s-a artat mai sus ); 30 Dac Pi(c)=0, 1mi1 , cR, atunci din relaia

Pi-1(c)=Pi(c)Qi(c)-Pi+1(c) Pi-1(c)= -Pi+1(c) Pi-1(c)Pi+1(c)= , deoarece P0=P i P =P1 nu au rdcini comune. Rezult c (s) este un ir Sturm al polinomului P(x) i consecina 2.2.1 este dovedit.

Observaia 2.2.1 n teorema lui Sturm se poate lua a=- (respectiv b=+) dac =R, )x(flim)(f),x(flim)(f

xx == .

Obsevaia 2.2.2 Dac f0, f1, f2,, fm este un ir Sturm asociat funciei f, iar r1, r2,, rm sunt numere strict pozitive oarecare, atunci f0, r1f1, r2f2,, rmfm este de asemenea un ir Sturm asociat lui f.

Observaia 2.2.3 Dac P(x) este un polinom cu rdcini multiple iar Q(x)=c.m.m.d.c (P, P ), atunci

QP

,...,QP

,QP

,QP k210

,

unde P0, P1, P2, sunt definite ca n consecina 2.2.1 , reprezint un ir Sturm asociat lui P. Observaia 2.2.4 Metoda irului lui Sturm se utilizeaz nu numai la determinarea numrului rdcinilor reale ale unei ecuaii pe un interval ci i la separarea rdcinilor reale ale ecuaiei.

Exemplul 2.2.1 Cu metoda irului lui Sturm s se afle numrul rdcinilor reale ale ecuaiei x4+2x2+4x-5=0 i s se separe rdcinile acesteia.

Soluie. Lum P0(x)=P(x)= x4+2x2+4x-5. Avem PI(x)= 4x3+4x+4=4(x3+x+1). Cu observaia 2.2.2, lum, pentru simplificarea calculelor,

P1= x3+x+1 41

r1 = . Restul mpririi lui P0 la P1 este x2+3x-5, astfel c, n baza consecinei 2.2.1 avem P2(x)=-x2-3x+5. Restul mpririi lui P1 la P2

este 15x-14 deci P3=-15x+14. Restul mpririi lui P2 la P3 este 225299

atfel c P4= - 225299

i cu observaia 2.2.2 vom lua P4(x)= -1. ntruct c.m.m.d.c.

al polinoamelor P0(x) i P1(x) este o constant rezult c P0 i P1 nu au rdcini comune, adic P0 nu are rdcini multiple. Pentru a afla numrul rdcinilor reale ale ecuaiei date aplicm consecina 2.2.1 i observaia 2.2.1. Avem P0(- )=+, P1(-)= -,

P2(-)= -, P3(-)=+,P4(-)= -1. Numrul schimbrilor de semn din irul {Pk(-)}, 4,0k = este N(-)=3. Apoi P 0 ( + ) = + , P 1 ( + ) = + , P 2 ( + ) = - , P 3 ( + ) = - , P 4 ( + ) = - 1 , deci N(+)=1. Atunci N ( - , + ) = N ( - ) -N ( ) = 3 - 1 = 2 . Aadar, ecuaia dat are dou rdcini reale. Cu metoda sumelor alternante gsim R=1 i R

-

= -2. Cele dou rdcini reale ale ecuaiei date se afl n intervalul (-2,1). Cum N(-2)=3 i N(1)=1, gsim ntr-adevr N(-2,1)=N(-2)-N(1)=3-1=2. Dar N(0)=2. Atunci N(-2,0)=N(-2)-N(0)= =3-2=1, iar N(0,1)=N(0)-N(1)=2-1=1. cu metoda irului lui Sturm am separat rdcinile reale ale ecuaie: x1(-2,0), x2(0,1). Cu metoda biseciunii (njumtirii intervalului) putem obine lungimi mai mici ale celor dou intervale. Calculm P(-2) = 11, P(-1) = - 6, -1 fiind mijlocul intervalului (-2,0). Cum P(-2)P(-1)=(-11)6

24

Fig. 2.2.3

2

C1 C 2B

xx x2

y

0

A

Exemplul 2.2.2 S se afle numrul rdcinilor reale ale ecuaiei (x-2)2- ln x=0 n intervalul 1=[1,2] i n intervalul 2=[2,5;3,5]. Soluie. Ecuaia dat este transcendent. Avem f(x)= (x-2)2- ln x. Formm irul

() f0(x)=f(x)= (x-2)2- ln x, f1(x)= )x(f =2(x-2)-x

1, f2(x)= )x(f =2+ 2x

1 .

Artm c irul () este un ir Sturm asociat funciei f pe 1. ntr-adevr, 10 f0(x)=f(x); 20 f2(x)>0, x1 (f2(x)0 n 1); 30 f1(x)

==

n baza definiiei 2.2.2. () este ir Sturm pentru f pe I1 Cu teorema 2.2.1 avem f0(1)=1 f0(2)= - ln2

f1(1)= -3 f1(2)= -21

f2(1)=3 f2(2)=2+ 41

N(1)=2 N(2)=1 Ecuaia dat are n 1 o rdcin real x1. Folosind procedeul biseciunii gsim x1(1,4;1,45). n mod analog se arat c () este ir Sturm asociat funciei f pe 2. Apoi,

f0(2,5)= - 0,666 f0(3,5)= 0,997 f1(2,5)= 0,6 f1(3,5)= 2,714 f2(2,5)=2,16 f2(3,5)=2,082 N(2,5)=1 N(3,5)=0 n baza teoremei 2.2.2 ecuaia dat are o rdcin real x2(2,5;3,5). Folosind procedeul njumtirii intervalului se gsete x2(3;3,1).

3. Metoda grafic. Pentru determinarea intervalelor care conin rdcinile unei ecuaii precum i numrul acestora se poate folosi metoda grafic binecunoscut din nvmntul liceal. Descriem metoda prin

Exemplul 2.2.3. S se separe rdcinile reale ale ecuaiei (x-2)2- ln x=0, x(0,). Soluie. Scriem ecuaia dat n forma (x-2)2= ln x. Notm y=(x-2)2, y=ln x i trasm curbele C1 i C2 de ecuaii

y=(x-2)2, y=ln x. Rdcinile reale ale ecuaiei date sunt abcisele punctelor de intersecie ale curbelor C1 i C2 . Din Fig. 2.2.3 se vede c

A i B sunt punctele de intersecie ale curbelor C1 i C2, iar x1(1,2) i x2(3;3,5) sunt abcisele celor dou puncte A i B. Aadar, ecuaia dat are pe (0,) dou rdcini reale, situate n cele dou intervale (1,2) i (3;3,5). Acelai rezultat s-a obinut n exemplul 2.2.2 cu metoda irului lui Sturm.

40 Metoda irului Budan - Fourier. Fie irul finit de numere reale

c1, c2, c3, ,ck,ck+1,,cn (c10, cn0) (2.2.5) Definiia 2.2.3. Se numete numr inferior N de schimbri (variaii) de semn ale irului (2.2.5) numrul

schimbrilor de semn ale subirului obinut din acesta prin nlturarea elementelor nule.

Definiia 2.2.3. Se numete numr superior N de schimbri (variaii) de semn ale irului (2.2.5) numrul schimbrilor de semn ale subirului obinut din acesta prin nlocuirea elementelor nule

ck=ck+1= ck+2==ck+s-1=0 (ck-10, ck+s0) prin elementele nenule, ikc~ + i=0,1,2,,s-1, astfel nct

sgn ikc~

+ =(-1)s-1sgn c k + s .

Joseph Jean Baptist Fourier (1768-1830)

N(1,2)=N(1)-N(2)=2-1=1

N(2,5;3,5)=N(2,5)-N(3,5)=1-0=1.


25

Dac irul (2.2.5) nu are elemente nule, atunci NN = . n general NN < . Exemplul 2.2.4 . S se afle N i N pentru irul

c1, c2, c3, c4, c5, c6

2, 0, 0, 0, -7, 5 (2.2.6) Soluie. Pentru aflarea lui N scriem subirul obinut prin nlturarea elementelor nule: 2, -7, 5. Acest subir are 2 schimbri de semn, deci

N =2.

Pentru determinarea lui N nlocuim elementele nule din irul (2.2.6) c2= c3 =c4 =0, k=2, c5=c2+s= -7 , s=3, sgn c5= - 1

prin elementele nenule

2c~

cu sgn 02c~

+ = (-1)3(-1)=+1, lum 2c~ =+1

3c~

cu sgn 12c~

+ = (-1)2(-1)= -1, lum 2c~ = -1

4c~

cu sgn 22c~

+ = (-1)1(-1)=+1, lum 4c~ =+1 Obinem astfel irul

2, +1, -1, +1, -7, +5, iar N =4 ( NN > ).

Fie ecuaia algebric P(x)=0, (2.2.7) unde P este o funcie polinomial cu coeficieni reali, grad P=n, P(x)=a0xn+ a1xn-1++ an . Definiia 2.2.4 irul

(B-F) P(x), )x(P , )x(P , )x(P ,, P(k)(x),, P(n)(x)=n!a0 se numete irul Budan- Fourier asociat polinomului P(x). Teorema 2.2.2 Numrul rdcinilor reale ale ecuaiei algebrice (2.2.7) din intervalul (a,b) cu P(a)0, P(b) 0 este

N(a,b)= )b(N)a(N sau mai mic cu un numr par

(N(a,b)= ...) ,2, 0,1p ,p2)b(N)a(N =

unde )a(N este numrul inferior de schimbri de semn din irul ( ) ;n0,k ,)a(P )k( = )b(N este numrul superior de schimbri de semn din irul ( ) .n0,k ,)b(P )k( =

Consecina 2.2.2 Dac N(a,b)=0 n (a,b) ecuaia (2.2.7) are 0 rdcini reale. Dac N(a,b)=1 ecuaia (2.2.7) are o singur rdcin real n (a,b).

Observaia 2.2.5 Dac 0)a(P )k( i n0,k ,0)b(P )k( = , atunci N(a,b)=N(a)-N(b)-2p, deoarece NN = =N.

Observaia 2.2.6 Se poate lua a= -, b=+.

Teorema 2.2.3 (Descartes) Numrul rdcinilor pozitive ale unei ecuaii algebrice (fiecare rdcin considerat cu ordinul ei de multiplicitate) P(x)=a0xn+ a1xn-1+ a2xn-2++ an-kxk++ an-2x2+ an-1x+ an, a00 (2.2.8) este egal cu numrul schimbrilor de semn din irul coeficienilor

(j) a0, a1, a2, an-k,,an (coeficienii nuli omii !) sau mai mic dect acesta cu un numr par.

Demonstraie. Aplicm teorema2.2.2 pe intervalul (0,). Avem Pk(0)=k!an-k, n,0k = deci irul Pk(0) are termenii

(l) an, 1an-1, 2!an-2, 3!an-3,, k!an-k,, (n-2)!a2, (n-1)!a1, n!a0

Ren Descartes (1596-1650)


26

Observm c irul (l) este format din elementele irului (j) (nmulite cu cte un numr pozitiv) i scrise n ordine invers. n aceste condiii pentru cele dou iruri (j) i (l) numrul inferior de schimbri de semn este acelai: )0(N .

Pe de alt parte irul Pk(+), n,0k = , are toi termenii de acelai semn (semnul lui a0), deoarece Pk(+) = n(n-1)(n-2)(n-k+1)a0(+)n-k, deci 0)(N =+ . Cu teorema 2.2.2 avem

N(0, +)= 0,1,2,...p ,p2)0(Np2)(N)0(N ==+ . Teorema 2.2.4 (Huat) Dac ecuaia algebric (2.2.8) are toi coeficienii reali i toate rdcinile reale , atunci, n mod necesar, ptratul oricrui coeficient neextrem (aka0, akan) este mai mare dect produsul coeficienilor vecini

ak2ak-1ak+1, 1n,1k = .

Consecina 2.2.3 Dac exist k astfel nct ak2

27

ecuaie sub forma echivalent n [a,b] x=g(x) (2.3.4)

Astfel, dac x* este soluie a ecuaiei (2.3.1) adic f(x*)=0, x* verific i x*=g(x*). (2.3.5) Punctul x* cu proprietatea (2.3.5) se numete punct fix al funciei g. Pentru ecuaia (2.3.4) irul de iterare se scrie sub forma xp=g(xp-1), p=1,2,3 sau sub forma x(p)=g(x(p-1)). Existena i unicitatea soluiei x* pentru ecuaia (2.3.4) n [a,b] precum i convergena iruluii iterativ x(p) se poate arta cu teorema contraciei pe care o vom demonstra ntr-un cadru mai general.

Fie T : E E, T operator, aplicaie, iar (E,) un spaiu metric complet. Definiia 2.3.2 Dac pentru Ex avem xTx = , x se numete punct fix al aplicaiei T.

Definiia 2.3.3 Se spune c alicaia T : E E este o contracie (aplicaie contractant, contractiv; operator contractant, contractiv) dac exist un numr , 0

28

(x(m-p),x(0)) (1++2++m-p-1) (x(1), x(0))= )0()1(pm

x,x(1

1

)

de unde, neglijnd m-p care are valoare pozitiv mic, obinem majorarea

(x(m-p),x(0)) ( ))0()1( x,x1

1

. (2.3.9) Ducnd (2.3.9) n (2.3.8) rezult

(x(m),x(p)) ( ))0()1(p x,x1

. (2.3.10)

Cum 00, T x*= x*, T x = x . Din ( T x*, T x ) ( x*, x ) rezult (x*, x )( x*, x ) de unde 1. Absurd, deoarece 0

29

20 );1(2

ab2

ba2

bag +

+

atunci:

a) ecuaia x=g(x) are n intervalul (a,b) unica soluie pp

* xlimx

= , xp=g(xp-1), p=1,2,3, x0 oarecare din (a,b);

b) relaia de evaluare a erorii apriori este

01p

p* xx

1xx

, p=1,2,3. (2.3.12)

Demonstraie. Aplicm teorema 2.3.2. Lum E=R, ].b,a[S,2

abr,

2ba

x~)0(

=

=

+= Ipotezele 10 i 30 ale

teoremei 2.3.2 sunt ndeplinite. Artm i ndeplinirea ipotezei 20. Pentru orice x , x S =[a,b], avem cu teorema lui Lagrange

xxxx)c(g)x(g)x(g = , c ntre x i x

unde s-a aplicat ipoteza 10 a teoremei 2.3.3, 1)x(g)c(g

30

y

A

B

x

y=x

y=g(x)

x0x12* xx12 1

2

x= g(x ) xx =g(0

0 )

1

B A A0

1

2

Fig. 2.3.1

adic .xxxx 01

1p1pp (2.3.15)

nlocuind (2.3.15) n (2.3.14) se obine

01p

1ppp* xx

1xx

1xx

. (2.3.16)

Dubla inegalitate (2.3.16) cuprinde cele dou evaluri aposteriori i apriori a erorii precum i faptul c prima este mai mic. Evaluarea apriori este utilizat pentru determinarea ordinului p al iteratei xp care aproximeaz x* cu precizia dorit. Observaia 2.3.2. Metoda iteraiei simple (metoda aproximaiilor succesive) pentru rezolvarea ecuaiei x=g(x)

are o interpretare geometric. tim c rdcina x* a acestei ecuaii este abcisa punctului de intersecie a dreptei y=x

(prima bisectoare) cu graficul funciei y=g(x), g o -contracie n [a,b] care conine x*. (Fig2.3.1). Perpendiculara ridicat n x0 pe ox ntlnete curba de ecuaie y=g(x) n A0, iar x0A0=x1=g(x0). Paralela prin A0 la ox ntlnete dreapta y=x n B1, iar paralela la oy dus prin B1ntlnete axa ox n x1 i curba y=g(x) n A1; x1A1=x2=g(x1). Paralela prin A1 la ox ntlnete dreapta y=x n B2; paralela la oy prin B2 ntlnete curba y=g(x) n A2 i axa ox n x2 .a.m.d.

Observaia 2.3.3. Dac 1)x( g > n (a,b), interval n care se afl soluia x* scriem ecuaia f(x)=0 sub alt

form echivalent x=h(x). Dac h(x) este inversa lui g(x) pe [a,b] avem 1))x(h( g1)x( h ++=

f(x) - + - + f 02377

37

37

37

31

f(-3) = -4, f(-2) = 8, x~ (-3,-2). Restrngem acest interval. Avem f(-2,5) = 3,875 deci x~ (-3;-2,5). Apoi f(-2,8) = -0,352 i f(-2,7) = 1,217 de unde rezult c x~ (-2,8;-2,7). Pentru calculul celor trei rdcini aplicm teorema 2.3.3 precum i observaiile 2.3.1 i 2.3.3.

Calculul lui x*. Scriem ecuaia dat sub forma 7x = x3 + 2 sau x = 71 (x3 + 2) i astfel, g(x) =

71 (x3 + 2). Avem g(x) =

73

x2 i g(x)=

=

73

x2 73 0,32 =

727,0

0,0386 = < 1, x [0,25;0,3]. Prima ipotez a teoremei 2.3.3 este ndeplinit. Apoi, r =205,0

225,03,0

2ab

=

=

=

=0,025, 255,0

225,03,0

2ab

=

+=

+ = 0,275, g

2ba

2ba +

+ (1- )r g(0,275) - 0,275 (1 - 0,0386)0,025 0.013685 0,024035

ndeplinirea celei de a doua ipoteze. Atunci irul xp = g(xp-1), p = 1,2,3, converge ctre x*. Lum x0 = 0,275. Avem:

x1 = g(x0) = 71 (x30 + 2) =

71 (0,2752 + 2) = 0,288685267.

Utiliznd formula de evaluare a erorii apriori (2.3.12)

x*- xp

1

px1 - x0= 0386,01

0386,0 p

0,275 - 0,288685267= 9614,0

0386,0 p 0,0136852267 10-6

0,0386p 610013685267,09614,0

p lg 0,0386 lg 0,00007025, p=2,93

Lum p = 4. Am aflat c x4 aproximeaz soluia exact cu precizia dorit. Gsim:

x2 = 71 (x13 + 2) =

71 (0,28868523673 + 2) = 0,289151256

x3 = g(x2) = 71 (0,2891512563 + 2) = 0,289167926

x4 = g(x3) = 71 (0,2891679263 + 2) = 0,289168524

Putem lua x* x4 = 0,2891685

Dac folosim formula de evaluare a erorii aposteriori (2.3.14), obinem:

x*-x4

1x4 - x3= 0386,01

0386,0

0,000000598 = 9614,0

100386,098,5 7 0,24 10-7

Reziduul este f(x4) = 0,000000313.

Calculul lui x . Cum x (2,4;2,5) = I, g(x) = 73

x2 are cea mai mare valoare pentru x = 2,5, adic Ix

sup

g(x)= 73 2,52 2,68, g nu

este contracie. Scriem ecuaia dat sub forma: x3 = 7x - 2, x = 3 2x7 i notm h(x) = 3 2x7 , h(x) = 3 2)2x7(3

7

;

h(x) 08405132,18

7

)24,27(37

3 2=

= 0,387081405 0,39 = < 1. Aadar pentru ecuaia x = h(x), h este contracie cu = 0,39. Se verific i

a doua ipotez a teoremei 2.3.3.

Calculm termenii irului iterativ. xp = h(xp-1), p = 1,2,3,, x0 = 2,45:

x1 = h(x0) = 3 0 2x7 = 3 245,27 = 2,474405528 x9 = h(x8) = 3 8 2x7 = 2,489286295

x2 = h(x1) = 3 1 2x7 = 2,483671648 x10 = h(x9) = 3 9 2x7 = 2,489287712

x3 = h(x2) = 3 2 2x7 = 2,487171699 x11 = h(x10) = 3 10 2x7 = 2,489288246 x4 = h(x3) = 3 3 2x7 = 2,488491199 x12 = h(x11) = = 3 11 2x7 2,489288447

x5 = h(x4) = 3 4 2x7 = 2,48898828 x13 = h(x12) = 3 12 2x7 = 2,489288522 x6 = h(x5) = 3 5 2x7 = 2,489175489 x14 = h(x13) = 3 13 2x7 = 2,489288551

x7 = h(x6) = 3 6 2x7 = 2,489272534 x15 = h(x14) = 3 14 2x7 = 2,489288562

x8 = h(x7) = 3 7 2x7 = 2,489286295

f(x*) = 0, f(x4) - f(x*), eroarea lui f(x4) fa de f(x*) se numete reziduul aproximaiei x4.


32

0 x* b x

y

B(b,f(b))

(x,y)

A(a,f(a)) P1Pk-1

Fig. 2.4.1

Folosim formula evalurii erorii aposteriori

x - x15

1x15 - x14 = 39,01

39,0

(0,000000011) = 61,039,0

0,000000011 =0,000000007 0 sau f < 0 , de unde rezult c f este strict monoton pe [a,b] astfel c ecuaia f(x) = 0 are o singur rdcin x* (a,b).

Presupunem c f(a) f (a) < 0 i f(a) < 0. Atunci f (a) > 0. Cum f (x) 0 n [a,b] i f continu urmeaz c f pstreaz semn constant, deci f (x) > 0 n [a,b], adic f este convex. Presupunnd c f(a) < 0, din f(a)f(b) < 0

rezult f(b) > 0. Cum f este strict monoton, rezult c f este strict cresctoare, deci f > 0 n [a,b] (fig. 2.4.1). Rdcina x*este abscisa punctului de intersecie cu axa 0x a graficului funciei f. Lund aproximaia de start a = x0, intersecia coardei AB cu axa 0x ne d aproximaia x1. Fie P1(x1,f(x1)). Intersecia coardei BP1 cu axa 0x ne d aproximaia x2, .a.m.d.

Scriem ecuaia dreptei care trece prin punctele B(b,f(b)) i Pk-1(xk-1,f(xk-1)). Fie (x,y) punctul curent al coardei Pk-1B. Ecuaia dreptei Pk-1B este:


33

)x(f)b(f)x(fy

xbxx

1k

1k

1k

1k

=

. (2.4.3)

Intersecia coardei Pk-1B cu axa 0x de ecuaie y = 0 ne d aproximaia xk. Aadar lum n (2.4.3) y = 0 i x = xk. Obinem:

xk

xk-1 = )x(f)b(f)x(f

1k

1k

(b xk-1)

de unde rezult:

xk = xk-1 )b(f)x(f)x(f

1k

1k

( xk-1 b), k = 1,2,3, (2.4.1)

Fie k 1 cu a xk-1 < x*. ntruct f este convex, avem f(xk-1) < 0. tim c f > 0 pe [a,b]. Utiliznd formula lui Lagrange, (2.4.1) ne d:

xk = xk-1 )bx)(c(f)x(f1kk

1k

(xk-1 b) = xk-1 )c(f)x(f

k

1k

> xk-1 ,

unde ck (xk-1,b). Aadar, a < xk-1 < xk < x*. Se arat c relaia se menine pentru orice k. Atunci irul (xk) definit prin (2.4.1) este strict cresctor i mrginit, deci convergent: xk x~ , pentru k . Trecnd la limit n (2.4.1) pentru k i innd seama de continuitatea funciei f, obinem:

x~ = x~ )b(f)x~(f)x~(f

( x~ b) f( x~ ) = 0.

Cum n (a,b) ecuaia f(x) = 0 are unica soluie x*, rezult c xk x*, k . Consecina 2.4.1. n condiiile teoremei 2.4.1, dac exist m1, M1 astfel nct: m1 f (x) M1, x [a,b], atunci unica soluie x*a ecuaiei f(x) = 0 n (a,b) verific relaiile de evaluare a erorii aposteriori:

x* xk 1

km

)x(f ; x* xk

1

11m

mM xk xk-1, k 1. (2.4.4)

Demonstraie. Cu teorema lui Lagrange, x [a,b], x fixat, dar arbitrar luat, avem: f(x*) f(x) = f(c) (x* x), unde c este situat n (x,x*) sau (x*,x), iar f(x*) = 0. Atunci:

x* x = - )c(f)x(f

x* x= )c(f)x(f

kxx=

x* xk1

km

)x(f .

Pentru a doua relaie (2.4.4) pornim de la egalitatea (2.4.1) scris n forma:

- f(xk-1) = bx)b(f)x(f

1k

1k

(xk xk-1) f(x*) f(xk-1) = bx)b(f)x(f

1k

1k

(xk xk-1).

Aplicnd teorema lui Lagrange n ambii membri ai ultimei egaliti, gsim succesiv:

f (ck)(x* xk-1) = bx)bx)(d(f

1k

1kk

(xk xk-1), x* xk-1 = )c(f)d(f

k

k

(xk xk-1),

unde ck (xk-1 , x*), dk (xk-1,b). Folosind ultima egalitate, putem scrie

x* xk = x* xk-1 (xk xk-1) x* xk = )c(f)d(f

k

k

(xk xk-1) (xk xk-1)

sau

x* xk= )c(f)c(f)d(f

k

kk

xk xk-1.

innd seama de faptul c f are semn constant pe [a,b], f(ck) i f(dk) au acelai semn, f(dk) - f(ck) M1 - m1 .


34

Fig. 2.4.5

y

1

2

3

2,2

y =

x + 2

,2y = ex

Cum i )(c f k m1, obinem majorarea:

x*- xk 1

11m

mM xk - xk-1, k 1

care este a doua relaie din (2.4.4) Observaia 2.4.1. La metoda coardei se ia aproximaia iniial x0 = a cnd f(a)f (a) < 0, adic f(a) < 0 i f (a) > 0 (fig. 2.4.1) sau f(a) > 0 i f (a) < 0 (fig. 2.4.2). n aceste cazuri xk x*, k , (xk) strict cresctor. Se ia aproximaia iniial x0 = b cnd f(b) f (b) < 0, adic f(b) < 0 i f (b) > 0 (fig. 2.4.3) sau f(b) > 0 i f (b) < 0 (fig. 2.4.4). n aceste cazuri xk x*, k , (xk) strict descresctor.

Exemplul 2.4.1. Utiliznd metoda coardei, s se afle rdcinile reale ale ecuaiei ex - x - 2,2 = 0, cu cel puin 7 cifre exacte.

Soluie. Pentru separarea rdcinilor reale ale ecuaiei transcendente date, folosim metoda grafic. Rdcinile ecuaiei date ex = x + 2,2 sunt abscisele punctelor de intersecie ale curbelor y = ex i y = x + 2,2 (fig. 2.4.5). Se vede din figur c ecuaia dat are dou rdcini reale: x* (1;1,5) , x~ (-2,2;-2)

S restrngem aceste intervale. Avem f(1) = e - 3,2 = -0,481718; f(1,5) = e1,5 - 1,5 - 2,2 = = 0,718311; f(1)f(1,5) < 0. Apoi f(1,3) = e1,3 - 3,5 = 0,169297; f(1,2) = e1,2 - 3,4 = = - 0,07988. Aadar x* (1,2;1,3). Pentru rdcina x~ avem f(-2) = e-2 + 2 - 2,2 = -0,06446; f(-2,2) = e-2,2 = 0,1108; f(-2,1) = e-2,1 - 0,1 = 0,02246; f(-2,1)f(-2) < 0, x~ (-2,1;-2). Calculul rdcinii x*. Deoarece f(1,2) = -0,079883077, f(1,2) = e1,2 > 0 vom folosi formula de iterare (2.4.1) (vezi fig. 2.4.1). Lund x0 = a = 1,2, avem succesiv, f(b) = f(1,3) = =0,169296666.

x1 = x0 - )b(f)x(f)x(f

0

0

(x0 - b) = 1,2 - 169296666,0079883077,0

079883077,0

(1,2 - 1,3) = 1,232058916

x2 = x1 - )b(f)x(f)x(f

1

1

(x1 - b) = 1,233541999

x3 = x2 - )b(f)x(f)x(f

2

2

(x2 - b) = 1,233609836

x4 = x3 - )b(f)x(f)x(f

3

3

(x3 - b) = 1,233612936

x5 = x4 - )b(f)x(f)x(f

4

4

(x4 - b) = 1,233613077

Cu prima din formulele (2.4.4) obinem eroarea x*- x5 1

5

m

)x(f, unde:

f(x5) = -1,7 10-8 , f(1,2) f(x) = ex - 1 f(1,3), m1 f(1,2) = 2,32012 i astfel avem:

B(b,f(b))

B(b,f(b))

A(a,f(a))

P1

a x* x

a x*

0

Fig. 2.4.3

y

Fig. 2.4.4

0x x2 1

x x2 1 x = b x 0x = b 0

y

Fig. 2.4.2

B(b,f(b))

A(a,f(a))

0 a = x x x x0 1 2

P1

x*

y

P1


35

x*- x5 1

5

m

)x(f =

32012,2107,1 8

= 0,732 10-8 < 0,5 10-7.

Aadar x* x5 = 1,2336131 cu cel puin 7 cifre exacte.

Calculul rdcinii x~ . Am vzut c x~ (-2,1;-2). Avem f(-2,1) = 0,02245649, f(-2) = -0,64664717, f (-2) = e-2 = 0,135335283. Deoarece f(-2)f (-2) < 0, suntem n cazul formulei de iterare (2.4.2), fig. 2.4.3, b = x0 = -2, a = -2,1.

x1 = x0 )a(f)x(f)x(f

0

0

(x0 a) = -2 - 022456428,0064664717,0064664717,0

(-2 + 2,1) = -2,074223906


1

1

(x1 a) = -2,074363394


2

2

(x2 a) = -2,074363649


3

3

(x3 a) = -2,07436365

Pentru evaluarea erorii folosim a doua formul (2.4.4). Deoarece f (x) = ex > 0, x [-2,1;-2], de unde rezult c f este strict cresctoare: f (-2;1) f (x) f (-2). Avem f (-2,1) = e-2,1 - 1 = 0,122456428 - 1 = -0,877543571; f (-2) = e-2 - 1 = -0,864664716; m1 = 0,864664716; M1 =0,877543571. Atunci

x~ x4 1

11m

mM x4 x3 = 864664716,0

012878855,0 0,000000001 0,015 10-9 < 0,15 10-10

de unde se vede c x~ x4 = -2,07436365 cu cel puin 7 cifre exacte. Reziduul este :

f( x~ ) f(x4) = 8 10-10 Observaia 2.4.2. n exemplele 2.3.1 i 2.4.1 am vzut c unele iruri de iterare pentru determinarea unei rdcini converg mai repede ctre acea rdcin, atingndu-se precizia dorit de aproximare dup efectuarea unui numr mic de iteraii, n timp ce alte iruri de iterare converg mai ncet (necesit un numr mult mai mare de iteraii pentru a obine o aceeai precizie). De aici a aprut noiunea de vitez de convergen a unei formule de iterare. 2.5. Formule de iterare de ordin superior. Metoda funciei inverse.

a) Ordinul unei formule de iterare. Fie g : I R, I interval R i x* soluie a ecuaiei: x = g(x) (2.5.1) calculat cu ajutorul irului convergent xk = g(xk-1), k = 1,2,3,, xk x*, (k ). (2.5.2) Presupunem c g Cn(I), n suficient de mare. Definiia 2.5.1. Se spune c formula de iterare (2.5.2) are ordinul m pentru rdcina x* a ecuaiei (2.5.1) dac: x* = g(x*), g(x*) = g(x*) = g(x*) = = g(m-1)(x*) = 0, iar g(m)(x*) 0 . (2.5.3) Observaia 2.5.1. Ordinul unei formule de iterare este important deoarece viteza de convergen a irului de iterare crete odat cu ordinul formulei de iterare, cum rezult din: Teorema 2.5.1. Dac formula de iterare (2.5.2) are ordinul m pentru rdcina x*, atunci viteza de convergen a irului de iterare xk ctre x* este dat de:

xk - x* 1m1km

, 0 < < 1, m 2. (2.5.4) Demonstraie. Scriem formula lui Taylor de ordinul m - 1 (m n) pentru g n punctul x*.

g(x) = g(x*) + !1

*xx g(x*) + !2*)xx( 2 g(x*) +

!3*)xx( 3 g(x*) + + )!1m(

*)xx( 1m

g(m-1)(x*) + !m*)xx( m g(m)(),

unde este situat ntre x* i x. Prin ipotez formula de iterare (2.5.2) are ordinul m pentru x* astfel c sunt verificate relaiile (2.5.3). Atunci egalitatea precedent se scrie:


36

g(x) - g(x*) = !m*)xx( m g(m)(). k ntre xk-1 i x*

nlocuind aici pe x prin xk-1, g(xk-1) = xk, x* = g(x*), obinem egalitatea, n modul:

xk - x* = !m

)(g k)m( xk-1 - x*

m.

Fie M = Ix

sup

g(m)(x). Egalitatea precedent devine:

xk - x* !mM

xk-1 - x*m

, k = 1,2,3, . (2.5.5)

Inegalitatea (2.5.5), pentru diferite valori ale lui k, ne d:

x1 - x* !mM

x0 - x*m

;

x2 - x* !mM

x1 - x*m

!m

M 2m0

m1mm

0 *xx!mM

*xx!m

M

=

+

;

x3 - x* !mM

x2 - x*m

!m

M 3m0

2mm1m2m

0

m1*xx

!mM

*xx!m

M

=

+++

;

. . . . . . . . . . . . . . . . .

xk - x* km

01m1km

km0

1km...2mm1*xx

!mM

*xx!m

M

=

++++. (2.5.6)

Dar, pentru m 2 avem 1m1mk

mk mk - 1 mk+1 - mk 2mk mk+1 + 1. mprind ambii membri ai

ultimei inegaliti prin mk se obine inegalitatea evident 2 m + km

1 (m 2). Cum x0 - x* < 1, este adevrat

inegalitatea x0 - x*km x0 - x* 1m

1mk

.

Cu acestea, (2.5.6) se scrie

xk - x* 1m1km

0 *xx!mM

i notnd !m

Mx0 - x*= < 1, rezult (2.5.4).

n continuare prezentm o formul de iterare de ordin superior. b) Metoda funciei inverse a lui Cebev. Fie f : [a,b] [c,d] i x* rdcina unic a ecuaiei f(x) = 0 n (a,b). Presupunem c f Cn[a,b], n suficient de mare i f (x) 0. Deoarece f este continu i nu se anuleaz, f pstreaz semn constant pe [a,b] astfel c f este strict monoton, deci injectiv, fiind i continu, f este i surjectiv. Funcia f este bijectiv i admite inversa x = F(y). Aadar, y = f(x) x = F(y), f : [a,b] [c,d], F : [c,d] [a,b] (2.5.7) i din f(x*) = 0 rezult x* = F(0). Din f Cn[a,b] rezult c i F Cn[c,d] i F(y) = )x(f

1

(2.5.8)

Pafnuti Lvovici Cebev (1821 - 1894)


37

n formula lui Taylor de ordinul m (m < n) pentru funcia F

F( + h) = F() + !1

h F() + !2

h 2 F() + !3

h3 F() + + )(F!m

h )m(m + Rm

lum h = -y i obinem

F( - y) = F() !1y F() +

!2y2 F()

!3y3 F() + + (-1)(m) )(F

!my )m(m + Rm .

n ultima egalitate nlocuim cu y i avem

x* = F(0) = F(y) !1y F(y) +

!2y2 F(y)

!3y3 F(y) + + (-1)(m) )y(F

!my )m(m

+ Rm .

innd seama de echivalena (2.5.7), ultima egalitate se scrie:

x* = F(0) = x !1

))x(f(F f(x) + !2

))x(f(F [f(x)]2 - !3

))x(f(F [f(x)]3 + + (-1)m !m))x(f(F )m(

[f(x)]m + Rm

sau

F(0) = x + =

m

1p(-1)p

!p))x(f(F )p( [f(x)]p + Rm .

Notm

m(x) = x + =

m

1p(-1)p

!p))x(f(F )p( [f(x)]p. (2.5.9)

S artm c xk = m(xk-1), k = 1,2,3, (2.5.10) este o formul de iterare de ordinul m + 1 pentru rdcina x*. Avem

m(x*) = x* + =

m

1p(-1)p

!p*))x(f(F )p( [f(x*)]p = x* , (f(x*) = 0).

Apoi,

m(x) = 1 F(f)ff F(f)f + 2ff2)f(F

+ F(f)ff -

innd seama de (2.5.8) 1 - F(f)f = 0 i de faptul c f(x*) = 0 apare n termenii care nu se reduc, se obine m(x*) = 0.

Analog se arat c m(x*) = m(x*) = = )m(m (x*) = 0, iar )1m(m + (x*) 0. Cu definiia (2.5.1) rezult c (2.5.10) este o formul de iterare de ordinul m + 1(s-a presupus, pentru a existe toate derivatele, c 2m n). S artm c m(x) se poate construi fr a cunoate explicit funcia invers F. Pentru aceasta notm: F(p)(f(x)) = ap(x), p = m,1 . (2.5.11)

Dac p = 1 (2.5.8), ne d: F(f) = f1

. Aadar,

a1(x) = )x(f1

. (2.5.12)

Pentru calculul lui a2(x) derivm relaia F(f)f = 1 n raport cu x.

F(f)f2 + F(f)f = 0 F(f)f2 + ff

= 0 F(f) = - 3)f(f

deci

a2(x) = - [ ]3)x(f)x(f

. (2.5.13)

n mod analog, derivnd n raport cu x, relaia F(f)(f)3 + f = 0, folosind (2.5.12) i (2.5.13), se obine:


38

0 x x xk k-1

y y = f(x)

P (x ,f(x ))k-1 k-1 k-1

x*

(x,y)

Fig. 2.5.1

a3(x) = - [ ]52

)x(ff3)x(f)x(f

(2.5.14)

.a.m.d. Cu aceasta, formula de iterare (2.5.10), se scrie:

xk = xk-1 + p

1-k1kp

pm

1p )][f(x

!p)x(a

)1( =

, k = 1,2,3, (2.5.15)

Pentru a arta c irul (2.5.10), respectiv (2.5.15) este convergent ctre x*, x* unica soluie a ecuaiei f(x) = 0 n (a,b), observm c din m(x*) = 0 i continuitatea funciei m, rezult c exist o vecintate Vx* a punctului x* astfel nct (m)(x) < 1, x Vx*. Atunci aplicaia m(x) este o - contracie i n baza teoremei (2.3.3), convergena xk x*, k , este asigurat.

Evident, cu ct m este mai mare, viteza de convergen a irului (xk) este mai mare, dar n acelai timp formula de iterare are o form tot mai complicat. Cea mai simpl formul (2.5.15) este pentru m = 1. Pentru m = 1, formula (2.5.15) se scrie:

xk = xk-1 !1)x(a 1k1 f(xk-1),

de unde cu (2.5.12) xk = xk-1 )x(f

)x(f1k

1k

, k = 1,2,3, (2.5.16)

Formula de iterare (2.5.16) definete metoda lui Newton (sau metoda tangentei) pentru aproximarea rdcinii x* (a,b) a ecuaiei f(x) = 0. Metoda lui Newton este dat printr-o formul de iterare de ordinul doi (m + 1=1 + 1 = 2). Teorema 2.5.2. Fie f C2[a,b], x0 (a,b). Dac:

10 Exist )x(f1

0 i )x(f

10

A0 ;

20 )x(f)x(f

0

0

B0 2

;

30 f (x) , x S = [x0 - ;x0 + ]; 40 0 = 2A0B0 < 1,

atunci irul lui Newton (2.5.16) este convergent, xk x*, k , x* este unica soluie a ecuaiei f(x) = 0 n S i are loc formula de evaluare a erorii

x* xk 1k21

120k

B0. (2.5.17) Observaia 2.5.2 Denumirea de metod a tangentei pentru metoda lui Newton se datoreaz faptului c xk este abscisa punctului de intersecie a tangentei la graficul funciei f n punctul Pk-1 (xk-1, f(xk-1)) cu axa ox (fig. 2.5.1). Dac

(x,y) este punctul curent al tangentei, ecuaia tangentei este : y f(xk-1) = )x(f 1k (x-xk-1).

Intersecia acestei tangente cu axa ox de ecuaie y = 0 se obine punnd n ecuaia tangentei y = 0 i x = xk

- f(xk-1) = )x(f 1k (xk-xk-1) , de unde

Isaac Newton (1643 - 1727)

Demonstraia teoremei se face n cap. IV ntr-un cadru mai general.


39

xkxk-1 = - )x(f)x(f

1k

1k

xk = xk-1 )x(f)x(f

1k

1k

, k = 1, 2, 3, .....

i astfel am obinut chiar formula lui Newton (2.5.16). Exemplul 2.5.1. S se determine, cu eroarea mai mic dect 10-5, rdcinile ecuaiei :

x4 + 10x2 - 25x - 26 = 0 Soluie. Cu teorema lui Descartes gsim c ecuaia dat are o rdcin pozitiv i o rdcin negativ. Atunci celelalte dou sunt complex conjugate. Limita superioar a rdcinilor pozitive este 2,4 iar limita inferioar a rdcinilor pozitive este 2,3. Avem f(x) = x4 + 10x2 - 25x - 26, f(2,3) = - 2,6159, f(2,4) = 4,7776, f(2,35) = 0,97300625, f(2,33) = - 0,48804479, f(2,34) = 0,23819536, x* (2,33 ; 2,34). Pentru rdcina negativ x~ gsim x~ (-1 ; -0,5) i restrngnd intervalul gsim c x~ (-0,8 ; -0,78).

Calculul rdcinii x*. Avem f(x)=x4 + 10x2 - 25x - 26, )x(f = 4x3 + 20x -25 , 20x12)x(f 2 += , x [2,33 ; 2,34] , x* (2,33 ; 2,34). Lum x0 = 2,335. Verificm cele patru ipoteze ale teoremei 2.5.2. Avem :

10 f (x0) = f (2,335) = 72,6237815 )x(f1

0= 0,013769594 < 0,014 = A0

20 6237815,72

12599255,0)x(f)x(f

0

0 =

= 0,001734866 0,002 = B0 = 2

30 |f (x)| f (2,339) = 85,651052 85,7 = , x [2,335 - 0,004 ; 2,335 + 0,004] = [2,331;2,339] = S 40 0 = 2 A0 B0 = 2 0,014 0,002 85,7 = 0,0047992 0,005 < 1

n baza teoremei 2.5.2 irul lui Newton xk = xk-1 - )x(f

)x(f1k

1k

, k = 1, 2, 3, ......

converge ctre x*, unica soluie a ecuaiei date n S i are loc formula de evaluare a erorii

|x* - xk| 1k21

12

0k

B0 = 1k2

1k )005,0(21

0,002 < 10-6

unde relaia subliniat este verificat pentru k = 2. Pentru a obine precizia dorit este suficient s aproximm x* prin x2. Avem :

x1=x0 - )x(f)x(f

0

0

= 2,335 - 6237815,72

12599255,0 = 2,335 + 0,001734866 = 2,336734866

x2=x1 - )x(f)x(f

1

1

= 2,336734866 - 77206973,7200012859,0

= 2,336734866 - 0,000001767 = 2,336733099

Putem lua x* x2 = 2,3367331. Calculnd reziduul f(2,3367331) = 0,7 10-7, ne convingem c am obinut rdcina x* cu precizia dorit. Calculul lui x~ . Deoarece x~ [-0,8 ; -0,78], lum x0 = -0,79. S verificm ipotezele teoremei 2.5.2. Avem :

10 f (x0) = - 42,772156, )x(f1

0= 0,023379695 0,0234 = A0 ;

20 )x(f)x(f

0

0

=

772156,4238050081,0

= 0,008895993 0,0089 = B0 = 2

;

30 |f(x)| f(0,8078) = 27,83049008 27,8305 = , x [x0-, x0+] = [-0,8078 ; -0,7722] = 40 0 = 2 A0 B0 = 2 0,0234 0,0089 27,8305 = 0,011591959 0,0116 < 1.

Fiind ndeplinite ipotezele teoremei 2.5.2 rezult c irul lui Newton xk converge ctre x~ , unica soluie a ecuaiei date n . Calculm

primele dou aproximaii :

x1=x0 - )x(f)x(f

0

0

= - 0,79 + 772156,42

38050081,0 = - 0,79 + 0,008895993 = -0,781104006

x2=x1 - )x(f)x(f

1

1

= -0,781104006 - 52835966,42

001085478,0

= -0,781104006 + 0,000025523 = - 0,78107848

Dac lum x~ x2 = -0,78107848, facem eroarea

| x~ - x2| 21 (0,0116)3 0,0089 = 0,6 10-8

Avem f(x*) = 0, iar f(x2) = 0,7 10-7 reprezint restul, reziduul, |f(x2) - f(x*)| = 0,7 10-7


40

Calculul rdcinilor complexe. Notm rdcinile complex conjugate cu x1 i x2 i folosim relaiile dintre rdcini i coeficieni (x* = 2,3367331, x~ = -0,78107843)

=

=+++

26x~*xxx0x~*xxx

21

21

=

=+

24523326,14xx55565462,1xx

21

21 x2 + 1,55565462 x + 14,24523326 = 0

x1,2 = 2614,2452332 4 55565462,1 i55565462,1 2

= -0,77782731 i 3,693266567

Observaia 2.5.3. Metoda lui Newton se poate aplica i la determinarea rdcinilor complexe ale unei ecuaii f(z) = 0. (2.5.18) Teorema 2.5.2. Dac f(z) este o funcie analitic ntr-un disc : |z - z0| r i dac ea verific (z0 ) :

10 )z(f1

0A0 ; 20 )z(f

)z(f0

0

B0 2

; 30 | f (z)| , z = {z |z - z0| }; 40 0 = 2 A0 B0 < 1

atunci irul lui Newton

zk = zk-1 - ,)z(f)z(f

1k

1k

k = 1,2,3, (2.5.19)

converge ctre z*, unica soluie a ecuaiei (2.5.18) n , z* = k

lim zk, iar rapiditatea convergenei este dat de:

z* - zk 1k21

1k20

B0. (2.5.20) Exemplul 2.5.2. S se afle valorile aproximative ale rdcinilor cu modul minimal ale ecuaiei f(z) = ez - 0,1z + 1 = 0 (2.5.21) Soluie. Cutm, cu irul lui Rolle, rdcinile reale ale ecuaiei date. Avem f(x) = ez - 0,1 = 0 pentru z = ln 0,1 -2,302558. irul lui Rolle este:

f(-) = + , f(-2,30258) > 0 , f(+) > 0 i nu prezint nici o variaie de semn. Aadar, ecuaia (2.5.21) nu are rdcini reale. Lum ca aproximaie iniial a rdcinii cutate z* rdcina z0 cu modul minim a ecuaiei apropiate ez + 1 = 0. Lum z0 = pii (rdcinile ecuaiei fiind zk = (2k -1) pii, k N*. Aplicm (2.5.19) pentru k = 0.

z1 = z0 - )z(f)z(f

0

0

= pii - )i(f)i(f

pi

pi=pii -

1,0e1i1,0e

i

i

+pipi

pi

= 3,141592653 i - 1,1

i 3141592653,0 - i 33,14159265

1,0sinicos1i 3141592653,0sinicos

=

pi+pi

+pi+pi

z1 = 2,855993321 i .

Apoi, pentru k = 2,3 obinem succesiv (cu formula lui Euler eiu = cos u +i sin u, u R)

z2 = z1 - )z(f)z(f

1

1

= 2,855993321 i - i) 855993321,2(fi) 855993321,2(f

= 2,855993321 i + i 281732557,0059492924,1i 003866775,0040507058,0

,

f(2,855993321 i) = cos 2,855993321 + isin 2,855993321 0,2855993321 i + 1 = -0,959492973 + 0,281732557 i 0,2855993321 i + 1 = =0,040507027 - 0,003866775 i

f (2,855993321 i) = -0,959492973 + 0,281732557 i - 0,1 = -1,059492973 + 0,281732557 i

z2 = 2,855993321 i + 22 281732557,0059492973,1i) 70,281732552973i)(1,05949 003866775,0040507027,0(

+

+ = 0,036613992 + 2,862079797i .

Pentru f(z2) obinem, folosind eu+iv = eu eiv = eu(cos v + i sin v), u,v R,

f(z2) = e 2z - 0,1z2 + 1 = e0,036613992(cos 2,862079797 + i sin 2,862079797) - 0,0036613992 - 0,2862079797 i + 1 = = 1,03729254(-0,961189949 + 0,275887444 i) + 0,996338601 - 0,2862079797 i

f(z2) = - 0,000696562 - 0,000031991 i Din ultima egalitate se vede c reziduul funciei f n punctul z2 este 0, astfel c putem lua z* z2. Propunem cititorului s continue

procesul (2.5.19) i s verifice ipotezele teoremei 2.5.2, lund eventual z0 = 2,855993321 i.


41

CAPITOLUL III REZOLVAREA SISTEMELOR DE ECUAII LINIARE

Soluionarea numeric a multor clase de probleme se reduce la rezolvarea sistemelor de ecuaii algebrice liniare. Pentru rezolvarea sistemelor liniare se utilizeaz, n general, dou tipuri de metode:

A. Metode exacte (Cramer, Metoda matricei inverse, metoda eliminrii succesive, respectiv complete, metoda matricelor tridiagonale, metoda Haleki, etc.); B. Metode aproximative (de tip iterativ). (Metoda iteraiei Jacobi, metoda Gauss-Seidel, metode de relaxare, etc.)

A. Metode exacte

3.1. Metode exacte de rezolvare a sistemelor de ecuaii liniare a) Metoda matricei inverse. Fie sistemul de n ecuaii algebrice liniare cu n necunoscute:

=+++

=+++

=+++

nnnn22n11n

2nn2222121

1nn1212111

bxa...xaxa. . . . . . . . . . . . . . . .

bxa...xaxabxa...xaxa

(3.1.1)

scris n form matriceal

Ax = b, A = [aij] =

nn2n1n

n22221

n11211

aaa

. .. . .. . .. . .

aaa

aaa

, x =

n

2

1

x

x

x

, b =

n

2

1

b

bb

O (3.1.1)

Se tie c sistemul (3.1.1) are soluie unic numai dac det A 0, adic numai dac exist matricea invers A-1, astfel nct

A-1A = AA-1 = I , (3.1.2)

unde I este matricea unitate de ordinul n, avnd elementele

ij =

=

ji,1ji,0 , I =

1000010000100001

. (3.1.3)

Dac se cunoate matricea A-1 = [cij], i,j = n,1 , pentru determinarea creia este necesar calculul a n2 determinani de ordinul n - 1 i a unui determinant de ordinul n; nmulind la stnga cu A-1 n (3.1.1) se obine A-1Ax = A-1b, adic x = A-1b, respectiv

xi = =

n

1jcijbj , i = n,1 . (3.1.4)

Relaia (3.1.4) ne d toate componentele xi ale vectorului necunoscut x. (n cazul cnd matricea A este singular, sistemul (3.1.1) va avea soluie numai pentru valori particulare ale componentelor vectorului b i soluia nu va fi unic). Metoda necesit un volum mare de calcule. Astfel pe lng calculele necesare determinrii matricei inverse A-1, pentru determinarea necunoscutelor xi din (3.1.4) sunt necesare n2 + n(n - 1) operaii, din care n2 operaii de nmulire i n(n - 1) de adunare. Pentru a ocoli volumul mare de calcule i capacitatea de memorie (pentru n mare) se utilizeaz n mod frecvent alte metode.

Gabriel Cramer (1704 - 1752)


42

b) Metoda eliminrii succesive a lui Gauss. Metoda eliminrii complete a lui Gauss - Jordan. Metoda eliminrii succesive a lui Gauss, const n urmtoarele: din prima ecuaie se scoate x1 i se nlocuiete n celelalte n - 1 ecuaii ale sistemului (3.1.1) care devine un sistem de n-1 ecuaii liniare cu n-1 necunoscute x2,x3,,xn i spunem c am eliminat necunoscuta x1. a doua ecuaie transformat (prima ecuaie din sistemul transformat) se utilizeaz la eliminarea lui x2 din ultimele n - 2 ecuaii, .a.m.d. Dup efectuarea celor n - 1 eliminri succesive se obine un sistem algebric liniar Cx = d, echivalent cu sistemul iniial Ax = b, (adic cele dou sisteme au aceeai soluie). Sistemul obinut n final Cx = d are form superior triunghiular i se rezolv uor.

Practic, calculele se pot ordona astfel: Se pornete de la matricea extins a sistemului Ax = b (neomogen,

(E)

b a a a a. . . . . . . . . . . .

b a a a ab a a a ab a a a a

nnnn3n21n

33n333231

22n232221

11n131211

asupra creia se efectueaz, de mai multe ori, urmtoarele operaii:

permutarea a dou linii; nmulirea elementelor unei linii cu un numr diferit de zero; (3.1.5) adunarea elementelor unei linii la elementele corespunztoare ale altei linii (operaii care fac ca sistemul obinut s fie mereu echivalent cu cel iniial), pn se obine n final matricea.

d 1 0 0 0. . . . . . . . .

d c 1 0 0d c c 1 0d c c c 1

n

33n

22n23

11n1312

(3.1.6)

care ne d sistemul triunghiular superior

=

=+

=++

=+++

=++++

nn

1nnn,1n1-n

3nn33

2nn23232

1nn13132121

d x dxc x

. . . . . . . . . .

dxcx dxcxcx dxcxcxcx

=

=

++=

+++=

+++=

nn

nn,1n1n1n

nn343433

nn242432322

nn131321211

dxxcdx

. . . . . . . . . . . . .

)xcxc(dx)xcxcxc(dx

)xcxcxc(dx

(3.1.7)

care se rezolv n ordine invers (n mers invers), xn,xn-1,,x1 (n ordinea indicat de sgeat n (3.1.7)) Metoda eliminrii complete Gauss - Jordan, nrudit cu metoda lui Gauss, const n a transforma sistemul de n

ecuaii algebrice liniare cu n necunoscute Ax = b ntr-un sistem de ecuaii echivalent, care are ca matrice a coeficienilor

necunoscutelor chiar matricea unitate, adic ntr-un sistem de forma:

Ix = e, adic

n

3

2

1

e 1 ... 0 0 0. . . . . . . .

e 0 ... 1 0 0e 0 ... 0 1 0e 0 ... 0 0 1

, de unde

=

=

=

=

nn

33

22

11

ex

. . . .

ex

ex

ex

. (3.1.8)

Karl Friedrich Gauss (1777 - 1855) Camille Jordan (1838-1922)


43

Practic, pornind de la matricea extins (E), se aplic de mai multe ori operaiile (3.1.5) pn ce matricea (E) se transform n matricea din (3.1.8). Exemplu 3.1.1. Utiliznd metoda eliminrii succesive, respectiv complete, s se afle soluia sistemului

=++

=+

=+

=+

2x8x4x6x3x8xx2x45x2x3x3x21x3x4x2x

4321

4321

4321

4321

. (3.1.9)

Soluie. Matricea extins a sistemului (3.1.9), este:

2 8 4- 6 13 8- 1 2- 45 2- 3 3- 21- 3- 4 2- 1

+

+

+

Efectund operaiile (1.3.5) vom face s apar pe prima coloan elemente nule sub primul element 1. n acest scop vom nmuli: prima linie cu -2 i o vom aduna la a doua; prima linie cu -4 i o vom aduna la a treia; prima linie cu -1 i o vom aduna la a patra. Obinem:

3 11 8- 8 0 7 4 15- 6 0

7 4 5- 1 01- 3- 4 2- 1

+

+ (3.1.10)

n continuare, cu operaiile indicate prin sgeat, vom obine elemente nule pe coloana a doua sub elementul 1, (primele dou linii rmn neschimbate):

53 - 21- 32 0 0 35- 20- 15 0 0

7 4 5- 1 01- 3- 4 2- 1

151

sau

53 - 21- 32 0 0

37

-

34

- 1 0 0

7 4 5- 1 01- 3- 4 2- 1

+

365

365

0 0 0

37

-

34

- 1 0 0

7 4 5- 1 01- 3- 4 2- 1

653

Am obinut n final matricea:

1 1 0 0 0

37

-

34

- 1 0 0

7 4 5- 1 01- 3- 4 2- 1

, (3.1.11)

adic sistemul echivalent cu (3.1.9)

=

=

=+

=+

1 x 37

x34

x

7x4x5 x1x3x4x2x

4

43

432

4321

1x1x2x

2x

4

3

2

1

=

=

=

=

; x =

1 122

. (3.1.12)

Pentru metoda eliminrii complete, pornim de la matricea (3.1.10) i facem s apar i element nul pe coloana a doua, deasupra lui 1:

3 11 8- 8 07 4 15- 6 07 4 5- 1 01- 3- 4 2- 1

+

+

+

(3.1.10)

53- 21- 32 0 035- 20- 15 0 07 4 5- 1 0

13 5 6- 0 1

151

;

53- 21- 32 0 037

-

34

- 1 0 0

7 4 5- 1 013 5 6- 0 1

(-2) (-4) (-1)

(-32)

(-6) (-8)

(6) (5) (-32) +

(2) (-6) (-8)

+

+


44

365

365

0 0 0

37

-

34

- 1 0 0

314

-

38

- 0 1 0

1- 3- 0 0 1

653

1 1 0 0 037

-

34

- 1 0 0

314

-

38

- 0 1 0

1- 3- 0 0 1

n final, gsim elemente nule pe coloana 4, liniile 1,2,3:

1 1 0 0 01- 0 1 0 02- 0 0 1 02 0 0 0 1

,

de unde obinem sistemul echivalent cu (3.1.9),

=

=

=

=

1x1x2x

2x

4

3

2

1

i de aici vectorul coloan cutat x =

112

2

. (3.1.11)

c) Metoda matricelor tridiagonale (Jacobiene). O matrice ptratic A de ordinul n se numete tridiagonal sau Jacobian dac este de forma

A =

nn

1n1n1-n

333

222

11

a b 0 ... 0 0 0 0cab ... 0 0 0 0

. . . . . . . . . . . .

0 0 0 ... c a b 00 0 0 ... 0 c a b0 0 0 ... 0 0 c a

. (3.1.13)

Fie sistemul de n ecuaii liniare cu n necunoscute scris n forma matriceal Ax = d, cu x =

n

2

1

x

...

x

x

, d =

n

2

1

d...

dc

,

A matricea din (3.1.13). Dac matricea A admite o factorizare sub forma A = T S, unde T i S sunt matrice bidiagonale, a doua avnd

diagonala unitate, atunci

A = TS =

nn

1-n1-n

33

22

1

0 ... 0 0 0 00 ... 0 0 0 0

. . . . . . . .

0 0 0 ... 0 00 0 0 ... 0 0 0 0 0 ... 0 0 0

1 0 0 ... 0 0 0 0 1 0 ... 0 0 0 0

0 1 ... 0 0 0 0. . . . . . . .

0 0 0 ... 1 0 00 0 0 ... 0 1 00 0 0 ... 0 0 1

1-n

2-n

3

2

1

sau

A =

+

++

n1nnn

333233

222122

111

0 ... 0 0 0 0 . . . . . . . . . . . . . . . . . . . . . . . . . . . .

0 0 0 ... 00 0 0 .. 0 0 0 0 ... 0 0

.

Comparnd cu (3.1.13) determinm elementele i,i,i n funcie de valorile date ai,bi,ci : 1 = a1 , ii-1 + i = ai , i = n,2 , ii = ci , i = 1n,1 , i = bi , i = n,2 , de unde:

34

38

(3)

+

+

+


45

==

==

==

=

1n,1i,

c

n,2i,a

n,2i,ba

i

ii

1iiii

ii

11

(3.1.14)

ultimele dou relaii (3.1.14) calculndu-se alternativ (1,2,2,3,etc). Dac i 0, i = n,1 , matricea A se poate scrie ca produs al matricelor T i S, iar elementele acestora sunt date

de (3.1.14). Ecuaia matriceal dat Ax = d ia forma TSx = d. Notnd Sx = y, vectorul necunoscut x se obine din lanul de ecuaii: Ty = d i Sx = y . (3.1.15) Prima din ecuaiile matriceale (3.1.15) ne d sistemul:

=+

=+

=+

=+

=

d y ydyy

. . . . . . . . . .

d y y d yy

d y

nnn1nn

1n1-n1n2-n1n

33323

22212

111

cu soluia

==

=

n,2i),yd(

1y

dy

1iiii

i

1

11

. (3.1.16)

A doua ecuaie din lanul (3.1.15) ne d sistemul:

=

=+

=+

=+

=+

nn

1nn1n1-n

3433

2322

1211

yx yxx

...................

y xxy xx

y xx

cu soluia

==

=

+ 1,2,3,...,2n,1ni,xyxyx

1iiii

nn . (3.1.17)

n concluzie, metoda matricelor tridiagonale se poate aplica numai dac i 0, i= n,1 . Exemplul 3.1.2. Utiliznd metoda matricelor tridiagonale, s se rezolve sistemul:

=+

=+

=+

=+

=+

=++

=

5,5x54x 192x3x-1,2x

5 xx21,5x -3,5 x3 x4x -8,5 xx32x

0,5 x2x3x2,5 x2x

76

765

654

543

432

321

21

. (3.1.18)

Soluie. Avem, comparnd cu (3.1.13): a1 = 1, a2 = 3, a3 = -3, a4 = 1, a5 = 2, a6 = -3, a7 = 5;

b2 = 1, b3 = 2, b4 = 4, b5 = 1,5, b6 = 1,2, b7 = 4; c1 = -2, c2 = 2, c3 = 1, c4 = -3, c5 = -1, c6 = 2;

d1 = 2,5, d2 = 0,5, d3 = -8,5, d4 = -3,5, d5 = 5, d6 = 19, d7 = 5,5. Utiliznd (3.1.14), gsim:

i = bi, i = n,2 , 2 = 1, 3 = 2, 4 = 4, 5 = 1,5, 6 = 1,2, 7 = 4.

1 = a1 = 1, 1 = 1

1

c = -2, 2 = a2 - 21 = 3 - 1 (-2) = 5

2 = 2

2

c =

52

= 0,4, 3 = a3 - 32 = -3 - 2 0,4 = -3,8 .a.m.d.

n acest mod, obinem: 1 = 1, 2 = 5, 3 = -3,8, 4 =

1939

, 5 = 13

5,54, 6 = - 5,54

9,147, 7 = 9,147

5,1175;

(mers direct)

(mers invers)


46

1 = -2, 2 = 0,4, 3 = - 8,31

, 4 = -1319

, 5 = - 5,5413

, 6 = - 9,147109

.

Folosind (3.1.16) determinm componentele vectorului y,

y1 = 1

1

d = 2,5 , y2 =

2

1 (d2 - 2y1) = 51 (0,5 - 1 2,5) = -0,4

y3 = 3

1 (d3 - 3y2) = - 8,31 (-8,5 - 2 (-0,4)) =

8,37,7

, .a.m.d.

astfel c:

y1 = 2,5, y2 = -0,4, y3 = 8,37,7

, y4 = -26

147, y5 =

1095,350

, y6 = - 9,1472,825

, y7 = 3,5.

Cu formulele (3.1.17) determinm componentele vectorului x:

x7 = y7 = 3,5; x6 = y6 - 6x7 = - 9,1472,825

+ 9,147

109 3,5 = -3

x5 = y5 - 5x6 = 109

5,350 +

5,5413 (-3) = 2,5 .a.m.d.

Vectorul necunoscut x, soluia sistemului (3.1.18), este:

x =

5,335,225,115,0

.

B. Metode aproximative de rezolvare a sistemelor de ecuaii liniare

3.2. Norma unei matrice. iruri i serii de matrice. Definiia 3.2.1. Spunem c matricele A = [aij], B = [bij] Mn,r(R), sunt n relaia:

A B def aij bij, i = n,1 , j = r,1 . (3.2.1)

Se vede, din definiia 3.2.1, c nu oricare dou matrice de acelai tip sunt comparabile ntre ele prin relaia

(3.2.1), care este astfel o relaie de ordine parial pe mulimea Mn,r(R). Definiia 3.2.2. Se numete valoare absolut a unei matrice A = [aij] Mn,r (elementele matricelor din mulimea Mn,r pot fi numere reale sau complexe), matricea format cu modulele elementelor matricei A i notm: A = [aij], (aij fiind modulele elementelor aij ale matricei A). (3.2.2) Dac A i B sunt matrice pentru care operaiile A + B, A B au sens, atunci:

10 A + B A + B

20 A B A B, n particular Ap Ap, p N*, A Mn,n

30 A = A, numr. Definiia 3.2.3. Se numete norm a matricei A = [aij] Mn,r, numrul real A care verific: 10 A 0, A = 0 A = O,

20 A = A, numr, ( = -1, -A = A) 30 A + B A + B dac operaiile au sens

40 A B A B (n particular Ap Ap, A matrice ptratic) Observaia 3.2.1. Din axiomele normei unei matrice rezult i A - B A - B. ntr-adevr, B = A + B - A A + B - A B - A B - A

A = B + A - B B + A - B A - B A - B A - B A - B.


47

Definiia 3.2.4. O norm de matrice se numete canonic dac verific i condiiile suplimentare:

50 aij A (modulul unui element nu poate depi norma matricei respective) 60 inegalitatea A B conduce la AB (A = A). Pentru o matrice A = [aij] Mn,r se consider trei norme uor de calculat:

1) Am = ni1

max

=

r

1jaij = cea mai mare dintre sumele modulelor elementelor de pe linii. Am se

numete m - norma sau norma maxim i se mai noteaz Am = A;

2) Al

=

rj1max

=

n

1iaij = cea mai mare dintre sumele modulelor elementelor de pe coloane. A

l se

numete l - norma i se mai noteaz Al = A1 ;

3) Ak = matriceir elementelomodulelor ptratelor sumaan

1i

r

1j2

ij = = =

. Ak se numete k - norma

sau norma euclidian i se mai noteaz Ak = A2 = AE.

Se arat c cele trei tipuri de norme de matrice sunt canonice. Exemplul 3.2.1. S se afle normele urmtoarelor matrice:

A =

12- 11 10-9 8- 7 6- 5 4- 3 2- 1

M4,3(R); x =

n

3

2

1

x

..

x

x

x

Mn,1; I =

1 ... 0 0 0.. ... ... ..

0 ... 1 0 00 ... 0 1 00 ... 0 0 1

= In

Soluie. Am = max {1 + 2 + 3, 4 + 5 + 6, 7 + 8 + 9, 10 + 11 + 12} = 33. Al = max {1 + 4 + 7 + 10, 2 + 5 + 8 + 11, 3 + 6 + 9 + 12} = 30.

Ak = 2222 12...321 ++++ = 6)124)(112(12 ++

= 2526 = 5 26 25,5.

xm = ni1

max

xi = cel mai mare dintre modulele elementelor liniilor.

xl =

=

n

1ixi = x1 + x2++xn = suma modulelor elementelor coloanei.

xk = ) x...xx( x...xx 2n2221Rix

2n

22

21 +++=+++

.

Pentru matricea unitate, avem:

Im = Il = 1, Ik = n . (3.2.3)

Definiia 3.2.5. Dou norme As, xs, prima fiind norm de matrice din Mn,n(R), iar a doua norm de matrice coloan din Mn,1(R) (vector coloan x Rn) se numesc compatibile ntre ele, dac: Axs As xs. (3.2.4) Se arat c normele de matrice As i xs, A Mn,n i x Mn,1, sunt compatibile ntre ele pentru

s = m, s = l, s = k.

Definiia 3.2.6. Limita irului de matrice Ap = [aij(p)] Mn,r , este matricea A = [aij] dac i numai dac

plim aij(p) = aij, i = n,1 , j = r,1 i se noteaz:

A = p

lim Ap = [p

lim aij(p)] sau Ap A pentru p . (3.2.5)

Observaia 3.2.2. Termenul general Ap al irului de matrice Ap are ca elemente termenii de rang p ale unor

iruri numerice aij(p). irul Ap are limita A = [aij] numai dac toate irurile numerice aij(p) au limit, aij(p) aij. Dac toate


48

numerele aij sunt finite, (adic irurile aij(p) sunt convergente) irul de matrice Ap este convergent, Ap A (Ap converge la A). n general, n continuare, ne intereseaz irurile convergente de matrice. n cele ce urmeaz prin nelegem oricare din cele trei norme canonice dac nu se specific tipul normei. Proprietatea 3.2.1. Ap A Ap - A 0, pentru p , (3.2.6) iar Ap A pentru p . (3.2.6') Consecina 3.2.1. Lund n (3.2.6) A = O, se obine: Ap O Ap 0. (3.2.7) Privind operaiile cu iruri convergente de matrice, reinem:

Proprietatea 3.2.2 Dac p

lim Ap = A i p

lim Bp = B, atunci:

plim (Ap Bp) = A B,

plim (Ap Bp) = A B,

plim Ap-1 = A-1, (3.2.8)

dac operaiile au sens. Criteriul general de convergen al lui Cauchy pentru un ir de matrice se enun n modul cunoscut de la

iruri numerice: Ap convergent > 0, p N astfel nct p > p i q N*, avem:

Ap+q - Ap < . (3.2.9)

Definiia 3.2.7. Se numete serie matriceal o serie de forma

=1ppA , unde Ap este un ir de matrice,

Ap Mn,r (elementele matricei Ap fiind numere din R sau C).

Fie Sp = =

p

1hhA suma parial de ordinul p a seriei

=1ppA .

Definiia 3.2.8. Dac Sp converge la S, Sp S pentru p , spunem c seria

=1ppA este convergent i

matricea S este suma seriei, S =

=1ppA .

Dac irul Sp nu este convergent seria matriceal Ap se numete divergent.

Proprietatea 3.2.3. Condiia necesar ca Ap s fie convergent este ca Ap O, p .

Definiia 3.2.9. Seria Ap se numete absolut convergent dac Ap este convergent.

Proprietatea 3.2.4. O serie matriceal absolut convergent este convergent.

Teorema 3.2.1. Dac seria

=1ppA este convergent, atunci seria

=1ppA este absolut convergent.

Demonstraie. Fie Ap = [aij(p)], p = 1,2,3, , i = n,1 , j = r,1 . Considerm seriile numerice

=1p

)p(ija .

Folosind definiia 3.2.4 a normei canonice de matrice aij(p) Ap, cu primul criteriu al comparaiei relativ

la seriile numerice cu termeni pozitivi, )p(ija , pA , innd seama de ipoteza teoremei, rezult c toate seriile

numerice )p(ija sunt convergente. De aici urmeaz c seria pA este convergent, de unde cu definiia 3.2.9 rezult

c seria pA este absolut convergent.

Pentru cele ce urmeaz prezint interes seriile matriceale ntregi.

Fie seria matriceal ntreag dreapt:

X Mn,n(R)

=0h

hh XA ,

unde Metode Numerice- Siclovan I., Heljiu M.

49

Ah Mr,n(R) sau Ah R sau Ah M1,n(R) (3.2.10)

i seria matriceal ntreag stng:

X Mn,n(R) Ah Mn,r(R) sau Ah R sau Ah Mn,1(R) (3.2.11)

Teorema 3.2.2. Dac R este raza de convergen a seriei de puteri (scalare)

=0h

hh xA , adic R =

hlim

1h

hAA

+,

atunci seriile (3.2.10) i (3.2.11) sunt absolut convergente pentru X < R . (3.2.12) Demonstraie. innd seama de proprietatea 40 a normei unei matrice (definiia 3.2.3), avem: AhXh AhXh AhXh . (3.2.13) Cum seria de numere pozitive AhXh este convergent (deoarece X < R , X (-R,R) , unde (-R,R) este intervalul de convergen absolut a seriei (Ahxh), rezult cu primul criteriu de comparaie i inegalitatea (3.2.13) c seria AhXh este convergent. De aici, cu teorema 3.2.1 rezult c seria AhXh este absolut convergent n baza relaiei (3.2.12). La fel se demonstreaz i convergena absolut a seriei (3.2.11). Teorema 3.2.3. Seriile matriceale geometrice

A + AX + AX2 ++ AXh + sau A M1,n(R) (3.2.14) A,X Mn,n(R) A + XA + X2A ++ XhA + sau A Mn,1(R) (3.2.15) sunt absolut convergente pentru: X < 1 (3.2.16) i

=0hAXh = A(I - X)-1,

=0hXhA = (I - X)-1A . (3.2.17)

Demonstraie. n baza teoremei 3.2.2 , raza de convergen a seriei de puteri scalare

=0hAxh

este R = h

limAA

= 1 i cum prin ipoteza (3.2.16) X < 1 seria (3.2.14) este absolut convergent (deci i

convergent !). Fie S suma acestei serii, S =

=0hAXh.

Pentru a determina suma S, pornim de la identitatea: A(I + X + X2 + X3 ++Xh)(I - X) = A(I - Xh+1). (3.2.18) Trecem la limit n (3.2.18) i obinem (h ). S(I - X) = A (3.2.19) ntr-adevr, Xh+1 O pentru h deoarece din X < 1 Xh+1 Xh+1 0, h , de unde Xh+1 0, iar de aici cu (3.2.7), avem Xh+1 O.

Dac lum A = I n (3.2.19), S se va nlocui cu S1 =

=0hXh i aceasta va deveni:

S1(I - X)=I. (3.2.20) Din (3.2.20) rezult det S1 det (I - X) = det I = 1 0. De aici deducem det (I - X) 0 astfel c I - X este o matrice nesingular i are inversa (I - X)-1. nmulind la dreapta n (3.2.19), obinem: S(I -X)(I - X)-1 = A(I - X)-1, de unde S = A(I - X)-1. Aadar:

=0hh

h AX , unde


50

S =

=0hAXh = A(I - X)-1

i cu aceasta am dovedit prima egalitate (3.2.17). Analog se dovedete i a doua egalitate.

Consecina 3.2.3. Dac X < 1, exist matricea invers (I - X)-1 =

=0hXh (egalitate care rezult din prima

egalitate (3.2.17) pentru A = I). n plus, dac I = 1 (m - norma, l - norma), avem:

(I - X)-1

=0hXh =

X11

(3.2.21)

deoarece I+X+X2++ Xh + = 1 + X+ X2++ Xh += X1

1

.

3.3. Metoda aproximaiilor succesive a lui Jacobi de rezolvare a sistemelor de ecuaii liniare Fie sistemul de n ecuaii algebrice liniare cu n necunoscute:

=++++++

=++++++

=++++++

=++++++

=++++++

nnnnini33n22n1n1

ininiii33i22i1i1

3nn3ii3333232131

2nn2ii2323222121

1nn1ii1313212111

bxa...xa...xaxaxa . . . . . . . . . . . . . . . . . . . . . . . . .

bxa...xa...xaxaxa . . . . . . . . . . . . . . . . . . . . . . . . . .

bxa...xa...xaxaxabxa...xa...xaxaxa

bxa...xa...xaxaxa

. aij, bi R . (3.3.1)

Notnd

A =

nnn21n

2n2221

1n1211

a ... a a

. . . . . . . .

a ... a a

a ... a a

, x =

n

2

1

x

x

x

, b =

n

2

1

b

bb

,

sistemul (3.3.1) se scrie sub forma matriceal: Ax = b. (3.3.1') Presupunnd coeficienii diagonali nenuli, aii 0, i = n,1 (se pot permuta eventual dou ecuaii ntre ele !),

putem rezolva ecuaiile sistemului (3.3.1) n raport cu xi, i = n,1 .

+=

+=

+=

+=

+=

nn

n1n

nn

1n,ni

nn

ni2

nn

2n1

nn

1nn

ii

in

ii

in2

ii

2i1

ii

1ii

33

3n

33

n3i

33

i32

33

321

33

313

22

2n

22

n2i

22

i23

22

231

22

212

11

1n

11

n1i

11

i13

11

132

11

121

a

bx

a

a...x

a

a...x

a

ax

a

ax

. . . . . . . . . . . . . . . . . . . . . . . . . .

a

bx

a

a. . . . . . . . .x

a

ax

a

ax

. . . . . . . . . . . . . . . . . . . . . . . . . .

a

bx

a

a...x

a

a...x

a

ax

a

ax

a

bx

a

a...x

a

a...x

a

ax

a

ax

a

bx

a

a...x

a

a...x

a

ax

a

ax

.

Cu notaiile


51

-

ii

ija

a = bij, i j, (bij = 0, i = j),

ii

ia

b = di, i = n,1 , (3.3.1'')

sistemul precedent se scrie:

++++=

++++=

++++=

++++=

n1n1n,n22n11nn

3nn32321313

2nn23231212

1nn13132121

dxb...xbxbx . . . . . . . . . . . . . . . . . . . .

dxb...xbxbxdxb...xbxbx

dxb...xbxbx

, (3.3.2)

iar cu notaiile

B =

0 ... b b b . . . . . . . . .

b ... 0 b bb ... b 0 bb ... b b 0

n3n2n1

3n3231

2n2321

1n1312

, x =

n

3

2

1

x

x

x

x

, d =

n

3

2

1

d

ddd

sub forma matriceal x = Bx + d. (3.3.2') Evident, sistemele (3.3.1) i (3.3.2) sunt echivalente (au aceeai soluie). Sistemul (3.3.2), respectiv (3.3.2'), se numete forma redus a sistemului (3.3.1), respectiv (3.3.1'). Cutm soluia sistemului (3.3.2), respectiv (3.3.2') prin metoda aproximaiilor succesive. Lum ca aproximaie iniial:

x(0)

=

0

000

sau x(0) = d sau x(0) oarecare din Rn.

Obinem aproximaiile succesive x(1) = Bx(0) + d, x(2) = Bx(1) + d, x(3) = Bx(2) + d,

x(p+1)

= Bx(p) + d, p = 0,1,2, (3.3.3) Dac irul de aproximaii succesive (3.3.3) (irul iterativ Jacobi) x(p) are limit, adic

plim x(p) = x*, atunci x*

este soluie a sistemului redus (3.3.2') deci soluie a sistemului (3.3.1). ntr-adevr, trecnd la limit n (3.3.3), obinem:

plim x(p+1) = B

plim x(p) + d x* = Bx* + d, x(p) =

)p(n

)p(2

)p(1

x

x

x

, x* =

*n

*2

*1

x

x

x

.

Observaia 3.3.1. Este posibil s scriem sistemul (3.3.1) sub forma x = Bx + d fr a rezolva acest sistem n raport cu xi , i = n,1 , cum s-a procedat mai sus. Este posibil s se scrie sistemul (3.3.1) sub forma (3.3.1') fr ca

bii = 0 , i = n,1 . ntr-adevr, de exemplu, ecuaia 2,6 x1 - 0,5x2 + 0,3x3 - 0,1x4 6=0 se poate scrie: x1 = -1,6x1 + 0,5x2 - 0,3x3 + 0,1x4 + 6, (b11 = -1,6).

Teorema 3.3.1. (criteriu de convergen pentru irul iterativ Jacobi).

* Carl Gustav Jacob Jacobi (1804 - 1851)


52

Pentru ca irul iterativ Jacobi (3.3.3) pentru sistemul liniar redus (3.3.2') s fie convergent ctre unica soluie x* a sistemului (3.3.2), oricare ar fi aproximaia de start x(0) Rn, este suficient ca o norm canonic oarecare a matricei B s fie mai mic dect 1, adic:

B < 1 (m - norma, l - norma, k - norma) (3.3.4) Demonstraie. Pornind de la o aproximaie de start x(0) oarecare, construim irul aproximaiilor succesive:

x(1)

= Bx(0) + d ; x

(2) = Bx(1) + d = B(Bx(0) + d) + d = B2x(0) + Bd + d ;

x(3) = Bx(2) + d = B (B2x(0) + Bd + d) + d = B3x(0) + B2d + Bd + d ; . . . . . . . . . . . . . .

x(p)

= Bpx(0) + Bp-1d + Bp-2d ++ B2d + Bd + d , adic

x(p)

= Bpx(0) + d + Bd + B2d ++Bp-1d (3.3.5) Trecnd la limit n (3.3.5), avem:

plim x(p) =

plim Bpx(0) +

plim (d + Bd + B2d ++ Bp-1d) (3.3.6)

Dar p

lim Bp = O, deoarece Bp Bp 0 pentru p , B < 1, de unde rezult Bp 0 i cu

(3.2.7), obinem: Bp O.

Apoi, p

lim (d + Bd + B2d ++ Bp-1d) =

=0p Bpd = (I - B)-1d, unde am folosit (3.3.4) i (3.2.17).

Cu acestea (3.3.6) se transform n

plim x(p) = O x(0) + (I - B)-1d = x*,

adic: (I - B)-1d = x*. (3.3.7) nmulind la stnga (3.3.7) cu I - B, gsim d = (I - B)x*, d = Ix* - Bx* sau x* = Bx* + d, de unde rezult c x* este soluie a sistemului (3.3.2'). Pentru a arta unicitatea soluiei x*, scriem ecuaia (3.3.2') n forma (I - B)x = d. Cum exist inversa (I - B)-1 , avem det (I - B) 0 de unde urmeaz c sistemul (3.3.2) scris sub forma matriceal (I - B)x = d are soluie unic. Consecina 3.3.1. irul iterativ Jacobi (3.3.3) pentru sistemul liniar redus (3.3.2) converge, dac:

a) Bm = ni1

max

=

n

1j ijb < 1 sau b) B

l =

ni1max

=

n

1iijb

53

a') aii > ijn

1j' a

=

, i = n,1 (' nseamn c nu se ia n sum iia ) altfel spus, convergena are loc dac

modulele elementelor diagonale ale matricei A = [aij] depesc, pentru fiecare linie, suma modulelor elementelor nediagonale ale acelei linii; sau inegalitile

b') ajj > ijn

1 i

' a=

, j = n,1 (' nseamn c nu se ia n sum jja ) altfel spus, convergena are loc dac

modulele elementelor diagonale ale matricei A = [aij] depesc, pentru fiecare coloan, suma modulelor elementelor nediagonale ale acelei coloane; Din a') i b') se poate spune c irul iterativ Jacobi (3.3.3) converge dac matricea A are diagonala principal dominant n sensul c elementele ei, n modul, sunt mult mai mari dect modulele elementelor de pe liniile sau coloanele respective.

S artm c dac inegalitile a') din consecina 3.3.2 au loc, atunci i inegalitatea a) din consecina 3.3.1 are loc, de unde va rezulta convergena irului. ntr-adevr,

Bm = ni1

max

=

n

1jbij =

imax

=

n

1j jiiiij

a

a

= ijn

1j'

iiia

a

1 max

=

< 1 numai dac ijn

1j'

ii a a >=

, i = n,1 .

Teorema 3.3.2. (evaluarea erorii metodei aproximaiilor succesive Jacobi). Dac irul aproximaiilor succesive x(p+1) = Bx(p) + d pentru sistemul liniar redus x = Bx + d este convergent

(B < 1). x(p) x*, p , x* unica soluie a sistemului liniar redus, atunci au loc formulele de evaluare a erorii:

x* - x(p) B1

B

x(p) - x(p-1) B1 B p

x(1) - x(0) , (m, l, k - norma). (3.3.8)

Demonstraie. Folosind irul Jacobi (3.3.3), putem scrie: x(p+1) - x(p) = Bx(p) + d - Bx(p-1) -d = B(x(p) - x(p-1)) B x(p) - x(p-1)

unde am folosit i proprietatea 40 a normei de matrice. Aadar,

x(p+1) - x(p) B x(p) - x(p-1) (3.3.9) Aplicnd succesiv (3.3.9), obinem:

x(p+2) - x(p+1) B2x(p) - x(p-1),

x(p+3) - x(p+2) B3x(p) - x(p-1), .a.m.d. (3.3.9') Fie p,q N. Cu proprietile 30 i 40 ale normei i (3.3.9), (3.3.9'), obinem:

x(p+q) - x(p) =x(p+1) - x(p) + x(p+2) - x(p+1) + x(p+3) - x(p+2) ++ x(p+q) - x(p+q-1)

x(p+1) - x(p) + x(p+2) - x(p+1) + x(p+3) - x(p+2) ++ x(p+q) - x(p+q-1)

Bx(p) - x(p-1)+ B2x(p) - x(p-1)+ B3x(p) - x(p-1)++ Bqx(p) - x(p-1)=

= B(1 + B+B2 ++Bq-1)x(p) - x(p-1)= B B1

B1 q

x(p) - x(p-1)

Cu o ultim majorare, prin neglijarea lui q B , avem:

x(p+q) - x(p) B1

B

x(p) - x(p-1). (3.3.10)


54

Cum, prin ipotez irul x(p) este convergent, trecnd la limit n (3.3.10) pentru q , obinem formula de evaluare a erorii aposteriori

x* - x(p) B1

B

x(p) - x(p-1), p = 1,2,3, (3.3.11)

Prin aplicarea succesiv a relaiei (3.3.9), putem scrie: x(p) - x(p-1) Bx(p-1) - x(p-2) B2x(p-2) - x(p-3) Bp-1x(1) - x(0),

adic, x(p) - x(p-1) Bp-1x(1) - x(0). (3.3.12) Ducnd (3.3.12) n (3.3.11) se obine dubla inegalitate (3.3.8) din care se vede c formula aposteriori ne d o evaluare mai bun a erorii dect formula apriori. Exemplul 3.3.1. Utiliznd metoda aproximaiilor succesive, s se afle soluia sistemului:

=++

=++

=++

=+

8,1x10x8,1x6,1x5,15,1x6,0x5x5,0x4,0

4,2x3,0x4,0x4x2,0 2,1x1,0x3,0x2,0x2

4321

4321

4321

4321

(3.3.13)

cu eroarea mai mic dect 10-5. Soluie. Pentru sistemul dat, consecina 3.2.2 a') ne asigur convergena irului Jacobi ctre soluia unic x* a sistemului. ntr-adevr, modulele elementelor diagonale (2,4,5,10) depesc, pentru fiecare linie, suma modulelor elementelor nediagonale ale liniei respective. (Se observ c b') nu este ndeplinit deoarece pentru prima coloan avem 2 < 0,2 + 0,4 + 1,5). Sistemul liniar redus corespunztor, este:

++=

+=

+=

++=

18,0x18,0x16,0x15,0x3,0x12,0x1,0x08,0x

6,0x075,0x1,0x05,0x6,0x05,0x15,0x1,0x

3214

4213

4312

4321

, B =

0 0,18

Metode numerice

Documents

Transcript of Metode numerice