Upload
juste-menard
View
109
Download
0
Embed Size (px)
Citation preview
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