Exemplu de lucrare de licent˘ a - uav.ro · Referat privind lucrarea de licent˘a cu...

Universitatea ,,Aurel Vlaicu” din Arad

Facultatea de Stiinte Exacte

Specializarea Informatica

Lucrare de licenta

Exemplu de lucrare de licenta

Absolvent:Ion Ionescu

Coordonator:Prof. dr. Octavian Cira

Iulie 2011

Referat

privind lucrarea de licenta cu titlul

,,Exemplu de lucrare de licenta”ıntocmit de absolventul Ion Ionescu.

Lucrarea are 81 pagini si este organizata ın 6 capitole:

1. Introducere

2. Capitolul 1

3. Capitolul 2

4. Capitolul 3

5. Concluzii

6. Anexa

Din punct de vedere al continutului si al prezentarii, lucrarea ıntrunestetoate conditiile cerute de o lucrare de licenta la specializarea Informatica dincadrul Facultatii de Stiinte Exacte.

Avand ın vedere cele de mai sus, recomand sustinerea publica a lucrariide licenta cu titlul ,,Exemplu de lucrare de licenta”, ıntocmita de absolventIon Ionescu, ın sesiunea din iulie 2010 si propun acordarea notei . . . . . . .

ARAD, 14 noiembrie 2010

Prof. dr. Octavian Cira

2

Cuprins

1 Elemente de analiza 71.1 Elemente de algebra liniara . . . . . . . . . . . . . . . . . . . 7

1.1.1 Polinom caracteristic . . . . . . . . . . . . . . . . . . . 71.1.2 Valori si vectori proprii . . . . . . . . . . . . . . . . . . 9

1.2 Elemente de analiza n-dimensionala . . . . . . . . . . . . . . . 161.3 Ordin de convergenta ın R . . . . . . . . . . . . . . . . . . . . 241.4 Ordin de convergenta ın Rn . . . . . . . . . . . . . . . . . . . 26

1.4.1 Q-ordinul de convergenta . . . . . . . . . . . . . . . . . 261.4.2 R–ordinul de convergenta . . . . . . . . . . . . . . . . 291.4.3 Relatii ıntre ordine de convergenta . . . . . . . . . . . 31

2 Metode numerice pentru ecuatii neliniare ın Rn 342.1 Metoda Newton . . . . . . . . . . . . . . . . . . . . . . . . . . 34

2.1.1 Constructia metodei Newton . . . . . . . . . . . . . . . 342.1.2 Convergenta metodei Newton . . . . . . . . . . . . . . 352.1.3 Programe pentru metoda Newton . . . . . . . . . . . . 422.1.4 Alegerea iteratiei initiale . . . . . . . . . . . . . . . . . 432.1.5 Bazinul de atratie pentru metoda Newton . . . . . . . 45

2.2 Metoda secantei si metoda Steffensen . . . . . . . . . . . . . . 462.2.1 Metoda secantei . . . . . . . . . . . . . . . . . . . . . . 462.2.2 Constructia metodei secantei si a metodei Steffensen . 482.2.3 Convergenta metodelor secantei si Steffensen . . . . . . 492.2.4 Programe pentru metoda secantei . . . . . . . . . . . . 522.2.5 Programe pentru metoda Steffensen . . . . . . . . . . . 53

2.3 Metode cvasi-Newton . . . . . . . . . . . . . . . . . . . . . . . 542.3.1 Leme preliminare . . . . . . . . . . . . . . . . . . . . . 542.3.2 Constructia metodei Broyden . . . . . . . . . . . . . . 592.3.3 Convergenta metodei Broyden . . . . . . . . . . . . . . 622.3.4 Programe pentru metoda Broyden . . . . . . . . . . . . 69

3 Bazine de atractie 72

3

Lista de figuri

1.1 Functia Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271.2 Functia R . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 301.3 Functia R si Q . . . . . . . . . . . . . . . . . . . . . . . . . . 32

2.1 Functia g(x) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

3.1 Bazinul de atractie pentru metoda Newton. . . . . . . . . . . . 733.2 Bazinul de atractie pentru metoda Broyden . . . . . . . . . . . 733.3 Bazinul de atractie pentru metoda Steffensen . . . . . . . . . . 74

4

Introducere

In lucrarea de fata sunt tratate metode numerice pentru aproximareasolutiilor ecuatiilor neliniare din Rn si bazinele lor de atractie.

In literatura de specialitate se cunosc monografiile lui L. B. Rall [28], [29],[30], a lui J. M. Ortega si W. C. Rheinboldt [26] si [27], a lui J. F. Traubsi H. Wozniakowski [34], a lui J. E. Dennis Jr. si R. B. Schnabel [15], I. K.Argyros si F. Szidarovszky [1] iar ın Romania cartea lui St. Maruster [23]tiparita ın anul 1981 si volumul autorilor O. Cira si St. Maruster [12] tiparitaın anul 2008. Alte lucrari ce au fost consultate sunt cele ale lui: Rheinboldt[31], Cuyt si Rall [13], Ypma [36].

Avand ın vedere progresele deosebite dupa 1990 ın demonstrarea conver-gentei metodelor de ordin superior cu teoreme de tip Ostrowski-Kantorovichsi dezvoltarea softurilor matematice ca: Mathemetica, [37], Mathcad, [38] siMatlab, [39]; ne-a determinat sa scriem aceasta lucrare. In toate aceste softuride calcul stiitific sunt implemtate, pentru rezolvarea numerica a ecuatiilorneliniare, metodele: metoda Newton, metoda Broyden si metoda Steffensen.

Pentru ecuatii neliniare din Rn (n > 1) s-au avutın vedere cea mai cunoscuta metoda numerica, metodaNewton cu teorema de convergenta a lui Kantorovich[21]. Teorema lui Kantorovich, publicat ın anul 1948,este rezultatul ce domina literatura de specialitate refer-itoare la rezolvarea numerica a ecuatiilor neliniare. Osubsectiune este alocata metodelor secantei si Steffensen.Prin doua articole, [4] si [5], Broyden demonstreazaconvergenta metodei cvasi-Newton, impusa mai tarziu, ınliteratura de specialitate, sub numele de metoda Broy-den. Aceasta metoda este una din cele mai folosite metode pentru rezolvareaecuatiilor neliniare.

Redactarea unui hypertext, atat de complex, s-a realizat cu ajutorulLATEX-ului. Avantajele hypertext-ului sunt urmatoarele: hypertext-ul, subformat pdf (printable document file), se poate citi cu ajutorul programului

5

Lucrare de licenta Ion Ionescu

Acrobat Reader ; pe langa salturile, printr-un simplu clic, la orice referintainterna sau referinta bibliografica din text, se mai pot face salturi cu aju-torul link -urilor externe la fisiere imagine realizate cu Mathcad -ul, la ar-ticole ,,free” de pe internet, citate ca atare ın bibliografie, sau la titlulsi rezumatul articolului din bazele de date ale portalurilor de specialitate(MathSciNet, links.jstor, portal.acm, SpringerLink, scitation.aip, ProjectEu-clid, etc). Aceste servicii de citire a hypertext-ului se pot realiza pe un calcu-lator legat la internet si cu Acrobat Reader -ul instalat (acest soft este free).

6

Capitolul 1

Elemente de analiza

1.1 Elemente de algebra liniara

1.1.1 Polinom caracteristic

Notam cu Mm,n(K) Mn,n multimea matricelor de dimensiune m × n cuelemente din corpul K.

Definitia 1.1.1. Fie A ∈Mn,n(R) cu n ≥ 1 o matrice data la care asociemmatricea B = A− x · I , unde B ∈Mn,n(R[x]) si I este matricea unitate dinMn,n(R). Polinomul PA(x) = det(B) ∈ R[x] se numeste polinomul caracter-istic al matricei A.

Observatia 1.1.1. Polinomul caracteristic pentru matrici particulare dinmultimea Mn,n(R).

1. Daca A ∈Mn,n(R), A = diag(d1, d2, . . . , dn) atunci

PA(x) = (−1)nn∏k=1

(x− dk)

2. Daca notam cu O matricea nula, O ∈Mn,n(R), atunci

PO(x) = (−1)n · xn

3. Daca notam cu I matricea identitate, I ∈Mn,n(R) atunci

PI(x) = (−1)n · (x− 1)n

7


4. Daca A ∈ Mn,n(R) este o matrice triunghiulara inferior (ak,j = 0pentru k < j, k, j ∈ In) atunci

PA(x) = (−1)nn∏k=1

(x− akk)

5. Daca A ∈ Mn,n(R) este o matrice triunghiulara superior (ak,j = 0pentru k > j, k, j ∈ In) atunci

PA(x) = (−1)nn∏k=1

(x− akk) .

Observatia 1.1.2. Pentru orice matrice A ∈Mn,n(R) PA(x) = det(A−x·I)rezulta ca PA(0) = det(A), de unde avem ca matricea A este singulara dacasi numai daca 0 este radacina a polinomului caracteristic PA(x).

Propozitia 1.1.1. Fie A ∈Mn,n(R), A = (akj), k, j ∈ In si polinomul saucaracteristic PA ∈ R[x], atunci:

(a) grad(PA) = n si PAT(x) = PA(x);

(b) Daca PA(x) = αnxn + αn−1x

n−1 + · · · + α1x + α0, atunci avem αn =(−1)n, αn−1 = (−1)n−1tr(A) si α0 = det(A).

unde tr(A) = a11 + a22 + · · ·+ ann este urma matricei A.

Demonstratie. (a) Evident grad(PA) = n. Notam cu I matricea unitate dinmultimea Mn,n(R) atunci AT − x · I = (A− x · I)T de unde rezulta

PAT(x) = det(AT − x · I

)= det (A− x · I) = PA(x)

(b) PA(x) = det(A− x · I) = (a11 − x) (a22 − x) · · · (ann − x) +Qn−2(x) undeQn−2 este un polinom grad cel mult n− 2. Atunci

PA(x) = (−1)nxn + (−1)n−1(a11 + a22 + · · ·+ ann)xn−1 + · · ·+ α0

deci αn = (−1)n, αn−1 = (−1)n−1tr(A), iar α0 = PA(x) = det(A − 0 · I) =det(A).

Definitia 1.1.2. Fie A,B ∈Mn,n(R). Matricele A si B se numesc asemeneasi scriem A ∼ B daca exista T ∈ Mn,n(R), nesingulara astfel ıncat B =T−1 · A · T .

Lema 1.1.1. Fie A,B ∈Mn,n(R) si A ∼ B atunci PA = PB.

8

Ion Ionescu Lucrare de licenta

Demonstratie. Daca A ∼ B atunci exista T ∈ Mn,n(R), nesingulara astfelıncat B = T−1 · A · T atunci

PB(x) = det(B − x · I) = det(T−1 · A · T − x · I)

= det(T−1 · A · T − T−1 · (x · I) · T ) = det(T−1(A · T − (x · I) · T )

)= det(T−1(A− x · I) · T ) = det(T−1) · det(A− x · I) · det(T )

= det(T−1) · PA(x) · det(T ) = PA(x) .

1.1.2 Valori si vectori proprii

Fie R corpul numerelor reale si V un spatiu vectorial peste R si operatorulliniar (endomorfism) f : V → V .

Definitia 1.1.3. Un scalar λ ∈ R se numeste valoare proprie a lui f dacaoperatorul liniar g : V → V , g(x) = f(x)− λ · x nu este izomorfism.

Multimea σ(f) ⊂ C a tuturor valorilor proprii ale lui f se numeste spec-trul lui f, atunci subspatiul Vλ = Ker(g) ⊂ V se numeste subspatiulpropriu corespunzator valorii proprii λ, iar vectori nenuli din Vλ se numescvectori proprii ai lui f , corespunzand valorii proprii λ. Se numeste razaspectrala numarul pozitiv ρ = ρ(σ) = ρ(σ(f)) = max |λ| | λ ∈ σ(f).

Fie V si W doua spatii vectoriale peste R, finit dimensionale, dimR(V ) =n si dimR(W ) = m. Fixam o baza B1 = v1, v2, . . . , vn ın V si B2 =w1, w2, . . . , wm o baza a lui W . Fie f : V → W o aplicatie liniara, atunciputem sa scriem

f(v1) = a11w1 + a21w2 + . . .+ am1wmf(v2) = a12w1 + a22w2 + . . .+ am2wm

......

...f(vn) = a1nw1 + a2nw2 + . . .+ amnwm

sau mai concentrat

f(vj) =m∑k=1

ak,j · wk j ∈ In

unde ak,j ∈ R k ∈ In, j ∈ Im sunt unic determinati pentru cele doua bazefixate si pentru aplicatia f .

Definitia 1.1.4. Matricea A = Af = (ak,j) din Mn,m(R) se numeste ma-tricea asociata aplicatiei liniare f : V → W relativ la cele doua baze fixate.

9


In baza celor aratate multimea aplicatiilor liniare

L(Rn,Rm) = f | f : Rn → Rm

unde f este o aplicatie liniara, poate fi identificata printr-un izomorfism cumultimea matricelor Mn,m(R). Pentru matricea A ∈ Mn,n(R) se asociazaoperatorul f : Rn → Rn care ıi atribuie vectorului x ∈ Rn vectorul x · AT

adica f(x) = x · AT.Valorile proprii si vectori proprii pentru matricea A ∈Mn,n(R) sunt prin

definitie cele ale operatorului f . Fie λ ∈ R valoare proprie pentru matricea A⇔ exista vectorul x 6= 0 astfel ıncat f(x) = λx⇔ exista vectorul x 6= 0 astfelıncat x ·AT = λx ⇔ exista vectorul x 6= 0 astfel ıncat A · x = λx ⇔ sistemulliniar si omogen (A− λI)x = 0 admite solutii nebanale ⇔ det(A− λI) = 0.De unde putem trage concluzia ca un scalar λ ∈ R este valoare propriepentru o matrice A ∈Mn,n(R) daca si numai daca λ este radacina a ecuatieicaracteristice det(A− λI) = 0.

In continuare dam cateva propozitii fara demonstratie referitoare la pro-prietatiile valorilor si vectorilor proprii. Pentru demonstratii se poate con-sulta lucrarea [3].

Propozitia 1.1.2. Daca

PA(x) = (−1)n(x− λ1)n1(x− λ2)n2 . . . (x− λp)np ,

unde n1, n2, . . . , np sunt multiplicitatile valorilor λ1, λ2, . . . , λp ∈ C care suntdistincte doua cate doua si daca n1, n2, . . . , np sunt ıntregi ≥ 1 cu n1 + n2 +. . .+ np = n, atunci σ(A) = λ1, λ2, . . . , λp.

In cele ce urmeaza presupunem ca matricea A ∈ Mn,n(R) are n valoriproprii distincte doua cate doua.

Propozitia 1.1.3. O matrice A ∈Mn,n(R) si AT ∈Mn,n(R) au acelasi poli-nom caracteristic deci au acelasi valori proprii dar ın general nu au aceeasivectori proprii.

Exemplul 1.1.1. Fie matricea A ∈Mn,n(R)

A :=

1 −1 01 2 10 −1 1

atunci A si AT au aceleasi valori proprii

λ := eigenvals(A)→

1

3 + i√

7

23− i

√7

2

τ := eigenvals(AT)→

1

3 + i√

7

23− i

√7

2

10


iar vectori proprii sunt diferiti

v := eigenvecs(A)→

1

2

1

2

−√

2

2−1− i

√7

4

−1 + i√

7

40

1

2

1

2

√2

2

si

w := eigenvecs(AT)→

1

2

1

2

√2

21 + i

√7

4

1− i√

7

40

1

2

1

2

−√

2

2

.

Calculul simbolic al valorilor si vectorilor proprii s-au facut cu functiile Math-cad eigenvals si eigenvecs [10].

Propozitia 1.1.4. Suma valorilor proprii pentru matricea A ∈Mn,n(R) esteegala cu urma matricei A, iar produsul valorilor proprii este egal cu det(A)

n∑k=1

λk = tr(A) ,n∏k=1

λk = det(A) .

Exemplul 1.1.2. Pentru matricea A ∈Mn,n(R)

A :=

1 −1 01 2 10 −1 1

,

avem3∑

k=1

λk = 4 si tr(A) = 4 ,3∏

k=1

λk = 4 si |A| = 4 ,

unde s-au folosit functiile Mathcad tr pentru suma elementelor de pe diago-nala principala a unei matricii patrate si |·| pentru determinatul unei matricipatrate [10].

Propozitia 1.1.5. Fie A ∈Mn,n(R) atunci A este singulara daca si numaidaca 0 ∈ σ(A).

Propozitia 1.1.6. Fie A ∈Mn,n(R) si λ ∈ σ(A), λ 6= 0, atunci λk ∈ σ(Ak).

11


Definitia 1.1.5. Matricea A ∈ Mn,n(R) este diagonalizabila daca exista omatrice D ∈ Mn,n(R) diagonala, D = diag(d1, d2, . . . , dn) astfel ıncat A ∼D.

Aceasta definitie este echivalenta cu definitia.

Definitia 1.1.6. Matricea A ∈ Mn,n(R) este diagonalizabila daca exista omatrice T ∈ Mn,n(R) nesingulara astfel ıncat T−1 · A · T = D, unde Deste o matrice diagonala D = diag(d1, d2, . . . , dn), unde Dk,j = 0 pentruk ∈ In, j ∈ In si k 6= j, iar Dkk = dk pentru orice k = In.

Teorema 1.1.7 (Criteriul de diagonalizare). Fie spatiul vectorial Rn si omatrice A ∈Mn,n(R) cu polinomul caracteristic

PA(x) = (1−)n(x− λ1)n1(x− λ2)n2 . . . (x− λp)np

cu toti λk ∈ R unde nk ≥ 1 si n1 +n2 + . . .+np = n. Atunci sunt echivalenteurmatoarele conditii

(a) Matricea A este diagonalizabila;

(b) Exista o baza B ın Rn formata numai cu vectori proprii a matricei A;

(c) Spatiul liniar Rn este suma directa de subspatiile Rnλk

, k ∈ Ip;

(d) Dimensiunea subspatiilor Rnλk

este egala cu nk, k ∈ Ip.

Demonstratie. Vezi demonstratia teoremei 3.10 (criteriul de diagonalizare)[3, pag. 85].

Corolarul 1.1.8. Fie spatiul liniar Rn si o matrice A ∈Mn,n(R) cu polino-mul caracteristic

PA(x) = (1−)n(x− λ1)n1(x− λ2)n2 . . . (x− λp)np

cu toti λk ∈ C unde nk ≥ 1 si n1 + n2 + . . . + np = n. Daca toti nk suntegali cu 1, adica toate valorile proprii sunt radacini simple ale polinomuluicaracterisctic, atunci matricea A este diagonalizabila.

Demonstratie. Vezi demonstratia corolarului 1 din [3, pag. 86].

Lema 1.1.2 (Gerschgorin). Fie A = (ak,j) k, j ∈ In o matrice din Mn,n(R).Pentru orice k ∈ In, se noteaza

rk =n∑j=1j 6=k

|ak,j|

12


si fie discul Dk = D(akk, rk) = z| |z − akk| < rk, z ∈ R, atunci are locincluziunea

σ(A) ⊂n⋃k=1

Dk

Demonstratie. Fie λ ∈ σ(A) atunci exita un vector x ∈ Rn nenul x =(x1, x2, . . . , xn)T astfel ıncat A·x = λ·x. Fie |xk| = max |x1| , |x2| , . . . , |xn|,evident xk 6= 0. Ecuatia k din sistemul liniar A · x = λ · x este

