Lucrare de licent a [616667]

Universitatea Lucian Blaga Sibiu
Facultatea de S tiint e
Departamentul de Matematic a  si Informatic a
Specializarea Matematic a-Informatic a
Lucrare de licent  a
Aplicat ii practice ale metodelor de rezolvare a
ecuat iilor transcendente de ordin superior
Absolvent:R aducu-R azvan Gheorghe
Coordonator:Conf. Dr. Daniel Florin Sofonea
March 19, 2017

Cuprins
Introducere 1
1 Metode clasice de rezolvare a ecuat iilor transcendente 3
1.1 Metoda coardei . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.1 Ordin de convergent  a . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.2 Interpretare geometric a . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.1.3 Implementarea metodei in C++ . . . . . . . . . . . . . . . . . . . . 6
1.2 Metoda secantei . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2.1 Convergent a metodei . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2.2 Ordin de convergent  a . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2.3 Interpretare geometric a . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.2.4 Implementarea metodei in C++ . . . . . . . . . . . . . . . . . . . . 11
1.3 Metoda lui Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.3.1 Construct ia metodei . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.3.2 Ordin de convergent  a . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.3.3 Interpretare geometric a . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.3.4 Implementarea metodei in C++ . . . . . . . . . . . . . . . . . . . . 16
1.4 Metoda ^ njum at at irii intervalului . . . . . . . . . . . . . . . . . . . . . . . 18
1.4.1 Implementarea metodei in C++ . . . . . . . . . . . . . . . . . . . . 19
1.5 Comparat ii ^ ntre metode . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.5.1 Comparat ii ^ ntre metoda coardei si metoda Newton . . . . . . . . . 21
1.5.2 Comparat ii ^ ntre metoda coardei si metoda secantei . . . . . . . . . 21
1.5.3 Comparat ii ^ ntre metoda secantei si metoda Newton . . . . . . . . . 24
1.5.4 Comparat ii ^ ntre metoda coardei si metoda ^ njum at at irii intervalului 24
2 Construct ia metodelor de ordin superior 25
2.1 Teorema de punct x . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.2 Metode cu mai mult i pa si . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.3 Metoda lui Ceb^  sev . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.3.1 Cazuri particulare . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.4 Metoda lui Steensen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.4.1 Cazuri particulare . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.5 Metoda lui Traub . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.5.1 C^ ateva funct ii iterative cu un singur punct de start . . . . . . . . . 35
2.6 ^Imbun at at irea ordinului de convergent  a . . . . . . . . . . . . . . . . . . . . 35
3 Aplicat ii software 36
Bibliograe 37
1

Introducere
2

