Universite Joseph Fourier
Methodes Numeriques
L3
2`eme semestre 2008/2009
Feuille dexercices no 3
R
esolution de syst`
emes lin
eaires.
M
ethodes directes
Exercice 1 : Donner lordre de grandeur du nombre doperations necessaires pour calculer
le determinant et linverse dune matrice A de taille n n grace aux formules
X
1
t
()a1(1) a2(2) ...an(n) et A1 =
com(A) .
det(A) =
det(A)
Meme question mais en utilisant la decomposition A = LU (methode de Gauss).
Un ordinateur standard effectue de lordre de 1010 operations par secondes (10 gigaflops).
Comparer les temps necessaires dans le cas dune matrice 100 100.
Exercice 2 : Soit Eij () la matrice egale a` lidentite sauf pour le coefficient (i, j) qui vaut
. Soit A une matrice quelconque. Comment la multiplication a` droite et a` gauche par
Eij () agit-elle sur A ?
Exercice 3 : Donner une decomposition LU des matrices suivantes
2 3 0
1 4
A=
B = 1 0 4 .
1 2
2 0 5
Exercice 4 : D
ecomposition QR.
P
n
On munit C du produit hermitien canonique < x|y >=
xi y i .
1) Soient a1 , ..., an des vecteurs formant une base de Cn . Montrer quil existe une base
orthonormee q1 , ..., qn et des nombres complexes rij (i j) tels que rii est un reel positif
pour tout i et
a1 = r11 q1
a2 = r12 q1 + r22 q2
..
a = r q +...+r q
n
1n 1
nn n
2) En deduire que toute matrice inversible A peut secrire A = QR o`
u Q est unitaire et R
est triangulaire superieure a` elements diagonaux reels et positifs et que cette decomposition
est unique.
3) Comment utiliser cette decomposition pour resoudre facilement le syst`eme Ax = b ?
4) Soit A GLn (C), montrer que t AA est hermitienne definie positive. Quel est le lien
entre la decomposition de Choleski et la decomposition QR ?
Exercice 5 : D
ecomposition de Choleski.
Soit A une matrice hermitienne definie positive. On rappelle quil existe une unique matrice
triangulaire inferieure L qui a des elements diagonaux strictement positifs telle que A = L t L
(decomposition de Choleski).
1) Donner lalgorithme qui permet de calculer L. Lappliquer a` la matrice
1 2
1
A = 2 13 1 .
1 1 3
Cet algorithme est-il appliquable a` des matrices non hermitiennes ?
2) Expliquer comment utiliser la decomposition de Choleski pour resoudre le syst`eme Ax =
b et donner le nombre doperations.
3) Une matrice A = (aij ) est appelee pbande si aij = 0 d`es que |i j| p.
a) Donner des exemples de matrices pbandes.
b) Montrer que si A est une matrice hermitienne definie positive pbande, alors L est
aussi pbande.
M
ethodes indirectes
Exercice 6 : On munit Cn de la norme kxk = supi |xi |. On munit Mn (C) de la norme
triple associee. Montrer que
|||A|||
n
X
kAxk
= sup
|aij | .
i=1,...,n
xCn \{0} kxk
j=1
sup
Donner une condition suffisante sur A pour que pour tout x Cn , Ak x 0 quand
k 0. Cette condition est-elle necessaire ?
Exercice 7 : Matrices `
a diagonale dominante.
On appelle matrice a` diagonale dominante une matrice A = (aij ) GLn (C) telle que, pour
i = 1, ..., n,
X
|aii | >
|aij | .
j6=i
1) Donner un exemple de matrice a` diagonale dominante.
2) Montrer que toute matrice a` diagonale dominante est inversible.
3) On souhaite appliquer la methode de Jacobi pour resoudre le syst`eme Ax = b o`
u A est
a` diagonale dominante. On pose
a1,1 0 . . . 0
0 a1,2
...
a1,n
..
..
.
..
.
.
.
0 a2,2 . .
a2,1 0
M = .
et
N
=
.
.
.
.
.
.
.. .. 0
..
..
..
..
an1,n
0 . . . 0 an,n
an,1 . . . an,n1
0
La methode de Jacobi consiste a` rechercher le point fixe de quelle fonction ? Montrer que
la methode de Jacobi converge toujours si A est a` diagonale dominante.
Conditionnement
Pour resoudre le syst`eme Ax = b, il faut connatre b. En general, celui-ci nest pas connu
avec une precision infinie car il peut y avoir des erreurs de mesures et car la precision des
instruments et de lordinateur nest pas infinie. On sinteresse donc a` lerreur qui peut etre
commise sur x a` cause des imprecisions sur b. La valeur pertinente est lerreur relative
kxk/kxk.
Exercice 8 : On souhaite resoudre le syst`eme lineaire Ax = b avec
1001 1000
A=
.
1000 1001
1) Donner les valeurs propres et vecteurs propres de A.
2) Expliciter la resolution de lequation Ax = b en fonction des elements propres.
3) Resoudre le syst`eme Ax = b avec b = (1, 1). On a en fait une petite erreur sur b qui est
donne par b avec kbk/kbk de lordre de 0, 01. On a donc une erreur x sur x donnee par
A(x + x) = b + b. Lerreur relative kxk/kxk est-elle grande ?
Exercice 9 : On consid`ere le syst`eme Ax = b avec A GLn (R). Les donnees A et b sont
imprecises. On a donc en realite le syst`eme lineaire
(A + A)(x + x) = b + b .
Etant donnee une norme matricielle, on definit le conditionnement de la matrice A par
(A) = |||A|||.|||A1|||.
1
1) Montrer que si |||A|||
(A)
, on a
|||A|||
kxk
(A)
kxk
1 (A) |||A|||
|||A|||
kbk |||A|||
+
kbk
|||A|||
2) Montrer que le conditionnement de A est minore par le rapport |n /1 |, o`
u n et 1
sont respectivement la plus grande et la plus petite valeur propre en module. Expliquer
lexercice precedent du point de vue du conditionnement.
TP Scilab
Exercice 10 : Ecrire un programme donnant la decomposition QR dune matrice. Le
transformer en un programme calculant linverse dune matrice.
Exercice 11 : Programmer la methode de Jacobi.
