36

ANALIZĂ NUMERICĂ

Conf. univ. dr. Gheorghe Grigore

I. APROXIMĂRI, ERORI

DefiniŃie. Dacă într-un calcul, în exprimarea unui rezultat înlocuim

numărul (vectorul) a cu numărul (vectorul) *a , spunem că l-am aproximat pe a

cu *a . DiferenŃa ** aaa −=∆ se numeşte eroarea cu care l-am aproximat pe a

prin *a . Spre exemplu, dacă numărul real a , care este o fracŃie zecimală infinită, se

aproximează cu o fracŃie zecimală *a finită unde în fracŃia infinită a lui a s-au înlocuit cu zero cifrele zecimale de la un rang în colo, se spune că aproximarea s-a

făcut prin rotunjire, iar diferenŃa *aa − se numeşte eroare de rotunjire. Astfel,

dacă ......, 2210 aaaaa = şi nn aaaaaaaaa ...,...00..., 210210* == , spunem că

rotunjirea s-a făcut la zecimala de ordin n. O asemenea rotunjire se poate face şi astfel:

<

≥+=

+

+−

5dacã...,

5adacã10...,

1210

1n210*

nn

nn

aaaaa

aaaaa

În acest caz naa −⋅≤− 102

1* .

DefiniŃie. Dacă a este un număr (vector), iar *a este numărul (vectorul)

obŃinut ca efect al unei formule matematice (egalitate, inegalitate), atunci *aa − se numeşte eroare de metodă sau rest. Astfel, prin aproximarea sumei unei serii convergente cu o sumă parŃială a sa, eroarea ce se face este un rest (numit chiar restul seriei). În formula lui Taylor:

( ) ( ) ( ) ( ) 10

)1(

00

0)(

)!1(!)( +

+

=

−+

ξ+−=∑ n

nn

k

kk

xxn

fxx

k

xfxf ,

expresia ( ) ( ) 1

0

)1(

)!1(+

+

−+

ξ nn

xxn

f este restul în aproximarea lui )(xf prin

( ) ( )∑=

−n

k

kk

xxk

xf

00

0)(

!.

De obicei, nu se evaluează *a∆ ci ** aaa −=∆ numită valoarea

absolută a erorii. De regulă, se poate găsi doar un majorant ∆′≤− *aa .

37

DefiniŃie. O cifră zecimală de ordinul n a lui *a se numeşte cifră exactă

dacă valoarea absolută a erorii nu depăşeşte n−10 .

De exemplu, dacă 73214,1=a şi 73202,1* =a , atunci primele patru

zecimale din *a sunt exacte.

În condiŃiile precedente, dacă a şi *a sunt vectori într-un spaŃiu normat,

atunci eroarea se apreciează prin *aa − , de fapt printr-un majorant pentru

*aa − .

II. METODE DIRECTE DE REZOLVARE A SISTEMELOR

DE ECUATII LINIARE

II.1. Metoda lui Gauss

Se consideră sistemul aAx = (1)

unde ( ){ }mjiijaA,...,1, ∈

= este o matrice reală, ( )maaa ,...,1= , mRa∈ şi

( )mxxx ,...,1= , mRx∈ . Presupunem că sistemul are soluŃie unică, deci că

0det ≠A . În metoda Gauss se transformă sistemul (1) în unul echivalent cu matricea triunghiulară. Transformarea se face prin operaŃii liniare, realizându-se eliminarea succcesivă a necunoscutelor. Sunt necesare şi unele permutări de linii şi de coloane, operaŃii numite de pivotare. Fixăm prima coloană în (1) şi permutând două linii plasăm coeficientul de modul maxim din prima coloană în prima linie. În particular, acest coeficient (numit pivot) este nenul. Sistemul se scrie

)0(

1

)0(i

m

jjij axa =∑

=

, { }mi ,...,1∈ (2)

unde )0(1

)0(11 iaa ≥ , { }mi ,...,1∈∀ .

ÎmpărŃind prima linie a sistemului cu )0(11a ea devine

1)1(

12)1(

121 ... bxaxax mm =+++ (3)

unde )0(

11

)0(1)1(

1a

aa j

j = , { }mj ,...,2∈ , )0(

11

)0(1

1a

ab = .

38

Pentru { }mi ,...,2∈ înmulŃim ecuaŃia (3) cu )0(1ia şi o scădem din linia i a

sistemului (2). ObŃinem sistemul:

)1()1(2

)1(2

)1(2

)1(22

)1(22

1)1(

12)1(

121

...

...

...

mmmmm

mm

mm

axaxa

axaxabxaxax

=++

=++=+++

⋯ (4)

unde )1()0(

1)0()1(

ijiijij aaaa −= , { }mji ,...,2, ∈

1)0(

1)0()1( baaa iii −= , { }mi ,...,2∈

Determinantul matricii sistemului format cu ultimele 1−n linii ale sistemului (4) este nenul, căci, în caz contrar, ar rezulta 0det =A . Procedeul aplicat în prima etapă se poate aplica sistemului

)1()1(2

)1(2

)1(2

)1(22

)1(22

...

...

mmmmm

mm

axaxa

axaxa

=++

=++

⋯

După m paşi se ajunge la sistemul

mm

mm

mm

bx

bxaxaxbxaxax

=

=+++=+++

⋯2

)2(23

)2(232

1)1(

12)1(

121

......

(5)

Sistemul (5) este atunci echivalent cu (1) şi din mm bx = obŃinem succesiv

∑+=

−=m

ijj

iijii xabx

1

)( , { }1,...,1−∈ mi

ObservaŃie. În procedeul prezentat, s-au permutat numai linii şi se spune că rezolvarea s-a făcut prin pivotare parŃială. Dacă se permută şi coloane, se poate realiza ca la fiecare pas să se obŃină un sistem în care coeficientul pivot să fie cel mai mare în modul printre coeficienŃii sistemului (se spune că rezolvarea s-a făcut prin pivotare totală). Se încearcă prin aceasta să se evite împărŃiri la numere mici, caz în care erorile de rotunjire pot fi mai mari. Exemplu. Folosind metoda lui Gauss să se rezolve sistemul:

35,899,669,165,321,2

45,1528,204,821,777,3

21,1246,278,745,892,3

65,1090,110,462,23,8

4321

4321

4321

4321

−=+++

=+++

=+++

−=+++

xxxx

xxxx

xxxx

xxxx

Prin pivotare de linii şi după operaŃiile descrise mai sus se obŃine:

39

7392314,0

4353474,49999438,55358069,40866916,0

571198,128444456,57936942,1

8982563,51127318,03003764,13902438,22166556,08101949,05142771,54840965,65983132,09523856,2

2874090,204169881,11777108,60193519,6

2398790,175626508,18436144,52126026,72831325,12289156,04939759,03156626,0

4

4

43

43

43

432

432

432

432

4321

−=

−==+−=+−

=+=++−=++

=++

=++−=+++

x

xxxxx

xxxxxxxx

xxx

xxxxxxx

Rezultă apoi 599892,43 =x , 1764066,12 −=x , 0147991,31 −=x .

ExerciŃiu. Folosind metoda Gauss să se rezolve sistemul:

9,95,22,0

9,32,53,0

9,215,845,04,0

7,21,02

4321

4322

4321

4321

=−++

−=++−

=−++

=+−+

xxxx

xxxx

xxxx

xxxx

R. 11 =x , 22 =x , 33 =x , 14 −=x .

II. 2. Metoda rădăcinii pătrate

Pe mR se consideră produsul scalar canonic, ∑=

=m

iii yxyx

1

, . Matricea

reală ( ){ }mjiijaA,...,1, ∈

= se numeşte pozitiv definită dacă 0, >xAx , pentru orice

0≠x , mRx∈ , adică dacă 01,

>∑=

m

jijiij xxa , 0≠∀x , ( )mxxx ,...,1= .

Amintim că matricea B se numeşte triunghiulară subdiagonală dacă deasupra diagonalei principale are numai zerouri. Dacă ( )

{ }mjiijbB,...,1, ∈

= atunci

( ){ }mjijibB,...,1,

*

∈= .

Fundamentul teoretic al metodei rădăcinii pătrate este următorul rezultat de factorizare. Teorema 1. Matricea reală A este simetrică şi pozitiv definită dacă şi

numai dacă există matricea nesingulară B astfel încât *BBA = . Fie A simetrică, pozitiv definită, ( ) { }mjiaA ij ,...,1, ∈= şi B

nesingulară, triunghiulară subdiagonală, ( ){ }mjiijbB,...,1, ∈

= , astfel încât

ABB =* (1)

40

Pentru a avea loc (1) este suficient să luăm:

1111 ab = , 11

11 b

ab ii = , { }mi ,...,2∈ (2)

∑−

=

−=1

1

2i

kikiiii bab , { }mi ,...,2∈ (3)

−= ∑

−

=

1

1

1 i

kikjkji

iiji bba

bb , { }mij ,...,1+∈ (4)

0=ijb dacă ji < (5)

Fie sistemul de ecuaŃii liniare aAx = (6)

unde A este simetrică şi pozitiv definită. Pentru rezolvarea directă a acestui

sistem, după descompunerea precedentă *BBA = se ajunge la axBB =* şi se

rezolvă succesiv sistemele cu matrici triunghiulare aBy = şi apoi yxB =* . Dacă

( )maaa ,...,1= , soluŃia sistemului aBy = este

11

11 b

ay = (7)

−= ∑

−

=

1

1

1 i

kkiki

iii yba

by , { }mi ,...,2∈ (8)

Sistemul yxB =* dă, în fine, soluŃia sistemului (6):

mm

mm b

yx = (9)

−= ∑

+=

m

ikikii

iii xby

bx

1

1, { }1,...,1−∈ mi (10)

Exemplu. Folosind metoda rădăcinii pătrate să se rezolve sistemul:

9,022,044,066,0

7,022,032,054,0

5,044,032,042,0

3,066,054,042,0

4321

4321

4321

4321

=+++

=+++

=+++

=+++

xxxx

xxxx

xxxx

xxxx

SoluŃie. Cu formulele (2), (3) şi (4) se obŃine

−

=

7055999,01853329,01793891,066,0

08353761,01026969,054,0

009075241,042,0

0001

B

41

Cu formulele (7) şi (8) se obŃine 3,01 =y , 4121102,02 =y ,

5933585,03 =y , 0459763,14 =y .

În fine, cu formulele (9) şi (10) se obŃine 4823929,14 =x ,

0391662,13 =x , 04348,02 =x , 25778,11 −=x .

ExerciŃii. Cu metoda rădăcinii pătrate să se rezolve sistemele: a)

349,944,446,043,088,0

009,946,098,287,134,1

115,043,087,195,342,0

172,1188,034,142,012,2

4321

4321

4321

4321

=+++

=+++

=+++

=+++

xxxx

xxxx

xxxx

xxxx

R. 7,31 =x , 5,12 −=x , 1,23 =x , 3,14 =x

b)

7,032,054,0

5,032,042,0

3,054,042,0

321

321

321

=++

=++

=++

xxx

xxx

xxx

R. 240521,01 −=x , 3737264,02 =x , 7102889,03 =x .

II.3. Metoda lui Ritz de inversare a unei matrici

simetrice şi pozitiv definite

Ca şi în paragraful precedent, pe mR se consideră produsul scalar canonic. Fie ( )

{ }mjiijaA,...,1, ∈

= o matrice reală, simetrică şi pozitiv definită.

Amintim că vectorii mRvu ∈, se numesc A-ortogonali dacă 0, =vAu . Dacă

{ }mxx ,...,1 sunt vectori A-ortogonali şi nenuli, atunci formează bază în mR .

