Chapitre UN : Rappels sur quelques méthodes numériques 2019

Partie I: Rappel sur le calcul matriciel.

1. Définitions
Matrice : une matrice est un tableau de chiffres rangés en lignes et en colonnes.

Exemple

- Ordre d’une matrice : Une matrice d’ordre m et n possède : m lignes et n colonnes. Dans
l’exemple précédent on dira que la matrice est d’ordre (2,3).
- Matrice colonne : Elle ne possède qu’une seule colonne et n lignes : matrice (n,1).

Matrice unité : C’est une matrice dont tous les éléments sont (1) ; elle est désignée par [I].

2. Matrice carrée
C’est une matrice qui a autant de lignes que de colonnes. Ex

La diagonale principale d’une matrice est formée par l’ensemble des éléments aii de la matrice.
Une matrice diagonale est donc une matrice qui a tous ses éléments nuls sauf ceux de sa diagonale
principale.
- La matrice unité est la matrice diagonale qui n’a que des 1 dans sa diagonale principale.
- La trace d’une matrice est la somme des éléments de la diagonale principale
3. Opérations sur les matrices

Transposition : Les lignes de la matrice [A] de départ deviennent les colonnes de la matrice
transposée [A]T. On dit qu’on a transposé la matrice

Exemple

Addition : On ne peut additionner que des matrices de même ordre. On additionne les
éléments équivalents (dans la même position dans les deux matrices) de chaque matrice.

Ex :

υ Université KASDI Merbah Ouargla- S2-M1 ME,RE, ELT- cour Méthode numériques appliquées et optimisation -
Dr : NACEUR Sonia
 Chapitre UN : Rappels sur quelques méthodes numériques 2019

Multiplication d’une matrice par un scalaire: Tous les éléments de la matrice sont
multipliés par ce scalaire

Multiplication de 2 matrices ([A]x[B]=[C]) : La multiplication n’est possible que si le

nombre de colonnes de [A] est égal au nombre de lignes de [B]. Si [A](m,p) multiplie
[B](p,n) alors [C] est une matrice d’ordre (m,n). La multiplication est effectuée en multipliant
terme à terme une ligne de [A] avec une colonne de [B] et en additionnant chacun des
produits

Exemple

Inversion : Uniquement pour les matrices carrées. Comme pour l’inverse d’un nombre, on
appellera [B] la matrice inverse de [A] si [A]x[B]=[I] la matrice unité (rappel : l’inverse d’un
nombre r est le nombre p tel que r.p= 1 soit p = r-1). La matrice [A]-1 existe si le
déterminant de [A] n’est pas nul.

4. Méthode de calcul de l’inverse d’une matrice

- On calcule le déterminant de la matrice [A] = det(A) ;
- On transpose la matrice [A]. Elle devient [A]T ;
- Pour chaque élément de la matrice [A]T, on calcule le mineur associé. Le mineur est le
déterminant de la matrice obtenue en supprimant la ligne et la colonne auxquelles appartient
l’élément.
- On associe à chacun de ces mineurs, 1 signe donné par (-1)i+j ; i étant le numéro de la ligne
et j le numéro de la colonne de l’élément envisagé. L’ensemble (signe) x (mineur) constitue
les cofacteurs de la matrice [A]T.
- Il suffit maintenant de remplacer tous les éléments de la matrice [A]T par les cofacteurs (on
obtient alors une matrice [A]C) et de diviser par det(A) pour obtenir l’inverse de la matrice
[A].

Exemple : Calcul du déterminant et inversion de matrices carrées :

φ Université KASDI Merbah Ouargla- S2-M1 ME,RE, ELT- cour Méthode numériques appliquées et optimisation -
Dr : NACEUR Sonia
 Chapitre UN : Rappels sur quelques méthodes numériques 2019

Patrie 2. Méthodes itératives pour la résolution des systèmes

linéaires et non-linéaires
2.1 Méthodes itératives pour la résolution des systèmes linéaires
I.1.-Définitions et Notations :
On appelle matrice de type (de dimension) (n,m) un tableau de nombres à n lignes,
m colonnes. L’ensemble de matrices de types (n,m) est notée M (IK) n,m , (K = R ou C),
(K : Ensemble des scalaires). On adopte la notation suivante :
Une matrice A de dimension (n,m) sera motée An,m =(ai,j ) 1≤i≤n ; 1 ≤j≤m

La transposée de A, notée
At sera alors

A est symétrique si AAt ; on a aussi la propriété : (A.B)

t
Bt .At
Une matrice carrée An,m , est une matrice dont le nombre de lignes est égal au nombre de
colonnes
1.2-Résolution des Systèmes Linéaires :
Tout système d’équations linéaires peut s’écrire sous forme matricielle AX = b , A : une
matrice carrée

Si detA0 ( A est inversible ou régulière), l’unique solution du système est donnée par

AX = b  A-1AX= A-1b  X= A-1b

