## Read an Excerpt

#### ANALYSIS OF NUMERICAL METHODS

**By EUGENE ISAACSON, HERBERT BISHOP KELLER**

**Dover Publications, Inc.**

**Copyright © 1966 John Wiley & Sons**

All rights reserved.

ISBN: 978-0-486-13798-8

All rights reserved.

ISBN: 978-0-486-13798-8

#### Contents

Chapter 1 Norms, Arithmetic, and Well-Posed Computations,Chapter 2 Numerical Solution of Linear Systems and Matrix Inversion,

Chapter 3 Iterative Solutions of Non-Linear Equations,

Chapter 4 Computation of Eigenvalues and Eigenvectors,

Chapter 5 Basic Theory of Polynomial Approximation,

Chapter 6 Differences, Interpolation Polynomials, and Approximate Differentiation,

Chapter 7 Numerical Integration,

Chapter 8 Numerical Solution of Ordinary Differential Equations,

Chapter 9 Difference Methods for Partial Differential Equations,

Bibliography,

Index,

CHAPTER 1

**Norms, Arithmetic, and Well-Posed Computations**

**0. INTRODUCTION**

In this chapter, we treat three topics that are generally useful for the analysis of the various numerical methods studied throughout the book. In **Section 1**, we give the elements of the theory of *norms* of finite dimensional vectors and matrices. This subject properly belongs to the field of *linear algebra*. In later chapters, we may occasionally employ the notion of the norm of a function. This is a straightforward extension of the notion of a vector norm to the infinite-dimensional case. On the other hand, we shall not introduce the corresponding natural generalization, i.e., the notion of the norm of a linear transformation that acts on a space of functions. Such ideas are dealt with in *functional analysis*, and might profitably be used in a more sophisticated study of numerical methods.

We study briefly, in **Section 2**, the practical problem of the effect of rounding errors on the basic operations of arithmetic. Except for calculalations involving only exactinteger arithmetic, rounding errors are invariably present in any computation. A most important feature of the later analysis of numerical methods is the incorporation of a treatment of the effects of such rounding errors.

Finally, in **Section 3**, we describe the computational problems that are 'reasonable' in some general sense. In effect, a numerical method which produces a solution insensitive to small changes in data or to rounding errors is said to yield a *well-posed computation*. How to determine the sensitivity of a numerical procedure is dealt with in special cases throughout the book. We indicate heuristically that any *convergent* algorithm is a well-posed computation.

**1. NORMS OF VECTORS AND MATRICES**

We assume that the reader is familiar with the basic theory of linear algebra, not necessarily in its abstract setting, but at least with specific reference to finite-dimensional linear vector spaces over the field of complex scalars. By 'basic theory' we of course include: the theory of linear systems of equations, some elementary theory of determinants, and the theory of matrices or linear transformations to about the Jordan normal form. We hardly employ the Jordan form in the present study. In fact a much weaker result can frequently be used in its place (when the divisor theory or invariant subspaces are not actually involved). This result is all too frequently skipped in basic linear algebra courses, so we present it as

**THEOREM 1.***For any square matrix A of order n there exists a non- singular matrix P, of order n, such that*

*B = P-1AP*

*is upper triangular and has the eigenvalues of A, say λj [equivalent to] λj(A), j* = 1, 2, ..., *n, on the principal diagonal (i.e., any square matrix is equivalent to a triangular matrix).*

*Proof.* We sketch the proof of this result. The reader should have no difficulty in completing the proof in detail.

Let λ1 be an eigenvalue of *A* with corresponding eigenvector **u**1. Then pick a basis for the *n*-dimensional complex vector space, *Cn*, with **u**1 as the first such vector. Let the independent basis vectors be the columns of a non-singular matrix *P*1, which then determines the transformation to the new basis. In this new basis the transformation determined by *A* is given by *B*1 ? *P*1-1 and since *A***u**1 = λ1**u**1,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where *A*2 is some matrix of order *n* - 1.

The characteristic polynomial of *B*1 is clearly

