Cours De Maths: Résolution des systèmes d’équations linéaires

Résolution des systèmes d’équations linéaires

I-Rappel sur les systèmes linéaires :

Nous cherchons à résoudre un système linéaire de n équations à n inconnues :

(1)

Où les aij sont les coefficients du système ; les xi les inconnues et les bi forment le second membre.

On associe l’équation matricielle : AX = B (2)

au système (1), où la matrice A et les vecteurs X et B sont définit par :

(3)

1) Opérations sur la matrice A :

Le système linéaire (1) reste invariant pour les 3 opérations suivantes, effectuées dans n’importe quel ordre et un nombre de fois indéterminé :

• Permutation de 2 lignes de la matrice A (et donc du vecteur B) ;

• Multiplication des éléments d’une ligne par une même constante non nulle

• Ajouter à une ligne Li une combinaison linéaire des autres lignes :

(4)

2) Cas des systèmes triangulaires :

Définition 1 : On dira que la matrice A est triangulaire supérieure si pour tout couple i,j tel que

)

NB : Le déterminant d’une matrice triangulaire est égales au produit des éléments de la diagonale.

Théorème 1 : Pour que le système (1) admette une et une seule solution, il faut et il suffit que det A 0. Dans ce cas, la matrice A est inversible et l’unique solution est donnée par (6)

3) Utilisation pratique des formules de Cramer :

Cramer propose les formules suivantes comme solution du système (1) :

Théorème 2 : Lorsque det A 0, la solution est donnée par :

(7)

Malheureusement, les formules de Cramer nécessitent un nombre d’opération trop élevé [ (n2-1)n! multiplications] et elles sont en pratique inutilisables. En effet, si n=20, il faut 1021 multiplications, si l’ordinateur fait une multiplication en 3 x 10-10 s, cela fait presque 105 années.

Il existe 2 types de méthodes numériques plus rapide et plus pratique pour résoudre le système (1) : les méthodes directes et les méthodes itératives.

II) Méthodes directes :

Les méthodes directes permettent d’obtenir la solution exacte d’un système en un nombre fini d’étapes. Nous mettrons en œuvre 3 méthodes directes :

A) Méthode du pivot de Gauss :

1) Principe :

Le procédé d’élimination de Gauss comprend 2 étapes :

a) Transformer le système (1) en un système équivalent triangulaire supérieur possédant la même solution que (1) (triangularisation) ;

b) Résoudre ce système triangulaire.

2) Exemple : Prenons le système suivant (n=3) :

(8)

a) Phase 1 :Triangularisation de la matrice A :

 Etape 1 : Les opérations à faire sont :

i. Parmi les coefficients de la 1° colonne (colonne ), on cherche celui dont la valeur absolue est la plus grande. Ici, m=2 l’indice de sa ligne. Le coefficient est appelé le 1° pivot ;

ii. On permute les lignes (L1) et (L2), le système devient :

(9)

iii. Ensuite, nous soustrayons a21/a11 (=3/4) fois l’équation L1 à l’équation L2 et a 31/a11 (=2/4) fois l’équation L1 à l’équation L3. Nous obtenons le système (10) suivant équivalent au (9) :

(10)

 Etape 2 : ‘’ On oublie ‘’ la ligne L1 puis :

i. On recherche parmi les lignes L2 et L3 , celui qui a le plus grand coefficient de y en valeur absolue, ici c’est la ligne L3 .

ii. On permute les lignes L2 et L3 ; le système devient :

(11)

iii. On laisse les lignes L1 et L2 inchangées et on soustraie fois L2 à L3 ; le coefficient de y dans l’équation L3 s’annule et on obtient alors le système équivalent suivant :

(12)

b) Phase 2 : Résolution du système triangulaire

De (12) On déduit que :

3) Cas général :

La méthode de Gauss Comprend 2 phases pour résoudre le système (1)

a) Phase 1 : Triangularisation de la matrice A :

 Etape 1 : Les opérations à faire sont :

i) Rechercher, parmi les coefficients a11 , a21 … an1 de la 1ère colonne (x), celui dont la valeur absolue est la plus grande. Soit m l’indice de sa ligne. Le coefficient am1 est appelé le 1er pivot.

ii) Permuter les lignes (1) et (m) ;

NB : Les sous-étapes i) et ii) s’appelle pivotage partiel : elle consiste à échanger 2 équations dans le but d’avoir le plus grand pivot en valeur absolue ;

iii) Afin d’éliminer x1 dans les lignes i=2 à n, donc avoir des zéros au dessous de a11 , il suffit de lui retrancher ai1/a11 fois la ligne L1 : pour : transformer la ligne Li en Li(2)= Li – (ai1/a11)L1

Càd : dans chaque ligne Li (i=2…n), transformer les coefficients :

aij (j=1…n) en aij(2)=

...