Calcul Numeric

Cursul 13

2015

Anca Ignat

1

Optimizare numeric

min { ( ) ; } , :n nf x x f Un punct * nx se numete punct de minim global pentru funcia f dac ( *) ( ) nf x f x x . Un punct * nx se numete punct de minim local pentru funcia f dac exist o vecintate V a punctului *x pentru care ( *) ( )f x f x x V . Un punct * nx se numete punct de minim strict local pentru funcia f dac exist o vecintate V a punctului *x pentru care ( *) ( ) , *f x f x x V x x . ( *, ) ; *nV S x r x x x r .

2

Dac funcia 1( )nf C se numete gradient al funciei f n punctul x vectorul:

1 2

( ) , , ,T

n

f f ff xx x x

.

Dac funcia 2( )nf C se numete matrice hessian a funciei f n punctul x matricea:

22

, 1,...,

( ) ( )i j i j n

ff x xx x

3

2 2 2

21 1 2 1

2 2 2

2 22 1 2 2

2 2 2

21 2

( ) ( ) ( )

( ) ( ) ( )( )

( ) ( ) ( )

n

n

n n n

f f fx x xx x x x x

f f fx x xf x x x x x x

f f fx x xx x x x x

4

Teorema lui Taylor Dac funcia 1( )nf C este continuu difereniabil atunci exist (0,1)t astfel ca:

( ) ( ) ( )Tf x p f x f x tp p . (1)

Dac 2( )nf C este de dou ori continuu difereniabil atunci exist (0,1)t astfel ca:

21( ) ( ) ( ) ( )2

T Tf x p f x f x p p f x tp p . (2)

5

Teorema 1 (condiii necesare de optim de ordinul nti) Fie 1( )nf C i * nx un punct de minim local pentru f. Atunci ( *) 0f x . Demonstraie: Presupunem prin reducere la absurd c

( *) 0f x . Fie ( *)p f x . Avem: ( *) ( *) 0.Tp f x f x

Deoarece f este continu n vecintatea lui *x , exist T > 0 astfel ca: ( ) 0 , 0,Tp f x tp t T . Pentru orice (0, ]s T , din Teorema lui Taylor avem:

( * ) ( *) ( * ) , pentru un (0, )Tf x sp f x sp f x tp t s .

6

Prin urmare ( * ) ( *) (0, ]f x sp f x s T , ceea ce implic faptul c *x nu este punct de minim local. Un punct *x pentru care ( *) 0f x se numete punct staionar. Teorema de mai sus spune c orice punct de minim local trebuie s fie punct staionar. Teorema 2 (condiii necesare de optim de ordinul al doilea) Fie 2( )nf C i * nx un punct de minim local pentru f. Atunci ( *) 0f x i matricea hessian 2 ( *)f x este pozitiv semidefinit.

7

O matrice n nA este pozitiv semidefinit dac , 0n nAx x x i este pozitiv definit dac , 0 , 0n nAx x x x . Demonstraie: Din Teorema 1 rezult c ( *) 0f x . Presupunem prin reducere la absurd c matricea hessian n

*x nu este pozitiv semidefinit, adic exist un vector p pentru care 2 ( *) 0Tp f x p i deorece matricea hessian este continu avem 2 ( * ) 0 [0, ]Tp f x tp p t T . Folosind relaia (2) din Teorema lui Taylor, avem (0, ]s T :

2 21( * ) ( *) ( *) ( ) ( *)2

T Tf x sp f x s f x p s p f x tp p f x .

8

Teorema 3 (condiii suficiente de ordinul al doilea) Fie 2( )nf C i * nx un punct pentru care ( *) 0f x i matricea hessian 2 ( *)f x este pozitiv definit. Atunci *x este punct de minim strict local pentru f. Demonstraie: Deoarece 2 f este continu matricea hessian este pozitiv definit ntr-o vecintate ( *, )V S x r a punctului

*x . Fie 0 cu p p r atunci *x p V i: 2

2

1( * ) ( *) ( *) ( * )2

1( *) ( * ) , (0,1)2

T T

T

f x p f x f x p p f x tp p

f x p f x tp p t

de unde deducem c:

9

( *) ( * ) , || || , 0f x f x p p p r p O funcie f se numete convex dac:

1 2 1 2 1 2(1 ) ( ) (1 ) ( ) , , , [0,1].nf a x a x af x a f x x x a

