metode si algoritmi de aproximare in probleme de optim

Probleme de optimizare

și

algoritmi de aproximare

a soluțiilor

Curs anul I – Semestrul I

Master SDOMEF

Sisteme Dinamice, Optimizări şi

Modele Economice şi Financiare

2 Probleme de optimizare și algoritmi de aproximare a soluțiilor

CUPRINS Capitolul 1. Elemente de analiză în spații Banach ................................................................ 4

§1. Noțiuni de bază și notații ................................................................................................. 4

§2. Diferențiala Gâteaux și derivata Fréchet ....................................................................... 13

2.1. Definiții .................................................................................................................... 13

2.2. Formule Taylor ........................................................................................................ 18

§3. Elemente de analiză convexă ......................................................................................... 21

3.1. Mulțimi convexe și funcționale convexe ................................................................. 21

3.2. Funcții scalare convexe de o variabilă ..................................................................... 26

3.3. Diferențiale direcționale laterale și subdiferențială ................................................. 27

3.4. Funcționale convexe G-diferențiabile ...................................................................... 33

3.5. Exemple. Diferențiabilitatea normei ........................................................................ 35

3.6. Proprietăți de continuitate și monotonie a diferențialelor direcționale. Clase speciale

de funcționale convexe ................................................................................................... 38

§4. Elemente de teorie punctelor de minim ale funcționalelor ............................................ 44

4.1. Semicontinuitate tare și slabă ................................................................................... 44

4.2. Teoreme de existență și de unicitate a punctelor de minim ..................................... 48

4.3. Teoreme de caracterizare a punctelor de minim ...................................................... 52

4.4. Exemple ................................................................................................................... 58

Capitolul. 2.

Algoritmi de minimizare fără restricţii a funcţionalelor convexe în spaţii Banach ......... 63

§1. O teorie generală a metodelor de descreştere ................................................................ 63

1.1. Introducere. Teorema de convergenţă ...................................................................... 63

1.2. Alegerea direcţiilor de convergenţă ......................................................................... 73

1.3. Alegerea factorilor de convergenţă .......................................................................... 80

1.4. Metoda lui Goldstein generalizată ........................................................................... 84

1.5. Metoda lui Armijo generalizată ............................................................................... 88

§ 2. Metodele gradienţilor conjugaţi .................................................................................... 91

2.1. Metoda gradienţilor conjugaţi pentru funcţionale pătratice ..................................... 91

Capitolul 1

ELEMENTE DE ANALIZĂ ÎN SPAȚII BANACH 3

Capitolul 3

Discretizarea problemelor de minim fără restricţii şi rezolvarea problemelor discretizate

finit dimensionale ................................................................................................................. 100

§1. Teoria generală a discretizării şi aplicaţii .................................................................... 100

1.1. Discretizarea spaţiului ............................................................................................ 100

1.2. Discretizarea problemei de optim .......................................................................... 104

1.3. O altă teoremă de convergenţă pentru funcţionale convexe .................................. 108

1.4. Metoda lui Galerkin de discretizare ....................................................................... 111

1.5. O discretizare internă a spaţiului ( )pL .............................................................. 113

1.6. O discretizare externă a spaţiului 1

0 ( )pW ........................................................... 115

1.5. Discretizarea problemei calculului variaţional ...................................................... 119

§2. Discretizarea problemelor pătratice ............................................................................. 123

2.1. Teorema generală de convergenţă ......................................................................... 123

2.2. Discretizarea problemei lui Dirichlet pentru ecuaţii eliptice prin metoda diferenţelor

finite .............................................................................................................................. 128

2.3. Metoda elementului finit ........................................................................................ 132

§3. Metode numerice specifice problemelor finit dimensionale ....................................... 143

3.1. Metodele lui Newton discretizate .......................................................................... 143

3.2. Metodele secantei ................................................................................................... 147

3.3. Metodele gradienţilor conjugaţi şi metricii variabile ............................................. 151

3.4. Algoritmi care evită calculul derivatelor. Metoda variaţiilor locale şi metodele lui

Zangwill ........................................................................................................................ 157

3.5. Metode de minimizare a unei funcţii de o singură variabilă .................................. 167

Comentarii bibliografice ............................................................................................... 175

Bibliografie ................................................................................................................... 177


Capitolul 1

ELEMENTE DE ANALIZĂ ÎN SPAȚII BANACH

§1. NOȚIUNI DE BAZĂ ȘI NOTAȚII

Problemele de optimizare vor fi studiate în cadrul general al spațiilor

infinit dimensionale, deși, în ultimă instanță, problemele ce pot fi rezolvate cu

calculatorul sunt cele finit dimensionale. Scopul nostru este însă, nu numai acela

de a prezenta algoritmi direct implementabili pe un sistem de calcul rapid, dar și

de a analiza căile prin care se poate aduce o problemă de natură continuă,

definită în stații generale, la una discretă în spații finit dimensionale, care se

poate apoi rezolva numeric.

Pentru simplitate ne vom restrânge la cadrul spațiilor Banach și, în multe

situații, chiar la spații Hilbert. De altfel majoritatea spațiilor de funcții utilizate

în problemele concrete sunt astfel de spații.

Printr-un spațiu Banach real E (în cele ce urmează nu vom considera

spații Banach complexe și nu vom mai preciza aceasta) vom înțelege un spațiu

liniar peste câmpul numerelor reale , care este complet în tipologia generată

de o normă definită pe E. Un spațiu Hilbert este un spațiu Banach în care

norma este definită prin intermediul unui produs scalar (.,.) prin 1 2( , )x x x .

Aplicațiile univoce T între două spații E și F vor fi numite în general

operatori, notând cu ( )D T E domeniul de definiţie şi cu ( )R t F mulţimea

Capitolul 1


imaginilor. Convenţional, în cazul în care spaţiul de definiţie este n , vom

spune că avem o funcţie (de n variabile), iar când spaţiul imaginilor F este ,

vom numi funcţională aplicaţia corespunzătoare.

Un operator : ,T E F E şi F fiind spaţii topologice, este continuuu în

0 ( )x D T dacă oricărei vecinătăţi U a lui 0( )T x îi corespunde o vecinătate V a

lui 0x , astfel încât ( )T V U . Operatorul T este continuu dacă el este continuu

în orice punct din domeniul de definiţie.

Dacă E este un spaţiu Banach, spaţiul Banach *E al funcţionalelor liniare

continue pe E este numit spaţiu dual; el generează o altă topologie pentru E,

diferită de cea a normei, topologia slabă, pentru care o bază de vecinătăţi ale

originii este dată de mulţimea de forma 1 1, ( ) , , ( )n nx E f x a f x a ,

*

1 2 1, , , , , , 0n nf f f E a a . Convergenţa la x E a unui şir nx , în

topologia slabă, va fi notată prin nx x , însemnând că ( ) ( )nf x f x ,

*f E . Convergenţa în topologia normei (tare) va fi notată corespunzător prin

nx x . Pentru valoarea unei funcţionale f din spaţiul dual într-un punct x E ,

vom folosi atât notaţia ( )f x , cât şi *,E

x f sau, simplu, ,x f atunci când

confuzia nu este posibilă. Norma lui *E va fi notată cu *

. Toate noţiunile

legate de topologia slabă vor fi numite, corespunzător, slabe. În general, vom

omite de multe ori să adăugăm adjectivul „tare”, atunci când este vorba de

noţiunile legate de topologia normei. Astfel, vom vorbi despre închiderea slabă

şi despre închiderea unei mulţimi. Continuitatea slabă a unui operator este

continuitatea operatorului în raport cu cele două topologii slabe ale spaţiilor de

referinţă. Un şir (tare) convergent este şi slab convergent, datorită continuităţii

funcţionalelor din spaţiul dual. De aici decurge că o mulţime slab închisă este şi

închisă şi o funcțională slab continuă este şi continuă.


Dualul lui *E , notat cu **E se poate defini corespunzător; spaţiul E poate

fi considerat ca o submulţime a lui **E deoarece, pentru fiecare x fixat în E,

putem defini o funcţională liniară şi continuă pe *E prin *( ) , ,x f x f f E .

Dacă în acest sens **E E , algebric şi topologic, spaţiul E se numeşte reflexiv.

Cum spaţiul dual este spaţiu Banach, un spaţiu reflexiv este de asemenea un

spaţiu Banach, de aceea, în general, vom specifica spaţiu Banach reflexiv pentru

a sublinia aceasta. Următoarea proprietate a spaţiilor Banach reflexive va fi

foarte des folosită în expunere pentru a dovedi convergenţa slabă a şirurilor.

Propoziţia 1.1. Într-un spaţiu Banach reflexiv, orice mulţime mărginită şi

slab închisă conţine cel puţin un şir slab convergent (este secvenţial slab

compactă).

Într-un spaţiu Hilbert E funcţionalele liniare continue se pot prezenta cu

ajutorul produsului scalar *, , ( ) ( , )f E y E f x x y (teorema lui Riesz);

de aceea vom identifica prin convenţie, elementele lui *E cu cele ale lui E,

schimbând dualitatea .,. cu produsul saclar (.,.) . Aceasta implică şi faptul că

spaţiul Hilbert este reflexiv.

Un rol important îl joacă, mai ales prin multiplele lor consecinţe,

teoremele de prelungire a funcţionaleleor liniare.

Definiţia 1.1. O funcţională p defintă pe un spaţiu liniar V se numeşte

subliniară dacă satisface condiţiile:

( ) ( ), ( ) ( ) ( ), , 0, ,p v p v p u v p u p v u v V

(este pozitiv omogenă şi subaditivă).

Teorema lui Hahn-Banach. Fie V un spaţiu liniar real, :p V o

funcţională subliniară, M un spaţiu liniar al lui V şi :f M o funcţională

liniară pe M majorată de : ( ) ( ),p f v p v v M . Atunci există o funcţională

Capitolul 1


liniară F definită pe întreg spaţiul V care prelungeşte pe ( ( )f F v

( ), )f v v M şi este majorată de p pe V.

Iată câteva din consecinţele acestei teoreme, prezentate în limitele unui

spaţiu Banach, care vor fi folosite în expunere.

Consecința 1.1. Fie E un spațiu Banach, , 0w E w . Atunci există

funcționala *v E , care satisface:

*

1, ,v w v w .

Consecința 1.2. Fie E un spațiu Banach și , 0w v pentru orice *v E .

Atunci 0w .

Consecința 1.3. Fie E un spațiu Banach, 0M un subspațiu liniar închis.

Fie w E și 0w M . Atunci există *v E încât

0 0 0, 0, , , 0m v m M w v .

O serie de consecințe se referă la mulțimi convexe.

Definiția 1.2. Fiind date elementele 1 2, , , nx x x din spațiul liniar E, o

combinație convexă este orice element x E de forma

1

n

i i

i

x x

cu 1

1, 0n

i i

i

pentru 1,2, ,i n .

O mulțime C E este convexă dacă orice combinație convexă de elemente ale

ei (în număr finit) aparține de asemenea mulțimii. Prin inducție se poate verifica

de fapt, că e suficient să ne referim la apartenența combinațiilor convexe de

două elemente distincte pentru a defini convexitatea unei mulțimi. Mulțimea

combinațiilor convexe de două elemente se numește segment.

Definiția 1.3. Fie A o mulțime din spațiul liniar E. Un element u A se

spune că este intern (algebric interior) în A dacă , 0v E încât

u v A pentru orice , cu . În cazul spațiilor Banach are loc următorul


rezultat care precizează legătura dintre noțiunea de punct intern și cea de punct

interior (topologic).

Propoziția 1.2. Într-un spațiu Banach, orice punct intern dintr-o mulțime

convexă și închisă este și punct interior în această mulțime și reciproc.

Să revenim acum la consecințele teoremei lui Hahn-Banach.

Consecința 1.4. Fie E un spațiu Banach, N și M două mulțimi convexe

din E astfel încât M să aibă interiorul nevid, iar N să nu conțină nici un punct

intern al lui M. Atunci există funcționala liniară *f E și numărul real astfel

încât ( ) ( ), ,f v f w v N w M .

Consecința 1.5. Fie E un spațiu Banach, N o mulțime convexă închisă din

E și ,u E u N . Atunci există *, 0f E f și , încât ( ) ( )f u f u ,

n N .

Consecința 1.6. Fie E un spațiu Banach, N o mulțime convexă din E.

Atunci N este slab închisă dacă și numai dacă este închisă.

Un alt rezultat de bază al analizei funcționale este principiul mărginirii

uniforme, pe care îl vom cita în forma particulară care are loc un spații Banach.

Operatorul liniar :T E F , definit între spațiile liniare normate E și F, este

mărginit, dacă există o constantă pozitivă M, încât Tx M x , ( )x D T .

Pentru operatorii liniari mărginiți se paote defini norma prin 0

supx

TxT

x

(facem convenția de a nota imaginile printr-un operator liniar, fără paranteze).

Un operator liniar este continuu dacă și numai dacă el este mărginit. Un operator

liniar :T E F are invers mărginit 1 :T F E dacă și numai dacă există

constanta pozitivă m, încât Tx m x , ( )x D T ; în acest caz, 1 1T

m .

Dacă 1T a , atunci operatorul I T are invers mărginit și

Capitolul 1


1 1( )

(1 )I T

a

.

Principiul mărginirii uniforme. Fie { , }aT a A o familie de operatori

liniari mărginiți, care duc spațiul Banach Aspațiul Banach E în spațiul normat F.

Dacă mulțimea { , }aT x a A este mărginită pentru fiecare x E fixat, atunci

0lim 0ax

T x

, uniform relativ la a A .

O consecință importantă a acestui principiu este următoarea:

Teorema rezonanței. Dacă, în condițiile de mai sus,{ , }aT x a A este

mărginită pentru fiecare x fixat, atunci și mulțimea { , }aT a A este mărginită.

Spațiul operatorilor liniari mărginiți definiți pe un spațiu liniar normat E

cu valori într-un spațiu Banach F este un spațiu Banach relativ la norma de mai

sus. Acest spațiu va fi notat cu ( , )L E F ; deci * ( , )E L E R .

Dacă ( , )T L E F și *f F , putem defini *e E prin ( ) ( )e x f Tx ,

x E . Aplicația lui f în e este liniară și se notează cu *T , operatorul adjunct

lui T. Dacă E este un spațiu Hilbert, ( , )T L E E și *T T , atunci T se numește

autoadjunct; în acest caz ( , ) ( , )Tx y x Ty pentru orice ,x y E . Cu ajutorul

operatorului adjunct se poate arăta că un operator liniar tare continuu este slab

continuu.

Dacă E este un spațiu Banach, spectrul unui operator ( , )T L E E este

prin definiție mulțimea de numere: ( ) { ,T R T I T neinversabil, sau

( )R T E sau 1T

nemărginit}, unde I este operatorul identic și supralinierea

înseamnă închiderea în topologia spațiului respectiv. Dacă E este un spațiu

Hilbert și T este autoadjunct, atunci numerele din ( )T sunt cuprinse în

intervalul [ , ]m M , unde


2 2

0 0

( , ) ( , )inf , supx x

x Tx x Txm M

x x

.

Atunci putem scrie

2 2

m x M x ,

de unde max ,T m M . Dacă 0,m T se numește pozitiv definit, iar dacă

0m , pozitiv sedidefint. Dacă T este pozitiv definit admite invers mărginit și,

cu notația de mai sus, 1 1T

m .

Într-un spațiu Hilbert E, o mulțime S E este numită sistem ortgonal

dacă, oricare ar fi ,x y S distincte, ele sunt ortogonale, adică ( , ) 0x y . Când

toate elementele unui sistem ortogonal sunt de normă egală cu unitatea, sistemul

se numește ortonormal. Un sistem ortonormal este complet în E dacă spațiul

generat de ,S sp S este dens în E, adică închiderea lui coincide cu întreg spațiul

(vom nota în genere cu sp S spațiul liniar generat de mulțimea S și cu sp S

închiderea acestuia). Dat un sistem ortonormal S complet în E, fiecărui element

x E îi putem atașa seria Fourier

( , )j S

x f f

,

în care numai un număr cel mult numărabil de termeni sunt nenuli. În condițiile

acestea, seria Fourier este convergentă la x în topologia lui E. Să încheiem

această scurtă trecere în revistă cu enumerarea unor spații Banach uzuale.

1. Spațiul euclidian real n . În acest spațiu, toate normele sunt

echivalente. Cele mai obișnuite norme sunt:

1

11

, maxn p n

p

i ip ii

x x x x

,

Capitolul 1


unde cu ix am notat componentele lui x. Convergența slabă este echivalentă cu

cea tare. În raport cu norma 2 , spațiul n este un spațiu Hilbert.

2. Spațiul funcțiilor continue pe un interval [ , ]C a b . Norma lui este

[ , ]max ( )t a b

x x t , iar convergența în normă este convergența uniformă. [ , ]C a b

este reflexiv. Funcționalele din spațiul dual se reprezintă prin

*, ( ) ( )d ( )

b

a

x x cx a x t t ,

unde c și ( )t este funcție cu variație mărginită. Analog, se definește

spațiul ( )C T , cu mT o mulțime compactă.

3. Spațiul funcțiilor de m ori continuu derivabile [ , ]mC a b pe un interval

închis, cu norma

( )

0max ,

mi

ix x

unde normele din definiție sunt normele derivatelor ( ) ( )ix t în [ , ]C a b .

Convergența în această normă înseamnă convergența uniformă a funcțiilor și a

derivatelor până la ordinul m. Funcționalele din spațiul dual sunt definite analog.

De exemplu, cele din 1[ , ]C a b sunt de forma

*

0 1, ( ) ( ) ( )d ( )

b

a

x x c x a c x a x t t ,

unde ( )t este o funcție de variație mărginită continuă la dreapta și 0 1,c c .

4. Spațiul [ , ]pL a b al funcțiilor reale de putere p Lebesgue-integrabilă, cu

norma

1

( ) db pp

p ax x t t ,


unde 1 p . Prin convenție se notează cu [ , ]L a b spațiul funcțiilor

măsurabile, esențial mărginite, cu norma

[ , ]

ess sup ( )t a b

x x t

.

Funcționalele liniare și mărginite peste [ , ] (1 )pL a b p sunt de forma

*, ( ) ( )db

ax x x t y t t ,

unde [ , ]qy L a b , cu 1 1

1p q

. Aceste spații sunt reflexive, iar pentru

2p chiar spații Hilbert.

5. Spațiile Sobolev [ , ]m

pW a b ale funcțiilor reale definite pe [ , ]a b absolut

continue împreună cu derivatele de ordin cel mult 1m și cu derivata de ordin

m în [ , ], 1pL a b p . Normele în aceste spații se pot da în multe forme

echivalente. De exemplu,

( )

0

mi

pi

x x

,

unde ( ) ( )ix t sunt derivatele. Funcționalele din spațiul dual sunt date de

* ( ) ( )

1

0

, ( ) ( ) ( )dm b

i m

ai

x x c x a x t y t t

,

unde ic și [ , ]qy L a b cu 1 1

1p q

.

Pentru 22, m mp W H este un spațiu Hilbert. Spațiile lui Sobolev, ca de

altfel și celelalte care au fost definite, se pot generaliza și la funcții de mai multe

variabile. Pentru spațiile Sobolev însă trecerea aceasta nu este de loc banală,

derivabilitatea funcțiilor absolut continue trebuind să fie înlocuită cu

derivabilitatea generalizată în sensul teoriei distribuțiilor. Topologia spațiilor

Capitolul 1


Sobolev este puternică. De exemplu, convergența slabă în 1[ , ]H a b implică

convergența uniformă.

§2. DIFERENȚIALA GÂTEAUX ȘI DERIVATA FRÉCHET

2.1. DEFINIȚII

Fie E un spațiu Banach real și :f E o funcție de variabilă reală cu

valori în spațiul E. Vom introduce noțiunile de derivată și integrală Riemann,

fără a intra în detalii.

Definiția 2.1. Vom spune că funcția f este derivabilă în ( )t D f

dacă există limita

0

[ ( ) ( )]( ) lim

f t f tf t

,

în sensul normei din : ( )E f t E este derivata în t a funcției.

Se pot ușor verifica liniaritatea operatorului de derivare și alte reguli de

calcul cu derivate. Funcția :f E definită în punctele în care f este

derivabilă poartă numele de funcție derivată. În cazul special, când E , se

obține derivata clasică a unei funcții scalare de variabilă reală, d

d

f

t. Dacă funcția


:f E este derivabilă într-un interval 0 1( , )t t , atunci, pentru orice

*e E , funcția scalară ( ) ( ),t f t e este derivabilă în acest interval și avem

*d( ), ( ), ,

df t e f t e e E

t .

Definiția 2.2. Fie f o funcție definită pe intervalul închis [ , ]a b , cu

valori în spațiul Banach E. Pentru fiecare divizare a intervalului [ , ]a b prin

puncte de diviziune 0 1 2 nt a t t t b , și orice numere 1[ , ]k k kt t , se

atașeayă suma Riemann:

1

0

( )( )n

k k k

k

f t t E

.

Dacă există limita sumelor Riemann când 1max( ) 0k kt t , în sensul

topologiei normei lui E, pentru orice șir de diviziuni { }kt și orice șir de numere

{ }k , atunci aceasta este independentă de alegerea șirului de diviziuni și se

numește integrala Riemann ( )db

af t t E . În acest caz se spune că funcția f este

integrabilă pe intervalul [ , ]a b . Pentru E se obține integrala Riemann a unei

funcții de variabilă reală. Dacă : [ , ]f a b E este integrabilă, atunci și

( ) ( ),t f t e , pentru *e E oarecare, este integrabilă, și

( ), d ( ) d ,b b

a af t e t f t t e .

Proprietățile integralei Riemann decurg din următoarea lemă simplă:

Lema 2.1. Dacă funcția : [ , ]f a b E este derivabilă în intervalul de

definiție și funcția derivată f este integrabilă pe [ , ]a b , atunci are loc

egalitatea

(2.1) ( )d ( ) ( )b

af t t f b f a .

Capitolul 1


Într-adevăr, dacă se consideră funcția scalară : [ , ]a b cu ( ) ( ),t f t e

pentru e E , atunci după formula lui Newton-Leibniz clasică, rezultă

d

( )d ( ), d ( ) ( ),d

b b

a at t f t e t f b f a e

t .

Din definiția de mai sus a integralei obținem

( ), d ( )d ,b b

a af t e t f t t e

și atunci din cauza arbitrarietății lui *c E rezultă (1).

Din această lemă decurg proprietățile obișnuite ale integralei. În

particular, vom utiliza mai târziu formula integrării prin părți sub următoarea

formă. Fie : [ , ]f a b E și : [ , ]g a b . Atunci în condițiile existenței

derivatelor și integralelor implicate are loc formula

(2.2) d

( ) ( )d ( ) ( )d ( ) ( ) ( ) ( )d

b b

a ag t f t t g t f t t g b f b g a f a

t .

Suntem acum în măsură să definim diferențiala Gâteaux.

Definiția 2.3. Fie E și F două spații Banach și :T E F . Fie ( )u D T și

E astfel încât există 0 0t ca ( )u t D T pentru 0t t . Să presupunem

că funcția de variabilă reală definită prin corespondența ( )t T u t admite

derivată în 0t . Atunci această derivată se numește diferențiala Gâteaux a lui T

în punctul u pe direcția . Conform acestei definiții diferențiala Gâteaux (G-

diferențiala) ( , )T u F este dată de

(2.3) 0

( ) ( )( , ) lim

t

T u t T uT u

t

.

Dacă ( , )T u există pentru orice E , atunci se spune că aplicația T este G-

diferențiabilă în u; în cazul în care aplicația ( , ),T u E este liniară și

continuă ea se nemește derivata Gâteaux (G-derivată) a operatorului T în

punctul u și se notează cu ( ) ( , )T u L E F . Avem atunci ( , ) ( )T u T u . În


general însă G-diferențiala este o aplicație din E E în F numai omogenă în

raport cu direcția , adică

(2.4) ( , ) ( , ),T u T u .

Aceasta rezultă ușor dim definiția de mai sus.

În cazul particular al unei funcționale :J E , G-derivata ( )J u este

un element din spațiul dual *E numit gradientul funcționalei J în u, notându-se

cu *grad ( )J u E . Deci

( , ) ,grad ( ) ( )J u J u J u .

În cazul special când E este un spațiu Hilbert se poate identifica

*( )J u E cu elementul corespunzător prin izomorfismul dintre E și *E

(teorema lui Riesz) și deci

( , ) ,grad ( ) ,J u J u E ,

unde grad ( )J u E .

Diferențiala de ordin superior se definește analog.

Definiția 2.4. Să presupunem că pentru ( ), ,u D T E , astfel ca

( )u t D T pentru 0t t , există ( , )T u t pentru toți t. Dacă funcția

definită prin corespondența ( , )t T u t admite derivată în 0t , acest

element din F se numește diferențiala a doua Gâteaux (G-diferențiala a doua) în

punctul u pe direcțiile și , ( , , )T u F . Avem

(2.5) 0

( , ) ( , )( , , ) lim

t

T u t T uT u

t

.

Dacă ( , , )T u există pentru orice , E , vom spune că operatorul T este de

două ori G-diferențiabil. Aplicația [ , ] ( , , )E E T u este în general

omogenă în și :

(2.6) ( , , ) ( , , ), ,T u T u .

Capitolul 1


Dacă această aplicație este biliniară și continuă în sensul topologiilor lui E E

și F, atunci ea este prin definiție derivata a doua Gâteaux a operatorului T în

punctul u, ( )T u și

( , ) ( )[ , ], [ , ]T u T u E E .

În cazul unei funcționale :J E , dacă ( , , )J u este biliniară și

continuă în raport cu [ , ] , derivata Gâteaux ( )J u se poate defini astfel:

Pentru fiecare E aplicația , ,J u este un element din spațiul dual

*E . Corespondența între și când variază este liniară și continuă, deci

un operator *( ) ( , )H u L E E . Acest operator este numit hessianul funcționalei J

în punctul u și

( , , ) , ( ) ( )[ , ]J u H u J u .

Când E este spațiu Hilbert, făcând identificarea între E și *E , vom scrie analog

( , , ) ( , ( ) )J u H u ,

unde ( ) ( , )H u L E E .

Să introducem acum un alt tip de derivată pentru operatorii definiți în

spații Banach.

Definiția 2.5. Fie :T E F un operator și E, F spații Banach. Dacă

pentru ( )u D T există un operator liniar și mărginit ( ) ( , )T u L E F astfel ca

(2.7) 0

( ) ( ) ( )lim 0F

E

T u T u T u

,

atunci ( )T u se numește derivata Fréchet a operatorului T în punctul u. Relația

(2.7) se mai poate scrie echivalent sub formele:

(2.8) 0

( ) ( ) ( ) ( , ), lim ( , ) 0T u T u T u u u

,

sau încă

(2.9) ( ) ( ) ( ) ( , )T u T u T u o u ,


unde ( , )o u F și 0

( , )lim 0

o u

. Legătura dintre cele două tipuri de

derivate este stabilită de următoarea propoziție simplă:

Propoziția 2.1. Dacă pentru operatorul :T E F există derivata

Fréchet în punctul u E atunci există și derivata Gâteaux în acest punct și ele

coincid.

Demonstrație. Fie E fixat, 0 . Luând în (2.7) în particular t

cu 0t obținem că ( )T u este diferențiala Gâteaux în u pe direcția . Cum

este arbitrar și ( ) ( , )T u L E F rezultă propoziția.

Reciproca nu este în general valabilă ceea ce arată că derivata Fréchet este

o noțiune mai puternică în acest sens.

2.2. FORMULE TAYLOR

Pentru multe rezultate privind evaluarea erorilor și a rapidității de

convergență a proceselor iterative, apare necesitatea introducerii unor formule

de tipul celor a lui Lagrange și Taylor din analiza clasică.

Vom considera cazul funcționalelor. Fie E un spațiu Banach.

Propoziția 2.2. Fie :J E și ( ),u D J E astfel încât

( ), [0,1]u t D J t . Dacă J este G-diferențiabilă în u t și pe direcția

, [0,1]t , atunci există (0,1) încât

(2.10) ( ) ( ) ( , )J u J u J u .

Capitolul 1


Propoziția 2.3. Fie :J E , ( ),u D J E cu ( )u t D J pentru

orice [0,1]t . Dacă J este de două ori G-diferențiabilă în u t pe direcțiile

[ , ] E E , atunci există (0,1) încât

(2.11) 1

( ) ( ) ( , ) ( , , )2

J u J u J u J u .

Propoziția 2.4. Dacă operatorul :T E F este G-diferențiabilă în

( )u t D T , [0,1]t , pe direcția E , atunci oricare ar fi g F , există

(0,1) (dependent de g) încât să aibă loc egalitatea:

(2.12) ( ) ( ), ( , ),T u T u g T u g .

Propoziția 2.5. Dacă operatorul :T E F satisface condițiile

propoziției precedente și în plus există ( , , ), [0,1]T u t t , atunci

oricare ar fi g F , există (0,1) dependent de g, astfel încât să aibă loc

formula:

(2.13) 1

( ) ( ), ( , ), ( , , ),2

T u T u g T u g T u g .

Consecința 2.1. Dacă sunt satisfăcute condițiile propoziției 2.4. atunci

există , (0,1) încât în norma spațiului F să avem:

(2.14) ( ) ( ) ( , )T u T u T u ,

