Méthode de Newton et méthode d’Euler - pcsi.kleber.free.frpcsi.kleber.free.fr/IPT/doc/INS2_Newton_et_Euler_codes.pdf · E Bougnol, JJ Fleck, M Heckmann & M Kostyra, Kléber, PCSI

INS2Méthode de Newton et méthode d’Euler

Code INS2.1: Recherche du zéro d’une fonction par dichotomie

# On regarde f(a), f(b) et f(milieu)# Tant que |f(milieu)| > epsilon choisi# Si f(a) et f(milieu) sont de signes différents# On bouge b vers le milieu# Si f(b) et f(milieu) sont de signes différents# On bouge a vers le milieu# On regarde les nouveaux f(a), f(b) et f(milieu)# Renvoie de la valeur de milieu en fin de boucle# (c’est qu’il est assez proche de 0)

1

E Bougnol, JJ Fleck,M Heckmann & M Kostyra,Kléber, PCSI& - INS2 Methode de Newton et methode d’Euler 2/12

Code INS2.2: Implémentation de la recherche du zéro par dichotomie

1 def zero_par_dichotomie(f,a,b,epsilon=1e-6):2 ’’’Recherche du zéro d’une fonction par dichotomie. Pour être sûr de3 marcher correctement, il ne doit y avoir qu’un seul zéro dans l’intervalle4 considéré. Néanmoins, si on a un peu de chance, il est possible que5 l’algorithme trouve au moins un zéro.’’’6 m = (a+b)/2.0 # On regarde f(a), f(b) et f(milieu)7 fa,fb,fm = f(a),f(b),f(m)8 while abs(fm) > epsilon: # Tant que |f(milieu)| > epsilon choisi9 if fa*fm < 0: # Si f(a) et f(milieu) sont de signes différents

10 b = m # On bouge b vers le milieu11 elif fb*fm < 0: # Si f(b) et f(milieu) sont de signes différents12 a = m # On bouge a vers le milieu13 else: # Sinon, c’est qu’il y a un problème...14 raise ValueError(’’’f(a) et f(b) sont de même signe,15 nombre pair ou nul de zéro sur l’intervalle, je préfère m’arrêter’’’)16 m = (a+b)/2.0 # On regarde les nouveaux f(a), f(b) et f(milieu)17 fa,fb,fm = f(a),f(b),f(m)18 return m # Renvoie de la valeur de milieu en fin de boucle

Code INS2.3: Recherche du zéro d’une fonction par méthode de Newton

# Tant que |f(x)| > epsilon choisi# On calcule la dérivée en x par approximation# On trouve la nouvelle valeur de x# Renvoie de la valeur finale

Code INS2.4: Implémentation de la recherche du zéro par méthode de Newton

1 def zero_par_newton(f,x0,epsilon=1e-6,h=1e-4):2 ’’’Recherche du zéro d’une fonction par méthode Newton qui consiste à3 approcher le zéro recherché par les zéros des tangentes successives à la4 courbe. Si la convergence marche, cela converge très vite, mais cela5 risque de partir en vrille en cas de dérivée presque nulle ou si l’on part6 trop loin du zéro recherché. À l’utilisateur d’initialiser l’algorithme7 dans une zone où la dérivée est de signe constant.8 Remarques:9 * epsilon est la précision sur la proximité de f(x) à zéro.

10 * h est utilisé pour estimer la valeur de la dérivée en l’assimilant au11 taux d’accroissement.’’’12 x = x0 # Initialisation13 while abs(f(x)) > epsilon: # Tant que |f(x)| > epsilon choisi14 derivee = (f(x+h) - f(x)) / h # dérivée en x_k par taux d’accroissement15 x = x - f(x)/derivee # nouvelle valeur x_{k+1} de x16 return x # Renvoie de la valeur finale


Code INS2.5: Des tests, des tests, oui mais des Panzani !

1 def teste_fonctions(fonctions,intervalles,epsilons):2 s= ’’3 for i in range(len(fonctions)):4 f = fonctions[i]5 a,b = intervalles[i]6 epsilon = epsilons[i]7 try:8 zero,nb_iter = zero_par_dichotomie_iter(f,a,b,epsilon)9 valeurs = (f.__name__,zero,a,b,epsilon,nb_iter)