ak1x1 + ak2x2 + . . .+ (akk − λ) · xk + . . .+ aknxn = 0

de unde avem

(akk − λ) · xk = −n∑j=1j 6=k

akj · xj

atunci

|akk − λ| ≤n∑j=1j 6=k

|akj| ·|xj||xk|

dar |xj| / |xk| ≤ 1 pentru orice j 6= k atunci

|akk − λ| ≤n∑j=1j 6=k

|akj| ·|xj||xk|≤

n∑j=1j 6=k

|akj| = rk

de unde rezulta λ ∈ Dk = D(akk, rk), atunci avem

σ(A) ⊂n⋃k=1

Dk

si lema este demonstrata.

Dam fara demonstratie urmatorul rezultat fundamental din algebraliniara

Lema 1.1.3. Pentru orice matrice A ∈Mn,n(R) exista o matrice nesingularaP ∈ Mn,n(C), astfel ıncat P−1 · A · P = J , unde J este o matrice bloc deforma

J =

J1 0. . .

0 J`

13


iar Jk sunt matrici unidimensionale (λ), sau de forma

Jk =

λ 1 0 · · · 0

0 λ 1. . .

......

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

. . . . . . 10 · · · · · · 0 λ

unde λ este valoare proprie pentru matricea A cu ordin de multiplicitate celputin egal cu dimensiunea lui Jk. Matricea J se numeste forma canonicaJordan.

Demonstratie. Pentru demonstratie a se vedea [3].

Daca A ∈ L(Rn,Rn) atunci notam cu ‖·‖ norma matricii consistenta.Aceasta norma poate fi una din normele:

(a) Norma aplicatiei liniare

‖A‖ = sup‖x‖=1

‖Ax‖ ,

(b) Norma

‖A‖ = maxk∈Inλk ,

unde λk sunt valorile proprii ale matricii ATA,

(c) Norma Frobenius

‖A‖ = tr(ATA) ,

unde tr(ATA) este urma matricii ATA, adica suma elementelor de pediagonala principala a matricii ATA.

Fie A,B ∈Mn,n(R) si x ∈ Rn atunci avem urmatoarele inegalitati

‖A · x‖ ≤ ‖A‖ · ‖x‖ si ‖A ·B‖ ≤ ‖A‖ · ‖B‖ .

Daca matricea A este inversabila, atunci avem

‖x‖ =∥∥A−1 · A · x

∥∥ ≤ ∥∥A−1∥∥ · ‖A‖ · ‖x‖ = κ ‖x‖ ,

unde κ ≥ 1. Dam urmatoarea definitie:

14


Definitia 1.1.7. Fie matricea A ∈ Mn,n(R) atunci numarul κ ∈ [1,∞)definit de relatia

κ =∥∥A−1

∥∥ · ‖A‖se numeste numarul de conditie al matricei A.

Lema 1.1.4. Fie A ∈Mn,n(R) astfel ıncat ‖A‖ < 1 atunci

limk→∞

Ak = 0

Demonstratie. Pentru doua matrici oarecare A, B ∈Mn,n(R) avem inegali-

tatea ‖A ·B‖ ≤ ‖A‖ · ‖B‖, rezulta ca∥∥Ak∥∥ ≤ ‖A‖k, atunci limk→∞ ‖A‖k =

0. Norma este o aplicatie continua atunci putem scrie∥∥limk→∞A

k∥∥ =

limk→∞∥∥Ak∥∥ ≤ limk→∞ ‖A‖k = 0, dar ‖x‖ = 0 daca si numai daca x = 0 si

cu asta lema este demonstrata.

Lema 1.1.5. Fie A ∈Mn,n(R) astfel ıncat ρ(A) < 1 atunci

limk→∞

Ak = 0 .

Demonstratie. Vezi lema 2.2 si lema 2.3 de la paginile 53 si 54 din [23].

Lema 1.1.6. Fie A ∈Mn,n(R) astfel ıncat ρ(A) < 1 atunci exista (I−A)−1

si

(I − A)−1 =∞∑k=0

Ak ,

unde I ∈Mn,n(R) si este matricea identitate.

Demonstratie. Observam ca daca matricea A are valori proprii pe λk, k ∈ Inatunci matricea I − A are valori proprii pe 1 − λk, k ∈ In. Daca ρ(A) < 1rezulta |λk| < 1 pentru orice k, k ∈ In deci 1− λk 6= 0 pentru k ∈ In, rezultaca 0 nu este valoare proprie pentru matricea I −A de unde rezulta ca exista(I − A)−1. Avem identitatea

I − Ak+1 = (I − A)(I + A+ . . . Ak)

daca ınmultim aceasta identitate cu (I − A)−1 va rezulta

(I − A)−1 − Ak+1(I − A)−1 =k∑j=0

Ak

trecand la limita dupa k si tinand cont ca limk→∞Ak = 0 daca ρ(A) < 1 vom

avea

(I − A)−1 =∞∑k=0

Ak .

15


In cele ce urmeaza prezentam lema de perturbare pe care o datoram luiJohn von Neumann [25], [23, Lema 2.5].

Lema 1.1.7 (von Nuemann 1943). Fie A,B ∈ Mn,n(R) astfel ıncat existaA−1 iar ‖A−1‖ ≤ α, ‖A−B‖ ≤ β si αβ < 1, atunci exista B−1 si ‖B−1‖ ≤α/(1− αβ).

Demonstratie. Avem∥∥I − A−1B∥∥ =

∥∥A−1(A−B)∥∥ ≤ ∥∥A−1

∥∥ · ‖A−B‖ ≤ αβ < 1

rezulta ρ(I − A−1B

)≤ ‖I − A−1B‖ < 1, atunci conform lemei 1.1.6 exista(

I− I +A−1B)−1

, adica exista AB−1, deci exista B−1. Atunci putem evaluanorma matricei B−1 .

∥∥B−1∥∥ ≤ ∥∥∥[I − (I − A−1B

)]−1∥∥∥ · ∥∥A−1

∥∥ =∥∥A−1

∥∥ · ∥∥∥∥∥∞∑k=0

(I − A−1B

)k∥∥∥∥∥=∥∥A−1

∥∥ · ∥∥∥∥∥∞∑k=0

[A−1(A−B)

]k∥∥∥∥∥ ≤ α

∥∥∥∥∥∞∑k=0

[A−1(A−B)

]k∥∥∥∥∥≤ α

∞∑k=0

∥∥∥[A−1(A−B)]k∥∥∥ ≤ α

∞∑k=0

∥∥(A−1)k∥∥ · ∥∥(A−B)k

∥∥≤ α

∞∑k=0

∥∥A−1∥∥k ‖A−B‖k ≤ α

∞∑k=0

αkβk = α∞∑k=0

(αβ)k =α

1− αβ.

Cu aceasta lema este demonstrata.

1.2 Elemente de analiza n-dimensionala

Prezentam cateva elemente de analiza n-dimensionala. Fie x ∈ Rn, x =(x1, x2, . . . , xn)T cu xk ∈ R pentru ∀k ∈ In. Un sir de elemente din Rn pecare ıl notam

x(k)

pentru a face diferenta fata de xk. Definim urmatoarelenorme

‖x‖p =

(n∑k=1

|xk|p) 1

p

pentru 1 ≤ p <∞

a) Pentru p = 1 avem norma unu ‖x‖1 =n∑k=1

|xk|

16


b) Pentru p = 2 avem norma euclidiana ‖x‖2 =

(n∑k=1

|xk|2)1/2

c) Pentru p =∞ avem norma infinit ‖x‖∞ = max |xk| | k ∈ In

Produsul scalar 〈· , · 〉 : Rn × Rn este definit de relatia

〈x, y〉 :=n∑k=1

xk · yk

atunci norma euclidiana poate fi scrisa si sub forma ‖x‖2 = 〈x, x〉1/2. Saremarcam ca

‖x+ y‖22 = 〈x, y〉 =

n∑k=1

(xk + yk) (xk + yk) =n∑k=1

(x2k + 2xk · yk + y2

k

)= 〈x, x〉+ 2 〈x, y〉+ 〈y, y〉 = ‖x‖2

2 + 2 〈x, y〉+ ‖y‖22 .

In cele ce urmeaza vom avea nevoie de inegalitatea lui Schwartz-Cauchy-Buniakovski

|〈x, y〉| ≤ ‖x‖2 · ‖y‖2

sau scrisa ın mod explicit dupa ce relatia a fost ridicata la patrat(n∑k=1

xk · yk

)2

≤n∑k=1

x2k

n∑k=1

y2k .

Observatia 1.2.1. Intr-un spatiu finit dimensional normele sunt echiva-lente. Fie doua norme ‖·‖α si ‖·‖β atunci ∃c, d ∈ [0,∞) astfel ıncat

c ‖x‖α ≤ ‖x‖β ≤ d ‖x‖α pentru ∀x ∈ Rn

ın acest sens se poate arata ca

‖x‖∞ ≤ ‖x‖p ≤p√n ‖x‖∞ pentru ∀x ∈ Rn si ∀p ∈ N.

Definitia 1.2.1. Un operator F : D ⊂ Rn → Rm este diferentiabil Gateauxın x ∈ D daca exista un operator liniar A ∈ L(Rn,Rm), astfel ıncat pentruorice h ∈ Rn si t real sa avem

limt→0

‖F (x+ th)− F (x)− A · th‖t

= 0 .

17


Se poate arata ca A este unic definit si ca nu depinde de norma. Acestoperator se numeste derivata Gateaux a lui F ın punctul x si noteaza cuF ′ (x). Daca F ′ (x) exista ın fiecare punct al unei multimi D0 ⊂ D, atunciF ′ este un operator (ın general neliniar) de la D0 ın L(Rn,Rm). In particular,acesta poate fi continuu ıntr-un punct x ∈ D0; conditia de continuitate sescrie

‖F ′ (x+ h)− F ′ (x)‖ → 0, cand h→ 0 .

Derivata Gateaux a unui operator admite urmatoarea reprezentare. Fief1, f2, . . . , fn, componentele lui F si e(j), j ∈ In, versorii axelor de coordonateın spatiul Rn, adica e(1) = (1, 0, 0, . . . , 0), e(2) = (0, 1, 0, . . . , 0), . . . , e(n) =(0, 0, . . . , 1). Sa notam cu ak,j elementele derivatei Gateaux ın punctul x sisa luam h = e(j). Din definitie obtinem

limt→0

∣∣fk (x+ te(j))− fk(x)− tak,j

∣∣t

= 0 ,

deci fk admite derivata partiala ın raport cu xk ın x si avem

∂fk(x)

∂xj= ak,j .

Asadar, daca F este diferentiabil Gateaux ın x, componentele lui F admitderivate partiale si

F ′ (x) =

∂f1(x)

∂x1

∂f1(x)

∂x2

. . .∂f1(x)

∂xn

∂f2(x)

∂x1

∂f2(x)

∂x2

. . .∂f2(x)

∂xn

......

. . ....

∂fm(x)

∂x1

∂fm(x)

∂x2

. . .∂fm(x)

∂xn

Reciproca acestei afirmatii nu este ın general adevarata, adica existenta

derivatelor partiale ale unui operator nu asigura derivabilitatea Gateaux. Inparticular daca m = 1, atunci

F ′ (x) =

(∂f(x)

∂x1

,∂f(x)

∂x2

, . . . ,∂f(x)

∂xn

).

Exista o serie de proprietati ale operatorilor diferentiabili Gateaux simi-lari cu proprietatile functiilor derivabile de o variabila reala. Astfel, daca F1

18


si F2 sunt doi operatori diferentiabili Gateaux si α, β ∈ R, atunci αF1 + βF2

este deasemenea diferentiabil Gateaux si

(αF1 + βF2) ′ = αF1′ + βF2

′ .

Alte proprietati nu se patreaza. De exemplu, un operator diferentiabilGateaux nu este ın general continuu. Are loc ınsa o proprietate ceva mai slabasi anume: daca F este diferentiabil Gateaux ın x, atunci F este hemicontinuuın x. Reamintim ca F : D ⊂ Rn → Rm este hemicontinuu ın x ∈ D dacapentru orice h ∈ Rn si ε > 0 exista un δ = δ(ε, h) astfel ıncat, daca |t| < δsi x + th ∈ D, atunci ‖F (x+ th)− F (x)‖ < ε. Cu alte cuvinte, F estecontinuu pe toate segmentele de dreapta care trec prin x.

Definitia 1.2.2. Un operator F : D ⊂ Rn → Rm este diferentiabil Frechetın x ∈ D daca exista un operator liniar A ∈ L(Rn,Rm), astfel ıncat

limh→0

‖F (x+ h)− F (x)− A · h‖‖h‖

= 0 ,

pentru h ∈ Rn.

Operatorul A este unic, se numeste derivata Frechet ın punctul x si senoteaza tot cu F ′ (x). Este evident ca un operator diferentiabil Frechet estesi diferentiabil Gateaux si deci derivata Frechet admite aceeasi reprezentareın functie de componentele lui F .

In cazul operatorilor diferentiabili Frechet, proprietatea de continuitatese pastreaza. Avem

Teorema 1.2.1. Daca operatorul F : D ⊂ Rn → Rm este diferentiabilFrechet ın punctul x ∈ D, atunci F este continuu ın x.

Demonstratie. Exista δ1 > 0 astfel ıncat x + h ∈ D daca ‖h‖ < δ1. Fieε > 0. Din definitia derivatei Frechet rezulta ca exista un δ, 0 < δ ≤ δ1 astfelıncat

‖F (x+ h)− F (x)− F ′ (x)h‖ ≤ ε ‖h‖ , pentru ∀ ‖h‖ ≤ δ .

Prin urmare, avem

‖F (x+ h)− F (x)‖ ≤ (ε+ ‖F (x)‖) ‖h‖ , pentru ∀ ‖h‖ ≤ δ ,

si continuitatea lui F este demonstrata.

Definitia 1.2.3. Un operator F : D ⊂ Rn → Rm este continuu diferentiabilpe o multime D0 ⊂ D daca F are derivata Frechet continua pe D0.

19


Se poate arata ca F ′ exista si este continua ıntr-un punct x daca si numaidaca derivatele partiale ∂fk/∂xj exista si sunt continue ın x.

Sa presupunem ca operatorul F : D ⊂ Rn → Rm este diferentiabilGateaux pe o multime D0 ⊂ D si fie operatorul F ′ : D0 ⊂ Rn → L(Rn,Rm).Deoarece L(Rn,Rm) este si el un spatiu de dimensiune finita n ×m, se potdefini derivatele Gateaux sau Frechet ale lui F ′. Se obtin astfel derivateleGateaux sau Frechet de ordinul al doilea.

Definitia 1.2.4. Presupunem ca operatorul F : D ⊂ Rn → Rm estediferentiabil Gateaux pe multimea deschisa D0 ⊂ D. Daca operatorulF ′ : D0 ⊂ Rn → L(Rn,Rm) este diferentiabil Gateaux ıntr-un punct x ∈ D0,atunci derivata lui F ′ se numeste derivata Gateaux de ordinul al doilea alui F ın x si se noteaza cu F ′′ (x). Daca F ′ este diferentiabil Frechet ıntr-un punct x ∈ D, derivata Frechet a lui F ′ se numeste derivata Frechet deordinul al doilea a lui F ın x si se noteaza cu F ′′ (x).

Daca derivata Gateaux sau Frechet de ordinul al doilea exista, atunciF ′′ (x) ∈ L

(Rn,L(Rn,Rm)

)si pentru orice h ∈ Rn, F ′′ (x)h ∈ L(Rn,Rm).

In mod analog se pot defini derivatele Gateaux sau Frechet de ordinul altreilea.

Teorema 1.2.2. Fie operatorul F : D ⊂ Rn → Rm diferentiabil Gateaux peo multime convexa D0 ⊂ D. Atunci pentru orice x, y ∈ D0 avem

‖F (y)− F (x)‖ ≤ supt∈[0,1]

‖F ′ (x+ t(y − x))‖ · ‖y − x‖ .

Demonstratie. Fie

M = supt∈[0,1]

‖F ′ (x+ t(y − x))‖ · ‖y − x‖

si fie Γ multimea punctelor din [0, 1] pentru care avem

‖F ′ (x+ t(y − x))− F (x)‖ ≤Mt ‖y − x‖+ εt ‖y − x‖ , (1.1)

unde ε este un numar pozitiv dat. Este evident ca 0 ∈ Γ si deci Γ nu estevida. Fie γ = supt∈Γ t. Deoarece F este hemicontinua pe D0, rezulta caF (x+ t(y − x)) este un operator continuu pe [0, 1] si avem

‖F (x+ γ(y − x))− F (x)‖ ≤Mγ ‖y − x‖+ εγ ‖y − x‖ . (1.2)

Daca γ = 1, teorema este demonstrata deoarece ε este arbitrar. Sa pre-supunem ca γ < 1. Atunci din definitia derivatei Gateaux a operatorului

20


F , scrisa ın punctul x + γ(y − x) si h = y − x, t = β − γ, unde β ∈ (γ, 1),obtinem

‖F (x+ β(y − x))− F (x+ γ(y − x))− F ′ (x+ γ(y − x)) (β − γ)(y − x)‖≤ ε(β − γ) ‖y − x‖ .

Prin urmare, avem

‖F (x+ β(y − x))− F (x+ γ(y − x))‖ ≤ (M + ε)(β − γ) ‖y − x‖ .

De aici si din relatia (1.2) obtinem

‖F (x+ β(y − x))− F (x)‖ ≤ (M + ε)(β − γ) ‖y − x‖+ (M + ε)γ ‖y − x‖= (M + ε)β ‖y − x‖ ,

adica o relatie de forma (1.1) ın care t = β > γ, ceea ce contrazice definitialui γ. Prin urmare γ = 1 si teorema este demonstrata.

Observatia 1.2.2. Daca ‖F ′ (x)‖ ≤ M < ∞ pe D0, atunci din teorema1.2.2 rezulta imediat ca F este continuu Lipschitz pe D0.

In cele ce urmeaza vom mai avea nevoie si de urmatoarele doua corolareale teoremei 1.2.2.

Corolarul 1.2.3. Daca F : D ⊂ Rn → Rm este diferentiabil Gateaux pemultimea convexa D0 ⊂ D, atunci pentru orice x, y, z ∈ D0 avem

‖F (y)− F (z)− F ′ (x) (y − z)‖≤ sup

t∈[0,1]

‖F ′ (z + t(y − z))− F ′ (x)‖ · ‖y − z‖ .

Demonstratie. Pentru fiecare x ∈ D0 definim operatorul G : D0 ∈ Rn → Rm,cuG(u) = F (u)−F ′ (u)u. DeoareceG′(u) = F ′ (u)−F ′ (x), aplicam teorema1.2.2 si corolarul rezulta din relatia

‖G(y)−G(z)‖ ≤ supt∈[0,1]

‖G′(z + t(y − z))‖ · ‖y − z‖ .

Corolarul 1.2.4. Daca F : D ⊂ Rn → Rm este diferentiabil Gateaux pe ovecinatate a lui x ∈ D si F ′ este continuu ın x atunci F este diferentiabilFrechet ın x.

21


Demonstratie. Deoarece F ′ este continuu ın x , fiind dat ε > 0, exista δ > 0astfel ıncat ‖F ′ (x+ h)− F ′ (x)‖ < ε daca ‖h‖ < δ. Din corolarul 1.2.3 ıncare luam y = x+ h si z = x, obtinem

‖F (x+ h)− F (x)− F ′ (x)h‖ ≤ supt∈[0,1]

‖F ′ (x+ th)− F ′ (x)‖ · ‖h‖ ≤ ε ‖h‖ .

Teorema 1.2.5. Daca F : D ⊂ Rn → Rm este de doua ori diferentiabilGateaux pe o multime convexa D0 ⊂ D, atunci pentru orice x, y ∈ D0, avem

‖F (y)− F (x)− F ′ (x) (y − x)‖ ≤ supt∈[0,1]

‖F ′′ (x+ t(y − x))‖ · ‖y − x‖2 .

Demonstratie. Din corolarul 1.2.3 si teorema 1.2.2 aplicate operatorului F ′,obtinem

‖F (y)− F (x)− F ′ (x) (y − x)‖≤ sup

t∈[0,1]

‖F ′ (x+ t(y − x))− F ′ (x)‖ · ‖y − x‖

≤ supt∈[0,1]

sups∈[0,1]

‖F ′′ (x+ ts(y − x))‖ · ‖y − x‖

‖y − x‖ .

Dar este evident ca

supt∈[0,1]

sups∈[0,1]

‖F ′′ (x+ ts(y − x))‖ = supt∈[0,1]

‖F ′′ (x+ t(y − x))‖

si teorema este demonstrata.

Fie F : D ⊂ Rn → Rm un operator diferentiabil Gateaux pe D si fiex, y doua puncte din D astfel ıncat x+ t(y − x) ∈ D pentru orice t ∈ [0, 1].Atunci, deoarece F este hemicontinuu pe D, rezulta ca componentele salef1, f2, . . . , fm luate ın punctul x + t(y − x) sunt functii continue ın raportcu t. Daca ın plus presupunem ca fk(x + t(y − x))(y − x) sunt integrabileRiemann pe [0, 1], atunci

fk(y)− fk(x) =

∫ 1

0

fk(x+ t(y − x))(y − x)dt (1.3)

Intr-adevar, daca notam cu x1, x2, . . . , xn si cu y1, y2, . . . , yn componentelelui x si ale lui y respectiv, atunci fk(x+ t(y− x)) = fk

(x1 + t(y1− x1), x2 +

22


t(y2 − x2), . . . , xn + t(yn − xn))

astfel ıncat

∂fk(x+ t(y − x))

∂t=∂fk∂x1

(y1 − x1) +∂fk∂x2

(y2 − x2) + . . . +∂fk∂xn

(yn − xn)

= f ′k(x+ t(y − x))(y − x)

si relatia (1.3) rezulta din egalitatea g(1) − g(0) =∫ 1

0g′(t)dt ın care luam

g(t) = fk(x + t(y − x)). Acum, daca definim integrala unei functionaleG : [0, 1]→ Rm, de componente g1, g2, . . . , gm prin

∫ 1

0

G(t)dt =

∫ 1

0g1(t)dt∫ 1

0g2(t)dt

...∫ 1

0gm(t)dt

,

din (1.3) rezulta ca

F (y)− F (x) =

∫ 1

0

F (x+ t(y − x)) (y − x)dt . (1.4)

Lema 1.2.1. Daca G : [0, 1]→ Rm este continua pe [0, 1], atunci∥∥∥∥∫ 1

0

G(t)dt

∥∥∥∥ ≤ ∫ 1

0

‖G(t)‖ dt .

Demonstratie. Deoarece norma este o functie continua, ‖G(t)‖ este integra-bila Riemann. Fiind dat un ε > 0, exista o partitie 0 = t0 < t1 < . . . < tp = 1astfel ıncat ∥∥∥∥∥

∫ 1

0

G(t)dt−p∑

k=1

G(tk)(tk − tk−1)

∥∥∥∥∥ ≤ ε

si ∣∣∣∣∣∫ 1

0

‖G(t)‖ dt−p∑

k=1

‖G(tk)‖ (tk − tk−1)

∣∣∣∣∣ ≤ ε .

Prin urmare∥∥∥∥∫ 1

0

G(t)dt

∥∥∥∥ ≤∥∥∥∥∥

p∑k=1

G(tk)(tk − tk−1)

∥∥∥∥∥+ ε ≤p∑

k=1

‖G(tk)‖ (tk − tk−1) + ε

≤∫ 1

0

‖G(t)‖ dt+ 2ε .

23


Teorema 1.2.6. Fie F : D ⊂ Rn → Rm un operator diferentiabil Frechetpe multimea convexa D0 ⊂ D Presupunem ca derivata Frechet este continuaLipschitz pe D0, adica

‖F ′ (x)− F ′ (y)‖ ≤ L ‖x− y‖ , pentru ∀x, y ∈ D0 .

Atunci pentru orice x, y ∈ D0 avem

‖F (x)− F (y)− F (x) (y − x)‖ ≤ L

2‖y − x‖2 .

Demonstratie. Tinand seama de relatia (1.4) si de lemma 1.2.1, avem

‖F (y)− F (x)− F ′ (x) (y − x)‖

=

∥∥∥∥∫ 1

0

[F ′ (x+ t(y − x))− F ′ (x)] (y − x)dt

∥∥∥∥≤∫ 1

0

‖F (x+ t(y − x))− F ′ (x)‖ · ‖y − x‖ dt

≤ L ‖y − x‖2

∫ 1

0

dt .

1.3 Ordin de convergenta ın RFie sirul real definit de o metoda de calcul ın p pasi

xk+1 = Φ (xk, xk−1, . . . , xk−p+1) k = 0, 1 . . . (1.5)

convergenta catre x?, unde x? este o solutie a ecuatiei neliniare f(x) = 0.

Definitia 1.3.1. Numarul real r ≥ 1 este ordinul de convergenta al siruluixk, k ∈ N daca

limk→∞

|xk+1 − x?||xk − x?|r

= ρ , (1.6)

unde 0 < ρ <∞.

Definitia 1.3.2. Numarul real pozitiv ρ obtinut cu relatia (1.6) se numesteeroare asimptotica a metodei (1.5).

Observatia 1.3.1. Pentru un sir real xk avem urmatoarele ordine de con-vergenta

24


• Daca r = 1 atunci spunem ca avem o convergenta liniara;

• Daca 1 < r < 2 atunci spunem ca avem o convergenta superliniara;

• Daca r = 2 atunci spunem ca avem o convergenta patratica;

• Daca r = 3 atunci spunem ca avem o convergenta cubica;

Observatia 1.3.2. Este posibil ca sirul xk sa convearga la x? dar sa nuexiste limita ρ data de (1.6). De exemplu prin interclasarea a doua siruricare converg cu viteze diferite la aceiasi limita x?. Fie sirurile

ak =1

ksi bk =

1

2k

atunci sirul definit dupa cum urmeaza

c2k = ak si c2k+1 = bk k = 0, 1, . . .

atunci ck → 0, iar

|ck+1||ck|r

=

kr

2k→ 0 , pentru ∀r ≥ 1 ,

2k·r

k + 1→∞ , pentru ∀r ≥ 1 .

Observatia 1.3.3. In situatia precizata de observatia 1.3.2 putem caracte-riza viteza de convergenta astfel: fie relatia

|xk+1 − x?| ≤ |xk − x?|r0 (1.7)

daca exista r ≥ 1 astfel ıncat sa avem relatia (1.6), atunci r ≥ r0. Intr-adevar, daca presupunem ca r < r0, atunci

|xk+1 − x?||xk − x?|r0

=|xk+1 − x?||xk − x?|r

· 1

|xk − x?|r0−r→∞ ,

ceea ce contrazice relatia (1.7).Daca avem o relatie de tipul (1.7), spunem ca metoda are o viteza de

convergenta cel putin de ordinul r0.

Observatia 1.3.4. Daca putem stabili relatia

ρ1 |xk − x?|r0 ≤ |xk+1 − x?| ≤ ρ2 |xk − x?|r0 (1.8)

si exista relatia (1.6) atunci se poate arata ca mai sus ca r = r0; daca avemrelatia (1.8), ın acest caz spunem ca viteza de convergenta este r0 (cu toateca s-ar putea sa existe relatia (1.8) dar sa nu existe limita din relatia (1.6)pentru r0).

25


1.4 Ordin de convergenta ın Rn

Fiex(k)⊂ Rn un sir convergent ın norma ‖·‖.

Definitia 1.4.1. Daca

limk→∞

∥∥x(k+1) − x?∥∥

‖x(k) − x?‖r= ρ

cu 0 < ρ < ∞, atunci r se numeste viteza de convergenta a siruluix(k)

,iar ρ este eroarea asimptotica.

1.4.1 Q-ordinul de convergenta

Fie sirulx(k)

convergent la x? cu x(k) 6= x? pentru orice k ∈ N iar

x(k+1) := Φ(x(k)). Ipoteza x(k) 6= x? este naturala caci daca x(k) = x? pentru

orice k > k0, atunci sirul devine constant si nu se mai pune problema vitezeide convergenta. In astfel de cazuri spunem ca sirul converge ıntr-un numarfinit de pasi.

Definitia 1.4.2. Fie functia Q : [1,∞)→ [0,∞) data de

Q(t) :=

lim supk→∞

∥∥x(k+1) − x?∥∥

‖x(k) − x?‖tdaca x(k) 6= x? pentru k ≥ k0

0 daca x(k) = x? pentru k ≥ k0

Spunem ca Q(t) se numeste Q–factori de convergenta cat.

Teorema 1.4.1. Fie Q(t), Q-factori de convergenta cat a unui sirx(k)

ınraport cu norma ‖·‖ atunci are loc una din relatiile:

a) Q(t) = 0 pentru ∀t ∈ [0, ∞);

b) Q(t) =∞ pentru ∀t ∈ [1, ∞);

c) ∃ q ∈ [1, ∞) astfel ıncat Q(t) = 0 pentru t ∈ [1, q) si Q(t) =∞ pentrut ∈ [q, ∞).

Demonstratie. Fie εk :=∥∥x(k) − x?

∥∥.

• Daca εk = 0 pentru k ≥ k0 atunci Q(t) = 0 pentru ∀t ∈ [1, ∞) si areloc cazul a).

• Daca εk > 0 pentru k ≥ k0 si fie q := inf t | t ∈ [1, ∞), Q(t) =∞,daca Q(t) <∞ pentru ∀t ∈ [1, ∞) , atunci q =∞.

26


6

-

Q

t(1,0)

∞

rq

Figura 1.1: Functia Q

• Daca q ∈ (1, ∞)

– atunci pentru ∀t ∈ [1, q) ⇒ Q(t) = 0, ıntradevar ∃t1 ∈ (t, q)astfel ıncat Q(t1) <∞ si

Q(t) = lim supk→∞

εk+1

εt1kεt1−tk = Q(t1) · lim

k→∞εt1−tk = 0

deci Q(t) = 0 (atunci cand exista limita avem limita superioaraegala cu limita sirului).

– atunci pentru ∀t ∈ (q, ∞) ⇒ Q(t) = ∞, ıntradevar, daca ar∃t ∈ (q, ∞) pentru care Q(t) < ∞ atunci fie t1 ∈ [q, t) astfelıncat Q(t1) =∞ (existenta lui t1 ⇒ din definitia lui q), atunci

Q(t1) = lim supk→∞

εk+1

εtk· εt−t1k = Q(t) · lim

k→∞εt−t1k = 0

ceea ce este absurd ⇒ Q(t) =∞ pentru ∀t ∈ (q, ∞).

Concluzia teoremei este graficul functiei Q : [1, ∞) → R dat de figura1.1.

Lema 1.4.1. Intr-un spatiu cu dimensiune finita relatiile Q(t) = 0, 0 <Q(t) <∞ si Q(t) =∞ nu depind de norma.

Demonstratie. Fie ‖·‖α si ‖·‖β doua norme pe Rn si Q(t) si Q′(t) Q–factori

unui sirx(k)

ın cele doua norme. Sa presupunem ca x(k) 6= x? pentru

27


∀k ≥ k0 ın caz contrar Q(t) = Q′(t) = 0 si lema este demonstrata. Normeleın Rn sunt echivalente, adica ∃c, d ∈ [0,∞) astfel ıncat

c ‖x‖α ≤ ‖x‖β ≤ d ‖x‖α ∀x ∈ Rn ,


∥∥x(k+1) − x?∥∥α

‖x(k) − x?‖tα≤ lim sup

k→∞

dt

c·

∥∥x(k+1) − x?∥∥β

‖x(k) − x?‖tβ=dt

cQ′(t)

si

Q′(t) = lim supk→∞

∥∥x(k+1) − x?∥∥β

‖x(k) − x?‖tβ≤ lim sup

k→∞

d

ct·∥∥x(k+1) − x?

∥∥α

‖x(k) − x?‖tα=d

ctQ(t)

de undec

dtQ(t) ≤ Q′(t) ≤ d

ctQ(t)

atunci Q(t) = 0 ⇔ Q′(t) = 0 si Q(t) =∞ ⇔ Q′(t) =∞ .

Definitia 1.4.3. Fie spatiul real n−dimendional Rn cu norma ‖·‖ si sirulx(k)⊂ Rn convergent la x? ∈ Rn. Fie Q(t), Q–factori sirului si

q := inf t | t ∈ [1, ∞), Q(t) =∞, atunci q se numeste Q–ordinul deconvergenta al sirului.

Observatia 1.4.1. Fie sirulx(k)⊂ Rn convergent la x? ∈ Rn atunci

• Daca q=1 convergenta se numeste Q–liniara;

• Daca 1 < q < 2 convergenta se numeste Q–superliniara;

• Daca q=2 convergenta se numeste Q–patratica;

• Daca q=3 convergenta se numeste Q–cubica.

Observatia 1.4.2. Fiex(k)

siy(k)

doua siruri convergente la x? sirespectiv la y?. Fie q, q′ Q–ordinele de convergenta corespunzatoare, atunci

• Daca q < q′ ⇒ siruly(k)

este mai rapid Q–convergent decatx(k)

;

• Daca q = q′ si ∃t astfel ıncat Q′(t) = 0 < Q(t) sau Q′(t) < Q(t) = ∞(aceste relatii sunt independente de norma) vom spune ca sirul

y(k)

este mai rapid Q–convergent decatx(k)

;

• Daca q = q′ si ∃t astfel ıncat 0 < Q′(t) < Q(t) <∞ atunci siruly(k)

este mai rapid Q–convergent ın norma ‖·‖ dar pot exista alte norme ıncare relatia sa fie inversa.

28


1.4.2 R–ordinul de convergenta

Fie spatiul Rn cu norma ‖·‖ si sirulx(k)⊂ Rn convergent la x? ∈ Rn.

Definitia 1.4.4. Fie functia R : [1, ∞)→ [0,∞) definit de

R(t) :=

lim supk→∞

∥∥x(k) − x?∥∥1/k

pentru t = 1

lim supk→∞

∥∥x(k) − x?∥∥1/tk

pentru t > 1

Vom spune ca R(t) sunt factori de convergenta radacina sau R–factori siruluix(k)

.

Observatia 1.4.3. Deoarece sirulx(k)

este convergent la x? atunci rezulta

ca ∃k0 ∈ N astfel ıncat∥∥x(k) − x?

∥∥ < 1 pentru ∀k > k0, atunci pentru∀k ≥ k0 avem 0 ≤ R(t) ≤ 1 pentru ∀t ∈ [1, ∞).

Observatia 1.4.4. R–factorii nu depind de norma. Fie normele ‖·‖α, ‖·‖βdin Rn, atunci ele sunt echivalente adica ∃c, d ∈ [0,∞) astfel ıncat

c ‖x‖α ≤ ‖x‖β ≤ d ‖x‖α ∀x ∈ Rn .

Fie sirul εk ⊂ R si limk→∞ εk = 0 atunci

R(t) = lim supk→∞

∥∥x(k) − x?∥∥εkα≤ lim sup

k→∞

1

cεk

∥∥x(k) − x?∥∥εkβ

= lim supk→∞

∥∥x(k) − x?∥∥εkβ

= R′(t) ∀t ∈ [1, ∞)

si

R′(t) = lim supk→∞

∥∥x(k) − x?∥∥εkβ≤ lim sup

k→∞dεk∥∥x(k) − x?

∥∥εkα

= lim supk→∞

∥∥x(k) − x?∥∥εkα

= R(t) ∀t ∈ [1, ∞)

deci R(t) ≤ R′(t) si R′(t) ≤ R(t) pentru ∀t ∈ [1, ∞) rezulta ca R(t) = R′(t)pentru ∀t ∈ [1, ∞).

Teorema 1.4.2. Fie R(t) R–factori siruluix(k)⊂ Rn convergent la x? ∈

Rn, atunci are loc unul din cazurile:

a) R(t)=0 pentru ∀t ∈ [1, ∞);

b) R(t)=1 pentru ∀t ∈ [1, ∞);

29


6

-

R

t(1,0)

1

rr

Figura 1.2: Functia R

c) ∃r ∈ [1, ∞) astfel ıncat R(t)=0 pentru ∀t ∈ [1, r) si R(t)=1 pentru∀t ∈ [r, ∞).

Demonstratie. Notam cu

αkt :=

1/k pentru t = 11/tk pentru t > 1

si fie r := inf t | t ∈ [1, ∞), R(t) = 1. Fie r ∈ [1, ∞) si t ∈ [1, r) fixatvom arata ca daca R(t) = 0, atunci ∃t1 ∈ (t, r) astfel ıncat R(t1) < 1. Notamcu εk :=

∥∥x(k) − x?∥∥, atunci

R(t) = lim supk→∞

εαktk = lim supk→∞

(εαkt1k

) αktαkt1 = lim

k→∞

(εαkt1k

) αktαkt1 = 0 .

Fie r ∈ [1, ∞) si t ∈ [r, ∞) fixat, vom arata ca R(t) = 1. Sa presupunemcontrariu adica ca R(t) < 1, deci ∃t1 ∈ (r, t) astfel ıncat R(t1) = 1, atunci

1 = R(t) = lim supk→∞

εαkt1k = lim sup

k→∞(εαktk )

αkt1αkt = R(t)

lim supk→∞

αkt1αkt

= R(t)limk→∞

αkt1αkt = 0 ,

ceea ce este absurd, rezulta ca R(t) = 1 pentru ∀t ∈ (r,∞) .

Definitia 1.4.5. Numarul r dat de r = t |t ∈ [1, ∞), R(t) = 1 senumeste R–ordinul de convergenta al sirului

x(k)

convergent la x?.

30


1.4.3 Relatii ıntre ordine de convergenta

Relatia ıntre R − ordinul de convergenta si Q− ordinul de convergentaeste data de urmatoarele teoreme:

Teorema 1.4.3. Fie sirulx(k)

convergent la x? atunci R(1) ≤ Q(1).

Demonstratie. Daca Q(1) =∞ atunci inegalitatea este demonstrata.Daca Q(1) < ∞ atunci fie ε > 0 oarecare. Atunci ∃k0 ∈ N astfel ıncat

εk+1 ≤(Q(1) + ε

)εk pentru ∀k ≥ k0, daca notam cu α = Q(1) + ε atunci

avem relatia εk+1 ≤ α · εk pentru ∀k ≥ k0. Din considerentele de mai susputem scrie

εk ≤ α · εk−1 ≤ α2 · εk−2 ≤ . . . ≤ αk−k0 · εk0 ,

de unde

(εk)1/k ≤ α

( εk0αk0

)1/k

.

In concluzie

R(1) = lim supk→∞

(εk)1/k ≤ α · lim sup

k→∞

( εk0αk0

)1/k

= α ,

deoarece εk0/αk0 este o contanta, adica

R(1) ≤ Q(1) + ε ,

ceea ce era de demonstrat.

Teorema 1.4.4. Fie sirulx(k)⊂ Rn si convergent la x? atunci q ≤ r.

Demonstratie. Daca q = 1 atunci relatia este evidenta pentru ca r ≥ 1.Daca q > 1, atunci fie t ∈ [1, q). Vom arata ca R(t) = 0 (adica r ≥ q).

Vezi figura 1.3 . Notam cu εk =∥∥xk − x?∥∥. Pentru t ∈ [1, q) rezulta Q(t) = 0.

Fie α > 0, atunci ∃k0 astfel ıncat εk+1 < αεtk pentru ∀k > k0. Fie α asa alesastfel ıncat α1/(t−1)εk0 < 1, atunci avem


εk+1

εtk< α

de unde rezulta ca Q(t) = 0. Atunci avem succesiunea de inegalitati

εk0+1 ≤ αεtk0

εk0+2 ≤ αεtk0+1 = ααtεt2

k0= αt+1εt

2

k0

εk0+3 ≤ αεtk0+2 = αα(t+1)tεt3

k0= αt

2+t+1εt3

k0

...

εk0+k ≤ αεtk0+k−1 = . . . = αtk−1+tk−2+...+1εt

k

k0.

31


6

-

Q,R

t(1, 0)

1

∞

rr

q)

( Q

r)

( R

Figura 1.3: Functia R si Q

Ultima inegalitate se ridica la puterea 1/tk si rezulta

(εk0+k)1

tk ≤ α1t+ 1t2

+...+ 1

tk εk0 ≤ limk→∞

α1t+ 1t2

+...+ 1

tk εk0 = α1t−1 · εk0 < 1 .

Cantitatea α1t−1 · εk0 < 1 este un numar ce nu depinde de k. Atunci avem

R(t) = limk→∞

(εk0+k)1

tk = α1t−1 · εk0 < 1 ,

de unde rezulta ca R(t) = 0 pentru ∀t ∈ [1, q). Daca R(t) = 0, atunci∃t ≥ q astfel ıncat R(t) = 1 de unde rezulta ca r ≥ q pentru ca r =inf t | t ∈ [1,∞), R(t) = 1.

Teorema 1.4.5. Fie sirulx(k)⊂ Rn, convergent la x?. Presupunem ca

exista

limk→∞

∥∥x(k+1) − x?∥∥

‖x(k) − x?‖p= ρ ,

unde 0 < ρ <∞ , atunci q = r = p.

Demonstratie. Notam cu εk =∥∥x(k) − x?

∥∥. Daca

Q(p) = lim supk→∞

εk+1

εpk= lim

k→∞

εk+1

εpk= ρ ,

atunci conform teoremei 1.4.1, Q(t) = 0 pentru ∀t ∈ [1, p) si Q(t) = ∞pentru ∀t ∈ (p, ∞), rezulta ca q = inf t | t ∈ (1,∞), Q(t) =∞ = p, adicaq = p.

Daca existalimk→∞

εk+1

εpk= ρ ,

32


cu 0 < ρ <∞, atunci rezulta ca ∃ k0 ∈ N astfel ıncat

εk+1 ≤ ρεpk si ρ(p−1)/p · εpk0 < 1

pentru ∀ k ≥ k0, de unde avem

εk0+1 ≤ ρ · εk0εk0+2 ≤ ρ · εpk0+1 ≤ ρp+1 · εpk0εk0+3 ≤ ρ · εpk0+2 ≤ ρ · ρp+1 · εp

2

k0= ρp

2+p+1 · εp3

k0

...

εk0+k+1 ≤ ρ · εpk0+k ≤ . . . = ρpk+pk−1+...+1 · εp

k+1

k0

Ridicam la puterea 1/pk ultima inegalitate, atunci

(εk0+k+1)1

pk ≤ ρ1+ 1

p+...+ 1

pk · εpk0 = ρ

1− 1p

1−(

1p

)k+1

· εpk0 ,

atunci

R(p) = lim supk→∞

(εk0+k+1

) 1

pk ≤ εpk0 · limk→∞

ρ

1− 1p

1−(

1p

)k+1

≤ ρp−1p · εpk0 < 1,

dar conform teoremei 1.4.1 avem situatia c) din teorema, atunci rezulta ca

r = inf t | t ∈ [1, ∞), R(t) = 1 = p ,

adica r = p.Cu aceasta s-a demonstrat ca q = r = p.

Definitia 1.4.6. Fie un sirx(k)⊂ Rn convergent la x? ∈ Rn si exista p

real, p ≥ 1 si ρ, 0 < ρ <∞ astfel ıncat

limk→∞

∥∥x(k+1) − x?∥∥

‖x(k) − x?‖p= ρ.

Numarul real pozitiv ρ se numeste eroarea asimptotica a metodei ce genereazasirul

x(k)

.

33

Capitolul 2

Metode numerice pentruecuatii neliniare ın Rn

Fie spatiul liniar Rn cu n ∈ N, n ≥ 2. Vom considera metode numericepentru rezolvarea ecuatiei neliniare F (x) = 0, unde F : D ⊂ Rn → Rn.

2.1 Metoda Newton

2.1.1 Constructia metodei Newton

In teorema de medie 1.2.6 fie y ≡ x si x ≡ x(k) , atunci teorema devine∥∥F (x(k))− F (x)− F ′

(x(k)) (x− x(k)

)∥∥ ≤ L

2

∥∥x− x(k)∥∥2

.

Daca x si x(k) sunt apropiate de x?, solutia ecuatiei F (x) = 0, atunci

F (x)− F(x(k))− F ′

(x(k)) (x− x(k)

) ∼= 0

sauF (x) ∼= F

(x(k))

+ F ′(x(k)) (x− x(k)

).

In locul ecuatiei F (x) = 0 putem considera ecuatia

F(x(k))

+ F ′(x(k)) (x− x(k)

)= 0 .

Rezolvam aceasta ecuatie. Egalitatea

F ′(x(k)) (x− x(k)

)= −F

(x(k))

este echivalenta cu

x− x(k) = −F ′(x(k))−1

F(x(k)),

34


de unde rezulta ca

x = x(k) − F ′(x(k))−1

F(x(k)).

In final rezulta formulele iterative pentru metoda Newton pentru o ecuatieneliniara din Rn. Convenim ca ın cele ce urmeaza sa notam cu Γ(x) functiaF ′ (x)−1 si cu N (x) operatorul Newton dat de produsul Γ(x)F (x).

x(k+1) := x(k) − Γ(x(k))F(x(k))

= x(k) −N(x(k))

(2.1)

cu k = 0, 1, . . . si x(0) ∈ Rn dat.Ca si ın cazul unidimensional putem avea metoda Newton simplificata

x(k+1) := x(k) − Γ(x(0))F(x(k)),

cu k = 0, 1, . . . si x(0) ∈ Rn dat , si metoda liniilor paralele

x(k+1) := x(k) − A · F(x(k)),

unde A ≈ Γ(x(p(k))

), cu k = 0, 1, . . . si x(0) ∈ Rn dat. Determinarea matricii

A din p(k) ın p(k + 1) pasi este o problema.

2.1.2 Convergenta metodei Newton

Pentru demonstrarea convergentei metodei Newton ın Rn vom apela lateorema lui Kantorovich, rezultat fundamental ın analiza numerica. Kan-torovich a demonstrat ın anul 1948 ın lucrarea [21] convergenta patratica ametodei Newton ın spatii Banach. Un rezultat recent al autorilor Ezquerrosi Hernandez, [16], generalizeaza conditiile de converenta ale teoremei Kan-torovich. Hernandez si Rubio ın articolul [19] studiaza aplicabilitatea metodeiNewton pentru o ecuatie operatoriala neliniara, F (x) = 0 unde operatorulF este nediferentiabil.

Teorema 2.1.1 (Kantorovich 1948). Fie F : D ⊂ Rn → Rn o aplicatiediferentiabila Frechet pe multimea D0 ⊂ D si x(0) ∈ D0. Daca avem ındepli-nite conditiile:

1. Exista Γ0 = Γ(x(0))

= F ′(x(0))−1

si ‖Γ0‖ ≤ β0,

2. ‖F ′ (y)− F ′ (x)‖ ≤ γ ‖y − x‖ pentru ∀x, y ∈ D0,

3.∥∥Γ0F

(x(0))∥∥ =

∥∥N (x(0))∥∥ ≤ η0,

4. α0 = β0γη0 ≤ 12,

35


5. S0 = S(x(0), r0

)⊆ D0 unde r0 =

(1−√

1− 2α0

)η0/α0,

atunci ecuatia F (x) = 0 are o unica solutie x? ∈ D0 iar sirulx(k)

generat

de metoda Newton (2.1) cu iteratia initiala x(0) converge la x? iar eroarea apriori a metodei este data de relatia∥∥x? − x(k)

∥∥ ≤ 21−k(2α0)2k−1 · η0 .

Demonstratie. Sa aratam ca η0 < r0 ≤ 2η0. Aceasta este echivalent cu

η0 <1−√

1− 2α0

α0

η0 ≤ 2η0 ,

dar η0/α0 > 0 deci putem ımparti relatia cu η0/α0, fara sa schimbam sensulrelatiilor, deci α0 < 1−

√1− 2α0 ≤ 2α0 ⇔ α0 − 1 < −

√1− 2α0 ≤ 2α0 − 1.

Dupa ımultirea cu −1 avem relatia echivalenta, 1−α0 >√

1− 2α0 ≥ 1−2α0,unde 1 − α0 > 0 si 1 − 2α0 ≥ 0, deci putem ridica relatia la patrat si avemrelatia echivalenta (1− α0)2 > 1− 2α0 ≥ (1− 2α0)2. Aceasta relatie este larandul ei echivalenta cu α2

0 > 0 > 4α20 − 2α0. Dar α2

0 > 0 este evidenta iar4α2

0 − 2α0 ≤ 0. Aceasta ultima relatie este echivalenta cu 2α0(2α0 − 1) ≤ 0care este la randul ei este echivalenta cu 2α0 − 1 ≤ 0 adica α0 ≤ 1/2.Deci relatia 4 din ipoteza teoremei, α0 ≤ 1/2, este echivalenta cu relatiaη0 < r0 ≤ 2η0.

• Avem∥∥x(1) − x(0)

∥∥ =∥∥N (x(0)

)∥∥ ≤ η0 < r0 de unde rezulta ca x(1) ∈S0 ⊂ D0.

•∥∥F ′ (x(1)

)− F ′

(x(0))∥∥ ≤ γ

∥∥x(1) − x(0)∥∥ ≤ γη0 deoarece avem, conditia

globala, ca functia F ′ este Lipschitz continua pe D0.

• Din relatia 1 din ipoteza teoremei rezulta ca exista Γ0 si ‖Γ0‖ ≤ β0 iarβ0γη0 = α0 ≤ 1/2 < 1.

Din ultimele doua aliniate, conform lemei 1.1.7, de perturbare a lui Johnvon Neumann, rezulta ca exista Γ1 = Γ

(x(1))

si

‖Γ1‖ ≤β0

1− β0γη0

=β0

1− α0

= β1 , (2.2)

unde s-a notat cu β1 expresia β0/(1 − α0). Deoarece ‖F ′ (y)− F ′ (x)‖ ≤γ ‖y − x‖ pentru ∀ x, y ∈ D0, adica conditia de Lipschitz continua a functieiF ′ pe D0 (conditie globala pe D0), atunci avem ca∥∥I − Γ0F

′ (x(1))∥∥ =

∥∥Γ0

[F ′(x(0))− F ′

(x(1))]∥∥

≤ ‖Γ0‖ ·∥∥F ′ (x(0)

)− F ′

(x(1))∥∥ ≤ β0γ

∥∥x(0) − x(1)∥∥

≤ β0γη0 = α0 ≤1

2< 1 . (2.3)

36


Deoarece ρ(A) ≤ ‖A‖ pentru ∀ A ∈Mn,n(R) rezulta ca, deoarece

ρ(I − Γ0F

′ (x(1)))≤ 1

2< 1 ,

atunci, conform lemei 1.1.6, avem ca exista[I − I + Γ0F

′ (x(1))]−1

, adica

exista[Γ0F

′ (x(1))]−1

= Γ(x(1))F ′(x(0))

= Γ1F′ (x(0)

), deci exista Γ1 si

avem

Γ1F′ (x(0)

)=∞∑k=0

[I − Γ0F

′ (x(1))]k

.

In relatia de mai sus s-a aplicat proprietatea (A ·B)−1 = B−1 ·A−1, adevaratapentru ∀ A,B ∈ L(Rn,Rn). Aceasta relatie o ınmultim la dreapta cu vectorulΓ0F

(x(1))

si rezulta

Γ1F(x(1))

= N(x(k))

=

[∞∑k=0

(I − Γ0F

′ (x(1)))k]

Γ0F(x(1)).

In ultima relatie aplicam norma si majoram

∥∥N (x(1))∥∥ ≤ [ ∞∑

k=0

∥∥I − Γ0F′ (x(1)

)∥∥k]∥∥Γ0F(x(1))∥∥

=

(∞∑k=0

αk0

)∥∥Γ0F(x(1))∥∥ =

1

1− α0

∥∥Γ0F(x(1))∥∥ .

In concluzie avem inegalitatea∥∥N (x(1))∥∥ ≤ 1

1− α0

∥∥Γ0F′ (x(1)

)∥∥ . (2.4)

Consideram aplicatia G(x) = x − Γ0F (x). Derivata Frechet a aplicatieG este G′(x) = I − Γ0F

′ (x) pentru ca Γ0 este o matrice constanta. De underezulta ca G′

(x(0))

= 0. Acum putem scrie

G(x(1))−G

(x(0))

= x(1) − Γ0F(x(1))−[x(0) −N

(x(0))]

= x(1) − Γ0F(x(1))− x(1) = −Γ0F

(x(1))

Acum rezulta egalitatea∥∥G (x(1))−G

(x(0))−G′

(x(0)) (x(1) − x(0)

)∥∥ =∥∥Γ0F

(x(1))∥∥ , (2.5)

37


unde s-a tinut cont ca G′(x(0))

= 0.

Sa aratam ca aplicatia G′ este Lipschitz continua.

‖G′(y)−G′(x)‖ = ‖I − Γ0F′ (y)− I + Γ0F

′ (x)‖≤ ‖Γ0‖ · ‖F ′ (y)− F ′ (x)‖ = β0γ ‖y − x‖ .

Deoarece β0γ < 1 rezulta ca aplicatia G′ este Lipschitz continua. Acumaplicam teorema de medie 1.2.6 pentru functia G ın egalitatea (2.5).∥∥Γ0F

(x(1))∥∥ =

∥∥G (x(1))−G

(x(0))−G′

(x(0)) (x(1) − x(0)

)∥∥≤ β0γ

2

∥∥x(1) − x(0)∥∥2 ≤ β0γη

20

2=α0

2η0

Din relatia (2.4) si (2.5) rezulta

∥∥N (x(1))∥∥ ≤ 1

1− α0

· α0

2η0 .

Facem notatia

η1 =1

1− α0

· α0

2η0 ,

atunci avem ındeplinita conditia∥∥N (x(1))∥∥ ≤ η1 , (2.6)

conditie similara cu conditia 3 din ipoteza teoremei. Notam cu

α1 = β1γη1 =β0γ

1− α0

· α0η0

2(1− α0)=

(β0γη0)α0

(1− α0)2=

1

2

(α0

1− α0

)2

Fie functia g : (0, 1/2]→ (0, 1], g(x) = [x/(1−x)]2 care este crescatoarepe (0, 1/2], pentru ca g′(x) = 2x/(1− x)3 > 0 pentru ∀ x ∈ (0, 1/2], atuncifunctia g atinge valoarea maxima ın x = 1/2 iar g(1/2) = 1 (vezi figura 2.1).Valoarea lui α1 este

α1 = β1γη1 =1

2

(α0

1− α0

)2

≤ 1

2(2.7)

Consideram sfera S1 = S(x(1), r1

)=x∣∣ ∥∥x− x(1)

∥∥ ≤ r1, x ∈ Rn

38


Figura 2.1: Functia g(x)

unde r1 =(1−√

1− 2α1

)η1/α1. Sa remarcam ca

r1 =

1−

√1−

(α0

1− α0

)2

1

2

(α0

1− α0

)2 · α0η0

2(1− α0)=

1−√

1− 2α0

(1− α0)2

α0

1− α0

η0

=1−√

1− 2α0

α0

η0 − η0 = r0 − η0 .

Sa aratam ca S1 ⊂ S0 = S(x(0), r0

)=x∣∣ ∥∥x− x(0)

∥∥ ≤ r0, x ∈ Rn

.

Sfera S1 este multimeax∣∣ ∥∥x− x(1)

∥∥ ≤ r1 = r0 − η0, x ∈ Rn

, atunci∥∥x− x(0)∥∥ =

∥∥x− x(1) + x(1) − x(0)∥∥ ≤ ∥∥x− x(1)

∥∥+∥∥x(1) − x(0)

∥∥≤ r0 − η0 + η0 = r0 ,

de unde rezulta caS1 ⊂ S0 ⊂ D0 . (2.8)

Recapitulam notatiile

β1 =β0

1− α0

, η1 =α0

2(1− α0)η0, α1 = β1γη1, r1 =

1−√

1− 2α1

α1

η1.

In relatiile (2.2), (2.6), (2.7) si (2.8) s-a dovedit ca

1′. ∃ Γ1 = Γ(x(1))

si ‖Γ1‖ ≤ β1 ,

3′.∥∥N (x(1)

)∥∥ ≤ η1 ,

39


4′. α1 = β1γη1 ≤ 1/2 ,

5′. S1 ⊂ S0 ⊂ D0 .

Acest set de conditii alaturi de conditia globala 2 este un set similar cuconditiile din ipoteza teoremei. Daca notam cu

βk =βk−1

1− αk−1

, ηk =αk−1

2(1− αk−1)ηk−1, αk = βkγηk, rk =

1−√

1− 2αkαk

ηk,

atunci ın mod analog se poate arata ca

1k. ∃ Γk = Γ(x(k))

si ‖Γk‖ ≤ βk ,

3k.∥∥N (x(k)

)∥∥ ≤ ηk ,

4k. αk = βkγηk ≤ 1/2 ,

5k. Sk ⊂ Sk−1 ⊂ Sk−2 ⊂ . . . ⊂ D0 .

Consideram relatia de recurenta a lui α si inegalitatea 4k

αk =1

2

(αk−1

1− αk−1

)2

≤ 1

2

de unde(αk−1

1− αk−1

)2

≤ (2αk−1)2 ⇔ αk−1

1− αk−1

≤ 2αk−1 ⇔ αk−1 ≤ 2αk−1 − 2α2k−1 .

Aceasta ultima inegalitate este echivalenta cu inegalitatea 2α2k−1−αk−1 ≤ 0 si

aceasta la randul ei cu inegalitatea αk−1(2αk−1−1) ≤ 0 . Pentru ca αk−1 > 0si αk−1 ≤ 1/2 rezulta ca

αk =1

2

(αk−1

1− αk−1

)2

≤ 1

2(2αk−1)2 .

Acum putem scrie sirul de inegalitati

2αk ≤ (2αk−1)2 ≤ (2αk−2)22

≤ . . . ≤ (2α0)2k ∀ k ∈ N∗ . (2.9)

De asemenea avem ηk = αk−1ηk−1/[2(1 − αk−1)] ≤ αk−1ηk−1, atunci putemscrie sirul de inegalitati ca ın relatia de mai sus

ηk ≤ αk−1ηk−1 ≤ αk−1αk−2ηk−2 ≤ . . . ≤ αk−1αk−2 . . . α0η0 . (2.10)

40


Din relatiile (2.9) si (2.10) rezulta inegalitatea

ηk ≤ 2−1 (2α0)2k−1

· 2−1 (2α0)2k−2

. . . 2−1 (2α0)20

η0 = 2−k (2α0)2k−1 η0

adicaηk ≤ 2−k (2α0)2k−1 η0 . (2.11)

Deoarece α0 ≤ 1/2 rezulta ca limk→∞ ηk = 0. De asemenea avem inega-litatea rk ≤ 2ηk pentru ∀ k ∈ N∗, aceasta se demonstreaza ın mod analogca inegalitatile η0 ≤ r0 ≤ 2η0, deja dovedita mai sus. Atunci rezulta calimk→∞ rk = 0. Atunci evident avem sirul de incluziuni

S0 ⊃ S1 ⊃ . . . ⊃ Sk ⊃ . . .

deci rezulta ca exita un unic x? ∈ Sk pentru ∀ k ∈ N astfel ıncat

limk→∞

x(k) = x? .

Sa aratam ca x? este solutia ecuatiei F (x) = 0. Deoarece aplicatia Feste diferentiabila Frechet pe D0 rezulta ca F este marginita pe o multimeΩ ⊂ D0 unde D0 este marginita (daca D0 este o sfera atunci D0 ar fi chiarun compact) deci Ω este marginita, atunci fie

M = maxx∈Ω‖F ′ (x)‖ .

Sa majoram pe∥∥F (x(k)

)∥∥∥∥F (x(k))∥∥ =

∥∥F ′ (x(k))

Γ(x(k))F(x(k))∥∥ ≤M

∥∥N (x(k))∥∥ ≤Mηk ,

atunci trecem la limita ın aceasta majorare

limk→∞

∥∥F (x(k))∥∥ =

∥∥∥ limk→∞

F(x(k))∥∥∥ =

∥∥∥F ( limk→∞

x(k))∥∥∥

= ‖F (x?)‖ ≤ limk→∞

Mηk = 0 .

Deoarece norma este o cantitate pozitiva sau nula rezulta ca ‖F (x?)‖ = 0,iar din proprietatiile normei avem ca ‖F (x?)‖ = 0 ⇔ F (x?) = 0.

Sa evaluam eroarea a priori din faptul ca x? ∈ Sk si din relatia (2.11),relatii adevarate pentru orice k ∈ N∗, atunci avem∥∥x(k) − x?

∥∥ ≤ rk ≤ 2ηk ≤ 21−k (2α0)2k−1 η0 .

Cu aceasta demonstratia este ıncheiata.

41


2.1.3 Programe pentru metoda Newton

Programele Mathcad pentru metoda Newton sunt prezentate ın aceastasectiune. Fie cazul bidimensional. Pentru exemplificare consideram sistemulneliniar

x31 − x2 = 25 ,x1 − x3

2 = −5 .(2.12)

Atunci ın Mathcad, [10], facem urmatoarele definiri

ORIGIN := 1 f1(x) := x31 − x2 − 25 f2(x) := x1 − x3

2 + 5

F (x) :=

(f1(x)f2(x)

).

Jacobianul functiei F , adica F ′ (x), se poate calcula cu ajutorul calcululuisimbolic. Atunci matricea J(x) este

J(x) :=

(3x2

1 −11 −3x2

2

).

Definim operatorii

Γ(x) := J(x)−1 si N (x) := Γ(x) · F (x) .

Programul 2.1.1. Parametri de intrare ın programul pentru metoda New-ton sunt: vectorul initial x si ε precizia impusa aproximatiei obtinuta prinprogram.

Newton(x, ε) := z ← xT

while |N (x) | ≥ εx← x−N (x))z ← stack

(z, xT

)return z

Exemplul 2.1.1. Apelul programului Newton pentru iteratia initiala

x :=

(10

)42


este

Newton(x, 10−14

)=

1 0−5 −42

−3.37332923489351 −27.9996926170134−2.06332234145433 −18.6652131298214

......

3.00712813027969 2.188852917506783.00060178080167 2.015867369134513.00000474688025 2.000124957493323.00000000029756 2.00000000783133

3 2

.

Convergenta patratica a metodei Newton, ın acest caz, are loc numai dela pasul al 18-lea din cei 23 de pasi. Acest lucru se datoreaza alegeri nefericitea iteratiei initiale.

2.1.4 Alegerea iteratiei initiale

Alegerea optima a iteratiei initiale se face pe baza conditiilor impuse deteorema 2.1.1 de convergenta globala a lui Kantorovich. Fie ecuatia neliniara(2.12). Definim un domeniu convex D0 = x | a ≤ x ≤ b, x ∈ R2 care sacontina numai solutia ce dorim s-o aproximam cu metoda Newton. Aceastaactiune se numeste separarea solutiilor ecuatiei F (x) = 0. In Mathcaddefinim cei doi vectori

a :=

(10

)si b :=

(54

),

care definesc pe D0. O alta posibilitate este sa definim o sfera prin precizareacentrului sferei si a razei sale. Cu ajutorul problemei de programare neliniare max

‖J(u)− J(v)‖‖u− v‖

u, v ∈ D0

determina constanta Lipschitz pentru operatorul J relativ la domeniul D0.Fie functia obiectiv

γ(u, v) :=norme

(J(u)− J(v)

)|u− v|

,

43


unde norme este functia Mathcad ce calculeaza norma euclidiana a matriciiiar modulul vectorului este norma ecuclidiana a vectorului. Fie doi vectoriinitiali, u ∈ D0 si v ∈ D0, de exemplu

u := a si v := b .

In Mathcad dupa ce au fost definite functia obiectiv si valorile initiale pentrunecunoscute, ıntr-un spatiu ecuatie se definesc retrictiile. Spatiu ecuatie esteregiunea dintre cuvintele cheie Given si Minimize sau Maximize. Atunciproblema de programare neliniara este

Given a ≤ u ≤ b a ≤ v ≤ b

(µω

):= Maximize(κ, u, v) .

Valorea functiei obiectiv ın solutiile optime µ si ω este constanta Lipschitzcautata.

γ := γ(µ, ω) γ = 29.9999586004977 .

Fie vectorul initial x := (1, 0)T. Prima conditie din teorema lui Kan-torovich se verifica prin calcul direct. Exista Γ(x).

Γ(x) =

(0 1−1 3

).

Definim celelalte functii ce depind de x, vectorul initial.

β(x) := norme(Γ(x)

)η(x) := |N (x)| α(x) := γ · β(x) · η(x) .

Fie functia:

r(x) :=

(1−

√1− 2 · α(x)

)η(x)

α(x).

Problema de programare neliniara ce determina cea mai mare sfera deconvergenta patratica pentru metoda Newton ın domeniul D0 este

max r(x)

α(x) <1

2x ∈ D0

.

Transpunera acestei probleme ın Mathcad este:

Given α(x) <1

2a ≤ x ≤ b s := Maximize(r, x) .

44


Solutia optima a problemei este iteratia de start pentru metoda Newton sicentru sferei de convergenta patratica

s =

(2.992785590487132.13539977585776

).

Raza sferei de convergenta patratica este

r(s) = 0.158048831996355 .

Apelul programului Newton cu aceasta iteratie de start este

Newton(s, 10−14

)=

2.99278559048713 2.135399775857763.00033106244535 2.008428067802043.00000134842740 2.000035429082073.00000000002392 2.00000000062959

3 2

.

2.1.5 Bazinul de atratie pentru metoda Newton

Bazinul de atractie depinde de metoda iterativa si de ecuatia considera-ta. Reprezentarea grafica a bazinelor de atractie se poate realiza cu ajutorulfunctiilor grafice din Mathcad [10]. O reprezentare intuitiva se obtine ın R2.Daca se doreste realizarea unor bazine de atractie pentru ecuatii din R3, deexemplu, din bazinul de atractie care este tridimensional vom putea vizualizadoar sectiuni prin acest bazin.

Pentru exemplificare vom considera sistemul neliniar din R2 (2.12). Seface definirea functiilor f1, f2, F (x) si a matricii J(x) ca ın sectiunea Pro-grame pentru metoda Newton. In plus se mai fac urmatoarele definiri:

a := −8 b := 12 m := 1000 h :=b− am

unde prin a si b se precizeaza segmentul [a, b] de pe axa x1. Prin m se indicanumarul de diviziuni de pe segmentul [a, b] iar h este lungimea diviziuni.Pentru axa x2 facem definiri analoage

c := −10 d := 10 n := 1000 q :=d− cn

unde prin c si d se precizeaza segmentul [c, d] de pe axa x2. Prin n se indicanumarul de diviziuni de pe segmentul [c, d] iar q este lungimea diviziuni.Mai definim doua variabile

kmax := 15 ε := 0.001 ,

45


cu urmatoarea semnificatie. Variabila kmax reprezinta numarul maxim deiteratii pe care ıl impunem metodei. Daca metoda numerica ,,nu reuseste” ınkmax pasi sa determine o solutie cu precizia ε, atunci consideram ca metodanu converge si oprim algoritmul.

Programul prezentat ın aceasta sectiune va returna pentru fiecare punctinitial de coordonate (a + `h, c + jq), punct identificat prin indicii ` si j,numarul de iteratii k, unde 0 ≤ k ≤ kmax. Aceste valori k vor fi elementelematricii B, care va avea m+ 1 linii si n+ 1 coloane.

Programul 2.1.2. Programul are ca parametri de intrare indicii ` si j.