Capitolul 1
Metode clasice de rezolvare a
ecuat iilor transcendente
1.1 Metoda coardei
Metoda coardei, numit a  si metoda falsei pozit ii sau metoda p art ilor proport ionale, se
num ar a printre cele mai vechi metode numerice de rezolvare a ecuat iilor, convergent a
metodei ind stabilit a ^ nc a de Fourier, acesta introduc^ and condit ia:
f(x0)f00>0;
(condit ia lui Fourier).
Consideram n=1, deci ecuat ia f(x) = 0 se^ nlocuie ste cu P1(x) = 0, unde P1este polinomul
de interpolare de gradul ^ ntai al funct iei f pe nodurile x0=asix1=sse obt ine metoda
coardei.
Solut ia ecuat iei P1(x) = 0 este
(1.1) x2=x0f(x1)x1f(x0)
f(x1)f(x0)
Forma general a a metodei se obt ine pun^ and in (1.1) x1=xn six2=xn+1. Rezult a:
(1.2) xk+1=x0f(xk)x1f(x0)
f(xn)f(x0);
punctul de "plecare", x0, este utilizat pe parcursul ^ ntregului proces de calcul.
1.1.1 Ordin de convergent  a
Convergent a metodei este legat a de alegerea optim a a acestui punct.
Lema 1.1.1 Fief2c2([a;b]);x0;x12[a;b]cuf(x0)6=f(x1) si ex2dat de (1.1).
Atunci are loc relat ia
f(x2) =f(x0)f(x1)f00(")
2f0("0)2;
3

unde";"02(x0;x1)
Demonstrat ie: Utiliz^ and (1.1)  si aplic^ and formula cre sterilor nite, obt inem
(1.3) x2x0=f(x0)
f0(0); x 2x1=f(x1)
f0(0);
unde02(x0;x1).Din formula restului de interpolare
f(x)Pn(x) =f(n+1)()
(n+ 1)!nY
i=0(xxi);
unde
Pn(x) =nX
k=0lk(x)f(xk);
cu
lk(x) =(xx0):::(xxk1)(xxk+1):::(xxn)
(xkx0):::(xkxk1)(xkxk+1):::(xkxn);
pentru n=1 rezult a
f(x)P1(x) =f00()
2(xx0)(xx1)
cu
P1(x) =xx1
x0x1f(x0) +xx0
x1x0f(x1) =1
x0x1((xx1)f(x0)(xx0)f(x1)):
Pentrux=x2, obt inem relat ia
f(x2)P1(x2) =f00()
2(x2x0)(x2x1);
cu
P1(x2) =1
x0x1((x2x1)f(x0)(x2x0)f(x1)):
Din relat ia (1.3) obt inem
P1(x2) =1
x0x1
f(x1)f(x0)
f0(0)+f(x0)f(x1)
f0(0)
= 0:
Din aceasta rezult a relat ia din lem a, adic a
f(x2) =f00()
2(xx0)(xx1) =f(x0)f(x1)f00()
2f0(0)2:
Lema 1.1.2 Fief2C2([a;b]);x0;x12[a;b],  si ex2dat de (1.1). Consider am c a
f0(x)6= 0 pe[a;b] si ecuat iaf(x) = 0 are solut ia x2(a;b):Are loc relat ia
(1.4) xx2=f00()f0(1)f0(2)
2f0()3(xx0)(xx1);
unde2(x;x0;x1);12(x;x0);22(x;x1):
Demonstrat ie: Deoarecef0(x)6= 0 pe[a;b], rezult a c a feste strict monoton a pe [a;b]
 si deci inversabil a, funct ia invers a 'este de dou a ori derivabil a pe [a;b]:
(1.5) '0(y) =1
f0(x); '00(y) =f00(x)
f0(x)3
4

Aplic am formula cre sterilor nite ^ n punctele x0;x six1;x si obt inem
y0=f(x0)f(x) = (x0x)f0(1);  12(x0;x);
y1=f(x1)f(x) = (x1x)f0(2);  22(x1;x):
Utiliz^ and formula restului de interpolare a lui Lagrange pentru funct ia invers a 'pe nodurile
y0;:::;yn si cu'0Qn(0), undeQneste polinomul de interpolare, se obt ine eroarea
aproxim arii
'(y)Qn(y) ='(n+1)(v)
(n+ 1)!nY
i=0(yyi);
undev2(y0;yn). Consider am y= 0;n= 1;iar'" siy0;y1sunt dat i de relat iile de mai
sus  si t inem seama c a varphi (0) =x si c aQ1(0) =x2, rezult a
xx2='00()
2(x0x)(x1x)f0(1)f0(2);
adic a
xx2=f00()f0(1)f0(2)
2f0()3(xx0)(xx1):
Deoarecef2C2([a;b]) sif0(x)6= 0 pe[a;b], exist a numerele m1;m2;M1;M2astfel ^ nc^ at
0<m 1jf0(x)jM1<+1;
0<m 2jf"(x)jM2<+1:
Obt inem relat ia
m2m2
1
2M3
1f00()f0(1)f0(2)
2f0()3M2M2
1
2m3
1:
Not amk=m2m1
(2M3
1); K =M2M1
(2m3
1):Se obt ine relat ia
(1.6) kjxx0jjxx1jjxx2jKjxx0jjxx1j:
Teorema 1.1.1 Fief2C2([a;b]) six0;x12[a;b]. Presupunem c a urm atoarele condit ii
sunt ^ ndeplinite:
1.f006= 0;8×2[a;b];
2.f(x0)f00(x0)>0;
3.f(x0)f(x1)<0:
Atunci ecuat ia f(x) = 0 are o solut ie unic a x^ n(x0;x1), iar  sirulfxkgdat de metoda
coardei (1.2) converge la x.
Demonstrat ie: Presupunem c a f00(x)>0pe[a;b] si decif(x0)>0;f(x1)<0precum
 si c ax0< x 1. Existent a solut iei rezult a din continuitatea lui f si din condit ia 3., iar
unicitatea ei rezult a din condit iile 1.  si 3.
Din lema (1.1.1) rezult a
f(x2) =f(x0)f(x1)f00()
f0(0)2
adic a
f(x2)<0)x<x 2:
5

Pe de alt a parte, relat ia (1.1) se poate scrie sub forma
x2=x1f(x1)
f(x1)f(x2)(x1x0);
de unde rezult a c a x2<x 1.
A sadarx<x 2<x 1:^In generalx<xk+1<xk si decixk!x;k!1:
Not am cu
Kjxx0j=;
undeKeste constanta din inegalitatea (1.6). Din aceast a inegalitate rezult a
jxx2jKjxx0jjxx1j=jxx1j
 si ^ n general
jxxk+1jjxxkj;
ceea ce ^ nseamn a c a metoda coardei are convergent a cel put in liniar a.
Observat ie 1.1.1 Metoda coardei poate s a aib a, ^ n cazuri particulare, ordin de convergent  a
superior lui unu.
1.1.2 Interpretare geometric a
Interpretarea general a a lui x2reprezint a abcisa punctului de intersect ie a "coardei" def-
inite de punctele ( x0;f(x0))  si (x1;f(x1)) cu axaOx.
1.1.3 Implementarea metodei in C++
#include " stdafx . h"
#include <iostream>
#include<math . h>
using namespace std ;
double f ( double x , double A)
f
return ( xxA);//pow(x ,(7+6.4)/2);
g
i n t i t e r =200;
double coarda ( double a , double b , double A, double eps )
f
i n t n r p a s i =0;
double x , x0 , x1 , y ;
x0=a ; x1=b ; x=x0 ; y=f (x ,A) ;
6

i f ( f ( x0 ,A)f ( x1 ,A)<0)
f
while ( ( nr pasi<=i t e r ) && (y <epsjjy>eps ) )
f
x=x0f ( x0 ,A)( x1x0 )/( f ( x1 ,A)f ( x0 ,A) ) ;
y=f (x ,A) ;
i f ( f ( x0 ,A)y<0) x1=x ;
e l s e x0=x ;
n rp a s i++;
g
i f ( nr pasi>i t e r )
f
cout<<"Problema nu se r e z o l v a in nr maxim de i t e r a t i i " ;
return 0 ;
g
e l s e
f
cout<<"Rezultat obtinut prin metoda coardei dupa "
cout<<nrpasi<<" pasi "<<endl ;
return x ;
g
g
e l s e cout <<"i n t e r v a l i n v a l i d " ;
g
i n t main ( )
f
double a , b ,A, eps ;
cout<<"I n t r o d u c e t i pe A: " ;
cin>>A;
cout<<"I n t r o d u c e t i a : " ; cin >>a ;
cout<<"I n t r o d u c e t i b : " ; cin >>b ;
cout<<"I n t r o d u c e t i aproximatia cu care d o r i t i sa se " ;
cout<<"c a l c u l e z e r a d i c a l u l ( ex 0 . 0 0 0 0 0 0 0 1 ) : " ; cin >>eps ;
cout . p r e c i s i o n ( 2 0 ) ;
cout<<"Radical din A r e z o l v a t prin metoda coardei e s t e : "
cout<<coarda ( a , b ,A, eps) <<endl<<"nn " ;
system ("PAUSE" ) ;
return 0 ;
g
Pornind de la intervalul [1 ;4](a= 1;b= 4)  si dorind s a calcul am radical din A=
3:8534245323 cu o eroare de aproximare de 1010obt inem dup a 23 de pa sip
A= 1:9630141446781526,
primele 9 zecimale ind exacte.
7

1.2 Metoda secantei
1.2.1 Convergent a metodei
Metoda secantei este o metod a de interpolare (liniar a) care se obt ine ^ nlocuind ecuat ia
f(x) = 0 cu ecuat ia P1(x) = 0, unde P1este polinomul de interpolare de gradul ^ ntai al
luifpe nodurile x0 six1(^ n general pe xk1;xk). Deosebirea eset ial a fat  a de metoda
coardei const a ^ n aceea c a, dup a calculul lui x2, punctelex0;x1se ^ nlocuiesc cu x1;x2 si
se repet a procedeul. Se presupune satisf acut a condit ia
f(x0)f(x1)<0:
Formula de calcul se poate obt ine din considerat ii geometrice simple sau ^ nlocuind ^ n
relat ia (1.2) pe x0cuxk1,
(1.7) xk+1=xk1f(xk)xkf(xk1)
f(xk)f(xk1);
Teorema 1.2.1 Fief2C2([a;b]) six0;x12[a;b]:Consider am urm atoarele condit ii ca
ind ^ ndeplinite:
1. ecuat iaf(x) = 0 are o solu  tie x2[a;b];
2.f0(x)6= 0 pe[a:b],
3.maxfKjxx0j;Kjxx1jg=d<1;undeKeste constanta din inegalitatea (1.6),
4.  sirulfxkgdat de (1.7) r am^ ane ^ n [a:b]:
Atuncixk!x;k!1:
Demonstrat ie:
Dac axk1;xk2[a;b]atunci dac a not am cu dk=Kjxxkj, obt inemdk+1dkdk1,
iar din condit ia 3:rezult a c a
(1.8) dkdpk;
8

undefpkgeste un  sir Fibonacci
(1.9) pk+1=pk+pk1
cu tot i termenii init iali p0=p1= 1:Este evident c a dk!0;k!1  sixk!x:
1.2.2 Ordin de convergent  a
Relat ia de recurent  a (1.9) constituie o ecuat ie cu diferent  a liniar a  si omogen a, cu coecient i
constant i. Polinomul caracteristic acestei ecuat ii este
'(t) =t2t1
 si are r ad acinile
t1=1 +p
5
21;6; t 2=1p
5
20;6:
Solut ia general a a ecuat iei (1.9) are forma
pk=C1tk
1+C2tk
2;
undeC1 siC2sunt constante arbitrare. Determin^ and aceste constante din condit iile
init ialep0=p1= 1, rezult a
pk=tk+1
1tk+1
2p
5:
S-a obt inut de fapt expresia termenului general al  sirului lui Fibonacci fpkgdenit de
relat ia (1.9). De aici  si din (1.8), rezult a
(1.10) dk<d1p
5(tk+1
1tk+1
2)<
d1p
5k
:
Consider am c a cele patru condit ii din teorema (1.2.1) sunt satisf acute, f2C3([a;b])  si
f0(x)>0, undexeste solut ia ecuat iei f(x) = 0:Presupunem c a  sirul fxkggenerat de
metoda secantei (1.7), apart ine unui interval de forma ( x";x+") ^ n caref" nu ^  si
schimb a semnul.
Din faptul c a f0^  si p astreaz a semnul pe [ a;b] obt inemf0(x)f00(x)>0 pe (x";x+").
Folosim o relat ie analoag a cu (1.4)
(1.11) xxk+2=f00()f0(1)f0(2)
2f0()3(xxk)(xxk+1);
unde2(x;xk;xk+1);12(x;xk);22(x;xk+1):Not amdk=jxxkj si observ am c a
(1.12) max( jxj;jx1j;jx2j)dk+dk+1:
Not am
yk= ln1
dk
 si
bk= ln2f0()3
f00()f0(1)f0(2);
 si din relat ia (1.12) avem
yk+2yk+1yk=bk;
9

adic ayksatisface o ecuat ie cu diferent  a liniar a, cu coecient i constant i. Consider am
b= ln2f0(x)
f00(x) sick=bkb, adic a
ck= 3 lnf0()
f0(x)lnf0(1)
f0(x)lnf0(2)
f0(x)lnf00()
f0(x):
Not am
M2= maxf00(x); M 3= maxf000(x);
m1= minf0(x); m 2=minf00(x);
pentrux2[a;b]. Fiecare din logaritmii care intervin ^ n expresia lui ckse pot majora ^ n
funct ie deM2;M3;m1;m2 sijxj;jx1j;jx2j;utiliz^ and teorema cre sterilor nite:
lnf0()
f0(x)=jlnjf0()jlnjf0(x)jj=(x)f00(x)
f0(c)M2
m1jxj;
undec2(x;):Din relat iile (1.10)  si (1.12) rezult a
(1.13)jckj
5M2
m1+M3
m2
(dk+dk+1)<1
K
5M2
m1+M3
m2
(1 +d1p
5)(d1p
5)k:
Rezult a c a1X
k=0cktkeste o serie ( ) cu=d1p
5<1:Facem schimbarea de funct ie yk=vk
 si obt inem
vk+2vk+1vk=ck:
Ecuat ia obt inut a satisface toate condit iile teoremei (1.2.1). Prima condit ie este satisf acut a
^ n conformitate cu (1.13), iar a doua condit ie rezult a din faptul c a
t1=1 +p
5
21;6; t 2=1p
5
20;6:
^In conformitate cu aceast a teorem a, exist a o constant a real a aastfel ^ nc^ at
vkatk
1=(k)!0; k!1:
Rezult a
yk+b=atk
1+(k):
Deoarece
yk= ln1
dk
; b = ln2f0(x)
f00(x);
avem
dk=2f0(x)
f00(x)eatk
1e(k):
Deoarece 1t1=t2, obt inem
dk+1
dk=2f0(x)
f00(x)t2
:
Rezult a c a metoda secantei are ordinul de convergent  a
t1=(1 +p
5)
21;6:
10

1.2.3 Interpretare geometric a
1.2.4 Implementarea metodei in C++
#include " stdafx . h"
#include <iostream>
#include<math . h>
using namespace std ;
double f ( double x , double A)
f
return ( xxA);//pow(x ,(7+6.4)/2);
g
double secanta ( double a , double b , double A, double eps )
f
i n t n r p a s i =0;
double x0 , x1 , y , x ;
x0=a ; x1=b ; x=x0 ; y=f (x ,A) ;
i f ( f ( x0 ,A)f ( x1 ,A)<0)
f
while ( ( nr pasi<=i t e r ) && ( abs ( x0 x1)>eps ) )
f
x=(x0f ( x1 ,A)x1f ( x0 ,A) ) / ( f ( x1 ,A) f ( x0 ,A) ) ;
x0=x1 ;
x1=x ;
n rp a s i++;
g
i f ( nr pasi>i t e r )
f
cout<<"Problema nu se r e z o l v a in nr maxim de i t e r a t i i " ;
return 0 ;
g
e l s e
f
cout<<"Rezultat obtinut prin metoda s e c a n t e i dupa " ;
cout<<nrpasi<<" pasi "<<endl ;
return x ;
g
g
e l s e cout <<"i n t e r v a l i n v a l i d " ;
g
i n t main ( )
11

f
double a , b ,A, eps ;
cout<<"I n t r o d u c e t i pe A: " ;
cin>>A;
cout<<"I n t r o d u c e t i a : " ; cin >>a ;
cout<<"I n t r o d u c e t i b : " ; cin >>b ;
cout<<"I n t r o d u c e t i aprmatia cu care d o o x i r i t i sa se " ;
cout<<" c a l c u l e z e r a d i c a l u l ( ex 0 . 0 0 0 0 0 0 1 ) : " ; cin >>eps ;
cout . p r e c i s i o n ( 2 0 ) ;
cout<<"Radical din A r e z o l v a t prin metoda s e c a n t e i e s t e : " ;
cout<<secanta ( a , b ,A, eps) <<endl<<"nn " ;
system ("PAUSE" ) ;
return 0 ;
g
Pornind de la intervalul [1 ;8];(a= 1;b= 8)  si dorind s a calcul am radical din A=
7:738392472842743 cu o eroare de aproximare de 1010obt inem dup a 58 pa sip
A=
2:7817966267940477, primele 9 zecimale ind exacte.
1.3 Metoda lui Newton
1.3.1 Construct ia metodei
Fief: [a;b]!R si ex02[a;b]. Dezvolt am funct ia f ^ n serie Taylor  si ret inem primii
doi termeni. Obt inem
f(x)f(x0) + (xx0)f0(x0):
^Inlocuim ecuat ia f(x) = 0 cu
(1.14) f(x0) + (xx0)f0(x0) = 0
12

a c arei solut ie este
x1=x0f(x0)
f0(x0):
Prin ^ nlocuirea lui x0cuxk, respectivx1cuxk+1, se obt ine metoda lui Newton sau metoda
Newton-Raphson
(1.15) xk+1=x0f(xk)
f0(xk):
Ecuat iaf(x0)+(xx0)f0(x0) = 0 aproximeaz a ecuat ia f(x) = 0 ^ n vecin atatea punctului
x0. Pentru a verica dac a x1aproximeaz a solut ia acestei ecuat ii este necesar a analiza
existent ei  sirului xk.^In cazul ^ n care se face ipoteza f0(x) = 0 pe intervalul [ a;b] acest
lucru nu mai este necesar.
Dac a ^ n 1.15 se ^ nlocuie ste f0(xk) cuf0(x0) rezult a metoda lui Newton simplicat a,
xk+1=x0f(xk)
f0(x0);
^ n care derivata se calculeaz a doar ^ n punctul x0. Putem considera un proces de tip
Newton ^ n care calculul derivatei se face dup a un anumit num ar de pa si:
xk+1=x0f(xk)
f0(xp(k));
unde p(k) este un num ar ^ ntreg mai mic sau egal cu k. Dac a consider am p(k)=0 obt inem
metoda lui Newton simplicat a.
Unul din procesele de tip iterativ, ce genereaz a metoda lui Newton simplicat a, este
metoda liniilor paralele:
xk+1=xkf(xk);
undeeste o constant a care aproximeaz a1
f0(x0):
Metoda lui Newton discretizat a este metoda ^ n care derivata este ^ nlocuit a cu diferent a
divizat a de ordinul ^ nt^ ai:
xk+1=xkf(xk)f(xk1)
xkxk11
f(xk):
Aceast a metod a coincide cu metoda secantei.
Teorema 1.3.1 (Ostrovski)
Fief2C2([a;b]) six02[a;b]. Presupunem ca urm atoarele condit ii sunt ^ ndeplinite:
1. f0(x0)6= 0;
2.intervalulI0= [x0;x0+ 2h0], undeh0=f(x0)
f0(x0), este inclus ^ n [a;b],
3.2jh0jMjf0(x0)j, undeM=max
x2I0jf"(x)j:
Rezult a c a ecuat ia f(x) = 0 are soltut ia unic a x2I0iar  sirul dat de metoda lui
Newton (1.15) este denit  si converge la x.
Eroarea aproximat iei este dat a de
jxxkj2M
f0(xk1)jxkxk1j2:
13

Demonstrat ie:
Aplic am formula cre sterilor nite funct iei f0^ n punctele x0;x1 si t inem seama de condit ia
3. si avem
jf0(x1)f0(x0)jjx1x0jM=jh0jMjf0(x0)j
2
 si
jf0(x1)jjf0(x0)jjf0(x1)f0(x0)jjf0(x0)jjf0(x0)j
2=jf0(x0)j
2:
Deci
(1.16) jf0(x1)jjf0(x0)j
2;
de unde rezult a, t in^ and seama de condit ia 1., c af0(x1)6= 0 si decix2este denit.
Calcul am ^ n dou a moduri diferite integrala
I=Zx1
x0(x1x)f"(x)dx:
Integr^ and prin p art i rezult a
I= (x1x)f0(x)jx1
x0+Zx1
x0f0(x)dx= (x1x0)f0(x0)+f(x)jx1
x0=x1f0(x0)x0f0(x0)+f(x1)f(x0):
Darx1=x1f(x0)
f0(x0)deci
I=x0f0(x0) +f0(x0)f(x0)
f0(x0)x0f0(x0) +f(x1)f(x0) =f(x1):
Obt inemI=f(x1). Efectu^ and schimbarea de variabil a x=x0+h0t, avem
I=h2
0Z1
0(1t)f"(x0+h0t)dt:
Rezult a
(1.17) jf(x1)jh2
0MZ1
0j1tjdt=h2
0M
2;
Consider am h1=f(x1)
f0(x1). Din (1.16)  si (1.17) obt inem
(1.18) jh1jh2
0M
jf0(x0)j
Prin urmare,
2jh1jM
jf0(x1)j2M2h2
0
jf0(x0)j2
jf0(x0)j=2jh0jM
jf0(x0)j2
:
Din condit ia 3.rezult a 2jh1jMjf0(x1)j, adic ah1satisface o relat ie analoag a cu 3.. Se
observ a c a
jh1jjh0j
22jh0jM
jf0(x0j)jh0j
2
14

 si intervalul I1= [x1;x1+ 2h1], analog cu I0, este inclus in I0. Utiliz^ and recurent a, se
obt ine pentru orice k:
f0(xk)6= 0;jhkj1
2jhk1j;2jhkjMjf0(xk)j;IkIk1;
undehk=f(xk)
f0(zk) siIk= [xk;xk+ 2hk]. Rezult a c a  sirul fxkgeste denit.
Consider am p un num ar ^ ntreg arbitrar. Avem Ik+pIk, decixk+p2Ik sijxk+p
xkj2hk. Darhk!0;k!1  si prin urmare, xk!x;k!1 . Ar at am c a xeste
solut ia ecuat iei f(x) = 0 . Avemjf0(x)jM1;8x2I0 si din
hk=f(xk)
f0(xk);
rezult a
jf(xk)jhkM1:
Prin trecerea la limit a avem f(x) = 0 . Ar at am c a xeste unic a ^ n I0. Pentru orice
x2(x0;x0+ 2h0)avemjxx0j<2jh0j:Din teorema cre sterilor nite  si din condit ia 3.
obt inem
jf0(x)f0(x0)jjxx0jM < 2jh0jMjf0(x0)j;
adic af0(x)6= 0 pe(x0;x0+ 2h0):
Funct ia f este monoton a, pe (x0;x0+2h0) si, prin urmare, xeste unic a ^ n (x0;x0+2h0):
Eroarea aproximat iei se obt ine din inegalitatea
jhkjh2
k1M
jf0(xk1)j
analoag a cu 1.18. T  in and seama c a jxk+pxkj2hkprecum  si de faptul c a hk1=
xkxk1, avem
jxk+pxkj2M
jf0(xk1)jxkxk1j2:
Consider^ and p!1 , se obt ine relat ia din enunt ul teoremei, adic a
jxxkj2M
f0(xk1)jxkxk1j2:
1.3.2 Ordin de convergent  a
Presupunem c a toate condit iile teoremei 1.3.1 sunt satisf acute. Deoarece f0(x0)6= 0 pe
(x0;x0+ 2h0) rezult a c a funct ia feste inversabil a pe I0. Fie'funct ia invers a  si s a not am
yk=f(xk),k= 0;1;:::, undefxkgeste  sirul generat de metoda Newton. Avem
'(yk1) =xk1;'(yk1) =1
f0(xk1):
Dezvolt am funct ia '^ n serie Taylor  si not am cu P1partea liniar a
P1(y) ='(yk1) + (yyk1)'0(yk1) =xk1+ (yyk1)1
f0(xk1):
Restul formulei lui Taylor este
(1.19) '(y)P1(y) ='"()
2(yyk1)2;
15

unde2(y;yk1). Not am='();2('(y);'(yk1)). Consider am ^ n relat ia (1.19)
y= 0  si t inem seama c a '(0) =x;P1(0) =xkprecum c a
'00(y) =f00()
2f0()3f(xk1)2;2(x;xk1):
Din teorema cre sterilor nite rezult a
f(xk1) =f(xk1)f(x) = (xk1x)f0();02(x;xk1):
Rezult a
xxk=f00()f0(0)2
2f0()3(xxk1)2:
Pentruxk!x;k!1 avem;0!x si
lim
k!1jxxkj
jxxk1j2=f00(x)
2f0(x):
Din aceast a relat ie rezult a c a metoda lui Newton are convergent  a p atratic a.
1.3.3 Interpretare geometric a
1.3.4 Implementarea metodei in C++
#include " stdafx . h"
#include <iostream>
#include<math . h>
using namespace std ;
double f ( double x , double A)
f
return ( xxA);//pow(x ,(7+6.4)/2);
g
double f1 ( double x )
f
return 2x ;
g
double tangenta ( double a , double b , double A, double eps )
f
i n t i =0;
double x , y1 , y ;
x=b ;
y=f (x ,A) ;
16

y1=f1 ( x ) ;
while ( ( i<=i t e r ) && ( ( y <eps )jj(y>eps ) ) )
f
x=xy/y1 ;
y=f (x ,A) ;
y1=f1 ( x ) ;
i ++;
g
i f ( i>i t e r )
f
cout<<"problema nu se r e z o l v a in nr maxim de i t e r a t i i " ;
return 0 ;
g
e l s e
f
cout<<"Rezultat obtinut prin metoda l u i Newton dupa " ;
cout<<i<<" pasi "<<endl ;
return x ;
g
g
i n t main ( )
f
double a , b ,A, eps ;
cout<<"I n t r o d u c e t i pe A: " ;
cin>>A;
cout<<"I n t r o d u c e t i a : " ; cin >>a ;
cout<<"I n t r o d u c e t i b : " ; cin >>b ;
cout<<"I n t r o d u c e t i aproximatia cu care d o r i t i sa se " ;
cout<<" c a l c u l e z e r a d i c a l u l ( ex 0 . 0 0 0 0 0 0 0 1 ) : " ; cin >>eps ;
cout . p r e c i s i o n ( 2 0 ) ;
cout<<"Radical din A r e z o l v a t prin metoda l u i Newton e s t e : " ;
cout<<tangenta ( a , b ,A, eps) <<endl<<"nn " ;
system ("PAUSE" ) ;
return 0 ;
g
Pornind de la intervalul [1 ;5];(a= 1;b= 5)  si dorind s a calcul am radical din A=
4:28394028492342 cu o eroare de aproximare de 1010obt inem dup a 5 pa sip
A= 2:069768171784772,
primele 9 zecimale ind exacte.
17

1.4 Metoda ^ njum at at irii intervalului
Presupunem ca avem de rezolvat ecuat ia f(x) = 0, cu funct ia f continu a  si c a am g asit
un interval inchis [a,b] cu proprietatea f(a)f(b)<0. Din teorema valorii intermediare,
obt inem existent a a cel put in o r ad acin a in intervalul [a,b]. Presupunem c a avem o singur a
r ad acin a in acest interval, de exemplu atunci c^ and f este strict monoton a. Not am aceast a
r ad acin a cu l.
Aceast a metod a const a ^ n a considera mijlocul intervalului [a,b],  si apoi ^ n a localiza
r ad acina l ^ n unul din cele dou a subintervale create, [ a;a+b
2] sau [a+b
2;b].
Renot am cu [ a;b] noul interval obt inut  si aplic am din nou procedeul p^ an a c^ and lungimea
intervalului [ a;b] este sucient de mic a.
Teorema 1.4.1 Fie f2C si presupunem c a f(a)f(b)<0.
Atunci  sirul (xn)n1denit mai sus este convergent la l, cu proprietatea:
en:=jxn1jba
2n;n1:
Metoda^ njum at at irii intervalului converge^ n toate cazurile^ n care s-a g asit f(a)f(b)<0,
eroarea aproxim arii reduc^ andu-se la jum atate la ecare pas.
Aceast a metod a este foarte lent a ^ n comparat ie cu celelalte metode, ind folosit a pentru
18

a
area unei aproximat ii init iale destul de bun a pentru alte metode( secantei, Newton,
etc.), ceea ce este esent ial pentru convergent a acestora.
Pentru valoarea maxim a admis a a erorii, ", se poate determina n-num arul necesar de
^ njum at at iri ale intervalului:
en<"=>ba
2n<"=>lg 2n+ lg(ba)<lg"=>n>lg(ba)lg"
lg 2
1.4.1 Implementarea metodei in C++
#include " stdafx . h"
#include <iostream>
#include<math . h>
using namespace std ;
double f ( double x , double A)
f
return ( xxA);//pow(x ,(7+6.4)/2);
g
i n t i t e r =200;
double b i s ( double a , double b , double A, double eps )
f
i n t i =0;
double y ;
i f ( f ( a ,A)f (b ,A)<0)
f
while ( fabs ( ab)>eps )
f
y=(a+b ) / 2 ;
i ++;
i f ( f (y ,A)==0)
f
a=y ;
b=y ;
g
e l s e
f
i f ( f (y ,A)f ( a ,A)<0) b=y ;
e l s e a=y ;
g
g
cout<<"nr de pasi : " <<i<<endl ;
19

return y ;
g
e l s e cout <<"i n t e r v a l i n v a l i d " ;
g
double b i s e c t i e ( double a , double b , double A, double eps )
f
i n t i =0;
double c ;
i f ( fabs (ba )<eps ) return ( a+b) / 2 . 0 ;
// Sa g a s i t radacina , o returnez
e l s e
f
c = ( a+b) / 2 . 0 ;
i f ( f ( a ,A)f ( c ,A)<0) return b i s e c t i e ( a , c ,A, eps ) ;
e l s e return b i s e c t i e ( c , b ,A, eps ) ;
g
g
i n t main ( )
f
double a , b ,A, eps ;
cout<<"I n t r o d u c e t i pe A: " ;
cin>>A;
cout<<"I n t r o d u c e t i a : " ; cin >>a ;
cout<<"I n t r o d u c e t i b : " ; cin >>b ;
cout<<"I n t r o d u c e t i aproximatia cu care d o r i t i sa se "
cout<<" c a l c u l e z e r a d i c a l u l ( ex 0 . 0 0 0 0 0 0 0 1 ) : " ; cin >>eps ;
cout . p r e c i s i o n ( 2 0 ) ;
cout<<"Radical din A r e z o l v a t prin metoda b i s e c t i e i : " ;
cout<<b i s ( a , b ,A, eps) <<endl<<"nn " ;
cout<<"Radical din A r e z o l v a t prin metoda b i s e c t i e i r e c u r s i v : " ;
cout<<b i s e c t i e ( a , b ,A, eps) <<endl<<"nn " ;
system ("PAUSE" ) ;
return 0 ;
g
Pornind de la intervalul [1 ;6](a= 1;b= 6)  si dorind s a calcul am radical din A=
5:82490245345 cu o eroare de aproximare de 1010obt inem dup a 36 de pa sip
A=
2:413483468::, primele 9 zecimale ind exacte.
20

1.5 Comparat ii ^ ntre metode
1.5.1 Comparat ii ^ ntre metoda coardei si metoda Newton
Pentru ecient a indexului metodei coardei folosit a ^ n consecint  a cu formula
x+1=x+1f(x)xf(x1)
f(x)f(x1);(= 1;2;:::)
este, ^ n practic a, 1.618… ^In aplicarea metodei Newton-Raphson este necesar s a se cal-
culezefsif0pentru ecare pas, astfel ^ nc^ at ecare pas de calcul este f acut cu mult a
greutate, atuncip
2 = 1:414:::este indexul de ecient  a al metodei Newton-Raphson.
Deci metoda coardei este mai bun a dec^ at metoda Newton-Raphson. Acest avantaj este
valabil doar pentru solut iile ecuat iilor simple, metoda coardei ind folositoare doar ^ n
acest scop, aplicat iile sale neput^ and  extinse cu u surint  a la alte teorii.
Pe de alt a parte principiul metodei Newton-Raphson se poate extinde la teoriile ecuat iilor
diferent iale, integrale, funct ionale  si multe alte p art i ale analizei.
Succesul metodei depinde ^ n mod direct de alegerea punctului de start, respectiv x0.
1.5.2 Comparat ii ^ ntre metoda coardei si metoda secantei
Implementarea metodei in C++
#include " stdafx . h"
#include <iostream>
#include<math . h>
using namespace std ;
21

double f ( double x , double A)
f
return ( xxA);//pow(x ,(7+6.4)/2);
g
double secanta ( double a , double b , double A, double eps )
f
i n t n r p a s i =0;
double x0 , x1 , y , x ;
x0=a ; x1=b ; x=x0 ; y=f (x ,A) ;
i f ( f ( x0 ,A)f ( x1 ,A)<0)
f
while ( ( nr pasi<=i t e r ) && ( abs ( x0 x1)>eps ) )
f
x=(x0f ( x1 ,A)x1f ( x0 ,A) ) / ( f ( x1 ,A) f ( x0 ,A) ) ;
x0=x1 ;
x1=x ;
n rp a s i++;
g
i f ( nr pasi>i t e r )
f
cout<<"Problema nu se r e z o l v a in nr maxim de i t e r a t i i " ;
return 0 ;
g
e l s e
f
cout<<"Rezultat obtinut prin metoda s e c a n t e i dupa " <<nrpasi<<" pasi "<<endl ;
return x ;
g
g
e l s e cout <<"i n t e r v a l i n v a l i d " ;
g
double coarda ( double a , double b , double A, double eps )
f
i n t n r p a s i =0;
double x , x0 , x1 , y ;
x0=a ; x1=b ; x=x0 ; y=f (x ,A) ;
i f ( f ( x0 ,A)f ( x1 ,A)<0)
f
while ( ( nr pasi<=i t e r ) && (y <epsjjy>eps ) )
f
x=x0f ( x0 ,A)( x1x0 )/( f ( x1 ,A)f ( x0 ,A) ) ;
y=f (x ,A) ;
i f ( f ( x0 ,A)y<0) x1=x ;
22

e l s e x0=x ;
n rp a s i++;
g
i f ( nr pasi>i t e r )
f
cout<<"Problema nu se r e z o l v a in nr maxim de i t e r a t i i " ;
return 0 ;
g
e l s e
f
cout<<"Rezultat obtinut prin metoda coardei dupa " ;
cout<<nrpasi<<" pasi "<<endl ;
return x ;
g
g
e l s e cout <<"i n t e r v a l i n v a l i d " ;
g
i n t main ( )
f
double a , b ,A, eps ;
cout<<"I n t r o d u c e t i pe A: " ;
cin>>A;
cout<<"I n t r o d u c e t i a : " ; cin >>a ;
cout<<"I n t r o d u c e t i b : " ; cin >>b ;
cout<<"I n t r o d u c e t i aproximatia cu care d o r i t i sa se c a l c u l e z e r a d i c a l u l ( ex 0 . 0 0 0 0 0 0 1 ) : " ; cin >>eps ;
cout . p r e c i s i o n ( 2 0 ) ;
cout<<"Radical din A r e z o l v a t prin metoda coardei e s t e : " <<coarda ( a , b ,A, eps) <<endl<<"nn " ;
cout<<"Radical din A r e z o l v a t prin metoda s e c a n t e i e s t e : " <<secanta ( a , b ,A, eps) <<endl<<"nn " ;
system ("PAUSE" ) ;
return 0 ;
g
Pornind de la intervalul [1 ;7](a= 1;b= 7)  si dorind s a calcul am radical din A=
6:79374828492353 cu o eroare de aproximare de 1010obt inemp
A= 2:6064819747 ::,
primele 10 zecimale ind exacte.
23

Observ am c a metoda secantei returneaz a rezultatul dup a un num ar de pa si mai mic
dec^ at cel din cazul metodei coardei. Deducem c a metoda secantei are convergent a mai
bun a dec^ at metoda coardei.
1.5.3 Comparat ii ^ ntre metoda secantei si metoda Newton
1.5.4 Comparat ii ^ ntre metoda coardei si metoda ^ njum at at irii
intervalului
24

Capitolul 2
Construct ia metodelor de ordin
superior
2.1 Teorema de punct x
Denit ia 2.1.1 Funct iaf:R!Reste o contract ie dac a (9)c2(0;1)astfel ^ nc^ at (8)
x;y2Rs a aib a loc inegalitatea:
jf(x)f(y)jcjxyj:
Teorema de punct x a lui Banach, care st a la baza unor metode iterative de rezolvare a
ecuat iilor de forma f(x) =x, presupune c a feste o contract ie pe R.
Teorema 2.1.1 Consider am f: [a;b]!R six2(a;b)un punct x al funct iei f. Pre-
supunem c a feste contract ie pe mult imea S(x;r) = [xr;x+r]:Atuncixeste un
punct x unic ^ n S(x;r) sifk(x0)!x;k!1 (8)x0dinS(x;r).
Demonstrat ie: Fie;0<  < 1;constanta contract iei. Presupun^ and c a fk(x)2
S(x;r), obt inem:
jfk+1(x)xjjfk(x)xj<r;
 si decifk+1(x)2S(x;r):Cumx2S(x;r);obt inem prin indut ie c a fk(x)2S(x;r);(8)k:
Rezult a
jfk(x)xjjxxj!0;k!1:
Observat ie 2.1.1 ^In teorema lui Banach s-a considerat x0arbitrar ales din domeniul de
denit ie al funct iei  si s-a format  sirul
x0;x1=f(x0);x2=f(x1) = (ff)(x0);:::;xn= (ff:::f|{z}
n ori)(x0):
Pentru a demonstra aceast a teorem a folosim
fk(x) = (ff:::f|{z}
k ori)(x);
adic a
jfk+1(x)f(x)j=jff:::f|{z}
k ori)(x)xjfcontrac t ie
jfk(x)xjfk(x)2S(x;r)
< r:
25

