Méthodes numériques

en
Ingénierie

Présenté par:
Dr. J. Ferahtia
 Introduction générale

I. Introduction générale
Un grand nombre de problèmes tels que les équations du second degré, les
intégrales admettant une primitive facile à calculer, les équations différentielles
possède une solution exacte ou analytique.
Cependant

Des problèmes tels que les équations polynomiales de degrés >5 , la majorité
des équations différentielles, les problèmes dont on ne connaît pas la solution
analytiques, problèmes dont la solution analytique est Inconnue ou inexploitable
exemple:équations transcendantes telles:
a.cos2x+[Link]+c=0
y’’ cos2x+x3y’+cy=0
ne peuvent être résolus de manière exacte.

d’où
Le seul moyen de calculer la solution, lorsqu’elle existe, est de l’approximer
numériquement. C’est le domaine de l’analyse numérique.

Le chapitre des mathématique qui a pour but d’arriver aux valeurs numériques
s’appelle analyse numérique.
 Introduction générale

La grande partie des calculs numériques se fait sur ordinateur. Mais pour que
les machines soient capable de faire des calculs, il faut les programmer, donc
…….écrire des programmes, qui est l’objet principale de l’analyse numérique.
 Cours d’analyse numérique
Introduction générale

Définition algorithmique
mathématique :: la
générale : l’analyse la résolution algorithmique
mathématique
numérique estde d’unnumérique
le l’analyse
domaine problème
des comporteoù
mathématiques
s’intéresse:
-à L’approximation
l’on
l’étude
étudie
des d’un problème
desconditions
algorithmes
d’existence mathématique
permettant et d’unicité
de résoudredécrit
de enproblèmes
lades termes
solution d’opérateurs
ainsi qu’aux de
de l’analyse
l’analyse (i.e. dérivées,
performances
mathématiques intégrales,..)
duauprocédé
moyen de
de résolutionpar(convergence,
un problème numérique
calcul arithmétique. défini au moyen
stabilité, précision…).
des seuls opérateurs arithmétiques.
- L’élaboration d’un procédé de résolution de ces problèmes numériques associé.
Introduction générale

Analyse
Analysenumérique
numérique

Sciences de
l’ingénieur

Informatique

Mathématiques
 Simulations
Simulationsnumériques
numériquesde
dephénomènes
phénomènescomplexes
complexes
"Scientific Computing / Computational Sciences"
"Scientific Computing / Computational Sciences"

Modélisation Analyse Résolution

Résolutionnumérique
Modélisation Analysemathématique
mathématique numérique
etetprogrammation
programmation

objectif : objectif :
• étude
• décrire le comportement des équations
de systèmes précédentes
physiques pour
beaucoup
• existence, de problèmes n’ont pas de solutions analytiques :
prédire, optimiser, contrôler unicité de solutions
le comportement de ces systèmes
recours aux ordinateurs pour la résolution
• mise en équation des•• choix
nature
phénomènesdes solutions : stables,
(et étude) physiques
de la méthodeobservésinstables, régulières,
de résolution
•singulières,
• sous-entendu : hypothèses, des ...
écrituredomaine de validité
algorithmes limité,
de résolution
description partielle parfois erronée
• analyse de la réalité, ...
de la solution
 Introduction générale

Objectifs du calcul numérique

 proposer des algorithmes pour calculer une solution approchée

 contrôler les différentes sources d’erreurs propres à l’approximation numérique

 tenir compte du fait que plusieurs algorithmes peuvent être utilisés pour
résoudre le même problème.

 fournir des valeurs numériques, c-à-d en fin du compte des nombres réels.
 Introduction générale

Domaines d’application

physique, mécanique, géophysique, aéronautique, génie civil,

électromagnétisme, météorologie, sciences de l’environnement
(pollution, nappes phréatiques, inondations, ...), biologie,
chimie, finance, ...
 Cours d’analyse numérique
Introduction générale

Les Méthodes numériques élémentaires couvre plus particulièrement

les sujets suivants :

– Analyse d’erreurs ;

– Racines d’une équation algébrique ;

– Systèmes d’équations linéaires et non linéaires ;

– Méthodes itératives et systèmes dynamiques ;

– Interpolation ;

– Différentiation et intégration numériques ;

– Equations différentielles ordinaires.

Calculs numériques approchés
 Chapitre I: Calculs numériques approchés

Il fait combien le calcul de :

2 * 2  2?
Réponse :

Il fait combien le calcul de :

1-3*(4/3-1)?
Réponse :
 Chapitre I: Calculs numériques approchés

Autre exemple :

Si on demande à un ordinateur d’effectuer les sommations suivantes

En utilisant les quantités :
a=1020, b=-1020, c=1

1ère opération :

(a+b)+c= 1

2ème opération
a+(b+c)= 0
 Chapitre I: Calculs numériques approchés

Pourquoi l’ordinateur fait-il tant d’erreurs?

Réponse :

Parce qu’il ne connaît qu’un nombre finit de nombre !

 Chapitre I: Calculs numériques approchés

À chaque fois qu’on effectue un calcul numérique, l’on est confronté aux erreurs

Qu’est ce qu’une erreur?

D’où viennent les erreurs?

Quelles conséquences ont-elles?

Comment analyser leurs effets?

 Chapitre I: Calculs numériques approchés
I-1 Nombre approché

Un nombre approché x̂ est un nombre légèrement différent du nombre exact x

et qui dans le calcul remplace ce dernier.

I-2 Erreur absolue

On appel erreur absolue x d’un nombre approché x̂

la valeur absolue de la
Différence entre le nombre exacte x et le nombre approché

 x  x  xˆ
L’écart relatif est le rapport :
xˆ  x
x  ou xˆ  x 1   x 
x
 Chapitre I: Calculs numériques approchés

I-3 Erreur relative

L’erreur relative x d’un nombre approché est la valeur absolue de l’écart relatif

xˆ  x  x
 x  x   si x 0
x x

L’erreur relative fournit une information plus pertinente sur la grandeur réelle
de l’erreur.
 Chapitre I: Calculs numériques approchés

I-4 Sources d’erreurs

Les quatre principales sources d’erreurs :

 erreurs de modélisation

 erreurs sur les données

 erreurs dues à la représentation des nombres sur ordinateurs

 erreurs de troncatures ou de discrétisation

 Chapitre I: Calculs numériques approchés

• les erreurs de modélisations proviennent de l’étape de mise d’un problème

sous forme mathématique (la mise en équation)

• pour réduire le degré de complexité d’un phénomène physique,

erreur de modélisation

• l’erreur de modélisation peut être contrôlée par un choix convenable du

modèle mathématique.
I-5 Erreurs sur les données

 elles sont liées à l’imprécision des mesures physiques

 elles peuvent être réduites en améliorant la précision des mesures

I-6 Représentation décimale approchée des nombres réelles

La notation la plus utilisée est la représentation en virgule flottante:

p
x m.b
où :
x: nombre réel
b: base de numération
m: la mantisse
p: exposant

Sur ordinateur les calculs sont généralement en base 2 et les résultats affichés en
base 10.
La mantisse m est écrite en virgule fixe possédant un nombre maximum N de
chiffre imposé par la mémoire de l’ordinateur:

N
m 0, a0a1.......... .....an  ak b  k , b  1 m  1
k 1

La précision relative d’un chiffre réel est donnée par:

x m b  N
   1 b1 N
x m b
Puisque l’exposant p est compris entre deux nombres entiers, L  p U
Alors, les nombres réels pouvant être représentés sur machine sont compris
Entre deux valeurs xmin et xmax:

L 1 U
xmin b  x b  xmax
 Exemple :

Considérant une notation binaire b=2 à virgule flottante qui utilise 1 bit pour le signe
m=23 bits pour la mantisse et 8 bits (signe inclus) pour l’exposant p.

xmax 2 2 2  1
U 7

Si un nombre réel quelconque xIR n’appartient pas au sous ensemble

IF(b,m,L,U)IR, des nombres réels qui peuvent être représentés et manipulés sur
ordinateur, l’approche typique est d’arrondir x de façon à ce que le nombre arrondi
Appartienne à IF.
Résolution d’équation à une variable
de type f (x)=0

Zéros de fonctions non- linéaires

 Chapitre II: Résolution d’équations à une variable

II-1 Principe

Les méthodes de résolution de f (x)=0 sont des méthodes itératives. Elles

consistent à construire une suite xn convergente, le plus rapidement possible,

vers x*.
 Chapitre II: Résolution d’équations à une variable

