CHAPTER 19

Numerics in General

Numeric analysis or briefly numerics has a distinct flavor that is different from basic calculus, from solving ODEs algebraically, or from other (nonnumeric) areas. Whereas in calculus and in ODEs there were very few choices on how to solve the problem and your answer was an algebraic answer, in numerics you have many more choices and your answers are given as tables of values (numbers) or graphs. You have to make judicous choices as to what numeric method or algorithm you want to use, how accurate you need your result to be, with what value (starting value) do you want to begin your computation, and others. This chapter is designed to provide a good transition from the algebraic type of mathematics to the numeric type of mathematics.

We begin with the general concepts such as floating point, roundoff errors, and general numeric errors and their propagation. This is followed in Sec. 19.2 by the important topic of solving equations of the type f(x) = 0 by various numeric methods, including the famous Newton method. Section 19.3 introduces interpolation methods. These are methods that construct new (unknown) function values from known function values. The knowledge gained in Sec. 19.3 is applied to spline interpolation (Sec. 19.4) and is useful for understanding numeric integration and differentiation covered in the last section.

Numerics provides an invaluable extension to the knowledge base of the problem-solving engineer. Many problems have no solution formula (think of a complicated integral or a polynomial of high degree or the interpolation of values obtained by measurements). In other cases a complicated solution formula may exist but may be practically useless. It is for these kinds of problems that a numerical method may generate a good answer. Thus, it is very important that the applied mathematician, engineer, physicist, or scientist becomes familiar with the essentials of numerics and its ideas, such as estimation of errors, order of convergence, numerical methods expressed in algorithms, and is also informed about the important numeric methods.

Prerequisite: Elementary calculus.

References and Answers to Problems: App. 1 Part E, App. 2.

19.1 Introduction

As an engineer or physicist you may deal with problems in elasticity and need to solve an equation such as x cosh x = 1 or a more difficult problem of finding the roots of a higher order polynomial. Or you encounter an integral such as

[see App. 3, formula (35)] that you cannot solve by elementary calculus. Such problems, which are difficult or impossible to solve algebraically, arise frequently in applications. They call for numeric methods, that is, systematic methods that are suitable for solving, numerically, the problems on computers or calculators. Such solutions result in tables of numbers, graphical representation (figures), or both. Typical numeric methods are iterative in nature and, for a well-choosen problem and a good starting value, will frequently converge to a desired answer. The evolution from a given problem that you observed in an experimental lab or in an industrial setting (in engineering, physics, biology, chemistry, economics, etc.) to an approximation suitable for numerics to a final answer usually requires the following steps.

1. Modeling. We set up a mathematical model of our problem, such as an integral, a system of equations, or a differential equation.
2. Choosing a numeric method and parameters (e.g., step size), perhaps with a preliminary error estimation.
3. Programming. We use the algorithm to write a corresponding program in a CAS, such as Maple, Mathematica, Matlab, or Mathcad, or, say, in Java, C or C⁺⁺, or FORTRAN, selecting suitable routines from a software system as needed.
4. Doing the computation.
5. Interpreting the results in physical or other terms, also deciding to rerun if further results are needed.

Steps 1 and 2 are related. A slight change of the model may often admit of a more efficient method. To choose methods, we must first get to know them. Chapters 19–21 contain efficient algorithms for the most important classes of problems occurring frequently in practice.

In Step 3 the program consists of the given data and a sequence of instructions to be executed by the computer in a certain order for producing the answer in numeric or graphic form.

To create a good understanding of the nature of numeric work, we continue in this section with some simple general remarks.

Floating-Point Form of Numbers

We know that in decimal notation, every real number is represented by a finite or an infinite sequence of decimal digits. Now most computers have two ways of representing numbers, called fixed point and floating point. In a fixed-point system all numbers are given with a fixed number of decimals after the decimal point; for example, numbers given with 3 decimals are 62.358, 0.014, 1.000. In a text we would write, say, 3 decimals as 3D. Fixed-point representations are impractical in most scientific computations because of their limited range (explain!) and will not concern us.

In a floating-point system we write, for instance,

or sometimes also

We see that in this system the number of significant digits is kept fixed, whereas the decimal point is “floating.” Here, a significant digit of a number c is any given digit of c, except possibly for zeros to the left of the first nonzero digit; these zeros serve only to fix the position of the decimal point. (Thus any other zero is a significant digit of c.) For instance,

all have 5 significant digits. In a text we indicate, say, 5 significant digits, by 5S.

The use of exponents permits us to represent very large and very small numbers. Indeed, theoretically any nonzero number a can be written as

On modern computers, which use binary (base 2) numbers, m is limited to k binary digits (e.g., k = 8) and n is limited (see below), giving representations (for finitely many numbers only!)

These numbers are called k-digit binary machine numbers. Their fractional part m (or ) is called the mantissa. This is not identical with “mantissa” as used for logarithms. n is called the exponent of .

It is important to realize that there are only finitely many machine numbers and that they become less and less “dense” with increasing a. For instance, there are as many numbers between 2 and 4 as there are between 1024 and 2048. Why?

The smallest positive machine number eps with 1 + eps > 1 is called the machine accuracy. It is important to realize that there are no numbers in the intervals [1, 1 + eps], [2, 2 + 2 · eps], …, [1024, 1024 + 1024 · eps], …. This means that, if the mathematical answer to a computation would be 1024 + 1024 · eps/2, the computer result will be either 1024 or 1024 · eps so it is impossible to achieve greater accuracy.

Underflow and Overflow. The range of exponents that a typical computer can handle is very large. The IEEE (Institute of Electrical and Electronic Engineers) floating-point standard for single precision is from 2⁻¹²⁶ to 2¹²⁸ (1.175 × 10⁻³⁸ to 3.403 × 10³⁸) and for double precision it is from 2⁻¹⁰²² to 2¹⁰²⁴ (2.225 × 10⁻³⁰⁸ to 1.798 × 10³⁰⁸).

As a minor technicality, to avoid storing a minus in the exponent, the ranges are shifted from [− 126. 128] by adding 126 (for double precision 1022). Note that shifted exponents of 255 and 1047 are used for some special cases such as representing infinity.

If, in a computation a number outside that range occurs, this is called underflow when the number is smaller and overflow when it is larger. In the case of underflow, the result is usually set to zero and computation continues. Overflow might cause the computer to halt. Standard codes (by IMSL, NAG, etc.) are written to avoid overflow. Error messages on overflow may then indicate programming errors (incorrect input data, etc.). From here on, we will be discussing the decimal results that we obtain from our computations.

Roundoff

An error is caused by chopping (= discarding all digits from some decimal on) or rounding. This error is called roundoff error, regardless of whether we chop or round. The rule for rounding off a number to k decimals is as follows. (The rule for rounding off to k significant digits is the same, with “decimal” replaced by “significant digit.”)