(2.14') ( ) ( ) ( , ) ( , ) ( , )T u T u T u T u T u .

Consecința 2.2. În ipotezele propoziției 2.5 există (0,1) încât să aibă

loc inegalitaea:


(2.15) 1

( ) ( ) ( , ) ( , )2

T u T u T u T u .

Consecința 2.3. Fie :T E F G-derivabil într-o vecinătate a punctului

( )u D T de forma { , [0,1], }v u t t E . Dacă derivata ( )T v este

continuă în u în sensul topologiei lui ( , )L E F atunci T este derivabil în sens

Fréchet și cele două coincid.

Propoziția 2.6. În ipotezele propoziției 2.4, dacă în plus funcția definită

prin

[0,1] ( )t T u t F

este integrabilă Riemann în [0,1], atunci are loc formula lui Lagrange cu rest

integral:

(2.16) 1

0( ) ( ) ( , )dT u T u T u t t .

Propoziția 2.7. În ipotezele propoziției 2.5, dacă în plus funcția

[0,1] (1 ) ( , , )t t T u t F

este integrabilă Riemann în [0,1], atunci

(2.17) 1

0( ) ( ) ( , ) (1 ) ( , , )dT u T u T u t T u t t .

Capitolul 1


§3. ELEMENTE DE ANALIZĂ CONVEXĂ

3.1. MULȚIMI CONVEXE ȘI FUNCȚIONALE CONVEXE

În cele ce urmează E este un spațiu Banach și este mulțimea numerelor

reale completată cu cu regulile de calcul obișnuite.

Definiția 3.1. O funcțională :J E se spune că este convexă pe

mulțimea convexă U E dacă pentru orice ,u v U și orice [0,1] avem

(3.1) ( (1 ) ) ( ) (1 ) ( )J u v J u J v ,

în cazul în care membrul drept are sens (dacă apare în membrul drept expresia

fără sens se poate lua, prin convenție, ( ) ( ) ( ) ).

În mod analog, J este concavă dacă are loc o inegalitate similară în care semnul

„” este înlocuit cu „”. Funcționala J este strict convexă, respectiv strict

concavă dacă inegalitățile respective sunt stricte pentru u v și (0,1) .

Proprietățile funcționalelor concave se pot obține din cele ale funcționalelor

convexe prin schimbarea semnului.

Prin inducție se arată că, dacă J este convexă, oricare ar fi un număr finit

de puncte 1 2, , , nu u u U și 1 2, , , n cu 1

1n

i

i

și 0i , avem

1 1

( )n n

i i i i

i i

J u J u

.

Includerea între valorile funcționalei a simbolurilor permite considerarea

numai a funcționaleor convexe definite pe întreg spațiul căci în afara domeniului

lor de definiție se poate lua valoarea ceea ce nu schimbă sensul definiției 3.1.


Funcționalele convexe care iau valoarea sunt foarte particulare. Dacă

într-un punct , ( )v E J v , pentru orice h E , avem ( )J v th

pentru toți 0t , cu excepția esențială a unei valori a lui t. De aceea aproape

peste tot nu vom considera decât funcționalele convexe care nu iau valoarea

și nu sunt identic egale cu . Aceste funcționale vor fi numite proprii. Este

ușor de arătat că o funcțională :J E are proprietatea că mulțimile de nivel

{ , ( ) },u E J u a a

sunt mulțimi convexe. Reciproca nu este adevărată.

Domeniul efectiv al funcționalei convexe :J E este mulțimea

convexă ( ) { , ( ) }D J u f u .

O caracterizare a funcționalelor convexe se obține cu ajutorul noțiunii

următoare:

Definiția 3.2. Se numește epigraf al unei funcționale convexe :J E

mulțimea epi [ , ] , ( )J u a E J u a .

Propoziția 3.1. O funcțională :J E este convexă dacă și numai dacă

epigraful său este o mulțime convexă.

Demonstrație. Dacă J este convexă și [ , ]u a , respectiv [ , ]v b sunt din

epigraful ei avem

( (1 ) ) ( ) (1 ) ( ) (1 ) , [0,1]J u v J u J v a b ,

adică [ (1 ) , (1 ) ] [ , ] (1 )[ , ] epiu v a b u a v b J .

Reciproc, presupunem că epi J este convexă. Proiecția ei pe E este ( )D J

și este de asemenea convexă. Fie , ( )u v D J . Notăm ( ), ( )a J u b J v . Deci

[ , ], [ , ] epiu a v b J . Prin ipoteză [ , ] (1 )[ , ] epiu a v b J , [0,1] .

Atunci ( (1 ) ) (1 ) ( ) (1 ) ( )J u v a b J u J v , adică J este

convexă în ( )D J . Pentru punctele din afara domeniului efectiv în care

Capitolul 1


funcționale ia valoarea se poate lua ( ) , ( )J u a J v b , oricare ar fi a și b

tinzând la și rezultă de asemenea (3.1). Prin prelungirea cu a

funcționalei convexitatea se păstrează astfel că și în acest caz rezultă propoziția.

Asupra operațiilor cu funcționale convexe putem demonstra imediat

următoarele:

Propoziția 3.2. Dacă :J E este convexă și 0 , atunci J este de

asemenea convexă. Dacă 1 :J E și 2 :J E sunt funcționale convexe

1 2J J este de asemenea convexă (fiind nedeterminată în punctele u pentru care

1 2( ) ( )J u J u pentru care putem lua prin convenție 1 2( )( )J J u ).

În fine, pentru orice familie { }i i IJ de funcționale convexe, sup ii I

J

este tot

convexă.

În ce privește continuitatea funcționalelor convexe în topologia normei

propoziția următoare este esențială.

Propoziţia 3.3. O funcţională convexă proprie :J R este continuă

pe intervalul domeniului său efectiv dacă şi numai dacă este mărginită superior

pe o vecinătate a unui punct din interiorul domeniului efectiv.

Demonstraţie. Fie 0 Int ( )x D J şi fie V o vecinătate a lui 0x pentru care

( ) ,J x M x V . Fără a restrânge generalitatea, putem lua 0 0x şi

0( ) 0J x , căci în caz contrar putem face o translaţie considerând funcționala

0 0( ) ( ) ( )J x J x x J x care este tot convexă. Deci putem presupune că pentru

x r avem ( )J x M . Fie 0 M oarecare. Atunci, pentru orice x cu

x rM

, avem

( ) 1 0 1 (0)M M

J x J x J x J MM M M M M

.


Apoi, deoarece

1 1 1 1(0) ( ) ( )

2 2 2 2J J x x J x J x ,

avem și

( ) ( )J x J x pentru x rM

.

Deci ( ) ( )J x rM

. Funcționala J este continuă așadar în 0. Prin translația

de mai sus rezultă continuitatea funcționalei în orice punct dintr-o vecinătate

inclusă în Int ( )D J , pe care funcționala este mărginită, în particular pentru orice

punct din V { , }x x r . Fie acum un punct oarecare Int ( )y D J din afara

vecinătății V. Deoarece y este punct interior lui ( )D J , va exista ( )z D J încât y

este pe segmentul determinat de 0 și z, adică (0,1) încât 0 (1 )y z

(1 )z . Oricare ar fi xV avem atunci ( ) ((1 ) )J y x J z x

(1 ) ( ) ( )J z J x (1 ) ( )J z M . Cum z e fixat și ( )J z , rezultă că

J este mărginită în vecinătatea y V a lui y. Conform primei părți a

demonstrației rezultă că J este continuă în y.

Consecința 3.1. Orice funcție convexă proprie definită pe spațiul n este

continuă pe interiorul domeniului său efectiv.

Demonstrație. Fie Int ( )u D J fixat și 0 ales astfel încât sfera cu

centrul în u și de rază să fie cuprinsă în ( )D J . Atunci vecinătatea definită

prin

1

, 0 , 1,2, ,n

i i i

i

U x u x e x i nn

,

unde { }ie este baza naturală în n , este cuprinsă în ( )D J . Orice element din U

se poate scrie sub forma

Capitolul 1


1 1

( ) 1n n

i ii

i i

x xx e u u

cu 1

0 1n

i

i

x

. Dacă funcția J este convexă avem

1 1 1

1( ) ( ) 1 ( ) ( ) ( )

n n n

i ii i

i i i

x xJ x J e u J u J e u J u M

n

pentru orice x U . Conform propoziției 3.3 rezultă atunci continuitatea funcției.

În ceea ce privește continuitatea funcționalei convexe pe un spațiu Banach

oarecare avem rezultatul:

Consecința 3.2. Fie J o funcțională convexă proprie definită pe spațiul

Banach E, fie 0 Int ( )x D J și 0( )J x . Dacă mulțimea de nivel { ( ),x D J

( ) }J x este închisă, atunci funcționala J este continuă în interiorul

domeniului efectiv.

Demonstrație. Să notăm cu 0{ , ( ) }U y E J x y . Cum mulțimea de

nivel este convexă e ușor de văzut că U este de asemenea o mulțime convexă. Ea

este închisă datorită ipotezei. Pentru z E , mulțimea 0{ , }x x z este

unidimensională și, conform consecinței 3.1, 0( )J x z este continuă de în

origine. Atunci există 0 încât pentru să avem

0 0 0( ) ( ) ( )J x z J x J x ,

de unde

0( )J x z

pentru , adică 0x este punct intern în U. Cum U este convexă și închisă,

conform propoziției 1.2, 0x este punct interior în U, adică există o vecinătate a

lui în U. Funcționala J este mărginită de în această vecinătate și deci este

continuă.


3.2. FUNCȚII SCALARE CONVEXE DE O VARIABILĂ

Proprietățile funțiilor convexe de o singură variabilă stau la baza

demonstrației multor proprietăți ale funcționalelor convexe.

Teorema 3.1. Fie :J E o funcție convexă și ( )x D f un punct

fixat oarecare. Atunci:

(i) funcția ( ( ) ( ))f x t f x

tt

este nedescrescătoare pentruorice t

pentru care ( )x t D f ;

(ii) funcția f admite derivată la stânga și la dreapta în x și

( ) ( )f x f x ;

(iii) oricare ar fi t pentru care ( )x t D f , avem

( ) ( ) ( )f x t f x f x t .

În cazul funcțiilor convexe ( )D f este un interval pe axa reală; derivatele

f și f se pot extinde și în afara acestui interval punându-le egale cu la

stânga intervalului și cu la dreapta. Cu această convenție are loc următorul

rezultat privind monotonia și continuitatea derivatelor (vom nota cu 0

limz x

, 0

limy x

limitele laterale pentru z x , respectiv y x ).

Teorema 3.2. Fie :J E o funcție convexă proprie. Atunci f și f

sunt nedescrescătoare pe , avem ( ) ( ) ( ) ( )f y f x f x f z pentru

y x z și pentru x fixat

(3.2) 0 0 0 0

lim ( ) lim ( ) ( ), lim ( ) lim ( ) ( )z x z x y x y x

f z f z f x f y f y f x

.

Capitolul 1


Consecința 3.3. Funcția :f D derivabilă în D este convexă

dacă și numai dacă derivata este nedescrescătoare.

Teorema 3.3. Fie f o funcție convexă proprie. Fie ( )C D J mulțimea

punctelor în care funcția f este derivabilă. Atunci ( ) \D f C conține cel mult o

mulțime numărabilă de puncte, iar derivata :f C este nedescrescătoare și

continuă pe C.

3.3. DIFERENȚIALE DIRECȚIONALE LATERALE ȘI

SUBDIFERENȚIALĂ

Existența diferențialei Gâteaux a unei funcționale este o condiție destul de

restrictivă pentru problemele de minimizare. Vom arăta însă că pentru

funcționalele convexe este asigurată existența măcar a unor diferențiale laterale

care generalizează derivatele f și f din secțiunea precedentă.

Definiția 3.3. Fie : ( )J D J E o funcțională definită în spațiul

Banach E și fie ( ), ,x D J h E astfel ca ( )x h D J pentru 0 .

Dacă există limita

0

( ) ( )( , ) lim

J x h J xJ x h

,

acest număr se numește diferențiala direcțională la dreapta în x pe direcția h.

Analog, se definește diferențiala direcțională la stânga

0

( ) ( )( , ) lim

J x h J xJ x h

.


Legătura dintre cele două diferențiale direcționale laterale este dată de egalitatea

(3.3) ( , ) ( , )J x h J x h ,

care se obține imediat din definiție. De asemenea este ușor de arătat că ele sunt

pozitiv omogene relativ la h:

(3.4) ( , ) ( , ), ( , ) ( , ), 0J x h J x h J x h J x h

și

( ,0) ( ,0) 0J x J x .

În plus, dacă ( , ) ( , )J x h J x h valoarea lor comună este diferențiala Gâreaux.

Teorema 3.4. Fie :J E o funcțională convexă proprie și fie x un

punct din interiorul domeniului efectiv ( ),D J h E oarecare. Atunci:

(i) funcția ( ( ) ( ))J x h J x

este nedescrescătoare;

(ii) există diferențiale laterale ( , )J x h , convexă în raport cu direcția

și ( , )J x h concavă în h; ( , ) ( , )J x h J x h

;

(iii) dacă J este continuă în x, există funcționala liniară * *x E astfel

ca pentru orice h E să avem

(3.5) ( ) ( ) ( , ) , ( , )J x h J x J x h h x J x h

.

Demonstrație. Să definim funcția scalară ( ) ( )f J x h care este

convexă în ipotezele noastre. Aplicând teorema 3.1 rezultă (i) și existența

diferențialelor laterale ( , ) (0) (0) ( , )J x h f f J x h . Pentru oarecare

obținem și relațiile

(3.6) ( ) ( , ), ( ) ( , )f J x h h f J x h h

ce vor fi deseori folosite. Ținând seama de (3.4) pentru a dovedi convexitatea lui

( , )J x h în raport cu h este suficient să arătăm sudaditivitatea acesteia. Fie

1 2,h h E oarecare; avem succesiv:

Capitolul 1


1 21 2

0

1 2

0

1 2

1 20

( ( )) ( )( , ) lim

2 2( )

2 2lim

1 1( 2 ) ( 2 ) ( )

2 2lim ( , ) ( , ).

J x h h J xJ x h h

x h x hJ J x

J x h J x h J xJ x h J x h

Deci ( , )J x h este convexă și datorită lui (3.3) ( , )J x h

este concavă în raport

cu h. Tot din teorema 3.1, (iii) implică inegalitatea

(3.5’) ( ) ( ) ( , ) ( , )J x h J x J x h J x h .

Pentru a dovedi (3.5) rămâne să mai arătăm existența funcționalei x din spațiul

dual apelând la teorema lui Hahn-Banach.

Fie 0h E fixat, 0 0h și să notăm cu 0E subspațiul generat de 0h ,

0 0{ , }E h h . Definim funcționala liniară 0x pe 0E prin

0 0 0 0( ) ( ) ( , )x h x h J x h .

Să arătăm că este mărginită. Din (3.5’) rezultă

( , ) ( , ) ( , ) ( ( ) ( ))J x h J x h J x h J x h J x ;

deci avem

( ( ) ( )) ( , ) ( ) ( )J x h J x J x h J x h J x ,

ceea ce dovedește continuitatea lui ( , )J x h în 0h , datorită ipotezei. ( , )J x h

este deci mărginită în orice sferă cu centrul în origine. Fie

1

sup ( , )h

J x h

.

Atunci pentru orice h E avem

( , )J x h h .

De asemenea, evident ( , )J x h h . Funcționala 0x satisface pentru 0

0 0 0( ) ( , )x h J x h


și

0 0 0 0 0 0( ) ( , ) ( , ) ( , ) ( , )x h J x h J x h J x h J x h

pentru 0 . Deci avem

0 0( ) ( , ),x h J x h h E ,

unde ( , )J x h este subliniară. După teorema lui Hahn-Banach rezultă existența

unei prelungiri liniare a acestei funcționale la întreg spațiul cu

( ) ( , ),x h J x h h E .

Trecând pe h în h obținem

( ) ( ) ( , ) ( , )x h x h J x h J x h ,

deci

( , ) ( ) ( , )J x h x h J x h .

x este mărginită deoarece ( , )J x h și ( , )J x h

este mărginită. Așadar, există

x E încât

, ( )h x x h

și teorema este complet demonstrată.

Funcționala x a cărei existență a fost demonstrată aici joacă un rol foarte

important în analiza convexă.

Definiția 3.4. Fie J o funcțională definită pe spațiul Banach E și fie

x E . Spunem că x E este subgradient al funcționalei în punctul x dacă

avem

(3.7) ( ) ( ) , ,J x h J x h x h E .

Mulțimea subgradienților în x formează subdiferențiala în acest punct a

funcționalei

(3.8) ( ) { , ( ) ( ) , , }J x x E J x h J x h x h E .

Capitolul 1


Se spune că J este subdiferențială în x și că x este în domeniul de definiție al lui

J dacă ( )J x .

Legătura dintre subdiferențială și diferențialele laterale este dată de

următoarea consecință:

Consecința 3.4. Fie :J E o funcțională convexă proprie finită și

continuă în x E . Atunci au loc:

(3.9) ( , ) sup , , ( ) ,J x h h x x J x h E

,

(3.10) ( , ) inf , , ( ) ,J x h h x x J x h E

și ( )J x este mărginită și ănchisă în E .

Demonstrație. Conform teoremei 3.4 există atât subdiferențială nevidă în x cât și

diferențiale laterale pe orice direcție h E . Deci

( ) ( ) ,J x h J x h x ,

de unde, împărțind la 0 și trecând la limită pentru 0 , obținem

( , ) , , , ( )J x h h x h E x J x

.

Așadar

sup , , ( ) ( , ),m h x x J x J x h h E

.

Însă pentru fiecare h E există o funcțională ( )x J x pentru care

, ( , )h x J x h

anume cea construită în cursul demonstrației precedente. Deci

(3.9) are loc și folosind relația (3.3) rezultă imediat și (3.10).

Funcționalele din ( )J x sunt așadar mărginite punctual și atunci după

teorema rezonanței (§1) mulțimea ( )J x este mărginită în norma din E. (3.7)

arată și faptul că ( )J x este închisă în această topologie.

Existența subdiferențialei nevide este specifică funcționalelor convexe

după cum rezultă din teorema următoare:


Teorema 3.5. Fie J o funcțională definită pe mulțimea convexă deschisă

U din spațiul Banach E. Atunci J este convexă și continuă în U dacă și numai

dacă este subdiferențială în orice punct din această mulțime.

Demonstrație. Necesitatea decurge din teorema 3.4. Să dovedim

suficiența. Fie ,x y U și [0,1] . Avem

( ) ( (1 ) ) (1 )( ),J x J x y x y z ,

( ) ( (1 ) ) ( ),J y J x y x y z

pentru orice ( (1 ) )z J x y . Înmulțind cele două inegalități cu ,

respectiv cu (1 ) și adunându-le, obținem

( ) (1 ) ( ) ( (1 ) ) 0J x J y J x y .

Deci J este convexă în U. Pentru a dovedi continuitatea vom folosi consecința

3.2. Prelungim cu funcționala pe întreg spațiul E; U este domeniul efectiv al

funcționalei prelungite. Fie 0x U și 0( )J x . Să arătăm că mulțimea de nivel

{ , ( ) }W x U J x

este închisă. Dacă nx W și nx x avem

( ) ( ) , , ( )n nJ x J x x x x x J x ,

de unde

( ) ( ) ,n nJ x J x x x x .

Cum însă ( )nJ x și , 0nx x x pentru n , rezultă ( )J x , adică

x W . Consecința 3.2 se poate deci aplica și atunci rezultă continuitatea.

Consecința 3.5. Dacă J este subdiferențială în U, atunci există

diferențialele direcționale laterale și au loc relațiile (3.9) și (3.10).

Demonstrația este imediată ca urmare a consecinței 3.4 și a teoremei

precedente.

Capitolul 1


3.4. FUNCȚIONALE CONVEXE G-DIFERENȚIABILE

Subdiferențialele unei funcționale convexe ca și diferențialele direcționale

laterale sunt generalizări ale diferențialei Gâteaux.

Teorema 3.6. Fie :J E o funcțională convexă diferențiabilă

Gâteaux în 0 ( )x D J . Atunci 0( )J x conține un singur element 0x , diferențiala

Gâteaux este liniară și continuă în raport cu direcția, și 0 0grad ( )x J x .

Reciproc, dacă J este convexă și continuă în 0x și 0( )J x conține un singur

element 0x , atunci J este derivabilă Gâteaux și 0 0grad ( )x J x .

Demonstrație. Dacă J este diferențiabilă Gâteaux în 0x avem

0 0 0( , ) ( , ) ( , ),J x h J x h J x h h E

și după (3.5)

0 0( , ) , ,J x h h x h E ,

adică 0x este unic și J este G-derivabilă cu 0 0grad ( )x J x . Reciproc, dacă

0( )J x conține un singur element 0x , conform consecinței 3.4 avem

0 0 0( , ) ( , ) , ,J x h J x h h x h E

,

adică J este G-derivabilă și 0 0grad ( )x J x .

Consecința 3.6. Funcționala J definită în spațiul Banach E, diferențiabilă

pe o mulțime convexă U din domeniul ei de definiție este convexă în U dacă și

numai dacă are loc inegalitatea:

(3.11) ( ) ( ) ( , ), ,J y J x J x y x x y U ;

funcționala este strict convexă dacă și numai dacă are loc

(3.11’) ( ) ( ) ( , ), , ,J y J x J x y x x y U x y .


Demonstrație. Prima parte a consecinței rezultă evident din teoremele 3.4,

3.5 și 3.6. Dacă în demonstrația teoremei 3.5 luăm inegalitățile stricte pentru

x y și (0,1) , obținem stricta convexitate. Reciproc, dacă J este strict

convexă avem pentru orice , ,x y U x y și (0,1) :

( ( )) ( ) ( ( ) ( ))J x y x J x J y J x

sau

( ( )) ( )

( ) ( )J x y x J x

J y J x

.

Dar dacă J este strict convexă ea este în particular convexă și atunci are loc

(3.11); deci

( ( )) ( ) ( , ( ))J x y x J x J x y x ,

care, în combinație cu inegalitatea de mai sus, ne dă (3.11’).

Aceasta este o caracterizare a funcționalelor convexe G-diferențiabile. O

altă caracterizare se va obține în secțiunea 3.6.

O condiție suficientă se obține în particular din consecința 3.6.

Consecința 3.7. Dacă funcționala :J E este de două ori G-

diferențiabilă pe o mulțime convexă U E și dacă

( , , ) 0, ,J x h h x U h E ,

atunci J este convexă în U; dacă ( , , ) 0J x h h pentru orice x U și 0h

este convexă în U; dacă ( , , ) 0J x h h pentru orice x U și 0h , atunci J

este strict convexă în U.

Demonstrație. După formula lui Taylor (2.11) avem

1( ) ( ) ( , ) ( ( ), , ) ( ) ( , )

2J y J x J x y x J x y x y x y x J x J x y x

pentru orice ,x y U . Deci J este convexă. Analog, dacă folosim ipoteza de

strictă nenegativitate pentru x y , obținem stricta convexitate.

Capitolul 1


Observație. Conform teoremei 3.3 pentru fiecare ( )x D J și h E

existența diferențialei Gâteaux ( , )J x h h a funcționalei convexe proprii

continue J este asigurată pentru fiecare real pentru care ( )x h D J cu

excepția unei mulțimi nenumărabile de valori ale lui .

3.5. EXEMPLE. DIFERENȚIABILITATEA NORMEI

În această secțiune vom considera câteva exemple de funcționale convexe

și vom cerceta subdiferențialele lor.

1. Dacă A este o mulțime convexă închisă din spațiul Banach E, funcția

indicatoare a acestei mulțimi este o funcție convexă A definită prin

(3.12) 0 dacă ,

( )dacă .

A

x Ax

x A

După definiția 3.4 subdiferențiala acestei funcții este

(3.13) ( ) { , , 0, },A x x E z x x z A x A .

Această mulțime este nevidă, conține cel puțin originea și este un con în E

(odată cu x , x aparține mulțimii pentru orice 0 ), numit conul normal la

A în x. Dacă A este un subspațiu liniar închis, conul normal la A în orice punct

este subspațiul ortogonal A (într-un spațiu Hilbert).

Funcția indicatoare permite transformarea unei funcții convexe definite pe

o mulțime convexă într-o funcție convexă definită pe întreg spațiul, prin simpla

adăugare a ei la funcția dată.


2. Fie E un spațiu Banach și fie :J E o funcțională subliniară (vezi

definiția 1.1). Aceasta este evident o funcțională convexă. Funcționalele din

(0)J se definesc atunci prin

(3.14) (0) { , , ( ), }J x E x x J x x E .

În orice alt punct, 0x , subdiferențiala este o submulțime a lui (0)J dată de

(3.15) ( ) { (0), , ( )}J x x J x x J x .

Într-adevăr, din definiția 3.4, orice punct x din ( )J x este determinat de

inegalitatea

( ) ( ) , ,J y J x y x x y E ,

care se mai scrie sub forma

(3.16) , ( ) max{ , ( )}y E

x x J x y x J y

.

Dacă am avea (0)x J atunci ar exista y E încât , ( ) 0y x J y și din

cauza omogenității, pentru orice 0t ,

, ( ) { , ( )}t y x J t y t y x J y ,

care tinde la pentru t , în contradicție cu (3.16). Așadar, (0)x J

și atunci conform lui (3.14) și (3.16) rezultă (3.15).

În particular, dacă [ , ]E C a b și [ , ]

( ) max ( )t a b

J x x t

, aceasta este o

funcțională subliniară și (0)J este definit prin funcțiile de variație mărginită

(vezi §1) pentru care

(3.17) [ , ]

max ( ) ( )d , [ , ]b

t a b ax t x t x C a b

.

Luând în particular 1x obținem d 1b

a . Apoi luând ( )x t în (3.17) avem

[ , ]

( )d max ( )b

t a bax t x t

.

Capitolul 1


Pentru orice x cu ( ) 0, [ , ]x t t a b avem ( )d 0b

ax t ; deci 0 . Reciproc,

pentru orice funcție cu variație mărginită , nenegativă, cu integrala egală cu 1

pe [ , ]a b este satisfăcută evident (3.17). Astfel se definește (0)J . Pentru un

0, [ , ]x x C a b avem

(3.18) [ , ]

( ) (0), ( )d max ( )b

t a baJ x J x t x t

.

3. Norma unui spațiu Banach E este o funcțională subliniară specială care

joacă un rol important în teoria noastră. Conform celor demonstrate mai sus,

avem

(0) { , , , }x E x x x x E .

Ținând seama de definiția normei în spațiul dual aceasta ne conduce la

(3.19) (0) { , 1}x E x

,

adică sfera unitate din E . Apoi, pentru 0x ,

( ) { , 1, , }x x E x x x x

Sau, deoarece , 1x x x x

,

(3.20) ( ) { , 1, , }x x E x x x x

.

Așadar, subgradienți în 0x ai normei sunt orice funcționale din E care iau în

x valoarea egală cu x a căror existență este asigurată de consecința 1.1 a

teoremei lui Hahn-Banach.

Pentru nici un spațiu Banach norma nu este diferențiabilă Gâteaux în

origine. Există însă spații Banach în care norma este diferențiabilă în orice punct

0x . De exemplu, pentru spații Hilbert (3.20) conduce la

grad , 0x

x xx

.


Dacă norma este G-diferențiabilă atunci conform teoremei 3.3 există gradientul

normei care satisface

(3.21) grad 1, ,gardx x x x

pentru orice 0x , ca urmare a relației (3.20).

3.6. PROPRIETĂȚI DE CONTINUITATE ȘI MONOTONIE A

DIFERENȚIALELOR DIRECȚIONALE.

CLASE SPECIALE DE FUNCȚIONALE CONVEXE

Teorema 3.2 conduce la continuitatea pe o direcție a diferențialelor

direcționale laterale.

Teorema 3.7. Fie :J E o funcțională convexă proprie și ( )u D J ,

h E fixați. Atunci ( , )J u h h și ( , )J u h h

sunt nedescrescătoare în

și avem

(3.22) 0 0

lim ( , ) lim ( , ) ( , )J u h h J u h h J u h

,

(3.23) 0 0

lim ( , ) lim ( , ) ( , )J u h h J u h h J u h

.

Demonstrație. Este suficient să aplicăm teorema 3.2 funcției convexe f,

definită prin ( ) ( )f J u h pentru punctul 0 și să ținem seama de (3.6).

O consecință simplă a acestei teoreme este următoarea:

Consecința 3.8. Dacă :J E este o funcțională convexă proprie,

atunci are loc inegalitatea:

(3.24) ( , ) ( , ), ( ),J u v u J v v u u D J v E .

Capitolul 1


Demonstrație. Într-adevăr, luând h v u și ținând seama de rezultatele

precedente, în particular, rezultă pentru 0 1 inegalitatea (3.24).

Această inegalitate caracterizează funcționalele convexe G-diferențiabile.

Teorema 3.8. Funcționala J definită pe spațiul Banach E, G-

diferențiabilă pe o mulțime convexă U din domeniul ei de definiție este convexă

în U dacă și numai dacă avem

(3.25) ( , ) ( , ), ,J u v u J v v u u v U .

Demonstrație. Necesitatea rezultă din consecința 3.8. Pentru a dovedi

suficiența să considerăm pentru ,u v U oarecare fixați funcția scalară

( ) ( ( ))f J u v u .

După (3.6), f este diferențiabilă și ( ) ( ( ), )f J u v u v u care este

nedescrescătoare pentru [0,1] prin ipoteză. Conform consecinței 3.3, f este

atunci o funcție convexă, ceea ce implică imediat că J este convexă în U

deoarece ,u v erau oarecare în U.

Condiția (3.25) se mai scrie sub forma

(3.26) ,grad ( ) grad ( ) 0, ,v u J v J u u v U

deoarece funcționalele convexe G-diferențiabile sunt derivabile Gâteaux

(teorema 3.6).

Teorema 3.7 demonstrează între altele continuitatea pe o direcție a

diferențialei laterale. Comportarea acestei diferențiale atunci când convergența

argumentelor este arbitrară este dată de următoarea teoremă:

Teorema 3.9. Fie :J E o funcțională convexă proprie, continuă în

Int ( )D J și fie , Int ( )ix x D J și , , 1,2, ,iy y E i astfel încât

lim , limi ii i

x x y y

,

în topologia normei lui E. Atunci


lim sup ( , ) ( , )i ii

J x y J x y

.

Demonstrație. Fie ( , )J x y oarecare. Atunci există 0 încât

Int ( )x y D J și

[ ( ) ( )]J x y J x

.

Dar din continuitatea funcționalei rezultă

lim ( ) ( )i ii

J x y J x y

și lim ( ) ( )ii

J x J x

Atunci pentru i suficient de mare avem încă

[ ( ) ( )]i i iJ x y J x

.

Însă după teorema 3.2 avem

[ ( ) ( )]

( , ) i i ii i

J x y J xJ x y

,

astfel că

lim sup ( , )i ii

J x y

.

Cum această inegalitate are loc pentru orice ( , )J x y urmează concluzia

teoremei.

În capitolul al II-lea

, §1 vor fi necesare condiții în care convergența din

(3.22) să fie uniformă. În legătură cu aceasta vom demonstra următorul rezultat.

Teorema 3.10. Fie :J E o funcțională convexă proprie, continuă în

Int ( )D J . Atunci următoarele afirmații sunt echivalente:

a) există funcția scalară : nedescrescătoare continuă cu

(0) 0 astfel încât să avem

( , ) ( , ) ( ), Int ( ), , 1J u h h J u h u D J h E h ;

Capitolul 1


b) există funcțiile 1 : continuă, nedescrescătoare cu 1(0) 0 și

: [0,1] , cu (0) (1) 0, ( ) 0t și 0

( )lim , 0t

t

t

, încât

pentru orice , ( )x y D J și [0,1]t să avem

1( ) (1 ) ( ) ( (1 ) ) ( )tJ x t J y J tx t y t x y x y .

Demonstrație. Fie , ( )x y D J oarecare și [0,1]t . Folosind teorema 3.4

putem scrie:

( ) ( (1 ) ) ( ,(1 )( )) (1 ) ( , )J x J tx t y J x t y x t J x x y ,

( ) ( (1 ) ) ( , ( )) ( , )J y J tx t y J y t x y t J y y x .

Dacă înmulţim cele două inegalităţi cu t, respectiv cu (1 )t şi le adunăm,

obţinem

( ) (1 ) ( ) ( (1 ) ) (1 )[ ( , ) ( , )]t J x t J y J tx t y t t J x x y J y y x .

Notând , , , 1y u x u h x y h şi ţinând cont de omogeneitatea

diferenţialelor în raport cu direcţia, obţinem

( ) (1 ) ( ) ( (1 ) ) (1 ) [ ( , ) ( , )]t J x t J y J tx t y t t J u h h J u h .

De aici rezultă că a) b) cu 1 şi ( ) (1 ) .

Reciproc, dacă b) are loc pentru orice , ( )x y D J şi (0,1]t ,

1( ( )) ( ) (1 ) ( ) ( )J x t y x t J y t J x t x y x y

1( ( )) ( ) (1 ) ( ) ( )J y t x y t J x t J y t x y x y ,

care, prin adunare şi împărţire la t, conduc la

1

1 1 2( ( ( )) ( ( ( )) ( ) ( )J x t y x J y t x y J y t x y x y

t t t .

Pentru 0t obţinem

1( , ) ( , ) 2J x y x J y x y x y x y

care cu notaţiile de mai sus conduce la a) cu 1( ) 2 ( ) .


Consecinţa 3.9. În ipotezele teoremei 3.10 condiţia b) implică

(3.27) 10 ( ) ( ) ( , )J y J x J x y x x y x y ,

, ( )x y D J .

Demonstraţie. Din b) rezultă pentru (0,1)t :

1( ( )) ( ) ( ( ) ( )) ( )J x t y x J x t J y J x t x y x y ,

de unde dacă împărţim la t şi facem 0t obţinem (3.27).

Consecinţa 3.10. Dacă :J E este convexă şi G-diferenţiabilă, atunci

relaţia (3.27) este necesară şi sufucientă pentru satisfacerea condiţiilor

echivalente a) sau b).

Demonstraţie. Necesitatea a fost dovedită. Pentru suficienţă avem:

1( ) ( (1 ) ) ( (1 ) , ( )) ( )J y J tx t y J tx t y t y x t x y t x y ,

( ) ( (1 ) ) ( (1 ) ,(1 )( ))J x J tx t y J tx t y t x y

1((1 ) )(1 )t x y t x y ,

de unde, ţinând seama de monotonia lui 1 ,

1( ) (1 ) ( ) ( (1 ) ) 2 (1 ) ( )tJ x t J y J tx t y t t x y x y ,

adică b).

O altă clasă de funcţionale convexe pentru care are loc uniformitatea

limitei (3.22) este definită în cele ce urmează.

Definiţia 3.5. Funcţionala convexă :J E este uniform direcțional

diferențiabilă pe o mulțime convexă ( )D D J dacă oricare ar fi 0 , există

( ) 0 astfel ca pentru orice x D și h E cu 1h avem

(3.28) ( ) ( )

0 ( , )J x h J x

J x h

îndată ce 0 ( ) .

Teorema 3.11. Convergența dată de a doua limită din (3.22) este

uniformă pentru ,u D h E cu 1h , unde D este o mulțime convexă

Capitolul 1


compactă din Int ( )D J , dacă și numai dacă funcționala J, convexă și continuă

în D este uniform direcțional diferențiabilă pe D.

Demonstrație. Deoarece pentru 0, ( ) ( )J u J u h

( , )J u h h ( , )J u h h

, avem

( ) ( )

0 ( , ) ( , ) ( , )J x h J x

J x h J u h h J u h

.

Așadar, necesitatea condiției este imediată.

Reciproc, să presupunem că J este uniform direcțional diferențiabilă pe D

și fie , 1x E h , arbitrare. Atunci, pentru orice 0 există ( ) 0 ,

independent de x și h, încât pentru 0 și 0 ( )t ,

( ) ( )

0 ( , )2

J x h th J x hJ x h h

t

.

Pentru un 0 (0, ( ))t fixat, avem

(3.29) 0 0

( ) ( )( , ) ( , )

2 2J x h h J x h

t t

,

unde 0 0( ) ( ) ( ) ( ) ( )J x h t h J x h J x t h J x . Continuitatea

funcționalei J pe mulțimea compactă D este uniformă. Deci există ( ) 0 încât

pentru 0 ( ) ,

00 0( ) ( ) ( ) ( ) ( )

2

tJ x h t h J x t h J x h J x

.

Atunci din (3.29) urmează ( , ) ( , )J x h h J x h pentru toți 0 ( ) și

orice ,x D h E cu 1h . Cum însă

0 ( , ) ( , ) ( , ) ( , )J x h h J x h J x h h J x h ,

rezultă afirmația.


§4. ELEMENTE DE TEORIE PUNCTELOR DE MINIM

ALE FUNCȚIONALELOR

4.1. SEMICONTINUITATE TARE ȘI SLABĂ

Un concept de bază în teoria punctelor de optim este acela de

semicontinuitate.

Definiția 4.1. Fie E un spațiu Banach. Se spune că funcționala :J E

este semicontinuă inferior în 0x E dacă

(4.1) 0

0liminf ( ) ( )x x

J x J x

,

unde limita inferioară este luată pentru 0x x în topologia normei, J este

semicontinuă superior în 0x dacă

(4.2) 0

0limsup ( ) ( )x x

J x J x

.

Analog, dacă argumentul converge la 0x în topologia slabă, se obțin noțiunile

corespunzătoare. J este slab semicontinuă inferior în 0x E dacă

(4.3) 0

0liminf ( ) ( )x x

J x J x

și respectiv, slab semicontinuă superior în 0x dacă

(4.4) 0

0limsup ( ) ( )x x

J x J x

.

Dacă J este (slab) semicontinuă în ambele sensuri în 0x , atunci ea este (slab)

continuă în acest punct. Deoarece proprietățile legate de semicontinuitate

Capitolul 1


inferioară și superioară sunt simetrice și se obțin una din alta prin considerarea

funcționalei J , ne vom ocupa numai de una din ele și anume de cea inferioară

(tare sau slabă). După definiția limitei inferioare (4.1) și (4.3) se pot scrie sub

forma

0

0( )

sup inf ( ) ( )x VV x

J x J x

V

,

unde 0( )xV este un sistem de vecinătăți ale lui 0x în topologia tare, respectiv

slabă. Cum însă 0x se află în orice astfel de vecinătate, 0inf ( ) ( )x V

J x J x

și

atunci (4.1) și (4.3) sunt echivalente cu

(4.1’) 0

0liminf ( ) ( )x x

J x J x

,

(4.3’) 0

0liminf ( ) ( )x x

J x J x

.

Dacă o funcţională este semicontinuă în orice punct din E, se spune că ea este

semicontinuă pe E. O caracterizare a acestei proprietăți este dată de următoarea

teoremă:

Teorema 4.1. Pentru funcționala :J E următoarele trei afirmații

sunt echivalente:

(i) J este (slab) semicontinuă pe E;

(ii) mulțimile de nivel { , ( ) },x E J x sunt (slab) închise în E;

(iii) epigraful funcționalei {[ , ] , ( ) }x E J x este (slab) închis în E.

Demonstrația se face la fel în topologia tare ca și în cea slabă (de altfel

teorema este adevărată într-un spațiu liniar topologic oarecare). Să arătăm că

(i) (iii). Dacă (i) are loc, fie [ , ]i ix E astfel ca ( )i iJ x și

lim , limi ii i

x x

. Cum limita inferioară a șirului ( )iJ x de numere reale

este cel mai mic punct de acumulare, vom avea la limită


( ) liminf ( )ii

J x J x

,

adică [ , ] epix J , deci (iii). Luând în particular i , obținem și implicția

(i) (ii). Reciproc, dacă (ii) are loc, să arătăm că J este (slab) semicontinuă

inferior. Fie ,nx E x E cu lim nn

x x

și fie

lim inf ( )nn

b J x

.

Dacă b , atunci pentru orice real, există un subșir ( )nJ x , de unde

din cauza ipotezei ( )J x și deci ( )J x b . Fie acum b finit. Să

presupunem prin reducere la absurd că ( )J x b . Atunci, pentru

0 ( )J x b , avem

(1.4) ( )J x b .

Din definiția lui b există însă subșirul nx cu

( )2 2

nb J x b

.

De aici, datorită ipotezei rezultă

( )2

J x b

,

care contrazice pe (1.4). Așadar ( )J x b și (4.1’) sau (4.3’) este dovedită.

Observând că (iii) (ii), demonstrația este încheiată.

Să considerăm acum cazul funcționalelor convexe.

Teorema 4.2. Fie :J E o funcțională convexă definită pe spațiul

Banach E. J este semicontinuă inferior în E dacă și numai dacă este slab

semicontinuă inferior în E.

Demonstrație. Conform propoziției 3.1 epigraful lui J este o mulțime

convexă. Dar într-un spațiu Banach, o mulțime convexă este închisă dacă și

numai dacă este slab închisă (consecința 1.6 a teoremei lui Hahn-Banach). Deci

Capitolul 1


aplicând teorema precedentă, rezultă echivalența semicontinuității inferioare cu

slaba semicontinuitate inferioară.

Un alt rezultat privitor la funcționalele convexe este următorul:

Teorema 4.3. Dacă o funcțională convexă proprie :J E este

semicontinuă inferior în E, atunci J este continuă în interiorul domeniului

efectiv.

Demonstrație. Aplicând consecința 3.2 și teorema 4.1 rezultă afirmația.

Consecința 4.1. Orice funcțională convexă și semicontinuă inferior este

subdiferențială în interiorul domeniului său efectiv și reciproc, o funcțională

subdiferențială pe o mulțime convexă în care ea este definită este convexă și

semicontinuă inferior.

