//img.uscri.be/pth/41b39e095cab5827ac87d2ddbfe693a90060598f
Cet ouvrage fait partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour le lire en ligne
En savoir plus

Méthodes numériques pour l'ingénieur

De
259 pages
Méthodes numériques pour l'ingénieur présente les algorithmes de base pour résoudre les problèmes en dimension finie rencontrés dans la modélisation des phénomènes physiques ou économiques. La résolution des équations matricielles, le calcul des valeurs propres ainsi que l'optimisation de fonctionnelles convexes sont développés de façon pédagogique. Les algorithmes opérationnels sont détaillés et la prise en compte de certaines contraintes ou de non linéarités font l'objet de développements spécifiques en fonction du type de problèmes rencontrés (contraintes égalité ou inégalité, non différentiabilité).
Cet ouvrage propose des ouvertures vers le contrôle optimal ainsi qu'une étude de la sensibilité des solutions de systèmes linéaires. S'adressant aux élèves ingénieurs ou en licence de mathématiques appliquées, Méthodes numériques pour l'ingénieur propose également des exercices et problèmes pour mettre en œuvre les méthodes de résolution.
Chapitre 1. Introduction générale. ANALYSE NUMÉRIQUE MATRICIELLE. Chapitre 2. La méthode de Gauss et ses variantes. Chapitre 3. Introduction à l'analyse numérique matricielle. Chapitre 4. Méthodes itératives de résolution des systèmes linéaires. Chapitre 5. Calcul de valeurs et de vecteurs propres. OPTIMISATION. Chapitre 6. Introduction à l'optimisation. Chapitre 7. Optimisation de fonctions convexes. Chapitre 8. Prise en compte des contraintes linéaires. Chapitre 9. Quelques remarques sur la programmation linéaire. Chapitre 10. Optimisation de fonctionnelles non différentiables. Chapitre 11. Optimisation convexe avec contraintes. Chapitre 12. Introduction au contrôle optimal. DONNÉES INCERTAINES. Chapitre 13. Prise en compte de certaines incertitudes. PROBLÈMES ET EXERCICES. Chapitre 14. Problème de synthèse. Chapitre 15. Examens proposés à différentes sessions. Chapitre 16. Quelques exercices proposés en cours. Bibliographie. Index.
Voir plus Voir moins





















Méthodes numériques pour l'ingénieur





















Photo de couverture : machine arithmétique de Blaise Pascal à chiffres plus sous et deniers, 1647.
©Musée des arts et métiers-Cnam, Paris / Photo Sylvain Pelly

© LAVOISIER, 2010
LAVOISIER
11, rue Lavoisier
75008 Paris

www.hermes-science.com
www.lavoisier.fr

ISBN 978-2-7462-2988-4



Le Code de la propriété intellectuelle n'autorisant, aux termes de l'article L. 122-5, d'une part,
que les "copies ou reproductions strictement réservées à l'usage privé du copiste et non
destinées à une utilisation collective" et, d'autre part, que les analyses et les courtes citations
dans un but d'exemple et d'illustration, "toute représentation ou reproduction intégrale, ou
partielle, faite sans le consentement de l'auteur ou de ses ayants droit ou ayants cause, est
illicite" (article L. 122-4). Cette représentation ou reproduction, par quelque procédé que ce
soit, constituerait donc une contrefaçon sanctionnée par les articles L. 335-2 et suivants du
Code de la propriété intellectuelle.
Tous les noms de sociétés ou de produits cités dans cet ouvrage sont utilisés à des fins
d’identification et sont des marques de leurs détenteurs respectifs.


Printed and bound in England by Antony Rowe Ltd, Chippenham, September 2010.




Méthodes numériques

pour l’ingénieur















Philippe Destuynder








