The Schwarzian-Newton method for solving nonlinear equations, with applications

Segura, Javier

doi:10.1090/mcom/3119

The Schwarzian-Newton method for solving nonlinear equations, with applications
HTML articles powered by AMS MathViewer

by Javier Segura PDF

Math. Comp. 86 (2017), 865-879 Request permission

Abstract:

The Schwarzian-Newton method (SNM) can be defined as the minimal method for solving nonlinear equations $f(x)=0$ which is exact for any function $f$ with constant Schwarzian derivative. Exactness means that the method gives the exact root in one iteration for any starting value in a neighborhood of the root. This is a fourth order method which has Halley’s method as limit when the Schwarzian derivative tends to zero. We obtain conditions for the convergence of the SNM in an interval and show how this method can be applied for a reliable and fast solution of some problems, like the inversion of cumulative distribution functions (gamma and beta distributions) and the inversion of elliptic integrals.

References

S. Amat, S. Busquier, and J. M. Gutiérrez, Geometric constructions of iterative functions to solve nonlinear equations, J. Comput. Appl. Math. 157 (2003), no. 1, 197–205. MR 1996476, DOI 10.1016/S0377-0427(03)00420-5
John P. Boyd, Numerical, perturbative and Chebyshev inversion of the incomplete elliptic integral of the second kind, Appl. Math. Comput. 218 (2012), no. 13, 7005–7013. MR 2880288, DOI 10.1016/j.amc.2011.12.021
George H. Brown Jr., On Halley’s variation of Newton’s method, Amer. Math. Monthly 84 (1977), no. 9, 726–728. MR 461884, DOI 10.2307/2321256
Alfredo Deaño, Amparo Gil, and Javier Segura, New inequalities from classical Sturm theorems, J. Approx. Theory 131 (2004), no. 2, 208–230. MR 2106538, DOI 10.1016/j.jat.2004.09.006
Toshio Fukushima, Numerical inversion of a general incomplete elliptic integral, J. Comput. Appl. Math. 237 (2013), no. 1, 43–61. MR 2966887, DOI 10.1016/j.cam.2012.07.002
A. Gil, J. Segura, and N. M. Temme, An efficient algorithm for the inversion of the cumulative central beta distribution, accepted for publication in Numer. Algorithms, DOI 10.1007/s11075-016-0139-2.
Amparo Gil, Javier Segura, and Nico M. Temme, Efficient and accurate algorithms for the computation and inversion of the incomplete gamma function ratios, SIAM J. Sci. Comput. 34 (2012), no. 6, A2965–A2981. MR 3023741, DOI 10.1137/120872553
Amparo Gil, Javier Segura, and Nico M. Temme, Gammachi: a package for the inversion and computation of the gamma and chi-square cumulative distribution functions (central and noncentral), Comput. Phys. Commun. 191 (2015), 132–139.
A. Melman, Geometry and convergence of Euler’s and Halley’s methods, SIAM Rev. 39 (1997), no. 4, 728–735. MR 1491054, DOI 10.1137/S0036144595301140
R. B. Paris, Incomplete gamma and related functions, NIST handbook of mathematical functions, U.S. Dept. Commerce, Washington, DC, 2010, pp. 175–192. MR 2655348
G. S. Salehov, On the convergence of the process of tangent hyperbolas, Doklady Akad. Nauk SSSR (N.S.) 82 (1952), 525–528 (Russian). MR 0048909
T. R. Scavo and J. B. Thoo, On the geometry of Halley’s method, Amer. Math. Monthly 102 (1995), no. 5, 417–426. MR 1327786, DOI 10.2307/2975033
Javier Segura, Reliable computation of the zeros of solutions of second order linear ODEs using a fourth order method, SIAM J. Numer. Anal. 48 (2010), no. 2, 452–469. MR 2646104, DOI 10.1137/090747762
J. F. Traub, Iterative methods for the solution of equations, Prentice-Hall Series in Automatic Computation, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1964. MR 0169356