Constructive Real Analysis

By Allen A. Goldstein

This text introduces the methods of applied functional analysis and applied convexity. Suitable for advanced undergraduates and graduate students of mathematics, science, and technology, it focuses on the solutions to two closely related problems. The first concerns finding roots of systems of equations and operative equations in a given region. The second involves extremal problems of minimizing or maximizing functions defined on subsets of finite and infinite dimensional spaces. Rather than citing practical algorithms for solving problems, this treatment provides the tools for studying problem-related algorithms.
Topics include iterations and fixed points, metric spaces, nonlinear programming, polyhedral convex programming, and infinite convex programming. Additional subjects include linear spaces and convex sets and applications to integral equations. Students should be familiar with advanced calculus and linear algebra. As an introduction to elementary functional analysis motivated by application, this volume also constitutes a helpful reference for theoretically minded engineers, scientists, and applied mathematicians.

• Language: English
• Publisher: Dover Publications
• Release date: May 20, 2013
• ISBN: 9780486286600

Book preview

Analysis

__________________________ CHAPTER I

ROOTS

AND EXTREMAL

PROBLEMS

INTRODUCTION

This book is concerned with processes for finding roots of functions. Often the function f whose root we seek is the derivative of some other function g, that is, g′ = f. In this case, it can happen that a root of f is an extremal (maximum or minimum) for g. These matters, and generalizations of them, will be considered below. We shall dwell on the problem of finding extremals of functions that are subject to restraint.

By an algorithm for a problem we mean a recipe by means of which the solution to the problem can be calculated. An effective algorithm is one that can be used without exorbitant cost on a modern automatic digital calculator. We shall discuss below algorithms that are not necessarily effective. Sometimes these algorithms are effective for some problems but not for others. Moreover, in many cases, no estimates of effectiveness are known. As a general method the contraction mapping theorem and other principles will be used to discuss algorithms. The heart of the book, however, will be the techniques of the detailed analysis of the algorithms presented. An example for which it is easy to give a detailed analysis follows.

. Here, a is a positive number whose square root we wish to extract. The above formula is a consequence of Newton’s method, Section A-2. We shall describe the sequence {xn: n = 1, 2, 3, …}, which this formula generates. If xn , recall that the relative error of this approximation is given by

Theorem

  (i) Assume a and x0 to be positive.

.

.

Then

n 0, n = 1, 2, 3, …;

> 0,

n, for n = 1, 2, 3, ….

Proof

. Using (ii),

. Hence (a) is proved.

1 is nonnegative by (a). Thus, (b) follows by use of (a) and induction.

To prove (c), we calculate that

using (ii). By (c),

. Hence

by (b). Q.E.D.

Of course the above analysis does not consider that, in practice, computations will be made with inexact numbers. Considerations of such effects are referred to Wilkinson.¹

would be as follows: Given a, x, we calculate the sequence x1, x2, … by (ii). For n 1, we calculate

When qn n. In this scheme the termination of computation is done with a posteriori information—that is, the termination depends on the sequence x1, xto desired accuracy.

Unfortunately, we do not usually know as much about an algorithm as we know in this case. The above description is therefore in the nature of an ideal that we strive toward in our study of iterative processes.

PROBLEMS