Roundoff Rule. To round a number x to k decimals, and 5 · 10^−(k+1) to x and chop the digits after the (k + 1)st digit.

Chopping is not recommended because the corresponding error can be larger than that in rounding. (Nevertheless, some computers use it because it is simpler and faster. On the other hand, some computers and calculators improve accuracy of results by doing intermediate calculations using one or more extra digits, called guarding digits.)

Error in Rounding. Let = fl (a) in (2) be the floating-point computer approximation of a in (1) obtained by rounding, where fl suggests floating. Then the roundoff rule gives (by dropping exponents) Since |m| 0.1, this implies (when a ≠ 0)

The right side is called the rounding unit. If we write = a(1 + δ), we have by algebra ( − a)/a = δ, hence |δ| u by (3). This shows that the rounding unit u is an error bound in rounding.

Rounding errors may ruin a computation completely, even a small computation. In general, these errors become the more dangerous the more arithmetic operations (perhaps several millions!) we have to perform. It is therefore important to analyze computational programs for expected rounding errors and to find an arrangement of the computations such that the effect of rounding errors is as small as possible.

As mentioned, the arithmetic in a computer is not exact and causes further errors; however, these will not be relevant to our discussion.

Accuracy in Tables. Although available software has rendered various tables of function values superfluous, some tables (of higher functions, of coefficients of integration formulas, etc.) will still remain in occasional use. If a table shows k significant digits, it is conventionally assumed that any value in the table deviates from the exact value a by at most unit of the kth digit.

Loss of Significant Digits

This means that a result of a calculation has fewer correct digits than the numbers from which it was obtained. This happens if we subtract two numbers of about the same size, for example, 0.1439 − 0.1426 (“subtractive cancellation”). It may occur in simple problems, but it can be avoided in most cases by simple changes of the algorithm—if one is aware of it! Let us illustrate this with the following basic problem.

Errors of Numeric Results

Final results of computations of unknown quantities generally are approximations; that is, they are not exact but involve errors. Such an error may result from a combination of the following effects. Roundoff errors result from rounding, as discussed above. Experimental errors are errors of given data (probably arising from measurements). Truncating errors result from truncating (prematurely breaking off), for instance, if we replace a Taylor series with the sum of its first few terms. These errors depend on the computational method used and must be dealt with individually for each method. [“Truncating” is sometimes used as a term for chopping off (see before), a terminology that is not recommended.]

Formulas for Errors. If is an approximate value of a quantity whose exact value is a, we call the difference

the error of . Hence

For instance, if = 10.5 is an approximation of a = 10.2, its error is = −0.3. The error of an approximation = 1.60 of a = 1.82 is = 0.22.

The relative error _r of is defined by

This looks useless because a is unknown. But if || is much less than ||, then we can use instead of a and get

This still looks problematic because is unknown—if it were known, we could get from (6) and we would be done. But what one often can obtain in practice is an error bound for , that is, a number β such that

This tells us how far away from our computed the unknown a can at most lie. Similarly, for the relative error, an error bound is a number β_r such that

Error Propagation

This is an important matter. It refers to how errors at the beginning and in later steps (roundoff, for example) propagate into the computation and affect accuracy, sometimes very drastically. We state here what happens to error bounds. Namely, bounds for the error add under addition and subtraction, whereas bounds for the relative error add under multiplication and division. You do well to keep this in mind.

Basic Error Principle

Every numeric method should be accompanied by an error estimate. If such a formula is lacking, is extremely complicated, or is impractical because it involves information (for instance, on derivatives) that is not available, the following may help.

Error Estimation by Comparison. Do a calculation twice with different accuracy. Regard the difference of the results as a (perhaps crude) estimate of the error ₁ of the inferior result Indeed, by formula (4*). This implies because is generally more accurate than so that |₂| is small compared to |₁|.

Algorithm. Stability

Numeric methods can be formulated as algorithms. An algorithm is a step-by-step procedure that states a numeric method in a form (a “pseudocode”) understandable to humans. (See Table 19.1 to see what an algorithm looks like.) The algorithm is then used to write a program in a programming language that the computer can understand so that it can execute the numeric method. Important algorithms follow in the next sections. For routine tasks your CAS or some other software system may contain programs that you can use or include as parts of larger programs of your own.

Stability. To be useful, an algorithm should be stable; that is, small changes in the initial data should cause only small changes in the final results. However, if small changes in the initial data can produce large changes in the final results, we call the algorithm unstable.

This “numeric instability,” which in most cases can be avoided by choosing a better algorithm, must be distinguished from “mathematical instability” of a problem, which is called “ill-conditioning,” a concept we discuss in the next section.

Some algorithms are stable only for certain initial data, so that one must be careful in such a case.

19.2 Solution of Equations by Iteration

For each of the remaining sections of this chapter, we select basic kinds of problems and discuss numeric methods on how to solve them. The reader will learn about a variety of important problems and become familiar with ways of thinking in numerical analysis.

Perhaps the easiest conceptual problem is to find solutions of a single equation

where f is a given function. A solution of (1) is a number x = s such that f(s) = 0. Here, s suggests “solution,” but we shall also use other letters.

It is interesting to note that the task of solving (1) is a question made for numeric algorithms, as in general there are no direct formulas, except in a few simple cases.

Examples of single equations are x³ + x = 1, sin x = 0.5x, tan x = x, cosh x = sec x, cosh x cos x = −1, which can all be written in the form of (1). The first of the five equations is an algebraic equation because the corresponding f is a polynomial. In this case the solutions are called roots of the equation and the solution process is called finding roots. The other equations are transcendental equations because they involve transcendental functions.

There are a very large number of applications in engineering, where we have to solve a single equation (1). You have seen such applications when solving characteristic equations in Chaps. 2, 4, and 8; partial fractions in Chap. 6; residue integration in Chap. 16, finding eigenvalues in Chap. 12, and finding zeros of Bessel functions, also in Chap. 12. Moreover, methods of finding roots are very important in areas outside of classical engineering. For example, in finance, the problem of determining how much a bond is worth amounts to solving an algebraic equation.

To solve (1) when there is no formula for the exact solution available, we can use an approximation method, such as an iteration method. This is a method in which we start from an initial guess x₀ (which may be poor) and compute step by step (in general better and better) approximations x₁, x₂, … of an unknown solution of (1). We discuss three such methods that are of particular practical importance and mention two others in the problem set.

It is very important that the reader understand these methods and their underlying ideas. The reader will then be able to select judiciously the appropriate software from among different software packages that employ variations of such methods and not just treat the software programs as “black boxes.”

In general, iteration methods are easy to program because the computational operations are the same in each step—just the data change from step to step—and, more importantly, if in a concrete case a method converges, it is stable in general (see Sec. 19.1).

Fixed-Point Iteration for Solving Equations f(x) = 0

Note: Our present use of the word “fixed point” has absolutely nothing to do with that in the last section.

By some algebraic steps we transform (1) into the form

