# Inverse Quadratic Interpolation For Finding Roots of Linear and Nonlinear Equations

by admin in Math, Statistics, and Optimization , MATLAB Family , Roots of Equation on June 14, 2019**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.

### Example On Using This Code

**Input**

f = @(x) x.^2-exp(x); % Equation we interested to solve a = -10; % First interval [a b] Term a b = +10; % Final interval [a b] Term b err = 0.001; % Error Tolerance

**Output**

Root X = -0.70347 , # Iterations = 7 , Accuracy f(X) = -6.4709e-13

### Contents

- The method
- Explanation of the method
- Behaviour
- Comparison with other root-finding methods
- See also
- References

### The Method

The inverse quadratic interpolation algorithm is defined by the recurrence relation

where *f*_{k} = *f*(*x*_{k}). As can be seen from the recurrence relation, this method requires three initial values, *x*_{0}, *x*_{1} and *x*_{2}.

### Explanation of the Method

We use the three preceding iterates, *x*_{n−2}, *x*_{n−1} and *x*_{n}, with their function values, *f*_{n−2}, *f*_{n−1} and *f*_{n}. Applying the Lagrange interpolation formula to do quadratic interpolation on the inverse of *f* yields

We are looking for a root of *f*, so we substitute *y* = *f*(*x*) = 0 in the above equation and this results in the above recursion formula.

### Behaviour

The asymptotic behaviour is very good: generally, the iterates *x*_{n} converge fast to the root once they get close. However, performance is often quite poor if you do not start very close to the actual root. For instance, if by any chance two of the function values *f*_{n−2}, *f*_{n−1} and *f*_{n} coincide, the algorithm fails completely. Thus, inverse quadratic interpolation is seldom used as a stand-alone algorithm. The order of this convergence is approximately 1.8 as can be proved by Secant Method analysis.

### Comparison With Other Root-Finding Methods

As noted in the introduction, inverse quadratic interpolation is used in Brent’s method. Inverse quadratic interpolation is also closely related to some other root-finding methods. Using linear interpolation instead of quadratic interpolation gives the secant method. Interpolating *f* instead of the inverse of *f* gives Muller’s method.

### References

- James F. Epperson, An introduction to numerical methods and analysis, pages 182-185, Wiley-Interscience, 2007. ISBN 978-0-470-04963-1

Share Now!