II-2 Rappels
 Cours d’analyse numérique

Chapitre II: Résolution d’équations à une variable

Objectif
y=f(x)
Résoudre l’équation :

f(x)=0

x
r1 r2 r3 r4

Points d’intersections de f(x)

Trouver les racines ri
avec l’axe des x
 Cours d’analyse numérique

Chapitre II: Résolution d’équations à une variable

Objectif
y=f(x)

1- Séparation des racines:

On cherche pour la (m+1)ième racine,

un intervalle [a,b] tq:
x
f(a).f(b)<0 r1 r2 r3 r4

a b
2- Méthodes de séparation des racines:
Si f(x) est continue sur [a,b] et N le nombre de racines de f(x)=0, alors:

f(a).f(b)>0 N est nul ou pair

f(a).f(b)<0 N est impair

3- Si f(x) est strictement monotone dans [a,b] alors l’existence d’une racine implique
son unicité.
 Cours d’analyse numérique

Chapitre II: Résolution d’équations à une variable

II-2 Récurrence
II-2-1 Formules de récurrence

Terme au Terme actuel

stade précèdent Récurrence simple xn
Xn-1

S1=a1
S2=a1+a2=S1+a2
Plusieurs termes Récurrence multiple Terme actuel
S3=a1+a2+a3précédents
=S2+a3 xn
….. xn-1,xn-2,…,xn-k
Sk=a1+a2+…+ak=Sk-1+ak
Suite de Fibonacci Suite de Chebychev
…
t0=1 T0(x)=1
Sn=a1+a2+…….+a n=Sn-1+an
t1=1 T1(x)=x
t2=2 T2(x)=2x2-1
t3=3 T3(x)=4x3-3x
t4=5 …..
Tk+1(x)=2xTk(x)-Tk-1(x)
t……..
k=t +t
k-1 k-2
 Cours d’analyse numérique

Chapitre II: Résolution d’équations à une variable

II-2-2 Principe d’itérations

Autre approximation plus

Approximation de
n- itérations Proche de la solution vraie
la solution vraie
(convergence pas toujours assurée)

Début Estimation initiale de la solution : x0

x1=F(x0)
x2=F(x1)
….
Converge X* solution du problème
xk=F(xk-1)
….
xn=F(xn-1)
Ne converge pas tout le temps.
Inconvénient
 Chapitre II: Résolution d’équations à une variable

Méthode I:
méthode des substitutions successives
(point fixe)
 Chapitre II: Résolution d’équations à une variable

II-3 Principe de la méthode des substitution successives ou méthode du point fixe

Le principe est de remplacer f (x)=0 par une équation équivalente x=F(x) et

Construire une suite récurrente définie par

 x0 fixé dans l' intervalle a, b


 xn1 F(x n )

Cette méthode est dite itérative.

 Cours d’analyse numérique

Chapitre II: Résolution d’équations à une variable

Méthodes de substitutions successives ou méthode du point fixe.

II-3-1 Principe

Ecrire f(x)=0 sous forme de x=F(x)

Avec F: nouvelle fonction de f.

Exemple :
f(x) =x2 + 3 ex – 12 = 0

x=F1(x)= x2 + 3 ex – 12 + x
Problème:
Non
x =F2(x)= 12- 3 ex unique

x= F3(x)=ln(12-x2)/3
 Cours d’analyse numérique

Chapitre II: Résolution d’équations à une variable

Méthodes de substitutions successives

II-3-2 Principe

Soit
x* : solution vérifiant f(x*)=0 donc x*=F(x*)
et x0 estimé de x*.

x0 x=F(x) x1=F(x0)
Substitution x2=F(x1)
x3=F(x2)
……
Problème
xn=F(xn-1)
Suite {x0,x1,x2,……,xn,…} converge-t-elle vers x*?
 Cours d’analyse numérique

Chapitre II: Résolution d’équations à une variable

Méthodes de substitutions successives

II-3-3 Théorème
Si F(x) de l’équation x=F(x) possède une dérivée qui vérifie :

| F’(x) |  m < 1  x  IR

Alors  x0  IR la suite

{x0,x1,x2,…..xn,....} générée par xi=F(xi-1)(i=1,2,3,….,n) converge vers x*

solution de x=F(x) donc f(x)=0

la racine x* est unique

Comportement de l’erreur d’estimation:

Si l’on note n=xn-x* l’erreur d’estimation de la nième itération, alors
lim n+1/n=F’(x*)
n
 Cours d’analyse numérique

Chapitre II: Résolution d’équations à une variable

Méthodes de substitutions successives

II-3-4 Ordre d’une méthode:

Comment savoir si la suite xn+1=f(xn) converge rapidement vers la racine x*?

C-à-d, comment diminue l’erreur d’une itération à la suivante.

Définition:
Une méthode de résolution de f(x)=0 est dite d’ordre p si:

lim n+1/(n)p=k=Cste k≠0

n

Exemple : la méthode des substitutions successives est du premier ordre (p=1)

 Cours d’analyse numérique

Chapitre II: Résolution d’équations à une variable

Exemple:
soit f(x) = 2 tg x – x – 1 = 0

- Réécrivez cette équation sous forme x=F(x)?

- Laquelle des écritures préfériez vous? Pourquoi ?

Solution
x=F1(x)=2tgx-1
x=F2(x)=arctg((x+1)/2)

Calculons la dérivée
1 1
F2' ( x) 
F’1(x)=2/cos2(x) 2
1
x  1
2

Il est clair que F’1(x) >1 et F’2(x)<1 donc on choisit F’2(x)

Chapitre II: Résolution d’équations à une variable

Méthode II
méthode de Dichotomie
(bissection)
 Cours d’analyse numérique

Chapitre II: Résolution d’équations à une variable

II-4 Méthode de dichotomie (Dichotomie de Bolzano)

L’estimé xk de la kième itération est évalué par:

xk=(xd+xg)/2
 Cours d’analyse numérique

Chapitre II: Résolution d’équations à une variable

II-4-1 Exemples

Soit la suite définit par le terme ordre n+1:

Xn+1=(xn+a/xn)/2

Sachant que le calcul s’arrête quand xk+1-xk<

1- Trouvez le terme de convergence (solution)

2- Que représente le terme de convergence?
Chapitre II: Résolution d’équations à une variable

Méthode III:
méthode Regula - Falsi
 Cours d’analyse numérique

Chapitre II: Résolution d’équations à une variable

II-5 Méthode d’interpolation régulière Regula- Falsi

Domaine borné [xg, xd] où x* [xg, xd]

y=f(x) La corde coupe x l’axe en x1 et définit
deux triangle semblables:

yd (x1-xg/0-yg)=(xd-x1/yd-0) d’où

