Exercices
Série 2: Syst‘emes lineaires
Pr. Christophe Prud’homme
1 Systèmes Linéaires
1.1 Objectifs
1. Savoir écrire la méthode de factorisation de Gauss avec pivot
2. Savoir écrire la méthode de factorisation de Cholesky
3. Savoir écrire la méthode de Jacobi
4. Savoir écrire la méthode de Gauss-Seidel
5. Savoir calculer un rayon de convergence
1.2 Exercices
Exercise 1
On veut résoudre le système linéaire Ax = b, où
1 1 1 1
A= 2 2 5 et b= 2
4 6 8 5
par la méthode d’élimination de Gauss.
1. Vérifier que l’algorithme de Gauss ne peut pas être exécuté jusqu’au bout.
2. On considère la matrice de permutation P suivante :
1 0 0
P = 0 0 1
0 1 0
Ecrire le système linéaire équivalent à Ax = b (c.-à-d. ayant la même solution x) qui a P A
comme matrice associée.
3. Appliquer l’algorithme de Gauss à la matrice P A, et calculer la factorisation LU de P A.
4. Calculer x en résolvant le système linéaire équivalent du point b), à partir de la factorisation
trouvée et en utilisant les algorithmes de substitution progressive et rétrograde.
Exercise 2
On considère la matrice carrée d’ordre 3 suivante :
4 −1 0
A = −1 4 −1
0 −1 4
1. Etudier la convergence des méthodes de Jacobi et de Gauss-Seidel pour cette matrice.
1
1.2 Exercices 1.2 Exercices
2. Vérifier que ρ(BGS ) = ρ2 (BJ ), où BGS et BJ sont respectivement les matrices d’itération
associées à la méthode de Gauss-Seidel et de Jacobi. Quelle est la méthode avec la vitesse de
convergence la plus rapide ?
Exercise 3
Pour η ∈ R, on considère le système linéaire
1 1−η 0 3−η
Aη x = bη , où Aη = 1/2 1 0 , bη = 2 . (1)
0 0 1 2
Le système est non-singulier si η 6= −1.
1. Déterminer les conditions nécessaires et suffisantes sur η afin que la méthode de Gauss-Seidel
appliquée au système (1) converge.
2. Pour quelle valeur η̄ de η peut-on appliquer la méthode du gradient pour résoudre le système
(1) ? Pour cette valeur, trouver le facteur C de réduction de l’erreur (en norme Aη̄ ) tel que
kx(k+1) − xkAη̄ ≤ Ckx(k) − xkAη̄ , k ≥ 0.
Soit x(0) = 0 ; combien d’itérations de la méthode du gradient sont nécessaires pour que kx(n) −
xkAη̄ < 2−20 ?
3. Est-ce que la méthode de Jacobi appliquée au système (1) pour η = η̄ converge ? On peut
montrer que dans le cas de cet exercice les itérations de la méthode sont telles que
kx(k+1) − xk2 ≤ ρ(BJ )kx(k) − xk2 , k ≥ 0,
BJ étant la matrice d’itération et k · k2 la norme euclidienne. Au vu de ce résultat, combien
d’itérations de la méthode de Jacobi sont nécessaires pour que kx(n) − xk2 < 2−20 si x(0) = 0 ?
Comparer avec le résultat obtenu au point précédent.
Exercise 8
On considère les deux systèmes linéaires suivants :
2 4 8 6
A1 x = b1 , où A1 = 1 1 4 , b1 = 5 ,
3 6 7 4
et
1 1 1 1 1
2 2 5 3 2
A2 x = b2 , où A2 =
4
, b2 =
5 .
6 8 0
3 3 9 8 0
1. Calculer la factorisation LU de la matrice A1 .
2. Résoudre le système linéaire A1 x = b1 en utilisant la factorisation trouvée au point précédent.
3. Vérifier que l’algorithme de factorisation LU sans pivoting pour la matrice A2 ne peut pas être
exécuté jusqu’au bout.
4. Trouver une matrice P de permutation de façon à ce que la matrice P A2 soit factorisable, puis
calculer la factorisation LU de P A2 .
5. Résoudre le système linéaire A2 x = b2 en utilisant la factorisation trouvée au point précédent.
6. Calculer le déterminant de la matrice A2 en utilisant sa factorisation LU (Sugg. on sait que
det(A2 ) = det(LU ) = det(L) · det(U )). (3)
)
Christophe Prud’homme Université de Strasbourg Christophe Prud’homme
1.2 Exercices 1.2 Exercices
Exercise 10
On considère le déplacement vertical u(x) d’un câble, représenté à repos par le segment [0, 1], et
fixé aux extrêmes, sur lequel on applique une force f (x). Ce déplacement u est la solution de l’équation
différentielle suivante : (
−u00 (x) = f (x), x ∈ (0, 1),
(4)
u(0) = 0, u(1) = 0.
Soit N ∈ N, h = 1/N et xi = ih pour i = 1, ..., N ; pour approcher la solution u(x) on considère la
discrétisation de l’intervalle (0, 1) en N sous-intervalles (xi , xi+1 ), et on construit une approximation
ui de u(xi ) par la méthode des différences finies. Cette méthode requiert de résoudre numériquement
le système linéaire tridiagonale Au = b qui suit :
2 −1 u1 f (x1 )
−1 2 −1 u2 f (x2 )
1 .. .. ..
..
..
= (5)
. . . . .
h2
−1 2 −1 uN −2 f (xN −2 )
−1 2 uN −1 f (xN −1 )
où u = [u1 , u2 , ..., uN −1 ]T et b = [f (x1 ), f (x2 ), ..., f (xN −1 )]T . Plus N est grand, plus l’approximation
sera précise et plus la taille du système linéaire à résoudre sera élevée.
1. On suppose que la force appliquée soit f (x) = x(1−x) et on prend N = 20 intervalles. Construire
la matrice A et le vecteur b correspondants, à l’aide des commandes suivantes :
f = ’x .*(1 - x ) ’;
N =20; h = 1/ N ;
x = linspace (h , 1 -h , N -1) ’;
b = eval ( f );
A =( N ^2)*( diag (2* ones (N -1 ,1) ,0) - diag ( ones (N -2 ,1) ,1) - ...
diag ( ones (N -2 ,1) , -1));
Calculer la factorisation LU de A par la commande Octave lu. Vérifier que la matrice de
permutation P est l’identité (on sait de la théorie que aucune permutation de lignes est effectuée
dès que la matrice est s.d.p., ce qui est le cas de A).
Calculer également la factorisation de Cholesky de A, et remarquer qu’elle diffère de la précé-
dente.
2. Calculer la solution du système linéaire Au = b à partir de la factorisation A = LU , en utilisant
la commande \ pour résoudre les deux systèmes triangulaires. Utiliser les commandes tic et
toc pour calculer le temps nécessaire (voir exemple ci-dessous). Ensuite comparer avec le temps
de calcul pour résoudre directement :
tic ; u = A \ b ; toc
3. A l’aide de la commande plot, représenter le déplacement u du câble aux noeuds xi définis au
point a).
Facultatif : comparer graphiquement les déplacements approchés ui avec la solution exacte du
problème (4).
4. On veut maintenant étudier la déformation du câble lorsque une distribution de force différente
est appliquée, notamment f˜(x) = x sin(2πx)2 . Toujours en considérant N = 20 sous-intervalles,
au vu des résultats précédents, calculer la déformation du câble due à f˜, en utilisant à nouveau
les facteurs L et U précédemment obtenus. Tracer le graphe correspondant à la solution calculée.
5. Etudier le comportement du conditionnement de la matrice A lorsque N augmente, en traçant
le graphe des valeurs de K(A) pour N = 100, 200, . . . , 1200. Tracer le graphe bilogarithmique
des mêmes valeurs avec la commande loglog. Quel type de courbe obtient-on ?
Si on suppose une relation linéaire log10 K(A) = m log10 N + c pour le graphe bilogarithmique,
alors on a K(A) = CN m (avec C = 10c ) : calculer les constantes m et C.
De combien K(A) croît-il lorsque on double le nombre N des sous-intervalles ?
Christophe Prud’homme Université de Strasbourg Christophe Prud’homme
1.2 Exercices 1.2 Exercices
Exercise 13
On se donne la matrice A (matrice d’Hilbert d’ordre 10)
» A = hilb (10);
et le système linéaire Ax = b, où b=A*ones(10,1). La solution exacte x de ce système est donc le
vecteur ones(10,1).
1. Vérifier que la matrice A est symétrique et définie positive.
2. Calculer la factorisation LU de A en utilisant la commande matlab lu dans la forme [L,U,P]=lu(A)
et ensuite la commande \ pour résoudre les deux systèmes triangulaires (faire attention à la
matrice de permutation !)
Jusqu’à quel chiffre après la virgule les composantes de la solution calculée sont exactes ? Ex-
pliquer brièvement pourquoi on ne peut pas obtenir un résultat très précis (en sachant que la
commande MATLAB pour calculer le nombre de conditionnement d’une matrice est cond).
3. Pour factoriser A aurait-on pu utiliser la factorisation de Cholesky ? Quelles sont les avantages ?
Utiliser donc - si possible - la commande chol de matlab (qui calcule une matrice H telle que
A = H > H) pour résoudre le système Ax = b et examiner la précision du résultat.
Exercise 15
On considère le système linéaire Ax = b avec
10 5 0 0 6
5 10 −4 0 25
A= 0 −4
et b=
−11 .
8 −1
0 0 −1 5 −11
Définir la matrice A et le vecteur b et répondre aux questions suivantes.
1. La matrice A peut s’écrire comme A = D − E − F où les matrices D, E, F sont données par
» D = diag ( diag ( A ));
» E = -( tril ( A ) - D );
» F = -( triu ( A ) - D );
Calculer les matrices d’itération B1 et B2 pour les deux méthodes itératives que l’on obtient
dans les cas suivantes :
1) Dx(n+1) = (E + F )x(n) + b
2) (D − E)x(n+1) = F x(n) + b
2. Calculer le rayon spectral des deux matrices d’itération et établir si les deux méthodes sont
convergentes. De quelles méthodes s’agit-il ? Au vu des rayons spectraux calculés en a), quelle
est la méthode la plus rapide ?
3. Résoudre par la commande itermeth (à télécharger) le système linéaire Ax = b, avec une
tolérance tol = 10−6 , en utilisant les deux méthodes précédentes et le vecteur initiale x(0) =
(0, 0, 0, 0)t . Comparer le nombre d’itérations de chaque méthode et vérifier votre réponse b).
test Octave 16
Soit A la matrice suivante
4 2 0 0
−1 4 2 0
A=
0 −1
,
4 2
0 0 −1 4
et A = D − E − F le splitting de A tel que D soit la partie diagonale de A, −E sa partie triangulaire
inférieure et −F sa partie triangulaire supérieure. Pour résoudre le système linéaire Ax = b, on
considère la méthode itérative
xk+1 = Bα xk + f ,
Christophe Prud’homme Université de Strasbourg Christophe Prud’homme
1.2 Exercices 1.2 Exercices
où Bα = (I − α(D − E)−1 A) est la matrice d’itération, avec α paramètre d’accélération et I matrice
identité de taille 4, et f une fonction connue de b.
1. Etablir pour quelles valeurs de α la méthode est convergente. A ces fins, utiliser le critère
nécessaire et suffisant de convergence des méthodes itératives et considérer les valeurs de α ∈
[−0.5, 2.5] données en Matlab par alpha=[-0.5:0.01:2.5].
2. Quelle est la valeur optimale de α (pour laquelle la convergence est la plus rapide) ? Combien
vaut-il le rayon spectral de Bα dans ce cas ?
3. Quelle méthode obtient-on pour α = 1 ? Résoudre par cette méthode le système linéaire Ax = b,
où b=A*ones(4,1) en utilisant convenablement le code itermeth avec tol=1e-6, nmax=100,
x0=zeros(4,1). Combien d’itérations sont-elles nécessaires ?
Christophe Prud’homme Université de Strasbourg Christophe Prud’homme