Corolar 2.1.1 Dac af2C([a;b]) sijf0(x)j <1, undex2(a;b)este punct x al
luif, atunci exist a S(x;r)[a;b]astfel cafk(x)!x;(8)x2S(x;r):
Din continuitatea lui f0pe[a;b]rezult a c a exist a S(x;r)[a;b] si0< astfel ^ nc^ at
jf0(x)j;(8)x2S(x;r):
Obt inem c a feste contract ie pe S(x;r):
Teorema 2.1.2 Fiefo funct ie real a denit a pe [a;b] six02(a;b)un punct oarecare.
Consider am fo contract ie pe S(x;r)cu constanta  si c a
jf(x0)x0j(1)r:
Rezult a c a exist a un punct x unic x2S(x;r) sifk(x0)!x;k!1:
Demonstrat ie: Ar at am c a dac a x2S(x;r), atuncif(x)2S(x;r);adic a f este o
contract ie a sferei S(x;r)^ n ea ^ ns a si.
Lu amx2S(x;r). Obt inem
jf(x)x0jjf(x)f(x0)j+jf(x0)x0jjxx0j+ (1)rr+rrr;
rezult a c af(x)2S(x;r):
2.2 Metode cu mai mult i pa si
Fie ecuat ia:
(2.1) f(x) = 0
undef:I!Reste o funct ie real a, Iind un interval al axei reale.
Presupunem c a ecuat iei (2.1) i se poate pune ^ n corespondent  a o funct ie ':I!R
astfel ^ nc^ at orice solut ie a ecuat iei (2.1) s a e  si solut ie a ecuat iei
(2.2) x='(x)
 si invers. Presupunem c a exist a o funct ie de kvariabile,k1;g:Ik!Rcu proprietatea
