Newton

TP 302

RÉSOLUTION APPROCHÉE D’ÉQUATIONS NON LINÉAIRES EN DIMENSION 1

• À rendre sur http://www.prepa-baggio.fr/moodle avant le mardi 17 mars, 23h.• Chaque fichier devra comporter un commentaire dans l’en-tête avec vos nom, prénom,

classe, groupe et numéro du TP.• Une exécution du fichier avec « F5 » dans IDLE ne devra pas provoquer d’erreur.• Les noms des fichiers et des fonctions demandées doivent être respectés.• Les résultats de vos tests doivent apparaître à la suite de vos fonctions, sur plusieurs lignes,

entre triple quote ( """. . . . . . """).• La note ne valide pas seulement le résultat de votre programme, mais également son style

– choix approprié des noms de variables,– présence de documentation et de tests pour les fonctions importantes,– commentaires pertinents.

• Pour les tests, on utilisera la convention suivante : pour une fonction foo, on nomme lafonction de test test_foo.

Le non-respect d’un des points précédents peut retrancher jusqu’à 50 points sur la note finale.L’objet de ce TP est l’approximation des racines d’une fonction réelle d’une variable réelle,

c’est-à-dire, la résolution approchée du problème suivant : étant donné f ∶ I = [a, b] → ℝ,trouver � ∈ [a, b] tel que

f (�) = 0. (1)Les méthodes numériques pour approcher une racine � sont en général itératives. Elles consistentà :

• Localiser grossièrement le ou les zéros de f en procédant à des évaluations qui souventsont de type graphique ; on note x0 cette solution grossière.

• construire, à partir de x0, une suite x1, x2, x3,… , xn,… telle quelimn→∞

xn = �.

On dit alors que la méthode est convergente.

302.1 MÉTHODE DE NEWTON-RAPHSON

Soit f ∶ [a, b] → ℝ une fonction de classe C 1 et soit � un zéro simple de f , c’est-à-diref (�) = 0 et f ′(�) ≠ 0. Supposons que l’on connaisse une valeur xn proche de �. Pour calculerxn+1, nous prenons l’intersection de l’axe Ox avec la droite tangente au graphe de f passant parle point (xn, f (xn)

).

1

2 Résolution approchée d’équations non linéaires en dimension 1

Clairement, nous avons la relation f (xn)∕(xn−xn+1) = f ′(xn) qui donne, lorsque x0 est choisiproche de �, la méthode de Newton-Raphson (ou méthode des tangentes) :

xn+1 = xn −f (xn)f ′(xn)

, n = 0, 1, 2,…

En théorie, une méthode de Newton convergente ne retourne le zéro � qu’après une infinitéd’itérations. En pratique, on recherche une approximation de � avec une certaine tolérance �.Ainsi, on peut interrompre la méthode à la première itération kmin pour laquelle on a l’inégalitésuivante

|

|

|

e(kmin)|||

= |

|

|

� − xkmin|

|

|

< �.

Ceci est un test sur l’erreur. Malheureusement, comme l’erreur est elle-même inconnue, on doit laremplacer par un estimateur d’erreur, c’est-à-dire, une quantité qui peut être facilement calculéeet grâce à laquelle on peut estimer l’erreur réelle. On montre que la différence entre deux itéréessuccessives fournit un estimateur d’erreur correct pour la méthode de Newton. Cela signifie quel’on peut interrompre les itérations à l’étape kmin telle que

|

|

|

xkmin− xkmin−1

|

|

|

< �;

c’est-à-dire lorsque |||

f (xkmin)∕f ′(xkmin

)|||

< �. Ceci est un test sur l’incrément. On montre quece test est optimal pour les méthodes d’ordre 2 comme la méthode de Newton en un zéro simple ;l’erreur absolue (� − xn) étant de l’ordre de xn+1 − xn.Exercice 1

1. Implémenter la méthode de Newton-Raphson dans une fonction newton de prototype1 newton(f, fprime, xzero, epsilon)

