×

zbMATH — the first resource for mathematics

Full linear multistep methods as root-finders. (English) Zbl 1426.65069
Summary: Root-finders based on full linear multistep methods (LMMs) use previous function values, derivatives and root estimates to iteratively find a root of a nonlinear function. As ODE solvers, full LMMs are typically not zero-stable. However, used as root-finders, the interpolation points are convergent so that such stability issues are circumvented. A general analysis is provided based on inverse polynomial interpolation, which is used to prove a fundamental barrier on the convergence rate of any LMM-based method. We show, using numerical examples, that full LMM-based methods perform excellently. Finally, we also provide a robust implementation based on Brent’s method that is guaranteed to converge.
MSC:
65H05 Numerical computation of solutions to single equations
65L06 Multistep, Runge-Kutta and extrapolation methods for ordinary differential equations
65L05 Numerical methods for initial value problems involving ordinary differential equations
Software:
BRENT
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Glassner, A. S., An introduction to ray tracing, (1991), Academic Press London
[2] Chaves, J., Introduction to non-imaging optics, (2008), CRC Press
[3] Butcher, J. C., The numerical analysis of ordinary differential equations, (1987), Wiley · Zbl 0616.65072
[4] Gautschi, W., Numerical analysis, (2012), Birkhäuser Boston
[5] Grau-Sánchez, M.; Noguera, M.; Díaz-Barrero, J. L., Adams-like techniques for zero-finder methods, Appl. Math. Comput., 211, 130-136, (2009) · Zbl 1162.65344
[6] Grau-Sánchez, M.; Díaz-Barrero, J. L., Zero-finder methods derived using Runge-Kutta techniques, Appl. Math. Comput., 217, 5366-5376, (2011) · Zbl 1229.65079
[7] Grau-Sánchez, M.; Gutiérrez, J. M., Zero-finder methods derived from obreshkov’s techniques, Appl. Math. Comput., 215, 8, 2992-3001, (2009) · Zbl 1187.65051
[8] Shengguo, L.; Xiangke, L.; Lizhi, C., A new fourth-order iterative method for finding multiple roots of nonlinear equations, Appl. Math. Comput., 215, 3, 1288-1292, (2009) · Zbl 1175.65054
[9] Soleymani, F.; Khattri, S.; Vanani, S. K., Two new classes of optimal jarratt-type fourth-order methods, Appl. Math. Lett., 25, 5, 847-853, (2012) · Zbl 1239.65030
[10] Behl, R.; Cordero, A.; Motsa, S. S.; Torregrosa, J. R., Construction of fourth-order optimal families of iterative methods and their dynamics, Appl. Math. Comput., 271, 89-101, (2015) · Zbl 1410.65146
[11] Kim, Y. I.; Behl, R.; Motsa, S. S., An optimal family of eighth-order iterative methods with an inverse interpolatory rational function error corrector for nonlinear equations, Math. Model. Anal., 22, 3, 321-336, (2017)
[12] Chun, C.; Neta, B., An analysis of a new family of eighth-order optimal methods, Appl. Math. Comput., 245, 86-107, (2014) · Zbl 1336.65081
[13] Lotfi, T.; Sharifi, S.; Salimi, M.; Siegmund, S., A new class of three-point methods with optimal convergence order eight and its dynamics, Numer. Algorithms, 68, 261-288, (2015) · Zbl 1309.65054
[14] Geum, Y. H.; Kim, Y. I., A family of optimal sixteenth-order multipoint methods with a linear fraction plus a trivariate polynomial as the fourth-step weighting function, Comput. Math. Appl., 61, 11, 3278-3287, (2011) · Zbl 1222.65046
[15] Brent, R. P., Algorithms for minimization without derivatives, (1973), Prentice-Hall · Zbl 0245.65032
[16] Adams, R. A., Calculus: A complete course, (2013), Pearson
[17] Hairer, E.; Wanner, G.; Nørsett, S. P., Solving ordinary differential equations I: nonstiff problems, (1987), Springer-Verlag · Zbl 0638.65058
[18] Quarteroni, A.; Sacco, R.; Saleri, F., Numerical mathematics, (2007), Springer · Zbl 0913.65002
[19] Donovan, G. C.; Miller, A. R.; Moreland, T. J., Pathological functions for newton’s method, Am. Math. Mon., 100, 1, 53-58, (1993) · Zbl 0828.65046
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.