NEWTON’S METHOD AND FRACTALS - Whitman College

1 NEWTON S METHOD AND FRACTALSAARON this paper Newton s METHOD is derived, the general speed ofconvergence of the METHOD is shown to be quadratic, the basins of attractionof Newton s METHOD are described, and finally the METHOD is generalized tothe complex the equationf(x) = 0 Given a functionf, finding the solutions of the equationf(x) = 0 is one of theoldest mathematical problems. General methods to find the roots off(x) = 0 whenf(x) is a polynomial of degree one or two have been known since 2000 [3]. Forexample, to solve for the roots of a quadratic functionax2+bx+c= 0 we mayutilize the quadratic formula:x= b b2 to solve polynomials of degree three and four were discovered in the16th century by the mathematicians dal Ferro, Tartaglia, Cardano, and Ferrai [3].

2 Finally, in 1826 it was discovered from work done by Abel, that there is no generalmethod to solve polynomials of degree five or greater [3].Since it is not possible to solve all equations of the formf(x) = 0 exactly, anefficient METHOD of approximating solutions is useful. The algorithm discussed inthis paper was discovered by Sir Issac Newton, who formulated the result in improved by Joseph Raphson in 1690, the algorithm is presently known asthe Newton-Raphson METHOD , or more commonly Newton s METHOD [3].Newton s METHOD involves choosing an initial guessx0, and then, through aniterative process, finding a sequence of numbersx0,x1,x2,x3, 1that convergeto a solution.

3 Some functions may have several roots. Later we see that the rootwhich Newton s METHOD converges to depends on the initial guessx0. The behaviorof Newton s METHOD , or the pattern of which initial guesses lead to which zeros,can be interesting even for polynomials. When generalized to the complex plane,Newton s METHOD leads to beautiful this paper, we derive Newton s METHOD , analyze the METHOD s speed of conver-gence, and explore the basins of attraction2. Finally, we extend Newton s methodto the complex plane, and through the aid of computer programming view thecomplex basins of attraction for several BURTONF igure geometry of Newton s Newton s methodAs stated in Section 1, Newton s METHOD involves choosing an initial approxi-mationx0, and then, through an iterative process, finding a sequence of numbersx0,x1,x2,x3, that converges to a solution.

4 Recall our goal is to approximatethe root of a functionf(x), thus once we chose ourx0we hope to find a pointx1(related tox0in some way) that is a better approximation for the root of the func-tionf(x). Given a single pointx0there are many ways in which we could proceedto find the pointx1. In this paper we will use the tangent line atx0. The tangentline provides the best linear approximation to the functionf(x) at the pointx0,thus we are implicitly assuming that the tangent line will intersect the x-axis nearthe desired root. This assumption seems to be valid based on Figure 1. In Section2 we will discuss how this assumption breaks down under certain , supposef(x) is a differentiable function on an interval [a,b] for which wewish to approximate the root.

5 We begin by making a guess or estimate of theroot s location, that is specifying an initial point (x0,0). To determine our nextestimate (x1,0), we draw the tangent line through (x0,f(x0)). The point at whichthe tangent line intersects thexaxis is (x1,0). Using our initial guessx0, the valueof the functionf(x0) and the slope of the tangent linef (x0) we can then find theequation of the tangent line at (x0,f(x0)) using the point-slope formula:y f(x0) =f (x0)(x x0).To solve for thexintercept we sety= 0 and rearrange terms to get f(x0) =f (x0)(x x0)1 Often called the orbit defined in Section 6, a Basin of Attraction is the set of points which converge to aparticular S METHOD AND FRACTALS3x x0= f(x0)f (x0)and finallyx=x0 f(x0)f (x0).

6 Thexintercept is our new guess, or estimate,x1. Thus we have,x1=x0 f(x0)f (x0).To findx2, we begin the whole process over again. However, this time we beginwith the point (x1,0) and solve for the point (x2,0). Repeating this algorithmgenerates a sequence ofxvaluesx0,x1,x2, by the rulexn+1=xn f(xn)f (xn), f (xn)6= 0we define as the Newton iteration functionN(x). Formally, given a differentiablefunctionf, the Newton function forfis:(1)N(x) =x f(x)f (x).Thenx1=N(x0)x2=N(x1) =N(N(x0)) =N2(x0)and, in general,xn=Nn(x0),where the Newton s METHOD failsOne natural question that arises is whether Newton s METHOD will always con-verge to a guess is a critical point off(x).

7 Recall from equation (1) that thedefinition of the Newton iteration function isN(x) =x f(x)f (x).From this definition we see thatN(x) will not exist iff (x) = 0. If we chose aninitial point wheref (x) = 0, then Newton s METHOD will fail to converge to a iff (xn) = 0 for some iterationxn, then Newton s METHOD will also fail toconverge to a root. The former case is illustrated forf(x) =x3+ 1 in Figure 2. Ifwe happen to choose our initial guess asx= 0, Newton s METHOD fails to convergesince the tangent line atx= 0 never intersects root to way in which Newton s METHOD will fail to convergeto the root of a function is if there is no root.

8 Consider the graph off(x) =x2+ 1in Figure 3. The functionf(x) =x2+ 1 never crosses thexaxis, and thus there isno possible solution. If we choose an initial guess, it can be proved that Newton smethod will chaotically move around BURTONF igure (x) =x3+ 1. The initial guess coincides with a critical third way in which Newton s METHOD will fail to convergeis if the initial guess or an iteration coincides with a cycle. For example, considerf(x) =x3 2x+ 2 and the initial guess ofx0= 1 as shown in Figure 4. Withx0= 1 we see thatx1=N(x0) = 1 13 2(1) + 23(1)2 2= 1 1 = 0,and thenx2=N(x1) = 0 03 2(0) + 23(0)2 2= 0 ( 1) = example is of a cycle with period two, but cycles of other orders may exist the problems just described can be avoided by choosing our initial pointwisely and by looking at the derivatives of the function to be approximated.

9 Usuallyit is helpful to graph the functionf(x) if possible before using Newton s further details, refer to Devaney Chapter example Devaney Chapter for an in depth explanation of S METHOD AND FRACTALS5 Figure (x) =x2+ 1. Nonexistent (x) =x3 2x+ 2. A cycle of period natural extension of Section 3 is the question of convergence. When exactlycan we be sure Newton s METHOD will converge to a root? First a few backgrounddefinitions and a rootrof the equationf(x) = 0hasmultiplicitykiff(r) = 0,f (r) = 0, ,f[k 1](r) = 0butf[k](r)6= 0. Heref[k](r)is thekthderivative example, 0 is a root of multiplicity 2 forf(x) =x2+x3and of multiplicity1 forf(x) =x+ pointx0is afixed pointof a functionf(x)if and only iff(x0) =x0.

10 Moreover, the pointx0is called anattracting fixed pointif|f (x0)|< our purposes it suffices for the reader to note that if a root is an attractingfixed point of the functionN(x), then Newton s METHOD will converge to that more information about fixed and attracting fixed points refer Appendix a root of multiplicitykfor a functionf(x), thenf(x)may bewritten in the formf(x) = (x r)kG(x),whereG(r)6= the Taylor expansion of a functionf(x) centered about the (x) =f(r) +f (r)(x r) +f (r)2!(x r)2+f (r)3!(x r)3+ Now suppose that the rootrhas a multiplicityk. From the definition of multiplicitywe have,f(x) = 0 + 0(x r) +02!(x r)2+ +f{k}(r)k!