Recherche des zéros d'une fonction : méthode par dichotomie et méthode de Newton : Différence entre versions

De WikiMéca
Sauter à la navigation Sauter à la recherche
(Méthode de Newton)
(Différence x_{n+1}-x_{n} comme critère d'arrêt)
(3 révisions intermédiaires par le même utilisateur non affichées)
Ligne 80 : Ligne 80 :
 
La méthode de Newton consiste à  utiliser la tangente au graphe de <math>f</math> au point d'abscisse <math>x_n</math>. Elle coupe l'axe <math>(0x)</math>. On désigne par <math>x(n+1)=x_{n+1}</math> l'abscisse de ce point d'intersection. On réitère avec la tangente au point d'abscisse <math>x_{n+1}</math> jusqu'à s'approcher de la solution.
 
La méthode de Newton consiste à  utiliser la tangente au graphe de <math>f</math> au point d'abscisse <math>x_n</math>. Elle coupe l'axe <math>(0x)</math>. On désigne par <math>x(n+1)=x_{n+1}</math> l'abscisse de ce point d'intersection. On réitère avec la tangente au point d'abscisse <math>x_{n+1}</math> jusqu'à s'approcher de la solution.
  
La relation de récurrence s'écrit : <math>x_{n+1} =  x_{n} - \frac f(x_{n}) f'(x_{n})  
+
La relation de récurrence s'écrit : <math>x_{n+1} =  x_{n} - \frac {f(x_{n})}{ f'(x_{n})} </math>
  
 +
<gallery style="margin:0;" mode="slideshow" widths=450px>
 +
Image:Newton1.png
 +
Image:Newton2.png
 +
Image:Newton3.png
 +
Image:Newton4.png
 +
Image:Newton5.png
 +
Image:Newton6.png
 +
Image:Newton7.png
 +
Image:Newton8.png
 +
Image:Newton9.png
 +
Image:Newton10.png
 +
Image:Newton11.png
 +
Image:Newton12.png
 +
Image:Newton13.png
 +
Image:Newton14.png
 +
Image:Newton15.png
 +
Image:Newton16.png
 +
Image:Newton17.png
 +
Image:Newton18.png
 +
</gallery>
 +
Sous certaines hypothèses, on peut démontrer qu'une telle suite <math>(x_n)_{n\in\N}</math> converge vers un zéro de <math>f</math>.
 +
 +
===Programmation python===
 +
==== Nombre d'itération comme critère d'arrêt====
 +
Soit :
 +
* une fonction <syntaxhighlight lang="Python" inline>f</syntaxhighlight> dont on recherche un zéro;
 +
* une fonction <syntaxhighlight lang="Python" inline>f_</syntaxhighlight> la fonction dérivée de <syntaxhighlight lang="Python" inline>f</syntaxhighlight>;
 +
* un réel <syntaxhighlight lang="Python" inline>x0</syntaxhighlight> proche de la racine recerchée;
 +
* et un réel strictement positif <syntaxhighlight lang="Python" inline>N</syntaxhighlight>, définissant la nombre d'itérations.
 +
 +
La fonction suivante renvoie la dernière valeur de <math>x</math> s'approchant de la racine de <syntaxhighlight lang="Python" inline>f</syntaxhighlight>.
  
 +
<syntaxhighlight lang="Python" line='line'>
 +
def Newton1(f,f_,x0,N) :
 +
x=x0
 +
for _ in range(N) :
 +
x=x-f(x)/df(x)
 +
return x
 +
</syntaxhighlight>
 +
==== Différence <math>x_{n+1}-x_{n}</math> comme critère d'arrêt====
 +
On peut aussi mettre en paramètre un réel <syntaxhighlight lang="Python" inline>eps>0</syntaxhighlight> et continuer les itérations tant que <math>|x_{n+1}-x_n|>eps</math>.
 +
<syntaxhighlight lang="Python" line='line'>
 +
def Newton2(f,f_,x0,eps) :
 +
x=x0
 +
ecart=f(x)/f_(x)
 +