Table des matières
Chapitre 1. Introduction générale . . . . . . . . . . . . . . . . . . . . . . . . 13
1.1. La résolution des systèmes linéaires . . . . . . . . . . . . . . . . . . . . 13
1.2. Le calcul des valeurs propres des matrices . . . . . . . . . . . . . . . . 15
1.2.1. La méthode globale de Jacobi . . . . . . . . . . . . . . . . . . . . 17
1.2.2. La sélective de la puissance itérée . . . . . . . . . . . . . 19
1.3. L’optimisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.4. Le contrôle des systèmes linéaires . . . . . . . . . . . . . . . . . . . . . 22
1.5. Les aspects aléatoires . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
PREMIÈRE PARTIE. ANALYSE NUMÉRIQUE MATRICIELLE . . . . . . . . . 27
Chapitre 2. La méthode de Gauss et ses variantes . . . . . . . . . . . . . . . 29
2.1. La factorisation de Gauss . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.2. L’algorithme de Gauss . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.3. Pivotage et astuces de programmation . . . . . . . . . . . . . . . . . . . 34
2.4. Décompte des opérations . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.5. Cas d’une matrice symétrique définie positive . . . . . . . . . . . . . . 35
2.6. Possibilités de méthodes par blocs, aspects opérationnels . . . . . . . . 37
2.7. Stockage des matrices creuses et bandes . . . . . . . . . . . . . . . . . 38
2.7.1. Stockage en ligne de ciel . . . . . . . . . . . . . . . . . . . . . . . 39
2.7.2. Stockage Morse . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
2.8. Vectorisation et parallélisation . . . . . . . . . . . . . . . . . . . . . . . 41
2.9. La méthodeQR de Householder . . . . . . . . . . . . . . . . . . . . . . 42
2.10. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
Chapitre 3. Introduction à l’analyse numérique matricielle . . . . . . . . . 47
3.1. Normes sur un espace vectoriel . . . . . . . . . . . . . . . . . . . . . . . 47
3.2. Convergence dans un espace vectoriel . . . . . . . . . . . . . . . . . . . 516 Méthodes numériques pour l’ingénieur
3.2.1. Exemples élémentaires de résultats d’analyse vectorielle . . . . . 51
3.3. Normes matricielles vectorielles et normes subordonnées . . . . . . . . 53
3.4. Quelques propriétés de convergence des suites vectorielles et matricielles 58
3.5. Robustesse et conditionnement des système linéaires . . . . . . . . . . 61
3.6. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
Chapitre 4. Méthodes itératives de résolution des systèmes linéaires . . . . 63
4.1. La méthode de Jacobi . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
4.2. La du point fixe . . . . . . . . . . . . . . . . . . . . . . . . . . 64
4.3. La méthode de relaxation de Gauss-Seidel . . . . . . . . . . . . . . . . 66
4.4. La de sur-relaxation . . . . . . . . . . . . . . . . . . . . . . . . 67
4.5. Remarques sur le préconditionnement . . . . . . . . . . . . . . . . . . . 70
4.5.1. Préconditionnement par la diagonale . . . . . . . . . . . . . . . . 71
4.5.2. Préconditionnement par la sous-matrice triangulaire inférieure deA 72
4.6. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
Chapitre 5. Calcul de valeurs et de vecteurs propres . . . . . . . . . . . . . 73
5.1. La puissance itérée inverse avec décalage spectral . . . . . . . . . . . . 73
5.1.1. Description de l’algorithme élémentaire . . . . . . . . . . . . . . . 74
5.1.2. Auto-ajustement de . . . . . . . . . . . . . . . . . . . . . . . . . 75
5.1.3. Calcul des autres valeurs et vecteurs propres . . . . . . . . . . . . 76
5.1.4. Cas d’une matriceM de pondération . . . . . . . . . . . . . . . . 77
5.2. Itération sur un sous-espace . . . . . . . . . . . . . . . . . . . . . . . . . 77
5.3. La méthode de Jacobi . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
5.3.1. Description de la méthode de Jacobi . . . . . . . . . . . . . . . . . 78
5.3.2. Convergence de la de Jacobi . . . . . . . . . . . . . . . . 80
5.4. La méthode de Lanczos . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
5.5. La de bissection des suites de Sturm . . . . . . . . . . . . . . 84
5.6. Recherche du noyau d’une matrice . . . . . . . . . . . . . . . . . . . . . 86
5.7. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
DEUXIÈME PARTIE. OPTIMISATION . . . . . . . . . . . . . . . . . . . . . . 89
Chapitre 6. Introduction à l’optimisation . . . . . . . . . . . . . . . . . . . . 91
6.1. Position du problème . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
6.2. Equivalence entre le problème d’optimisation et un système linéaire . . 92
6.3. Cas d’une matrice symétrique positive mais non définie . . . . . . . . . 93
6.3.1. Procédé de Schmidt pour orthogonaliser . . . . . . . . . . . . . . 94
6.3.2. Construction d’un algorithme de résolution du système linéaire
lorsqueA est singulière . . . . . . . . . . . . . . . . . . . . . . . . 94
6.4. L’algorithme du gradient . . . . . . . . . . . . . . . . . . . . . . . . . . 95
6.5. Convergence de l’algorithme du gradient . . . . . . . . . . . . . . . . . 97Table des matières 7
6.5.1. Convergence du gradient à pas optimal . . . . . . . . . . . . . . . 98
6.5.2. Convergence du à pas constant . . . . . . . . . . . . . . . 99
6.6. Le gradient conjugué . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
6.6.1. Description de l’algorithme . . . . . . . . . . . . . . . . . . . . . . 100
6.6.2. Analyse de la méthode du gradient conjugué . . . . . . . . . . . . 101
6.7. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
Chapitre 7. Optimisation de fonctions convexes . . . . . . . . . . . . . . . . 105
7.1. Rappels sur les fonctions convexes . . . . . . . . . . . . . . . . . . . . . 105
7.2. Algorithme du gradient à pas constant pour minimiser une
fonctionnelle convexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
7.3. Algorithme de Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
7.4. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
Chapitre 8. Prise en compte des contraintes linéaires . . . . . . . . . . . . . 117
8.1. Existence et unicité d’une solution . . . . . . . . . . . . . . . . . . . . . 117
8.2. Caractérisation de la solution de (8.1) . . . . . . . . . . . . . . . . . . . 118
8.2.1. Projection orthogonale surKer(B) . . . . . . . . . . . . . . . . . 118
8.3. Construction de la projectionP . . . . . . . . . . . . . . . . . . . . . 121K
8.4. Introduction de la dualité . . . . . . . . . . . . . . . . . . . . . . . . . . 123
8.5. Une interprétation du système dual . . . . . . . . . . . . . . . . . . . . 124
8.5.1. La méthode d’Uzawa . . . . . . . . . . . . . . . . . . . . . . . . . 124
8.5.2. La d’Uzawa régularisée . . . . . . . . . . . . . . . . . . . 127
8.5.3. L’algorithme d’Arrow-Urwicz . . . . . . . . . . . . . . . . . . . . 129
8.6. La pénalisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
8.7. La méthode de Tychonov . . . . . . . . . . . . . . . . . . . . . . . . . . 133
8.7.1. Remarques préliminaires . . . . . . . . . . . . . . . . . . . . . . . 133
8.7.2. Construction d’un développement asymptotique . . . . . . . . . . 134
8.7.3. Etude de l’erreur . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
08.7.4. Propriété dex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
8.8. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
Chapitre 9. Quelques remarques sur la programmation linéaire . . . . . . 139
9.1. Un premier exemple intuitif . . . . . . . . . . . . . . . . . . . . . . . . . 139
9.2. Un second exemple plus complexe . . . . . . . . . . . . . . . . . . . . . 144
9.3. Cas général de l’algorithme décrit sur l’exemple de la section 9.2 . . . 146
9.3.1. Principe du simplexe . . . . . . . . . . . . . . . . . . . . . . . . . 146
9.3.2. Quelques remarques théoriques . . . . . . . . . . . . . . . . . . . 147
9.3.3. L’algorithme du simplexe . . . . . . . . . . . . . . . . . . . . . . . 148
9.4. Remarque sur la convergence . . . . . . . . . . . . . . . . . . . . . . . . 149
9.5. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1498 Méthodes numériques pour l’ingénieur
Chapitre 10. Optimisation de fonctionnelles non différentiables . . . . . . . 151
10.1. Le problème initial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
10.2. Analyse du problème posé lorsqueA est définie . . . . . . . . . . . . . 152
10.2.1. La fonctionnelle est strictement convexe . . . . . . . . . . . . . . 152
10.2.2. LaeJ est coercive . . . . . . . . . . . . . . . . . . . 152
10.2.3. Décentralisation partielle de la fonctionnelle . . . . . . . . . . . . 152
10.2.4. Non convexité du terme de degré un . . . . . . . . . . . . . . . . 153
10.2.5. Non coercivité des termes de degré un . . . . . . . . . . . . . . . 153
10.2.6.J n’est pas dérivable . . . . . . . . . . . . . . . . . . . . . . . . . 154
10.2.7. Existence et unicité de solutions sous conditions . . . . . . . . . 154
10.3. Régularisation du problème non dérivable . . . . . . . . . . . . . . . . 156
10.3.1. Calcul de la dérivée Gâteaux deJ . . . . . . . . . . . . . . . . . 157
10.3.2. Analyse du problème d’optimisation régularisé . . . . . . . . . . 158
10.3.3. Etude de l’équation d’Euler du modèle . . . . . . . . . 159
10.4. Algorithme de résolution du type gradient . . . . . . . . . . . . . . . . 161
10.5. Une méthode de dualité pour le problème initial (10.2) . . . . . . . . . 163
10.6. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
Chapitre 11. Optimisation convexe avec contraintes . . . . . . . . . . . . . . 167
11.1. Existence et unicité de solution . . . . . . . . . . . . . . . . . . . . . . 167
11.2. Caractérisation des solutions . . . . . . . . . . . . . . . . . . . . . . . . 168
11.3. Projection sur le convexeK . . . . . . . . . . . . . . . . . . . . . . . . 169
11.4. L’algorithme du gradient projeté . . . . . . . . . . . . . . . . . . . . . . 169
11.5. Introduction de la dualité . . . . . . . . . . . . . . . . . . . . . . . . . . 171
11.5.1. Formalisme théorique . . . . . . . . . . . . . . . . . . . . . . . . . 171
11.5.2. Algorithme d’Uzawa . . . . . . . . . . . . . . . . . . . . . . . . . 174
11.6. La méthode de pénalisation . . . . . . . . . . . . . . . . . . . . . . . . 175
11.7. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
Chapitre 12. Introduction au contrôle optimal . . . . . . . . . . . . . . . . . 177
12.1. Un problème modèle . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
12.2. Quelques résultats mathématiques utiles . . . . . . . . . . . . . . . . . 179
12.3. Calcul de la dérivée Gâteaux deJ . . . . . . . . . . . . . . . . . . . . 182
12.4. Relation d’optimalité . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
12.5. Méthodes de calcul du contrôle optimal . . . . . . . . . . . . . . . . . 183
12.5.1. Algorithme du gradient à pas constant . . . . . . . . . . . . . . . 184
12.5.2. Résolution par la méthode de Riccati . . . . . . . . . . . . . . . . 184
12.6. Passage à la limite lorsque"! 0 . . . . . . . . . . . . . . . . . . . . . 186
12.6.1. Une méthode asymptotique . . . . . . . . . . . . . . . . . . . . . 186
12.6.2. Résultat de convergence . . . . . . . . . . . . . . . . . . . . . . . 190
12.7. Résolution approchée du modèle de contrôle optimal . . . . . . . . . . 191
12.8. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192Table des matières 9
TROISIÈME PARTIE. DONNÉES INCERTAINES . . . . . . . . . . . . . . . . . 193
Chapitre 13. Prise en compte de certaines incertitudes . . . . . . . . . . . . 195
13.1. Position des problèmes à résoudre . . . . . . . . . . . . . . . . . . . . . 195
13.2. Principe du maximum pour les matrices . . . . . . . . . . . . . . . . . 197
13.3. Cas de lois gaussiennes . . . . . . . . . . . . . . . . . . . . . . . . . . . 201
13.3.1. Intervalle d’incertitude . . . . . . . . . . . . . . . . . . . . . . . . 204
13.4. Indépendance des variables aléatoires . . . . . . . . . . . . . . . . . . . 204
13.5. Cas où la matrice est aléatoire . . . . . . . . . . . . . . . . . . . . . . . 210
13.6. Estimation statistique des lois de probabilité . . . . . . . . . . . . . . . 212
13.7. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213
QUATRIÈME PARTIE. PROBLÈMES ET EXERCICES . . . . . . . . . . . . . 215
Chapitre 14. Problème de synthèse . . . . . . . . . . . . . . . . . . . . . . . 217
14.1. Un problème sur l’optimisation non différentiable . . . . . . . . . . . . 217
14.1.1. Le problème initial . . . . . . . . . . . . . . . . . . . . . . . . . . 217
14.1.2. Difficultés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217
14.1.3. Régularisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218
14.1.4. Algorithme de résolution . . . . . . . . . . . . . . . . . . . . . . . 219
Chapitre 15. Examens proposés à différentes sessions . . . . . . . . . . . . . 221
15.1. Examen de la première session 2005-2006 . . . . . . . . . . . . . . . . 221
15.2. de la 2007-2008 . . . . . . . . . . . . . . . . 224
15.3. Examen de la seconde session . . . . . . . . . . . . . . . . 228
15.4. de la première 2008-2009 . . . . . . . . . . . . . . . . 230
15.5. Examen de la session 2009-2010 . . . . . . . . . . . . . . . . 232
15.6. de la seconde . . . . . . . . . . . . . . . . 235
Chapitre 16. Quelques exercices proposés en cours . . . . . . . . . . . . . . 237
Bibliographie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245
Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247Avant-propos
Il y a un siècle, les mathématiciens travaillaient à trouver des solutions analytiques
aux équations proposées par les physiciens et les mécaniciens. Parfois, la complexité
de ces était telle, qu’ils mirent beaucoup d’énergie à simplifier ces modèles
afin d’en obtenir des plus simples pour lesquels les outils disponibles, en particulier
l’analyse complexe, pouvaient fonctionner. Ces apports considérables ont constitué le
fond de roulement de l’ingénieur de bureau d’étude. Cependant, ils se sont vite
révélés insuffisants et ce n’est qu’avec l’apparition des premiers calculateurs au milieu
du XXième siècle, qu’une autre voie beaucoup plus prometteuse et complémentaire,
a vu le jour : c’est l’analyse numérique. Les premiers problèmes furent obtenus par
discrétisation d’équations aux dérivées partielles en utilisant la célèbre méthode des
différences finies. Cela permit de se ramener à la résolution d’un système matriciel.
Très vite, les limites de cette méthode sont apparues principalement en raison des
géométries complexes, des milieux hétérogènes et des conditions aux limites variées que
l’ingénieur souhaitait introduire dans ses modèles. L’arrivée de la méthode des
éléments finis a alors apporté une solution efficace et agréable à tous ces problèmes et
a transformé tous les modèles d’équations aux dérivées partielles de la physique en
systèmes matriciels (linéaires ou non) mais qui, bien entendu, demeurent une
approximation du modèle continu. L’objet de cet ouvrage est de donner les principales
méthodes dont dispose le scientifique pour résoudre ces systèmes.Chapitre 1
Introduction générale
Ce chapitre est consacré à une présentation rapide des méthodes numériques qui sont
étudiées en détail dans ce cours. Nous y donnons une approche très simplifiée des
quatre parties qui sont abordées :
– larésolution dessystèmeslinéaires,
– le calculdesvaleurspropresdesmatrices,
– l’optimisation,
–lecontrôledessystèmeslinéaires.
1.1. La résolution des systèmes linéaires
Désignons parA une matrice carréeNN à coefficients réels etb un vecteur de
NR . On s’intéresse à l’équation vectorielle suivante :
Ntrouver X2R tel que :AX =b: (1.1)
L’algèbre matricielle nous apprend que (1.1) admet une solution unique dès que le
déterminant (notédetA) de la matriceA est non nul.
Une première stratégie consiste à utiliser la méthode des cofacteurs. Mais le nombre
d’opérations nécessaires est tellement élevé dès que l’on dépasse la dimensionN = 3,
qu’il faut très vite oublier cette méthode. En effet, pour calculer un déterminant d’une
matriceNN il fautN:N! multiplications !
Une seconde approche conduit aux méthodes directes. Pour cela on décompose (c’est
la factorisation) la matriceA en la composée de deux matrices notées respectivement6
14 Méthodes numériques pour l’ingénieur
L (Lower) etU (Upper) de telle sorte queA = LU et queL soit une matrice
triangulaire inférieure régulière etU une matrice triangulaire supérieure qui est également
régulière. Le système (1.1) est alors équivalent au suivant :