x1=(ydxg/yd-yg)-(ygxd/(yd-yg)  première
estimée
Alors on continu à calculer les estimés
x1,x2,… à quel interval appartient x*?
xg x x [xg,x1] ou [x1,xd] ?
1 2 x
x* xd
yg
 Cours d’analyse numérique

Chapitre II: Résolution d’équations à une variable

Méthode d’interpolation régulière Regula- Falsi

On définit P=yd.y1 P<0 la racine est dans [x1,xd]

Soit

P=f(xd).f(x1) P>0 la racine est dans [x g,x1]

On procède par itération

Si P<0 xg=x1
Réitérer | xg - xd | <
yg=y1

Si P>0 xd=x1
yd=y1
Chapitre II: Résolution d’équations à une variable

Méthode III
méthode de Newton Raphson
 Cours d’analyse numérique

Chapitre II: Résolution d’équations à une variable

II-6 Méthode de Newton- Raphson

Soit la fonction f(x) continue et continuellement
f(x) dérivable au voisinage de x*.

f(x) Tracer la tangente à chaque

point (xn,f(xn))

On développement
Le considère ainsi en quesérie
le meilleur
de Taylor
au voisinage
estimé est: de x* autour de xn:
xn+1=xn+n
x f(x*)=f(x n)+f’(xn
On obtient )(x*-xl’algorithme
ainsi n)+(x*-xn) /2!f’’(x
2
de n)
Newton- Raphson:
+…..
x2 x1 x0
Sachantxn+1 =xnf(x*)=0:
que -f(xn)/f’(xn)
f(xn)+f’(xn)(x*-xn)=0

(n=0,1,2….n
L’approximation max)
de l’erreur 
n= - f(xn)/f’(xn)
 Cours d’analyse numérique

Chapitre II: Résolution d’équations à une variable

Méthode de Newton- Raphson

II-6-1 Convergence

Théorème

Soit (a,b) un intervalle telle que:

f (a) . f (b) < 0

 x[a,b] f ’(x) ≠ 0

 x[a,b] f ’’(x) ≠ 0

Alors f (x)=0 possède une seule racine dans [a,b] et  x0 [a,b] alors:

la suite xn+1= xn- f (xn) / f ’(xn) converge quadratiquement

 Cours d’analyse numérique

Chapitre II: Résolution d’équations à une variable

Méthode de Newton- Raphson

Convergence

Pour assurer la convergence on choisira un x0 telle que la condition de Fourier

Soit vérifier:

f ’’(x0) . f (x0) > 0

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

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

III-1 Rappel sur les matrices

III-1-1 Définition

Une matrice est un tableau rectangulaire d’éléments, généralement

des nombres ou des fonctions. Ces grandeurs sont généralement des
réelles ou des complexes.

III-1-2 Notation

Une matrice A de dimension m*n est notée A  IR m*n.

Cette matrice est une matrice de m lignes et n colonnes.

a11 a12 ……..a1n

a21 a22 ……..a2n
A=[aij]= . .
. aij. .
.
am1 am2……….amn
 Cours d’analyse numérique

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

Une matrice V qui ne comporte q’une seule colonne, V IRm*1 est

Vecteur colonne
v1
v2
.
V= .
.
vm
 Cours d’analyse numérique

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

 Addition

Soient AIR m*n et B  IRm*n , l’addition de ces deux matrices est donnée :

C = [cij] = [aij+bij]
Note: A et B de même dimension, ainsi que C
Il en va de même pour la soustraction
 Cours d’analyse numérique

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

 Produit

Étant donné AIR m*n une matrice, es b un scalaire, alors les éléments de la matrice
C est donnée par

cij = b aik

La matrice C=bA est de même dimension que A, C  IR m*n

 Cours d’analyse numérique

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

III-1-3 Multiplication matricielle

Règle

La multiplication entre deux matrices n’est définie que lorsque leurs dimensions
son compatibles: le nombre de colonne de la matrice gauche de l’opérateur doit
correspondre au nombre de lignes de la matrice à droite de l’opérateur.

Si A  IR m*n, et si B  IR n*p , la multiplication entre les matrices A et B donne une

Matrice C de dimension m*p:

n
cij  aik bkj
k 1
 Cours d’analyse numérique

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

III-1-4 Opérateur de transposition

La transposée d’une matrice A est la matrice AT (notée aussi A’)

Définie par A  IR m*n, AT  IR n*m

A=[aij]m*n , AT=[aji]n*m
 Cours d’analyse numérique

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

Propriétés

(AT)T=A

(A+B)T=AT+BT

(AB)T=BTAT
 Cours d’analyse numérique

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

III-2 Matrices particulières

III-2-1 Matrice nulle

Une matrice dont tous les termes son nuls.

Notée A=0, aij=0,  i,  j

 Cours d’analyse numérique

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

III-2-2 Matrice diagonale

Une matrice diagonale A  IR n*n est une matrice carrée dont tous les
éléments non diagonaux sont nuls: aij=0,  i ≠ j

a11 0 0 ………..0
0 a22 0 …..…...0
.
A=[aij]= . aij 0
.
0 0 ……………ann
 Cours d’analyse numérique

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

III-2-3 Matrice identité

Une matrice identité est une matrice diagonale A  IR n*n (carrée) dont tous les
éléments diagonaux qui sont unitaires et les éléments non diagonaux nuls:

aij=0,  i ≠ j

A=I

aii=1 , i=1,2,..n
 Cours d’analyse numérique

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

III-2-4 Matrice triangulaire

Une matrice triangulaire supérieure (respectivement inférieurs) est une matrice carrée
A  IR n*n dont les éléments qui se trouvent au-dessous (respectivement au-dessus)
de la diagonale principale sont nuls:

aij=0,  i > j ( i < j )

a11 0 ……...0
a11 a12 ………..a1n a21 a22 ….....0
0 a22 …..…...a2n .
. (respectivement A=[a ]= .
ij
A=[aij]= . a in . 0
. an1 an2 ………ann
0 0 ……… 0 ann
 Cours d’analyse numérique

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

III-2-5 Matrice symétrique et antisymétrique

A  IR n*n une matrice carrée

Si A=AT , alors A est dite matrice symétrique

Si AT=-A , alors A est dite matrice antisymétrique

 Cours d’analyse numérique

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

Propriétés

A.0 =0.A =0

A+0 =0+A =A

A.I =I.A =A
 Cours d’analyse numérique

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

III-3 Déterminant d’une matrice

On appel déterminant d’une matrice A carrée, A  IR n*n le nombre notée det(A)

ou |A|:

n
det( A)  ( 1) i 1 ai1 det( Ai ) Où Ai est la matrice obtenue
i 1 en rayant la 1ére colonne et
la i-ème ligne.
 Cours d’analyse numérique

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

III-3-1 Propriétés des déterminants

det(AB)=det(A).det(B)

det(A-1)=1/det(A)
 D E
det(A)= det(  F G  ) =det(G)det(D-EG F)=det(D)det(G-FD-1E)
-1

 
 D E IRn*n , D  IRm*m et les matrices E,F et G sont en
Où A  
 F G  accord avec celle de A et D, D-1 doit exister.
 Cours d’analyse numérique

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

III-3-2 Théorèmes:

1. Si tous les éléments d’une ligne (colonne) d’une matrice A  IR n*n sont nuls
alors det(A)=0

2. Si tous les éléments d’une ligne (colonne) du déterminant d’une matrice A  IR n*n
Sont multiplier par un scalaire k, alors le déterminant est multiplier par k.

3. Si B est obtenue à partir de A  IR n*n en échangeant deux de ces lignes (colonnes)

Alors det(B)=-det(A).

4. Si B est obtenu à partir de A  IR n*n en faisant passer la ième ligne (colonne)par

dessus p lignes (colonnes), alors det(B)=(-1)pdet(A)

5. Si deux lignes (colonnes) de A  IR n*n sont identiques, alors det(A)=0

6. Si, aux éléments d’une ligne (colonne) on ajoute k fois les éléments correspondants

D’une autre ligne (colonne), la valeur du déterminant reste inchangée.

 Cours d’analyse numérique

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

III-4 Mineurs et cofacteurs

Les mineurs mij des éléments aij d’une matrice A carrée, A  IR n*n , sont les
déterminants de la partie restante de A lorsqu’on ne tient pas compte de la
Ligne i et la colonne j.

III-4-1
III-4-2 Mineurs
Les cofacteurs
directeurs (leading minors)

m1=a
Les cofacteurs cij11(∆ij) des éléments aij d’une matrice carrée A, A  IR n*n, sont donnés :
  a11 a12   mn=det(A)
m2 det   

  a21 a22  
cij=(-1)i+jmij
  a11 ..  
m3 det    
  .. a33  
……
 Cours d’analyse numérique

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

III-4-3 Matrice adjointe

La matrice des cofacteurs cij des éléments aij de la matrice A, A  IR n*n , lorsqu’elle
est transposée, est appelée la matrice adjointe de A.
T
 c11 .......... .c1n 
 Propriétés . 
 
~ . 
T
A adj ( A)  cij  
. c

 ij 
Ã.A=A.Ã=|A|.I . où  |A| = det(A)
adj(AB) = adj(A).adj(B)
 
 cn1 .......... .cnn 

adj(A)=CT, avec C=[cij]

 Cours d’analyse numérique

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

III-5 Matrice inverse

La matrice inverse A-1 d’une matrice A carrée, A  IR n*n , est donnée par:

adj ( A)
1
A 
det( A)
Pour qu’une matrice soit inversible, il faut que son déterminant soit ≠ 0

On dit alors que la matrice est régulière ou non singulière.

 Cours d’analyse numérique

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

Matrice inverse
Exemple 1 2 1
- Calculez la matrice inverse A-1de A 2 1 1
1 3 2

- Calculez le produit A-1.A, Que remarquez-vous?

 Cours d’analyse numérique

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

Matrice inverse
Solution
1- Calcul du déterminant

det(A)=a12c12+a22c22+a32c32

 a12 a23   a11 a13   a11 a13 

 a12    a22    a32  
a a
 31 33  a a
 31 33  a a
 21 23 

Remarque: en choisissant judicieusement la ligne (colonne) par laquelle on effectue le développement, on peut très largement
Simplifier les calculs (ex. ligne (colonne) comportant des zéros)).
 Cours d’analyse numérique

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

Matrice inverse
Solution
1- Calcul du déterminant
det(A)=a12c12+a22c22+a32c32

 a21 a23   a11 a13   a11 a13 

 a12    a22    a32  
a a
 31 33  a a
 31 33  a a
 21 23 

2 1 1 1 1 1
 2   1    3   2
1 2 1 2 2 1

Remarque: en choisissant judicieusement la ligne (colonne) par laquelle on effectue le développement, on peut très largement
Simplifier les calculs (ex. ligne (colonne) comportant des zéros)).
 Cours d’analyse numérique

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

