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

Introduction

4ème année

A.U. 2020/2021

Activité introductive

On considère le circuit, donné ci-dessous, pour lequel on donne :

U1 = 100V, U2 = 115V, 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

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

i1 + i2 − i3 = 0

En appliquant la loi des mailles, on obtient

Maille 1 : A, R1, U1, B, U2, R2, A, avec le sens de parcours indiqué :

En remplaçant R1, R2, U1 et U2 par ses valeurs, on obtient

R1 · i1 − U1 + U2 − R2 · i2 = 0.

0.5 · i1 − 0.25 · i2 + 0 · i3 = 15

(1)

(2)

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

i1 + i2 − i3 = 0

En appliquant la loi des mailles, on obtient

Maille 1 : A, R1, U1, B, U2, R2, A, avec le sens de parcours indiqué :

En remplaçant R1, R2, U1 et U2 par ses valeurs, on obtient

R1 · i1 − U1 + U2 − R2 · i2 = 0.

0.5 · i1 − 0.25 · i2 + 0 · i3 = 15

(1)

(2)

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

En appliquant la loi des mailles, on obtient

Maille 1 : A, R1, U1, B, U2, R2, A, avec le sens de parcours indiqué :

En remplaçant R1, R2, U1 et U2 par ses valeurs, on obtient

R1 · i1 − U1 + U2 − R2 · i2 = 0.

0.5 · i1 − 0.25 · i2 + 0 · i3 = 15

(2)

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

Maille 1 : A, R1, U1, B, U2, R2, A, avec le sens de parcours indiqué :

En remplaçant R1, R2, U1 et U2 par ses valeurs, on obtient

R1 · i1 − U1 + U2 − R2 · i2 = 0.

0.5 · i1 − 0.25 · i2 + 0 · i3 = 15

(2)

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

En appliquant la loi des mailles, on obtient

i1 + i2 − i3 = 0

(1)

@UP-Maths

RØsolution numØrique des systŁmes d’Øquations linØaires

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

En appliquant la loi des mailles, on obtient

Maille 1 : A, R1, U1, B, U2, R2, A, avec le sens de parcours indiqué :

En remplaçant R1, R2, U1 et U2 par ses valeurs, on obtient

R1 · i1 − U1 + U2 − R2 · i2 = 0.

0.5 · i1 − 0.25 · i2 + 0 · i3 = 15

(1)

(2)

@UP-Maths

RØsolution numØrique des systŁmes d’Øquations linØaires