NTrouverY 2R ; solution de :LY =b;
(1.2)Npuis résoudreX2R UX =Y:
Le secret de la méthode est qu’un système linéaire associé à une matrice
triangulaire est facile à résoudre. Pour cela, on procède par substitutions successives en
partant de la première ou de la dernière équation suivant qu’il s’agisse d’une matrice
triangulaire inférieure ou supérieure. Toutes les méthodes qui découleront de cette
stratégie s’appellent les méthodes de Gauss et leurs variantes (Crout, Cholesky . . . ).
Une autre approche de la résolution des systèmes linéaires consiste à construire une
suite d’approximation qui converge vers la solution. Pour en donner une idée simple
mais réaliste, considérons un cas élémentaire, celui de la règle de trois. Il s’agit de :
trouverx2R; tel que ax =b oùa = 0 etb sont deux réels donnés. (1.3)
Bien entendu, la solution estx =b=a. Mais intéressons-nous à la construction d’une
suitex qui converge vers cette solution. Pour cela nous observons tout d’abord quen
la solutionx vérifie :
8%2R; x =x %(ax b): (1.4)
L’idée est par exemple de proposer un algorithme de point fixe en construisant la suite
nx de la façon suivante :
n+1 n n 0
x =x %(ax b); x étant donné: (1.5)
nMontrons que si% est astucieusement choisi, la suitex converge géométriquement
n nversx. Introduisons les variables d’écartx =x x. Elles vérifient :
n+1 nx = (1 %a)x : (1.6)
Soit :
n+1 n n+1 0jx jj1 %ajjx jj1 %aj jxj: (1.7)
Par conséquent, nous sommes assurés de la convergence dès que% vérifie la double
inégalité qui assure que le coefficient 1 %a soit en module strictement inférieur à
l’unité :
0<a%< 2: (1.8)
Par ailleurs, on notera que l’erreur est d’autant plus petite à même nombre d’itérations
0que l’on part proche de la solution (jxj petit). En outre, l’erreur diminue à chaque
itération. On parle alors de méthodes auto-correctives.Introduction générale 15
y
o xn xn+1 xn+2 x
Figure 1.1. Schéma de l’algorithme itératif pour systèmes linéaires
La figure 1.1 illustre la méthode que nous venons de décrire et qui contient les idées
fondamentales d’un grand nombre de méthodes itératives pour résoudre les systèmes
linéaires. Si nous revenons au cas de l’équation (1.1), l’analogue de l’algorithme que
nous venons de décrire est :
n N n+1 n n 0 NX 2R ; X =X %(AX b); X donné dansR . (1.9)
Il s’agit en fait d’une méthode de gradient lorsque A est une matrice symétrique.
Elle permet de rechercher le minimum de la fonction ((:;:) est le produit scalaireN
Neuclidien dansR etjj:jj est la norme associée) :N
1NX2R ! (AX;X) (b;X) ;N N
2
NdansR lorsqueA est aussi définie positive (c’est-à-dire que toutes ses valeurs propres
sont strictement positives).
1.2. Le calcul des valeurs propres des matrices
Prenons l’exemple de la figure 1.2. Il s’agit d’un enfant jouant avec un POGO
stick. La flexibilité de ce dernier est modélisée par un ressort de raideurk et sa masse2
est M. L’enfant a une masse m et la flexibilité de ses jambes est représentée par
un ressort de raideurk . Notonsx (respectivementx ), le déplacement de l’enfant1 1 2
(respectivement celui du POGO stick). Les équations du mouvement données par la6
6
16 Méthodes numériques pour l’ingénieur
x1 Enfantm
k1
x2 M POGO stick
k2
Figure 1.2. Enfant + POGO stick
mécanique sont les suivantes :

