Davidson K.R., Donsig A.P. Real Analysis with Real Applications

Подождите немного. Документ загружается.

11.1 Fixed Points and the Contraction Principle 343

This formula (I −A)

−1

∞

k=0

should be seen as parallel to the power series

identity

1 − x

∞

k=0

for |x| < 1.

The condition |x| < 1 guarantees that the series converges. The same role is played

for matrices by the contractive condition (11.1.11).

Exercises for Section 11.1

A. Let T x = 1.8(x − x

). Find the smallest real number R so that lim

n→∞

x| = +∞

for all |x| > R.

B. Show that T x = sin x is not a contraction on [−1, 1].

C. Give an example of a differentiable map T from R to R whose ﬁxed points are exactly

the set of integers. Find points where |T

(x)| > 1.

D. Explain why, in the previous example, points with |T

(x)| > 1 necessarily exist.

E. Suppose that S and T are contractions with Lipschitz constants s and t, respectively.

Prove that the composition ST is a contraction with Lipschitz constant st.

F. Consider a case of Example 11.1.11 for A =

.5 .4

0 .8

and b =

. Explicitly

compute the inﬁnite sum

∞

k=0

in order to solve for the ﬁxed point of T x = Ax + b.

G. Redo Example 11.1.11 using the 1-norm kxk

i=1

| on R

in place of kxk

∞

HINT: Show that T is a contraction if and only if max

1≤j≤n

i=1

| < 1.

H. Deﬁne T on C[−1, 1] by T f(x) = f (x) +

− f(x)

. Set f

= 0 and f

n+1

= Tf

for n ≥ 0. Prove that f

is a monotone increasing sequence of functions such that

0 ≤ x

− f

n+1

(x)

≤ (1 −

)(x

− f

(x)

Hence show that f

is a sequence of polynomials converging uniformly to |x|.

I. Deﬁne a map D on C[0, 1] as follows:

Df(x) =











f(3x) for 0 ≤ x ≤

(2 + f(1))(

− x) for

≤ x ≤

x −

for

≤ x ≤ 1.

(a) Sketch the graph of some function f and Df .

(b) Show that D is a contraction.

344 Discrete Dynamical Systems

J. Suppose that S and T are contractions on X with Lipschitz constant c < 1 and ﬁxed

points x

and x

respectively. Prove that kx

− x

k ≤ (1 − c)

−1

kS − T k

∞

, where

kS − T k

∞

= sup

x∈X

kSx − T xk.

HINT: Estimate kx

− x

k in terms of kx

− T x

K. Suppose that for 0 ≤ s ≤ 1, T

is a contraction of a complete normed space X

with Lipschitz constant c < 1. Moreover, assume that this is a continuous path of

contractions. That is, lim

s→s

−T

∞

= 0. Prove that the ﬁxed points x

of T

form

a continuous path.

HINT: Use the previous exercise.

11.2. Newton’s Method

Newton’s method is an iterative method for rapidly computing the zeros of dif-

ferentiable functions. The Contraction Principle gives a nice proof that this method

works.

Suppose we have a function f on R and a reasonable guess x

for the zero (or

root) of f. If f is differentiable at x

, then we can draw the tangent line at x

. It

seems plausible that if x

is close to the root of the function, the root of the tangent

line will be even closer. This uses one of the basic ideas of Differential Calculus:

The tangent line to f at x

is a good approximation to f near x

The equation of the tangent line is

y = f (x

) + f

)(x − x

To ﬁnd the root, we set y = 0 and solve for x, to obtain

x = x

−

f(x

)

Call this root x

. By repeating the same calculation for x

, we obtain a sequence

)

∞

n=1

, where

n+1

= x

−

f(x

)

for n ≥ 1.

Our hope is that the sequence converges to a point x

∗

satisfying f(x

∗

) = 0. See

Figure 11.4 for an example of (the ﬁrst few terms) of such a sequence.

To prove this, we reformulate the problem using ﬁxed points. Suppose f(x) is

twice differentiable and f(x

∗

) = 0 for some point x

∗

. Deﬁne a dynamical system

T by

T x = x −

f(x)

(x)

It is easy to see that if f(x

∗

) = 0, then T x

∗

= x

∗

and vice versa. So we are looking

for a ﬁxed point for the function T . Notice that for this deﬁnition to make sense,

