Méthodes numériques et optimisation
Théorie et pratique pour l'ingénieur

Sommaire et contenu du livre "Méthodes numériques et optimisation - Théorie et pratique pour l'ingénieur"

Table des matières


1 Interpolation et approximation 1

1.1
Approximation d'une fonction par une autre fonction. 1

1.1.1
Fonctions d'approximation ..... 1

1.1.2
Approximation polynomiale. . . . . . 2

1.2
Détermination des polynômes d'interpolation 3

1.2.1
Calcul du polynôme d'interpolation 3

1.2.2
Polynôme d'interpolation de Newton. 4

1.2.3
Polynôme d'interpolation de Lagrange 8

1.2.4
Interpolation polynomiale avec des points régulièrement es­pacés 9

1.2.5
Polynômesde Hermite. .................. .. 12

1.2.6
Polynômes de Chebyshev et points irrégulièrement espacés 14

1.2.7
Interpolation par fonctions splines 19

1.2.8
Interpolation par des courbes splines paramétriques 25

1.3
Courbes de Bézier .. 26

1.4
Discussion et conclusion 27

2 Intégration numérique 29

2.1
Formules d'intégration de Newton et Cotes fermées 29

2.1.1
Intégration globale sur l'intervalle [a, b] ... 29

2.1.2
Intégration sur des sous-intervalles . . . . 32

2.2
Formules d'intégration de Newton et Cotes ouvertes 34

2.3
Conclusions sur les formules d'intégration de Newton et Cotes. 35

2.4
Intégration répétée par dichotomie et intégration de Romberg 35

2.5
Intégration numérique avec des points irrégulièrement espacés 38

2.5.1
Rappels sur les polynômes orthogonaux 39

2.5.2
Quadrature de Gauss-Legendre 42

2.5.3
Quadrature de Gauss-Laguerre 46

2.5.4
Quadrature de Gauss-Chebyshev 46

2.5.5
Quadrature de Gauss-Hermite 46

2.6
Discussion et conclusion . . . . . . . . . 47

3 Résolution d'équations par des méthodes itératives 49

3.1
Méthode de Graeffe 49

3.2
Méthode de Bernoulli 51

3.3
MéthodedeBairstow: . . . . . . . . . 54

3.4
Méthode des substitutions successives 57

3.5
Méthode de Newton et méthodes dérivées 60

3.5.1
Méthode de Newton . 60

3.5.2
Méthode de la sécante . . . 63

3.6
Méthodes de dichotomie et regula falsi 63

3.6.1
Méthode de dichotomie 64

3.6.2
Méthode regula falsi 66

3.7
Méthode d'Aitken 66

3.8
Méthode d'homotopie ... 68

3.8.1
Introduction 68

3.8.2
Méthode de continuation 68

3.9
Discussion et conclusion ..... 72

4 Opérations numériques sur les matrices 75

4.1
Introduction . 75

4.2
Rappels sur les matrices . 75

4.3
Rappels sur les vecteurs . . . . . . 77

4.4
Transformations linéaires et sous-espaces. 79

4.4.1
Théorème de Gershgorin . 81

4.4.2
Théorème de Cayley-Hamilton et conséquences 82

4.4.3
Méthode de puissance . 83

4.5
Matrices semblables et polynômes de matrices . 85

4.6
Matrices symétriques et matrices hermitiennes .. 85

4.7
Réduction de matrices sous une forme plus simple 90

4.8
Méthode LR de Rutishauser. 91

4.9
Méthode de Householder. 95

4.10
Méthode QR de Francis 99

4.11
Discussion et conclusion . 109

5 Résolution des systèmes d'équations algébriques 111

5.1
Introduction................... 111

5.2
Résolution de systèmes linéaires triangulaires 111

5.3
Résolution de systèmes linéaires: méthode
d'élimination de Gauss. . . . . . . . 112

5.4
Calcul du déterminant d'une matrice 119

5.5
Algorithme de Gauss-Jordan 120

5.6
Factorisation LDLT ......... 123

5.7
Décomposition de Cholesky . . . . . 124

5.8
Décomposition en valeurs singulières 125

5.9
Méthode des moindres carrés pour les systèmes linéaires sur-déterminés127
5.10
Résolution itérative de grands systèmes linéaires (Jacobi, Gauss­
Seidel)................................ .. 129