N(`, j) := x← (a+ ` · h c+ j · q)T

return kmax on error δ ← J(x)−1 · F (x)return kmax on error µ← |δ|k ← 0while (µ ≥ ε) ∧ (k < kmax)

x← x− δk ← k + 1return kmax on error δ ← J(x)−1 · F (x)return kmax on error µ← |δ|

return k

Matricea B se genereaza cu ajutorul functiei Mathcad matrix(n,m,N),unde N este numele programului ce aplica metoda Newton

B := matrix(m,n,N) .

Cu ajutorul regiunii grafice Mathcad CountourP lot, ce va avea ca argumentmatricea B, se va realiza graficul bazinului de atractie folosind reprezentareacu linii de nivel (vezi ın Anexa 1 figura 3.1). Graficul a fost colorat cuconventia topografica prin care se realizeaza hartile geografice.

2.2 Metoda secantei si metoda Steffensen

2.2.1 Metoda secantei

Metoda secantei ın cazul n-dimensinal se poate obtine pe doua cai. Primacale consta ın liniarizarea ecuatiei F (x) = 0. Vom face aproximarea

F (x) ≈ A · x+ a

46


unde A ∈ L(Rn,Rn) si a ∈ Rn. Determinarea elementelor matricii A sia componentelor vectorului a, adica a n(n + 1) necunoscute, se poate facecunoscand n + 1 vectori initiali, x(0), x(1), . . . x(n), unde x(k) ∈ Rn, k =0, 1, . . . , n. Vom scrie