Matrice inverse
Solution
2- Calcul de la matrice des cofacteurs

C [cij ]  1 mij

i j

-1 -3 5
 1 -3 5 ~
Matrice A C T  - 1 1 - 1
-1 1 1 adjointe Ã
5 -1 -3
1 1 -3
 Cours d’analyse numérique

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

Matrice inverse
Solution
3- Calcul de la matrice inverse
1 1 1
-
2 2 2
~
A 3 1 1
A 1   - -
det( A) 2 2 2
5 1 3

2 2 2
 Cours d’analyse numérique

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

Matrice inverse
Solution
4- Calcul du produit

1 0 0
1
A . A  0 1 0 I
0 0 1
 Cours d’analyse numérique

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

III-5-1 Propriétés de la matrice inverse

•(A-1)-1=A
•(A-1)T=(AT)-1
•(AB)-1=B-1.A-1 (par extension (ABC)-1=C-1.B-1.A-1,
si C est inversible)

•det(A-1)=1/det(A)
•A(In+A)-1=(In+A)-1A si (In+A)-1 existe
•A(In+A)-1+(In+A)-1A=In si (In+A)-1 existe
•A(In+BA)-1=(Im+AB)-1A si AIR m*n,BIR n*m,et si (In+BA)-1
existe

•A(In+AB)-1+A(In+BA)-1B=Im si AIR m*n,BIR n*m,et si (In+BA)-1

existe
 Cours d’analyse numérique

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

III-6 Matrice augmentée

Considérant le système linéaire suivant:

Sa matrice augmentée est la matrice de taille m*(n+1)

a11 a12 a13 ….a1n x1 b1
a21 a22 a23 ….a2n x2 b2
. . 11 .12 a13 …...a1n b1
a a
. . a21= a22 a23 …...a2n b

A, b 
………………….. . 2
. . . . .
. . …………………....
. .
am1 am2 am3 ….amn xn. bm .
. .
am1 am2 am3 ….amn bm.
 Cours d’analyse numérique

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

III-7 Indépendance linéaire des vecteurs

Soit un ensemble a1,a2,…..an de vecteurs de dimension m, et n un ensemble

de scalaire:
Soit A une matrice, AIRn m*n :

Le vecteur définit par c   i ai forme une combinaison linéaire noté {a i}
- Les colonnes de A soni linéairement
1 indépendantes si et seulement si ATA est
une matrice non singulière de rang plein

L’ensemble {ai} est

- Les lignes de Alinéairement indépendant
son linéairement si :
indépendantes si et seulement si ATA est
non singulière
c=0  1=2=….=n=0

Une matrice carrée AIR n*n , est dite non singulière (ou inversible) si  B IR n*n tq:
A.B=B.A=I  det (A) ≠0
 Cours d’analyse numérique

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

III-8
III-9 Rang
Trace d’une
d’une matrice
matrice

Le rang d’une matrice correspond au nombre maximum de colonnes ou de lignes

La trace d’uneindépendantes.
Linéairement matrice A, AIR
C’est est
n*n ,
égale
aussi à ladu
l’ordre somme des éléments
plus grand de lanon nul.
déterminant
diagonale de cette matrice:
Une matrice A, AIR n*n est dite de rang plein si: rang(A)=min(m, n).
 Propriétés: trace(A)=(aii)
rang(A)=rang(AT)=rang(AAT)=rang(ATA)
 Cours d’analyse numérique

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

III-10 Norme d’une matrice

On appel p-norme d’une matrice A, AIR n*n , la norme:

1
 m n p
p
A p    aij 
 i 1 j 1 

La norme matricielle (équivalente à la norme Euclidienne chez les vecteurs), on

L’appelle la norme de Frobenius:

A  A E  trace( AT A)
 Cours d’analyse numérique

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

III-11 Valeurs et vecteurs propres

Soit A une matrice, AIR n*n, les valeurs propres i de cette matrice, sont les
racines de l’équation polynomiale:

det(A-iI)=0
L’ensemble des i de cette matrice constituent son spectre.

Les vecteurs propres Vi de cette matrice se déduisent :

AVi=iVi
det(A-iI)=0 est appelé polynôme caractéristique de A
iI-A est appelé matrice caractéristique de A
Deux matrices sont semblables si elles ont le même polynôme caractéristique
 Cours d’analyse numérique

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

Méthodes directes de résolution

des
systèmes linéaires
 Cours d’analyse numérique

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

En analyse numérique, résoudre un système linéaires, c’est résoudre

Ax = b
Où A est une matrice (à priori) inversible , b est un vecteur, et X est le vecteur
inconnu.

Les questions attenantes à ce problème sont :

Calculer A-1, Det(A), valeurs propres de A, vecteurs propres de A

Une dizaine de méthodes existent, mais certains outils sont commun à
de nombreuses méthodes… (Pivot de Gauss, Décomposition en matrice
triangulaire,Méthode de substitution )
 Cours d’analyse numérique

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

Exercice

Calculer det(Ai) pour les cas suivants:

2 1 -1 3
1 2 3
1 2 0 1 2 1
A1  A2  2 1 - 1 A3 
1 1 3 3 2 0
0 2 4
1 1 2 3

- Quel est le nombre d’opérations arithmétiques effectuées pour chaque cas?

- Lorsque la matrice est de dimension n*n, quel est le nombre maximum

d’opérations à effectuer?

-Donnez la formule de récurrence?

 Cours d’analyse numérique

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

Solution 2 1 -1 3
1 2 3
1 2 0 1 2 1
det(AA1 
1)=(1.1-2.1)=-1 A2  2 1 - 1 A3 
1 1
det(A2)=[Link](2)-[Link](2)+ 3 3 2 0
[Link](2)=1.(1.4+1.2)-2.(2.4+1.0)+3.(2.2-1.0)=10
0 2 4
1 1 2 3
det(A3)=[Link](3)-[Link](3)-[Link](3)-[Link](3)=2.[[Link](2)-[Link](2)+[Link](2)]-1.[
[Link](2)-2det(2)+1det2)]-1.[[Link](2)-[Link](2)+[Link](2)]-3.[[Link](2)-[Link](2)+[Link](2)]=
Si Nk est le nombre totale d’opérations à effectuer pour calculer un det d’ordre k:

NExemple:
1=0
NPour
2=3
calculer un déterminant d’ordre 50 il faudra effectuer:
N10 64
opérations
3=3.N2+5
Si l’on considère
……..
Nombre qu’unpour
d’opérations ordinateur effectue
le calcul chaque opération en 1 microseconde
d’un déterminant
NIlKfaudrait donc: (formule de récurrence)
=kNK-1+2.K-1

1050 ansAinsi le calcul

!! pour d’unledéterminant
N=2calculer
N=4
N=3 2 déterminantd’ordre
4 déterminants
3 multiplications d’ordren50.
d’ordre 2
requiert:
-Le calcul de n déterminants d’ordre (n-1)
41 multiplications
3 addition (soustraction)
- n multiplications
3 additions (soustractions)
- n additions2(soustractions)
 Cours d’analyse numérique

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

a11x1+a12x2+…..+a1nxn=b1 a11 a12 a13 ….a1n x1 b1

a21x1+a22x2+…..+a2nxn=b2 a21 a22 a23 ….a2n x2 b2
a31x1+a32x2+…..+a3nxn=b3 Forme . . .
matricielle
………………….. . =
. . .
……………………… . . .
. . . .
an1x1+an2x2+…..+annxn=bn an1 an2 an3 ….ann xn bn
n
noté Ax=b ou a x
j 1
ij j bi (i=1,2,…..n)

n équations
n inconnues

Pour résoudre des systèmes linéaires :

- Méthodes directes
- Méthodes itératives
 Cours d’analyse numérique

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

Étude
Étudedes
dessolutions
solutions

Si det(A)≠0 (A régulière) solution unique

Exemple: x+y=3
x+2y=5