(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

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

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







(S)

= 0

i1 + i2 − i3

0.5 · i1 − 0.25 · i2 + 0 · i3 = 5

0 · i1 + 0.25 · i2 + 0.5 · i3 = 15

⇔ RI = U

@UP-Maths

RØsolution numØrique des systŁmes d’Øquations linØaires







, I =



















et U =













−1

0.25

0.5

= −0.5 (cid:54)= 0, ⇒ le système (S) est de Cramer et

où i1 i2 et i3 sont les inconnues, R =

0.5 −0.25

−0.25

det R =

(cid:12)

admet une solution unique, donnée par

0.25 0.5

1 −1

− 0.5

0.25

(cid:12)

0.5

@UP-Maths

RØsolution numØrique des systŁmes d’Øquations linØaires

(cid:136) i2 =

(cid:39) 10 A

0 −1

0.5

15 0.5

det R

0.5 −0.25

(cid:12)

(cid:136) i3 =

0.25

det R

(cid:39) 25 A

(cid:39) 15 A

(cid:12)

5 −0.25

0.25

det R

(cid:136) i1 =

(cid:12)

−1

(cid:12)

0.5

@UP-Maths

RØsolution numØrique des systŁmes d’Øquations linØaires

(cid:12)

0.5 −0.25

(cid:12)

0.25

det R

(cid:136) i3 =

(cid:39) 25 A

(cid:39) 15 A

(cid:12)

−1

(cid:12)

0.5

(cid:12)

(cid:136) i1 =

(cid:136) i2 =

5 −0.25

0.5

0.25

det R

(cid:12)

0 −1

(cid:12)

15 0.5

det R

(cid:39) 10 A

@UP-Maths

RØsolution numØrique des systŁmes d’Øquations linØaires

(cid:39) 15 A

(cid:12)

−1

(cid:12)

0.5

(cid:12)

(cid:136) i1 =

(cid:136) i2 =

(cid:136) i3 =

5 −0.25

0.5

0.25

det R

(cid:12)

0 −1

(cid:12)

15 0.5

det R

0.5 −0.25

0.25

det R

(cid:39) 10 A

(cid:12)

(cid:39) 25 A

@UP-Maths

RØsolution numØrique des systŁmes d’Øquations linØaires

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

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égaﬂops (ﬂops = opérations à virgule

ﬂottante par secondes), il faudrait environ 3 · 10146 années pour résoudre notre

système !

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

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

@UP-Maths

RØsolution numØrique des systŁmes d’Øquations linØaires

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

souhaite de 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égaﬂops (ﬂops = opérations à virgule

ﬂottante 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

(cid:73) 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

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

systèmes d’équations linéaires:

(cid:73) Méthodes directes qui permettent d’obtenir la solution en un nombre ﬁni

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

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

systèmes d’équations linéaires:

(cid:73) Méthodes directes qui permettent d’obtenir la solution en un nombre ﬁni

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

(cid:73) 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

Méthodes de

résolution

AX = b

Méthodes

directes

Méthodes

itératives

Pivot de Gauss

Décomposition

Jacobi

Gauss-Seidel

@UP-Maths

RØsolution numØrique des systŁmes d’Øquations linØaires

Système d’équations linéaires

DØ(cid:28)nition

Un système de n équations à n inconnues x1, x2, · · · , xn, à coefﬁcients ai j, et seconds

membres b1, b2, · · · , bn, est de la forme:







(Sn)

a1 1x1 + a1 2x2 + · · · + a1 nxn = b1

a2 1x1 + a2 2x2 + · · · + a2 nxn = b2

· · ·

an 1x1 + an 2x2 + · · · + an nxn = bn,

@UP-Maths

RØsolution numØrique des systŁmes d’Øquations linØaires

Forme matricielle d’un système linéaire

Un système d’équations linéaires peut aussi s’écrire sous la forme matricielle:

où A ∈ Mn(R) est la matrice dont les coefﬁcients sont les ai j, X ∈ Mn,1(R) est le

vecteur inconnu et b ∈ Mn,1(R) est le vecteur second membre:

AX = b,

A =







a1,1

...

an,1







· · · an,1

...

. . .

· · · an,n

, X =













...

et b =













...

Résultat fondamental :

Un système d’équations linéaires (Sn) admet dans Rn une solution ou une inﬁnité de

solutions ou il n’admet aucune solution.

@UP-Maths

RØsolution numØrique des systŁmes d’Øquations linØaires

Correction :

(cid:136) (S) s’écrit sous la forme matricielle suivante :





−1 1















 =









(S) admet une solution unique X =



. Le déterminant de la matrice vaut

2 (cid:54)= 0 et dans ce cas on dit que (S) est un système de Cramer.

Existence des solutions

Les systèmes suivants ont-ils dans R2 une solution unique, une inﬁnité de solution

ou aucune solution?

(S)

(cid:40)

= 1

x1 + x2

−x1 + x2 = 1

, (S(cid:48))

(cid:40)

x1 + x2 = 1

x1 + x2 = 3

, (S(cid:48)(cid:48))

(cid:40)

= 1

x1 + x2

2x1 + 2x2 = 2

@UP-Maths

RØsolution numØrique des systŁmes d’Øquations linØaires

Existence des solutions

Les systèmes suivants ont-ils dans R2 une solution unique, une inﬁnité de solution

ou aucune solution?

(S)

(cid:40)

= 1

x1 + x2

−x1 + x2 = 1

, (S(cid:48))

(cid:40)

x1 + x2 = 1

x1 + x2 = 3

, (S(cid:48)(cid:48))

(cid:40)

= 1

x1 + x2

2x1 + 2x2 = 2

Correction :

(cid:136) (S) s’écrit sous la forme matricielle suivante :











−1 1



 =









(S) admet une solution unique X =







. Le déterminant de la matrice vaut

2 (cid:54)= 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

(cid:136) (S(cid:48)(cid:48)) s’écrit sous la forme matricielle suivante :





1 1

2 2















 =











1 − x2

(S(cid:48)(cid:48)) admet une inﬁnité de solutions X =

 où x2 est l’inconnue

auxiliaire qui peut prendre une valeur arbitraire. Le déterminant de la matrice

vaut 0 .

(cid:136) (S(cid:48)) s’écrit sous la forme matricielle suivante :















 =









1 1

(S(cid:48)) 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

(cid:136) (S(cid:48)) s’écrit sous la forme matricielle suivante :















 =









1 1

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

(cid:136) (S(cid:48)(cid:48)) s’écrit sous la forme matricielle suivante :









1 1

2 2



 =













(S(cid:48)(cid:48)) admet une inﬁnité de solutions X =





1 − x2



 où x2 est l’inconnue

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

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

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

(S) : AX = b

A ∈ Mn(R)

det A (cid:54)= 0

det A = 0

(S) admet

une unique solution

((S) est de Cramer)

(S) n’admet

pas

des solution

(S) admet

une inﬁnité

de solutions

@UP-Maths

RØsolution numØrique des systŁmes d’Øquations linØaires

(S) : AX = b

A ∈ Mn(R)

det A (cid:54)= 0

det A = 0

(S) admet

une unique solution

((S) est de Cramer)

(S) n’admet

pas

des solution

(S) admet

une inﬁnité

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

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

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