Interpolation quadratique inverse


Interpolation quadratique inverse

En Analyse numérique, l'interpolation quadratique inverse est un Algorithme de recherche d'un zéro d'une fonction: c'est une méthode permettant de résoudre en x des équations du type f(x) = 0. L'idée est d'utiliser une interpolation quadratique afin d'approcher la fonction inverse de f. Cet algorithme est rarement utilisé seul mais prend sa place dans la populaire Méthode de Brent.

Sommaire

La méthode

L'algorithme de l'interpolation quadratique inverse est donné par la Relation de récurrence:

 x_{n+1} = \frac{f_{n-1}f_n}{(f_{n-2}-f_{n-1})(f_{n-2}-f_n)} x_{n-2} + \frac{f_{n-2}f_n}{(f_{n-1}-f_{n-2})(f_{n-1}-f_n)} x_{n-1}
 {} + \frac{f_{n-2}f_{n-1}}{(f_n-f_{n-2})(f_n-f_{n-1})} x_n,

fk = f(xk). Cette méthode nécessite donc trois valeurs initiales x0, x1 et x2.

Explication de la méthode

On utilise les trois itérations précédentes xn-2, xn-1 et xn, avec leur image, fn-2, fn-1 et fn. En appliquant une Interpolation lagrangienne quadratique, on trouve l'approximation suivante de l'inverse de f

 f^{-1}(y) = \frac{(y-f_{n-1})(y-f_n)}{(f_{n-2}-f_{n-1})(f_{n-2}-f_n)} x_{n-2} + \frac{(y-f_{n-2})(y-f_n)}{(f_{n-1}-f_{n-2})(f_{n-1}-f_n)} x_{n-1}
 {} + \frac{(y-f_{n-2})(y-f_{n-1})}{(f_n-f_{n-2})(f_n-f_{n-1})} x_n.

On recherche une racine de f, donc on remplace y = f(x) = 0 dans la relation précédente et on obtient la relation souhaitée.

Comportement

Le comportement asymptotique est très bon: en général, les itérations xn convergent rapidement vers la racine, une fois qu'elles en sont proches. Toutefois, les performances sont souvent assez pauvres si on part trop loin de la racine. Par exemple, si par malchance deux des images fn-2, fn-1 et fn coïncident, l'algorithme échoue complètement.


Comparaison avec d'autres méthodes

Comme indiqué plus haut, l'interpolation quadratique inverse est utilisée dans la Méthode de Brent. Il existe d'autres liens avec les autres méthodes:

Voir aussi


Références


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Interpolation quadratique inverse de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… …   Wikipédia en Français

  • Methode de Brent — Méthode de Brent En analyse numérique, la méthode de Brent est un algorithme de recherche d un zéro d une fonction combinant la méthode de dichotomie, la méthode de la sécante et l’interpolation quadratique inverse. À chaque itération, elle… …   Wikipédia en Français

  • Méthode De Brent — En analyse numérique, la méthode de Brent est un algorithme de recherche d un zéro d une fonction combinant la méthode de dichotomie, la méthode de la sécante et l’interpolation quadratique inverse. À chaque itération, elle décide laquelle de ces …   Wikipédia en Français

  • Méthode de Brent — En analyse numérique, la méthode de Brent est un algorithme de recherche d un zéro d une fonction combinant la méthode de dichotomie, la méthode de la sécante et l’interpolation quadratique inverse. À chaque itération, elle décide laquelle de ces …   Wikipédia en Français

  • Méthode de brent — En analyse numérique, la méthode de Brent est un algorithme de recherche d un zéro d une fonction combinant la méthode de dichotomie, la méthode de la sécante et l’interpolation quadratique inverse. À chaque itération, elle décide laquelle de ces …   Wikipédia en Français

  • Algorithme De Recherche D'un Zéro D'une Fonction — Un algorithme de recherche d un zéro d’une fonction est une méthode numérique ou un algorithme de recherche d’une valeur approchée d’un x vérifiant f(x) = 0, pour une fonction donnée f. Ici, x est un nombre réel appelé zéro de f ou lorsque f est… …   Wikipédia en Français

  • Algorithme de recherche d'un zero d'une fonction — Algorithme de recherche d un zéro d une fonction Un algorithme de recherche d un zéro d’une fonction est une méthode numérique ou un algorithme de recherche d’une valeur approchée d’un x vérifiant f(x) = 0, pour une fonction donnée f. Ici, x est… …   Wikipédia en Français

  • Algorithme de recherche d'un zéro d'une fonction — Un algorithme de recherche d un zéro d’une fonction est une méthode numérique ou un algorithme de recherche d’une valeur approchée d’un x vérifiant f(x) = 0, pour une fonction donnée f. Ici, x est un nombre réel appelé zéro de f ou lorsque f est… …   Wikipédia en Français

  • Liste des articles de mathematiques — Projet:Mathématiques/Liste des articles de mathématiques Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou probabilités et statistiques via l un des trois bandeaux suivants  …   Wikipédia en Français

  • Variable régionalisée — La VR comme phénomène physique : topographie de la ville de Binche …   Wikipédia en Français