Cours methodes numeriques PDF

Preview

Summary

cours méthode numérique...

Description

Méthodes numériques

Table des matières 1

Recherche de racines d’une fonction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1

La méthode de dichotomie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

2

La méthode de Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2

Interpolation polynomiale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

1

Existence de l’interpolant . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2

Forme de Lagrange . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

3

Forme de Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

3

Intégration numérique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

1

Approximation d’une intégrale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

2

Méthodes élémentaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

3

Étude de l’erreur pour les formules élémentaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

4

Formules composites . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

2

TABLE DES MATIÈRES

3

Il y a une différence majeure en mathématiques entre ce qu’on sait qu’on peut faire et ce qu’on sait faire. Un exemple très simple : on sait qu’on peut calculer la longueur du rayon d’un cercle de périmètre 1, qui sera 1 ,un nombre réel. Mais sait-on calculer le périmètre de ce cercle : combien mesure-t-il ? Répondre à cette question, 2π c’est connaître la valeur de π. Cette préoccupation, celle de réaliser des calculs, d’obtenir les valeurs précises de nombres, est centrale en mathématiques. Mais peut-on trouver la valeur de π ? On sait de façon sûre depuis le 18e siècle que c’est un nombre irrationnel, qui ne peut donc pas s’écrire comme la fraction de deux nombres entiers. Cela entraîne qu’on ne peut pas écrire π comme un nombre à virgule dont les décimales s’arrêtent ou se répètent selon un motif régulier. Il faudra donc se contenter d’une valeur approximative, par exemple π ≈ 3.14 signifie qu’on a 3.135 < π < 3.145, ce qui nous permet d’exprimer le périmètre du cercle avec une précision de l’ordre d’1%. Ce qu’on appelle méthode numérique, c’est une technique de calcul qui permet d’obtenir une approximation d’un objet mathématique : un nombre le plus souvent, ou une fonction par exemple. Dans ce cours, on cherchera à développer des méthodes numériques pour obtenir les premières décimales d’un nombre réel, ou pour approcher une fonction à l’aide d’un polynôme.

Historiquement, les méthodes numériques ont très vite été au centre de la pratique des mathématiques. Ainsi, par exemple, une tablette babylonienne retrouvée à Suse en Iran, et datée d’il y a environ 3600 ans donne une valeur plus précise que 3 pour π : la valeur π ≈ 3 1/8 = 3.125. Cette approximation donne deux décimales correctes pour π, mais on en connaît aujourd’hui bien plus. La figure suivante1 présente justement le nombre de décimales correctes de π connues à une époque donnée.

On constate que le nombre de décimales connues a sans cesse augmenté, mais il est remarquable de constater le changement abrupt de tendance qui s’est déroulé autour de 1950 : c’est le développement de l’ordinateur et l’augmentation exponentielle de la quantité de calcul qu’on connaît depuis. Toute méthode numérique exige du calcul numérique, c’est pourquoi les ordinateurs sont particulièrement adaptés dans ce contexte. Ce cours vise donc à développer des méthodes numériques données sous forme d’algorithmes, donnés en langage naturel. Comme dernière remarque, on sait que les décimales de π sont en nombre infini sans se répéter périodiquement. Comment peut-on alors trouver de nouvelles décimales, qui les invente, ou encore pourquoi la 42 e décimale de π est un 9 et pas un 5 ? Bien entendu, personne n’invente les décimales de ce nombre, qui est fixé à une valeur précise (bien qu’inconnue) dès qu’on le définit. Ce qui fait qu’on peut dire que 3.14159265 sont les huit premières décimales de π c’est que |π − 3.14159265| < 10−8 , alors que tout autre nombre avec huit chiffres après la virgule ne vérifie pas ce fait (sauf 3.14159266 qui est l’arrondi supérieur). Dire qu’on connaît maintenant plus de 1012 décimales correctes de π, c’est donc affirmer qu’on connaît un 12 nombre a avec 1012 chiffres après la virgule tel que |π − a | < 10−10 , le nombre de droite s’écrivant comme un 1 placé après mille milliards de 0 après une virgule. On dégage ici une notion clé des méthodes numériques : c’est l’estimation de l’erreur d’approximation. Une approximation a d’un nombre x sera jugée bonne ou mauvaise selon la valeur de l’erreur E = | x − a |, et trouver une 1. source : https://fr.wikipedia.org/wiki/Approximation_de_%CF%80

