CPGE OUJDA SPE

Résolution d'un système linéaire inversible à l'aide de la méthode de Gauss

On approximera la solution par une valeur de la suite qui converge vers la solution.

Description de l’algorithme du pivot de Gauss

Sur un système linéaire de la forme hU ; i les traitements possibles

sont sans changer sa solution:

_ Changer l’ordre des équations

_ Changer l’ordre des variables

_ Multiplier une équation par une constante non nulle

_ Ajouter à une équation une « combinaison linéaire » des autres équations

_ Le but est de faire le nombre d'opérations possibles afin d'obtenir un système tri-diagonale. Et par remontées successives d'avoir les solutions du système initiale.

Où il est facile par remontées successives d'avoir la solution si elle existe.

Dans ce texte, on suppose que les systèmes linéaires sont de Cramer, c’est-à-dire qui admettent une unique solution. La matrice A est donc inversible. On suppose que A est de taille n de coefficients

A chaque étape, on obtient un sous-système carré qui a une inconnue de moins.

Le cas triangulaire

Si la matrice A est triangulaire, on résoud facilement le système par "substitutions remontantes".

Le système s’écrit :

On a ainsi :

Implémentation en Python

Découpage du travail

def echanges_lignes(A,i,j):

nc=len(A[i])

for k in range(nc):

A[i][k], A[j][k] = A[j][k], A[i][k]

def tranvection_ligne(A,i,j,x):

nc=len(A[i])

for k in range(nc):

A[i][k] += x * A[j][k]

Choix du pivot

A cause des arrondis dans les calculs, le choix du pivot est essentiel.

_ La règle est de toujours choisir comme pivot la plus grande valeur absolue des éléments d'une sous-colonne choisie. On fera alors un échange de ligne afin d'amener ce pivot à sa position ultime, c'est-à dire tout en haut d'une sous-colonne traitée.

Codons maintenant la fonction qui recherche le pivot maximal.

def pivot(A,i):

n=len(A) # nb de lignes du systeme

max=i # le numero du maximum pour initialisation

for k in range(i+1,n):

if abs(A[k][i]) > abs(A[max][i]):

max=k # nouveau pivot trouve

return max

Puisque nous allons appliquer des échanges et des transvections à la matrice de départ, celle-ci va être modifiée. Nous allons donc faire en premier lieu une copie de notre donnée

def copie_matrice(M):

n = len(M)

N = [[] for _ in range(n)]

for i in range(n) :

for elem in M[i]:

N[i].append(elem)

return N

Recoller les morceaux

import numpy as np
def resolution(A, Y):

A0 = copie_matrice(A)

n = len(A)

for i in range(n-1):

j = pivot(A0, i)

echanges_lignes(A0, i, j)

Y[i], Y[j] = Y[j], Y[i]

for k in range(i+1, n):

x = A0[k][i]/float(A0[i][i])

tranvection_ligne(A0, k, i, -x)

Y[k] -= Y[i]*x

# B est maintenant triangulaire

X = [0]*n

for i in range(n-1, -1, -1):

X[i] = (Y[i]-sum(A0[i][j]*X[j] for j in range(i+1,n)))/float(A0[i][i])

return X

Testons avec :

A=[[2,1,-1],[1,-1,1],[1,1,-2]]

B=[1,2,-3]

print(A,"X =",B)

print("Solution")

X=resolution(A,B)

print("X =",X)

Comparaison avec Numpy et un logiciel de calcul formel

aa=np.array(A)

xx=np.array(X)

print(np.dot(aa,xx))

La fonction numpy.linalg.solve permet de résoudre les systèmes linéaires. Elle utilise des

Complexité temporelle

Coût temporel de l’élimination :

On effectue = transvections sur la matrice A donc de l’ordre de. Chaque transvection coûte opérations flottantes du type . Il y a donc environ opérations flottantes du type

Pour chercher les pivots, pour compris entre entre, on effectue comparaisons du type, soit un total de comparaisons qui est de l’ordre de.

Coût de la remontée :

Il y a deux boucles imbriquées, le coût est seulement quadratique.

Ainsi le coût global est en en on parle de complexité cubique.