Then we choose an x₀ and compute x₁ = g(x₀), x₂ = g(x₁), and in general

A solution of (2) is called a fixed point of g, motivating the name of the method. This is a solution of (1), since from x = g(x) we can return to the original form f(x) = 0. From (1) we may get several different forms of (2). The behavior of corresponding iterative sequences x₀, x₁, … may differ, in particular, with respect to their speed of convergence. Indeed, some of them may not converge at all. Let us illustrate these facts with a simple example.

An iteration process defined by (3) is called convergent for an x₀ if the corresponding sequence x₀, x₁, … is convergent.

A sufficient condition for convergence is given in the following theorem, which has various practical applications.

We mention that a function g satisfying the condition in Theorem 1 is called a contraction because |g(x) − g(v)| K|x − v|, where K < 1. Furthermore, K gives information on the speed of convergence. For instance, if K = 0.5, then the accuracy increases by at least 2 digits in only 7 steps because 0.5⁷ < 0.01.

Fig. 427. Iteration in Example 2

Fig. 428. Newton's method

Newton's Method for Solving Equations f(x) = 0

Newton's method, also known as Newton–Raphson's method,¹ is another iteration method for solving equations f(x) = 0 where f is assumed to have a continuous derivative f′. The method is commonly used because of its simplicity and great speed.

The underlying idea is that we approximate the graph of f by suitable tangents. Using an approximate value x₀ obtained from the graph of f, we let x₁ be the point of intersection of the x-axis and the tangent to the curve of f at x₀ (see Fig. 428). Then

In the second step we compute x₂ = x₁ − f(x₁)/f′(x₁), in the third step x₃ from x₂ again by the same formula, and so on. We thus have the algorithm shown in Table 19.1. Formula (5) in this algorithm can also be obtained if we algebraically solve Taylor's formula

Table 19.1 Newton's Method for Solving Equations f(x) = 0

If it happens that f′(x_n) = 0 for some n (see line 2 of the algorithm), then try another starting value x₀. Line 3 is the heart of Newton's method.

The inequality in line 4 is a termination criterion. If the sequence of the x_n converges and the criterion holds, we have reached the desired accuracy and stop. Note that this is just a form of the relative error test. It ensures that the result has the desired number of significant digits. If |x_n+1| = 0, the condition is satisfied if and only if x_n+1 = x_n = 0, otherwise |x_n+1 − x_n| must be sufficiently small. The factor |x_n+1| is needed in the case of zeros of very small (or very large) absolute value because of the high density (or of the scarcity) of machine numbers for those x.

Line 5 gives another termination criterion and is needed because Newton's method may diverge or, due to a poor choice of x₀, may not reach the desired accuracy by a reasonable number of iterations. Then we may try another x₀. If f(x) = 0 has more than one solution, different choices of x₀ may produce different solutions. Also, an iterative sequence may sometimes converge to a solution different from the expected one.

Order of an Iteration Method. Speed of Convergence

The quality of an iteration method may be characterized by the speed of convergence, as follows.

Let x_n+1 = g(x_n) define an iteration method, and let x_n approximate a solution s of x = g(x). Then x_n = s − _n, where _n is the error of x_n. Suppose that g is differentiable a number of times, so that the Taylor formula gives

The exponent of _n in the first nonvanishing term after g(s) is called the order of the iteration process defined by g. The order measures the speed of convergence.

To see this, subtract g(s) = s on both sides of (6). Then on the left you get x_n+1 − s = −_n+1, where _n+1 is the error of x_n+1. And on the right the remaining expression equals approximately its first nonzero term because |_n| is small in the case of convergence. Thus

Thus if _n = 10^−k in some step, then for second order, _n+1 = c · (10^−k)² = c · 10^−2k, so that the number of significant digits is about doubled in each step.

Convergence of Newton's Method

In Newton's method, g(x) = x − f(x)/f′(x). By differentiation,

Since f(s) = 0, this shows that also g′(s) = 0. Hence Newton's method is at least of second order. If we differentiate again and set x = s, we find that

which will not be zero in general. This proves

Comments. For Newton's method, (7b) becomes, by (8*)

For the rapid convergence of the method indicated in Theorem 2 it is important that s be a simple zero of f(x) (thus f′(s) ≠ 0) and that x₀ be close to s, because in Taylor's formula we took only the linear term [see (5*)], assuming the quadratic term to be negligibly small. (With a bad x₀ the method may even diverge!)

Difficulties in Newton's Method. Difficulties may arise if |f′(x)| is very small near a solution s of f(x) = 0. For instance, let s be a zero of f(x) of second or higher order. Then Newton's method converges only linearly, as is shown by an application of l'Hopital's rule to (8). Geometrically, small |f′(x)| means that the tangent of f(x) near s almost coincides with the x-axis (so that double precision may be needed to get f(x) and f′(x) accurately enough). Then for values far away from s we can still have small function values

In this case we call the equation f(x) = 0 ill-conditioned. is called the residual of f(x) = 0 at . Thus a small residual guarantees a small error of only if the equation is not ill-conditioned.

Secant Method for Solving f(x) = 0

Newton's method is very powerful but has the disadvantage that the derivative f′ may sometimes be a far more difficult expression than f itself and its evaluation therefore computationally expensive. This situation suggests the idea of replacing the derivative with the difference quotient

Then instead of (5) we have the formula of the popular secant method

Fig. 429. Secant method

Geometrically, we intersect the x-axis at x_n+1 with the secant of f(x) passing through P_n−1 and P_n in Fig. 429. We need two starting values x₀ and x₁. Evaluation of derivatives is now avoided. It can be shown that convergence is superlinear (that is, more rapid than linear, |_n+1| ≈ const · |_n|^1.62; see [E5] in App. 1), almost quadratic like Newton's method. The algorithm is similar to that of Newton's method, as the student may show.

because this may lead to loss of significant digits if x_n and x_n−1 are about equal. (Can you see this from the formula?)

Summary of Methods. The methods for computing solutions s of f(x) = 0 with given continuous (or differentiable) f(x) start with an initial approximation x₀ of s and generate a sequence x₁, x₂, … by iteration. Fixed-point methods solve f(x) = 0 written as x = g(x), so that s is a fixed point of g, that is, s = g(s). For g(x) = x − f(x)/f′(x) this is Newton's method, which, for good x₀ and simple zeros, converges quadratically (and for multiple zeros linearly). From Newton's method the secant method follows by replacing f′(x) by a difference quotient. The bisection method and the method of false position in Problem Set 19.2 always converge, but often slowly.

19.3 Interpolation

We are given the values of a function f(x) at different points x₀, x₁, …, x_n. We want to find approximate values of the function f(x) for “new” x’s that lie between these points for which the function values are given. This process is called interpolation. The student should pay close attention to this section as interpolation forms the underlying foundation for both Secs. 19.4 and 19.5. Indeed, interpolation allows us to develop formulas for numeric integration and differentiation as shown in Sec. 19.5.

