Résolution numérique de systèmes d’équations linéaires

Introduction

Master de Recherche "DSIR"

MNI - 3ème année - A.U. 2020/2021 2022/2023
 2

Activité introductive
On considère le circuit, donné ci-dessous, pour lequel on donne :
U1 = 110V, U2 = 105V, U3 = 90V, R1 = 0.5Ω, R2 = 0.25Ω, et R3 = 0.5Ω, où V et Ω
désignent respectivement Volt et Ohm.

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

 3

Question : Calculer les intensités du courant (en Ampères A) i1 , i2 et i3 ?

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

 3

Question : Calculer les intensités du courant (en Ampères A) i1 , i2 et i3 ?

En appliquant la loi des nœuds en A, on a

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

 3

Question : Calculer les intensités du courant (en Ampères A) i1 , i2 et i3 ?

En appliquant la loi des nœuds en A, on a

i1 + i2 − i3 = 0 (1)

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

 3

Question : Calculer les intensités du courant (en Ampères A) i1 , i2 et i3 ?

En appliquant la loi des nœuds en A, on a

i1 + i2 − i3 = 0 (1)
En appliquant la loi des mailles, on obtient

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

 3

Question : Calculer les intensités du courant (en Ampères A) i1 , i2 et i3 ?

En appliquant la loi des nœuds en A, on a

i1 + i2 − i3 = 0 (1)
En appliquant la loi des mailles, on obtient
Maille 1 : A, R1 , U1 , B, U2 , R2 , A, avec le sens de parcours indiqué :
R1 · i1 − U1 + U2 − R2 · i2 = 0.
En remplaçant R1 , R2 , U1 et U2 par ses valeurs, on obtient

0.5 · i1 − 0.25 · i2 + 0 · i3 = 5 (2)

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

 4

Maille 2 : A, R2 , U2 , B, U3 , R3 , A avec le sens de parcours indiqué, l’application de la

loi des mailles donne :
R2 · i2 − U2 + U3 + R3 · i3 = 0.
En remplaçant R2 , R3 , U2 et U3 par ses valeurs, on obtient
0 · i1 + 0.25 · i2 + 0.5 · i3 = 15 (3)
On obtient un système d’équation linéaires, en effet

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

 4

Maille 2 : A, R2 , U2 , B, U3 , R3 , A avec le sens de parcours indiqué, l’application de la

loi des mailles donne :
R2 · i2 − U2 + U3 + R3 · i3 = 0.
En remplaçant R2 , R3 , U2 et U3 par ses valeurs, on obtient
0 · i1 + 0.25 · i2 + 0.5 · i3 = 15 (3)
On obtient un système d’équation linéaires, en effet
(1), (2) et (3) ⇒

i1 + i2 − i3
 =0
(S) 0.5 · i1 − 0.25 · i2 + 0 · i3 = 5 ⇔ RI = U

0 · i1 + 0.25 · i2 + 0.5 · i3 = 15


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

 5

     
1 1 −1 i1 0
     
0.5 −0.25 0  , I = i2  et U =  5  .
où i1 i2 et i3 sont les inconnues, R =      

0 0.25 0.5 i3 15
−0.25 0 1 −1
det R = − 0.5 = −0.5 6= 0, ⇒ le système (S) est de Cramer et
0.25 0.5 0.25 0.5
admet une solution unique, donnée par

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

 6

0 1 −1
5 −0.25 0
15 0.25 0.5
• i1 = det R ' 15 A

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

 6

0 1 −1
5 −0.25 0
15 0.25 0.5
• i1 = det R ' 15 A
1 0 −1
0.5 5 0
0 15 0.5
• i2 = det R ' 10 A

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

 6

0 1 −1
5 −0.25 0
15 0.25 0.5
• i1 = det R ' 15 A
1 0 −1
0.5 5 0
0 15 0.5
• i2 = det R ' 10 A
1 1 0
0.5 −0.25 5
0 0.25 15
• i3 = det R ' 25 A

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

 7

Pourquoi le problème de la résolution d’un tel système se pose alors que la formule de
Cramer permet de le résoudre?

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

 8

Supposons qu’on a un circuit complexe qui contient plus de 100 mailles et on

souhaite calculer les valeurs de l’intensité ik , 1 ≤ k ≤ 100.

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

 8

Supposons qu’on a un circuit complexe qui contient plus de 100 mailles et on

souhaite calculer les valeurs de l’intensité ik , 1 ≤ k ≤ 100.
Nous devons calculer:
un déterminant d’une matrice de taille n ⇒ n! − 1 additions et n!(n − 1)
multiplications ⇒ n! − 1 + n!(n − 1) = nn! − 1 opérations.
n + 1 déterminants de taille n ⇒ (n + 1)(nn! − 1) opérations.
⇒ Pour n = 100 on trouve 9, 4 · 10161 opérations.
Avec un ordinateur fonctionnant à 100 mégaflops (flops = opérations à virgule
flottante par secondes), il faudrait environ 3 · 10146 années pour résoudre notre
système !

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

 9