(2.3) g(x;x;:::;x ) ='(x);
pentru orice x2I:
O metod a iterativ a cu kpa si de iterat ie pentru rezolvarea numeric a a ecuat iei (2.3)
are forma general a astfel construit a
i)g:Ik!R;undeIk=II:::IRk
ii)
(2.4) xk=g(x0;x1;:::;xk1)xk+i=g(xi;xi+1;:::;xi+k1);
i= 1;2;3;:::;x 0;x1;:::;xk12I
26

De exemplu metoda lui Newton este o metod a cu un singur pas, iar funct ia de iterat ie
geste denit a ^ n felul urm ator:
g(x) =xf(x)
f0(x);(8)x2I:
^In schimb, metoda secantei este o metod a cu doi pa si, iar funct ia de iterat ie gare
urm atoarea form a:
g(x;y) =xf(y)yf(x)
f(y)f(x);(8)(x;y)2I2:
Pentru metodele cu un singur pas putem da urm atoarea teorem a general a asupra
convergent ei  si a ordinului de convergent  a.
Teorema 2.2.1 Fieg2C(p)([a;b]) six2(a;b)un punct x al lui g. Dac a
g0(x) =:::=g(p1)(x) = 0;g(p)(x)6= 0;
atunci oricare ar  x0dintr-o anumit a sfer a centrat a ^ n xavem c a convergent a metodei
este egal a cu p.
Demonstrat ie: Deoareceg0(x) = 0<1;convergent a metodei rezult a imediat din
corolarul (2.1.1). Dezvolt^ and funct ia f^ n serie Taylor obt inem
g(x) =g(x) +p1X
i=1g(i)(x)
i!(xx)i+g(p)()
p!(xx)p;2(x;x):
Din ipotezele teoremei  si ^ nlocuind xcuxkobt inem
jxk+1xj
jxkxjp=g(p)(k)
p!;k2(xk;x):
Rezult a
lim
k!1jxk+1xj
jxkxjp=g(p)(k)
p!
 si metoda are ordin de convergent  a p.