Continuing our discussion, we write these given values of a function f in the form

or as ordered pairs

Where do these given function values come from? They may come from a “mathematical” function, such as a logarithm or a Bessel function. More frequently, they may be measured or automatically recorded values of an “empirical” function, such as air resistance of a car or an airplane at different speeds. Other examples of functions that are “empirical” are the yield of a chemical process at different temperatures or the size of the U.S. population as it appears from censuses taken at 10-year intervals.

A standard idea in interpolation now is to find a polynomial p_n(x) of degree n (or less) that assumes the given values; thus

We call this p_n an interpolation polynomial and x₀, …, x_n the nodes. And if f(x) is a mathematical function, we call p_n an approximation of f (or a polynomial approximation, because there are other kinds of approximations, as we shall see later). We use p_n to get (approximate) values of f for x’s between x₀ and x_n (“interpolation”) or sometimes outside this interval x₀ x x_n (“extrapolation”).

Motivation. Polynomials are convenient to work with because we can readily differentiate and integrate them, again obtaining polynomials. Moreover, they approximate continuous functions with any desired accuracy. That is, for any continuous f(x) on an interval J: a x b and error bound β > 0, there is a polynomial p_n(x) (of sufficiently high degree n) such that

This is the famous Weierstrass approximation theorem (for a proof see Ref. [GenRef7], App. 1).

Existence and Uniqueness. Note that the interpolation polynomial p_n satisfying (1) for given data exists and we shall give formulas for it below. Furthermore, p_n is unique: Indeed, if another polynomial q_n also satisfies q_n(x₀) = f₀, …, q_n(x_n) = f_n, then p_n(x) − q_n(x) = 0 at x₀, …, x_n, but a polynomial p_n − q_n of degree n (or less) with n + 1 roots must be identically zero, as we know from algebra; thus p_n(x) = q_n(x) for all x, which means uniqueness.

How Do We Find p_n? We shall explain several standard methods that give us p_n. By the uniqueness proof above, we know that, for given data, the different methods must give us the same polynomial. However, the polynomials may be expressed in different forms suitable for different purposes.

Lagrange Interpolation

Given (x₀, f₀), (x₁, f₁), …, (x_n, f_n) with arbitrarily spaced x_j, Lagrange had the idea of multiplying each f_j by a polynomial that is 1 at x_j and 0 at the other n nodes and then taking the sum of these n + 1 polynomials. Clearly, this gives the unique interpolation polynomial of degree n or less. Beginning with the simplest case, let us see how this works.

Linear interpolation is interpolation by the straight line through (x₀, f₀), (x₁, f₁); see Fig. 431. Thus the linear Lagrange polynomial p₁ is a sum p₁ = L₀f₀ + L₁f₁ with L₀ the linear polynomial that is 1 at x₀ and 0 at x₁; similarly, L₁ is 0 at x₀ and 1 at x₁. Obviously,

This gives the linear Lagrange polynomial

Fig. 431. Linear Interpolation

Fig. 432. L₀ and L₁ in Example 1

Quadratic interpolation is interpolation of given (x₀, f₀), (x₁, f₁), (x₂, f₂) by a second-degree polynomial p₂(x), which by Lagrange's idea is

with L₀(x₀) = 1, L₁(x₁) = 1, L₂(x₂) = 1, and L₀(x₁) = L₀(x₂) = 0, etc. We claim that

How did we get this? Well, the numerator makes L_k(x_j) = 0 if j ≠ k. And the denominator makes L_k(x_k) = 1 because it equals the numerator at x = x_k.

Fig. 433. L₀, L₁, L₂ in Example 2

General Lagrange Interpolation Polynomial. For general n we obtain

where L_k(x_k) = 1 and L_k is 0 at the other nodes, and the L_k are independent of the function f to be interpolated. We get (4a) if we take

We can easily see that p_n(x_k) = f_k. Indeed, inspection of (4b) shows that l_k(x_j) = 0 if j ≠ k, so that for x = x_k, the sum in (4a) reduces to the single term (l_k(x_k)/l_k(x_k))f_k = f_k.

Error Estimate. If f is itself a polynomial of degree n (or less), it must coincide with p_n because the n + 1 data (x₀, f₀), …, (x_n, f_n) determine a polynomial uniquely, so the error is zero. Now the special f has its (n + 1)st derivative identically zero. This makes it plausible that for a general f its (n + 1)st derivative f^{(n + 1)} should measure the error

It can be shown that this is true if f^{(n + 1)} exists and is continuous. Then, with a suitable t between x₀ and x_n (or between x₀, x_n, and x if we extrapolate),

Thus |_n(x)| is 0 at the nodes and small near them, because of continuity. The product (x − x₀)…(x − x_n) is large for x away from the nodes. This makes extrapolation risky. And interpolation at an x will be best if we choose nodes on both sides of that x. Also, we get error bounds by taking the smallest and the largest value of f^{(n + 1)}(t) in (5) on the interval x₀ t x_n (or on the interval also containing x if we extrapolate).

Most importantly, since p_n is unique, as we have shown, we have

Practical error estimate. If the derivative in (5) is difficult or impossible to obtain, apply the Error Principle (Sec. 19.1), that is, take another node and the Lagrange polynomial p_{n + 1}(x) and regard p_{n + 1}(x) − p_n(x) as a (crude) error estimate for p_n(x).

Newton's Divided Difference Interpolation

For given data (x₀, f₀), …, (x_n, f_n) the interpolation polynomial p_n(x) satisfying (1) is unique, as we have shown. But for different purposes we may use p_n(x) in different forms. Lagrange's form just discussed is useful for deriving formulas in numeric differentiation (approximation formulas for derivatives) and integration (Sec. 19.5).

Practically more important are Newton's forms of p_n(x), which we shall also use for solving ODEs (in Sec. 21.2). They involve fewer arithmetic operations than Lagrange's form. Moreover, it often happens that we have to increase the degree n to reach a required accuracy. Then in Newton's forms we can use all the previous work and just add another term, a possibility without counterpart for Lagrange's form. This also simplifies the application of the Error Principle (used in Example 3 for Lagrange). The details of these ideas are as follows.

Let p_n−1(x) be the (n − 1)st Newton polynomial (whose form we shall determine); thus p_n−1(x₀) = f₀, p_n−1(x₁) = f₁, …, p_n−1(x_n−1) = f_n−1. Furthermore, let us write the nth Newton polynomial as

hence

Here g_n(x) is to be determined so that p_n(x₀) = f₀, p_n(x₁) = f₁, …, p_n(x_n) = f_n.

Since p_n and p_n−1 agree at x₀, …, x_n−1, we see that g_n is zero there. Also, g_n will generally be a polynomial of nth degree because so is p_n, whereas p_n−1 can be of degree n − 1 at most. Hence g_n must be of the form