• f est l’image d’une fonction f d’une variable réelle et de classe C 1,• fprime sa dérivée,• xzero est un flottant x0,• epsilon est un flottant �.

On suppose que x0 est une approximation grossière d’un zéro de f . Cette fonction calculeles itérées successives obtenues par la méthode de Newton et retourne la première itérationxk dont l’erreur estimée est inférieure à �

|

|

xk − xk−1|| < �.

2. Ajouter une instruction print affichant les itérées successives (vous commenterez cetteligne pour dans le compte rendu final). Tester rapidement la fonction newton avec la fonc-tion x ↦ x2 − 2 et x0 = 2 et diverses valeurs de �. Que peut-on dire de la vitesse deconvergence comparée à la méthode de dichotomie ?

Exercice 2 Nous voulons déterminer le volume V occupé par un gaz dont la température est Tet dont la pression est p. L’équation d’état (i.e. l’équation liant p, V et T ) est donnée par

[

p + a (N∕V )2]

(V −Nb) = kNT , (2)où a et b sont deux coefficients qui dépendent du gaz considéré, N est le nombre de moléculescontenues dans le volume V et k est la constante de Boltzmann. Nous devons donc résoudre uneéquation non linéaire dont la racine est V .

302.2. Méthode de la sécante 3

1. Pour CO2 (dioxyde de carbone), les coefficients a et b dans (2) prennent les valeurs sui-vantes : a = 0.401Pa m6, b = 42.7 × 10−6m3. Trouver le volume occupé par 1000 mo-lécules de CO2 à la température T = 300K et la pression p = 3.5 × 107 Pa par la mé-thode de Newton-Raphson, avec une tolérance de 10−12 (la constante de Boltzmann vautk = 1.380 650 3 × 10−23 J K−1).

2. Ce résultat est-il cohérent ? Expliquer les initiatives que vous avez dû prendre.Exercice 3

1. Un solide ponctuel, au repos à t = 0, est placé sur un plan dont la pente varie avec unevitesse constante !. À un temps t > 0, sa position est donnée par

s(t, !) =g

2!2(sh(!t) − sin(!t)) ,

où g = 9.8m/s2 désigne l’accélération de la gravité. En supposant que cet objet s’est déplacéd’un mètre en une seconde, calculer la valeur de ! avec une tolérance de 10−5.

2. Ce résultat est-il cohérent ? Expliquer les initiatives que vous avez dû prendre.

302.2 MÉTHODE DE LA SÉCANTE

Laméthode de la sécante permet d’éviter l’usage de la dérivée de f en remplaçant le calculde f ′(xn) par le taux d’accroissement de f entre deux itérées successives

f ′(xn) ≈ qn ≝f(

xn)

− f(

xn−1)

xn − xn−1

En se donnant deux valeurs initiales x−1 et x0, on calcule les itérées successives par

xn+1 = xn −f (xn)qn

= xn −xn − xn−1

f (xn) − f (xn−1)f (xn), n = 0, 1, 2,… (3)

Exercice 4

1. Implémenter la méthode de la sécante dans une fonction secante de prototype1 secante(f, xa, xb, epsilon)

• f est l’image d’une fonction f d’une variable réelle et de classe C 1,• xa et xb sont des flottant x−1 et x0,• epsilon est un flottant �.

Cette fonction calcule les itérées successives obtenue par la méthode de la sécante en utili-sant les premières approximations x−1 = xa et x0 = xb. Cette fonction retourne la premièreitération xk dont l’erreur estimée est inférieure à �

|

|

xk − xk−1|| < �.

2. Ajouter une instruction print affichant les itérées successives (vous commenterez cetteligne pour dans le compte rendu final). Tester rapidement la fonction secante avec la fonc-tion x ↦ x2 − 2 et x0 = 2 et diverses valeurs de �. Que peut-on dire de la vitesse deconvergence comparée à la méthode de Newton-Raphson ?