૚
Avec A-1= ‫) ∗࡭( )࡭(ܜ܍܌‬t

A* :et la matrice donnée par

A*= (Ci,j), 1≤i,j≤ n
Ci,j=(-1)i+j det(Ai,j)
Aij : C’est la matrice A sans la ième ligne et la jème colonne.

Formule générale pour le calcul de detAselon les lignes :

χ Université KASDI Merbah Ouargla- S2-M1 ME,RE, ELT- cour Méthode numériques appliquées et optimisation -
Dr : NACEUR Sonia
 Chapitre UN : Rappels sur quelques méthodes numériques 2019

࢔
‫ )࡭(ܜ܍܌‬ൌ ෍ െ૚࢏ା࢐ࢇ࢏࢐‫ܜ܍܌‬
ሺ࡭࢏࢐)
࢐ୀ૚

Méthode de Cramer :

L’unique solution du système AX b ( detA0 ) est donnée selon Cramer par
‫ܜ܍܌‬
ሺ࡭ )
࢏
Xi = ‫ܜ܍܌‬ሺ࡭ሻ

Ai est la matrice A où l’on a remplacé le ième colonne par le vecteur second membre « b ».
Cette méthode de Cramer est inadaptée pour résoudre les systèmes de grandes tailles car il y a
trop de déterminants à calculer. Pour cela, on a recours à d’autres méthodes de résolution des
systèmes d’équations AX = b . Ces méthodes sont classées dans deux groupes.
Les premières méthodes, intitulées Méthodes directes, sont basées sur la transformation du
système initial AX = b , en passant par un nombre d’étapes finies, pour avoir la solution X .
Parmi ces méthodes, on a la méthode de Gauss, La décomposition LU et la méthode de
Cholesky.
Les méthodes du deuxième groupe, intitulées méthodes itératives, sont basées sur des
procédures itératives qui permettent d’approcher la solution du système, en amorçant le calcul
(0)
à partir d’une solution initiale X . Parmi ces méthodes, on a la méthode de Jacobi et la
méthode de Gauss-Seidel

I.2 Méthodes Itératives :

I.2.1 Définitions :
Soit A une matrice carrée d’ordre n . A n n, .
 On appelle trace de A le scalaire noté : tra(A)= ∑࢔࢏ୀ૚ ࢇ࢏࢏
 On dit que λє Cest une valeur propre de A si et seulement si il existe une vecteur
ഥ є Cn tel que ࢂ
ࢂ ഥ࡯࢔ et ࡭ࢂ
ഥ≠૙ ഥ ൌ ࣅࢂ
ഥ
 Les valeurs propres de la matrice A sont les racines réelles ou complexes du
polynôme caractéristique de A noté : PA(λ) = det(A - λI ) = 0.
 Trac(A)=∑࢔࢏ୀ૚ ૃ࢏ሺ‫ۯ‬ሻ, det (A)= ∏࢔࢏ୀ૚ ࣅ࢏ሺ࡭ሻ
 Le spectre de la matrice A , noté S (A) { λi(A)}
 Le rayon spectral de la matrice A , noté ρ(A) =max(|ૃܑሺ࡭ሻ|
 La matrice A est à diagonale dominante stricte (D.D.S) si et seulement si

࢔ ࢔

|ࢇ࢏࢏| ൐ ෍ หࢇ࢏࢐ห‫࢞࢏ࢌ࢏׊‬±࢕࢛หࢇ࢐࢐ห൐ ෍ หࢇ࢏࢐ห‫࢞࢏ࢌ࢐׊‬±

࢐ୀ૚ ࢏ୀ૚
࢐ஷ࢏ ࢐ஷ࢏

ψ Université KASDI Merbah Ouargla- S2-M1 ME,RE, ELT- cour Méthode numériques appliquées et optimisation -
Dr : NACEUR Sonia
 Chapitre UN : Rappels sur quelques méthodes numériques 2019

Propositions :
1- Si A est symétrique, alors toutes les valeurs propres de A sont réelles, de plus si A est
définie positive, alors les valeurs propres de A sont toutes positives.
2- On suppose que A est une matrice à diagonale strictement dominante (D.D.S), alors les
valeurs propres de A sont non nulles.

Conséquences : A est une matrices à diagonale strictement dominante detA0 ,

l’inverse de A existe.

Normes Matricielles :
On appelle norme matricielle toute application de Mp (R dans R+ qui satisfait les axiomes
suivants

1.3 Principales méthodes itératives

On considère la décomposition suivante de la matrice A

ω Université KASDI Merbah Ouargla- S2-M1 ME,RE, ELT- cour Méthode numériques appliquées et optimisation -
Dr : NACEUR Sonia
 Chapitre UN : Rappels sur quelques méthodes numériques 2019

où,

D : la diagonale de A,
−E : la partie au dessous de la diagonale de A,
−F : la partie au dessus de la diagonale de A.

Exemple :

Soit A = Alors

On suppose que∀i = 1, 2 · · · , n, aii ≠ 0 (on peut s'y ramener si A est inversible).

i) Méthode de Jacobi : M = D, N = E + F
ii) Méthode de Gauss-Seidel : M = D − E, N = F
1.3.1 Présentation des algorithmes
On va, dans ce qui suit, expliciter les méthodes de Jacobi et Gauss-Seidel, et cela sur un
système linéaire à trois équations (n = 3).
Méthode de Jacobi :
Soit donc AX = b où A Є M3(R), b Є R3

les (aii) i=1,2,...,n étant supposés non nuls ; tirons x1 de (1), x2 de (2) et x3 de (3), on obtient

La méthode de Jacobi revient au processus itératif suivant :

1`ere étape :

ϊ Université KASDI Merbah Ouargla- S2-M1 ME,RE, ELT- cour Méthode numériques appliquées et optimisation -
Dr : NACEUR Sonia
 Chapitre UN : Rappels sur quelques méthodes numériques 2019

2`eme étape

D’où l’algorithme de Jacobi :

Critère d’arrêt :
En pratique, les itérations vont jusqu’à atteindre la précision e donnée au préalable, qui se
traduit par :

ϋ Université KASDI Merbah Ouargla- S2-M1 ME,RE, ELT- cour Méthode numériques appliquées et optimisation -
Dr : NACEUR Sonia
 Chapitre UN : Rappels sur quelques méthodes numériques 2019

Conclusion : Le système AX b devient équivalent au système réduit X X 

AX b X X (Forme récursive)
A partir du système X X , en partant d’une approximation initiale arbitraire X  , on 0


résout le système : X k 1
X k ; k N
Algorithme de Jacobi :

Qui n’est autre que la formule de Jacobi

Ainsi, on aboutit à l’algorithme de Jacobi.
Remarque : On peut noter par J d’où

Convergence de la méthode de Jacobi :

Méthode de Gauss-Seidel :
La méthode de Gauss-Seidel est une amélioration de la méthode de Jacobi en effet elle rend le
processus itératif plus rapide.
Le système réduit reste le même sauf que la valeur nouvelle de obtenue dans la ième
équation sera injectée dans la suivante.

ό Université KASDI Merbah Ouargla- S2-M1 ME,RE, ELT- cour Méthode numériques appliquées et optimisation -
Dr : NACEUR Sonia
 Chapitre UN : Rappels sur quelques méthodes numériques 2019

C'est à dire toutes les composantes calculées (x1, x2, ..., xi−1) sont utilisées pour calculer
xi), et ainsi de suite, jusqu'à satisfaction du critère d'arrêt.
Algorithme de Gauss-Seidel :
Une autre décomposition de A , autre que celle développée ci-dessus, permet d’aboutir à la
méthode de Gauss-Seidel