we require f

(x) 6= 0 on our domain. This will show up in our hypotheses as the

condition f

∗

) 6= 0.

11.2 Newton’s Method 345

y = f(x)

FIGURE 11.4. Example of a function f and sequence (x

We compute the derivative

(x) = 1 −

(x)

− f(x)f

(x)

f(x)f

(x)

Notice that T

∗

) = 0. So x

∗

is an attractive ﬁxed point by Lemma 11.1.2. More-

over, the constant c used may be any small positive number. Indeed, the closer we

get to x

∗

, the smaller the value of c that may be used. This will be important in

obtaining very rapid convergence.

In addition to verifying that Newton’s method works, we can estimate how

quickly the error decreases. This kind of error analysis is fundamental to deciding

the effectiveness of an algorithm. It is considered minimally acceptable if the error

tends to zero geometrically in the sense that

n+1

− x

∗

| ≤ c|x

− x

∗

| for n ≥ N

for some constant c < 1. For if c

< .1, we obtain an additional digit of accuracy

every s iterations. Compare Example 11.1.8.

However, if great accuracy is desired, this is not all that fast. Some algorithms,

such as Newton’s method, converge quadratically, meaning that there is a constant

M so that

n+1

− x

∗

| ≤ M |x

− x

∗

for n ≥ N.

Once |x

− x

∗

| < .1/M, the number of digits of accuracy doubles every iteration.

Thus, once we get sufﬁciently close to the solution, the sequence approaches x

∗

very rapidly.

11.2.1. NEWTON’S METHOD.

Suppose that f is twice continuously differentiable, and there is a point x

∗

∈ R

such that f (x

∗

) = 0 and f

∗

) 6= 0. There is an r > 0 so that if x

belongs

to [x

∗

− r, x

∗

+ r], then the iterates x

n+1

= x

− f(x

)/f

) converge to x

∗

Moreover, there is a constant M such that

n+1

− x

∗

| < M |x

− x

∗

for n ≥ 1;

so the iterates converge quadratically.

346 Discrete Dynamical Systems

PROOF. Let T x = x − f(x)/f

(x). Then T x

∗

= x

∗

. As computed previously,

(x) =

f(x)f

(x)

In particular, T

∗

) = 0. Also, T

(x) is deﬁned for x near x

∗

since f

(x) 6= 0

for x near x

∗

. Choose r > 0 sufﬁciently small so that |T

(x)| ≤

on the interval

∗

−r, x

∗

+r]. By Lemma 11.1.2, for any x

in this range, the iterates x

n+1

= T x

converge to x

∗

, and

− x

∗

| ≤ 2

−n

− x

∗

| ≤ 2

1−n

− x

In particular, x

converge at least geometrically to the ﬁxed point, and each x

n+1

is closer to this point than x

Quadratic convergence is a consequence of using the Mean Value Theorem

in a more precise way. The estimate from Lemma 11.1.2 only used the fact that

(x)| ≤ c near the ﬁxed point x

∗

. We will exploit the fact that T

∗

) = 0. Here

are the details. Let

A = sup

|x−x

∗

|≤r

(x)| and B = inf

|x−x

∗

|≤r

(x)|,

and set M = A/B. By the Mean Value Theorem, there is a point a

between x

and x

∗

such that

f(x

) = f (x

) − f (x

∗

) = f

)(x

− x

∗

Solve for x

− x

∗

and substitute into the following:

n+1

− x

∗

= (x

− x

∗

) + (x

n+1

− x

)

f(x

)

−

f(x

)

f(x

)

) − f

)

− x

∗

)

) − f

)

Applying the Mean Value Theorem again, this time to f

, provides a point b

be-

tween x

and a

such that

) − f

)| = |f

)(x

− a

)| ≤ A|x

− x

∗

Combining this with |f

)| ≥ B and substituting again yields

n+1

− x

∗

| ≤

− x

∗

A|x

− x

∗

| = M |x

− x

∗

This establishes the quadratic convergence. ¥

11.2.2. EXAMPLE. COMPUTATION OF SQUARE ROOTS. A long time ago in

places far far away, everyone had to compute square roots by hand. Today, a few

people have to program calculators to compute them. Newton’s method is an ex-

cellent way for a person or a computer to ﬁnd square roots rapidly to high accuracy.