Teorema Dac f este funcie convex orice punct de minim local este punct de minim global. Dac n plus 1( )nf C atunci orice punct staionar este punct de minim global.

10

Metode de descretere Se numete direcie de descretere a funciei f n punctul x un vector nd pentru care

( ) ( ) , [0, )f x d f x . Teorema Fie 1( )nf C . Un vector d este direcie de descretere pentru f n x dac i numai dac: ( ) , ( ) 0nTf x d d f x .

11

Algoritm de descretere

1. alege nx 2. do - gsete o direcie de descretere d a lui f n x - gsete 0 astfel ca ( ) min{ ( ); (0, )}f x d f x d (ajustarea pasului line search) - x x d while (nu am gsit soluia)

12

Ajustarea pasului (line search)

Trebuie rezolvat o problem de minimizare unidimensional

min{ ( ) ; [ , ]}g a a b c Metoda Newton Fie ak aproximarea curent a soluiei problemei de minimizare de mai sus. Vom folosi dezvoltarea n serie Taylor a funciei g

2 31 1( ) ( ) ( )( ) ( )( ) ( )( )2 3!k k k k k k k

g a g a g a a a g a a a g b a a

21( ) ( ) ( )( ) ( )( )2k k k k k

q a g a g a a a g a a a

13

Pentru ka a putem considera c funcia q aproximeaz funcia g , ( ) ( )q a g a i

min{ ( ) ; [ , ]} min{ ( ) ; [ , ]}g a a c b q a a c b .

Construim elementul ak+1 ca fiind soluia problemei:

1( ) min{ ( ) ; [ , ]}kq a q a a c b

ak+1 este soluia ecuaiei

1( )

( ) 0 ( ) ( ) "( )( )"( )

kk k k k k

k

g aq a q a g a g a a a a ag a

14

Metoda secantei Dac n relaiile de mai sus se face urmtoarea aproximare:

1

1

'( ) '( )"( ) k kk

k k

g a g ag aa a

obinem urmtoarea metod de aproximare, numit i metoda secantei:

11

1

( )'( ) '( )

k kk k k

k k

a aa a g ag a g a

15

Aproximare spline cubic Vom folosi pentru a construi ak+1 pe ak-1 , ak , g(ak-1), g(ak), g(ak-1), g(ak). Aproximm funcia g cu un polinom de grad 3

3 20 1 2 3( ) ( )g a q a c a c a c a c

Funcia q (respectiv constantele ci) se calculeaz a..

1 1

1 1

( ) ( ) , ( ) ( )'( ) '( ) , '( ) '( )

k k k k

k k k k

q a g a q a g aq a g a q a g a

ak+1 este punctul de minim al funciei q

16

2 11 1

1 2

11 1

1

22 1 1

'( )( )

'( ) '( ) 2

( ) ( )'( ) '( ) 3

'( ) '( )

kk k k k

k k

k kk k

k k

k k

g a u ua a a ag a g a u

g a g au g a g aa a

u u g a g a

17

Ajustarea inexact a pasului

( ) min{ ( ); (0, )}f x d f x d - nu se obine optimal - pentru reducerea timpului de calcul optimizarea se oprete nainte de a ajunge la soluie, n funcie de anumite criterii/teste de oprire Regula lui Armijo ( ) ( ) , ( ) (0) '(0) , (0,1)k kg a f x a d g a g a g a este acceptabil dup regula lui Armijo dac

18

(1) ( ) ( )(2) ( ) ( )

g a g ag a g a

0

1

0;se alege

( ( ) ( ) )1

1

k k

k k

ka

while g a g a

a a

k k

2 sau 10 , 0.2

19

Testul Goldstein Dat (0,2), este considerat acceptabil dac:

( ) ( ) si ( ) (0) (1 ) '(0)g g g g g

1k k kx x d este acceptat dac

1( ) ( ) 1( )

k k

k k

f x f xf x d

20

Testul Wolfe

(0,2)

: ( ) ( ) (0) '(0)'( ) (1 ) '(0)

g g g gg g

21

22

Metoda pantei maxime

dat

direcie de descretere a lui n

direcie de descretere dac :

0 1

min{ ( ) ; } , :

, , 0,1, ...

0 ( ) min{ ( ) ; [0, ]}