Si det(A)=0 (A singulière) système dégénéré (impossible ou indéterminé)

Exemple: 2x+3y=4 2x+3y=4

4x+6y=5 4x+6y=8

(0,8/6),(2,0),(1/2,1),(3/2,1/3)…..
 Cours d’analyse numérique

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

Systèmes linéaires à matrices particulières

Systèmes linéaires à matrice triangulaire inférieur

Ax=b où A: matrice triangulaire inférieur

La solution est donnée par :

i i 1
bi  aij x j  aij x j  aii xi i 1, n
j 1 j 1
 Cours d’analyse numérique

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

Systèmes linéaires à matrices particulières

Donc, si l’on connaît les (i-1) premiers éléments de x, le ième s’écrit:

1  i 1 
xi 
aii
 bi   aij x j  i 1, n
 j 1 
 Cours d’analyse numérique

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

Systèmes linéaires à matrices particulières

Systèmes linéaires à matrice triangulaire supérieure

Ax=b où A: matrice triangulaire supérieure

La solution est donnée par :

n n
bi  aij x j   aij x j  aii xi i 1, n
j i j i 1
 Cours d’analyse numérique

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

Systèmes linéaires à matrices particulières

Donc, si l’on connaît les (i-1) premiers éléments de x, le ième s’écrit:

1  n 
xi 
aii
 bi   aij x j  i n, n  1,....1
 j i 1 
 Cours d’analyse numérique

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

Résolution
Résolutionpar
parlalarègle
règlede
deCramer:
Cramer: Ax=b
La méthode la plus connue de résolution des systèmes linéaires. Néanmoins, c’est
la moins recommandable !

det k A
xk  avec
det( A) x=A-1.b
a11 ......a1,k  1 b1 a1,k 1........a1n
a21......a2,k  1 b 2 a2,k 1........a2 n
La méthode
det ( A) 
consiste de Cramer Aest
-1 impraticable en temps de calcul en plus de l’accumulation
k
Elle à calculer .......lui post-multiplier le vecteur b.
, puis
de l’erreur d’arrondi.
an1......an ,k  1 b n an ,k 1........ann
Exemple: pour un système n=50, le nombre d’opération =7.1067
 Cours d’analyse numérique

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

Méthode
Méthodede
deGauss
Gauss

Question:
Comment résoudre le système Ax=b ?

Réponse :

Transformer le système Ax=B en A’x=b’ où A’ est une

matrice triangulaire supérieure

 Cours d’analyse numérique

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

Méthode
Méthodede
deGauss
Gauss

On transforme donc [A, b] en une matrice triangulaire supérieur (U) :

a21(1)=a31(1)=…..an1(1)=0
Étape 1
1. Pré multpliez [A,b] par E21(-a21/a11) (a11 est le pivot)
(annuler les termes sub- diagonaux de la première colonne)

Les termes de la deuxième ligne deviennent

a21(1) = a21 - (a21 / a11). a11 = 0

a22(1) =a22 - (a21 /a11). a12
……..
a2,n+1(1) = a2,n+1- (a21 /a11) . a1,n+1 (n+1: colonne du vecteur b)
Ou plus généralement :
a2j(1) = a2j - (a21 /a11). a1j (j=2,…..,n+1)
 Cours d’analyse numérique

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

Méthode
Méthodede
deGauss
Gauss

Le système ainsi résultant, après cette première étape, s’écrit

a11 a12 a13 …. a1n x1 a1,n+1

0 a22(1) a23(1) …. a2n(1) x2 a2,n+1(1)
. . .
………………….. . =
. .
. . .
. . .
0 an2(1) an3(1) …. ann(1) xn an,n+1(1)
 Cours d’analyse numérique

Chap2. Systèmes linéaires

Méthode
Méthodede
deGauss
Gauss
Étape 2 • Pré multipliez [A,b] par E32(-a32(1)/a22(1)) (a22(1) est le pivot)
(annuler les termes sub- diagonaux de la deuxième colonne)

Les termes de la troisième ligne deviennent

a32(2) = a32(1) - (a32(1) / a22(1)). a22(1) = 0

a33(2) = a32 (1)- (a32 (1)/ a22(1)). a23(1)
……..
a3,n+1(2) = a3,n+1(1)- (a32(1) /a22(1)) . a2,n+1(1)

Ou plus généralement :
a3j(2) = a3j(1) - (a32(1) /a22(1)). A2j(1) (j=3,…..,n+1)
 Cours d’analyse numérique

Chap2. Systèmes linéaires

Méthode
Méthodede
deGauss
Gauss

Le système ainsi résultant, après cette deuxième étape, s’écrit

a11 a12 a13 …. a1n x1 a1,n+1

0 a22(1) a23(1) …. a2n(1) x2 a2,n+1(1)
0 0 a33(2) ….…a3n(2) . a3,n+1(2)
. = .
.
. .
. . .
0 0 an3(2)….. ann(2) xn an,n+1(2)
 Cours d’analyse numérique

Chap2. Systèmes linéaires

Méthode
Méthodede
deGauss
Gauss

Etape k:
On annule les termes sous- diagonaux de la kième colonne :

ak+1,k(k)=ak+2(k)=…….=an,k(k)=0

Prémultipliez [A,b](k-1) par Ek+1k(-ak+1,k(k-1)/akk(k-1))

Ainsi la kième ligne de [A,b](k-1) :

ak+1,k(k) = ak+1,k(k-1) - (ak+1,k(k-1)/ak,k(k-1)).ak,k(k-1) =0

ak+1,k+1(k) = ak+1,k(k-1) - (ak+1,k(k-1)/ak,k(k-1)).ak,k+1(k-1) =0
……………………
ak+1,n+1(k) = ak+1,n+1(k-1) - (ak+1,k(k-1)/ak,k(k-1)).ak,n+1(k-1) =0
 Cours d’analyse numérique

Chap2. Systèmes linéaires

Méthode
Méthodede
deGauss
Gauss

• Pré multipliez [A,b] par (-a31/a11)

Les termes de la troisième ligne deviennent

a31(1) = a31 - (a31 / a11). a11 = 0

a32(1) =a32 - (a31 /a11). a12
……..
a3,n+1(1) = a3,n+1- (a31 /a11) . a1,n+1

Ou plus généralement :
a3j(1) = a3j - (a31 /a11). a1j (j=2,…..,n+1)
 Cours d’analyse numérique

Chap2. Systèmes linéaires

Méthode
Méthodede
deGauss
Gauss
• Pour annuler les termes ai1

ai1(1) = ai1 - (ai1 / a11). a11 = 0

ai2(1) =ai2 - (ai1 /a11). a12
……..
ai,n+1(1) = ai,n+1- (ai1 /a11) . a1,n+1

D’où la forme générale:

aij(1) = aij - (aij /a11). a1j (i=2,…..,n+1)

(j=2,…..,n+1)
 Cours d’analyse numérique

Chap2. Systèmes linéaires

Méthode
Méthodede
deGauss
Gauss

Exemple:
2x+y-4z=8 Notation : 2 1 -4 8
3x+3y-5z=14 A= 3 3 -5 14
4x+5y-2z=16 4 5 -2 16

1er pivot 2
2ème ligne – 1ére ligne * 3/2 2 1 -4 8
0 3/2 1 2
3ème ligne – 1ère ligne*4/2 4
0 5
3 -2
6 16
0

2ème pivot: 3/2

2 1 -4 8
3ème ligne-2ème ligne*3/(3/2) 0 3/2 1 2
04 05 4-2 16
-4
 Cours d’analyse numérique

Chap2. Systèmes linéaires

Méthode
Méthodede
deGauss
Gauss Notation : 2 1 -4 8
A= 3 3 -5 14
4 5 -2 16

1er pivot 2
2ème ligne – 1ére ligne * 3/2 2 1 -4 8
0 3/2 1 2
3ème ligne – 1ère ligne*4/2 4 5
0 3 -2
6 16
0

2ème pivot: 3/2

2 1 -4 8
3ème ligne-2ème ligne*3/(3/2) 0 3/2 1 2
04 05 4-2 16
-4

3ème pivot 4
D’où : 4z=-4 z=-1 Question
3/2y-1=2 y=2 Calculez le det des matrices intermédiaires
2x+2+4=8 x=1 Qu’est ce que vous remarquez?
 Cours d’analyse numérique

Chap2. Systèmes linéaires

Méthode
Méthodede
deGauss
Gauss

Nombre d’opérations:
Pour passer de [A,b](k-1) à [A,b](k), il faut:

(n-k).(n-k+1) multiplications : nm
(n-k).(n-k+1) additions : na
(n-k) divisions : nd

1- Donc pour passer de [A,b] à [A,b](n-1) le nombre d’opérations sera:

n 1
n(n 2  1)
nm na  (n  k ).(n  k  1) 
k 1 3
n 1
n(n  1)
nd  (n  k ) 
k 1 2
 Cours d’analyse numérique

Chap2. Systèmes linéaires

Méthode
Méthodede
deGauss
Gauss

2- Pour résoudre le système triangularisé, on doit effectuer :

n(n  1)
n 1
nm na  (n  k ) 
k 1 2
nd n
 Cours d’analyse numérique

Chap2. Systèmes linéaires

Méthode
Méthodede
deGauss
Gauss

Donc, la résolution d’un système linéaire par l’algorithme de Gauss demande :

n(n  1)(2n  5)
nm 
6
na nm
n(n  1)
nd 
2
 Cours d’analyse numérique

Chap2. Systèmes linéaires

Méthode
Méthodede
deGauss
Gaussavec
avecpivot
pivot

Remarque

Jusqu’ici nous avons supposé qu’à chaque étape de la méthode

d’élimination de Gauss, le pivot a(k)k,k ≠ 0, l’inconvénient est que cette condition
n’est pas assurée pour une matrice inversible quelconque.
D’autre part, même lorsque cette condition est satisfaite, le pivot peut prendre des
valeurs |a(k)k,k| proches de 0, ce qui conduit à des instabilités numériques. C’est
pourquoi en général, nous avons recours à une étape supplémentaire de permutation
de lignes pour remplacer un pivot éventuellement nul par un autre pivot qui lui sera
non nul à coup sûr. Cette étape permet également de stabiliser l’algorithme
par rapport aux erreurs d’arrondi.
 Cours d’analyse numérique

Chap2. Systèmes linéaires

Méthode
Méthodede
deJordan
Jordan(Gauss-
(Gauss-Jordan)
Jordan)

Consiste à transformer le système Cramérien :

Ax=b
en un système :

A’x=b’

Où A’ est la matrice identité d’ordre n.

 Cours d’analyse numérique

Chap2. Systèmes linéaires

Méthode
Méthodede
deJordan
Jordan(Gauss-
(Gauss-Jordan)
Jordan)

A la kième étape, on combine toutes les lignes (sauf la ligne k) avec la ligne k
(au lieu de ne le faire que pour les lignes d’indice supérieur à k).

On fait ainsi apparaître des 0 sur toutes la colonne sauf au niveau du pivot akk(k).
 Cours d’analyse numérique

Chap2. Systèmes linéaires

Méthode
Méthodede
deJordan
Jordan(Gauss-
(Gauss-Jordan)
Jordan)
Soit le système de Cramer :

a11 a12 a13 ….a1n x1 a1,n+1

a21 a22 a23 ….a2n x2 a2,n+1
. . .
………………….. . =
. .
. . .
. . .
an1 an2 an3 ….ann xn an,,n+1

Etape 1: a) Normalisation
Remplacer a11 (pivot) par 1 résultant de la multiplication de la première ligne de [A,b]
par E1(1/a11), d’où:

a(1)1j=a1j/a11 (j=1,2,….,n+1)
 Cours d’analyse numérique

Chap2. Systèmes linéaires

Méthode
Méthodede
deJordan
Jordan(Gauss-
(Gauss-Jordan)
Jordan)
b) Réduction
Les coefficients extra diagonaux de A son remplacés par :

a(1)21=a(1)31=……..=a(1)n1=0

Ceci s’obtient par la multiplication avec :

E21(-a21).E31(-a31)…..En1(-an1)

Soit :

a(1)1j = aij- ai1 . a(1)1j

(i=2,3,….,n)

(J=1,2,….n+1)
 Cours d’analyse numérique

Chap2. Systèmes linéaires

Méthode
Méthodede
deJordan
Jordan(Gauss-
(Gauss-Jordan)
Jordan)

d’où le système:

1 a12(1) a13(1) ….a1n(1) x1 a1,n+1(1)

0 a22(1) a23(1) ….a2n(1) x2 a2,n+1(1)
. . .
………………….. . =
. .
. . .
. . .
0 an2 an3 ….ann
(1) (1) (1)
xn an,,n+1(1)

Etape 2 : a) Normalisation

Remplacer le pivot (a22(1)) par 1, en multipliant E2(1/a22(1)). La deuxième ligne devient :

a2j(2)=a2j(1)/a22(1) (j=2,……,n+1)
 Cours d’analyse numérique

Chap2. Systèmes linéaires

Méthode
Méthodede
deJordan
Jordan(Gauss-
(Gauss-Jordan)
Jordan)

b) Réduction

Annuler les termes extra diagonaux de [A,b](1) en le multipliant E12(-a12(1)). D’où

La première rangée:

a12(2) = a12(1) - a12(1) = 0

a13(2) =a13(1) – a12(1) . a23(2)
……..
a1,n+1(2) = a1,n+1(1)- a12(1) . a2,n+1(2)

Soit en général:
a1j(2)=a1j(1)-a12(1).a2j(2) (j=3,….,n+1)
 Cours d’analyse numérique

Chap2. Systèmes linéaires

Méthode
Méthodede
deJordan
Jordan(Gauss-
(Gauss-Jordan)
Jordan)

b) Réduction

Annuler les termes extra diagonaux de [A,b](1) en le multipliant Ei2(-ai2(1)). D’où

Les termes de la ième rangée:

ai2(2) = ai2(1) - ai2(1) = 0

ai3(2) =ai3(1) – ai2(1) . a23(2)
……..
ai,n+1(2) = ai,n+1(1)- ai2(1) . a2,n+1(2)

Soit en général:
aij(2)=aij(1)-ai2(1).a2j(2) (i≠2)
(j=3,….,n+1)
 Cours d’analyse numérique

Chap2. Systèmes linéaires

Méthode
Méthodede
deJordan
Jordan(Gauss-
(Gauss-Jordan)
Jordan)

Nous avons donc le système suivant :

1 0 a13(2) ….a1n(2) x1 a1,n+1(2)

0 1 a23(2) ….a2n(2) x2 a2,n+1(2)
0 0 . .
………………….. . =
. .
. . .
. . .
0 0 an3 ….ann
(2) (2)
xn an,,n+1(2)
 Cours d’analyse numérique

Chap2. Systèmes linéaires

Méthode
Méthodede
deJordan
Jordan(Gauss-
(Gauss-Jordan)
Jordan)

Kième étape:

Normalisation :
Le terme pivot akk(k-1) est remplacé par 1, en multipliant [A,b](k-1) par Ek(1/akk(k-1))

La kième ligne devient ainsi:

akj(k-1)=akj(k-1)/akk(k-1) j=k,…..,n+1

Réduction
Les termes extradiagonaux de la kième colonne sont annulés en multipliant
[A,b](k-1) par Eik(-aik(k-1)) d’où:
j=k+1,…,n+1
i≠k
aij(k)=aij(k-1)-aik(k-1)*akj(k) i=1,2,….,n
 Cours d’analyse numérique

Chap2. Systèmes linéaires

Méthode
Méthodede
deJordan
Jordan(Gauss-
(Gauss-Jordan)
Jordan)

Nombre d’opérations :

Pour passer de [A,b](k-1) à [A,b]k nous avons besoin de :

na=nm=(n-1)(n-k-1)
nd=(n-k-1)

Donc pour passer de [A,b] à [A,b]n nous avons besoin de :

n
na nm  (n  1)(n  k  1) n(n 2  1) / 2
k 1
n
nd  (n  k  1) n(n  1) / 2
k 1
 Cours d’analyse numérique

Chap2. Systèmes linéaires

Exemple :
Soit le système linéaire suivant:

2 1 -4 8 
A  3 3 - 5  B 14
 4 5 - 2  16

Trouvez les racines de ce système par la méthode de Gauss- Jordan

 Cours d’analyse numérique

Chap2. Systèmes linéaires

Solution : Ligne 1/2

1 1/2 - 2 4 
A(1)  0 3/2 1 2  Ligne 2-3*ligne 1
 0 3 6 0  Ligne 3-4*ligne1

1 0 - 7/3 10/3 Ligne 1-1/2*ligne2

A( 2 )  0 1 2/3 4/3  Ligne 2/(3/2)
 0 0 4 - 4  Ligne 3-3*ligne2

