Livre_silo 30 août 2013 16:32 Page 180
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
180
Informatique pour tous
Dans le pseudo-code qui suit, on résout le système Ax = y. La ligne L i désigne à la fois
les coefficients de A (qui sont dans une matrice, un tableau bidimensionnel) et les seconds
membres, qui sont dans une matrice colonne y. Les indexations de tableaux vont de 0
à n − 1 comme en Python :
pour i de 0 à n − 2 faire
Trouver j entre i et n − 1 tel que |a j,i | soit maximale.
Échanger L i et L j (coefficients de la matrice et membres de droite).
pour k de i + 1 à n − 1 faire
L k ← L k −
a k,i
a i,i
Li
Rechercher j entre i et n tel que |a j,i | soit maximale (puis échanger deux lignes) a deux
objectifs : d’une part s’assurer que le coefficient en position (i, i) sera différent de 0 (c’est
essentiel pour pouvoir pivoter) et, d’autre part, minimiser les erreurs numériques dans la
suite du calcul.
Arrivé ici, le système est sous forme triangulaire et il n’y a plus qu’à « remonter », via des
substitutions. Le résultat est mis dans un tableau x et il s’agit donc de calculer :
x i =
1
a i,i
(
y i −
n−1 ∑
k=i+1
a i,k x k
)
.
pour i de n − 1 à 0 faire
pour k de i + 1 à n − 1 faire
y i ← y i − a i,k x k
x i ←
y i
a i,i
Exercice 7.5 Montrer que le caractère « de Cramer » d’un système ne dépend pas des membres de droite
des équations.
7.1.5 Le formalisme matriciel
Décrivons rapidement le pivot de Gauss dans le cadre matriciel. On note que ce point de
vue peut être mis de côté dans un premier temps si le cours sur les matrices n’a pas encore
été traité en mathématiques.
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
180
Informatique pour tous
Dans le pseudo-code qui suit, on résout le système Ax = y. La ligne L i désigne à la fois
les coefficients de A (qui sont dans une matrice, un tableau bidimensionnel) et les seconds
membres, qui sont dans une matrice colonne y. Les indexations de tableaux vont de 0
à n − 1 comme en Python :
pour i de 0 à n − 2 faire
Trouver j entre i et n − 1 tel que |a j,i | soit maximale.
Échanger L i et L j (coefficients de la matrice et membres de droite).
pour k de i + 1 à n − 1 faire
L k ← L k −
a k,i
a i,i
Li
Rechercher j entre i et n tel que |a j,i | soit maximale (puis échanger deux lignes) a deux
objectifs : d’une part s’assurer que le coefficient en position (i, i) sera différent de 0 (c’est
essentiel pour pouvoir pivoter) et, d’autre part, minimiser les erreurs numériques dans la
suite du calcul.
Arrivé ici, le système est sous forme triangulaire et il n’y a plus qu’à « remonter », via des
substitutions. Le résultat est mis dans un tableau x et il s’agit donc de calculer :
x i =
1
a i,i
(
y i −
n−1 ∑
k=i+1
a i,k x k
)
.
pour i de n − 1 à 0 faire
pour k de i + 1 à n − 1 faire
y i ← y i − a i,k x k
x i ←
y i
a i,i
Exercice 7.5 Montrer que le caractère « de Cramer » d’un système ne dépend pas des membres de droite
des équations.
7.1.5 Le formalisme matriciel
Décrivons rapidement le pivot de Gauss dans le cadre matriciel. On note que ce point de
vue peut être mis de côté dans un premier temps si le cours sur les matrices n’a pas encore
été traité en mathématiques.