Upload
buingoc
View
220
Download
0
Embed Size (px)
Citation preview
Calcul matriciel
Laydi M.R.
2
Sommaire
0 Notations principales 50.1 Nombres, ensembles . . . . . . . . . . . . . . . . . . . . . . . . . 50.2 Vecteurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
0.2.1 Produit scalaire . . . . . . . . . . . . . . . . . . . . . . . . 60.2.2 Orthogonalité . . . . . . . . . . . . . . . . . . . . . . . . 60.2.3 Normes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60.2.4 Inégalité de Schwarz . . . . . . . . . . . . . . . . . . . 6
0.3 Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70.4 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1 Matrice symétrique ou hermitienne 111.1 Exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121.2 Remarques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2 Normes sur les matrices 172.1 Norme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172.2 Norme matricielle . . . . . . . . . . . . . . . . . . . . . . . . . . . 182.3 Norme matricielle subordonnée . . . . . . . . . . . . . . . . . . . 192.4 Caractérisation de la norme kAk1 . . . . . . . . . . . . . . . . . 202.5 Caractérisation de la norme kAk2 . . . . . . . . . . . . . . . . . . 21
3 Lien de la norme avec le rayon spectral 233.1 Majoration du rayon spectral par la norme matricielle : Théorème
de Browne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233.2 Majoration d�une norme par le rayon spectral . . . . . . . . . . . 253.3 Convergence d�une suite de matrices . . . . . . . . . . . . . . . . 273.4 Stabilité d�un système itératif . . . . . . . . . . . . . . . . . . . . 293.5 Application à la méthode de Jacobi . . . . . . . . . . . . . . . . . 30
4 Localisation des valeurs propres: Th. de Gershgorin 33
5 Matrice dé�nie positive 375.1 Inversibilité d�une matrice dé�nie positive . . . . . . . . . . . . . 375.2 Cas d�une matrice symétrique . . . . . . . . . . . . . . . . . . . . 38
3
4 SOMMAIRE
6 Matrice à diagonale fortement dominante 39
7 Matrice réductible ou irréductible 417.1 Matrice réductible . . . . . . . . . . . . . . . . . . . . . . . . . . 417.2 Matrice irréductible . . . . . . . . . . . . . . . . . . . . . . . . . 457.3 Localisation des valeurs propres . . . . . . . . . . . . . . . . . . . 477.4 Matrice à diagonale fortement dominante . . . . . . . . . . . . . 507.5 Cas d�une matrice symétrique . . . . . . . . . . . . . . . . . . . . 51
8 Matrice positive 53
9 Matrice monotone 559.1 Condition su¢ sante pour les M-matrices . . . . . . . . . . . . . . 559.2 Borne de l�inverse d�une matrice monotone . . . . . . . . . . . . . 569.3 Stabilité d�une matrice . . . . . . . . . . . . . . . . . . . . . . . . 58
10 Analyse d�erreurs dans les systèmes linéaires 6110.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6110.2 Perturbation de la matrice . . . . . . . . . . . . . . . . . . . . . . 62
10.2.1 Estimation de l�erreur . . . . . . . . . . . . . . . . . . . . 6310.2.2 Optimalité de l�estimation . . . . . . . . . . . . . . . . . . 66
10.3 Perturbation du second membre . . . . . . . . . . . . . . . . . . . 68
11 Exercices 71
0
Notations principales
0.1 Nombres, ensembles
N ensemble des entiers naturels et N� = Nn f0g :R ensemble des nombres réels.C ensemble des nombres complexes.Mn (R) ensemble des matrices carrées réelles d�ordre n; n entier � 2.Mn (C) ensemble des matrices carrées complexes d�ordre n:
�i;j symbole de Kronecker : �i;j =�1 si i = j0 si i 6= j .
� nombre complexe conjugué de �, i.e. � = Re (�) � i Im (�), oùi2 = �1
j�jmodule d�un nombre complexe �, i.e. j�j =p�� =
qRe (�)
2+ Im (�)
2:
0.2 Vecteurs
ei i�ème vecteur colonne de la base canonique de Rn, i.e.
e1
0BBBB@10::0
1CCCCA ; e20BBBB@010:0
1CCCCA ; ::; en0BBBB@0::01
1CCCCA :
x =(xi) 2 Cn vecteur colonne, de i�ème composante complexe xi,i.e.
x
0BB@x1x2:xn
1CCA = x1e1 + ::+ xnen:
5
6 0. NOTATIONS PRINCIPALES
xt vecteur ligne (x1; ::; xn) :
0 =(0) :
1 =(1) :
x � y pour x;y 2 Rn si xi � yi 8i. On dit que x est positif six � 0:x > y pour x;y 2 Rn si xi > yi 8i.
0.2.1 Produit scalaire
hx;yi =nPi=1
xiyi produit scalaire de vecteurs x =(xi) ; y =(yi) 2 Cn.On a
hx;yi = xt:y = hy;xi x;y 2 Cnh�x;yi = � hx;yi � 2 C, x;y 2 Cnhx; �yi = � hx;yi � 2 C, x;y 2 Cnhx+ y; zi = hx; zi+ hy; zi x;y; z 2 Cnhx;y + zi = hx;yi+ hx; zi x;y; z 2 Cn
0.2.2 Orthogonalité
On dit que x;y 2 Cn sont orthogonaux si hx;yi = 0:
Un ensemble B = fb1;b2; ::;bng est orthogonal si hbi;bji = 08i 6= j:
Un ensemble orthogonal B est orthonormal si hbi;bii = 1 8i, i.e.B est orthonormal si hbi;bji = �i;j .
0.2.3 Normes
kxk2 = hx;xi12 =
�nPi=1
jxij2� 1
2
norme euclidienne sur Cn.
kxk1 = max1�i�n
jxij norme du max sur Cn:
0.2.4 Inégalité de Schwarz
Pour x;y 2Cn, on a :�����nXi=1
xiyi
�����| {z }jhx;yij
�
nXi=1
jxij2! 1
2
| {z }kxk2
nXi=1
jyij2! 1
2
| {z }kyk2
:
0.3. MATRICES 7
0.3 Matrices
A=(ai;j) matrice deMn (C) ; d�éléments ai;j = hAej ; eii. On écrit
A
0B@ a1;1 � � � a1;n... � � �
...an;1 � � � an;n
1CA :O=(0) matrice nulle.
I=(�i;j) matrice identité.
P� = (pi;j) matrice de permutation associée à une application bijec-tive � de f1; 2; ::ng dans f1; 2; ::ng, dé�nie par
P�ei = e�(i) 8i:
diag(d) ; où d =(di)2 Cn, matrice diagonale, telle que :
(diag (d))i;j =�di 8i = j0 8i 6= j :
diag(A) ; où A=(ai;j)2Mn (C), matrice diagonale, telle que :
(diag (A))i;j =�ai;i 8i = j0 8i 6= j :
A � B pour A;B 2Mn (R) si ai;j � bi;j 8i; j.
On dit que A est positive si A � O. On a
A � O , fAx � 0 8x 2 R : x � 0g :
det (A) déterminant d�une matrice A:
pA(�) = det(A� �I) polynôme caractéristique de A:� = � (A) valeur propre d�une matrice A, i.e. pA(�) = 0:
Sp (A) spectre d�une matrice A, i.e. Sp (A) =nSi=1
f�i (A)g.
� (A) = max�2Sp(A)
j�j rayon spectral d�une matrice A:
xk vecteur propre associé à une valeur propre �k = � (A), i.e.
Axk = �kxk, xk 6= 0:
A�1 matrice inverse d�une matrice inversible A. Rappelons que
A inversible, 0 =2 Sp (A), pA(0) = det (A) 6= 0, fAx = 0) x = 0g :
8 0. NOTATIONS PRINCIPALES
At =�ati;j�matrice transposée de A, dé�nie par ati;j = aj;i. On a :
hAx;yi =x; Aty
�; 8x;y 2 Cn; 8A 2Mn (R) :
Pour une matrice de permutation P� = (pi;j), on a :
P�1� = P t�:
Les opérations matricielles courantes :
(At)t
= A A 2Mn (C)(A+B)t = At +Bt A;B 2Mn (C)(�A)
t= �At � 2 C, A 2Mn (C)
(AB)t
= BtAt A;B 2Mn (C)det (At) = det (A) A 2Mn (C)�A�1
�t= (At)
�1 pour les matrices inversibles A 2Mn (C)
A� =�a�i;j�matrice adjointe de A, dé�nie par a�i;j = aj;i. On a :
hAx;yi = hx; A�yi ;x;y 2 Cn; A 2Mn (C) :
Les opérations matricielles courantes :
(A�)�
= A A 2Mn (C)(A+B)� = A� +B� A;B 2Mn (C)(�A)
�= �A� � 2 C, A 2Mn (C)
(AB)�
= B�A� A;B 2Mn (C)det (A�) = det (A) A 2Mn (C)�A�1
��= (A�)
�1 pour les matrices inversibles A 2Mn (C)
0.4 Exercices
Exercice 1 - Soit � (1) = 2; � (2) = 4; � (3) = 1; � (4) = 3. Véri�er que
P� =
0BB@0 0 1 01 0 0 00 0 0 10 1 0 0
1CCA :Exercice 2 - Soit une matrice de permutation P� = (pi;j).Véri�er que pi;k = �i;�(k): En déduire que
P�Pt� = I:
0.4. EXERCICES 9
Exercice 3 - Calculer l�inverse de A
0@ 0 1 00 0 11 0 0
1A et de B
0BB@0 0 1 01 0 0 00 0 0 10 1 0 0
1CCA :
Rép. A�1 =
0@ 0 0 11 0 00 1 0
1A, B�1 =0BB@0 1 0 00 0 0 11 0 0 00 0 1 0
1CCA :
Exercice 4 - Calculer le déterminant de A
0@ 0 �i 0i 1 1� i0 1 + i 1
1A et de B0BB@2 0 1 01 3 0 10 0 � 11 1 1 1
1CCA :Rép. det (A) = �1, det (B) = 4� � 4:
Exercice 5 - Calculer l�inverse ainsi que le polynôme caractéristique de A
0BB@0 0 1 01 0 0 10 0 �1 10 1 0 0
1CCA :
Rép. A�1 =
0BB@�1 1 �1 00 0 0 11 0 0 01 0 1 0
1CCA, pA(�) = �4 + �3 � �� �2 � 1:
Exercice 6 - soit A =
0@ 2 �1 0�1 2 00 0 1
1A, x10@ 1
1�2
1A ; x20@ 111
1A ; x30@ �1
10
1A.Véri�er que x1; x2;x1 + �x2 8� 2 R et x3 sont des vecteurs propres de A:Véri�er que B = fx1;x2;x3g est une base orthogonale de R3.
Exercice 7 - Calculer le spectre de A
0@ 1 �1 2�1 2 �1�2 �1 3
1A. Déduire � (A) :Rép. �1 = 2; �2 = 2 + i; �3 = 2� i; donc � (A) =
p5:
Exercice 8 - Soit A =
�0 i�i 0
�. Calculer les valeurs propres �k et les
vecteurs propres associés xk; tels que hxk; eki = 1.
Rép. �1 = �1; �2 = 1; x1 =�1i
�; x2 =
�i1
�:
Déduire An et exp (A) =1Pn=0
1n!A
n:
Rép. An = P�1��n1 00 �n2
�P et exp (A) = P�1
�exp (�1) 0
0 exp (�2)
�P ;
P =
�1 ii 1
�:
10 0. NOTATIONS PRINCIPALES
Donner le cas général.
1
Matrice symétrique ouhermitienne
Dé�nition 1 - Une matrice A est hermitienne si
A� = A:
Dé�nition 2 - Une matrice A est symétrique si
A� = A et A 2Mn (R) .
Exemple 1 - Pour A =
0@ 0 �i 0i 1 1� i0 1 + i 1
1A, on a
At =
0@ 0 i 0�i 1 1 + i0 1� i 1
1A ; A� =0@ 0 �i 0i 1 1� i0 1 + i 1
1A = A:
Donc A est hermitienne.
Par contre, B =
0@ 1 �1 2�1 2 �1�2 �1 3
1A est une matrice non hermitienne, puisque
B� =
0@ 1 �1 �2�1 2 �12 �1 3
1A 6= B:
Rappelons un résultat important concernant les valeurs propres d�une ma-trice hermitienne.
11
12 1. MATRICE SYMÉTRIQUE OU HERMITIENNE
Théorème 1 - Les valeurs propres d�une matrice hermitienne A 2 Mn (K),K = C ou K = R, sont réelles, i.e. Sp (A) � R. De plus, il existe une baseorthonormale B = fb1;b2; ::;bng de Kn; formée de n vecteurs propres de A.
� Preuve de Sp (A) � R. Soit � une valeur propre de A et x 6= 0 un vecteurpropre associé, tel que Ax = �x: Donc*
Ax|{z}�x
;x
+=
*x; A�|{z}
A
x
| {z }�x
+
h�x;xi = hx; �xinPi=1
�xixi =nPi=1
xi�xi
� kxk22 = � kxk22
D�où � = �) � 2 R:
� Orthogonalité des vecteurs propres. Si x1 et x2 sont deux vecteurs propresd�une matrice hermitienne A; associés respectivement à �1 et �2, avec �1 6= �2;alors x1 et x2 sont orthogonaux. En e¤et, on sait déjà que �1 et �2 sont réelles.Donc, si
Ax1=�1x1 et Ax2=�2x2;
alors *Ax1|{z}�1x1
;x2
+=
*x1; A
�|{z}A
x2| {z }�2x2
+
�1 hx1;x2i = �2 hx1;x2ii.e.
(�1 � �2)| {z }6=0
hx1;x2i = 0) hx1;x2i = 0:
1.1 Exemples
Exemple 2 - Considérons la matrice hermitienne A
0@ 0 �i 0i 1 1� i0 1 + i 1
1A.pA(�) =
�������� �i 0i 1� � 1� i0 1 + i 1� �
������ = �1+2�+2�2��3 = (1 + �) ���2 + 3�� 1� :Les valeurs propres de A sont bien réelles
�1 = �1; �2 =3
2+1
2
p5; �3 =
3
2� 12
p5:
1.1. EXEMPLES 13
Un calcul élémentaire montre que : Axi = �ixi pour x1
0@ 2i2
�1� i
1A ; x20@ 1
i�2(1� i) (1� �2)
1A ;x3
0@ 1i�3
(1� i) (1� �3)
1A. Comme les valeurs propres sont distinctes, alors B = fb1;b2;b3g ;où bi = xi
kxik2; est une base orthonormale de C3:
Exemple 3 - De même pour la matrice hermitienne A
0@ 1 1 11 1 01 0 1
1A. On véri-�e que Axi = �ixi pour
�1 = 1 �2 = 1 +p2 �3 = 1�
p2
x1
0@ 0�11
1A x2
0@ p211
1A x3
0@ �p2
11
1A :
On déduit que B = fb1;b2;b3g ; bi = xikxik2
; est une base orthonormale de R3:
Exemple 4 - Considérons le cas où une valeur propre est double.
Par exemple pour A
0@ 2 �1 0�1 2 00 0 1
1A ; on a Axi = �ixi pour�1 = 1 �2 = 1 �3 = 3
x1
0@ 110
1A x2
0@ 111
1A x3
0@ �110
1A :
Il est clair que
�2 6= �3 ) hx2;x3i = 0:�1 6= �3 ) hx1;x3i = 0:
Par contre, pour la valeur propre double � = 1, on a :
hx1;x2i 6= 0:
On peut remplacer x1 par fx1 de la forme :fx1 = x1 + �x2 8� 2 R:
En e¤et, fx1 est aussi vecteur propre de A, associé à la valeur propre �1 = 1,puisque
Afx1 = Ax1 + �Ax2 = �1x1 + � �2|{z}�1
x2 = �1 (x1 + �x2)| {z }fx1:
14 1. MATRICE SYMÉTRIQUE OU HERMITIENNE
Il véri�e en plushfx1;x3i = hx1;x3i| {z }
0
+� hx2;x3i| {z }0
= 0:
Choisissons alors �; tel que
hfx1;x2i = 0) (1 + �; 1 + �; �) :
0@ 111
1A = 0) � = �23) fx1 = 1
3
0@ 11
�2
1A :Ainsi
hfx1;x2i = hfx1;x3i = hx2;x3i = 0:On déduit donc que B = fb1;b2;b3g ; où
b1 =fx1
kfx1k2 = fx1, b2 = x2kx2k2
=1p3x2, b3 =
x3kx3k2
=1p2x3
est une base orthonormale de R3:
1.2 Remarques
Remarque 1 - Puisque
(AA�)�= (A�)
�| {z }A
A� = AA�;
alors, AA� est symétrique pour A 2Mn (R) et hermitienne pour A 2Mn (C).
Remarque 2 - Les vecteurs propres d�une matrice hermitienne ne sontpas orthogonaux, en général.
Prendre la matrice identité, x1 =�10
�et x2 =
�11
�.
Remarque 3 - Les valeurs propres de la matrice non symétrique A =
0@ 1 �1 2�1 2 �1�2 �1 3
1Asont complexes. En e¤et,
pA(�) =
������1� � �1 2�1 2� � �1�2 �1 3� �
������ = 10�13�+6�2��3 = (2� �) ��2 � 4�+ 5� :D�où
�1 = 2; �2 = 2 + i; �3 = 2� i:
Cet exemple montre que le fait que la matrice soit hermitienne estnécessaire pour établir le théorème.
1.2. REMARQUES 15
Remarque 4 - Les valeurs propres de la matrice non symétrique A
0@ 0 �2 0�1 0 �20 �1 0
1Asont réelles.
pA(�) =
�������� �2 0�1 �� �20 �1 ��
������ = ��3 + 4� = �� ��2 � 4� :Donc
�1 = �2; �2 = 0; �3 = 2:
Cet exemple montre que la symétrie d�une matrice n�est pas néces-saire pour que les valeurs propres soient réelles.
De manière générale, on a :
Lemme 1 - Pour une matrice tridiagonale d�ordre n � 2 de la forme
A =
266666664
a b 0 � � � 0
c a b. . .
...
0. . .
. . .. . . 0
.... . .
. . . a b0 � � � 0 c a
377777775, où a 2 C, b; c 2 R et bc > 0;
les valeurs propres �k (A) sont données par
�k = a+ 2b
rc
bcos
�k�
n+ 1
�; k = 1; 2; ::; n: (1.1)
� Preuve. On écrit A sous la forme
A = aI +B
et on pose
�k = a+ 2b
rc
bcos
�k�
n+ 1
�| {z }
�k
;
de sorte queAxk=�kxk , Bxk=(�k � a)| {z }
�k
xk:
Le problème donc revient à montrer que � = �k est une valeur propre de Bdans le cas où b; c > 0. Utilisons la solution générale de
br2 � �r + c = 0:
16 1. MATRICE SYMÉTRIQUE OU HERMITIENNE
i.e.
r1 =��
p�
2bet r2 =
�+p�
2b
où
� = �2 � 4bc = �4bc sin2�k�
n+ 1
�i.e.
r1 =
rc
b
�cos
�k�
n+ 1
�� i sin
�k�
n+ 1
��=
rc
bexp
��i�k�
n+ 1
��r2 =
rc
b
�cos
�k�
n+ 1
�+ i sin
�k�
n+ 1
��=
rc
bexp
�i
�k�
n+ 1
��Ainsi, pour
xs = rs2 � rs1, s = 0; 1; ::; n; n+ 1) x0 = xn+1 = 0;
et pour tout j = 1; ::; n, on a :
(Bx)j � (�x)j = cxj�1 + bxj+1 � �xj= c
�rj�12 � rj�11
�+ b
�rj+12 � rj+11
�� �
�rj2 � r
j1
�= rj�12
0@br22 � �r2 + c| {z }0
1A+ rj�11
0@br21 � �r1 + c| {z }0
1A= 0:
Remarque 5 - La valeurs propre �k; 1 � k � n, admet pour vecteur proprexk = (xj), où
xj =rj2 � r
j1
2i=
rc
bsin
�j
�k�
n+ 1
��:
Exercice 9 - Déduire les valeurs propres des matrices :
A
0@ 1 �2 0�1 1 �20 �1 1
1A et B
0BB@�1 1 0 01 �1 1 00 1 �1 10 0 1 �1
1CCA
2
Normes sur les matrices
On distingue trois types de normes surMn (C) :
1. norme.
2. norme matricielle.
3. norme matricielle subordonnée.
2.1 Norme
Dé�nition 3 - Une norme surMn (C) est une application N deMn (C) dansR, telle que :
N1) N (A) = 0) A = ON2) N (�A) = j�j �N (A) 8� 2 C, 8A 2Mn (C) :N3) N (A+B) � N (A) +N (B) 8A;B 2Mn (C) :
Exercice 10 - Il résulte de la dé�nition que :
N (O) = 0 et N (A) � 0 8A 2Mn (C) : (2.1)
Exercice 11 - L�application
N1 (A) = max1�i;j�n
jai;j j ;
est une norme surMn (C).Par contre, l�application A 2Mn (C)! min
1�i;j�njai;j j ne l�est pas.
Exercice 12 - L�application
N2 (A) =
0@ nXi;j=1
jai;j j21A 1
2
;
est une norme surMn (C). C�est la norme de Schur.
17
18 2. NORMES SUR LES MATRICES
Exercice 13 - L�application N (A) = � (A) n�est pas une norme sur Mn (C).
Prendre A�0 10 0
�.
2.2 Norme matricielle
Dé�nition 4 - Une norme matricielle surMn (C) est une norme N surMn (C),véri�ant :
N4) N (AB) � N (A)�N (B) 8A;B 2Mn (C) : (2.2)
Exercice 14 - La norme N1 n�est pas une norme matricielle. Prendre A�1 11 1
�;
B
�1 10 1
�:
Exemple 5 - La norme de Schur est une norme matricielle.La propriété N4) est une conséquence directe de l�inégalité de Schwarz.
� Preuve. En e¤et, soit C = AB, i.e. C = (ci;j) où
ci;j =nXk=1
ai;kbk;j 8 i; j 2 f1; ::; ng :
Donc
jci;j j �
nXk=1
jai;kj2! 1
2
nXk=1
jbk;j j2! 1
2
) jci;j j2 �
nXk=1
jai;kj2!
nXk=1
jbk;j j2!
nXi=1
nXj=1
jci;j j2| {z }nP
i;j=1
jci;j j2=jN2(C)j2
�
nXi=1
nXk=1
jai;kj2!!
| {z }nP
i;k=1
jai;kj2=jN2(A)j2
0@ nXj=1
nXk=1
jbk;j j2!1A
| {z }nP
k;j=1
jbk;j j2=jN2(B)j2
i.e.
N2 (C) � N2 (A)�N2 (B) :
Exercice 15 - Si N est une norme matricielle surMn (C), l�application
ND (A) = N�D�1AD
�;
où D est une matrice inversible, l�est aussi.
2.3. NORME MATRICIELLE SUBORDONNÉE 19
2.3 Norme matricielle subordonnée
Les normes vectorielles les plus couramment utilisées sur Cn sont
kxk1 = max1�i�n
jxij
kxk2 =
�nPi=1
jxij2� 1
2
:
De manière générale
Dé�nition 5 - Une norme sur Cn est une application k:k de Cn dans R, telleque :
N1) kxk = 0) x = 0N2) k�xk = j�j � kxk 8� 2 C, 8x 2Cn:N3) kx+ yk � kxk+ kyk 8x;y 2Cn:
Exercice 16 - L�application
kxk1 =nXi=1
jxij
est une norme sur Cn.Par contre, l�application x 2Cn ! min
1�i�njxij ne l�est pas.
Dé�nition 6 - Soit k:k une certaine norme vectorielle. On dé�nit une normematricielle, appelée norme matricielle subordonnée à la norme k:k, par
kAk = maxx2Cnnf0g
kAxkkxk :
Exercice 17 - Il résulte de la dé�nition que :
P1) kIk = 1:P2) kAxk � kAk � kxk 8x 2Cn, 8A 2Mn (C) :P3) kABk � kAk � kBk 8A;B 2Mn (C) :
Exercice 18 - La norme de Schur n�est pas une norme matricielle subordon-née, i.e. elle n�est pas induite par une norme vectorielle. Prendre N2 (I) :
Dé�nition 7 - A partir de la norme vectorielle k:kq, q = 1; 2 ou 1; on note lanorme matricielle subordonnée
kAkq = maxx2Cnnf0g
kAxkqkxkq
:
20 2. NORMES SUR LES MATRICES
2.4 Caractérisation de la norme kAk1
Lemme 2 - Soit A 2Mn (C). Alors
kAk1 = max1�i�n
nXj=1
jai;j j : (2.3)
� Preuve. Montrons d�abord
kAk1 � max1�i�n
nXj=1
jai;j j :
Par dé�nition
kAxk1 = max1�i�n
j(Ax)ij où (Ax)i =nXj=1
ai;jxj :
Or
j(Ax)ij =
������nXj=1
ai;jxj
������ �nXj=1
jai;j j jxj j|{z}�kxk1
� kxk1nXj=1
jai;j j :
Donc
kAxk1 � kxk1 max1�i�n
nXj=1
jai;j j ) kAk1 � max1�i�n
nXj=1
jai;j j :
Il reste à montrer
kAk1 � max1�i�n
nXj=1
jai;j j :
En e¤et, soit k un indice, tel que
nXj=1
jak;j j = max1�i�n
nXj=1
jai;j j ;
et soit x, tel que
xj =
(ak;jjak;j j si ak;j 6= 01 si ak;j = 0
:
Ainsikxk1 = 1;
et
(Ax)k =nXj=1
ak;jxj =nXj=1
(ak;jak;jjak;j j si ak;j 6= 0ak;j si ak;j = 0
=nXj=1
�jak;j j si ak;j 6= 0ak;j si ak;j = 0
=nXj=1
jak;j j :
2.5. CARACTÉRISATION DE LA NORME kAk2 21
Donc
kAxk1 � (Ax)k =nXj=1
jak;j j = max1�i�n
nXj=1
jai;j j :
Alors,
kAk1 � kAxk1kxk1
= kAxk1 � max1�i�n
nXj=1
jai;j j :
Exemple 6 - Pour A =
0@ 1 �1 0�1 1 �31 �1 �1
1A, on akAk1 = max f2; 5; 3g = 5 et
At 1 = max f3; 3; 4g = 4:
Exemple 7 - La matrice de Hilbert A
0BBB@1 1
2 � � � 1n
12
13 � � � 1
n+1...
... � � �...
1n
1n+1 � � � 1
2n�1
1CCCA a pour norme
kAk1 =nPk=1
1k :
2.5 Caractérisation de la norme kAk2
Lemme 3 - Soit A 2Mn (C). Alors
kAk2 =�� (A) pour les matrices hermitiennes.p� (A�A) cas général.
(2.4)
� Preuve. On sait, pour une matrice hermitienne A, qu�il existe une base or-thonormale de Cn; formée de vecteurs propres b1; b2; ::; bn. Donc 8x 2 Cn
x =nXi=1
xi|{z}=hx;bii2C
bi, kxk22 =nXi=1
jxij2 ;
et l�on a :
Ax =nXi=1
xiAbi =nXi=1
xi�ibi:
Ainsi,
kAxk22 =nX
i;j=1
�ixi�ixj hbi;bji| {z }�i;j
=
nXi=1
0B@ j�ij|{z}��(A)
1CA2
jxij2 � � (A)2nXi=1
jxij2| {z }kxk22
= (� (A) kxk2)2:
22 2. NORMES SUR LES MATRICES
Il résultekAxk2kxk2
� � (A)8x 2Cn n f0g ) kAk2 � � (A) :
Par ailleurs, pour un certain indice k, tel que : j�kj = � (A), on a aussi
Abk = �kbk ) kAbkk2 = k�kbkk2 = j�kj|{z}�(A)
�kbkk2
) kAbkk2kbkk2
= � (A)) kAk2 � � (A) :
D�où le résultat recherché pour les matrices hermitiennes. Le cas général sedéduit de manière similaire.
Exemple 8 - Soit la matrice symétrique A =
0@ 0 �1 1�1 1 �11 �1 0
1A : On véri�eque les valeurs propres de A sont
�1 = �1; �2 =p2 + 1; �3 = 1�
p2:
DonckAk2 = � (A) =
p2 + 1:
Exemple 9 - Soit la matrice non symétrique A =�1 10 1
�. On voit que les
valeurs propres sont�1 = �2 = 1) � (A) = 1:
Par (2.4), on obtient
A�A =
�1 01 1
��1 10 1
�=
�1 11 2
�) �1 (A
�A) =3
2+1
2
p5, �2 (A�A) =
3
2� 12
p5
) kAk2 =r3
2+1
2
p5:
On constate que � (A) 6= kAk2, mais
� (A) < kAk2 :
La symétrie de la matrice est donc nécessaire pour établir (2.4).
3
Lien de la norme avec lerayon spectral
3.1 Majoration du rayon spectral par la normematricielle : Théorème de Browne
Théorème 2 (Browne 1928) - Soit N une norme matricielle, subordonnéeou non. Alors,
� (A) � N (A) 8A 2Mn (C) : (3.1)
� Preuve. Soit � une valeur propre, tel que : j�j = � (A). Donc,
Ax = �x pour x 6= 0:
On lui associe la matrice M 2Mn (C) dé�nie par :
M = xxt =
0BB@x21 x1x2 : x1xn
x2x1 x22 : x2xn: : : :
xnx1 xnx2 : x2n
1CCA 6= O:
Alors,
N
0@� xxt|{z}M
1A = N
0@A xxt|{z}M
1Aj�j|{z}�(A)
N (M)| {z }6=0
= N (AM) � N (A)�N (M)| {z }6=0
:
D�où le résultat.
23
24 3. LIEN DE LA NORME AVEC LE RAYON SPECTRAL
Exemple 10 - Pour A
0@ 0 1 10 1 �11 �1 0
1A, on a : N2 (A) = p6; kAk1 = 2;
kAtk1 = 3: Par le théorème de Browne on obtient
� (A) � 2:
Cependant, la valeur exacte est � (A) =p2; puisque Sp (A) =
�1;p2;�
p2:
Remarque 6 - Remarquons que
� (A)| {z }p2
� N1 (A)| {z }1
:
La propriété N4) est donc nécessaire pour établir (3.1).
Exemple 11 - Pour A
0@ 0 0 1�1 1 �21 �1 0
1A ; on a : N2 (A) = 3; kAk1 = 4 et
kAtk1 = 3: On conclut que� (A) � 3:
En e¤et, � (A) = 1+p13
2 ; puisque Sp (A) =n0; 1+
p13
2 ; 1�p13
2
o:
Exemple 12 - En choisissant pour norme matricielle ND (A) = D�1AD
1
où D =diag(d), d 2Rn; d > 0; le théorème de Browne nous donne :
�(A)|{z}�(D�1AD)
� max1�i�n
nPj=1
jai;j j dj
di| {z }kD�1ADk1
8A 2Mn (C) :
Cette estimation est optimale.
Par exemple, pour A =
0@ 0 0 1�1 1 �21 �1 0
1A, on a :� (A) =
D�1AD 1 pour d1 = d3 =
1
2
p2 et d2 = 1:
Véri�cation :
D�1AD =
0@ 1d1
0 0
0 1d2
0
0 0 1d3
1A0@ 1 1 11 2 11 1 1
1A0@ d1 0 00 d2 00 0 d3
1A =
0@ 1 1d1d2
1d1d3
1d2d1 2 1
d2d3
1d3d1
1d3d2 1
1A ;donc D�1AD
1 = max
�1 +
d2 + d3d1
; 2 +d1 + d3d2
; 1 +d1 + d2d3
�8d > 0:
3.2. MAJORATION D�UNE NORME PAR LE RAYON SPECTRAL 25
Pour d1 = d3 = 12
p2 et d2 = 1, on a :
1 +d2 + d3d1
= 2 +d1 + d3d2
= 1 +d1 + d2d3
= 2 +p2:
D�où D�1AD 1 = 2 +
p2:
3.2 Majoration d�une norme par le rayon spec-tral
On a vu dans le cas où A 2Mn (C) est une matrice hermitienne que
N (A) = � (A) pour la norme N (B) = kBk2 8B 2Mn (C) :
Dans le cas où la matrice A 2 Mn (C) est diagonalisable, i.e. il existe unematrice de changement de base U , telle que :
U�1AU = diag (�) ;
on a aussi
N (A) = � (A) pour la norme N (B) = U�1BU 1 8B 2Mn (C) :
Dans le cas général, on remarque que l�inégalité suivante
N (A) � � (A) ;
est toujours fausse pour des matrices telles que : � (A) = 0 et A 6= O. C�est le
cas par exemple de la matrice A =�0 10 0
�.
Cependant, on montre
Théorème 3 - Pour A 2 Mn (C) et � > 0, il existe au moins une normematricielle subordonnée k:kA;�, telle que :
kAkA;� � � (A) + �:
� Preuve. La démonstration se base sur l�existence d�une matrice de changementde base U , telle que :
U�1AU =
0BBBB@�1 c1;2 � � � c1;n
0 �2. . .
......
. . .. . . cn�1;n
0 � � � 0 �n
1CCCCA ;
26 3. LIEN DE LA NORME AVEC LE RAYON SPECTRAL
les �k étant les valeurs propres de A. Sous forme matricielle, on écrit
U�1AU = diag (�) + C:
Introduisons la matrice diagonale D� =diag(d), où d =�1; �; �2; ::; �n�1
�,
� > 0, de sorte que :
(UD�)�1A (UD�) = D
�1� U�1AUD� = diag (�) +D
�1� CD�
= diag (�) +
0BBBB@0 �c1;2 � � � �n�1c1;n...
. . .. . .
...... � � � . . . �cn�1;n0 � � � � � � 0
1CCCCA :Ainsi, pour �, telle que :
D�1� CD�
1 = max
1�i�n
nXj=i+1
�j�i jci;j j � �;
on obtient (UD�)�1A (UD�) 1� kdiag (�)k1| {z }
�(A)
+ D�1
� CD� 1| {z }
�
= � (A) + �:
La norme recherchée est
kBkA;� = (UD�)�1B (UD�)
1;
qui s�écrit aussi sous la forme :
kBkA;� = maxx6=0
(UD�)�1B (UD�)x| {z }y
1
kxk1= max
y 6=0
(UD�)�1By 1 (UD�)�1 y 1
= maxy 6=0
kBykA;�kykA;�
oùkykA;� =
(UD�)�1 y 1:
Exemple 13 - Pour la matrice A
0@ �1 0 11 �2 �11 0 �1
1A on peut prendre la norme
kBkA;� = (UD�)�1B (UD�)
1; 0 < � � �;
où
U =
0@ 12 0 1
20 1 012 0 � 1
2
1A et D� =
0@ 1 0 00 � 0
0 0 �2
1A ;
3.3. CONVERGENCE D�UNE SUITE DE MATRICES 27
car0@ 1 0 10 1 01 0 �1
1A| {z }
U�1
0@ �1 0 11 �2 �11 0 �1
1A| {z }
A
0@ 12 0 1
20 1 012 0 � 1
2
1A| {z }
U
=
0@ 0 0 00 �2 00 0 �2
1A| {z }
diag(�)
+
0@ 0 0 00 0 10 0 0
1A| {z }
C
et
D�1� CD�
1 = � � � où D�1
� CD� =
0@ 1 0 00 1
� 00 0 1
�2
1A0@ 0 0 00 0 10 0 0
1A0@ 1 0 00 � 0
0 0 �2
1A =
0@ 0 0 00 0 �0 0 0
1A :En e¤et, on a :
UD� =
0@ 12 0 1
20 1 012 0 � 1
2
1A0@ 1 0 00 � 0
0 0 �2
1A =
0@ 12 0 1
2�2
0 � 012 0 � 1
2�2
1A) (UD�)�1=
0@ 1 0 10 1
� 01�2
0 � 1�2
1A :Donc
(UD�)�1A (UD�) =
0@ 1 0 10 1
� 01�2
0 � 1�2
1A0@ �1 0 11 �2 �11 0 �1
1A0@ 12 0 1
2�2
0 � 012 0 � 1
2�2
1A =
0@ 0 0 00 �2 �0 0 �2
1A :Ainsi, comme Sp = f0;�2;�2g = f0;�2g, on retrouve
kAkA;� = (UD�)�1A (UD�)
1= 2|{z}
�(A)
+ �|{z}��
� � (A) + �:
3.3 Convergence d�une suite de matrices
Dé�nition 8 - On note Ak = AA:::A| {z }k fois
=�a(k)i;j
�pour A 2 Mn (C) et k 2 N�.
On écritlimk!1
Ak = 0 si limk!1
a(k)i;j = 0 8i; j:
Remarque 7 - Ce qui est équivalent à limk!1
Ak = 0 pour toute norme ma-tricielle, puisque toutes les normes matricielles sur Mn (C) sont équivalentes,i.e. il existe deux nombres �1 et �2 strictement positifs, qui peuvent dépendrede n, tels que :
�1 kAk1 � kAk � �2 kAk1 8A 2Mn (C) :
Théorème 4 - Soit A 2Mn (C). Les conditions suivantes sont équivalentes:P1) lim
k!1Ak = 0,
P2) limk!1
Akx = 0 8x 2Cn;P3) � (A) < 1;P4) kAk < 1 pour au moins une norme matricielle subordonnée k:k.
28 3. LIEN DE LA NORME AVEC LE RAYON SPECTRAL
� Preuve.
P1))P2) : Résulte de l�inégalité Akx � Ak � kxk :
P2))P3) : Si � (A) � 1, on peut trouver un vecteur propre x, tel que :Ax = �x;j�j = � (A) � 1: Alors la suite de vecteurs Akx = �kx ne converge pas vers 0.
P3))P4) : Choisissons pour norme k:kA;�. Alors Ak
A;���kAkA;�
�k�
(� (A) + �)k: Dans le cas où � (A) < 1, on peut trouver 0 < � < 1�� (A), telle
que Ak
A;�� rk pour r = � (A)+� < 1. On conclut que lim
k!1
Ak A;�= 0:
P4))P1) : Conséquence de l�inégalité Ak � kAkk :
Exemple 14 - Soit A =
�0 10 a
�; a 2 R�. On a : Sp (A) = f0; ag : On
véri�e que :
Udiag (�)U�1 =�1 10 a
�0BB@�1|{z}0
0
0 �2|{z}a
1CCA� 1 � 1a
0 1a
�= A:
Ainsi,
Ak = U
0BBB@�k1|{z}0
0
0 �k2|{z}ak
1CCCAU�1:On voit que P1),P3), i.e.
limk!1
Ak = 0, limk!1
��ak�� = limk!1
� (A)k= 0:
Exemple 15 - Pour A =
0@ 1 1 10 1 11 1 0
1A et x = 1, on a :
Ax =
0@ 1 1 10 1 11 1 0
1A0@ 111
1A =
0@ 322
1A � 2x)Akx �2kx:
Donc limk!1
Ak1 6= 0 : On conclut que � (A) � 1.
Lemme 4 - Soit A 2Mn (C). La série I+A+A2+ :: converge vers (I �A)�1si et seulement si � (A) < 1.
3.4. STABILITÉ D�UN SYSTÈME ITÉRATIF 29
� Preuve. Supposons que � (A) < 1. La matrice (I �A) est donc inversible,puisque d�après P4), on a :
(I �A)x = 0)kxk = kAxk � kAk�kxk )
0@1� kAk|{z}<1
1A kxk � 0) x = 0:
Posons Sk = I +A+A2 + ::+Ak: Donc
Sk (I �A) = I �Ak+1 , Sk = (I �A)�1�I �Ak+1
�, Sk � (I �A)�1 = � (I �A)�1Ak+1
Par conséquent, en utilisant la norme de P4) Sk � (I �A)�1 = (I �A)�1Ak+1 � (I �A)�1 � Ak+1 :Ainsi,
limk!1
Sk � (I �A)�1 � (I �A)�1 � limk!1
Ak+1 | {z }0
:
Réciproquement, si la série I + A + A2 + :: existe, on a limk!1
Ak = 0, donc
� (A) < 1:
3.4 Stabilité d�un système itératif
On en déduit le résultat très utile suivant :
Lemme 5 - Soit B 2Mn (C) et b 2Cn. La stabilité d�un système itératif 1
xk+1 = Bxk + b
est liée à la condition (nécessaire et su¤usante)
� (B) < 1:
1 i.e. pour une norme k:k sur Cn, il existe une constante positive indépendante de m; telleque :
kxmk � C|{z}constante p ositive indép endante de m
8m .
30 3. LIEN DE LA NORME AVEC LE RAYON SPECTRAL
3.5 Application à la méthode de Jacobi
Soit à résoudre le système :8<: �x1 � x2 = 1�x1 + �x2 � x3 = 0�x2 + �x3 = 1
; � =2n�p2; 0;�
p2o;
i.e.
0@ � �1 0�1 � �10 �1 �
1A| {z }
A
0@ x1x2x3
1A| {z }
x
=
0@ 101
1A| {z }
y
) x =1
�2 � 2
0@ �2�
1A
La méthode standard de Jacobi consite, en partant de x0 donné, à calculerde proche en proche xk+1; k 2 N; par :8<:
�xk+11 � xk2 = 1
�xk1 + �xk+12 � xk3 = 0
�xk2 + �xk+13 = 1
,
8<:xk+11 = 1
�
�1 + xk2
�xk+12 = 1
�
�xk1 + x
k3
�xk+13 = 1
�
�1 + xk2
�où
xk+1 = Jxk + b avec J =1
�
0@ 0 1 01 0 10 1 0
1A ; b =0@ 1
�01�
1A :De manière générale, la méthode de Jacobi pour la résolution d�un système
linéaire, de la forme Ax = y; consiste à résoudre
Dxk+1 + (A�D)xk = y; i.e. Dxk+1 = y+(D �A)xk;
ou encorexk+1 = D�1 (D �A)| {z }
J
xk +D�1y| {z }b
:
Véri�cation pour l�exemple :
J = D�1 (D �A) =
0@ 1� 0 00 1
� 00 0 1
�
1A0@ 0 1 01 0 10 1 0
1A =1
�
0@ 0 1 01 0 10 1 0
1A :On remarque que
Sp (J) =
(0;
p2
�;�p2
�
)) � (J) =
�����p2
�
����� < 1, j�j >p2:
Ainsi, le système n�est stable que si
j�j >p2:
3.5. APPLICATION À LA MÉTHODE DE JACOBI 31
Par exemple, pour � = 1, i.e. pour J =
0@ 0 1 01 0 10 1 0
1A ; b =0@ 101
1A, on a :� (J) =
p2 > 1
Donclimk!1
��xk�� =1:On trouve en partant de x0 = 0 :
x1 =
0@ 0 1 01 0 10 1 0
1A| {z }
J
0@ 000
1A| {z }
x0
+
0@ 101
1A| {z }
b
=
0@ 101
1A ; ) x� x1 2=
0@ �2�2�2
1A 2
= 2p3
x2 =
0@ 0 1 01 0 10 1 0
1A| {z }
J
0@ 101
1A| {z }
x1
+
0@ 101
1A| {z }
b
=
0@ 121
1A) x� x2
2=
0@ �2�4�2
1A 2
= 2p6
� � �
x6 =
0@ 0 1 01 0 10 1 0
1A| {z }
J
0@ 767
1A| {z }
x5
+
0@ 101
1A| {z }
b
=
0@ 7147
1A) x� x6
2=
0@ �8�16�8
1A 2
= 8p3
� � �
On constate qu�on s�éloigne de la solution du système : x =
0@ �1�2�1
1A :Par contre, pour � = 2, i.e. pour
b =
0@ 12012
1A ; J = 1
2
0@ 0 1 01 0 10 1 0
1A) � (J) =
p2
2< 1
on constate la converge vers la solution :
x1 =1
2
0@ 0 1 01 0 10 1 0
1A0@ 000
1A+0@ 1
2012
1A =
0@ 12012
1A) x� x1
2=1
2
p6
x2 =1
2
0@ 0 1 01 0 10 1 0
1A0@ 101
1A+0@ 1
2012
1A =
0@ 12112
1A) x� x2
2=1
2
p2
� � �
x4 =1
2
0@ 0 1 01 0 10 1 0
1A0@ 1121
1A+0@ 1
2012
1A =
0@ 34134
1A) x� x4
2=1
4
p2
� � �
32 3. LIEN DE LA NORME AVEC LE RAYON SPECTRAL
A la limite on trouve :
limk!1
x� xk 2= 0:
4
Localisation des valeurspropres: Th. de Gershgorin
Dans la suite, on associe à une matrice A 2Mn (C) le nombre positif
�k (A) =
0B@ nXj 6=kj=1
jak;j j
1CA où 1 � k � n:
On dit que �k (A) est le k�ième rayon de Gershgorin et on note Dk (A) ledisque dé�ni par
Dk (A) = fz 2 C, jz � ak;kj � �k (A)g :Théorème 5 ( Gershgorin 1931) - Pour tout A 2 Mn (C) ; il existe un in-dice k; 1 � k � n; pour lequel
j� (A)� ak;kj � �k (A) :i.e.
� 2n[i=1
Di (A) 8� 2 Sp (A) :
� Preuve. Soit � une valeur propre de A et x 6= 0 un vecteur propre associé,i.e. Ax = �x:Soit k un indice, tel que jxkj = kxk1 :Le k�ième ligne du système algébrique s�écrit :
(Ax)k =(�x)k)ak;kxk +Xi 6=k
ak;ixi = �xk) (�� ak;k)xk =Xi 6=k
ak;ixi:
Alors
j�� ak;kj � jxkj|{z}kxk1
�Xi 6=k
jak;ij � jxij|{z}�kxk1
�Xi 6=k
jak;ij| {z }�k(A)
kxk1 :
33
34 4. LOCALISATION DES VALEURS PROPRES: TH. DE GERSHGORIN
D�où j�� ak;kj � �k (A) :
Exemple 16 - Les valeurs propres de la matrice A
0@ i �i 00 �1 10 0 1
1A sont con-
tenues1 dans la région3Si=1
Di (A) formée de la réunion des trois disques :
D1 (A) : j�� ij � 1D2 (A) : j�+ 1j � 1D3 (A) : j�� 1j � 0 =) � = 1:
x-
y
6
&%'$q i&%'$q
-1 1qe
Exemple 17 - On peut déduire également une nouvelle région où sont localiséesles valeurs propres, puisque les valeurs propres d�une matrice sont les mêmesque celles de la matrice transposée associée. En appliquant le théorème de Ger-
shgorin à At =
0@ i 0 0�i �1 00 1 1
1A ; on obtient la région 3Si=1
Di (At) constituée
des disques :
D1 (At) : j�� ij � 0 =) � = i:
D2 (At) : j�+ 1j � 1
D3 (At) : j�� 1j � 1
1à comparer avec les valeurs propres de A
�1 = i; �2 = �1; �3 = 1:
35
x-
y
6
cq iq&%'$
-1 1q&%'$
On conclut �nalement que les valeurs propres sont contenues dans la région 3[i=1
Di (A)
!\ 3[i=1
Di�At�!:
x-
y
6
cq iq"!# -1 1qc
Exemple 18 - Les valeurs propres de la matrice A =
0BBBBBBB@
2 �1 0 � � � 0
1. . . �1 . . .
...
0. . .
. . .. . . 0
.... . .
. . .. . . �1
0 � � � 0 n� 1 2
1CCCCCCCAsont contenues dans
n[i=1
Di (A)
!= fz 2 C; jz � 2j � n� 1g :
36 4. LOCALISATION DES VALEURS PROPRES: TH. DE GERSHGORIN
5
Matrice dé�nie positive
Dé�nition 9 - On dit que A 2Mn (R) est dé�nie positive si
hAx;xi > 0 8x 2Rn, x 6= 0:
Exemple 19 - La matrice A�
1 2�1 1
�est telle que
hAx;xi = jx1j2 + jx2j2 + x1x2 =1
2
�jx1j2 + jx2j2
�+1
2(x1 + x2)
2> 0 8x 6= 0:
Donc A est dé�nie positive. Par contre la matrice B��1 11 �1
�n�est pas
dé�nie positive, puisque hB1;1i = 0 � 0:
Remarque 8 - En fait, la condition: bi;i = hBei; eii > 0 8i, est nécessairepour qu�une matrice B 2Mn (R) soit dé�nie positive.
5.1 Inversibilité d�une matrice dé�nie positive
Lemme 6 - Si A est une matrice dé�nie positive alors A est inversible, i.e.0 =2 Sp (A) :
� Preuve. On doit montrer que Ax = 0) x = 0: En e¤et, Ax = 0)hAx;xi = 0: Mais, cela n�est possible, lorsque A est dé�nie positive, que six = 0:
Remarque 9 - La réciproque est fausse comme le montre la matrice A��1 00 1
�qui est inversible, mais non dé�nie positive puisque a1;1 � 0:
37
38 5. MATRICE DÉFINIE POSITIVE
5.2 Cas d�une matrice symétrique
Théorème 6 - Soit A 2Mn (R) une matrice symétrique. Alors
A est dé�nie positive, les valeurs propres de A sont réelles > 0: (5.1)
� Preuve. Il existe, dans le cas symétrique, une base orthonormaleB = fb1;b2; ::;bngde Rn; formée de n vecteurs propres de A. En particulier, tout x 2 Rn est dela forme : x =
nPi=1
xibi avec kxk22 =nPi=1
jxij2 : Donc
hAx;xi =nX
i;j=1
xixj
*Abi|{z}�ibi
;bj
+=
nXi;j=1
�ixixj hbi;bji| {z }�i;j
: i.e. hAx;xi =nXi=1
�i jxij2 :
Ainsi
A est dé�nie positive, hAx;xi > 0 8x 6= 0,nXi=1
�i jxij2 > 0 8x 6= 0, �i > 0 8i:
Exemple 20 - Pour A�1 20 1
�; on a �1 = �2 = 1 > 0, mais elle n�est pas
dé�nie positive, puisque
hAx;xi =*�
1 20 1
��1
�1
�| {z }
x
;
�1
�1
�| {z }
x
+=
���1�1
�;
�1
�1
��= 0:
Cet exemple montre que la symétrie de la matrice est nécessaire pourétablir (5.1).
Remarque 10 - Pour toute matrice symétrique A 2Mn (R), on a :
min1�i�n
f�i (A)g kxk22 � hAx;xi � max1�i�n
f�i (A)g kxk22 8x 2Rn:
Exemple 21 - La matrice symétrique A
266666664
a b 0 � � � 0
b. . .
. . .. . .
...
0. . .
. . .. . . 0
.... . .
. . .. . . b
0 � � � 0 b a
377777775est dé�nie
positive, si et seulement si,
�k = a+ 2b cos
�k�
n+ 1
�> 0 8k = 1; ::; n:
Ce résultat est obtenu en utilisant (1.1).
6
Matrice à diagonalefortement dominante
Dé�nition 10 - On dit que A 2Mn (C) est une matrice à
diagonale dominante si jai;ij � �i (A) 8 i = 1; ::; n:diagonale strictement dominante si jai;ij > �i (A) 8 i = 1; ::; n:
diagonale fortement dominante si�jai;ij � �i (A) 8 i 2 f1; ::; ng :jak;kj > �k (A) pour un certain k 2 f1; ::; ng :
Exemple 22 - Les rayons de Gershgorin associés à A =
0@ a �2 �10 b 12 3 c
1Asont �1 = 3; �2 = 1 et �3 = 5. La matrice A est à
diagonale dominante si jaj � 3; jbj � 1 et jcj � 5:diagonale strictement dominante si jaj > 3; jbj > 1 et jcj > 5:
diagonale fortement dominante si
8<: jaj � 3; jbj � 1, jcj � 5;et
jaj+ jbj+ jcj > 9:
Exemple 23 - La matrice
A =
0BBBBBB@1 �1 0 : : 01 2 �1 0 : 00 2 3 �1 0 :: : : : : :0 0 0 n� 2 n� 1 �10 0 0 0 n� 1 n
1CCCCCCA ; n � 2;
n�est pas à diagonale strictement dominante, mais à diagonale fortement domi-nante.
39
40 6. MATRICE À DIAGONALE FORTEMENT DOMINANTE
Théorème 7 - Si A 2 Mn (C) est une matrice à diagonale strictement domi-nante alors A est inversible, i.e. 0 =2 Sp (A) :
� Preuve. On doit montrer que
Ax = 0) x = 0:
Soit k un indice tel que jxkj = kxk1. Alors
Ax = 0 ) ak;kxk = �Pj 6=k
ak;jxj
) jak;kj � jxkj|{z}kxk1
�Pj 6=k
jak;j j � jxj j|{z}�kxk1
= kxk1 �k (A)
)
0B@jak;kj � �k (A)| {z }>0
1CA kxk1 � 0
) kxk1 � 0) x = 0:
Exemple 24 - La matrice A =
0@ 2 0 �10 �2 1
�1 1 3
1A est à digonale strictement
dominante, donc inversible.
Exemple 25 - De même, la matrice A =
0BBBBBB@2 �1 0 : : 01 3 �1 0 : 00 2 4 �1 0 :: : : : : :0 0 0 n� 2 n �10 0 0 0 n� 1 n+ 1
1CCCCCCA,n � 3, est à digonale strictement dominante, donc inversible.
Remarque 11 - La réciproque est évidement fausse. La matrice A =�0 11 0
�est inversible mais à diagonale non dominante.
Remarque 12 - Une matrice à diagonale fortement dominante n�est pas néces-
sairement inversible. C�est le cas de la matrice A =�1 00 0
�:
7
Matrice réductible ouirréductible
7.1 Matrice réductible
Dé�nition 11 - Une matrice A 2Mn (C) est réductible s�il existe une matricede permutation P�, telle que :
P t�AP� =
�A1;1 A1;20 A2;2
�;
où A1;1 et A2;2 sont deux matrices carrées.
Exemple 26 - Remarquons d�abord qu�on a :
�P t�AP�
�i;j=P t�AP�ej ; ei
�=
*AP�ej| {z }e�(j)
; P�ei|{z}e�(i)
+
=Ae�(j); e�(i)
�= a�(i);�(j):
Considérons maintenant la matrice A =
0@ 11 12 130 22 031 32 33
1A.Comme a2;1 = a2;3 = 0, on obtient une partition de l�ensemble des indicesf1; 2; 3g en K = f2g et Kc = f1; 3g, de sorte que :
ai;j = 0 8i 2 K, j 2 Kc:
Donc �P t�AP�
�3;1= a�(3);�(1) = 0;�
P t�AP��3;2= a�(3);�(2) = 0;
41
42 7. MATRICE RÉDUCTIBLE OU IRRÉDUCTIBLE
pour� (3) 2 K = f2g ; � (1) ; � (2) 2 Kc = f1; 3g :
Ainsi, pour le cas � (1) = 3; � (2) = 1; on constate que
P t�AP� =
0@ 0 0 11 0 00 1 0
1A0@ 11 12 130 22 031 32 33
1A0@ 0 1 00 0 11 0 0
1A =
0@ 33 31 3213 11 120 0 22
1A
=
0BBBBB@
�33 3113 11
�| {z }
A1;1
�3212
�| {z }A1;2�
0 0�| {z }
A2;1
(22)|{z}A2;2
1CCCCCA :
La matrice P t�AP� s�écrit donc sous la forme
P t�AP� =
�A1;1 A1;20 A2;2
�;
où A1;1 et A2;2 sont deux matrices carrées, donc A est réductible.
De même, pour le cas � (1) = 1; � (2) = 3; on a
P t�AP� =
0@ 1 0 00 0 10 1 0
1A0@ 11 12 130 22 031 32 33
1A0@ 1 0 00 0 10 1 0
1A =
0@ 11 13 1231 33 320 0 22
1A
=
0BBBBB@
�11 1331 33
�| {z }
A1;1
�1232
�| {z }A1;2�
0 0�| {z }
A2;1
(22)|{z}A2;2
1CCCCCA :
Exemple 27 - Considérons la matrice A =
0BB@11 12 13 140 22 0 031 32 33 3441 42 43 44
1CCA :Comme a2;1 = a2;3 = a2;4 = 0, on obtient la partition de l�ensemble f1; 2; 3; 4gen
K = f2g et Kc = f1; 3; 4g ;telle que :
ai;j = 0 8i 2 K, j 2 Kc:
i.e. �P t�AP�
�4;1= a�(4);�(1) = 0;�
P t�AP��4;2= a�(4);�(2) = 0;�
P t�AP��4;3= a�(4);�(3) = 0;
7.1. MATRICE RÉDUCTIBLE 43
pour
� (4) 2 K = f2g et � (1) ; � (2) ; � (3) 2 Kc = f1; 3; 4g :
Ce qui donne six permutations :
1�2�3�4�5�6�
� (1) 1 3 4 1 3 4� (2) 3 4 1 4 1 3� (3) 4 1 3 3 4 1
Pour chaque cas, on obtient
P t�AP� =
�A1;1 A1;20 A2;2
�;
où A1;1 et A2;2 sont deux matrices carrées, donc A est irréductible.
Par exemple, pour le cas 1: � (1) = 1; � (2) = 3, � (3) = 4; on a
P t�AP� =
0BB@1 0 0 00 0 1 00 0 0 10 1 0 0
1CCA0BB@11 12 13 140 22 0 031 32 33 3441 42 43 44
1CCA0BB@1 0 0 00 0 0 10 1 0 00 0 1 0
1CCA =
0BB@11 13 14 1231 33 34 3241 43 44 420 0 0 22
1CCA
=
0BBBBBBB@
0@ 11 13 1431 33 3441 43 44
1A| {z }
A1;1
0@ 123242
1A| {z }
A1;2�0 0 0
�| {z }A2;1
(22)|{z}A2;2
1CCCCCCCA:
Exemple 28 - Soit A =
0BB@11 12 13 140 22 0 2431 32 33 340 42 0 44
1CCA :Ici, on a :
ai;j = 0 8i 2 K = f2; 4g , j 2 Kc = f1; 3g ;
où K et Kc est une partition de f1; 2; 3; 4g. Donc
�P t�AP�
�i;j= a�(i);�(j) = 0 8 (i; � (i)) 2 f3; 4g �K, (j; � (j)) 2 f1; 2g �Kc:
44 7. MATRICE RÉDUCTIBLE OU IRRÉDUCTIBLE
Par exemple pour � (3) = 2; � (4) = 4; � (1) = 1; � (2) = 3, on trouve
P t�AP� =
0BB@1 0 0 00 0 1 00 1 0 00 0 0 1
1CCA0BB@11 12 13 140 22 0 2431 32 33 340 42 0 44
1CCA0BB@1 0 0 00 0 1 00 1 0 00 0 0 1
1CCA =
0BB@11 13 12 1431 33 32 340 0 22 240 0 42 44
1CCA
=
0BBBBBBB@
�11 1331 33
�| {z }
A1;1
�12 1432 34
�| {z }
A1;2�0 00 0
�| {z }
A2;1
�22 2442 44
�| {z }
A2;2
1CCCCCCCA;
Donc A est réductible.
De manière générale, on a :
Lemme 7 - Une matrice A 2Mn (C) est réductible, si et seulement si, il existeune partition de l�ensemble f1; 2; ::; ng en K et Kc, telle que :
ai;j = 0 8i 2 K, j 2 Kc:
� Preuve. Si A 2 Mn (C) est réductible, alors il existe une matrice de permu-tation P� , telle que :
P t�AP� =
�A1;1 A1;20 A2;2
�;
où A1;1 2Mp (C) ; 1 � p < n; et A2;2 2Mn�p (C). Donc, pour
i 2 K = f� (i0) ; p+ 1 � i0 � ng et j 2 Kc = f� (j0) ; 1 � j0 � pg ,
on obtientai;j = a�(i0);�(j0) =
�P t�AP�
�i0;j0
= 0:
Réciproquement, soit une partition de f1; 2; ::; ng en K et Kc, telle que :
ai;j = 0 8i 2 K; j 2 Kc:
On dé�nit une permutation, telle que :
� : f1; ::; pg ! K: fp+ 1; ::; ng ! Kc
On trouve pour i 2 fp+ 1; ::; ng et j 2 f1; ::; pg�P t�AP�
�i;j= a�(i);�(j) = 0:
Remarque 13 - Si une ligne k d�une matrice A est nulle alors A est réductible,puisque
ai;j = 0 8i 2 K = fkg et j 2 Kc = f1; 2; ::; ng nK:
7.2. MATRICE IRRÉDUCTIBLE 45
7.2 Matrice irréductible
Dé�nition 12 - Une matrice A 2Mn (C) est irréductible si A est une matricenon réductible.
A�n, de caractériser ce type de matrice, on associe à A 2Mn (C) un graphede n sommets notés S1; ::; Sn.
Dé�nition 13 (Arc) - Un arc du graphe Si y Sj relie Si à Sj si ai;j 6= 0:
Exemple 29 - Le graphe de la matrice A =
0@ 0 1 00 1 �11 �1 0
1A comporte 5 arcs
liés à 3 sommets.
Les arcs du graphe de A :
S1 y S2 a1;2 6= 0:S2 y S2 a2;2 6= 0:S2 y S3 a2;3 6= 0:S3 y S1 a3;1 6= 0:S3 y S2 a3;2 6= 0:
uS1�����*uS2HHHHHjHH
HHHY uS3�
Graphe de la matrice A
Exemple 30 - Pour la matrice A =
0BB@0 12 0 00 22 0 031 32 0 340 0 43 0
1CCA, on a :
uS1�����*uS2
HHHH
HY uS3�
Graphe de la matrice A
uS4�
������
Dé�nition 14 (Chemin) - Un chemin du graphe
Si y Si1 y Si2 y :::y Sip y Sj�
46 7. MATRICE RÉDUCTIBLE OU IRRÉDUCTIBLE
allant de Si à Sj est une suite d�arcs, si elle existe, telle que :
Si y Si1 ; Si1 y Si2 ; ::::; Sip y Sj,
soient des arcs du graphe.
Remarque 14 - Un arc est donc un chemin.Dans l�exemple (29), Il n�ya pas d�arc reliant S2 à S1, par contre S2 y S3 y S1est un chemin de S2 à S1.
Dé�nition 15 (Graphe fortement connexe) - Un graphe est dit fortementconnexe s�il existe au moins un chemin allant de tout sommet Si à tout sommetSj, i; j = 1; :::; n:
Exemple 31 - Ainsi, le graphe de A de l�exemple (29) est fortement connexe.
Par contre, celui de la matrice B =
0@ 0 12 00 22 031 32 0
1A ne l�est pas, car il n�ya pas
de chemin allant de S1 à S3.
uS1�����*uS2
HHHH
HY uS3�
Graphe de la matrice B
Lemme 8 - Une matrice A 2 Mn (C) est irréductible, si et seulement si, songraphe associé est fortement connexe.
� Preuve. Soit A une matrice irréductible. Soit Si un sommet de graphe et Eil�ensemble des indices des sommets qui peuvent être joints par un chemin issude Si. On a nécessairement Ei 6= ; (voir remarque 13). Plus précisement on aEi = f1; 2; ::; ng, car sinon en posant
K = Ei et Kc = f1; 2; ::; ng nK
on auraitai;j = 0 8i 2 K, j 2 Kc:
Donc le graphe de A est fortement connexe.
Réciproquement, supposons que A est réductible, i.e.
ai;j = 0 8i 2 K, j 2 Kc;
7.3. LOCALISATION DES VALEURS PROPRES 47
pour une partition de f1; 2; ::; ng en K, Kc. Comme le graphe de A est forte-ment connexe, il existe un chemin allant de Si à Sj ; ce qui entraîne que :
ai0;j0 6= 0 8i0 2 K, j0 2 Kc;
ce qui est impossible. Donc A est irréductible.
Exemple 32 - La matrice A de l�exemple (29) est irréductible. Par contre, lamatrice B de l�exemple (31) est réductible.
Exemple 33 - Une matrice de la forme
A =
0BBBBBB@� � � � � �� � � � � �� � � � � �� � � � � �� � � � � �� � � � � �
1CCCCCCA� terme 6= 0 et � terme quelconque,
est irréductible.
7.3 Localisation des valeurs propres
Théorème 8 (Gershgorin (suite)) - Soit A 2 Mn (C) une matrice irré-ductible. Alors, si � (A) est située sur la frontière de la réunion des disques
de GershgorinnSi=1
Di (A), tous les cercles de Gershgorin passent par � (A), i.e.
j� (A)� ak;kj = �k (A) 8k = 1; ::; n:
� Preuve. Soit � une valeur propre de A et x un vecteur propre associé. Intro-duisons le sous-ensemble d�indices
K = fk; tel que jxkj = kxk1g :
Il est clair que K 6= ;. Posons
y =x
kxk1;
de sorte queAy =�y; (7.1)
avec
jykj = 1 8k 2 K;jyij < 1 8i =2 K:
48 7. MATRICE RÉDUCTIBLE OU IRRÉDUCTIBLE
La k-ième ligne de (7.1), où k 2 K; s�écritnXi=1
ak;iyi = �yk:
Donc
j�� ak;kj � jykj|{z}1
=
�������nXi=1i 6=k
ak;iyi
������� �nXi=1i 6=k
jak;ij � jyij|{z}�1
� �k (A)| {z }nPi=1i 6=k
jak;ij
;
i.e.
j�� ak;kj �nXi=1i 6=k
jak;ij � jyij � �k (A) : (7.2)
Par ailleurs, si � est située sur la frontière denSi=1
Di (A), i.e. � n�étant pas à
l�intérieur denSi=1
Di (A), donc il n�existe aucun j pour lequel
j�� aj;j j < �j (A) :
Doncj�� aj;j j � �j (A) 8j = 1; ::; n:
De (7.2), on a nécessairement
j�� ak;kj =nXi=1i 6=k
jak;ij � jyij = �k (A) 8k 2 K: (7.3)
Distinguons deux cas :Cas 1- K = f1; :::; ng :La preuve dans ce cas est triviale, pour les matrices irréductibles ou non, puisque(7.3) s�écrit
j�� ak;kj = �k (A)8k = 1; ::n:Cas 2- K 6= f1; :::; ng :Donc
jyij < 1 8i 2 Kc;
pourKc = f1; :::; ng nK 6= ;:
Or, de (7.3)
�k (A)�nXi=1i 6=k
jak;ij � jyij =nXi=1i 6=k
jak;ij �
0B@1� jyij|{z}�1
1CA| {z }
�0
= 0 8k 2 K;
7.3. LOCALISATION DES VALEURS PROPRES 49
ou encore
jak;ij �
0@1� jyij| {z }>0
1A = 0 8i 2 Kc; 8k 2 K;
donc
ak;i = 0 8k 2 K; 8i 2 Kc:
Résultat impossible pour les matrices irréductibles. D�où
Kc = ;;
ce qui conduit au cas 1.
Exemple 34 - Considérons le cas de la matrice irréductible A =
0BB@0 2 0 00 1 �3 0
�1 1 0 10 0 �1 0
1CCA.
uS1�����*uS2HHHHHjHH
HHHY uS3�
Graphe de la matrice A
uS4�
������
x-
y
6
n����&%'$r0 r1 4
D2&%'$
On peut utiliser le théorème 8 pour déduire, par exemple, que �i (A) 6= 4, car le
50 7. MATRICE RÉDUCTIBLE OU IRRÉDUCTIBLE
point z = 4 qui est situé sur la frontière de la réunion des disques4Si=1
Di (A),
où
D1 = fz 2 C; jzj � 2g ;D2 = fz 2 C; jz � 1j � 3g ;
D3 = fz 2 C; jzj � 3g ;D4 = fz 2 C; jzj � 1g ;
ne se trouve pas sur la frontière du disque D4:
Exemple 35 - La matrice A =
0BBBBBB@2 �1 0 : : 0
�1 2 �1 0 : 00 �1 2 �1 0 :: : : : : :0 0 0 �1 2 �10 0 0 0 �1 2
1CCCCCCA est inversible.En e¤et, les valeurs propres de A sont contenues dans la région
n[i=1
Di (A) = fz 2 C; jz � 2j � 2g :
A étant irréductible et le point � = 0, situé sur la frontière denSi=1
Di (A), ne se
trouve pas sur le cercle D1 (A). Donc
0 =2 Sp (A) :
7.4 Matrice à diagonale fortement dominante
Lemme 9 - Si A 2 Mn (C) est à diagonale fortement dominante et irré-ductible, alors A est inversible.
� Preuve. La matrice A est à diagonale dominante, donc
j0� ak;kj � �k (A) 8k = 1; ::; n:
Si 0 était valeur propre, il serait donc sur la frontière denSi=1
Di (A). Comme A
irréductible, alors
j0� ak;kj = �k (A) 8k = 1; ::; n:
Ce qui contredit le fait que A à diagonale fortement dominante, i.e. qu�il existeun indice i pour lequel :
j0� ai;ij > �i (A) :
7.5. CAS D�UNE MATRICE SYMÉTRIQUE 51
Exemple 36 - La matrice A =
0BB@3 2 �1 02 3 1 00 �1 2 10 0 1 �2
1CCA est à diagonale forte-
ment dominante et irréductible, donc inversible.
7.5 Cas d�une matrice symétrique
Lemme 10 - Soit A 2Mn (R) une matrice symétrique, telle que:
ak;k > 0 8k = 1; ::; n: (7.4)
Si A est à diagonale fortement dominante et irréductible, alors A est dé�niepositive.
� Preuve. On se base sur l�équivalence (5.1). On sait, grâce à la symétrie que� (A) 2R. On sait aussi par le théorème 5 que
j� (A)� ak;kj � �k (A) 8k = 1; ::; n:
Doncak;k � � (A)| {z }�j�(A)�ak;kj
� �k (A) 8k = 1; ::; n:
De (7.4), on déduit
0 � jak;kj| {z }ak;k
��k (A) � � (A) 8k = 1; ::; n:
Or, A est inversible d�après le lemme 9. D�où
0 < � (A) 8k = 1; ::; n:
Exemple 37 - La matrice A� =
0BB@3 2 �1 02 3 �1 0
�1 �1 � 10 0 1 1
1CCA satisfait aux hypothèsesdu lemme 10 lorsque � > 3.Donc A� est dé�nie positive pour � > 3:
Remarque 15 - Pour � < �3, la matrice symétrique A� est à diagonale forte-ment dominante et irréductible, mais non dé�nie positive, puisque
� = hA�e3; e3i < 0:
L�hypothèse (7.4) est donc nécessaire pour établir le lemme 10.
52 7. MATRICE RÉDUCTIBLE OU IRRÉDUCTIBLE
8
Matrice positive
Théorème 9 (Frobenius) - Soit A 2Mn (R), A � 0. Alors, on a1 :P1) Le rayon spectral � (A) est une valeur propre de A.P2) Il existe au moins un vecteur propre réel x� � 0 associé à � (A) :P3)
� (B) � � (A) 8B � A � 0:
Si de plus A est irréductible, alorsP4) Le rayon spectral � (A) est une valeur propre simple.P5) Le vecteur propre x� > 0:P6)
� (B) > � (A) 8B 6= A et B � A � 0.
Exemple 38 - Le rayon spectral de la matrice B =�0 �11 0
�n�est pas une
valeur propre. Ceci ne contredit pas P1) car A � 0:
Exemple 39 - Pour la matrice positive A =
0@ 1 0 00 3 11 0 2
1A, on a Axk = �kxkavec
�1 (A) = 1, x1 =
0@ 21
�2
1A ,�2 (A) = 2, x2 =
0@ 0�11
1A�3 (A)| {z }�(A)
= 3, x3|{z}x�
=
0@ 010
1A :1Pour la démonstration voirVARGA R.S. (1962) Edit. John Wiley, �Matrix Iterative Analysis�.
53
54 8. MATRICE POSITIVE
On véri�e bien P1) et P2), puisque
� (A) = �3 (A) et x� � 0:
Comme x� � 0, on déduit de P5) que A n�est pas irréductible.
Exemple 40 - Soit B =
0@ 1 2 32 3 11 3 2
1A et A =
0@ 1 0 00 3 11 0 2
1A. On a :
�1 (B) = i, x1 =
0@ 110 �
1710 i
� 710 +
910 i
1
1A ,�2 (B) = �i, x2 =
0@ 110 +
1710 i
� 710 �
910 i
1
1A ,
�3 (B)| {z }�(B)
= 6, x3|{z}x�
=
0@ 111
1A :On véri�e bien P4) et P5), puisque
� (B) = �3 (B) est une propre simple et x� > 0:
De P6), on déduit que :� (B)| {z }6
> � (A)| {z }3
:
Remarque 16 - Si A 2Mn (R) ; A � 0, alors
kAk1 = kA1k1 :
9
Matrice monotone
Dé�nition 16 - Une matrice A 2 Mn (R) est monotone et on dit M-matricesi A�1 existe et si A�1 � O.
Exemple 41 - Pour A =
0@ 0 �1 11 1 �1
�1 0 1
1A on a A�1 =
0@ 1 1 00 1 11 1 1
1A � 0.
Donc A est une M-matrice.
Par contre, la matrice B =
0@ 0 �1 11 1 �1
�1 0 �1
1A ne l�est pas puisque B�1 =0@ 1 1 0�2 �1 �1�1 �1 �1
1A � 0:
Exemple 42 - La matrice A =
0@ 3 �2 �10 1 �10 �1 a
1A a pour inverse A�1 =0@ 1
3132a+1a�1
1a�1
0 aa�1
1a�1
0 1a�1
1a�1
1A :Alors
A est M �matrice, a > 1:
Remarque 17 - Soit A 2Mn (R) : Alors
A est une M-matrice, fx 2 Rn: Ax �0) x �0g :
9.1 Condition su¢ sante pour les M-matrices
Pour reconnaître une M-matrice nous utiliserons souvent le
Théorème 10 - Soit A 2Mn (R) une matrice telle que :
ai;i > 0 8i 2 f1; ::; ng ;ai;j � 0 8i 6= j 2 f1; ::; ng :
55
56 9. MATRICE MONOTONE
Si A est à diagonale dominante et inversible (en particulier, si A une matriceà diagonale fortement dominante et irréductible), alors A est une M-matrice.
� Preuve. La matrice diagonale D = (di;j), telle que di;i = ai;i est donc in-versible. On écrit A sous la forme
A = D � (D �A) = D
0@I �D�1(D �A)| {z }B
1A :Les matrices D�1 et D � A sont positives et donc B � 0: Plus précisement,pour B = (bi;j) on a
bi;i = 0 8i; bi;j =jai;j jjai;ij
8i 6= j:
De plus Xj
jbi;j j =�i (A)
jai;ij� 1;
car A est à diagonale dominante. D�où jjBjj1 � 1. Donc �(B) � 1:Montrons maintenant que �(B) 6= 1. En e¤et, comme B � 0; alors le rayonspectral �(B) est une valeur propre de B. Supposons que �(B) = 1, alors ilexiste x 6= 0, tel que Bx = x. Donc Ax = 0. Ceci implique que x = 0 car Aest inversible. Ce qui est absurde. On conclut �nalement que �(B) < 1:
La matrice (I �B) est donc inversible et (I �B)�1 =1Pk=0
Bk � 0: D�où
A�1 = (I �B)�1D�1 � 0:
Exemple 43 - La matrice A =
0@ 3 �2 �10 1 �10 �1 a
1A, a > 1, est une M-matrice.
Exemple 44 - La matrice A =
0BBBBBB@2 �1 0 : : 0
�1 2 �1 0 : 00 �1 2 �1 0 :: : : : : :0 0 0 �1 2 �10 0 0 0 �1 2
1CCCCCCA de l�exemple35 est une M-matrice.
9.2 Borne de l�inverse d�une matrice monotone
Théorème 11 - Si A 2Mn (R) est une M-matrice, alors
Ay = 1) A�1 1 = kyk1 : (9.1)
Ay � 1) A�1 1 � kyk1 : (9.2)
9.2. BORNE DE L�INVERSE D�UNE MATRICE MONOTONE 57
� Preuve. On déduit de Ay � 1 (resp. Ay = 1) que 0 � A�11 � y(resp. A�11 = y) car A�1 � 0. Le résultat suit en utilisant le fait que A�1 1 =
A�11 1.Exemple 45 - Pour la M-matrice A =
0@ 0 �1 11 1 �1
�1 0 1
1A, on a : Ay = 1
pour y =
0@ 223
1A : Donc A�1 1 = kyk1 = 3:
On véri�e bien que A�1 =
0@ 1 1 00 1 11 1 1
1A et donc A�1 1 = 3.
Exemple 46 - Le résultat est faux pour la matrice non monotone B =�1 20 1
�.
La matrice inverse B�1 =�1 �20 1
�a pour norme
B�1 1 = 3.
Cependant, By = 1 pour y =��11
�; kyk1 = 1 6=
B�1 1 :Lemme 11 - Soit A;B deux matrices monotones deMn (R), alors
A � B ) B�1 1 �
A�1 1 :� Preuve. Compte tenu du fait que A�1 � 0, B�1 � 0; on a :
A � B ) B�1A � B�1B| {z }I
) B�1AA�1| {z }I
� IA�1 ) B�1 � A�1 ) B�1 1 �
A�1 1 :
Exemple 47 - Par exemple A =
0@ 3 �1 �1�1 2 �1�1 0 1
1A � B =
0@ 3 �1 0�1 2 �10 0 1
1A.Les matrices A;B sont monotones d�après le théorème 10, donc B�1 1 �
A�1 1 :Véri�cation :
B�1 =
0@ 25
15
15
15
35
35
0 0 1
1A) B�1 1 =
7
5;
A�1 =
0@ 1 12
32
1 1 21 1
252
1A) A�1 1 = 4:
On a bien B�1 1 �
A�1 1.
58 9. MATRICE MONOTONE
9.3 Stabilité d�une matrice
On aura également besoin des résultats utiles suivants :
Théorème 12 - Soit B = I��A où � > 0 et A = [ai;j ] une matrice inversibleet à diagonale dominante (en particulier, si A une matrice à diagonale fortementdominante et irréductible), telle que
ai;i > 0 8i et ai;j � 0 pour i 6= j: (9.3)
Si� � min
i
1
ai;i; (9.4)
alors
B � 0;kBk1 � 1;� (B) < 1:
� Preuve. La matrice B = [bi;j ] est dé�nie par
bi;j =
�1� �ai;i i = j��ai;j i 6= j :
Compte tenu des hypothèses (9.3)-(9.4)
B � 0:
Par suite
kBk1 = maxi
8<:Xj
jbi;j j
9=;= max
i
8<:1� �ai;i +Xj 6=i
��ai;j
9=;
= maxi
8>>>>><>>>>>:1� �
0BBBBB@jai;ij �Xj 6=i
jai;j j| {z }�0
1CCCCCA
9>>>>>=>>>>>;;
or A est à diagonale dominante, donc
kBk1 � 1:
Par conséquent,� (B) � kBk1 � 1:
9.3. STABILITÉ D�UNE MATRICE 59
Il reste à montrer que� (B) 6= 1:
En e¤et, le rayon spectral � (B) est une valeur propre lorsque B � 0. Donc, si� (B) = 1, on aurait
B�!v = �!vpour
�!v 6= �!0 :Il en découle, puisque A est inversible, que
(I � �A)�!v = �!v ) A�!v = �!0) �!v = �!0 :
Ce qui est absolument absurde.
Théorème 13 - Soit C = (I + �A)�1 où � > 0 et A = [ai;j ] une matrice
inversible et à diagonale dominante (en particulier, si A une matrice à diagonalefortement dominante et irréductible), telle que
ai;i > 0 8i et ai;j � 0 pour i 6= j: (9.5)
Alors
C � 0;kCk1 � 1;� (C) < 1:
� Preuve. On a C =M�1 où M = [mi;j ] est dé�nie par
M = I + �A:
i.e.
mi;j =
�1 + �ai;i i = j�ai;j i 6= j :
Il est facile de voir, compte tenu des hypothèses, que la matriceM est à diagonalestrictement dominante. Donc inversible. De plus
mi;j > 0 pour i = j et mi;j � 0 pour i 6= j:
On conclut immédiatement que M est une M�matrice, i.e. C � 0. Comme
M�!1 � �!1 ;
alors� (C) � kCk1 =
M�1 1 �
�!1 1= 1:
Il reste à montrer que� (C) 6= 1:
60 9. MATRICE MONOTONE
En e¤et, comme C � 0; alors si � (C) = 1, on aurait
C�!v = �!v pour �!v 6= �!0 :
Par suite
(I + �A)�1�!v = �!v ) �!v = (I + �A)�!v
) A�!v = �!0) �!v = �!0 :
Ce qui est absurde.
10
Analyse d�erreurs dans lessystèmes linéaires
10.1 Introduction
Une incertitude1 sur les données A 2Mn (R) ; y 2Rn du système linéaire
Ax = y; (10.1)
peut donner une solution x entachée d�une erreur relative de 100 , 1000 fois oumême nettement supérieure.
Exemple 48 - En e¤et, considérons le système élémentaire suivant :�10 99 8
�| {z }
A
�x1x2
�| {z }
x
=
�1917
�| {z }
y
; de solution�x1x2
�=
�11
�
Perturbons les coe¢ cients de sa matrice de la manière suivante :�10 8:99:1 8:1
�| {z }eA
� ex1ex2�
| {z }ex=
�1917
�;
soit une erreur relative commise sur la matrice, en norme k:k1 ; de
�A =k�Ak1kAk1
=0:2
19= 1: 052 6� 10�2 où �A = eA�A = � 0 �0:1
0:1 0:1
�:
1L�erreur est due, par exemple, aux instruments de mesures, ou simplement les donnéesA; y sont calculées par des méthodes de discrétisation numérique ( di¤érences �nies, éléments�nis,...), ou en�n par leurs représentations en nombres machine lors de sa résolution parordinateur.
61
62 10. ANALYSE D�ERREURS DANS LES SYSTÈMES LINÉAIRES
On constate que la solution du système perturbé est égale à� ex1ex2�=
�+260�290
�:
10.2 Perturbation de la matrice
De manière générale, considérons la résolution du problème (10.1) pour unematrice inversible A donnée. Pour une raison quelconque, supposons que lamatrice A est remplacée par la matrice
~A � A+�A:
Alors, une solution du nouveau système notée par
ex � x+�x;véri�e :
(A+�A)ex = y: (10.2)
L�erreur commise sur la matrice est d�une valeur égale à k�Ak, ou en erreurrelative, est égale à
�A =k�AkkAk :
Ici, le symbole k : k désigne une norme matricielle subordonnée à dé�nir.
Nous allons calculer une estimation du rapport d�ampli�cation des erreurs
k�xkkx+�xkk�AkkAk
:
Pour cela, on a :�Ax = y(A+�A)(x+�x) = y
=) A�x = ��A(x+�x):
On en déduit, puisque A�1 existe, que :
�x = �A�1�A(x+�x):
On a donc
k�xk = A�1�A(x+�x)
� A�1 � k�Ak � kx+�xk :
D�où
10.2. PERTURBATION DE LA MATRICE 63
k�xkkx+�xk �
A�1 � k�Ak= (
A�1 � kAk)k�AkkAk
(10.3)
De sorte que l�erreur sur les résultats est encore donnée par
k�xkkx+�xk � Cond(A)�
k�AkkAk (10.4)
pourCond(A) =
A�1 � kAk : (10.5)
Dé�nition 17 - Ce nombre
Cond(A) = A�1 � kAk ;
s�appelle le conditionnement de la matrice A, relativement à la norme matricielleconsidérée, et mesure la sensibilité de la solution par rapport aux variations dela matrice.
10.2.1 Estimation de l�erreur
En résumé, on vient de démontrer le
Théorème 14 - Soit A une matrice inversible. Soient x et ex � x + �x 6= 0les solutions respectives des systèmes :
Ax = y et (A+�A)ex = y:Alors, on a :
k�xkkx+�xk � Cond(A)�
k�AkkAk ; (10.6)
pour toute norme matricielle subordonnée k:k :
Exemple 49 - Le conditionnement en norme k:k1 de la matrice
A =
�10 99 8
�) A�1 =
��8 99 �10
�;
est égal àCond1(A) = kAk1| {z }
19
� A�1 1| {z }
19
= 192 = 361:
Remarque 18 - Le nombre Cond(A) véri�e toujours
Cond (A) � 1:
Ceci vient du fait que
AA�1 = I =) kIk = AA�1 =) 1 � kAk �
A�1 = Cond (A) :
64 10. ANALYSE D�ERREURS DANS LES SYSTÈMES LINÉAIRES
Remarque 19 - Si nous connaissons le plus petit et le plus grand module desvaleurs propres, notés respectivement �1; �n, de la matrice produit A
�A, le calculde
Cond2 (A) = kAk2 � A�1
2
peut s�e¤ectuer sans connaître A�1 par la formule :
Cond2 (A) =
s�����n�1����:
Cette relation devient dans le cas où la matrice est symétrique
Cond2 (A) =
�����n�1���� ;
où les �j sont les valeurs propres de A, rangées de la façon suivante :
j�1j � j�2j � ::: � j�nj:
Exemple 50 - On choisit la norme k:k2 et on se place dans le cadre de l�exempledonné par
A =
�10 99 8
�) A�1 =
��8 99 �10
�:
Calcul du conditionnement : les valeurs prores de A sont
�2 = 9 +p82; �1 = 9�
p82:
La matrice A étant symétrique, donc
kAk2 = �2 et A�1
2=
1
j�1j) Cond2(A) = kAk2�
A�1 2=
�����2�1���� = 9 +
p82
�9 +p82' 326:
Calcul du rapport d�ampli�cation :
k�xk2kx+�xk2k�Ak2kAk2
=?. On a
8>><>>:�x = ex� x =� 259
�291
�x+�x = ex =� +260
�290
� ) k�xk2kx+�xk2
=
p2592 + 2912p2602 + 2902
' 1: 000 2
Calculons k�Ak2 =?. La matrice
(�A)��A =
�0 0:1
�0:1 0:1
��0 �0:1
0:1 0:1
�=
�:0 1 :0 1:0 1 :0 2
�;
a pour valeurs propres
�1 ' 3: 819 7� 10�3 et �2 ' :0 261 8) ��(�A)
��A�= �2;
10.2. PERTURBATION DE LA MATRICE 65
donck�Ak2 =
q��(�A)
��A�'p:0 261 8:
Ce qui donnek�xk2
kx+�xk2k�Ak2kAk2
'
p2592+2912p2602+2902p:0 261 89+p82
' 111: 61
On constate qu�on a bien :
k�xk2kx+�xk2k�Ak2kAk2| {z }111: 61
� Cond2(A)| {z }326
:
Exemple 51 - Considérons la résolution du système Ax = y où
A =
0BBBBBB@1 1
213
14
15
16
12
13
14
15
16
17
13
14
15
16
17
18
14
15
16
17
18
19
15
16
17
18
19
110
16
17
18
19
110
111
1CCCCCCA et y =
0BBBBBB@1
�11
�11
�1
1CCCCCCA :
La solution est
x =
0BBBBBB@21 918
�618 8704161 360
�10 780 56011 865 420�4665 276
1CCCCCCA :Considérons maintenant le système (A+�A)ex = y où la matrice
A+�A =
0BBBBBB@1 :5 :33 :25 :20 : 16:5 :33 :25 :20 : 16 : 14:33 :25 :20 : 16 : 14 : 12:25 :20 : 16 : 14 : 12 : 11:20 : 16 : 14 : 12 : 11 :10: 16 : 14 : 12 : 11 :10 :09
1CCCCCCAobtenue en tronquant les nombres après 2 chi¤res décimaux signi�catifs. Ontrouve
ex =0BBBBBB@
5: 088 56: 415 9164: 38�417: 9249: 558206: 42
1CCCCCCA au lieu de x =
0BBBBBB@21 918
�618 8704161 360
�10 780 56011 865 420�4665 276
1CCCCCCA :
66 10. ANALYSE D�ERREURS DANS LES SYSTÈMES LINÉAIRES
Soit une erreur relative sur les solutions de
k�xk1kx+�xk1
=1: 186 5� 107417: 92
= 28391;
pour une erreur relative sur le matrice de
k�Ak1kAk1
' 7: 2886� 10�3:
Le rapport d�ampli�cation des erreurs est égal à
k�xk1kx+�xk1k�Ak1kAk1
' 28391
7: 2886� 10�3 ' 3 895 300:
On constate que le conditionnement en norme k:k1 est égal à2
Cond1(A) =49
20|{z}kAk1
� 11 865 420| {z }kA�1k1
= 29 070 279:
10.2.2 Optimalité de l�estimation
Exemple 52 - Soit
A =1
8
��1 33 �1
�; A+�A =
1
8
�7 33 7
�et y =
10
8
�11
�) A�1 =
�1 33 1
�:
Considérons le système de départ
Ax = y) x =
�55
�ainsi que le système perturbé
(A+�A)ex = y) ex|{z}x+�x
=
�11
�:
2La matrice inverse
A�1 =
0BBBBB@36 �630 3360 �7560 7560 �2772�630 14 700 �88 200 211 680 �220 500 83 1603360 �88 200 564 480 �1411 200 1512 000 �582 120�7560 211 680 �1411 200 3628 800 �3969 000 1552 3207560 �220 500 1512 000 �3969 000 4410 000 �1746 360�2772 83 160 �582 120 1552 320 �1746 360 698 544
1CCCCCA :
10.2. PERTURBATION DE LA MATRICE 67
En choisissant la norme k:k1, on trouve8>><>>:k�xk1
kx+�xk1= 4
1 = 4
k�Ak1kAk1
= 148
= 2)
k�xk1kx+�xk1k�Ak1kAk1
=4
2= 2:
Cond1(A) =4
8|{z}kAk1
� 4|{z}kA�1k1
= 2:
i.e.k�xk1
kx+�xk1k�Ak1kAk1
= Cond1(A):
On conclut que l�inégalité (10.6) est optimale pour la norme k:k1.
De manière générale, pour toute norme matricielle subordonée, on a :
Théorème 15 - L�inégalité (10.6) est optimale dans le sens où le nombreCond(A) est la meilleure constante possible pour toute perturbation de la ma-trice et tout second membre.
Preuve. Raisonnons par l�absurde. Supposons qu�il existe un nombre c > 0,tel que : 8<:
k�xkkx+�xk � c
k�AkkAk pour
c < Cond(A):(10.7)
Soit ex6= 0 un vecteur tel que :maxz 6=0
jjA�1zjjjjzjj| {z }
kA�1k
=jjA�1exjjjjexjj ;
et considérons une perturbation de la matrice par l�identité, i.e. �A = I; avecun second membre donné sous la forme
y = (A+ �A|{z}I
)ex:On obtient alors :
y = (A+ I|{z}�A
)(x+�x| {z }ex) = Ax|{z}
y
+A�x+ ex:
68 10. ANALYSE D�ERREURS DANS LES SYSTÈMES LINÉAIRES
i.e.0 = A�x+ ex) �x =�A�1ex
Ainsi,k�xk =
A�1ex = A�1 � kexk :On conclut �nalement, que :
k �x kkx+�xk =
A�1 =
� A�1 � kAk� kIkkAk
= Cond (A)k�AkkAk
> ck�AkkAk :
La première relation de (10.7) est donc fausse, ce qui est absurde.
10.3 Perturbation du second membre
Envisageons maintenant le cas d�une perturbation des coe¢ cients du secondmembre, sans changement de la matrice.
Théorème 16 - Soit A une matrice inversible. Soient x 6= 0 et ex � x + �xles solutions respectives des systèmes :
Ax = y et Aex = y +�y:Alors, on a :
k �x kkxk � Cond (A) k�ykkyk ; (10.8)
pour toute norme matricielle subordonnée k:k :
Preuve. Par di¤érence des deux équations, on a :
A�x = �y =) �x = A�1�y:
Il résulte donc de la dé�nition des normes subordonnées que :
k�xk � A�1 � k�yk :
10.3. PERTURBATION DU SECOND MEMBRE 69
Par ailleurs,
Ax = y)kyk = kAxk � kAk � kxk =) 1
kxk �kAkkyk ;
d�où, de ces deux dernières inégalités
k �x kkxk �
A�1 � k�yk � kAkkyk = Cond (A)k�ykkyk :
Remarque 20 - On peut également montrer que l�inégalité (10.8) est optimale.
Exemple 53 - Soit le système linéaire0BB@10 7 8 77 5 6 58 6 10 97 5 9 10
1CCA| {z }
A
2664x1x2x3x4
3775| {z }
x
=
26644331
3775| {z }
y
=) x =
26641
�11
�1
3775 :
Considérons le système perturbé, où la matrice restant inchangée et le secondmembre est modi�é de la manière suivante :
y +�y =
26644:12:93:1:9
3775 :Soit une erreur relative sur le seconds membre, en norme k:k1 ; de
k�yk1kyk1
=:1
4= 0:0 25
La solution ex � x+�x est égale àex =
26649: 2
�14: 64: 5
�3: 1
3775 :Soit une erreur relative sur la solution de
k�xk1kxk1
=13:6
1= 13:6
Le rapport d�ampli�cation des erreurs est égal à
k�xk1kxk1k�yk1kyk1
=13:6
0:0 25= 544:
70 10. ANALYSE D�ERREURS DANS LES SYSTÈMES LINÉAIRES
Le conditionnement dans ce cas est égal à3
Cond1(A) = 33|{z}kAk1
� 136|{z}kA�1k1
= 4488:
3La matrice inverse
A�1 =
0BB@25 �41 10 �6�41 68 �17 1010 �17 5 �3�6 10 �3 2
1CCA :
11
Exercices
Exercice 19 - Soit la matrice A =
0BB@a �1 0 0�1 a �1 00 �1 a �10 0 �1 a
1CCA ; a 2 R.Donner par le théorème de Browne une estimation pour les valeurs propres deA.Localiser les valeurs propres de A à l�aide du théorème de Gershgorin.Calculer kAk1et kAk2 :Donner des conditions sur a, en précisant celles qui sont nécessaires, pour queA soit :1) irréductible,2) dé�nie positive,3) à diagonale fortement dominante,4) inversible,5) M-matrice.
Exercice 20 - Sans calcul de A�1, déduire de (9.1) la valeur de A�1 1 dans
les cas suivants:
Cas 1 : A =�
3 �1�1 2
�; y =
�34
�:
Cas 2 : A =
0@ 2 �1 0�1 2 �10 �1 2
1A, y =0@ 343
1A :Appliquer (9.1) à A =
�2 10 1
�:
Expliquer pourquoi le résultat est faux.
Exercice 21 - Soit A =
0BB@1 �1 0 0
�1 a �1 00 �1 b �10 0 �1 1
1CCA où a et b 2 R, ba 6= a+ b:
71
72 11. EXERCICES
1) Calculer k A k1.2) Pour quelles valeurs de a et b la matrice A est-elle inversible ?3) Donner le graphe de A. En déduire que A est irréductible.4) Donner des conditions sur a et b pour que A soit dé�nie positive.5) Donner des conditions sur a et b pour que �(A) soit dans le segment ]0; 2[.6) Donner des conditions sur a et b pour que A soit une M-matrice.
Calculer dans ce cas Ay; y =
0BB@b+ ba� a
2b2a
�b+ ba+ a
1CCA. En déduire A�1 1 :
Exercice 22 - Soit A =
266666642 �1 0 : : 0�1 2 �1 0 : 0: : : : : :: : : : : 00 : 0 �1 2 �10 : : 0 �1 2
37777775 2Mn (R) et
y = (yi) 2 Rn, yi =i
n+ 1
�1� i
n+ 1
�:
Calculer Ay. En déduire A�1 1 :
Exercice 23 - Soit A 2 Mn (R) une matrice à diagonale strictement domi-nante. On pose
� = mini(jai;ij � �i (A)):
1) Montrer que
kAxk1kxk1
� � 8x 6= 0:
2) En déduire que A�1 1 � 1
�:
3) Application. Donner une majoration de A�1 1 dans les cas suivants :
A =
�2 10 1
�; A =
0@ 4 1 01 3 10 �1 2
1A :4) Montrer que le résultat obtenu dans 2) est faux pour A =
�1 20 1
�:
Expliquer pourquoi.
73
Exercice 24 - Calculer Cond2(A) et Cond1(A) pour la matrice
A =
266666642 �1 0 : : 0�1 2 �1 0 : 0: : : : : :: : : : : 00 : 0 �1 2 �10 : : 0 �1 2
37777775 2Mn (R) :
Exercice 25 - Soit la matrice A =
0BB@a �1 0 0�1 a �1 00 �1 a �10 0 �1 a
1CCA ; a � 2.1) Montrer que A est une M-matrice.
2) On introduit le vecteur y =
0BB@a
a+ 1a+ 1a
1CCA. Calculer Ay, en déduire que A�1 1 =
a+ 1
a2 � a� 1 :
3) Calculer le nombre Cond(A) pour la norme k:k1.4) En utilisant la méthode de votre choix, donner une majoration de Cond(A)pour la norme k:k2.
Exercice 26 - Soit la matrice A =
0BB@2 �1 0 0
�1 3 �2 00 �2 3 �1a 0 �1 2
1CCA, où a 2 R:1) Pour quelles valeurs de a :A est-elle irréductible (donner le graphe de A) ?,A est-elle à diagonale fortement dominante ?.2) En déduire (sans aucun calcul) des conditions su¢ santes sur a pour que :A�1 existe,A�1 � 0.3) On supposera que �1 < 2a � 0 et on pose y = (2; 3; 3; 2)t.Expliquer clairement pourquoi A�1 � 0.Véri�er qu�il existe c > 0, telle que: Ay � c 1. En déduire une majoration de A�1 1.A l�aide du théorème de Browne, donner une estimation pour les valeurs propresde A.Calculer kAk1 et donner une majoration de Cond(A) pour la norme k:k1.