Demonstrația decurge aplicând teoremele 4.3 și 3.5.

Consecința 4.2. Orice funcțională G-diferențiabilă și convexă este

semicontinuă inferior.

Demonstrație. Într-adevăr, o funcțională G-diferențiabilă și convexă este

subdiferențiabilă (teorema 3.6) și deci este semicontinuă inferior.

Echivalența între slaba semicontinuitate și semicontinuitatea inferioară nu

este o proprietate caracteristică funcționalelor convexe.

Definiția 4.2. O funcțională J este cvasiconvexă pe o mulțime convexă U

din domeniul său de definiție dacă

( (1 ) ) max{ ( ), ( )}, [0,1]J x y J x J y ;

J este strict cvasiconvexă în U dacă inegalitatea este strictă pentru orice x y și

(0,1) .

Desigur funcționalele convexe sunt în particular cvasiconvexe.

Iată o caracterizare a acestora din urmă.


Lema 4.1. O funcțională J este cvasiconvexă pe mulțimea convexă U

dacă și numai dacă orice mulțime de nivel a ei este convexă.

Demonstrație. Din definiție se verifică ușor că mulțimile de nivel ale unei

funcționale cvasiconvexe sunt convexe. Reciproc, dacă presupun aceasta, fie

,x y U și max{ ( ), ( )}a J x J y . Cum ,x y sunt în mulțimea de nivel

{ , ( ) }x U J x a , care este convexă prin ipoteză, va rezulta că și orice

combinație convexă a lui x și y face parte din această mulțime.

Consecința 4.3. Pentru funcționalele cvasiconvexe semicontinuitatea

inferioară este echivalentă cu slaba semicontinuitate inferioară.

Demonstrație. Lema 4.1 împreună cu teorema 4.3 (ii) demonstrează

rezultatul.

4.2. TEOREME DE EXISTENȚĂ ȘI DE UNICITATE

A PUNCTELOR DE MINIM

Definiția 4.3. Fie : ( , ]J E o funcțională definită în spațiul

Banach E și U E o submulțime a domeniului său de definiție. Vom spune că

u U este punct de minim local al funcționalei J în U dacă există o vecinătate

( )u UV a acestui punct astfel ca

( )

( ) inf ( )v u

J u J v

V

.

În acest caz vom folosi notația „min” pentru marginea inferioară.

Se spune că u U este punct de minim absolut în U al funcționalei J dacă

( ) min ( )v U

J u J v

.

Capitolul 1


Definiții corespunzătoare se pot da pentru punctele de maxim local sau absolut.

Principalul rezultat privind existența punctelor de minim este o

generalizare a teoremei lui Weierstrass clasice.

Teorema 4.4. Fie E un spațiu Banach reflexiv, funcționala

: ( , ]J E slab semicontinuă inferior în E și U o mulțime mărginită și

slab închisă din E; atunci există cel puțin un punct de minim absolut al

funcționalei J în U.

Demonstrație. Fie inf ( )v U

l J v

și { }nu U astfel ca 0lim ( )n

J u l

. Cum

spațiul este reflexiv U este slab secvențial compactă (propoziția 1.1). fie { }nu un

subșir al șirului { }nu slab convergent,

,nu u U n .

Conform ipotezei de slabă semicontinuitate inferioară,

( ) lim inf ( ) inf ( )nn v U

J u J u l J v

.

Deci ( )J u l și teorema este dovedită.

Consecința 4.4. Dacă :J E definită pe spațiul reflexiv E este

convexă proprie și semicontinuă inferior și U E o mulțime convexă, închisă

și mărginită din E, atunci există puncte de minim absolut al funcționalei, în U.

Observația 4.1. Conform consecinței 4.3 condiția de convexitate a

funcționalei se poate înlocui și cu cvasiconvexitatea ei. Teorema 4.4, deși foarte

generală, conține ipoteza tare a mărginirii mulțimii U pe care se caută minimul.

O variantă a teoremei prin care se slăbește această ipoteză este următoarea:

Teorema 4.5. Fie E un spațiu Banach reflexiv, : ( , ]J E o

funcțională slab semicontinuă inferior și U E slab închisă astfel încât

(4.5) 0 0 0, ( ) { , ( ) ( )}x U W x x U J x J x este mărginită.

În aceste condiții există măcar un punct de minim absolut în U al funcționalei.


Demonstrație. Teorema se reduce la cea precedentă căci 0( )W x este slab

închisă conform teoremei 4.1 și marginea inferioară a lui J pe U nu este

influențată de valorile acestei funcționale în afara lui 0( )W x .

Observația 4.2. O condiție mai puternică decât (4.5), dar mai comodă în

aplicații, este condiția de coercivitate:

(4.6) lim ( )x

J x

.

Această condiție asigură mărginirea mulțimilor de nivel 0{ , ( ) ( )}x E J x J x

pentru orice 0 ( )x D J pentru care J este finită. Astfel, alegerea lui 0x – foarte

importantă la modelele iterative – nu mai constituie o problemă.

Consecința 4.5. Dacă :J E definită pe spațiul Banach reflexiv este

convexă proprie și semicontinuă inferior și dacă există o mulțime de nivel

0( )W x în mulțimea convexă și închisă U E care satisface (4.5) atunci J

admite cel puțin un punct de minim absolut u în U.

În cazul dublei G-derivabilități are loc rezultatul următor foarte des folosit

în aplicații.

Consecința 4.6. Fie E un spațiu Banach reflexiv și :J E o

funcțională de două ori G-diferențiabilă astfel că există funcția scalară pozitivă

( )r t cu lim ( )t

r t

pentru care are loc

( , , ) ( ), ( ),J u r u D J E .

Atunci funcționala J are cel puțin un punct de minim absolut în E.

Demonstraţie. Conform consecinţei 3.7, J este convexă, deci G-derivabilă

şi semicontinuă inferior (consecinţa 4.2). Formula lui Taylor ne dă:

1

( ) (0) ,gard (0) ( , , )2

J x J x J J x x x ,

unde (0,1) . De aici

Capitolul 1


1

( ) (0) grad (0) ( )2

J x J J x r x ,

care, în ipotezele date, implică condiţia (4.6) de coercivitate. Aşadar există cel

puţin un punct de minim absolut în U.

Dacă se renunţă la reflexivitatea spaţiului, pentru a asigura existenţa

punctelor de minim se impun condiţii mai puternice asupra mulţimii U.

Teorema 4.6. Fie : ( , ]J E definită pe spaţiul Banach oarecare E,

semicontinuă inferior. Dacă U E este o mulţime compactă din spaţiu, atunci

funcţionala J admite cel puţin un punct de minim absolut în U.

Demonstraţia este similară cu cea a teoremei 4.4. În spaţii finit

dimensionale aceste două teoreme coincid.

Să indicăm acum şi o teoremă de unicitate a minimului.

Teorema 4.7. O funcţională J strict cvasiconvexă admite cel mult un punct

de minim absolut pe o mulţime convexă U.

Demonstraţie. Dacă 1 2 1 2, ,x x U x x ar fi puncte de minim, adică

1 2( ) ( ) inf ( )x U

J x J x J x

, am avea

1 2 1 2( (1 ) ) max{ ( ), ( )} inf ( ), (0,1)x U

J x x J x J x J x

,

ceea ce este absurd deoarece 1 2(1 )x x U .

În particular, unicitatea are loc pentru funcţionale strict convexe, care sunt

evident strict cvasiconvexe. În condiţiile consecinţei 4.6, dacă ( ) 0, 0r t t ,

atunci J este evident strict convexă şi avem unicitatea.

Poliak a arătat că o funcţională continuă pe un spaţiu reflexiv E îşi atinge

minimul unic pe fiecare mulţime convexă, închisă şi mărginită dacă şi numai

dacă ea este strict cvasiconvexă. Astfel că ipoteza de strictă cvasiconvexitate

este, se pare, cea mai naturală pentru problemele de minimizare.


Totuşi vom prefera să impunem condiţia mai puternică a convexităţii

funcţionalei, pentru motivul că funcţionalele convexe, după cum am văzut mai

sus, admit diferenţiale direcţionale laterale pe orice direcţie, ceea ce permite

abordarea unor metode eficiente de calcul numeric al punctelor de minim.

4.3. TEOREME DE CARACTERIZARE A PUNCTELOR DE MINIM

Condiţia necesară clasică de extremum local se generalizează pentru

funcţionale G-diferenţiabile după cum urmează.

Teorema 4.8. Dacă J este o funcţională G-diferenţiabilă definită în

spaţiul Banach E, U o mulţime deschisă din spaţiu şi u un punct de minim local

în U, atunci

(4.7) ( , ) 0,J u h h E .

Demonstraţie. Cum U este deschisă şi u este punct de minim local, există

o vecinătate a lui 0{ , , , }u v E v u h h E inclusă în U, în care

( )J u este minimul valorilor lui J. Deci

0( ) ( ), ,J u h J u h E .

Pentru 0 cu valori pozitive obţinem ( , ) 0,J u h h E . Schimbând pe h

în h , obţinem şi ( , ) 0J u h , adică (4.7).

În cazul în care J este G-derivabilă, (4.7) se scrie sub forma

