c(cid:13) Franc¸ois Fayard, protégé par la GNU Free Documentation License
source disponible sur http://www.velvia.org
TP de Maple : Pivot de Gauss
Le but de ce TP est d’implémenter l’algorithme du pivot de Gauss. Dans une première
partie, on utilisera cet algorithme pour calculer le rang d’une matrice. La seconde partie est
consacrée a la résolution des systemes linéaires de Cramer, c’est-a-dire a la résolution des
équations du type AX = Y où A ∈ GLn (R) et Y ∈ Mn,1 (R).
1 Calcul du rang par pivot de Gauss
1. Écrire une procédure
pivot_cherche:=proc(A::matrix,k::integer)
qui en entrée accepte une matrice A ∈ Mq,p (R) et un entier k ∈ N∗ et en sortie
retourne :
– la liste [0,0] lorsque : ∀i ∈ Jk, qK
∀j ∈ Jk, pK
– la liste [i,j] où (i, j) ∈ Jk, qK × Jk, pK est le premier couple d’entier trouvé tel que
ai,j = 0
ai,j 6= 0 sinon.
2. Écrire une procédure
pivot_elim:=proc(A::matrix,k::integer)
qui en entrée prend une matrice A ∈ Mq,p (R) de la forme
a1,p
a1,1
0
0 ak,k
0
0 aq,k
aq,p
avec ak,k 6= 0. Le procédure effectuera un pivot de Gauss en utilisant pour pivot le
nombre ak,k et retournera la matrice équivalente ainsi obtenue.
3. Écrire une procédure
qui en entrée prend une matrice A ∈ Mq,p (R) et en sortie retourne la séquence B,r où
B est la matrice équivalente à A de la forme
b1,1
?
Publicité
0
0
br,r
0
0
?
0
0
?
?
0
0
avec
∀k ∈ J1, rK
bk,k 6= 0
obtenue par l’algorithme du pivot de Gauss, et r le rang de A.
2 Résolution d’un système de Cramer
Dans cette partie, on cherche a résoudre l’équation AX = Y ou A ∈ GLn (R) et
Y ∈ Mn,1 (R) par la méthode du pivot de Gauss.
2.1 Algorithme du pivot de Gauss
1. Écrire une procédure
pivot_cherche_ga:=proc(A::matrix,k::integer)
qui en entrée prend une matrice A ∈ GLn (R) de la forme
a1,n
a1,1
0
0 ak,k
0
0 an,k
an,n
Publicité
gauss_elim=proc(A::matrix)
et un entier k ∈ J1, nK et retourne i, plus petit entier de Jk, nK tel que ai,k 6= 0.
2. Écrire une procédure
pivot_elim_ga:=proc(A::matrix,Y::matrix,k::integer)
qui en entrée prend une matrice A ∈ GLn (R) de la forme
(b) Pour éviter ce genre de problème, on modifie l’algorithme de recherche d’un pivot
de la manière suivante : au lieu de se contenter de chercher un pivot non nul dans la
colonne k, on cherche le pivot de cette colonne ayant la plus grande valeur absolue.
Écrire les procédures :
a1,n
a1,1
0
0 ak,k
0
0 an,k
an,n
une matrice Y ∈ Mn,1 (R) et un entier k ∈ J1, nK et retourne la liste [B,Z] où BX = Z
est le systeme équivalent au systeme AX = Y obtenu après une étape du pivot de
Gauss.
3. Écrire une procédure
triang_solve_ga:=proc(A::matrix,Y::integer)
qui en entrée prend une matrice A ∈ GLn (R) triangulaire supérieure et une matrice
Publicité
Y ∈ Mn,1 (R) et qui retourne l’unique solution X de l’équation AX = Y .
4. Écrire une procédure
gauss_solve_ga:=proc(A::matrix,Y::matrix)
qui en entrée prend une matrice A ∈ GLn (R) et un vecteur Y ∈ Mn,1 (R) et retourne
l’unique solution X du système AX = Y .
2.2 Résolution numérique
1. Méthode du pivot partiel
(a) En utilisant gauss_solve_ga, résoudre le système linéaire
1, 0 · 10−20x + 1, 0 · y = 1, 0
1, 0 · x + 1, 0 · y = 2, 0
(cid:26)
puis le système linéaire équivalent
1, 0 · x + 1, 0 · y = 2, 0
1, 0 · 10−20x + 1, 0 · y = 1, 0
(cid:26)
pivot_cherche_pp:=proc(A::matrix,k::integer)
gauss_solve_pp:=proc(A::matrix,Y::matrix)
mettant en oeuvre cet algorithme.
2. Conditionnement d’un système linéaire
(a) En utilisant gauss_solve_ga, résoudre les systèmes linéaires :
10a + 7b + 8c + 7d = 32
7a + 5b + 6c + 5d = 23
8a + 6b + 10c + 9d = 33
7a + 5b + 9c + 10d = 31
le
puis
système
« tres légerement » modifiés :
linéaire perturbé,
où les
seconds membres
ont
été
10a + 7b + 8c + 7d = 32 + 1/10
7a + 5b + 6c + 5d = 23 − 1/10
8a + 6b + 10c + 9d = 33 + 1/10
7a + 5b + 9c + 10d = 31 − 1/10
Que remarquez vous ?
(b) Définir la matrice de Hilbert A de taille 10 × 10 : par :
∀i, j ∈ J1, 10K
ai,j =
1
i + j
et la matrice Y ∈ Mn,1 (R) :
∀i ∈ J1, 10K
yi = 1
puis résoudre le système AX = Y en utilisant successivement :
gauss_solve_ga(A,Y)
gauss_solve_ga(map(evalf,A),map(evalf,Y))
gauss_solve_pp(map(evalf,A),map(evalf,Y))
Que remarquez-vous ? Quelle est la bonne solution ? Expliquez ce qui s’est passé.
Répétez les deux derniers calculs en augmentant la variable Digits.