Introductory Numerical Analysis

By Anthony J. Pettofrezzo

Geared toward undergraduate mathematics majors, engineering students, and future high school mathematics teachers, this text offers an understanding of the principles involved in numerical analysis. Its main theme is interpolation from the standpoint of finite differences, least squares theory, and harmonic analysis. Additional considerations include the numerical solutions of ordinary differential equations and approximations through Fourier series. Discussions of the relationships between the calculus of finite differences and the calculus of infinitesimals will prove especially important to future teachers of mathematics.
More than seventy worked-out illustrative examples are featured; some include solutions by different methods, showing the relative merits of a variety of approaches. Over 280 multipart exercises range from drill problems to those requiring some degree of ingenuity on the part of the student. Answers are provided to problems with numerical solutions. The only prerequisites are a grasp of differential and integral calculus and some familiarity with determinants. An appendix containing definitions and several theorems from elementary determinant theory is included.

• Language: English
• Publisher: Dover Publications
• Release date: Jun 29, 2012
• ISBN: 9780486152196

Book preview

INDEX

1

Finite Differences

1. INTRODUCTION

A functional relationship between two variables may be expressed in several ways. Among the more common ways is a mathematical formula, a verbal rule, or a set of points (values). Empirical data are usually given in the form of a set of points which may or may not be equally spaced with regard to the independent variable. In elementary mathematics, interpolation is defined as the process of determining intermediate values of a function from a set of points. The Danish mathematician Thiele described this as the art of reading between the lines of a table. In dealing with functions whose analytical representation may or may not be known, we may, with the knowledge of certain values of the independent and dependent variables, substitute or define another analytic function which approximates the original function. This is interpolation in its broadest sense.

The basis of the subject of interpolation lies in two important theorems proved by Weierstrass in 1885 which may be stated as follows:

1. Every function f(x) which is continuous on a closed interval (a, b) can be approximated to any desired degree of accuracy by a polynomial p(x); that is, there exists a p(x) such that

