In numerical analysis, inverse quadratic interpolation is a root-finding algorithm, meaning that it is an algorithm for solving equations of the form f(x) = 0. The idea is to use quadratic interpolation to approximate the inverse of f. This algorithm is rarely used on its own, but it is important because it forms part of the popular Brent's method.
The method The inverse quadratic interpolation algorithm is defined by the recurrence relation
x n + 1 = f n − 1 f n ( f n − 2 − f n − 1 ) ( f n − 2 − f n ) x n − 2 + f n − 2 f n ( f n − 1 − f n − 2 ) ( f n − 1 − f n ) x n − 1 {\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}}
+ f n − 2 f n − 1 ( f n − f n − 2 ) ( f n − f n − 1 ) x n , {\displaystyle {}+{\frac {f_{n-2}f_{n-1}}{(f_{n}-f_{n-2})(f_{n}-f_{n-1})}}x_{n},}
where fk = f(xk). As can be seen from the recurrence relation, this method requires three initial values, x0, x1 and x2.
Explanation of the method We use the three preceding iterates, xn−2, xn−1 and xn, with their function values, fn−2, fn−1 and fn. Applying the Lagrange interpolation formula to do quadratic interpolation on the inverse of f yields
… excerpt ends here. Continue reading the full article.
