Giansalvo EXIN Cirrincione unité #4 Matrice symétrique définie positive Hermitienne : A H = A...

Giansalvo EXIN CirrincioneGiansalvo EXIN Cirrincione

unité #4unité #4

Matrice symétrique définie positive

• Hermitienne : AH = A• Symétrique : AT = A• Définie positive : , , 0 ( 0 : strictement d.f.)x Ax x

2 2min avec min min

min ( )

min

x x x

T T

x

T

x

y y Bx Bx Bx,Bx

x B B x

x Ax

2

avec

, , 0

TA B B

x Ax x Bx

Exemple :

Matrice symétrique définie positive

Exemple : la matrice est elle définie positive

2 -1 0

-1 2 -1 ?

0

-1 2

1

1 2 3 2

3

1 2

1 2 3 1 2 3

2 3

2 2 21 1 2 2 2 3 3

2 22 21 1 2 2 3 3

2 -1 0

-1 2 -1

0 -1 2

2 -

- 2 -

- 2

2 2 2 2 2

0

T

x

x Ax x x x x

x

x x

x x x x x x

x x

x x x x x x x

x x x x x x

• Hermitienne : AH = A• Symétrique : AT = A• Définie positive : , , 0 ( 0 : strictement d.f.)x Ax x

Matrice symétrique définie positive

• Hermitienne : AH = A• Symétrique : AT = A• Définie positive : , , 0 ( 0 : strictement d.f.)x Ax x

T T TA A x Ay y Ax T T TA A x Ay y Ax

iiH

ij ji

H H H H

A A a a

A A x Ay y Ax x Ax

a

iiH

ij ji

H H H H

A A a a

A A x Ay y Ax x Ax

a

x x x h.p.d. full rank h.p.d.m m m n H n nA X m n X AX x x x h.p.d. full rank h.p.d.m m m n H n nA X m n X AX

hermitienne :

définie po

0 0

sit

ive :

et

0

HH H H H

HH H

X AX X A X X AX

x Xx

x X AX x Xx A Xx

Matrice symétrique définie positive

• Hermitienne : AH = A• Symétrique : AT = A• Définie positive : , , 0 ( 0 : strictement d.f.)x Ax x

T T TA A x Ay y Ax T T TA A x Ay y Ax

iiH

ij ji

H H H H

A A a a

A A x Ay y Ax x Ax

a

iiH

ij ji

H H H H

A A a a

A A x Ay y Ax x Ax

a

x x x h.p.d. full rank h.p.d.m m m n H n nA X m n X AX x x x h.p.d. full rank h.p.d.m m m n H n nA X m n X AX

hermitienne :

définie po

0 0

sit

ive :

et

0

HH H H H

HH H

X AX X A X X AX

x Xx

x X AX x Xx A Xx

singulière ker( ) 0

0 ker( )

or ker( ) 0 et donc 0

ce qui est contradictoire avec l'hypothèse

T

A A

x A

x A Ax x Ax

Si A est une matrice n x n strictement définie positive

Alors : A est non singulière aii > 0 pour i = 1, … , n

Théorème :

Propriétés des matrices définies positives

Si A est une matrice n x n strictement définie positive

Alors : A est non singulière aii > 0 pour i = 1, … , n

Théorème :

Propriétés des matrices définies positives

( ) ( )

( ), 0, en particulier pour position

or 0 par hypot

0

hè

0

se

1iT ème

i iii

x x Ax i

x

x

x A a

Propriétés des matrices définies positives

Définition : une sous matrice principale d’une matrice Aest une matrice carrée de la forme A(1:i,1:i) quelque soit i

0

0

0

k

0

=k

Les Les nn sous-matrices sous-matrices kk sont définies positives et donc inversibles. sont définies positives et donc inversibles.

Théorème de SylvesterThéorème de Sylvester : Une matrice symétrique est définie positive ssi chacune de ses sous matrices principales à un déterminant positif