Exercice 5Le traitement thermique d’une pièce en acier consiste en un chauffage de sa couche superfi-

cielle à une température supérieure à Ta = 1293 K, à partir de laquelle se forme de l’austénite(austénitisation). Les couches superficielles doivent être ensuite refroidies très rapidement à unetempérature inférieure à Tc = 993 K, ce qui provoque la formation de martensite. La dureté del’acier s’en trouve alors très sensiblement augmentée (austénite et martensite sont deux phases dudiagramme d’équilibre fer-carbone).

La phase de chauffage de la pièce est réalisée à l’aide d’un laser CO2 pulsé, de longueurd’onde � = 10, 6 �m. Le faisceau laser incident est supposé parfaitement cylindrique. L’évolu-tion de la densité de puissance incidente (puissance par unité de surface) en fonction du tempsa un profil de type créneau ("pulse") dont la représentation est donnée ci-dessous. Le temps tPreprésente la durée de l’impulsion laser.

FIGURE 302.1 –

On donne :⋆ température ambiante T0 = 293 K ;⋆ température de formation de l’austénite Ta = 1 293 K ;⋆ conductivité thermique : K = 35 W.K−1.m−1 ;⋆ coefficient de diffusion thermique D = 1.0 × 10−5 m2.s−1 ;⋆ durée de l’impulsion laser tP = 40 ms ;⋆ densité de puissance JL = 72 × 106 W.m−2.Pour t ∈ [0, tP ], la température en un point de cote z > 0 du métal s’écrit sous la forme :

T (z, t) = T0 +2 JLK

√

Dt F (u) avec

⎧

⎪

⎪

⎨

⎪

⎪

⎩

u =z

2√

Dt

F (u) =e−u2√

�− u + u erf(u)

où z = 0 correspond à la surface du métal et où la fonction erreur erf est définie parerf(u) ∶ ℝ ⟶ ℝ

u ⟼2√

� ∫

u

0e−x

2dx

1. Déterminer la valeur numérique de la profondeur d pour laquelle T = Ta à l’instant tP (finde l’impulsion laser).

302.3. Schéma d’Euler rétrograde 5

302.3 SCHÉMA D’EULER RÉTROGRADE

On considère le problème de Cauchy.u(t) = f (t, u(t))u(t0) = u0,

(4)

où nous avons noté .u(t) = dudt

(t).Pour établir un schéma d’approximation du problème (4), nous commençons par partitionner

l’axe (Ot), c’est-à-dire nous choisissons des points t0, t1, t2,… tels quet0 < t1 < t2 <⋯ < tn < tn+1 <…

En posant ℎn = tn+1 − tn, nous pouvons approcher.u(tn+1) par u(tn+1) − u(tn)

ℎn.

Si un est une approximation de u(tn), cette approche nous suggère le schéma suivant, dit schémad’Euler rétrograde

un+1 − unℎn

= f(

tn+1, un+1) , n = 0, 1, 2,…

u0 = u0.(5)

Le schéma d’Euler rétrograde est un schéma implicite car il ne permet pas d’expliciter un+1 enfonction de un lorsque la fonction f n’est pas triviale. En effet, on a dans ce cas

un+1 − ℎnf(

tn+1, un+1) = un.

Si nous voulons calculer un+1, nous définissons la fonctiong ∶ x↦ x − ℎnf (tn+1, x) − un

et nous cherchons un zéro de g en prenant par exemple une méthode de Newton-Raphson. Ainsi,nous pouvons poser x0 = un et

xm+1 = xm − g(xm)∕g′(xm), m = 0, 1,…

Puisque g′(x) = 1 − ℎn)f (tn+1, x)∕)x, nous obtenons donc dans ce cas le schémax0 = un,

xm+1 = xm −xm − ℎnf

(

tn+1, xm)

− un

1 − ℎn)f)x (tn+1, xm)

, m = 0, 1,…