while abs(ecart)>eps :
 +
x=x-ecart
 +
ecart=f(x)/f_(x)
 +
return x
 +
</syntaxhighlight>
  
Sous certaines hypothèses, on peut démontrer qu'une telle suite <math>(x_n)_{n\in\N}</math> converge vers un zéro de <math>f</math>.
 
 
{{DLMC|Informatique}}
 
{{DLMC|Informatique}}
 
[[Catégorie : Algorithmes et méthodes numériques ]]
 
[[Catégorie : Algorithmes et méthodes numériques ]]

Version du 22 septembre 2019 à 15:50

Méthode de dichotomie

Généralités

On rappelle que, d'après le théorème des valeurs intermédiaires, si la fonction est continue et si alors, il existe tel que .

L'algorithme de dichotomie permet de trouver une valeur approchée d'un tel à une précision donnée. Par récurrence, on coupe l'intervalle en deux et on cherche dans quelle moitié est la solution.

On construit deux suites et de la façon suivante:

  • on pose et
  • on calcul qui coupe l'intervalle en deux :
  • on cherche dans lequel des deux intervalles ou se situe la solution :
    • si , la solution est dans le premier intervalle. On continue alors la recherche dans celui-ci en posant et
    • sinon, on continue la recherche dans l'autre intervalle en posant et .
  • on arrête la recherche lorsque

Alors, on peut démontrer que et sont adjacentes et qu'elles convergent vers un zéro de .

Complexité

Le nombre d’itérations sera tel que l'intervalle aura été coupée en deux jusqu'à la sortie de la boucle lorsque , c'est à dire que la boucle s'est exécutée n fois tel que .

En calculant n :

La complexité est donc un .


Programmation python

Soit :

  • une fonction f dont on recherche un zéro;
  • des réels a et b, bornes de l'intervalle de recherche;
  • et un réel strictement positif eps, définissant la précision de la recherche.

Le code suivant renvoie la première valeur de pour laquelle et le nombre d'itérations.

1 N=0
2 while b-a>eps :
3 	c=(a+b)/2
4 	N=N+1
5 	if f(a)*f(c)<0 : #si la solution est dans l intervalle [a,c[
6 		b=c  #on continue la recherche dans [a,c[
7 	else :       #sinon
8 		a=c  #on continue la recherche dans [c,b]
9 print(a,N)

Exemple :

Pour:

  • ;

l'algorithme ci-dessus revoie 1.99951171875 en 14 itérations.

Méthode de Newton

On considère une fonction de classe et on se donne dans l'ensemble de définition de tel que . La méthode de Newton consiste à utiliser la tangente au graphe de au point d'abscisse . Elle coupe l'axe . On désigne par l'abscisse de ce point d'intersection. On réitère avec la tangente au point d'abscisse jusqu'à s'approcher de la solution.

La relation de récurrence s'écrit :

Sous certaines hypothèses, on peut démontrer qu'une telle suite converge vers un zéro de .

Programmation python

Nombre d'itération comme critère d'arrêt

Soit :

  • une fonction f dont on recherche un zéro;
  • une fonction f_ la fonction dérivée de f;
  • un réel x0 proche de la racine recerchée;
  • et un réel strictement positif N, définissant la nombre d'itérations.

La fonction suivante renvoie la dernière valeur de s'approchant de la racine de f.

1 def Newton1(f,f_,x0,N) :
2 		x=x0
3 		for _ in range(N) :
4 				x=x-f(x)/df(x)
5 		return x

Différence comme critère d'arrêt

On peut aussi mettre en paramètre un réel eps>0 et continuer les itérations tant que .

1 def Newton2(f,f_,x0,eps) :
2 		x=x0
3 		ecart=f(x)/f_(x)
4 		while abs(ecart)>eps :
5 				x=x-ecart
6 				ecart=f(x)/f_(x)
7 		return x


Autres pages de la catégorie "Informatique"

Pages relatives à l'informatique en CPGE scientifiques.

Bases du langage Python

Algorithmes et méthodes numériques‎