Dacă mRx∈ , se notează RRx m →:* , yxyx ,)(* = , iar dacă

( )maaax ,...,, 21= , atunci

=

221

22212

12121

*

mmm

m

m

aaaaa

aaaaa

aaaaa

xx

⋯

⋮⋱⋮⋮

⋯

⋯

.

Fie { }mxx ,...,1 vectori A-ortogonali şi nenuli. Notăm

*11

111 ,

1xx

xAxC = , ∑

=

=k

iii

iik xx

xAxC

1

*1 (1)

42

Teorema 1. Dacă kxx ,...,1 sunt A-ortogonali şi nenuli, atunci

jjk xAxC = , { }kj ,...,1∈ 1−= ACm .

Algoritmul următor construieşte un sistem de m vectori A-ortogonali

nenuli şi cu formulele (1) conduce la 1−A .

Fie 01 ≠x , mRx ∈1 , şi *11

111 ,

1xx

xAxC = .

Presupunem că am construit kxx ,...,1 vectori A-ortogonali şi nenuli.

Aceasta permite să construim

∑=

=k

iii

iik xx

xAxC

1

*

,

1.

Alegem apoi mRy∈ , astfel încât yAyCk ≠ . Fie AyCyx kk −=+1 . Atunci 1−= ACm .

Exemplu. Să considerăm matricea simetrică şi pozitiv definită

=

132,054,0

32,0142,0

54,042,01

A

Luăm )0,0,1(1 =x şi obŃinem

=

000

000

001

1C

Luăm apoi ( )0,1,0=y şi obŃinem 0)0;1;42,0(1 ≠−=− AyCy . Putem

lua )0;1;42,0(2 =x şi atunci

−

−

=

000

02141816,15099562,0

05099562,02141816,1

2C

Considerând )1;0;0(=y constatăm că

( )1;1131617,0;492472,02 −−=− AyCy şi putem lua deci

)1;1131617,0;492472,0(3 −−=x . Rezultă că

−−

−−

−−

==−

4329727,11621568,07056955,0

1621568,02325314,14300986,0

7056955,04300986,05617176,1

31 CA .

43

III. METODE ITERATIVE DE REZOLVARE A SISTEMELOR DE ECUAłII LINIARE

III.1. Elemente de analiză funcŃională

Se notează cu ( )mRL spaŃiul operatorilor liniari definiŃi pe mR . Se ştie că, organizat cu operaŃiile obişnuite de adunare, înmulŃire cu scalari şi cu operaŃia de

compunere, ( )mRL este o algebră cu unitate. Se notează cu I operatorul identitate

( xxI =)( , mRx∈∀ ).

Se notează cu mM mulŃimea matricilor reale cu m linii şi m coloane,

organizată ca algebră cu operaŃiile obişnuite de adunare, înmulŃire cu scalari şi înmulŃire a matricilor. Fiecărei matrici ( )

{ }mjiijaA,...,1, ∈

= i se asociază operatorul liniar, notat

pentru început A~, mm RRA →:

~, definit prin yxA =

~, unde dacă

( )myyy ,...,1= , ( )mxxx ,...,1= , atunci

∑=

=m

jjiji xay

1

, { }mi ,...,1∈

CorespondenŃa AA~

֏ este un izomorfism de algebre între mM şi

( )mRL , deci este o bijecŃie în care sumei a două matrici îi corespunde suma operatorilor, produsului dintre o matrice şi un număr îi corespunde produsul operatorului corespunzător cu acel număr, iar înmulŃirii a două matrici îi corespunde compunerea operatorilor corespunzători. Având în vedere acestea, se

identifică A~ cu A şi se notează operatorul A

~ tot cu A .

Dacă pe mR se fixează o normă, notată ⋅ , atunci pe spaŃiul ( )mRL se

consideră norma operatorială indusă:

AxAx 1sup

≤= .

Au loc proprietăŃile:

xAAx ⋅≤ , mRx∈∀

BAAB ⋅≤ .

De exemplu, dacă operatorul A este generat de matricea ( ){ }mjiija,...,1, ∈

, iar

pe mR se consideră ∞⋅ ( i

mixx

≤≤∞=

1max ), atunci se notează

∞≤∞

∞= AxA

x 1sup (1)

44

şi are loc formula

∑=

≤≤∞=

m

jij

miaA

11max (1')

Dacă se consideră pe mR norma 1⋅

=∑

=

m

i

xx1

11, atunci, prin

definiŃie

111

1sup AxAx ≤

= (2)

şi are loc formula

∑=

≤≤=

m

iij

mjaA

111max (2')

Deoarece ( ) ∞<= 2dim mRmL , orice două norme pe ( )mRL , în

particular cele date de (1) sau (2), sunt echivalente.

Amintim că prezenŃa unei norme pe ( )mRL conduce la existenŃa unei

distanŃe, ( ) BABAd −=, şi deci se poate vorbi în acest spaŃiu de convergenŃă,

continuitate etc. Astfel, dacă ( ) NnnA ∈ este un şir în ( )mRL şi ( )mRA L∈ , atunci

AAnn

=∞→

lim înseamnă 0lim =−∞→

AAnn

.

Fie ( )mRB L∈ , BBB ⋅=2 , …, 1−⋅= nn BBB . Teoremă 1. AfirmaŃiile următoare sunt echivalente:

i) 0lim =∞→

n

nB ;

ii) 1lim <∞→

n n

nB ;

iii) 0lim =∞→

xB n

n, pentru orice mRx∈ .

Se notează

( ) ( ){ }0det,max =λ−∈λλ=ρ IBCB

şi se arată că ( ) n n

nBB

∞→=ρ lim , deci afirmaŃiile din teorema precedentă sunt

echivalente şi cu ( ) 1<ρ B . Dacă una din afirmaŃiile din teorema precedentă are

loc, se scrie 0lim =∞→

n

nB .

MulŃimea ( ){ }0det =λ−∈λ IVC se numeşte spectrul lui B şi se notează

( )BS . Dacă matricea B este simetrică, atunci spectrul ei este format numai din numere reale.

45

Dacă o matrice T are spectrul format din numere reale, atunci ( )TS∈λ

dacă şi numai dacă există mRx∈ , 0≠x , astfel încât xTx λ= . Un asemenea vector x se numeşte vector propriu pentru T corespunzător valorii proprii λ .

Matricea T se numeşte pozitiv definită dacă 0, >xTx pentru orice mRx∈ , 0≠x ( , este produsul scalar canonic pe mR ).

Reamintim că o aplicaŃie RRp m →: se numeşte normă dacă

i) 00)( =⇒= xxp ;

ii) )()( xpxp λ=λ R∈λ∀ , mRx∈∀ ;

iii) )()()( ypxpyxp +≤+ mRyx ∈∀ , .

Atunci 0)( ≥xp pentru orice mRx∈ . Cu ajutorul unei asemenea

aplicaŃii se introduce pe mR noŃiunea de distanŃă între doi vectori: )(),( yxpyxd −= .

Se ştie că pe mR orice două norme p, q sunt echivalente în sensul :

0, >µλ∃ , astfel încât )()()( xpxqxp µ≤≤λ mRx∈∀ . Dacă p şi q sunt două norme echivalente, atunci un şir este convergent în raport cu norma p dacă şi numai dacă este convergent în raport cu norma q.

Dacă ( ) Nnnx ∈)( , ( ))()(

1)( ,..., n

mnn xxx = , atunci şirul ( ) Nn

nx ∈)( se numeşte

convergent dacă există ( ) mn Rxxx ∈= ,...,1 , astfel încât i

ni

nxx =

∞→

)(lim

{ }mi ,...,1∈∀ . Se scrie xx n

n=

∞→

)(lim .

Dacă p este o normă pe mR , atunci ( ) 0limlim )()( =−⇔=∞→∞→

xxpxx n

n

n

n.

III.2. Metoda lui Jacobi

Se consideră sistemul bxBI =− )( (1)

unde I este matricea unitate, ( ){ }mjiijbB,...,1, ∈

= , ( )mxxx ,...,1= , ( )mbbb ,...,1= .

Pe componente sistemul (1) se scrie

i

m

jjiji bxbx =−∑

=1

, { }mi ,...,1∈ (1')

Fie mRx ∈)0( şi ( ) Nnnx ∈)( şirul definit prin

bBxx nn +=+ )()1( (2)

46

Dacă ( ))()(2

)(1

)( ,...,, nm

nnn xxxx = atunci, pe componente, şirul (2) se scrie

i

m

j

njij

ni bxbx +=∑

=

+

1

)()1( , { }mi ,...,1∈ (2')

Teorema 1. AfirmaŃiile următoare sunt echivalente

i) 0lim =∞→

n

nB

ii) BI − este o bijecŃie şi pentru orice nRbx ∈,)0( , şirul (2) converge către

soluŃia z a sistemului (1).

Dacă ⋅ este norma operatorială indusă pe ( )mRL şi 1<≤ qB , atunci

au loc şi următoarele evaluări ale erorii:

)0()1()1()()(

11xx

q

qxx

q

qzx

nnnn −

−≤−

−≤− − .

Procedeul prin care soluŃia z se aproximează prin )(nx se numeşte metoda lui Jacobi. Fie sistemul

aAx = (3)

unde ( ){ }mjiijaA,...,1, ∈

= şi ( )maaa ,...,1= . Dacă 0≠iia pentru orice { }mi ,...,1∈ ,

atunci matricea

=

mma

a

D

⋯

⋮⋱⋮

⋯

0

011

este inversabilă şi

=−

mma

aD

10

01

111

⋯

⋮⋱⋮

⋯

.

Sistemul (3) este echivalent cu bxBI =− )( (4)

unde ADIB 1−−= şi aDb 1−= . Pe componente, sistemul (4) se scrie

∑≠

=

+−=m

ij

j ii

ij

ii

iji a

bx

a

ax

1

(4')

Presupunem că

∑≠

=

>m

ij

jijii aa

1

{ }mi ,...,1∈∀ (5)

47

Atunci

1:max11

<== ∑≠

=≤≤∞q

a

aB

m

ij

j ii

ij

mi (6)

Conform teoremei Jacobi, sistemul (5), şi deci (3), are pentru orice mRa∈ soluŃie unică z şi pentru orice mRx ∈)0( , şirul bBxx nn +=+ )()1(

converge către z. Au loc evaluările de eroare:

∞∞

−

∞−

−≤−

−≤− )0()1()1()()(

11xx

q

qxx

q

qzx

nnnn (7)

Dacă ( ))()(2

)(1

)( ,...,, nm

nnn xxxx = , atunci, pe componente, şirul este definit

prin

ii

im

ij

j

nj

ii

ijni a

ax

a

ax +−= ∑

≠

=

+

1

)()1( , { }mi ,...,1∈ (8)

Dacă au loc relaŃiile (5), se spune că matricea A este diagonal dominantă pe linii. Pentru acelaşi sistem (3) şi cu aceleaşi notaŃii ca mai sus, să presupunem că

∑≠

=

>m

ji

iijjj aa

1

{ }mj ,...,1∈∀ (9)

Sistemul (3) este schivalent cu ( ) aDxCI =− (10)

unde 1−−= ADIC . Considerăm sistemul

axCI =− )( (11) Din (9) rezultă că

1:max111

<== ∑≠

=≤≤q

a

aC

m

ji

i jj

ij

mj (12)

Conform teoremei lui Jacobi, sistemul (11) are soluŃie unică w şi, pentru

orice mRy ∈)0( , şirul ( ) Nnny ∈)( , definit prin aCyy nn +=+ )()1( , converge către

w. Atunci, sistemul (10), şi deci sistemul (3), are soluŃie unică z şi anume

wDz 1−= . Şirul ( ) Nnnx ∈)( , )(1)( nn yDx −= , converge către z şi au loc evaluările

de eroare:

q

qyy

aq

qyy

azx

n

iimi

nn

iimi

n

−−≤

−−≤−

≤≤

−

≤≤1min

1

1min

1 )0()1(

1

)1()(

1

1

)(

48

Dacă ( ))()(1

)( ,..., nm

nn yyy = , ( ))()(1

)( ,..., nm

nn xxx = , atunci

i

m

ij

j

nj

jj

ijni ay

a

ay +−= ∑

≠

=

+

1

)()1(

ii

im

ij

j

nj

jj

ij

ii

ni a

ay

a

a

ax +−= ∑

≠

=

+

1

)()1( 1

Dacă au loc inegalităŃile (9), se spune că matricea A este diagonal dominantă pe coloane. Exemplul 1. Să rezolvăm sistemul următor cu o eroare mai mică decât

310− :

78,221,114,025,0

555,115,013,141,0

515,03,025,002,1

321

321

321

=+−−

=−+−

=−−

xxx

xxx

xxx

Este evident că sunt adevărate inegalităŃile (5). Rezultă că sistemul este cu matrice diagonal dominantă pe linii şi deci are soluŃia unică z. SoluŃia se poate aproxima cu termenii şirului (8), care în acest caz devine:

2975206,21157024,02066115,0

3761061,11327433,03628318,0

5049019,02941176,0245098,0

)(2

)(1

)1(3

)(3

)(1

)1(2

)(3

)(2

)1(1

++=

++=

++=

+

+

+

nnn

nnn

nnn

xxx

xxx

xxx

Parametrul q din (6) este în acest caz 5392156,0=q . Eroarea se evaluează conform formulei (7), care în acest caz este

∞

−

∞−≤− )1()()( 17,1 nnn xxzx

Luând )0;0;0()0( =x , se obŃine

)9991238,2;498743,2;9988054,1()10( =x

)9996073,2;4994498,2;9994339,1()11( =x

şi avem 33)11( 101017,1 −− ≈⋅≤− zx .

Exemplul 2. Să rezolvăm cu o eroare mai mică decât 210− sistemul

68,32799,6459,0489,2

17,50224,5724,10351,1

91,5968,518,2714,8

321

321

321

=+−

=++−

=++

xxx

xxx

xxx

49

Matricea sistemului este diagonal dominantă pe linii. Şirul (8) este acum

8065892,40675099,03660832,0

678229,44871316,01259791,0

8751434,66522836,02501721,0

)(2

)(1

)1(3

)(3

)(1

)1(2

)(3

)(2

)1(1

++−=

+−=

+−−=

+

+

+

nnn

nnn

nnn

xxx

xxx

xxx

Evaluarea erorii se face conform formulei

∞

−

∞−≤− )1()()( 25,9 nnn xxzx

Luând )5;3;3()0( =x obŃinem

)7037528,3;3304719,3;6252229,3()11( =x

)7042958,3;330778,3;626055,3()12( =x

)7040118,3;3304516,3;6256242,3()13( =x

III.3. Metoda Gauss-Seidel

Se consideră sistemul ( ) bxBI =− (1)

Dacă ( ){ }mjiijbB,...,1, ∈

= , se notează

=

mm

m

b

bb

R

⋯

⋮⋱⋮

⋯

0

111

şi RBL −= .

Sistemul (1) este echivalent cu cxCI =− )( (2)

unde ( ) RLIC 1−−= , ( ) bLIc 1−−= . Metoda Gauss-Seidel este metoda Jacobi pentru sistemul (2). Se consideră

deci şirul ( ) Nnnx ∈)( , definit prin cCxx nn +=+ )()1( , şi se aproximează cu )(nx

soluŃia sistemului (1) atunci când aceasta există şi este unică.

Şirul ( ) Nnnx ∈)( poate fi descris prin construcŃia echivalentă

bRxLxx nnn ++= ++ )()1()1( (3) care pe componente este

i

m

ij

njij

i

j

njij

ni bxbxbx ++= ∑∑

=

−

=

++ )(1

1

)1()1( (3')

Se observă că specificul acestei metode este că în schema de construcŃie de la teorema Jacobi se intervine cu următoarea modificare: în construcŃia

componentei de ordin i a lui )1( +nx se utilizează componentele lui )1( +nx anterior evaluate.

50

Fie

∑=

=m

jjbq

111 ,

∑∑=

−

=

+=m

ijijj

i

jiji bqbq

1

1

, { }mi ,...,1∈

{ }{ }miqq i ,...,1max ∈=

Teorema 1. Dacă 1<q , atunci sistemul (1) are soluŃie unică z şi pentru

orice mRx ∈)0( , şirul (3) converge către z. Au loc atunci următoarele formule de evaluare a erorii:

∞∞

−

∞−

−≤−

−≤− )0()1()1()()(

11xx

q

qxx

q

qzx

nnnn

Teorema 2. Dacă au loc inegalităŃile

11

≤∑=

m

jijb { }mi ,...,1∈∀

1<∑=

m

ijijb { }mi ,...,1∈∀

(4)

atunci 1<q şi deci are loc teorema 1. În plus, şirul dat de metoda Jacobi este de

asemenea convergent către soluŃia sistemului (1). ObservaŃie. Dacă sistemul de rezolvat este dat sub forma aAx = , şi dacă poate fi adus la forma echivalentă

( ) bxBI =− (5)

unde ADIB 1−−= , ADb 1−= , atunci inegalitătile (4) pentru sistemul (5) sunt:

ii

m

ij

jij aa ≤∑

≠

=1

{ }mi ,...,1∈∀

ii

m

ijij aa <∑

+= 1

{ }mi ,...,1∈∀

(6)

CondiŃiile (6) ne asigură deci că pentru sistemul (5) se poate aplica teorema 1. Atunci

∑=

=m

j

j

a

aq

2 11

11 , ∑∑

+=

−

=

+=m

ij ii

iji

jj

ii

ij

i a

aq

a

aq

1

1

1

, { }mi ,...,1∈

51

Pe componente şirul (3) este

11

1

2

)(

11

1)1(1 a

ax

a

ax

m

j

nj

jn +−= ∑=

+

ii

im

ij

nj

ii

ijnj

ii

ijni a

ax

a

ax

a

ax +−−= ∑∑

+=

+

1

)()()1( , { }mi ,...,2∈

(7)

Exemplul 1. Folosind metoda Gauss-Seidel, să se rezolve sistemul:

5,1610

6102

108210

321

321

321

−=++

−=++−

=+−

xxx

xxx

xxx

SoluŃie. Se verifică pentru început că au loc inegalităŃile (6). Şirul (7) este:

65,11,01,0

6,01,02,0

8,101,02,0

)1(2

)1(1

)1(3

)(3

)1(1

)1(2

)(3

)(2

)1(1

−−−=

−−=

+−=

+++

++

+

nnn

nnn

nnn

xxx

xxx

xxx

Parametrii iq sunt 3,01 =q ; 16,02 =q ; 046,03 =q şi deci 3,0=q .

Pornind de la iteraŃia iniŃială )0;0;0()0( =x , după patru paşi se obŃine

soluŃia cu cinci zecimale exacte (soluŃia exactă este )3;2;5,11( − ). ExerciŃiu. Folosind metoda Gauss-Seidel, să se aproximeze, cu o eroare

mai mică decât 510− , soluŃia sistemului:

11,165,328,181,098,0

48,2281,071,485,073,0

705,2253,198,053,405,1

855,1681,075,002,182,3

4321

4321

4321

4321

=+++

=+++

=+++

=+++

xxxx

xxxx

xxxx

xxxx

IndicaŃie. 7106315,0=q ; soluŃia exactă este )2;5,3;3;5,2(=z .

III.4. Metode de relaxare

Sub acest nume sunt cunoscute unele variaŃiuni ale metodelor Jacobi şi

Gauss-Seidel. Dacă în una din metodele amintite, şirul aproximant ( ) Nnnx ∈)( este

prezentat schematic prin )()()1( nnn xxx ∆+=+ , relaŃie care se citeşte "pentru a

oŃine pe )1( +nx i se adaugă lui )(nx corecŃia )(nx∆ ", atunci într-o metodă de relaxare se supracorectează înmulŃimd corecŃia cu un parametru pozitiv. Se face

deci o construcŃie de forma )()()1( nnn xxx ∆α+=+ .

52

III.4.1. Metoda relaxării simultane

Se consideră sistemul aAx = (1)

unde A este simetrică şi pozitiv definită. Atunci A este inversabilă şi deci sistemul (1) are soluŃie unică. Dacă ( )

{ }mjiijaA,...,1, ∈

= , atunci 0>iia pentru orice

{ }mi ,...,1∈ . Diagonala D a lui A este atunci o matrice inversabilă şi sistemul (1) este echivalent cu

( ) αα =− bxBI (2)

unde ADIB 1−α α−= şi aDb 1−

α α= .

Metoda relaxării simultane este metoda Jacobi pentru sistemul (2). SoluŃia

ecuaŃiei (1) se aproximează deci cu termenii şirului ( ) Nnnx ∈)( , unde

αα+ += bxBx nn )()1( (3)

ConvergenŃa metodei Jacobi pentru (2) este echivalentă cu faptul că ( ) 1<ρ αB şi avem:

PropoziŃie 1. Spectrul matricii AD 1− este format din numere reale strict

pozitive. Dacă ( ) ( )mAD λλλ=− ,...,, 211

S , atunci

( ) ( )mB αλ−αλ−αλ−=α 1,...,1,1 21S .

În continuare, se presupune că spectrul lui AD 1− este ordonat:

mλ≤≤λ≤λ ...21 . Se notează ∑=

=m

iiiiD

xax1

2 . Fie 0≠α , R∈α .

Teorema 1. Dacă A este o matrice simetrică şi pozitiv definită, atunci următoarele afirmaŃii sunt echivalente:

i) Pentru orice mRx ∈)0( şirul (3) converge către soluŃia z a ecuaŃiei (1);

ii) mλ

<α<2

0 .

Dacă are loc ii), atunci evaluarea erorii se face prin

