for all a, b ∈ A. By considering

g(x) = (1 ’ )f (x) + a0

for some a0 ∈ A and > 0 show that

inf{ f (a) ’ a : a ∈ A} = 0

and deduce that f has a ¬xed point in A.

Give an example to show that the conclusion may be false if any one of

the three conditions:- convex, closed and bounded is omitted.

The following result is useful in the theory of Markov chains (see Exer-

cise K.258). Suppose pij ≥ 0 for 1 ¤ i, j ¤ n and n pij = 1 for 1 ¤ i ¤ n.

j=1

n

Give R the norm

n

j=1 |xj |. By choosing an appropriate

1 where x 1 =

A and f show that we can ¬nd πi ≥ 0 for 1 ¤ i ¤ n with n πi = 1 such

i=1

that

n

πi pij = πj .

i=1

Exercise K.257. [12.1, P] Throughout this question (X, d) is a non-empty

metric space with the Bolzano-Weierstrass property and T : X ’ X is

a map such that d(T x, T y) ¤ d(x, y) and such that, given any x, y ∈ X

such that x = y we can ¬nd a strictly positive integer N (x, y) such that

d(T N (x,y) x, T N (x,y) y) < d(x, y).

(i) Show that the map S : X ’ R given by Sx = d(x, T x) is continuous.

Explain why this means that there is a y ∈ X such that d(y, T y) ¤ d(T x, x)

for all x ∈ X. Show that, in fact y = T y. Show that y is the unique ¬xed

point of T .

(ii) Let > 0 and write

Un = {x ∈ X : d(T n x, y) < }.

572 A COMPANION TO ANALYSIS

Show that Un ⊆ Un+1 and that Un is open for all n ≥ 1. Write U = ∞ Un

n=1

and F = X \ U . Why does F have the Bolzano-Weierstrass property? Show

that T x ∈ F whenever x ∈ F . Use part (i) to show that, if F were non-

empty, there would exist a w ∈ F with T w = w. Deduce that F is indeed

empty.

(iii) Show that, if x ∈ X, then d(T n x, y) ’ 0 as n ’ ∞.

Exercise K.258. (Finite Markov chains.) [12.1, T!, ‘ ] In a ¬nite

Markov chain with states 1, 2, . . . , m, if the system is in state i at time

n it will be in state j at time n + 1 with probability pij irrespective of any

earlier history. Thus, if it is in state i with probability qi at time n and in

state j with probability qj at time n + 1, we have

m

qj = qi pij .

i=1

The reader may ignore the previous paragraph but it explains why we are

interested in the space

m

X = {q ∈ Rm : qi = 1, qs ≥ 0 [1 ¤ s ¤ m]}

i=1

and the map T : X ’ Rm given by T q = q where qj = m qi pij for all

i=1

1 ¤ j ¤ m. Verify that if, as we shall do from now on, we take pij ≥ 0 for all

1 ¤ i, j ¤ m and m pij = 1 for all 1 ¤ i ¤ m then T q ∈ X for all q ∈ X

j=1

and so we may consider T as a map from X to X.

Finally we have to choose a metric d. In most of this book the particular

choice of metric has not been important but here it is. We take

m

d(u, v) = u ’ v |ui ’ vi |

=

1

i=1

for all u, v ∈ X.

(i) Explain why (X, d) has the Bolzano-Weierstrass property.

(ii) Show that d(T u, T v) ¤ d(u, v) for all u, v ∈ X.

(iii) Show that, if n ≥ 1,

m

(n)

n

(T q)j = qi pij

i=1

(n) (n)

for all 1 ¤ j ¤ m where pij ≥ 0 for all 1 ¤ i, j ¤ m and m pij = 1 for

j=1

all 1 ¤ i ¤ m. If you know some probability prove this both by an algebraic

and a probabilistic argument.

573

Please send corrections however trivial to twk@dpmms.cam.ac.uk

(iv) Show that, if

(N )

pij > 0 for all 1 ¤ i, j ¤ m

for some N ≥ 1, then d(T N u, T N v) < d(u, v) for all u, v ∈ X with u = v.

(v) Conclude, using Exercise K.257, that, provided only that holds for

some N ≥ 1, there is a unique π ∈ X such that T π = π and that, if q ∈ X,

then d(T n q, π) ’ 0 as n ’ ∞. If the associated Markov chain has been

running for a long time, what can you say about the probability that it is in

state i?

(vi) Suppose that m = 2, p12 = p21 = 1 and p11 = p22 = 0. Show that