1. n} monotonically converges to 0 and hence {xn.

2. . Prove this by induction and show that 2n n .

3. with a relative error of 10−10. Take x0 = 1.

SECTION A. ITERATIONS AND FIXED POINTS

A-1. Functional Iteration and Roots: One Variable

Let I = [a, b] and assume that f is a continuous function on I, taking values on a closed interval of the reals, say J. The function f is also called a map from I into J. If J is a subset of I, then f is called a map from I into itself. Suppose f is a map from I into itself. A fixed point of f is a point x I such that f(x) = x.

Lemma 1

Every continuous function f mapping I into itself has a fixed point.

Proof

If a is not a fixed point, then f(a) > a. If b is not a fixed point, then f(b) < b. Let h(x) = f(x) − x. Then h(a) = f(a) − a > 0 and h(b) = f(b) − b < 0. Since h is continuous, h has a root in I at, say, z. Consequently, f(z) = z.

A map from I into itself is said to be a contractor if, for every pair of points x and y in I, |f(x) − f(yq|x − y|, with q < 1.

Theorem 2

Assume that f is a contractor on I and set xn + 1 = f(xn) with x0 in I. Then there exists a unique fixed point of f, say z; the sequence {xn} converges to z; and |xn+1 − zqn + ¹|x0 − z|.

Proof

By the lemma, the existence of a fixed point is ensured. Hence, |xn + 1 − z| = |f(xn) − f(zq|xn − z|. This establishes the formula

for n = 0. Assume that |xn − zqn|x0 − z| for any n 1. Then

Because q z. To prove that z is unique, suppose there were two distinct fixed points z1 and z2. Then

a contradiction.

The process of generating a sequence by the formula xn + 1 = f(xn) is often called iteration or functional iteration. This is because x1 = f(x0), x2 = f(x1) = f(f(x0))…, and xn = fn(x0). Here fn stands for the composition of f n-times. In this terminology we have proved that {fn(xz.

Our object now is to determine suitable hypotheses (that is, hypotheses that can be verified and sometimes fulfilled) on a function h in order to calculate its roots by iteration.

Lemma 2

If f has a continuous derivative on I and if f maps I into itself, then |f′(x)| < 1 on I implies that f is a contractor.

Proof

By the mean-value theorem, |f(x) − f(y)| = |f′)| |x − ybetween x and yis less than unity; hence, f is a contractor.

Assume that h is a monotone function on I, which has a continuous positive derivative. Suppose h has a root z in the interior of I. Then h(a) < 0 < h(b). Define F(x) = x h(x). If F is to be a map of I into itself, we must have a F(xb for all x I> 0, F(a) > a and F(b) < bsmall and positive, a < F(x) < b for all x in I. Furthermore, since F′(xh′(x), and h′(x) > small and positive, |F′(x)| < 1 on I. These ideas are stated formally in the next paragraph.

Theorem 3

Assume h belongs to C¹[a, b], h(a)h(bh′(xfor all x in [a, b]. Set xn +1 = xn h(xn) with x0 arbitrary in [a, b]. Then {xn} converges to a root z of h and |xn + 1 − z)n+1|x0 − z|.

Proof

Set F(x) = x h(x). Observe that z is a fixed point of F if and only if z is a root of h. Since for all x in [a, bh′(xh′(xF′(x< 1 for all x in [a, b], and F is monotone-increasing on [a, b]. Since h(a)h(b) < 0 and h is monotone-increasing, h(a) < 0. Hence, F(a) > a, and F(b) < b > 0. Because F is monotone, a < F(x) < b for all x in [a, b]. Furthermore, |F′(x< 1 for all x in [a, b]. Thus, the theorem follows by Theorem 2 and Lemma 2.

Observe that the root z is unique because F has a unique fixed point. If h is monotone-decreasing, −h is monotone-increasing and has the same roots as h.

PROBLEM

The formula |xn + l − z)n+1|x0 − z| would be of practical interest if we could estimate |x0 − zcan be estimated. Show that

We conclude with the observation that Theorem 3 above assures us we can, roughly speaking, calculate roots, provided we can isolate an interval in which a function is monotone and changes sign.

is positive can be relaxed. This will be done in Section A-3. In Section A-2, we cite an example in which F′(x) changes sign on [a, b].

Example

Let h(x) = x, and assume a (a², b²). Then h(a) < 0 and h(b) > 0. Also, 0 < 2a h′(x2b for all x in [a, b]. By Theorem 3 above, the sequence

whenever x[a, b]. The rate of convergence is given by

In Theorem 3, other iterations could be defined. For example, we could have set xn + l = xn h(xnbe a function in C¹[a, b(x) is positive on [a, bis chosen in such a way that for x [a, bF′(x′(x)h(x) − h′(x(x) < 1, where F(x) = x (x)h(x).

A-2. Newton’s Method

(x) = 1/h′(x) and assume the hypotheses on h of Theorem 3. Assume moreover, h C²[a, b], and calculate that

The iteration defined by

is called Newton’s method. By Theorem 2 and Lemma 2, we obtain convergence of the sequence {xn}, provided |F′(xq < 1 for all x [a, b], and F is a map of [a, b] into itself.

Newton’s method has the following geometrical motivation: Given xn, approximate h by the tangent line at (xn, h(xn)). Choose xndenote the linear function that approximates h (xn+1) = 0 = h(xn) + h′(xn)(xn +1 − xn).

A pleasant feature of Newton’s method is that if the sequence generated by it converges, the rate at which convergence takes place is quadratic. To see this, assume that z is a fixed point of F and write xn − z = F(xn−l) − F(z) = F′n)(xn−1 − z) or

n is between xn−1 and z. Assume {xnz. Expanding h around its root, we get

n n and z. Put Bn = |h″n)h′n)/h′n)| and B = supn Bn. Then |xn − z| < B|xn−1 − z|². Observe that as n , Bn |h″(z)/h′(z)|. A detailed study of Newton’s method in a more general setting will be found in Chapter III, Section C-4.

Example

If Newton’s method is applied to the function x, we obtain the familiar formula

, an interval [a, b] exists such that the function F of Newton’s method is a contractor. Choose a and b such that 0 < a< b², b > (a)/2a and 3a. For example, a /2 and b > 3a.† We shall verify that x [a, b] implies a F(x) = (x)/2x b by showing that the minimum and maximum values of F on [a, b] belong to [a, b].

and F″(x/x. Evidently, the maximum of F must occur at the end points a or b because F′ vanishes only once. But F(a) = (a)/2a < b and F(b) = (b)/2b < b/a² > −3 implies that

Thus, |F′(x)| < 1 on [a, b]. Observe that an easy choice for xand b = max{3a+ 1}, x[a, b].

A-3. Subcontractors

A subcontractor is a map f of a finite interval I into itself such that

  (i) x and y in I imply |f(x) − f(y|x − y|,

 (ii) if x f(x), |f(f(x)) − f(x)| < |f(x) − x|.

Theorem

Assume f is a subcontractor on I. Choose x0 arbitrarily in I and set xn+1 = f(xn). Then {xn} converges to a fixed point of f.

Proof

Deferred to Section B-5.

Lemma

Assume f C¹[a, bf′(x1, and f′(x1 for some x [a, b]. Then

Proof

Since f′ is continuous on [a, b], it has a minimum on [a, b] = I, say at z. Then f′(z) = q < 1. There exists an open interval N in [a, b] such that x N implies f′(x) < (1 + q(N) denote the length of the interval N. Then

Corollary

Assume that h belongs to C¹[a, b], h(a)h(b) < h′(x, and for each subinterval I′ of [a, b], there exists x I′ such that h′(x0. Set xn + 1 = xn h(xn) with x0 arbitrary in [a, b]. Then {xn} converges to a root of h.

PROBLEM

Show by example that h′ may have infinitely many zeros on [a, b], and satisfy the above hypotheses.

Proof of Corollary

Reasoning as in Section A-1, we have for all x in [a, b] that

and a < F(x) < b. Also, |F(x) − F(y|x − y| for all x and y in [a, b]. Choose x0 in I. If x0 is a root, we are done; otherwise, F(xx0. Then

by the lemma above. Hence, by the above theorem, {xnz such that h(z) = 0.

Observe that for subcontractors, we have no information on rates of convergence.

We remark that the hypotheses for each subinterval I′, f′(x0 for some x I′.

I′ can be replaced by the hypotheses that f has a power series representation on [a, b] and f′ 0. Then it follows that f′ can vanish only on a countable set of points, showing that for every I′, f′(x0 for some x I′.

Example

, with [a, b] = [−nπ, nπ], n