Interpolation quadratique inverse

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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 méthode de Brent.

La méthode[modifier | modifier le code]

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[modifier | modifier le code]

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 (analyse numérique)[modifier | modifier le code]

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, les calculs via l'algorithme échouent complètement.


Comparaison avec d'autres méthodes[modifier | modifier le code]

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:

Références[modifier | modifier le code]