is a unique π ∈ X such that T π = π. For which q ∈ X is it true that

d(T n q, π) ’ 0 as n ’ ∞? Why does your result not contradict (v)?

(vii) Suppose that m = 2, p12 = p21 = 0 and p11 = p22 = 1. Find all the

π ∈ X such that T π = π. What can you say about the behaviour of T n q

as n ’ ∞ for each q ∈ X? Why does your result not contradict (v)?

(viii) Suppose that m = 4 and that pij = 1/2 if 1 ¤ i, j ¤ 2 or 3 ¤ i, j ¤

4 and that pij = 0 otherwise. Find all the π ∈ X such that T π = π. What

can you say about the behaviour of T n q as n ’ ∞ for each q ∈ X?

(ix) Note that, by Exercise K.256, the equation T π = π always has a

solution in X even if does not hold.

Exercise K.259. (Countable Markov chains.) [12.1, T!] In this exer-

cise and the next we consider Markov chains with an in¬nite number of states

1, 2, . . . . In algebraic terms we consider a collection of positive numbers pij

[1 ¤ i, j] such that ∞ pij = 1 for each i ≥ 1.

j=1

1

(i) Consider l the space of real sequences whose sum is absolutely con-

∞

n=1 |xn |. Show that, if we write

vergent, with norm 1 given by x ∞ =

∞

(T x)j = j=1 xi pij , then T is well de¬ned continuous linear map from l 1 to

l1 with operator norm T = 1. Show further that, if we write

X = {q ∈ l1 : q = 1 and qi ≥ 0 for all i ≥ 1},

1

then T q ∈ X whenever q ∈ X. (Note that you are manipulating in¬nite

sums and you must justify each step carefully. Results like Lemma 5.3.9 may

be useful.)

(ii) We shall only be interested in systems satisfying the following exten-

sion of . If k ≥ 1 there exists an N (k) such that

(N (k))

> 0 for all 1 ¤ i, j ¤ k.

pij

Show that, under this condition, given any u, v ∈ X with u = v, we can

¬nd an N ≥ 1 such that d(T N u, T N v) < d(u, v).

574 A COMPANION TO ANALYSIS

(iii) Show, under assumption , that, if the equation T π = π has a

solution π ∈ X, then it is unique. Let

Y = {h ∈ l1 : hi ≥ 0 for all i ≥ 1.}

Find all the solutions of the equation T h = h with h ∈ Y ¬rstly under the

assumption that the equation T π = π has a solution π ∈ X and secondly

under the assumption that it does not.

(iv) Show, under assumption , that, if the equation T π = π has a

solution π ∈ X, then πi > 0 for all i.

(v) Consider the following systems. In each case show we have a Markov

chain satisfying . By solving the appropriate di¬erence equations, or

otherwise, show that in case (a) the equation T π = π has a solution π ∈ X

but in cases (b) and (c) it does not.

(a) p12 = 1; pi i’1 = 1/2, pi i = pi i+1 = 1/4 for i ≥ 2; pij = 0 otherwise.

(b) p12 = 1; pi i+1 = 1/2, pi i = pi i’1 = 1/4 for i ≥ 2; pij = 0 otherwise.

(c) p12 = 1; pi i’1 = pi i = pi i+1 = 1/3 for i ≥ 2; pij = 0 otherwise.

Exercise K.260. [12.1, T!, ‘ ] This question continues the previous one.

We assume that condition holds and that the equation T π = π has a

solution π ∈ X. We will need part (ii) of Exercise K.195.

(i) Let J ≥ 1 be ¬xed. Show, using part (iv) of question K.259, that we

can ¬nd an h ∈ Y such that T h = h and hJ = 1.

(ii) We continue with the notation of (i). Explain why X does not have

the Bolzano-Weierstrass property but

XJ = {q ∈ X : hi ≥ qi for all i ≥ 1}

does. Explain why XJ is non-empty and show, carefully, that T q ∈ XJ

whenever q ∈ XJ . Deduce that, if q ∈ XJ , then T n q ’ π 1 ’ 0 as n ’ ∞.

(iii) Let e(p) ∈ l 1 be given by e(p)p = 1, e(p)i = 0 otherwise. Explain why

T n e(p)’π 1 ’ 0 as n ’ ∞. Deduce that, if q ∈ X, then T n q’π 1 ’ 0.

Interpret this result probabilistically.

Exercise K.261. [12.2, P] Let (X, d) be a complete metric space and T :

