Bibliogra eRezolvarea numeric a a ecuat iilor neliniare De aici ^ ncepe adev arata Analiz a numeric a Radu Tr ^ mbit a s UBB 26 mai 2017… [603676]

Rezolvarea
numeric a a
ecuat iilor neliniare
Radu Tr ^ mbit a s
Ecuat ii neliniare
Ordin de
convergent  a
Falsa pozit ie
Metoda secantei
Metoda lui Newton
Metoda
aproximat iilor
succesive
R ad acini multiple
Ecuat ii algebrice
Sisteme neliniare
Metode
quasi-Newton
Interpolare liniar a
Metode de modicare
Interpolare invers a
Metode hibride
BibliograeRezolvarea numeric a a ecuat iilor neliniare
De aici ^ ncepe adev arata Analiz a numeric a
Radu Tr ^ mbit a s
UBB
26 mai 2017

Rezolvarea
numeric a a
ecuat iilor neliniare
Radu Tr ^ mbit a s
Ecuat ii neliniare
Ordin de
convergent  a
Falsa pozit ie
Metoda secantei
Metoda lui Newton
Metoda
aproximat iilor
succesive
R ad acini multiple
Ecuat ii algebrice
Sisteme neliniare
Metode
quasi-Newton
Interpolare liniar a
Metode de modicare
Interpolare invers a
Metode hibride
BibliograeEcuat ii neliniare I
IProblema discutat a ^ n acest capitol se poate scrie
generic sub forma
f(x) = 0, (1)
dar admite diverse interpret ari, depinz^ and de
semnicat ia lui x sif.
ICel mai simplu caz este cel al unei singure ecuat ii cu o
singur a necunoscut a, caz ^ n care feste o funct ie dat a
de o variabil a real a sau complex a  si ^ ncerc am s a g asim
valorile acestei variabile pentru care fse anuleaz a.
Astfel de valori se numesc r ad acini ale ecuat iei (1) sau
zerouri ale funct iei f.
IDac a xdin (1) este un vector, s a zicem
x= [x1,x2,. . .,xd]T2Rd sifeste de asemenea un
vector ale c arui componente sunt funct ii de cele d
variabile x1,x2,. . .,xd, atunci (1) reprezint a un sistem
de ecuat ii .

Rezolvarea
numeric a a
ecuat iilor neliniare
Radu Tr ^ mbit a s
Ecuat ii neliniare
Ordin de
convergent  a
Falsa pozit ie
Metoda secantei
Metoda lui Newton
Metoda
aproximat iilor
succesive
R ad acini multiple
Ecuat ii algebrice
Sisteme neliniare
Metode
quasi-Newton
Interpolare liniar a
Metode de modicare
Interpolare invers a
Metode hibride
BibliograeEcuat ii neliniare II
ISe spune c a sistemul este neliniar dac a cel put in una
dintre componentele lui fdepinde neliniar de cel put in
una din variabilele x1,x2,. . .,xd. Dac a toate
componentele lui fsunt funct ii liniare de x1,. . .,xd
avem de-a face cu un sistem de ecuat ii algebrice liniare.
IMai general (1) ar putea reprezenta o ecuat ie
funct ional a, dac a xeste un element al unui spat iu de
funct ii  si feste un operator (liniar sau neliniar) ce
act ioneaz a pe acest spat iu. ^In ecare din aceste situat ii
zeroul din dreapta lui (1) poate avea diverse
interpret ari: num arul zero ^ n primul caz, vectorul nul ^ n
al doilea  si funct ia identic nul a ^ n cel de-al treilea.
IMare parte din acest capitol este consacrat a unei ecuat ii
neliniare scalare. Astfel de ecuat ii apar frecvent ^ n
analiza sistemelor ^ n vibrat ie, unde r ad acinile corespund
frecvent elor critice (rezonant  a).

Rezolvarea
numeric a a
ecuat iilor neliniare
Radu Tr ^ mbit a s
Ecuat ii neliniare
Ordin de
convergent  a
Falsa pozit ie
Metoda secantei
Metoda lui Newton
Metoda
aproximat iilor
succesive
R ad acini multiple
Ecuat ii algebrice
Sisteme neliniare
Metode
quasi-Newton
Interpolare liniar a
Metode de modicare
Interpolare invers a
Metode hibride
BibliograeEcuat ii neliniare III
ICazul special al ecuat iilor algebrice, unde fdin (1) este
un polinom, este de important  a considerabil a  si merit a
un tratament special.

Rezolvarea
numeric a a
ecuat iilor neliniare
Radu Tr ^ mbit a s
Ecuat ii neliniare
Ordin de
convergent  a
Falsa pozit ie
Metoda secantei
Metoda lui Newton
Metoda
aproximat iilor
succesive
R ad acini multiple
Ecuat ii algebrice
Sisteme neliniare
Metode
quasi-Newton
Interpolare liniar a
Metode de modicare
Interpolare invers a
Metode hibride
BibliograeIterat ii, convergent  a  si ecient  a
INici chiar cele mai simple ecuat ii – de exemplu cele
algebrice – nu admit solut ii care s a e exprimabile prin
expresii rat ionale sau radicali.
IDin acest motiv este imposibil, ^ n general, s a calcul am
r ad acinile ecuat iilor neliniare printr-un num ar nit de
operat ii aritmetice. Este nevoie de o metod a iterativ a,
adic a de o procedur a care genereaz a o secvent  a innit a
de aproximat iifxngn2Nastfel ^ nc^ at
lim
n!¥xn=a, (2)
unde aeste o r ad acin a a ecuat iei.
I^In cazul unui sistem xk siasunt vectori de dimensiune
adecvat a, iar convergent a trebuie ^ nt eleas a ^ n sensul
convergent ei pe componente.
I^In practic a, ceea ce se dore ste este o convergent  a
rapid a.

Rezolvarea
numeric a a
ecuat iilor neliniare
Radu Tr ^ mbit a s
Ecuat ii neliniare
Ordin de
convergent  a
Falsa pozit ie
Metoda secantei
Metoda lui Newton
Metoda
aproximat iilor
succesive
R ad acini multiple
Ecuat ii algebrice
Sisteme neliniare
Metode
quasi-Newton
Interpolare liniar a
Metode de modicare
Interpolare invers a
Metode hibride
BibliograeOrdinul de convergent  a I
Conceptul de baz a pentru m asurarea vitezei de convergent  a
este ordinul de convergent  a.
Denit ia 1
Spunem c a xnconverge c atre a(cel put in) liniar dac a
jxnajen (3)
undefengeste un  sir pozitiv ce satisface
lim
n!¥en+1
en=c, 0<c<1. (4)
Dac a (3)  si (4) au loc cu egalitate ^ n (3) atunci cse
nume ste eroare asimptotic a.
IExpresia ,,cel put in\ ^ n aceast a denit ie se leag a de
faptul c a avem doar inegalitate ^ n (3), ceea ce dorim ^ n
practic a.

Rezolvarea
numeric a a
ecuat iilor neliniare
Radu Tr ^ mbit a s
Ecuat ii neliniare
Ordin de
convergent  a
Falsa pozit ie
Metoda secantei
Metoda lui Newton
Metoda
aproximat iilor
succesive
R ad acini multiple
Ecuat ii algebrice
Sisteme neliniare
Metode
quasi-Newton
Interpolare liniar a
Metode de modicare
Interpolare invers a
Metode hibride
BibliograeOrdinul de convergent  a II
IDe fapt, strict vorbind, marginea enconverge liniar,
^ nsemn^ and c a, ^ n nal (pentru nsucient de mare)
ecare din aceste margini ale erorii este aproximativ o
fract ie constant a din precedenta.
Denit ia 2
Se spune c a xnconverge c atre a(cel put in) cu ordinul p1
dac a (3) are loc cu
lim
n!¥en+1
ep
n=c,c>0 (5)
IAstfel convergent a de ordinul 1 coincide cu convergent a
liniar a, ^ n timp ce convergent a de ordinul p>1 este
mai rapid a.

Rezolvarea
numeric a a
ecuat iilor neliniare
Radu Tr ^ mbit a s
Ecuat ii neliniare
Ordin de
convergent  a
Falsa pozit ie
Metoda secantei
Metoda lui Newton
Metoda
aproximat iilor
succesive
R ad acini multiple
Ecuat ii algebrice
Sisteme neliniare
Metode
quasi-Newton
Interpolare liniar a
Metode de modicare
Interpolare invers a
Metode hibride
BibliograeOrdinul de convergent  a III
IDe notat c a ^ n acest ultim caz nu se pune nici o
restrict ie asupra constantei c: odat a ce eneste sucient
de mic, exponentul pva avea grij a de convergent  a. S i
^ n acest caz, dac a avem egalitate ^ n (3), cse nume ste
eroare asimptotic a .
IAcelea si denit ii se aplic a  si  sirurilor vectoriale, cu
modulul ^ nlocuit cu orice norm a vectorial a.
IClasicarea convergent ei ^ n raport cu ordinul este destul
de rudimentar a, deoarece sunt tipuri de convergent  a la
care denit iile (1)  si (2) nu se aplic a. Astfel, un  sir feng
poate converge c atre zero mai ^ ncet dec^ at liniar, de
exemplu dac a c=1 ^ n (4). Acest tip de convergent  a se
nume ste subliniar a . La fel, c=0 ^ n (4) conduce la
convergent  a superliniar a , dac a (5) nu are loc pentru nici
unp>1.

Rezolvarea
numeric a a
ecuat iilor neliniare
Radu Tr ^ mbit a s
Ecuat ii neliniare
Ordin de
convergent  a
Falsa pozit ie
Metoda secantei
Metoda lui Newton
Metoda
aproximat iilor
succesive
R ad acini multiple
Ecuat ii algebrice
Sisteme neliniare
Metode
quasi-Newton
Interpolare liniar a
Metode de modicare
Interpolare invers a
Metode hibride
BibliograeOrdinul de convergent  a IV
IEste instructiv s a examin am comportarea lui en, dac a ^ n
loc de relat ia la limit a avem egalitate pentru un anumit
n, s a zicem
en+1
ep
n=c,n=n0,n0+1,n0+2,. . . (6)
IPentru n0sucient de mare, relat ia (6) este aproape
adev arat a. Printr-o simpl a induct ie se obt ine c a
en0+k=cpk1
p1epk
n0,k=0, 1, 2, . . ., (7)
care desigur are loc pentru p>1, dar  si pentru p=1
c^ and p#1:
en0+k=cken0,k=0, 1, 2, . . .,(p=1)(8)

