|P (xn’1 ’Sn’1 P (xn’1 ))| ¤ |P (xn’1 )’P (xn’1 )Sn’1 P (xn’1 )|+K|xn ’xn’1 |2 .

Substituting this inequality into (1.19), we get

|xn+1 ’ xn | ¤ K|P (xn’1 ) ’ P (xn’1 )Sn’1 P (xn’1 )| + K 2 |xn ’ xn’1 |2 . (1.20)

Now since Sn’1 = P (xn’1 )’1 the ¬rst term on the right vanishes and we get

n

|xn+1 ’ xn | ¤ K 2 |xn ’ xn’1 |2 ¤ K 2 e’2c„ .

So in order to pass from n to n + 1 in (1.16) we must have

n n+1

K 2 e’2c„ ¤ e’c„

or

K 2 ¤ ec(2’„ )„ . (1.21)

Since „ < 2 we can arrange for this last inequality to hold if we choose c

su¬ciently large. To get started, we must verify (1.16) for n = 1 This says

S0 P (0) ¤ e’c„

or

e’c„

|P (0)| ¤ . (1.22)

K

So we have proved:

Theorem 1.2.1 Suppose that (1.13) holds and we have chosen K and c so that

(1.17) and (1.21) hold. Then if P (0) satis¬es (1.22) the Newton iteration scheme

converges exponentially in the sense that (1.16) holds.

If we choose „ = 3 as in the proposition, let c be given by K 2 = e3c/4 so

2

that (1.21) just holds. This is our choice in the proposition. The inequality

K ≥ 23/4 implies that e3c/4 ≥ 43/4 or

ec ≥ 4.

This implies that

1

e’c/2 ¤

2

so (1.17) holds. Then

e’c„ = e’3c/2 = K ’4

13

1.2. NEWTON™S METHOD

so (1.22) becomes |P (0)| ¤ K ’5 completing the proof of the proposition.

We have put in all the gory details, but it is worth reviewing the guts of

the argument, and seeing how things di¬er from the special case of ¬nding the

square root. Our algorithm is

xn+1 = xn ’ Sn [P (xn )] (1.23)

where Sn is chosen as (1.18). Taylor™s formula gave (1.20) and with the choice

(1.18) we get

|xn+1 ’ xn | ¤ K 2 |xn ’ xn’1 |2 . (1.24)

In contrast to (1.4) we do not know that K ¤ 1 so, once we get going, we can™t

quite conclude that the error vanishes as

n

r„

with „ = 2. But we can arrange that we eventually have such exponential

convergence with any „ < 2.

1.2.5 Basins of attraction.

The more decisive di¬erence has to do with the “basins of attraction” of the

solutions. For the square root, starting with any positive number ends us up

1

with the positive square root. This was the e¬ect of the en+1 < 2 en argument

which eventually gets us to the region where the exponential convergence takes

over. Every negative number leads us to the negative square root. So the “basin

of attraction” of the positive square root is the entire positive half axis, and the

“basin of attraction” of the negative square root is the entire negative half axis.

The only “bad” point belonging to no basin of attraction is the point 0.

Even for cubic polynomials the global behavior of Newton™s method is ex-

traordinarily complicated. For example, consider the polynomial

P (x) = x3 ’ x,

with roots at 0 and ±1. We have

x3 ’ x 2x3

P (x)

x’ =x’ 2 =2

3x ’ 1 3x ’ 1

P (x)

so Newton™s method in this case says to set

2x3

n

xn+1 = . (1.25)

2 ’1

3xn

There are obvious “bad” points where we can™t get started, due to the vanishing

of the denominator, P (x). These are the points x = ± 1/3. These two points

are the analogues of the point 0 in the square root algorithm.

We know from the general theory, that any point su¬ciently close to 1 will

converge to 1 under Newton™s method and similarly for the other two roots, 0

and -1.

14 CHAPTER 1. ITERATIONS AND FIXED POINTS

If x > 1, then

2x3 > 3x2 ’ 1

since both sides agree at x = 1 and the left side is increasing faster, as its

derivative is 6x2 while the derivative of the right hand side is only 6x. This

implies that if we start to the right of x = 1 we will stay to the right. The same

argument shows that

2x3 < 3x3 ’ x

for x > 1. This is the same as

2x3

< x,

3x2 ’ 1

which implies that if we start with x0 > 1 we have x0 > x1 > x2 > · · · and

eventually we will reach the region where the exponential convergence takes

over. So every point to the right of x = 1 is in the basin of attraction of the

root x = 1. By symmetry, every point to the left of x = ’1 will converge to ’1.

But let us examine what happens in the interval ’1 < x0 < 1. For example,

1

suppose we start with x0 = ’ 2 . Then one application of Newton™s method

gives

’.25

x1 = = 1.

3 — .25 ’ 1

In other words, one application of Newton™s method lands us on the root x = 1,

right on the nose. Notice that although ’.5 is halfway between the roots ’1

and 0, we land on the farther root x = 1. In fact, by continuity, if we start with

x0 close to ’.5, then x1 must be close to 1. So all points, x0 , su¬ciently close

to ’.5 will have x1 in the region where exponential convergence to x = 1 takes

over. In other words, the basin of attraction of x = 1 will include points to the

immediate left of ’.5, even though ’1 is the closest root.

Suppose we have a point x which satis¬es

2x3

= ’x.

3x2 ’ 1

So one application of Newton™s method lands us at ’x, and a second lands us

back at x. The above equation is the same as

0 = 5x3 ’ x = x(5x2 ’ 1)

which has roots, x = 0, ± 1/5. So the points ± 1/5 form a cycle of order two:

Newton™s method cycles between these two points and hence does not converge

to any root.

In fact, in the interval (’1, 1) there are in¬nitely many points that don™t

converge to any root. We will return to a description of this complicated type

of phenomenon later. If we apply Newton™s method to cubic or higher degree

polynomials and to complex numbers instead of real numbers, the results are

even more spectacular. This phenomenon was ¬rst discovered by Cayley, and

was published in an article which appeared in the second issue of the American

Journal of Mathematics in 1879. This paper of Cayley™s was the starting point

for many future investigations.