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

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

11.1 Fixed Points and the Contraction Principle 333

∗

so that for every point x in (a, b) except for x

∗

itself, the orbit O(x) always

leaves the interval U.

Notice that for an attractive ﬁxed point x

∗

, the interval U around x

∗

may be

quite small. Also, for a repelling ﬁxed point x

∗

, the orbit O(x) may return to the

interval U after it leaves. However, it must then leave the interval again eventually.

We shall see that if T is differentiable, the difference between attractive and

repelling ﬁxed points comes down to the size of the derivative at x

∗

. A ﬁxed point

∗

is attracting if |T

∗

)| < 1 and repelling if |T

∗

)| > 1. The case |T

∗

)| = 1

is ambiguous and might be one, the other, or neither.

In our example,

(x) = 1.8 −5.4x

So T

(0) = 1.8 > 1. The tangent line at the origin is L(x) = 1.8x. Since the

tangent line is a good approximation to T near x = 0, it follows that T roughly

multiplies x by the factor 1.8 when x is small. So repeated application of this to

a very small nonzero number will eventually move the point far from 0. We will

make this precise in Lemma 11.1.2 by using the Mean Value Theorem to show that

0 is a repelling point in the interval (−

On the other hand, at x = ±

, T

(x) = −.6. This has absolute value less than

1. So near x =

, the function is approximated by the tangent line

L(x) =

− .6(x −

This decreases the distance to

by approximately a factor of .6 each iteration. That

is,

n+1

x −

≈ .6(T

x −

So T

x converges to

. Again, we will obtaina precise inequality in Lemma 11.1.2.

So the points ±

are attractive ﬁxed points.

Consider the graph of the function given in Figure 11.2. Fixed points corre-

spond to the intersection of the graph of T with the line y = x. Starting with

any point x

, mark the point (x

, x

) on the diagonal. A vertical line from this

point meets the graph of T at (x

, T x

) = (x

, x

). Then a horizontal line from

here meets the diagonal at (x

, x

). Repeated application yields a graphical pic-

ture of the dynamics. Note that starting near a ﬁxed point, the slope of the graph

determines whether the points approach or move away from the ﬁxed point.

In our example, another typical behaviour is exhibited by all |x| sufﬁciently

large. For the sake of simplicity, consider |x| > 2. Then

|T x| = 1.8(x

− 1)|x| ≥ 5.4|x|.

It is clear then that lim

n→∞

x| = +∞. So all of these orbits go off to inﬁnity.

Usually we will try to restrict our domain to a bounded region that is mapped back

into itself by the transformation T .

We now connect our classiﬁcation of ﬁxed points with derivatives. Say that

T is a C

dynamical system on X ⊂ R if the function T is C

, that is, has a

continuous derivative.

334 Discrete Dynamical Systems

y = x

FIGURE 11.2. Fixed points for Tx = 1.8(x − x

11.1.2. LEMMA. Suppose that T is a C

dynamical system with a ﬁxed point

∗

. If |T

∗

)| < c < 1, then x

∗

is an attractive ﬁxed point. Moreover, there is an

interval U = (x

∗

− r, x

∗

+ r) about x

∗

so that for every x

∈ U, the sequence

= T

satisﬁes

− x

∗

| ≤ c

− x

∗

| ≤

1 − c

− x

If |T

∗

)| > 1, then x

∗

is an repelling ﬁxed point.

PROOF. Suppose that |T

∗

)| < c < 1, and let ε = c − |T

∗

)| > 0. By the

continuity of T

, there is an r > 0 so that

(x) − T

∗

)| < ε for all x

∗

− r < x < x

∗

+ r.

Hence for x in the interval U = (x

∗

− r, x

∗

+ r),

(x)| ≤ |T

∗

)| + |T

(x) − T

∗

)| < (c − ε) + ε = c.

Let x

be an arbitrary point in U , and consider the sequence x

= T

Applying the Mean Value Theorem to the points x

and x

∗

, there is a point z

between them so that

T x

− T x

∗

− x

∗

= T

(z).

Rewriting this using T x

= x

n+1

and T x

∗

= x

∗

, we obtain

n+1

− x

∗

| = |T

(z)||x

− x

∗

Provided that x

belongs to the interval U , we obtain that

n+1

− x

∗

| < c|x

− x

∗

In particular, x

