Mathématiques et analyse numérique
A. Aghaei
ISBS 1– FI/FA
EPISEN - Université Paris Est Créteil
Contenu du cours
Introduction
Algèbre de matrices
Résolution d’équations et de systèmes linéaires
Résolution d’équations et de systèmes non-linéaires
Interpolation polynomiale et méthode des moindres carrés
Intégration numérique de fonctions
Résolution d'équations différentielles
Motivation :
. Il est presque impossible d'effectuer une analyse numérique sans rencontrer des systèmes linéaires ;
. Réduire le coût de calcul en exploitant des propriétés spéciales des matrices.
Un système linéaire a la forme :
où les coefficients 𝐴𝑖𝑗 et les constantes 𝑏𝑗 sont connus, et 𝑥𝑙 représentent les inconnues.
4
En notation matricielle, les équations sont écrites comme :
ou simplement : 퐴x = 푏
Méthodes de résolution :
Méthodes directes : transforment les équations d'origine en équations équivalentes
(équations qui ont la même solution) qui peuvent être résolues plus facilement.
Méthodes itératives : résolution approchée du système linéaire.
5
Méthodes directes :
Méthode Forme initiale Forme finale
Elimination de Gauss 𝑨𝑥 = 𝑏 𝑼𝑥 = 𝑐
Décomposition LU 𝑨𝑥 = 𝑏 𝑳𝑼𝑥 = 𝑏
Elimination de Gauss-Jordan 𝑨𝑥 = 𝑏 𝑰𝑥 = 𝑐
Où :
. 𝑼 représente une matrice triangulaire supérieure ,
. 𝑳 est une matrice triangulaire inférieure ,
. 𝑰 désigne la matrice identité.
Remarque : Une matrice carrée est dite triangulaire si elle ne contient que des zéros d'un côté de la diagonale principale.
6
. Les matrices triangulaires jouent un rôle important en algèbre linéaire car elles simplifient de nombreux calculs,
par exemple considèrerons l’équation 𝑳 𝒙 = 𝒄
La solution se déroulerait donc comme suit :
Cette procédure est connue sous le nom de substitution directe 7
Exercice : Résoudre le système linéaire équations 𝐴𝑥 = 𝑏, où :
la décomposition 𝐿𝑈 de la matrice donne :
Méthode :
Soit 𝑳𝑼𝑥 = 𝑏 , suposons que 𝑼𝑥 = 𝑦 nous obtenons : 𝑳𝑦 = 𝑏
La méthode consiste à résoudre tout d'abord par substitution directe les équations 𝑳𝑦 = 𝑏, la solution x est ensuite
obtenue à partir de 𝑼𝑥 = 𝑦. 8
La décomposition LU de la matrice donne :
Solution :
On résout d'abord les équations 𝑳𝑦 = 𝑏 par substitution directe :
La solution 𝑥 est alors obtenue à partir de 𝑼𝑥 = 𝑦 :
2
𝑥 = − 1
3
9
Méthode d'élimination de Gauss
Cette méthode se compose de deux parties : la phase d'élimination et la phase de solution : 𝑼𝒙 = 𝒄
Exemple :
résolvons les équations :
Solution :
Phase d'élimination
L'équation à soustraire, à savoir Eq. ( 𝑗 ), est appelée équation pivot.
10
Méthode d'élimination de Gauss
Les équations originales sont remplacées par des équations équivalentes qui peuvent être facilement résolues.
b. Phase de substitution :
11
Méthode d'élimination de Gauss - Algorithme
. Supposons que les 𝑘 premières lignes de 𝐴 aient déjà été transformées en forme triangulaire supérieure. Par
conséquent, l'équation pivot actuelle est la 𝑘eme équation, et toutes les équations en dessous doivent encore être
transformées.
. Notez que les composants de A ne sont pas les coefficients des équations d'origine (sauf pour la première ligne), car ils
ont été modifiés par la procédure d'élimination. Il en va de même pour les composantes du vecteur constant b.
. Soit la 𝑖 ème ligne, une ligne typique en dessous de l'équation pivot qui doit être transformée, c'est-à-dire que l'élément
𝐴𝑖𝑘 doit être éliminé. Nous pouvons y parvenir en multipliant l’équation pivot par 𝜆 = 𝐴𝑖𝑘 /𝐴𝑘𝑘 et en la
soustrayant de la 𝑖 ème equation. Les changements correspondants dans la 𝑖 ème ligne sont :
Equation pivot
Equation en cours
de transformation
12
Méthode de décomposition LU
. Toute matrice carrée A peut être décomposée en une matrice triangulaire inférieure 𝑳 et une matrice triangulaire
supérieure 𝑼 :
. Le processus de calcul de 𝑳 et 𝑼 pour un A donné est connu sous le nom de décomposition 𝑳𝑼 ou factorisation LU.
. il existe trois décomposition LU décompositions couramment utilisées :
Méthode Contraintes
Décomposition de Doolittle 𝑳𝑖𝑖 = 𝟏, 푖 = 1, 2, ….., n
Décomposition de Crout 𝑼𝒊𝒊 = 𝟏, 푖 = 1, 2, ….., n
Décomposition de Choleski 𝑳 = 𝑼𝑻
. L'avantage de la décomposition 𝑳𝑼 par rapport à la méthode d'élimination de Gauss est qu'une fois la matrice 𝐴 est
décomposée, nous pouvons résoudre 𝑨𝑥 = 𝑏 pour autant de vecteurs constants 𝑏 que nous le souhaitons. 13
Méthode de décomposition de Doolittle
Appliquons maintenant la méthode d'élimination de Gauss :
14
Méthode de décomposition de Doolittle
. Stocker les multiplicateurs dans la partie triangulaire inférieure de la matrice des coefficients, en remplaçant les
coefficients au fur et à mesure de leur élimination (𝐿𝑖𝑗 remplaçant 𝐴𝑖𝑗 ).
. Les éléments diagonaux de 𝐿 ne doivent pas être stockés.
. La forme finale de la matrice des coefficients serait donc la combinaison suivante de 𝐿 et 𝑈 :
15
Méthode de décomposition de Doolittle
Exemple
Utilisez la méthode de décomposition de Doolittle pour résoudre les équations 𝑨𝒙 = 𝒃, où :
Solution :
Phase d'élimination
En stockant les multiplicateurs 𝐿23 = 1 et 𝐿31 = 2 à la place des termes éliminés, on obtient :
16
Méthode de décomposition de de Doolittle
Solution :
b. Phase substitution :
17
Rappel: Une matrice carrée A symétrique est dite
Méthode de décomposition de Choleski définie positive si on a
𝑥𝑡𝐴 𝑥 > 0
pour tout 𝑥 ≠ 0
La décomposition de Cholesky a deux limitations : La matrice 𝐴 doit être définie positive et symétrique, puisque le
produit matriciel 𝐿𝐿𝑇 est symétrique. I.e. une condition nécessaire et suffisante pour qu’une matrice 𝐴 soit
symétrique et définie positive est qu’il existe une matrice 𝐿 inversible triangulaire inférieure telle que
18
Méthode de décomposition de Choleski
Solution :
19
Méthode de décomposition de Choleski
Exemple :
Calculer la décomposition de Choleski de la matrice:
Solution
20
Méthode de décomposition de Choleski
Exemple :
Calculer la décomposition de Choleski de la matrice:
Solution
21
Méthode de décomposition LU de Choleski - Algorithme
Nous pouvons maintenant extrapoler les résultats pour une matrice 𝑛 × 𝑛. Nous observons qu'un élément typique dans
la partie triangulaire inférieure de 𝐿𝐿𝑇 est de la forme :
Eq 1
ou
Eq 2
Pour 𝑗 = 1
22
Méthode de décomposition LU de Choleski
En passant aux autres colonnes, nous observons que l'inconnue dans l’eq 1 est 𝐿𝑖𝑗 (les autres éléments de L apparaissant
dans l'équation ont déjà été calculés). En prenant le terme contenant 𝐿𝑖𝑗 en dehors de la sommation dans l’eq 1, on obtient
Si 𝑖 = 𝑗 (un terme diagonal) , la solution est :
Pour un terme non diagonal on obtient :
23
Présentation de l’environnement de calcul Matlab
Décomposition LU avec Matlab
Décomposition LU avec Matlab
Les méthodes itératives ou indirectes commencent par une estimation initiale de la solution x, puis améliorent à plusieurs
reprises la solution jusqu'à ce que le changement de 𝑥 devienne négligeable.
Avantages :
. Il est possible de stocker uniquement les éléments non nuls de la matrice des coefficients. Cela permet de traiter de très
grandes matrices peu denses, mais pas nécessairement bandées.
. Les procédures itératives sont autocorrectives, ce qui signifie que les erreurs d'arrondi (ou même les erreurs
arithmétiques) dans un cycle itératif sont corrigées dans les cycles suivants.
Inconvénients :
. Étant donné que le nombre d'itérations requis peut être très important, les méthodes indirectes sont, en général, plus
lentes que leurs homologues directes.
24
Un exemple
Un exemple
Une méthode itérative générique
Convergence
Critère de Convergence
Méthode de Jacobi
Méthode de Jacobi
Méthode de Gauss–Seidel
Méthode de Gauss–Seidel
Nous approchons ainsi la solution exacte en 2 itérations
Méthode de Gauss–Seidel
Nous approchons ainsi la solution exacte en 2 itérations
Méthode de Gauss–Seidel
Exemple:
Résolvez le système des équations par la méthode de Gauss-Seidel :
Solution
En choisissant les valeurs de départ 𝑥1 = 𝑥2 = 𝑥3 = 0,
nous avons pour la première itération :
26
Méthode de Gauss–Seidel
Solution
La deuxième itération donne :
La troixième itération donne :
Après cinq itérations supplémentaires, les résultats correspondent à la solution exacte : 𝑥1 = 3, 𝑥2 = 𝑥3 = 1
27
Quelques remarques
• L’utilisation des méthodes itératives est généralement plus avantageuse lorsque celles-ci convergent.
• Les méthodes de Jacobi et de Gauss-Seidel ne convergent le plus souvent que dans les cas que nous avons d’écrits dans
ce chapitre. Il existe des méthodes itératives beaucoup plus élaborées et qui convergent dans des cas plus généraux que
ceux d´écrits ici.
• La méthode de Gauss-Seidel converge généralement plus vite et plus souvent que la méthode de Jacobi.
• La convergence des méthodes itératives se teste généralement en utilisant un paramètre de tolérance 𝜖. On arrête ainsi
les calculs dès que l’erreur relative est assez petite :
• Une autre alternative est de tester le résidu :
Méthode du Gradient
Rechercher un vecteur 𝑥 qui minimise la fonction scalaire :
où la matrice 𝐴 est symétrique et positive
f est minimale si : 0
La méthode du Gradient réalise la minimisation par itération, en commençant par un vecteur initial 𝑥0 . Chaque cycle
itératif 𝑘 calcule une solution raffinée.
La longueur de pas 𝛼𝑘 est choisie de telle sorte que 𝑥𝑘+1 minimise 𝑓(𝑥𝑘+1 ) dans la direction de recherche 𝑠𝑘 . C'est-à-dire
que 𝑥𝑘+1 doit satisfaire l'équation :
En introduisant le résidu :
28
Méthode du Gradient
Multipliant les deux côtés de l’équation par et résolvons pour Nous obtenons :
Déterminaant maintenant la direction de recherche 𝑠𝑘 . Et posons :
La constante 𝛽𝑘 est choisie pour que les deux directions de recherche successives soient conjuguées (non interférentes) l'une
de l'autre, c'est-à-dire : En remplacement pour , nous obtenons
Ce qui donne :
29
Méthode du Gradient
En résumé:
1. Choisir 𝑥0
2.
3.
4. Faire avec
30
Méthode du Gradient
Exemple:
Résolvez le système des équations du Gradient:
Solution:
Choisissons un vecteur initial:
31
Méthode du Gradient
32
Méthode du Gradient
33
Méthode du Gradient
34
