Some derivatives of Newton's method

Primus: Problems, Resources, and Issues in Mathematics Undergraduate Studies, Jun 2002 by Thoo, J B

ABSTRACT: Every first-year calculus student learns Newton's method as part of a repertoire of numerical root-finding methods. We present two other numerical root-finding methods that we derive using Newton's method: a simplified Newton's method, and Halley's method. These two methods are not new, yet they seldom find their way into a first calculus course even though they would not be out of place in such a course.

KEYWORDS: Newton's method, Halley's method, numerical root-- finding, dynamical systems, fixed point, orbit, iteration function.

1 INTRODUCTION

Every first-year calculus student learns Newton's method (N.M.) as part of a repertoire of numerical root-finding methods; see [12], for example. Of the variety of root-finding methods introduced, N.M. is a particularly important one for several reasons: it is a marvelous application of the differential calculus; it is widely applicable; it is relatively fast, being quadratically convergent,' while not being computationally too expensive. And it even leads to beautiful pictures that have found their way into art galleries, coffeetable books, and everyday homes [7].

We present two other numerical root-finding methods that we derive using N.M. (hence, the title, "Some derivatives of Newton's method"): a simplified Newton's method (S.N.M.), and Halley's method (H.M.). These two methods are not new, yet they seldom find their way into a first calculus course even though they would not be out of place in such a course. We hope that this note will encourage the classroom presentation of these other two methods.

This paper is organized as follows. In Section 2, we introduce the methods and give a geometrical interpretation for each method. In Section 3, we compare the methods by using each of them to approximate 2(square root). In Section 4, we take a dynamical systems approach to the methods, and use this point of view to make a second comparison of the methods, as well as to discuss briefly a couple of ways in which the methods may fail.

ACKNOWLEDGMENTS

We thank the editor and an anonymous referee for their suggestions on content and style, which greatly improved the manuscript.

1 This means that an answer that is correct to one decimal place at one step should be correct to two decimal places at the next step, four decimal places at the following step, and so on[6, p. 401.

2Yes, this is the Halley of "Halley's comet" fame. See [9] for some historical background.

3Numerical results are obtained using Maple V Release 4.

4Orbits are computed and plotted using Mary Ann Software PSMathGraphsII.

REFERENCES

1. Bateman, H. 1938. Halley's methods for solving equations. Amer. Math. Monthly. 45: 11-17.

2. Davies, M. and B. Dawson. 1975. On the global convergence of Halley's iteration formula. Numer. Math. 24: 133-135.

3. Devaney, Robert L. 1992. A First Course in Chaotic Dynamical Systerms: Theory and Experiment. Reading MA: Addison-Wesley.

4. Frame, J. S. 1944. A variation of Newton's method. Amer. Math. Monthly. 51: 36-38.

5. Garrett, Paul. "Pathological example for Newton's method (applet)", Web page http://www.math. li.umn. edu/-garrett/qy/BadNewton.html, email garrett(Omath. umn. edu.

6. Hosking, R. J., S. Joe, D. C. Joyce, and J. C. Turner. 1996. First Steps in Numerical Analysis. 2nd ed. London: Arnold.

7. H.-O. Peitgen and P. H. Richter. 1986. The Beauty of F-actals: Images of Complex Dynamical Systems. Berlin: Springer-Verlag.

8. Salehov, G. S. 1952. On the convergence of the process of tangent hyperbolas (Russian). Dokl. Akad. Nauk SSSR. 82: 525-528.

9. Scavo, T. R. and J. B. Thoo. 1995. On the geometry of Halley's method. Amer. Math. Monthly. 102(5): 417-426.

10. Stakgold, Ivar. 1979. Green's Functions and Boundary Value Problems, Wiley Interscience Ser. in Pure and Appl. Math. New York: John Wiley & Sons.

11. Traub, J. F. 1964. Iterative Methods for the Solution of Equations, Englewood Cliffs NJ: Prentice-Hall.

12. Varberg, Dale, Edwin J. Purcell, and Steven E. Rigdon. 2000. Calculus, 8th. ed. Upper Saddle River NJ: Prentice-Hall, 2000.

J. B. Thoo*

* Written while a visiting lecturer at the University of California, Davis CA 956168633 USA.

ADDRESS: Mathematics Department, Yuba College, 2088 N. Beale Road, Marysville CA 95901-7699 USA.

BIOGRAPHICAL SKETCH

John is the luckiest man in the world: he has a darling wife, two precocious children (both girls), a dream position at Yuba College (Marysville), andas if that wasn't enough-is enjoying a sabbatical year visiting UC Davis. John likes to remind his students (and two children) that, "Practice makes perfect, but if you practice wrong, you'll be perfectly wrong." He did his post-high school, post-USMC education at Cabrillo College, Cal Berkeley, and UC Davis.