n+1

is closer to x

∗

than x

is; and therefore x

n+1

also belongs to U.

By induction, we obtain (verify this!) that

− x

∗

| < c

− x

∗

| for all n ≥ 1.

Hence lim

n→∞

−x

∗

| = 0 by the Squeeze Theorem. That is, lim

n→∞

= x

∗

. So x

∗

is an attractive ﬁxed point.

11.1 Fixed Points and the Contraction Principle 335

y = x

∗

, x

)

, x

)

, x

)

, x

)

, y

)

, y

)

, y

)

, y

)

y = x

∗

, x

)

, x

)

, x

)

, x

)

, y

)

, y

)

, y

)

, y

)

y = x

∗

, x

)

, x

)

, x

)

y = x

∗

, x

)

, x

)

, x

)

FIGURE 11.3. Iteration of a function g.

Similarly, suppose that |T

∗

)| > c > 1, and let ε = |T

∗

)|−c > 0. By the

continuity of T

, there is an r > 0 so that

(x) − T

∗

)| < ε for all x

∗

− r < x < x

∗

+ r.

Hence for x in the interval U = (x

∗

− r, x

∗

+ r),

(x)| ≥ |T

∗

)| − |T

(x) − T

∗

)| > (c + ε) − ε = c.

The Mean Value Theorem argument works the same way as long as x

belongs

to the interval U. However, in this case, repeated iteration eventually moves x

outside of U, at which point we have almost no information about the dynamics of

T . So as long as x

is in U, we obtain a point z between x

and x

∗

so that

n+1

− x

∗

| = |T

(z)||x

− x

∗

| > c|x

− x

∗

This can be repeated as long as x

remains inside U to obtain

− x

∗

| > c

− x

∗

As this distance to x

∗

is tending to +∞, repeated iteration eventually will move

n+1

outside of U. Therefore, x

∗

is a repelling ﬁxed point. ¥

336 Discrete Dynamical Systems

Notice that in this proof, we only used differentiability in order to apply the

Mean Value Theorem and obtain a distance estimate. The following deﬁnition de-

scribes this distance estimate directly, and so allows us to abstract the arguments of

the previous proof to other settings, where differentiability may not hold. However,

we demand that these estimates hold on the whole domain. While this may seem

to be excessively strong, remember that we may be able to restrict our attention to

a smaller domain in which these conditions apply. For example, in our previous

proof, the interval U would be a suitable domain.

11.1.3. DEFINITION. Let X be a subset of a normed vector space (V, k ·k). A

map T : X → X is called a contraction on X if there is a positive constant c < 1

so that

kT x − T yk ≤ ckx − yk for all x, y ∈ X.

That is, T is Lipschitz with constant c < 1.

11.1.4. EXAMPLE. Let us look more closely at the map T x = 1.8(x − x

)

introduced in the ﬁrst section. The ﬁxed points are −

, 0, and

Now |T

(

)| = | − .6| < 1, so this is an attracting ﬁxed point. We will show

that T is a contraction on the interval [.5, .7]. In this interval, T has a single critical

point at 1/

√

3, a local maximum, and

T (.5) = .675, T (1/

√

3) = .4

√

3 ≈ .6928, and T (.7) = .6426.

As T is increasing on [.5, 1/

√

3] and decreasing on [1/

√

3, .7], it follows that T

maps [.5, .7] into itself. Moreover,

sup

.5≤x≤.7

(x)| = sup

.5≤x≤.7

1.8|1 − 3x

| = max{|.45|, | − 0.846|} = 0.846.

Therefore, T is a contraction on [.5, .7] with contraction constant c = .846.

Now consider the ﬁxed point 0. Since T

(0) = 1.8 > 1, this is a repelling ﬁxed

point. On the interval [−

], we have

inf

|x|≤

(x) = inf

|x|≤

1.8(1 − 3x

) = 1.2.

So the proof of Lemma 11.1.2 shows that