11.2 Newton’s Method 347

To illustrate the value of the method and of quadratic convergence, we’ll compute

a few square roots. Unlike a calculator, we also give an upper bound for the error

between our computed value and the true value.

Finding the square root of a > 0 means ﬁnding the positive root of the function

f(x) = x

− a. Applying Newton’s method, a simple computation gives

T x = x −

− a

x +

In fact, we will see that any initial positive choice of x

will converge to

√

a. Try

this on your calculator as a method of computing

√

2 or

√

71.

Suppose that you are asked to compute

√

149 to 20 digits of accuracy. Since

= 144 < 149 < 169 = 13

, let x

= 12 be our ﬁrst approximation. Clearly,

the error is at most .5. Moreover,

(x) =

1 −

149

This is evidently monotone. Thus on [12, 13], the derivative is bounded by

max

(12)|, |T

(13)|

= max

288

169

< .06.

Therefore, Newton’s method guarantees that the sequence

= 12, x

n+1

149

for n ≥ 0

converges quadratically to

√

149.

Let us compute the other constants involved. As f

(x) = 2x and f

(x) = 2,

we obtain

A = sup

12≤x≤13

(x)| = 2

B = inf

12≤x≤13

(x)| = 24

M =

< .084.

Again using the Mean Value Theorem, note that

|f(x

)| = |f (x

) − f (x

∗

)| = |f

(c)||x

− x

∗

| ≥ B|x

− x

∗

Thus

− x

∗

| < |f (x

)|/24 = 5/24 < .21.

From the error estimate for Newton’s method, we obtain

n+1

− x

∗

| ≤ .084|x

− x

∗

Starting with x

= 12, we have the following table of terms and bounds on the

error.

348 Discrete Dynamical Systems

n x

Bound on |x

− x

∗

0 12 .21

1 12.2083 3.704 × 10

−3

12.206555745165 1.153 × 10

−6

12.2065556157337036 3.572 ×10

−13

12.20655561573370295189 1.117 × 10

−26

12.20655561573370295189 1.048 × 10

−53

We already have 20 digits of accuracy at n = 4. In fact, to progress further,

we need to worry more about the round-off error of our calculations than with

Newton’s method.

Look at the global aspects of this example. It is easy to see from the graph that

f(x) = x

− 149 is concave, much like Figure 11.4. If x

lies in (0,

√

149), then

√

149. However, taking x

very small will result in a huge second term. After

that, it is also apparent from the graph that x

decreases monotonely and quickly to

√

149. Similarly, starting with x

< 0, the same procedure follows from reﬂection

of the whole picture in the y-axis—the sequence converges rapidly to −

√

149. The

point x

= 0 is a nonstarter because f

(0) = 0.

Exercises for Section 11.2

A. Show that f(x) = x

+ x + 1 has exactly one real root. Use Newton’s method to

approximate it to eight decimal places. Show your error estimates.

B. The equation sinx = x/2 has exactly one positive solution. Use Newton’s method to

approximate it to eight decimal places. Show your error estimates.

C. (a) Set up Newton’s method for computing cube roots.

(b) Show by hand that

√

2 − 1.25 < .01.

√

2 to eight decimal places.

