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

详细信息    查看全文

• 作者：M. Ç ; etin Koç ; ak
• 关键词：Algebraic equations solvers ; Iterative methods ; Fixed-point iterations ; Simulation ; Convergence order ; Direct substitution ; Partial substitution ; Halley's method ; Newton's method ; Acceleration of iteration
• 刊名：Journal of Computational and Applied Mathematics
• 出版年：2008
• 出版时间：1 September 2008
• 年：2008
• 卷：218
• 期：2
• 页码：350-363
• 全文大小：202 K

文摘

Direct substitution x_k+1=g(x_k) 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 g_m(x)=(g(x)-m(x)x)/(1-m(x)) or, equivalently, through partial substitution g_mps(x)=x+G(x)(g-x), G(x)=1/(1-m(x)). As a matter of fact, g_m(x)≡g_mps(x) is the point of intersection of a linearised g with the 39a21ea76521a9b790"" title=""Click to view the MathML source"" alt=""Click to view the MathML source"">g=x line. Aitken's and Wegstein's accelerators are special cases of g_m. 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 g_m. 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.