( ) 0.

n n

k k k k

k k

k k k k k k

kT

k k

f x x f

x x x d k

d f x

f x d f x d

d

f x d

23

Metoda pantei maxime:

( )k kd f x

Cazul ptratic:

1 1( ) , ,2 2 n n

T Tf x x Ax x b Ax x b x

,n n nb A simetric i pozitiv definit

A pozitiv definit det A 0, f este strict convex

2( ) , ( )f x Ax b f x A

24

punct unic de minim

soluia sistemului liniar 1

( *) min{ ( ); } *

* , *

nf x f x x x

x Ax b x A b

( )g x Ax b

1 ,

argmin{ ( ) ; [0, ]}

k k k k k k

k k k

x x g g Ax b

f x g

25

2

2

1( ) ( ) ( ) ( )21 ( )21 ( )2

T Tk k k k k k k k

T T Tk k k k k k

T Tk k k k k

f x g x g A x g x g b

g Ag g Ax g b f x

g Ag g g f x

ecuaie de gr. 2 n , coef. lui 2( ) , 0Tk k k kf x g g Ag

min

Tk k

k Tk k

g gg Ag

26

Metoda pantei maxime pentru funcionale ptratice:

dat0

1 , 0,1, ...Tk k

k k kTk k

k k

x

g gx x g kg Ag

g Ax b

1 1( ) ( *) ( *) ( ) * *2 2

( ) ( ) ( )

T TE x x x A x x f x x Ax

E x f x g x

27

irul construit cu metoda pantei maxime satisface:

2

1 1( ) 1 ( )

Tk k

k kT Tk k k k

g gE x E x

g Ag g A g

Inegalitatea lui Kantorovich

pozitiv definit

2

21

, , 0

4( )

n n T

T

T T

A A A A

x x cCc Cx Ax x A x

c, C - cea mai mica i cea mai mare valoare proprie a lui A.

28

Teorem Cazul ptratic: Pentru orice iteraie iniial 0x , irul construit cu metoda pantei maxime converge la *x unicul punct de minim al funciei f. Avem:

2

1( ) ( )k kC cE x E xC c

Cazul general: 2: , ( ),n nf f C f are un punct de minim local *x . Presupunem c 2( *) ( *)F x f x are c > 0 cea mai mic valoare proprie i C > 0 cea mai mare valoare proprie. Dac irul kx construit cu metoda pantei maxime converge la *x (la fiecare pas 2 ( ) , ( )k kA f x b f x ),

29

*kx x atunci ( ) ( *)kf x f x converge liniar cu o rat de convergen

2C cC c .

Metoda Newton

kx - punctul curent de aproximare

21( ) ( ) ( ) ( ) ( ) ( )( ) ( )2

T Tk k k k k kf x f x f x x x x x f x x x g y

g funcional ptratic, ky x x ,

30

2

1( )2

( ) , ( ) , ( )

T T

k k k

g y y Ay y b c

A f x b f x c f x

* argmin{ ( ); }ny g y y este unica soluie a sistemului

liniar 11 2, * ( ) ( )k kAy b y A b f x f x

Metoda Newton

- dat12

1 0( ) ( ) , 0,1, ... ,k k k kx x f x f x k x

31

Teorem Fie 3( )nf C care are un punct de minim local *x astfel ca matricea 2 ( *) 0f x este pozitiv definit. Dac punctul de nceput 0x este suficient de aproape de *x , || * ||x x r , atunci irul kx generat cu metoda lui Newton converge la

*x i ordinul de convergen este cel puin 2. Variante ale metodei lui Newton

121 ( ) ( ) , 0,1, ...k k k k kx x f x f x k

k se alege astfel ca :

32

121( ) min{ ( ( ) ( )); [0, ]}k k k kf x f x f x f x

1 , 0 , , ( )

n nk k k k k k kx x M g M g f x

panta maxim

metoda Newton12 ( )

k n

k k

M I k

M f x

Cum alegem ? direcie de descreterek k k kM d M g

2

1 1 1( ) ( ) ( ) ( ) (|| || )T

k k k k k k kf x f x f x x x O x x

21( ) ( ) ( )

Tk k k k kf x f x g M g O

33

1( ) ( ) , 0 0T

k k k k kf x f x g M g Lum 0kM pozitiv definit

12 ( ) , 0k k n k kM I f x

