Notesale: Turn your study into money

Document Preview

Extracts from the notes are below, to see the PDF you'll receive please use the links above

---

0
...
Son principe intérêt vient du fait qu'il peut fonctionner aussi pour des matrices
non inversibles, conduisant ainsi à la notion de pseudo-inverse
...
1
...

• A+ A+ à l'étape m (Soit les m premières lignes)
...
1
...
On suppose que nous avons
k
k−1
crée A+ matrice donc on a :
k−1
Ak−1 A+ Ak−1 = Ak−1
k−1

A+ Ak−1 A+ = A+
k−1
k−1
k−1
Ak−1 A+ = (Ak−1 A+ )t
k−1
k−1
A+ Ak−1 = (A+ Ak−1 )t
k−1
k−1

on veut A+ avec Ak A+ Ak = Ak et Ak = Ak−1 ak pour avoir un produit de matrice cohérent,
k
k
il faut ajouter une ligne à A+
...


Bk−1
bk

Ak−1 ak

Bk−1 Ak−1 Bk−1 ak
bk Ak−1
b k ak

= Ak−1 Bk−1 Ak−1 + ak bk Ak−1 Ak−1 Bk−1 ak + ak bk ak

1

= Ak−1 ak

alors on trouve un système de deux équations et on cherche Bk−1 et bk :
Ak−1 Bk−1 Ak−1 + ak bk Ak−1 = Ak−1
Ak−1 Bk−1 ak + ak bk ak = ak

Initialisation :
A 1 = a1
1
A+ = at t
1
1
(a1 a1 )

Vérication pour k = 1
On montre que A1 A+ A1 = A1 :
1
A1 A+ A1 = A1 (
1
1

=

(at a1 )
1

=

at
1
)A1
t
a1 a1

(A1 at A1 )
1

1
(at a1 )
1

(a1 at A1 )
1

A1 A+ A1 = A1
1

Si A1 = 0 alors A+ = 0t , donc A1 A+ A1 = A1 :
1
1
On montre que A+ A1 A+ = A+
1
1
1
A+ A1 A+ =
1
1
=

At
At
1
A1 t 1
at a1 a1 a1
1

At
at
1
a1 t 1
at a1 a1 a1
1
At
1
t
a1 a1

=

A+ A1 A+ = A+
1
1
1

Si A1 = 0 alors A+ = 0t , donc A+ A1 A+ = A+
1
1
1
1
On montre que (A+ A1 )t = (A+ A1 ) :
1
1
(A+ A1 )t = At (A+ )t
1
1
1
=
=

at t
t
A1 ( t 1 )
a1 a1
1
at a1
1

(at a1 )
1

=1

(A+ A1 ) = at
1
1

2

1
a1
(at a1 )
1

1
at a1
t
(a1 a1 ) 1
1 = (A+ A1 )t
1

=
=

Si A1 = 0 alors A+ = 0t , donc (A+ A1 )t = (A+ A1 ) :
1
1
1
On montre que (A1 A+ )t = (A1 A+ ) :
1
1
(A1 A+ )t = (A1 At
1
1
=

1
(at a1 )
1

)t

A1 At
1

A1 A+ = A1 At
1
1
=

1
(at a1 )
1

1

(at a1 )
1
+ t
(A1 A1 )

Si A1 = 0 alors A+ = 0t , nous arrivons à l'égalité :(A1 A+ )t = (A1 A+ )
1
1
1
Les propriétés sont vériées au rang 1
...

on suppose
Ak−1 A+ Ak−1 = Ak−1
k−1

A+ Ak−1 A+ = A+
k−1
k−1
k−1
Ak−1 A+ = (Ak−1 A+ )t
k−1
k−1
A+ Ak−1 = (A+ Ak−1 )t
k−1
k−1

on montre que Ak A+ = (Ak A+ )t :
k
k
A+ (I − ak pt )
k
k−1
pt
k

Ak A+ = Ak−1 ak
k

= Ak−1 (A+ (I − ak pt )) + ak pt
k
k
k−1
= Ak−1 A+ − Ak−1 A+ ak pt + ak pt
k
k
k−1
k−1
(I − AK−1 A+ )aK
K−1
or pk =
+
||(I − AK−1 AK−1 )ak ||2
Ak A+ = Ak−1 A+ +
k
k−1
=A

k−1

A+
k−1

(−Ak−1 A+ ak ((I − AK−1 A+ )ak )t + (ak ((I − AK−1 A+ )ak ))t
K−1
K−1
k−1
||(I − AK−1 A+ )ak ||2
K−1

(−Ak−1 A+ ak at − Ak A+ ak at AK−1 A+ + ak at − ak at AK−1 A+ )
k
k
k
k
K−1
K−1
k
k−1
+
+
2
||(I − AK−1 AK−1 )ak ||

d'où
(Ak A+ )t = Ak−1 A+ +
k
k−1

(−ak at AK−1 A+ − Ak A+ ak at AK−1 A+ + ak at − Ak−1 A+ ak at )
k
k
k
k
K−1
K−1
k
k−1
||(I − AK−1 A+ )ak ||2
K−1

car
3

(Ak−1 A+ )t = Ak−1 A+
k−1
k−1
(ak at )t = ak at
k
k

donc :

(Ak A+ )t = Ak A+
k
k

Pour le cas particulier :pk =

(A+ )t A+ aK
K−1
K−1
1 + (A+ )ak 2
K−1
A+ (I − ak pt )
k
k−1
pt
k

Ak A+ = Ak−1 ak
k

= Ak−1 (A+ (I − ak pt )) + ak pt
k
k
k−1
= Ak−1 A+ − Ak−1 A+ ak pt + ak pt
k
k
k−1
k−1

or
Ak−1 A+ ak = ak car (I − AK−1 A+ )ak = 0
K−1
k−1
= AK−1 A+ − ak pt + ak pt
k
k
K−1
= AK−1 A+
K−1

nous avons AK−1 A+ symétrique donc AK A+ est symétrique
...


(A+ )t A+ aK
K−1
K−1
1+||(A+ )ak ||2
K−1

pt ak
k

at (A+ )t A+ aK
= k K−1 + K−1 2
(1 + ||(AK−1 )ak || )

(A+ )ak ||2
K−1
=
(1 + ||(A+ )ak ||2 )
K−1
pt Ak−1 =
k
=

at (A+ )t A+ Ak−1
k
K−1
K−1
+
(1 + (AK−1 )ak 2 )

(A+ Ak−1 A+ ak )t
k−1
k−1
(1 + (A+ )ak 2 )
K−1

(A+ ak )t
k−1
=
(1 + (A+ )ak
K−1

2)

gure :L'organigramme de l'algorithme de Gréville
5

Exemple 1 :

Soit la matrice :




1 −1 1
2
1 −1

A=
1
2
1
−1 1
2

On cherche à calculer Pseudo-inverse
...

3

1
9

3 −1 1 2 ,

Exemple 2 :

Soit la matrice :




5 1 7
A = 1 2 2 
7 2 10

On cherche à calculer Pseudo-inverse
...

=

1
676

7



---