Mai departe, vom studia convergent a acestei metode.
Teorema 2.2.2 Dac a funct ia g veric a urm atoarele condit ii:
(i) funct ia g transform a mult imea Is^ nI;
(ii) funct ia g veric a condit ia (2.3);
(iii) pentru orice y1;y2;:::;ys;ys+12Ieste vericat a inegalitatea:
(2.5)jg(y1;y2;:::;ys)g(y2;y3;:::;ys+1)j1jy1y2j+2jy2y3j+:::+sjysys+1j;
unde10;20;:::;s0sunt numere reale care veric a condit ia
(2.6) 1+2+:::+s<1;
27

atunci  sirul (xn)1
n=0generat de (2.4) este convergent (8)x0;x1;:::;xs12I si dac a not am
cux= lim
n!1xn, atuncixeste unica solut ie a ecuat iei x='(x)din intervalul I.
Demonstrat ie: Demonstr am c a  sirul (xn)1
n=0generat de (2.4) este  sir Cauchy.
Din condit ia (2.5) rezult a c a au loc urm atoarele inegalit at i:
(2.7)jxn+1xnj=jg(xns+1;xns+2;:::;xn)g(xns;xns+1;:::;xn1)j
1jxns+1xnsj+2jxns+2=xns+1j+:::+jxnxn1j;
pentru ecare n=s;s+ 1;:::
C aut am o majorare pentru jxixi1j;i= 1;2;3;:::.
Consider am ecuat ia
(2.8) P(u) =ussus1+s1us2:::+2u1= 0:
Ecuat ia (2.8) are o singur a r ad acin a pozitiv a. Fac^ and schimbarea de variabil a u=1
tobt inem ecuat ia echivalent a
Q(t) =1ts+2ts1+:::+st1 = 0;
pentru care Q0(t)>0dac at>0deoarecei0pentrui= 1;2;:::;s: Rezult a c a ecuat ia
Q(t) = 0 poate avea o singur a r ad acin a pozitiv a  si deci ecuat ia P(u) = 0 poate avea doar
o r ad acin a pozitiv a. Observ am c a P(1)>0deoarece este vericat a inegalitatea (2.6)  si
P(0)<0. Dac aP(0) = 0 atunci exist a un num ar natural i<s pentru care dac a not am
cuR(u) =P(u)
uiavemR(0)<0 siR(1)>0.
Rezult a c a ecuat ia P(u) = 0 are o singur a r ad acin a pozitiv a  si subunitar a.
^In rat ionamentul prezentat mai sus ne-am bazat pe faptul c a exist a cel put in un num ar
naturalispentru care i>0, ^ n caz contrar funct ia g ar coincide cu funct ia constant a
 si problema pus a nu ar avea sens.
