×

Fast switch and spline scheme for accurate inversion of nonlinear functions: the new first choice solution to Kepler’s equation. (English) Zbl 1433.65108

Summary: Numerically obtaining the inverse of a function is a common task for many scientific problems, often solved using a Newton iteration method. Here, we describe an alternative scheme, based on switching variables followed by spline interpolation, which can be applied to monotonic functions under very general conditions. To optimize the algorithm, we designed a specific ultra-fast spline routine. We also derive analytically the theoretical errors of the method and test it on examples that are of interest in physics. In particular, we compute the real branch of Lambert’s \(W(y)\) function, which is defined as the inverse of \(x\exp(x)\), and we solve Kepler’s equation. In all cases, our predictions for the theoretical errors are in excellent agreement with our numerical results, and are smaller than what could be expected from the general error analysis of spline interpolation by many orders of magnitude, namely by an astonishing \(3 \times 10^{- 22}\) factor for the computation of \(W\) in the range \(W(y) \in [0, 10]\), and by a factor \(2 \times 10^{- 4}\) for Kepler’s problem. In our tests, this scheme is much faster than Newton-Raphson method, by a factor in the range \(10^{- 4}\)–\(10^{- 3}\) for the execution time in the examples, when the values of the inverse function over an entire interval or for a large number of points are requested. For Kepler’s equation and tolerance \(10^{- 6}\) rad, the algorithm outperforms Newton’s method for all values of the number of points \(N \geq 2\).

MSC:

65J22 Numerical solution to inverse problems in abstract spaces

Software:

BRENT; SplinePak
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Fukushima, T., Numerical computation of inverse complete elliptic integrals of first and second kinds, J. Comput. Appl. Math., 249, 37-50 (2013) · Zbl 1302.65060
[2] Boyd, J. P., Four ways to compute the inverse of the complete elliptic integral of the first kind, Comput. Phys. Commun., 196, 13-18 (2015) · Zbl 1360.65080
[3] Corless, R. M.; Gonnet, G. H.; Hare, D. E.G.; Jeffrey, D. J.; Knuth, D. E., On the lambert w function, Adv. Comput. Math., 5, 329-359 (1996) · Zbl 0863.65008
[4] Fukushima, T., Precise and fast computation of lambert w-functions without transcendental function evaluations, J. Comput. Appl. Math., 244, 77-89 (2013) · Zbl 1260.65013
[5] Veberič, D., Lambert w function for applications in physics, Comput. Phys. Commun., 183, 2622-2628 (2012)
[6] Prussing, J. E.; Conway, B. A., Orbital Mechanics (2012), Oxford University Press
[7] Curtis, H. D., Orbital Mechanics for Engineering Students (2014), Elsevier
[8] Fukushima, T., A method solving Kepler’s equation without transcendental function evaluations, Celestial Mech. Dyn. Astron., 66, 309-319 (1997) · Zbl 0889.70002
[9] Mathews, J. H.; Fink, K. D., Numerical Methods Using MATLAB (2004), Pearson
[10] Danby, J.; Burkardt, T., The solution of Kepler’s equation, i, Celest. Mech., 31, 95-107 (1983) · Zbl 0572.70014
[11] Danby, J.; Burkardt, T., The solution of Kepler’s equation, iii, Celest. Mech., 40, 303-312 (1987) · Zbl 0647.70011
[12] Gerlach, J., Accelerated convergence in newton’s method, SIAM Rev., 36, 272-276 (1994) · Zbl 0814.65046
[13] Palacios, M., Kepler equation and accelerated newton method, J. Comput. Appl. Math., 138, 335-346 (2002) · Zbl 0998.65054
[14] Conway, B. A., An improved algorithm due to laguerre for the solution of Kepler’s equation, Celest. Mech., 39, 199-211 (1986) · Zbl 0613.70007
[15] Charles, E. D.; Tatum, J. B., The convergence of newton-raphson iteration with Kepler’s equation, Celest. Mech. Dyn. Astron., 69, 357-372 (1998) · Zbl 0947.70003
[16] Stumpf, L., Chaotic behaviour in the newton iterative function associated with Kepler’s equation, Celest. Mech. Dyn. Astron., 74, 95-109 (1999) · Zbl 0981.70003
[17] Ostrowski, A., Solutions of Equations and System of Equations (1960), Academic Press, New York · Zbl 0115.11201
[18] Brent, R. P., Algorithms for Minimization without Derivatives (1973), Englewood Cliffs, NJ: Prentice-Hall · Zbl 0245.65032
[19] Petkovic, M.; Neta, B.; Petkovic, L.; Dzunic, J., Multipoint Methods for Solving Nonlinear Equations (2013), Academic Press, Elsevier · Zbl 1286.65060
[20] Sharma, J. R.; Arora, H., A new family of optimal eighth order methods with dynamics for nonlinear equations, Appl. Math. Comput., 273, 15, 924-933 (2016) · Zbl 1410.65173
[21] Amat, S.; Busquier, S.; Gutierrez, J., Geometric constructions of iterative functions to solve nonlinear equations, J. Comput. Appl. Math., 157, 197-205 (2003) · Zbl 1024.65040
[22] Argyros, I., A note on the Halley method in Banach spaces, Appl. Math. Comput., 58, 215-224 (1993) · Zbl 0787.65034
[23] Hansen, E.; Patrick, M., A family of root finding methods, Appl. Math. Comput., 27, 257-269 (1977) · Zbl 0361.65041
[24] Kung, H.; Traub, J., Optimal order of one-point and multi-point iteration, J. ACM, 21, 643-651 (1974) · Zbl 0289.65023
[25] King, R., A family of fourth order methods for nonlinear equations, SIAM J. Numer. Anal., 10, 876-879 (1973) · Zbl 0266.65040
[26] Jarratt, P., Some fourth order multipoint iterative methods for solving equations, Math. Comput., 20, 434-437 (1966) · Zbl 0229.65049
[27] Sharma, J. R.; Guha, R. K.; Sharma, R., Some variants of hansen-patrick method with third and fourth order convergence, Appl. Math. Comput., 214, 171-177 (2009) · Zbl 1179.65051
[28] Neta, B.; Petkovic, M., Construction of optimal order nonlinear solvers using inverse interpolation, Appl. Math. Comput., 217, 2448-2455 (2010) · Zbl 1202.65062
[29] Sharifi, S.; Salimi, M.; Siegmund, S.; Lotfi, T., A new class of optimal four-point methods with convergence order 16 for solving nonlinear equations, Math. Comput. Simul., 119, 69-90 (2016) · Zbl 07313592
[30] Zheng, Q.; Li, J.; Huang, F., An optimal steffensen-type family for solving nonlinear equations, Appl. Math. Comput., 217, 23, 9592-9597 (2011) · Zbl 1227.65044
[31] Kansal, M.; Kanwar, V.; Bhatia, S., New modifications of Hansen-Patrick’s family with optimal fourth and eighth orders of convergence, Appl. Math. Comput., 269, 15, 507-519 (2015) · Zbl 1410.65163
[32] Schumaker, L. L., Spline Functions: Computational Methods (2015), SIAM, Philadelphia · Zbl 1333.65018
[33] Brinks, R., On the convergence of derivatives of b-splines to derivatives of the gaussian function, Comput. Appl. Math., 27, 1, 79-92 (1997) · Zbl 1154.42304
[34] Allasia, G.; Cavoretto, R.; Rossi, A. D., Lobachevsky spline functions and interpolation to scattered data, Comput. Appl. Math., 32, 1, 71-87 (2013) · Zbl 1273.65015
[35] Akima, H., A new method of interpolation and smooth curve fitting based on local procedures, J. Assoc. Comput. Mach., 17, 4, 589-602 (1970) · Zbl 0209.46805
[36] SciPy, 2016, https://docs.scipy.org/doc/scipy-0.18.1/reference/generated/scipy.interpolate.Akima1DInterpolato; SciPy, 2016, https://docs.scipy.org/doc/scipy-0.18.1/reference/generated/scipy.interpolate.Akima1DInterpolato
[37] Sonneveld, P., Errors in cubic spline interpolation, J. Eng. Math., 3, 2, 107-111 (1969) · Zbl 0183.44202
[38] de Boor, C., A Practical Guide to Splines (1978), Springer-Verlag New York · Zbl 0406.41003
[39] SciPy, 2016, https://docs.scipy.org/doc/scipy-0.18.1/reference/generated/scipy.interpolate.CubicSpline.html; SciPy, 2016, https://docs.scipy.org/doc/scipy-0.18.1/reference/generated/scipy.interpolate.CubicSpline.html
[40] SciPy, 2014, https://docs.scipy.org/doc/scipy-0.16.0/reference/generated/scipy.interpolate.PPoly.html; SciPy, 2014, https://docs.scipy.org/doc/scipy-0.16.0/reference/generated/scipy.interpolate.PPoly.html
[41] Numpy, 2014, https://docs.scipy.org/doc/numpy/reference/generated/numpy.searchsorted.html; Numpy, 2014, https://docs.scipy.org/doc/numpy/reference/generated/numpy.searchsorted.html
[42] Goldreich, O., Computational Complexity: A Conceptual Perspective (2008), Cambridge University Press · Zbl 1154.68056
[43] Richard Brent, P. Z., Modern Computer Arithmetic (2010), Cambridge University Press
[44] A. Sanchez-Gonzalez, 2016, https://github.com/alvarosg/pynverse; A. Sanchez-Gonzalez, 2016, https://github.com/alvarosg/pynverse
[45] SciPy, 2019, https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.brentq.html; SciPy, 2019, https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.brentq.html
[46] SciPy, 2014, https://docs.scipy.org/doc/scipy-0.14.0/reference/generated/scipy.special.lambertw.html; SciPy, 2014, https://docs.scipy.org/doc/scipy-0.14.0/reference/generated/scipy.special.lambertw.html
[47] Knuth, D., Sorting and searching. The Art of Computer Programming (1998), Addison-Wesley Professional · Zbl 0895.65001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.