Cours 1

Introduction
1 / 85
On cherche à résoudre un système linéaire de n équations à n inconnues
x1 , x2 , . . . xn :
8
>
> a11 x1 + a12 x2 + . . . + a1n xn = b1
>
< a21 x1 + a22 x2 + . . . + a2n xn = b2
..
>
> .
>
:
an1 x1 + an2 x2 + . . . + ann xn = bn
Ce système s’écrit sous forme matricielle Ax = b avec

0 1
a11 a12 . . . a1n
Ba21 a22 . . . a2n C
B C
A=B . . . C = (aij ) 2 IRn⇥n ,
@ .. .. .. A
an1 an2 . . . ann
0 1 0 1
b1 x1
B b2 C B x2 C
B C B C
b = B . C = (bi ) 2 IRn , et x = B . C = (xi ) 2 IRn .
@ .. A @ .. A
bn xn
2 / 85
Ce système admet une solution unique ssi une des conditions suivantes
équivalentes est vérifiée :
1. A est inversible
2. det(A) 6= 0
3. rang(A) = n
4. la système homogène Ax = 0 admet x = 0 comme unique solution.
La solution est donnée par les formules de Cramer :

Di
xi = , i = 1, . . . , n,
det(A)
où Di est le déterminant de la matrice obtenue en remplaçant la i ième

colonne de A par b.
Cette formule est d’un intérêt pratique très limité !
3 / 85
En e↵et, le coût de calcul est ⇠ n(n + 1) ! opérations élémentaires
pour n grand.
Résoudre un système de 50 équations avec un ordinateur calculant à 100
mégaflops (108 opérations flottantes par seconde) nécessite :
1052 années (=1042 fois l’âge de l’Univers).
Cours : on définit des méthodes numériques pour résoudre un système

linéaire plus rapidement :
Méthodes directes : on a la solution en un nombre fini d’étapes
Méthodes itératives : on a la solution en un nombre infini d’étapes
(théoriquement).
4 / 85
Chapitre I : Méthodes directes de résolution de systèmes linéaires
5 / 85
I.1 Résolution d’un système triangulaire
Soit le système triangulaire Ax = b suivant :
8
>
> a11 x1 + a12 x2 + . . . + a1n xn = b1
>
>
>
< a22 x2 + . . . + a2n xn = b2
..
> .
>
>
>
> an 1,n 1 xn 1 + an 1,n xn = bn 1
:
ann xn = bn
Si det(A) = a11 a22 . . . ann 6= 0, alors ce système admet une solution
unique
8 bn
> x n = ann ,
>
>
< xn 1 = 1
an 1,n 1 (bn 1 an 1,n xn ),
> ..
>
> .
:
x1 = a111 (b1 a12 x2 . . . a1,n 1 xn 1 a1n xn ).
C’est la méthode de la remontée. Pour un système triangulaire
inférieur, on utilise la méthode de la descente.
Exercice 1
Montrer que ces deux méthodes requièrent n2 opérations élémentaires.
6 / 85
I.2 La méthode d’élimination de Gauss
On transforme Ax = b en un système triangulaire supérieur équivalent.

Propriété : on ne change pas la solution du système quand on ajoute à
une équation donnée une combinaison linéaire des autres équations.
I.2.1 Elimination de Gauss sans permutations
Soit le système linéaire Ax = b avec A = (aij ) et b = (bi ). On pose

(1) (1)
A(1) = (aij ) = A et b (1) = (bi ) = b.
1ère étape : On suppose que a11 6= 0 (c’est le premier pivot). On

élimine x1 de la 2ème à la dernière équation en remplaçant chaque ligne
Li , i = 2, . . . , n, par Li aa11i1 L1 :
ai1
Li Li L1 , i = 2, . . . , n.
a11
7 / 85
On obtient un nouveau système A(2) x = b (2) avec
0 1
a11 a12 ... a1n
B 0 a22 aa21 a12 ... a2n a21 C
a11 a1n C
(2) B 11
A(2) = (aij ) = B . .. .. C,
@ .. . ... . A
0 an2 aan1 11
a12 ... ann an1
a11 a1n
0 1
b1
Bb2 aa21 b1 C
(2) B 11 C
b (2) = (bi ) = B .. C.
@ . A
bn aan1 11
b1
Exercice 2
Montrer que pour tout k = 1, 2, . . . , n 1,
A(k+1) = S (k) A(k)

0 (k) 1
0 1 ak+1,k
I 0 0
1 B . C
avec S (k) = @0 1 0 A et m = (k) @ .. C
(k) B
A.
0 m (k) I akk (k)
an,k
k
8 / 85
(k)
kème étape : Si akk 6= 0 , alors on élimine xk de la k + 1–ième équation
à la dernière en faisant
(k)
(k) (k) aik (k)
Li Li L ,
(k) k
i = k + 1, . . . n.
akk
On a donc
8
(k)
>
> (k+1) (k) aik (k)
>
> a = a a , i, j = k + 1, . . . , n,
>
< ij ij (k) kj
akk
>
> (k)
aik
>
> (k+1) (k) (k)
> b
: i = b i b ,
(k) k
i = k + 1, . . . , n,
akk
On itère ce processus pour k allant de 1 à n 1. Par récurrence, et à

condition qu’on ne rencontre aucun pivot nul, on obtient à la fin un
système triangulaire supérieur A(n) x = b (n) équivalent au système initial
que l’on résout en utilisant la méthode de la remontée.
9 / 85

Cours 1

Transféré par

Droits d'auteur :

Formats disponibles

Cours 1

Transféré par

Informations du document

Titre original

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Cours 1

Transféré par

Droits d'auteur :

Formats disponibles

Introduction

Ce système s’écrit sous forme matricielle Ax = b avec

La solution est donnée par les formules de Cramer :

où Di est le déterminant de la matrice obtenue en remplaçant la i ième

Cours : on définit des méthodes numériques pour résoudre un système

On transforme Ax = b en un système triangulaire supérieur équivalent.

I.2.1 Elimination de Gauss sans permutations

Soit le système linéaire Ax = b avec A = (aij ) et b = (bi ). On pose

1ère étape : On suppose que a11 6= 0 (c’est le premier pivot). On

A(k+1) = S (k) A(k)

On itère ce processus pour k allant de 1 à n 1. Par récurrence, et à

Vous aimerez peut-être aussi