Propriétés des matrices définies positives

Définition : une sous matrice principale d’une matrice Aest une matrice carrée de la forme A(1:i,1:i) quelque soit i

Théorème de SylvesterThéorème de Sylvester : Une matrice symétrique est définie positive ssi chacune de ses sous matrices principales à un déterminant positif

4....det1det2detdet

031421

12detdet

;02det

21-0

1-21-

01-2

A

22

2

1

AAA

A

A

4....det1det2detdet

031421

12detdet

;02det

21-0

1-21-

01-2

A

22

2

1

AAA

A

A

Propriétés des matrices définies positives

( ) ( )

(

( )

) ( )

0 si et

1 si

-1 si

(1) symétrique 2

(2)

, 0, en particulier pour

sym

or 0

et

étriq 2

0

ue

T

jk jkjj kk jk kj

jk jkii kk jk kj

jk

jk jj kk

jk

x x Ax

x Ax a a a a

x A x a a a a

i j i k

x i j

i k

A a a a

A a

,(1) (2) max et donc :

2max maxjj kk

j

jj kk

jk ik iii

ij k i

a aet a a

a a

a a

Théorème :

,max max jk ii

k j ia a

Si A est une matrice n x n symétrique strictement définie positive

Alors :

Propriétés des matrices définies positives

Théorème : Si

A est une matrice n x n symétrique strictement définie positiveAlors : 2

ij ii jja a a i j

( )

2

( ) ( ) 2

2

, 0, en particulier pour

or 2 0

sont déterminant est né

0 si et

1 si

si

gatif

4 4 0

T

j

jk

jk jj kk

k jkjj kk jk

jk jj kk

i j i

x x Ax

x A

k

x i j

i k

x a a a

a a a a a a

Propriétés des matrices définies positives

1 2

1 1 1 2 2 2 1 2

2 1 2 1 2 2 1 1 2 1 1 1 2

1 2 1 2 1 2

,

0 0

0 0H

H H H H H

H

H

H

Ax x Ax x

x x x Ax x A

Ax x x

x x

x Ax x

x

x x x x

x

x x

Théorème : Si

A est une matrice n x n hermitienne strictement définie positive

Alors : ses valeurs propres sont réelles et positives et ses vecteurs propres sont orthogonales

Élimination symétrique de Gauss Élimination symétrique de Gauss

1 0 1

11 1

00 0

1 0 1

1

0

0

0

11

0 0

H H

H

H

HH

H

H

H

H

w wA

Iw K K ww

w

K ww

w

K ww I

wA

I K ww

w

w

ww K I

11

1111

11

1

1

11

1

1

1

0

0

10

0

H

H

H H

wA

R

w K

w

w wwI K

I

a

aa

a

A R

a

a

Élimination symétrique de Gauss Élimination symétrique de Gauss

11

1111

11

1

1

11

1

1

1

0

0

10

0

H

H

H H

wA

R

w K

w

w wwI K

I

a

aa

a

A R

a

a

11 1 1sous matrice principale de la matrice d.p. HR A R

matrice d.p.

2 11 22 2 12 22H HH AA R A R R R A R R

Factorisation de Cholesky Factorisation de Cholesky

2 11 22 2 12 22H HH AA R A R R R A R R

x

1

¨

1 2 2

, triangulaire supérieure, > 0

, triangulaire inférieure >, 0

H

jj

m m

H H

RR

m

j

Hm

H

Hj

A

A R R R R R R

A R R

A

r

lL

R

L L

Si Si AA est une matrice hermitienne définie positive, il est une matrice hermitienne définie positive, il existe une unique factorisation de Cholesky.existe une unique factorisation de Cholesky.

Factorisation de Cholesky Factorisation de Cholesky

, :, :

, : , : , :

for 1 to

for 1 to

k jj j

k

m j j m k j mk

k mk k

k

k

m

k

R A

k m

j k m

R

RR R R

R