5.11
Résolution de systèmes linéaires: cas d'une matrice tridiagonale . 133

5.12
Résolution de systèmes non linéaires: méthode de Newton-Raphson 134

5.13
Résolution de systèmes non linéaires par optimisation 137

5.14Discussionetconclusion
..................... .. 137

6 Intégration numérique des équations différentielles ordinaires 139

6.1
Introduction......................... 139

6.1.1
Equations différentielles linéaires et non-linéaires 140

6.1.2
Unicité de la solution 141

6.2
Problèmesàvaleur initiale. . . . . . . . . . . . . . . . . 141

6.2.1 Méthodes à un pas . 142
6.2.2 Méthodes à pas multiples . 157
6.2.3 Formules d'intégration ouvertes. 157
6.3 Stabilité des méthodes d'intégration numérique 164
6.4 Casdessystèmesraides . . . . . . . . . . . . 167
6.5 Systèmes algébro-différentiels . 168
6.6 Equations différentielles à frontières multiples 170
6.7 Discussion et conclusion . 170
1 Intégration numérique des équations aux dérivées partielles 113
7.1 Quelques exemples de systèmes physiques . 173
7.1.1 Transfert de chaleur par conduction 173
7.1.2 Transfert de matière 175
7.1.3 Equationdesondes. . . . . . . . . . 175
7.1.4 EquationdeLaplace . . . . . . . . . 175
7.2 Propriétés des équations aux dérivées partielles 176
7.2.1 Généralités . . . . . 176
7.2.2 Problème bien posé 177
7.2.3 Classification.... 178
7.2.4 Caractérisation des solutions 178
7.2.5 Méthode des caractéristiques 179
7.3 Méthode des différences finies 188
7.3.1 Préambule........... 188

7.3.2 Discrétisation......... 189

7.4 Calcul automatique des dérivées partielles 205
7.4.1 Calcul de (~)o et (~) N .. 206
7.4.2 Calcul de (2) et (2) 207
ox 0 ox N
7.5 Méthodedeslignes ........... 207

7.5.1 Cas de conditions aux limites de Dirichlet 208
7.5.2 Cas de conditions aux limites de Neumann 208
7.5.3 Simulation d'un échangeur de chaleur 209
7.6 Méthode des volumes finis 213
7.6.1 Introduction 213
7.6.2 Maillage...... 213
7.6.3 Intégration sur un volume de contrôle quelconque. 215
7.6.4 Prise en compte des conditions aux limites à gauche 217
7.6.5 Prise en compte des conditions aux limites à droite. 218
7.6.6 Cas de deux milieux solides en contact et de conductivités différentes......... 219
7.6.7 Résolution numérique . . . . . . . 220
7.6.8 Problème bi-dimensionnel . . . . . 223
7.6.9 Extension au cas des écoulements. 224
7.6.10 Conservation appliquée à un volume de contrôle 225
7.6.11 Algorithme SIMPLER 226
7.7 Discussionetconclusion .................. 227

8 Méthodes analytiques d'optimisation 229

8.1
Quelques rappels mathématiques 229

8.2
Introduction.......... 230

8.3
Fonctions d'une seule variable 231

8.3.1
Intervalle infini . . . . 231

8.3.2
Intervalle fini . . . . . 234

8.3.3
Présence de discontinuités 235

8.4
Fonctions de plusieurs variables 235

8.4.1
Intervalle infini . . . . . . 235

8.4.2
Intervalle fini . . . . . . . 236

8.4.3
Présence de discontinuités 236

8.5
Fonction soumise à des contraintes d'égalité 236

8.5.1
MéthodedeJacobi . . . . . . . . . . 236

8.5.2
Multiplicateurs de Lagrange. . . . . 238

8.5.3
Signification des multiplicateurs de Lagrange 240

8.5.4
Conditionsdeminimum . . . . . . . . . . . . 240

8.5.5
Conditions de minimum par le gradient projeté dans le cas
de contraintes d'égalité 240

8.6
Fonction soumise à des contraintes d'inégalité 245

8.6.1
Utilisation de fonctions d'écart . . . . 245

8.6.2
Paramètres de Kuhn-Thcker . . . . . . 246