|ƒ(x) − p(x

for a ≤ x ≤ bis any preassigned positive value.

2. Every continuous function ƒ(x) of period 2π can be approximated to any desired degree of accuracy by a trigonometric series T(x) of the form

that is, it is possible to determine a T(x) such that

|ƒ(x) − T(x

for a ≤ x ≤ bis any preassigned positive value.

A basic problem in numerical analysis is to determine, with some criteria in mind, a simple formula representing a functional relationship exhibited by a set of empirical data. For a given set of n + 1 points (x0, y0), (x1, y1), . . . , (xn, yn), one criterion under which we may fit a curve to the data is to require that an approximation function I(x) be determined such that

This is most often the process of interpolation by the methods of finite differences and shall be one of our chief concerns in Chapter 2. The methods used in the calculus of finite differences almost always assume the form of I(x) to be a rational integral function, or polynomial; that is,

I(x) = a + bx + cx² + . . . + kxn.

The calculus of finite differences is a study of the changes in functional values due to finite changes in the independent variable(s).

In this chapter, we shall examine some of the basic definitions, theorems, and relationships for the calculus of finite differences.

2. TABLES OF DIFFERENCES

Given the set of points (x0, y0), (x1, y1), ... , (xn, yn), determined by the relationship y = ƒ(x) such that x1 − x0 = x2 − x= xn − xn−1 = h, some constant, we shall define the quantities y1 − y0, y2 − y1, . . . , yn − yn−1 as the first differences of the function. Symbolically, we shall denote the first differences of y by Δyi, where the subscript i shall be the same as the second member of the difference; that is,

1.1

Differences of the first differences are called second differences and are denoted by Δ²yi; that is,

1.2

In a similar manner, we may define the higher-order differences. In general, the nth-order differences of a function are defined by the formula

1.3

It is possible to express differences of any order in terms of the given values of the function, y0, y1, . . . , yn, by successive substitutions. For example, since

Δ²y0 = Δy1 − Δy0

and

Δyi = yi+1 − yi,

we have

In a similar manner,

In general,

1.4

is the binomial coefficient defined by

1.5

Schematically, we may represent the successive differences of a set of values of a function by means of a diagonal difference table as shown in Table 1.1.

TABLE 1.1

DIAGONAL DIFFERENCE TABLE

Each entry in the body of a diagonal difference table is the difference of the adjacent entries above and below in the column to the left. The entry y0 is called the leading term, and the first terms in each column, Δy0, Δ²y0, ... , Δny0, are called the leading differences. Note that a difference table for n + 1 points has n first differences, n − 1 second differences, n − 2 third differences, etc.

Table 1.2 represents a diagonal difference table in terms of the given values of the function.

TABLE 1.2

EXAMPLE 1. Construct a difference table for the set of points (−3, −25), (−1, 1), (1, 3), (3, 29), and (5, 205).

Solution: Labeling the points (x0, y0), (x1, y1), ... , (x4, y4), respectively, we construct Difference Table A from Table 1.1 and the definition of differences.

Difference Table A

EXAMPLE 2. Express Δ⁴y0 in terms of the successive entries of the table in Example 1 and evaluate.

Solution: From equation (1.4),

Therefore,

This agrees with the results of the difference table in Example 1.

EXERCISES

Construct difference tables for the following sets of points:

(2, 0), (3, 1), (4, 8), (5, 21);

(0, −5), (1, −3), (2, 1), (3, 8), (4, 14);

(−3, 2), (−1, 12), (1, 21), (3, 33);

(2.0, −9), (2.5, 0), (3.0, 3), (3.5, 12), (4.0, 39), (4.5, 96);

(0, 3), (3, 9), (6, 15), (9, 21).

Construct a difference table for the function y = x³ − 2x² + 7 with x0 = 0 and h = 0.5. Consider ten successive points.

Show that:

Find Δ⁵y0 in terms of successive functional values.

Express Δnyk in terms of successive functional values.

Find the next term of the following sequences by extending their difference tables:

1, 4, 10, 20, 35, 56;

−1, 0, 1, 8, 27, 64;

2, 2, 14, 74, 242;

1, 3, 8, 17, 32, 57, 100, 177, 320;

14, 23, 34, 42, 59.

What assumption has been made in each case?

Given the points (2, 1), (3, 6), (4, 13), (5, 22), and (6, 33), find y for x = 0. State the assumption under which the value is determined.

Derive equation (1.4) by means of mathematical induction.

3. SYMBOLIC OPERATORS

In order to obtain Δƒ(x) for any function ƒ(x), we have to change ƒ(x) to ƒ(x + h) and then determine the difference f(x + h) − ƒ(x). The symbol Δ is called the difference operator since it defines this operation of obtaining the difference of two values of a function when applied to that function. The function ƒ(x + h) may be symbolically denoted by Eƒ(x) so that

1.6

defines the operation of taking the first differences of ƒ(x). The symbol E is called the shift operator since it defines the operation of obtaining the value of a function after a shift in the independent variable by some constant h. If we omit the ƒ(x) expressions in equation (1.6), we may write the relationship between the two operators Δ and E as

1.7

or

1.8

Careful note should be made that f(x) has not been factored out. Equations (1.7) and (1.8) merely define an operational relationship.

By repeated applications of the shift operator E to ƒ(x), we have

E²ƒ(x) = E[Eƒ(x)] = Eƒ(x + h) = ƒ(x + 2h);

E³ƒ(x) = E[E²ƒ(x)] = Eƒ(x + 2h) = ƒ(x + 3h).

In general,

1.9

where n is a positive integer. The student should note that the operators Δn and En have been defined only for positive integral values of n. No interpretation of these operators has been made for fractional or negative values of n.

Making use of equations (1.8) and (1.9), we may write

ƒ(x + nh) = Enƒ(x) = (1 + Δ)nƒ(x).

Hence, by means of the binomial expansion of (1 + Δ)n, we have

1.10

In terms of a given set of points (x0, y0), (x1, y1), . . . , (xn, yn), where xi+1 − xi = h, equation (1.6) is interpreted as

1.11

wnere

1.12

Equation (1.9) is interpreted as

1.13

Equation (1.10) gives us an expression for every tabular value of a function in terms of the leading term and leading differences. That is, letting x = x0 and n = i in equation (1.10), we have

1.14

EXAMPLE 1. Find Eƒ(x) where ƒ(x) = 2x³ − x.

Solution: By definition,

Eƒ(x) = ƒ(x + h).

Therefore,

EXAMPLE 2. Find Δƒ(x) where ƒ(x) = x² + 3x − 1.

Solution: By definition,

Δƒ(x) = ƒ(x + h) − ƒ(x).

Therefore,

EXAMPLE 3. Given the set of functional values y0 = −1, y1 = 0, y2 = 5, y3 = 20, express y3 in terms of the leading term and leading differences and evaluate.

Solution: Difference Table B is constructed for the given data.

Difference Table B

The leading term is y0 = −1 and the leading differences are Δy0, = 1, Δ²y0 = 4, and Δ³y0 = 6. Applying equation (1.14),

Substituting the values of the leading term and leading differences,

The result agrees with the given data.

Other important operators will be discussed later in our work on finite differences. However, we now make brief mention of two interesting operators.

It follows from the definition of the shift operator that

Em[Enƒ(x)] = Em+nƒ(x).

Making use of this property, we are able to define the inverse operator E−1. Now,

Hence,

1.15

and, in general,

1.16

A second operator of interest is the Backward difference operator ∇ defined by

1.17

Making use of equations (1.15) and (1.17), we may write

1.18

Higher-order backward differences are defined in an analogous manner to higher-order forward differences. Hence, we may show that

1.19

EXERCISES

Find the following where the unit of increment for the independent variable is h = 1:

Δx³;

Δ³ax³;

Δax;

Δnax;

Δex;

Δx!;

Δ sin x;

Δx3x;

Ex⁴;

E²x!;

E cos x;

Enex;

∇x²;

E−13x²;

E−nx.

Find Δ²ƒ(x) for ƒ(x) = ax² + bx + c with h = 2.

for x = 9 with h = 1.

Find E³(ax² + bx + c) using equation (1.10) with h = 1.

for k < r with h = 1.

Consider a set of points (t0, y0), (t1, y1), . . . , (tn, yn), where ti+1