Simple geometry facilitates iterative solution of a nonlinear equation via a special transformation to accelerate convergence to third order

摘要

Direct substitution xk+1=g(xk) generally represents iterative techniques for locating a root z of a nonlinear equation f(x). At the solution, f(z)=0 and g(z)=z. Efforts continue worldwide both to improve old iterators and create new ones. This is a study of convergence acceleration by generating secondary solvers through the transformation gm(x)=(g(x)-m(x)x)/(1-m(x)) or, equivalently, through partial substitution gmps(x)=x+G(x)(g-x), G(x)=1/(1-m(x)). As a matter of fact, gm(x)≡gmps(x) is the point of intersection of a linearised g with the g=x line. Aitken's and Wegstein's accelerators are special cases of gm. Simple geometry suggests that m(x)=(g′(x)+g′(z))/2 is a good approximation for the ideal slope of the linearised g. Indeed, this renders a third-order gm. The pertinent asymptotic error constant has been determined. The theoretical background covers a critical review of several partial substitution variants of the well-known Newton's method, including third-order Halley's and Chebyshev's solvers. The new technique is illustrated using first-, second-, and third-order primaries. A flexible algorithm is added to facilitate applications to any solver. The transformed Newton's method is identical to Halley's. The use of m(x)=(g′(x)+g′(z))/2 thus obviates the requirement for the second derivative of f(x). Comparison and combination with Halley's and Chebyshev's solvers are provided. Numerical results are from the square root and cube root examples.