D. Let f(x) = (

√

for x ∈ R. Sketch y = f(x) and y = x on the same graph. Given

∈ R, we deﬁne a sequence by x

n+1

= f(x

) for n ≥ 0.

(a) Find all ﬁxed points of f.

(b) Show that the sequence (x

)

∞

n=1

is monotone.

∗

= lim

n→∞

exists, prove that f(x

∗

) = x

∗

(d) For which x

∈ R does the sequence (x

) converge, and what is the limit?

E. Find the largest critical point of f(x) = x

sin(1/x) to four decimal places.

F. Find the minimum value of f(x) = (logx)

+ x on (0, ∞) to four decimal places.

G. Apply Newton’s method to ﬁnd the root of f(x) = (x − r)

1/3

. Start with any point

6= r, and compute |x

− r|. Explain what went wrong here.

11.3 Orbits of a Dynamical System 349

H. Modiﬁed Newton’s method. With the same setup as for Newton’s method, show that

the sequence x

n+1

= x

−

f(x

)

for n ≥ 0 converges to x

∗

I. (a) Let a > 0. Show that Newton’s formula for solving xa = 1 yields the iteration

n+1

= 2x

− ax

(b) Suppose that x

1 − ε

for some |ε| < 1. Derive the formula for x

n+1

= x

(3 − ax

− (ax

)

Explain why this is a superior algorithm.

J. Let h(x) = x

1/3

−x

(a) Set up Newton’s method for this function.

(b) If 0 < |x

| < 1/

√

6, then |x

n+1

| > 2|x

> 1/

√

6, then x

< x

n+1

< x

(d) Hence show that Newton’s method never works unless x

= 0. However, given

ε > 0, there will be an N so large that |x

n+1

− x

| < ε for n ≥ N.

(e) Sketch h and try to explain this nasty behaviour.

K. Three towns, Alphaville, Betatown, and Gammalot, are situated around the shore of a

circular lake of radius 1 km. The largest town Alphaville claims one half of the area of

the lake as its territory. The town mathematician is charged with computing the radius

r of a circle from the town hall (which is right on the shore) that will cut off half the

area of the lake. Compute r to seven decimal places.

HINTS: Let T denote the town hall, and O the centre of the lake. The circle of radius

r meets the shoreline at X and Y . The area enclosed is the union of two segments of

circles cut off by the chord XY . Express r and the area A as functions of the angle

θ = ∠OT X.

MORE HINTS: (1) Show that (i) 1 < r < 2; (ii) ∠T OX = π − 2θ; (iii) the area

of the segment of a circle of radius ρ cut off by a chord that subtends an angle α is

(α −sinα)/2. (2) Show that r = 2cos θ and A(θ) = 2π −4θ sin

θ −2sin(2θ). (3)

Solve A(θ) = π using Newton’s method. Show error estimates.

11.3. Orbits of a Dynamical System

There are several possibilities for the structure of the orbit of a point x

. Fixed

points, which we’ve discussed in detail, have the simplest possible orbits, namely

O(x

) = {x

}. Almost as good as ﬁxed points from the point of view of dynamics,

and certainly more common, are periodic points. We say that x

∗

is a periodicpoint

if there is a positive integer n such that T

∗

= x

∗

. The smallest positive n for

which this holds is called the period. Notice that x

∗

is a ﬁxed point of T

. We can

therefore call x

∗

an attractive periodic point or a repelling periodic point for T

if it is an attractive or repelling ﬁxed point of T

. Because T maps an open set

around x

∗

to an open set around T x

∗

, it is easy to check that points in the same

periodic orbit are either all attractive or all repelling.

Let us discuss the terminology of dynamical systems by examining a particular

map, namely the map T x = 1.8(x − x

) that we discussed in Section 11.1. Our

350 Discrete Dynamical Systems

example contains an orbit of period 2, namely {±

√

14/3}. Indeed, it is an easy

calculation to see that

T (

√

14/3) = −

√

14/3 and T (−

√

14/3) =

√

14/3.

See Figure 11.5. This is a repelling orbit since

)

(

√

14/3) = T

√

14/3)T

(

√

14/3)

= (1.8 − 5.4

)

= 547.56 > 1.

FIGURE 11.5. Graph of T x = 1.8(x−x

) showing period 2 orbit

and a nearby orbit.

A point x is called an eventually periodic point if T

x eventually belongs to

a period. Consider our example again. Notice that T (1) = 0. So T

(1) = 0 for all

n ≥ 1. The equation T x = 1 has a solution that is the root of the cubic

1 = 1.8x − 1.8x

This has a solution r since every real polynomial of odd degree has a root by Ex-

ercise 5.6.D and we may calculate r ≈ −1.20822631883. Then with x

= r, we

obtain x

= T x

= 1 and x

= T (1) = 0, and so x

= T

= 0 for all n ≥ 2.

Similarly, we have a sequence (r

) of points so that T

) = 0, such as r

= 0,

11.3 Orbits of a Dynamical System 351

= 1, r

≈ −1.20823, r

≈ 1.24128. Observe that r

is close to (−1)

n−1

√

14/3

for large n, in the sense that r

− (−1)

n−1

√

14/3 converges to zero.

Likewise there are points that are eventually mapped onto the two attractive

ﬁxed points ±

Figure 11.6, called a phase portrait, attempts to show graphically the be-