Pour autant que f soit suffisamment régulière et que x0 soit suffisamment proche de un+1, ce quiest le cas si le pas ℎn est suffisamment petit, nous avons

limm→∞

xm = un+1.

Exercice 6

1. Écrire une fonction euler_retrograde conduisant à la résolution approchée du problèmede Cauchy .u(t) = f (t, u(t))

u(t0) = u0,(6)

Les arguments de cette fonction étant


• une fonction f de deux variables, image de la fonction f ,• une liste subdiv de flottants dont les éléments sont triés par ordre strictement croissant

(c’est la liste des tn).• u_zero est un flottant représentant la valeur initiale au temps t0, le premier élément

de la liste subdiv.• une fonction dfx de deux variables image de )f

)x ,• epsilon est un flottant représentant la tolérance utilisée lors de l’utilisation de la

méthode de Newton-Raphson.Cette fonction retourne la liste des approximations successives obtenues par la méthoded’Euler rétrograde avec la subdivision subdiv (c’est la liste des un).

2. Effectuer un test rapide avec l’équation différentielle .u(t) = u(t) et u(0) = 1 sur l’intervalle[0, 1].

Exercice 7 Un réservoir cylindrique de section S rempli d’eau se termine par un tube horizontalde longueur L = 1 m et de section s ≪ S situé à sa base et fermé par un robinet qu’on ouvre àl’instant t = 0. Initialement la hauteur d’eau dans le réservoir est ℎ0 = 1 m, et on la note ℎ(t) àl’instant t.

L’accélération de la pesanteur est prise égale à g = 10 m.s−2.

Une fois le robinet ouvert, on suppose l’écoulement unidimensionnel à l’interface air-eau dansle réservoir avec #»v (M, t) = −V (t) #»u z et dans le tube horizontal où #»v (M, t) = v(t) #»u x.On montre que la vitesse dans le tube vérifie l’équation différentielle suivante :

Ldvdt

= gℎ0 −v2

2.

1. Représenter graphiquement la solution numérique approchée de la vitesse v sur [0, 5] avecun pas constant de 0.5 en utilisant

• le schéma d’Euler progressif,• le schéma d’Euler rétrograde.

2. Reprendre la question précédente avec un pas de 0.2, puis 0.4, puis 0.6 et enfin 0.8 (onpourra modifier un peu l’intervalle [0, 5]). Commenter les résultats obtenus.

302.4. Compléments 7

302.4 COMPLÉMENTS

§1 Analyse numérique : ordre d’une méthode

Définition 1 On dit qu’une suite (xn)

n∈ℕ construite par une méthode numérique converge vers� avec un ordre p ≥ 1 si il existe une constante C > 0

∀k ≥ k0,|

|

xk+1 − �|||

|

xk − �||p ≤ C.

Dans ce cas, on dit que la méthode est d’ordre p.

Remarque. • Si p est égal à 1, il est nécessaire que C < 1 pour que (xn) converge vers �. Onparle de convergence linéaire.• Si p = 2, on parle de convergence quadratique.• Si p = 3, on parle de convergence cubique.

§2 Méthode de HalleyEdmund Halley (1656–1742) était un contemporain et un ami de Newton. Sa contribution à la

recherche de racine utilise l’information contenue dans le terme suivant dans (ce que l’on appellede nos jours) le développement de Taylor, et fait intervenir la dérivée seconde.

La schéma devient alors

xk+1 = xk −f (xk)

f ′(xk)(

1 − f (xk)f ′′(xk)2f ′(xk)2

) . (7)

C’est essentiellement la méthode de Newton-Raphson, mais avec une correction (normalementmineure) du terme au dénominateur.

L’utilisation de la méthode de Halley n’a du sens que s’il est facile de calculer f ′′(xk). C’estnotamment le cas pour les fonctions polynomiales ou lorsque le calcul de f ′′(xk) est quasimentgratuit (par exemple, si l’on arrive à récupérer une partie des calculs effectués pour f (xk) etf ′(xk)).

Documents

Newton