Math 2.0

Numerical analysis Nonlinear equations Theorem

Inverse quadratic interpolation

Builds on Lagrange interpolationSecant methodRate of convergenceInverse function

Statement

Let ff be a real function that is three times continuously differentiable on an open interval II, and let r∈Ir \in I satisfy f(r)=0f(r) = 0 and f′(r)≠0f'(r) \ne 0. Given three points xn−2,xn−1,xnx_{n-2}, x_{n-1}, x_n whose values fk=f(xk)f_k = f(x_k) are pairwise distinct, inverse quadratic interpolation defines xn+1=fn−1fn xn−2(fn−2−fn−1)(fn−2−fn)+fn−2fn xn−1(fn−1−fn−2)(fn−1−fn)+fn−2fn−1 xn(fn−fn−2)(fn−fn−1).x_{n+1} = \frac{f_{n-1} f_n \, x_{n-2}}{(f_{n-2} - f_{n-1})(f_{n-2} - f_n)} + \frac{f_{n-2} f_n \, x_{n-1}}{(f_{n-1} - f_{n-2})(f_{n-1} - f_n)} + \frac{f_{n-2} f_{n-1} \, x_n}{(f_n - f_{n-2})(f_n - f_{n-1})}. Then there is δ>0\delta > 0 with the following property. For all starting points x0,x1,x2x_0, x_1, x_2 within δ\delta of rr for which the iteration is defined, the iterates converge to rr with order q≈1.839q \approx 1.839. Here qq is the real root of q3=q2+q+1q^3 = q^2 + q + 1.

Remarks

The new point is the value at y=0y = 0 of the Lagrange interpolation polynomial of degree at most 22 through the points (fk,xk)(f_k, x_k). This polynomial approximates the inverse function of ff near rr, so its value at 00 approximates r=f−1(0)r = f^{-1}(0). The error analysis gives en+1≈Cenen−1en−2e_{n+1} \approx C e_n e_{n-1} e_{n-2} for the errors ek=xk−re_k = x_k - r, which leads to the stated order. Interpolating xx as a function of yy avoids solving a quadratic equation, unlike Muller's method. The method breaks down when two of the values fkf_k coincide, and it can diverge from poor starting points. For this reason it is used inside safeguarded methods such as Brent's method. With two points instead of three, the same idea gives the secant method.

Going deeper

For a student

The method needs no derivatives and only one new function value per step. Its order is a little less than 22 but better than the secant method's 1.6181.618. It is fast but fragile, so libraries combine it with bisection to keep a bracket around the root.

Reading path

To understand this page from the ground up, read these 9 pages in order. The foundations come first.

Show the path as a graph
Continuously differentiable function, concept, no evidence levelContinuously differen…conceptDerivative, concept, no evidence levelDerivativeconceptInverse function, concept, no evidence levelInverse functionconceptLagrange interpolation, concept, no evidence levelLagrange interpolationconceptRate of convergence, concept, no evidence levelRate of convergenceconceptRoot-finding algorithm, concept, no evidence levelRoot-finding algorithmconceptSecond derivative, concept, no evidence levelSecond derivativeconceptSecant method, statement, no evidence levelSecant methodstatementInverse quadratic interpolation, statement, no evidence levelInverse quadratic int…statement
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Continuously differentiable function concept
  2. Derivative concept
  3. Inverse function concept
  4. Lagrange interpolation concept
  5. Rate of convergence concept
  6. Root-finding algorithm concept
  7. Second derivative concept
  8. Secant method statement
  9. Inverse quadratic interpolation statement

Where this leads

1 page builds on this one.

Further reading

  1. Web https://en.wikipedia.org/wiki/Inverse_quadratic_interpolation
About this page
TagNW1XQ95R5P
URIm2://NW1XQ95R5P
Kindstatement, theorem
WritingW0 stub
MSC65H05, 65D05
StatusThis copy of the site has no build data. Run m2 status NW1XQ95R5P.
AboutRoot-finding algorithm
UsesLagrange interpolation, Secant method, Rate of convergence, Inverse function
Same as

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • an inventory row: the row of the inventory that the node accounts for (0 of 1)
  • a source with a locator (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

Used by