En pratique, Il existe deux grandes familles de méthodes de résolution pour des

systèmes d’équations linéaires:
I Méthodes directes qui permettent d’obtenir la solution en un nombre fini
d’opérations soit par triangularisation ou soit par décomposition de la matrice A.
Les méthodes directes que nous allons étudier sont: Pivot de Gauss et La
méthode de décomposition LU

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

 9

En pratique, Il existe deux grandes familles de méthodes de résolution pour des

systèmes d’équations linéaires:
I Méthodes directes qui permettent d’obtenir la solution en un nombre fini
d’opérations soit par triangularisation ou soit par décomposition de la matrice A.
Les méthodes directes que nous allons étudier sont: Pivot de Gauss et La
méthode de décomposition LU
I Méthodes itératives qui consistent à construire une suite (xn )n qui converge
vers la solution. Les méthodes itératives que nous allons étudier sont : La
méthode de Jacobi et la méthode de Gauss-Seidel

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

 10

10

Méthodes de
résolution
AX = b

Méthodes Méthodes
directes itératives

Décomposition
Pivot de Gauss Jacobi Gauss-Seidel
LU

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

 11

11

Système d’équations linéaires

Définition
Un système de n équations à n inconnues x1 , x2 , · · · , xn , à coefficients ai j , et seconds
membres b1 , b2 , · · · , bn , est de la forme:


a1 1 x1 + a1 2 x2 + · · · + a1 n xn = b1

a2 1 x1 + a2 2 x2 + · · · + a2 n xn = b2





 ··· ··· ··· ···
(Sn )


 ··· ··· ··· ···
··· ··· ··· ···





an 1 x1 + an 2 x2 + · · · + an n xn = bn


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

 12

12

Forme matricielle d’un système linéaire

Un système d’équations linéaires peut aussi s’écrire sous la forme matricielle:
AX = b,
où A ∈ Mn (R) est la matrice dont les coefficients sont les ai j , X ∈ Mn,1 (R) est le
vecteur inconnu et b ∈ Mn,1 (R) est le vecteur second membre:
   
  x1 b1
a1,1 · · · an,1  
x 
 
b 
 . .. ..   2  2
A= . . , X = et b =  . 
 . .  .

 ..   .. 
an,1 · · · an,n
   
xn bn

Résultat fondamental :
Un système d’équations linéaires (Sn ) admet dans Rn une solution ou une infinité de
solutions ou il n’admet aucune solution.

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

 13

13

Existence des solutions

Les systèmes suivants ont-ils dans R2 une solution unique, une infinité de solution
ou aucune solution?
( ( (
x1 + x2 =1 x 1 + x 2 = 1 x1 + x2 =1
(S) , (S 0 ) , (S 00 )
−x1 + x2 = 1 x1 + x2 = 3 2x1 + 2x2 = 2

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

 13

13

Existence des solutions

Les systèmes suivants ont-ils dans R2 une solution unique, une infinité de solution
ou aucune solution?
( ( (
x1 + x2 =1 x 1 + x 2 = 1 x1 + x2 =1
(S) , (S 0 ) , (S 00 )
−x1 + x2 = 1 x1 + x2 = 3 2x1 + 2x2 = 2
Correction :
• (S) s’écrit sous la forme matricielle suivante :
    
1 1 x 1
   1 =  
−1 1 x2 1
 
0
(S) admet une solution unique X =  . Le déterminant de la matrice vaut
1
2 6= 0 et dans ce cas on dit que (S) est un système de Cramer.
Résolution numérique des systèmes d’équations linéaires
 14

14

• (S 0 ) s’écrit sous la forme matricielle suivante :

    
1 1 x 1
   1 =  
1 1 x2 3

(S 0 ) n’admet pas des solutions. Le déterminant de la matrice vaut 0.

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

 14

14

• (S 0 ) s’écrit sous la forme matricielle suivante :

    
1 1 x 1
   1 =  
1 1 x2 3

(S 0 ) n’admet pas des solutions. Le déterminant de la matrice vaut 0.

• (S 00 ) s’écrit sous la forme matricielle suivante :
    
1 1 x 1
   1 =  
2 2 x2 2
 
1 − x2
(S 00 ) admet une infinité de solutions X =   où x2 est l’inconnue
x2
auxiliaire qui peut prendre une valeur arbitraire. Le déterminant de la matrice
vaut 0 .

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

 15

15

(S) : AX = b
A ∈ Mn (R)

det A 6= 0 det A = 0

(S) admet (S) n’admet (S) admet

une unique solution pas une infinité
((S) est de Cramer) des solution de solutions

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

 15

15

(S) : AX = b
A ∈ Mn (R)

det A 6= 0 det A = 0

(S) admet (S) n’admet (S) admet

une unique solution pas une infinité
((S) est de Cramer) des solution de solutions

L’objectif de ce cours est de résoudre des systèmes de Cramer en utilisant des

méthodes numériques (à travers des algorithmes).

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