DOC

# When calculating results of an iterated function, g, several

By Frederick Harrison,2014-11-26 12:50
7 views 0
When calculating results of an iterated function, g, several

Basins of Roots and Periodicity in

Newton’s Method for Cubic

Polynomials

Amy M. Smith

Senior Honors Thesis

May 11, 2000

Department of Mathematics

Davidson College

1

Acknowledgments

I would like to thank my advisors Dr. Tim Flaherty at Carnegie Mellon University, who created the project, and Dr. Richard Neidinger at Davidson College, who helped me to continue my study of Newton’s method. I would also like to thank Kari Whitcomb at Valparaiso University and Zalenda Cyrille at Carnegie Mellon University with whom I worked on the project during the summer of 1999.

2

Introduction

Newton’s method is generally introduced in Calculus I courses as a useful tool for finding the roots of functions when analytical methods fail. This method works well because, if the initial guess is close enough to the actual root, iterations will converge quickly to the root. The student is usually warned against picking a point where the derivative is zero because the function used in Newton’s method is undefined at that point.

Polynomials used for Calculus I problems don’t tend to have any further complications, but polynomials with interesting behavior do exist.

If we expand our study of the dynamics of Newton’s method to the complex plane, we find lots of interesting properties. Fractals, chaos, attracting periodic cycles, Mandelbrot sets, and other phenomena are present, depending on what type of functions we study. We will focus on cubic polynomials with real coefficients for the actual analysis in Sections III and IV, but we begin with some background on the properties we will use for analytic functions in Section I and rational functions in Section II.

I. Iteration and Newton’s method

A sequence of points can be created by functional iteration which, given a

, is defined by the successive evaluation of the function g: C ? C and an initial value p0

results of the function starting with the initial value. The sequence obtained is of the form {p, p=g(p),…,p=g(p),…}. It is possible for the sequence to yield a periodic n-cycle 010ii-1

(n)(n)where g(p) = p for some p ? C, where g denotes the nth iteration of g. One special

case of this is a fixed point, which occurs when n = 1. A periodic point p can be classified

(n)depending on the value of = (g)’(p).

3

Definition: ([Cr], p. 203)

(n)(p) = p is The periodic point p where g

superattracting if = 0,

attracting if || < 1,

neutral if || = 1,

repelling if || > 1. ;

nn()Since (g)'(p)g'(p)?ii1

by the chain rule, each point in the periodic cycle will have the same . Thus, the cycle

can be described with the above terminology.

If a point p is attracting or superattracting, then there is a collection of points such

that functional iteration of g with any of these points as the initial value will converge to p.

Definition:

The basin of attraction for a fixed point p is

(n) A(p) = {z?C : g(z) ? p as n ? ?}.

The basin of attraction for a periodic cycle P = {p, p,…, p} of length n is 12n

(in) A(P) = {z?C : g(z) ? p for some k?{1, 2,…, n} as i ? ?}. ; k

We would like to be assured that attracting periodic and fixed points, based on the

definition using , actually have basins of attraction.

Theorem 1:

Suppose p is an attracting or superattracting periodic point for an iterative function,

g. Then there exists a neighborhood U of p such that U ? A(p).

Proof:

4

