×

Newton’s method’s basins of attraction revisited. (English) Zbl 1175.65055

Summary: We revisit the chaotic number of iterations needed by Newton’s method to converge to a root. Here, we consider a simple modified Newton method depending on a parameter. It is demonstrated using polynomiography that even in the simple algorithm the presence and the position of the convergence regions, i.e. regions where the method converges nicely to a root, can be complicatedly a function of the parameter.

MSC:

65H05 Numerical computation of solutions to single equations
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Nordgaard, M. A., A Historical Survey of Algebraic Methods of Approximating the Roots of Numerical Higher Equations up to the Year 1819 (1922), Columbia University: Columbia University New York
[2] Cajori, F., Historical note on the Newton-Raphson method of approximation, Am. Math. Monthly, 18, 2, 19-33 (1911)
[3] Ypma, T. J., Historical development of the Newton-Raphson method, SIAM Rev., 37, 4, 531-551 (1995) · Zbl 0842.01005
[4] Schröder, E., Über unendlich viele Algorithmen zur Auflösung der Gleichungen, Math. Annal., 2, 317-365 (1870), English translation by G.W. Stewart, On infinitely many algorithms for solving equations, Technical Report TR-92-121, Department of Computer Science, University of Maryland, College Park, MD, USA, 1992
[5] Ortega, J. M.; Rheinboldt, W. C., Iterative Solution of Nonlinear Equations in Several Variables, Monograph Textbooks Comput. Sci. Appl. Math. (1970), Academic Press: Academic Press New York · Zbl 0241.65046
[6] Traub, J. F., Iterative Methods for the Solution of Equations (1982), Chelsea Publishing Company: Chelsea Publishing Company New York · Zbl 0472.65040
[7] Yamamoto, T., Historical developments in convergence analysis for Newton’s and Newton-like methods, J. Comput. Appl. Math., 124, 1-23 (2000) · Zbl 0965.65079
[8] Abbasbandy, S., Improving Newton-Raphson method for nonlinear equations by modified Adomian decomposition method, Appl. Math. Comput., 145, 887-893 (2003) · Zbl 1032.65048
[9] Adomian, G., Solving Frontier Problems of Physics: The Decomposition Method (1994), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht · Zbl 0802.65122
[10] He, J.-H., Comparison of homotopy perturbation method and homotopy analysis method, Appl. Math. Comput., 156, 527-539 (2004) · Zbl 1062.65074
[11] Liao, S.-J., Comparison between the homotopy analysis method and homotopy perturbation method, Appl. Math. Comput., 169, 1186-1194 (2005) · Zbl 1082.65534
[12] Wu, T.-M., A study of convergence on the Newton-homotopy continuation method, Appl. Math. Comput., 168, 1169-1174 (2005) · Zbl 1082.65535
[13] Petković, M. S.; Herceg, D., On rediscovered iteration methods for solving equations, J. Comput. Appl. Math., 107, 275-284 (1999) · Zbl 0940.65046
[14] Petković, L. D.; Petković, M. S., A note on some recent methods for solving nonlinear equations, Appl. Math. Comput., 185, 368-374 (2007) · Zbl 1121.65321
[15] P. Sebah, X. Gourdon, Newton’s method and high order iterations, Technical Report, 2001 (unpublished); Available at: <http://numbers.computation.free.fr/>; P. Sebah, X. Gourdon, Newton’s method and high order iterations, Technical Report, 2001 (unpublished); Available at: <http://numbers.computation.free.fr/>
[16] Pakdemirli, M.; Boyacı, H., Generation of root finding algorithms via perturbation theory and some formulas, Appl. Math. Comput., 184, 783-788 (2007) · Zbl 1115.65056
[17] Kellison, S. G., Fundamentals of Numerical Analysis (1975), R.D. Irwin, Inc.: R.D. Irwin, Inc. Homewood, Illinois
[18] Hubbard, J. H.; Schleicher, D.; Sutherland, S., How to find all roots of complex polynomials by Newton’s method, Invent. Math., 146, 1, 1-33 (2001) · Zbl 1048.37046
[19] Amat, S.; Busquier, S.; Plaza, S., Review of some iterative root-finding methods from a dynamical point of view, Sci. Ser. A: Math. Sci., 10, 3-35 (2004) · Zbl 1137.37316
[20] Varona, J. L., Graphic and numerical comparison between iterative methods, Math. Intell., 24, 1, 37-46 (2002) · Zbl 1003.65046
[21] Jacobsen, J.; Lewis, O.; Tennis, B., Approximations of continuous Newton’s method: an extension of Cayley’s problem, Electron. J. Diff. Equat., 15, 163-173 (2007) · Zbl 1118.65046
[22] Peitgen, H. O.; Richter, P. H., The Beauty of Fractals (1986), Springer-Verlag: Springer-Verlag New York · Zbl 0601.58003
[23] Szyszkowicz, M., Computer art from numerical methods, Comput. Graph. Forum, 10, 3, 255-259 (1991)
[24] Pickover, C. A., Overrelaxation and chaos, Phys. Lett. A, 130, 3, 125-128 (1988) · Zbl 0709.65039
[25] Pickover, C. A., Computers, Pattern, Chaos and Beauty (1990), St. Martin’s Press: St. Martin’s Press New York
[26] Ott, E., Basin of attraction, Scholarpedia, 1, 8, 1701 (2006)
[27] Reeves, R., A note on Halley’s method, Comput. Graph., 15, 1, 89-90 (1991)
[28] Reeves, R., Further insights into Halley’s method, Comput. Graph., 16, 235-236 (1992)
[29] Petković, M. S., Comments on the Basto-Semiao-Calheiros root finding method, Appl. Math. Comput., 184, 143-148 (2007) · Zbl 1115.65057
[30] Kalantari, B., Polynomiography and applications in art, education and science, Comput. Graph., 28, 417-430 (2004)
[31] Jin, Y.; Kalantari, B., On general convergence in extracting radicals via a fundamental family of iteration functions, J. Comput. Appl. Math., 206, 832-842 (2007) · Zbl 1118.65035
[32] B. Kalantari, On homogeneous linear recurrence relations and approximation of zeros of complex polynomials, in: M.B. Nathanson (Ed.), Unusual Applications of Number Theory, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 64, 2000, pp. 125-144.; B. Kalantari, On homogeneous linear recurrence relations and approximation of zeros of complex polynomials, in: M.B. Nathanson (Ed.), Unusual Applications of Number Theory, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 64, 2000, pp. 125-144. · Zbl 1083.12001
[33] Gerlach, J., Accelerated convergence in Newton’s method, SIAM Rev., 36, 272-276 (1994) · Zbl 0814.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. 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.