RR

, :

, :

, : , : , :

for 1 to

for 1 to

k jj j

k

m j j m k j mk

k mk k

k

k

m

k

R A

k m

j k m

R

RR R R

R

RR

Stabilité de la factorisation de Cholesky Stabilité de la factorisation de Cholesky

The factors The factors RR can never grow large. In the can never grow large. In the 22-norm, e.g., -norm, e.g., 1/ 2

2 22

HR R A

The stability is achieved without the need for The stability is achieved without the need for any pivotingany pivoting. . Intuitively, it is related to the fact that most of the weight of Intuitively, it is related to the fact that most of the weight of a hermitian positive definite matrix is on the diagonal.a hermitian positive definite matrix is on the diagonal.

x hermitienne définie positi

,

ve

m m

Hmachine

AR R A A O

A

A

If is ill-conditioned, will not generally be close to ;

the best we can say is :

machine

R RO

R

R

A

A R

Factorisation de Cholesky (à partir de Doolittle) Factorisation de Cholesky (à partir de Doolittle) 11

21 22

1 2m m mm

b

b bB

b b b

min ,

1 1

1

, 1 ,

puisque 0 si 1 . Pour la symétrie de il suffit :

, 1

i jmT T

i j ik jk ik jki jk k

pq

j

i j ik jkk

A BB a BB b b b b i j m

b p q m A

a b b i j m

1

12

1

1

1, ,

1

, 1 1 1,1 1, 1

1 1

1,1

1

Après avoir déterminé les 1 premières colonnes

1

:

i

ii ii ikk

ii i i ii ii

i i i

i

i i i i ik i kkii

i ii i i

im i m

b a b

b a b bb

j i a b b b b

j i a b b b b

j m

i

a b b

1

1

1

i

mii m i im ik mkkii

i b a b bb

b b

2

11 11

12 11 21

1 11

11 11

21 12 11

1 11 11

Faisant 1 , il

1

2

v

ient :

mm m m

i

j a b

j a b b

j m a b

b

b

a

b a b

b a b

première colonne de première colonne de BB

ii-ème colonne de -ème colonne de BB

Solution de A x = b

3

3

2

2

x

1 flops

3

flops

hermitienne définie positive

total work :

flops

1

flop

s3

m

H

m

HA R R

R

O m

O m

y b

Rx y

O m

O m

A

The solution of hermitian positive definite systems A x = b via Cholesky factorization is backward stable :

, machine

AA A x b O

A

Projecteurs (projectors)Projecteurs (projectors)

Un projecteur est une matrice carrée Un projecteur est une matrice carrée PP telle que telle que P²P² = = PP ((idempotentidempotent))

vv

range(range(PP))

Pv-vPv-vdirection de projection

2

l

0

nul

P Pv v P v

Pv

Pv

v P

null(P)

2range

range

v P v

v P v P

Px Pv P x Px v

v

PvPv

Projecteurs (projectors)Projecteurs (projectors)

Un projecteur est une matrice carrée Un projecteur est une matrice carrée PP telle que telle que P²P² = = PP ((idempotentidempotent))

vv

range(range(PP))

Pv-vPv-v nullPv v P null(P)PvPv

2 2

complementary projector t

est un projecteur

( )o

2

I P

I P I P I P

P

P

null

range

direct. project.

0 range

rang

null

null range nu

l

l

e l

l

nu

PI P

Pv I P v v I P P

I P

I P P

v v Pv P I P P

null range

P I P

P P

I

I

range(I-P)

null(null(I-PI-P))

Projecteurs (projectors)Projecteurs (projectors)

Un projecteur est une matrice carrée Un projecteur est une matrice carrée PP telle que telle que P²P² = = PP ((idempotentidempotent))

vv

range(range(PP))

Pv-vPv-v nullPv v P null(P)PvPv

range nullI P P

null rangeI P P range(I-P)

null(null(I-PI-P))

rang