m x = k (x x );1 1 1 1 2
(1.10)
m x = k (x x ) k x :2 2 1 2 1 2 2
On peut écrire ce système différentiel sous forme matricielle en posant :

m 0 k k1 1 1X + X = 0; (1.11)
0 m k k +k2 1 1 2
avec la notation :
x x1 1X = ; X = : (1.12)
x x2 2
On recherche alors des solutions harmoniques (dites stationnaires) de cette
équation différentielle matricielle en posant a priori :
i t^ ^X =Xe ; 2R; X = 0:
Les solutions éventuelles seront des fonctions sinus et cosinus du temps à la
pulsation . En reportant dans l’équation (1.11), on obtient un problème aux valeurs
propres :
2 + 2^ ^ ^ ^trouver = 2R ; X2R ; X = 0 tels que : M X =KX; (1.13)6
6
Introduction générale 17
où :
m 0 k k1 1 1
M = K = : (1.14)
0 m k k +k2 1 1 2
2 ^Ainsi = est la valeur propre etX le vecteur propre. Par ailleursM est la matrice
de produit scalaire. Notons que les deux matricesM etK sont symétriques et définies
positives (exercice). Le problème (1.13) est équivalent au suivant :
+ 2 1^ ^ ^ ^trouver2R ; X2R ; X = 0 tels que :X =M KX: (1.15)
1Cependant la matriceM K qui intervient, n’est plus symétrique. Cette formulation
n’est donc pas recommandée, car les matrices symétriques ont des avantages
considérables, ne serait-ce que par le gain en stockage qu’elles permettent. On préfère donc
la formulation qui suit. Posons :
p
m 011=2 1=2 2D = p et donc : (D ) =D =M; (1.16)
0 m2
puis :
1=2 1=2^ ^ ^ ^X =D Y; Y =D X (1.17)
1=2 1=2(D est l’inverse deD ), notre problème (1.13) est maintenant équivalent à :
+ 2 1=2 1=2^ ^ ^ ^trouver2R ; Y 2R ; Y = 0 tels que :Y =D KD Y: (1.18)
1=2 1=2La matriceA =D KD est cette fois symétrique et cela nous facilitera le
travail. Nous verrons deux types d’approches pour calculer les éléments propres d’une
telle matrice : les méthodes globales avec lesquelles on calcule toutes les valeurs et
les vecteurs propres et les méthodes sélectives, qui permettent de choisir un nombre
donné de valeurs et de vecteurs propres en fonction de la valeur propre qui nous
intéresse. Donnons-en une idée sur le petit modèle que nous avons introduit ici.
1.2.1. La méthode globale de Jacobi
Plaçons-nous dans le plan rapporté au système d’axes orthonormés (o;e ;e ) et1 2
considérons une rotation d’angle qui transforme les vecteurs de base (e ;e ) en1 2
(E ;E ). Nous avons les relations :1 2