det (λ*In - B*1 = (λ - λ1) det (λ*In-i - A*2),

where *In* is the identity matrix of order *n*. Now pick some eigenvalue λ2 of *A*2 and corresponding (*n* - 1)-dimensional eigenvector, **v**2; i.e.,

*A*2**v**2 = λ2**v**2.

With this vector we define the independent *n*-dimensional vectorts

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Note that with the scalar α = α1ν12 + α2ν22 + ... + α*n*- 1ν*n*-1, 2

*B*1[??]1 = λ1[??]1, *B*1[??]2 = λ2[??]2 + α[??]1,

and thus if we set **u**1 = *P*1[??]1, **u**2 = *P*1[??]2, then

*A***u**1 = λ1**u**1, *A***u**2 = λ2**u**2 + α**u**1.

Now we introduce a new basis of *Cn* with the first two vectors being and **u**1 and **u**2. The non- singular matrix *P*2 which determines this change of basis has **u**1 and **u**2 as its first two columns; and the original linear transformation in the new basis has the representation

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where *A*3 is some matrix of order *n* - 2.

The theorem clearly follows by the above procedure; a formal inductive proof could be given.

It is easy to prove the related stronger result of Schur stated in **Theorem 2.4** of **Chapter 4** (see **Problem 2.13** (b) of **Chapter 4**). We turn now to the basic content of this section, which is concerned with the generalization of the concept of distance in *n*-dimensional linear vector spaces.

The 'distance' between a vector and the null vector, i.e., the origin, is a measure of the 'size' or 'length' of the vector. This generalized notion of distance or size is called a *norm*. In particular, all such generalizations are required to have the following properties:

(0) To each vector **x** in the linear space, [??], say, a unique real number is assigned; this number, denoted by ||**x**|| or *N*(**x**), is called the norm of **x** iff:

(i)||**x**|| ̥ 0 for all **x** [member of] [??] and ||**x**|| = 0 iff **x** = **o**; where o denotes the *zero vector* (if [??] *Cn*, then *oi* = 0);

(ii)||α**x**|| = ||α|| · ||**x**|| for all scalars α and all **x** [member of] [??];

(iii) ||**x** + **y**|| ≤ ||**x**|| + ||**y**||, the *triangle inequality*, for all **x, y** [member of] [??].

Some examples of norms in the complex *n*-dimensional space *Cn* are

(1a) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

(1b) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

(1c) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

(1d) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

It is an easy exercise for the reader to justify the use of the notation in (**1d**) by verifying that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The norm, ||·||2, is frequently called the *Euclidean norm* as it is just the formula for distance in ordinary three-dimensional Euclidean space extended to dimension n. The norm, ||·||∞, is called the *maximum norm* or occasionally the *uniform norm*. In general, ||·||*p*, for *p* ≥ 1 is termed the *p-norm*.

To verify that (**1**) actually defines norms, we observe that conditions (0), (i), and (ii) are trivially satisfied. Only the triangle inequality, (iii), offers any difficulty. However,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

so (**1a**) and (**1d**) define norms.

The proof of (iii) for (**1b**), the Euclidean norm, is based on the well known Cauchy-Schwarz inequality which states that

(2) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

To prove this basic result, let |**x**| and |**y**| be the *n*-dimensional vectors with components |*xj*| and |*yj*|, *j* = 1, 2, ..., *n*, respectively. Then for any real scalar, [xi],

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

But since the real quadratic polynomial in [xi] above does not change sign its discriminant must be non-positive; i.e.,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

However, we note that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and (**2**) follows from the above pair of inequalities.

Now we form

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

An application of the Cauchy-Schwarz inequality yields finally

*N*2(**x** + **y**) ≤ *N*2(**x**) + *N*2(**y**)

and so the Euclidean norm also satisfies the triangle inequality.

The statement that

**(3) Np(x + y) ≤ Np(x) + Np(y), p ≥ 1,**

is know as *Minkowski's inequality*. We do not derive it here as general *p*-norms will not be employed further. (A proof of (**3**) can be found in most advanced calculus texts.)

We can show quite generally that all vector norms are continuous functions in *Cn*. That is,

**LEMMA 1.***Every vector norm, N( x), is a continuous function of x1, x2, ..., xn, the components of x.*

*Proof.* For any vectors **x** and δ we have by (iii)

*N*(**x** + δ) ≤ *N*(**x**) + *N*(δ),

so that

*N*(**x** + δ) - *N*(**x**) ≤ *N*(δ).

On the other hand, by (ii) and (iii),

*N*(x) = *N*(x + [de;ta] - [delta) ≤ *N*(x + δ) + *N*([deta])

so that

*-N*(δ) ≤ *N*(**x** + δ) - *N*(**x**).

Thus, in general

|*N*(**x** + δ) - *N*(**x**)| ≤ *N*(δ).

With the unit vectors {**e***k*}, any δ has the representation

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Using (ii) and (iii) repeatedly implies

(4a) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where

(4b) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Using this result in the previous inequality yields, for any ε > 0 and all δ with *N*∞(δ) ≤ ε/*M*,

|*N*(**x** + δ) - *N*(**x**)| ≤ ε.

This is essentially the definition of continuity for a function of the *n* variables *x*1, x2, ..., *xn*.

See **Problem 6** for a mild generalization.

Now we can show that all vector norms are equivalent in the sense of

**THEOREM 2.***For each pair of vector norms, say N( x) and N'(x), there exist positive constants m and M such that for all x [member of] Cn:*

*mN'* (**x**) ≤ *N*(**x**) ≤ *MN'*(**x**).

*Proof.* The proof need only be given when one of the norms is *N*∞, since *N* and *N'* are equivalent if they are each equivalent to *N*∞. Let *S* [subset] *Cn* be defined by

*S* [equivalent to] {**x** | *N*∞(**x**) = 1, **x** [member of] *Cn*}

(this is frequently called the surface of the unit ball in *Cn*). *S* is a closed bounded set of points. Then since *N*(**x**) is a continuous function (see **Lemma 1**), we conclude by a theorem of Weierstrass that *N*(**x**) attains its minimum and its maximum on *S* at some points of *S*. That is, for some **x**0 [member of] *S* and **x**1 [member of] *S*

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

or

0 < *N*(**x**0) ≤ *N*(**x**) ≤ *N*(**x**1) < ∞

for all **x** [member of] *S*.

*(Continues...)*

Excerpted fromANALYSIS OF NUMERICAL METHODSbyEUGENE ISAACSON, HERBERT BISHOP KELLER. Copyright © 1966 John Wiley & Sons. Excerpted by permission of Dover Publications, Inc..

All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.

Excerpts are provided by Dial-A-Book Inc. solely for the personal use of visitors to this web site.