TABLE DES MATIÈRES

4

méthode numérique qui donne une approximation de x, c’est précisément trouver comment faire tendre E vers 0. On pourra aussi dire qu’une méthode numérique est meilleure qu’une autre si l’erreur obtenue est plus petite. Nous reviendrons plusieurs fois sur cette notion d’erreur, mais il est bon de noter par avance que c’est une notion indétachable de celle de méthode numérique, et d’approximation. Ces notes de cours sont essentiellement une remise en page des notes de cours élaborées par Nicolas Couellan, Sophie Jan et Youchun Qiu pour la même UE. Elles sont donc issues de précédentes notes par Jean-Paul Calvi, et d’un manusccrit de François de Thélin. Qu’ils soient tous vivement remerciés ici. La mise en page a été possible grâce à l’aide technique de Joan Bellier-Millès, qu’il soit aussi remercié ici. Les figures refaites, ainsi que les textes d’introduction de chaque chapitre sont un ajout par Etienne Werly à cette version.

1

Recherche de racines d’une fonction

Dans ce chapitre, on développe des méthodes pour trouver une approximation numérique de la racine d’une fonction. Rappelons qu’on dit que le nombre r ∈ R est une racine de la fonction f lorsque f (r) = 0. On sait d’après le théorème de d’Alembert que dans C , un polynôme de degré n Ê 1 admet n racines. Mais pour quels polynômes sait-on vraiment calculer les racines ? Il existe des méthodes assez simples pour les équations de degré 1 et 2. Il existe aussi des méthodes pour résoudre en général les équations de degré 3 (méthode de Cardan) et 4 (méthode de Ferrari), mais celles-ci sont plus difficiles à appliquer et engendrent des calculs lourds pour être faits à la main. Mais au delà du 5e degré, on ne peut plus trouver de formules. Le problème n’est pas qu’on n’arrive pas à les trouver, mais qu’il a été montré qu’on ne peut pas trouver des formules pour calculer les racines d’un polynôme de d , ce que l’on appelle résoudre degré 5 ou plus qui utilisent les opérations + , −, ×, ÷ et des racines de tout ordre p une équation par radicaux. Ce résultat négatif est une conséquence du théorème d’Abel, un théorème difficile à prouver mais qui a mis fin à des centaines d’années de recherche de telles formules. Théorème d’Abel L’équation générale du cinquième degré, y5 + a y4 + b y3 + c y2 + d y + e = 0, ne peut être résolue par radicaux. Est-ce à dire qu’on ne peut pas résoudre une équation polynomiale générale si le degré de l’équation est plus grand que 5 ? C’est là qu’interviennent les méthodes numériques, qui proposent des moyens de calculer une approximation numérique de telles solutions.

5

Recherche de racines d’une fonction Objectifs : ◦ Définir la méthode de dichotomie ◦ Écrire un algorithme pour la méthode de dichotomie ◦ Définir la suite de Newton associée à une racine

6

Cours n°1 – 1h