Et en développant la formule récursive ci-dessus, on aboutit à l’algorithme de Gauss-Seidel

Algorithme de Gauss-Seidel :

Remarque :
1- La matrice de Gauss-Seidel, notée G s est donnée par :
2- La matrice de Jacobi, notée J , est donnée par : 
3- Pour pouvoir appliquer la méthode de Gauss-Seidel, il faut que les aii ≠0 , 1, n.

ύ Université KASDI Merbah Ouargla- S2-M1 ME,RE, ELT- cour Méthode numériques appliquées et optimisation -
Dr : NACEUR Sonia
 Chapitre UN : Rappels sur quelques méthodes numériques 2019

4- Tous les résultats de convergence pour la méthode de Jacobi ( J ) restent valables pour la
méthode de Gauss-Seidel (G s) (remplacer par J ou par G s).

2.2 Méthodes itératives pour la résolution des systèmes non-

linéaires
Les méthodes de Gauss-Seidel et Jacobi vus dans la section 1 pour la solution de systèmes
linéaires peuvent être ´étendus pour la résolution de systèmes non-linéaires. En général on
normalise les équations, c’est-`a-dire on les réécrit sous la forme

Ou encore, chercher un vecteur X = (x1; x2; :::; xn) vérifiant F(X) = 0

L'algorithme

(0).
Choix d'un vecteur initial X

Itération jusqu'à convergence

Où J(X(k)) est la matrice jacobienne évalué en X(k).

Ce qui s'écrit encore :

En posant le problème revient à résoudre le système linéaire

suivant, à chaque itération k :

La méthode de Newton linéarise ainsi le système. Il faut alors, à chaque itération, résoudre un

υτ Université KASDI Merbah Ouargla- S2-M1 ME,RE, ELT- cour Méthode numériques appliquées et optimisation -
Dr : NACEUR Sonia
 Chapitre UN : Rappels sur quelques méthodes numériques 2019

système linéaire jusqu'à ce que le vecteur X soit suffisamment proche de la solution .Pour une
seule équation non linéaire et une suite de réels, le critère d'arrêt est basé sur l'erreur entre le
résultats de deux itérations successives (par exemple

Pour un système d'équations et une suite de vecteurs, le critère d'arrêt est basé sur la norme
entre le résultats de deux itérations successives ; qui doit être
inférieure à unevaleur donnée.
En calcul numérique, trois normes sont fréquemment utilisées :

υυ Université KASDI Merbah Ouargla- S2-M1 ME,RE, ELT- cour Méthode numériques appliquées et optimisation -
Dr : NACEUR Sonia