Rezolvarea
numeric a a
ecuat iilor neliniare
Radu Tr ^ mbit a s
Ecuat ii neliniare
Ordin de
convergent  a
Falsa pozit ie
Metoda secantei
Metoda lui Newton
Metoda
aproximat iilor
succesive
R ad acini multiple
Ecuat ii algebrice
Sisteme neliniare
Metode
quasi-Newton
Interpolare liniar a
Metode de modicare
Interpolare invers a
Metode hibride
BibliograeOrdinul de convergent  a V
IPresupun^ and c a en0este sucient de mare astfel ^ nc^ at
aproximarea xn0are un num ar de zecimale corecte,
scriem en0+k=10dken0.
IAtunci dk, ^ n conformitate cu (3) reprezint a num arul
suplimentar de cifre zecimale corecte din aproximat ia
xn0+k( ^ n contrast cu xn0). Logaritm^ and (7)  si (8)
obt inem
dk=(
klog1
c, dac a p=1
pkh
1pk
p1log1
c+ (1pk)log1
en0i
, dac a p>1
IDeci c^ and k!¥
dkc1k(p=1),dkcppk(p>1), (9)

Rezolvarea
numeric a a
ecuat iilor neliniare
Radu Tr ^ mbit a s
Ecuat ii neliniare
Ordin de
convergent  a
Falsa pozit ie
Metoda secantei
Metoda lui Newton
Metoda
aproximat iilor
succesive
R ad acini multiple
Ecuat ii algebrice
Sisteme neliniare
Metode
quasi-Newton
Interpolare liniar a
Metode de modicare
Interpolare invers a
Metode hibride
BibliograeOrdinul de convergent  a VI
unde c1=log1
c>0, dac a p=1  si
cp=1
p1log1
c+log1
en0
(presupunem c a n0este sucient de mare  si deci en0
sucient de mic, pentru a avea cp>0).
IAceasta ne arat a c a num arul de cifre zecimale corecte
cre ste liniar odat a cu kc^ and p=1, dar exponent ial
c^ and p>1.^In ultimul caz dk+1/dkp^ nseamn a c a
(pentru kmare) num arul de cifre zecimale corecte
cre ste, pe iterat ie, cu un factor p.
IDac a ecare iterat ie necesit a munit at i de lucru (o
,,unitate de lucru" este efortul necesar pentru a calcula
o valoare a funct iei sau a unei anumite derivate a sa),
atunci indicele de ecient  a al iterat iei poate  denit
prin
lim
k!¥[dk+1/dk]1/m=p1/m.

Rezolvarea
numeric a a
ecuat iilor neliniare
Radu Tr ^ mbit a s
Ecuat ii neliniare
Ordin de
convergent  a
Falsa pozit ie
Metoda secantei
Metoda lui Newton
Metoda
aproximat iilor
succesive
R ad acini multiple
Ecuat ii algebrice
Sisteme neliniare
Metode
quasi-Newton
Interpolare liniar a
Metode de modicare
Interpolare invers a
Metode hibride
BibliograeOrdinul de convergent  a VII
IAceasta ne d a o baz a comun a de comparare ^ ntre
diversele metode iterative. Metodele liniare au indicele
de ecient  a 1.

Rezolvarea
numeric a a
ecuat iilor neliniare
Radu Tr ^ mbit a s
Ecuat ii neliniare
Ordin de
convergent  a
Falsa pozit ie
Metoda secantei
Metoda lui Newton
Metoda
aproximat iilor
succesive
R ad acini multiple
Ecuat ii algebrice
Sisteme neliniare
Metode
quasi-Newton
Interpolare liniar a
Metode de modicare
Interpolare invers a
Metode hibride
BibliograeCriteriul de oprire I
ICalculele practice necesit a o regul a de oprire care s a
termine iterat ia atunci c^ and s-a obt inut (sau se crede c a
s-a obt inut) precizia dorit a.
IIdeal, ne oprim atunci c^ and kxnak<tol,toldat.
IDeoarece anu este cunoscut se obi snuie ste s a se
^ nlocuiasc a xnacuxnxn1 si se impune cerint a ca
kxnxn1ktol (10)
unde
tol=kxnk#r+#a (11)
cu#r,#avalori date ale erorii.
ICa o m asur a de sigurant  a, am putea cere ca (10) s a
aib a loc pentru mai multe valori consecutive ale lui n,
nu doar pentru una singur a.

Rezolvarea
numeric a a
ecuat iilor neliniare
Radu Tr ^ mbit a s
Ecuat ii neliniare
Ordin de
convergent  a
Falsa pozit ie
Metoda secantei
Metoda lui Newton
Metoda
aproximat iilor
succesive
R ad acini multiple
Ecuat ii algebrice
Sisteme neliniare
Metode
quasi-Newton
Interpolare liniar a
Metode de modicare
Interpolare invers a
Metode hibride
BibliograeCriteriul de oprire II
IAleg^ and #r=0 sau #a=0 se obt ine un test de eroare
absolut a sau relativ a. Este totu si prudent s a utiliz am un
test mixt, cum ar , s a zicem #r=#a=#. Atunci, dac a
kxnkeste mic sau moderat de mare, se controleaz a
efectiv eroarea absolut a, ^ n timp ce pentru kxnkfoarte
mare se controleaz a eroarea relativ a.
ITestele de mai sus se pot combina cu jjf(x)jj#.^In
algoritmii din acest capitol vom presupune c a avem o
funct ie critoprire care implementeaz a testul de oprire.

Rezolvarea
numeric a a
ecuat iilor neliniare
Radu Tr ^ mbit a s
Ecuat ii neliniare
Ordin de
convergent  a
Falsa pozit ie
Metoda secantei
Metoda lui Newton
Metoda
aproximat iilor
succesive
R ad acini multiple
Ecuat ii algebrice
Sisteme neliniare
Metode
quasi-Newton
Interpolare liniar a
Metode de modicare
Interpolare invers a
Metode hibride
BibliograeMetoda falsei pozit ii
ICa ^ n metoda ^ njum at at irii, presupunem c a avem dou a
numere a<bastfel ^ nc^ at
f2C[a,b],f(a)f(b)<0 (12)
 si gener am un  sir descendent de intervale [an,bn],
n=1, 2, 3, . . .cua1=a,b1=bastfel ^ nc^ at
f(an)f(bn)<0.
ISpre deosebire de metoda ^ njum at at irii, pentru a
determina urm atorul interval nu lu am mijlocul lui
[an,bn], ci solut ia x=xna ecuat iei liniare
(L1f)(x;an,bn) = 0.
IAceasta pare s a e o alegere mai
exibil a dec^ at ^ n
metoda ^ njum at at irii deoarece xnva  mai apropiat de
cap atul ^ n carejfjeste mai mic (Vezi gura 1)

Rezolvarea
numeric a a
ecuat iilor neliniare
Radu Tr ^ mbit a s
Ecuat ii neliniare
Ordin de
convergent  a
Falsa pozit ie
Metoda secantei
Metoda lui Newton
Metoda
aproximat iilor
succesive
R ad acini multiple
Ecuat ii algebrice
Sisteme neliniare
Metode
quasi-Newton
Interpolare liniar a
Metode de modicare
Interpolare invers a
Metode hibride
BibliograeMetoda falsei pozit ii – algoritmul
Procedura decurge dup a cum urmeaz a:
forn:=1, 2,. . .do
xn:=ananbn
f(an)f(bn)f(an);
iff(an)f(xn)>0then
an+1:=xn;bn+1:=bn;
else
an+1:=an;bn+1:=xn;
end if
end for
Iterat ia se poate termina c^ and min (xnan,bnxn)tol,
unde toleste o valoare dat a.

Rezolvarea
numeric a a
ecuat iilor neliniare
Radu Tr ^ mbit a s
Ecuat ii neliniare
Ordin de
convergent  a
Falsa pozit ie
Metoda secantei
Metoda lui Newton
Metoda
aproximat iilor
succesive
R ad acini multiple
Ecuat ii algebrice
Sisteme neliniare
Metode
quasi-Newton
Interpolare liniar a
Metode de modicare
Interpolare invers a
Metode hibride
BibliograeMetoda falsei pozit ii – convergent a I
IConvergent a se analizeaz a mai u sor dac a presupunem
c afeste convex a sau concav a pe [a,b]. Dac a feste
convex a, avem
f00(x)>0,×2[a,b],f(a)<0,f(b)>0. (13)
IS irul
xn+1=xnxnb
f(xn)f(b)f(xn),n2N,x1=a
(14)
este monoton cresc ator  si m arginit superior de a, deci
convergent c atre o limit a x, iarf(x) = 0.
IViteza de convergent  a se determin a sc az^ and adin ambii
membri ai lui (14)  si utiliz^ and faptul c a f(a) = 0:
xn+1a=xnaxnb
f(xn)f(b)[f(xn)f(a)].

Rezolvarea
numeric a a
ecuat iilor neliniare
Radu Tr ^ mbit a s
Ecuat ii neliniare
Ordin de
convergent  a
Falsa pozit ie
Metoda secantei
Metoda lui Newton
Metoda
aproximat iilor
succesive
R ad acini multiple
Ecuat ii algebrice
Sisteme neliniare
Metode
quasi-Newton
Interpolare liniar a
Metode de modicare
Interpolare invers a
Metode hibride
BibliograeMetoda falsei pozit ii – convergent a II
I^Imp art ind cu xnaavem
xn+1a
xna=1xnb
f(xn)f(b)f(xn)f(a)
xna.
IF ac^ and n!¥ si utiliz^ and faptul c a xn!a, obt inem
lim
n!¥xn+1a
xna=1(ba)f0(a)
f(b). (15)
IDeci metoda converge liniar, cu eroarea asimptotic a
c=1(ba)f0(a)
f(b).
IDatorit a ipotezei convexit at ii avem c2(0, 1).
IAnalog se face demonstrat ia ^ n cazul c^ and feste
concav a.

Rezolvarea
numeric a a
ecuat iilor neliniare
Radu Tr ^ mbit a s
Ecuat ii neliniare
Ordin de
convergent  a
Falsa pozit ie
Metoda secantei
Metoda lui Newton
Metoda
aproximat iilor
succesive
R ad acini multiple
Ecuat ii algebrice
Sisteme neliniare
Metode
quasi-Newton
Interpolare liniar a
Metode de modicare
Interpolare invers a
Metode hibride
BibliograeMetoda falsei pozit ii – convergent a III
IDac a fnu este convex a sau concav a pe [a,b], ci
f2C2[a,b] sif00(a)6=0,f00are semn constant pe o
vecin atate a lui a si pentru un nsucient de mare xn
ajunge ^ n acea vecin atate  si se poate proceda ca mai
sus.
IDezavantaje. (i) Convergent a lent a; (ii) Faptul c a unul
din capete poate r am^ ane x. Dac a feste turtit a ^ n
vecin atatea r ad acinii  si aeste apropiat de a sib
dep artat convergent a poate  foarte lent a.

Rezolvarea
numeric a a
ecuat iilor neliniare
Radu Tr ^ mbit a s
Ecuat ii neliniare
Ordin de
convergent  a
Falsa pozit ie
Metoda secantei
Metoda lui Newton
Metoda
aproximat iilor
succesive
R ad acini multiple
Ecuat ii algebrice
Sisteme neliniare
Metode
quasi-Newton
Interpolare liniar a
Metode de modicare
Interpolare invers a
Metode hibride
Bibliograe
Figura: Metoda falsei pozit ii

Rezolvarea
numeric a a
ecuat iilor neliniare
Radu Tr ^ mbit a s
Ecuat ii neliniare
Ordin de
convergent  a
Falsa pozit ie
Metoda secantei
Metoda lui Newton
Metoda
aproximat iilor
succesive
R ad acini multiple
Ecuat ii algebrice
Sisteme neliniare
Metode
quasi-Newton
Interpolare liniar a
Metode de modicare
Interpolare invers a
Metode hibride
BibliograeMetoda secantei I
IEste o variant a a metodei falsei pozit ii, ^ n care nu se
mai cere ca fs a aib a valori de semne contrare, nici
m acar la capetele intervalului init ial.
ISe aleg dou a valori arbitrare de pornire x0,x1 si se
continu a cu
xn+1=xnxnxn1
f(xn)f(xn1)f(xn),n2N(16)
IAceasta pre ^ nt^ ampin a aparit ia unei false pozit ii  si
sugereaz a o convergent  a mai rapid a.
IDin p acate, nu mai are loc convergent a ,,global a\ pe
[a,b]ci doar convergent a ,,local a\, adic a numai dac a x0
 six1sunt sucient de apropiate de r ad acin a.
IVom avea nevoie de o relat ie ^ ntre trei erori consecutive

Rezolvarea
numeric a a
ecuat iilor neliniare
Radu Tr ^ mbit a s
Ecuat ii neliniare
Ordin de
convergent  a
Falsa pozit ie
Metoda secantei
Metoda lui Newton
Metoda
aproximat iilor
succesive
R ad acini multiple
Ecuat ii algebrice
Sisteme neliniare
Metode
quasi-Newton
Interpolare liniar a
Metode de modicare
Interpolare invers a
Metode hibride
BibliograeMetoda secantei II
xn+1a=xnaf(xn)
f[xn1,xn]
= (xna)
1f(xn)f(a)
(xna)f[xn1,xn]
= (xna)
1f[xn,a]
f[xn1,xn]
= (xna)f[xn1,xn]f[xn,a]
f[xn1,xn]
= (xna)(xn1a)f[xn,xn1,a]
f[xn1,xn].

Rezolvarea
numeric a a
ecuat iilor neliniare
Radu Tr ^ mbit a s
Ecuat ii neliniare
Ordin de
convergent  a
Falsa pozit ie
Metoda secantei
Metoda lui Newton
Metoda
aproximat iilor
succesive
R ad acini multiple
Ecuat ii algebrice
Sisteme neliniare
Metode
quasi-Newton
Interpolare liniar a
Metode de modicare
Interpolare invers a
Metode hibride
BibliograeMetoda secantei III
IDeci
(xn+1a) = ( xna)(xn1a)f[xn,xn1,a]
f[xn1,xn],n2N
(17)
IDin (17) rezult a imediat c a dac a aeste o r ad acin a
simpl a ( f(a) = 0,f0(a)6=0)  si xn!a si dac a f2C2
pe o vecin atate a lui a, convergent a este superliniar a.

Rezolvarea
numeric a a
ecuat iilor neliniare
Radu Tr ^ mbit a s
Ecuat ii neliniare
Ordin de
convergent  a
Falsa pozit ie
Metoda secantei
Metoda lui Newton
Metoda
aproximat iilor
succesive
R ad acini multiple
Ecuat ii algebrice
Sisteme neliniare
Metode
quasi-Newton
Interpolare liniar a
Metode de modicare
Interpolare invers a
Metode hibride
BibliograeOrdinul de convergent  a I
I^Inlocuim raportul diferent elor divizate din (17) cu o
constant a, ceea ce este aproape adev arat c^ and neste
mare. Pun^ and ek=jxkaj, avem
en+1=enen1C,C>0
I^Inmult ind ambii membri cu C si pun^ and En=Cen
obt inem
En+1=EnEn1,En!0.
ILogaritm^ and  si pun^ and yn=1
Enobt inem
yn+1=yn+yn1, (18)
care este recurent a pentru  sirul lui Fibonacci.

Rezolvarea
numeric a a
ecuat iilor neliniare
Radu Tr ^ mbit a s
Ecuat ii neliniare
Ordin de
convergent  a
Falsa pozit ie
Metoda secantei
Metoda lui Newton
Metoda
aproximat iilor
succesive
R ad acini multiple
Ecuat ii algebrice
Sisteme neliniare
Metode
quasi-Newton
Interpolare liniar a
Metode de modicare
Interpolare invers a
Metode hibride
BibliograeOrdinul de convergent  a II
ISolut ia este
yn=c1tn
1+c2tn
2,
c1,c2constante  si
t1=1
2(1+p
5), t2=1
2(1p
5).
IDeoarece yn!¥, avem c16=0  siync1tn
1, c aci
jt2j<1. Revenind la substitut ie1
Enec1tn
1,
1
enCec1tn
1 si deci
en+1
et1nCt1ec1tn
1t1
Cec1tn+1
1=Ct11,n!¥.
IOrdinul de convergent  a este
t1=1+p
5
21.61803 . . .(sect iunea de aur).

Rezolvarea
numeric a a
ecuat iilor neliniare
Radu Tr ^ mbit a s
Ecuat ii neliniare
Ordin de
convergent  a
Falsa pozit ie
Metoda secantei
Metoda lui Newton
Metoda
aproximat iilor
succesive
R ad acini multiple
Ecuat ii algebrice
Sisteme neliniare
Metode
quasi-Newton
Interpolare liniar a
Metode de modicare
Interpolare invers a
Metode hibride
BibliograeConvergent a metodei secantei I
Teorema 3
Fieaun zero simplu al lui f si e
I#=fx2R:jxaj<#g si presupunem c a f2C2[I#].
Denim pentru #sucient de mic
M(#) = max
s2I#
t2I#f00(s)
2f0(t). (19)
Presupunem c a
#M(#)<1 (20)
Atunci metoda secantei converge c atre r ad acina unic a a2I#
pentru orice valoare de pornire x06=x1cux02I#,x12I#.
Observat ia 4

Rezolvarea
numeric a a
ecuat iilor neliniare
Radu Tr ^ mbit a s
Ecuat ii neliniare
Ordin de
convergent  a
Falsa pozit ie
Metoda secantei
Metoda lui Newton
Metoda
aproximat iilor
succesive
R ad acini multiple
Ecuat ii algebrice
Sisteme neliniare
Metode
quasi-Newton
Interpolare liniar a
Metode de modicare
Interpolare invers a
Metode hibride
BibliograeConvergent a metodei secantei II
Se observ a c a lim
#!0M(#) =f00(a)
2f0(a)<¥, deci (20) poate
satisf acut a pentru #sucient de mic. Natura local a a
convergent ei este cuanticat a prin cerint a ca x0,x12I#.

Rezolvarea
numeric a a
ecuat iilor neliniare
Radu Tr ^ mbit a s
Ecuat ii neliniare
Ordin de
convergent  a
Falsa pozit ie
Metoda secantei
Metoda lui Newton
Metoda
aproximat iilor
succesive
R ad acini multiple
Ecuat ii algebrice
Sisteme neliniare
Metode
quasi-Newton
Interpolare liniar a
Metode de modicare
Interpolare invers a
Metode hibride
BibliograeDemonstrat ie – pasul I
Se observ a c a aeste singurul zero al lui f^ nI#. Aceasta
rezult a din formula lui Taylor pentru x=a:
f(x) =f(a) + ( xa)f0(a) +(xa)2
2f00(x)
unde f(a) = 0  six2(x,a)(sau(a,x)). Astfel dac a x2I#,
atunci  si x2I# si avem
f(x) = ( xa)f0(a)
1+xa
2f00(x)
f0(a)
Aici, dac a x6=a, tot i trei factorii sunt diferit i de 0, c aci
xa
2f00(x)
f0(a)#M(#)<1.
Deci fse poate anula pe I#numai ^ n x=a.

Rezolvarea
numeric a a
ecuat iilor neliniare
Radu Tr ^ mbit a s
Ecuat ii neliniare
Ordin de
convergent  a
Falsa pozit ie
Metoda secantei
Metoda lui Newton
Metoda
aproximat iilor
succesive
R ad acini multiple
Ecuat ii algebrice
Sisteme neliniare
Metode
quasi-Newton
Interpolare liniar a
Metode de modicare
Interpolare invers a
Metode hibride
BibliograeDemonstrat ie – pasul II
S a ar at am c a xn2I#pentru orice n, ^ n afar a de cazul c^ and
f(xn) = 0, ^ n care xn=a si metoda converge ^ ntr-un num ar
nit de pa si. Vom demonstra aceasta prin induct ie:
presupunem c a xn1,xn2I# sixn6=xn1. Acest lucru este
adev arat pentru n=1 din ipotez a.
Deoarece f2C2[I#]
f[xn1,xn] =f0(x1),f[xn1,xn,a] =1
2f00(x2),xi2I#,i=1, 2,
din (17) rezult a
jxn+1aj#2f00(xn)
2f0(x1)##M(#)<#,
adic a xn+12I#.

Rezolvarea
numeric a a
ecuat iilor neliniare
Radu Tr ^ mbit a s
Ecuat ii neliniare
Ordin de
convergent  a
Falsa pozit ie
Metoda secantei
Metoda lui Newton
Metoda
aproximat iilor
succesive
R ad acini multiple
Ecuat ii algebrice
Sisteme neliniare
Metode
quasi-Newton
Interpolare liniar a
Metode de modicare
Interpolare invers a
Metode hibride
BibliograeDemonstrat ie – pasul III
Convergent a . Mai mult, din relat ia ^ ntre trei erori
consecutive, (17), rezult a xn+16=xn^ n afar a de cazul c^ and
f(xn) = 0 ( si atunci xn=a). Utiliz^ and (17) avem
jxn+1ajjxnaj#M(#)
care aplicat a repetat ne d a
jxn+1ajjxnaj#M(#)


 [#M(#)]n1jx1aj.
Cum #M(#)<1, rezult a c a metoda este convergent a  si
xn!ac^ and n!¥.

Rezolvarea
numeric a a
ecuat iilor neliniare
Radu Tr ^ mbit a s
Ecuat ii neliniare
Ordin de
convergent  a
Falsa pozit ie
Metoda secantei
Metoda lui Newton
Metoda
aproximat iilor
succesive
R ad acini multiple
Ecuat ii algebrice
Sisteme neliniare
Metode
quasi-Newton
Interpolare liniar a
Metode de modicare
Interpolare invers a
Metode hibride
BibliograeAlgoritmul
Deoarece este nevoie de o singur a evaluare a lui fpe pas,
indicele de ecient  a este p=1+p
5
21.61803 . . ..
Figura: Ilustrarea metodei secantei

Rezolvarea
numeric a a
ecuat iilor neliniare
Radu Tr ^ mbit a s
Ecuat ii neliniare
Ordin de
convergent  a
Falsa pozit ie
Metoda secantei
Metoda lui Newton
Metoda
aproximat iilor
succesive
R ad acini multiple
Ecuat ii algebrice
Sisteme neliniare
Metode
quasi-Newton
Interpolare liniar a
Metode de modicare
Interpolare invers a
Metode hibride
BibliograeAlgoritmul ^ n pseudocod
Intrare: Funct ia f, valorile de pornire x0 six1, numarul
maxim de iterat ii, Nmax , informat ii de tolerant  a tol
Ie sire: O aproximat ie a r ad acinii sau un mesaj de eroare
1:xc:=x1; xv=x0;
2:fc:=f(x1); fv:=f(x0);
3:fork:=1toNmax do
4: xn:=xcfc(xcxv)/(fcfv);
5: ifcritoprire (tol)then
6: return xn;fSuccesg
7: end if
8: xv:=xc;fv:=fc;xc:=xn;fc=f(xn);
9:end for
10:error ("S-a dep a sit num arul de iterat ii").

Rezolvarea
numeric a a
ecuat iilor neliniare
Radu Tr ^ mbit a s
Ecuat ii neliniare
Ordin de
convergent  a
Falsa pozit ie
Metoda secantei
Metoda lui Newton
Metoda
aproximat iilor
succesive
R ad acini multiple
Ecuat ii algebrice
Sisteme neliniare
Metode
quasi-Newton
Interpolare liniar a
Metode de modicare
Interpolare invers a
Metode hibride
BibliograeMetoda lui Newton I
IPoate  privit a ca un caz la limit a al metodei secantei,
c^ and xn1!xn:
xn+1=xnf(xn)
f0(xn)(21)
IAlt a interpretare: liniarizarea ecuat iei f(x) = 0 ^ n
x=xn(vezi gura 3)
f(x)(T1f)(x) =f(xn) + ( xxn)f0(xn) = 0.
IAstfel, metoda lui Newton se poate generaliza la ecuat ii
neliniare de toate tipurile (sisteme neliniare, ecuat ii
funct ionale, caz ^ n care f0trebuie ^ nt eleas a ca derivat a
Fr echet), iar iterat ia este
xn+1=xn[f0(xn)]1f(xn). (22)

Rezolvarea
numeric a a
ecuat iilor neliniare
Radu Tr ^ mbit a s
Ecuat ii neliniare
Ordin de
convergent  a
Falsa pozit ie
Metoda secantei
Metoda lui Newton
Metoda
aproximat iilor
succesive
R ad acini multiple
Ecuat ii algebrice
Sisteme neliniare
Metode
quasi-Newton
Interpolare liniar a
Metode de modicare
Interpolare invers a
Metode hibride
BibliograeMetoda lui Newton II
IStudiul erorii ^ n metoda lui Newton este la fel ca cel al
erorii ^ n metoda secantei
xn+1a=xnaf(xn)
f0(xn)
= (xna)
1f(xn)f(a)
(xna)f0(xn)
= (xna)
1f[xn,a]
f[xn,xn]
= (xna)2f[xn,xn,a]
f[xn,xn](23)
IDe aceea, dac a xn!a, atunci
lim
n!¥xn+1a
(xna)2=f00(a)
2f0(a)
 si ordinul de convergent  a al metodei lui Newton este 2
dac a f00(a)6=0.

Rezolvarea
numeric a a
ecuat iilor neliniare
Radu Tr ^ mbit a s
Ecuat ii neliniare
Ordin de
convergent  a
Falsa pozit ie
Metoda secantei
Metoda lui Newton
Metoda
aproximat iilor
succesive
R ad acini multiple
Ecuat ii algebrice
Sisteme neliniare
Metode
quasi-Newton
Interpolare liniar a
Metode de modicare
Interpolare invers a
Metode hibride
BibliograeInterpretarea geometric a a metodei lui Newton
Figura: Metoda lui Newton

Rezolvarea
numeric a a
ecuat iilor neliniare
Radu Tr ^ mbit a s
Ecuat ii neliniare
Ordin de
convergent  a
Falsa pozit ie
Metoda secantei
Metoda lui Newton
Metoda
aproximat iilor
succesive
R ad acini multiple
Ecuat ii algebrice
Sisteme neliniare
Metode
quasi-Newton
Interpolare liniar a
Metode de modicare
Interpolare invers a
Metode hibride
BibliograeConvergent a
Referitor la convergent a local a a metodei lui Newton avem
Teorema 5
Fieao r ad acin a simpl a a ecuat iei f(x) = 0 si
I#=fx2R:jxaj#g. Presupunem c a f2C2[I#].
Denim
M(#) = max
s2I#
t2I#f00(s)
2f0(t)(24)
Dac a #este sucient de mic astfel ^ nc^ at
2#M(#)<1, (25)
atunci pentru orice x02I#, metoda lui Newton este bine
denit a  si converge p atratic c atre singura r ad acin a a2I#.
Demonstrat ia: ca la secant a.

Rezolvarea
numeric a a
ecuat iilor neliniare
Radu Tr ^ mbit a s
Ecuat ii neliniare
Ordin de
convergent  a
Falsa pozit ie
Metoda secantei
Metoda lui Newton
Metoda
aproximat iilor
succesive
R ad acini multiple
Ecuat ii algebrice
Sisteme neliniare
Metode
quasi-Newton
Interpolare liniar a
Metode de modicare
Interpolare invers a
Metode hibride
BibliograeCriteriul de oprire I
Criteriul de oprire pentru metoda lui Newton
jxnxn1j<#
se bazeaz a pe urm atoarea propozit ie:
Propozit ia 6
Fie(xn) sirul de aproximante generat prin metoda lui
Newton. Dac a aeste o r ad acin a simpl a din [a,b],
f2C2[a,b] si metoda este convergent a, atunci exist a un
n02Nastfel ^ nc^ at
jxnajjxnxn1j, n>n0.
Demonstrat ie. Vom ar ata ^ nt^ ai c a
jxnaj1
m1jf(xn)j, m1inf
x2[a,b]jf0(x)j. (26)

Rezolvarea
numeric a a
ecuat iilor neliniare
Radu Tr ^ mbit a s
Ecuat ii neliniare
Ordin de
convergent  a
Falsa pozit ie
Metoda secantei
Metoda lui Newton
Metoda
aproximat iilor
succesive
R ad acini multiple
Ecuat ii algebrice
Sisteme neliniare
Metode
quasi-Newton
Interpolare liniar a
Metode de modicare
Interpolare invers a
Metode hibride
BibliograeCriteriul de oprire II
Utiliz^ and teorema lui Lagrange,
f(a)f(xn) =f0(x)(axn), cux2(a,xn)(sau(xn,a)).
Din relat iile f(a) = 0  sijf0(x)jm1pentru x2(a,b)
rezult a c ajf(xn)jm1jaxnj, adic a chiar (26).
Pe baza formulei lui Taylor avem
f(xn) =f(xn1) + (xnxn1)f0(xn1) +1
2(xnxn1)2f00(m),
(27)
cum2(xn1,xn)saum2(xn,xn1).
T in^ and cont de modul de obt inere a unei aproximat ii de
metoda lui Newton, avem
f(xn1) + ( xnxn1)f0(xn1) = 0  si din (27) se obt ine
jf(xn)j=1
2(xnxn1)2jf00(m)j1
2(xnxn1)2kf00k¥,

Rezolvarea
numeric a a
ecuat iilor neliniare
Radu Tr ^ mbit a s
Ecuat ii neliniare
Ordin de
convergent  a
Falsa pozit ie
Metoda secantei
Metoda lui Newton
Metoda
aproximat iilor
succesive
R ad acini multiple
Ecuat ii algebrice
Sisteme neliniare
Metode
quasi-Newton
Interpolare liniar a
Metode de modicare
Interpolare invers a
Metode hibride
BibliograeCriteriul de oprire III
iar pe baza formulei (26) rezult a c a
jaxnjkf00k¥
2m1(xnxn1)2.
Cum am presupus c a metoda este convergent a, exist a un n0
natural cu proprietatea c a
kf00k¥
2m1(xnxn1)<1, n>n0
 si deci
jxnajjxnxn1j, n>n0.

Rezolvarea
numeric a a
ecuat iilor neliniare
Radu Tr ^ mbit a s
Ecuat ii neliniare
Ordin de
convergent  a
Falsa pozit ie
Metoda secantei
Metoda lui Newton
Metoda
aproximat iilor
succesive
R ad acini multiple
Ecuat ii algebrice
Sisteme neliniare
Metode
quasi-Newton
Interpolare liniar a
Metode de modicare
Interpolare invers a
Metode hibride
BibliograeAlegerea valorii de pornire
IAlegerea valorii de pornire este, ^ n general, o problem a
dicil a.
I^In practic a, se alege o valoare, iar dac a dup a un num ar
maxim xat de iterat ii nu s-a obt inut precizia dorit a,
testat a prin unul din criteriile uzuale, se ^ ncearc a cu alt a
valoare de pornire.
ICriterii
Criteriul 1 dac a r ad acina este izolat a ^ ntr-un interval
[a,b] sif00(x)6=0,×2(a,b), un criteriu
de alegere este f(x0)f00(x0)>0.
Criteriul 2 dac a feste convex a sau concav a pe [a,b],
f(a)f(b)<0  si tangentele ^ n capete
intersecteaz a Ox^ n (a,b), orice valoare x0
se poate alege ca valoare de pornire.

Rezolvarea
numeric a a
ecuat iilor neliniare
Radu Tr ^ mbit a s
Ecuat ii neliniare
Ordin de
convergent  a
Falsa pozit ie
Metoda secantei
Metoda lui Newton
Metoda
aproximat iilor
succesive
R ad acini multiple
Ecuat ii algebrice
Sisteme neliniare
Metode
quasi-Newton
Interpolare liniar a
Metode de modicare
Interpolare invers a
Metode hibride
BibliograeAlgoritmul ^ n pseudocod
Intrare: Funct ia f, derivata f0, valoarea de pornire x0,
numarul maxim de iterat ii, Nmax , informat ii de
tolerant  a tol
Ie sire: O aproximat ie a r ad acinii sau un mesaj de eroare
1:fork:=0toNmax do
2: xk+1:=xkf(xk)
f0(xk);
3: ifcritoprire (tol)then
4: return xk+1;fSuccesg
5: end if
6:end for
7:error ("S-a dep a sit num arul de iterat ii").

Rezolvarea
numeric a a
ecuat iilor neliniare
Radu Tr ^ mbit a s
Ecuat ii neliniare
Ordin de
convergent  a
Falsa pozit ie
Metoda secantei
Metoda lui Newton
Metoda
aproximat iilor
succesive
R ad acini multiple
Ecuat ii algebrice
Sisteme neliniare
Metode
quasi-Newton
Interpolare liniar a
Metode de modicare
Interpolare invers a
Metode hibride
BibliograeMetoda aproximat iilor succesive I
IAdesea, ^ n aplicat ii, ecuat iile neliniare apar sub forma
unei probleme de punct x: s a se determine xastfel
^ nc^ at
x=j(x). (28)
IUn num ar ace satisface aceast a ecuat ie se nume ste
punct x al lui j.
IOrice ecuat ie f(x) = 0 se poate scrie ( ^ n multe moduri
diferite) ^ n forma echivalent a (28). De exemplu, dac a
f0(x)6=0, ^ n intervalul de interes putem lua
j(x) =xf(x)
f0(x). (29)

Rezolvarea
numeric a a
ecuat iilor neliniare
Radu Tr ^ mbit a s
Ecuat ii neliniare
Ordin de
convergent  a
Falsa pozit ie
Metoda secantei
Metoda lui Newton
Metoda
aproximat iilor
succesive
R ad acini multiple
Ecuat ii algebrice
Sisteme neliniare
Metode
quasi-Newton
Interpolare liniar a
Metode de modicare
Interpolare invers a
Metode hibride
BibliograeMetoda aproximat iilor succesive II
IDac a x0este o aproximat ie init ial a a unui punct x aa
lui (28) atunci metoda aproximat iilor succesive
genereaz a un  sir de aproximat ii
xn+1=j(xn). (30)
IDac a acest  sir converge  si jeste continu a, atunci  sirul
converge c atre un punct x a lui j.
IDe notat c a (30) este chiar metoda lui Newton dac a j
este dat a de (29). Astfel metoda lui Newton poate
privit a ca o iterat ie de tip punct x, dar nu  si metoda
secantei.
IPentru o iterat ie de forma (30), presupun^ and c a xn!a
c^ and n!¥, ordinul de convergent  a este u sor de
determinat.

Rezolvarea
numeric a a
ecuat iilor neliniare
Radu Tr ^ mbit a s
Ecuat ii neliniare
Ordin de
convergent  a
Falsa pozit ie
Metoda secantei
Metoda lui Newton
Metoda
aproximat iilor
succesive
R ad acini multiple
Ecuat ii algebrice
Sisteme neliniare
Metode
quasi-Newton
Interpolare liniar a
Metode de modicare
Interpolare invers a
Metode hibride
BibliograeMetoda aproximat iilor succesive III
IS a presupunem c a ^ n punctul x aavem
j0(a) =j00(a) =


=j(p1)(a) = 0,jp(a)6=0
(31)
IPresupunem c a j2Cppe o vecin atate Va luia.
Avem atunci, conform teoremei lui Taylor
j(xn) =j(a)+(xna)j0(a)+. . .+(xna)p1
(p1)!j(p1)(a)
+(xna)p
p!j(p)(xn) =j(a) +(xna)p
p!j(p)(xn),
unde xn2(a,xn)(sau(xn,a)).
IDeoarece j(xn) =xn+1 sij(a) =aobt inem
xn+1a
(xna)p=1
p!j(p)(xn).

Rezolvarea
numeric a a
ecuat iilor neliniare
Radu Tr ^ mbit a s
Ecuat ii neliniare
Ordin de
convergent  a
Falsa pozit ie
Metoda secantei
Metoda lui Newton
Metoda
aproximat iilor
succesive
R ad acini multiple
Ecuat ii algebrice
Sisteme neliniare
Metode
quasi-Newton
Interpolare liniar a
Metode de modicare
Interpolare invers a
Metode hibride
BibliograeMetoda aproximat iilor succesive IV
IC^ and xn!a, deoarece xneste ^ ntre xn sia, deducem
pe baza continuit at ii c a
limn!¥xn+1a
(xna)p=1
p!j(p)(a)6=0. (32)
IAceasta ne arat a c a ordinul de convergent  a este exact p
 si eroarea asimptotic a este
c=1
p!j(p)(a). (33)
ICombin^ and aceasta cu condit ia uzual a de convergent  a
local a se obt ine:

Rezolvarea
numeric a a
ecuat iilor neliniare
Radu Tr ^ mbit a s
Ecuat ii neliniare
Ordin de
convergent  a
Falsa pozit ie
Metoda secantei
Metoda lui Newton
Metoda
aproximat iilor
succesive
R ad acini multiple
Ecuat ii algebrice
Sisteme neliniare
Metode
quasi-Newton
Interpolare liniar a
Metode de modicare
Interpolare invers a
Metode hibride
BibliograeMetoda aproximat iilor succesive V
Teorema 7
Fieaun punct x al lui j siI#=fx2R:jxaj#g.
Presupunem c a j2Cp[I#] si satisface (31). Dac a
M(#):=max
t2I#jj0(t)j<1 (34)
atunci iterat ia (30) converge c atre a,8x02I#. Ordinul de
convergent  a este p, iar eroarea asimptotic a este dat a de (33).

Rezolvarea
numeric a a
ecuat iilor neliniare
Radu Tr ^ mbit a s
Ecuat ii neliniare
Ordin de
convergent  a
Falsa pozit ie
Metoda secantei
Metoda lui Newton
Metoda
aproximat iilor
succesive
R ad acini multiple
Ecuat ii algebrice
Sisteme neliniare
Metode
quasi-Newton
Interpolare liniar a
Metode de modicare
Interpolare invers a
Metode hibride
BibliograeInterpretarea geometrica a metodei aproximat iilor
succesive
Convergent a

Rezolvarea
numeric a a
ecuat iilor neliniare
Radu Tr ^ mbit a s
Ecuat ii neliniare
Ordin de
convergent  a
Falsa pozit ie
Metoda secantei
Metoda lui Newton
Metoda
aproximat iilor
succesive
R ad acini multiple
Ecuat ii algebrice
Sisteme neliniare
Metode
quasi-Newton
Interpolare liniar a
Metode de modicare
Interpolare invers a
Metode hibride
BibliograeInterpretarea geometrica a metodei aproximat iilor
succesive
Divergent a

Rezolvarea
numeric a a
ecuat iilor neliniare
Radu Tr ^ mbit a s
Ecuat ii neliniare
Ordin de
convergent  a
Falsa pozit ie
Metoda secantei
Metoda lui Newton
Metoda
aproximat iilor
succesive
R ad acini multiple
Ecuat ii algebrice
Sisteme neliniare
Metode
quasi-Newton
Interpolare liniar a
Metode de modicare
Interpolare invers a
Metode hibride
BibliograeMetoda lui Newton pentru r ad acini multiple I
IDac a aeste o r ad acin a multipl a de ordinul m, atunci
ordinul de convergent  a a metodei lui Newton este doar
1.^Intr-adev ar, e
j(x) =xf(x)
f0(x).
IDeoarece
j0(x) =f(x)f00(x)
[f0(x)]2
procesul va  convergent dac a j0(a) = 11/m<1.

Rezolvarea
numeric a a
ecuat iilor neliniare
Radu Tr ^ mbit a s
Ecuat ii neliniare
Ordin de
convergent  a
Falsa pozit ie
Metoda secantei
Metoda lui Newton
Metoda
aproximat iilor
succesive
R ad acini multiple
Ecuat ii algebrice
Sisteme neliniare
Metode
quasi-Newton
Interpolare liniar a
Metode de modicare
Interpolare invers a
Metode hibride
BibliograeMetoda lui Newton pentru r ad acini multiple II
IO modalitate de a evita aceasta este s a rezolv am
ecuat ia
u(x):=f(x)
f0(x)=0
care are acelea si r ad acini ca  si f, dar simple. Metoda lui
Newton pentru problema modicat a are forma
xk+1=xku(xk)
u0(xk)=f(xk)f0(xk)
[f0(xk)]2f(xk)f00(xk). (35)
IDeoarece aeste o r ad acin a simpl a a lui u, convergent a
lui (35) este p atratic a. Singurul dezavantaj teoretic al
lui (35) este derivata a doua necesar a suplimentar  si
complexitatea mai mare a calculului lui xk+1dinxk.^In
practic a aceasta este o sl abiciune, deoarece numitorul
lui (35) poate lua valori foarte mici ^ n vecin atatea lui a
c^ and xk!a.

Rezolvarea
numeric a a
ecuat iilor neliniare
Radu Tr ^ mbit a s
Ecuat ii neliniare
Ordin de
convergent  a
Falsa pozit ie
Metoda secantei
Metoda lui Newton
Metoda
aproximat iilor
succesive
R ad acini multiple
Ecuat ii algebrice
Sisteme neliniare
Metode
quasi-Newton
Interpolare liniar a
Metode de modicare
Interpolare invers a
Metode hibride
BibliograeMetoda lui Newton pentru r ad acini multiple III
IConvergent a p atratic a a metodei lui Newton se poate
realiza nu numai prin modicarea problemei ci  si prin
modicarea metodei. ^In vecin atatea unei solut ii multiple
de ordinul m,a, avem
f(x) = ( xa)mj(x)(xa)m
c, (36)
de unde rezult a
f(x)
f0(x)xa
m)axmf(x)
f0(x).
IMetoda modicat a corespunz atoare
xk+1:=xkmf(xk)
f0(xk), k=0, 1, 2, . . . (37)
converge p atratic c atre r ad acina multipl a de ordinul m
c^ and se ^ ntrebuint eaz a o valoare corect a a lui m^ n (37).

Rezolvarea
numeric a a
ecuat iilor neliniare
Radu Tr ^ mbit a s
Ecuat ii neliniare
Ordin de
convergent  a
Falsa pozit ie
Metoda secantei
Metoda lui Newton
Metoda
aproximat iilor
succesive
R ad acini multiple
Ecuat ii algebrice
Sisteme neliniare
Metode
quasi-Newton
Interpolare liniar a
Metode de modicare
Interpolare invers a
Metode hibride
BibliograeMetoda lui Newton pentru r ad acini multiple IV
IEcient a variantei (37) a metodei lui Newton depinde
de utilizarea unei valori de aproximare bune pentru m,
dac a aceast a valoare nu este cunoscut a din alte surse.
^In ipoteza
jxkaj<jxk1aj^jxkaj<jxk2aj
putem ^ nlocui ^ n (36) aprinxk
f(xk1)(xk1xk)m
c
f(xk2)(xk2xk)m
c.
I^In continuare se obt ine m:
mlog[f(xk1)/f(xk2)]
log[(xk1xk)/(xk2xk)].
Aceast a valoare poate  utilizat a ^ n (37).

Rezolvarea
numeric a a
ecuat iilor neliniare
Radu Tr ^ mbit a s
Ecuat ii neliniare
Ordin de
convergent  a
Falsa pozit ie
Metoda secantei
Metoda lui Newton
Metoda
aproximat iilor
succesive
R ad acini multiple
Ecuat ii algebrice
Sisteme neliniare
Metode
quasi-Newton
Interpolare liniar a
Metode de modicare
Interpolare invers a
Metode hibride
BibliograeEcuat ii algebrice I
IExist a multe metode special concepute pentru a rezolva
ecuat ii algebrice.
IAici vom descrie numai metoda lui Newton aplicat a ^ n
acest context, concentr^ andu-ne asupra unui mod
ecient de a evalua simultan valoarea polinomului  si a
primei derivate.
IConsider am o ecuat ie algebric a de grad d
f(x) = 0,f(x) =xd+ad1xd1+


+a0, (38)
^ n care coecientul dominant se presupune (f ar a a
restr^ ange generalitatea) a  egal cu 1  si unde putem
presupune, f ar a a restr^ ange generalitatea c a a06=0.
IPentru simplitate vom presupune c a tot i coecient ii
sunt reali.

Rezolvarea
numeric a a
ecuat iilor neliniare
Radu Tr ^ mbit a s
Ecuat ii neliniare
Ordin de
convergent  a
Falsa pozit ie
Metoda secantei
Metoda lui Newton
Metoda
aproximat iilor
succesive
R ad acini multiple
Ecuat ii algebrice
Sisteme neliniare
Metode
quasi-Newton
Interpolare liniar a
Metode de modicare
Interpolare invers a
Metode hibride
BibliograeEcuat ii algebrice II
IPentru a aplica metoda lui Newton ecuat iei (38) este
nevoie de o metod a bun a de evaluare a polinomului  si
derivatei. Schema lui Horner este potrivit a pentru a sa
ceva:
bd:=1;cd:=1;
fork=d1downto 1do
bk:=tbk+1+ak;
ck:=tck+1+bk;
end for
b0:=tb1+a0;
IAtunci f(t) =b0,f0(t) =c1.
IDeci proced am astfel:
ISe aplic a metoda lui Newton, calcul^ and simultan f(xn)
 sif0(xn)
xn+1=xnf(xn)
f0(xn).

Rezolvarea
numeric a a
ecuat iilor neliniare
Radu Tr ^ mbit a s
Ecuat ii neliniare
Ordin de
convergent  a
Falsa pozit ie
Metoda secantei
Metoda lui Newton
Metoda
aproximat iilor
succesive
R ad acini multiple
Ecuat ii algebrice
Sisteme neliniare
Metode
quasi-Newton
Interpolare liniar a
Metode de modicare
Interpolare invers a
Metode hibride
BibliograeEcuat ii algebrice III
ISe aplic a apoi metoda lui Newton polinomuluif(x)
xa.
IPentru r ad acini complexe se ^ ncepe cu x0complex  si
toate calculele se fac ^ n aritmetic a complex a.
IEste posibil s a se ^ mpart a cu factori p atratici  si s a se
foloseasc a aritmetica real a { metoda lui Bairstow.
IFolosind metoda aceasta de sc adere a gradului erorile
pot  mari.
IO modalitate de ^ mbun at at ire este de a utiliza r ad acinile
astfel calculate ca aproximat ii init iale  si a aplica metoda
lui Newton polinomului original.

Rezolvarea
numeric a a
ecuat iilor neliniare
Radu Tr ^ mbit a s
Ecuat ii neliniare
Ordin de
convergent  a
Falsa pozit ie
Metoda secantei
Metoda lui Newton
Metoda
aproximat iilor
succesive
R ad acini multiple
Ecuat ii algebrice
Sisteme neliniare
Metode
quasi-Newton
Interpolare liniar a
Metode de modicare
Interpolare invers a
Metode hibride
BibliograeMetoda lui Newton pentru sisteme neliniare I
IMetoda lui Newton este u sor de generalizat la sisteme
neliniare
F(x) = 0, (39)
unde F:WRn!Rn, iarx,F(x)2Rn.
ISistemul (39) se scrie pe componente
8
><
>:F1(x1,. . .,xn) = 0
…
Fn(x1,. . .,xn) = 0
IFieF0(k))jacobianul lui F^ nx(k):
J:=F0(k)) =2
64¶F1
¶x1(x(k)). . .¶F1
¶xn(x(k))
………
¶Fn
¶x1(x(k)). . .¶Fn
¶xn(x(k))3
75. (40)

Rezolvarea
numeric a a
ecuat iilor neliniare
Radu Tr ^ mbit a s
Ecuat ii neliniare
Ordin de
convergent  a
Falsa pozit ie
Metoda secantei
Metoda lui Newton
Metoda
aproximat iilor
succesive
R ad acini multiple
Ecuat ii algebrice
Sisteme neliniare
Metode
quasi-Newton
Interpolare liniar a
Metode de modicare
Interpolare invers a
Metode hibride
BibliograeMetoda lui Newton pentru sisteme neliniare II
ICantitatea 1 /f0(x)se ^ nlocuie ste ^ n acest caz cu inversa
jacobianului ^ n x(k):
x(k+1)=x(k)[F0(x(k))]1F(x(k)). (41)
IScriem iterat ia sub forma
x(k+1)=x(k)+w(k). (42)
Se observ a c a wkeste solut ia sistemului de necuat ii
liniare cu nnecunoscute
F0
x(k)
w(k)=F(x(k)). (43)
IEste mai ecient  si mai convenabil ca, ^ n loc s a
invers am jacobianul la ecare pas, s a rezolv am sistemul
(43)  si s a folosim iterat ia ^ n forma (42).

Rezolvarea
numeric a a
ecuat iilor neliniare
Radu Tr ^ mbit a s
Ecuat ii neliniare
Ordin de
convergent  a
Falsa pozit ie
Metoda secantei
Metoda lui Newton
Metoda
aproximat iilor
succesive
R ad acini multiple
Ecuat ii algebrice
Sisteme neliniare
Metode
quasi-Newton
Interpolare liniar a
Metode de modicare
Interpolare invers a
Metode hibride
BibliograeMetoda lui Newton pentru sisteme neliniare III
Teorema 8
Fieao solut ie a ecuat iei F(x) = 0 si presupunem c a ^ n bila
^ nchis a B(d)fx:kxakdg, exist a matricea Jacobi a
luiF:Rn!Rn, este nesingular a  si satisface condit ia
Lipschitz
kF0(x)F0(y)k¥ckxyk¥,8x,y2B(d),c>0.
Punem g=cmaxk[F0(x)]1k¥:kaxk¥d
 si
0<#<minfd,g1g. Atunci pentru orice aproximat ie
init ial a x(0)2B(#):=fx:kxak¥#gmetoda lui
Newton este convergent a, iar vectorii e(k):=ax(k)
satisfac urm atoarele inegalit at i:
(a)ke(k+1)k¥gke(k)k2
¥
(b)ke(k)k¥g1(gke(0)k¥)2k.

Rezolvarea
numeric a a
ecuat iilor neliniare
Radu Tr ^ mbit a s
Ecuat ii neliniare
Ordin de
convergent  a
Falsa pozit ie
Metoda secantei
Metoda lui Newton
Metoda
aproximat iilor
succesive
R ad acini multiple
Ecuat ii algebrice
Sisteme neliniare
Metode
quasi-Newton
Interpolare liniar a
Metode de modicare
Interpolare invers a
Metode hibride
BibliograeMetoda lui Newton pentru sisteme neliniare IV
Demonstrat ie. Dac a F0este continu a pe segmentul ce
une ste punctele x,y2Rn, conform teoremei lui Lagrange
F(x)F(y) =Jk(xy),
unde
Jk=2
64¶F1
¶x1(x1). . .¶F1
¶xn(x1)
………
¶Fn
¶x1(xn). . .¶Fn
¶xn(xn)3
75)
e(k+1)=e(k)[F0(x(k))]1(F(a)F(x(k)))
=e(k)[F0(x(k))]1Jke(k)
= [F0(x(k))]1(F0(x(k))Jk)e(k)

Rezolvarea
numeric a a
ecuat iilor neliniare
Radu Tr ^ mbit a s
Ecuat ii neliniare
Ordin de
convergent  a
Falsa pozit ie
Metoda secantei
Metoda lui Newton
Metoda
aproximat iilor
succesive
R ad acini multiple
Ecuat ii algebrice
Sisteme neliniare
Metode
quasi-Newton
Interpolare liniar a
Metode de modicare
Interpolare invers a
Metode hibride
BibliograeMetoda lui Newton pentru sisteme neliniare V
 si de aici rezult a imediat (a). Din condit ia Lipschitz
kF0(x(k))Jkk¥cmax
j=1,nkx(k)x(j)kckx(k)ak
Deci, dac akax(k)k¥#, atunci
kax(k+1)k¥(g#)##.
Deoarece (a) este adev arat a pentru orice k, se obt ine (b)
imediat.

Rezolvarea
numeric a a
ecuat iilor neliniare
Radu Tr ^ mbit a s
Ecuat ii neliniare
Ordin de
convergent  a
Falsa pozit ie
Metoda secantei
Metoda lui Newton
Metoda
aproximat iilor
succesive
R ad acini multiple
Ecuat ii algebrice
Sisteme neliniare
Metode
quasi-Newton
Interpolare liniar a
Metode de modicare
Interpolare invers a
Metode hibride
BibliograeMetoda lui Newton – pseudocod
Intrare: Funct ia F, derivata Fr echet F0, vectorul de pornire
x(0), numarul maxim de iterat ii, Nmax , informat ii de
tolerant  a tol
Ie sire: O aproximat ie a r ad acinii sau un mesaj de eroare
1:fork:=0toNmax do
2: Calculeaz a matricea jacobian J=F0(x(k));
3: Rezolv a sistemul Jw=F(x(k));
4: x(k+1):=x(k)+w;
5: ifcritoprire (tol)then
6: return x(k+1);fSuccesg
7: end if
8:end for
9:error ("S-a dep a sit num arul de iterat ii").

Rezolvarea
numeric a a
ecuat iilor neliniare
Radu Tr ^ mbit a s
Ecuat ii neliniare
Ordin de
convergent  a
Falsa pozit ie
Metoda secantei
Metoda lui Newton
Metoda
aproximat iilor
succesive
R ad acini multiple
Ecuat ii algebrice
Sisteme neliniare
Metode
quasi-Newton
Interpolare liniar a
Metode de modicare
Interpolare invers a
Metode hibride
BibliograeMetode quasi-Newton I
IO sl abiciune semnicativ a a metodei lui Newton pentru
rezolvarea sistemelor de ecuat ii neliniare este necesitatea
ca la ecare pas s a calcul am matricea jacobian a  si s a
rezolv am un sistem nncu aceast a matrice.
IPentru a ilustra dimensiunile unei astfel de slabiciuni, s a
evalu am volumul de calcule asociat cu o iterat ie a
metodei lui Newton. Matricea jacobian a asociat a unui
sistem de necuat ii neliniare scris ^ n forma F(x) = 0
necesit a evaluarea celor n2derivate part iale ale celor n
funct ii componente ale lui F.^In cele mai multe situat ii,
evaluarea exact a a derivatelor part iale este
neconvenabil a  si de multe ori imposibil a. Efortul total
pentru o iterat ie a metodei lui Newton va  de cel put in
n2+nevalu ari de funct ii scalare ( n2pentru evaluarea
jacobianului  si npentru evaluarea lui F)  siO(n3)
operat ii aritmetice pentru a rezolva sistemul liniar.

Rezolvarea
numeric a a
ecuat iilor neliniare
Radu Tr ^ mbit a s
Ecuat ii neliniare
Ordin de
convergent  a
Falsa pozit ie
Metoda secantei
Metoda lui Newton
Metoda
aproximat iilor
succesive
R ad acini multiple
Ecuat ii algebrice
Sisteme neliniare
Metode
quasi-Newton
Interpolare liniar a
Metode de modicare
Interpolare invers a
Metode hibride
BibliograeMetode quasi-Newton II
Acest volum de calcule este prohibitiv, except^ and valori
mici ale lui n si funct ii scalare u sor de evaluat.
IEste resc ca atent ia s a e ^ ndreptat a spre reducerea
num arului de evalu ari  si evitarea rezolv arii unui sistem
liniar la ecare pas.
ILa metoda secantei aproximat ia urm atoare x(k+1)se
obt ine ca solut ie a ecuat iei liniare
¯`k=f(x(k)) + ( xx(k))f(x(k)+hk)f(x(k))
hk=0.
IAici funct ia ¯`kpoate  interpretat a ^ n dou a moduri:
1. ca aproximare a ecuat ie tangentei
`k(x) =f(x(k)) + ( xx(k))f0
x(k)
;
2. ca interpolare liniar a ^ ntre punctele x(k) six(k+1).

Rezolvarea
numeric a a
ecuat iilor neliniare
Radu Tr ^ mbit a s
Ecuat ii neliniare
Ordin de
convergent  a
Falsa pozit ie
Metoda secantei
Metoda lui Newton
Metoda
aproximat iilor
succesive
R ad acini multiple
Ecuat ii algebrice
Sisteme neliniare
Metode
quasi-Newton
Interpolare liniar a
Metode de modicare
Interpolare invers a
Metode hibride
BibliograeMetode quasi-Newton III
ISe pot obt ine diverse generaliz ari ale metodei secantei
la sisteme de ecuat ii neliniare ^ n funct ie de modul ^ n
care se interpreteaz a ¯`k.
IPrima interpretare conduce la metode de tip Newton
discretizate, iar a doua la metode bazate pe interpolare.
IMetodele de tip Newton discretizate se obt in dac a ^ n
metoda lui Newton (41) F0(x)se ^ nlocuie ste cu cu o
aproximare discret a A(x,h). Derivatele part iale din
matricea jacobian a (40) se vor ^ nlocui prin diferent ele
divizate
A(x,h)ei:= [F(x+hiei)F(x)]/hi, i=1,n,
(44)

Rezolvarea
numeric a a
ecuat iilor neliniare
Radu Tr ^ mbit a s
Ecuat ii neliniare
Ordin de
convergent  a
Falsa pozit ie
Metoda secantei
Metoda lui Newton
Metoda
aproximat iilor
succesive
R ad acini multiple
Ecuat ii algebrice
Sisteme neliniare
Metode
quasi-Newton
Interpolare liniar a
Metode de modicare
Interpolare invers a
Metode hibride
BibliograeMetode quasi-Newton IV
unde ei2Rneste al i-lea vector al bazei canonice  si
hi=hi(x)este m arimea pasului de discretizare. O
alegere posibil a a pasului este de exemplu
hi:=#jxij, dac a xi6=0;
#, altfel,
cu#:=peps, unde eps este epsilon-ul ma sinii.

Rezolvarea
numeric a a
ecuat iilor neliniare
Radu Tr ^ mbit a s
Ecuat ii neliniare
Ordin de
convergent  a
Falsa pozit ie
Metoda secantei
Metoda lui Newton
Metoda
aproximat iilor
succesive
R ad acini multiple
Ecuat ii algebrice
Sisteme neliniare
Metode
quasi-Newton
Interpolare liniar a
Metode de modicare
Interpolare invers a
Metode hibride
BibliograeInterpolare liniar a I
ILa interpolare ecare dintre planele tangente se
^ nlocuie ste cu un (hiper)plan care interpoleaz a funct iile
componente Fiale lui F^ nn+1 puncte date xk,j,
j=0,n, ^ ntr-o vecin atate a lui x(k), adic a se determina
vectorii a(i) si scalarii ai, astfel ^ nc^ at pentru
Li(x) =ai+a(i)Tx, i=1,n (45)
are loc
Li(xk,j) =Fi(xk,j), i=1,n,j=0,n.
IUrm atoarea aproximat ie x(k+1)se obt ine ca punct de
intersect ie ^ ntre cele nhiperplane (45) din Rn+1cu
hiperplanul y=0.x(k+1)rezult a ca solut ie a sistemului
de ecuat ii liniare
Li(x) = 0, i=1,n. (46)

Rezolvarea
numeric a a
ecuat iilor neliniare
Radu Tr ^ mbit a s
Ecuat ii neliniare
Ordin de
convergent  a
Falsa pozit ie
Metoda secantei
Metoda lui Newton
Metoda
aproximat iilor
succesive
R ad acini multiple
Ecuat ii algebrice
Sisteme neliniare
Metode
quasi-Newton
Interpolare liniar a
Metode de modicare
Interpolare invers a
Metode hibride
BibliograeInterpolare liniar a II
I^In funct ie de alegerea punctelor de interpolare se obt in
diferite metode, dintre care cele mai cunoscute sunt
metoda lui Brown  si metoda lui Brent.
IMetoda lui Brown combin a aproximarea lui F0 si
rezolvarea sistemului prin eliminare gaussian a.
I^In metoda lui Brent se ^ ntrebuint eaz a la rezolvarea
sistemului metoda QR. Ambele metode apart in unei
clase de metode, care, la fel ca metoda lui Newton,
converg p atratic, dar au nevoie doar de (n2+3n)/2
evalu ari de funct ii pe iterat ie.
I^Intr-un studiu comparativ, Mor e  si Cosnard [7] au ajuns
la concluzia c a metoda Brent este adeseori de preferat
metodei lui Brown  si c a pentru sisteme de ecuat ii
neliniare, la care evaluarea lui fnecesit a un efort mai
mic, metoda lui Newton discretizat a este cea mai
ecient a metod a de rezolvare.

Rezolvarea
numeric a a
ecuat iilor neliniare
Radu Tr ^ mbit a s
Ecuat ii neliniare
Ordin de
convergent  a
Falsa pozit ie
Metoda secantei
Metoda lui Newton
Metoda
aproximat iilor
succesive
R ad acini multiple
Ecuat ii algebrice
Sisteme neliniare
Metode
quasi-Newton
Interpolare liniar a
Metode de modicare
Interpolare invers a
Metode hibride
BibliograeMetode de modicare I
IDin punct de vedere al efortului de calcul, sunt deosebit
de convenabile metodele ^ n care la ecare pas se
^ ntrebuint eaz a o aproximare Aka lui F0(x(k)), care se
obt ine din Ak1printr-o modicare de rang 1, adic a
prin ad augarea unei matrice de rang 1:
Ak+1:=Ak+u(k)h
v(k)iT
,u(k),v(k)2Rn,k=0, 1, 2, . . .
IPe baza formulei Sherman-Morrison (vezi [4])

A+uvT1
=A11
1+vTA1uA1uvTA1
(47)
pentru Bk+1:=A1
k+1are loc relat ia de recurent  a
Bk+1=BkBku(k)h
v(k)iT
Bk
1+
v(k)TBku(k), k=0, 1, 2, . . .,

Rezolvarea
numeric a a
ecuat iilor neliniare
Radu Tr ^ mbit a s
Ecuat ii neliniare
Ordin de
convergent  a
Falsa pozit ie
Metoda secantei
Metoda lui Newton
Metoda
aproximat iilor
succesive
R ad acini multiple
Ecuat ii algebrice
Sisteme neliniare
Metode
quasi-Newton
Interpolare liniar a
Metode de modicare
Interpolare invers a
Metode hibride
BibliograeMetode de modicare II
at^ at timp c^ at 1 +h
v(k)iT
Bku(k)6=0.
INecesitatea rezolv arii unui sistem liniar la ecare pas
dispare; aceasta se ^ nlocuie ste cu ^ nmult iri
matrice-vector, ceea ce corespunde unei reduceri a
efortului de calcul de la O(n3)laO(n2).
IAcest avantaj va  pl atit prin aceea c a nu vom mai avea
o convergent a p atratic a ca la metoda lui Newton, ci
doar una superliniar a:
lim
k!¥kx(k+1)ak
kx(k)ak=0. (48)
I^Inmetoda lui Broyden alegerea vectorilor u(k) siv(k)
are loc dup a principiul aproximat iei secantei. ^In cazul
scalar aproximarea akf0
x(k)
se face unic prin
ak+1(x(k+1)x(k)) =f(x(k+1))f(x(k)).

Rezolvarea
numeric a a
ecuat iilor neliniare
Radu Tr ^ mbit a s
Ecuat ii neliniare
Ordin de
convergent  a
Falsa pozit ie
Metoda secantei
Metoda lui Newton
Metoda
aproximat iilor
succesive
R ad acini multiple
Ecuat ii algebrice
Sisteme neliniare
Metode
quasi-Newton
Interpolare liniar a
Metode de modicare
Interpolare invers a
Metode hibride
BibliograeMetode de modicare III
IPentru n>1, din contr a, aproximarea
Ak+1(x(k+1)x(k)) =F(x(k+1))F(x(k)) (49)
(a sa numita ecuat ie quasi-Newton) nu mai este unic
determinat a; orice alt a matrice de forma
¯Ak+1:=Ak+1+pqT
cup,q2Rn siqT(x(k+1)x(k)) = 0 veric a de
asemenea ecuat ia (49).
IPe de alt a parte,
yk:=F(x(k))F(x(k1)) sisk:=x(k)x(k1)
cont in numai informat ii despre variat ia lui F^ n direct ia
sk, dar nici o informat ie ^ n direct ii ortogonale pe sk.

Rezolvarea
numeric a a
ecuat iilor neliniare
Radu Tr ^ mbit a s
Ecuat ii neliniare
Ordin de
convergent  a
Falsa pozit ie
Metoda secantei
Metoda lui Newton
Metoda
aproximat iilor
succesive
R ad acini multiple
Ecuat ii algebrice
Sisteme neliniare
Metode
quasi-Newton
Interpolare liniar a
Metode de modicare
Interpolare invers a
Metode hibride
BibliograeMetode de modicare IV
IPe aceste direct ii trebuie ca efectul lui Ak+1 siAks a
coincid a
Ak+1q=Akq,8q2fv:v6=0,vTsk=0g. (50)
IPornind de la prima aproximare A0F0(0)), se
genereaz a  sirul A1,A2,. . .utiliz^ and formulele (49)  si
(50) (Broyden [2], Dennis  si Mor e [4]).
IPentru  sirul B0=A1
0[F(x(0))]1,B1,B2,. . .cu
ajutorul formulei Sherman-Morisson (47) se obt ine
relat ia de recurent  a
Bk+1:=Bk+(sk+1Bkyk+1)sT
k+1Bk
sT
k+1Bkyk+1, k=0, 1, 2, . . .
care cont ine doar ^ nmult iri matrice vector  si a c arei
complexitate este doar O(n2).

Rezolvarea
numeric a a
ecuat iilor neliniare
Radu Tr ^ mbit a s
Ecuat ii neliniare
Ordin de
convergent  a
Falsa pozit ie
Metoda secantei
Metoda lui Newton
Metoda
aproximat iilor
succesive
R ad acini multiple
Ecuat ii algebrice
Sisteme neliniare
Metode
quasi-Newton
Interpolare liniar a
Metode de modicare
Interpolare invers a
Metode hibride
BibliograeMetode de modicare V
ICu ajutorul matricelor Bkse poate deni metoda lui
Broyden prin
x(k+1):=x(k)BkF(x(k)), k=0, 1, 2, . . .
IAceast a metod a converge superliniar ^ n sensul lui (48),
dac a pa sii skse apropie asimptotic (c^ and k!¥) de
pa sii metodei lui Newton.
ISe poate recunoa ste ^ n aceasta semnicat ia central a a
principiului lineariz arii locale la rezolvarea ecuat iilor
neliniare.

Rezolvarea
numeric a a
ecuat iilor neliniare
Radu Tr ^ mbit a s
Ecuat ii neliniare
Ordin de
convergent  a
Falsa pozit ie
Metoda secantei
Metoda lui Newton
Metoda
aproximat iilor
succesive
R ad acini multiple
Ecuat ii algebrice
Sisteme neliniare
Metode
quasi-Newton
Interpolare liniar a
Metode de modicare
Interpolare invers a
Metode hibride
BibliograeMetoda lui Broyden
Intrare: F, vectorul x(0),Nmax , tolerant a tol
Ie sire: O aproximat ie a r ad acinii sau un mesaj de eroare
B0:=F0(x(0));v:=F(x);B:=B1
0;
s:=Bv;x:=x+s;
fork:=1toNmax do
w:=v; v:=F(x); y:=vw;
z:=By;fz=Bk1ykg
p:=sTz;fp=sT
kBk1ykg
C:=pI+ (s+z)sT;
fC=sT
kB1
k1ykI+ (sk+Bk1yk)sT
kg
B:= (1/p)CB;fB=Bkg
s:=Bv;fs=BkF(x(k))g
x:=x+s;
ifcritoprire (tol)then
return x;fsuccesg
end if
end for
error ("S-a dep a sit num arul maxim de iterat ii")

Rezolvarea
numeric a a
ecuat iilor neliniare
Radu Tr ^ mbit a s
Ecuat ii neliniare
Ordin de
convergent  a
Falsa pozit ie
Metoda secantei
Metoda lui Newton
Metoda
aproximat iilor
succesive
R ad acini multiple
Ecuat ii algebrice
Sisteme neliniare
Metode
quasi-Newton
Interpolare liniar a
Metode de modicare
Interpolare invers a
Metode hibride
BibliograeInterpolare invers a I
IDac a feste inversabil a pe o vecin atate Va luia sig
este inversa sa ( g=f1), atunci
f(a) = 0=)a=g(0).
IInterpolarea invers a const a ^ n aproximarea lui g(0)prin
valoarea unui polinom de interpolare de grad mic.
IDac a aproxim am gprin polinomul s au Taylor de grad 1,
avem
g(y)(T1g)(y) =g(yn) + ( yyn)g0(yn).
IDac a yn=f(xn), t in^ and cont c a g0(yn) =1
f0(xn), se
obt ine
g(0)xnf(xn)
f0(xn)=:xn+1,
adic a metoda lui Newton! ^Incercat i s a obt inet i metoda
corespunz atoare pentru T2g.

Rezolvarea
numeric a a
ecuat iilor neliniare
Radu Tr ^ mbit a s
Ecuat ii neliniare
Ordin de
convergent  a
Falsa pozit ie
Metoda secantei
Metoda lui Newton
Metoda
aproximat iilor
succesive
R ad acini multiple
Ecuat ii algebrice
Sisteme neliniare
Metode
quasi-Newton
Interpolare liniar a
Metode de modicare
Interpolare invers a
Metode hibride
BibliograeInterpolare invers a II
IDac a lu am gL1g, avem
g(y)(L1g)(y) =g(yn) +g[yn,yn1](yyn).
IT in^ and cont c a
g[yn,yn1] =g(yn)g(yn1)
ynyn1=xnxn1
f(xn)f(xn1),
se obt ine
g(0)xnxnxn1
f(xn)f(xn1)f(xn),
adic a metoda secantei.

Rezolvarea
numeric a a
ecuat iilor neliniare
Radu Tr ^ mbit a s
Ecuat ii neliniare
Ordin de
convergent  a
Falsa pozit ie
Metoda secantei
Metoda lui Newton
Metoda
aproximat iilor
succesive
R ad acini multiple
Ecuat ii algebrice
Sisteme neliniare
Metode
quasi-Newton
Interpolare liniar a
Metode de modicare
Interpolare invers a
Metode hibride
BibliograeMetode hibride
IAceste metode combin a metodele cu convergent  a
global a, dar mai lente, cu metode cu convergent  a local a
(de exemplu, Newton sau secant a).
IDe asemenea, se utilizeaz a scheme adaptive de
monitorizare a iterat iilor  si de testare a condit iilor de
oprire.
IUna dintre cele mai cunoscute metode de acest tip este
algoritmul lui Dekker, ^ n varianta lui Brent, cunoscut  si
sub numele de algoritmul Dekker-Brent sauzeroin
[6],[8].
IEl combin a metoda ^ njum at at irii cu metoda secantei  si
cu metoda interpol arii inverse p atratice (IQI).
IFunct ia MATLAB fzero se bazeaz a pe acest algoritm.

Rezolvarea
numeric a a
ecuat iilor neliniare
Radu Tr ^ mbit a s
Ecuat ii neliniare
Ordin de
convergent  a
Falsa pozit ie
Metoda secantei
Metoda lui Newton
Metoda
aproximat iilor
succesive
R ad acini multiple
Ecuat ii algebrice
Sisteme neliniare
Metode
quasi-Newton
Interpolare liniar a
Metode de modicare
Interpolare invers a
Metode hibride
BibliograeDescrierea algoritmului
ISe ^ ncepe cu a sibastfel ^ nc^ at f(a) sif(b)au semne
opuse.
ISe utilizeaz a un pas al metodei secantei pentru a obt ine
c^ ntre a sib.
ISe repet a pa sii urm atori p^ an a c^ and jbaj<#jbjsau
f(b) = 0
ISe permut a a,b,castfel ^ nc^ at
If(b) sif(a)au semne opuse
Ijf(b)jj f(a)j
Iceste valoarea precedent a a lui b.
IDac a c6=ase realizeaz a un pas IQI, altfel un pas al
metodei secantei.
IDac a rezultatul pasului IQI sau secantei este ^ n [a,b], se
accept a
IDac a nu, ^ njum at at ire.

Rezolvarea
numeric a a
ecuat iilor neliniare
Radu Tr ^ mbit a s
Ecuat ii neliniare
Ordin de
convergent  a
Falsa pozit ie
Metoda secantei
Metoda lui Newton
Metoda
aproximat iilor
succesive
R ad acini multiple
Ecuat ii algebrice
Sisteme neliniare
Metode
quasi-Newton
Interpolare liniar a
Metode de modicare
Interpolare invers a
Metode hibride
BibliograeBibliograe I
Octavian Agratini, Ioana Chiorean, Gheorghe Coman,
Tr ^ mbit a s Radu, Analiz a numeric a  si teoria aproxim arii ,
vol. III, Presa Universitar a Clujean a, 2002, coordonatori
D. D. Stancu  si Gh. Coman.
C. G. Broyden, A Class of Methods for Solving
Nonlinear Simultaneous Equations, Math. Comp. 19
(1965), 577{593.
Gheorghe Coman, Analiz a numeric a , Editura Libris,
Cluj-Napoca, 1995.
J. E. Dennis, J. J. Mor e, Quasi-Newton Metods,
Motivation and Theory, SIAM Review 19(1977), 46{89.
W. Gautschi, Numerical Analysis. An Introduction ,
Birkh auser, Basel, 1997.

Rezolvarea
numeric a a
ecuat iilor neliniare
Radu Tr ^ mbit a s
Ecuat ii neliniare
Ordin de
convergent  a
Falsa pozit ie
Metoda secantei
Metoda lui Newton
Metoda
aproximat iilor
succesive
R ad acini multiple
Ecuat ii algebrice
Sisteme neliniare
Metode
quasi-Newton
Interpolare liniar a
Metode de modicare
Interpolare invers a
Metode hibride
BibliograeBibliograe II
C. Moler, Numerical Computing in MATLAB , SIAM,
2004
J. J. Mor e, M. Y. Cosnard, Numerical Solutions of
Nonlinear Equations, ACM Trans. Math. Softw. 5
(1979), 64{85.
W. H. Press, S. A. Teukolsky, W. T. Vetterling, B. P.
Flannery, Numerical Recipes in C , Cambridge University
Press, Cambridge, New York, Port Chester, Melbourne,
Sidney, 1996, disponibila prin
www, http://www.nr.com/ .
J. Stoer, R. Bulirsch, Introduction to Numerical
Analysis , 2nd ed., Springer Verlag, 1992.