8.6.3
Conditions de minimum par le gradient projeté dans le cas
de contraintes d'inégalité 250

8.7
Fonction soumise à des contraintes d'égalité et d'inégalité 255

8.8
Analyse de sensibilité. . 256

8.9
Discussion et conclusion . . . . . . . . 258

9 Méthodes numériques d'optimisation 259

9.1
Fonctions d'une seule variable. 259

9.1.1
Méthode de dichotomie 259

9.1.2
Méthode de Newton . . 261

9.1.3
Méthode de Fibonacci . 262

9.2
Fonctions de plusieurs variables 264

9.2.1
Méthodes de recherche directe 265

9.2.2
Recherche simple monovariable 265

9.2.3
Méthode du simplexe .... 265

9.2.4
Méthodes d'accélération . . . 267

9.2.5
Méthode du complexe de Box 271

9.2.6
Algorithme génétique .... 273

9.2.7
Méthodes de gradient .. . . 276

9.2.8
Méthode de la plus grande pente 282

9.2.9
Problème de la recherche dans une direction 8 donnée 283

9.2.10
Méthode des gradients conjugués 286

9.2.11
Méthode de Newton-Raphson. . . . 293

9.2.12
Méthode de quasi-Newton. . . . . . 298

9.2.13
Méthodes pour les sommes de carrés 301

9.2.14
Méthode de Gauss-Newton . . . . 303

9.2.15
Méthode de Levenberg-Marquardt 304

9.2.16
Approximation de quasi-Newton . 306

9.2.17
Systèmes d'équations non linéaires 308

9.3
Discussion et conclusion 308

10 Programmation linéaire 309

10.1Généralités................... 309

10.2
Formulation du problème à partir d'exemples 310

10.2.1
Utilisation de variables d'écart . . . . 310

10.2.2
Utilisation de variables d'écart et de variables artificielles 311

10.2.3
Conditions d'optimalité . . . . . . . . 313

10.3
Résolution du problème, tableau du simplexe . . . . . . . . . .. 313

10.3.1
Interprétation géométrique, exemple 1 . . . . . . . . . .. 313

10.3.2
Tableau du simplexe avec variables d'écart et artificielles,
exemple2 ..................... 319

10.4Solutionthéorique
.................... 321

10.5
Cas de contraintes simultanées d'inégalité et d'égalité 325

10.6
Dualité 329

10.6.1
Exemplede dualité. . . . . . . . . . . . 329

10.6.2
Démonstration du théorème de dualité. 330

10.7
Méthodes de point intérieur . . . . . . . . . . 335

10.7.1
Méthode de projection de Karmarkar 335

10.7.2
Transformation affine 340

10.8
Discussion et conclusion . . . . . . . . . . 344

11 Optimisation quadratique et non linéaire 347

11.1Introduction............................. .. 347

11.2
Optimisation quadratique, conditions de Kuhn-Tucker et résolution
parlesimplexe ......... 348

11.2.1
Premièreprésentation . . . . . . . . . . . . . . 348

11.2.2
Deuxième présentation. . . . . . . . . . . . . . 348

11.2.3
Solution sous forme d'un problème de simplexe 348

11.3
Optimisation quadratique, méthode de barrière . . . . 350

11.4
Optimisation non linéaire par optimisation quadratique successive 354

11.4.1
Introduction 354

11.4.2
Notion de région possible et de cône tangent 355

11.4.3
Optimisation quadratique successive . . . . 356

11.4.4
Spécificités et difficultés du problème SQP . 360

11.5Discussionetconclusion
............... 366

12 Exercices 367

12.1
Interpolation et approximation . . . . . . . . . . . 367

12.2Intégrationnumérique
................ 374

12.3
Résolution d'équations par des méthodes itératives 377

12.4
Opérations numériques sur les matrices 382

12.5
Résolution des systèmes d'équations algébriques. . 385

12.6
Intégration numérique des équations différentielles ordinaires 393

12.7
Intégration numérique des équations aux dérivées partielles 401

12.8
Méthodes analytiques d'optimisation 404

12.9
Méthodes numériques d'optimisation . . . 413

12.10Programmation
linéaire . . . . . . . . . . 420

12.110ptimisation
quadratique et non linéaire. 427