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

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

10.9 Uniform Approximation by Splines 323

that ξ depends on b. Then we obtain

−

c − a

(ξ) =

f(a) − f(c)

c − a

+ lim

b→a

f(b) − f(a)

b − a

f(a) − f(c)

c − a

+ f

(a).

Rearranging, this becomes

f(c) = f(a) + f

(a)(c − a) +

(c − a)

(ξ) for some ξ ∈ (a, c).

We could make the limit argument correct, but we do not need to do so because this

is just a consequence of the order one Taylor Theorem (see Exercise 10.1.B).

PROOF OF THEOREM 10.9.1. We need to show that h

is close to f

at the

points x

. We rewrite the formula (10.8.6) as

) =

6(a

i+1

− a

)

∆

i+1

−

+ 2s

i+1

∆

i+1

for 0 ≤ i ≤ k − 1

) =

−6(a

− a

i−1

)

∆

i−1

+ 4s

∆

for 1 ≤ i ≤ k.

The idea is to eliminate the unknown s

, . . . , s

k−1

from these 2k equations to yield

k + 1 equations for the h

), 0 ≤ i ≤ k.

We save some time by presenting the list of equations and ask the interested

reader to verify that they are correct.

2∆

) + ∆

) = 6

− a

∆

− s

∆

i−1

)+2(∆

+∆

i+1

)+∆

i+1

) = 6

i+1

−a

∆

i+1

−

−a

i−1

∆

for 1 ≤ i ≤ k − 1

∆

k−1

) + 2∆

) = 6

−

− a

k−1

∆

Let us deﬁne the matrix

Y =







2∆

∆

0 0 . . . 0 0 0

∆

2(∆

+∆

) ∆

0 . . . 0 0 0

0 ∆

2(∆

+∆

) ∆

. . . 0 0 0

0 0 0 . . . ∆

k−2

2(∆

k−2

+∆

k−1

) ∆

k−1

0 0 0 . . . 0 ∆

k−1

2(∆

k−1

+∆

) ∆

0 0 0 . . . 0 0 ∆

2∆







324 Approximation by Polynomials

So if we set







)

k−1

)







, f







)

k−1

)







, and z =







−a

∆

− s

−a

∆

−

−a

∆

−a

k−1

∆

−

k−1

−a

k−2

∆

k−1

−

−a

k−1

∆







then the equation becomes Y h

= z.

Now we apply Lemma 10.9.2 to approximate z. Use x

i−1

, x

i+1

for a, b, c.

There is a point ξ

in [x

i−1

, x

i+1

] so that

i+1

− a

∆

i+1

−

− a

i−1

∆

= 6

−x

i−1

)f(x

i+1

) − (x

i+1

−x

i−1

)f(x

) + (x

i+1

−x

)f(x

i−1

)

i+1

− x

)(x

− x

i−1

)

= 3

i+1

− x

i−1

(ξ

) = 3(∆

+ ∆

i+1

(ξ

)

for 1 ≤ i ≤ k − 1. The two end terms are approximated using the limit version,

namely Taylor’s formula of order 2

− a

∆

− s

= 6

f(x

) − f(x

)

− x

− f

)

= 3

− x

(ξ

) = 3∆

(ξ

)

for some ξ

in [x

, x

]. Similarly, there is a point ξ

in [x

k−1

, x

] such that

−

− a

k−1

∆

= 6

) −

f(x

) − f (x

k−1

)

− x

k−1

= 3

− x

k−1

(ξ

) = 3∆

(ξ

Now we approximate h

− f

by evaluating Y (h

− f

). The ﬁrst coefﬁcient

is estimated by

3∆

(ξ

) − 2∆

) − ∆

)

≤ 2∆

(ξ

) − f

)| + ∆

(ξ

) − f

≤ 3∆

ω(f

;δ).

Recall from Lemma 14.9.10 that ω(f

;2δ) ≤ 2ω(f

;δ). For 1 ≤ i ≤ k − 1, we

obtain

3(∆

+∆

i+1

(ξ

) − ∆

i−1

) − 2(∆

+∆

i+1

) − ∆

i+1

)

≤ 2(∆

+ ∆

i+1

)

(ξ

) − f

)

+ ∆

(ξ

) − f

i−1

)

+ ∆

i+1

(ξ

)−f

i+1

)

≤ 2(∆

+ ∆

i+1

)ω(f

;δ) + (∆

+ ∆

i+1

)ω(f

;2δ)

