Inverse quadratic interpolation: Difference between revisions

Revision as of 19:09, 6 October 2011

Latest revision as of 23:27, 21 July 2024

(16 intermediate revisions by 14 users not shown)

Line 1:

{{Short description|Method of solving equations}}

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 [[polynomial interpolation|quadratic interpolation]] to approximate the [[inverse function|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]].

Line 17 ⟶ 18:

:<math> 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} </math>

:::::<math> {}\qquad + \frac{(y-f_{n-2})(y-f_{n-1})}{(f_n-f_{n-2})(f_n-f_{n-1})} x_n. </math>

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 youthe doinitial notvalues startare verynot close to the actual root. For instance, if by any chance two of the function values ''f''_{''n''&minus;2}, ''f''_{''n''&minus;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,84 itas can be proved by the[[secant Secant Methodmethod]] analysis.

==Comparison with other root-finding methods==

Line 32 ⟶ 33:

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 [[MüllerMuller's method]].

==See also==

Line 39 ⟶ 40:

==References==

*[[James F. Epperson]], [httphttps://books.google.com/books?id=Mp8-z5mHptcC&lpg=PP1&pg=PA182#v=onepage&q&f=false An introduction to numerical methods and analysis], pages 182-185182–185, Wiley-Interscience, 2007. ISBN 9780470049631{{isbn|978-0-470-04963-1}}

*[[Cleve Moler]], [http://www.mathworks.com/moler/chapters.html Numerical Computing with MATLAB], Section 4.5, Society for Industrial and Applied Mathematics (SIAM), 2004. ISBN 0-89871-560-1.

*[[James F. Epperson]], [http://books.google.com/books?id=Mp8-z5mHptcC&lpg=PP1&pg=PA182#v=onepage&q&f=false An introduction to numerical methods and analysis], pages 182-185, Wiley-Interscience, 2007. ISBN 9780470049631

{{root-finding algorithms}}

[[Category:Root-finding algorithms]]

[[fr:Interpolation quadratique inverse]]