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

Susanto, H.; Karjanto, N.

Appl. Math. Comput. 215, No. 3, 1084-1090 (2009).

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

Keywords:

Newton-Raphson methods; iteration methods; numerical examples; chaotic number of iterations

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 New York
[2]	Cajori, F., Historical note on the newton – raphson method of approximation, Am. math. monthly, 18, 2, 19-33, (1911) · JFM 42.0126.06
[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 New York · Zbl 0241.65046
[6]	Traub, J.F., Iterative methods for the solution of equations, (1982), 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 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/>.
[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. 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 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 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. · Zbl 1083.12001
[33]	Gerlach, J., Accelerated convergence in newton’s method, SIAM rev., 36, 272-276, (1994) · Zbl 0814.65046