We determine the constant a_n. For this we set x = x_n and solve (6″) algebraically for a_n. Replacing g_n(x_n) according to (6′) and using p_n(x_n) = f_n, we see that this gives

We write a_k instead of a_n and show that a_k equals the kth divided difference, recursively denoted and defined as follows:

and in general

If n = 1, then p_n−1(x_n) = p0(x₁) = f₀ because p0(x) is constant and equal to f₀, the value of f(x) at x₀. Hence (7) gives

and (6) and (6″) give the Newton interpolation polynomial of the first degree

If n = 2, then this p₁ and (7) give

where the last equality follows by straightforward calculation and comparison with the definition of the right side. (Verify it; be patient.) From (6) and (6″) we thus obtain the second Newton polynomial

For n = k, formula (6) gives

With p0(x) = f₀ by repeated application with k = 1, …, n this finally gives Newton's divided difference interpolation formula

An algorithm is shown in Table 19.2. The first do-loop computes the divided differences and the second the desired value

Example 4 shows how to arrange differences near the values from which they are obtained; the latter always stand a half-line above and a half-line below in the preceding column. Such an arrangement is called a (divided) difference table.

Table 19.2 Newton's Divided Difference Interpolation

Equal Spacing: Newton's Forward Difference Formula

Newton's formula (10) is valid for arbitrarily spaced nodes as they may occur in practice in experiments or observations. However, in many applications the x_j’s are regularly spaced—for instance, in measurements taken at regular intervals of time. Then, denoting the distance by h, we can write

We show how (8) and (10) now simplify considerably!

To get started, let us define the first forward difference of f at x_j by

the second forward difference of f at x_j by

and, continuing in this way, the kth forward difference of f at x_j by

Examples and an explanation of the name “forward” follow on the next page. What is the point of this? We show that if we have regular spacing (11), then

In (10) we finally set x = x₀ + rh. Then x − x₀ = rh, x − x₁ = (r − 1)h since x₁ − x₀ = h, and so on. With this and (13), formula (10) becomes Newton's (or Gregory²–Newton's) forward difference interpolation formula

where the binomial coefficients in the first line are defined by

and s! = 1 · 2 … s.

Error. From (5) we get, with x − x₀ = rh, x − x₁ = (r − 1)h, etc.,

with t as characterized in (5).

Formula (16) is an exact formula for the error, but it involves the unknown t. In Example 5 (below) we show how to use (16) for obtaining an error estimate and an interval in which the true value of f(x) must lie.

Comments on Accuracy. (A) The order of magnitude of the error _n(x) is about equal to that of the next difference not used in p_n(x).

(B) One should choose x₀, …, x_n such that the x at which one interpolates is as well centered between x₀, …, x_n as possible.

The reason for (A) is that in (16),

(and actually for any r as long as we do not extrapolate). The reason for (B) is that |r(r − 1) … (r − n)| becomes smallest for that choice.

This example also explains the name “forward difference formula”: we see that the differences in the formula slope forward in the difference table.

Equal Spacing: Newton's Backward Difference Formula

Instead of forward-sloping differences we may also employ backward-sloping differences. The difference table remains the same as before (same numbers, in the same positions), except for a very harmless change of the running subscript j (which we explain in Example 6, below). Nevertheless, purely for reasons of convenience it is standard to introduce a second name and notation for differences as follows. We define the first backward difference of f at x_j by

the second backward difference of f at x_j by

and, continuing in this way, the kth backward difference of f at x_j by

A formula similar to (14) but involving backward differences is Newton's (or Gregory–Newton's) backward difference interpolation formula

There is a third notation for differences, called the central difference notation. It is used in numerics for ODEs and certain interpolation formulas. See Ref. [E5] listed in App. 1.

19.4 Spline Interpolation

Given data (function values, points in the xy-plane) (x₀, f₀), (x₁, f₁), …, (x_n, f_n) can be interpolated by a polynomial p_n(x) of degree n or less so that the curve of p_n(x) passes through these n + 1 points (x_j, f_j); here f₀ = f(x₀), …, f_n = f(x_n), See Sec. 19.3.

Now if n is large, there may be trouble: p_n(x) may tend to oscillate for x between the nodes x₀, …, x_n. Hence we must be prepared for numeric instability (Sec. 19.1). Figure 434 shows a famous example by C. Runge³ for which the maximum error even approaches ∞ as n → ∞ (with the nodes kept equidistant and their number increased). Figure 435 illustrates the increase of the oscillation with n for some other function that is piecewise linear.

Those undesirable oscillations are avoided by the method of splines initiated by I. J. Schoenberg in 1946 (Quarterly of Applied Mathematics 4, pp. 45–99, 112–141). This method is widely used in practice. It also laid the foundation for much of modern CAD (computer-aided design). Its name is borrowed from a draftman's spline, which is an elastic rod bent to pass through given points and held in place by weights. The mathematical idea of the method is as follows:

Fig. 434. Runge's example f(x) = 1/(1 +x²) and interpolating polynomial P₁₀(x)

Fig. 435. Piecewise linear function f(x) and interpolation polynomials of increasing degrees

Instead of using a single high-degree polynomial P_n over the entire interval a x b in which the nodes lie, that is,

we use n low-degree, e.g., cubic, polynomials

one over each subinterval between adjacent nodes, hence q₀ from x₀ to x₁, then q₁ from x₁ to x₂, and so on. From this we compose an interpolation function g(x), called a spline, by fitting these polynomials together into a single continuous curve passing through the data points, that is,

Note that g(x) = q₀(x) when x₀ x x₁, then g(x) = q₁(x) when x₁ x x₂, and so on, according to our construction of g.

Thus spline interpolation is piecewise polynomial interpolation.

The simplest q_j’s would be linear polynomials. However, the curve of a piecewise linear continuous function has corners and would be of little interest in general—think of designing the body of a car or a ship.

We shall consider cubic splines because these are the most important ones in applications. By definition, a cubic spline g(x) interpolating given data (x₀, f₀), …, (x_n, f_n) is a continuous function on the interval a = x₀ x x_n = b that has continuous first and second derivatives and satisfies the interpolation condition (2); furthermore, between adjacent nodes, g(x) is given by a polynomial q_j(x) of degree 3 or less.

We claim that there is such a cubic spline. And if in addition to (2) we also require that

(given tangent directions of g(x) at the two endpoints of the interval a x b), then we have a uniquely determined cubic spline. This is the content of the following existence and uniqueness theorem, whose proof will also suggest the actual determination of splines. (Condition (3) will be discussed after the proof.)

Storage and Time Demands in solving (9) are modest, since the matrix of (9) is sparse (has few nonzero entries) and tridiagonal (may have nonzero entries only on the diagonal and on the two adjacent “parallels” above and below it). Pivoting (Sec. 7.3) is not necessary because of that dominance. This makes splines efficient in solving large problems with thousands of nodes or more. For some literature and some critical comments, see American Mathematical Monthly 105 (1998), 929–941.

