CPGE-AGADIR TP Python
Algèbre linéaire avec python
Pivot de Gauss
On décrit ici un algorithme pour résoudre numériquement des systèmes linéaires. Après une phase d’introduction,
on s’en remet au formalisme matriciel. On décrit les algorithmes permettant les opérations de base (transvections
et échanges de lignes…), puis l’algorithme du pivot en lui-même.
I-Introduction
Prenons un système 3 x3 que l’on veut résoudre:
𝑥 + 𝑦 + 𝑧 = 2 (𝐿1)
{𝑥 − 𝑦 + 2𝑧 = 9 (𝐿2)
2𝑥 − 𝑦 + 𝑧 = 7 (𝐿3)
Pour résoudre le système et éliminer la variable x dans les deux dernières équations, on commence par réaliser les
opérations L2 L2- L1 et L3 L3 - 2x L1. On obtient alors le système:
𝑥 + 𝑦 + 𝑧 = 2 (𝐿1)
{ −2𝑦 + 𝑧 = 7 (𝐿2)
−3𝑦 − 𝑧 = 3 (𝐿3)
On peut ensuite éliminer y dans la dernière équation en réalisant l’opération L3 L3 - (3/2)x L2. On obtient
𝑥 + 𝑦 + 𝑧 = 2 (𝐿1)
{ −2𝑦 + 𝑧 = 7 (𝐿2)
5 15
− 𝑧 = − (𝐿3)
2 2
Maintenant que le système est sous forme triangulaire, on va pouvoir effectuer une phase de remontée pour
déterminer la solution :
𝑥+𝑦+𝑧 =2 𝑥+𝑦+𝑧 =2 𝑥 = 12
{ −2𝑦 + 𝑧 = 7 { 𝑦 = −2 { 𝑦 = −2
𝑧=3 𝑧=3 𝑧=3
,
II- Formalisme matriciel et opérations élémentaires
Le système précédent peut s’écrire sous forme matricielle
𝟏 𝟏 𝟏 𝒙 𝟐
AX = Y avec A= ( 𝟏 − 𝟏 𝟐 ) X= (𝒚) Et Y= (𝟗)
𝟐 −𝟏 𝟏 𝒛 𝟕
On a vu que la résolution se fait en deux phases : mise du système sous forme triangulaire, et phase de remontée.
Pour la première phase, l’opération principale consiste à ajouter à une ligne une autre ligne, multipliée par
un certain facteur : cette opération s’appelle une transvection. Remarquez qu’il faut faire la même
opération sur le vecteur colonne Y.
Pivot de gausse 1/4 M.GUEROIHI
Ajoutons à cela une autre opération : l’échange de deux lignes. Nous n’en avons pas eu besoin dans
l’exemple introductif, mais si nous étions par exemple partis du système :
𝑦 + 𝑧 = 2 (𝐿1)
{ 𝑥 − 𝑦 + 2𝑧 = 9 (𝐿2)
2𝑥 − 𝑦 + 𝑧 = 7 (𝐿3)
Il aurait été impossible d’éliminer x dans la deuxième et troisième équation puisque le coefficient devant x est nul
dans la première. Pour se faire, il suffit d’échanger la première ligne avec une des deux autres, ce qui se traduit
matriciellement par l’échange de deux lignes de la matrice A et des lignes correspondantes du vecteur colonne Y .
Dans notre implémentation, on décide de représenter une matrice par une liste double (une liste de listes).
𝟏 𝟏 𝟏
Par exemple, la matrice M =( 𝟏 − 𝟏 𝟐 ) sera représenter par la liste L=[[1,1,1],[1,-1,2],[2,-1,1]].
𝟐 −𝟏 𝟏
On accèdera à l’indice (i , j) de la matrice A grâce à l’instruction L[i][j]. Attention cependant aux indices: en
mathématiques, les indices des matrices commencent à 1. En Python, les indices commencent à 0!
On décide de résoudre les systèmes linéaires sous forme matricielle. Pour résoudre le système AX = Y supposé de
Cramer ( la matrice A est inversible).
On effectue les opérations sur les lignes de la matrice A et le vecteur colonne B jusqu’à arriver à un système
triangulaire. On remonte ensuite par substitutions pour obtenir la solution du système.
On aura besoin d'une fonction permettant de réaliser la copie d'une matrice. En effet, a priori on ne veut pas
toucher à la matrice de départ A, ni au vecteur colonne Y.
def copie_matrice(A):
return [A[i][:] for i in range(len(A))]
Écrire une fonction echanger(A,i,j) qui échange dans la matrice A la ligne i et la ligne j. On devra
obtenir:
>>>A=[[1,2,3],[5,6,7],[9,10,11]]
>>>echanger (A , 0, 2)
>>>A
[[9,10,11],[5,6,7],[1,2,3]
Écrire une fonction transvection (A,i, j ,mu) qui ajoute, à la ligne i, mu fois la ligne j.
>>>A=[[1,2,3],[5,6,7],[9,10,11]]
>>>transvection (A , 0, 2, -2)
>>>A
[[-17,-18,-19],[5,6,7],[9,10,11]]
Pivot de gausse 2/4 M.GUEROIHI
Écrire une fonction choixPivot(A,i) qui cherche dans les éléments ai,i, a(i+1),i , a(i+2),i
....,an,i le pivot ayant la valeur maximum en valeur absolue et qui renvoie l’indice de la ligne
correspondante. On doit obtenir le résultat suivant:
>>> A =[[1,3,2,4,1],[0,0,3,7,1],[0,1,5,1,0],[1,2,1,1,4]]
>>> indice_pivot(A ,1)
Lorsque l’on s’occupe de la colonne d’indice i, l’algorithme du pivot de Gausse déroule de la façon suivante:
— rechercher un pivot : on le trouve à la ligne i0 ;
— échanger les lignes i et i0 ;
𝒂
— pour chaque valeur de k entre i +1 et n, réaliser l’opération 𝑳𝒌 𝑳𝑲 − 𝒂𝒌𝒊 𝑳𝒊
𝒊𝒊
Et on passe ensuite à la colonne suivante. On fait cela sur la matrice A et le vecteur colonne Y pour les
colonnes de 1 à n.
Écrire une fonction trianguler(A,Y) qui réalise cette opération. On devrait obtenir le résultat suivant
>>>A=[[1, 1, 1], [1, -1, 2], [2, -1, 1]]
>>>Y=[[2],[9],[7]]
>>>trianguler(A,Y)
>>> A
[[2, -1, 1], [0.0, 1.5, 0.5], [0.0, 0.0, 1.6666666666666667]]
>>> Y
[[7], [-1.5], [5.0]]
Calculer la complexité de la fonction trianguler(M)
La phase suivante est la phase de remontée. Comme son nom l'indique, il suffit de calculer les composantes de X
en commençant par la dernière. Posons 𝐴 = (𝑎𝑖,𝑗 )0≤𝑖 ,𝑗≤𝑛−1 𝑎𝑣𝑒𝑐 𝑎𝑖,𝑗 = 0 𝑝𝑜𝑟 𝑖 > 𝑗
Posons X le vecteur colonne de composantes : 𝑥0 , 𝑥1 , … , 𝑥𝑛−1 , le produit A.X s'écrit:
𝑎0,0 𝑎0,1 . . . . . . 𝑎0,𝑛−1 𝑥0 𝑛−1
𝑎0,0 . 𝑥0 + ∑ 𝑎0,𝑗 . 𝑥𝑗
𝑗=1
0 𝑎1,1 𝑎 1,2 . . . 𝑎1,𝑛−1 𝑛−1
𝑥1 𝑎1,1 . 𝑥1 + ∑ 𝑎1,𝑗 . 𝑥𝑗
𝑗=2
0 0 𝑎 2,2 . . . 𝑎2,𝑛−1 𝑛−1
× 𝑥2 = 𝑎2,2 . 𝑥2 + ∑ 𝑎2,𝑗 . 𝑥𝑗
. 𝑗=3
. . . . . . . . . . . . . .
. . .
. . .
0 . . . . . . 0 𝑎𝑛−1,𝑛−1 𝑥𝑛−1 𝑎𝑛−1,𝑛−1 . 𝑥𝑛−1 .
( ) ( ) ( )
Pour tout i entre 0 et n-1, on tire l'égalité : 𝑎𝑖,𝑖 . 𝑥𝑖 + ∑𝑛−1
𝑗=𝑖+1 𝑎𝑖,𝑗 . 𝑥𝑗 = 𝑦𝑖
Pivot de gausse 3/4 M.GUEROIHI
1
L'expression 𝑥𝑖 = 𝑎𝑖,𝑖
( 𝑦𝑖 − ∑𝑛−1
𝑗=𝑖+1 𝑎𝑖,𝑗 . 𝑥𝑗 ) , ne fait intervenir que les 𝑥𝑖 avec j > i.
1 𝑛−1
𝑋[𝑖][0] = . ( 𝑌[𝑖][0] − ∑ 𝐴[𝑖][𝑗]. 𝑋[𝑗][0])
𝐴[𝑖][𝑖] 𝑗=𝑖+1
Écrire la fonction remonter(A,Y) de remontée qui prend en argument la matrice A et le vecteur colonne Y
de type supposés triangulaires et renvoie le vecteur colonne solution X associé. On doit obtenir le résultat
suivant:
>>>A=[[1, 1, 1], [1, -1, 2], [2, -1, 1]]
>>>Y=[[2],[9],[7]]
>>>trianguler(A,Y)
>>> A
[[2, -1, 1], [0.0, 1.5, 0.5], [0.0, 0.0, 1.6666666666666667]]
>>> Y
[[7], [-1.5], [5.0]]
>>> remonter(A,Y)
[[1.0], [-2.0], [3.0]]
Écrire une fonction PivotDeGauss(A,Y) qui prend en argument la matrice A carrée supposée inversible et
la matrice colonne Y et renvoie le vecteur solution X de l’équation AX = Y. Par exemple, pour le système de
l’exemple introductif :
𝑥+𝑦+𝑧=2
{ 𝑥 − 𝑦 + 2𝑧 = 9
2𝑥 − 𝑦 + 𝑧 = 7 )
On aura :
>>>PivotDeGauss([[1, 1, 1], [1, -1, 2], [2, -1, 1]],[[2],[9],[7]])
[[1.0], [-2.0], [3.0]]
Vérifier le résultat avec la fonction solve du module numpy.linalg, on doit obtenir :
>>>from numpy.linalg import solve
>>>solve([[1, 1, 1], [1, -1, 2], [2, -1, 1]],[[2],[9],[7]])
array([[ 1.],
[-2.],
[ 3.]])
Pivot de gausse 4/4 M.GUEROIHI
