Cours et exercices d’analyse numerique
Télécharger-
Cours et exercices d’analyse numérique
Chapitre 1 Les systèmes linéaires
1.1 Introduction
1.1.1 Gestion des erreurs
Il arrive souvent lors de calcul que nous soyons obligés de donner une valeur approchée de la solution (0,333 pour 1/3 par exemple), c’est ce que l’on appelle la représentation des nombres en virgule flottante (8 ou 16 chiffres significatifs après la virgule). Il se peut également qu’une méthode employée pour résoudre un problème ne nous amène pas exactement à la solution mais à côté, on dit alors que l’on a une approximation de la solution (c’est souvent le cas pour les problèmes non linéaires que nous verrons dans le chapitre suivant et moins fréquent pour les problèmes linéaires). Le but est de pouvoir maîtriser ces erreurs de sorte qu’elles ne s’accumulent pas au cours des opérations successives. C’est un des chevaux de bataille des numériciens qui ne souhaitent pas voir leurs approximation s’éloigner des solutions exactes, ce qui rendrait leur travail complètement inefficace. L’objectif est donc de chercher à élaborer des méthodes numériques qui n’amplifient pas trop les erreurs d’arrondi au cours des calculs. Intuitivement, nous imaginons bien que cette amplification est d’autant plus grande que le nombre d’opérations est important (additions, multiplications, etc.).
Nous cherchons donc à réduire le nombre d’opérations au maximum et par voie de consé- quence le temps de calcul. A titre d’exemple, pour calculer le déterminant d’une matrice carrée 24 ⇥ 24 par la méthode classique de Cramer il faudrait plus de 20 ans à un ordinateur capable de faire 1015 opérations à la seconde (un Peta-flops) ! On voit donc qu’il est plus que nécessaire de trouver des méthodes beaucoup plus efficaces que celle-là. Nous introduirons donc les notions de stabilité et d’efficacité. Et suivant les méthodes utilisées, nous aurons affaire à tel ou tel type d’erreur. Pour les systèmes linéaires par exemple nous étudierons deux types de méthodes bien distinctes :
1. les méthodes directes : qui consistent en des algorithmes qui permettent de calculer la solution exacte (mis à part les erreurs d’arrondis en virgule flottante) en un nombre fini d’opération,
2. les méthodes itératives : qui consistent en l’approche de la solution exacte x par une suite (xn)n2N de solutions approchées. Nous arrêtons alors les calculs lorsque nous atteignons un certain xn0 . Nous avons alors une erreur de troncature due à l’approximation de la solution exacte que nous mesurons à l’aide d’une norme appropriée (suivant la dimension de l’espace dans lequel x se trouve) kx # xn0 k.
1.1.2 Exemple de problème menant à la résolution d’un système linéaire
On considère l’équation différentielle du second ordre posée sur l’intervalle [0, 1], #u00(x) + c(x)u(x) = f(x) pour tout x 2]0, 1[, définie en 0 et 1 par u(0) = ↵ et u(1) = ', où ↵ et ' sont des réels donnés, f : [0, 1] ! R est continue et donnée, et c : [0, 1] ! R+ est une fonction continue positive donnée. L’inconnue est ici la fonction u : [0, 1] ! R qui est de classe C 2. On discrétise cette équation par ce que l’on appelle la méthode des différences finies (voir chapitre sur les équations différentielles). On se donne un nombre fini de points dans [0, 1] espacés à égale distance h. Nous avons alors pour tout n 2 N⇤, h = 1 n que l’on appelle le “pas du maillage”.
On note pour tout j = 0, ..., n, xj = j n . Nous allons essayer alors de calculer une valeur approchée de la solution u aux points x0,...xn. Nous passons donc d’un problème continu à un problème discret. Pour tout i = 0, ..., n on pose ci = c(xi), fi = f(xi) et ui la valeur approchée des u(xi) calculée par le schéma numérique. Le problème est le suivant : comment approcher u00(xi) ?
Table des matières
1 Les systèmes linéaires 5
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.1.1 Gestion des erreurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.1.2 Exemple de problème menant à la résolution d’un système linéaire . . . . . 6
1.2 Quelques rappels sur les matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2.1 Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2.2 Lien avec les applications linéaires . . . . . . . . . . . . . . . . . . . . . . 9
1.2.3 Opérations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.2.4 Trace et déterminant . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.2.5 Matrice et produit scalaire . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.2.6 Valeurs propres, vecteurs propres et réduction de matrices . . . . . . . . . 16
1.3 Normes vectorielles et matricielles . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.3.1 Rappels sur les normes vectorielles . . . . . . . . . . . . . . . . . . . . . 18
1.3.2 Boules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.3.3 Normes matricielles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.3.4 Conditionnement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.4 Méthodes directes de résolution de systèmes linéaires . . . . . . . . . . . . . . . . 24
1.4.1 Principe des méthodes directes . . . . . . . . . . . . . . . . . . . . . . . . 25
1.4.2 Pivot de Gauss - Décomposition LU ..................... 25
1.4.3 Cas des matrices symétriques définies positives :la factorisation de Cholesky 28
1.4.4 Factorisation QR ............................... 28
1.5 Méthodes itératives de résolution de systèmes linéaires . . . . . . . . . . . . . . . 28
1.5.1 Principe des méthodes itératives . . . . . . . . . . . . . . . . . . . . . . . 29
1.5.2 Trois méthodes classiques . . . . . . . . . . . . . . . . . . . . . . . . . . 30
1.5.3 Critère général de convergence, étude des suites d’itérées de matrices . . . 31
1.5.4 Quelques cas particuliers de convergence . . . . . . . . . . . . . . . . . . 32
1.6 Méthodes numériques de calcul de valeurs propres et vecteurs propres . . . . . . . 33
1.6.1 Motivation : modes propres . . . . . . . . . . . . . . . . . . . . . . . . . 33
1.6.2 Difficultés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
1.6.3 Conditionnement spectral . . . . . . . . . . . . . . . . . . . . . . . . . . 34
1.6.4 Méthode de la puissance . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
1.6.5 Généralisation de la méthode de la puissance : la méthode QR ....... 37
2 Résolution approchée d’équations non linaires 41
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
2.2 Dichotomie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
2.3 Méthode de type point fixe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
2.3.1 Théorème-énoncé général . . . . . . . . . . . . . . . . . . . . . . . . . . 42
2.3.2 Construction de méthodes pour f(x)=0 .................. 43
2.3.3 Vitesse de convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
2.4 Méthode de Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
2.4.1 Principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
2.4.2 Théorème de convergence . . . . . . . . . . . . . . . . . . . . . . . . . . 45
2.5 Méthode de la sécante . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
2.6 Ordre d’une méthode itérative . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
2.7 Systèmes d’équations non linéaires . . . . . . . . . . . . . . . . . . . . . . . . . . 47
2.7.1 Point fixe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
2.7.2 Méthode de Newton dans Rn ......................... 48
2.7.3 Retour sur les systèmes linéaires et aux méthodes itératives . . . . . . . . . 48
3 Interpolation et approximation (polynomiales) 49
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.2 Interpolation polynomiale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.2.1 Interpolation de Lagrange . . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.2.2 Interpolation d’Hermite . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.3 Approximation polynomiale au sens des moindres carrés . . . . . . . . . . . . . . 54
- Evaluation :
-
Total des Votes : 0 -
Soyez le premier à écrire un commentaire sur ce fichier!
Veuillez vous identifier ou vous enregistrer.