≤ 4(∆

+ ∆

i+1

)ω(f

;δ).

10.9 Uniform Approximation by Splines 325

Finally, the last term is estimated

3∆

(ξ

) − ∆

(ξ

k−1

) − 2∆

)

≤ ∆

(ξ

) − f

(ξ

k−1

)| + 2∆

(ξ

) − f

≤ 3∆

ω(f

;δ).

Let A = max{|h

) − f

)| : 0 ≤ i ≤ k} occur at i

. Then looking at the

th coefﬁcient of Y (h

− f

), we obtain

4(∆

+ ∆

)ω(f

;δ)

≥

∆

−1

) − f

−1

)

+ 2(∆

+ ∆

)

) − f

)

+ ∆

) − f

)

≥ 2

(∆

+ ∆

)

) − f

)

−

∆

−1

) − f

−1

)

−

∆

) − f

)

≥ (∆

+ ∆

)A.

So A ≤ 4ω(f

;δ). When the i

= 0 or k, we obtain 3ω(f

;δ) instead.

We are almost done with the estimate for the second derivative. Notice that on

i−1

, x

], h

(x) = h

(x) is linear. So h

(x) lies between h

i−1

) and h

For convenience, suppose that h

i−1

) ≤ h

). The other case is similar. Then

−5ω(f

;δ) ≤

i−1

) − f

i−1

)

i−1

) − f

(x)

≤ h

(x) − f

(x)

≤

) − f

)

−

) − f

(x)

≤ 5ω(f

;δ).

Thus kh

− f

∞

≤ 5ω(f

;δ).

The rest is easy. Since f(x

i−1

) − h(x

i−1

) = 0 = f(x

) − h(x

), Rolle’s

Theorem provides a point ζ

in [x

i−1

, x

] such that f

(ζ

) − h

(ζ

) = 0. Hence for