|T x| ≥ 1.2|x| for all x ∈ [−

So the sequence T

x moves away from 0 until it leaves this interval.

11.1.5. EXAMPLE. Consider the linear function T (x) = mx + b for x ∈ R.

Then

|T x − T y| = |m||x − y|.

Hence T is a contraction on R provided that |m| < 1. This map has a ﬁxed point if

there is a solution to

x = T x = mx + b.

11.1 Fixed Points and the Contraction Principle 337

It is easy to compute that x

∗

1−m

is the unique solution provided that m 6= 1.

What happens when m = 1?

We may think of T as the dynamical system on R that maps each point x to

T x. Consider the forward orbit O(x) = {T

x : n ≥ 0} of a point x. We obtain a

sequence deﬁned by the recurrence

n+1

= T x

for n ≥ 0.

A simple calculation shows that

= mx

+ b

= m

+ (1 + m)b

= m

+ (1 + m + m

= m

+ (1 + m + m

+ m

)b.

It appears that there is a general formula

= m

+ (1 + m + m

+ ··· + m

n−1

)b.

We may verify this by induction. It evidently holds true for n = 1. Suppose that it

is valid for a given n. Then

n+1

= mx

+ b = m

+ (1 + m + m

+ ··· + m

n−1

+ b

= m

n+1

+ (m + m

+ ··· + m

)b + b

= m

n+1

+ (1 + m + m

+ ··· + m

)b.

Hence the formula follows for n + 1, and so for all positive integers by induction.

When |m| < 1, the contraction case, this sequence has a limit that we obtain

by summing an inﬁnite geometric series.

lim

n→∞

= lim

n→∞

+ (1 + m + m

+ ··· + m

n−1

= 0 + b

∞

k=0

1 − m

Hence this sequence converges to the ﬁxed point x

∗

. Therefore, x

∗

is an attractive

ﬁxed point that may be located by starting anywhere and iterating T . This means

that an approximate solution to T x = x will be stable, meaning that the orbit of

any point close to x

∗

will remain close to x

∗

. In fact, it was not even necessary to

start close to x

∗

to obtain convergence.

On the other hand, when |m| > 1, lim

n→∞

| = ∞ and so this sequence di-

verges. There is still a ﬁxed point, but it is repelling. In this case, the answer is in

the past. The map T is one to one and thus we may solve for

−1

x = (x − b)/m =

x −

This map T

−1

is a contraction, and we can apply the previous analysis to it. Each

point x comes from the point x

−1

= T

−1

x. Going “back into the past” by setting

−n−1

= T

−1

−n

converges to the ﬁxed point x

∗

. As points close to x

∗

move

outward and eventually go off to inﬁnity, x

∗

is a source.

338 Discrete Dynamical Systems

Finally, when m = −1, there is a unique ﬁxed point. But this point cannot be

located as the limit of an orbit. The reason is that

x = −(T x) + b = −(−x + b) + b = x.

That is, T

equals the identity map on R. So with the exception of the ﬁxed point

∗

= b/2, every point has a period 2 orbit.

11.1.6. THE BANACH CONTRACTION PRINCIPLE.

Let X be a closed subset of a complete normed vector space (V, k · k). If T is a

contraction map of X into X, then T has a unique ﬁxed point x

∗

. Furthermore, if

x is any vector in X, then x

∗

= lim

n→∞

x and

x − x

∗

k ≤ c

kx − x

∗

k ≤

1 − c

kx − T xk,

where c is the Lipschitz constant for T .

PROOF. The statement of the theorem suggests how the proof should proceed. Pick

any point x

in X and form the sequence (x

) given by x

n+1

= T x

for n ≥ 0.

CLAIM: This sequence is Cauchy. To see this, ﬁrst observe that

n+1

− x

k = kT x

− T x

n−1

≤ ckx

− x

n−1

≤ c

n−1

− x

n−2

≤ c

− x

k = c

where D = kx

−x

k is a ﬁnite number. Using this fact and the triangle inequality,

we compute

n+m

− x

k ≤

m−1

i=0

n+i+1

− x

n+i

k ≤

m−1

i=0

n+i

D(11.1.7)

∞

i=0

n+i

D =

(1 − c)

Given ε > 0, choose N so large that c

< ε(1 − c)/D, which is possible since

lim

n→∞

= 0. Hence for n ≥ N and m ≥ 0, we have kx

n+m

− x

k < ε. So the

sequence (x

) is Cauchy, as claimed.

Because V is complete, the sequence (x

) converges to a point in V , say

lim

n→∞

= x

∗

And since X is closed, this limit point belongs to X. Observe that T is uniformly

continuous because it is Lipschitz (Proposition 5.5.4). Using continuity, we have

T x

∗

= T

lim

n→∞

= lim

n→∞

T x

= lim

n→∞

n+1

= x

∗

Hence x

∗

is a ﬁxed point.

11.1 Fixed Points and the Contraction Principle 339

Suppose that y ∈ X is also a ﬁxed point: so T y = y. Then

∗

− yk = kT x

∗

− T yk ≤ ckx

∗

− yk.

Since c < 1, this implies that kx

∗

− yk = 0, whence x

∗

= y. Therefore, x

∗

is the

unique ﬁxed point.

Now using the estimate (11.1.7), we obtain that

− x

∗

k = kT

− T

∗

≤ c

− x

∗

= c

lim

m→∞

− x

≤ c

(1 − c)

−1

kT x

− x

Finally, for an arbitrary point x in X, the preceding estimates yield the same

story. Since the ﬁxed point is unique, the limit x

∗

is obtained as the limit of every

orbit independent of the starting point. ¥

11.1.8. EXAMPLE. Let V = R, X = [−1, 1] and T x = cos x. By the Mean

Value Theorem, for any x, y ∈ X, there is a point z between x and y so that

|T x − T y| = |x − y||sin z|.

In particular, |z| < 1. Since sinx is increasing on [−1, 1],

max

|z|≤1

|sinz| = |sin±1| = sin1 < 1.

Thus T is a contraction. To ﬁnd the ﬁxed point experimentally, type any value

into your calculator and repeatedly hit the

cos button. If your calculator is set for

radians, the sequence will converge rapidly to 0.73908513321516064 . . ..

What happens when you do the same for T x = sin x? It is not a contraction.

Nevertheless, there is a unique ﬁxed point sin0 = 0, and the iterated sequence

converges. But it converges at a painfully slow rate. Try it on your calculator. It is

slow because the derivative at the ﬁxed point is cos0 = 1.

Indeed, the inequality 0 < sinθ < θ for θ in (0, π/2] shows that the only ﬁxed

point in [0, ∞) is x = 0. As sinx is odd, the same is true on (−∞, 0]. The ﬁrst

iteration x

= sinx

lies in [−1, 1]; and thereafter this inequality shows that if

0 < x

≤ 1, then 0 ≤ x

n+1

< x

< 1 for n ≥ 1. Likewise, if −1 ≤ x

< 0, then

the sequence x

is monotone increasing and bounded above by 0. Hence the limit

exists and must be the unique ﬁxed point of sinx. We can use the Taylor series of

sinx (see Exercise 10.1.D) to show that

|sinx − x| ≤

|x|

Thus if x

= .1, it follows that

− x

n+1

| ≤

= 10

−3

/6.

340 Discrete Dynamical Systems

Since each step moves us at most 10

−3

/6, it will take over

.1 − .01

−3

= 540 iter-

ations before x

≤ .01. After that, it will take at least 54,000 iterations to get

below .001 and 5.4 million more steps to obtain a fourth decimal of accuracy in the

approximation of the ﬁxed point.

One moral of this example is that for maps T that are not contractions, even if

applying T moves a point x very little, x need not be very close to a ﬁxed point x

∗

For contractions, it is true and we have a numerical estimate for kx − x

∗

k in terms

of kT x − xk and the Lipschitz constant.

11.1.9. EXAMPLE. If, in the deﬁnition of contraction, the condition is weak-

ened to kT x −T yk ≤ kx −yk, then we cannot conclude that there is a ﬁxed point.

For example, take X = R and T x = x + 1. Clearly, T has no ﬁxed points. But

since kT x − T yk = kx − yk, distance is preserved.

Even the strict inequality kT x − T yk < kx − yk is not sufﬁcient. Consider

X = [1, ∞) and Sx = x + x

−1

. Then

|Sx − Sy| = (x +

) − (y +

) = |x − y|(1 −

) < |x − y|

for all x, y ≥ 1. However, Sx > x for all x, so S has no ﬁxed point.

11.1.10. REMARK. The ﬁrst part of Lemma 11.1.2 may be proved as a simple

consequence of the Banach Contraction Principle. Indeed, suppose that T is a C

dynamical system with a ﬁxed point x

∗

such that |T

∗

)| < c < 1. As before,

use the continuity of T

to ﬁnd an interval I = [x

∗

− r, x

∗

+ r] so that |T

(x)| ≤ c

for all x ∈ I. The only difference here is that we are using a closed interval and

a ≤ sign instead of an open interval and strict inequality. Apply the Mean Value

Theorem to any two points x, y in I. For such points, there is a point z between

them so that |T x − T y| = |T

(z)||x − y| ≤ c|x − y|.

In particular,

|T x − x

∗

| = |T x − T x

∗

| ≤ c|x − x

∗

| ≤ cr.

Therefore, T maps the interval I into itself, and it is a contraction with contraction

constant c. By the Contraction Principle, we see that x

∗

is the unique ﬁxed point in

I. Moreover, we obtain the desired distance estimates.

11.1.11. EXAMPLE. This example deals with a system of linear equations and

looks for a condition that guarantees an attractive ﬁxed point. Let A =

be an

n × n matrix, and let b = (b

, . . . , b

) be a (column) vector in R

. Consider the

system of equations

(11.1.12) x = Ax + b.

We will try to analyze this problem by studying the dynamical system given by the

map T : R

→ R

according to the rule

T x = Ax + b.

A solution to (11.1.12) corresponds to a ﬁxed point of T.

11.1 Fixed Points and the Contraction Principle 341

There are various norms on R

, and different norms lead to different criteria

for T to be a contraction. In this example, we will use the max norm,

kxk

∞

= max

1≤i≤n

If we think of points in R

as real-valued functions on {1, . . . , n}, say x(i) = x

for 1 ≤ i ≤ n, then this is the uniform norm on a space of continuous functions.

We will show that T is a contraction on R

in this norm if and only if

c := max

1≤i≤n

j=1

| < 1.

First suppose that c ≥ 1. There is some integer i

so that

c =

j=1

Set x

= sign(a

). Then

kx − 0k

∞

= kxk

∞

= max

1≤i≤n

| = 1

while

kT x − T 0k

∞

= kAxk

∞

≥ |(Ax)

j=1

= c ≥ 1 = kx − 0k

∞

So T is not contractive.

On the other hand, if c < 1, then we compute for x, y ∈ R

kT x − T yk

∞

= kA(x − y)k

∞

= max

1≤i≤n

j=1

− y

)

≤ max

1≤i≤n

j=1

||x

− y

≤

max

1≤i≤n

j=1

´³

max

1≤j≤n

− y

= ckx − yk

∞

So T is a contraction.

Thus by the Banach Contraction Principle, we know that there is a unique so-

lution that can be computed iteratively from any starting point. Choose x

= 0.

342 Discrete Dynamical Systems

Then

= T x

= b

= T x

= b + Ab = (I + A)b

= T x

= b + A(b + Ab) = (I + A + A

)b.

We will show that

= (I + A + ··· + A

n−1

)b.

This is evident for n = 0, 1, 2, 3 by the previous calculations. Assume it is true for

some integer n. Then

n+1

= T x

= b + A(I + A + ··· + A

n−1

)b = (I + A + ··· + A

)b.

So the formula is established by induction.

The solution to (11.1.12) is the unique ﬁxed point

∗

= lim

n→∞

= lim

n→∞

(I + A + ··· + A

n−1

)b =

∞

k=0

The important factor that makes this inﬁnite sum convergent is that, because T and

A are contractions,

∞

= kA

b − A

0k ≤ c

kb − 0k

∞

= c

kbk

∞

So this series is dominated by a convergent geometric series and thus converges

by the comparison test. Indeed, the same argument shows that the series

∞

k=0

converges for every vector x ∈ R

. So the sum C =

∞

k=0

makes sense as a

linear transformation. We note that, in particular, if x is any vector in R

, then

lim

n→∞

x = 0. The solution to our problem is x

∗

= Cb.

We know from linear algebra how to solve the equation x = Ax + b. This

leads to (I − A)x = b. When I − A is invertible, there is a unique solution

x = (I − A)

−1

b. This suggests that our contractive condition (11.1.11) leads to

the conclusion that I − A is invertible with inverse C =

∞

k=0

. To see that this is

the case, compute

(I − A)Cx = lim

n→∞

(I − A)(I + A + ··· + A

n−1

= lim

n→∞

(I + A + ··· + A

n−1

)x − (A + A

+ ··· + A

= lim

n→∞

x − A

x = x.

Therefore, I − A has inverse C.