D

n

D

nn

D

n xxq

qxx

q

qzx )0()1()1()()(

11−

−≤−

−≤− −

unde imi

q αλ−=≤≤

1max1

.

ObservaŃia 1. Pe componente şirul (3) este

( )ii

im

ij

j

nj

ii

ijni

ni a

ax

a

axx α+α−α−= ∑

≠

=

+

1

)()()1( 1 (4)

53

ObservaŃia 2. Dacă ⋅ este o normă operatorială pe ( )mRL şi

AD 1

20

−<α< , atunci

mλ<α<

20 şi deci se poate aplica teorema 1.

Dacă notăm ( ) imi

q αλ−=α≤≤

1max1

, o valoare mai mică a lui ( )αq asigură

o convergenŃă mai rapidă. Teorema 2.

( )1

1

1

220min

λ+λ

λ−λ=

λ+λ=

λ<α<α

m

m

mm

qq .

Spunem că mλ+λ1

2 este valoarea optimă a parametrului de relaxare.

III.4.2. Metoda relaxării succesive

Este vorba de o relaxare a metodei Gauss-Seidel, corespunzătoare sistemului (1), modelat, spre exemplu, ca în metoda lui Jacobi pentru matrici diagonal dominante pe linii. Se consideră deci sistemul (1) în care matricea A este simetrică şi pozitiv definită. Dacă ( )

{ }mjiijaA,...,1, ∈

= , se notează

=

− 00

000

0000

1,1

21

mmm aa

aL

⋯

⋮⋮⋱⋮⋮

⋯

⋯

,

=

mma

a

a

D

⋯

⋮⋱⋮⋮

⋯

⋯

00

00

00

22

11

, DLAR −−= .

Pentru 0≠α sistemul (1) este echivalent cu ( ) αα =− cxCI (5)

unde

−

−α

+α

=−

α RDLDC 111

1

. aLDc1

1−

α

+α

= .

SoluŃia z a sistemului (1) se aproximează cu termenii şirului ( ) Nnnx ∈)( ,

unde

αα+ += cxCx nn )()1( (6)

54

Teoremă. Dacă matricea A este simetrică şi pozitiv definită, atunci următoarele afirmaŃii sunt echivalente:

i) Pentru orice mRx ∈)0( , şirul (6) converge către soluŃia z a sistemului (1); ii) 20 <α< . Dacă 20 <α< , atunci evaluarea erorii se face prin

A

n

A

nn

A

n xxq

qxx

q

qzx )0()1()1()()(

11−

−≤−

−≤− − (7)

unde

∑∑= =

=m

i

m

jijijA

xxax1 1

iar

AAx

AxCCq α

≤α ==

1sup .

ObservaŃie. Pe componente, şirul (6) este

( )ii

im

ij

njij

ii

ni

i

j

njij

ii

ni a

axa

axxa

ax

α+

α−α−+

α−= ∑∑

+=

−

=

++

1

)()(1

1

)1()1( 1 (8)

Exemplul 1. Cu notaŃiile din acest paragraf să se afle valoarea optimă a parametrului de relaxare şi folosind atunci metoda relaxării simultane să se

aproximeze soluŃia sistemului cu o eroare mai mică decât 310− . a)

15112

51112

482211

321

21

321

=++−

−=++

=−+

xxx

xxx

xxx

SoluŃie.

( )

+−

=−

22

3321,

11

12,

22

33211ADS .

Metoda relaxării simultane converge dacă 3321

440

−<α< .

Valoarea optimă a parametrului de relaxare este 21

22=α . Pentru acest α

şirul (4) din paragraful 4 este

21

30

21

1

21

2

21

421

102

21

2

21

1

21

421

96

21

4

21

4

21

1

)(3

)(2

)(1

)1(3

)(3

)(2

)(1

)1(2

)(3

)(2

)(1

)1(1

+−−=

−−−−=

++−−=

+

+

+

nnnn

nnnn

nnnn

xxxx

xxxx

xxxx

55

Pornind cu iteraŃia iniŃială )0;0;0()0( =x , se obŃine

)9996218,2;999463,5;9992418,5()7( −=x .

SoluŃia exactă este )3;6;6( −=z . b)

327

4873

7237

321

321

321

−=++−

=++

=−+

xxx

xxx

xxx

.

( )

+−

=−

14

1711,

14

1711,

7

101ADS

Metoda relaxării simultane converge dacă 10

140 <α< . Valoarea optimă a

parametrului de relaxare este 041787,1=α . Pentru această valoare se obŃine cel

mai mic q , care este 4882671,00 =q . Vom lua 04,1=α . Şirul (4) din

paragraful 4 este

7

28,3304,0

7

04,1

7

04,17

92,49

7

04,104,0

7

12,37

88,74

7

04,1

7