haviour of our mapping T . Rather than using a graph, it represents the space as

a line and the function as arrows taking a point x to T x. In particular, you should

observe that except for a sequence of points that eventually map to 0, every other

point in (−

√

14/3,

√

14/3) has an orbit that converges to one of the two attractive

ﬁxed points ±2/3. Notice that, except for the two arrows for the period 2 orbit,

arrows above the line show the ﬁrst few terms of the sequence (r

) mentioned

previously, while those below the line show the “nearby” orbit from Figure 11.5.

√

14/3−

√

14/3

2/3

−2/3

FIGURE 11.6. Phase portrait of T x = 1.8(x − x

)

Of course, this example does not exhaust the possibilities for the behaviour of

an orbit. It can happen that the orbit of a single point is dense in the whole space.

A point x is called a transitive point if O(x) = X. The following examples

are more complicated than our ﬁrst one and exhibit this new possibility as well as

having many periodic points.

11.3.1. EXAMPLE. Let the space be the unit circle T. We can describe a typical

point on the circle by the angle θ it makes to the positive real axis in radians. If

θ is changed to θ + 2nπ, the point determined remains the same. So this angle is

determined “up to a multiple of 2π.” We may add two angles, or multiply them

by an integer. The resulting point does not depend on how we initially measure

the angle. (Notice that when multiplying by a fraction such as

, the answer does

depend on which way the angle is represented. Half of 1 does not determine the

same point as half of 1 + 2π.) We call this arithmetic modulo 2π. We will write

θ ≡ ϕ (mod 2π)

to mean that θ−ϕ is an integer multiple of 2π, which is to say that θ and ϕ represent

the same point on the circle. In this way, we may think of the unit circle T as the

real line wrapping around the circle inﬁnitely often, meeting up at the same point

every 2π. This will be convenient for calculation.

352 Discrete Dynamical Systems

Consider the rotation map R

through an angle α given by

θ ≡ θ + α (mod 2π).

It is rather easy to analyze what happens here. The only way to obtain a periodic

point is to have

θ ≡ R

θ = θ + nα (mod 2π).

This requires nα to be an integer multiple of 2π. When this occurs and n is as

small as possible, it follows that every point in T has period n. Indeed, R

= id,

the identity map. This is the case for those α that are a rational multiple of 2π.

Equivalently, R

is periodic if and only if α/2π ∈ Q.

On the other hand, for all irrational values of α/2π, R

has no periodic points.

We will show that the orbit of every point is dense in the circle. Indeed, suppose

that ε > 0 and that θ and ϕ are two points on the circle. We wish to ﬁnd an integer

n so that |R

θ − ϕ| < ε.

To do this, we ﬁrst solve a simpler problem. We will ﬁnd a positive integer m

so that |R

0| < ε. This says that, while there are no periodic points, points do

come back very close to where they start every once in a while. Our method uses

the pigeonhole principle.

Pick an integer N so large that 2π < Nε. Divide the circle into N intervals

(k−1)2π

k2π

for 1 ≤ k ≤ N . Note that each interval has length

2π

< ε.

Now consider the N + 1 points

≡ R

0 = jα (mod 2π) : 0 ≤ j ≤ N}.

These N + 1 points are distributed in some way among the N intervals I

. As there

are more points than intervals, the pigeonhole principle merely asserts that some

interval contains at least two points. Let i < j be two integers in our set so that x

and x

both lie in some interval I

. These two points are therefore close to each

other. Precisely,

− x

| <

2π

< ε.

Now we use the fact that R

is isometric, meaning that

θ − R

ϕ| = |θ − ϕ|

for any two points θ, ϕ ∈ T. This just says that the map R

is a rigid rotation that

does not change the distance between points. Let m = j − i. Hence

0| = |x

j−i

− x

= |R

j−i

− R

| = |x

− x

| < ε.

It is also important that x

is not 0. This follows because α/2π is irrational.

So we observe that

0 ≡ kx

(mod 2π) for k ≥ 0

forms a sequence of points that move around the circle in steps smaller than ε. So

it is possible to choose k so that kx

is close to ϕ − θ, and thus

|ϕ − R

θ| = |(ϕ − θ) − R

0| = |(ϕ − θ) − kx

| < ε.

So every orbit is dense in the whole circle.