any point x in [x

i−1

, x

(x) − h

(x)| =

(t) − h

(t) dt

≤ 5ω(f

;δ)|x − ζ

| ≤ 5δω(f

;δ).

Therefore kh

− f

∞

≤ 5δω(f

;δ). Now pick the nearest partition point x

to x,

so that |x − x

| ≤ δ/2. Since f(x

) = h(x

|f(x) − h(x)| =

(t) − h

(t) dt

≤ 5δω(f

;δ)|x − x

| ≤

ω(f

;δ).

So kh − f k

∞

≤

ω(f

;δ). ¥

326 Approximation by Polynomials

Exercises for Section 10.9

A. Show that S(∆) has dimension k + 3.

B. A second-order Mean Value Theorem (Lemma 10.9.2) suggests the possibility of a

third-order Mean Value Theorem. Suppose that f ∈ C

[a, d] and b, c in (a, d) with b 6=

c. If P is the unique quadratic polynomial through (a, f(a)), (c, f(c)) and (d, f(d)),

show that there is a point ξ ∈ [a, d] with

f(b) − P (b) =

(b − c)(b − a)(b − d)

000

(ξ).

C. Prove that every continuous function on [0, 1] is the uniform limit of the sequence of

cubic splines h

with nodes at {j2

−k

: 0 ≤ j ≤ 2

10.10. Appendix: The Stone–Weierstrass Theorem

We conclude this chapter with a very general approximation theorem that has

many applications to approximation problems. It provides a very simple, easy to

check criterion for when all continuous functions on a compact metric space can be

approximated by some element of a subalgebra of functions. In particular, we shall

see immediate consequences for approximation by polynomials in several variables

and by trigonometric polynomials.

10.10.1. DEFINITION. A subset A of C(X), the space of continuous real-

valued functions on a compact metric space X, is an algebra if it is a subspace of

C(X) that is closed under multiplication (i.e., if f, g ∈ A, then fg ∈ A).

For f, g ∈ C(X), deﬁne new elements of C(X), f ∨ g and f ∧ g, by

(f ∨ g)(x) = max{f(x), g(x)} and (f ∧ g)(x) = min{f(x), g(x)}.

A subset L of C(X) is a vector lattice if it is a subspace that is closed under these

two operations, that is, f, g both in L imply f ∨ g and f ∧ g are in L.

It is easy to verify the two identities f ∨g = 1/2(f + g) + 1/2|f −g| and that

f ∧ g = 1/2(f + g) − 1/2|f − g|. Conversely, |f| = f ∨ (−f). It follows that an

algebra, A, is a vector lattice if and only if |f| ∈ A for each f ∈ A.

10.10.2. DEFINITION. A set S of functions on X separates points if for each

pair of points x, y ∈ X, there is a function f ∈ S such that f(x) 6= f(y). Say that

S vanishes at x

if f(x

) = 0 for all f ∈ S.

In order to approximate arbitrary continuous functions on X from elements of

A, a moment’s thought shows that A must separate points. Moreover, A cannot

vanish at any point, for then we could not approximate the constant function 1.

These rather modest requirements, combined with the algebraic structure of an

algebra, yield the following beautiful result.

10.10 Appendix: The Stone–Weierstrass Theorem 327

10.10.3. STONE–WEIERSTRASS THEOREM.

An algebra A of continuous real-valued functions on a compact metric space X

that separates points and does not vanish at any point is dense in C(X).

We break the proof into several parts. Because norms over several domains

occur in this proof, let us write kfk

for the uniform norm over X, and write

kpk

∞

for the uniform norm of a function on a real interval [a, b], if the interval is

understood.

10.10.4. LEMMA. If A is an algebra of real-valued continuous functions on X,

then its closure

A is a closed algebra and a vector lattice.

PROOF. It is easy to check that the closure of a subspace is still a subspace. The

veriﬁcation is left as an exercise. To see that A is closed under multiplication, take

f, g ∈ A. Choose sequences f

and g

in A that converge uniformly to f and g,

respectively. Since A is an algebra, f

belongs to A. Then the sequence (f

)

converges uniformly to fg (see Exercise 8.2.D). So A is closed under multiplica-

tion, and thus is an algebra.

Fix a function f ∈ A. By the Weierstrass Approximation Theorem, the func-

tion h(t) = |t| for t ∈ [−kfk

, kfk

] is the uniform limit of a sequence p

polynomials. We can arrange that p

(0) = 0. Indeed, 0 = h(0) = lim

n→∞

(0).

Thus q

(x) = p

(x) − p

(0) satisﬁes q

(0) = 0 and

kh − q

∞

≤ kh − p

∞

+ |p

(0)|.

The right-hand side converges to 0, and thus (q

) converges uniformly to h.

We will show that |f| belongs to A also. Since A is an algebra, all linear

combinations of f, f

, f

, . . . belong to A. So if q is a polynomial with q(0) = 0,

say q(x) = a

x + a

+ ··· + a

, then

q(f) = a

f + a

+ ··· + a

belongs to A. Moreover, if p, q are two such polynomials, then

kp(f) − q(f)k

= sup

x∈X

|p(f(x)) − q(f(x))|

≤ sup

t∈[−kfk

,kfk

]

|p(t) − q(t)| = kp − qk

∞

Since kq

(f) − q

(f)k

≤ kq

− q

∞

and (q

) is a Cauchy sequence, we

conclude that (q

(f)) is also a Cauchy sequence. Thus the limit g belongs to A.

Then g(x) = lim

n→∞

(f(x)) = h(x) = |f(x)|. So |f| belongs to A for each

f ∈ A. As we remarked previously, this implies that A is a vector lattice. ¥

10.10.5. LEMMA. If A is an algebra on X that separates points and never

vanishes, then for any x, y ∈ X and α, β ∈ R, there is a function h ∈ A such that

h(x) = α and h(y) = β.

328 Approximation by Polynomials

PROOF. There is a function f ∈ A such that f(x) 6= f(y). We may assume that

f(y) 6= 0. If f(x) 6= 0 also, try h = f

− tf. We require

f(x)

− tf(x) = α

f(y)

− tf(y) = β.

Solving yields t =

α − β

f(y) − f(x)

+ f (x) + f(y). If f(x) = 0, there is a function

g ∈ A with g(x) 6= 0. In this case,

h =

g(x)

g +

βg(x) − αg(y)

g(x)f(y)

will sufﬁce. ¥

PROOF OF THE STONE–WEIERSTRASS THEOREM. Fix a function f ∈ C(X)

and ε > 0. We will approximate f within ε by functions in A. For each pair

of points x, y ∈ X, use Lemma 10.10.5 to ﬁnd functions g

x,y

∈ A such that

x,y

(x) = f (x) and g

x,y

(y) = f(y).

Fix y. For each x 6= y,

= {z ∈ X : g

x,y

(z) > f(z) − ε} = (g

x,y

− f)

−1

(−ε, ∞)

is an open set containing x and y. Thus {U

: x ∈ X \{y}} is an open cover of X.

By the Borel–Lebesgue Theorem (Theorem 9.2.3), this cover has a ﬁnite subcover

, . . . , U

. Let g

= g

∨g

∨. . . g

. By Lemma 10.10.4, g

belongs to

A. By construction, g

(y) = f(y) and g

(x) > f (x) − ε for all x ∈ X.

Now deﬁne V

= {x ∈ X : g

(x) < f (x)+ε}, which is an open set containing

y. Then {V

: y ∈ X} is an open cover of X. By the Borel–Lebesgue Theorem,

this cover has a ﬁnite subcover V

, . . . , V

. Let g = g

∧ g

∧ . . . g

. By

Lemma 10.10.4, g belongs to

A. By construction, g(x) < f(x) + ε for all x ∈ X.

Moreover, since g

> f(x) − ε for 1 ≤ j ≤ l,

f(x) − ε < g(x) < f(x) + ε for all x ∈ X.

Thus kf − gk

< ε as desired. ¥

10.10.6. COROLLARY. Let X be a compact subset of R

. The algebra of all

polynomials p(x

, x

, . . . , x

) in the n coordinates is dense in C(X).

PROOF. It is immediately clear that the set P of all polynomials in n variables

is an algebra. The constant function 1 does not vanish at any point. Finally, any

two distinct points are separated by at least one of the coordinate functions x

Therefore, P satisﬁes the hypotheses of the Stone–Weierstrass Theorem and hence

is dense in C(X). ¥

Another application of the Stone–Weierstrass Theorem yields an abstract proof

of the following corollary, which will be given a different and more direct proof in

Fej

er’s Theorem (Theorem 14.6.4). See also Corollary 13.6.6 for yet another proof.

10.10 Appendix: The Stone–Weierstrass Theorem 329

10.10.7. COROLLARY. The set of all trigonometric polynomials is dense in

∗

[−π, π], the space of 2π-periodic functions on R.

PROOF. The set TP of all trig polynomials f(t) = a

i=1

coskt + b

sinkt

(see Section 7.4) is not so obviously an algebra. The crucial identities are

sinkt sin lt =

cos(k − l)t −

cos(k + l)t

sinkt cos lt =

sin(k + l)t +

sin(k − l)t

coskt cos lt =

cos(k − l)t +

cos(k + l)t.

This shows that the product of two trig functions is a trig polynomial. As the set

of trig polynomials is a vector space, the general multiplication of trig polynomials

will also be a trig polynomial. So TP is an algebra.

To put this problem into the context of the Stone–Weierstrass Theorem, let T

be the unit circle. Consider the map P (t) = (cost, sint) of R onto T . Observe that

P (s) = P (t) if and only if s −t is an integer multiple of 2π. In particular, [−π, π]

is wrapped around the circle with only the endpoints ±π coinciding. A continuous

function g ∈ C(T ) may be identiﬁed with the function f(t) = g(P (t)). It is easy

to see that f (−π) = f(π). If we deﬁne C

∗

[−π, π] to be the closed subspace given

{f ∈ C[−π, π] : f(−π) = f (π)},

then it is also easy to see that every function in C

∗

[−π, π] is obtained as g(P (t))

for some g ∈ C(T ). Moreover, this correspondence between C(T) and C

∗

[−π, π]

is isometric, linear, and preserves multiplication.

The two coordinate functions x

and x

on T send the point P (t) to cost

and sint, respectively. So the ﬁrst paragraph shows that polynomials in x

and

are actually trig polynomials of the variable t. So the algebra TP of all trig

polynomials in C

∗

[−π, π] is identiﬁed with the algebra of all usual polynomials on

T . By Corollary 10.10.6, the algebra of polynomials is dense in C(T). Therefore,

the algebra of trig polynomials is dense in C

∗

[−π, π]. ¥

Exercises for Section 10.10

A. Show that the closure of a subspace of C(X) is also a subspace of C(X).

B. Let X and Y be compact metric spaces. Show that the set of all functions of the form

i=1

(x)g

(y) for k ≥ 1 and f

∈ C(X) and g

∈ C(Y ) is dense in C(X × Y ).

C. Let h ∈ C[0, 1]. Show that every f ∈ C[0, 1] is a limit of polynomials in h if and only

if h is strictly monotone.

D. Let X be a compact metric space. Suppose that A is a subalgebra of C(X) that sep-

arates the points of X. If A 6= C(X), show that there is a point x

∈ X such that

A = {f ∈ C(X) : f (x

) = 0}.

HINT: Show that A + R1 is an algebra that does not vanish. Can A vanish at more

than one point?

330 Approximation by Polynomials

E. Let X be a compact metric space. A subset J of C(X) is an ideal if it is a vector space

with the property that if p ∈ J and f ∈ C(X), then fp ∈ J.

(a) Let E = {x ∈ X : J vanishes at x}. Show that E is closed.

(b) Show that J separates points of X \ E.

HINT: Fix f and ε > 0, and set F = {x ∈ X : |f(x)| ≥ ε}. For x ∈ X, ﬁnd

∈ J such that p

(x) = 2. Hence ﬁnd a ﬁnite set of elements p

∈ J such that

p(x) =

i=1

(x)

≥ 1 for x ∈ F . Let q =

fnp

1 + np

for n sufﬁciently large.

F. Let A be a complex algebra of complex-valued continuous functions on X. That is, A

is a vector space over C and is closed under multiplication. Suppose that A separates

points and does not vanish at any point and further if f ∈ A, then

f belongs to A. Then

show that A is dense in the space C

(X) of all complex-valued continuous functions

on X.

HINT: Consider the set A

of all real-valued functions in A.

CHAPTER 11

Discrete Dynamical Systems

Suppose we wish to describe some physical system. The dynamical systems ap-

proach starts with a space X of all possible states of the system—think of a point

x in X as representing a state for some physical situation at some time. We will

assume that X is a subset of some normed linear space. Often X will be a subset

of R. The evolution of the system over time determines a function T mapping X

into itself that takes each state x to a new state, one unit of time later.

Suppose that x

is the state of the system at time zero and x

is the state of the

system at time n. If T

n+1

(x) := T (T

(x)) for n ≥ 1, then we have

= T x

n−1

= T

n−2

= ··· = T

Notice that in this chapter, T

x virtually always means T (T (x)) and not (T (x))

11.0.8. DEFINITION. Suppose that X is a subset of a normed linear space, and

T is a continuous map from X into itself. The pair (X, T ) is called a discrete

dynamical system. For each point x ∈ X, the forward orbit of x is the sequence

O(x) := {T

x : n ≥ 0}.

To determine the behaviour of this system, we study the forward orbit O(x).

What is the limit of this orbit for each x, as n goes to +∞? If x is changed a

little (in some sense), then how does this limit change? This turns out to be an

interesting problem, and there are systems where the limit can change dramatically

for tiny changes in the starting point. This leads to the idea of chaos, which we

study in Section 11.5.

We concentrate ﬁrst on ﬁxed points, that is, points x

∈ X with x

= T x

These are interesting for their own sake, since analysis problems can sometimes

be formulated so that the solution is the ﬁxed point of some dynamical system.

Viewing a problem this way can give important results that are otherwise hard to

obtain. In this chapter, we will take this approach to Newton’s method for solving

equations numerically. In Chapter 12, we will use it to study differential equations.

Later in this chapter, we describe other types of orbits and then look at the

notion of chaos for dynamical systems. The ﬁnal section of the chapter considers

331

332 Discrete Dynamical Systems

iterated function schemes, which provide a means of generating fractals. It requires

only Section 11.1 and the ﬁrst section of Chapter 9.

11.1. Fixed Points and the Contraction Principle

Fixed points are so important in analysis that we will discuss two methods for

ensuring their existence. Our ﬁrst method has the added advantage that it comes

equipped with a natural algorithm for computing the limit point. This has both

theoretical and computational advantages over purely existential arguments.

As motivation, we start with an example, the function graphed in Figure 11.1,

namely

T x = 1.8(x − x

Factoring shows that this cubic has roots at −1, 0 and 1. It has a local maximum

at the point (

√

). Since T is an odd function, it has a local minimum at

(−

√

, −

√

). To ﬁnd the ﬁxed points, we solve the equation

x = T x = 1.8x − 1.8x

This has three solutions, x = −

, 0, and

y = x

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

) showing ﬁxed points.

We classify ﬁxed points based on the orbits of nearby points. This behaviour is

crucial to understanding how to approximate a ﬁxed point.

11.1.1. DEFINITION. A ﬁxed point x

∗

is called an attractive ﬁxed point or a

sink is there is a open neighbourhood U = (a, b) containing x

∗

so that for every

point x in (a, b), the orbit O(x) converges to x

∗

. A ﬁxed point x

∗

is called a

repelling ﬁxed point or a source if there is a neighbourhood U = (a, b) containing