12,304,0

)(3

)(2

)(1

)1(3

)(3

)(2

)(1

)1(2

)(3

)(2

)(1

)1(1

−−−=

+−−−=

++−−=

+

+

+

nnnn

nnnn

nnnn

xxxx

xxxx

xxxx

.

Pornind de la iteraŃia iniŃială )0;0;0()0( =x , se obŃine

)000039,4;0005719,4;0004329,8()11( −=x .

SoluŃia exactă este )4;4;8( −=z .

Exemplul 2. Folosind metoda relaxării succesive cu 5,1=α , să se rezolve sistemul:

327

4873

7237

321

321

321

−=++−

=++

=−+

xxx

xxx

xxx

IndicaŃie. Şirul (8) din paragraful 4 este:

8571428,65,07

5,1

7

5,1

285714,107

5,15,0

7

5,4

428571,157

5,1

7

5,45,0

)(3

)1(2

)1(1

)1(3

)(3

)(2

)1(1

)1(2

)(3

)(2

)(1

)1(1

−−−=

+−−−=

++−−=

+++

++

+

nnnn

nnnn

nnnn

xxxx

xxxx

xxxx

56

IV. METODE NUMERICE DE REZOLVARE A SISTEMELOR DE ECUAłII NELINIARE

EcuaŃiile studiate în acest capitol vor fi de forma 0)( =xf sau xxf =)( . Pentru început, va fi studiată posibilitatea rezolvării unor asemenea ecuaŃii în cazul funcŃiilor reale de o variabilă reală.

IV.1. Metoda bisecŃiei

Fie [ ]ba, un interval în R şi [ ] Rbaf →,: o funcŃie continuă.

Presupunem că există şi este unic ( )baz ,∈ , astfel încât 0)( =zf . Atunci

0)()( <⋅ bfaf .

Fie aa =0 , bb =0 şi fie [ ]

+

+∈ 0

0000011 ,

2,

2,, b

babaaba ,

astfel încât ( ) ( ) 011 ≤⋅ bfaf . Dacă ( ) ( ) 011 =⋅ bfaf , atunci rădăcina căutată este

200 ba +. Dacă ( ) ( ) 011 <⋅ bfaf , continuăm construcŃia. Alegem

[ ]

+

+∈ 1

1111122 ,

2,

2,, b

babaaba astfel încât ( ) ( ) 022 ≤⋅ bfaf . Dacă

( ) ( ) 022 =⋅ bfaf , atunci rădăcina căutată este 2

11 ba +. În caz contrar,

( ) ( ) 022 <⋅ bfaf şi aşa mai departe. Să presupunem că procesul este infinit, deci că se construieşte un şir

[ ]( ) Nnnn ba ∈, de intervale, astfel încât ( ) ( ) 0<⋅ nn bfaf şi nnn

abab

2

−=− .

Avem atunci nn bza << pentru orice Nn∈ . Se aproximează z cu na (sau cu

nb ) , alegerea făcându-se în funcŃie de eroarea propusă folosind următoarele

formule de evaluare a erorii:

nn

abaz

20

−≤−≤ ,

nn

abzb

20

−≤−≤ .

Exemplul 1. Să rezolvăm cu o eroare mai mică decât 210− ecuaŃia 0sin2 =− xx .

SoluŃie. Prin metode elementare se constată că ecuaŃia are trei rădăcini:

00 =x ,

ππ

∈ ,21x , 12 xx −= . Considerăm deci funcŃia xxxf −= sin2)( .

57

Avem ( ) 02

<π⋅

πff . Pentru a aproxima rădăcina 1x cu o eroare mai mică

decât 210− va trebui să avem 100

1

2 1<

π+n

, pentru care este suficient să luăm

8=n . Folosind metoda bipartiŃiei, constatăm că [ ]

ππ=

512

309,

512

308, 88 ba şi deci

rădăcina 1x se poate aproxima cu 512

308π sau cu

512

309π, făcând o eroare mai mică

decât 31013,6512

−⋅≈π

.

Exemplul 2. Să aproximăm prin metoda bipartiŃiei, făcând o eroare mai

mică decât 210− , rădăcina din intervalul

ππ4

3,

4 a ecuaŃiei 022 =−− xtgx .

SoluŃie. Se consideră funcŃia Rf →

ππ4

3,

4: , 22)( −−= xtgxxf .

Avem 04

3

4<

π⋅

πff şi prin metode elementare se constată că rădăcina este

unică în intervalul considerat. Pentru ca în metoda bipartiŃiei eroarea să fie mai

mică decât 210− este suficient ca 100

1

28<

⋅

πn

, adică π>+ 1002 3n . Este suficient

să luăm 6=n . După realizarea calculelor avem 1024

3196

π=a ,

1024

3206

π=b .

Rădăcina se poate aproxima deci cu 1024

319π sau cu

1024

320π, făcând o eroare mai

mică decât 3106,31024

−⋅≈π

.

IV.2. Metoda aproximaŃiilor succesive

Metoda este folosită pentru rezolvarea aproximativă a unor ecuaŃii de forma xxf =)( . Aproximarea se face prin termenii unui şir ( ) Nnnx ∈ construit

după formula ( )nn xfx =+1 . Suportul teoretic este dat de principiul contracŃiei pe

care îl vom prezenta pentru funcŃii reale de o variabilă reală. Fie I un interval în R . DefiniŃie. FuncŃia RIf →: se numeşte contracŃie dacă există [ )1,0∈q ,

astfel încât yxqyfxf −≤− )()( , pentru orice Iyx ∈, .

ObservaŃie 1. Orice contracŃie este uniform continuă şi este deci continuă.

58

ObservaŃie 2. Constanta q nu este unică. PropoziŃie. Fie RIf →: o funcŃie derivabilă, pentru care există

[ )1,0∈q , astfel încât qxf ≤′ )( pentru orice Ix∈ . Atunci f este o contracŃie.

Teoremă (principiul contracŃiei). Fie I un interval închis în R şi IIf →: o contracŃie. Atunci există şi este unic Iz∈ , astfel încât zzf =)( .

Pentru orice Ix ∈0 , şirul ( ) Nnnx ∈ , definit prin ( )nn xfx =+1 , converge către z.

Dacă yxqyfxf −≤− )()( pentru orice Iyx ∈, ( [ )1,0∈q ), atunci

011 11xx

q

qxx

q

qzx

n

nnn −−

≤−−

≤− − .

ObservaŃie. Aproximarea lui z prin nx (teorema precedentă) este cu atât

mai eficientă cu cât q este mai mic.

Exemplu. Fie funcŃia ( )323

1)( xxf −= . Să se arate că

⊂

3

2,0

3

2,0f şi că pe acest interval f este o contracŃie. Să se rezolve

ecuaŃia xxf =)( cu o eroare mai mică decât 510− .

SoluŃie. FuncŃia f este strict descrescătoare, continuă, 3

2)0( =f ,

81

46

3

2=

f , deci

⊂

3

2.0

3

2,0f . Apoi,

9

4)( ≤′ xf pentru orice

∈3

2,0x şi deci yxyfxf −≤−

9

4)()( . Conform principiului contracŃiei,

există şi este unic un punct

∈3

2,0z , astfel încât zzf =)( . Fie

3

20 =x şi

( )nn xfx =+1 . La fiecare pas eroarea se evaluează prin 15

4−−<− nnn xxzx .

Avem

6101111 1004,5596077,05960707,0

5

4

5

4 −⋅=−=−≤− xxzx

Se aproximează z cu 5960707,011 =x , făcând o eroare mai mică decât 61004,5 −⋅ .

ObservaŃie. În exemplul precedent s-a modelat ecuaŃia 0233 =−+ xx , astfel încât să se ajungă la forma xxf =)( .

59

ExerciŃiu 1. Fie 0>a şi [ ) Raf →+∞,: ,

+=x

axxf

2

1)( .

Folosind principiul contracŃiei, să se arate că şirul ( ) Nnnx ∈ , definit prin

+=+

nnn x

axx

2

11 , ax >0 , este convergent şi că 1−−≤− nnn xxax .

ExerciŃiul 2. Folosind metoda din exemplul 1, să se aproximeze cu o

eroare mai mică decât 510− rădăcina din intervalul

2

1,0 a ecuaŃiei

0155 =+− xx . IndicaŃie. Cu şirul lui Rolle se arată că ecuaŃia are trei rădăcini reale în intervalele ( )1,−∞− , ( )1,1− , ( )+∞,1 . Cu metoda bipartiŃiei se reduce intervalul

( )1,1− la

2

1,0 . Pe acest interval se modelează ecuaŃia sub forma ( ) xx =+1

5

1 5 .

FuncŃia ( )15

1)( 5 += xxf este atunci o contracŃie pe

2

1,0 .

IV.3. Metoda lui Newton

Cunoscută şi sub numele de metoda tangentei, metoda aproximează rădăcinile unor ecuaŃii de forma 0)( =xf .

Fie [ ] Rba ⊂, .

Teorema 1 (metoda lui Newton). Fie [ ] Rbaf →,: o funcŃie de clasă 2

C , astfel încât 0)(),( ≠′′′ xfxf pentru orice [ ]bax ,∈ şi 0)()( <⋅ bfaf .

Atunci există şi este unic ( )baz ,∈ , astfel încât 0)( =zf . Pentru orice

[ ]bax ,0 ∈ , astfel încât ( ) ( ) 000 >′′⋅ xfxf , şirul ( ) Nnnx ∈ definit prin

( )( )n

nnn xf

xfxx

′−=+1 rămâne în [ ]ba, , converge către z şi

( )

[ ])(inf

,xf

xfzx

bax

nn ′

≤−∈

.

Teorema 2 (metoda lui Newton simplificată). Fie [ ] Rbaf →,: o

funcŃie de clasă 2C , astfel încât 0)(),( ≠′′′ xfxf pentru orice [ ]bax ,∈ şi

0)()( <⋅ bfaf . Atunci există şi este unic ( )baz ,∈ , astfel încât 0)( =zf . Dacă

[ ]bax ,0 ∈ este astfel încât ( ) ( ) 000 >′′⋅ xfxf , atunci şirul ( ) Nnnx ∈ definit prin

( )( )0

1 xf

xfxx nnn ′−=+ rămâne în [ ]ba, , converge către z şi

( )

[ ])(inf

,xf

xfzx

bax

nn ′

≤−∈

.

60

Exemplul 1. Să se rezolve, cu o eroare mai mică decât 610− , ecuaŃia

0733 =−− xx . SoluŃie. Prin metode elementare se constată că ecuaŃia are o singură rădăcină reală, aflată în intervalul [ ]3,2 , unde 0)(),( ≠′′′ xfxf pentru orice x.

Dacă 30 =x , atunci ( ) ( ) 000 >′′ xfxf şi deci, conform teoremei 1, şirul ( ) Nnnx ∈ ,

definit prin ( )( ) 33

722

3

1 −

+=

′−=+

n

n

n

nnn

x

x

xf

xfxx , converge către rădăcina ecuaŃiei

considerate. Deoarece

[ ]9)(inf

3,2=′

∈xf

x, eroarea se evaluează prin

739

1 3 −−≤− nnn xxzx . Se obŃine 4259887,24 =x , iar eroarea este mai mică

decât 8107 −⋅ . Exemplul 2. Să se rezolve ecuaŃia 01 =−− xarctgx . SoluŃie. Folosind pentru început metoda bipartiŃiei, se constată că ecuaŃia

are soluŃie unică aflată în intervalul [ ]3,2 . Avem 2

2

1)(

x

xxf

+=′ ,

( )221

2)(

x

xxf

+=′′ , funcŃii care nu se anulează în intervalul [ ]3,2 . Se poate lua

30 =x . Deoarece [ ] 5

4)(min

3,2=′

∈xf

x, pentru şirul ( ) Nnnx ∈ definit prin

( )( )2

2

1

11

n

nnnnn

x

xxarctgxxx

+−−−=+

sau

( )n

n

n

n xxarctg

xx

11

11

21 −+

+=+ ,

eroarea se evaluează după formula ( )nn xfzx4

5≤− . Se obŃine

1322679,23 =x , ( ) 73 10−=xf şi rădăcina se aproximeazăă cu 3x , făcându-se o

eroare mai mică decât 71025,1 −⋅ . ObservaŃie. În cele două exemple precedente este de remarcat numărul mic de iteraŃii făcute pentru obŃinerea unei aproximări bune, aceasta în comparaŃie cu metoda bipartiŃiei.

61

IV.4. Metoda lui Newton (cazul funcŃiilor de mai multe variabile)

Se consideră pe spaŃiul mR una din normele uzuale, spre exemplu

imixx

≤≤∞=

1max , iar pe spaŃiul ( )mRL norma operatorială indusă AxA

x 1sup

≤= .

Astfel, dacă ( ){ }mjiijaA,...,1, ∈

= , atunci ∑=

≤≤∞=

m

jij

miaA

11max .

Amintim că dacă mm RRDf →⊂: , ( )mfff ,...1= este derivabilă,

atunci

( )

( ) ( )

( ) ( )

∂

∂

∂

∂

∂

∂

∂

∂

=′

001

01

01

1

0

xx

fx

x

f

xx

fx

x

f

xf

m

mm

m

⋯

⋮⋱⋮

⋯

.

Metoda urmăreşte rezolvarea aproximativă a sistemului de ecuaŃii neliniare ( )( )

( ) 0,...,

0,...,

0,...,

1

12

11

=

=

=

mm

m

m

xxf

xxf

xxf

⋯ (1)

Sistemul precedent se scrie 0)( =xf , unde ( )mfff ,...,1= .

PropoziŃiile care urmează produc tehnicile necesare obŃinerii metodei lui Newton în acest cadru.. Amintim că

{ }ryxRyrxB m <−∈=),( ; { }ryxRyrxB m ≤−∈=),( .

PropoziŃia 1. Fie D o mulŃime deschisă şi convexă în mR şi mRDf →:

o funcŃie derivabilă, pentru care există 0>M , astfel încât

yxMyfxf −≤′−′ )()( pentru orice Dyx ∈, . Fie Dw∈ un punct în care

derivata )(wf ′ este inversabilă şi fie ( ) 1)( −′≥α wf . Fie 0>r , astfel încât

DrwB ⊂),( şi 1<αMr . Atunci, pentru orice ),( rwBx∈ , există ( ) 1)( −′ xf şi

( )Mr

xfα−α

≤′ −

1)( 1

.

FuncŃia f este injectivă pe ),( rwB .

62

PropoziŃia 2. Fie mRD ⊂ o mulŃime deschisă şi convexă, fie mRDf →: o funcŃie derivabilă pentru care există 0>M , astfel încât

yxMyfxf −≤′−′ )()( pentru orice Dyx ∈, . Atunci

2

2))(()()( yx

Myxyfyfxf −≤−′−− Dyx ∈∀ , .

Teorema 1 (metoda lui Newton). Fie mRD ⊂ o mulŃime deschisă şi

convexă, mRDf →: o funcŃie derivabilă pentru care există 0>M , astfel încât

yxMyfxf −≤′−′ )()( pentru orice Dyx ∈, . Presupunem că există

Dz∈ , astfel încât 0)( =zf şi că )(zf ′ este inversabilă. Fie ( ) 1)( −′≥α zf ,

( )1,0∈q şi 0>r , astfel încât DrzB ⊂),( şi α+

<Mq

qr

)21(

2. Atunci, pentru

orice ),()0( rzBx ∈ , şirul ( ) Nnnx ∈)( , construit prin

( )( ) ( )( ))(1)()()1( nnnn xfxfxx−+ ′−= ,

rămâne în ),( rzB , converge către z şi

rqzxnn 12)( −≤− .

Teorema 2 (metoda lui Newton simplificată). Cu aceleaşi ipoteze şi notaŃii ca în teorema precedentă, fie 0>r , astfel încât DrzB ⊂),( şi

α+<

Mq

qr

)2(. Atunci, pentru orice ),(,)0( rzBwx ∈ , şirul ( ) Nn

nx ∈)( definit

prin

( ) ( )( ))(1)()1( )( nnn xfwfxx −+ ′−=

rămâne în ),( rzB , converge către z şi

rqzx nn ≤−)( .

ObservaŃie. În prezentarea teoremei 1, prezenŃa unui parametru iniŃial ( )1,0∈q şi alegerea corespunzătoare a razei r, astfel încât

α+<

Mq

qr

)21(

2,

este făcută pentru a pune în evidenŃă superrapiditatea procesului în vecinătatea soluŃiei z. O variantă mai acceptabilă în eventualitatea în care se doreşte verificarea îndeplinirii ipotezelor este următoarea:

63

Teorema 3. Fie mRD ⊂ o mulŃime deschisă şi convexă, mRDf →: o

funcŃie derivabilă pentru care există 0>M , astfel încât

yxMyfxf −≤′−′ )()( pentru orice Dyx ∈, . Presupunem că există

Dz∈ , astfel încât 0)( =zf , şi că există ( ) 1)( −′ zf . Fie ( ) 1)( −′>α zf şi

0>r , astfel încât DrzB ⊂),( şi 3

2<αMr . Atunci, pentru orice

),()0( rzBx ∈ , şirul ( ) Nnnx ∈)( , construit prin

( )( ) ( )( ))(1)()()1( nnnn xfxfxx−+ ′−= ,

rămâne în ),( rzB , converge către z şi

rqzxnn 12)( −≤− ,

unde

( )Mr

Mrq

α−α

=12

.

În metoda Newton simplifiată se poate impune restricŃia 3

1<αMr ,

evaluarea erorii fiind rqzx nn ≤−)( cu precizarea că ( )Mr

Mrq

α−α

=12

3.

Exemplu. Fie sistemul

02020

040202

2

=+−+

=+−+

yxy

xyx

Prin metode grafice, construind în acelaşi sistem de axe graficele curbelor

de ecuaŃii 24020 xxy −−= şi 22020 yyx −−= , constatăm că sistemul are două rădăcini, ambele în primul cadran şi că una dintre rădăcini este localizată în [ ] [ ]2,13,2 × . Pentru a aproxima aceastăă rădăcină considerăm funcŃia

( )2020,4020),( 22 +−++−+= yxyxyxyxf Atunci

−

−=′

2021

1202),(

y

xyxf

( )

−−

−−

δ=′ −

2021

120201),( 1

x

yyxf

unde 39940404),(det +−−=′=δ xyxyyxf . Se poate arăta că sunt îndeplinite condiŃiile din teorema 3, spre exemplu că pe dreptunghiul considerat derivata este în fiecare punct inversabilă. Fie

)1,2()0( =x şi ( )( ) ( )( ))(1)()()1( nnnn xfxfxx−+ ′−= . Atunci

64

( )( )

+=

′−= −

3

5

161

118

287

1)1,2(

3

51,2)1,2( 1)1( fx .

Se obŃine )184,1;324,2()1( =x . Apoi

( )

+=

046,0

105,0

352,151

163,17

270

1184,1;324,2)2(x .

Se găseşte )187,1;331,2()2( =x .

ObservaŃie. ( ) )00003,0;0005,0()2( −=xf .

IV.5. Metoda Newton-Kantorovici

Metoda lui Newton prezentată în paragraful precedent are avantajul de a fi foarte rapid convergentă şi dezavantajul de a localiza procesul iterativ în jurul soluŃiei necunoscute. Acest dezavantaj este înlăturat în varianta următoare a metodei, datorată lui Kantorovici. În acest procedeu stabilitatea metodei în domeniul de definiŃie se face pas cu pas prin intermediul următoarei proprietăŃi: PropoziŃia 1. Cu ipotezele şi notaŃiile din paragraful 1, fie

( ) ( ))()()( 1 xfxfxxg −′−= . Dacă există ),( rwBx∈ astfel încât

),()( rwBxg ∈ , atunci

( )wxgM

xxgMxgxgg

−α−

−α≤−

)(12

)()())((

2

.

Teorema 1 (metoda Newton-Kantorovici). Fie mm RRDf →⊂: , o

funcŃie derivabilă pentru care există 0>M , astfel încât

yxMyfxf −≤′−′ )()( pentru orice Dyx ∈, . Fie ( )( ) 1−′≥α wf ,

( ) ( ))()( 1 wfwf −′≥β . Dacă 2

1<αβM şi DrwB ⊂),( , unde

( )MM

r αβ−−α

= 2111

,

atunci ecuaŃia 0)( =xf are soluŃie unică ),( rwBz∈ . Dacă wx =)0( şi

( )( ) ( )( ))(1)()()1( nnnn xfxfxx−+ ′−= ,

atunci ( )rwBx n ,)( ∈ şi zx n

n=

∞→

)(lim .

65

Teorema 2 (metoda Newton-Kantorovici simplificată). Cu notaŃiile şi

ipotezele din teorema precedentă, există şi este unic ),( rwBz∈ , astfel încât

0)( =zf . Pentru orice ),()0( rwBx ∈ , şirul ( ) Nnnx ∈)( ,

( ) ( )( ))(1)()1( )( nnn xfwfxx −+ ′−= rămâne în ),( rwB , converge către z şi

)0()1()1()()(

11xx

q

qxx

q

qzx

nnnn −

−≤−

−≤− −

unde Mrq α= ( ( )MM

r αβ−−α

= 2111

).

Teorema 3. Fie mRD ⊆ o mulŃime deschisă şi convexă, mRDf →: o

funcŃie derivabilă pentru care există 0>M , astfel încât

( ) ( ) yxMyfxf −≤′−′ pentru orice Dyx ∈, . Fie Dx ∈)0( , astfel încât

( )( )0xf ′ este inversabilă şi fie ( )( )( ) 10 −′≥α xf . Fie ( )( )( ) ( )( )( )010 xfxf

−′≥β şi

presupunem că 9

82 <αβM . Fie ( )M

Mr αβ−−

α= 211

1 şi presupunem că

( ) DrxB ⊂,0 .

Atunci există şi este unic ( )( )rxBz ,0∈ , astfel încât 0)( =zf . Şirul

( ) Nnnx ∈)( , ( )( ) ( )( )( )nnnn xfxfxx

1)()()1( −+ ′−= rămâne în ( )rxB ,)0( , converge

către z şi ( ) rqzxnn 12 −≤− unde

M

Mq

αβ−

αβ−−=

212

211.

IV.6. Metoda aproximaŃiilor succesive (cazul funcŃiilor de mai multe variabile)

Ca şi în paragraful 2, metoda se ocupă de rezolvarea aproximativă a unor

ecuaŃii de forma xxf =)( , unde mm RRDf →⊂: .

DefiniŃie. FuncŃia mm RRDf →⊂: se numeşte contracŃie dacă există

[ )1,0∈q , astfel încât yxqyfxf −≤− )()( pentru orice Dyx ∈, .

Exemplu. Amintim că dacă mRD ⊂ este o mulŃime deschisă şi mRDf →: este derivabilă pe segmentul [ ] Dyx ⊂, , atunci

[ ]yxtfyfxf

yxt

−⋅′≤−∈

)(sup)()(,

Atunci, dacă funcŃia f este derivabilă pe mulŃimea deschisă şi convexă D şi

1)( <≤′ qxf pentru orice Dx∈ , funcŃia f este o contracŃie pe D.

Amintim că se spune că funcŃia f este derivabilă pe mulŃimea închisă A dacă există o mulŃime deschisă D pe care funcŃia f este derivabilă şi DA ⊂ .

66

Dacă funcŃia f este derivabilă, cu derivata continuă pe mulŃimea compactă şi convexă A, atunci

yxtfyfxfAt

−⋅′≤−∈

)(sup)()(

pentru orice Ayx ∈, , iar dacă 1)( <≤′ qtf pentru orice At∈ , atunci funcŃia f

este o contracŃie pe A.

Teorema 1 (principiul contracŃiei). Fie mRA ⊂ o mulŃime închisă şi AAf →: o contracŃie. Atunci există şi este unic Az∈ , astfel încât zzf =)( .

Pentru orice Ax ∈)0( şirul ( ) Nnnx ∈)( definit prin ( ))()1( nn xfx =+ converge

către z. Dacă yxqyfxf −≤− )()( pentru orice Ayx ∈, ( 1<q ), atunci

)0()1()1()()(

11xx

q

qxx

q

qzx

nnnn −

−≤−

−≤− − .

Metoda rezultată, în care z se aproximează cu termenii şirului )(nx , se numeşte metoda aproximaŃiilor succesive. Exemplul 1. Fie [ ] [ ] [ ] [ ]dcbadcbaf ,,,,: ×→× , ( )ψϕ= ,f , o funcŃie

derivabilă pentru care există [ )1,0∈q , astfel încât

qyxy

yxx

≤∂ϕ∂

+∂ϕ∂

),(),(

qyxy

yxx

≤∂ψ∂

+∂ψ∂

),(),(

pentru orice [ ] [ ]dcbayx ,,),( ×∈ . Atunci funcŃia f este o contracŃie pe

[ ] [ ]dcba ,, × ( qyxf ≤′∞

),( [ ] [ ]dcbayx ,,),( ×∈∀ ) şi deci exisŃă şi este unic

( ) [ ] [ ]dcba ,,, ×∈βα , astfel încât ( ) ( )βα=βα ,,f , iar pentru aproximare se poate folosi metoda aproximaŃiilor succesive. Exemplul 2. Se consideră sistemul

( )

( ) yyx

xyx

=+−

=++

3

1

6

12

1

6

1

33

33

.

Fie

×

→

×

10

9,0

10

9,0

10

9,0

10

9,0:f , ( )ψϕ= ,f ,

( )2

1

6

1),( 33 ++=ϕ yxyx , ( )

3

1

6

1),( 33 +−=ψ yxyx ,

67

−=′

22

22),( 22

22

yx

yx

yxf .

Atunci

81,02

),(22

≤+

=′∞

yxyxf .

Rezultă că funcŃia f este o contracŃie pe

×

10

9,0

10

9,0 :

{ } ( )∞∞

−=−−≤− ),(,81,0,max81,0),(),( vuyxvyuxvufyxf .

EcuaŃia ),(),( yxyxf = are atunci soluŃie unică în dreptunghiul considerat şi pentru aproximarea acestei soluŃii se poate folosi metoda

aproximaŃiilor succesive. Fie )0,0()0( =x şi ( ))()1( nn xfx =+ . Eroarea se aproximează prin

∞

−

∞−

−≤− )1()()(

81,01

81,0 nnn xxzx

adică prin

∞

−−≤− )1()()( 24,4 nnn xxzx

Se obŃine

)3512868,0;5323985,0()7( =x ,

)3512597,0;5323761,0()8( =x

şi atunci 3)8( 10−

∞<− zx .

Exemplul 3. Se consideră sistemul

yyx

xyx

=+

+

=+

+

201

202

2

2

FuncŃia

++

++=

201,

202),(

22 yxyxyxf are proprietăŃile:

[ ] [ ] [ ] [ ]2,13,22,13,2: ×→×f ,

=′

1020

120

1

10),(y

x

yxf

10

7

1020

1,

20

1

10max),( ≤

++=′

∞

yxyxf

68

Rezultă că

∞∞−≤− ),(),(

10

7),(),( vuyxvufyxf

şi deci f este o contracŃie pe [ ] [ ]2,13,2 × . Există atunci şi este unic ( )βα= ,z ,

astfel încât [ ] [ ]2,13,2 ×∈z , ),(),( βα=βαf . Pentru aproximarea soluŃiei z se poate folosi metoda aproximaŃiilor succesive. Formula de evaluare a erorii este atunci

∞

−

∞−≤− )1()()(

3

7 nnn xxzx .

V. APROXIMAREA SPECTRULUI UNEI MATRICI

REALE SIMETRICE

V.1. Spectrul unei matrici simetrice

Pe spaŃiul mR se consideră produsul scalar canonic ∑=

=m

iii yxyx

1

, ,

( )mxxx ,...,1= , ( )myyy ,...,1= şi se notează xxx ,2= (norma euclidiană).

Dacă mm RRT →: este un operator liniar, atunci 2

T este norma operatorială

generată de norma euclidiană: 2

122

sup TxTx ≤

= . Dacă ( ){ }mjiijtT,...,1, ∈

= , atunci

( ){ }mjijit ,...,1, ∈

generează operatorul adjunct *T , ce poate fi definit şi prin

proprietatea yTxyTx *,, = , pentru orice mRyx ∈, . Dacă matricea

( ){ }mjiijt ,...,1, ∈

este simetrică, atunci operatorul generat T este autoadjunct:

TyxyTx ,, = mRyx ∈∀ , .

MulŃimea ( ){ }0det =λ−∈λ ITC , adică familia rădăcinilor polinomului

caracteristic se numeşte spectrul lui T şi se notează )(TS . Dacă T este autoadjunct, atunci spectrul este format numai din numere reale. Fie A o matrice reală simetrică. Se ordonează spectrul lui A:

( )mA λλλ= ,...,,)( 21S , mλ≤≤λ≤λ ...21 .

Unul din rezultatele cu importanŃă mai mult calitativă, care stă la baza realizării unor metode de aproximare a spectrului, este:

69

Teorema 1 (E. Fischer). Dacă A este o matrice reală simetrică şi ( )mA λλλ= ,...,,)( 21S , mλ≤≤λ≤λ ...21 , atunci

2

20,

,supinf

x

xAx

xXxjXj

≠∈∈=λ

S

,

unde jS este familia subspaŃiilor de dimensiune j în mR .

Ca o consecinŃă a teoremei precedente are loc un prim fenomen de aproximare: Teorema 2. Fie A, B matrici reale simetrice ale căror spectre, scrise în ordine crescătoare, sunt mλλλ ,...,, 21 , respectiv mµµµ ,...,, 21 . Atunci

2BAii −≤µ−λ , { }mi ,...,1∈∀ . (1)

Dacă ( ){ }mjiijtT,...,1, ∈

= , se notează

∑=

=m

jiijFtT

1,

2 .

Aceasta este o normă pe mulŃimea metricilor mm× , numită norma Frobenius, şi avem

FTT ≤

2 (2)

Din (1) şi (2) rezultă că avem

Fii BA −≤µ−λ (3)

Pentru matricea simetrică A se notează

==

mma

a

diagAD

⋯

⋮⋱⋮

⋯

0

011

.

Să presupunem că elementele de pe diagonala matricii A , scrise în ordine crescătoare, sunt mααα ,...,, 21 şi că spectrul lui A este mλλλ ,...,, 21 . Atunci

Fii DA −≤α−λ , { }mi ,...,1∈∀ (4)

Se notează ||ADAF=− , deci ∑

≠

=ji

ijaA 2|| şi relaŃia (4) se scrie

||Aii ≤α−λ , { }mi ,...,1∈∀ (5)

70

V.2. Metoda rotaŃiilor

Fie ( ){ }mjiijaA,...,1, ∈

= o matrice reală simetrică. Fie

τ

σ

θθ

θ−θ

=

linia

linia

T

1

1cossin

1

1

sincos1

1

⋱

⋯⋯⋯

⋮⋮

⋮⋱⋮

⋮⋮

⋯⋯⋯

⋱

(1)

Matricea T are m linii şi m coloane şi în afara elementelor specificate are numai zerouri. Metoda rotaŃiilor este un procedeu iterativ de aproximare a spectrului

matricii A constând în construcŃia unui şir de matrici ( ) NnnA ∈)( , unde AA =)0( ,

nn

nn TATA )(*)1( =+ , iar nT este de forma (1). Fiecare matrice )(nA are acelaşi

spectru ca şi A , iar şirul se construieşte astfel încât 0lim )( =∞→

||n

nA

în (5), paragraful 1, va rezulta că spectrul lui A poate fi aproximat cu diagonala lui )(nA , scrisă în ordine crescătoare.

Fie ATTB *= , ( ){ }mjiijbB,...,1, ∈

= .

Dacă { }τσ∉ ,i , { }τσ∉ ,j , atunci ijjiij abb == .

Dacă { }τσ∉ ,j , atunci θ+θ== τσσσ sincos jjjj aabb ,

θ+θ−== τσττ cossin jjjj aabb .

( ) ( ) θθ−+θ−θ== σσττσττσστ cossinsincos 22 aaabb .

θ+θθ+θ= ττστσσσσ22 sincossin2cos aaab

θ+θθ−θ= ττστσσττ22 coscossin2sin aaab

Au loc următoarele proprietăŃi: *1 TT =−

( ) ( )BA SS =

trBtrA =

( )2222 2 στστ −+= abAB |||| .

71

Din egalitatea precedentă se observă că dacă 0=στb , atunci |||| AB ≤ şi

aceasta, împreună cu (5) paragraful 1 va permite construcŃia unui şir de matrici în care diagonalele pot aproxima spectrul lui A.

Dacă ττσσ ≠ aa şi ττσσ

στ

−=θ

aa

atg

22 , atunci 0=στb (

4

π<θ ).

Dacă ττσσ = aa şi 4

π=θ , atunci 0=στb .

Teoremă (metoda rotaŃiilor). Fie 3≥m şi A o matrice reală simetrică.

Se consideră şirul de matrici ( ) NnnA ∈)( , unde AA =)0( , n

nn

n TATA )(*)1( =+ , nT

fiind de tipul (1), în care, dacă ( ) { }mji

nij

n aA,...,1,

)()(

∈= , parametrii nσ , nτ ,

nn τ≠σ sunt astfel încât )()( max nij

ji

n

nnaa

≠τσ = , iar parametrul nθ este ales astfel

încât 0)1( =+τσ

n

nna . Fie )()(

1 ,..., nm

n αα elementele de pe diagonala matricii )(nA scrise

în ordine crescătoare şi mλλ ,...,1 spectrul lui A scris, de asemenea, în ordine

crescătoare.

Atunci jnj

nλ=α

∞→

)(lim , { }mj ,...,1∈∀ şi

|||| AqA nnj

nj ≤≤λ−α )()( ,

unde mm

q−

−=2

21 .

ExerciŃii. Folosind metoda rotaŃiilor, să se aproximeze cu o eroare mai

mică decât 410− spectrele matricilor următoare: 1.

=

3210

2321

1232

0123

A

R. ( ) )16228,7;41422,3;837723,0;585787,0(=AS 2.

=

1414104

14181610

10161814

4101414

A

R. ( ) )298254,51;656898,11;7017798,0;3431464,0(=AS

72

3.

=

2210

2221

1222

0122

A

R. ( ) )16228,6;41422,2;162277,0;41423,0( −−=AS

VI. INTERPOLARE

Aproximarea funcŃiilor prin polinoame este legată în cazul funcŃiilor analitice de chiar definiŃia analiticităŃii, iar în cazul general al funcŃiilor continue pe un interval compact, de existenŃa unui şir de polinoame uniform convergent către funcŃie. Interpolarea cu polinoame este un fenomen de aproximare, în general punctual, în care, cunoscând valorile unei funcŃii în anumite puncte, se aproximează acea funcŃie cu un polinom având proprietatea că în acele puncte ia aceleaşi valori ca şi funcŃia. Această coincidenŃă este cerută uneori şi pentru derivatele până la un anumit ordin.

VI.1. ExistenŃa şi unicitatea polinomului de interpolare

Se consideră următorul sistem de date:

(D)

*Nm∈ Rxi ∈ , { }mi ,...,1∈ , puncte distincte două câte două

*Nai ∈ , { }mi ,...,1∈

Rzij ∈ , { }mi ,...,1∈ , { }1,...,1,0 −∈ iaj

Fie ∑=

=m

iian

1

şi ( )∏=

−=ωm

i

iaixxx

1

)( .

DefiniŃie. Se numeşte polinom de interpolare asociat sistemului (D), un polinom [ ]xRP∈ cu proprietăŃile:

1−≤ ngradP ,

( ) ijij zxP =)( , { }mi ,...,1∈ , { }1,...,1,0 −∈ iaj .

Teorema 1.Există şi este unic un polinom de interpolare asociat sistemului (D).

73

Teorema 2 (formula lui Hermite). Polinomul de interpolare asociat sistemului (D) se poate scrie sub forma

( )( )∑ ∑

=

−

=

−−

ω=

n

i

ia

jij

jiijia

i

xrxxzxx

xxP

1

1

0

)()(

)(

unde

( ) ( )( )∑−−

=

−

ω

−=

1

0

)(

)(!

1

!

1)(

jia

k

kii

kia

iij xxx

x

xx

kjxr .

DefiniŃie. Dacă 1...1 === maa , polinomul de interpolare corespunzător

se numeşte polinom de interpolare Lagrange. Dacă în cazul descris în definiŃia precedentă notăm 0ii zz = , atunci

polinomul de interpolare Lagrange este un polinom P, de grad cel mult 1−m şi având proprietatea ( ) ii zxP = , { }mi ,...,1∈ . Se poate uşor constata că are loc

formula lui Lagrange:

∑ ∏=

≠

= −

−=

n

i

n

ij

j ji

ji xx

xxzxP

1 1

)( .

Exemple 1. Fie nxx ,...,1 numere reale distincte două câte două şi *Nk ∈ , 1−≤ nk ,

kii xz =0 , { }ni ,...,1∈ . Atunci polinomul de interpolare asociat acestui sistem de

date este kxxP =)( .

2. Fie 2

11 −=x , 02 =x ,

2

13 =x , 1=ia , { }3,2,1∈i ,

5

41 =z , 12 =z , 03 =z .

Atunci polinomul de interpolare asociat acestui sistem de date este

15

4

5

12)( 2 +−−= xxxP .

3. Fie 2

11 −=x , 02 =x ,

2

13 =x , 2=ia , { }3,2,1∈i ,

5

410 =z ,

25

1611 =z ,

120 =z , 121 =z , 030 =z , 25

1631 −=z . Atunci 1

25

24

25

16)( 24 +−= xxxP .

VI.2. Polinoame de interpolare asociate funcŃiilor

Fie D un domeniu în R, nxx ,...,1 puncte din D nu neapărat distincte două

câte două şi { }myy ,...,1 mulŃimea elementelor distincte două câte două din

nxx ,...,1 . Să presupunem că iy apare de oriai − printre nxx ,...,1 şi nam

ii =∑

=1

.

74

Fie RDf →: o funcŃie derivabilă de 1−ia ori în iy , pentru fiecare

{ }mi ,...,1∈ . DefiniŃie. Se numeşte polinom de interpolare asociat funcŃiei f şi sistemului ( )nxx ,...,1 un polinom P, de grad cel mult 1−n , astfel încât

( ) ( )iji

j yfyP )()( = , { }mi ,...,1∈ , { }1,...,1,0 −∈ iaj .

Se notează ( )xxxfPxP n ;,...,;)( 1= .

Se spune că nxx ,...,1 sunt noduri, iar dacă x este un asemenea nod şi dacă

apare de oria − printre nxx ,...,1 se spune că x are multiplicitatea a. Dacă 1=a ,

nodul x se numeşte simplu, şi se numeşte multiplu dacă 1>a . De exemplu, în );8,8,8,2,1,1;( xfP nodul 1 este dublu, nodul 2 este simplu, iar nodul 8 este triplu.

Exemple: 1. )();;( 11 xfxxfP = .

2. Fie 21 xx ≠ şi ( )112

121

)()()()( xx

xx

xfxfxfxP −

−

−+= . Deoarece

1≤gradP , )()( 11 xfxP = , )()( 22 xfxP = , din definiŃia şi unicitatea

polinomului de interpolare rezultă că );,;()( 21 xxxfPxP = . 3. Dacă f este derivabilă în punctul x, atunci

))(()()( 111 xxxfxfxP −′+= este polinomul de interpolare asociat funcŃiei f şi

nodului dublu 1x , adică );,;()( 11 xxxfPxP = . Se observă pentru acesta că

1≤gradP , )()( 11 xfxP = şi )()( 11 xfxP ′=′ . DefiniŃie. Se numeşte diferenŃă divizată asociată funcŃiei f şi nodurilor

nxx ,...,1 coeficientul lui 1−nx din ( )xxxfP n ;,...,; 1 .

Se notează [ ]nxxf ,...,1 .

ObservaŃie. Atât ( )xxxfP n ;,...,; 1 , cât şi [ ]nxxf ,...,1 nu depind de

ordinea nodurilor. Teorema 1 (formulă de recurenŃă). Dacă 2≥n şi nxx ≠1 , atunci

( ) ( ) ( )n

nn

nnn xx

xxxxxfP

xx

xxxxxfPxxxfP

−

−+

−

−= −

111

1

121 ;,...,;;,...,;;,...,; .

Corolar 1. Dacă 21 xx ≠ , atunci

( ) ( ) ( )21

21

12

1221 ;,;

xx

xxxf

xx

xxxfxxxfP

−

−+

−

−=

iar P se numeşte polinom de interpolare liniară.

75

Corolar 2. Dacă 2≥n şi nxx ≠1 , atunci

[ ] [ ] [ ]1

1121

,...,,...,,...,

xx

xxfxxfxxf

n

nnn −

−= − .

În particular

[ ] ( ) ( )12

1221 , xx

xfxfxxf

−

−= .

PropoziŃie 1. Dacă nxxx === ...21 , atunci

[ ] ( )1)1(11 )!1(

1,..., xf

nxxf n

orin

−

−−

=�����

.

Teorema 2 (formulă de recurenŃă). Dacă 2≥n , atunci

( ) ( ) [ ]( ) ( )111111 ...,...,;,...,;;,...,; −− −−+= nnnn xxxxxxfxxxfPxxxfP .

Mai general

( ) ( ) [ ]i

nniin xx

xxxfxxxxxfPxxxfP

−ω

+= +−

)(,...,;,...,,,...,;;,...,; 11111 .

Teorema 3 (formula lui Newton cu diferenŃe divizate).

( ) [ ]( ) ( )∑=

−−−=n

iiin xxxxxxfxxxfP

11111 ...,...,;,...,; .

VI.3. Evaluarea erorii

Fie ( ) ( )nxxxxx −−=ω ...)( 1 .

PropoziŃia 1. Dacă funcŃia f este cel puŃin de oriai − derivabilă în

fiecare nod de multiplicitate ia , atunci pentru orice Dx∈ avem

( ) [ ] )(,,...,;,...,;)( 11 xxxxfxxxfPxf nn ω+= .

PropoziŃia 2. Fie RDf →: o funcŃie de clasă nC şi nxx ,...,1 puncte

din D. Atunci, pentru orice Dx∈ , există D∈ξ , astfel încât

( ) ( ) ( )xfn

xxxfPxf nn ωξ+= )(

1 !

1;,...,;)( .

ObservaŃie. Punctul ξ din teorema precedentă aparŃine intervalului

{ } { }[ ]xxxxxx nn ,,...,max,,,...,min 11 .

Corolar (formulă de evaluare a erorii). Dacă f este de clasă nC pe

intervalul D, atunci

( ) )(sup)(!

1;,...,;)( )(

1 xfxn

xxxfPxf n

Dxn

∈ω≤− .

76

PropoziŃia 3. Dacă 2≥n şi dacă funcŃia f este de clasă 1−nC pe

intervalul D, atunci există D∈ξ , astfel încât

[ ] ( )ξ−

= − )1(1 )!1(

1,..., n

n fn

xxf .

Teorema 4 (continuitatea diferenŃelor divizate). Dacă 2≥n , iar funcŃia

f este de clasă 1−nC pe intervalul D, atunci diferenŃa divizată [ ]nxxf ,...,1 , ca

funcŃie de n variabile, este continuă pe nD . Teorema 5 (derivabilitatea diferenŃelor divizate). Dacă funcŃia f este de

clasă in+C , atunci

[ ] [ ],...,,,,...,!,,...,1

11 �����orii

nn xxxxxfixxxfx

+

=′∂

∂′.

Algoritmul lui Aitkien Fie nxx ,...,0 puncte distincte două câte două din D şi RDf →: . Fie

( )kk xfxP =)(0 , nk ,...,1= şi

( ) ( )dk

kddddkdk xx

xPxxxPxxxP

−

−−−=+

)()()(1, , { }ndk ,...,1+∈ .

Atunci ( )xxxfPxP nnn ;,...,;)( 1= .

Exemplul 1. Să aproximăn 4

sinπ prin interpolare prin

−−2

1;3,2,1,0,1,2;fP , unde

2sin)(

xxf

π= .

Pentru controlul rezultatelor intermediare din algoritmul lui Aitkien se

poate utiliza tabloul următor, în care 2

1=x şi se scriu

2

1kiP .

ix 0kP

1kP 2kP 3kP 4kP 55P xxk −

-2 0 -2,5 -1 -1 -2,5 -1,5 0 0 0 1,25 -0,5 1 1 0,8(3) 0 0,625 0,5 2 0 0 -1,25 0,625 0,625 1,5 3 -1 -0,5 -1,75 0,75 0,59375 0,671875 2,5

Atunci 671875,04

sin ≈π

.

77

Exemplul 2. Fie funcŃia 21

1)(

xxf

+= şi nodurile duble

2

121 −== xx ,

043 == xx , 2

165 == xx . Cu ajutorul formulei lui Newton cu diferenŃe divizate

să se calculeze polinomul de interpolare. Să se verifice evaluarea erorii în 4

1=x .

SoluŃie. Calculul diferenŃelor divizate este prezentat în următorul tablou:

2

1−

2

1− 0 0

2

1

2

1 ix

5

4

5

4 1 1

5

4

5

4 ( )ixf

25

16

25

10 0

25

10−

25

16− [ ]1, +ii xxf

25

12−

25

20−

25

20−

25

12− [ ]21 ,, ++ iii xxxf

25

16− 0

25

16 [ ]321 ,,, +++ iiii xxxxf

25

16

25

16 [ ]4321 ,,,, ++++ iiiii xxxxxf

0 [ ]654321 ,,,,, xxxxxxf

Atunci

( ) 2222

61 2

1

25

16

2

1

25

16

2

1

25

12

2

1

25

16

5

4;,...,; xxxxxxxxxfP

++

+−

+−

++= ,

deci

( ) 125

24

25

16;,...,; 24

61 +−= xxxxxfP .

Avem 9411764,04

1=

f , iar aproximarea se face cu 9425,0

4

1=

P . Formula

de evaluare a erorii dă majorarea cu

(6)

1 1,

2 2

1 1 9sup ( ) 0,00219726

6! 2 4096x

f x ω ∈ −

= =

şi evaluările propuse verifică relaŃia de evaluare a restului.

78

VI.4. Polinoame de interpolare cu noduri simple echidistante

Fie D un interval în R, 0>h şi RDf →: . Notăm

RDhDfh →−∆ ∩: ,

( ) )()()( xfhxfxfh −+=∆ .

Operatorul h∆ , cât şi numărul )()( xfhxf −+ se numesc diferenŃă

nedivizată ascendentă de ordinul întâi. Dacă { } Dnhxhxx ⊂++ ,...,, se defineşte

( ) ( ) ( ) )()()( 11 xfhxfxf nh

nh

nh

−− ∆−+∆=∆

adică 1−∆∆=∆ nhh

nh . Operatorul n

h∆ , cât şi numărul ( ) )(xfnh∆ se numesc

diferenŃă nedivizată ascendentă de ordinul n. Prin convenŃie, ff =∆0 .

PropoziŃia 1. Fie RDf →: , 0>h şi { } Dnhxhxx ⊂++ ,...,, . Atunci

( ) ),...,,(!)( nhxhxxfhnxf nnh ++=∆ .

Corolar 1. Dacă f este de clasă nC pe intervalul [ ]nhxx +, , atunci

există [ ]nhxx +∈ξ , , astfel încât

( ) ( )ξ=∆ )()( nnnh fhxf .

Corolar 2. Dacă f este de clasă nC pe intervalul [ ]nhxx +, , atunci

( ))(

)(lim )(

0xf

h

xf n

n

nh

h=

∆→

.

Cu ajutorul diferenŃelor nedivizate se obŃin formule cu o anumită simetrie, cu o anumită independenŃă faŃă de intervalul în care se face interpolarea. Fie Rx ∈0 , 0>h şi ihxxi += 0 , Zi∈ . Fie { } Dxxx n ⊂,...,, 10 şi

RDf →: . Pentru Dx∈ , fie t astfel încât thxx += 0 . Avem atunci

( ) ( )( )∑=

∆=+n

i

ih

itn xfCthxxxxfP

00010 ;,...,,; ,

unde !

)1)...(1(

i

itttC i

t

+−−= , 10 =tC .

În această prezentare polinomul de interpolare se numeşte polinomul lui Newton de interpolare ascendentă. Evaluarea erorii, pentru cazul în care funcŃia f

este de clasă 1+nC şi în raport cu schimbarea de variabilă folosită este:

( ) ( ) )(sup))...(1()!1(

;,...,,; )1(1

0100 xfntttn

hthxxxxfPthxf n

Dx

n

n+

∈

+

−−+

≤+−+ .

Formula de interpolare precedentă se dovedeşte a fi mai bună (în sensul unei minimizări a restului) dacă punctul în care se face aproximarea se află în intervalul [ ]hxx +00 , .

79

Se notează ( ) )()()( hxfxfxfh −−=∇ şi se numeşte diferenŃă

nedivizată descendentă. Ca mai sus , ( ) ( ) ( ) )()()( 11 hxfxfxf nh

nh

nh −∇−∇=∇ −−

Are loc:

( ) ( ) ( )( )∑=

−− ∇−=−n

i

ih

is

in xfCshxxxxfP

00010 1;,...,,;

numită formula lui Newton de interpolare descendentă. Se preferă în cazul în care punctul în care se face aproximarea aparŃine intervalului [ ]00 , xhx − .

În formula următoare se notează ( )( ) ki

kih fxf ∆=∆ , Zk ∈ . Are loc:

( )

( ) ( )

( )

( ) ( )( )( )

( ) ( )( )( ))!2(

1...1

)!12(

)1(2...1

...!4

)2(1

!3

1

!2

)1(

,,...,2,2,,,;

2222

22222

112

2

24

2

13

12

00

0000000

n

ntntttf

n

ntntttf

tttf

ttf

ttftfxf

nhxnhxhxhxhxhxxfP

nn

nn

−−−−∆+

+−

−−−−−∆+

++−−

∆+

+−

∆+−

∆+∆+=

=−+−+−+

−

+−−

−

−−

numită formula lui Gauss ascendentă.

Exemplul 1. Sunt cunoscute valorile funcŃiei ∫ −

π=φ

x t dtex0

22)( în

punctele 10

1i

+ , { }10,...,1,0∈i . Folosind formula de interpolare Newton

ascendentă cu 4 noduri să se aproximeze )43,1(φ . Valorile funcŃiei cât şi ale

diferenŃelor nedivizate sunt prezentate în tabelul următor ( 1,0=h ).

x )(xφ φ∆ h φ∆2h φ∆3

h φ∆4h

1 0,8427 0,0375 -0,0074 0,001 0 1,1 0,8802 0,0301 -0,0064 0,001 -0,0001 1,2 0,9103 0,0237 -0,0054 0,0009 0 1,3 0,9340 0,0183 -0,0045 0,0009 0 1,4 0,9523 0,0138 -0,0036 0,0009 -0,0004 1,5 0,9661 0,0102 -0,0027 0,0005 0,0001 1,6 0,9763 0,0075 -0,0022 0,0006 -0,0002 1,7 0,9838 0,0053 -0,0016 0,0004 1,8 0,9891 0,0037 -0,0012 1,9 0,9928 0,0025 2 0,9953

80

Conform notaŃiilor precedente 43,1=x , se alege 4,10 =x . Atunci

3,00 =−

=h

xxt şi deci:

( ) ( ) ( )( ) ( )( )( )( ) ( )( )0

440

33

022

01

03210 43,1;,,,;

xCxC

xCxCxxxxxP

htht

htht

φ∆+φ∆+

+φ∆+φ∆+φ=φ,

unde:

( ) 9523,00 =φ x ; ( )( ) 0138,00 =φ∆ xh ; ( )( ) 0036,002 −=φ∆ xh ;

( )( ) 0009,003 =φ∆ xh ; ( )( ) 0004,00

4 −=φ∆ xh .

3,01 == tCt ; 105,02 −=tC ; 0595,03 =tC ; 0401,04 −=tC

şi se obŃine ( ) 95688,043,0;,,,; 3210 ≈φ xxxxP . Se aproximează deci

( ) 95688,043,1 ≈φ . Se poate arăta că eroarea este mai mică decât 410− , deci primele 3 zecimale sunt exacte. Exemplul 2. Folosind metoda şi tabelul din exerciŃiul precedent, să se aproximeze cu formula lui Newton ascendentă cu patru noduri ( )53,1φ .

Se va lua 5,10 =x şi se obŃine ( ) 9694737,053,1 ≈φ eroarea teoretică

fiind mai mică decât 5102,1 −⋅ .

VI.5. Interpolare cu funcŃii spline cubice

Fie [ ] Rbaf →,: şi nodurile bxxxa n =<<<= +121 ... .

DefiniŃie. Se numeşte funcŃie spline cubică asociată funcŃiei f şi nodurilor

11 ,..., +nxx , o funŃie de clasă 2C , [ ] Rbas →,: , astfel încât ( ) ( )ii xfxs =

{ }1,...,1 +∈∀ ni şi restricŃia funcŃiei s la fiecare interval [ ]1, +ii xx este

polinomială de grad cel mult 3. Teorema 1. Există şi este unică o funcŃie spline cubică asociată funcŃiei f şi nodurilor 11 ,..., +nxx , astfel încât 0)()( =′′=′′ bsas .

Să notăm iii xxh −= +1 , ( )ii xsa ′′= , { }1,...,1 +∈ ni . Atunci

011 == +naa . Se arată că pentru [ ]1, +∈ ii xxx avem:

( ) ( )

( ) ( )i

ii

ii

i

ii

ii

i

ii

i

ii

h

xxa

hxf

h

xxa

hxf

h

xxa

h

xxaxs

−

−+

−

−+

+−

+−

=

+++

++

1

2

11

2

3

1

31

66

66)(

Se arată că necunoscutele rămase naa ,...,2 sunt soluŃiile sistemului

bAx = , unde ( )naax ,...,2= ,

81

+

+

+

=

−−

360000

000636

000063

11

3322

221

nnn hhh

hhhh

hhh

A

⋯

⋮⋮⋱⋮⋮⋮⋮

⋯

⋯

( )11 ,..., −= nbbb , ( ) ( ) ( )21

11

1111+

++

+

+

+−= i

ii

iii

ii xf

hxf

hhxf

hb .

Matricea A este diagonal dominantă pe linii şi deci sistemul bAx = are soluŃie unică, iar aceasta se poate aproxima cu metoda lui Jacobi. Pe fiecare interval [ ]1, +ii xx evaluarea erorii se face cu formulele stabilite

la interpolare cu polinoame. Fie

( ) ( ) { }{ }1,...,1,2],[ +∈=∈= nixfxgg iibaCX

şi

R→φ X: , ( )∫ ′′=φb

adxxgg 2)()( .

Are loc următoarea caracterizare variaŃională: Teorema 2. Dacă X∈s este funcŃia spline cubică din teorema 1, atunci

( )gsg

φ=φ∈X

min)( . Reciproc, dacă X∈u şi ( )xug

φ=φ∈X

min)( , atunci u este

funcŃia spline cubică din teorema 1.

VII. FORMULE DE CUADRATURA

VII.1. ConvergenŃa punctuală

Problema aproximării integralei Riemann a unei funcŃii continue pe un interval compact [ ]ba, presupune, în partea calitativă a fenomenului, unele consideraŃii de analiză funcŃională. Se consideră mulŃimea ],[ baC a funcŃiilor reale continue pe [ ]ba, ,

organizat ca spaŃiu normat cu norma )(max],[

xffbax∈

= . Integrala Riemann

∫=b

adxxffI )()( este o funcŃională liniară şi continuă pe ],[ baC , iar aproximarea

ei se face punctual cu funcŃionale de tipul ( )∑=

α=n

iii xffJ

1

)( , unde

{ } [ ]baxx n ,,...,1 ⊂ sunt puncte distincte două câte două, iar { } Rn ⊂αα ,...,1 .

82

AplicaŃia J este funcŃională liniară şi continuă pe ],[ baC care, prin abuz, se va numi

în acest context "formulă de cuadratură", căci se va proceda la aproximarea

)()( fJdxxfb

a≈∫ .

Pentru stabilirea convergenŃei punctuale a unui şir de formule de cuadratură către integrală este util următorul rezultat:

Teorema 1. Fie { })()(1 ,..., n

nkn xx un sistem de puncte distincte două câte

două din intervalul [ ]ba, , { } Rn

nkn ⊂αα )()(

1 ,..., şi ( )∑=

α=nk

i

ni

nin xffJ

1

)()()( .

AfirmaŃiile următoare sunt echivalente:

i) ∫=∞→

b

ann

dxxffJ )()(lim pentru orice ],[ baf C∈ ;

ii) Există 0>M , astfel încât Mnk