A · x(k) + a = F(x(k)), k = 0, 1, . . . , n .

Elementele lui A, respectiv componentele lui a rezulta dintr-un sistem liniarde n(n+1) ecuatii cu n(n+1) necunoscute. Ecuatia F (x) = 0, o vom ınlocuicu ecuatia liniara A · x + a = 0, a carei solutie x o vom considera iteratieurmatoare x(n+1). Procesul se continua lunand ın considerare vectori intialix(1), x(2), . . . x(n+1). Se observa ca pentru fiecare iteratie se utilizeaza n+ 1iteratii precedente si ca la fiecare pas trebuie rezolvate doua sisteme liniare,unul cu n(n+ 1) ecuatii iar celalalt cu n ecuatii.

Exemplul 2.2.1. Fie functia neliniara F : R2 → R2

F (x) =

(x2

1 − x2

2x1 + x1x2 − 3

)si matricea x

x =

0 −3

4

5

2

1

2−1

2

3

4

unde fiecare coloana reprezinta vectori initiali x(0), x(1) si x(2). Sistemulliniar, care permite determinarea componentelor A11, A12, A21 si A22 alematicii A si elementele a1 si a2 ale vectorului a, este

01

20 0 1 0

0 0 01

20 1

−3

4−1

20 0 1 0