ntotdeauna exist 0k astfel ca matricea 0kM s fie pozitiv definit. - Fie i constant fixat2 ( ) 0k kF f x . - Se calculeaz valorile proprii ale matricii 1 2: , , ...,k nF

34

- Se alege 0k cea mai mic constant nenegativ pentru care matricea k n kI F are valorile proprii :

0 & , 1, ...,

0 & max{ ; 1, ..., }

k k i

k k i

i n

i n

Noua direcie de descretere este:

1k k n k kd I F g .

- se det. cu ajustarea pasului1 ,k k k k kx x d

35

Metoda gradienilor conjugai (a direciilor conjugate)

, , 0n n TA A A A pozitiv definit

1min{ ( ) ; }2

T T nf x x Ax x b x

Definiie Pentru o matrice ,n n TA A A simetric, doi vectori

1 2,nd d se numesc A-ortogonali sau conjugai n raport

cu A dac: 1 2 2 1 2 1 1 2, , , 0n n nTd Ad Ad d d Ad Ad d

36

sunt ortogonali

ortogonalitate clasic

1 2

1 2

0 ,

, 0n

n n

n

A d d A

A I d d

Vectorii 0 1, , , kd d d se numesc A-ortogonali sau A-conjugai dac: , 0 , , , 0,1, ...,nTi j j id Ad Ad d i j i j k

Propoziie Fie , , 0n n TA A A A , i 0 1, , , kd d d direcii A-conjugate, 0 , 0, ...,id i k . Atunci vectorii 0 1, , , kd d d sunt liniar independeni.

37

baz n - direcii conjugate

0 1 1

0 1 1

, , 0, , ,

, , ,

n n T

nn

n

A A A Ad d d

d d d A

soluia sist. * argmin{ ( ); } *nx f x x x Ax b

0 0 1 1 1 1*

*, *n

n n

T Ti i i i i

b

x d d d

Ax d d Ax d Ad

38

1

0

,,

,*

,

n

n

n

n

Tii

i Ti i i i

ni

ii i i

b dd bd Ad Ad d

b dx d

Ad d

Considerm procesul iterativ

dat01 , 0,1,2, ..., 1

,

n

k k k kTk k

k k kTk k

xx x d k n

g d g Ax bd Ad

are proprietatea c *nx x .

39

0 0 0 1 1 1 1

0 0 0 1 1 1 1*

k k k

n n

x x d d d

x x d d d

, 0 0( ) ( * )T Ti k i

i iT Ti i i i

d A x x d A x xd Ad d Ad

0( ) 0Tk kd A x x

0 0 0 1 1 1 1 1* ( ) ( )k k k k k k n nx x d d d d

Corolar

0Tk ig d i k

40

Algoritmul gradienilor conjugai

sau

0 0 0

0 0 0

1

1 1 1

1

1 1

,n

Tk k

k Tk k

k k k k

k k k k k kTk k

k Tk k

k k k k

x g Ax bd g b Ax

g dd Ad

x x dg Ax b g g Ad

g Add Ad

d g d

41

span

= subspaiul generat de vectorii

1 2

1 2 1 1

1 2

, , ... ,

{ , , ... , } { ; , 1, ..., }

, , ... ,

np

np p p i

p

y y y

y y y y a y a y a i p

y y y

Teorem Presupunem c * .kx x Avem urmtoarele relaii: (1) 0 0,1, ..., 1Tk ig g i k (2) span span0 1 0 0 0{ , , ..., } { , , ..., }

kkg g g g Ag A g

(3) span span0 1 0 0 0{ , , ..., } { , , ..., }

kkd d d g Ag A g

42

(4) 0 0,1, ..., 1Tk id Ad i k irul *kx x n cel mult n pai. span0 0 0 0( , ) { , , ..., }

kg k g Ag A gK - se numete subspaiu Krylov de grad k pentru 0g .

43

Forma practic a metodei gradienilor conjugai dat

0

0 0 0 0

1

1

1 1

1 1

, 0,

( 0)

1;

n

k

Tk k

k Tk k

k k k k

k k k kTk k

k Tk k

k k k k

x kg Ax b d gwhile g

g gd Ad

x x dg g Ad

g gg g

d g dk k

44