1 0 0 1  Ligne 1+7/3*ligne3
A( 3)  0 1 0 2  Ligne 2-2/3*ligne3 Ligne 3/4
 0 0 1 - 1

On a directement les racines dans la 4e colonne

 Cours d’analyse numérique

Chap2. Systèmes linéaires

Calcul de la matrice inverse A-1

L’algorithme de Jordan opère le passage de la matrice C=[A,b] à la matrice [I,x]

X est la solution du système linéaire Ax=b d’où x=A-1b

Donc l’algorithme de Jordan fait la transformation:

C=[A,b]  D=[I,A-1b]
 Cours d’analyse numérique

Chap2. Systèmes linéaires

Exemple :
Calculez l’inverse de la matrice A:

1 3 3
A  2 2 0 
 3 2 6 
 Cours d’analyse numérique

Chap2. Systèmes linéaires

Solution:
1 3 3 1 0 0 1 3 3 1 0 0
N :  2 2 0 0 1 0  R :  0 - 4 - 6 - 2 1 0 
 3 2 6 0 0 1   0 - 7 - 3 - 3 0 1 

1 3 3 1 0 0 1 0 - 3/2 - 1/2 3/4 0

N :  0 1 3/2 1/2 - 1/4 0  R :  0 1 3/2 1/2 - 1/4 0 
 0 - 7 - 3 - 3 0 1   0 0 15/2 1/2 - 7/4 0 

1 0 - 3/2 - 1/2 3/4 0  1 0 0 - 2/5 2/5 1/5 

N :  0 1 3/2 1/2 - 1/4 0 
 R :  0 1 0 2/5 1/10 - 1/5 
 0 0 1 1/15 - 7/30 2/15   0 0 1 1/15 - 7/30 2/15 

Vérifiez que A-1.A=I

 Cours d’analyse numérique

Chap2. Systèmes linéaires

Factorisation
FactorisationLU
LU

Soit une matrice A inversible. Cette matrice peut être décomposée en:

P-1A=LU
d’où A=PLU
Avec:
P: est une matrice de permutation
L : matrice triangulaire inférieure avec des 1 sur la diagonale principale
U : matrice triangulaire supérieure.

Lorsque P est choisit matrice identité:

A=LU
 Cours d’analyse numérique

Chap2. Systèmes linéaires

Factorisation
FactorisationLU
LU

Théorème (Existence et unicité de la décomposition LU):

Soit A  IR n*n une matrice inversible. Supposons que toutes les sous- matrices
principales d’ordre 1 à n-1 de A soient inversibles. Alors il existe une unique
matrice L triangulaire inférieure à diagonale unité (ne comportant que des 1 sur
la diagonale) et une matrice U triangulaire supérieure inversibles, telle que:

A=LU
 Cours d’analyse numérique

Chap2. Systèmes linéaires

Factorisation
FactorisationLU
LU

1 0............ 0   u11 u12 ..........u1n 

l
 21 1..............0   0 u22 ..........u 2n 
 l31 l32 1.........0   0 0 u33 ......u3n 
A   . 
.  . 
. 1 0  . 
   
 ln1 ln 2 ....lnn  1 1   0 0 0.......0 unn 

U est obtenue par la méthode du pivot de Gauss

 Cours d’analyse numérique

Chap2. Systèmes linéaires

Factorisation
FactorisationLU
LU

Détermination des éléments lij

n
A=LU d’où aij  lik ukj
k 1

Le déterminant :

det(A)=det(L)*det(U)=u11*u22*….*unn
 Cours d’analyse numérique

Chap2. Systèmes linéaires

Factorisation
FactorisationLU
LU
Exemple :
Déterminer la factorisation LU de A, telle que L n’ait que des 1 sur sa diagonale
principale :

2 1 -4 

A  3 3 - 5  
 4 5 - 2 
 Cours d’analyse numérique

Chap2. Systèmes linéaires

Factorisation
FactorisationLU
LU

Solution
On se sert de la méthode du pivot de Gauss:
Etape 1:

2 1 -4 
A (1)  0 3/2 1  Ligne2ligne2-3/2*ligne1
 0 3 6  Ligne 3ligne 3-4/2*ligne1
Idée géniale: au lieu de garder le 0, on conserve dans cette case le coefficient
Par lequel on a multiplié L1

2 1 -4 
A(1)  3 3/2 1 
 4 3 6 
 Cours d’analyse numérique

Chap2. Systèmes linéaires

Factorisation
FactorisationLU
LU
Etape 2:

2 1 -4 
A (1)  0 3/2 1 
 0 3 6  Ligne 3ligne 3-3/(3/2)*ligne2

au lieu de garder le 0, on conserve dans cette case le coefficient

Par lequel on a multiplié L2 (c-à-d 3)

2 1 -4 
A( 2 )  3 3/2 1 
 4 3 4 
 Cours d’analyse numérique

Chap2. Systèmes linéaires

Factorisation
FactorisationLU
LU

U
2 1 -4 
A ( 2)  
 3 3/2 1 
 4 3 4 
~L
Plus précisément, on divise chaque colonne par l’élément diagonal pour
mettre des 1 sur la diagonale de L
 Cours d’analyse numérique

Chap2. Systèmes linéaires

Factorisation
FactorisationLU
LU

1 0 0  2 1 -4 

L  3/2 1 0  U  0 3/2 1 

 2 2 1   0 0 4 

Vérifiez que LU=A !!

 Cours d’analyse numérique

Chap2. Systèmes linéaires

Factorisation
FactorisationLU
LU
Exemple :
Déterminer la factorisation LU de A, telle que L n’ait que des 1 sur sa diagonale
principale :

1 5 8 0
0 2 6 9 
A 
1 5 11 7
 
0 2 6 13
 Cours d’analyse numérique

Chap2. Systèmes linéaires

Factorisation
FactorisationLU
LU

Résolution du système Ax=b

Résoudre Ax=b peut aussi s’écrire

Ax=(L U) x = L (U x) = b

Que l’on peut décomposer en deux étapes, avec une variable

intermédiaire : y

Ax=b  (LU)x=b  L (Ux) = b  L y=b avec y=Ux

1. Résoudre L y =b
2. Résoudre U x =y
 Cours d’analyse numérique

Chap2. Systèmes linéaires

Factorisation
FactorisationLU
LU
Exemple :
Résoudre le système Ax=b suivant:

2 1 -4  8 
A  3 3 - 5  
b 14 
 4 5 - 2  16
 Cours d’analyse numérique

Chap2. Systèmes linéaires

Factorisation
FactorisationLU
LU

Remarques sur le déterminant:

n
1. Le déterminant d’une matrice triangulaire= u
i 1
ii

2. Après application de l’algorithme de Gauss le déterminant :

n
det( A) det(U ) uii
i 1
3. Plus généralement, le déterminant d’une matrice=produit des pivots successifs
pour la décomposer.
n
det( A)  pi
i 1
 Cours d’analyse numérique

Chap2. Systèmes linéaires

Rappel
Rappel
Définition: Matrice symétrique
Soit A une matrice carrée d'ordre n. On dit que A est symétrique si A = A T.
Définition Matrice définie positive
Soit A une matrice carrée d'ordre n. On dit que A est définie positive si elle vérifie la condition
suivante :

 x  IRn et x ≠ 0; xTAx > 0

Propriété si une matrice carrée A d'ordre n est symétrique définie positive alors :

aii > 0
aij2 < aiiajj i ≠ j
maxj;k |ajk| maxi |aii|

Théorème si une matrice carrée A d'ordre n est définie positive alors elle est inversible.

Corollaire si une matrice carrée A d'ordre n est définie positive, alors le système linéaire Ax = b
ou x et b appartiennent a IRn admet une solution unique.

Théorème Soit M une matrice carrée réelle d'ordre n et non- singulière, alors la matrice A = M TM
 Cours d’analyse numérique

Chap2. Systèmes linéaires

Factorisation
Factorisationde
deCholesky
Cholesky

La factorisation de Cholesky consiste pour une matrice hermitienne

définie positive A à déterminer une matrice triangulaire supérieure
R telle que :
A=R R T

La matrice R est en quelque sorte la racine carrée de A.

Cette décomposition permet notamment de résoudre des systèmes linéaires
du type Ax=b ou de calculer le déterminant de A qui n’est rien d’autre
que le carré du produit des éléments diagonaux de R
 Cours d’analyse numérique

Chap2. Systèmes linéaires

Factorisation
Factorisationde
deCholesky
Cholesky

