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
(Programmation python)
Ligne 60 : Ligne 60 :
  
 
l'algorithme ci-dessus revoie 1.99951171875 en 14 itérations.
 
l'algorithme ci-dessus revoie 1.99951171875 en 14 itérations.
 +
 +
==Méthode de Newton==
 +
On considère une fonction <math>f</math> de classe <math>{\cal C}^1</math> et on se donne <math>x(n)=x_n</math> dans l'ensemble de définition de <math>f</math> tel que <math>f'(x_n)\neq0</math>.
 +
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.
 +
 +
[[Fichier:NewtonIteration Anim.gif]]
 
{{DLMC|Informatique}}
 
{{DLMC|Informatique}}
 
[[Catégorie : Algorithmes et méthodes numériques ]]
 
[[Catégorie : Algorithmes et méthodes numériques ]]

Version du 21 septembre 2019 à 06:56

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

Dichotomie svg.svg

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.

NewtonIteration Anim.gif

Autres pages de la catégorie "Informatique"

Pages relatives à l'informatique en CPGE scientifiques.

Bases du langage Python

Algorithmes et méthodes numériques‎