E = cos()e + sin()e ;1 1 2 (1.19)
E = sin()e + cos()e2 1 2
La matrice de changement de base qui permet d’exprimer les coordonnées :
X = (x ;x )1 26
18 Méthodes numériques pour l’ingénieur
dans la base (o;e ;e ) en fonction de celles notéesY = (y ;y ) dans la nouvelle base1 2 1 2
(o;E ;E ) estP avec :1 2

cos() sin()
P = ; X =P Y Y =P X: (1.20)
sin() cos()
Le problème de la recherche des valeurs propres de la matrice symétriqueA définie
plus haut, est donc équivalent à :
+ 2^ ^trouver2R ; Y 2R ; Y = 0 tels que :
(1.21)
^ ^ ^Y =P AP Y =A Y;
soit, après un simple calcul (on posec = cos() ets = sin(), les coefficients deA
étant notésa ) :ij

2 2 2 2c a + 2sca +s a ); cs(a a ) + (c s )a11 12 22 22 11 12A = (1.22)2 2 2 2cs(a a ) + (c s )a ; c a +s a 2sca22 11 12 22 11 12
En choisissant l’angle tel que :
2 2(c s )a =cs(a a );12 11 22
on rend la matriceA diagonale et les valeurs propres sont sur la diagonale de cette
nouvelle matrice. Les vecteurs propres se déduisent sans difficulté. Or la relation
précédente est équivalente à :
2a12
tan(2) = :
a a11 22
Soit :
1 2a 12
= arctan( ) +k ; k2Z:
2 a a 211 22