i

ni ≤α∑

=1

)( , pentru orice Nn∈ şi

( ) ∫=∞→

b

a

kkn

ndtttJlim , pentru orice Nk ∈ .

Cu notaŃiile din teorema precedentă are loc:

Corolar. Dacă 0)( ≥α ni pentru orice { }nki ,...,1∈ şi orice Nn∈ , atunci

∫=∞→

b

ann

dxxffJ )()(lim pentru orice ],[ baf C∈ dacă şi numai dacă

( ) ∫=∞→

b

a

kkn

ndtttJlim pentru orice Nk ∈ .

VII.2. Formulele Newton-Côtes

Fie *Nn∈ , n

abh

−= , ihaxi += , { }ni ,...,0∈ . Prin integrarea

polinomului de interpolare ( )xxxfP n ;,...,; 0 se obŃine formula

( )∫=b

a nn dxxxxfPfJ ;,...,;)( 0 . Are loc

( ) ( )∑=

−=n

ii

nin xfHabfJ

0

)()( (1)

FuncŃionala nJ se numeşte "formula de cuadratură Newton-Côtes".

CoeficienŃii )(niH au proprietăŃile:

10

)( =∑=

n

i

niH (2)

)()( nin

ni HH −= (3)

Evaluarea erorii se obŃine folosind rezultatele de la interpolare.

83

PropoziŃie. Dacă 1],[

+∈ nbaf C , atunci

( ) ∫∑∫ −−+

≤−− +

∈

+

=

b

a

n

bax

nn

ii

ni

b

adtntttxf

n

hxfHabdxxf ))...(1()(sup

)!1()()( )(

],[

2

0

)( .

Pentru 1=n avem 2

1)1(1

)1(0 == HH , iar formula ce se obŃine

( ))()(2

)( bfafab

fT +−

=

se numeşte "formula de cuadratură a trapezului".

Dacă 2],[ baf C∈ , evaluarea erorii rezultă din propoziŃia precedentă:

( ) )(sup12

)()()(

2)(

],[

3

xfab

bfafab

dxxfbax

b

a′′−

≤+−

−∈

∫ .

Pentru 2=n avem 6

1)2(2

)2(0 == HH ,

6

4)2(1 =H , iar formula care se

obŃine:

+

++

−= )(

24)(

6)( bf

bafaf

abfS

poartă numele de "formula de cuadratura a lui Simpson".

Dacă 4],[ baf C∈ , formula de evaluare a erorii este:

)(sup2880

)()(

2)(

6)( )4(

],[

5

xfab

bfba

fafab

dxxfbax

b

a ∈

−≤

+

++

−−∫ .

VII.3. Formule sumate

Pentru 1>n , fie n

abh

−= , ihaxi += , { }ni ,...,1,0∈ . Prin sumarea

formulelor trapezului corespunzătoare intervalelor [ ]1, +ii xx se obŃine, pentru

],[ baf C∈ ,

( ) ( )( )∑−

=++

−=

1

012

)(n

iiin xfxf

n

abfT

numită formula sumată a trapezului.

Dacă 2],[ baf C∈ , are loc următoarea formulă de evaluare a erorii:

)(sup12

)()()(

],[2

3

xfn

abfTdxxf

baxn

b

a′′−

≤−∈

∫ .

84

Ca o consecinŃă a formulei precedente şi a corolarului de la teorema 1, paragraful 1, rezultă că:

∫=∞→

b

ann

dxxffT )()(lim , ],[ baf C∈∀ .

Dacă pentru 1>n , Nn∈ , se notează n

abh

−= , ihaxi += ,

( )ni 2,...,1,0∈ , prin sumarea formulelor lui Simpson corespunzătoare intervalelor

[ ]222 , +ii xx se obŃine

( ) ( ) ( ) ( )( )∑−

=++ ++

−=

1

022122 4

6

n

iiiim xfxfxf

n

abfS

numită formula sumată a lui Simpson.

Dacă [ ]baf ,4C∈ , are loc următoarea formulă de evaluare a erorii:

( )[ ]

)(sup2880

)()( )4(

,4

5

xfn

abfSdxxf

baxm

b

a ∈

−≤−∫ .

Ca o consecinŃă a formulei precedente şi a corolarului de la teorema 1 rezultă că:

∫=∞→

b

a

nn

dxxffS )()(lim , [ ]baf ,C∈∀ .

Exemple.

1. Aproximarea integralei ∫ −1

0

2dxe x cu formula sumată a trapezului se face cu

următoarele evaluări: 7313702,0)(2 =fT ; 742984,0)(4 =fT ;

7458656,0)(8 =fT ; 7462,0)(10 =fT . În cazul 10=n pentru evaluarea

erorii constatăm că ( ) 22 122)( xexxf −−=′′ , ( ) 2228)( xexxxf −−=′′′ . Din

studiul variaŃiei rezultă că 2)( ≤′′ xf . Din (1) rezultă că eroarea este cel mult

002,010012

2<

⋅.

2. Să se aproximeze cu formula sumată a lui Simpson pentru 4=n , integrala

∫1

0

2dxe x . Se obŃine 4627231,1)(4 =fS .

85

VII.4. Formulele de cuadratură ale lui Gauss

Fie nxx ,...,1 puncte distincte două câte două în intervalul [ ]ba, şi formula

de cuadratură

( )∑=

α=n

iii xffJ

1

)( , ],[ baf C∈ (1)

DefiniŃie. Formula J se numeşte exactă pe mulŃimea ],[ baA C⊂ dacă

∫=b

adxxffJ )()( pentru orice Af ∈ .

ObservaŃie. Formula trapezului este exactă pentru orice funcŃie polinomială de grad cel mult 1, iar formula lui Simpson este exactă pentru orice funcŃie polinomială de grad cel mult 2. Se notează cu kP spaŃiul polinoamelor de grad cel mult k.

PropoziŃia 1. Dacă funcŃionala (1) este exactă pe spaŃiul mP , atunci

12 −≤ nm .

ObservaŃie. Dacă funcŃionala (1) este exactă pe 12 −nP şi notăm

( )∏=

−=n

iixxxq

1

)( , atunci

0)()( =∫b

adxxpxq 1−∈∀ np P (2)

Un polinom de grad n se numeşte monic dacă coeficientul lui nx este 1. Teorema 1. Există şi este unic un polinom monic cu proprietatea (2). El este dat de

( ) )()()(

)!2(

!)(

nnnn bxax

n

nx −−=γ

( nγ se numeşte polinomul lui Legendre).

PropoziŃia 2. Polinomul nγ are n rădăcini reale distincte aflate în ( )ba, .

Teorema 2. Fie { })()(1 ,..., n

nn xx puncte distincte două câte două aflate în

intervalul ( )ba, şi { } Rnn

n ⊂αα )()(1 ,..., . Fie

( )∑=

α=σn

i

ni

nin xff

1

)()()( , ],[ baf C∈

FuncŃionala n

σ este exactă pe 12 −nP dacă şi numai dacă )()(1 ,..., n

nn xx sunt

rădăcinile polinomului Legendre nγ , iar ∫ ∏≠

= −

−=α

b

a

n

ij

jnj

ni

njn

i dxxx

xx

1)()(

)()( .

(funcŃionala nσ se numeşte formula de cuadratură a lui Gauss).

86

PropoziŃia 3. Pentru orice ],[ baf C∈ , ∫=σ∞→

b

ann

dxxff )()(lim .

Teorema 3 (evaluarea erorii). Dacă nbaf 2],[C∈ , atunci

( )( )

)(sup12

)(

)!2(

!)()( )2(

],[

12

3

4

xfn

ab

n

ndxxff n

bax

nb

an∈

+

+−

⋅≤− ∫σ .

Pentru calculul prin recurenŃă al polinoamelor Legendre are loc:

PropoziŃia 4. 1)(0 =γ x , )(2

1)(1 baxx +−=γ ,

)()()()( 11 xxxxx nnnnnn −+ γβ−γα−γ=γ , 1≥n

unde

∫∫

γ

γ=α

b

a n

b

a n

n

dxx

dxxx

)(

)(

2

2

, 0≥n ,

∫∫

−

−

γ

γγ=β

b

a n

b

a nn

n

dxx

dxxxx

)(

)()(

21

1, 1≥n .

De exemplu, pe intervalul [ ]1,1− avem 1)(0 =γ x , xx =γ )(1 ,

3

1)( 2

2 −=γ xx , 5

3)( 3

3 −=γ xx , 35

3

7

6)( 24

4 ++=γ xxx ,

xxxx63

15

9

10)( 35

5 +−=γ .

Teorema 4. Pe un interval de forma [ ]aa,− , funcŃia n2γ este pară, iar

12 +γ n este impară.

ObservaŃie. Dacă )()(1 ,..., n

nn xx sunt rădăcinile lui nγ corespunzătoare

intervalului [ ]1,1− , atunci rădăcinile corespunzătoare în cazul intervalului [ ]ba,

sunt )(

22n

ixabba −

++

. Dacă )()(1 ,..., n

nn αα sunt coeficienŃii din nσ pe intervalul

[ ]1,1− , atunci coeficienŃii corespunzători intervalului [ ]ba, sunt )(

2ni

abα

−.

De exemplu, pe intervalul [ ]1,1− avem

++

−=σ

5

3

9

5)0(

9

8

5

3

9

5)(3 ffff

iar formula sumată corespunzătoare acestora este 1

( ) 1 1 13

0

3 3( ) 5 8 5

18 2 2 5 2 2 2 5

nn i i i i i i

i

x x x x x xb a b a b af f f f

n n nσ

−+ + +

=

+ + +− − − = − + + + ∑

87

Pentru 4=n , pe intervalul [ ]1,1− , rădăcinile polinomului Legendre sunt

861136,01 −=x ; 339981,02 −=x , 23 xx −= ; 14 xx −= . CoeficienŃii din

formula lui Gauss sunt 347854,041 =α=α ; 652145,032 =α=α . Eroarea se

majorează cu )(sup1088,2 )8(

]1,1[

7 xfx −∈

−⋅ .

Pentru 5=n , pe intervalul [ ]1,1− , rădăcinile polinomului Legendre sunt

906179.01 −=x ; 538469,02 −=x ; 03 =x ; 24 xx −= ; 15 xx −= . CoeficienŃii

din formula lui Gauss sunt 236926,051 =α=α , 478628,042 =α=α ,

568888,03 =α . Eroarea se majorează cu )(sup1008,8 )10(

]1,1[

10 xfx −∈

−⋅ .

VIII. METODE NUMERICE PENTRU ECUATII DIFERENTIALE

Fie RRBAu →⊂× 2: o funcŃie continuă, [ ] Aba ⊂, şi problema Cauchy

( )( ) [ ]battxtutx

ax

,,)(,)(0

∈=′

α= (1)

Presupunem că problema precedentă are soluŃie unică, ceea ce se întâmplă,

de exemplu, dacă există 0>L , astfel încât vzLvtuztu −≤− ),(),( , pentru

orice [ ]bat ,∈ şi orice Bvz ∈, . Vom spune în continuare că u este de clasă nC ,

ceea ce va permite aproximarea soluŃiei x cu polinomul său Taylor de ordinul n. Notăm

),(),(),(

),(),(

11

0

yty

uyt

t

uytu

ytuytu

jj

j ∂

∂+

∂

∂=

=

−−

Atunci polinomul Taylor de grad n, asociat funcŃiei x în punctul 0s , este

( )( )∑

=

− −+=n

j

jjsxn st

j

sxsusxtT

10

0010)0,,( !

)(,)()( . (2)

Aproximarea soluŃiei x prin polinomul Taylor ),,( axnT este posibilă

deoarece în (2) sunt necesare doar informaŃiile din (1), dar metoda are mai mult importanŃă teoretică. O folosire mai bună a comportării soluŃiei x şi în alte puncte decât a este conŃinută într-o metodă derivată din cea a aproximării cu polinomul Taylor.

88

VIII.1. Metoda lui Taylor

Fie btttta mm =<<<<= +110 ... o diviziune δ a intervalului [ ]ba, .

Fie 00 α=x şi fie Rbay →],[: o funcŃie construită astfel:

∑=

− −+=n

j

jj ttj

xtuxty

10

0010 )(

!

),()( , [ ]10 , ttt∈ .

Fie ( )11 tyx = , ∑=

− −+=n

j

jj ttj

xtuxx

101

00101 )(

!

),(.

Presupunând că am construit [ ] Rtty k →,: 0 , reŃinem ( )kk tyx = şi

continuăm prin

∑=

− −+=n

j

jk

kkjk tt

j

xtuxty

1

1 )(!

),()( , [ ]1, +∈ kk ttt .

Luăm ( )11 ++ = kk tyx , adică ∑=

+−

+ −+=n

j

jkk

kkjkk tt

j

xtuxx

11

11 )(

!

),(.

Definim Rz →δ: , ( ) kk xtz = , iar aproximarea soluŃiei x la diviziunea

δ cu funcŃia z poartă numele de metoda lui Taylor. FuncŃia z este determinată deci de soluŃiile următoarei ecuaŃii:

( )

α=

−=−

− −+

=

−

+

+ ∑

00

11

1

1

1

1

!

),(

x

ttj

xtu

tt

xx jkk

n

j

kkj

kk

kk

(3)

EcuaŃiile precedente se numesc ecuaŃii cu diferenŃe. Pentru 1=n se obŃine metoda lui Euler. Prin urmare, restricŃia soluŃiei c la diviziunea δ se aproximează cu soluŃia z a următoarei ecuaŃii cu diferenŃe

∈=−

−

α=

+

+ },...,0{),,(1

1

00

mkxtutt

xx

x

kkkk

kk

VIII.2. Metoda Euler-Cauchy

Să presupunem că diviziunea δ este echidistantă, deci că htt kk =−+1 .

Metoda Euler-Cauchy constă din aproximarea soluŃiei x la diviziunea δ cu soluŃiile z ale următoarei ecuaŃii cu diferenŃe:

( )( )( )

++=−

α=

++

kkkkkkkk xthuxtuxtu

h

xx

x

,,),(2

11

1

00

.

89

VIII.3. Metoda Runge-Kutta

SoluŃia ecuaŃiei (1) se aproximează cu soluŃia ecuaŃiei cu diferenŃe:

( )

+++=−

α=

+ ),(),(),(2),(6

14321

1

00

kkkkkkkkkk xtvxtvxtvxtv

h

xx

x

unde

),(),(1 ztuztv = ,

++= ),(2

,2

),( 12 ztvh

zh

tuztv

++= ),(2

,2

),( 23 ztvh

zh

tuztv , ( )),(,),( 34 zthvzhtuztv ++= .

ObservaŃie. Pentru a aproxima soluŃia x în alte puncte decât cele ale diviziunii δ se apelează apoi la interpolare. Exemplu. Să rezolvăm cu metoda lui Euler pentru 05,0=h problema

[ ]1,0,)(

2)()(

1)0(

∈−=′

=

ttx

ttxtx

x

.

SoluŃie. Avem z

tztzu

2),( −= . EcuaŃiile cu diferenŃe (numite uneori

ecuaŃii apropiate) sunt

−+=

=

+k

kkkk x

txhxx

x

2

1

1

0

cu ktk 05,0= , { }20,...,1,0∈k . Se obŃine 10 =x , 05,11 =x , 097,12 =x ,

148,13 =x , etc.

BIBLIOGRAFIE

1. Gh. Grigore, LecŃii de analiză numerică, Editura UniversităŃii Bucureşti, 1992. 2. B. Demidovici, I. Maron, Elements de calcul numerique, Edition Mir, Moscou,

1973. 3. Gh. Marinescu, Gh. Grigore ş.a., Probleme de analiză numerică, Editura

Didactică şi Pedagogică, Bucureşti, 1978.