Math 2.0

Numerical analysis Nonlinear equations Theorem

Muller's method

Builds on Polynomial interpolationSecant methodRate of convergenceComplex numbers

Statement

Let ff be a complex function that is holomorphic near a simple zero rr, so f(r)=0f(r) = 0 and f′(r)≠0f'(r) \ne 0. Given three distinct points xk−2,xk−1,xkx_{k-2}, x_{k-1}, x_k, write f[xi,xj]=f(xi)−f(xj)xi−xjf[x_i, x_j] = \dfrac{f(x_i) - f(x_j)}{x_i - x_j} and f[xk,xk−1,xk−2]=f[xk,xk−1]−f[xk−1,xk−2]xk−xk−2f[x_k, x_{k-1}, x_{k-2}] = \dfrac{f[x_k, x_{k-1}] - f[x_{k-1}, x_{k-2}]}{x_k - x_{k-2}}, and put w=f[xk,xk−1]+f[xk,xk−2]−f[xk−1,xk−2].w = f[x_k, x_{k-1}] + f[x_k, x_{k-2}] - f[x_{k-1}, x_{k-2}]. Muller's method defines xk+1=xk−2f(xk)w±w2−4f(xk) f[xk,xk−1,xk−2],x_{k+1} = x_k - \frac{2 f(x_k)}{w \pm \sqrt{w^2 - 4 f(x_k) \, f[x_k, x_{k-1}, x_{k-2}]}}, where the sign is chosen so that the denominator has the larger absolute value. Then there is δ>0\delta > 0 with the following property. For all starting points 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 point xk+1x_{k+1} is the zero, closest to xkx_k, of the interpolating polynomial of degree at most 22 through (xk−2,f(xk−2))(x_{k-2}, f(x_{k-2})), (xk−1,f(xk−1))(x_{k-1}, f(x_{k-1})) and (xk,f(xk))(x_k, f(x_k)). The formula is the quadratic formula written in the stable form that avoids cancellation. The errors ek=xk−re_k = x_k - r satisfy ek+1≈Cekek−1ek−2e_{k+1} \approx C e_k e_{k-1} e_{k-2}, which gives the stated order. Because of the square root, the iterates can leave the real line, so the method finds complex zeros even from real starting points. This makes it useful for zeros of real polynomials that are not real. With a line through two points instead of a parabola through three, the same idea gives the secant method.

Going deeper

For a student

The method needs no derivatives and one new function value per step. Its order is about 1.841.84, between the secant method and Newton's method. It is a common choice for finding all roots of a polynomial one at a time, combined with deflation.

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
Complex numbers, object, no evidence levelComplex numbersobjectContinuously differentiable function, concept, no evidence levelContinuously differen…conceptDerivative, concept, no evidence levelDerivativeconceptPolynomial interpolation, concept, no evidence levelPolynomial interpolat…conceptRate 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 methodstatementMuller's method, statement, no evidence levelMuller's methodstatement
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. Complex numbers object
  2. Continuously differentiable function concept
  3. Derivative concept
  4. Polynomial interpolation concept
  5. Rate of convergence concept
  6. Root-finding algorithm concept
  7. Second derivative concept
  8. Secant method statement
  9. Muller's method statement

Further reading

  1. Web https://en.wikipedia.org/wiki/Muller%27s_method
About this page
TagE4FMVDQ2GR
URIm2://E4FMVDQ2GR
Kindstatement, theorem
WritingW0 stub
MSC65H05, 65H04
StatusThis copy of the site has no build data. Run m2 status E4FMVDQ2GR.
AboutRoot-finding algorithm
UsesPolynomial interpolation, Secant method, Rate of convergence, Complex numbers
Same as

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • 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

No page links to this page yet.