0 0 −3

4−1

20 1

5

2

3

40 0 1 0

0 05

5

3

40 0

·

A11

A12

A21

A22

a1

a2

=

1

2

3

−17

16

33

8

−11

2

−31

8

.

47


Solutia acestui sistem liniar este

A =

A11 A12

A21 A22

=

409

148−269

74

211

74−75

74

a =

a1

a2

=

195

148

−369

148

.

Daca rezolvam sistemul linear A · x(3) + a = 0 rezulta solutia

x(3) =

3078

2239

6303

4478

∼=(

1.374720857525681.40754801250558

).

Matricea x care contine iteratiile rezultate prin metoda secantei este

x =

0 −3

4

5

2

3078

2239

1

2−1

2

3

4

6303

4478

.

Procesul se reia de la ınceput folosind vectori initiali x(1), x(2) si x(3). Dupaaplicarea acestui pas rezulta

x(4) =

(0.718399716028791.02550561839328

).

Sa remarcam ca solutia ecuatiei F (x) = 0 este x? = (1, 1)T.

A doua cale consta ın discretizarea metodei Newton, prin ınlocuireaderivatelor partiale cu diferente divizate de ordinul ıntai.

2.2.2 Constructia metodei secantei sia metodei Steffensen

Fie F : D ⊂ Rn → Rn un operator neliniar, h ∈ Rn un element oarecare siej, j ∈ In versorii axelor de coordonate e1 = (1, 0, . . . , 0), e2 = (0, 1, 0, . . . , 0),. . ., en = (0, 0, . . . , 1). In metoda Newton data de formula (2.1) vom luacomponentele derivatei Frechet dupa cum urmeaza

∂fk∂xj

= limhj→0

fk(x+ hjej)− fk(x)

hj≈ fk(x+ hje

j)− fk(x)

hj.

48


Derivata Frechet F ′ (x) este aproximata de matricea J(x, h).

J(x, h) =

f1(x+ h1e1)− f1(x)

h1

. . .f1(x+ hne

n)− f1(x)

hn

......

fn(x+ h1e1)− fn(x)

h1

. . .fn(x+ hne

n)− fn(x)

hn

(2.13)

Vom alege vectorul h diferit la fiecare iteratie (vom nota valorile succesiveale lui h cu h(k)) si astfel ıncat h(k) → 0 cand k → ∞. Astfel daca h(k) =x(k+1) − x(k), se obtine

x(k+1) := x(k) − J(x(k), x(k+1) − x(k)

)−1F(x(k)),

metoda secantei ın doi pasi, [22], deoarece la fiecare iteratie este nevoie dedoua iteratii precedente. Metoda a fost considerata pentru prima data subaceata forma de Korganoff ın anul 1961.

Daca h(k) = F(x(k)), se obtine metoda

x(k+1) := x(k) − J(x(k), F

(x(k)))−1

F(x(k)),

numita metoda Steffensen. Metoda a fost considerata pentru prima data deWegge ın articolul [35]. O bogata bibliografie la aceasta tema se gaseste ınmonografia lui Janko [20].

2.2.3 Convergenta metodelor secantei si Steffensen

Forma generala a unei metode cu mai multi pasi (p pasi p ∈ N, p ≥ 1)este

x(k+1) := G(x(k), x(k−1), . . . , x(k−p+1)

).

O forma particulara a acestei metode este

x(k+1) := G(x(k), h(k)

), h(k) = gk

(x(k), x(k−1), . . . , x(k−p+1)

),

unde G : D ×Dh ⊂ Rn × Rn → Rn si gk : Dk ⊂(Rn)p → Dh ⊂ Rn. Putem

lua pentru h(k) un anumit sir din Rn si metoda devine

x(k+1) := G(x(k), h(k)

). (2.14)

49


Lema 2.2.1. Fie G : D × Dh ⊂ Rn × Rn → Rn un operator neliniar six? ∈ D. Presupunem ca exista o constanta α < 1 astfel ıncat

‖G(x, h)− x?‖ ≤ α ‖x− x?‖ , ∀ x ∈ S, h ∈ D′h ,

unde S = S (x?, r) ⊂ D si D′h ⊂ D. Atunci pentru orice sirh(k)⊂ D′h sirul

x(k)

dat (2.14) apartine lui S si converge la x?. In plus R(1) ≤ Q(1) ≤ α.

Demonstratie. Avem∥∥x(k) − x?∥∥ =

∥∥G (x(k−1), h(k−1))− x?

∥∥ ≤ α∥∥x(k−1) − x?

∥∥ ≤ . . .

. . . ≤ αk∥∥x(0) − x?

∥∥ ,

deci sirulx(k)⊂ S si x(k) → x?, cand k → ∞. Partea a doua a lemei

rezulta direct din definitia 1.4.2, a lui Q(1) si teorema 1.4.3.

Vom considera ın continuare metoda mai generala

x(k+1) := x(k) − J(x(k), h(k)

)−1F(x(k)), (2.15)

unde J : Rn × Rn → L(Rn)

este un anumit operator neliniar(nu neaparat

de forma (2.13))

iarh(k)

un sir din Rn. Se vede ca metoda secantei cu doi

pasi si metoda Steffensen sunt cazuri particulare ale metodei (2.15). In cazulın care operatorul J este dat de (2.13), J(x, h) tinde la F ′ (x) cand h → 0.Aceasta observatie conduce la urmatoarea definitie:

Definitia 2.2.1. Fie F : D ⊂ Rn → Rn diferentiabil Gateaux pe D0 ⊂ D sifie J : Dj×Dh ⊂ Rn×Rn → L

(Rn). Operatorul J se numeste o aproximare

consistenta a lui F ′ pe D0 ⊂ Dj daca zero este punct limita pentru Dh si

limh→0h∈Dh

J(x, h) = F ′ (x) uniform pe D0 .

Se vede ca, daca F este continuu diferentiabil pe D0, atunci operatorul Jdat de (2.13) este o aproximatie consistenta a lui F ′.

Lema 2.2.2. Fie F : D ⊂ Rn → Rn diferentiabil Gateaux pe o vecinatateS0 ⊂ D a lui x?, solutie a ecuatiei F (x) = 0. Presupunem ca F ′ estecontinuu ın x? si ca F ′ (x?) este nesingulara. Fie J : Rn × Rn → L

(Rn)

oaproximare consistenta a lui F ′ pe S0. Atunci exista, constantele reale, δ > 0si r > 0 astfel ıncat functia G : S0 → Rn data de

G(x, h) = x− J(x, h)−1 · F (x)

este definita pentru x ∈ S = S (x?, δ), h ∈ D′h = Dh ∩ S (0, r) si

‖G(x, h)− x?‖ ≤ ω(x, h) ‖x− x?‖ , ∀ x ∈ S, h ∈ D′h ,

unde ω(x, h)→ 0 pentru x→ x? si h→ 0.

50


Demonstratie. Notam cu β =∥∥F ′ (x?)−1