10 s+= "Dichot: {} s’annule en {:.9f} ".format(f.__name__,zero)11 s+= "sur [{},{}] à {} près ".format(a,b,epsilon)12 s+= "en {} itérations.\n".format(nb_iter)13 except ValueError:14 s+= "Dichot: Pas de zéro trouvé pour {} ".format(f.__name__)15 s+= "sur [{},{}] en {} itérations.\n".format(a,b,nb_iter)16 try:17 zero,nb_iter = zero_par_newton_iter(f,a,epsilon)18 valeurs = (f.__name__,zero,a,epsilon,nb_iter)19 s+= "Newton: {} s’annule en {:.9f} ".format(f.__name__,zero)20 s+= "partant de {} à {} près en {} itérations.\n".format(a,epsilon,nb_iter)21 except ZeroDivisionError:22 s+= "Newton: Problème de division par 0 pour {} partant de {}.\n".format(f.__name__,a)23 return s24

25 from math import * # sin, cos et pi26

27 def f(x): return x**2-228 def g(x): return 2-x**229 def h(x): return pi-x**230

31 fs = [f,f,f,f,f,g,h,sin,sin,cos,cos,cos,cos]32 ints=[(1,2),(1,2),(1,2),(1,2),(1,2),(1,2),(0,2),(-1,1),(3,4),(-1,1),(1,2),(0,6),(0,10)]33 eps= [1e-1,1e-3,1e-5,1e-6,1e-9,1e-9,1e-6] + [1e-6]*634 s = teste_fonctions(fs, ints, eps)35 print(s)


Code INS2.6: Résultat des tests précédents

Dichot: f s'annule en 1.437500000 sur [1,2] à 0.1 près en 3 itérations.Newton: f s'annule en 1.416668055 partant de 1 à 0.1 près en 2 itérations.Dichot: f s'annule en 1.414062500 sur [1,2] à 0.001 près en 6 itérations.Newton: f s'annule en 1.414215775 partant de 1 à 0.001 près en 3 itérations.Dichot: f s'annule en 1.414215088 sur [1,2] à 1e-05 près en 14 itérations.Newton: f s'annule en 1.414215775 partant de 1 à 1e-05 près en 3 itérations.Dichot: f s'annule en 1.414213657 sur [1,2] à 1e-06 près en 20 itérations.Newton: f s'annule en 1.414213562 partant de 1 à 1e-06 près en 4 itérations.Dichot: f s'annule en 1.414213562 sur [1,2] à 1e-09 près en 28 itérations.Newton: f s'annule en 1.414213562 partant de 1 à 1e-09 près en 4 itérations.Dichot: g s'annule en 1.414213562 sur [1,2] à 1e-09 près en 28 itérations.Newton: g s'annule en 1.414213562 partant de 1 à 1e-09 près en 4 itérations.Dichot: h s'annule en 1.772453785 sur [0,2] à 1e-06 près en 21 itérations.Newton: h s'annule en 1.772453851 partant de 0 à 1e-06 près en 19 itérations.Dichot: sin s'annule en 0.000000000 sur [-1,1] à 1e-06 près en 0 itérations.Newton: sin s'annule en -0.000000000 partant de -1 à 1e-06 près en 4 itérations.Dichot: sin s'annule en 3.141592026 sur [3,4] à 1e-06 près en 18 itérations.Newton: sin s'annule en 3.141592653 partant de 3 à 1e-06 près en 2 itérations.Dichot: Pas de zéro trouvé pour cos sur [-1,1] en 2 itérations.Newton: cos s'annule en -1.570796327 partant de -1 à 1e-06 près en 3 itérations.Dichot: cos s'annule en 1.570796967 sur [1,2] à 1e-06 près en 17 itérations.Newton: cos s'annule en 1.570796327 partant de 1 à 1e-06 près en 3 itérations.Dichot: cos s'annule en 1.570796013 sur [0,6] à 1e-06 près en 20 itérations.Newton: cos s'annule en 20000.949629079 partant de 0 à 1e-06 près en 5 itérations.Dichot: cos s'annule en 7.853982449 sur [0,10] à 1e-06 près en 21 itérations.Newton: cos s'annule en 20000.949629079 partant de 0 à 1e-06 près en 5 itérations.