Teorem Dac matricea A are doar r valori proprii distincte, algoritmul gradienilor conjugai calculeaz soluia *x n cel mult r iteraii. Teorem Dac 1 2 n sunt valorile proprii ale matricii A atunci:

22 21

1 01

21 1

2

11 0

1

|| * || || * ||

|| * || 2 ( )

( ) ( ).

n kk A A

n k

k A k

n kk

n k

x x x x

x x E x

E x E x

45

Metodele neliniare ale gradienilor conjugai 21( ) ( ) ( )( ) ( ) ( )( )

2T

k k k k k kf x f x f x x x x x f x x x

2

( )

( )

k k

k

g f x

A f x

Varianta pentru funcii oarecare a metodei gradienilor conjugai:

46

dat00 0 0 0

2

1

1 1

1

1 1

, 0( ),

( 0)

( )

( )

1;

n

k

k

Tk k

k Tk k

k k k k

k kTk k

k Tk k

k k k k

x kg f x d gwhile g

A f x

g dd Ad

x x dg f x

g Add Ad

d g dk k

47

Metoda Fletcher-Reeves

k se calculeaz folosind metoda ajustrii pasului

1 1Tk k

k Tk k

g gg g

dat00 0 0 0

,( ), , 0

nxg f x d g k

48

exact sau inexact cu testul lui Wolfe

1

1 1

1

1 1

( 0)min{ ( ); [0, )}

( )

( )

1;

k

k k k

k k k k

k kT

FR k kk T

k kFR

k k k k

while gf x d

x x dg f x

g gg g

d g dk k

Se pune problema dac kd sunt direcii de descretere?

49

1 1

1 1

k k k k

T T Tk k k k k k k

d g d

g d g g g d

Dac se folosete ajustarea pasului exact:

1k este punct de minim local pentru f pe direcia 1kd prin urmare 1 0 ( ( ))

Tk k k kg d g f x .

22|| || 0

T Tk k k k k kg d g g g d direcie de descretere

Dac se folosete ajustarea pasului inexact am putea avea

0Tk kg d ( kd direcie de cretere!!) dar folosind testul lui Wolfe deducem:

50

( ) ( )

| ( ) | (1 ) | |10, 02

Tk k k k k k k

T Tk k k k k k

Tk k

f x d f x g d

f x d d g d

g d

Metoda Polak-Ribire

- variant a metodei Fletcher-Reeves

1 1( )T

PR k k kk T

k k

g g gg g

Dac se face ajustarea pasului inexact cu testul lui Wolfe nu putem deduce c kd sunt direcii de descretere.

51

Se folosete max{ ,0}PRk k i un test Wolfe adaptat pentru a obine kd direcii de descretere. Varianta Hestenes-Stiefel

1 1

1

( )( )

THS k k kk T

k k k

g g gg g d

52

Precondiionare Se consider norma:

|| || , nAx Ax x

Evaluarea erorii n metoda pantei maxime:

( ) (0)

1

1 2

( ) 1|| || || ||( ) 1

( ) numrul de condiionare spectral

0 < valorile proprii ale matricii

kk

A A

n

n

k Ax x x xk A

k A

A

53

Avem convergen rapid dac numrul de condiionare spectral al matricii A este apropiat de 1 (k(A)1 ntotdeauna). Ideea precondiionrii este de a transforma sistemul Ax=b

astfel nct s mbuntim proprietile spectrale.

, cu ( ) ( )Ax b Ax b k A k A Precondiionare

1 1

1 1

1 1 1 11 2 1 2 1 2

( la stnga)( la dreapta)

(split)

Ax b M Ax M bAM y b x M yM AM y M b x M y M M M

54

cu M matrice nesingular , M A. Matricea M sau M-1 poart numele de matrice de precondiionare. Cum trebuie s alegem matricea M?

- sistemul precondiionat ( Ax b ) s fie uor de rezolvat (convergen rapid)

- matricea de precondiionare s fie economic de construit i aplicat ietariile s nu fie costisitor de construit

55

Matricea de precondiionare Jacobi

11 22diag[ , , , ]nnM a a a Matrici de precondiionare SSOR

1( ) ( ) ( )T TM D L D D L A L D L 11 1 1 1( ) (0,2)

2

T

M D L D D L

Pentru - optimal, n anumite cazuri: 1( ( ) ) ( ( ))optk M A O k A

( opt - foarte costisitor de calculat)