GuideNonlinear equationsadvanced

High-order methods: Halley, Traub, Ostrowski and Jarratt

Three techniques to design iterative methods faster than Newton: quadrature formulas, scheme composition (with frozen derivative) and weight functions, with the Chebyshev-Halley and King families.

Composition: why chaining Newtons is not enough

Composing Newton with itself (double Newton) gives order 44, but requires 4 evaluations per iteration (ff and f′f' at two points): it is not optimal. Freezing the derivative reuses f′(xk)f'(x_k) in the second step and saves one evaluation, at the cost of some order. The result is Traub's method (or Potra-Pták), of order 3 with 3 evaluations:

yk=xk−f(xk)f′(xk)xk+1=yk−f(yk)f′(xk)\begin{aligned} y_k&=x_k-\frac{f(x_k)}{f'(x_k)}\\ x_{k+1}&=y_k-\frac{f(y_k)}{f'(x_k)} \end{aligned}
Traub's method (Potra-Pták): order 3 with frozen derivative.

Quadrature formulas

Just as in ODE methods, one can write f(x)=f(xk)+∫xkxf′(t) dtf(x)=f(x_k)+\int_{x_k}^{x}f'(t)\,dt and approximate the integral with different quadratures, using Newton as predictor yk=xk−f(xk)f′(xk)y_k=x_k-\frac{f(x_k)}{f'(x_k)}. The trapezoidal rule yields the trapezoid method; the midpoint rule and Simpson give their analogues:

xk+1=xk−2f(xk)f′(yk)+f′(xk)x_{k+1}=x_k-\frac{2f(x_k)}{f'(y_k)+f'(x_k)}
Trapezoid method.
xk+1=xk−f(xk)f′(xk+yk2)x_{k+1}=x_k-\frac{f(x_k)}{f'\bigl(\tfrac{x_k+y_k}{2}\bigr)}
Midpoint method.
xk+1=xk−6f(xk)f′(xk)+4f′(xk+yk2)+f′(yk)x_{k+1}=x_k-\frac{6f(x_k)}{f'(x_k)+4f'\bigl(\tfrac{x_k+y_k}{2}\bigr)+f'(y_k)}
Simpson method.

The Chebyshev-Halley family

Using the degree of logarithmic convexity Lf(xk)=f(xk)f′′(xk)f′(xk)2L_f(x_k)=\frac{f(x_k)f''(x_k)}{f'(x_k)^2} one builds a one-parameter family of third-order methods with second derivative:

xk+1=xk−f(xk)f′(xk)[1+12 Lf(xk)1−βLf(xk)]x_{k+1}=x_k-\frac{f(x_k)}{f'(x_k)}\left[1+\frac{1}{2}\,\frac{L_f(x_k)}{1-\beta L_f(x_k)}\right]
Chebyshev-Halley family, parameter β\beta.
  • β=0\beta=0: Chebyshev's method, xk+1=xk−ff′[1+Lf2]x_{k+1}=x_k-\frac{f}{f'}\bigl[1+\frac{L_f}{2}\bigr].
  • β=12\beta=\tfrac12: Halley's method, xk+1=xk−ff′[1+Lf2−Lf]x_{k+1}=x_k-\frac{f}{f'}\bigl[1+\frac{L_f}{2-L_f}\bigr].
  • β=1\beta=1: Super-Halley method, xk+1=xk−ff′[1+Lf−22(Lf−1)]x_{k+1}=x_k-\frac{f}{f'}\bigl[1+\frac{L_f-2}{2(L_f-1)}\bigr].
  • β→∞\beta\to\infty: Newton's method is recovered.

Weight functions: King, Ostrowski and Jarratt

The third technique multiplies Traub's second step by a weight function H(μ)H(\mu) of the variable μ=f(yk)f(xk)\mu=\frac{f(y_k)}{f(x_k)}:

yk=xk−f(xk)f′(xk)xk+1=yk−H(μk) f(yk)f′(xk)\begin{aligned} y_k&=x_k-\frac{f(x_k)}{f'(x_k)}\\ x_{k+1}&=y_k-H(\mu_k)\,\frac{f(y_k)}{f'(x_k)} \end{aligned}

Choosing H(μ)=1+βμ1+(β−2)μH(\mu)=\frac{1+\beta\mu}{1+(\beta-2)\mu} (which satisfies all three conditions for every β\beta) yields King's family, optimal of order 4:

xk+1=yk−f(xk)+βf(yk)f(xk)+(β−2)f(yk) f(yk)f′(xk)x_{k+1}=y_k-\frac{f(x_k)+\beta f(y_k)}{f(x_k)+(\beta-2)f(y_k)}\,\frac{f(y_k)}{f'(x_k)}
King's family. With β=0\beta=0 one obtains Ostrowski's method.
yk=xk−23 f(xk)f′(xk)xk+1=xk−12(3f′(yk)+f′(xk)3f′(yk)−f′(xk))f(xk)f′(xk)\begin{aligned} y_k&=x_k-\frac{2}{3}\,\frac{f(x_k)}{f'(x_k)}\\ x_{k+1}&=x_k-\frac{1}{2}\left(\frac{3f'(y_k)+f'(x_k)}{3f'(y_k)-f'(x_k)}\right)\frac{f(x_k)}{f'(x_k)} \end{aligned}
Jarratt's method, also optimal of order 4 (two derivatives and one evaluation of ff).

The actual behaviour of all these methods on test functions is analysed in the numerical comparison.