Code INS2.7: Algorithme de la méthode d’Euler pour une équadiff du premier ordre

# Initialisation des variables# Tant qu’on n’a pas atteint le t maximal d’intégration# On calcule la nouvelle valeur de y# On incrémente le temps# On stocke si besoin# Renvoie des tableaux concernant t et y


Code INS2.8: Implémentation de la méthode d’Euler pour une équadiff du premier ordre

1 def euler_premier_ordre(f,y0,t0=0,dt=1e-3,dt_out=1e-1,tmax=10):2 ’’’Méthode d’Euler pour une équadiff du premier ordre du type3 dy/dt = f(y(t),t) avec pour condition initiale y(t0)=y0.4

5 L’intégration va de t0 à tmax par pas de temps de valeur dt mais on ne6 renvoie les tableaux de sortie que lorsque le temps t dépasse t0 + n*dt_out7 de manière à éviter de surcharger la sortie quand on veut améliorer la8 précision en abaissant le pas de temps effectif d’intégration dt.9

10 Renvoie un doublet de tableaux contenant respectivement les temps11 d’intégration et les valeurs de la fonction y calculée à ces temps.’’’12 # Initialisation des variables13 y,t = y0,t0 # Valeurs initiales14 t_out= t0 + dt_out # Première sortie15 y_arr,t_arr=[y],[t] # Espaces de stockage16 while t < tmax: # Tant qu’on n’a pas atteint le t maximal d’intégration17 y = y + f(y,t)*dt # On calcule la nouvelle valeur de y18 t = t + dt # On incrémente le temps19 if t >= t_out: # On stocke si besoin20 y_arr.append(y) # Valeur de y21 t_arr.append(t) # Valeur de t22 t_out += dt_out # Prochaine étape de stockage23 return t_arr,y_arr # Renvoi des tableaux concernant t et y

Code INS2.9: Algorithme de la méthode d’Euler pour une équadiff du second ordre

# Initialisation des variables# Tant qu’on n’a pas atteint le t maximal d’intégration# On calcule les incrément en y et vy# Puis on met à jour les valeurs de y, vy et t# On stocke si besoin# Renvoie des tableaux concernant t, y (et vy si on veut un portrait de phase)


Code INS2.10: Implémentation de la méthode d’Euler pour une équadiff du second ordre

1 def euler_second_ordre(f,y0,v0=0,t0=0,dt=1e-3,dt_out=1e-1,tmax=10):2 ’’’Méthode d’Euler pour une équadiff du premier ordre du type3 d^2y/dt^2 = f(y(t),vy(t),t) avec pour conditions initiales4 y(t0)=y0 et vy(t0)=v0.5

6 L’intégration va de t0 à tmax par pas de temps de valeur dt mais on ne7 renvoie les tableaux de sortie que lorsque le temps t dépasse t0 + n*dt_out8 de manière à éviter de surcharger la sortie quand on veut améliorer la9 précision en abaissant le pas de temps effectif d’intégration dt.

10

11 Renvoie un triplet de tableaux contenant respectivement les temps12 d’intégration, les valeurs de la fonction y calculée à ces temps ainsi que13 les valeurs de sa dérivée (utiles si on veut faire un portrait de phase14 comme en physique).’’’15 # Initialisation des variables16 y,vy,t = y0,v0,t0 # Valeurs initiales17 t_out= t0 + dt_out # Première sortie18 y_arr,vy_arr,t_arr=[y],[vy],[t] # Espaces de stockage19 while t < tmax: # Tant qu’on n’a pas atteint le t maximal d’intégration20 dy = vy * dt # On calcule les incrément en y21 dvy= f(y,vy,t)*dt # et en vy22 y = y + dy # Et on incrément les valeurs23 vy= vy+ dvy # Question: pourquoi n’a-t-on pas tout fait en une étape ?24 t = t + dt # par exemple via y=y+vy*dt et vy=vy+f(y,vy,t)*dt ?25 if t >= t_out: # On stocke si besoin26 y_arr.append(y) # Valeur de y27 vy_arr.append(vy) # Valeur de vy28 t_arr.append(t) # Valeur de t29 t_out += dt_out # Prochaine étape de stockage30 return t_arr,y_arr,vy_arr # Renvoi des tableaux concernant t, y et vy