Théorème (Factorisation de Cholesky d’une matrice)

Soit A  IRn*n une matrice définie positive. Alors il existe au moins une matrice
triangulaire supérieure R telle que :

A = RT R.

Si de plus les éléments diagonaux de la matrice R sont tous positifs alors la

factorisation correspondante est unique.

La décomposition de Choleski peut être assimilée a une décomposition

LU et ressemble a une méthode de Gauss.
 Cours d’analyse numérique

Chap2. Systèmes linéaires

Factorisation
Factorisationde
deCholesky
Cholesky

 r11 0............ 0   r11 r21 .......... ....rn1 

 r r .......... ...0   0 r22 .......... ....r n2 
 21 22  
 r31 r32 r33 ......... 0   0 0 r33 ..........rn 3 
A   . 
.  . 
. 0  . 
   
r r ....r r
 n1 n 2 nn  1 nn   0 0 0.......0 rnn 

n
aij  rik rjk
k 1
 Cours d’analyse numérique

Chap2. Systèmes linéaires

Factorisation
Factorisationde
deCholesky
Cholesky

1 1/2 1/2
A 1/2 1 1/2 
1/2 1/2 1 

1. Vérifiez que A est symétrique définie positive

2. Utilisez la factorisation de Cholesky pour trouver R
3. Résoudre le système Ax=b, avec b=[2 1 3]T
Solution
Solution

1 0.5 0.5 

R  0 0.866 0.2887
 0 0 0.8165

X=[1 -1 3 ]T
 Cours d’analyse numérique

Chap2. Systèmes linéaires

Factorisation
Factorisationde
deCholesky
Cholesky

Donc pour la pième ligne de la matrice triangulaire supérieure :

p
a pj  rik rjk
k 1
p 1
 rik rjk rpp rjp
k 1
D’où l’algorithme suivant:

p 1 1/ 2
 2
rpp  a pp   rpk 
p=1,n
 k 1 
p 1
 
 arp   r r
pk jk 

rjp   
k 1
j  p  1, n
rpp
 Cours d’analyse numérique

Chap2. Systèmes linéaires

Conditionnement
Conditionnementd’une
d’unematrice
matrice
Exemple : Donnez la solution du système suivant

 10 7 8 7   x1   32
 7 5 6 5   x   23
  . 2    X=[1 1 1 1]T
 8 6 10 9   x3   33
    
 7 5 9 10   x4   31

Perturbons quelques éléments du système de 1%, quelle sera la nouvelle solution?

 10 7 8.1 7.2   x1   32

 7.08 5.04 6 5   x   23
  . 2    X=[-81 137 -34 22]T
8 5.98 9.89 9   x3   33
    
 6.99 4.99 9 9.98   x4   31
 Cours d’analyse numérique

Chap2. Systèmes linéaires

Conditionnement
Conditionnementd’une
d’unematrice
matrice

Ainsi, l’exemple précédent montre qu’une faible perturbation (0.01) peut

entraîner de grands écarts sur la solution du système.
Ceci est typique des matrices mal conditionnées.

Le conditionnement d’une matrice A se calcul par :

Cond2 (A)=max(i)/min(i)

Le système le mieux conditionné est celui où cond2(I)=1

Plus Cond(A) est proche de 1, mieux est le conditionnement du système.
 Cours d’analyse numérique

Chap2. Systèmes linéaires

Méthodes
Méthodesitératives
itératives

Pour les très grosses matrices on préférera les méthodes itératives :

elle convergent vers la solution progressivement:

L’objectif est de résoudre un système Cramérien de type:

Ax=b
Idée : Résoudre une équation du type : X=F(x)

avec une suite du type : Xk+1=F(Xk)

Xk convergera vers la bonne valeur de X.

Question : Comment transformer : AX=B en un équation du type

X=F(X) ? Où F est une opération linéaire ??
 Cours d’analyse numérique

Chap3. Systèmes linéaires

Méthodes
Méthodesitératives
itératives

Réponse :

Transformer A =M-N

D’où : Ax=b  (M-N)x=b

et Mx=b+Nx

ainsi x=M-1b+M-1Nx=Px+c
 Cours d’analyse numérique

Chap3. Systèmes linéaires

Méthodes
Méthodesitératives
itératives

Nous cherchons par récurrence une suite de vecteur x(i) obtenu à partir d’un
Vecteur x(0) et de la relation :

Xk+1=M-1Nxk+M-1b

La convergence de la suite xk vers la solution x* est donnée par le théorème suivant :

 Cours d’analyse numérique

Chap3. Systèmes linéaires

Méthodes
Méthodesitératives
itératives

Le choix de la décomposition de A devra respecter les directives suivantes:

 (M-1N)<1
La résolution de Xk+1=M-1Nxk+M-1b doit être simple et nécessiter le moins
d’opérations possibles

Pour obtenir la meilleure convergence, (M-1N) doit être le plus petit possible.
 Cours d’analyse numérique

Chap3. Systèmes linéaires

Méthodes
Méthodesitératives
itératives

Principales
Principalesdécompositions
décompositions

Décomposition DEF :

A=D+E+F
 a11 0........0   0 0..................0   0 a 12 ........a1n 
     
 0 a 22 .......0  a
 21 0.......... ........0   0 0 ...........a 2n 
D  .  E  .  F  . 
     
.  .   . ............. a n -1n 
     
 0 0. ........a nn  a a
 n1 n 2 . ....a nn  1 0   0 0. ..........0 

Nous obtiendrons donc la décomposition M-N à partir des différents types de

regroupement des ces matrices D,E,F
 Cours d’analyse numérique

Chap3. Systèmes linéaires

Méthodes
Méthodesitératives
itératives

Principales
Principalesdécompositions
décompositions
Méthode de Jacobi

On pose M = D , N = -(E+F)
M-1N=D-1(-E-F) ce qui implique

Xk+1=D-1(-E-F)xk+D-1b
Ainsi, si on exprime cette relation en fonction des éléments de A:

n aij bi

(i ) (k )
xk 1  xj  , i 1,...n
j 1, j i aii aii
 Cours d’analyse numérique

Chap3. Systèmes linéaires

Méthodes
Méthodesitératives
itératives

Principales
Principalesdécompositions
décompositions
Méthode de Gauss- Seidel
On pose : M=D+E , N=-F
On a : xk+1=-(D+E)-1Fxk+(D+E)-1b

Le calcul de l’inverse (D+E) peut être évité, si on écrit (D+E)xk+1=-Fxk+b

D’où

i 1 n
1 1 bi
 a x
(i ) ( j) ( j)
xk 1  aij xk 1  ij k 
aii j 1 aii j i 1 aii
 Cours d’analyse numérique

Chap3. Systèmes linéaires

Méthodes
Méthodesitératives
itératives

Principales
Principalesdécompositions
décompositions
Méthode de relaxation
On se pose un paramètre w]0,2[ appelé facteur de relaxation :

D  1 w 
M  E N  D  F
w  w 
Et par conséquent :

D   1 w 
  E x 
 k 1  D  F  xk  b
w   w 
D’où
w i 1 n
(1  w) xk  (  aij xk 1   aij xk
(i ) ( j) (i )
xk 1  bi )
aii j 1 j i 1
 Cours d’analyse numérique

Chap3. Systèmes linéaires

Méthodes
Méthodesitératives
itératives

Convergence
Convergencedes
desméthodes
méthodesitératives
itératives

Les méthodes itératives convergent si le rayon spectral (C)<1,mais comme le

calcul du rayon spectral est souvent difficile, on préfère utiliser un autre critère.

Cas
Casdes
desmatrices
matricesààdiagonale
diagonalestrictement
strictementdominante
dominante
Définition: une matrice est dite à diagonale dominante si :
n
i,1 i n, aii  a
j 1, j i
ij

Elle est dite à diagonale strictement dominante si

n
i,1 i n, aii  a
j 1, j i
ij
 Cours d’analyse numérique

Chap3. Systèmes linéaires

Méthodes
Méthodesitératives
itératives

Convergence
Convergencedes
desméthodes
méthodesitératives
itératives

Théorème

Si A est une matrice à diagonale strictement dominante, alors A est inversible

et en outre, les méthodes de Jacobi et de Gauss- Seidel convergent.

Cas
Casdes
desmatrices
matricessymétriques
symétriquesdéfinies
définiespositives
positives
Théorème

Si A une matrice symétrique définie positive, alors la méthode de Gauss- Seidel

et de relaxation (pour w]0,2[) convergent.