(4.7') grad ( ) 0J u

Capitolul 1


şi este o ecuaţie (neliniară în general) printre soluţiile căreia se găsesc şi

punctele de minim local ale lui J.

În cazul funcţionalelor convexe obţinem chiar o condiţie necesară şi

suficientă de minim.

Teorema 4.9. Fie :J E o funcţională convexă proprie, ( )u D J

este punct de minim absolut al funcţionalei J în E dacă şi numai dacă J este

subdiferenţiabilă în u şi 0 ( )J u . Pentru funcţionale convexe, orice punct de

minim local într-o mulţime deschisă este punct de minim absolut pe întreg

spaţiul.

Demonstraţie. Prima parte rezultă din definiţia subdiferenţialei. Dacă

0 ( )J u , avem

( ) ( ) ,0 0,J v J u v u v E ;

reciproc, dacă u este punct de minim absolut pe E, avem

( ) ( ) ,0 0,J v J u v u v E

adică în u funcţionala este subdiferenţiabilă, 0 fiind subgradient.

Fie acum u un punct de minim local într-o mulţime deschisă (eventual pe

întreg spaţiul). Atunci ( ) ( ),J u J u h h E , pentru suficient de mic.

Luând 0 şi împărţind la , obţinem ( , ) 0,J u h h E . Pe de altă parte,

după (3.6'), avem ( ) ( ) ( , ) 0,J u h J u J u h h E , adică u este punct de

minim absolut pe întreg spaţiul.

Consecinţa 4.7. Condiţia necesară şi suficientă ca funcţionala J convexă

şi G-diferenţiabilă să admită un punct de minim absolut în E (sau local într-o

mulţime deschisă U E ) este relaţia (4.7').


Demonstraţie. După teorema 3.6, J este G-derivabilă şi ( )J u conţine un

singur punct și anume conține grad ( )J u . Din teorema 4.9 rezultă atunci

afirmaţia.

Observaţia 4.3. Rezolvarea ecuaţiei (4.7') este echivalentă cu determi-

narea punctelor de minim ale funcţionalei J. Operatorii :T E E pentru care

există funcţionala :J E astfel ca ( ) grad ( ),T u J u u E se numesc

operatori potenţiali. Conform teoremei 3.8, condiţia necesară şi suficientă ca

rezolvarea ecuaţiei ( ) 0T u , cu operatorul T potenţial, să fie echivalentă cu

găsirea punctelor de minim ale funcţionalei J, este ca (vezi 3.26)

, ( ) ( ) 0, ,v u T v T u u v E .

Operatorii cu această proprietate se numesc operatori monotoni.

Pentru punctele de minim absolut pe o mulţime U convexă, condiţia

necesară standard este dată de următoarea teoremă.

Teorema 4.10. Dacă J este o funcţională G-diferenţiabilă definită în

spaţiul Banach E, U o mulţime convexă şi u U un punct de minim absolut în

U, atunci are loc inegalitatea variaţională:

(4.8) ( , ) 0,J u v u v U .

Demonstraţie. Avem pentru orice v U şi (0,1] ,

( ) ( ( )) ( )u v u U J u v u J u ,

de unde dacă împărţim la 0 şi facem pe 0 să tindă la zero obţinem (4.8). Pentru

funcţionale convexe avem corespunzător un rezultat de caracterizare a punctelor

de minim.

Teorema 4.11. Fie :J E o funcţională convexă proprie şi U o

mulţime convexă din E. Elementul u U este punct de minim absolut în U dacă

şi numai dacă are loc inegalitatea variaţională

(4.9) ( , ) 0,J u v u v U .

Capitolul 1


În plus, orice punct de minim local în U este şi punct de minim absolut în

această mulţime.

Demonstraţie. În demonstraţia teoremei 4.10 s-a luat 0 convergent la

zero, aşadar în condiţiile noastre rezultă (4.9). Reciproc, conform lui (3.6') avem

( ) ( ) ( , ) 0,J v J u J u v u v U ,

adică u este punct de minim absolut în U.

Dacă u este punct de minim local în U există vecinătatea

0{ ( ), , 0 1}x u v u v U din U pentru care

( ) ( ( )) ( )J x J u v u J u .

Făcând pe 0 obţinem după împărţirea la inegalitatea (4.9) care implică

faptul că u este punct de minim absolut în U.

Consecinţa 4.8. Fie :J E o funcţională convexă G-diferenţiabilă pe

mulţimea convexă U E . Atunci următoarele afirmaţii sunt echivalente:

(i) u U este punct de minim absolut în U;

(ii) ( , ) 0,J u v u v U ;

(iii) ( , ) 0,J v v u v U .

Demonstraţie. Echivalenţa lui (i) cu (ii) rezultă ca un caz particular din

teorema 4.11. Apoi dacă (i) are loc după consecinţa 3.6 avem

0 ( ) ( ) ( , ) ( , ),J u J v J v u v J v v u v U ,

adică (iii). În sfârşit dacă (iii) are loc avem în particular pentru

( ), , (0,1]v u w u w U ,

( ( ), ) 0J u w u w u ,

de unde împărţind la şi apoi făcând pe 0 obţinem conform teoremei 3.7,

( , ) 0,J u w u w U ,

adică (ii).


Observaţia 4.4. Deoarece funcţionalele convexe G-diferenţiabile sunt

chiar G-derivabile (teorema 3.6), inecuaţiile variaţionale (ii) şi (iii) se pot scrie şi

sub forma

,gard ( ) 0,v u J u v U ,

respectiv

,gard ( ) 0,v u J v v U .

Consecinţa 4.9. Fie :J E o funcţională care se poate scrie ca sumă

a două funcţionale 1 2J J J cu 1 :J E convexă G-diferenţiabilă în U

(convexă) şi 2 :J E convexă în U. Atunci următoarele afirmaţii sunt

echivalente:

(i) u U este punct de minim absolut în U;

(ii) 1 2 2( , ) ( ) ( ) 0,J u v u J v J u v U ;

(iii) 1 2 2( , ) ( ) ( ) 0,J v v u J v J u v U .

Demonstraţie. Dacă (i) are loc avem

1 2 2 1 2( , ) ( ) ( ) ( , ) ( , ) ( , ) 0,J u v u J v J u J u v u J u v u J u v u v U ,

după teorema 4.11 adică (ii). În aceeaşi ipoteză, dacă ţinem seama că

1 1( , ) ( , ),J v v u J u v u v U ,

conform teoremei 3.8 rezultă şi (iii).

Reciproc, dacă (ii) are loc avem

1 1 2 2 1 2 2( ) ( ) ( ) ( ) ( ) ( ) ( , ) ( ) ( ) 0J v J u J v J u J v J u J u v u J v J u ,

v U ,

adică u este punct de minim în U. Faptul că (iii) (ii) se demonstrează ca şi la

consecinţa 4.8.

În multe probleme practice, mulţimea U în care se caută minimul este

descrisă de inegalităţi cu funcţionale convexe. Pentru aceste situaţii

Capitolul 1


caracterizarea punctului de minim dată de teorema 4.11 ia o formă specială care

stă la baza multor algoritmi de aproximare a soluţiei.

Teorema 4.12. Fie 1 : , 0,1,2, ,J E i m funcţionale convexe

semicontinue inferior pe spaţiul Banach E şi fie 1{ , ( ) 0,U x J x

, ( ) 0}mJ x cu interiorul nevid. Atunci u U este punct de minim al

funcţionalei 0J absolut în U dacă şi numai dacă are loc relaţia

(4.10) 0min max{ ( , ), ( ) ( , ), 1,2, , } 0i ih S

J u h J u J u h i m

,

pentru orice S E care conţine originea.

Demonstraţie. Relaţia (4.10) este echivalentă cu

(4.10') 0max{ ( , ), ( ) ( , ), 1,2, , } 0,i iJ u h J u J u h i m h E

căci pentru 0h acest maxim este evident 0. Dacă v u h este în U avem

după (3.6), 0 ( ) ( ) ( , )i i iJ u h J u J u h . Dacă u satisface (4.10') va trebui

atunci ca 0 0( , ) ( , ) 0J u h J u v h ceea ce arata că u este punct de minim

absolut în U conform teoremei 4.11.

Reciproc, dacă u este punct de minim absolut în U să arătăm că are loc

(4.10'). Să presupunem că ar exista h E astfel ca ( ) ( , ) 0i iJ u J u h ,

1,2, ,i m şi totuşi 0 ( , ) 0J u h . Pentru acei indici i pentru care ( ) 0iJ u

din cauza continuităţii lui iJ există 0i încât ( , ) 0iJ u h . Pentru ceilalţi

indici avem ( ) 0iJ u şi deci ( , ) 0iJ u h . După definiţia diferenţialei laterale

pentru orice 0 ( , )iJ u h există i încât 0 ( ) ( )i i iJ u h J u

( , )i i iJ u h de unde din nou ( ) 0i iJ u h .

Luând min{ , 1,2, , }i i m , u h U şi atunci, conform teoremei 4.11

0 ( , ) 0J u h , absurd. De aici rezultă cu necesitate (4.10').


Consecinţa 4.10. În ipotezele teoremei 4.12 condiţia (4.10) este

echivalentă cu relaţia:

(4.11) 0

0( )

min max ( , ) 0, ( ) {0} { 0, ( ) 0}i ih S i I u

J u h I u i J u

,

Pentru orice S E care conţine pe 0.

Demonstraţie. Condiţia (4.11) este echivalentă cu

(4.11') 0max{ ( , ), ( )} 0,iJ u h i I u h E .

Dacă (4.11') are loc atunci evident

0 00 max{ ( , ), ( )} max{ ( , ) ( , ), }i iJ u h i I u J u h J u h i ,

adică (4.10').

Reciproc, dacă are loc (4.10) u este punct de minim absolut în U. Să

presupunem că ar exista h E astfel încât 0( , ) 0, ( )iJ u h i I u . Atunci,

aplicând acelaşi raţionament ca în demonstraţia teoremei precedente, ar rezulta

existenţa unui 0 , astfel încât u h U şi deci 0 ( , ) 0J u h ceea ce

contrazice presupunerea făcută deoarece 00 ( )I u . De aici urmează (4.11') şi

demonstraţia este încheiată.

4.4. EXEMPLE

1. Fie :a E E o funcţională biliniară, simetrică, continuă pe E E

(E fiind un spaţiu Banach reflexiv) şi astfel ca

(4.12) 2

0, , ( , )m x E a x x m x .

Capitolul 1


Fie de asemenea ,f E şi funcţionala pătratică (vezi exemplul 2,

secţiunea 2.5) :J E definită prin 1

( ) ( , ) ,2

J v a v v v f . Am văzut că

( , ) ( , ) , ,

( , , ) ( , ) , ,

J v a v f Av f

J v a A

unde ( , )A L E E . În ipotezele noastre avem

2

( , , ) ( , ) , 0J v a m ,

deci conform consecinţei 3.7 J este strict convexă.

Condiţiile de existenţă a unui punct de minim absolut unic pe E sunt

satisfăcute (consecinţa 4.6).

Conform consecinţei 4.7 acest punct de minim este caracterizat de ecuaţia

(4.7) care aici are forma

Au f .

Acesta este de altfel singurul caz în care ecuaţia cu operator potenţial

echivalentă cu problema de minim este liniară. De aceea între minimizarea

funcţionalelor pătratice şi minimizarea altor funcţionale există acelaşi raport ca

între ecuaţiile liniare şi cele neliniare. Din cauza formulei lui Taylor orice

funcţională de două ori G-derivabilă cu hessianul pozitiv definit se comportă

local ca o funcţională pătratică. Această observaţie stă la baza multor algoritmi

analogi pentru problemele de optimizare cu metodele de liniarizare din cazul

ecuaţiilor neliniare.

2. Să considerăm un caz particular important. Fie o mulţime deschisă

din n cu frontieră . Considerând derivatele în sensul teoriei distribuţiilor

spaţiul Sobolev 1( )H este spaţiul funcţiilor 2 ( )v L cu derivatele


generalizate 2 ( ), 1,2, ,i

uL i n

x

, cu topologia de spaţiu Hilbert indusă de

produsul scalar

1

(( , )) ( , ) ,n

i i i

u vu v u v

x x

,

şi norma 1 2

1(( , ))v v v , unde cu (.,.) am notat produsul scalar din 2 ( )L . Fie

de asemenea ( )D spaţiul funcţiilor indefinit derivabile cu suport compact în

şi fie 1

0( )H închiderea acestui spaţiu în topologia lui 1( )H . Considerăm

funcţionala

(4.14)

2

2

0

1

1( ) ( ) ( ) ( ) ( ) d ( ) ( )d

2

n

i

i i

vJ v A x x A x v x x F x v x x

x

,

unde ( )jA L şi ( ) 0, 0,1, ,jA x C j n , a.p.t. în , 2( )F L iar

1

0( )v H . Aceasta este o funcţională pătratică cu

(4.15) 0

1

( , ) ( ) ( ) ( ) ( ) ( ) ( ) dn

i

i i i

u va u v A x x x A x u x v x x

x x

și

( , ) ( ) ( )dv f F x v x x

.

În condiţiile date avem

1 1

1

( , ) dn

i i i

u va u v M u v x M u v

x x

,

unde 0

maxn

jj

M A

. În plus

2

2 2

11

( )( , ) d ( ) d

n

i i

v xa u v C x v x x C v

x

.

Capitolul 1


Deci J are punct de minim unic u în 1

0( )H care este caracterizat de ecuaţia

variaţională

(4.16) 0

1

( ) ( ) ( ) ( ) ( ) ( ) d ( ) ( )dn

i

i i i

uA x x x A x u x x x F x x x

x x

pentru orice 1

0( )H . Dacă în particular coeficienţii , 1,2, ,iA i n au derivate

generalizate de ordinul întâi şi căutăm 1 2

0( ) ( )u H H pentru orice cu

închiderea în , formula lui Green aplicată integralei din membrul stâng pentru

( ) D , ne dă

(4.17) 0

1

( ) ( ) ( ) ( )d ( ) ( )dn

i

i i i

uA x A x u x x x F x x x

x x

pentru că ( ) 0,u x x . Cum ( )D este densă în 1

0( )H ecuaţia

variaţională revine la problema lui Dirichlet,

(4.18) 0

1

( ) ( ) ( ) ( ) 0,n

i

i i i

uA x A x u x F x x

x x

,

( ) 0,u x x .

Reciproc, orice soluţie a problemei lui Dirichlet (4.18) din 1

0( )H care aparţine

lui 2( ),H cu satisface ecuaţia variaţională (4.16) a.p.t. în .

Ecuaţia variaţională are sens însă şi dacă renunţăm la condiţiile ca iA să fie

diferenţiabile şi să fie în 2 ( )H . Vom numi atunci soluţie generalizată în

1( )H a problemei lui Dirichlet (4.18) orice funcţie 1

0( )u H care satisface

ecuaţia variaţională (4.16) pentru orice 1

0( )H . Existenţa şi unicitatea

acestei soluţii este demonstrată de faptul că ea este punctul de minim unic al

funcţionalei J. Analog, se poate arăta că într-un sens generalizat problema lui

Neumann este echivalentă cu o ecuaţie variaţională pe 1( )H .


3. Fie E un spaţiu Hilbert, U E o mulţime convexă şi închisă şi x E

fixat. Considerăm funcţionala :J E dată prin

2 21 1 1

( ) ( , ) ( , )2 2 2

J v v x v v x v x .

Aceasta este o funcţională pătratică cu ( , ) ( , ), , 1a u v u v f x m şi 21

2x .

Conform celor de mai sus există un punct de minim unic u în mulţimea U care

este caracterizat după consecinţa 4.8 (ii), (iii) prin inegalităţile echivalente:

( , ) 0,u x v u v U ,

sau

( , ) 0,v x v u v U .

Punctul u se numeşte proiecţia lui x pe U. Dacă lăsăm pe x să varieze în E,

obţinem un operator

( )x E u P x U ,

care este caracterizat prin inegalităţile

(4.19) ( ( ) , ( )) 0,P x x v P x v U ,

sau

(4.20) ( , ( )) 0,v x v P x v U .

Capitolul 2

ALGORITMI DE MINIMIZARE FĂRĂ RESTRICŢII A FUNCŢIONALELOR CONVEXE ÎN SPAŢII

BANACH 63

Capitolul 2

ALGORITMI DE MINIMIZARE FĂRĂ RESTRICŢII A

FUNCŢIONALELOR CONVEXE ÎN SPAŢII BANACH

§1. O TEORIE GENERALĂ A METODELOR DE DESCREŞTERE

Contents Capitolul 2 ALGORITMI DE MINIMIZARE FĂRĂ RESTRICŢII A

FUNCŢIONALELOR CONVEXE ÎN SPAŢII BANACH................................................. 63

§1. O TEORIE GENERALĂ A METODELOR DE DESCREŞTERE .............................. 63

1.1. INTRODUCERE. TEOREMA DE CONVERGENŢĂ ........................................... 63 1.2. ALEGEREA DIRECŢIILOR DE CONVERGENŢĂ ............................................. 73

1.3. ALEGEREA FACTORILOR DE CONVERGENŢĂ ............................................. 80 1.4. METODA LUI GOLDSTEIN GENERALIZATĂ .................................................. 84 1.5. METODA LUI ARMIJO GENERALIZATĂ ......................................................... 88

§ 2. METODELE GRADIENŢILOR CONJUGAŢI .......................................................... 91 2.1. METODA GRADIENŢILOR CONJUGAŢI PENTRU FUNCŢIONALE

PĂTRATICE ................................................................................................................... 91

1.1. INTRODUCERE. TEOREMA DE CONVERGENŢĂ

Fie J o funcţională definită pe spaţiul Banach E. Problema determinării

punctelor u E pentru care

(1.1) min ( ) ( )v E

J v J u

,


dacă astfel de puncte există se numeşte problemă de minimizare fără restricţii a

funcţionalei J. Denumirea este justificată de faptul că atunci când se consideră

problema minimizării unei funcţionale pe o mulţime U E această mulţime

este descrisă în cele mai multe cazuri prin egalităţi sau inegalităţi care reprezintă

restricţiile problemei.

În capitolul I – §4, am văzut în ce condiţii avem asigurată existenţa unui

punct de minim absolut u pe întreg spaţiul: reflexivitatea spaţiului,

semicontinuitatea inferioară slabă a funcţionalei J şi o condiţie de forma

(1.2) 0 0 0( ), ( ) { , ( ) ( )}u D J W u x E J x J u

mărginită sau, mai restrictiv,

(1.3) lim ( )x

J x

,

condiţii care permit reducerea problemei (1.1) la o problemă de minimizare pe o

mulţime mărginită. Pentru a găsi algoritmi practici de rezolvare a problemei nu

sunt însă suficiente aceste condiţii generale de existenţă a soluţiei fiind necesare

ipoteze care să permită şi caracterizări ale punctelor de minim. Teorema I.4.9 şi

consecinţa I.4.7 furnizează caracterizări simple în ipoteza suplimentară că J este

convexă şi subdiferenţiabilă sau G-diferenţiabilă. Conform teoremelor I.3.5 şi

I.4.3 este necesar şi suficient ca funcţionala să fie convexă şi semicontinuă

inferior pentru a fi subdiferenţiabilă şi în aceste ipoteze conform teoremei I.4.2,

J este şi slab semicontinuă inferior.

Aşadar, fie :J E o funcţională convexă proprie, semicontinuă

inferior, definită pe spaţiul Banach reflexiv E şi astfel încât condiţia (1.2) să fie

satisfăcută. Pentru anumite metode iterative particulare vom face chiar ipoteza

mai puternică (1.3). În aceste condiţii există măcar un punct de minim absolut u,

soluţie a problemei (1.1) care este caracterizat de relaţia

(1 .4) 0 ( )J u .

Capitolul 2


BANACH 65

În cazul în care J este chiar G-diferenţiabilă (1.4) are forma

(1.5) grad ( ) 0J u ,

ecuaţie cu operator potenţial monoton.

Observaţia 1.1. Conform teoremei I.4.9 orice punct de minim local într-o

mulţime deschisă U E este punct de minim absolut pe întreg spaţiul. Aşadar,

putem rezolva şi probleme de minimizare cu restricţii în care domeniul

restricţiilor U este deschis căutând puncte de minim absolut u în E cu singura

condiţie ca u U . În acest mod toate metodele de aproximare a punctelor de

minim fără restricţii, expuse în acest capitol, pot fi adaptate şi pentru probleme

cu restricţii impunând în plus condiţii ca aproximările succesive să satisfacă

restricţiile dar aceasta se poate face numai dacă domeniul restricţiilor este o

mulţime deschisă.

În cele ce urmează ne vom ocupa de o clasă de metode iterative de

aproximare a soluţiilor problemei (1.1) pe care le vom numi metode de

descreştere. Ideea acestor metode este simplă. Vom construi un şir de elemente

{ }nu numite iteraţii pornind de la 0u dat de (1.2) cu formula

(1.6) 1 , 0,1,2,n n n nu u h n ,

unde nh E şi n se aleg pentru fiecare pas în aşa fel încât să asigurăm

descreşterea valorilor funcţionalei J şi convergenţa într-un sens sau altul a

şirului nu la o soluţie a problemei (1.1).

Fără a restrânge generalitatea putem presupune că 0n căci semnul lui

n se poate totdeauna schimba pe seama lui nh . De asemenea, putem presupune

0nh şi chiar 1nh deoarece un factor de normare se poate include în n .

Vom impune asupra lui { }nh şi { }n condiţii care să permită convergenţa slabă


a subşirurilor lui { }nu la punctele de minim absolut ale lui J. Aceste condiţii sunt

înglobate în următoarele definiţii:

Definiţia 1.1. Vom spune că şirul { }nh E cu 1nh este un şir de direcţii

de convergenţă pentru metoda iterativă (1.6) dacă satisface următoarele condiţii:

(1.7) ( , ) 0, 0,1,2,n nJ u h n

(1.8) lim ( , ) 0 ( ), lim 0n n n n nn n

J u h u J u u

.

Pentru cazul când se renunţă la condiţia de normare a şirului { }nh avem

următorul rezultat simplu:

Lema 1.1. Fie { } , 0, 0,1,2,n nh E h n care satisface condiţiile

(1.7) și (1.8). Dacă şirul este mărginit în normă atunci şirul normat n

n

h

h

este

un şir de direcţii de convergenţă pentru (1.6).

Demonstraţie. Condiţia (1.7) este satisfăcută evident şi de şirul normat.

Dacă , 0,1,2,nh M n avem

1

, ( , )nn n n

n

hJ u J u h

h M

,

de unde rezultă (1.8) pentru şirul normat.

Aşadar, condiţia 1nh se poate înlocui prin , 0,1,2,nh M n cu

păstrarea condiţiilor de direcţii de convergenţă.

Definiţia 1.2. Vom spune că şirul { }n de numere reale pozitive este

un şir de factori de convergenţă pentru iteraţia (1.6) corespunzător direcţiilor de

convergenţă { }nh dacă satisface condiţiile:

(1.9) ( ) ( ), 0,1,2,n n n nJ u h J u n

(1.10) lim ( ) ( ) 0 lim ( , ) 0n n n n n nn n

J u J u h J u h

.

Capitolul 2


BANACH 67

Observaţia 1.2. În cazul în care { }nh nu este normat { }n nh sunt factori

de convergență pentru şirul n

n

h

h

dacă condiţiile (1.9) și

(1.10') lim ( ) ( ) 0 lim , 0nn n n n n

n nn

hJ u J u h J u

h

sunt satisfăcute.

Pe baza acestor definiţii putem acum enunţa teorema de convergenţă.

Teorema 1.1. Fie :J E o funcţională convexă proprie,

semicontinuă inferior, definită pe spaţiul Banach reflexiv E, astfel încât condiţia

(1.2) să fie îndeplinită. Fie { }nh un şir de direcţii de convergenţă pentru şirul

{ }nu dat de (1.6) şi { }n un şir de factori de convergenţă corespunzător lui

{ }nh . Atunci şirul { }nu are puncte de acumulare slabă şi acestea sunt puncte de

minim absolut pentru funcţionala J pe E. În plus

(1.11) lim ( ) min ( )nn v E

J u J v

.

Demonstraţie. În condiţiile teoremei există măcar un punct de minim al

funcţionalei, aşadar inf ( )v E

J v

.

Conform lui (1.9) şirul de numere ( )nJ u este monoton necrescător şi

mărginit inferior. Deci există lim ( )nn

J u

de unde rezultă

lim ( ) ( ) 0n n n nn

J u J u h

.

După (1.10) aceasta implică lim ( , ) 0n nn

J u h

din care rezultă, conform lui (1.8)

existenţa subgradienţilor ( )n nu J u astfel încât

(1.12) lim 0nn

u

.

Din definiţia subgradienţilor avem


(1.13) ( ) ( ) , ,n n nJ v J u v u u v E .

Dar, din cauza ipotezei (1.2) şi a lui (1.9), elementele şirului { }nu sunt în 0( )W u ,

deci acest şir este mărginit şi atunci

lim , 0n nn

v u u

.

În spaţiul reflexiv E, mulţimea de nivel 0( )W u este slab închisă şi

mărginită, deci secvenţial slab compactă. Există aşadar 0( )u W u încât subşirul

{ }nu converge slab la u. Ţinând seama de (1.12), (1.13) şi de semicontinuitatea

slabă a funcţionalei avem

(1.14) ( ) lim ( ) , lim ( ) ( ),n n n nn n

J v J u v u u J u J u v E

.

Deci u este punct de minim absolut al funcţionalei. Făcând în (1.14) v u ,

obţinem (1.11).

Consecinţa 1.1. Dacă în condiţiile teoremei 1.1 J este strict convexă,

atunci şirul { }nu este slab convergent la punctul de minim unic al funcţionalei.

Demonstraţie. Într-adevăr, dacă J este strict convexă există un singur

punct de minim deci un singur punct de acumulare slabă al şirului { }nu .

Deşi convergenţa slabă în unele spaţii este destul de puternică se impune

totuşi cercetarea condiţiilor în care are loc chiar convergenţa tare a şirului de

iteraţii.

Definiţia 1.3. Vom spune că funcţionala : ( , ]J E este uniform

convexă dacă există funcţia scalară continuă, crescătoare, pozitivă pentru

0t , cu (0) 0 şi lim ( )t

t t

şi funcţia sclară definită pe intervalul [0,1]

cu (0) (1) 0, ( ) 0 pentru (0,1) şi cu lim ( ) , 0

,

astfel încât pentru orice ,x y E şi [0,1] să avem

(1.15) ( ) (1 ) ( ) ( (1 ) ) ( )J x J y J x y x y ,

Capitolul 2


BANACH 69

cu convenţia ( ) (vezi definiţia I. 3.1).

Lema 1.2. Dacă funcţionala J este uniform convexă, atunci ea este strict

convexă şi are loc inegalitatea

(1.16) ( ) ( ) ( , ) , ( ),J v h J v J v h h v D J h E .

Demonstraţie. (1.15) arată că J este strict convexă datorită proprietăţilor

lui şi . De asemenea, din (1.15) rezultă

( ( )) ( ) ( )

( ) ( )J y x y J y

J x J y x y

.

Luând ( ),y v D J x y h E şi făcând pe să tindă la zero obţinem

(1.16). Inegalitatea (1.16) nu este în general echivalentă cu (1.15) decât în cazuri

speciale.

Lema 1.3. Fie 1 o funcţie scalară crescătoare continuă astfel ca

(1.17) 1 1( ) ( ) 0, 0, 0ct c t c t .

Dacă funcţionala : ( , ]J E satisface

(1.18) 1( ) ( ) ( , ) , ( ),J v h J v J v h h h v D J h E ,

atunci J este uniform convexă.

Demonstraţie. Fie , ( )x y D J şi [0,1] . Ipoteza implică inegalităţile

( ) ( (1 ) ) ( (1 ) ,(1 )( ))J x J x y J x y x y

2

1(1 ) x y x y

şi

( ) ( (1 ) ) ( (1 ) , ( ))J y J x y J x y y x

2

1x y x y .

Dacă înmulţim prima relaţie cu şi a doua cu 1 şi le adunăm şi ţinând

seama de proprietăţile diferenţialei laterale (teorema I.3.4 (iii)), obţinem


( ) (1 ) ( ) ( (1 ) )J x J y J x y

1(1 ) x y x y .

Astfel are loc (1.15) cu ( ) (1 ) şi 1( ) ( )t t t care satisfac condiţiile

definiţiei 1.3 căci 1 1

( )( ) (1)

tt t

t

. Pentru x sau y în afara domeniului efectiv

(1.15) este imediată cu convenţia făcută.

Consecinţa 1.2. Fie J o funcţională de două ori G-diferenţiabilă în

domeniul său de definiţie ( )D J E convex şi astfel încât

(1.19) 1( , , ) , ( ),J x h h h h x D J h E ,

unde 1 este o funcţie care satisface (1.17). Atunci J este uniform convexă.

Demonstraţie. Funcţionala J este strict convexă conform consecinţei I. 3.7

şi conform lemei precedente este chiar uniform convexă căci formula lui Taylor

ne dă

1

1 1( ) ( ) ( , ) ( , , ) ( , )

2 2J v h J v J v h J v h h h J v h h h ,

cu (0,1) .

Teorema 1.2. Fie :J E o funcţională uniform convexă, proprie,

semicmtinuă inferior pe spaţiul Banach reflexiv E. Atunci J are un punct de

minim absolut unic pe E şi iteraţiile { }nu construite cu (1.6), în care { }nh şi

{ }n sunt direcţii şi respectiv, factori de convergenţă sunt convergente în normă

la punctul de minim u şi avem

(1.20) 1[ ( ) ( )], 0,1,2,n nu u J u J u n

Demonstraţie. Conform lemei 1.2, J este strict convexă şi are loc (1.16).

În particular, pentru un v fixat în care J este subdiferenţiabilă avem

( ) ( ) , ,J v h J v h v h h E ,

Capitolul 2


BANACH 71

unde ( )v J v . De aici

( ) ( )h

J v h J v h vh

şi ţinând seama de proprietăţile lui , rezultă

lim ( )x

J x

.

Sunt astfel satisfăcute condiţiile teoremei 1.1 şi în plus, după consecinţa 1.1,

şirul { }nu este slab convergent la punctul de minim unic u E . Deci

( )

2

nu uu

, pentru n . Folosind semicontinuitatea lui J, uniforma

convexitate şi (1.11) avem

1 1

0 liminf limsup2 2

n nn n

u u u u

1 1 1 1

( ) lim ( ) lim inf ( ) ( ) ( ) 02 2 2 2 2

nn

n n

u uJ u J u J J u J u J u

,

de unde

lim 0nn

u u

.

De aici din cauza continuităţii şi monotoniei lui , urmează convergenţa şirului

{ }nu la u, în normă.

Pentru a dovedi evaluarea erorii (1.20) să aplicăm din nou lema 1.2:

( ) ( ) ( , ) , 0,1,2,n n nJ u J u J u u u u u n

u fiind punctul de minim, 0 ( )J u şi conform egalităţii (I. 3.9) avem

( , ) 0nJ u u u , de unde rezultă (1.20).

Consecinţa 1.3. Dacă J este de 2 ori G-diferenţiabilă astfel că G-

diferenţiala a doua satisface (1.19) atunci şirul iteraţiilor { }nu dat de (1.6) cu


{ }nh şi { }n satisfăcând condiţiile definiţiilor 1.1 şi 1.2 este convergent în

normă la punctul de minim unic al funcţionalei.

În particular, dacă J are hessian pozitiv definit adică

2

( , , ) , ( ) , ( ),J v h h h H v h m h v D J h E ,

are loc convergenţa tare a şirului { }nu la soluţia u şi evaluarea erorii:

2 2

[ ( ) ( )]n nu u J u J um

.

Capitolul 2


BANACH 73

1.2. ALEGEREA DIRECŢIILOR DE CONVERGENŢĂ

Fie E un spaţiu Banach reflexiv şi :J E o funcţională convexă

proprie, semicontinuă inferior care satisface condiţia (1.2). Conform teoremei

1.1 pentru convergenţa slabă a subşirurilor de iteraţii { }nu date de (1.6) la

punctele de minim ale funcţionalei este suficient să alegem şirul { }nh să fie un

şir de direcţii de convergenţă şi şirul numeric { }n să fie un şir de factori de

convergenţă corespunzător. Pentru fiecare alegere particulară a acestor şiruri se

obţine câte o metodă iterativă astfel că acest mod de abordare permite obţinerea

unor familii de iteraţii a căror convergenţă este demonstrată în teoremele 1.1 sau

1.2 odată pentru totdeauna. Ne vom ocupa în cele ce urmează mai întâi de

alegerea direcţiilor { }nh .

Definiţia 1.4. Vom spune că h E este o direcţie de descreştere a

funcţionalei J în punctul u E dacă în acest punct avem

(1.22) ( , ) 0J u h .

Conform definiţiei diferenţialei laterale pentru orice 0 ( , )J u h există

( ) 0 încât

[ ( ) ( )]

0 ( ) ( , ) 0J u h J u

J u h

,

adică ( ) ( )J u h J u , pentru 0 ( ) . Deci într-adevăr, pe direcţia h

funcţionala poate fi micşorată pornind din u, ceea ce justifică denumirea. În

cazul când ( , ) 0J u h avem conform lui (I. 3.5),

( ) ( ) ( , ) 0, 0J u h J u J u h ,

adică funcţionala nu mai poate fi micşorată pe această direcţie (admite un minim

în u pe direcţia h).


Lema 1.4. h E este direcţie de descreştere pentru J în punctul u dacă şi

numai dacă există 0 încât

(1 .23) , , ( )h u u u J u

.

Demonstraţie. Conform consecinţei I. 3.4 avem pentru direcţia de

descreştere h E ,

, ( , )

0h u J u h

u

,

unde ( )

supu J u

u

. Reciproc, dacă presupunem că avem ,h u u

,

( )u J u , mai întâi rezultă că 0 ( )J u . Cum subdiferenţiala este o mulţime

închisă în norma lui E avem atunci

(1.24) ( )

inf 0u J u

u

.

Ipoteza (1.23) implică inegalitatea , , ( )h u u J u , de unde trecând

la supremum, obţinem

( , ) 0J u h .

Să revenim acum la problema alegerii direcţiilor de convergenţă { }nh . În

definiţia 1.1 condiţia (1.7) poate fi înlocuită cu inegalitatea strictă (1.22) fără a

pierde generalitatea căci cazul limită ( , ) 0n nJ u h ar conduce la imposibilitatea

micşorării valorii funcţionalei şi deci la repetarea iteraţiei. Aşadar direcţiile de

convergenţă { }nh trebuie căutate printre direcţiile de descreştere ale funcţionalei

în nu . Teoremele care urmează precizează condiţii suficiente pentru care

direcţiile de descreştere satisfac şi (1.8).

Teorema 1.3. Dacă pentru şirul { }nh E , cu 1nh , există 0 încât

(1.25) , , ( ), 0,1,2,n n n n nh u u u J u n

,

atunci { }nh este un şir de direcţii de convergenţă pentru procesul iterativ (1.6).

Capitolul 2


BANACH 75

Demonstraţie. Conform lemei 1.4, nh este direcţie de descreştere pentru J

în nu , adică ( , ) 0, 0,1,2,n nJ u h n . Deoarece

( )

( , ) sup ,n n

n n n nv J u

J u h h v

,

pentru fiecare n şi pentru 0 ( , )n n nJ u h , există un subgradient ( )n nu J u

în aşa fel încât

, ( , ) 2 ( , )n n n n n n n nu h u J u h J u h

Deci există ( )n nu J u încât

2

( , )n n nu J u h

,

ceea ce implică satisfacerea condiţiei (1.8). Aşadar { }nh sunt direcţii de

convergenţă pentru (1.6).

Observaţia 1.3. Deoarece în ipoteza (1.25) avem , ,n n n nh u h u ,

din definiţia normei în E obţinem cu necesitate

(1.26) 0 1 .

Condiţia (1.25) este destul de restrictivă căci se cere să fie satisfăcută

pentru orice subgradient al funcţionalei şi la fiecare iteraţie nu . O condiţie mai

puţin restrictivă este dată mai jos.

Teorema 1.4. Dacă , 0,1,2,nu n , nu este punct de minim absolut al

funcţionalei J, atunci orice şir { } , 1n nh E h , satisfăcând inegalitatea

(1.27) ( )

( , ) inf , 0,1,2,n n

n n nv J u

J u h v n

pentru un 0 independent de n este şir de direcţii de convergenţă pentru

(1.6). În plus, condiţia (1.27) are loc dacă (1.25) este îndeplinită.

Demonstraţie. Deoarece nu nu este punct de minim pentru nici un n, 0

nu este subgradient în nu şi atunci


( )

inf 0, 0,1,2,n n

nv J u

v n

.

Aşadar nh este direcţie de descreştere pentru J în nu . Pe de altă parte pentru

fiecare n, oricare ar fi 0 există ( )n nu J u încât

(1 )n nu

.

Deci, pentru fiecare n,

( ), ( , )1

n n n n nu J u J u h u

,

de unde rezultă implicaţia (1.8), adică { }nh sunt direcţii de convergenţă pentru

iteraţiile (1.6).

În sfârşit, dacă este satisfăcută condiţia (1.25) avem

, , ( )n n n n nh u u J u ,

de unde rezultă (1.27), pentru orice n.

Observaţia 1.4. Avem inegalităţile:

( , ) , , ( )n n n n n n nJ u h h u u u J u

,

de unde ( , ) , 0,1,2,n n nJ u h n , adică şi pentru condiţia (1.27)

satisface inegalitatea (1.26).

Teoremele demonstrate sunt generale pentru spaţii Banach reflexive. Să

cercetăm acum câteva alegeri particulare pentru direcţiile nh .

1. Dacă funcţionala J este G-diferenţiabilă în 0( )W u , conform teoremei

I. 3.6, există un singur subgradient în fiecare iteraţie nu şi anume grad ( )nJ u . În

acest caz condiţiile (1.25) şi (1.27) se confundă şi capătă forma:

(1.28) 0, ,grad ( ) grad ( ) , 0,1,2,n n nh J u J u n

Capitolul 2


BANACH 77

O alegere particulară a lui nh care satisface (1.28) se poate face astfel. Fie

ny subgradient al normei spaţiului dual în punctul grad ( )nJ u . Identificând E

cu E şi ţinând seama de (I. 3.21) avem

1, ,grad ( ) grad ( )n n n ny y J u J u

.

Luând , 0,1,2,n nh y n , (1.28) este satisfăcută cu 1 . După cum va

rezulta mai târziu, valoarea maximă a lui (egală cu 1 după (1.26)) este optimă

într-un anumit sens pentru rapiditatea de convergenţă a procedeelor 1.6.

2. Să considerăm cazul în care E este un spaţiu Hilbert care s-a

identificat cu dualul său cu ajutorul reprezentării funcţionalelor liniare şi

continue prin produs scalar. În acest caz subgradienţii sunt elemente din E şi

condiţia (1.25) revine la

(1.29) cos( , ) , ( ), 0,1,2,n n n nh u u J u n

Deci putem lua pentru fiecare , ( )n n nn y v J u , astfel ca unghiul dintre acesta

şi oricare alt subgradient să nu fie egal cu 2 şi atunci

nn

n

yh

y .

Condiţia (1.29) este satisfăcută dacă unghiurile succesive între ny şi

subgradienţii în nu pentru 0,1,2,n nu au 2 ca punct limită. Aceasta ne dă

o libertate foarte mare de alegere ceea ce este important mai ales în situaţia în

care J este G-diferenţiabilă. În acest caz alegerea corespunzătoare lui 1 ,

adică pentru unghiul , 0n nh u este

(1.30) grad ( )

grad ( )

nn

n

J uh

J u .


Metodele iterative de forma (1.6) cu nh de această formă poartă numele de

metodele gradientului şi sunt cunoscute încă de la Cauchy. Aceste metode

corespund valorii maxime a lui , ceea ce implică cea mai bună convergenţă

liniară pentru (1.6). Pe de altă parte, direcţia opusă gradientului în nu este cea

pentru care se realizează cea mai mare descreştere a funcţionalei J pornind din

punctul nu . Într-adevăr, pentru orice direcţie de descreştere nh cu 1nh , avem

( , ) (grad ( ), ) grad ( )n n n n nJ u h J u h J u ,

în care egalitatea are loc pentru nh de forma (1.30). Aşadar metodele

gradientului sunt optime din acest punct de vedere. În practică însă sunt rare

cazurile în care gradientul se poate calcula exact şi chiar dacă aceasta este

posibil de multe ori volumul mare de calcule necesare pentru obţinerea lui

anulează avantajele teoretice de mai sus. Datorită însă lui (1.29) avem

posibilitatea alegerii unei aproximări chiar grosolane a gradientului care se poate

obţine cu un volum mic de calcule condiţiile de direcţii de convergenţă

rămânând satisfăcute.

3. Fie J diferenţiabilă Gâteaux pe spaţiul Banach reflexiv E, sau măcar

în 0( )W u , şi fie : , 0,1,2,nD E E n , un şir de operatori liniari mărginiţi

ce satisfac condiţiile:

(1.31) 2

, , , 0,1,2,nD v v m v v E n

(1.32) , 0,1,2,nD d n

cu m şi d constante pozitive independente de n.

În acest caz o alegere posibilă a direcţiilor de convergenţă este

(1.33) , grad ( ), 0,1,2,nn n n n

n

zh z D J u n

z

Într-adevăr, cu această alegere,

Capitolul 2


BANACH 79

21,grad ( ) grad ( ),grad ( ) grad ( )n n n n n n

n n

mh J u D J u J u J u

z z

şi cum grad ( )n nz d J u

, condiţia (1.28) este satisfăcută cu 0m

d .

4. Fie J diferenţiabilă Gâteux pe 0( )W u şi { }ng un şir de direcţii de

convergenţă. Putem atunci obţine alte direcţii de convergenţă în următorul mod.

Vom considera { }nh definit prin recurenţa

(1.34) 1 1 0 0, 0,1, ,n n n nh g h n h g .

Alegem pe n astfel încât şirul { }nh să fie mărginit şi pe { }n din (1.6) în

aşa fel ca

(1.35) 1, grad ( ) 0, 0,1,2,n n nh J u n

Atunci avem

( , ) ,grad ( ) ,grad ( ) ( , )n n n n n n n nJ u h h J u g J u J u g ,

ceea ce ne asigură satisfacerea condiţiilor (1.7) şi (1.8) pentru nh dacă ele sunt

verificate de ng . În acest mod, dacă ţinem seama de lema 1.1, { }nh sunt direcţii

de convergență nenormate (adică n

n

h

h sunt direcţii de convergență în sensul

definiţiei 1.1). Alegerea factorilor n este făcută pentru metodele din această

clasă în aşa mod încât să se asigure o convergenţă mai rapidă a iteraţiilor. De

altfel aceasta este şi raţiunea pentru care se consideră alegeri aşa de sofisticate

pentru nh . În majoritatea metodelor din această clasă condiţia (1.35) este

satisfăcută cu semnul de egalitate. Metodele de acest tip vor fi studiate în §3.

Uneori se poate renunţa chiar şi la condiţia de mărginire a şirului { }nh fără a

pierde proprietăţile de convergenţă ale iteraţiilor.


1.3. ALEGEREA FACTORILOR DE CONVERGENŢĂ

După ce am văzut cum se pot alege elementele nh în aşa fel încât să fie

satisfăcute condiţiile cuprinse în definiţia 1.1, rămâne să găsim alegeri ale

factorilor n conform definiţiei 1.2 pentru a avea asigurate condiţiile teoremelor

de convergenţă.

Vom face în acest scop o ipoteză suplimentară faţă de cele din secţiunea

precedentă. Fie din nou E un spaţiu reflexiv şi :J E o funcţională convexă

proprie, semicontinuă inferior care satisface condiţia (1.2). Conform teoremei

I. 3.7, pentru fiecare element v din domeniul efectiv ( )D J al funcţionalei şi

pentru fiecare , ( , )h E J v h h descreşte monoton când descreşte cu

valori pozitive şi

(1.36) 0

lim ( , ) ( , )J v h h J v h

.

Vom face în plus ipoteza că în (1.36) convergenţa este uniformă pentru orice

0( )v W u şi orice h E cu 1h , adică

(1.37) 0, ( ) 0, 0 ( ) 0 ( , ) ( , )J v h h J v h .

În secţiunea 3.6 din capitolul I am discutat posibilitatea unei astfel de

ipoteze. Astfel am văzut că pentru ca (1.37) să fie satisfăcută este suficient ca

funcţionala J să satisfacă condiţia

(1.38) 10 ( ) (1 ) ( ) ( (1 ) ) ( ) ( )tJ x t J y J tx t y t x y x y ,

pentru orice 0, ( )x y W u şi orice [0,1]t , unde 1 este o funcţie scalară

continuă, nedescrescătoare cu 1(0) 0 şi o funcţie scalară nenegativă pe

[0,1], cu (0) (1) 0 şi 0

( )lim , 0t

t

t

.

Capitolul 2


BANACH 81

În cazul în care J este G-diferenţiabilă în 0( )W u condiţia (1.37) este satisfăcută

dacă are loc uniforma continuitate a gradientului în 0( )W u , ipoteză echivalentă

cu uniforma diferenţiabilitate în 0( )W u a funcţionalei.

În cele ce urmează va juca un rol important funcţia ( ) definită în (1.37).

Definiţia 1.5. Vom numi funcţie pondere orice funcţie scalară astfel

încât ( ) 0t pentru 0t şi

( ) 0 0t t pentru 0t .

Este uşor de văzut că luând

(1.39) ( ) inf{ 0, ( , ) ( , )J u h h J u h ,

0( ), , 1}u u h E h ,

este satisfăcută condiţia (1.37) şi în acelaşi timp ( ) este o funcţie pondere. De

aici înainte vom presupune că în ipoteza (1.37) ( ) este o funcţie pondere.

Observaţia 1.5. Dacă ( )t este o funcţie pondere, funcţia ( )t t este tot o

funcţie pondere. Într-adevăr, dacă nt este un şir de numere pozitive pentru care

( ) 0n nt t şi presupunem prin absurd că 0nt m , ar rezulta ( ) 0nt , de

unde 0nt , ceea ce contrazice presupunerea făcută. Aşadar ( ) 0n nt t

0nt , adică ( )t t este funcţie pondere.

Cu aceste preliminarii să trecem acum la rezultatul principal.

Teorema 1.5. În ipotezele indicate mai sus, dacă { }nh este un şir de

direcţii de convergenţă pentru iteraţia (1.6), au loc următoarele trei criterii

pentru factorii de convergenţă corespunzători:

(i) orice şir de numere pozitive { }n care satisface inegalitatea

(1.40) ( ) ( ) ( ( , )), 0,1,2,n n n n n nJ u J u h J u h n ,

unde este o funcţie pondere este un şir de factori de convergenţă;


(ii) dacă { }n este un şir de factori de convergenţă şi dacă pentru şirul de

numere pozitive { }n , există 0 0c încât să aibă loc

(1.41) 0( ) ( ) [ ( ) ( )]n n n n n n n nJ u J u h c J u J u h ,

oricare ar fi 0,1,2,n , atunci şi { }n este un şir de factori de convergenţă;

(iii) orice şir { }n de numere pozitive care satisfac

(1.42) ( ( , )) ( ( , )), 0,1,2,n n n n nJ u h cJ u h n ,

unde 0 1,c este o funcţie pondere şi este funcţia pondere din (1.39), este

un şir de factori de convergenţă.

Demonstraţie. Condiţiile din definiţia 1.2 sunt imediat satisfăcute dacă

are loc inegalitatea (1.40) căci ( , ) 0n nJ u h şi este o funcţie pondere. De

asemenea, dacă { }n verifică cele două condiţii (1.9) şi (1.10), inegalitatea

(1.41) asigură satisfacerea lor şi de către şirul { }n .

Să demonstrăm acum criteriul (iii). Conform proprietăţilor diferenţialei

laterale putem scrie succesiv

( ) ( ) ( , ) ( , )n n n n n n n n n n n n n nJ u J u h J u h h J u h h .

Pe de altă parte, ipoteza (1.37) face ca din a doua parte a inegalităţii (1.42) să

rezulte

( , ) ( , ) ( , )n n n n n n n nJ u h h J u h cJ u h .

Atunci ţinând seama de prima inegalitate (1.42) putem scrie

( ) ( ) (1 ) ( , )

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

n n n n n n n

n n n n

J u J u h c J u h

c J u h J u h

Funcţia ( ) (1 ) ( )t c t t este o funcţie pondere după observaţia 1.5 şi atunci

{ }n este un şir de factori de convergenţă conform criteriului (i).

Consecinţa 1.4. ( ( , ))n n n nc cJ u h sunt factori de convergenţă dacă

0 1nc şi 0 1c , conform criteriului (iii).

Capitolul 2


BANACH 83

Să cercetăm acum câteva cazuri particulare.

1. Să presupunem că diferenţialele laterale ale funcţionalei J satisfac

condiţia

00 ( , ) ( , ) , ( ), , 1, 0J v h h J v h L v W u h E h ,

Această condiţie este îndeplinită conform teoremei I. 3.10 dacă funcţionala

satisface condiţia

2

0

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

(1 ) , , ( ), [0,1].

J x J y J x y

L x y x y W u

În acest caz putem lua ( )L

care este evident o funcţie pondere şi atunci,

după consecinţa 1.4,

( , )n n n n

cc J u h

L , cu 0 1, 0 1nc c ,

sunt factori de convergenţă.

În particular, dacă J este G-diferenţiabilă condiţia de mai sus este o

condiţie Lipschitz pentru gradient de forma

0grad ( ) grad ( ) , ( ), , 1J v h J v L v W u h E h ,

şi factorii de convergenţă se scriu:

2

0( , , ) , ( ),J v h h M h v W u h E ,

2. În ipoteza şi mai puternică că funcţionala este de două ori G-diferenţiabilă cu

2

0( , , ) , ( ),J v h h M h v W u h E ,

avem, după formula lui Taylor,

2

( ) ( ) ( , ) ( , , )2

n n n n n n n n n nJ u J u h J u h J u h h h


2

( , ) , 0, 0,1,2,2

n nJ u h M n

în care sunt iteraţiile şi nh direcţii de convergenţă date. Pentru

( , )n n n

cJ u h

M , cu 0 2c ,

Obţinem

2

22( ) ( ) [ ( , )]

2n n n n n n

c cJ u J u h J u h

M

,

adică n sunt factori de convergenţă conform criteriului (i) cu funcţia pondere

2

22( )

2

c ct t

M

.

Aceste două cazuri particulare nu sunt însă aplicabile decât în ipoteze mai

restrictive decât cele făcute până aici şi în plus presupunem că sunt cunoscute

evaluări ale constantei Lipschitz L sau a marginii M a diferenţialei a doua. În

secţiunile următoare vom indica alte procedee de alegere a factorilor de

convergenţă care au loc în condiţiile generale în care ne-am plasat şi sunt în

acelaşi timp adecvate aplicaţiilor practice cu calculatorul.

1.4. METODA LUI GOLDSTEIN GENERALIZATĂ

Fie { }nh un şir de direcţii de convergenţă pentru (1.6).

Teorema 1.6. Orice şir de numere pozitive { }n care satisface

(1.43) ( ) ( )

( , ) (1 ) ( , ), 0,1,2,n n n nn n n n

n

J u J u hcJ u h c J u h n

cu (0,1 2)c este un şir de factori de convergenţă corespunzător şirului { }nh .

Demonstraţie. Vom arăta că { }n satisface inegalitatea

Capitolul 2


BANACH 85

(1.44) ( , ) , 0,1,2,n n ncJ u h n .

Presupunem că există n pentru care ( ( , ))n n ncJ u h , ceea ce conform

ipotezei (1.37) ar implica

0 ( ) ( , ) ( , )n n n n n n nJ u h J u h cJ u h ,

de unde

( ) ( ) ( , )n n n n n n n n nJ u J u h J u h h

( , ) (1 ) ( , )n n n n n n n nJ u h h c J u h ,

contrar ipotezei (1.43). Aşadar (1.44) are loc pentru orice n şi atunci folosind

ipoteza avem

( ) ( ) ( , ) ( , ) ( ( , ))n n n n n n n n n n nJ u J u h c J u h cJ u h cJ u h ,

de unde urmează că n sunt factori de convergenţă conform criteriului (i) din

teorema 1.5 cu ( ) ( )t ct ct .

Posibilitatea construirii unui şir numeric { }n care să satisfacă dubla

inegalitate (1.43) este asigurată de următoarea teoremă.

Teorema 1.7. În ipotezele date oricare ar fi 0( )v W u şi h o direcţie de

descreştere în v pentru funcţionala J şi pentru orice 0 1 2c , există 0 în

aşa fel încât să fie satisfăcută inegalitatea

(1.45) ( ) ( )

( , ) (1 ) ( , )J v J v h

cJ v h c J v h

.

Demonstraţie. Deoarece 0( )W u este mărginită, există 0 0 încât pentru

orice 0 să avem

( ) ( ) 0J v J v h

şi deci, deoarece h este direcţie de descreştere, există 0 suficient de mare,

pentru care

( ) ( ) (1 ) ( , )J v J v h c J v h .


Pe de altă parte, din definiţia diferenţialei direcţionale laterale, există 1 0

astfel ca pentru 10 să avem

( ) ( )

0 ( , ) (1 ) ( , )J v h J v

J v h c J v h

,

adică

( ) ( ) ( , )J v J v h cJ v h .

Conform teoremei I. 3.4, funcţia f definită prin

( ) ( )

0 ( )J v J v h

f

este monotonă şi deci există 0 pentru care ambele inegalităţi de mai sus sunt

satisfăcute simultan.

Demonstraţia de mai sus sugerează şi algoritmul de determinare a unui

0 care să satisfacă inegalitatea (1.45). Ideea acestui algoritm este simplă. Se

determină prin încercări succesive discrete un interval iniţial 0 0[ , ]a b pe semiaxa

reală pozitivă astfel ca pentru a să fie satisfăcută prima inegalitate şi pentru

0b să fie satisfăcută a doua inegalitate din (1.45). Apoi se rafinează

intervalul prin înjumătăţire până când se ajunge la un punct care satisface

ambele inegalităţi simultan. Conform teoremei precedente un astfel de punct

există şi deci algoritmul are sens. Să mai observăm că prin satisfacerea cu

semnul egal a primei inegalităţi din (1.47) este verificată automat şi cea de-a

doua datorită faptului că (0,1 2)c . O afirmaţie similară are loc şi pentru a

doua inegalitate căci stricta inegalitate în (1.45) nu este esenţială (prin

modificarea lui c se poate face să avem şi posibilitate de egal în a doua

inegalitate rămânând prima strictă). Iată algoritmul:

Date: , , , 0v c h , subrutine pentru J şi J .

Pas 1. Pune .

Capitolul 2


BANACH 87

Pas 2. Calculează 1( ) ( ( ) ( )) ( , )f J v J v h cJ v h .

Pas 3. Dacă 1( ) 0f , pune şi stop; dacă 1( ) 0f , pune

şi treci la Pasul 2; dacă 1( ) 0f , treci la Pasul 4.

Pas 4. Calculează 2( ) ( ( ) ( )) (1 ) ( , )f J v J v h c J v h .

Pas 5. Dacă 2( ) 0f , pune şi stop; în caz contrar pune a ,

b şi treci la Pasul 6.

Pas 6. Pune ( ) 2a b .

Pas 7. Calculează 1( )f şi 2 ( )f .

Pas 8. Dacă 1( ) 0f şi 2( ) 0f pune şi stop; în caz contrar treci

la Pasul 9.

Pas 9. Dacă 1( ) 0f , pune b şi treci la Pasul 6; în caz contrar pune

a şi treci la Pasul 6.

Conform teoremei 1.7 algoritmul are stop sigur după un număr finit de

paşi. Acest număr de paşi poate fi foarte mare dacă c este prea apropiat de 1 2

căci în acest caz intervalul [ ( , ), (1 ) ( , )]cJ v h c J v h este prea îngust şi

rafinarea făcută la paşii 6 – 9 necesită un volum mare de calcule.

Pentru programarea metodei lui Goldstein algoritmul de mai sus este o

subrutină la care se apelează la fiecare iteraţie. Asupra criteriilor de stop se pot

face aceleaşi consideraţii ca în secţiunea precedentă. Printr-o alegere judicioasă

a constantei c metoda este destul de eficientă cu condiţia să poată fi calculate

diferenţialele direcţionale cu precizie.


1.5. METODA LUI ARMIJO GENERALIZATĂ

Ne situăm în aceleaşi ipoteze ca şi înainte şi presupunem de asemenea că

posedăm o subrutină de calcul a diferenţialei direcţionale cu precizie oricât de

bună. Un rezultat asemănător cu cel din teorema 1.6 este următorul.

Teorema 1.8. Fie { }nh un şir de direcţii de convergenţă pentru iteraţia

(1.6) şi fie 0 1, 2c constante. Atunci orice şir de numere pozitive { }n ,

care satisface simultan inegalităţile

(1.46)

( ) ( )( , ),

( ) ( )( , ),

n n n nn n

n

n n n nn n

n

J u J u hcJ u h

J u J u hcJ u h

pentru 0,1,2,n , este un şir de factori de convergenţă pentru direcţiile date.

Demonstraţie. Vom dovedi mai întâi inegalitatea:

(1.47) ( (1 ) ( , )), 0,1,2,n n nc J u h n ,

prin reducerea la absurd. Presupunem că există n încât

( (1 ) ( , ))n n nc J u h .

Conform ipotezei (1.37) aceasta implică inegalitatea:

(1.48) ( , ) ( , ) (1 ) ( , )n n n n n n n nJ u h h J u h c J u h .

Pe de altă parte avem

( ) ( ) ( , ) ( , )n n n n n n n n n n n n n nJ u J u h J u h h J u h h ,

care, datorită lui (1.48), conduce la contrazicerea celei de-a doua inegalităţi

(1.46). Aşadar are loc (1.47) pentru orice 0,1,2,n şi atunci conform lui

(1.46) putem scrie:

( ) ( ) ( , )n n n n n n nJ u J u h cJ u h

( , ) ( (1 ) ( , )) ( ( , ))n n n n n n

cJ u h c J u h J u h

,

Capitolul 2


BANACH 89

unde ( ) (1 ) ((1 ) )(1 )

ct c t c t

c

este o funcţie pondere. Criteriul (i) din

teorema 1.5 ne asigură atunci că { }n sunt factori de convergenţă.

În practică se foloseşte următoarea subrutină simplă de calcul al lui n la

fiecare iteraţie cu ajutorul teoremei.

Pas 1. Pune 0 .

Pas 2. Calculează 1( ) ( ( ) ( )) ( , )n n n n nf J u J u h cJ u h .

Pas 3. Dacă 1( ) 0f , pune n ; în caz contrar pune

şi treci la

Pasul 2.

Teorema 1.9. Oricare ar fi 0 0 , algoritmul de mai sus furnizează

factorul n într-un număr finit de paşi pentru fiecare iteraţie şi şirul { }n astfel

obţinut este un şir de factori de convergenţă pentru iteraţiile (1.6).

Demonstraţie. Dacă pentru un 1 0, ( ) 0n f , conform algoritmului luăm

0n şi avem

(1.49) 0( ) ( ) ( , )n n n n n nJ u J u h c J u h .

Dacă însă 1 0( ) 0f , conform algoritmului se construieşte succesiv şirul

0 , 1,2,j j pentru care se verifică îndeplinirea primei inegalităţi (1.46).

După definiţia diferenţialei direcţionale va exista 0j de la care încolo să avem

0

0

0

0

( ) ( ( ) )( , ) (1 ) ( , )

j

n n nn n n nj

J u J u hJ u h c J u h

,

adică prima inegalitate (1.46) satisfăcută pentru 0

0

j

n . Aşadar n este

obţinut după un număr finit de paşi. Deoarece 0j este primul indice pentru care


0

0

j

n satisface prima inegalitate (1.46), va rezulta că pentru 0 1j j , cu

alte cuvinte pentru n este satisfăcută inegalitatea cealaltă din (1.46). Deci în

acest caz ipotezele teoremei 1.8 sunt verificate şi conform demonstraţiei avem

(1.50) ( ) ( ) ( ( , ))n n n n n nJ u J u h J u h ,

unde ( )t are valoarea precizată mai sus.

Introducând funcţia

1 0( ) min{ , ( )}t c t t ,

care este o funcţie pondere şi combinând (1.49) şi (1.50) obţinem

1( ) ( ) ( ( , )), 0,1,2,n n n n n nJ u J u h J u h n ,

adică { }n sunt factori de convergenţă.

Simplitatea algoritmului de mai sus îl recomandă ca preferabil

algoritmului lui Goldstein generalizat dar necesitatea cunoaşterii diferenţialei cu

precizie rămâne şi aici valabilă.

Capitolul 2


BANACH 91

§ 2. METODELE GRADIENŢILOR CONJUGAŢI

2.1. METODA GRADIENŢILOR CONJUGAŢI PENTRU FUNCŢIONALE PĂTRATICE

În tot acest paragraf E este un spaţiu Hilbert separabil cu produsul scalar

(.,.) . Fie ( , )H L E F un operator autoadjunct care satisface inegalitatea dublă:

(2.1) 2 2

0 ( , ) ,m v Hv v M v v E .

Fie de asemenea f E şi . Considerăm funcţionala :J E definită prin

(2.2) 1

( ) ( , ) ( , )2

J v Hv v f v ,

care este de două ori G-derivabilă cu gard ( )J v Hv f şi hessianul

( )H v f . J este uniform convexă şi admite un punct de minim unic u E care

satisface ecuaţia 0Hu f (vezi exemplul 1 din secţiunea I 4.4). Pentru a

introduce metodele iterative din titlu să dăm următoarea definiţie.

Definiţia 2.1. Şirul { }, 1,2,np n , de elemente din spaţiul Hilbert E

este un şir de direcţii H-conjugate (pe scurt „direcţii conjugate", dacă nu e

posibilă confuzia) dacă satisface egalităţile

(2.3) ( , ) ( , ), ,n m nm m mp Hp p Hp n m ,

unde nm este simbolul lui Kronecker ( 0nm dacă n m şi 1, ,nn n m ).

Dacă în plus,

(2.4) { }nsp p E ,


unde prin { }nsp p am notat închiderea în topologia lui E a spaţiului liniar generat

de şirul { }np , atunci spunem că { }np este un sistem complet de direcţii

H-conjugate în E.

Dacă dispunem de un sistem complet de direcţii H-conjugate putem defini

o metodă iterativă simplă de aproximare a punctului de minim u al funcţionalei.

Teorema 2.1. Fie { }np un sistem complet de direcţii H-conjugate în E şi

0u E oarecare. Atunci şirul { }nu construit cu recurenţa

(2 .5) 11 1

1 1

(grad ( ), )

( , )

n nn n n

n n

J u pu u p

p Hp

converge la u, când n .

Demonstraţie. Cu ajutorul operatorului H, putem introduce în spaţiul E un

nou produs scalar ((.,.)) dat de

(( , )) ( , ), ,v w v Hw v w E .

Datorită proprietăţilor (2.1) ale lui H, topologia indusă de acest produs scalar

este echivalentă cu cea existentă în spaţiu. Relativ la acest produs scalar şirul

{ }np este un sistem ortogonal complet datorită relaţiilor (2.3) şi (2.4).

Normalizând elementele şirului obţinem şirul { }nq unde

1 2

( ), 1,2,

( , )

nn

n n

pq n

p Hp ,

care este un sistem ortonormal complet în E. Fie 0u E oarecare; 0u u

1

0grad ( )H J u are dezvoltarea Fourier în raport cu acest sistem ortonormal

de forma

0

1

k k

k

u u c q

,

unde coeficienţii Fourier sunt

Capitolul 2


BANACH 93

1

0 01 2

1(( , )) ( grad ( ), )

( , )k k k

k k

c u u q H J u Hpp Hp

01 2

1(grad ( ), ), 1,2,

( , )k

k k

J u p kp Hp

.

Deci

(2.6) 00

1

(grad ( ), )

( , )

kk

k k k

J u pu u p

p Hp

.

Notând cu nu suma parţială avem

0 00 1

1

(grad ( ), ) (grad ( ), )

( , ) ( , )

nk n

k n n

k k k n n

J u p J u pu u p u p

p Hp p Hp

.

Din cauza condiţiei de H-conjugare, putem uşor dovedi că

1 1 0 1(grad ( ), ) ( , ) ( , )n n n n nJ u p Hu f p Hu f p .

adică 1nu se obţine cu recurenţa (2.5). Datorită convergenţei seriei (2.6) rezultă

atunci că nu u pentru n .

Observaţia 2.1. Dacă { }np este un şir de direcţii H-conjugate fără a fi

complet în E, concluzia teoremei se păstrează cu condiţia suplimentară privind

alegerea iteraţiei iniţiale:

(2.7) 0 { }nu u sp p .

Metodele iterative (2.5) se numesc metode cu direcţii conjugate. Pentru

construirea unui şir de direcţii H-conjugate se poate aplica un procedeu de

ortogonalizare a unui şir oarecare de elemente liniar independente. Un algoritm

practic care de altfel conduce la metoda gradienţilor conjugaţi este dat de

următoarea teoremă, datorată lui Hestenes.

Teorema 3.2. Fie 0 0g un element fixat din E. Şirurile { }ng şi { }nh ,

0,1,2,n se construiesc succesiv cu ajutorul formulelor de recurenţă:


(2.8) 1 1 1 0 0, , , 0,1,2,n n n n n n n ng g Hh h g h h g n

cu

(2.9) 1( , ) ( , ), , 0,1,2,

( , ) ( , )

n n n nn n

n n n n

g g Hh gn

g Hh Hh h

.

În aceste condiţii { }ng este un şir ortogonal, iar { }nh un şir de direcţii

H-conjugate.

Demonstraţie. Să observăm mai întâi că n şi n sunt luaţi astfel încât să

avem

(2.10) 1 1( , ) 0, ( , ) 0, 0,1,2,n n n ng g h Hh n .

Vom demonstra prin inducţie, simultan egalităţile:

(2.11) 2

( , ) , ( , ) ( , )i j ij j i j ij j jg g g h Hh h Hh .

După (2.10), avem mai întâi 1 0( , ) 0g g şi 1 0( , ) 0Hh h . Dacă presupunem

(2.11) adevărat pentru 0 ,i j n , urmează pentru 1 1i n ,

1( , ) ( , ) ( , )n i n n n i n n ig g g Hh g Hh g

1 1( , ) 0n n i i iHh h h ,

iar pentru 0i ,

1 0 0 0 0( , ) ( , ) ( , ) ( , ) 0n n n n n n n ng g g Hh g Hh g Hh h .

Apoi pentru 0 1i n , dacă 0i , putem scrie succesiv:

1 1 1( , ) ( , ) ( , )n i n n n i n ih Hh g h Hh g Hh

1 1

1, ( ) 0n i i

i

g g g

.

Dacă pentru un indice i, 0i , urmează 0ig şi atunci 0ih , de unde rezultă

toţi ng şi nh egali cu zero pentru n i . În acest caz egalităţile (2.11) au de

asemenea loc şi deci teorema este complet demonstrată.

Consecinţa 2.1. În condiţiile teoremei 2.2 au loc egalităţile:

Capitolul 2


BANACH 95

(2.12) ( , ) 0, , , 0k nh g k n k n ;

(2.13) ( , )

( , )

n nn

n n

h g

h Hh pentru toți 0n pentru care 0, 0n ng h ;

(2.14) 1 1 1( , ) ( , )

( , ) ( , )

n n n n nn

n n n n

Hg h g g g

Hh h g g

2

1

2

n

n

g

g

când 0, 0n ng h .

Demonstraţie. (2.12) se arată prin inducţie după n. Pentru 1n avem

0 1 0 1( , ) ( , ) 0h g g g , după (2.10). Presupunem că are loc egalitatea

(2.15) 1( , ) 0n nh g .

Atunci

1 1 1( , ) ( , ) ( , ) ( , )n n n n n n n n n n n n nh g h g Hh g h g h Hh

1 1( , ) ( , ) ( , ) ( , ) 0n n n n n n n n n n n ng g g h Hh g g g Hh .

Deci relaţia (2.15) are loc pentru orice 1n . Atunci pentru orice k și

1n cu 0 1k n , avem

1 1 1 1 1( , ) ( , ) ( , ) ( , ) 0k n k n n n k n k kh g h g Hh h g h g ,

din cauza lui (2.15).

Relaţia (2.13) rezultă imediat pe baza egalităţii (2.15):

1 1

1

( , ) ( , ) ( , )

( , ) ( , ) ( , )

n n n n n n n nn

n n n n n n n

g g h h g h g

g Hh h Hh Hh h

.

În sfârşit, (2.14) se dovedeşte de asemenea direct după cum urmează. Mai întâi,

deoarece H este autoadjunct avem

1 1( , ) ( , )

( , ) ( , )

n n n nn

n n n n

Hh g h Hg

Hh h Hh h

.

Apoi folosind (2.8) şi (2.15) când 0, 0n ng h , urmează


1 1

1 1

1 11

1( , )

( , )

1 ( , )( , )

n n n

n n n nn

n n n nn n n

g g gg g g

g g hg g h

2

11 1

2

( , )

( , )

nn n n

n n n

gg g g

g g g

.

Consecinţa este astfel complet demonstrată.

Observaţia 2.2. Din formulele (2.8) se vede că în ultimă instanţă ng şi nh ,

pentru 0,1,2,n , aparţin spaţiului liniar generat de elementele

2

0 0 0 0, , , , ,kg Hg H g H g . Dacă acest subspaţiu al lui E este finit dimensional,

există un n natural pentru care 0n ng h şi toţi kg şi kh sunt nuli pentru k n .

Algoritmul de mai sus nu dă un sistem complet de direcţii H-conjugate în

E, decât în cazul când 0 0{ , , }E sp g Hg . Pe baza observaţiei 2.1 vom putea

însă evita impunerea unei astfel de condiţii destul de restrictive. Folosind drept

direcţii conjugate { }np în metoda (2.5) tocmai şirul { }nh obţinut mai sus, vom

putea deduce metoda gradienţilor conjugaţi, a cărei convergenţă este dovedită în

următoarea teoremă.

Teorema 2.3. Fie 0u E astfel încât să satisfacă condiţia:

(2.16) 0 0 0 0{ , , }nu u sp g Hg H g cu 0 0 0gard ( )g J u f Hu .

Atunci metoda iterativă

(2.17) 1 1 1 0 0, gard ( ), ,n n n n n n n n n nu u h g J u h g h h g .

cu

(2.18) 1( , ) ( , ), , 0,1,2,

( , ) ( , )

n n n nn n

n n n n

g g Hh gn

g Hh Hh h

,

generează un şir { }nu convergent la punctul de minim u al funcţionalei.

Demonstraţie. Calculând gradientul (2.17) se scrie sub forma

Capitolul 2


BANACH 97

1 1 1, , 0,1,2,n n n n n n n ng g Hh h g h n ,

care, după teorema 2.2, generează un şir { }nh de direcţii H-conjugate.

Comparând cu iteraţiile (2.5) în care luăm 1n np h şi ţinând seama şi de (2.13),

rezultă că teorema 2.1 se poate aplica în varianta sugerată de observaţia 2.1.

Deci şirul nu este convergent la n când n .

Observaţia 2.3. Relaţia (2.15) arată că 1( , ) 0n nJ u h , adică nu se alege

astfel încât pe direcţia 1nh să avem 1 1 1( ) ( )n n n nJ u J u h

1 10

min ( )n nJ u h

, adică n se obţine cu metoda descreşterii maxime.

Condiţia (2.16) este de natură să implice dificultăţi la aplicarea practică a

metodei gradienţilor conjugaţi (2.17) – (2.18). Neîndeplinirea acestei condiţii

conduce fie la divergenţa şirului { }nu , fie şi acesta este cazul cel mai nefericit

pentru aplicaţii, la convergenţa şirului la un alt element decât punctul de minim.

În acest caz, limita este o proiecţie a lui u pe 0 0{ , , }sp g Hg . Vom indica în cele

ce urmează un procedeu simplu de alegere a iteraţiei iniţiale 0u , în aşa fel încât

pentru această valoare de start să fie satisfăcută condiţia (2.16).

Lema 3.1. Dacă se cunosc constantele 0 m M pentru care este

satisfăcută inegalitatea (2.1), atunci pentru

(2.19) 0

2u f

M m

,

iteraţiile { }nu date de metoda gradienţilor conjugaţi (3.17) – (3.18) sunt

convergente la u când n .

Demonstraţie. Fie ( , )K L E E definit prin

2

M mK H I

,

unde I este operatorul identic. Deoarece pentru orice v E ,


2

( , ) ( , ) ( , )2 2

M m M mKv v Hv v v v v

și

2

( , ) ( , ) ( , )2 2

M m M mKv v v v Hv v v

,

urmeaza că 2 2

M m M mK

. Deci

21K

M m

şi atunci avem

1

1 2 2u H f I K f

M m M m

2 12 2 2

n

nf Kf K fM m M m M m

.

De aici rezultă

(2.20) 2

0 { , , , , }nu u sp Kf K f K f .

Pe de altă parte avem succesiv

0 0

2g f Hu Kf

M m

,

2

0

2 2

2

M mHg I K Kf Kf K f

M m M m

,

2 2

0

2

2 2

M m M mH g I K Kf I K K f

M m

2 322

2

M mKf K f K f

M m

,

şi aşa mai departe. Inductiv este uşor de arătat că

2 2

0 0 0{ , , , } { , , }sp g Hg H g sp Kf K f .

Comparând cu (2.20) rezultă satisfacerea condiţiei (2.16) şi deci convergenţa

şirului { }nu la u.

Metoda gradienţilor conjugaţi este unul dintre cele mai eficiente procedee

de rezolvare a ecuaţiilor liniare, deci de minimizare a funcţionalelor pătratice.

Capitolul 2


BANACH 99

Există o literatură destul de vastă privind rapiditatea de convergenţă a acestei

metode. Cea mai bună evaluare a rapidităţii este dată de J. W. Daniel care arată

superioritatea acestei metode faţă de metoda gradientului. În cazul spaţiului

n-dimensional procedeul este finit în sensul că dacă facem abstracţie de erorile

de rotunjire după un număr m de iteraţii cel mult egal cu 1n , se obţine 0mg ,

adică mu u . Într-adevăr, { }kg formează un sistem ortogonal conform teoremei

2.2 şi un astfel de sistem nu poate conţine decât cel mult n vectori nenuli în

spaţiul n . Din cauza erorilor de rotunjire însă ortogonalităţile nu sunt exacte

( ( , )i ig g este mai mic decât precizia cu care se lucrează pentru i j ) şi procesul

nu se termină practic după 1n paşi dar în orice caz 2 – 3 cicluri de 1n paşi

rezolvă problema cu orice precizie dorim.


Capitolul 3

DISCRETIZAREA PROBLEMELOR DE MINIM FĂRĂ

RESTRICŢII ŞI REZOLVAREA PROBLEMELOR

DISCRETIZATE FINIT DIMENSIONALE

§1. TEORIA GENERALĂ A DISCRETIZĂRII ŞI APLICAŢII

1.1. DISCRETIZAREA SPAŢIULUI

Pentru rezolvarea numerică a unei probleme de optim definite într-un

spaţiu de funcţii, în general infinit dimensional, trebuie parcurse două etape

distincte. Mai întâi este necesară aproximarea ei printr-o problemă discretă, de

obicei finit dimensională, mai adecvată lucrului cu calculatorul, în a doua etapă,

problema discretizată se rezolvă numeric cu metode specifice, în acest paragraf

ne vom ocupa cu unele procedee de discretizare a problemelor de minim fără

restricţii.

Discretizarea unei probleme de optim constă în discretizarea spaţiului de

definiţie şi apoi a funcţionalei al cărei optim se caută.

Fie E un spaţiu liniar normat şi { }, 1,2,nE n , un şir de spaţii liniare

normate prin care vom face discretizarea (aproximarea) lui E. Dacă nE E şi

au aceeaşi topologie, compararea elementelor n nu E cu elementul u E se

Capitolul 3


RESTRICŢII ŞI REZOLVAREA PROBLEMELOR DISCRETIZATE FINIT DIMENSIONALE 101

poate face uşor în norma spaţiului E. În general, nE pot fi spaţii distincte de E

sau cel puţin cu topologii distincte. În acest caz vom defini nişte aplicaţii între

nE şi E în ambele sensuri care să ne permită compararea lui n nu E şi u E în

acelaşi spaţiu.

Definiţia 1.1. Se numeşte discretizare internă (aproximare internă) a

spaţiului liniar normat E un şir de spaţii liniare normate { }, 1,2,nE n ,

împreună cu un şir de operatori ( , )n np L E E numiţi operatori de prelungire

şi un şir de operatori :n nr E E numiţi operatori de restricţie. Operatorii np

sunt liniari şi continui, de multe ori chiar injectivi, dar asupra operatorilor nr nu

se impune liniaritate şi nici continuitatea, deşi de cele mai multe ori în aplicaţii

le satisfac. Aproape întotdeauna spaţiile nE sunt de dimensiune finită,

reprezentând spaţiile în care se discretizează funcţionala. Vom nota cu şi

respectiv, cu n normele în E şi în nE . În general spaţiile discretizării nE sunt

de aceeaşi natură cu spaţiul E. Dacă E şi nE sunt spaţii Banach vom spune că

avem o discretizare Banach iar dacă E şi nE sunt spaţii Hilbert – o discretizare

Hilbert.

Definiţia 1.2. Fie v E şi , 1,2,n nv E n . Vom spune că nv

converge tare (slab) la v dacă lim n nn

p v v

în topologia tare (respectiv, slabă)

a lui E. Cantitatea n nv p v se numeşte eroarea dintre nv şi v. Când

lim 0n n nnv r v

se spune că nv converge discret la v iar n n n

v r v este

eroarea discretă dintre nv şi v. În sfârşit, se spune că discretizarea { , , }n n nE p r

a spaţiului E este convergentă dacă, pentru orice v E , avem

lim 0n nn

p r v v

.


Cantitatea n np r v v este numită eroarea de trunchiere a lui v.

Definiţia 1.3. Discretizarea { , , }n n nE p r a spaţiului liniar normat E este

stabilă dacă normele operatorilor de prelungire sunt majorate independent de n:

(1.1) , 1,2,np M n .

Lema 1.1. Fie { , , }n n nE p r o discretizare stabilă a spaţiului liniar normat

E. Pentru ca această discretizare să fie convergentă este necesar şi suficient ca

lim 0n nn

p r v v

pentru toate elementele v ale unui subspaţiu V E dens în E.

Demonstraţie. Necesitatea este evidentă. Pentru suficienţă fie v E ,

v V ; trebuie să definim n nr v E astfel încât n np r v v când n . Acest

element v poate fi aproximat oricât de bine prin elemente din V; pentru fiecare

m natural, există mv V încât

1

mv vm

.

Dar pentru fiecare , n n mm p r v converge la mv pentru n ; deci există

m natural încât

1

m n n m mn p r v vm

.

Putem lua 1max{ , }m m m ceea ce permite obţinerea unui şir { }m crescător

şi convergent la infinit când m . Vom defini atunci

n n mr v r v pentru 1m mn .

În acest mod, pentru 1, 0,1,2,m k m kn k , obţinem

2 2

n n m k m k n n m kp r v v v v v p r vm k m

,

adică

2n np r v v

m , îndată ce mn ,

Capitolul 3



de unde rezultă convergenţa discretizării.

Lema 1.2. Dacă discretizarea { , , }n n nE p r a spaţiului liniar normat este

stabilă şi convergentă, atunci convergenţa discretă implică convergenţa tare.

Demonstraţie. Dacă n nv E şi v E , avem inegalitatea:

( )n n n n n n n n n n n nv p v v p r v p r v v v p r v M r v v ,

de unde rezultă implicaţia cerută.

Uneori pentru discretizarea unui spaţiu liniar normat E este mai comod să

definim operatorii de prelungire de la spaţiile discretizării nE la un alt spaţiu

liniar normat F, de obicei cu o topologie mai simplă. Astfel se ajunge la un alt

tip de discretizare.

Definiţia 1.4. Fie E şi F spaţii liniare normate şi :e E F un

izomorfism al lui E în F. Vom spune că avem o discretizare externă a

spaţiului E dacă am definit un şir de spaţii liniare normate nE , un şir de

operatori de prelungire ( , )n np L E F şi un şir de operatori de restricţie

:n nr E E . Dacă notăm cu norma lui F, în acest caz eroarea se defineşte prin

n np v ev şi corespunzător se dă definiţia convergenţei tari sau slabe a unui şir

n nv E la v E în topologia corespunzătoare a lui F. Eroarea discretă şi

convergenţa discretă se păstrează sub aceeaşi formă ca în definiţia 1.2. În fine,

pentru eroarea de discretizare vom lua de data aceasta n np r v ev . Definiţia

unei discretizări convergente se completează însă după cum urmează.

Definiţia 1.5. O discretizare externă este convergentă dacă:

1) pentru orice v E , avem lim 0n nn

p r v ev

,

2) pentru orice şir n nv E , astfel ca un subşir nv să fie slab convergent la

v F , avem v eE .


Noţiunea de discretizare externă este mai generală decât cea de discretizare

internă care se obţine pentru F E şi e — operatorul identic.

Este uşor de constatat că lemele 1.1 şi 1.2 îşi păstrează valabilitatea şi

pentru discretizarea externă (lema 1.1 trebuie uşor modificată prin adăugarea

condiţiei 2) din definiţia 1.5). Necesitatea introducerii condiţiei 2) de mai sus va

apărea cu mai multă claritate în secţiunile următoare.

1.2. DISCRETIZAREA PROBLEMEI DE OPTIM

Fie E un spaţiu Banach reflexiv şi :J E o funcţională slab

semicontinuă inferior care satisface condiţia:

(1.2) 00 0( ), { , ( ) ( )}xx D J W x E J x J x e mărginită.

Problema de minim,

(1.3) min ( ) ( )v E

J v J u

,

are soluţii în aceste condiţii.

Fie { , , }n n nE p r o discretizare Banach internă a spaţiului E şi :n nJ E ,

1,2,n un şir de funcţionale pentru care problemele

(1.4) min ( ) ( )n n

n n n nv E

J v J u

au soluţii n nu E (de exemplu, vom putea presupune că nJ satisfac condiţii care

asigură existenţa punctelor de minim de aceeaşi natură cu cele pentru J).

Problemele (1.4) se numesc probleme de optim discretizate. Şirul { , , , }n n n nE p r J

poartă numele de discretizare a problemei de minim (1.3).

Capitolul 3



Definiţia 1.6. Discretizarea problemei de optim se numeşte consistentă

dacă satisface condiţiile

(1.5) lim lim sup ( )n n nnn nv J v

,

proprietate numită uniformă coercivitate, şi

(1.6) ,{ } { },n n n n nv E v v v slab convergent la lim ( ) ( )n nn

v E J v J v

,

pe care o vom numi slaba continuitate a discretizării.

Teorema 1.1. Fie dată problema de minim (1.3) care satisface condiţiile

de existenţă a soluţiei şi fie o discretizare Banach a ei { , , , }n n n nE p r J care

verifică următoarele ipoteze:

i) discretizarea { , , }n n nE p r a spaţiului E este stabilă şi convergentă;

ii) problemele discretizate (1.4) au soluţii pentru fiecare 1,2,n ;

iii) discretizarea problemei este consistentă.

Atunci, dacă { }nu este un şir de soluţii ale problemelor discretizate, există

subşiruri { } { }n nu u slab convergente, limitele lor slabe sunt puncte de minim

u ale funcţionalei J şi avem

(1.7) lim ( ) lim ( ) ( )n n n nn n

J u J r u J u

.

Demonstraţie. Fie ( )v D J fixat oarecare. Deoarece discretizarea

spaţiului este convergentă avem

lim n nn

p r v v

,

Adică nr v converge tare la v în sensul definiţiei 1.2. Ipoteza (1.6) ne dă atunci

lim ( ) ( )n nn

J r v J v

.

Cum însă nu este punct de minim al lui nJ de aici rezultă lim sup ( )n nn

J u

( )J v . Condiţia de uniformă coercivitate implică atunci că şirul de numere


n nu este mărginit. Deoarece discretizarea spaţiului este stabilă va rezulta atunci

că şirul { }n np u E este mărginit. Spaţiul E fiind reflexiv, urmează că există

subşirul n np u u E . Pentru orice v E avem

( ) ( )n n n nJ u J r v .

Cum însă nu converge slab la u şi nr v converge slab la v, folosind slaba

continuitate a discretizării, rezultă

( ) ( ),J u J v v E ,

adică faptul că u este soluţie a problemei (1.3).

În sfârşit, deoarece pentru orice subşir { } { }n nu u slab convergent, avem

lim ( ) lim ( ) ( ) min ( )n n n nn n v E

J u J r u J u J v

, urmează că şirurile numerice

{ ( )}n nJ u şi { ( )}n nJ r u sunt convergente şi are loc (1.7).

Pentru a obţine convergenţa tare a şirului { }nu vom introduce o ipoteză

nouă asupra funcţionalelor nJ .

Definiţia 1.7. Funcţionalele nJ sunt egal uniform convexe dacă satisfac

condiţia de uniformă convexitate:

(1.8) 0 0( ) (1 ) ( ) ( (1 ) ) ( ) ( )n n n n n n n n nJ x J y J x y x y ,

, , [0,1]n n nx y E ,

unde 0 şi 0 sunt funcţii scalare indep endente de n, cu proprietăţile:

(1.9) 0 0 0(0) (1) 0, ( ) 0t pentru

00 0

0

( )(0,1), l im , 0

t

tt

t

şi

(1.10) 0 0(0) 0, ( )t continuă, crescătoare, 0( ) 0t , pentru

0( )0, l im

t

tt

t

.

Capitolul 3



Teorema 1.2. Fie { , , , }n n n nE p r J o discretizare Banach reflexivă a

problemei (1.3), satisfăcând ipotezele i) şi iii) de mai sus. Presupunem că

funcţionala J este uniform convexă şi semicontinuă inferior şi că funcţionalele

nJ sunt egal uniform convexe şi semicontinue inferior. Atunci problemele

discretizate (1.4) au soluţii unice , 1,2,nu n , şirul acestor soluţii converge

tare la punctul de minim unic u al funcţionalei şi au loc

(1.11) lim ( ) ( )n nn

J p u J u

şi evaluarea erorii

(1.12) 1( ) { ( ) ( )}, 1,2,n n n np u u J p u J u n .

Demonstraţie. Funcţionalele J, nJ fiind uniform convexe şi semicontinue

inferior, rezultă imediat existenţa şi unicitatea punctelor lor de minim , nu u (vezi

demonstraţia teoremei II. 1.2). Deci, conform teoremei precedente, şirul n nu E

converge slab la u E , adică în sensul în care a fost aici definită convergenţa,

n np u u când n . Atunci avem şi

,2

n n n np u p r uu n

.

După (1.8) avem însă

0 0

1 1 1( ) ( ) ( )

2 2 2 2

n nn n n n n n nn

u r uu r u J u J r u J

.

Folosind acum slaba continuitate a discretizării, putem scrie:

0 0

1 1 10 lim ( ) ( ) ( ) ( ) 0

2 2 2n n nn

u r u J u J u J u

,

de unde, ţinând seama de proprietăţile lui 0 , rezultă lim 0n n nnu r u

, adică

convergenţa discretă a şirului nu la u. Pe baza lemei 1.2, rezultă atunci

convergenţa tare.


Pentru a dovedi evaluarea (1.12) vom folosi uniforma convexitate a lui J

şi pe baza lemei II. 1.2 vom scrie:

( ) ( ) ( , ) ( )n n n n n nJ p u J u J u p u u p u u .

Ţinând seama de faptul că u este punct de minim absolut pe E, deci

( , ) 0n nJ u p u u , rezultă evaluarea (1.12).

În sfârşit, egalitatea (1.11) se poate dovedi direct, dar rezultă şi din faptul

că J este continuă (vezi teorema I 4.3).

Observaţia 1.1. Teoremele 1.1 şi 1.2 se pot extinde şi la cazul unei

discretizări externe a spaţiului, modificând corespunzător limitele şirurilor

obţinute prin prelungiri prin elemente din spaţiul F. În cursul demonstraţiei se

foloseşte cu necesitate şi condiţia 2) din definiţia 1.5.

1.3. O ALTĂ TEOREMĂ DE CONVERGENŢĂ PENTRU FUNCŢIONALE CONVEXE

În cazul funcţionalelor convexe, se poate înlocui condiţia de slabă

continuitate a discretizării (1.6) cu o altă condiţie, care în aplicaţie este mai

comodă uneori.

Teorema 1.3. Fie :J E definită pe spaţiul reflexiv E, convexă

proprie, semicontinuă inferior şi satisfăcând condiţia (1.2). Considerăm o

discretizare Banach { , , , }n n n nE p r J care verifică ipotezele:

i) discretizarea { , , }n n nE p r a spaţiului E este stabilă şi convergentă;

ii) problemele discretizate (1.4) au soluţii n nu E pentru fiecare

1,2,n ;

Capitolul 3



iii) nJ satisfac condiţia de uniformă coercivitate şi în plus are loc

(1.13) lim sup{ ( ) ( )} 0,n n n n n nn

J v J p v v E

.

Atunci şirul { }nu are puncte limită slabe şi acestea sunt puncte de minim ale lui

J. În plus, are loc

(1.14) lim sup ( ) lim sup ( ) ( )n n n nn n

J u J r u J u

.

Demonstraţie. J este continuă în interiorul domeniului său efectiv ( )D J ,

conform teoremei I 4.3. Deci, din ipoteza de convergenţă a discretizării, rezultă

(1.15) lim ( ) ( ), Int ( )n nn

J p r v J v v D J

.

Pe de altă parte, condiţia (1.13) implică, pentru orice n nv E ,

(1.16) lim sup ( ) lim sup ( ) 0 lim sup ( )n n n n n n nn n n

J v J p v J v

lim sup ( )n nn

J p v

.

Deci lim sup ( ) lim sup ( ) lim sup ( ) ( )n n n n n nn n n

J u J r v J p r v J v

, pentru

orice Int ( )v D J . Condiţia de uniformă coercivitate implică atunci că { }n nu

este mărginit, de unde, folosind stabilitatea, { }n np u este mărginit, deci slab

secvenţial compact. Fie u limita slabă a unui subşir { }n np u . Folosind slaba

semicontinuitate a funcţionalei J (teorema I 4.2) şi inegalităţile (1.16), putem

scrie şirul de inegalităţi:

( ) l im inf ( ) l im sup ( )

lim sup ( ) lim ( ) ( )

n n n nn n

n n n nnn

J u J p u J u

J r v J p r v J v

pentru orice Int ( )v D J , adică faptul că u este punct de minim absolut al

funcţionalei. Făcând v u în şirul de inegalităţi de mai sus şi luând orice subşir

n np u slab convergent, obţinem şi (1.14).


Ca şi în secţiunea precedentă, se poate dovedi şi un rezultat privind

convergenţa tare a şirului nu .

Teorema 1.4. Fie :J E definită pe spaţiul Banach reflexiv E,

uniform convexă, proprie şi semicontinuă inferior. Fie discretizarea Banach

{ , , , }n n n nE p r J , unde nE sunt spaţii reflexive şi sunt satisfăcute condiţiile i) şi iii)