Not am cu p r ad acina ecuat iei P(u) = 0 , care veric a relat ia 0< p0<1. Observ am
c a exist a un num ar real  si pozitiv astfel ^ nc^ at dac a not am cu i=jxixi1j;i= 1;2;:::;
atunci au loc inegalit at ile
()1; 2p;:::;sps1:
Lu am
= max
1;2
p;:::;s
ps1
Din sistemul de inegalit at i (2.7) obt inem:
8
>>>>>>><
>>>>>>>:s+1=ss+s1s1+:::+11;
s+2=ss+1+s1s+:::+12;
…
s+t=ss+t1+s1s+t2+:::+1t;
…
Din relat iile de mai sus, din (*)  si din faptul c a p este r ad acina ecuat iei
28

P(u) = 0 rezult a urm atoarele inegalit at i:
s+1=sps1+s1ps2+:::+1=(sps1+s1ps2+:::+1)ps:
^In mod analog ar at am c a au loc inegalit at iile
(2.9) s+tps+t1; t = 1;2;:::
Ar at am c a  sirul (xn)1
n=0generat de (2.4) veric a condit iile lui Cauchy  si obt inem:
(2.10)jxn+mxnj=m1X
i=0jxn+i+1xn+ij=m1X
i=0n+im1X
i=0pn+i1pn1
1p;
care ne arat a c a pentru orice " >0exist a un num ar N(")astfel ^ nc^ atjxn+mxnj< "
pentru orice n>N (") si pentru orice num ar natural m.
Din faptul c a  sirul (xn)1
n=0este  sir Cauchy rezult a c a este  si convergent. Lu am x=
lim
n!1xn si trec^ and la limit a ^ n inegalitatea (2.10) pentru m!1 obt inem:
jxxnjpn1
1p; n = 1;2;:::
Din condit ia (2.5) care asigur a continuitatea funct iei g, rezult a faptul c a xveric a
ecuat ia considerat a.
Indic am dou a moduri ^ n care se pot obt ine  si alte metode de iterat ie de tip Newton.
Fie funct ia h:I2!Rcare are proprietatea c a restrict ia ei la diagonala mult imii I2
coincide cu f, unde f este funct ia ce dene ste ecuat ia (2.1), adic a
(2.11) h(x;x) =f(x)
pentru orice x2I.
FieI= [a;b]:Presupunem c a funct ia h admite derivate part iale ^ n raport cu ecare
din variabilele sale, pentru orice (x;y)2(a;b)(a;b):
Pentru a rezolva ecuat ia (2.1) consider am urm atorul procedeu iterativ
(2.12) xn+1=xnf(xn)
h0
x(xn;xn);n= 0;1;:::;
unde prinh0
xam notat derivata part ial a a funct iei h ^ n raport cu variabila x. Aceast a
metod a este chiar o variant a a metodei lui Newton.
Presupunem c a funct ia h veric a condit ia (2.11)  si consider am pentru rezolvarea
ecuat iei (2.3) urm atorul procedeu iterativ:
(2.13) xn+1=xnh(xn;xn1) +h0
y(xn;xn1)(xnxn1)
h0
x(xn;xn1);
n= 1;2;::::
Utiliz^ and procesul iterativ de la (2.13) obt inem un  sir de numere reale (xn)1
n=0care dac a
este convergent, atunci limita sa este chiar r ad acina ecuat iei (2.3).
Dac ax= lim
n!1xn, atunci pentru n!1 din (2.3) obt inem:
x=xh(x;x) +h0
y(x;x)(xx)
h0
x(x;x)
de unde rezult a h(x;x) = 0 , adic af(x) = 0:
29

2.3 Metoda lui Ceb^  sev
Fief2C(p+1)([a;b])  six2(a;b) o solut ie a ecuat iei f(x) = 0. Presupunem c a f0(x)6= 0
pe [a;b]; atunci exist a funct ia invers a 'a lui f, denit a pe [ f(a);f(b)]  si ^ n plus 'este de
p+ 1 ori derivabil a. Utiliz am formula lui Taylor  si obt inem
'(z) ='(y) +pX
i=1'(i)(y)
i!(zy)i+'(p+1)()
(p+ 1)!(zy)(p+1);2(y;z):
Pentruz= 0  siy=f(x) obt inem '(0) =x, deoarece f(x) =y,x='(y)  si
2(f(x);f(x), prin urmare, exist a un 2(x;x) astfel ^ nc^ at f() =:Not amai(x) =
'(i)[f(x)]  si obt inem
(2.14) x=x+pX
i=1(1)iai(x)
i!f(x)i+ (1)p+1'(p+1)[f()]
(p+ 1)!f(x)p+1:
Not am
F(x) =x+pX
i=1(1)iai(x)
i!f(x)i;
 si lu am F ca funct ie de iterat ie. Obt inem metoda
(2.15) xk+1=F(xk);
numit a metoda lui Ceb^  sev.
Teorema 2.3.1 Dac a'(p+1)(0)6= 0atunci metoda lui Ceb^  sev are ordinul de convergent  a
p+ 1.
Demonstrat ie: Scriem funct ia F sub forma
F(x) =x'0[f(x)]f(x) +f(x)2pX
i=2(1)iai(x)
i!f(x)i2
 si not am
g(x) =pX
i=2(1)iai(x)
i!f(x)i2
Obt inem
F0(x) = 1'00[f(x)]f0(x)f(x)'0[f(x)]f0(x) + 2f(x)f0(x)g(x) +f(x)2g0(x):
Deoarece'0[f(x)]f0(x) = 1 , rezult a c a F0(x) = 0  si metoda lui Ceb^  sev este convergent a.
^Inlocuindxcuxk^ n relat ia (2.14) obt inem
xxk+1= (1)p+1'(p+1)[f(k)]
(p+ 1)!f(xk)p+1; k2(xk;x):
Pe de alt a parte
f(xk) =f(xk)f(x) = (xkx)f0(0
k); 0
k2(xk;x):
Rezult a
lim
k!1jxk+1xj
jxkxjp+1='(p+1)(0)
(p+ 1)!f0(x)p+1:
Deci metoda lui Ceb^  sev are ordin de convergent  a p+ 1.
Calculul coecient iilor aise poate face prin derivarea succesiv a a identit at ii '[f(x)]
x. Rezult a
30

'0[f(x)]f0(x) = 1;
'00[f(x)]f0(x)2+'0[f(x)]f00(x) = 0;
…………
de unde rezult a urm atoarele formule care ne dau pe ai(x)recursiv
a1(x)f0(x) = 1;
a2f0(x)2+a1(x)f00(x) = 0
……………..
Primele dou a valori sunt
a1(x) =f0(x)1; a 2(x) =f00(x)f0(x)3:
2.3.1 Cazuri particulare
(i) Pentrup= 1 formula de recurent  a (2.15) devine
xk+1=xkf(xk)
f0(xk);
aceasta ind chiar metoda lui Newton. Din teorema (2.3.1) rezult a c a metoda lui
Newton are convergent a p atratic a.
(ii) Pentru p= 2 se obt ine urm atoarea metod a de tip Ceb^  sev cu ordinul de convergent  a
egal cu 3.
xk+1=xkf(xk)
f0(xk)f00(xk)f(xk)2
2f0(xk)3:
(iii) Pentru p= 3 obt inem urm atoarea metod a cu ordinul de convergent  a egal cu patru
xk+1=xkf(xk)
f0(xk)f00(xk)f(xk)2
2f0(xk)3f3(xk)
3!f000(xk)f0(xk)3f00(xk)
(f0(xk))4:
2.4 Metoda lui Steensen
Presupunem c a am reu sit s a punem ecuat ia:
f(x) = 0;
sub urm atoarea form a echivalent a
g(x)x'(x) = 0;
unde presupunem c a punctele xe ale funct iei 'coincid cu r ad acinile ecuat iei f(x) = 0:
Presupunem c a e intervalul I funct ia g are o funct ie invers a  si ^ n acest interval este
cont inut a o singur a r ad acin a xa acestei ecuat ii.
Not am cux0o aproximat ie init ial a a r ad acinii x si construim  sirul denit ^ n felul
urm ator:
31

(2.16)8
>>>>>><
>>>>>>:x0
0=x0;
x0
1='(x0
0)
x0
2='(x0
1)
:::::::::::::
x0
n='(x0
n1):
Folosim polinomul de interpolare invers a, iar ca noduri de interpolare consider am valorile
y0
i=g(x0
i);i= 0;1;:::;n  si obt inem aproximat ia urm atoare a r ad acinii xcu formula:
x1=!0(0)nX
i=0x0
i
y0
i!0
0(y0
i);
unde, prin!0(y) am notat polinomul
!0(y) =nY
j=0(yy0
j):
Presupunem c a xkeste o aproximat ie oarecare a r ad acinii xa ecuat iei ^ n cauz a, atunci
aproximat ia xk+1o vom obt ine ^ n felul urm ator:
(2.17)8
>>>>>><
>>>>>>:xk
0=xk;
xk
1='(xk
0)
xk
2='(xk
1)
:::::::::::::
xk
n='(xk
n1):
 si not am cu yk
