Interpolation quadratique inverse

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

${\displaystyle 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}}$

${\displaystyle {}+{\frac {f_{n-2}f_{n-1}}{(f_{n}-f_{n-2})(f_{n}-f_{n-1})}}x_{n},}$

où f_k = f(x_k). Cette méthode nécessite donc trois valeurs initiales x₀, x₁ et x₂.

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

${\displaystyle 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}}$

${\displaystyle {}+{\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.

Le comportement asymptotique est très bon: en général, les itérations x_n 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 f_n-2, f_n-1 et f_n coïncident, les calculs via l'algorithme échouent complètement.

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

• remplacer l'interpolation quadratique par une interpolation linéaire donne la méthode de la sécante;
• interpoler f plutôt que son inverse donne la méthode de Müller.

• Cleve Moler, Numerical Computing with MATLAB, Section 4.5, Society for Industrial and Applied Mathematics (SIAM), 2004. (ISBN 0-89871-560-1).