în care (1.13) este înlocuită cu

(1.13’) lim{ ( ) ( )} 0,n n n n n nn

J v J p v v E

.

Presupunem că nJ sunt egal uniform convexe şi semicontinue inferior. Atunci

problemele discretizate au soluţii unice nu , şirul { }nu converge tare la punctul

de minim unic u al funcţionalei J şi au loc (1.11) şi (1.12).

Demonstraţie. Existenţa şi unicitatea soluţiilor nu şi u rezultă imediat ca

în teorema 1.2. Condiţia de egal uniformă convexitate a funcţionalelor nJ

implică

0 0

1 1 1( ) ( ) ( )

2 2 2 2

n nn n n n n n nn

u r uu r u J u J r u J

.

Conform ipotezei (1.13'), dacă notăm

2 2

n n n n n nn n

u r u p u p r uJ J

,

avem l im 0nn

.

Deci, după (1.14),

1 10 lim inf ( ) lim sup ( )

2 2n n n nn n

n n

u r u u r u

1 1( ) ( ) lim inf lim

2 2 2

n n n nn

nn

p u p r uJ u J u J

Dar n np u u conform rezultatului teoremei precedente şi unicităţii lui u, în

timp ce n np r u u din cauza convergenţei discretizării. Aplicând atunci slaba

Capitolul 3



semicontinuitate inferioară a lui J, rezultă lim ( ) 0n nn

u r u

, adică

convergenţa discretă a şirului nu la u. Folosind lema 1.2, rezultă şi convergenţa

tare. Relaţiile (1.11) şi (1.12) se demonstrează ca şi la teorema 1.2.

1.4. METODA LUI GALERKIN DE DISCRETIZARE

Un caz particular de discretizare foarte des folosit în aplicaţii este

procedeul lui Galerkin.

Fie E un spaţiu Hilbert şi { }, 1,2,nE n , un şir de subspaţii închise ale

lui E cu topologiile induse de cea a spaţiului E. Vom spune că şirul { }nE este

complet în E dacă avem

(1.17) 1

n

n

E E

.

Definim operatorii de prelungire :n np E E ca fiind injecţiile identice:

(1.18) ,n n n n np v v v E .

Operatorii de restricţie :n nr E E vor fi aici proiectorii ortogonali pe nE . Dacă

:J E este funcţionala al cărei minim se caută pe întreg spaţiul, vom lua

drept funcţionale discretizate :n nJ E , restricţiile lui J la nE . Cu această

construcţie se poate dovedi următorul rezultat.

Teorema 1.5. Fie funcţionala :J E convexă proprie, semicontinuă

inferior şi satisfăcând condiţia de coercivitate:


(1.19) l im ( )v

J v

.

Fie, de asemenea, şirul { }, 1,2,nE n , de subspaţii închise ale lui rE

complet în E. În aceste ipoteze, funcţionala J are puncte de minim nu pe nE

pentru fiecare n natural, şirul { }nu are puncte de acumulare slabă şi acestea

sunt puncte de optim ale lui J. Dacă, în plus, J este uniform convexă, şirul { }nu

este tare convergent la punctul de minim unic u al funcţionalei şi are loc

evaluarea

(1.20) 1( ) { ( ) ( )}, 1,2,n nu u J u J u n .

Demonstraţie. Definim discretizarea { , , }n n nE p r a spaţiului E ca mai sus.

Condiţia de stabilitate este evident satisfăcută deoarece 1, 1,2,np n . Ca

proiectori ortogonali, nr realizează distanţa minimă faţă de elementele

subspaţiului nE , deci avem

, ,n n n n n np r v v r v v v v v E v E .

În particular, datorită completitudinii şirului { }nE , putem alege n nv E în aşa

fel încât 0nv v când n , pentru fiecare v E fixat. De aici rezultă

atunci convergenţa discretizării spaţiului.

Condiţia de uniformă coercivitate a restricţiilor nJ ale funcţionalei J la nE

rezultă din ipoteza (1.15), iar condiţia (1.13') este aici imediată. Ipoteza (1.15) e

valabilă în particular şi pentru n nv E cu nv , deci problemele discretizate

au soluţii nu pentru fiecare n. Astfel teorema 1.3 se poate aplica şi rezultă prima

concluzie.

Dacă J este în plus uniform convexă, condiţia de egal uniformă

convexitate este automat satisfăcută. Aşadar şi teorema 1.4 se poate aplica, de

unde rezultă convergenţa tare a şirului nu la u şi evaluarea (1.20).

Capitolul 3



În practică de obicei se consideră un șir { }ne de elemente liniar

independente în E şi se ia 1 2{ , , , }n nE sp e e e . În modul acesta problemele

discretizate sunt finit dimensionale. Alegerea şirului { }ne complet în spaţiu este

în acest caz esenţială pentru rapiditatea de convergenţă a şirului { }nu .

1.5. O DISCRETIZARE INTERNĂ A SPAŢIULUI ( )pL

Fie un domeniu mărginit din m şi ( )pL spaţiul funcţiilor de putere

p sumabilă în (1 )p , cu norma

( ) dp p

v v x x

.

Pentru a defini o discretizare a acestui spaţiu, introducem o reţea de puncte în

m . Notăm cu j vectorul din m cu componente întregi 1 2( , , , )mj j j şi cu

1

m

i

i

j j

. Pentru n natural, reţeaua n este formată din punctele:

1

1 1 1, , , întregim in

j j j jn n n

.

Dacă 1 2( , , , ) m

nx x x x , introducem notaţiile:

1 1

1 1 1 1( ) , ,

2 2 2 2n m mx x x x x

n n n n

,

1

1

( )2

n n

j

jx x

n

,

1 11 1,n n nj j

n n

,


1 11 1,n n nj j

n n

,

1 dacă ( ) ,

( )0 dacă ( ) .

n

nx

n

y xy

y x

Pentru discretizarea lui ( )pE L , considerăm drept spaţii nE subspaţiile lui

( )m

pL de funcţii etajate de forma

(1.21) 1

( ) ( ) ( )

n

n n ny

y

v x v y x

,

cu normele

(1.22) 1

1( ) d ( )

mn

p p p

n n nmny

v v x x v yn

.

nE sunt finit dimensionali, avînd ca dimensiune numărul punctelor din 1

n şi

baza 1{ , }ny ny . Operatorii de prelungire sunt :n np E E definiţi simplu

prin

(1.23) ( ) ( ), ,n n n n np v x v x x v E .

Evident, 1np . Operatorii de restricţie :n nr E E se definesc prin

(1.24) 1

1

( )

( ) ( ) ( ), ( ) ( )d ,

n n

m

n n ny n n

y y

r v x r v y x r v y n v x x y

.

Pentru aceşti operatori avem

1 1

1

( )

1( ) ( ) ( )d

n n n

p

p p m p

n nmny y y

r v r v y n v x xn

.

După inegalitatea lui Holder,

1 1

( ) ( ) ( )

1 1( )d ( ) d d , 1

n n n

p q

p

y y y

v x x v x x xp q

,

urmează

Capitolul 3



(1.25) p p

n nnr v v ,

adică nr sunt mărginiţi, deci continui şi 1nr . Convergenţa discretizării se

demonstrează cu ajutorul lemei 1.1. Spaţiul funcţiilor continue cu suport

compact în este dens în ( )pL şi atunci este suficient să arătăm convergenţa

pentru acest subspaţiu. După definiţia lui np , avem n n np r v r v şi nr v converge

la v în ( )pL , cum se vede uşor pentru funcţiile din subspaţiul considerat.

1.6. O DISCRETIZARE EXTERNĂ A SPAŢIULUI 1

0 ( )pW

Vom considera acum spaţiul Sobolev 1( )pW al funcţiilor din ( )pL ale

căror derivate în sensul teoriei distribuţiilor sunt în ( )pL , înzestrat cu norma

1

m

pi i p

vv v

x

,

unde cu p am notat norma din ( )pL . Închiderea subspaţiului ( )D al

funcţiilor indefinit diferenţiabile cu suport compact în , luată în topologia lui

1( )pW , este un subspaţiu al acestuia pe care îl vom nota cu 1

0 ( )pW . Definim o

discretizare externă a acestui spaţiu.

Drept spaţiu F al prelungirilor considerăm spaţiul 1( )m

pF L cu

izomorfismul


(1.26) 1 1

0

1

( ) , , , ( )m

p p

n

v vv W ev v L

x x

.

Ca şi mai înainte, nE sunt spaţii de funcţii etajate de forma

(1.27) 1

( ) ( ) ( )

n

n n ny

y

v x v y x

,

însă cu norma

(1.28) 1

( ) d ( ) dm m

mp p pp

n n in nni

v v x x n v x x

,

unde diferenţele in sunt definite prin

(1.29) 1 1

( )2 2

in n n i n iv x v x e v x en n

,

{ }ie fiind vectorii bazei naturale a lui m . Spaţiul nE are dimensiunea egală cu

numărul punctelor din 1

n .

Operatorii de prelungire se definesc prin

(1.30) 1[ , , , ]n n n n n mn np v v n v n v F ,

unde funcţiile componente sunt restrânse la .

Restricţiile nr le definim numai pe ( )D , care este densă în 1

0 ( )pW , prin

(1.31) 1

( ) ( ) ( )

n

n ny

y

r v x v y x

.

Discretizarea este stabilă deoarece pentru orice n nv E ,

1

d dm

p p p pp

n n n in n n ni

p v v x n v x v

.

Să demonstrăm acum că este şi convergentă. Vom dovedi lucrul acesta numai

pentru ( )v D . Pentru prima condiţie a definiţiei 1.5 trebuie să arătăm că

Capitolul 3



nr v v şi in n

i

vn r v

x

în ( )pL , când n , pentru orice ( )v D . Fie n

suficient de mare astfel ca suportul lui v să fie inclus în mulţimea

1

( )

n

n n

y

y

. Pentru orice 1

ny și ( )nx y , formula lui Taylor ne dă

1 1( ) ( ) ( ) ( ) ( ) ( )2

n

mr v x v x v y v x c v y x c v

n ,

unde 1( ) sup grad ( )x

c v v x

. Deci

1( )sup ( ) ( )

2n

nx

c v mr v x v x

n

.

Evaluând aceeaşi expresie şi pe — n , obţinem

1sup ( ) ( ) ( ) d( , )2

n nx

mr v x v x c v

n

,

unde este frontiera lui şi ( , )nd este distanţa între n şi . Deci nr v

converge la v în ( )L , deci şi în ( )pL .

Apoi, similar, pentru 1

ny , ( )nx y

( ) ( )in n

i

n r v x v xx

2

1 1

2 2( ) ( )

1

n i n i

i

r v y e r v y emn n

v x c vx n

n

,

unde 2 ( )c v depinde numai de norma maximă a derivatelor secunde ale lui v. Pe

— n avem


2( ) ( )d( , )n

i

v x c vx

şi deci rezultă şi aici convergenţa în ( )pL a lui in nn r v la , 1,2, ,i

vi m

x

.

Să dovedim acum valabilitatea condiţiei 2) din definiţia 1.5.

Fie n nv E un subşir al şirului { }nv oarecare, astfel încât n n rp v w F când

n , adică 0lim , lim , 1n in n in n

v w n v w i m

, în topologia slabă a lui

( )pL , adică în ( )qL , unde 0 1

1 11, ( , , , )mw w w w

p q . Cum funcţiile

,n in nv n v au suportul compact în , putem prelungi limitele de mai sus în

( )n

qL , luând , 0jw j m , egali cu zero în afara lui . Se poate uşor dovedi

o formulă de integrare prin părţi discretă, de forma

(1.32) ( ) ( )d ( ) ( )dm m

in n n inn v x x x v x n x x ,

pentru orice ( ) ( )m m

qL D . Când n , membrul stâng converge la

( ) ( )dm

iw x x x ,

iar membrul drept tinde la

deoarece in

i

nx

în ( )mL (ceea ce se arată la fel ca mai sus). Deci

obţinem

0( ) ( )d ( ) d , ( )m m

m

i

i

w x x x w x xx

D ,

Capitolul 3



care arată că 0 , 1i

i

w w i mx

, în sensul teoriei distribuţiilor. Aşadar,

1

0 0 ( )m

pw W şi cum 0w se anulează în afara lui 1

0 0, ( )pw W . Deci rw eE

ceea ce era de arătat.

Discretizarea { , , }n n nE p r a spaţiului 1

0 ( )pW se poate extinde şi la întregul

spaţiu 1( )pW cu puţine modificări. Acest tip de discretizări poartă numele de

discretizări (aproximări) cu diferenţe finite.

1.5. DISCRETIZAREA PROBLEMEI CALCULULUI VARIAŢIONAL

Considerăm problema minimizări funcţionalei

(1.33) 0

( ) ( , ( ) , ( ))d

t

J x g t x t x t t .

cu condiţiile

(1.34) (0) (1) 0x x .

Vom considera funcţionala definită pe spaţiul 1

0 [0,1] { ; (0) (1) 0,pW x x x x

absolut continuă pe [0,1], [0,1]}px L . Impunem condiţii asupra lui g care să

asigure existenţa punctelor de minim. Anume, presupunem că ( , , )g t x y este

continuă de cele trei variabile pentru 0 1, ,t x y şi derivabilă în


raport cu y, cu ( , , )y

t x yg

continuă în x, uniform pentru ,t y mărginiţi şi astfel

încât

(1.35) 1 2 1 2 2( , , ) ( , , ) ( ) ( , , )g

g t x y g t x y y y t x yy

,

1 2[0,1], , ,t x y y . Aceasta din urmă este de fapt o condiţie care

asigură că g este convexă şi derivabilă ca funcţie de y. De aici se poate uşor

arăta că J este slab semicontinuă inferior. În plus, presupunem că există

constantele ,a b cu 0b astfel ca

(1.36) ( , , )p

g t x y a b y pentru [0,1]t , x finit, orice y.

Această ipoteză implică inegalitatea:

( )p

J x a b x ,

unde cu am notat norma din [0,1]pL . Luând puterea p în identitatea

0

( ) ( )d

t

x t x s s

şi integrând pentru [0,1]t , obţinem

1 1 1 1

1 1

0 0 0 0 0

1( )d d ( ) d d ( ) d d

pt t

p p p pp p

s

x x s s t x s s t t x s t t s xp

.

Deci avem, pentru norma a spaţiului 1

0 [0,1]pW ,

(1.37) 1

1p p p p

x x x xp

.

Atunci, condiţia (1.36) implică

( )1

ppJ x a x

p

,

Capitolul 3



ceea ce arată că l im ( )x

J x

. Spaţiul 1

0 [0,1]pW este subspaţiu închis al

spaţiului Sobolev 1[0,1]pW , care este reflexiv. Deci şi el este reflexiv şi astfel

avem asigurate condiţiile de existenţă a minimului. Pentru discretizarea

problemei vom folosi discretizarea spaţiului 1

0 [0,1]pW din secţiunea precedentă

în cazul particular când 1m şi [0,1] . După cum am demonstrat, această

discretizare este stabilă şi convergentă. În cazul nostru, reţeaua este formată din

punctele , 0,1,2, ,i

it i n

n , din care 1n sunt interioare intervalului [0,1],

deci spaţiul nE este ( 1)n -dimensional. nv şi n nv se definesc corespunzător cu

formulele (1.27) – (1.29), iar prelungirile np şi restricţiile nr cu (1.30) şi (1.31)

pentru 1m .

Fie acum funcţionalele discretizate:

1

1

1( ) ( , ( ) , ( ))

n

n n i n i n n i

i

J x g t x t n x tn

,

pentru orice 1

1

( ) ( ) ( )n

n n i ni n

i

x t x t t E

, unde ( ) 1ni t , dacă 1

2it t

n

1

2it

n . Conform ipotezei (1.36), avem

1

1

1( ) [ | ( ) | ]

np p

n n n n i

i

J x a bn x tn

.

O formulă discretă de tipul formulei (1.37) se poate demonstra pe o cale

similară, luând normele în nE şi, în loc de derivată, diferenţele n nn x . Pe baza

acestei formule se obţine uniforma coercivitate a funcţionalelor nJ .

Pentru a avea verificată şi a doua condiţie de consistenţă (1.6) va trebui să

impunem ipoteze suplimentare asupra lui g. Anume se presupune că


( , ( ), ( ))g t x t y t este qL -continuă în x şi y, adică dacă nx x şi ny y în

topologia lui qL , când n , atunci ( , ( ), ( )) ( , ( ), ( ))n ng t x t y t g t x t y t

uniform pentru [0,1]t .

Fie 1

1

, ( ) ( ) ( )n

n n n n i ni

i

x E x t x t t

; prelungirile np duc pe nx în

2[ , ] [0,1]n n n px n x L F . Faptul că n np x converg slab la ex F , cu

1

0 [0,1]px W , înseamnă convergenţele

lim ( ) ( ), lim ( ) ( )n n nn n

x t x t n x t x t

,

în topologia lui [0,1]qL . Pentru a arăta slaba continuitate a discretizării, se

evaluează

1 1

10

1( ) ( ) ( , ( ) , ( )) d ( , ( ) , ( ))

n

n n i n i n n i

i

J x J x g t x t x t t g t x t n x tn

1 2 1

0 (2 1) 2

( , ( ) , ( )) d ( , ( ) , ( )) d

n

n n

g t x t x t t g t x t x t t

1 1 2

1 21

( , ( ) , ( )) ( , ( ) , ( )) di

i

n t n

i n n nt n

i

g t x t x t g t x t n x t t

,

care conduce la condiţia (1.6) ţinând seama de ipotezele impuse asupra funcţiei g.

În acest mod, aplicând teorema 1.1 dacă funcţionalele nJ admit puncte de

minim n nu E , orice punct de acumulare slabă în [0,1]pL , adică punct limită în

topologia lui [0,1]L , este un punct de minim al funcţionalei J. Condiţii mai

puternice impuse asupra lui g, care să asigure uniforma convexitate a lui J,

conduc la convergenţa tare a şirului.

Capitolul 3



§2. DISCRETIZAREA PROBLEMELOR PĂTRATICE

2.1. TEOREMA GENERALĂ DE CONVERGENŢĂ

Fie E un spaţiu Hilbert cu produsul scalar ( . ,. ) şi norma indusă . Ca şi

până aici, vom identifica spaţiu dual E cu spaţiul E, astfel încât dualitatea . ,.

este dată de produsul scalar. Fie :a E E o funcţională biliniară, continuă

în raport cu topologia lui E E şi simetrică. Presupunem de asemenea că există

m real astfel încât

(2.1) 2

( , ) , 0,a v v m v m v E .

Pentru un element f E fixat, definim funcţionala pătratică :J E prin

(2.2) 1

( ) ( , ) ( , ) ,2

J v a v v l v v E .

În ipotezele de mai sus, funcţionala J admite un punct de minim absolut unic

u E , care este caracterizat de ecuaţia variaţională (vezi secţiunea I 4.4):

(2.3) ( , ) ( , ),a u v l v v E .

Să considerăm o discretizare Hilbert { , , }n n nE p r a spaţiului E şi să notăm

cu ( . ,.)n şi n produsul scalar şi norma în nE . Pentru a cuprinde toate cazurile

vom presupune că discretizarea este externă, notând cu :e E F izomorfismul

lui E în spaţiul prelungirilor F care este un spaţiu Banach reflexiv. Pentru a

defini problema discretizată, fie :n n na E E un şir de funcţionale biliniare,

continue şi simetrice, împreună cu un şir n nl E care satisface


(2.4) 2

0 0 1( , ) , 0, ,n n n n n n nna v v m v m v E l m ,

cu 0m şi 1m independente de n. Fie de asemenea funcţionalele :n nJ E date de

(2.5) 1

( ) ( , ) ( , ) ,2

n n n n n n n n nJ v a v v l v v E .

În ipotezele date, funcţionalele nJ admit puncte de minim unice un în nE

care sunt caracterizate de ecuaţiile

(2.6) ( , ) ( , ) ,n n n n n n n na u v l v v E .

Condiţia (2.4) asigură uniforma coercivitate a şirului de funcţionale nJ . În locul

condiţiei de slabă continuitate a discretizării, vom face două ipoteze care, în

general, sunt mai slabe şi anume:

(2.7) , lim ( , ) ( , )n n n n nn

v v w w a v w a v w

şi

(2.8) lim( , ) ( , )n n n nn

v v l v l v

,

unde , , ,n nv w E v w E şi convergenţa subşirurilor { }nv şi { }nw este cea dată

în definiţia 1.4.

Putem dovedi atunci următoarea teoremă de convergenţă.

Teorema 2.1. Dacă discretizarea { , , }n n nE p r este stabilă şi convergentă

şi dacă sunt satisfăcute condiţiile (2.1), (2.4), (2.7) şi (2.8) pentru funcţionalele

a şi na , atunci şirul { }nu al soluţiilor ecuaţiilor variaţionale (2.6) converge tare

la soluţia u a ecuaţiei (2.3) şi are loc evaluarea

(2.9) 2

1 12{ ( ) ( )}n n n ne p u u J e p u J u

m

.

Demonstraţie. Punând n nv u în (2.6) şi folosind condiţiile (2.4), obţinem

2

0 1n n n nn n n nm u l u m u ,

Capitolul 3



de unde 1 0n nu m m . Cum discretizarea este stabilă, rezultă că şirul { }n np u

este mărginit. Deci există măcar un subşir { }n np u slab convergent la un element

z F . Conform definiţiei 1.5, z eE , adică există un y E astfel ca z ey .

Deci, în sensul definiţiei 1.4, nu converge slab la y. Atunci, luând în

consideraţie ipoteza de convergenţă a discretizării şi condiţia (2.7), putem scrie

pentru orice v E :

lim ( , ) ( , )n n nn

a u r v a y v

şi analog, conform lui (2.8),

lim ( , ) ( , )n nn

l r v l v

.

Deci dacă în (2.6) luăm n nv r v şi trecem la limită pentru n obţinem

( , ) ( , ),a y v l v v E ,

adică y u soluţia unică a ecuaţiei (2.3). Pentru orice subşir al lui { }n np u slab

convergent, obţinem aceeaşi limită eu, aşadar şirul { }n np u este convergent la eu

în topologia lui F.

Pentru a dovedi convergenţa tare, să considerăm expresia

( , ) ( , ) 2( , ) ( , )n n n n n n n n n n n n n na u r u u r u a u u u r u a r u r u .

Folosind însă ipotezele şi faptul că nu converge slab la u, obţinem

lim ( , ) lim( , ) ( , )n n n n nn n

a u u l u l u

,

lim ( , ) lim( , ) ( , )n n n n nn n

a r u r u u r u a u u

.

Deci lim ( , ) 2 ( , ) ( , ) 0n a u u a u u l u . Pe de altă parte

2

0n n n nm u r u ,

de unde rezultă convergenţa discretă a şirului nu la u. Conform lemei 1.2 de aici

rezultă convergenţa tare.


În sfârşit, pentru a deduce evaluarea (2.9), folosim identitatea

1 1 1 1 1( , ) ( , ) 2 ( , ) ( , )n n n n n n n n n na e p u u e p u u a e p u e p u a e p u u a u u

şi

1 1 1 11 1( ) ( ) ( , ) ( , ) ( , )

2 2n n n n n n n nJ e p u J u a e p u e p u a u u l e p u u

1 1 1 11( , ) ( , ) ( , )

2n n n n n n n na e p u u a e p u u e p u u l e p u

2

1

2n n

me p u u ,

ceea ce era de demonstrat.

Un caz special de discretizare este cea de tip Galerkin.

Fie E un spaţiu Hilbert şi { }nE un şir complet în E de subspaţii închise ale

lui E. Funcţionala pătratică (2.2) în ipotezele date aici, satisface condiţiile cerute

de teorema 1.5 şi deci şirul { }nu care satisface ecuaţiile

(2.10) ( , ) ( , ),n n n na u v l v v E ,

pentru fiecare n natural este convergent tare la punctul de minim unic u al

funcţionalei.

În cazul nostru putem obţine o evaluare a erorii în care se reflectă

importanţa alegerii şirului nE . Fie n nv E astfel încât l im 0nn

u v

, ceea ce

este posibil datorită completitudinii şirului nE . Avem

( , ) ( , ) 2 ( , ) ( , )n n n n n n n n n n na u v u v a u u u u a u u u v a u v u v ,

în care termenul din mijloc este zero căci ( , ) ( , )n n n n na u u v a u u v

( , )n nf u v , iar ultimul termen e pozitiv. Deci

2 2

( , ) ( , )n n n n n nm u u a u u u u a u v u v M u v ,

M fiind o evaluare a normei lui a, de unde

Capitolul 3



(2.11) n n

Mu u u v

m .

De aici rezultă că rapiditatea de convergenţă a şirului nu depinde de ordinul

aproximării elementelor lui E prin elemente ale şirului complet nE . Dar eficienţa

acestor metode nu depinde numai de alegerea spaţiilor nE , ci şi de complexitatea

problemelor discretizate (2.10) la care se ajunge. De obicei spaţiile nE sunt finit

dimensionale. Alegerea bazelor în aceste spaţii este foarte importantă în acest

sens.

Fie de exemplu pentru spaţiul 1

02[0,1]W , spaţiile 1 2{ , , , }n nE sp p p p

generate de polinoame liniar independente care se anulează în 0 şi 1, de exemplu

2 2 2

1 2 3(1 ), (1 ), (1 ) ,p x x p x x p x x . Cu această alegere ecuaţia

(2.10) este echivalentă cu sistemul de ecuaţii

(2.12) 1

( , ) ( , ) , 1,2, ,n

i j i

j

a p p l p i n

,

unde j sunt coordonatele lui nu în baza dată.

Dacă, de exemplu,

1 1

0 0

( , ) ( ) ( ) d ( ) ( ) da v w v t w t t v t w t t ,

matricea sistemului (2.12) nu conţine în general multe zerouri.

Fie acum nE mulţimea funcţiilor continue definite prin polinoame de

gradul întâi pe fiecare subinterval 1

, , 0,1, ,1 1

i ii n

n n

al intervalului

[0,1]. O bază în acest spaţiu este formată de exemplu din funcţiile

, 1,2, ,iq i n , continue, cu 1, ( )1

i i

iq q t

n

liniare în intervalul


1 1,

1 1

i i

n n

şi nule în rest. Este clar că iq are suportul 1 1

,1 1

i i

n n

şi deci

pentru sistemul

1

( , ) ( , ), 1,2, ,n

i j j i

j

a q q l q i n

,

avem

1 1

0 0

( , ) ( ) ( )d ( ) ( )d 0i j i j i ja q q q x q x x q x q x x

pentru două funcţii din bază cu suporturi disjuncte. Aşadar cu această alegere se

obţine un sistem liniar cu matricea de tip bandă, sistem pentru care volumul de

calcule necesar la rezolvarea sa numerică este mult redus faţă de un sistem

oarecare. Faţă de prima alegere unde pentru a obţine baza în spaţiul 1nE , nu

avem decât să mai adăugăm un element 1np liniar independent de celelalte, în

exemplul al doilea baza lui 1nE este complet diferită de cea din nE . Aceasta nu

constituie însă un impediment pentru că în aplicaţii ne limităm de obicei la o

singură evaluare nu despre care însă avem informaţii bune privind eroarea.

2.2. DISCRETIZAREA PROBLEMEI LUI DIRICHLET PENTRU ECUAŢII ELIPTICE PRIN METODA DIFERENŢELOR FINITE

Ca o aplicaţie, vom considera pe spaţiul 1

02 ( )W , unde m este un

domeniu mărginit, funcţionala pătratică 1

( ) ( , ) ( , )2

J v a v v f v cu

Capitolul 3



(2.13) 0

1

( , ) ( ) ( ) ( ) ( ) ( ) ( ) dn

i

i i i

u va u v A x x x A x u x v x x

x x

şi

(2.14) ( , ) ( ) ( )df v f x v x x

.

Aici , 0,1,2, ,jA j m sunt funcţii din ( )L care satisfac condiţiile de

elipticitate:

(2.15) ( ) 0, 0,1, ,jA x c j m , a.p.t. în ,

iar F este o funcţie de pătrat sumabil în . După cum s-a arătat în I 4.4

(exemplul 2) are un punct de minim unic — o funcţie din 1

02 ( )W — care este

soluţie generalizată a problemei lui Dirichlet

(2.16) 0

1

( ) ( ) ( ) ( ) ( ) 0,m

i

i i i

uA x x A x u x f x x

x x

,

( ) 0,u x x ,

unde este frontiera lui .

Pentru a discretiza această problemă vom considera mai întâi discretizarea

externă cu diferenţe finite a spaţiului 1

02 ( )W indicată în secţiunea 1.6. În cazul

nostru 2p şi spaţiul 1

02 ( )W este un spaţiu Hilbert cu produsul scalar

1

( , ) ( ) ( )d ( ) ( )dm

i i j

u vu v u x v x x x x x

x x

,

iar spaţiile nE introduse în secţiunea 1.6 sunt de asemenea spaţii Hilbert cu

produsele scalare:

2

1

(( , )) ( ) ( )d ( ) ( )dm m

m

n n n n in n in k

i

u v u x v x x n u x v x x

,

unde in sunt daţi în (1.29).


Pentru a construi funcţionalele discretizate vom defini

2

0

1

( , ) ( ) ( ) ( )d ( ) ( ) ( )dm

n n n i in n in n n n

i

a u v n A x u x v x x A x u x v x x

şi

( , ) ( ) ( )dn n nl v f x v x x

.

În cele ce urmează vom nota cu ( . ,. ) şi produsul scalar şi, respectiv, norma

din 2 ( )L .

Vom dovedi acum valabilitatea condiţiilor din teorema 2.1. Funcţionalele

:n n na E E sunt biliniare şi continuie căci

2

1

( , )m

n n n in n in n n n n nn ni

a u v M n u v u v M u v

,

oricare ar fi ,n n nu v E , unde 0

maxm

jj

M A

.

Condiţia de uniformă coercivitate este de asemenea satisfăcută deoarece

2 2 22

0

( , ) ( ) d ( ) d ,m

n n n in n n n n nni

a v v n v x x v x x c v v E

şi

( , ) ,n n n n n nnl v f v f v v E .

Condiţiile (2.7) şi (2.8) se verifică direct. Dacă n nv E converge slab la v E şi

n nw E converge tare la w E , aceasta revine conform topologiei lui

2 1( )mF L la l im , lim , 1,2, ,u

n i nn n

i

vv v n v i m

x

, în topologia slabă a

lui 2 ( )L şi l im , lim , 1,2, ,n in nn n

i

ww w n w i m

x

, în topologia normei

lui 2 ( )L . De aici

Capitolul 3



1

( , ) ( , ) ( ) ( ) ( )m

n n n i in in n

i i

wa v w a v w A n v x n w x x

x

( ) ( ) ( ) din n

i i

w vx n v x x x

x x

0( )[ ( )( ( ) ( )) ( )( ( ) ( ))]dn n nA x v x w x w x w x v x v x x

0 1

,m m

in n in n i in n

i ii i i

w w vM n v n w A n v

x x x

0( ,n n nM v w w A w v v ,

care tinde la zero când n în condiţiile date. Analog, se verifică şi (2.8).

Aşadar, conform teoremei 2.1, rezultă convergenţa tare a soluţiilor

n nu E ale ecuaţiilor variaţionale

(2.17) ( , ) ( , )n n n n na u v l v , n nv E ,

la soluţia generalizată în 1

02 ( )W a problemei lui Dirichlet (2.16). Aceasta

înseamnă

l im , lim , 1,2, ,n in nn n

i

uu u n u i m

x

,

în topologia lui 2 ( )L .

Spaţiile nE sunt finit dimensionale, după cum s-a văzut în secţiunea 1.6 şi

funcţiile ny , cu 1

ny , formează o bază în spaţiul nE . Deci rezolvarea

ecuaţiei variaţionale (2.17) este echivalentă cu rezolvarea sistemului:

1

1( , ) ( , ) ,

n

ny n ny nz n nz

y

a l z

,


în care necunoscutele ny sunt coordonatele lui nu în baza 1{ , }ny ny . Se știe

că, în condiţii foarte puţin restrictive pentru constantele C şi M sau pentru clasa

de funcţii din care fac parte coeficienţii kA , acest sistem de ecuaţii este cu

matricea pozitivă. Aceasta permite utilizarea unor metode numerice de rezolvare

cu iteraţii monotone foarte avantajos în calculele practice.

2.3. METODA ELEMENTULUI FINIT

Convergenţa obţinută în secţiunea precedentă pentru discretizarea

problemei lui Dirichlet prin metoda diferenţelor finite este destul de slabă. Vom

descrie aici un alt procedeu de discretizare a spaţiilor Sobolev şi a problemelor

eliptice care conduce la convergenţă în topologii mai puternice şi în acelaşi timp

la o rapiditate superioară.

Pentru aceasta să introducem unele noţiuni şi rezultate preliminare.

Să spunem că 1m puncte , 0,1, ,m

ia i m , de coordonate

1( , , )i mia a sunt în poziţie generală dacă vectorii 0{ – , 0,1, , }ia a i m sunt

liniar independenţi. În raport cu un astfel de sistem de puncte, coordonatele

baricentrice i ale unui punct 1( , , ) m

mx x x oarecare sunt unic

determinate de egalităţile

(2.18) 0 0

, 1m m

j ji i i

i i

x a

.

Capitolul 3



Intersecţia tuturor mulţimilor convexe din m , care conţin cele 1m

puncte (închiderea convexă a lor), poartă numele de m-simplex cu vârfurile ia .

El este mulţimea punctelor cu coordonatele baricentrice

(2.19) 0 1, 0,1, ,i i m .

Orice k-simplex, k m , generat de 1k dintre punctele { }ia este o k-faţă a

m-simplexului dat. Pentru 1k se obţine o muchie.

Propoziţia 2.1. Dacă , 0,1, ,ia i m sunt în poziţie generală şi

, 0,1, ,i i m sunt numere reale oarecare, atunci există un singur polinom

de gradul întâi u, astfel încât ( ) , 0,1, ,i iu a i m şi

(2.20) 0

( ) ( ),m

m

i i

i

u x x x

,

unde ( )i x sunt coordonatele baricentrice ale lui x.

Demonstraţie. Fie 0

1

( )m

j j

j

u x x

. Punând ( )i iu a obţinem

0

1

m

j ji i

j

a

, care are soluţie unică , 0,1, ,j j m în ipoteza că { }ia sunt

în poziţie generală. Relaţia (2.20) se verifică pentru , 0,1, ,jx a j m , căci

( )i j ija , simbolul lui Kronecker. Pentru un x oarecare rezultă atunci, din

liniaritatea coordonatelor, i ca funcţii de x (vezi 2.18).

Să dăm acum câteva proprietăţi diferenţiale ale coordonatelor i ca

funcţii de coordonatele carteziene , 1,2, ,jx j m .

Lema 2.1. Au loc egalităţile:

(2.21) 0

grad ( ) 0,m

i

i

x


(2.22) grad ( ) ( ) ( ), 0 ,i j ij ix a x x i j m .

Demonstraţie. (2.21) rezultă imediat derivând a doua egalitate (2.18). Din

(2.18) putem explicita

(2.23) 0

1

, 0m

i ij j i

j

b x b i m

,

unde { }, 0 ,ijb i j m , este inversa matricei sistemului (2.18) în i . Atunci

avem succesiv:

1 1

grad ( ) ( )m m

i j ik kj ik k

k k

x a x b a b x

0

1

, 0 ,m

ik kj i i i j i

k

b a b i j m

.

Lema 2.2. Dacă este marginea superioară a diametrelor tuturor

sferelor incluse în m-simplexul S, generat de { }ia , atunci

(2.24) 1

gard , 0i i m

,

unde cu am notat norma euclidiană în m .

Demonstraţie. Orice vector mx cu 1x poate fi scris sub forma

1 ( )x y z , unde ,y z S . Dacă notăm cu ( ), 0,1, ,i x i m ,

coordonatele baricentrice ale lui x, putem scrie folosind independenţa

gradientului lui i de punct şi (2.22),

1 , 0

1gard sup gard sup gard ( )( )

m

i i i i jx y z S j

x y a z

, ,0

1 1 1sup ( ) ( ) sup ( ) ( )

m

j ij i j jy z S y z Sj

y z y z

deoarece 0 ( ), ( ) 1, 0,1, ,j jy z j m .

Capitolul 3



Lema 2.3. Fie S şi S două m-simplexe cu vârfurile { }ia , respectiv

ˆ{ }, 0,1, ,ia i m , cu 0 0ˆa a şi , diametrul celei mai mici sfere care

conţine pe S, respectiv al celei mai mari sfere conţinute în S; ˆ ˆ, sunt

numerele similare pentru S . Dacă : m mB este un operator liniar

inversabil pentru care avem 0 0ˆ( ) , 1,2, ,i iB a a a a i m , atunci

(2.25) 1 ˆ,

ˆB B

.

Demonstraţie. Dacă mx cu 1x , există ˆˆ ˆ,y z S încât ˆ(1 )x

ˆ ˆ( )y z . Avem

0 0 0 0

1 1

ˆ ˆ ˆ ˆˆ ˆ( )( ) , ( )( )m m

i i i i

i i

y a y a a z a z a a

și atunci

0 0 0 0

1 1

ˆ ˆ ˆ ˆ( ) ( )( ), ( ) ( )( )m m

i i i i

i i

B y a y a a B z a z a a

,

de unde

0

1

ˆ ˆˆ ˆ( ) ( ) ( )m

i i i

i

B y z y z a a

deoarece ˆ ˆ0 ( ), ( ) 1i iy z . De aici rezultă ˆ

Bx

pentru fiecare mx cu

1x , adică prima inegalitate (2.25). Analog, se dovedește și cealaltă.

Fie acum m o mulțime deschisă și mărginită.

Definiţia 2.1. O familie T de m-simplexe în m formează o triangulaţie

admisibilă a lui dacă satisface condiţiile:

(2.26) S

S

T


şi

(2.27) , , Int Int ,S S S S S S T este o k-faţă sau ,

unde cu am notat mulţimea vidă.

Fiecărei triangulaţii admisibile T îi putem ataşa numerele:

(2.28) sup , inf , sup SS S

SS S S

TT T

,

unde S şi S au semnificaţiile din lema 2.3 pentru simplexul S. Evident,

, 1 .

Definiţia 2.2. Un şir , 1,2,n n T , de triangulaţii admisibile ale lui

este regulat dacă satisface condiţiile:

(2.29) l im 0nn

și , 1,2,n n

şi

(2.30) K compactă, ( ) , ( )n n

n n

S

n K n n K S K

T

,

în care n şi n au semnificaţiile din (2.28) pentru triangulaţia nT şi 0 este

independent de n.

Observaţie. În cazul 2m se poate arăta că pentru un simplex 2S ,

avem

1 2

sin2tg

2

S

S

,

unde este cel mai mic unghi al lui S. Deci semnificaţia condiţiei (2.29) este

aceea că în şirul de triangulaţii, unghiurile triunghiurilor nu trebuie să tindă la

zero.

La metoda elementului finit, funcţiile din spaţiile discretizării nE , vor fi

polinoame de interpolare pe simplexe. În legătură cu aceasta vom da următoarea

definiţie.

Capitolul 3



Definiţia 2.3. Fie un simplex mS şi Q o mulţime finită de q puncte

din S. Vom spune că Q este k-unisolventă dacă pentru orice q numere reale

, 1,2, ,i i q , există un polinom unic p de grad cel mult k definit pe S, în aşa

fel încât

( ) , , 1,2, ,i i ip z z Q i q .

Polinomul p se numeşte polinom de interpolare pe mulţimea Q.

Conform propoziţiei 2.1, vârfurile simplexului formează o mulţime

1-unisolventă.

Propoziţia 2.2. Vârfurile ia ale unui simplex S, împreună cu mijloacele

i jm ale muchiilor, formează o mulţime 2-unisolventă pe simplexul S, şi

polinomul de interpolare corespunzător este

(2.31) 2

0 , 0

( ) (2 ( ) ( )) ( ) 2 ( ) ( ) ( )m m

i i i i j ij

i i j

p x x x p a x x p m

.

Demonstraţie. Polinoamele de gradul doi pe m sunt de forma

2

0

1 1

( )m m

ij i i i i j i j

i i

x x x x

și conţin ( 1)( 2) 2m m parametri. Punctele

ia sunt în număr de 1m , iar i jm în număr de ( 1) 2m m . Aşadar, condiţiile de

interpolare determină în mod unic coeficienţii dacă sistemul obţinut are soluţii.

Dar se poate verifica direct că polinomul ( )p x dat de (2.31) satisface aceste

condiţii.

Mulţimi 3-unisolvente pot fi definite, de asemenea, considerînd vârfurile

simplexului, câte două puncte pe fiecare muchie, care împart muchia în trei părţi

egale şi în plus baricentrul simplexului (care are toate coordonatele baricentrice

egale între ele şi deci egale cu 1 1m ).


Fie acum { }, 1,2,n n T , un şir regulat de triangulaţii admisibile ale lui

. Să considerăm pe fiecare simplex nST , o mulţime SQ -unisolventă de

puncte şi să notăm cu n

n S

S

Q Q

T

. Vom lua ca spaţii nE de discretizare a lui

1

02 ( )W spaţiile funcţiilor continue, care sunt pe fiecare simplex nST

polinoame de grad cel mult k şi care se anulează pe frontiera domeniului.

Operatorii de prelungire np se definesc simplu prin

,n n n n np u u u E ,

căci 1

02( )nu W . Deci 1np şi discretizarea este stabilă. Operatorii de

restricţie :n nr E E se definesc prin

( ) ( )n nr u x u x ,

unde ( )nu x este polinomul de interpolare relativ la mulţimea SQ pe fiecare

simplex nST . Pentru a demonstra convergenţa discretizării să observăm că

pentru fiecare ( )u D care este dens în 1

02 ( )W avem

n n n np r u u r u u u u .

Deci va trebui să evaluăm norma diferenţei între o funcţie ( )u D şi

polinomul său de interpolare pe fiecare simplex.

Să considerăm în spaţiul 1

02 ( )W normele:

22

( ) dk

k

v D v x x

22

( ) dk

k

v D v x x

unde cu am notat multiindicele 1 2( , , , )m cu

1

m

i

i

și 1 2

1 2

1 2

m

m

m

Dx x x

.

Capitolul 3



Fie kP spaţiul polinoamelor de grad cel mult k pe şi 02( )k

kW P spaţiul cât al

lui 02 ( )kW faţă de kP cu normele

02inf , , ( )k

k

kk kp Pv v p v v v W P

,

şi, respectiv,

infk

k kp Pv v p

.

Lema 2.4. Dacă domeniul mărginit are frontiera Lipschitz-continuă,

atunci există ( )kC încât

02 ( ), ( )

k

kk kk

Wv v C v

P

.

Lema 2.5. Fie m deschisă, mărginită, cu frontiera Lipschitz-

continuă şi fie 0k fixat şi 0 1r k . Dacă 1

02 02( ) , ( )k rL W W astfel

ca p p , pentru orice kp P , atunci există 0C încât

(2.23) 1

021, ( )k

r kv v C I u v W

.

Demonstraţie. Avem pentru 1

02 ( ),k

kv W p P , v v

( )( )I v p , de unde deducem:

1

infk

r r kp Pv v v v I v p

şi (2.32) urmează din lema 2.4 şi definiţia normei în spaţiul cât.

În cele ce urmează vom spune că două mulţimi deschise ˆ, din m

sunt afin-echivalente dacă există o aplicaţie afină inversabilă ˆˆ:F x

ˆ ˆ( )F x Bx b , astfel ca ˆ( )F . Pentru fiecare funcţie v definită pe

vom considera funcţia v definită pe prin ˆ ˆ ˆ( ) ( )v x v Bx b . Unui operator


1

02 02( ( ), ( ))k rL W W îi ataşăm 1

02 02ˆˆ ( ( ), ( ))k rL W W definit prin

ˆ v v . Cu aceste notaţii avem lema următoare.

Lema 2.6. Fie şi , afin-echivalente. Atunci, pentru orice 02( )rv W

avem:

(2.33) 1 2

ˆ detr

r rv B B v

și

(2.34) 1 21 ˆdet

r

r rv B B v .

Demonstraţie. Într-adevăr, dacă r , putem scrie ˆr

D v B D v

deoarece ˆ ˆ( ) ( )v x v Bx b şi atunci

2 22 2 1

ˆ

ˆ ˆ ˆd d detr r

rr r

D v x B D v x B B v

,

unde B este norma euclidiană a matricei B , iar 1

det B

provine de la

schimbarea de variabilă din integrală. La fel se arată şi (2.34).

Rezultatul principal este următorul.

Teorema 2.2. Fie S un simplex din , 0m k fixat, 0 1r k şi

1

02 02( ( ), ( ))k rL W S W S astfel ca p p pentru toţi ( )kp P S . Atunci există

0C încât să avem:

(2.35) 1

1

0 021, ( )

kk

rr kv v C v v W S

,

unde şi au semnificaţiile din lema 2.3.

Demonstraţie. Fie S un simplex afin-echivalent cu S. După lema 2.6 avem

2 22 1 1

0 0

ˆ ˆdet detr r

i m

r i ii i

v B B v B B v

2

1 ˆdetm

rB B v

Capitolul 3



dacă presupunem că 1 1B , ceea ce are loc conform lemei 2.3 dacă ˆ

căci

1ˆ 11 B

h B

.

Obţinem

1 2 1 ˆˆ ˆ(det )r r

v v B B r v v .

Lema 2.5 ne dă însă

1

ˆ ˆˆ ˆkr

v v C I v

.

Apoi, folosind lema 2.6,

11 2 1 1 2

1ˆ(det ) (det )

r k

r kv v B B C I B B v

după lema 2.3,

1

1 1

ˆ ˆˆ

r k

r kr kv v C I v

,

de unde inegalitatea (2.35) cu 0 1

ˆˆˆ

r

kC C I

.

Consecinţa 2.1. Fie un şir regulat nT de triangulaţii admisibile ale

mulţimii şi fie ( )v D . Să notăm cu nv o funcţie continuă care este

polinom de interpolare de gradul cel mult k pe fiecare simplex nST relativ la o

mulţime k-unisolventă de puncte ale simplexului. Atunci

(2.36) 1

0 1, 0 1r k r

n n krv v C v r k

,

în care normele sunt luate pentru spaţiile 02 ( )r

nW , cu n

n

S

S

T

, iar n este

dat de (2.28).


Demonstraţie. Luând în teorema 2.2 nu u pe fiecare simplex nST şi

0u în rest, şi sumând integralele ce definesc normele în (2.35) după nST ,

obţinem normele pe n . Combinând condiţia (2.29) cu inegalitatea (2.35)

obţinem evaluarea (2.36).

În particular, pentru 1r se obţine

0 1, 1,2,k

n n kv v C v n

.

Ţinând seama şi de condiţia (2.30) pentru n suficient de mare suportul funcţiei v

este cuprins în n , astfel că are loc convergenţa discretizării definite mai sus.

Procedeul de discretizare a spaţiului 1

02 ( )W descris aici se numeşte

metoda elementului finit de ordin k dacă operatorii de restricţie au valori funcţii

continue, care sunt polinoame de gradul cel mult k pe fiecare simplex. Din

construcţia făcută mai sus se vede că astfel de discretizări se pot face pentru

orice spaţiu 02 ( )kW şi chiar se pot extinde cu uşurinţă la spaţiile 0 ( )k

pW ,

1 p . În propoziţiile 2.1 şi 2.2 s-a văzut cum se pot construi polinoamele de

interpolare de gradul 1 şi 2.

Dacă se consideră acum o problemă pătratică de minimizare ca în

secţiunea 2.1, dat fiind că spaţiile nE ale discretizării cu metoda elementului

finit sunt subspaţii ale lui E, se pot lua drept funcţionale discretizate restricţiile

la nE ale funcţionalei date. Astfel, problemele discretizate se reduc la ecuaţii de

forma (2.10) care sunt echivalente cu sisteme de ecuaţii liniare cu matrice-bandă

(vezi exemplul de la sfîrşitul secţiunii 2.1).

Capitolul 3



§3. METODE NUMERICE SPECIFICE

PROBLEMELOR FINIT DIMENSIONALE

Am văzut că prin discretizare problemele de optim din spaţii generale se

aproximează cu probleme definite în spaţii care sunt de cele mai multe ori de

dimensiune finită. Pentru a avea asigurat un grad înalt de aproximare, problema

discretizată este considerată într-un spaţiu cu dimensiune relativ mare. De aceea

pentru rezolvarea numerică a problemelor obţinute sunt necesare metode

specifice care ţin seama de dimensiunea mare a vectorilor cu care se lucrează.

Desigur că toate metodele descrise în capitolul precedent pentru spaţii

Banach oarecare se pot aplica şi problemelor finit dimensionale. În acest

paragraf vom descrie însă câţiva algoritmi în care este esenţială ipoteza că

spaţiul în care se lucrează are o bază finită şi deci nu se pot aplica în spaţii

infinit dimensionale.

3.1. METODELE LUI NEWTON DISCRETIZATE

În secţiunea 2.4 am arătat că prin înlocuirea hessianului în metoda lui

Newton cu aproximări consistente ale lui se obţin algoritmi care păstrează în

anumite condiţii proprietăţile metodei lui Newton de superliniaritate a rapidităţii

de convergenţă.


Fie : mf D o funcţie de două ori continuu diferenţiabilă cu

matricea hessiană 2( ) { , , 1,2, , }i jH x f x x i j m uniform pozitiv definită

în D, adică

(3.1) 2

0 0( ) , , 0, , mH x y y m y m x D y ,

unde produsul scalar a doi vectori este ( , ) Tv w w v , norma este cea euclidiană,

1 2( )Tv v v , iar 0m este o constantă independentă de x şi y.

Pentru a construi aproximări consistente ale hessianului vom considera

drept spaţiu al parametrilor 2mF (vezi definiţia II 2.2). Astfel putem lua

matrice de diferenţe divizate de forma

( , ) ( ) ( ) , , 1,2, ,i j j i j

i i

f fK x h x h e x h i j m

x x

sau

1

1 1

( , ) , , 1,2, ,j j

ik k ik k ij

k ki i

f fK x h x h e x h e h i j m

x x

Pentru 2

,m mx h . Mai general, vom lua matricea ( , )K x h cu elementele:

(3.2)

1 1

1 1

,

2 1

1

( , ) dacă 0,

dacă 0 .

j j

ik k ij j ik k ij

k ki i

i j i j

j

ik k ij

ki j

f fx h e h e x h e h

x x

K x h h

fx h e h

x x

cu [0,1] şi ke vectorii bazei naturale a spaţiului. Pentru 0 şi respectiv,

1 se obţin cele două cazuri de mai sus.

Teorema 3.1. Fie : mf D de două ori continuu diferenţiabilă

pe mulţimea deschisă D. Atunci pentru orice mulţime compactă 0D D , există

Capitolul 3



0r încât pentru 2

{ , }m

h ijD h h r , matricea 0: ( , )m m

hK D D L

definită de (3.2) este o aproximare consistentă a lui H pe 0D . Dacă, în plus,

hessianul satisface o condiţie Lipschitz:

(3.3) ( ) ( ) , ,H x H y x y x y D ,

atunci K este o aproximare tare consistentă pe 0D .

Demonstraţie. Vom folosi norma 1

1

m

i

i

v v

. Fie 1 { mD x ,

01, }x y y D D , care este evident compactă. H este uniform continuă

pe 1D , deci pentru orice 0 există 1 (0, ) încât

2 2

1 11( ) ( ) , , 1,2, , , , ,

i j i j

f fx y i j m x y D x y

x x x x

.

Fie 1rm

și

1

1

( )j

i j i j k

k

h h e

. Pentru orice hh D avem ( )ij ij jh h e

1 , , 1,2, ,mr i j m . Deci, pentru orice 0 1, ( )ij ij jx D x h h e D

şi pentru 0i jh avem

2 2

, ,( , ) ( ) ( , ) ( ( ))i j i j i j

i j i j

f fK x h x K x h x h

x x x x

2 2

( ( )) ( ) 2i j

i j i j

f fx h x

x x x x

.

Deci, pentru orice 0x D şi orice , ( ) ( , ) 2hh D H x K x h m , adică K este o

aproximare consistentă a lui H pe 0D .

În ipoteza suplimentară (3.3) avem 11 1( ) ( )H x H y x y din cauza

echivalentei normelor în n şi atunci


2 2

1 1( ) ( ) , ,

i j i j

f fx y x y x y D

x x x x

,

după definiţia normei matriceale subordonate normei vectoriale 1 . În acest caz,

putem scrie:

2

, 1 1

1

( , ) ( ) ( )m

i j ij ij ik

ki j

fK x h x h h h

x x

.

Deci

1 01 1( , ) ( ) ,H x h H x h x D ,

adică K este aproximare tare consistentă a lui H.

Consecinţa 3.1. Fie : mf D de două ori continuu diferenţiabilă

în mulţimea deschisă D, cu hessianul uniform pozitiv definit în D. Atunci există

1 0r şi 1 0 , încât pentru orice 0 1( , )u S u D , unde 1( , ) { mS u v ,

1}v u şi grad ( ) 0f u şi pentru orice 2m

nh cu ( )

1

n

ijh r ,

, 1,2, ,i j m , iteraţiile { }nu obţinute cu formula

(3.4) 1

1 ( , ) grad ( ), 0,1,2,n n n n nu u K u h f u n

se află toate în 1( , )S u şi converg la u când n . Dacă l im 0nn

h

,

convergenţa este superliniară.

Acest rezultat urmează din teorema precedentă prin aplicarea teoremei

II 2.5 care a fost demonstrată pentru spaţii Banach oarecare.

În particular, dacă luăm grad ( )n nh f u la fiecare iteraţie, obţinem

metoda lui Steffensen care în ipoteza suplimentară (3.3) converge cu rapiditate

pătratică în aceleaşi condiţii ca mai sus (teorema II 2.7). Pentru iniţializarea

iteraţiilor (3.4) pentru care rezultatul de mai sus ne asigură numai convergenţă

locală se pot utiliza iteraţiile lui Goldstein sau Armijo (teorema II 2.8).

Capitolul 3



3.2. METODELE SECANTEI

Dacă f este funcţie de o singură variabilă, metoda lui Newton discretizată

este în particular de forma

1

1

( ) ( )( )n n n

n n n

n

f u h f uu u f u

h

,

Unde 1nu poate fi interpretat ca fiind soluţia ecuaţiei liniare ( ) 0nl v , unde nl

este interpolata liniară a funcţiei f în punctele nu şi n nu h , adică

( ) ( )

( ) ( ) ( )n n nn n n

n

f u h f ul v v u f u

h

.

Fie acum : mf D o funcţie continuu diferenţiabilă de m variabile. Vom

generaliza procedeul de mai sus, construind o interpolată liniară de variabile

( )L v Kv a , unde K este o matrice pătratică de ordin m şi a un vector

m-dimensional. Pentru a construi interpolata în afara iteraţiei nu calculate la

pasul precedent mai sunt necesare m puncte ajutătoare (1) (2) ( ), , , m

n n nu n u . Dacă

vectorii (1) ( ), , , m

n n nu u u sunt în poziţie generală (vezi secţiunea 2.3), atunci

matricea K şi vectorul a sunt unic determinaţi de condiţiile:

(3.5) ( ) ( )grad ( ), grad ( ), 1,2, ,i i

n n n nKu a f u Ku a f u i m .

Într-adevăr, din (3.5) obţinem

( ) ( )( ) grad ( ) grad ( ), 1,2, ,i i

n n n nK u u f u f u i m ;

dacă notăm (1) (2) ( )[ , , , ]m

n n n n n n nH u u n u u u , această matrice este

nesingulară şi deci

(3.6) (1) (1) 1[grad ( ) grad ( ), ,grad ( ) grad ( )]n n n n nK f u f u f u f u H .

a se determină din (3.5):


(3.7) grad ( )n na f u Ku .

Dacă şi vectorii (1) ( )grad ( ), grad ( ), ,grad ( )m

n n nf u f u f u sunt în poziţie

generală, matricea K este nesingulară şi atunci din condiţia 1( ) 0nL u se

deduce

1 1 1

1 (grad ( ) ) grad ( )n n n n nu K a K f u Ku u K f u

.

Vom nota ( , )n nK K u H ţinând seama de (3.6) şi astfel obţinem

(3.8) 1

1 ( , ) grad ( )n n n n nu u K u H f u

care este metoda secantei generalizată. Ţinând seama de (3.6) formula (3.8) se

mai scrie:

(3.9) (1) ( )

1 [grad ( ) grad ( ), ,grad ( )m

n n n n n nu u H f u f u f u

1grad ( )] grad ( )n nf u f u ,

de unde rezultă că ipoteza privind vectorii (1) ( ), , , m

n n nu u u poate fi înlăturată

eventual. Totuşi, în această ipoteză, formula (3.8) aminteşte de metoda lui

Newton discretizată. Vom cerceta acum în ce condiţii se poate arăta că matricea

K este o aproximare consistentă. Aceste condiţii se referă la alegerea vectorilor

ajutători (1) ( ), , m

n nu u sau, echivalent, a vectorilor (1) (1) ,n n nh u u , ( )m

nh

( )m

n nu u coloanele matricei nH .

Definiţia 3.1. Vom nota cu ( )M mulţimea matricelor pătratice de ordin

1, [ , , ]mm H h h , cu coloanele neidentic nule şi astfel ca

(3.10) 1

1det , , 0

m

m

h h

h h

,

normele fiind cele euclidiene. O mulţime Q de matrice pătratice de ordin m se

spune că este o familie uniform nesingulară de matrice dacă există 0 încât

( )Q M .

Capitolul 3



Lema 3.1. O mulţime Q de matrice nesingulare de ordin m este o familie

uniform nesingulară dacă şi numai dacă există 0 , încât

(3.11)

11

1, , ,

m

m

h hH Q

h h

.

Demonstraţie. Fie Q o familie uniform nesingulară de matrice,

( )Q M , 0 . Fie

1

1 { [ , , ] ( ), 1, 1, , }m jK A a a M a j m .

1K este mărginită şi închisă, deci funcţia 1:f K definită prin 1( )f A A

fiind continuă este mărginită. Aşadar există 0 , încât 1A , pentru orice

1A K . Dacă 1 1

1ˆ, , , m mH Q H h h h h K

, de unde (3.11). Reciproc,

presupunem 1 ,H H Q . Notăm cu { , }S A A o sferă în mulţimea

matricelor de rază . Funcţia ( ) detg A A este continuă deci există 0 ca

det ,A S . Matricea 1H S prin ipoteză, deci 1ˆ ˆdet 1 detH H

1 , adică (1 )Q K .

Teorema 3.2. Fie : mf D de două ori continuu diferenţiabilă şi

fie Q o familie uniform nesingulară de matrice pătratice de ordin m. Atunci

oricare ar fi 0D D compactă, există 0r , încât pentru 0{hD H Q ,

0 }H r , matricele 0: ( , )m m

hK D D L date de

1 1

0( , ) [grad ( ) grad ( ), ,grad ( ) grad ( )]mK v H f v h f v f v h f v H

cu 1

0 [ , , ]mH h h , sunt aproximări consistente ale hessianului ( )H v pe 0D .

Dacă hessianul satisface în plus o condiţie Lipschitz (3.3), K este chiar o

aproximare tare consistentă.


Demonstraţie. Fie 0 astfel ca 1 0{ , , }D x x y y D să fie

inclusă în D. Hessianul este uniform continuu pe 1D ; deci există, pentru fiecare

0 , un 0 r încât pentru ( ) grad ( ) grad ( ) ( )G h f x h f x H x h , să

avem

0( ) , ,G h h x D h r .

Pentru orice 0H Q cu , 1,2, ,ih r i m și orice 0x D , putem scrie:

1 1

0( , ) ( ) [ ( ), , ( )]mK x H H x G h G h H

11 1

1 1

( ) ( ), , , ,

m m

m m

G h G h h hC

h h h h

,

conform lemei 3.1, C fiind o constantă independentă de 0H şi x. Aşadar K este o

aproximare consistentă a lui H pe 0D . În ipoteza suplimentară (3.3) avem

2( )G h h de unde rezultă uşor 0 1 0( ) ( )K xH H x C H .

Consecinţa 3.2. Fie : mf D , de două ori continuu diferenţiabilă

cu hessianul satisfăcând (3.1) şi u D cu grad ( ) 0f u . Atunci există 1 0r şi

1 0 încât, pentru orice 0 1( , )u S u şi orice ( ), 0nH M , cu 1nH r ,

iteraţiile (3.8) sunt toate în 1( , )S u şi converg la u. Dacă l im 0nn

H

,

convergenţa este superliniară, iar dacă în plus are loc şi (3.3) este chiar pătratică.

Să discutăm acum câteva alegeri particulare pentru (1)[ ,n n nH u u

( ), ]m

n nu u . Notând cu ,n ju coordonatele lui ( 1,2, , )nu j m , vom putea lua

în particular

( )

1, ,( ) , 1,2, ,i

n n n i n i iu u u u e i m ,

adică

1,1 ,1 1, ,diag[ , , ]n n n n n n nH u u u u ,

Capitolul 3



o matrice diagonală.

Dacă renotăm ( , ) ( , ),n n n n nK u H K u h h fiind vectorul cu componentele

diagonalei lui nH , metoda secantei (3.8) se scrie sub forma:

(3.12) 1

1 1( , ) grad ( )n n n n n nu u K u u u f u

,

formulă de recurenţă cu doi paşi. Este uşor de văzut că matricele diagonale

nesingulare formează o familie uniform nesigulară căci ele sunt în (1)M .

Din punct de vedere practic, metoda (3.12) implică 1m evaluări ale

gradientului la fiecare iteraţie.

O metodă iterativă cu 1m paşi se obţine luând

1 2[ , , , )n n n n n n m nH u u u u u u , adică ( )i

n n iu u ,

1,2, ,i m , care necesită la fiecare pas o singură evaluare a gradientului (în

nu ). În schimb, însă nu există criterii sigure de convergenţă a unui astfel de

proces.

3.3. METODELE GRADIENŢILOR CONJUGAŢI ŞI METRICII VARIABILE

Fie H o matrice simetrică şi pozitiv definită de ordin , mn l şi .

Considerăm funcţia pătratică

(3.13) ( ) ( , ) ( , ) , mf v Hv v l v v .

În secţiunea II 3.1 am introdus metodele gradienţilor conjugaţi pentru

aproximarea punctului de minim u al funcţionalelor pătratice care sunt aplicabile

în particular şi funcţiei f. În cazul acesta însă algoritmii au o particularitate foarte

importantă în aplicaţii: sunt finiţi.


Teorema 3.3. Fie dată funcţia pătratică (3.13) cu H simetrică şi pozitiv

definită. Dacă 0u este ales astfel încât 2 1

0 0 0 0, , , , mg Hg H g H g , cu

0 0g l Hu să fie liniar independente, atunci pentru metoda iterativă,

(3.14) 1 1 1 0 0, , ,n n n n n n n n n nu u h g l Hu h g h h g ,

unde

(3.15) 1( , ) ( , ), , 0,1,

( , ) ( , )

n n n nn n

n n n n

g g Hh gn

g Hh Hh h

,

există 1k m , încât 0kg şi atunci ku u .

Demonstraţie. Conform teoremelor II 3.2 şi II 3.3 şirul iteraţiilor (3.14)

generează vectori { }ng ortogonali unul pe altul. Cum ng sunt în spaţiul finit

dimensional m cel mult m dintre ei sunt nenuli. Deci după 1k m paşi cu

necesitate se obţine 0kg adică grad ( ) 0kf u , de unde ku u .

În realitate însă, din cauza erorilor de rotunjire care se acumulează la

calculul produselor scalare care intervin în (3.15), vectorii ng nu sunt exact

ortogonali şi atunci procesul nu se opreşte după 1k m paşi. Totuşi după

1m paşi 1mg este apropiat de zero şi atunci se poate relua algoritmul cu

0 1mu u şi se parcurg din nou 1m paşi. După un număr de 2-3 astfel de cicluri

în practică se obţin aproximări ale lui u cu precizie foarte bună.

Un algoritm specific spaţiilor finit dimensionale prin care se obţin de fapt

tot direcţii { }nh H-conjugate este metoda lui Fletcher-Powell foarte populară

datorită rezultatelor numerice bune pe care le dă. Algoritmul este următorul:

(3.16) 1 , grad ( ),n n n n n n n n nu u h g f u h H g ,

unde nH este un şir de matrice pătratice date de formula de recurenţă:

(3.17) 1 0

( ) ( ),

( , ) ( , )

T T

n n n n n nn n

n n n n n

H g H g u uH H H I

g H g u g

,

Capitolul 3



cu 1n n ng g g şi 1n n nu u u şi unde n sunt daţi de procedeul

descreşterii maxime

(3.18) 0

( ) min ( )n n n n nf u h f u h

.

Din (3.18) rezultă imediat

(3.19) 1( , ) 0, 0,1,n ng h n ,

de unde pentru funcţia pătratică (3.13) cu n ng l Hu obţinem

(3.20) ( , )

, 0,1,( , )

n nn

n n

g hn

h Hh

Lema 3.2. Matricele nH date de recurenţa (3.17) sunt simetrice şi pozitiv

definite dacă H este simetrică şi pozitiv definită.

Demonstraţie. Simetria rezultă inductiv din simetria termenilor

membrului drept al formulei (3.17). Să dovedim şi faptul că nH sunt pozitiv

definite tot prin inducţie. Pentru 00,n H I este evident pozitiv definită.

Presupunem că kH este pozitiv definită. Introducem produsul scalar

[ , ] ( , ) T

k kv w H v w w H v şi notăm cu 1 2[ , ]v v v norma corespunzătoare. Cu

aceste notaţii se scrie pentru orice mv :

2 2

2

1 2

1

[ , ] ( , )( , )

( , )

k kk

k k k kk

g v g vH v v v

h g gg

22 2 2

2 2

[ , ] ( , )k k k k

k k

v g g v h v

g g

,

care este nenegativă datorită inegalităţii lui Schwartz pentru produsul scalar

[ . ,. ] . Dacă 1( , ) 0kH v v , atunci 22 2[ , ] 0k kv g g v și ( , ) 0kh v .

Inegalitatea lui Schwartz este egalitate numai pentru vectori coliniari, deci


k k kv g Hh şi cum ( , ) ( , ) 0k k k kg h g Hg , rezultă ( , ) 0k kh Hh , care

implică 0kh . Aşadar 1kH este pozitiv definită şi lema este demonstrată.

Teorema 3.4. Dacă matricea H este simetrică şi pozitiv definită,

elementele construite cu algoritmul (3.16) — (3.19) satisfac relaţiile:

(3.21) ( , ) 0, , 1,2,n j j n jH Hh h h Hh j n n ,

şi după un număr finit de iteraţii 1k m obţinem 0kh şi ku u , punctul de

minim al funcţiei f.

Demonstraţie. Pentru a dovedi formulele (3.21) vom proceda prin inducţie

după n. Mai întâi să observăm că formula (3.17) se scrie echivalent sub forma

(3.21) 1 0

( ),

( , ) ( , )

T T

n n n n nn n n

n n n n n

H Hh H Hh hH H h H I

Hh H Hh h Hh .

Pentru 1n , avem 0H I şi 1 0 0 0 0 0H Hh Hh Hh h h ; apoi 1 0( , )h Hh

1 1 0 1 1 0 1 0( , ) ( , ) ( , ) 0H g Hh g H Hh g h , după (3.19). Să presupunem egalităţi-

le (3.21) adevărate pentru n k . Atunci, pentru j k ,

1( , ) ( , )

T T

k k k j k k j

k j j j

k k k k k

H Hh h Hh h h HhH Hh h h

Hh H Hh h Hh ,

iar pentru j k ,

1

( ) ( )

( , ) ( , )

T T

k k k k kk k k k k k k k

k k k k k

h HH Hh h HhH Hh H Hh H Hh h h

Hh H Hh h Hh .

Apoi, pentru 1j k ,

1 1 1 1 1 1( , ) ( , ) ( , ) ( , )k j k k j k k j k jh Hh H g Hh g H Hh g h .

Dacă 1, ( , ) 0k jj k g h după (3.19), pentru j k , avem succesiv

1 1( , ) ( , ) ( , ) ( , ) 0k j k k k j k j j jg h g Hh h g h g h .

Astfel formulele (3.21) sunt dovedite. De aici rezultă că vectorii nh sunt

H-conjugaţi, deci liniar independenţi. Cum spaţiul este finit dimensional, există

Capitolul 3



1k m încât 0k k kh H g . Cum kH este pozitiv definită, rezultă

gard ( ) 0k kg f u , adică ku u .

Algoritmul lui Fletcher-Powell are o mare stabilitate numerică în sensul

că erorile de rotunjire nu afectează rezultatul în aşa măsură încât să nu obţinem

soluţia într-un număr finit de paşi. De aceea de obicei nu sunt necesare reluări

ale algoritmului ca la metodele gradienţilor conjugaţi. De altfel, se poate arăta că

şirul { }nu construit cu acest algoritm coincide teoretic vorbind cu cel obţinut cu

metoda (3.14) — (3.15), dar erorile de rotunjire afectează în mai mare măsură pe

acesta din urmă. Totuşi, dacă dimensiunea m este foarte mare şi nu dispunem de

un calculator cu memorie internă mare este preferabil algoritmul (3.14) —

(3.15) în comparaţie cu metoda lui Fletcher-Powell care cere păstrarea în

memorie a două matrice H şi nH la fiecare iteraţie.

Algoritmul lui Fletcher-Powell este o variantă a metodelor metricii

variabile a lui Davidon care au comun faptul că direcţiile nh pe care se face

minimizarea funcţiei sunt obţinute cu formula n n nh H g , cu grad ( )n ng f u ,

unde { }nH este un şir de matrice pozitiv definite care generează astfel o

„metrică” la fiecare iteraţie. O altă variantă a acestor metode se obţine

construind şirul nH cu formula

(3.22) 1

1

( )( )

( , )

T

n n n n n nn n

n n n n

u H g u H gH H

u H g g

dacă numitorul este nenul şi 1n nH H dacă ( , ) 0n n n nu H g g . Se poate

uşor arăta că formulele (3.21) îşi păstrează valabilitatea şi pentru aceste matrice

şi că nH sunt simetrice şi pozitiv definite. De aici rezultă atunci, ca şi în teorema

precedentă, că soluţia u se obţine după un număr finit de păşi.


Să considerăm acum : mf D o funcţie oarecare continuu

diferenţiabilă de două ori în D cu matricea hessiană ( )H x uniform pozitiv

definită, adică satisfăcând (3.1). Convergenţa metodelor gradienţilor conjugaţi a

fost demonstrată în capitolul al II-lea pentru funcţionale definite pe un spaţiu

Banach oarecare. La aplicarea acestor metode pentru funcţii se programează

algoritmul în cicluri de câte 1m iteraţii, la fiecare nou ciclu neiniţiindu-se

algoritmul. Acest mod de lucru este justificat de faptul că local funcţia se poate

aproxima cu o funcţie pătratică şi de teorema 3.3.

În ceea ce priveşte algoritmul lui Fletcher-Powell convergenţa iteraţiilor

în cazul general a fost demonstrată destul de recent de Powell. Teorema lui

Powell este următoarea:

Teorema 3.5. Fie funcţia f de trei ori continuu diferenţiabilă în 0uW

0{ , ( ) ( )}mv f v f u cu hessianul uniform pozitiv definit în 0uW . Atunci

şirul { }nu , obţinut cu metoda lui Fletcher-Powell (3.16) — (3.17), converge la

punctul unic u de minim al funcţiei f.

Demonstraţie. Vom schiţa modul de demonstraţie fără a intra în detalii.

Mai întâi se poate arăta că lema 3.2 rămâne valabilă şi în cazul nostru mai

general. Într-adevăr, în prima parte a demonstraţiei acestei leme — când se

dovedeşte că 1( , ) 0kH v v — nu se foloseşte faptul că funcţia este pătratică,

deci această inegalitate se păstrează şi aici. Acum, dacă 1( , ) 0kH v v , rezultă

kv g şi ( , ) 0kh v , adică ( , ) 0k kh g . Formula lui Taylor cu rest integral

ne dă însă

1

1

0

( ) dk k k k k k kg g g H u t h h t ,

şi deci

Capitolul 3



12

0

0

0 ( ( ) , )dk k k k k kH u t h h h t m h ,

de unde 0kh , adică 0kg şi deci 0v . Rezultatul principal al lui Powell

este existenţa constantelor , 0m M încât şirul matricelor nH satisface

(3.23) 2 2

( , ) , 0,1,nm y H y y M y n .

Demonstraţia acestei inegalităţi duble este laborioasă şi constituie cheia întregii

demonstraţii. De aici rezultă imediat

( , )

gard ( ) , n n n nn n

n n n

h g H g mJ u g

h H g M

,

ceea ce arată că n nh h sunt direcţii de convergenţă pentru iteraţiile

1n n n nu u h (vezi secţiunea II 1.2, inegalitatea (1.28)). Cum { }n daţi de

metoda descreşterii maxime (3.18) sunt factori de convergenţă pentru aceste

iteraţii (secţiunea II 1.4), rezultă convergenţa tare a şirului nu , conform

teoremelor de convergenţă a metodelor de descreştere.

Rapiditatea de convergenţă este superliniară şi în plus algoritmul este

stabil numeric ceea ce îl recomandă ca unul dintre cele mai eficiente procedee

de minimizare în m .

3.4. ALGORITMI CARE EVITĂ CALCULUL DERIVATELOR. METODA VARIAŢIILOR LOCALE ŞI METODELE LUI ZANGWILL


Toate metodele de minimizare descrise până acum cer calculul

gradientului funcţiei în unul sau mai multe puncte la fiecare iteraţie. Vom indica

acum algoritmi care nu necesită calculul derivatelor la aplicarea lor practică.

Un astfel de algoritm — poate cel mai simplu care este cunoscut — este

metoda variaţiilor locale a lui Baniciuk. Fie f o funcţie de m variabile oarecare.

Algoritmul este următorul (fără criteriu de oprire):

Date: 0 0, 0mu , subrutină pentru funcţia f.

Pas 1. Pune 00,n u u .

Pas 2. Calculează ( )f u .

Pas 3. Pune n .

Pas 4. Pune 1i .

Pas 5. Calculează ( )if u d .

Pas 6. Dacă ( ) ( )if u d f u , pune iu u d şi treci la Pasul 4; în caz

contrar treci la Pasul 7.

Pas 7. Dacă 2i m , pune 1i i şi treci la Pasul 5; în caz contrar treci la Pasul 8.

Pas 8. Pune 1 1, , 12

n nu u n n

şi treci la Pasul 3.

Aici am notat cu 2 1 2,i i i id e d e , pentru 1,2, ,i m , direcţiile pozitive şi

negative de coordonate, astfel că la pasul 6 o singură componentă a lui u este

modificată de fiecare dată. Teorema de convergenţă a şirului { }nu este

următoarea.

Teorema 3.6. Dacă : mf D este convexă şi dacă există 0u D

astfel ca 0 0( ) { , ( ) ( )}W u v D f v f u să fie mărginită, atunci şirul { }nu dat

de algoritmul de mai sus are puncte de acumulare şi acestea sunt puncte de

minim ale funcţiei.

Capitolul 3



Demonstraţie. În ipotezele date există puncte de minim. La pasul 6 există

posibilitatea aparentă ca algoritmul să se cicleze între acest pas şi pasul 5, fără a

ajunge niciodată să treacă la pasul următor. În ipotezele noastre aceasta nu este

însă posibil, pentru că toţi iu d construiţi la pasul 6 aparţin lui 0( )W u care

este mărginită. Deci după un număr finit de paşi vom găsi un vector care iese din

0( )W u şi va fi satisfăcută inegalitatea care asigură trecerea la pasul 7. La acest

stadiu deoarece sunt 2m valori pe care le poate lua i, se ajunge la pasul 8 şi deci

la o nouă iteraţie. Deci şirul { }mu este infinit şi are puncte de acumulare, căci

0( ),nu W u n . Fie u un punct de acumulare al şirului

l im nn

u u

.

0( )nu W u căci funcţia este convexă şi deci continuă în Int D. Din modul de

construcţie al şirului avem

1( ) ( ), 1,2, ,2n n i nf u d f u i m .

Funcţia fiind convexă există diferenţialele laterale direcţionale şi atunci putem

scrie:

1 1 1( ) ( ) ( , )n n n i n n i n if u f u d f u d d ,

de unde

1 1 10 ( ) ( ) ( , )n n i n n n n i if u d f u f u d d 1 1( , )n n n i if u d d

.

Prin construcţie, 1lim( )n n in

u d u

şi după teorema I 3.9 rezultă atunci

10 lim sup ( , ) ( , ) , 1,2, ,2n n i i i in

f u d d f u d L i m

.

Aşadar,

2 2 1( , ) ( , ) 0 ( , ) , 1,2, ,i i i i iL f u e f u e f u e L i m .

Conform consecinţei I 3.4 aceasta înseamnă că oricare ar fi un subgradient

1 2( , , , )mu u u u al funcţiei f în u, avem


2 2 1, 1,2, ,i i iL u L i m

.

Deci vectorul nul este un subgradient în u, adică u este punct de minim al

funcţiei (teorema I 4.9).

Consecinţa 3.3. Dacă f este strict convexă, şirul nu converge la punctul

de minim unic al funcţiei.

În general, convergenţa acestui procedeu este lentă-comparabilă cu

convergenţa lui (1 2)n când n , dar algoritmul are avantajul simplităţii şi nu

cere calculul gradientului. În scopul măririi rapidităţii de convergenţă s-au

propus algoritmi care de asemenea, fără a cere calculul derivatelor, sunt similari

într-un anumit sens cu metodele direcţiile conjugate. Înainte de a descrie un

astfel de algoritm, să definim un algoritm de acelaşi tip cu precedentul, dar mai

sofisticat. Această metodă construieşte succesiv seturi de vectori liniar

independenţi şi minimizează funcţia pe fiecare direcţie. Algoritmul lui Zangwill

este următorul:

Date: 1,0 , (0,1]mu , subrutină pentru calculul funcţiei f, subrutină

pentru calculul minimului pe o direcţie.

Pas 1. Pune 1, 1( 1,2, , ) 1i id e i m şi 1n .

Pas 2. Calculează , ( 1,2, , )n rt r m ca

, 1 , , , 1 ,( ) min ( )n r n r n r n r n rt

f u t d f u td

și pune

, , 1 , , ( 1,2, , )n r n r n r n ru u t d r m .

Pas 3. Calculează , ,0

, ,0 , 1

( ),

n m n

n n m n n m

n

u uu u d

şi , 1n mt încât

, , 1 , 1 , , 1( ) min ( )n m n m n m n m n mt

f u t d f u td

.

Pune , 1 , , 1 , 1 1,0 , 1,n m n m n m n m n n mu u t d u u .

Pas 4. Calculează , ,max{ , 1,2, , }n s n rt t r m . Dacă ,n s n nt , pune

Capitolul 3



1, , 1n s n md d , 1, ,n r n rd d pentru r s şi ,

1

n c n

n

n

t

. Dacă

,n c n

n

t

, pune 1, , ( 1,2, , )n r n rd d r m şi 1n n .

Pas 5. Pune 1n n şi treci la Pasul 2.

Testul de oprire al algoritmului va rezulta din teorema de convergenţă,

înainte de aceasta să dovedim lema următoare.

Lema 3.3. Vectorii ,1 ,2 ,, , ,n n n md d d sunt liniar independenţi pentru

fiecare n şi ,1 ,det[ ]n n m nd d .

Demonstraţie. Pentru 1,1, i in d e şi 1 1det[ , , ] 1ne e .

Presupunem relaţia din enunţ adevărată pentru un n natural. Atunci putem scrie,

conform algoritmului,

1,1 1, ,1 , 1 , 1 , 1 ,

, , ,

,1 , 1 , 1 , 1

1

det[ , , ] det[ , , , , , , ]

det , , , , , ,

n n m n n s n m n s n m

mn r n r n s n

n n s n s n m n

r n n

d d d d d d d

t d td d d d

dacă suntem în primul caz de la pasul 4. În celălalt caz vectorii nu se schimbă şi

1n n .

De aici se vede că rolul lui este de a evita să se piardă liniara

independenţă din cauza erorilor de rotunjire.

Teorema de convergenţă este următoarea:

Teorema 3.7. Dacă funcţia : mf D este strict convexă pe

mulţimea deschisă D şi dacă există 1,0u D încât 1,0( ) {W u v D ,

1,0( ) ( )}f v f u este mărginită, atunci şirurile ,{ }, 1,2, ,n ru r m , au aceeaşi

limită pentru n şi anume punctul de minim unic al funcţiei.


Demonstraţie. Să observăm că , 1, 1,2, ,n rd r m şi , 1,0{ } ( )n ru W u ,

0,1,2, , ,r m n , conform algoritmului astfel că se pot extrage subşirurile

convergente , ,( 1,2, , ), ( 0,1, , )n r r n r rd d r m u u r m când n . Să

arătăm că ru sunt egali între ei. Putem scrie

(3.23) 1 , 1 ,( ) lim ( ) lim ( ) ( )r n r n r rn n

f u f u f u f u

.

Însă , 1 , , 1( ) ( ),n r n r n rf u f u td t , implică din cauza continuităţii

funcţiilor convexe (consecinţa I 3.1),

(3.24) 1 1( ) ( ),r r rf u f u td t .

Dacă notăm 1 , 1l imr n rn

t t

, obţinem

(3.25) 1 1 1r r r ru u t d .

Pentru indicele ( 1)n următor în subşir putem scrie, conform algoritmului,

( 1) , , 1( ) ( )n r n rf u f u , de unde

1( ) ( )r rf u f u .

Comparând cu (3.23), obţinem 1( ) ( )r rf u f u . Din cauza strictei convexităţi,

urmează pentru (0,1) şi 1r ru u :

1 1( (1 ) ) ( ) (1 ) ( ) ( )r r r r rf u u f u f u f u

în timp ce, după (3.25) şi (3.24),

1 1 1( (1 ) ) ( (1 ) ) ( )r r r r r rf u u f u t d f u ,

absurd. Deci 1, 0,1,2, , 1r ru u r m , adică toate punctele limită sunt egale.

Să notăm cu u valoarea lor comună. După (3.24) avem

(3.26) ( ) ( ), , 1,2, ,rf u f u td t r m .

De aici rezultă, luând întâi 0t convergent la zero şi împărţind la t şi apoi la fel

pentru 0t ,

(3.27) ( , ) 0 ( , ), 1,2, ,r rf u d f u d r m .

Capitolul 3



Conform lemei 3.3, ,1 ,det[ , , ] ,n n md d n şi atunci, deoarece , 1n rd , la

limită obţinem 1det[ , , ] 0md d , adică direcţiile { }rd sunt liniar

independente. Aşadar, subgradienţii în u ai funcţiei sunt vectorii u din m ,

care satisfac

( , ) ( , ) ( , ) , 1,2, ,r r rf u d u d f u d r m

.

Cum vectorul 0u satisface această inegalitate dublă, rezultă că 0 este

subgradient în u, adică u este punct de minim absolut al lui f. Unicitatea

punctului de minim asigură convergenţa şirurilor ,{ }, 0,1, ,n ru r m la acest

punct.

O variantă îmbunătăţită a acestui algoritm care a fost dată tot de Zangwill

este următoarea:

Date: 0

mx , matricea 1,1 1,[ ]md d cu 1, 1rd , pentru 1,2, ,r m ,

subrutină pentru calculul funcţiei f şi subrutină pentru minimul pe

o direcţie.

Pas 1. Calculează 0,mt pentru care 0 0, 1, 0 1,( ) min ( )m m mt

f x t d f x td şi

pune 0, 1 0 0, 1,m m mx x t d ; pune 1, 1l n .

Pas 2. Pune k l , calculează încât 1, 1 1, 1( ) min (n m k n mt

f x e f x

)kte , pune s k , înlocuieşte pe k cu 1 mod ulok m . Dacă

k l , stop.

Pas 3. Dacă 0 , pune ,0 1, 1 ,n n mx x e l k şi treci la Pasul 4; în

caz contrar, treci la Pasul 2.

Pas 4. Calculează succesiv , , 1,2, ,n rt r m , încât , 1 , ,( )n r n r n rf x t d

, 1 ,min ( )n r n rt

f x td şi pune , , 1 , ,n r n r n r n rx x t d .


Pas 5. Calculează , 1, 1

, 1

, 1, 1

( )n m n m

n m

n m n m

x xd

x x

şi , 1n mt încât

, , 1 , 1( )n m n m n mf x t d , , 1min ( )n m n m

tf x td

;

pune , 1 , , 1 , 1n m n m n m n mx x t d .

Pas 6. Pune 1, , 1, 1,2, ,n r n rd d r m , pune 1n n şi treci la Pasul 2.

Algoritmul de mai sus are o oprire la pasul 2, în care caz 1, 1n mx este

soluţia problemei dacă ipotezele teoremei 3.7 sunt satisfăcute. Într-adevăr,

această oprire are loc dacă 0 de m ori succesiv, adică dacă avem

1, 1 1, 1( ) ( ), 1,2, ,n m n m kf x f x te k m .

Urmând acelaşi raţionament ca în demonstraţia teoremei precedente, de aici

rezultă imediat că 0 este subgradient în 1, 1n mx , adică în acest punct este atins

minimul absolut al funcţiei. Vom arăta că, în cazul funcţiilor pătratice, se ajunge

la stop într-un număr finit de iteraţii. În acest scop vom dovedi mai întâi două

leme.

Lema 3.4. Fie 1

( ) ( , ) ( , )2

f x Ax x b x , cu A o matrice simetrică şi

pozitiv definită. Dacă pornind din punctele 1x şi 2x pe direcţia p, funcţia f este

minimizată în 1x , respectiv 2x , atunci vectorul 1 2x x este A-conjugat cu p,

adică 1 2( ( ), ) 0A x x p .

Demonstraţie. Prin ipoteză 1 1 2 2( ) min ( ), ( ) min (t t

f x f x tp f x f x

)tp . Cum grad ( )f x Ax b , urmează 1 2( , ) ( , ) 0Ax b p Ax b p , de

unde 1 2( ( ), ) 0A x x p .

Lema 3.5. Fie 1p şi 2p două direcţii A-conjugate și 1 2 3, ,x x x astfel încât

2 1 1 3 2( ) min ( ), ( ) min ( )t t

f x f x tp f x f x tp . Atunci

Capitolul 3



3 1 1 2,

( ) min ( )t s

f x f x tp sp .

Demonstraţie. Fie 2 1 1 1x x t p și 3 2 2 2x x t p . Conform ipotezei,

2 1( , ) 0Ax b p şi 3 2( , ) 0Ax b p . În plus, 3 1 2 2 2( , ) (Ax b p Ax t Ap

1 2 1 2 2 1, ) ( , ) ( , ) 0b p Ax b p t Ap p . Deci 3 1 2( , ) 0Ax b tp sp , de unde

concluzia.

Teorema 3.8. Dacă 1

( ) ( , ) ( , )2

f x Ax x b x cu A simetrică şi pozitiv

definită, atunci iteraţiile de mai sus se opresc la pasul 2 după un număr de cicli

q m .

Demonstraţie. Vom arăta că pentru fiecare n m , direcţiile , 1n m nd ,

, 2 ,, ,n m n n md d sunt A-conjugate. Pentru 1n aceasta este adevărat, căci o

singură direcţie este A-conjugată: 1, 1,( , ) 0m mAd d . Dacă la iteraţia n, aceste

direcţii sunt A-conjugate şi nu ne oprim la pasul 2, atunci 1, 1 ,0n m nx x , deci

1, 1 ,n m n mx x şi , 1 0n md . Mergând înapoi, la iteraţia 1n , 1, 1n mx s-a obţinut

prin minimizare succesivă pe direcţiile 1, 1 1, 1,1, , ,n m n m nd d d , care sunt apoi

după pasul 6 respectiv , , 1 ,0, , ,n m n m nd d d . Cum , , 1 , 1, , ,n m n m n m nd d d sunt A-

conjugate după ipoteza de inducţie, conform lemei 3.5, rezultă că 1, 1n mx

realizează minimul lui f pe orice vector din spaţiul generat de aceste direcţii.

La fel, la iteraţia ,, n mn x realizează minimul lui f pe orice vector din

acelaşi spaţiu, dar pornind din alt punct. Conform lemei 3.4, , 1, 1n m n mx x , adică

, 1n md este A-conjugat cu toate direcţiile de mai sus. Ţinând seama de pasul 6,

inducţia este completă. Aşadar cel mai târziu la iteraţia de rang m, vom ajunge la

direcţiile ,1 ,, ,m m md d A-conjugate şi deci liniar independente. La pasul 4 al

iteraţiei de rang 1n m , vom fi minimizat succesiv pe aceste m direcţii şi deci


1, 1m mx este punctul de minim. Prin urmare la pasul 2 al iteraţiei următoare, de

rang n m , vom ajunge la oprire.

În cazul general se poate dovedi o teoremă asemănătoare cu teorema 3.7.

Teorema 3.9. Fie : mf D strict convexă, astfel că există 0x D

încât 0( ) {W x x D , 0( ) ( )}f x f x este mărginită. Atunci şirurile ,{ }n rx

1,2, ,r m , construite cu algoritmul de mai sus, sunt convergente la punctul

de minim unic al funcţiei.

Demonstraţie. Întrucât nu diferă prea mult de cea a teoremei 3.7, vom

schiţa numai demonstraţia acestei teoreme.

Şirurile ,{ }n rx sunt mărginite conform construcţiei pentru că fac parte din

0( )W x . Va exista atunci mulţimea K de indici încât

, ,lim , 0,1, , 1, 0,1, , 1n j r i rn K

x x r m j m

.

Luând o submulţime a lui K pentru care şi direcţiile pe care se fac minimizările

în cursul algoritmului să conveargă şi aplicând un raţionament similar cu cel din

teorema 3.7, vom putea arăta că punctele limită coincid:

, , 0,1, , , 0,1, , 1j rx x j m r m .

Cum am considerat rezultatele a m cicluri consecutive în algoritmul nostru,

lucrând cu ,n j rx pentru 0,1, , 1j m , rezultă că toate direcţiile de coordonate

sunt folosite în minimizare pentru fiecare n când j şi r variază. Va rezulta atunci

( ) ( ), , 1,2, ,rf x f x te t r m , de unde urmează concluzia.

Fiind o metodă exactă pentru funcţii pătratice, ne putem aştepta la o

rapiditate bună de convergenţă a acestui algoritm ca şi în cazul metodelor

gradienţilor conjugaţi. Deşi rezultate de această natură nu sunt încă demonstrate

se pare, procedeul este în practică printre cel mai eficient din clasa metodelor

care nu cer calculul derivatelor.

Capitolul 3



3.5. METODE DE MINIMIZARE A UNEI FUNCŢII DE O SINGURĂ VARIABILĂ

Atât în capitolul acesta cât şi în capitolul al II-lea deseori intervin

subrutine intermediare de minimizare pe o direcţie, de obicei pe o semidreaptă.

Aceste probleme sunt în fond probleme de minimizare a unei funcţii de o

singură variabilă.

Algoritmii de minimizare pe o direcţie sunt în genere de două tipuri:

metode de comparare şi metode de aproximare. Metodele din prima categorie

determină un şir de intervale incluse unul în altul care conţin un punct de minim,

prin compararea valorilor funcţiei în puncte succesive. Aceste procedee nu

apelează la derivate şi se caracterizează prin simplitate, dar în acelaşi timp prin

convergenţă lentă. Următoarea lemă stă la baza acestor metode.

Lema 3.6. Fie funcţia : [0, ]f convexă. Dacă există 1 20 şi

3 1 2( , ) astfel încât 3 1( ) ( )f f şi 3 2( ) ( )f f , atunci f are cel puţin

un punct de minim absolut în intervalul deschis 1 2( , ) şi pentru orice

1 3( , )y , avem 1( ) ( )f y f , iar pentru 3 2( , )y , corespunzător

2( ) ( )f y f . Apoi, dacă există 1 0 încât 1( ) (0)f f , există puncte de

minim absolut în intervalul semideschis 1[0, ) şi 1(0, )y implică

1( ) ( )f y f . În sfârşit, dacă pentru 3 1 2( , ) are loc 1 3( ) ( )f f

2( )f , tot segmentul 1 2[ , ] este format din puncte de minim absolut ale

funcţiei.


Demonstraţie. Funcţia convexă f este continuă (consecinţa I 3.1) şi atunci,

după teorema lui Weierstrass, pe intervalul închis 1 2[ , ] admite cel puţin un

punct de minim care nu poate fi în capetele intervalului datorită ipotezelor. Deci

este vorba de un punct de minim local, dar pentru funcţii convexe aceasta este

suficient ca el să fie punct de minim absolut (teorema I 4.9). Pentru 1 3( , )y ,

adică 1 3(1 )y t t cu (0,1)t , avem

1 3 1 1 1( ) ( ) (1 ) ( ) ( ) (1 ) ( ) ( )f y tf t f tf t f f .

Analog, rezultă şi cealaltă implicaţie care dovedeşte prima parte a lemei. Dacă

aplicăm teorema lui Weierstrass în intervalul 1[0, ] şi facem un raţionament

similar, obţinem şi cea de-a doua afirmaţie. În sfârşit, dacă

1 3 2( ) ( ) ( )f f f , pentru orice 1 3( , )y , avem 3( ) ( )f y f , căci

dacă am avea 2( ) ( )f y f ar rezulta 3 2( ) ( (1 ) ) ( )f f y f y

2 2(1 ) ( ) ( )f f , contrar ipotezei. La fel se arată că şi pentru 3 2( , )z

are loc 1( ) ( )f z f . Deci funcţia este constantă în intervalul 1 3[ , ] , adică are

derivata nulă şi deci toate punctele intervalului sunt puncte de minim.

Algoritmul înjumătăţirii, cel mai simplu dintre metodele de comparaţie,

are următoarea formă:

Date: 0, 0 , subrutină pentru funcţia f.

Pas 1. Calculează (0)f şi ( )f .

Pas 2. Dacă ( ) (0)f f , pune 0 0 00, ,2

a b c

şi treci la Pasul 7, în

caz contrar, treci la Pasul 3.

Pas 3. 0 11, 0,i .

Pas 4. 1i i .

Pas 5. Calculează 1( )if .

Capitolul 3



Pas 6. Dacă 1( ) ( )i if f , pune 0 1 0 1 0, ,i i ia b c şi treci la

Pasul 7; în caz contrar pune 1i i şi treci la Pasul 4.

Pas 7. Pune 0j .

Pas 8. j j jl b a .

Pas 9. jl , pune jc şi stop; în caz contrar treci la Pasul 10.

Pas 10. Pune ( ) ( )

,2 2

j j j j

j j

a c c bv w

, calculează ( ), ( )j jf v f w .

Pas 11. Dacă ( ) ( )j jf v f c , pune 1 1 1, ,j j j j j ja a b c c v ; dacă

( ) ( )j jf w f c , pune 1 1 1, ,j j j j j ja c b b c w ; în caz

contrar, pune 1 1 1, ,j j j j j ja v b w c c .

Pas 12. Pune 1j j şi treci la Pasul 8.

Teorema 3.10. Algoritmul înjumătăţirii furnizează într-un număr finit de

paşi o aproximare a punctului de minim, situată la mijlocul unui interval de

lungime mai mică decât în care se găseşte acest punct de minim.

Demonstraţie. Prin paşii 1 – 6 se găseşte într-un număr finit de iteraţii un

interval iniţial 0 0( , )a b în care se află un punct de minim, astfel că punctul 0c din

mijlocul intervalului satisface condiţiile lemei 3.6: 0 0( ) ( )f c f a ,

0 0( ) ( )f c f b . Apoi, în următorii paşi se rafinează intervalul iniţial prin

înjumătăţire, până când se ajunge la intervalul de lungime jl . La pasul 11,

dacă ( ) ( )j jf v f c , în segmentul [ , ]j ja c avem ( ) ( ), ( ) ( )j j j jf v f a f v f c ,

adică avem situaţia din lema 3.6, care ne asigură că în acest interval de lungime

2

jl există un punct de minim. Dacă ( ) ( )j jf w f c avem o situaţie similară în

intervalul [ , ]j jc b . Dacă însă ( ) ( )j jf v f c şi ( ) ( )j jf w f c , în intervalul


[ , ]j jv w se află punctul de minim. În caz de egalitate, avem un segment de

puncte de minim (funcţia nu este strict convexă), iar în caz de inegalitate,

punctul de minim este în intervalul deschis ( , )j jv w şi din nou am reuşit o

înjumătăţire a intervalului. Astfel, după un număr finit de paşi se găseşte un

interval de lungime mai mică sau egală cu în care se găseşte cu siguranţă un

punct de minim.

Algoritmul înjumătăţirii este lent ca toate metodele de comparaţie, dar în

plus cere la fiecare pas în rafinare, calculul valorilor funcţiei în 5 puncte, dintre

care în trei sunt cunoscute valorile de la iteraţia precedentă. Vom descrie acum

un alt algoritm în care la fiecare iteraţie de rafinare se compară valorile funcţiei

în numai patru puncte, dintre care numai una trebuie calculată, celelalte fiind

cunoscute, dinainte. Aceasta este metoda secţiunii de aur sau a lui Fibonacci.

Date: 1 20, 0, (3 5) 2, ( 5 1) 2k k , subrutină pentru

valorile funcţiei f.

Pas 1. Calculează (0), ( )f f .

Pas 2. Dacă ( ) (0)f f , pune 0 00,a b şi treci la Pasul 7, în caz

contrar treci la Pasul 3.

Pas 3. 0 10, 0,i .

Pas 4. 1i i .

Pas 5. Calculează 1( )if .

Pas 6. Dacă 1( ) ( )i if f , pune 0 1 0 1,i ia b şi treci la Pasul 7;

în caz contrar, pune 1i i şi treci la Pasul 4.

Pas 7. 0j .

Pas 8. j j jl b a .

Capitolul 3



Pas 9. Dacă jl pune

( )

2

j ja b şi stop; în caz contrar treci la

Pasul 10.

Pas 10. 1 2,j j j j jv a k l w a k l .

Pas 11. Dacă ( ) ( )j jf v f w , pune 1 1,j j j ja a b w ; în caz contrar

pune 1 1,j j j ja v b b .

Pas 12. Pune 1j j şi treci la Pasul 8.

Teorema 3.11. După un număr finit de iteraţii, în algoritmul de mai sus

se găseşte un interval de lungime jl , care conţine cel puţin un punct de

minim al funcţiei şi este atins stopul de la pasul 9.

Demonstraţie. Ca şi la algoritmul precedent, până la pasul 7 se găseşte un

interval iniţial care conţine cel puţin un punct de minim conform lemei 3.6.

Apoi, pentru rafinarea acestui interval, se consideră punctele jv şi jw ca în pasul

10, cu 1k şi 2k satisfăcând

2

1 2 1 21,k k k k .

Dacă ( ) ( )j jf v f w , cum după pasul 11 se ia 1j jb w şi 1j ja a , vom obţine

1 2j j j jl w a k l . În cealaltă situaţie obţinem analog 1j j jl b v

1 1 2(1 )j j j r jb a k l k l k l . Deci în toate cazurile 1 2j jl k l , adică 2 0

j

jl k l .

Intervalele sunt aşadar incluse unul în celălalt şi deci, după un număr finit de

iteraţii, vom obţine un interval de lungime jl . Să arătăm că punctele de

minim se află în acest interval prin inducţie după j. În intervalul 0 0( , )a b se află

punctele de minim conform construcţiei iniţiale şi, în plus, 0 00( )

2

a bf f a

,


0 00( )

2

a bf f b

. Aşadar 0 0( ) ( )f v f a şi 0 0( ) ( )f w f b , conform lemei

3.6.

Să presupunem acum că în intervalul ( , )j ja b se află puncte de minim şi

că ( ) ( )j jf v f a şi ( ) ( )j jf w f b . Dacă ( ) ( )j jf v f w , următorul interval

este conform algoritmului 1 1( , ) ( , )j j j ja b a w . După ipoteza de inducţie,

( ) ( )j jf v f a , şi atunci suntem în situaţia din lema 3.6, valoarea funcţiei în

( , )j j jv a w este mai mică decât valoarea în capete. Deci în intervalul ( , )j ja w

există puncte de minim. În plus,

2

1 1 1 1 1 1 2 1 2 1j j j j j j j j j j jv a k l w a k l a k l a k l v

şi deci valoarea funcţiei în 1jw este deja calculată şi egală cu ( ) ( )j jf v f w

1( )jf b . După lema 3.6 avem şi 1 1( ) ( )j jf v f a şi astfel inducţia este

completă în acest caz.

Dacă 1 1( ) ( ), ( , ) ( , )j j j j j jf w f v a b v b şi din nou, acest interval conţine

punctele de minim deoarece 1( ) ( ) ( )j j jf w f b f b şi 1( ) ( )j jf w f a . De

asemenea,

2

1 1 1 1 1 1 2 2 1 2 2j j j j j j j j j j j jv a k l a k l k k l a k l k k l a k l w ,

adică valoarea funcţiei în 1jv este deja calculată şi egală cu

1( ) ( ) ( )j j jf w f v f a . În plus, după lema (3.6), 1 1 2 1( ) ( )j j jf w f a k l

1( ) ( )j jf b f b . Astfel, inducţia este completă şi în acest caz. Dacă avem

egalitate, minimul se află în intervalul semideschis 1 1[ , ) [ , )j j j jv b a b şi avem

1 1( ) ( )j jf v f a şi 1( ) ( )j jf w f b . La iteraţia următoare situaţia se clarifică:

dacă 1 1( ) ( )j jf v f w , avem trei puncte succesive în care valorile funcţiei sunt

Capitolul 3



egale, aşadar un segment de puncte de minim. În cazul când între valorile

1( )jf v şi 1( )jf w sunt inegalităţi stricte, raţionamentul se continuă ca de

obicei. Cu aceasta teorema este demonstrată.

Observaţie. La programarea algoritmului pentru calculator, trebuie ţinut

seama de demonstraţia de mai sus, din care rezultă că începând de la a doua

iteraţie de rafinare a intervalului, o singură valoare a funcţiei se calculează la

fiecare iteraţie. În plus, trebuie introdus un test de oprire corespunzător situaţiei

de egalitate a valorilor funcţiei în trei puncte, în limitele preciziei cu care se fac

calculele.

Metodele de comparaţie prin natura lor nu folosesc valorile funcţiei decât

pentru a le compara între ele. Maximul de informaţii ce se pot obţine din valorile

funcţiei este folosit de metodele de aproximaţie care formează a doua clasă de

procedee de minimizare a unei funcţii de o singură variabilă.

Ideea acestor metode este simplă: având la fiecare iteraţie valorile funcţiei

calculate în două, trei puncte, putem aproxima funcţia printr-un polinom de

interpolare şi să determinăm apoi punctele de minim ale acestui polinom. De

exemplu, dacă se cunosc valorile funcţiei f în trei puncte 1 2 3, , , se poate

considera polinomul de interpolare Lagrange de gradul doi pentru aceste date al

cărui punct de minim este

2 2 2 2 2 2

2 3 1 3 1 2 1 2 3

2 3 1 3 1 2 1 2 3

( ) ( ) ( ) ( ) ( ) ( )1ˆ

2 ( ) ( ) ( ) ( ) ( ) ( )

f f f

f f f

,

se poate lua ca o aproximare a punctului de minim al funcţiei f.

În cazul în care se cunoaşte valoarea derivatei împreună cu cea a funcţiei

în două puncte 1 2, , se poate folosi polinomul Hermite de gradul trei, al cărui

minim este


22 1

1 2

( )ˆ ( )

( ) ( ) 2

f

f f

,

unde 1 22

1 2

2 1 1 2

3 ( ) ( )( ) ( ),

( ) ( ) ( )

f ff f

f f

.

Acest procedeu se poate aplica, de exemplu, la metodele de descreştere din

capitolul al II-lea, la care se cunosc valorile gradientului pe fiecare direcţie.

Aproximarea a punctului de minim obţinută cu una din cele două

metode nu este suficientă aunci când se cere valoarea acestuia cu o precizie

mare. Pentru obţinerea unor aproximări din ce în ce mai bune ale punctului de

minim, va trebui să se definească un proces iterativ, constând din aplicarea

succesivă a unor interpolări. Pentru aceasta este necesară înlocuirea unuia din

cele două, trei puncte pe care se face interpolarea prin punctul nou obţinut .

Cel mai natural este să se înlăture acel punct unde valoarea funcţiei este mai

mare. Dar în acest mod, se poate întâmpla să ajungem la un interval care nu mai

conţine punctul de minim şi deci, în loc de interpolare, să facem extrapolare

pentru a obţine pe . Pentru a evita aceasta (extrapolarea poate conduce la erori

relativ mari de aproximare), se fac combinaţii între metodele aproximării şi cele

ale comparaţiei. De exemplu, pentru interpolarea Lagrange pe trei puncte se

poate proceda astfel.

Se efectuează paşii 1 – 6 din metoda secţiunii de aur până se obţine un

interval iniţial în care se află punctul de minim. Se începe interpolarea pe aceste

puncte şi pe cel din mijlocul intervalului (în care valoarea funcţiei este

cunoscută de la pasul precedent). Apoi se înlătură punctul în care valoarea

funcţiei este cea mai mare şi se face o nouă interpolare. Se procedează la fel

până când, la o interpolare se obţine un punct din afara intervalului, ceea ce se

testează cu ajutorul lemei 3.6. În acest caz, se înlătură punctul obţinut prin

interpolare şi se efectuează un pas din procedeul secţiunii de aur, reluându-se

Capitolul 3



apoi procedeul. De asemenea, se poate introduce pentru mai bune rezultate

reluarea algoritmului secţiunii de aur în cazul când distanţele dintre punctul din

interval şi cele din extremităţi sunt prea diferite între ele (dacă raportul lor

depăşesc o valoare prestabilită).

Cu aceasta algoritmul devine foarte eficient, având rapiditate superliniară

de convergenţă. În mod similar se poate proceda şi cu interpolarea Hermite.

COMENTARII BIBLIOGRAFICE

Teoria discretizării spaţiilor generale şi a problemelor liniare sau neliniare

definite pe astfel de spaţii s-a dezvoltat în ultimul timp datorită lucrărilor lui

P. Aubin [1], [2], F. Stummel [19], G. Marinescu [14] şi alţii. Discretizarea

problemelor de optimizare este tratată în condiţii generale şi cu numeroase

exemple în monografia lui J. W. Daniel [7]. Schemele generale de discretizare

descrise în secţiunile 1.2 şi 1.3 sunt distincte de cele din [7] căci folosesc

discretizări stabile şi convergente ale spaţiului ceea ce a permis modificarea

condiţiilor de consistenţă cerute în lucrarea citată. Acesta este însă un cadru

destul de natural, dacă se ţine seama, că aproximările uzuale — cu diferenţe

finite, de tip Galerkin sau de tipul elementului finit — satisfac condiţiile de

stabilitate şi convergenţă. Discretizările spaţiilor ( )pL şi a spaţiilor Sobolev

sunt cele date de R. Téman [21]. În limba română cităm lucrarea lui Al. Şchiop

[20] în care sunt descrise şi unele metode de aproximare a problemelor de

optimizare.


În ce priveşte discretizarea problemelor pătratice, literatura este foarte

vastă, aici încadrându-se de fapt toate lucrările privind aproximarea problemelor

eliptice. Ne-am mărginit să expunem schema generală a lui Aubin în care am

încadrat într-un tot unitar atât metoda diferenţelor finite, cât şi cea a elementului

finit. În ce priveşte aceasta din urmă, am utilzat lucrările lui P.G. Ciarlet [6] şi

P.A. Raviart [18].

Metodele lui Newton discretizate şi metodele secantei au fost studiate de

mulţi autori, între care cităm pe J. Ortega şi W.C. Rheinboldt [15], S. Ulm [22],

B. Janko [13], M. Balázs [3], [12], I. Păvăloiu [13]. În lucrarea noastră aceste

metode sunt studiate în legătură cu rezolvarea problemelor de minimizare şi

pentru aceasta am folosit mai ales monografia [15].

Pentru metodele metricii variabile, lucrările de bază sunt cele ale lui

R. Fletcher, M.J.D. Powell [9], M.J.D. Powell [17], E. Polak [16],

W.C. Davidon [8].

Metoda variaţiilor locale a fost propusă şi studiată de F.L. Cernousko [5]

şi N.V. Baniciuk ş.a. [4] în condiţii de diferenţiabilitate a funcţiei. În Secţiunea

3.4 este dovedită convergenţa algoritmului în condiţii mai generale. Procedeele

lui W.I. Zangwill [23] sunt de asemenea considerate în condiţii mai generale

decât în lucrările originale.

Algoritmii de minimizare a unei funcţii de o singură variabilă care au fost

expuşi se bazează pe lucrările lui P.E. Gill şi W. Murray [10], [11].

Capitolul 3



BIBLIOGRAFIE

J.P. Aubin

1. Evaluation des erreurs de troncations des approximations des espaces de

Sobolev, J. Math. Anal. Appl., 21 356-368, (1968).

2. Approximation of elliptic boundary value problems, Wiley Interscience, 1972.

M. Balasz

3. Asupra metodei coardei pentru rezolvarea ecuaţiilor operaţionale neliniare,

St. cercet. mat., 20, 2 129-136 (1968).

N.V. Baniciuk, V.M. Petrov, F.L. Cernousko

4. Rezolvarea numerică a problemelor variaţionale şi la limită prin metoda

variaţiilor locale (în ruseşte), J. Vîcisl. Mat. i Matem.Fiz., 6, 947-961, (1966).

F.L. Cernousko

5. Metoda variaţiilor locale pentru rezolvarea numerică a problemelor

variaţionale (în ruseşte), J. Vîcisl. Mat. i Matern. Fiz., 5, 4, (1965).

P.G. Ciarlet

6. Numerical analysis of the finite element method, Univ. Montréal, 1796.

J.W. Daniel

7. The approximate minimization of functionals, Prentice-Hall, 1971.

W.C. Davidon

8. Variance algorithm for minimization, Comput. J., 10 406-410 (1968).


R. Fletcher, M.J.D. Powell

9. A rapidly convergent method for minimization Comput. J., 6, 163-168 (1963).

P.E. Gill, W. Murray

10. Numerical methods for unconstrained optimization, Acad. Press, 1974.

11. Safeguard steplength algorithms for optimization using descent methods,

Rept. NAC-37, Nat. Phys. Lab., Teddington, 1974.

G. Goldner, M. Balázs

12. Asupra metodei coardei și a unei modificări a ei pentru rezolvarea

ecuaţiilor operațional neliniare, St. cerc. mat., 20, 7 981-990, (1968),

N. Janko

13. Rezolvarea ecuaţiilor operaţionale neliniare în spaţii Banach, Edit.

Academiei, 1969.

G. Marinescu

14. Tratat de analiză funcţională, vol. I-II, Edit. Academiei, 1971, 1972.

J.M. Ortega, W.C. Rheinboldt

15. Iterative solution of nonlinear equations in several variables, Academic

Press, 1970.

E. Polak

16. Computational methods in optimization: a unified approach, Academic

Press, 1971.

Capitolul 3



M.J.D. Powell

17. An efficient method for finding the minimum of a function of several

variables without calculating derivatives, Comput. J., 7 155-162, (1964).

P.A. Raviart

18. Analyse numérique de la méthode des éléments finits, Rapp. 102, Univ.

Louvain, 1977.

E. Stummel

19. Approximation methods in analysis, Lecture Notes Series 35, Aarhus Univ.,

Matem. Inst., 1973.

Al. Şchiop

20. Metode aproximative în analiza neliniară, Edit. Academiei, 1972.

R. Témam

21. Metode numerice de rezolvare a ecuaţiilor funcţionale, Edit. tehnică, 1973.

S. Ulm

22. Asupra unor metode iterative cu aproximări succesive ale operatorului

invers (în ruseşte), Izv. Akad. Nauk. Eston. S.S.R., 16, 4 403-411, (1967).

W. I. Zangwill

23. Minimizing a function without calculating derivatives, Comput. J., 10, 293-

296, (1967).

metode si algoritmi de aproximare in probleme de optim

Documents