Suppose a fixed point, p, is attracting or superattracting, so that || < 1 (recall =

(n)(p).) g’(p)). (If p is a periodic point, a similar argument could be applied to g

We can expand g about p using a Taylor approximation.

gp''()2gzgpgpzp()()'()()！？？？？？()...zp

2!

For values of z ? C near p

gzgpgpzp()()'()()?？？

gzgpgpzpzp()()'()()？?？！？

This shows that g(z) and g(p) = p are approximately closer together than z and p

since || < 1, so the iteration would eventually converge to p. However, we would

like this to be more rigorous.

Let ? R such that || < < 1.

lim((g)z(g))p/(z)p'g()p1Now z?p

By the definition of the derivative, such that |z-p| < implies

(g(z)g(p))/(zp)

Let p ? C such that | p-p| < , i.e. p ? U(p) (the neighborhood of points within a iii

distance of from p) and recall p = g(p) . i+1i

g(p()gp())/(pp)?ppgp()gp()ppThen iii1ii

Since < 1, p ? U(p) and the same argument holds. i+1

Now let p ? U(p). Then, 0

|p-p| < |p-p| = |g(p)-p| i+1ii-1

5

2|p-p| < i-1

3 < |p-p| i-2

i+1 < |p-p|. 0

Since < 1, this value approaches zero as i goes to infinity, so p ? A(p). 0

Therefore, U(p) ? A(p).

Now we would like to understand the difference between attracting and

superattracting. Suppose a fixed point p is superattracting so = 0. Again, we can use

Taylor’s approximation to expand g about p.

gp''()2gzgpgpzp()()'()()！？？？？？()...zp

2!

For values of z ? C near p

2g(z)?g(p)0g''(p)(zp)/2!

22g(z)g(p)?g''(p)/2!(zp)Mzp

where M = |g’’(p)/2!|.

Suppose p ? C and |p-p| < 1/M, and p = g(p) for i = 0,1,2,… then 00i+1i

2 |p-p| = |g(p)-g(p)| ? M|p-p| < 1/M. 100

Now

2|p-p| ? (1/M)(M|p-p|) i+1i

4 ? (1/M)(M|p-p|) i-1

(i+1) ? (1/M)(M|p-p|)^2 < 1/M. 0

6

This is converging to zero, but faster than in the attracting case. Unfortunately,

the above heuristic argument is more difficult to prove. If we were working in R, then we

2 for some x could have used Taylor’s Theorem to get |g(z)-g(p)| = |g’’(x)/2!||z-p|

between z and p. However, the simplest case of Taylor’s Theorem, the Mean Value Theorem, is not valid for complex valued functions ([Co], p. 305). A more rigorous argument can be found in Proposition 8 in ([K], p.64).

We can classify the two types of convergence without relying on the value of .

Definition:

A sequence [p] converges linearly to a point p if there exists an M < 1 such that, n

for all i = 0, 1, 2,…, |p-p| < M |p-p|. ; i+1i

Definition:

A sequence [p] converges quadratically to a point p if there exists an M ? R such n

2that, for all i = 0, 1, 2,…, |p-p| < M |p-p|. ; i+1i

Again, quadratic convergence is faster than linear convergence, which explains the

term “superattracting.”

Newton’s method is an iterative function with quadratic convergence that is used

to find roots of an analytic function f. Definition:

For an analytic function f: C ? C and some z ? C, Newton’s method is the

functional iteration of

~N(z)zf(z)/f(z)f

(The subscript will be omitted when it is clear from context.) ;

7

Theorem 2:

. If p is a simple root of f, then p is a superattracting fixed point of Nf

Proof:

Suppose that p is a simple root of f so that f(p) = 0 and f’(p) 0.

f(p)N(p)pp0pff'(p) 2[f'(p)]f(p)f''(p)N'(p)11100f2[f'(p)]

So p is a superattracting fixed point for N. f

This is the property that makes Newton’s method work so well. Once you get inside a certain neighborhood of the root of f, the iterations of N will converge quickly to f

the root. When we study the basins of attraction for Newton’s method, we find some quite interesting behavior.

II. Rational functions and Julia sets

The study of Newton’s method, and all rational functions, is interesting because the attracting basins are not the only sets of points present in the plane. Theorem:

For any attracting fixed point p of a continuous function g, the basin, A(p) is open. Proof:

From Theorem 1 we know that there is a neighborhood U of p such that U ? A(p).

-1-Since U is a neighborhood, it is open. Since g is continuous, g(U) is open and g

(n)(U) is open for all n = 1,2,…. Then

?()n;gU()1n

8

is open. Suppose we have a point u in this union. Then iterating g with u as the

initial point will eventually yield a point in U, and thus will converge to p.

Therefore, ?()n;gUAp()()?1n

Now suppose we have a point a in A(p). Then there exists an n ? {1, 2,…} such

(n)that g(a) ? U. Then ?()n;agU?()1n

Therefore, ?()n;gUAp()()?1n

Therefore, the union and the basin are equal, so A(p) is open.

Then, the complement of A(p) must be closed.

There are points in the complex plane that are not members of basins of attraction for attracting fixed points of a rational function R. Based on algebra, there are solutions

(n)to R(p) = p, yielding periodic points. These points can not be in the fixed point basins, because that would imply that they converge to the fixed point, contradicting the periodicity. It is difficult to find these periodic points because they usually are repelling, so that || > 1. The closure of these repelling periodic points forms the complement of the attracting basins.

Definition: ([K], p.64)

The Julia set J for the rational function R: C ? C is the closure of the repelling R

periodic points.

(The subscript will be omitted when it is clear from context.) ;

Theorem 3: ([PS], p. 208)

9

,z,…,z, For a rational function R, that has attracting periodic points, z12k

J = )A(z), i = 1,2,…,k. Ri

This tells us that, if we are on the boundary of one basin of attraction, then we must be on the boundary of all basins of attraction. We can bring much of what we have discussed so far together by looking at Figure 1. (See Appendix for programs used to create figures.)

Figure 1

q(z) = (z-i)(z+i)(z-1.7320508)

This is the dynamic plane of a polynomial p with roots at i, -i, and 1.7320508 (approximately ?3) in the complex plane. Each pixel is used as an initial value for iterating N. Once iteration yields a value within the white circle around a root, the initial value p

pixel is colored according to that root. Green represents A(i), red represents A(-i), and blue represents A(1.7320508). We can see that the boundary of each basin touches each of the other basins. The boundary is also where we find the Julia set, which has even more interesting behavior.

10

Report this document

For any questions or suggestions please email
cust-service@docsford.com