i=g(xk
i);i= 0;1;:::;n  si cu!k(y) =nY
i=0(yyk
i):Rezult a:
(2.18) xk+1=!k(0)nX
i=0xk
i
yk
i!0
k(yk
i); k = 0;1;:::
Metoda iterativ a obt inut a mai sus poart a denumirea de metoda general a a lui Aitken-
Steensen.
2.4.1 Cazuri particulare
1. Pentrun= 1  six0aproximat ia init ial a a r ad acinii xa ecuat iei ^ n cauz a, avem:
8
>>><
>>>:x0
0=x0;
x0
1='(x0
0) ='(x0);
y0
0=g(x0
0) =x0'(x0);
y0
1=g(x0
1) ='(x0)'('(x0)):
Folosim polinomul de interpolare invers a sub forma lui Newton  si deducem pentru
x1urm atoarea expresie:
x1=x0g(x0)
[x0;'(x0);g];
32

adic a
x1=x0[x0'(x0)]2
x02'(x0) +'('(x0)):
^In form a general a avem
(2.19) xk+1=xk[xk'(xk)]2
xk2'(xk) +'('(xk)); k = 0;1;:::
2. Pentrun= 2  six0aproximat ia init ial a a r ad acinii xa ecuat iei ^ n cauz a, avem:
8
><
>:x0
0=x0;
x0
1='(x0
0) ='(x0);
x0
2='(x0
1) ='('(x0))
^Inlocuind ^ n formula
x4=x3f(x3)
[x2;x3;f][x1;x2;x3;f]f(x2)f(x3)
[x1;x2;f][x1;x3;f][x2;x3;f];
nodurile de interpolare x1=x0;x2='(x0)  six3='('(x0)),x4=x1 sif=g, vom
deduce:
(2.20) x1='('(x0))'('(x0))'('('(x0)))
['(x0);'('(x0));g]
[x0;'(x0);'('(x0));g]['(x0)'('(x0))]
[x0;'(x0);g]['(x0);'('(x0));g]


['('(x0))'('('(x0)))]
[x0;'('(x0));g]:
^In general, dac a am calculat aproximat ia xk, atunci o nou a aproximat ie se obt ine
astfel: Calcul am nodurile xk
0;xk
1;xk
2cu ajutorul formulelor
8
><
>:xk
0=xk;
xk
1='(xk
0) ='(xk);
xk
2='(xk
1) ='('(xk)):
Proced^ and ca  si ^ n cazul formulei (2.21) vom obt ine:
(2.21) xk+1='('(xk))'('(xk))'('('(xk)))
['(xk);'('(xk));g]
[xk;'(xk);'('(xk));g]['(xk)'('(xk))]
[xk;'(xk);g]['(xk);'('(xk));g]


['('(xk))'('('(xk)))]
[xk;'('(xk));g]:
undek= 0;1;:::
Pentru a obt ine metode iterative de tip Aitken-Steensen ^ n cazul n= 3;n= 4;::
folosim metoda iterativ a general a (2.18).
33

2.5 Metoda lui Traub
Presupunem c a '(p)este continu a ^ n vecin atatea lui x. Fie'(x) =x;'(j)(x) = 0;j=
1;2;:::;p1;'(p)(x)6= 0:Din teorema lui Taylor rezult a
(2.22) xi+1='(xi) =x+'(p)(i)
p!(xix)p;
undemin(x;xi)<i<max (xi;x):Din aceasta rezult a urm atoarea teorem a:
Teorema 2.5.1 Fie'o funct ie iterativ a cu un singur punct de start  si e '(p)continu a
^ ntr-o vecin atate a lui x. Atunci'are ordinul pdac a  si numai dac a
'(x) =x;'(j)(x) = 0;j= 1;2;:::;p1;'(p)(x)6= 0:
^In plus
ei+1
ep
i!'(p)(x)
p!;
unde am notat ei=xix:
Aceasta este o teorem a de existent a, deoarece este dicil s a construim o funct ie iterativ a
'() ='(f;) astfel ca'(j)(x) = 0;j= 1;2;:::;pentru orice f. Putem construi algoritmi
pentru generarea de funct ii de iterat ie de toate ordinele.
Condit iile ^ n care xi!xsunt date ^ n cele ce urmeaz a.
Teorema 2.5.2 Consider am '(p)continu a ^ n intervalul
I=fx;jxxjjx0xjg:
Fiexn+1='(xn);n2N;'2C(p)(I):Dac a
(2.23)j'(p)(x)j
p!M; (8)x2I
 si
(2.24) Mje0jp1<1; e 0=x0x;
atunci
i)xi2I;i= 1;2;:::;
ii)xnconverge c atre x, av^ and ordinul de convergent  a cel put in egal cu p.
Demonstrat ie: Evidentx02I. Presupunem c a xi2I. Rescriem (2.22) ca
(2.25) ei+1=Miep
i; Mi='(p)(i)
p!
Din (2.23), (2.24), (2.25)  si prin denit ia lui I, se obt ine
jei+1jMjeijMje0jp1je0jje0j
Rezult a c a xi+12I si concluzion am c a jei+1j Mjeijp;i= 0;1;:::, ceea ce implic a
jeijM1+p+:::+pi1je0jpi. De aici rezult a
(2.26) jeijM1
p1(Mje0j)pi
p1; p> 1;
(2.27) jeijMije0j; p = 1:
34

