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

De WikiMéca
Sauter à la navigation Sauter à la recherche

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

Principe

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 :

Théorème

Soit une application de classe et une solution de l'équation en laquelle .

Alors la suite définie par la relation de récurrence converge géométriquement vers . Si de plus est de classe , alors la convergence est quadratique.

Conditions de convergence - choix de la valeur de départ

Soit :

  • une application de classe
  • une solution de l'équation en laquelle
  • est convexe ( pour tout

Alors :

  • Si pour tout choix de dans la suite obtenue par la méthode de Newton est définie, décroissante et converge vers .
  • Si pour tout choix de dans la suite obtenue par la méthode de Newton est définie, croissante et converge vers .

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)/f_(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‎