X ’ X a mapping such that T n is a contraction mapping. Show that T has

a unique ¬xed point. [Hint. Show that if w is a ¬xed point for T n then so is

T w.]

If you have done Question K.253, explain why the example asked for in

the last paragraph of that question does not contradict the result of the ¬rst

paragraph of this question.

575

Please send corrections however trivial to twk@dpmms.cam.ac.uk

Consider the space C([a, b]) with the uniform norm. Let φ be a continuous

real-valued function on R — [a, b] which satis¬es the Lipschitz condition

|φ(x, t) ’ φ(y, t)| ¤ M for x, y ∈ R and t ∈ [a, b],

and let g ∈ C([a, b]). De¬ne T : C([a, b]) ’ C([a, b]) by

t

(T h)(t) = g(t) + φ(h(s), s) ds.

a

Show, by induction, or otherwise that

1n

(T n h)(t) ’ (T n k)(t) M (t ’ a)n h ’ k

¤

∞ ∞

n!

for all h, k ∈ [a, b].

Show that T has a ¬xed point and comment brie¬‚y on the associated

theorem on the existence of solutions of a certain di¬erential equation.

Exercise K.262. [12.2, P] Suppose that f : R ’ R is di¬erentiable with

|f (x)| < M for all x ∈ R. Show that the system of equations

n

aij f (xj ) + bi [1 ¤ i ¤ n]

xi =

j=1

with aij and bi real has a unique solution provided that

n n

1

a2 < .

ij

M2

i=1 j=1

Exercise K.263. [12.2, P, S] Consider the di¬erential equation for a func-

tion y : R ’ R

y (t) = y(t)± , y(0) = 0

where ± is real and strictly positive. For which values of ± does have only

one solution and for which values of ± does it have more than one? If has

only one solution, prove this. If has more than one solution, give at least

two solutions explicitly.

Exercise K.264. [12.2, P] Dieudonn´ is associated in most mathemati-

e

cians™ minds with the abstract approach of Bourbaki and his own text Foun-

dations of Modern Analysis [13]. He may have had this in mind when he

576 A COMPANION TO ANALYSIS

wrote the determinedly concrete In¬nitesimal Calculus [14] from which this

exercise is taken.

(i) Suppose f : R2 ’ R is a continuous function with f (t, u) < 0 when

tu > 0 and f (t, u) > 0 when tu < 0. Explain why f (0, t) = f (u, 0) = 0 for

all t and u. If y : R ’ R is a di¬erentiable function with

y (t) = f (t, y(t)) for all t ∈ R, y(0) = 0,

show, by considering the behaviour of y at a maximum and a minimum in

each interval [0, c] with c > 0, or otherwise, that y(t) = 0 for all t ≥ 0. Show

that y(t) = 0 for all t ∈ R and so has a unique solution.

(ii) Now de¬ne

±

if x ≥ t2 ,

’2t

f (t, u) = ’2x/t if t2 > x > ’t2 ,

if ’t2 > x.

2t

Verify that f is well de¬ned and continuous everywhere and satis¬es the

hypotheses of (i). Now set y0 (t) = t2 and de¬ne

t

yn+1 (t) = f (s, yn (s)) ds.

0

Show that yn (t) fails to converge as n ’ ∞ for any t = 0 although, as we

know from (i), has a unique solution.

Exercise K.265. [12.3, P] (This exercise makes repeated use of the mean

value inequality.)

(i) Consider the di¬erential equation

y (t) = |y(t)|±

with ± > 1. Suppose y is a solution with y(0) ≥ 1. Show that y(t) is strictly

increasing for t ≥ 0 and y(t) ≥ t + 1 for t ≥ 0. Let tj be de¬ned by taking

y(tj ) = 2j . Show that tj+1 ’ tj ¤ 2(1’β)j and deduce that there exists a

t— ∈ R such that tj ’ t— as j ’ ∞. Conclude that y(t) ’ ∞ as t ’ t—

through values of t < t— .

(ii) Prove the result of Example 12.3.6 by an argument along the lines of

part (i).

(iii) Show that there exists a di¬erentiable function y : [0, ∞) ’ R such

that y(0) = e and

y (t) = y(t) log y(t).

577

Please send corrections however trivial to twk@dpmms.cam.ac.uk

Exercise K.266. (Euler™s method.) [12.3, T] The next few questions

deal with Euler™s method for ¬nding approximate solutions of a di¬erential

equation. They were suggested by the typically neat treatment in [44]. You

will ¬nd the discussion more interesting if you have used Euler™s method