Si et

null null 0

A projector separates into two space

null

e nul

n

s

l

0

0

ull

m

v v

v v I P v

I

P

P

I

P

P

v

P

P

P

Projecteurs (projectors)Projecteurs (projectors)

Un projecteur est une matrice carrée Un projecteur est une matrice carrée PP telle que telle que P²P² = = PP ((idempotentidempotent))

vv

range(range(PP))

Pv-vPv-v nullPv v P null(P)PvPv

range nullI P P

null rangeI P P range(I-P)

null(null(I-PI-P))

A projector separates

range null 0

into two spacesm

P P

m1 2 1 2 1 2

1 2 1 2 1 2 1 1 2 2

Conversely, let and two subspaces of such that 0 and , where

denotes the span of and , that is the set of vectors with and

complementary subspac

( .es)

mS S S S S S

S S S S s s s S s S

1 2there is a projector such that ran Th ge anen .d nullP P S P S

P is the projector onto S1 along S2

vv

range(range(PP))

Projecteurs orthogonauxProjecteurs orthogonauxS1 et S2 sont orthogonaux

PvPv

Pv-vPv-v

Un projecteur Un projecteur P P est est orthogonalorthogonal ssi ssi PP = = PPHH

1 2

2

Si alors le produit scalaire entre and est nul.

0

Alors le projecteur est orthogonal.

H

H H H

P P Px S I P y S

x P I P y x P P y

Projecteurs orthogonauxProjecteurs orthogonauxS1 et S2 sont orthogonaux

Un projecteur Un projecteur P P est est orthogonalorthogonal ssi ssi PP = = PPHH

1 2

1 2

basis for

1

basis f o

1 2

r

projects onto (dimension ) along .

, orthonor, , , mal basis for, , mn m

S

n

S

q

P

q q q

S n S

q

x1

0

, , , ,

j j

j

m mj m

Pq q j n

Pq j n

Q q q q

PQPQ = = qq11 …… qqnn 00 ……

0 0 0

0 0

0 0 0

1

0

1

0

HQ PQ

HHH H H H HP Q Q Q Q Q Q Q QP P

H HP Q Q QQ

Q

HQ

n

m

Projecteurs orthogonauxProjecteurs orthogonaux

0 0 0

0 0

0 0 0

1

0

1

0

HQ PQ

Projecteurs orthogonauxProjecteurs orthogonaux

v

H HP Q Q QQ

Q

HQ

n

m

1

nH H

i ii

y QQ v q q v

1

nH

i ii

v q q v

orthogonal projector onto range Q

The complement of an orthogonal projector

is also an orthogonal projector and projects

onto the space orthogonal to range .

HH H

Q

I QQ I QQ

vecteur normé

(rang 1)

(rang 1)

Hq

Hq

P qq

P I qq

q

m

vecteur arbitraire

(rang 1)

(rang 1)

H

a H

H

a H

aaP

a a

aaP

a

amI

a

Projection avec une base arbitraireProjection avec une base arbitraire

1 2

x1

, , , l.i.

, , , ,

n

m nj n

a a a

A a a a

range

0 0

range

0

H H

H H

j j

H

y v A

a y v j a Ax v j

A Ax A Ax A v

v A

v

y

2

2

x singulière

rank-deficient

rank-deficient

singulière

Si est "full rank", est non singulière.

0 / 0 0

0 0 ( )

x 0 / 0

0

H H H

H

H

H

H

A Ax x A Ax

Ax Ax

A

A A

A

A

A A

x

A A

A

A

Ax

1 1H H H Hx A A A v y Ax A A A A v

1H HP A A A A

Factorisation QRFactorisation QR

Espaces colonnesEspaces colonnes 1 1 2 1 2 3

1 2 1 2

x

span( ) span( , ) span( , , )

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

m n

j jq q q a a

a a a a a a

A m n

a j n

1 11 1

2 12 1 22 2

3 13 1 23 2 33 3