∥∥ si fie 0 < ε < (2β)−1. DeoareceJ este o aproximare consistenta a lui F ′ pe S0, exista un numar real r > 0astfel ıncat D′h = Dh ∩ S (0, r) este nevida si

‖J(x, h)− F ′ (x)‖ ≤ ε

2, ∀ x ∈ S0, h ∈ D′h .

F ′ fiind continuu ın x?, rezulta ca exista o constanta reala δ > 0 astfel ıncatS = S (x?, δ) ⊂ S0 si

‖F ′ (x)− F ′ (x?)‖ ≤ ε

2, ∀ x ∈ S .

Asadar

‖J(x, h)− F ′ (x?)‖ ≤ ‖J(x, h)− F ′ (x)‖+ ‖F ′ (x)− F ′ (x?)‖ ≤ ε

pentru ∀ x ∈ S, h ∈ D′h. Din lema 1.1.7 rezulta ca exista J(x, h)−1 si satisfacerelatia ∥∥J(x, h)−1

∥∥ ≤ η =β

1− βε∀ x ∈ S, h ∈ D′h .

Astfel, G este definit pe S ×D′h si

‖G(x, h)− x?‖=∥∥J(x, h)−1 [J(x, h)(x− x?)− F (x)]

∥∥ ≤ η ‖J(x, h)(x− x?)− F (x)‖≤ η (‖J(x, h)− F ′ (x)‖+ ‖F ′ (x)− F ′ (x?)‖) ‖x− x?‖

+ η ‖F (x)− F (x?)− F ′ (x?) (x− x?)‖ .

Relatia din lema are loc cu

ω(x, h) = η ‖J(x, h)− F ′ (x)‖+ η ‖F ′ (x)− F ′ (x?)‖

+ η‖F (x)− F (x?)− F ′ (x?) (x− x?)‖

‖x− x?‖.

Acum, deoarece F ′ exista si este continuu ın x? iar J este o aproximatieconsistenta a lui F ′, rezulta ca ω(x, h)→ 0, daca x→ x? si h→ 0.

O aplicatie imediata a acestei leme este urmatorul rezultat asupraconvergentei metodei (2.15).

Teorema 2.2.1. Fie F si J ca ın lema 2.2.2. Atunci exista o sfera S =S (x?, δ1) ⊂ S0 si un numar real r1 > 0 astfel ıncat pentru orice x(0) ∈ S sipentru orice sir

h(k)⊂ Dh ∩ S (0, r1), sirul

x(k)

dat de (2.15) apartine

lui S si converge la x?. Mai mult, daca h(k) → 0 cand k → ∞, atunciR(1) = Q(1) = 0.

51


Demonstratie. Fie δ si r ca ın lema 2.2.2. Deoarece ω(x, h) → 0, putemdetermina un δ1 ≤ δ si un r1 ≤ r astfel ıncat

ω(x, h) ≤ α < 1 , ∀ x ∈ S (x?, δ1) , h ∈ Dh ∩ S (0, r1) .

Existenta sirului rezulta din lema 2.2.2 iar convergenta lui la x? din lema2.2.1. Tot din lema 2.2.1 rezulta

R(1) ≤ Q(1) ≤ α

si cum α este arbitar, obtinem R(1) = Q(1) = 0.

Din aceasta teorema rezulta imediat convergenta locala a metodei secanteiın doi pasi si a metodei Steffensen. Mai mult, daca F ′ este continua Lipschitzpe D iar J este o aproximatie strict consistenta, adica

‖F ′ (x)− J(x, h)‖ ≤ c ‖h‖ , ∀ x ∈ D0 , h ∈ Dh ∩ S (0, r) ,

atunci se poate arata ca r ≥ q ≥ 2 pentru metoda Steffensen si r ≥ (1 +√5)/2, pentru metoda secantei ın doi pasi [26].

2.2.4 Programe pentru metoda secantei

In cele ce urmeaza prezentam programele Mathcad pentru metoda secan-tei. Fie cazul bidimensional, adica n = 2 si sistemul neliniar (2.12). Atunciın Mathcad, [10], facem urmatoarele definiri:

ORIGIN := 1 n := 2 f1(x) := (x1)2 − x2 f2(x) := x1 (x2 + 1)− 2 ,

F (x) :=

[f1(x)f2(x)

].

Jacobianul functiei F , adica F ′ (x), definit cu ajutorul diferentelor divizateeste:

J(x, h) :=

f1

[x+

(h1

0

)]− f1(x)

h1

f1

[x+

(0h2

)]− f1(x)

h2

f2

[x+

(h1

0

)]− f2(x)

h1

f2

[x+

(0h2

)]− f2(x)

h2

(2.16)

Programul 2.2.1. Parametri de intrare ın programul Secanta sunt: vectoriinitiali y si x, parametrul r ce defineste norma folosita si ε precizia impusaaproximatie solutiei obtinuta prin program.

52


Secanta(y, x, r, ε) := h← y − xδ ← no(r, F (x))while δ ≥ ε

break if |J(x, h)|=0return x on error h← J(x, h)−1 · F (x)x← x− hδ ← no(r, F (x))

return x

Exemplul 2.2.2. Apelul programului Mathcad Secanta ın norma euclidiana(adica r = 2) este

Secanta

[(00

),

(53

), 2, 10−13

]=

(11

),

sau ın norma ‖·‖1 (adica r = 1)

Secanta

[(00

),

(53

), 1, 10−13

]=

(11

).

2.2.5 Programe pentru metoda Steffensen

Prezentam programele Mathcad pentru metoda Steffensen. Fie cazul bidi-mensional, adica n = 2 si sistemul neliniar (2.12). Atunci ın Mathcad, [10],facem urmatoarele definiri:

ORIGIN := 1 n := 2 f1(x) := (x1)2 − x2 f2(x) := x1 (x2 + 1)− 2 ,

F (x) :=

[f1(x)f2(x)

].

Jacobianul functiei F , adica F ′ (x), definit cu ajutorul diferentelor divizateeste dat de (2.16). Pentru functia norma se foloseste functia utilizator

no(r, x) :=

(n∑k=1

|xk|r)1/r

.

Programul 2.2.2. Parametri de intrare ın programul Steffensen sunt: vec-torul initial x, parametrul r ce defineste norma folosita si ε precizia impusaaproximatie solutiei obtinuta prin program.

53


Steffensen(x, r, ε) := δ ← no(r, F (x))while δ ≥ ε

break if |J(x, F (x))|=0return x on error x← x− J(x, F (x))−1 · F (x)δ ← no(r, F (x))

return x

Exemplul 2.2.3. Apelul programului Mathcad Steffensen ın norma eucli-diana (adica r = 2) este

Steffensen

[(53

), 2, 10−13

]=

(11

),

sau ın norma ‖·‖1 (adica r = 1)

Steffensen

[(53

), 1, 10−13

]=

(11

).

2.3 Metode cvasi-Newton

In anul 1965 si 1970 ın articolele [4] si [5] Broyden considera o metodaintitulata de autor ca metoda cvasi-Newton. De fapt aceasta metoda este ometoda care generalizeaza metoda secantei ın Rn. Pentru alte considerentese pot consulta monografiile lui Ortega si Rheinboldt [26] si respectiv [27]lucrarea lui Dennis si More [14] sau lucrearea a lui Gay [17]. In generalmetodele de tip cvasi-Newton sunt de forma

x(k+1) := x(k) −B(x(k))−1

F(x(k)),

sau

x(k+1) := x(k) −B−1k F

(x(k)),

adica matricea B nu depinde de F sau depinde numai de k ın cel de al doileacaz. Daca matricea B = F ′ (x) atunci evident obtinem metoda Newton.

2.3.1 Leme preliminare

Pentru a dovedi convergenta metodei Broyden avem nevoie de umatoareleleme.

54


Lema 2.3.1. Fie u, v ∈ Rn, u 6= 0, v 6= 0 si α ∈ (0, 1). Daca ‖u− v‖ ≤α ‖u‖, atunci

〈u, v〉 > 0,

∣∣∣∣1− ‖v‖‖u‖∣∣∣∣ ≤ α si 1− 〈u, v〉2

‖u‖2 · ‖v‖2 ≤ α2 .

Demonstratie. In inegalitatea triunghiului ‖u+ v‖ ≤ ‖u‖ + ‖v‖ substituimpe u cu u−v si rezulta ‖u‖ ≤ ‖u− v‖+‖v‖, relatie din care avem inegalitatea|‖u‖ − ‖v‖| ≤ ‖u− v‖. Aceasta inegalitate o ımpartim cu ‖u‖ si rezulta∣∣∣∣1− ‖v‖‖u‖

∣∣∣∣ ≤ ‖u− v‖‖u‖≤ α ,

de unde avem a doua inegalitate din concluzia lemei∣∣∣∣1− ‖v‖‖u‖∣∣∣∣ ≤ α .

Fie ω = 〈u, v〉 /(‖u‖·‖v‖

)si sa evaluam urmatoarea expresie ‖u− v‖2 =

〈u− v, u− v〉

〈u− v, u− v〉 = 〈u, u〉 − 2 〈u, v〉+ 〈v, v〉 = ‖u‖2 − 2 〈u, v〉+ ‖v‖2

= ‖u‖2

(1− 2

〈u, v〉‖u‖2 +

‖v‖2

‖u‖2

)= ‖u‖2

(1− 2ω

‖v‖‖u‖

+‖v‖2

‖u‖2

).

Punctul de minim pentru trinomul t2− 2ωt+ 1 este pentru t = ω si valoareaminima este 1− ω2, deci ‖u− v‖2 ≥ ‖u‖2 (1− ω2

), atunci

‖u− v‖2

‖u‖2 ≥ 1− ω2 .

Deoarece ‖u− v‖ ≤ α ‖u‖ rezulta ca

1− ω2 ≤ ‖u− v‖2

‖u‖2 ≤ α2 ,

de unde rezulta cea de a treia inegalitate din concluzia lemei

1− 〈u, v〉2

‖u‖2 · ‖v‖2 ≤ α2 .

Din relatia ‖u− v‖2 = ‖u‖2 − 2 〈u, v〉+ ‖v‖2 rezulta ca 2 〈u, v〉 = ‖u‖2 +‖v‖2 − ‖u− v‖2. Acum tinem cont de inegalitatea din ipoteza ‖u− v‖ ≤

55


α ‖u‖, atunci avem 2 〈u, v〉 ≥ ‖u‖2+‖v‖2−α2 ‖u‖2 =(1−α2

)‖u‖2+‖v‖2 > 0

pentru ca α > 0 iar u 6= 0 si v 6= 0. Atunci s-a demonstrat si prima inegalitatedin concluzia lemei

〈u, v〉 > 0 .

Lema 2.3.2 (Shermann-Morrison 1949). Fie u, v ∈ Rn, A ∈ L(Rn,Rn), Anesingulara, atunci A+ uvT este nesingulara si

(A+ uvT

)−1= A−1 − A−1uvTA−1

1 + 〈v, A−1u〉.

Demonstratie. Demonstratia se face direct prin calcul, verificand identitatea(A+ uvT

)−1(A+ uvT

)= I. Sa calculam produsul

(A−1 − A−1uvTA−1

1 + 〈v,A−1u〉

)(A+ uvT)

= I + A−1uvT − A−1uvTA−1

1 + 〈v, A−1u〉(A+ uvT

)= I + A−1uvT

(I −

A−1(A+ uvT

)1 + 〈v,A−1u〉

)

= I + A−1uvT

(I − I + A−1uvT

1 + 〈v,A−1u〉

)= I + A−1uvT

(I + A−1uvT − I − A−1uvT

1 + 〈v, A−1u〉

)= I + A−1uvT 0

1 + 〈v,A−1u〉= I .

In sirul de egalitati s-a folosit faptul ca A−1uvT = 〈v, A−1u〉. Din calculul demai sus rezulta concluzia lemei.

Observatia 2.3.1. Sa presupunem ca Hk este inversabila si fie Bk = H−1k .

Conform lemei 2.3.2, ın care luam u = HkF(x(k+1)

)si vT = dT

k /dTk y

(k),

unde s-a notat y(k) = F(x(k+1)

)−F

(x(k)), matricea Hk+1 este de asemenea

56


inversabila si

Bk+1 = H−1k+1

= Bk +1

1− dTk

dTk y

(k)BkHkF (x(k+1))

BkHkF(x(k+1)

) dTk

dTk y

(k)Bk

= Bk +1

dTk y

(k) − dTkF (x(k+1))

F(x(k+1)

)dTkBk

= Bk −dTkBk

dTkF (x(k))

F(x(k+1)

). (2.17)

Lema 2.3.3. Fie u, v ∈ Rn astfel ıncat vTu = 1. Atunci∥∥I − vuT∥∥ ≤ ‖u‖ · ‖v‖ .

Demonstratie. Fara sa restrangem generalitatea putem considera pe u decomponente 1, 0, . . . , 0. Atunci din vTu = 1 rezulta ca prima componenta alui v va fi v1 = 1; vectorul de componente v2, v3, . . . , vn, din Rn−1, ıl vomnota cu v′. Fie z ∈ Rn. Lema este demonstrata daca aratam ca∥∥(I − vuT

)z∥∥ ≤ ‖z‖ · ‖v‖

si ca pentru un anumit z se obtine egalitate. Presupunem ca z este de forma

z =

(z1

z′

),

unde z′ ∈ Rn−1. Relatia precedenta se reduce la

‖z − z1v‖2 = ‖z′ − z1v′‖2 ≤

(z2

1 + ‖z′‖2)(

1 + ‖v′‖2)

sau dupa efectuarea calculelor se obtine inecuatia echivalenta

z21 + 2 〈z′, v′〉 z1 + ‖z′‖2 · ‖v′‖2 ≥ 0 .

Aceasta relatie este satisfacuta pentru orice z1 ∈ R ıntrucat ∆ = 〈z′, v′〉2 −‖z′‖2 ‖v′‖2 ≥ 0 iar egalitatea se obtine pentru z′ = v′ si z1 = −‖v′‖2.

Lema 2.3.4. Fie F : D0 ⊂ Rn → Rn un operator diferentiabil Frechetpe multimea D0 si x? ∈ D0. Presupunem ca derivata Frechet, F ′, satisfacerelatia ‖F ′ (x)− F ′ (x?)‖ ≤ κ ‖x− x?‖, pentru orice x ∈ D0 si fie x, y ∈ D0,B ∈ L(Rn,Rn), d ∈ Rn astfel ıncat dTF (x) 6= 0 si

B′ = B + [F (y)− F (x)−B(y − x)]dTB

dTB(y − x),

57


q =‖y − x‖ ·

∥∥dTB∥∥

|dTB(y − x)|.

Atunci

‖B′ − F ′ (x?)‖ ≤ q ‖B − F ′ (x?)‖+qκ

2 ‖y − x‖(‖y − x?‖2 + ‖x− x?‖2) .

Demonstratie. Avem

B′ − F ′ (x?) = B − F ′ (x?) + [F (y)− F (x?)− F ′ (x?) (y − x?)]

−[F (x)− F (x?)− F ′ (x?) (x− x?)]− [B − F ′ (x?)](y − x) dTB

dTB(y − x).

Atunci rezulta

B − F ′ (x?)− [B − F ′ (x?)](y − x)dTB

dTB(y − x)

= [B − F ′ (x?)][I − (y − x)

dTB

dTB(y − x)

].

Daca luam u = y − x, vT = dTB/dTB(y − x) atunci avem evident vTu = 1si putem aplica lema 2.3.3. Obtinem∥∥∥∥I − (y − x)

dTB

dTB(y − x)

∥∥∥∥ = q .

In expresia lui B′ − F ′ (x?) pentru termenii din mijloc avem

‖F (y)− F (x?)− F ′ (x?) (y − x?)‖ ≤ κ

2‖y − x?‖2

si

‖F (x)− F (x?)− F ′ (x?) (x− x?)‖ ≤ κ

2‖x− x?‖2

unde s-a aplicat teorema de medie 1.2.6. Atunci

‖B′ − F ′ (x?)‖ ≤ q ‖B − F ′ (x?)‖+qκ

2 ‖y − x‖(‖y − x?‖2 + ‖x− x?‖2)

ceea ce era de demonstrat.

Observatia 2.3.2. Daca luam x = x(k), y = x(k+1), B = Bk si d =HTk HkF

(x(k)), atunci

q =

∥∥HkF(x(k))∥∥ · ∥∥F (x(k)

)HTk HkBk

∥∥∣∣∣F (x(k))THTk HkF (x(k))

∣∣∣=

∥∥HkF(x(k))∥∥ · ∥∥∥(HkF

(x(k)))T∥∥∥∣∣∣(HkF (x(k)))

THkF (x(k))

∣∣∣ = 1 .

58


2.3.2 Constructia metodei Broyden

Fie aplicatia neliniara F : D0 ⊂ Rn −→ Rn si ecuatia atasataF (x) = 0. Daca derivata Frechet a functiei F este Lipschitz continua, adica‖F ′ (y)− F ′ (x)‖ ≤ L ‖y − x‖, atunci, conform teoremei de medie 1.2.6, avem

‖F (y)− F (x)− F ′ (x) (y − x)‖ ≤ L

2‖y − x‖2 .

Putem face aproximarea

F (y) ∼= F (x) + F ′ (x) (y − x) .

In aceasta formula facem pe x = x(k) si y = x(k+1) si rezulta

F(x(k+1)

) ∼= F(x(k))

+ F ′(x(k)) (x(k+1) − x(k)

).

Consideram egalitatea F ′(x(k)) (x(k+1) − x(k)

)= F

(x(k+1)

)− F

(x(k)), nu-

mita si ecuatia cvasi-Newton si consideram pasul iterativ

x(k+1) := x(k) −B−1k F

(x(k)), (2.18)

unde cautam matricea Bk, care sa satisfaca ecuatia cvasi-Newton. Broydena considerat urmatoarele formule iterative

y(k) := F(x(k+1)

)− F

(x(k)), (2.19)

s(k) := x(k+1) − x(k) , (2.20)

Bk+1 := Bk +

(y(k) −Bks

(k)) (s(k))T

‖s(k)‖2 . (2.21)

Daca avem iteratia initiala x(0) si matricea initiala B0 din relatia (2.18)gasim pe x(1), cu x(0) si x(1) aplicam formulele (2.20) si (2.21). Vom obtine pey(0) si s(0) iar cu formula (2.21) calculam pe B1, apoi se ıncepe de la ınceputcalculand pe x(2). Cu x(2) si x(1) aplicam formulele (2.20) si (2.21) si asa maideparte.

Sa verificam ca matricea Bk verifica ecuatia cvasi-Newton, adica avemidentitatea F ′

(x(k))s(k) = y(k).

Bk+1s(k) =

(Bk +

(y(k) −Bks

(k)) (s(k))T

‖s(k)‖2

)s(k)

= Bks(k) +

(y(k) −Bks

(k)) ⟨s(k), s(k)

⟩‖s(k)‖2 = y(k)

59


Din punct de vedere al calculului nu avem un avantaj pentru ca ın loculcalculului inversei matricii F ′

(x(k))

ın ecuatia cvasi-Newton pentru procesuliterativ

x(k+1) := x(k) + F ′(x(k))−1 (

F(x(k+1)

)− F

(x(k)))

,

se calculeaza inversa matricii Bk pentru urmatorul proces iterativ

x(k+1) := x(k) +B−1k

(F(x(k+1)

)− F

(x(k)))

.

Cu ajutorul lemei 2.3.2 (Shermann-Morrison) putem evita calculul inverseimatricii Bk. Fie ın lema Shermann-Morrison A = Bk, u = y(k) − Bks