before or if you try one of the excellent demonstrations which now exist on

the Internet.

Suppose we wish to solve the di¬erential equation y (t) = f (t, y(t)),

y(0) = y0 numerically on a computer. (We shall look at y(t) for t ≥ 0

but the same ideas apply when t ¤ 0.) A natural approach is to seek (ap-

proximate) solutions at the points xr = rh where the strictly positive number

h is called the ˜step length™ and r is a positive integer. Explain brie¬‚y why

we expect

y (r + 1)h ≈ y(rh) + f (rh, y(rh))h.

This suggests that our approximation yr to y(rh) could be obtained by solving

the system of equations

yr+1 = yr + f (xr , yr )h. (A)

This is called Euler™s method.

Euler™s method seems reasonable and works on suitable test examples.

In this question we investigate its behaviour in general. We shall assume

stronger conditions on f than we did in Theorem 12.2.3 and elsewhere in

Sections 12.2 and 12.3. Speci¬cally, we demand that f : R2 ’ R is once

di¬erentiable and there exist constants K and L such that |f,2 (t, u)| ¤ K

and

|f,1 (t, u)| + |f,2 (t, u)f (t, u)| ¤ L

for all (t, u) ∈ R2 . Explain brie¬‚y why these conditions imply the existence

of a unique di¬erentiable y : R ’ R such that

y (t) = f (t, y(t)), y(0) = y0 . (B)

Explain why y is twice di¬erentiable and express y (t) in terms of f (t, y(t)),

f,1 (t, y(t)) and f,2 (t, y(t)). By using the 2nd mean value theorem (Exer-

cise K.49), or otherwise, show that

Lh2

|y (n + 1)h) ’ y(nh) ’ f (nh, y(nh))h| ¤ .

2

Use this result to show that

Lh2

|y (n + 1)h) ’ yn+1 | ¤ (1 + Kh)|y(nh) ’ yn | + .

2

578 A COMPANION TO ANALYSIS

Deduce that

Lh

((1 + Kh)N +1 ’ 1).

|y(N h) ’ yN | ¤

2K

[h]

In order to emphasise the dependence on h, let us write yn = yn . Show

that, if the positive number a is ¬xed and we take hN = a/N , then

LhN

[h ]

((1 + KhN )N +1 ’ 1).

|y(a) ’ yN N | ¤

2K

Observe (or recall) that that, if x ≥ 0, then

m

1 m1

x m

xr ≥ 0,

e ’ (1 + x) ≥ ’

r mr

r!

r=0

and deduce that

LhN aK

[h ]

|y(a) ’ yN N | ¤ (e ’ 1) (C)

2K

[h ]

and, in particular, yN N ’ y(a) as N ’ ∞.

Exercise K.267. [12.3, T, ‘ ] We continue with the discussion of Exer-

cise K.266. Informally, we may interpret the inequality (C) in Exercise K.266

as saying that that ˜our error estimate for Euler™s method is roughly propor-

tional to the step length™. nequality (C) is, however, only an upper estimate

for the error. Can we get a substantially better estimate? Consider the spe-

cial case f (t, u) = u, y0 = 0 and a = 1. Show that y(t) = et and yn = (1+y)n .

Show that

[h ]

y(1) ’ yN N = e ’ (1 + N ’1 )N

N

1 N1 1 hN

≥ ’ ≥ = .

r Nr

r! 2N 2

r=0

Informally, we may say ˜in this case, the error for Euler™s method decreases

no faster than the step length™.

We see that (roughly speaking) halving the step length in Euler™s method

will double the amount of calculation and only halve the error. Thus Euler™s

method is a reasonable one if we want to solve one di¬erential equation to

a reasonable degree of accuracy but unattractive if we want to solve many

di¬erential equations to a high degree of accuracy.

579

Please send corrections however trivial to twk@dpmms.cam.ac.uk

Exercise K.268. [12.3, T, ‘ ] We continue with the discussion of Exer-

cises K.266 and K.267. So far we have ignored the fact that computers only

work to a certain degree of accuracy. As a simple model to take account of

this, we replace equation (A) of Exercise K.266 by

yr+1 = yr + f (xr , yr )h +

˜ ˜ ˜ (D)

r

where the ˜error™ r satis¬es the condition | r | ¤ for some ¬xed > 0. As

before, we impose the initial condition y0 = 0.

˜

[h]

(i) As in Exercise K.266, we take yn = yn , ¬x a positive number a and

take hN = a/N . Show that

LhN

[h ]