1 1 2 2

n n n nn n

a r q

a r q r q

a r q r q r q

a r q r q r q

= 00 00 …… rrnnnn

00 rr2222 …… rr1111 rr1212 …… rr1n1n

qq11 ……qq22 qqnnaa11 ……aa22 aann

x

x

ˆ

ˆ

ˆ

ˆ

m n

n n

A QR

Q

R

reduced QR factorizationreduced QR factorization

orthonormalisation de orthonormalisation de Gram-SchmidtGram-Schmidt

00 00 …… 0000 00 …… 00

Factorisation QRFactorisation QR

x

x

ˆ

ˆ

ˆ

ˆ

m n

n n

A QR

Q

R

reduced reduced QR factorizationQR factorization

orthonormalisation de orthonormalisation de Gram-SchmidtGram-Schmidt

= 00 00 …… rrnnnn

00 rr2222 …… rr1111 rr1212 …… rr1n1n

qq11 qq22aa11 ……aa22 aann …… qqnn qqmm……

x

x

m m

m n

A

Q

QR

R

full full QR factorizationQR factorization

orthonormalisation de orthonormalisation de HouseholderHouseholder

1. Compute a QR factorization A = Q R2. Compute y = QH b3. Solve R x = y for x

Solution de Solution de A xA x = = bb par factorisation QR par factorisation QR

Il est si facile de résoudre un système « triangulaire » !

1bQRxbAxQRA

Q « facilement »  inversible et R triangulaire

HRx Q b

Othogonal triangularization Othogonal triangularization (Householder)(Householder)

Alston HouseholderAlston Householder

The matrix The matrix QQkk is chosen to introduce zeros below the diagonal is chosen to introduce zeros below the diagonal

in the in the kkth column while preserving all the zeros previously th column while preserving all the zeros previously introduced. It operates on rows introduced. It operates on rows 11, … , , … , mm..

Othogonal triangularization Othogonal triangularization (Householder)(Householder)

2 1

1 2 u est nitaire

H

n

H

Q

H Hn

Q Q Q A R A QR

Q Q Q Q

22 22 1nQ Q Q AR A

2 31

1 2 1

0

0 0

0 0 0

0

0

0

Q QQ

A Q A Q Q A

3 2 1 Q Q Q A

Othogonal triangularization Othogonal triangularization (Householder)(Householder)

1 2 1kQ Q Q A

kk-ème ligne-ème ligne

kk-ème colonne-ème colonne

x

1m kx

1

1 x 1

1 x

1

1

Householder reflect

0

0

( or)

k

k k

m k m

k

m k

k

F

F

QI

I

Othogonal triangularization Othogonal triangularization (Householder)(Householder)

1 2 1kQ Q Q A

x

1m kx

1

1 x 1

1 x

1

1

Householder reflect

0

0

( or)

k

k k

m k m

k

m k

k

F

F

QI

I

12

2

0

0

0

0

0

0

e

x

x

F

1m kx

Othogonal triangularization Othogonal triangularization (Householder)(Householder)

2

12

0

0

0

0

0

0

x

x eFx

HH

xx

1Fx x e

vv1v x e x

hyperplane

1m kx

Othogonal triangularization Othogonal triangularization (Householder)(Householder)

2

12

0

0

0

0

0

0

x

x eFx

HH

1Fx x e

vv

H H

H H

vv v yPx I x y v

v v v v

xx

2 2H H

H H

vv v yFx I x x v

v v v v

full rank

unita

2

ry

H

H

vvF I

v v

1m kx

Othogonal triangularization Othogonal triangularization (Householder)(Householder)

H H ++

xx1x e x

H H --

1x e1x e

1x e x

2

12

0

0

0

0

0

0

xFx

x

e

real casereal case

cancellationerror

2

1 1

1 1

sgn 1 si

sgn

0

v x x e

x x

x

Factorisation QR de HouseholderFactorisation QR de Householder

