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

Introduction

AN - 3A&B - A.U. 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.

@UP-Maths Résolution numérique des systèmes d’équations linéaires AN

 3

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

@UP-Maths Résolution numérique des systèmes d’équations linéaires AN

 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

@UP-Maths Résolution numérique des systèmes d’équations linéaires AN

 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)

@UP-Maths Résolution numérique des systèmes d’équations linéaires AN

 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

@UP-Maths Résolution numérique des systèmes d’équations linéaires AN

 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)

@UP-Maths Résolution numérique des systèmes d’équations linéaires AN

 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

@UP-Maths Résolution numérique des systèmes d’équations linéaires AN

 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


@UP-Maths Résolution numérique des systèmes d’équations linéaires AN

 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

@UP-Maths Résolution numérique des systèmes d’équations linéaires AN

 6

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

@UP-Maths Résolution numérique des systèmes d’équations linéaires AN

 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

@UP-Maths Résolution numérique des systèmes d’équations linéaires AN

 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

@UP-Maths Résolution numérique des systèmes d’équations linéaires AN

 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?

@UP-Maths Résolution numérique des systèmes d’équations linéaires AN

 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.

@UP-Maths Résolution numérique des systèmes d’équations linéaires AN

 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 !

@UP-Maths Résolution numérique des systèmes d’équations linéaires AN

 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

@UP-Maths Résolution numérique des systèmes d’équations linéaires AN

 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

@UP-Maths Résolution numérique des systèmes d’équations linéaires AN

 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

@UP-Maths Résolution numérique des systèmes d’équations linéaires AN

 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


@UP-Maths Résolution numérique des systèmes d’équations linéaires AN

 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 · · · a1,n  
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.

@UP-Maths Résolution numérique des systèmes d’équations linéaires AN

 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

@UP-Maths Résolution numérique des systèmes d’équations linéaires AN

 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.
@UP-Maths Résolution numérique des systèmes d’équations linéaires AN
 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.

@UP-Maths Résolution numérique des systèmes d’équations linéaires AN

 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 .

@UP-Maths Résolution numérique des systèmes d’équations linéaires AN

 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

@UP-Maths Résolution numérique des systèmes d’équations linéaires AN

 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).

@UP-Maths Résolution numérique des systèmes d’équations linéaires AN