c(cid:13) Franc¸ois Fayard, prot´eg´e 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´ementer l’algorithme du pivot de Gauss. Dans une premi`ere
partie, on utilisera cet algorithme pour calculer le rang d’une matrice. La seconde partie est
consacr´ee a la r´esolution des systemes lin´eaires de Cramer, c’est-a-dire a la r´esolution des
´equations du type AX = Y o`u A ∈ GLn (R) et Y ∈ Mn,1 (R).
1 Calcul du rang par pivot de Gauss
1. ´Ecrire une proc´edure
pivot_cherche:=proc(A::matrix,k::integer)
qui en entr´ee 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`u (i, j) ∈ Jk, qK × Jk, pK est le premier couple d’entier trouv´e tel que
ai,j = 0
ai,j 6= 0 sinon.
2. ´Ecrire une proc´edure
pivot_elim:=proc(A::matrix,k::integer)
qui en entr´ee prend une matrice A ∈ Mq,p (R) de la forme
a1,p
a1,1
0
0 ak,k
0
0 aq,k
aq,p
Publicité
avec ak,k 6= 0. Le proc´edure effectuera un pivot de Gauss en utilisant pour pivot le
nombre ak,k et retournera la matrice ´equivalente ainsi obtenue.
3. ´Ecrire une proc´edure
qui en entr´ee prend une matrice A ∈ Mq,p (R) et en sortie retourne la s´equence B,r o`u
B est la matrice ´equivalente `a A de la forme
b1,1
?
0
0
br,r
0
0
?
0
0
?
?
0
0
Publicité
avec
∀k ∈ J1, rK
bk,k 6= 0
obtenue par l’algorithme du pivot de Gauss, et r le rang de A.
2 R´esolution d’un syst`eme de Cramer
Dans cette partie, on cherche a r´esoudre l’´equation AX = Y ou A ∈ GLn (R) et
Y ∈ Mn,1 (R) par la m´ethode du pivot de Gauss.
2.1 Algorithme du pivot de Gauss
1. ´Ecrire une proc´edure
pivot_cherche_ga:=proc(A::matrix,k::integer)
qui en entr´ee prend une matrice A ∈ GLn (R) de la forme
a1,n
a1,1
0
0 ak,k
0
0 an,k
an,n
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. ´Ecrire une proc´edure
pivot_elim_ga:=proc(A::matrix,Y::matrix,k::integer)
qui en entr´ee prend une matrice A ∈ GLn (R) de la forme
(b) Pour ´eviter ce genre de probl`eme, on modifie l’algorithme de recherche d’un pivot
de la mani`ere suivante : au lieu de se contenter de chercher un pivot non nul dans la
Publicité
colonne k, on cherche le pivot de cette colonne ayant la plus grande valeur absolue.
´Ecrire les proc´edures :
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`u BX = Z
est le systeme ´equivalent au systeme AX = Y obtenu apr`es une ´etape du pivot de
Gauss.
3. ´Ecrire une proc´edure
triang_solve_ga:=proc(A::matrix,Y::integer)
qui en entr´ee prend une matrice A ∈ GLn (R) triangulaire sup´erieure et une matrice
Y ∈ Mn,1 (R) et qui retourne l’unique solution X de l’´equation AX = Y .
4. ´Ecrire une proc´edure
gauss_solve_ga:=proc(A::matrix,Y::matrix)
qui en entr´ee prend une matrice A ∈ GLn (R) et un vecteur Y ∈ Mn,1 (R) et retourne
l’unique solution X du syst`eme AX = Y .
2.2 R´esolution num´erique
1. M´ethode du pivot partiel
(a) En utilisant gauss_solve_ga, r´esoudre le syst`eme lin´eaire
1, 0 · 10−20x + 1, 0 · y = 1, 0
1, 0 · x + 1, 0 · y = 2, 0
Publicité
(cid:26)
puis le syst`eme lin´eaire ´equivalent
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`eme lin´eaire
(a) En utilisant gauss_solve_ga, r´esoudre les syst`emes lin´eaires :
10a + 7b + 8c + 7d = 32
7a + 5b + 6c + 5d = 23
8a + 6b + 10c + 9d = 33
7a + 5b + 9c + 10d = 31
le
puis
syst`eme
« tres l´egerement » modifi´es :
lin´eaire perturb´e,
o`u les
seconds membres
ont
´et´e
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´efinir 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´esoudre le syst`eme 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´e.
R´ep´etez les deux derniers calculs en augmentant la variable Digits.