1

: ,

: ,

1

: : : ,

2

,

2

: :2

s

For 1 to

gn

Hk m k n k m k n k k k m k

k m k

kk

k

k

n

k n

x A

v

v x x e x

v

v

v

A A v A

xm nA

m n

: , : , : : ,

If the vector length is ,

it requires scalar operations:

- for subtraction

- for scalar multiplication

- for dot product.

This is 4 f fo

1

r ealop ch

2

ent

2

s

4 4

1

r

1

Hk m j k m k n k k k m jA A v A

m k

v

y operated on.

Factorisation QR de HouseholderFactorisation QR de Householderxm nA

m n

1

: ,

: ,

1

: : : ,

2

,

2

: :2

s

For 1 to

gn

Hk m k n k m k n k k k m k

k m k

kk

k

k

n

k n

x A

v

v x x e x

v

v

v

A A v A

four times four times the volumethe volume

3lim1

3ziggurat pyramidnV nV

2

,lim

1

3staircase prismm n

m n nV V

2 322 flops

3mn n

Factorisation QR de HouseholderFactorisation QR de Householderxm nA

m n

1

: ,

: ,

1

: : : ,

2

,

2

: :2

s

For 1 to

gn

Hk m k n k m k n k k k m k

k m k

kk

k

k

n

k n

x A

v

v x x e x

v

v

v

A A v A

2 322 flops

3mn n

HRx Q b

: : :

For 1 to

2 Hk m k m k k k m

n

b b v v

k

b

flopsmn

Qx

: : :

For downto 1

2 Hk m k m k k k mx v

k

x v

n

x

flopsmn 1 2, , , mQe Qe QeIQ Q

Q

Q 1 2, , , nQe Qe QeIQ Q

Stabilité de la factorisation de Householder Stabilité de la factorisation de Householder

161.11 10machine

twenty digits of accuracy have been lost ! accurate to a full fifteen digits !

The errors in Q2 and R2 are forward errors. In general, a large forward error can be the result of an ill-conditioned problem or an unstable algorithm (here the former). As a rule, the sequence of column spaces of a random triangular matrix are exceedingly ill-conditioned as a function of the entries of the matrix.The error in Q2 R2 is the backward error or residual.

Stabilité de la factorisation de Householder Stabilité de la factorisation de Householder

1 2

Let denote the reflector

defined by the floating point vector

exactly unita

.

ry

n

k

k

Q

v

Q Q Q Q

La factorisation QR de Householder est backward stableLa factorisation QR de Householder est backward stable

machineQR AA

AA O

Stabilité de la solution QR de Stabilité de la solution QR de A xA x = = bb Stabilité de la solution QR de Stabilité de la solution QR de A xA x = = bb

1. Compute a QR factorization A = Q R

2. Compute y = QH b

3. Solve R x = y for x

, machine

AQR A A O

A

BS

, machineQ Q y b Q O BS

, machine

RR R x y O

R

BS

, machine

AA A x b O

A

BS

xm mA

Stabilité de la solution QR de Stabilité de la solution QR de A xA x = = bb Stabilité de la solution QR de Stabilité de la solution QR de A xA x = = bb

, machine

AA A x b O

A

BS

1

, =

, =

= , =

H

machine

machine

machine machin

machine

machine

Q Q R R x QR Q R Q R Q R x

R A AQR A A Q O

A A

RQ Q y b Q O Q

A

OA

RR RR R x y O Q

AR R

b A x

Q R

A

O

RQ O O

R

Q R

A

2

=

machine

machine

e O

AO

A

Q R

A

Q RQ R Q RA

A A A

RRQ

AR

A

Stabilité de la solution QR de Stabilité de la solution QR de A xA x = = bb Stabilité de la solution QR de Stabilité de la solution QR de A xA x = = bb

, machine

AA A x b O

A

BS

machine

x xO A

x

accuracyaccuracy

FINEFINE