Code INS2.11: Procédure de tests pour les deux méthodes d’Euler implémentées

1 import numpy as np2 import matplotlib.pyplot as plt3

4 def teste_euler(euler,f,liste_dt,filename,solution,titre):5 ’’’Procédure permettant de tester plusieurs pas d’intégration pour les6 implémentations du premier ou du second ordre de la méthode d’Euler faites7 précédemment.’’’8 # On boucle sur les pas de temps donnés9 for dt in liste_dt:

10 res = euler(f,1,dt=dt)11 t = res[0]12 y = res[1]13 plt.plot(t,y,label=’dt={}’.format(dt))14 plt.plot(t,solution(t),label=’Solution analytique’)15 plt.legend(loc=’lower left’)16 plt.xlabel(’Temps $t$’)17 plt.ylabel(’Position $x$’)18 plt.title(titre)19 plt.savefig(filename)20 plt.clf()21

22 def harmonique(y,vy,t): return -y23 def expon(y,t): return y24

25 liste_dt = [v*10**-i for i in range(1,3) for v in [5,1] if (i,v) != (1,5)]26

27 teste_euler(euler_premier_ordre,expon,liste_dt,’euler1.png’,np.exp,’Premier ordre’)28 teste_euler(euler_second_ordre,harmonique,liste_dt,’euler2.png’,np.cos,’Second ordre’)




Code INS2.13: Méthode d’Euler, version vectorielle comme sp.integrate.odeint

1 def euler_vectoriel(f,y0,t0=0,dt=1e-3,dt_out=1e-1,tmax=10):2 ’’’Méthode d’Euler pour un système d’équadiff du premier ordre du type3 dy/dt = f(y(t),t) avec y un vecteur et pour condition initiale y(t0)=y0.4

5 L’intégration va de t0 à tmax par pas de temps de valeur dt mais on ne6 renvoie les tableaux de sortie que lorsque le temps t dépasse t0 + n*dt_out7 de manière à éviter de surcharger la sortie quand on veut améliorer la8 précision en abaissant le pas de temps effectif d’intégration dt.9

10 Renvoie un doublet de np.array contenant respectivement les temps11 d’intégration et les valeurs de la fonction y calculée à ces temps.12

13 La méthode est exactement la même que pour euler_premier_ordre si ce n’est14 que l’on fait des conversions "au vol" en np.array pour utiliser les15 facilité d’addition des tableaux de Numpy.’’’16 # Initialisation des variables, on notera que l’on impose le type du17 # stockage dans y pour éviter par exemple un np.array d’entiers qui ne18 # bougerait pas si on lui rajoute un petit flottant.19 y,t = np.array(y0,dtype=float),t020 t_out= t0 + dt_out # Première sortie21 y_arr,t_arr=[y],[t] # Espaces de stockage22 while t < tmax: # Tant qu’on n’a pas atteint le t maximal d’intégration23 y = y + np.array(f(y,t))*dt # On calcule la nouvelle valeur de y24 # NB: on ne peut pas utiliser la notation "y += " car cela modifie25 # l’ancien objet présent dans y plutôt que d’en créer un nouveau. On26 # se retrouverait alors avec un tableau de résultat contenant27 # uniquement le dernier point de mesure !28 t = t + dt # On incrémente le temps29 if t >= t_out: # On stocke si besoin30 y_arr.append(y) # Valeur de y31 t_arr.append(t) # Valeur de t32 t_out += dt_out # Prochaine étape de stockage33 return np.array(t_arr),np.array(y_arr) # Renvoi des tableaux concernant t et y34

35 def systeme_harmonique(y,t): # Transformation de l’oscillateur harmonique x’’+x=036 x,v = y # en système d’équations différentielles37 return [v,-x] # x’ = v et v’ = -x (soit v’+x=0 donc x’’+x=0)38