Sia =a on choisit = .11 22
4
A titre d’exercice le lecteur pourra appliquer cette méthode à notre petit problème
avec les données suivantes :
m = 1 =m ; k =k =k:1 2 1 2
Il comparera pour se rassurer avec un calcul direct des valeurs propres en annulant le
déterminant de la matriceA I qu’il explicitera.6
6
Introduction générale 19
1.2.2. La méthode sélective de la puissance itérée
On sait qu’une matrice symétrique est diagonalisable dans une base de vecteurs
propres orthonormés. C’est l’un des résultats fondamentaux de l’algèbre matricielle
que nous utiliserons souvent dans ce cours. Désignons parW etW (respectivement1 2
et ), les deux vecteurs propres (respectivement les deux valeurs propres), de la1 2
matriceA. Considérons ensuite une suite de vecteurs construite de la façon suivante
((:;:) est le produit scalaire etjj:jj la norme associée) :N N
n+1=2Xn+1=2 n n+1 n n+1=2 n 0X =AX ; X = ; = (X ;X ) ; X donné:Nn+1=2jjX jjN
Suppposons que > (elles sont toutes deux strictement positives puisque la1 2
0matriceA est définie positive) et que (X ;W ) = 0. Posons :1 N
0 0 0X = W + W ; où : = (X ;W ) ; = (X ;W ) ; = 0: (1.23)1 1 2 2 1 1 N 2 2 N 1
On a alors par un simple calcul :
2n+1 2n+12n+1 0 0 2 2(A X ;X ) + Nn 1 1 2 2 = = : (1.24)2 2n 2 2n 20jjAX jj + N 1 1 2 2
On peut aussi écrire :
2 22n+1 21 + ( ) ( )
n 1 1 1 = [ ]! : (1.25)n!1 1 2 22n 21 + ( ) ( )
1 1
nLa suite converge donc vers la plus grande valeur propre de A. De façon
siminlaire, on établit que la suite de vecteurs X converge versW (suivant le signe1
du coefficient ). Nous verrons alors que cette méthode peut permettre de calculer1
les valeurs propres et les vecteurs propres associés, voisines d’une valeur donnée à
l’avance. On parle alors de méthode du shift (décalage). On peut aussi travailler avec
plusieurs vecteurs itérés : c’est l’algorithme de la puissance itérée sur un sous-espace.
Bien d’autres variantes seront discutées pour cette méthode qui a, en général, la faveur
des ingénieurs de bureaux d’études.
1.3. L’optimisation
ConsidéronsN points distincts, classés par ordre croissant et notésx et autant dei
valeurs désignées pary . Désignons parfpg; k = 1;P , un ensemble deP fonctionsi k
définies aux pointsx . On se pose le problème de lissage suivant :i
X X
2min J(a); oùJ(a) = j a p (x ) yj ; (1.26)k k i i
Pa=fa g2Rk
i=1;N k=1;P6
6
6
20 Méthodes numériques pour l’ingénieur
PLa solution ena2R permet de définir une fonction :
X
p(x) = a p (x);k k
k=1;P
qui passe au mieux (au sens des moindres carrés), par les valeursy auxN pointsx .i i
C’est le problème classique du lissage. Examinons rapidement quelques-unes de ses
propriétés.
Pour cela commençons par le cas où les fonctionsfpg sont les polynômes dek
degrés inférieurs ou égal àN 1. La dimension de cet espace de polynômes est bien
N, nous avons donc dans ce cas :N = P . On construit ensuite lesN polynômes de
Lagrange notés ; k = 1;N valant respectivement 0 au pointsx ; j2f1;Ng; j =k j
k et 1 enx . Un calcul classique nous donne :k
(x x )i=1;N;i=k i
( x) = : (1.27)
(x x )i=1;N i=k k i
Considérons ensuite le polynôme :
X
p(x) = y (x): (1.28)k k
k=1;N
Il vaut exactement y aux points x pour i = 1;N. Choisissons alors pour a lesi i k
kcoefficients des monômesx dans l’expression dep. La fonctionnelleJ(a) s’annule.
Comme elle est positive, on a trouvé un minimum. C’est bien le seul possible dans
Nl’ensemble de recherche. En effet, supposons qu’il en existe un autre - soitb2R -
P
ket notonsq(x) = b x le polynôme associé. On aurait :kk=1;N
r(x ) =p(x ) q(x ) = 0 8i = 1;N:i i i
Par conséquent, le polynômer qui est de degréN 1 s’annule enN points distincts.
En d’autres termes il admet en facteur un polynôme de degréN et donc est nul ! Ceci
prouve l’unicité.
Plaçons-nous maintenant dans un cas moins évident. Supposons que P < N et
considérons un ensemble de P fonctions définies aux points x . Nous faisons unei
Nhypothèse de qualification sur lesP vecteursX =fp (x )g2R ; i = 1;N. Nousk k i
Psupposons qu’ils sont linéairement indépendants. Sia2R réalise le minimum de la
fonctionJ. Nous avons par exemple :
8k2f1;Pg;8b 2R; b = (a ;a ;:::;a ;b ;a ;:::a );k 1 2 k 1 k k+1 P
(1.29)
J(a)J(b):
En explicitant, l’expression deJ(b) en fonction deb nous obtenons un polynôme duk
second degré de la forme :
2J(b) =A b + 2B b +C ;k k k kk6
Introduction générale 21
dont le minimum est atteint ena de telle sorte que :k
A a +B = 0:k k k
Explicitons les coefficientsA etB . Nous obtenons ainsi :k k
X X X X
2A = p (x ) ; B = a p (x )p (x ) y p (x ):k k i k j k i j i i k i
i=1;N j=1;N;j=ki=1;N i=1;N
Le vecteura est donc solution du système matriciel suivant :
Qa =d
avec :
0 P P 1
2p (x ) : p (x )p (x ) ::::1 i 1 i 2 ii=1;N i=1;NP
@ AQ = p (x )p (x ) :::: :::: (1.30)1 i 2 ii=1;N P
2:::: ::::: p (x )N ii=1;N
P0 1
y p (x )i 1 ii=1;NP
B Cy p (x )i 2 ii=1;NB C
B C:B C
B C:B C
B Cd = : (1.31)B CPB Cy p (x )i k iB i=1;N C
B C:B C
@ A:
:
La matrice Q = (q ) est manifestement symétrique. En fait, nous allons voir quekl
grâce à l’hypothèse de qualification énonçée précédemment elle est aussi définie
positive. Ceci nous permettra aussi d’assurer qu’elle est inversible. Désignons parq leskl
Pcoefficients de la matriceQ. NotonsZ =fzg un vecteur deR . Considérons ensuitek
l’expression (forme quadratique associée àQ) :
X X X
(QZ;Z) = z zq = z zp (x )p (x );k l kl k l k i l i
i=1;Nk;l=1;P k;l=1;P
qui est aussi égale à : X X
2
[ z p (x )] 0:k k i
i=1;N k=1;P
Par conséquentQ est positive. Par ailleurs si :
X
z p (x ) = 0;k k i
k=1;P22 Méthodes numériques pour l’ingénieur
alors l’hypothèse de qualification (indépendance linéaire des vecteurs p (x )), nousk i
permet d’assurer que :
8k = 1;N; z = 0k
et par conséquent la matrice Q est bien définie positive. Toutes ses valeurs propres
sont strictement positives et donc elle est inversible. Ainsi le problème de lissage que
nous avons envisagé est bien posé et se ramène à la résolution d’un système linéaire
qui de plus est associé à une matrice symétrique définie positive.
Remarque 1.3.1 Le choix de la fonctionnelle à minimiser que nous avons retenue
dans cet exemple est arbitraire et relève de l’intuition de l’ingénieur. Néanmoins, les
critères quadratiques présentent l’immense avantage de conduire à des systèmes
linéaires. Cela justifie leur importance dans les problèmes d’optimisation.
Remarque 1.3.2 Dans ce second exemple rien ne garantit que les valeurs de la
foncP
tion lissée :p = a p prennent les valeursy aux pointsx . Mais on peutk k i ik=1;P
décider par exemple d’un intervalle autorisé autour de ces valeurs. Par exemple de la
forme suivante :
8i2f1;Ng; y " p(x )y +" ; (1.32)i i i i i
où" sont des tolérances fixées par des considérations liées au problème à résoudre.i
On obtient alors un nouveau problème d’optimisation avec des contraintes. Nous
verrons comment procéder pour résoudre ce type de problèmes dits sous contraintes dans
la partie consacrée à l’optimisation.
1.4. Le contrôle des systèmes linéaires
Considérons l’équation différentielle suivante qui par exemple modélise
l’évolution de la températureT (mesurée par rapport à la température extérieure) en un point
donné d’une pièce etc représente la quantité de chaleur apportée par le chauffage. Le
coefficientk représente les fuites thermiques dues à une mauvaise isolation etT est0
la température initiale.
_T (t) +kT (t) =c(t); 8t> 0; T (0) =T : (1.33)0
Si on ne fait rien, c’est-à-dire c 0, la température évolue comme indiqué sur la
figure 1.3. La solution analytique est :
ktT (t) =T e : (1.34)0
Imaginons maintenant qu’à l’instantt , la température atteigne la valeurT <T (ce1 1 0Introduction générale 23
20
15
10
5
0
0 2 4 6 8
t
Figure 1.3. Evolution de la température sans chauffage en fonction du temps
Log(T =T )1 0
qui donnet = ) et qu’un thermostat mette le chauffage en route. On1
k
suppose l’apport de chaleur constant :
c(t) =c :0
La solution de l’équation (1.33) est :
c0k(t t ) k(t t )1 1T (t) =T e + [1 e ]: (1.35)1
k
Elle est représentée sur la figure 1.4.
Dans un processus de régulation automatique, le thermostat arrêtera
automatique0ment le chauffage dès que la température sera repassée au-dessus deT (valeur 200
sur la figure 1.4 correspondant à un temps t ’ 3:7heures). Mais bien entendu, le2
temps de marche du chauffage dépend de la puissance de chauffec et du coefficient0
de pertek. Par exemple sic kT il sera impossible de réchauffer la pièce. C’est0 1
ainsi que pour une chaudière donnée (puissance fixée par le constructeur), le seuil de
c0
déclenchement devra être tel queT > . Sinon le coefficient de l’exponentielle est1
k
négatif et la température demeure décroissante (voir figure 1.5). Par ailleurs, pour que
0l’asymptote soit au-dessus de la température de 20 , de façon à revenir en un temps
c0 0fini à la température de départ, il faut que : > 20 . La figure 1.6 montre le
comk
portement de la température dans le cas où cette condition supplémentaire ne serait
pas vérifiée. On se pose alors le problème suivant : comment choisir T de façon à1
minimiser le coût du chauffage qui est de la forme (t t )c ?2 1 0