(k) si

v = s(k)/∥∥s(k)

∥∥2, atunci conform lemei, daca B0 este nesingulara rezulta ca

B0 +

(y(0) −B0s

(0)) (s(0))T

‖s(0)‖2

este nesingulara si exista B−11

B−11 = B−1

0 +

B−10

(y(0) −B0s

(0)) (s(0)

)T

‖s(0)‖2B−10

1 +

⟨s(0)

‖s(0)‖2 , B−10 (y(0) −B0s(0))

⟩ .

Prin inductie matematica, daca Bk este nesingulara atunci conform lemeirezulta ca

Bk +

(y(k) −Bks

(k)) (s(k))T

‖s(k)‖2

este nesingulara si exista B−1k+1

B−1k+1 = B−1

k +

B−1k

(y(k) −Bks

(k)) (s(k)

)T

‖s(k)‖2B−1k

1 +

⟨s(k)

‖s(k)‖2 , B−1k (y(k) −Bks(k))

⟩ . (2.22)

Dar⟨s(k)

‖s(k)‖2 , B−1k

(y(k) −Bks

(k))⟩

=

⟨s(k)

‖s(k)‖2 , B−1k y(k) − s(k)

⟩

=

⟨s(k)

‖s(k)‖2 , B−1k y(k)

⟩−

⟨s(k)

‖s(k)‖2 , s(k)

⟩=

1

‖s(k)‖2

⟨s(k), B−1

k y(k)⟩

− 1

‖s(k)‖2

⟨s(k), s(k)

⟩=

1

‖s(k)‖2

⟨s(k), B−1

k y(k)⟩− 1 .

60


Atunci numitorul din expresia lui B−1k+1, data de relatia (2.22) este

1 +

⟨s(k)

‖s(k)‖2 , B−1k

(y(k) −Bks

(k))⟩

= 1 +1

‖s(k)‖2

⟨s(k), B−1

k y(k)⟩− 1 =

1

‖s(k)‖2

⟨s(k), B−1

k y(k)⟩.

Numaratorul din aceeasi expesie a lui B−1k+1 poate fi scrisa sub forma

B−1k

(y(k) −Bks

(k)) (s(k)

)T

‖s(k)‖2B−1k =

(B−1k y(k) − s(k)

) (s(k))T

‖s(k)‖2B−1k .

Atunci expresia lui B−1k+1 se poate scrie sub forma

B−1k+1 = B−1

k +

(B−1k y(k) − s(k)

) (s(k))T⟨

s(k), B−1k y(k)

⟩ B−1k . (2.23)

Observatia 2.3.3. Inversarea unei matrici A ∈ Mn,n(R) necesita operatiide ordinul n3. De exemplu, daca se foloseste regula dreptunghilui numaruloperatiilor este 4n3 − n2 − n [24, pag. 22]. In metoda Broyden numaruloperatiilor prin folosirea lemei Shermann-Morrison este de ordinul n2. Deciordinul de marime pentru operatiile din metoda Broyden este n2, iar pentrumetoda Newton ordinul de marime al numarului de operatii este n3.

Notam pe B−1k cu Hk, atunci procesul iterativ al metodei Broyden devine

x(k+1) := x(k) −HkF(x(k)),

y(k) := F(x(k+1)

)− F

(x(k)),

s(k) := x(k+1) − x(k) ,

Hk+1 := Hk +

(Hky

(k) − s(k)) (s(k))T

〈s(k), Hky(k)〉Hk ,

(2.24)

pentru k = 0, 1, . . ., unde x(0) ∈ D ⊂ Rn si H0 ∈Mn,n(R) sunt dati. Facem

notatiile x = x(k), x = x(k+1), s = s(k), y = y(k), B = Bk, B = Bk+1 , H = Hk

si H = Hk+1. Atunci metoda Broyden poate fi scrisa sub formax := x−HF (x) ,y := F (x)− F (x) ,s := x− x ,

H := H +(Hy − s) sT

〈s,Hy〉H ,

(2.25)

61


unde x ∈ D ⊂ Rn si H ∈Mn,n(R) sunt dati.

2.3.3 Convergenta metodei Broyden

Conergenta locala si superliniara a metodei Quasi-Newton a fost aratatade Broyden, Dennis si More ın articolul [6]. Presupunem ca aplicatia F :D ⊂ Rn → Rn ındeplineste urmatoarele conditii:

1. (a) Aplicatia F este continuu diferentiabila pe D, unde D este omultime deschisa si convexa,

(b) Exista x? ∈ D astfel ıncat F (x?) = 0 si exista F ′ (x?)−1, unde F ′

este un operator de la Rn la multimea aplicatiilor.

2. Aplicatia F ′ este Lipschitz continua pe multimea deschisa si convexaD, adica ‖F ′ (y)− F ′ (x)‖ ≤ κ ‖y − x‖ pentru orice x, y ∈ D.

Definitia 2.3.1. Sirulx(k)⊂ Rn are o convergenta cel putin superliniara

daca exista un sir αk ⊂ R astfel ıncat

limk→∞

αk = 0 si∥∥x(k+1) − x?

∥∥ ≤ αk∥∥x(k) − x?

∥∥ .

Observatia 2.3.4. Din inegalitatea∥∥x(k+1) − x?

∥∥ ≤ αk∥∥x(k) − x?

∥∥ rezultaca ∥∥x(k+1) − x?

∥∥‖x(k) − x?‖

≤ αk

iar

limk→∞

∥∥x(k+1) − x?∥∥

‖x(k) − x?‖= 0 .

Atunci rezulta ca R− ordinul de convergenta este r > 1.

Definitia 2.3.2. Sirulx(k)⊂ Rn are o convergenta cel putin patratica

daca exista o constanta β ∈ R astfel ıncat∥∥x(k+1) − x?

∥∥ ≤ β∥∥x(k) − x?

∥∥2

pentru orice k ∈ N.

Teorema 2.3.1. Daca aplicatia neliniara F : D ⊂ Rn → Rn satisfaceconditiile 1(a) si 1(b), de la pagina 62, atunci exista o multime deschisaS ⊂ D astfel ıncat x? ∈ S iar iteratiile metodei Newton

x(k+1) := x(k) − F ′(x(k))−1

F(x(k)),

sunt definite silimk→∞

x(k) = x? ,

iar convergenta este superliniara. Daca aplicatia F satisface si conditia 2,de la pagina 62, atunci convergenta metodei Newton este cel putin patratica.

62


Demonstratie. Pentru demonstratie vezi [27, p. 206-214].

Teorema 2.3.2. Daca aplicatia neliniara F : D ⊂ Rn → Rn satisfaceconditiile 1(a) si 1(b), de la pagina 62 si matriciile B(x(k)) sunt inversabilepentru fiecare x(k) si ρ

(B (x?)−1 F (x?)

)= σ < 1, atunci sirul definit de

relatia

x(k+1) := x(k) −B(x(k))−1

F(x(k))

pentru k = 0, 1, . . . si x(0) dat, converge la x?, iar R-ordinul de convergentaeste 1.

Demonstratie. Pentru demonstratie vezi [27, pag. 206-214].

Observatia 2.3.5. Daca B(x) = F ′ (x) atunci rezulta ca σ = 0. In acestcaz avem metoda Newton si rezulta o convergenta cel putin superliniara.

Teorema 2.3.3. Daca aplicatia neliniara F : D ⊂ Rn → Rn satisfaceconditiile 1(a) si 1(b), de la pagina 62 si fie Bk ⊂ L(Rn,Rn) astfel ıncat Bk

este nesingulara pentru orice k ∈ N, atunci sirulx(k)

generat de formulaiterativa

x(k+1) := x(k) −B−1k F

(x(k))

pentru k = 0, 1, . . . si x(0) dat, converge la x?. Convergenta este cel putinsuperliniara daca

limk→∞

∥∥[Bk − F ′(x(k))] (

x(k+1) − x(k))∥∥

‖x(k+1) − x(k)‖= 0 .

Demonstratie. Pentru demonstratie vezi [14].

Teorema 2.3.4. Fie aplicatia neliniara F : D0 ⊂ Rn → Rn diferentiabilaFrechet pe D0 si x? ∈ D0 o solutie a ecuatiei F (x) = 0. Presupunem caF ′ satisface relatia ‖F ′ (x)− F ′ (x?)‖ ≤ κ ‖x− x?‖, pentru orice x ∈ D0 sica F ′ (x?) este inversabila. Atunci exista numerele δ si ε astfel ıncat daca‖B0 − F ′ (x?)‖ ≤ δ si

∥∥x(0) − x?∥∥ ≤ ε, metoda Broyden, data de formulele

(2.24), cu iteratiile initiale x(0) si H0 = B−10 converge la x?.

Demonstratie. Fie constanta pozitiva β =∥∥F ′ (x?)−1

∥∥. Impunem lui ε con-

ditia naturala S(x(0), ε

)⊂ D0. Deoarece ‖B0 − F ′ (x?)‖ ≤ δ consideram

pe β astfel ıncat 2βδ < 1, rezulta, conform lemei 1.1.7, ca exista B−10 = H0

si ‖H0‖ ≤ β/(1 − 2βδ). Asadar, iteratia urmatoare din metoda Broyden,

63


x(1) = x(0) − H0F(x(0))

este definita. Sa notam ek =∥∥x(k) − x?

∥∥, atunciavem

e1 =∥∥x(1) − x?

∥∥ =∥∥x(0) − x? −H0

(F(x(0))− F (x?)

)∥∥≤ ‖−H0‖ ·

∥∥F (x(0))− F (x?)−B0

(x(0) − x?

)∥∥≤ ‖H0‖

(∥∥F (x(0))− F (x?)− F ′ (x?)

(x(0) − x?

)∥∥+ ‖F ′ (x?)−B0‖ ·

∥∥x(0) − x?∥∥) ≤ β

1− 2βδ

(1

2κe2

0 + δe0

)≤ β

1− 2βδ

(1

2κε+ δ

)e0 .

Fie functia obiectiv

f(κ, ε, β, δ) =β

1− 2βδ

(1

2κε+ δ

)si restrictiile

βδ < 15κε < 2δ2f(κ, ε, β, δ) < 1

.

Atunci maxf(κ, ε, β, δ) se obtine pentru valorile

κ? = 0.3081295532316694 . . . , ε? = 0.3070664760350668 . . .

β? = 0.6293244688930841 . . . , δ? = 0.3731760461811351 . . . .

In concluzie avem

e1 ≤ f(κ?, ε?, β?, δ?)e0 <1

2e0.

Deoarece

d

dκf(κ, ε, β, δ) =

1

2· εβ

1− 2βδ> 0 ,

d

dεf(κ, ε, β, δ) =

1

2· κβ

1− 2βδ> 0 ,

d

dβf(κ, ε, β, δ) =

κε+ 2δ

2(1− 2βδ)2> 0 si

d

dδf(κ, ε, β, δ) =

β(κεβ + 1)

(1− 2βδ)2> 0 ,

atunci pentru orice valori pozitive κ ≤ κ?, ε ≤ ε?, β ≤ β? si δ ≤ δ? avem caf(κ, ε, β, δ) < f(κ?, ε?, β?, δ?) < 1/2. De exemplu

f

(3

10,

3

10,3

5,

7

20

)=

237

580≈ 0.4086206896551724 . . . .

64


Sa mai observam ca∥∥x(1) − x(0)∥∥ ≥ ∥∥x(0) − x?

∥∥− ∥∥x(1) − x?∥∥ ≥ e0 −

1

2e0 =

1

2e0 .

Vom aplica lema 2.3.4 lunand x = x(0), y = x(1), B = B0 si B′ = B1 datde (2.17). Se poate vedea usor ca ıntra-devar B1 are forma din lema 2.3.4,ıntrucat F

(x(0))

= −B0

(x(1) − x(0)

)si

B1 = B0 +[F(x(1))− F

(x(0))−B0

(x(1) − x(0)

)] dTB0

dTB0 (x(1) − x(0)).

Deasemenea, tinand seama de observatia 2.3.2, avem q = 1. Asadar obtinem

‖B1 − F ′ (x?)‖ ≤ δ +κ

2 ‖x(1) − x(0)‖

(1

4e2

0 + e20

)≤ δ +

5

4κe0 ≤ δ +

5

4κε < δ +

δ

2=

(2− 1

2

)δ .

De aici rezulta ca B−11 = H1 exista si ‖H1‖ ≤ β/(1− 2βδ).

Presupunem ca x(1), . . . , x(k−1) si H1, . . . , Hk−1 sunt definiti si ca existarelatiile

ek ≤1

2ek−1, ‖Bk − F ′ (x?)‖ ≤

[2− 1

2k

]δ . (2.26)

Sa observam ın primul rand ca Hk = B−1k exista si ‖Hk‖ ≤ β/(1 − 2βδ).

Tinand seama ca e0 < ε si ca ε < 2δ/(5κ), atunci avem

ek ≤1

2ke0 ≤

2δ

5κ· 1

2k.

Utilizand aceasta relatie, obtinem ca si pentru e1 relatia

ek+1 =∥∥x(k+1) − x?

∥∥ =∥∥x(k) − x? −Hk

(F(x(k))− F (x?)

)∥∥≤ ‖−Hk‖ ·

∥∥F (x(k))− F (x?)−Bk

(x(k) − x?

)∥∥ ≤ ‖Hk‖×(∥∥F (x(k)

)− F (x?)− F ′ (x?)

(x(k) − x?

)∥∥+ ‖F ′ (x?)−Bk‖ ·∥∥x(k) − x?

∥∥)≤ β

1− 2βδ

(1

2κe2

k + δek

)≤ β

1− 2βδ

(1

2κε+ δ

)ek <

1

2ek .

Ultima inegalitate se obtine din problema de programare neliniara conside-rata. Astfel prin inductie matematica s-a demonstrat ca ek+1 < ek/2 pentruorice k ∈ N∗. Pentru a doua relatie din (2.26) aplicam lema 2.3.4 ın care

65


luam x = x(k), y = x(k+1), B = Bk si B′ = Bk+1 dat de (2.17). Vom tineseama ca q = 1, conform observatiei 2.3.2 si ca∥∥x(k+1) − x(k)

∥∥ > ek2.

Obtinem

‖Bk+1 − F ′ (x?)‖ ≤ ‖Bk − F ′ (x?)‖+κ

2 ‖x(k+1) − x(k)‖(e2k+1 + e2

k

)≤(

2− 1

2k

)δ +

κ

ek

(1

4e2k + e2

k

)=

(2− 1

2k

)δ +

5

4κek

≤(

2− 1

2k

)δ +

5

4· κe0

2k≤(

2− 1

2k

)δ +

δ

2k+1=

(2− 1

2k+1

)δ ,

adica a doua relatie din (2.26) este adevarata pentru orice k ∈ N∗. Prininductie rezulta ca x(k) si Hk sunt definiti pentru orice k ∈ N∗ si avemrelatia ek+1 < ek/2. Din relatia ek ≤ e0/2

k rezulta ca∥∥x(k) − x?

∥∥→ 0, cand

k →∞, adica x(k) → x? cand k →∞.

Teorema 2.3.5. Fie aplicatia neliniara F : D ⊂ Rn → Rn care satisfaceconditiile 1 si 2 de pe pagina 62 si fie

x(k)

sirul generat de metoda Broyden,(2.25), atunci acest sir converge cel putin superliniar la x?.

Demonstratie. In cele ce urmeaza vom folosi notatiile din formulele (2.25).Aplicam toerema 2.3.1, daca F ındeplineste conditiile 1(a) si 1(b), de lapagina 62, rezulta ca exista o multime deschisa S ⊂ Rn astfel ıncatx? ∈ S iar iteratiile metodei Newton x := x− F ′ (x)−1 F (x) sunt definite six(k) → x? cand k → ∞, convergenta fiind cel putin superliniara. Calculam∥∥∥B − F ′ (x?)∥∥∥.

B − F ′ (x?) = B +(y −Bs)sT

‖s‖2 − F ′ (x?) + F ′ (x?)ssT

‖s‖2 − F′ (x?)

ssT

‖s‖2

= B +〈s, y −Bs〉‖s‖2 − F ′ (x?) + F ′ (x?)

ssT

‖s‖2 − F′ (x?)

ssT

‖s‖2

= B +〈s, y〉‖s‖2 −

〈s, Bs〉‖s‖2 − F

′ (x?) + F ′ (x?)ssT

‖s‖2 − F′ (x?)

ssT

‖s‖2

= B − F ′ (x?)− ssT

‖s‖2 (B − F ′ (x?)) +〈s, y〉 − 〈s, F (x?) s〉

‖s‖2

= (B − F ′ (x?))(I − ssT

‖s‖2

)+〈s, y − F ′ (x?) s〉

‖s‖2 .

66


Atunci rezulta∥∥∥B − F ′ (x?)∥∥∥ ≤ ‖B − F ′ (x?)‖ · ∥∥∥∥I − ssT

‖s‖2

∥∥∥∥+‖〈s, y − F ′ (x?) s〉‖

‖s‖2 . (2.27)

Fie u = sT si v = sT/ ‖s‖2 atunci avem vTu = 1. Din lema 2.3.3 rezulta ca∥∥∥∥I − ssT

‖s‖2

∥∥∥∥ ≤ 1 .

Pe de alta parte avem

‖〈s, y − F ′ (x?) s〉‖‖s‖2 =

∥∥(y − F ′ (x?) s) sT∥∥

‖s‖2

=

∥∥(F (x)− F (x)− F ′ (x?) s) sT∥∥

‖s‖2 ≤ κ

2· ‖x− x‖‖s‖

‖s‖ =κ

2‖s‖ = κσ .

In final avem inegalitatea

‖B − F ′ (x?)‖ ≤ ‖B − F ′ (x?)‖+ κσ . (2.28)

Din aceasta inegalitate rezulta convergenta siruluix(k)

generat de metodaBroyden, adica

limk→∞

x(k) = x?.

In continuare sa demonstram convergenta cel putin superliniara a siruluix(k)

generat de metoda Broyden, plecand de la identitatea pentru norma

Frobenius ‖A‖2F = Tr(ATA).

Prin calcul direct avem egalitatea∥∥∥∥E (I − ssT

‖s‖2

)∥∥∥∥2

F

= Tr

((E − EssT

‖s‖2

)T(E − EssT

‖s‖2

))

= Tr(ETE)− Tr(ETEssT

‖s‖2

)− Tr

(ssTETE

‖s‖2

)+ Tr

((EssT

)TEssT

‖s‖4

)

= ‖E‖2F − 2

‖Es‖2

‖s‖2 +‖Es‖2

‖s‖2 = ‖E‖2F −

(‖Es‖‖s‖

)2

,

pentru orice E ∈ L(Rn,Rn). Pentru orice α > 0 si β ≥ 0, numere reale, aveminegaliatea

√α2 − β2 ≤ α − (2α)−1β2 adevarata. Intradevar β4/4α2 ≥ 0

atunci avem

α2 − β2 +β4

4α2≥ α2 − β2 ⇔ α2 − 2α

β2

2α+

(β2

2α

)2

≥ α2 − β2 ⇔

67


⇔(α− β2

2α

)2

≥ α2 − β2 ⇔ α− β2

2α≥√α2 − β2 .

Fie acum α = ‖E‖F si β = ‖Es‖ / ‖s‖ si ınlocuim ın relatia mai sus demon-strata. Atunci rezulta∥∥∥∥E (I − ssT

‖s‖2

)∥∥∥∥F