Condition (3) includes the clamped conditions

in which the tangent directions f′(x₀) and f′(x_n) at the ends are given. Other conditions of practical interest are the free or natural conditions

(geometrically: zero curvature at the ends, as for the draftman's spline), giving a natural spline. These names are motivated by Fig. 293 in Problem Set 12.3.

Determination of Splines. Let k₀ and k_n be given. Obtain k₁, …, k_n−1 by solving the linear system (9). Recall that the spline g(x) to be found consists of n cubic polynomials q₀, …, q_n−1. We write these polynomials in the form

where j = 0, …, n − 1. Using Taylor's formula, we obtain

with a_j3 obtained by calculating from (12) and equating the result to (8), that is,

and now subtracting from this 2a_j2 as given in (13) and simplifying.

Note that for equidistant nodes of distance h_j = h we can write c_j = c = 1/j in (6*) and have from (9) simply

Fig. 436. Function f(x) = x⁴ and cubic spline g(x) in Example 1

19.5 Numeric Integration and Differentiation

In applications, the engineer often encounters integrals that are very difficult or even impossible to solve analytically. For example, the error function, the Fresnel integrals (see Probs. 16–25 on nonelementary integrals in this section), and others cannot be evaluated by the usual methods of calculus (see App. 3, (24)–(44) for such “difficult” integrals). We then need methods from numerical analysis to evaluate such integrals. We also need numerics when the integrand of the integral to be evaluated consists of an empirical function, where we are given some recorded values of that function. Methods that address these kinds of problems are called methods of numeric integration.

Numeric integration means the numeric evaluation of integrals

where a and b are given and f is a function given analytically by a formula or empirically by a table of values. Geometrically, J is the area under the curve of f between a and b (Fig. 440), taken with a minus sign where f is negative.

We know that if f is such that we can find a differentiable function F whose derivative is f, then we can evaluate J directly, i.e., without resorting to numeric integration, by applying the familiar formula

Your CAS (Mathematica, Maple, etc.) or tables of integrals may be helpful for this purpose.

Rectangular Rule. Trapezoidal Rule

Numeric integration methods are obtained by approximating the integrand f by functions that can easily be integrated.

The simplest formula, the rectangular rule, is obtained if we subdivide the interval of integration a x b into n subintervals of equal length h = (b − a)/n and in each subinterval approximate f by the constant the value of f at the midpoint of the jth subinterval (Fig. 441). Then f is approximated by a step function (piecewise constant function), the n rectangles in Fig. 441 have the areas and the rectangular rule is

The trapezoidal rule is generally more accurate. We obtain it if we take the same subdivision as before and approximate f by a broken line of segments (chords) with endpoints [a, f(a)], [x₁, f(x₁)], …, [b, f(b)] on the curve of f (Fig. 442). Then the area under the curve of f between a and b is approximated by n trapezoids of areas

Fig. 440. Geometric interpretation of a definite integral

Fig. 441. Rectangular rule

Fig. 442. Trapezoidal rule

By taking their sum we obtain the trapezoidal rule

where h = (b − a)/n, as in (1). The x_j’s and a and b are called nodes.

Table 19.3 Computations in Example 1

Error Bounds and Estimate for the Trapezoidal Rule

An error estimate for the trapezoidal rule can be derived from (5) in Sec. 19.3 with n = 1 by integration as follows. For a single subinterval we have

with a suitable t depending on x, between x₀ and x₁. Integration over x from a = x₀ to x₁ = x₀ + h gives

Setting x − x₀ = v and applying the mean value theorem of integral calculus, which we can use because (x − x₀)(x − x₀ − h) does not change sign, we find that the right side equals

where is a (suitable, unknown) value between x₀ and x₁. This is the error for the trapezoidal rule with n = 1, often called the local error.

Hence the error of (2) with any n is the sum of such contributions from the n subintervals; since h = (b − a)/n, nh³ = n(b − a)³/n³, and (b − a)² = n²h², we obtain

with (suitable, unknown) between a and b.

Because of (3) the trapezoidal rule (2) is also written

Error Bounds are now obtained by taking the largest value for f″, say, M₂, and the smallest value, in the interval of integration. Then (3) gives (note that K is negative)

Error Estimation by Halving h is advisable if f″ is very complicated or unknown, for instance, in the case of experimental data. Then we may apply the Error Principle of Sec. 19.1. That is, we calculate by (2), first with h, obtaining, say, J = J_h + _h, and then with obtaining J = J_h/2 + h/2. Now if we replace h² in (3) with the error is multiplied by . Hence (not exactly because may differ). Together, J_h/2 + h/2 = J_h + h ≈ J_h + 4h/2. Thus J_h/2 − J_h = (4 − 1)_h/2. Division by 3 gives the error formula for J_h/2

Simpson's Rule of Integration

Piecewise constant approximation of f led to the rectangular rule (1), piecewise linear approximation to the trapezoidal rule (2), and piecewise quadratic approximation will lead to Simpson's rule, which is of great practical importance because it is sufficiently accurate for most problems, but still sufficiently simple.

To derive Simpson's rule, we divide the interval of integration a x b into an even number of equal subintervals, say, into n = 2m subintervals of length h = (b − a)/(2m), with endpoints x₀(= a), x₁, …, x_2m−1, x_2m (= b); see Fig. 443. We now take the first two subintervals and approximate f(x) in the interval x₀ x x₂ = x₀ + 2h by the Lagrange polynomial p₂(x) through (x₀, f₀), (x₁, f₁), (x₂, f₂), where f_j = f(x_j). From (3) in Sec. 19.3 we obtain

The denominators in (6) are 2h², −h², and 2h², respectively. Setting s = (x − x₁)/h, we have

and we obtain

We now integrate with respect to x from x₀ to x₂. This corresponds to integrating with respect to s from −1 to 1. Since dx = h ds, the result is

Fig. 443. Simpson's rule

A similar formula holds for the next two subintervals from x₂ to x₄, and so on. By summing all these m formulas we obtain Simpson's rule⁴

where h = (b − a)/(2m) and f_j = f(x_j). Table 19.4 shows an algorithm for Simpson's rule.

Table 19.4 Simpson's Rule of Integration

Error of Simpson's Rule (7). If the fourth derivative f⁽⁴⁾ exists and is continuous on a x b, the error of (7), call it _s, is

here is a suitable unknown value between a and b. This is obtained similarly to (3). With this we may also write Simpson's rule (7) as

Error Bounds. By taking for f⁽⁴⁾ in (8) the maximum M₄ and minimum on the interval of integration we obtain from (8) the error bounds (note that C is negative)

Degree of Precision (DP) of an integration formula. This is the maximum degree of arbitrary polynomials for which the formula gives exact values of integrals over any intervals.

Hence for the trapezoidal rule,

because we approximate the curve of f by portions of straight lines (linear polynomials).

For Simpson's rule we might expect DP = 2 (why?). Actually,

by (9) because f⁽⁴⁾ is identically zero for a cubic polynomial. This makes Simpson's rule sufficiently accurate for most practical problems and accounts for its popularity.

Numeric Stability with respect to rounding is another important property of Simpson's rule. Indeed, for the sum of the roundoff errors _j of the 2m + 1 values f_j in (7) we obtain, since h = (b − a)/2m,

where u is the rounding unit ( if we round off to 6D; see Sec. 19.1). Also 6 = 1 + 4 + 1 is the sum of the coefficients for a pair of intervals in (7); take m = 1 in (7) to see this. The bound (b − a)u is independent of m, so that it cannot increase with increasing m, that is, with decreasing h. This proves stability.

Newton–Cotes Formulas. We mention that the trapezoidal and Simpson rules are special closed Newton–Cotes formulas, that is, integration formulas in which f(x) is interpolated at equally spaced nodes by a polynomial of degree n(n = 1 for trapezoidal, n = 2 for Simpson), and closed means that a and b are nodes (a = x₀, b = x_n). n = 3 and higher n are used occasionally. From n = 8 on, some of the coefficients become negative, so that a positive f_j could make a negative contribution to an integral, which is absurd. For more on this topic see Ref. [E25] in App. 1.

Table 19.5 Computations in Example 3

Instead of picking an n = 2m and then estimating the error by (9), as in Example 3, it is better to require an accuracy (e.g., 6D) and then determine n = 2m from (9).

Error Estimation for Simpson's Rule by Halving h. The idea is the same as in (5) and gives

J_h is obtained by using h and J_h/2 by using and _h/2 is the error of J_h/2.

Derivation. In (5) we had as the reciprocal of 3 = 4 − 1 and resulted from h² in (3) by replacing h with h. In (10) we have as the reciprocal of 15 = 16 − 1 and results from h⁴ in (8) by replacing h with h.

Adaptive Integration

The idea is to adapt step h to the variability of f(x). That is, where f varies but little, we can proceed in large steps without causing a substantial error in the integral, but where f varies rapidly, we have to take small steps in order to stay everywhere close enough to the curve of f.

Changing h is done systematically, usually by halving h, and automatically (not “by hand”) depending on the size of the (estimated) error over a subinterval. The subinterval is halved if the corresponding error is still too large, that is, larger than a given tolerance TOL (maximum admissible absolute error), or is not halved if the error is less than or equal to TOL (or doubled if the error is very small).

Adapting is one of the techniques typical of modern software. In connection with integration it can be applied to various methods. We explain it here for Simpson's rule. In Table 19.6 an asterisk means that for that subinterval, TOL has been reached.

Table 19.6 Computations in Example 6

Fig. 444. Adaptive integration in Example 6

Gauss Integration Formulas Maximum Degree of Precision

Our integration formulas discussed so far use function values at predetermined (equidistant) x-values (nodes) and give exact results for polynomials not exceeding a certain degree [called the degree of precision; see after (9)]. But we can get much more accurate integration formulas as follows. We set

with fixed n, and t = ±1 obtained from x = a, b by setting Then we determine the n coefficients A₁, …, A_n and n nodes t₁, …, t_n so that (11) gives exact results for polynomials of degree k as high as possible. Since n + n = 2n is the number of coefficients of a polynomial of degree 2n − 1, it follows that k 2n − 1.

Gauss has shown that exactness for polynomials of degree not exceeding 2n − 1 (instead of n − 1 for predetermined nodes) can be attained, and he has given the location of the t_j(= the jth zero of the Legendre polynomial P_n in Sec. 5.3) and the coefficients A_j which depend on n but not on f(t), and are obtained by using Lagrange's interpolation polynomial, as shown in Ref. [E5] listed in App. 1. With these t_j and A_j formula (11) is called a Gauss integration formula or Gauss quadrature formula. Its degree of precision is 2n − 1 as just explained. Table 19.7 gives the values needed for n = 2, …, 5. (For larger n, see pp. 916−919 of Ref. [GenRef1] in App. 1.)

Table 19.7 Gauss Integration: Nodes t_j and Coefficients A_j

Gauss integration is of considerable practical importance. Whenever the integrand f is given by a formula (not just by a table of numbers) or when experimental measurements can be set at times t_j (or whatever t represents) shown in Table 19.7 or in Ref. [GenRef1], then the great accuracy of Gauss integration outweighs the disadvantage of the complicated t_J and A_j (which may have to be stored). Also, Gauss coefficients A_j are positive for all n, in contrast with some of the Newton–Cotes coefficients for larger n.

Of course, there are frequent applications with equally spaced nodes, so that Gauss integration does not apply (or has no great advantage if one first has to get the t_j in (11) by interpolation).

Since the endpoints −1 and 1 of the interval of integration in (11) are not zeros of P_n, they do not occur among t₀, …, t_n, and the Gauss formula (11) is called, therefore, an open formula, in contrast with a closed formula, in which the endpoints of the interval of integration t₀ are t_n. and [For example, (2) and (7) are closed formulas.]

Numeric Differentiation

Numeric differentiation is the computation of values of the derivative of a function f from given values of f. Numeric differentiation should be avoided whenever possible. Whereas integration is a smoothing process and is not very sensitive to small inaccuracies in function values, differentiation tends to make matters rough and generally gives values of f′ that are much less accurate than those of f. The difficulty with differentiation is tied in with the definition of the derivative, which is the limit of the difference quotient, and, in that quotient, you usually have the difference of a large quantity divided by a small quantity. This can cause numerical instability. While being aware of this caveat, we must still develop basic differentiation formulas for use in numeric solutions of differential equations.

We use the notations etc., and may obtain rough approximation formulas for derivatives by remembering that

This suggests

Similarly, for the second derivative we obtain

More accurate approximations are obtained by differentiating suitable Lagrange polynomials. Differentiating (6) and remembering that the denominators in (6) are 2h², −h², 2h², we have

Evaluating this at x₀, x₁, x₂, we obtain the “three-point formulas”

Applying the same idea to the Lagrange polynomial p4(x), we obtain similar formulas, in particular,

Some examples and further formulas are included in the problem set as well as in Ref. [E5] listed in App. 1.

CHAPTER 19 REVIEW QUESTIONS AND PROBLEMS

1. What is a numeric method? How has the computer influenced numerics?
2. What is an error? A relative error? An error bound?
3. Why are roundoff errors important? State the rounding rules.
4. What is an algorithm? Which of its properties are important in software implementation?
5. What do you know about stability?
6. Why is the selection of a good method at least as important on a large computer as it is on a small one?
7. Can the Newton (–Raphson) method diverge? Is it fast? Same questions for the bisection method.
8. What is fixed-point iteration?
9. What is the advantage of Newton's interpolation formulas over Lagrange's?
10. What is spline interpolation? Its advantage over polynomial interpolation?
11. List and compare the integration methods we have discussed.
12. How did we use an interpolation polynomial in deriving Simpson's rule?
13. What is adaptive integration? Why is it useful?
14. In what sense is Gauss integration optimal?
15. How did we obtain formulas for numeric differentiation?
16. Write −46.9028104, 0.000317399, 54/7, −890/3 in floating-point form with 5S (5 significant digits, properly rounded).
17. Compute (5.346 − 3.644)/(3.444 − 3.055) as given and then rounded stepwise to 3S, 2S, 1S. Comment. (“Stepwise” means rounding the rounded numbers, not the given ones.)
18. Compute 0.38755/(5.6815 − 0.38419) as given and then rounded stepwise to 4S, 3S, 2S, 1S. Comment.
19. Let 19.1 and 25.84 be correctly rounded. Find the shortest interval in which the sum s of the true (unrounded) numbers must lie.
20. Do the same task as in Prob. 19 for the difference 3.2 − 6.29.
21. What is the relative error of n in terms of that of ?
22. Show that the relative error of is about twice that of .
23. Solve x² − 40x + 2 = 0 in two ways (cf. Sec. 19.1). Use 4S-arithmetic.
24. Solve x² − 100x + 1 = 0. Use 5S-arithmetic.
25. Compute the solution of x⁴ = x + 0.1 near x = 0 by transforming the equation algebraically to the form x = g(x) and starting from x₀ = 0.
26. Solve cos x = x² by Newton's method, starting from x = 0.5.
27. Solve Prob. 25 by bisection (3S-accuracy).
28. Compute sinh 0.4 from sinh 0, sinh 0.5 = 0.521, sinh 1.0 = 1.175 by quadratic interpolation.
29. Find the cubic spline for the data f(0) = 0, f(1) = 0, f(2) = 4, k₀ = −1, k₂ = 5.
30. Find the cubic spline q and the interpolation polynomial p for the data (0, 0), (1, 1), (2, 6), (3, 10), with q′(0) = 0, q′(3) = 0 and graph p and q on common axes.
31. Compute the integral of x³ from 0 to 1 by the trapezoidal rule with n = 5. What error bounds are obtained from (4) in Sec. 19.5? What is the actual error of the result?
32. Compute the integral of cos(x²) from 0 to 1 by Simpson's rule with 2m = 4.
33. Solve Prob. 32 by Gauss integration with n = 3 and n = 5.
34. Compute f′(0.2) for f(x) = x³ using (14b) in Sec. 19.5 with (a) h = 0.2, (b) h = 0.1. Compare the accuracy.
35. Compute f″(0.2) for f(x) = x² using (13) in Sec. 19.5 with (a) h = 0.2, (b) h = 0.1.

SUMMARY OF CHAPTER 19 Numerics in General

In this chapter we discussed concepts that are relevant throughout numeric work as a whole and methods of a general nature, as opposed to methods for linear algebra (Chap. 20) or differential equations (Chap. 21).

In scientific computations we use the floating-point representation of numbers (Sec. 19.1); fixed-point representation is less suitable in most cases.

Numeric methods give approximate values of quantities. The error of is

where a is the exact value. The relative error of is /a. Errors arise from rounding, inaccuracy of measured values, truncation (that is, replacement of integrals by sums, series by partial sums), and so on.

An algorithm is called numerically stable if small changes in the initial data give only correspondingly small changes in the final results. Unstable algorithms are generally useless because errors may become so large that results will be very inaccurate. The numeric instability of algorithms must not be confused with the mathematical instability of problems (“ill-conditioned problems,” Sec. 19.2).

Fixed-point iteration is a method for solving equations f(x) = 0 in which the equation is first transformed algebraically to x = g(x), an initial guess x₀ for the solution is made, and then approximations x₁, x₂, …, are successively computed by iteration from (see Sec. 19.2)

Newton's method for solving equations f(x) = 0 is an iteration

Here x_n+1 is the x-intercept of the tangent of the curve y = f(x) at the point x_n. This method is of second order (Theorem 2, Sec. 19.2). If we replace f′ in (3) by a difference quotient (geometrically: we replace the tangent by a secant), we obtain the secant method; see (10) in Sec. 19.2. For the bisection method (which converges slowly) and the method of false position, see Problem Set 19.2.

Polynomial interpolation means the determination of a polynomial p_n(x) such that p_n(x_j) = f_j, where j = 0, …, n and (x₀, f₀), …, (x_n, f_n) are measured or observed values, values of a function, etc. p_n(x) is called an interpolation polynomial. For given data, p_n(x) of degree n (or less) is unique. However, it can be written in different forms, notably in Lagrange's form (4), Sec. 19.3, or in Newton's divided difference form (10), Sec. 19.3, which requires fewer operations. For regularly spaced x₀, x₁ = x₀ + h, …, x_n = x₀ + nh the latter becomes Newton's forward difference formula (formula (14) in Sec. 19.3):

where r = (x − x₀)/h and the forward differences are Δf_j = f_j+1 − f_j and

A similar formula is Newton's backward difference interpolation formula (formula (18) in Sec. 19.3).

Interpolation polynomials may become numerically unstable as n increases, and instead of interpolating and approximating by a single high-degree polynomial it is preferable to use a cubic spline g(x), that is, a twice continuously differentiable interpolation function [thus, g(x_j) = f_j], which in each subinterval x_j x x_j+1 consists of a cubic polynomial q_j(x); see Sec. 19.4.

Simpson's rule of numeric integration is [see (7), Sec. 19.5]

with equally spaced nodes x_j = x₀ + jh, j = 1, …, 2m, h = (b − a)/(2m), and f_j = f(x_j). It is simple but accurate enough for many applications. Its degree of precision is DP = 3 because the error (8), Sec. 19.5, involves h⁴. A more practical error estimate is (10), Sec. 19.5,

obtained by first computing with step h, then with step h/2, and then taking of the difference of the results.

Simpson's rule is the most important of the Newton–Cotes formulas, which are obtained by integrating Lagrange interpolation polynomials, linear ones for the trapezoidal rule (2), Sec. 19.5, quadratic for Simpson's rule, cubic for the three-eights rule (see the Chap. 19 Review Problems), etc.

Adaptive integration (Sec. 19.5, Example 6) is integration that adjusts (“adapts”) the step (automatically) to the variability of f(x).

Romberg integration (Team Project 26, Problem Set 19.5) starts from the trapezoidal rule (2), Sec. 19.5, with h, h/2, h/4, etc. and improves results by systematically adding error estimates.

Gauss integration (11), Sec. 19.5, is important because of its great accuracy (DP = 2n − 1, compared to Newton–Cotes's DP = n − 1 or n). This is achieved by an optimal choice of the nodes, which are not equally spaced; see Table 19.7, Sec. 19.5.

Numeric differentiation is discussed at the end of Sec. 19.5. (Its main application (to differential equations) follows in Chap. 21.)