39 # On appelerait la fonction de la manière suivante:40 tps,sol = euler_vectoriel(systeme_harmonique,[1,0])41 position= sol[:,0]42 vitesse = sol[:,1]43

44 # Adaptation de la fonction teste_euler définie précédemment pour faire le graphe45 teste_euler2(euler_vectoriel,systeme_harmonique,liste_dt,’euler_vectoriel.png’,np.cos,’Version vectorielle’)



Code INS2.15: Différentes méthodes d’intégration

Pour intégrer une équation du typedy

dt= f(y, t) avec y = y(t)

Méthode d’Euler y(t+ dt) = y + f(y, t)× dt

Méthode de Heun, on affine l’estimation faite par EuleryEuler = y + f(y, t)× dt

y(t+ dt) = y +f(y, t) + f(yEuler, t+ dt)

2× dt

Méthode « RK4 »: Runge-Kutta d’ordre 4. On passe par le calcul de valeurs intermédiaires

α = y + f(y, t)× dt

2

β = y + f

(α, t+

dt

2

)× dt

2

γ = y + f

(β, t+

dt

2

)× dt

et on a y(t+ dt) = y +

[f(y, t) + 2f

(α, t+

dt

2

)+ 2f

(β, t+

dt

2

)+ f(γ, t+ dt)

]× dt

6


Code INS2.16: Méthode de Heun: intégrateur d’ordre 2

1 def heun_vectoriel(f,y0,t0=0,dt=1e-3,dt_out=1e-1,tmax=10):2 y,t = np.array(y0,dtype=float),t03 t_out= t0 + dt_out # Première sortie4 y_arr,t_arr=[y],[t] # Espaces de stockage5 while t < tmax: # Tant qu’on n’a pas atteint le t maximal d’intégration6 # Estimation "crue" par Euler7 y_euler = y + np.array(f(y,t))*dt8 # Puis affinage par Heun9 y = y + (np.array(f(y,t)) + np.array(f(y_euler,t+dt)))*dt/2

10 # NB: on ne peut pas utiliser la notation "y += " car cela modifie11 # l’ancien objet présent dans y plutôt que d’en créer un nouveau. On12 # se retrouverait alors avec un tableau de résultat contenant13 # uniquement le dernier point de mesure !14 t = t + dt # On incrémente le temps15 if t >= t_out: # On stocke si besoin16 y_arr.append(y) # Valeur de y17 t_arr.append(t) # Valeur de t18 t_out += dt_out # Prochaine étape de stockage19 return np.array(t_arr),np.array(y_arr) # Renvoi des tableaux concernant t et y

Code INS2.17: Résultats pour la méthode de Heun


Code INS2.18: Méthode de Runge-Kutta: intégrateur d’ordre 4

1 def rk4_vectoriel(f,y0,t0=0,dt=1e-3,dt_out=1e-1,tmax=10):2 y,t = np.array(y0,dtype=float),t03 t_out= t0 + dt_out # Première sortie4 y_arr,t_arr=[y],[t] # Espaces de stockage5 af = lambda y,t: np.array(f(y,t)) # Pour gagner de la place6 while t < tmax: # Tant qu’on n’a pas atteint le t maximal d’intégration7 # Les divers intermédiaires8 a = y + af(y,t)*dt/29 b = y + af(a,t+dt/2)*dt/2

10 c = y + af(b,t+dt/2)*dt11 # Puis remise ensemble12 y = y + (af(y,t) + 2*af(a,t+dt/2) + 2*af(b,t+dt/2) + af(c,t+dt))*dt/613 t = t + dt # On incrémente le temps14 if t >= t_out: # On stocke si besoin15 y_arr.append(y) # Valeur de y16 t_arr.append(t) # Valeur de t17 t_out += dt_out # Prochaine étape de stockage18 return np.array(t_arr),np.array(y_arr) # Renvoi des tableaux concernant t et y

Code INS2.19: Résultats pour la méthode de Runge-Kutta

Documents

Méthode de Newton et méthode d’Euler - pcsi.kleber.free.frpcsi.kleber.free.fr/IPT/doc/INS2_Newton_et_Euler_codes.pdf · E Bougnol, JJ Fleck, M Heckmann & M Kostyra, Kléber, PCSI