Dans tout le chapitre on consière une fonction continue sur un intervalle [a; b] ⊂ R. On cherche à déterminer numériquement une bonne approximation d’une racine r ∈ [a; b] tel que f (r) = 0 Le théorème qui va nous aider à assurer l’existence d’une telle racine sur l’intervalle [a; b] est le théorème des valeurs intermédiaires, qui indique qu’une fonction continue se trace "sans lever le stylo". Théorème des Valeurs Intermédiaires Soient a et b deux réels tels que a < b et f : [ a; b] → R une fonction continue telle que f (a)f (b) < 0. Alors il existe c ∈]a; b[ tel que f (c) = 0.

1. La méthode de dichotomie 1.1. Présentation de la méthode On suppose que f n’admet qu’une racine dans l’intervalle [a; b] et que f (a) f(b) < 0. La méthode de dichotomie consiste à réduire de plus en plus l’intervalle dans lequel la racine peut se trouver. Elle se présente de la manière suivante : 1. On pose m =

a +b 2

et on évalue f (m).

2. Si f (m) = 0 on a trouvé la racine, la méthode s’arrête.

3. Sinon on calcule f (a)f (m).

(a) Si f (a)f (m) < 0, alors d’après le théorème des valeurs intermédiaires, la racine qu’on cherche est dans [a; m]. On reprend au point 1. avec a ← a et b ← m.

(b) Sinon, on a f (m) f(b) < 0 donc la racine est dans l’intervalle [m;b]. On reprend au 1. avec a ← m et b ← b.

Avec cette méthode, on peut donc construire trois suites ( a n ), ( b n) et ( c n) en suivant l’algorithme suivant (les suites sont finies si on arrive à trouver la valeur exacte de la racine). Algorithme 1 : Méthode de dichotomie

1 2 3 4 5 6 7 8 9 10 11 12

Sorties : Trois suites générées par dichotomie. Entrées : deux nombres a < b et une fonction f n←0 c ← a2+b tant que n Ê 0 faire si f (c) = 0 alors Stop. La racine cherchée est c . sinon si f (a)f (m) < 0 alors b←c sinon a←c b c ← a+ 2 n ← n+1

Recherche de racines d’une fonction

7

1.2. Convergence de la méthode de dichotomie On souhaite démontrer que la méthode de dichotomie va donner une approximation de la racine r que l’on cherche, c’est à dire qu’on voudrait que la suite (c n ) converge vers r. C’est le cas, comme l’énonce le théorème suivant. Théorème 1 Soit f une fonction continue sur un intervalle [a ;b]. On suppose que f (a)f (b) < 0 et que l’équation f (x ) = 0 admet une unique solution dans l’intervalle [a; b ]. Si l’algorithme de dichotomie parvient justqu’à l’étape n (c’est à dire si c i 6= r pour i entre 0 et n − 1), alors on a b−a |r − c n | É n+1 2 Démonstration On a par application de l’algorithme trois nombresa n , b n et c n tels que a n < c n < b n , et la racine r est soit dans l’intervalle [a n ;c n ] soit dans l’intervalle [c ; b n ], qui sont deux intervalles de longueur b n2−a n. Ainsi | c n − r| É

bn − an 2

Or par construction on a bn − an =

b n −1 − a n −1 2

=

b n −2 − a n −2 22

Ainsi on a bien | c n − r| É

= ··· =

b0 − a 0 b−a = n 2n 2

b−a

2 n +1

ä

Ainsi, la suite (c n ) se rapproche bel et bien de la racine r. Bien entendu, il en va de même des suites (a n ) et (b n ). Cependant, la méthode de dichotomie converge trop lentement en pratique : il faut se rendre compte qu’on divise à chaque fois l’erreur d’approximation par deux, donc si on écrit l’approximation comme un nombre binaire à virgule, on obtient de l’ordre d’un nouveau bit à chaque itération. Parfois évaluer la fonction représentera un coût important en ressources, et on comprend que la méthode de dichotomie donne alors des résultats trop faibles pour être utilisée. C’est pourquoi cette méthode est surtout utilisée pour obtenir la localisation approximative d’une racine, avant d’utiliser une méthode plus fine pour obtenir une bonne approximation, par exemple la méthode de Newton présentée à la prochaine partie, ou les méthode de la sécante ou du point fixe, qui ne sont pas présentées dans ce cours. Remarque 1 Le critère d’arrêt qui intervient dans l’algorithme, ligne 3, fait que l’algorithme ne s’arrête jamais. En pratique, on utilisera un critère d’arrêt de la forme bn − an 0 sur [0; π/2] donc la fonction f est strictement décroissante sur l’intervalle et la racine r est unique. En appliquant la p méthodepde dichotomie on obtient ¤ ¡ ¢ £ ◦ f π4 = π4 − 22 = π−24 2 > 0 donc r ∈ 0; π4 . ¡π¢ π ¡π¢ £π π¤ ◦ f 8 = 8 − cos 8 ≈ −0.53 donc r ∈ 8 ; 4 .

2. La méthode de Newton

Recherche de racines d’une fonction

8

2.1. Suite de Newton Définition 1 Soient a et b deux réels tels que a < b. On note C p ([a; b]) l’ensemble des fonctions f définies sur [a;b] qui sont p fois dérivables et dont la p-ième dérivée f ( p) est continue. On suppose que f ∈ C1 ([a; b]) (c’est à dire que f est dérivable et que f ′ est continue) et que f ne s’annule qu’une fois sur l’intervalle [a; b ]. L’idée de la méthode de Newton est de remplacer f par sa tangente en x0 ∈ [a;b], représentée par la fonction T 0 (x) = f ′ (x0 )(x − x0 ) + f (x0 ) et de chercher la racine de la tangente. Il suffit donc de résoudre T 0 ( x) = 0 qui a pour solution f (x0 ) x1 = x0 − ′ f (x0 ) Bien sûr, le nombre calculé n’est pas une bonne approximation de la racine de f , mais si x1 ∈ [a; b], on peut recommencer le procédé en remplaçant x0 par x1 et T 0 par T 1 (x) = f ′ (x1 )(x − x1 ) + f (x1 ) pour obtenir un nouveau point x2 = x1 −

f (x1 ) f ′ (x1 )

Définition 2 On construit de cette manière, par récurrence et sous réserve du fait que x n ∈ [a ;b] pour tout n la suite de Newton, f (x n ) x n+1 = x n − ′ f (x n ) Remarque 2 Cette définition n’est bien posée que lorsque ◦ La dérivée de f ne s’annule pas sur les points x n : ∀ n ∈ N f ′ (x n ) 6= 0 ◦ Le point de départ x0 ∈ [a; b] a été choisi de sorte que ∀ n ∈ N x n ∈ [a; b]

Les deux conditions énoncées ci-dessus peuvent être difficiles à justifier en pratique. Des conditions suffisantes pour assurer la bonne définition de la méthode de Newton sont présentées en annexe. On utilise donc la méthode de dichotomie pour espérer arriver suffisamment près de la racine r pour appliquer la méthode de Newton.

Recherche de racines d’une fonction

9

Objectifs : ◦ Montrer que la méthode de Newton converge ◦ Étudier sur des exemples la convergence quadratique

Cours n°2 – 1h

2.2. Convergence de la méthode de Newton Définition 3 On dit qu’une suite de réels (x n )n∈N converge quadratiquement vers sa limite r lorsque lim x n = r

n →+∞

et

lim

n →+∞

| x n+1 − r| =C >0 | x n − r|2

Intuitivement, cette définition permet de parler de la vitesse à laquelle converge une suite vers sa limite. Si on souhaite une approximation de la limite r en écriture décimale, il va exister un rang N tel que | x n − r| < 10 − p , c’est à dire qu’on connaît les p premiers chiffres exacts de la limiter . À l’itération suivante, on a | x n+1 − r| < C ′ | x n − r|2 (où C ′ est une constante "proche" de C). Donc on a | x n+1 − r| < C ′ 10 −2p : le nombre de chiffres exacts qu’on connaît de r a environ doublé. La convergence quadratique offre donc des approximations qui deviennent rapidement très bonnes. Remarquons qu’on peut adapter la définition en remplaçant la puissance 2 par toute autre valeur α > 1, pour définir la convergence d’ordre α.

Théorème 2 Soient f ∈ C2 ([a; b]) et r ∈ [a; b] tel que f (r) = 0. On suppose que, pour tout x ∈ [a; b ], ¯ ¯ ¯ f ′ (x)¯ Ê m 1 > 0

Alors pour tout x0 ∈]r − ε; r + ε[⊂ [a; b] où ε <

2m 1 M2

et

on a

¯ ¯ ¯ f ′′(x)¯ É M2

1. Pour tout n ∈ N, il existe θn entre x n et r tel que x n+1 − r =

f ′′(θn ) 2 f ′ (x n )

(x n − r)2

2. Pour tout n ∈ N, x n ∈]r − ε; r + ε[.

3. Pour tout n ∈ N,

| x n+1 − r| É

µ

M2 2m 1

¶2n −1

| x0 − r|2

n

4. La suite (x n ) converge vers r quadratiquement. Démonstration 1. Le premier point vient des formules de Taylorqui ne sont pas développées cette année. D’après ces formules dont vous pouvez trouver la démonstration dans de nombreux livres de L1, commef ∈ C2 ([a; b]), il existe pour tout x n ∈] r − ε ; r + ε[ un nombre θ n entre x n et r tel que f ′′ (θ n ) f (r) = f (x n ) + f ′ (x n )(r − x n ) + (r − x n )2 2 et comme f (r) = 0 on a − f (x n ) = f ′ (x n )(r − x n ) +

f ′′ (θ n ) 2 2 (x n − r) . On en déduit que

f ′′(θ n ) f ′ (x n ) f ′′(θ n ) f (x n ) = xn + ′ (r − x n ) + ′ (x n − r)2 = r + (x n − r)2 x n +1 = x n − ′ 2f (x n ) f (x n ) f (x n ) 2f ′ (x n ) 2. En utilisant le point précédent, on voit que si x n ∈]r − ε; r + ε[ on a ¯ ¯ 2 ¯ ¯ ¯ ¯ f ′′ ¯ x n+1 − r ¯ = ¯ (θ n ) ¯ | x n − r|2 < M2 ε2 = ε = ε ε 2 ¯ f ′ (x n )¯ 2m 1 donc x n+1 ∈]r − ε; r + ε[. On conclut par récurrence. 0

3. À nouveau par récurrence, on a | x0 − r| = | x0 − r|2 , puis si µ ¶ n n M 2 2 −1 | x0 − r|2 | xn − r| É 2m 1 on a

¯ ¯ ¶2×(2n −1) µ ¶ n + 1 −1 µ ¯ ¯ ¯ ¯ f ′′ n +1 n M2 2 ¯ x n+1 − r ¯ = ¯ (θ n ) ¯ | x n − r|2 É M2 M2 | x0 − r|2 | x0 − r|2×2 = 2 ¯ f ′ (x n )¯ 2m 1 2m 1 2m 1

Recherche de racines d’une fonction 4. On a | x0 − r| < ε, donc | xn − r| É

Or comme

εM2 2m 1

< 1, on en déduit que

µ

10

¶ n M 2 2 −1

2m 1

n

| x0 − r|2 <

´ n ε M 2 −1 ε 2m2 1 ³

µ

M2 2m 1

¶2n −1

n

ε2 = ε

µ

¶ n ε M 2 2 −1

2m 1

tend vers 0, donc x n tend vers r. Comme de plus on a ¯ ¯ ¯ ¯ ¯ f ′′ (r)¯ ¯ f ′′(θ n )¯ ¯ −→n→+∞ ¯ ¯ Ê0 = ¯¯ ′ 2 f (x n )¯ | x n − r|2 2 ¯ f ′ (r)¯

¯ ¯ ¯ x n +1 − r ¯

on a une convergence (au moins) quadratique.

ä

Ce théorème garantit que la méthode de Newton est bien définie et converge vers la racine recherchée sur un intervalle ]r − ε;r + ε [ autour de la racine, et on a des informations sur la vitesse de convergence, qui est au moins quadratique, et on a une formule explicite pour l’erreur (point 3). On peut alors savoir exactement combien d’itérations faire avec la dichotomie avant de commencer la méthode de Newton qui convergera rapidement vers la racine. Au niveau des hypothèses, le théorème exige une assez bonne connaissance de la fonction f pour être appliqué : la fonction doit être de classe C2 ([a; b]) , avec une dérivée qui ne s’annule pas et qui reste même à une distance au moins m 1 de 0, et une dérivée seconde qui reste bornée par M2 . En pratique, cette deuxième hypothèse est toujours vérifée puisque f ′′ est continue sur un intervalle [a;b], et est donc bornée (un résultat qu’on peut retrouver dans beaucoup de livres de L1). Remarquons enfin que si r est un point d’inflexion (c’est à dire si f ′′ (r )= 0), alors la convergence est meilleure que quadratique puisqu’alors lim | xn+1 −r2| = 0. | x − r| n

2.3. Exemples d’application de la méthode de Newton Détaillons quelques utilisations de la méthode de Newton pour mettre en pratique le théorème 2, observer la convergence quadratique ou voir quels problèmes peuvent se produire en voulant appliquer la méthode. Exemple 2. Racine de x − cos( x) £ ¤ On a vu que la fonction f (x) = x − cos(x) admet une solution dans l’intervalle π8 ; 4π avec la méthode de dichotomie. On a f ′ (x) = 1 + sin(x) et f ′′( x) = cos(x) ¯ ¯ ¯...