=

√‖E‖2

F −‖Es‖2

‖s‖2 ≤ ‖E‖F −‖Es‖2

2 ‖E‖F ‖s‖2 .

Fie acum ın locul matricii E care este o matrice oarecare din L(Rn,Rn), vomconsidera matricea B − F ′ (x?)). Atunci rezulta inegalitatea∥∥∥∥(B − F ′ (x?))

(I − ssT

‖s‖2

)∥∥∥∥F

≤ ‖B − F ′ (x?)‖F −‖(B − F ′ (x?)) s‖2

2 ‖B − F ′ (x?)‖F ‖s‖2 . (2.29)

Atunci din relatia (2.27) si (2.29) avem

∥∥∥B − F ′ (x?)∥∥∥ ≤ ‖B − F ′ (x?)‖ · ∥∥∥∥I − ssT

‖s‖2

∥∥∥∥+‖〈s, y − F ′ (x?) s〉‖

‖s‖2

≤ ‖B − F ′ (x?)‖F −‖(B − F ′ (x?)) s‖2

2 ‖B − F ′ (x?)‖F ‖s‖2 + κ

‖s‖2

.

Notam cu

ηk = ‖Bk − F ′ (x?)‖F , ψk =‖(Bk − F ′ (x?)) sk‖

‖sk‖, σk =

‖sk‖2

.

atunci ın noile notatii relatia de mai sus devine

ηk+1 ≤ ηk −ψ2k

2ηk≤ ηk + κσk . (2.30)

Relatia (2.28) transcrisa ın notatiile mai sus precizate este

ηk+1 ≤ ηk + κσk .

Avand ın vedere ca sirul ηk converge, rezulta ca sirul ηk este marginitde o constanta reala pozitiva, notata η. Atunci din relatia (2.30) avem

ψ2k

2η≤ ψ2

k

2ηk≤ ηk − ηk+1 + κσk .

68


Insumam dupa k ın aceasta relatie rezulta

1

2η

∞∑k=0

ψ2k ≤ η0 + κ

∞∑k=0

σk <∞

deoarece seria∑σk converge, dar o serie converge daca termenul general al

ei converge la 0. Atunci rezulta

limk→∞

ψk = 0 ,

adica

limk→∞

∥∥Bk − F ′ (x?)(x(k+1) − x(k)

)∥∥‖x(k+1) − x(k)‖

= 0 ,

relatie ce reprezinta conditia din ipoteza teoremei 2.3.3, care spune ca sirulx(k)

are o convergenta cel putin superliniara.

Convergenta super liniara a metodei Broyden este dovedita si ın lucrarealui Stachurski [33]. Remarcam articolul lui X. Chen [7] ın care se puneproblema convergentei metodelor de tip Broyden ın conditia ın care functiaF din ecuatia neliniara F (x) = 0 este nediferentiabila.

2.3.4 Programe pentru metoda Broyden

Programul Mathcad pentru metoda Broyden este prezentat ın aceastasectiune. Pentru exemplificare consideram sistemul neliniar

x1 + x2 = 2 ,x1 − ln(x2) + x3 = 2 ,x2

2 − 2x3 = −1(2.31)

Atunci ın Mathcad, [10], facem urmatoarele definiri

ORIGIN := 1 F (x) :=

x1 + x2 − 2x1 − ln(x2) + x3 − 2

x22 − 2x3 + 1

.

Programul 2.3.1. Parametri de intrare ın programul pentru metoda Broy-densunt: vectorul initial x, matricea initiala H si ε precizia impusaaproximatiei obtinuta prin program.

Broyden(x,H, ε) := δ ← |F (x)|while δ ≥ ε

s← − (H · F (x))

69


y ← F (x+ s)− F (x)break if s · (H · y) = 0

H ← H +(s−H · y) · sT

s · (H · y)·H

x← x+ sδ ← |F (x)|

return x

Exemplul 2.3.1. Apelul programului Broyden pentru iteratia initiala

x :=

0.20.3−0.1

si matricea initiala

H :=

0.2 0.6 0.40.6 −0.8 −0.40.5 −0.6 −0.6

este

Broyden(x,H, 10−2

)=

1.00283741103158790.99693994946033900.9960873111016953

,

Broyden(x,H, 10−16

)=

1.00000000000000020.99999999999999980.9999999999999997

.

O alegere aleatoare a iteratiei de start sau a maticii de start poate sa aibeurmatoarele consecinte:

• Metoda sa nu convearga1

Broyden

1000.3−0.1

, H, 10−16

=

• Metoda sa convearga catre o alta solutie a sistemului neliniar

Broyden

131415

, H, 10−16

=

−0.28588870250989422.2858887025098943.1126435801311834

1In Mathcad orice eroare este semnalata prin afisare ın rosu a comenzii. In acest caz

avem o depasire flotanta superioara.

70


F

−0.28588870250989422.2858887025098943.1126435801311834

=

00

0.00000000000000089

.

71

Capitolul 3

Bazine de atractie

Odata cu dezvoltarea softurilor matematice (Mathematica, Matlab, Math-cad), a graficii pe calculator, s-au realizat graficele ce reprezinta bazinele deatractie ale diferitelor metode numerice [8], [9], [12], [11]. Prezentam ın figura3.1 bazinele de atractie, din fereastra [−9, 12] × [−10, 10], pentru metodaNewton, referitor la sistemul neliniar (3.1), care are solutia (1, 1)T. Pentru orecunoastere usoara, toate bazinele de atractie, din aceasta sectiune, pentrumetoda Newton s-au realizat cu schema de colorare Royal.

x21 − x2 = 0x1 · (x2 + 1) = 2

, (3.1)

Bazinele de atractie au devenit un subiect intens studiat de specialisti,[2], [18], [32]. S-au facut programe ın Mathcad care permit realizarea aces-tor bazine de atractie. Acest document Mathcad poate fi luat ca modelpentru toate cele 2 exemple si cele 3 metode numerice (Newton, Broyden,Steffensen), carora li s-a realizat bazinele de atractie ın jurul solutiilor.

Figura 3.2 reprezinta bazinele de atractie, din dreptunghiul [−3, 18] ×[−3, 27], pentru metoda Broyden, referitor la sistemul neliniar (3.1), care aresolutia (1, 1). Pentru o recunoastere usoara, toate bazinele de atractie, dinaceasta sectiune, pentru metoda Broyden s-au afisat cu schema de colorareNeon.

In figura 3.3 avem bazinele de atractie, din dreptunghiul [−4, 6]×[−4, 6],pentru metoda Steffensen, referitor la sistemul neliniar (3.1), care are solutia(1, 1). Pentru o recunoastere usoara, toatele bazinele de atractie, din aceastasectiune, pentru metoda Steffensen s-au afisat cu schema de colorare Gamma.

Sistemul x3

1 + sin(3 · x1)− x2 = 04 · x2

1 + x22 − 4 · exp(−x1) = 0

, (3.2)

72


Figura 3.1: Bazinul de atractie pentru metoda Newton.

Figura 3.2: Bazinul de atractie pentru metoda Broyden

73


Figura 3.3: Bazinul de atractie pentru metoda Steffensen

are doua solutiile

x?1 ≈(

0.5194835221505531.140113124204160

)si

x?2 ≈(−1.59912492450220−3.09289408932662

).

Fereastra din planul x1Ox2, pe care s-au vizualizat bazinele de atractiepentru metoda Newton relativ la sistemul (3.2), este [−15, 15] × [−10, 10].Numarul de noduri considerate pe axa Ox1 este 1500, iar de pe axa Ox2 este1000. Bazinele de atractie se pot vizualiza, ın varianta electronica a lucrarii,printr-un clic pe N02.pdf.

Fereastra din planul x1Ox2, pe care s-au vizualizat bazinele de atractiepentru metoda Broyden relativ la sistemul (3.2), este [−15, 15] × [−10, 10].Numarul de noduri considerate pe axa Ox1 este 1500, iar de pe axa Ox2 este1000. Bazinele de atractie se pot vizualiza, ın varianta electronica a lucrarii,printr-un clic pe By02.pdf.

Fereastra din planul x1Ox2, pe care s-au vizualizat bazinele de atractiepentru metoda Steffensen relativ la sistemul (3.2), este [−5, 5] × [−5, 10].Numarul de noduri considerate pe axa Ox1 este 1000, iar de pe axa Ox2

este tot 1000. Bazinele de atractie se pot vizualiza, ın varianta electronica alucrarii, printr-un clic pe St02.pdf.

74

Concluzii

Lucrarea de fata este un exemplu de lucrare de licenta. Pentru a rezultaautomat referatul lucrarii trebuie complectat obligatoriu: titlul lucrarii,autorul, coordonatorul si specialitatea ın preambulul fisierului radacina

,,LucrareLicenta.tex”. De remarcat ca odata completate informatii va rezulta

ın mod automat pagina de titlu si referatul lucrarii. In principiu autorul tre-buie sa redacteze capitolele: Introducere, Capitolul1, Capitolul2, Capitolul3si Concluzii. Va rezuta ın mod automat: Cuprinsul, Glosarul si Bibligrafia.

75

Glosar

Argyros I. K., 5

Broyden C. G., 5, 54, 59, 62

Chen X., 69Cira O., 5Cuyt A. A. M., 5

Dennis J. E., 5, 54, 62

Ezquerro J. A., 35

Gay D. M., 54

Hernandez M. A., 35

Janko B., 49

Kantorovich L. V., 35Korganoff A., 49

Maruster St., 5More J. J., 54, 62

Neumann J. von, 16, 36

Ortega J. M., 5, 54

Rall L. B., 5Rheinboldt W. C., 5, 54Rubio M. J., 35

Schnabel R. B., 5Stachurski A., 69Szidarovszky F., 5

Traub J. F., 5

Wegge L., 49

Wozniakowski H., 5

Ypma T. J., 5

76

Index de notiuni

Mm,n(K) Mn,n este multimea matricelor de dimensiune m× n cu elementedin corpul K – ıncepand de la pagina 7;

PA(x) este polinomul caracteristic al matricei A – ıncepand de la pagina 7;

det(A) este determinatul matricii A – ıncepand de la pagina 7;

grad(P ) este gradul polinomului P – ıncepand de la pagina 8;

In este multimea indicilor 1, 2, . . . , n – ıncepand de la pagina 8;

Ker(f) este nucleul lui f – ıncepand de la pagina 9;

dimK(V ) este dimensiunea spatiului vectorial V peste corpul K – ıncepandde la pagina 9;

N multimea numerelor naturale N = 1, 2, . . . ıncepand de la pagina 17;

N∗ = 0 ∪N ıncepand de la pagina 40;

77

Bibliografie

[1] I. K. Argyros and F. Szidarovszky. The Theory and Applicationsof Iteration Methods. CRC Press, Boca Raton, FL, 1993. amazon.

[2] K. Baranski. Connectedness of the basin of attraction for rationalmaps. Proc. Amer. Math. Soc., 126(6):1857–1866, June 1998. ams,links.jstor.

[3] V. Brınzanescu and O. Stanasila. Matematici speciale. Ed. All,Bucuresti, a II-a edition, 1998. raft.ro.

[4] C. G. Broyden. A class of methods for solving nonlinear simultaneousequations. Mathematics of Computation, 19:577–593, 1965. links.jstor.

[5] C. G. Broyden. The convergence of single-rank quasi-Newton methods.Mathematics of Computation, 24(110):365–382, April 1970. links.jstor.

[6] C. G. Broyden, J. E. Dennis, and J. J. More. On the local and su-perlinear convergence of quasi-Newton method. IMA Journal of AppliedMathematics, 12(3):223–245, 1973. imamat.

[7] X. Chen. On the convergence of Broyden-like methods for nonlinearequations with nondifferentiable terms. Annals of the Intitute of Statis-tical Mathematics, 42(2):387–401, June 1990. SpringerLink.

[8] O. Cira. Numerical experiments on attraction basin. Advanced Model-ing and Optimization (AMO), 2(3):122–134, 2001. www.ici.ro.

[9] O. Cira. Metode numerice pentru rezolvarea ecuatiilor algebrice. Ed.Academiei Romane, Bucuresti, 2005. (Propusa ın 2008 pentru premiulAcademiei).

[10] O. Cira. Lectii de Mathcad 2001 Professional. Ed. Albastra, Cluj-Napoca, second edition, 2006. Ed. Albastra.

78

http://www.amazon.com/Applications-Iteration-Methods-Systems-Engineering/dp/0849380146

http://www.ams.org/proc/1998-126-06/S0002-9939-98-04184-7/S0002-9939-98-04184-7.pdf

http://links.jstor.org/sici?sici

http://www.raft.ro/detaliu.asp?IDCarte=3207&IdDomeniu=1009

http://dx.doi.org/10.2307/2003941

http://dx.doi.org/10.2307/2004483

http://dx.doi.org/10.1093/imamat/12.3.223

http://dx.doi.org/10.1007/BF00050844

http://www.ici.ro/camo/JOURNAL/vol2/v2c2.htm

http://www.gmi.ro/librarie/catalog/


[11] O. Cira. Aplicatii, probleme si exercitii rezolvate cu Mathcad-ul. Ed.MatrixRom, Bucuresti, 2010. Ed. Matrixrom.

[12] O. Cira and St. Maruster. Metode numerice pentru ecuatii neliniare.Ed. Matrix Rom, Bucuresti, 2008. Ed. Matrixrom.

[13] A. A. M. Cuyt and L. B. Rall. Computational implementation of themultivariate Halley method for solving nonlinear systems of equations.ACM Trans. Math. Softw., 11(1):20–36, 1985. portal.acm.

[14] J. E. Dennis and J. J. More. A caracterisation of superlinear con-vergence and its application to quasi-Newton methods. Mathematics ofComputation, 28:549–560, 1974. links.jstor.

[15] J. E. Dennis Jr. and R. B. Schnabel. Numerical Methods for Un-constrained Optimization and Nonlinear Equations (Classics in AppliedMathematics). Soc. for Industrial and Applied Mathematics, 1996. por-tal.acm.

[16] J. A. Ezquerro and M. A. Hernandez. Generalized differentiabilityconditions for Newton´s method. IMA Journal of Numerical Analysis,22(2):187–205, 2002. imajna.

[17] D. M. Gay. Some convergece properties of Broyden method. SIAMJournal on Numerical Analysis, 16(4):623–630, August 1979. scita-tion.aip.

[18] E. M. Haruta. Newton´s method on the complex exponential function.Trans. Amer. Math. Soc., 351(6):2499–2513, 1999. Article electronicallypublished on February 15, 1999.

[19] M. A. Hernandez and M. J. Rubio. A modification of Newton´smethod for nondifferentiable equations. J. Comp. Appl. Math., 164-165:409–417, 2004. ScienceDirect.

[20] B. Janko. Rezolvarea ecuatiilor operationale neliniare ın sapatii Ba-nach. Ed. Academiei Romane, 1969.

[21] L. V. Kantorovich. Functional Analysis in Applied Mathematics (ınrusa). Uspekhi Mat. Nauk., 3:89–135, 1948.

[22] A. Korganoff. Methodes de Calcul Numerique. Algebre nonlineaire.Dunod, Paris, 1961. scitation.aip.

79

http://www.matrixrom.ro/

http://www.matrixrom.ro/

http://doi.acm.org/10.1145/3147.3162

http://dx.doi.org/10.2307/2005926

http://portal.acm.org/citation.cfm?id=1096889\&dl=acm&coll= \&CFID=15151515\&CFTOKEN=6184618

http://portal.acm.org/citation.cfm?id=1096889\&dl=acm&coll= \&CFID=15151515\&CFTOKEN=6184618

http://dx.doi.org/10.1093/imanum/22.2.187

http://dx.doi.org/10.1137/0716047

http://dx.doi.org/10.1137/0716047

http://dx.doi.org/10.1016/S0377-0427(03)00650-2

http://dx.doi.org/10.1137/1003057


[23] St. Maruster. Metode numerice ın rezolvarea ecuatiilor neliniare. Ed.Tehnica, Bucuresti, 1981.

[24] C. Mihu. Sisteme de ecuatii liniare si forme patratice. Ed. Tehnica,Bucuresti, 1985. Coperta 1.

[25] J. von Neumann. On some algebraical properties of operator rings.Annals of Mathematics, 44(4):709–715, Oktober 1943. links.jstor.

[26] J. M. Ortega and W. C. Rheinboldt. Iterative Solution of Nonlin-ear Equations in Several Variables. Academic Press, New York, SanFrancisco and London, 1970.

[27] J. M. Ortega and W. C. Rheinboldt. Iterative Solution of NonlinearEquations in Several Variables. SIAM, Philadelphia, 2000. amazon.

[28] L. B. Rall. Quadratic equations in Banach spaces. Rend. Circ. Mat.Palermo, 10(2):314–332, 1961.

[29] L. B. Rall. Computational Solution of Nonlinear Operator Equations.Robert E. Krieger Publishing Company, Inc., New York, 1969. amazom.

[30] L. B. Rall. Solution of finite systems of equations by interval iteration.BIT Numer. Math., 22(2):233–251, June 1982. SpringerLink.

[31] W. C. Rheinboldt. Nonlinear Systems of Equations. ACM Press NewYork, January 1969. doi.acm.

[32] K. R. Roeder. Topology for the basins of attraction of Newton´smethod in two complex variables. Technical report, Faculty of the Grad-uate School of Cornell University, august 2005. math.cornell.

[33] A. Stachurski. Superlinear convergence of Broyden´s bounded θ-classof methods. Mathematical Programming, 20(1):196–212, December 1981.SpringerLink.

[34] J. F. Traub and H. Wozniakowski. Convergence and complexityof Newton iteration for operator equations. J. Assoc. Comp. Mach.,29:250–258, 1979. portal.acm.

[35] L. Wegge. On a discrete version of Newton-Raphston method. J.Numer. Anal., 3:134–142, 1966. scitation.aip.

[36] T. J. Ypma. Historical development of the Newton-Raphson method.SIAM Review, 37(4):531–551, December 1995. scitation.aip.

80

http://dx.doi.org/10.2307/1969106

http://www.amazon.com/Iterative-Nonlinear-Equations-Variables-Mathematics/dp/0898714613/sr =1-3/qid=1170848622/ref=sr_1_3/105-0757921-3134036?ie=UTF8\&s=books

http://www.amazon.com/Computational-Solution-Nonlinear-Operator-Equations/dp/0882756672/sr= 1-1/qid=1171357751/ref=sr/_1/_1/002-4849993-3700055?ie=UTF8/&s=books

http://dx.doi.org/10.1007/BF01944479

http://doi.acm.org/10.1145/1198450.1198453

http://www.math.cornell.edu/People/PhD/2005Aug/roeder.html

http://dx.doi.org/10.1007/BF01589345

http://dx.doi.org/10.1145/322123.322130

http://dx.doi.org/10.1137/0703009

http://dx.doi.org/10.1137/1037125


[37] Official website. Mathematica. http://www.wolfram.com/.

[38] Official website. Mathcad. http://www.ptc.com/.

[39] Official website. Matlab. http://www.mathworks.com/.

81

http://www.wolfram.com/

http://www.ptc.com/

http://www.mathworks.com/

Exemplu de lucrare de licent˘ a - uav.ro · Referat privind lucrarea de licent˘a cu...

Documents

Transcript of Exemplu de lucrare de licent˘ a - uav.ro · Referat privind lucrarea de licent˘a cu...