Din formula (2.24) rezult a c a ei!0:
Se observ a c a relat iile (2.26)  si (2.27) dau limitele de eroare dup a pasul i. Observ am c a
dac ap= 1 (cazul convergent ei de ordinul ^ ntai), condit ia de convergent  a este j'0j<1 ^ n
vecin atatea lui x. Dac ap>1(cazul convergent ei liniare) exist a ^ ntotdeauna o vecin atate
a luix, pentru care iterat ia converge.
^In metodele de ordinul doi se cere evaluarea lui f sif0, ^ n metodele de ordinul trei este
necesar a evaluarea lui f,f0,f", etc. Aceasta sugereaz a c a funct iile iterative de ordin
pcer ^ ntotdeauna evaluarea a cel put in pfunct ii  si de fapt cel evaluarea cel put in a
f;f0;f";:::;f(p1).
Esent a teoremei fundamentale a funct iilor iterative cu un singur punct de start este
reprezentat a de faptul c a cele prezentate mai sus sunt ^ ntradev ar cazul pentru funct iile
iterative cu un singur punct de start.
2.5.1 C^ ateva funct ii iterative cu un singur punct de start
2.6 ^Imbun at at irea ordinului de convergent  a
O metod a de construct ie a funct iilor iterative de ordin p+ 1 care cer pevalu ari ale lui f
 si una a lui f0este bazat a pe urm atoarea teorem a:
Teorema 2.6.1 Fie'de ordinulp. Atunci
(x) ='(x)f['(x)]
f0(x)
este de ordinul p+ 1:
^In plus dac a denim
'j+1(x) ='j(x)f['(x)]
f0(x);'1(x) =x;
atunci'p(x)este de ordinul p.
^In particular,
'3(x) =xu(x)[xu(x)]
f0(x);u(x) =f(x)
f0(x);
este de ordinul trei.
Un exemplu de funct ie iterativ a de ordin superior ^ n care se folosesc mai multe puncte de
start este dat a de relat ia
'(x) =xu(x)f[xu(x)]f(x)
2f[xu(x)]f(x):
^In aceast a relat ie sunt folosite dou a evalu ari ale lui f si una a lui f0dar este de ordinul
patru. Aceastua funct ie iterativ a are urm atoarea interpretare geometric a:
Fie z=x-u(x). Consider am Pjum atatea liniei tangente ^ n [x;f(x)], aceasta a
^ andu-se
^ ntre punctele [x;f(x)] si[z;0]. Atunci'(x)este intersect ia dreptei ce trece prin Psi
[z;f(z)]cu axa x-lor.
35

Capitolul 3
Aplicat ii software
36

Bibliograe
[1] Daniel Florin Sofonea , Analiz a Numeric a  si Teoria Aproxim arii, Editura universit at ii
din Bucure sti, 2006
[2] Vraciu George, Micu Sorin, Efrem Raluca, C alug aru Dan, Analiz a numeric a-Metode
numerice ^ n algebr a  si ^ n metoda elementelor nite- Culegere de exercit ii  si probleme-
volumul al II-lea, Reprograa Universit at ii din Craiova, 1999
37