CHAPTER 21

Numerics for ODEs and PDEs

Ordinary differential equations (ODEs) and partial differential equations (PDEs) play a central role in modeling problems of engineering, mathematics, physics, aeronautics, astronomy, dynamics, elasticity, biology, medicine, chemistry, environmental science, economics, and many other areas. Chapters 1–6 and 12 explained the major approaches to solving ODEs and PDEs analytically. However, in your career as an engineer, applied mathematicians, or physicist you will encounter ODEs and PDEs that cannot be solved by those analytic methods or whose solutions are so difficult that other approaches are needed. It is precisely in these real-world projects that numeric methods for ODEs and PDEs are used, often as part of a software package. Indeed, numeric software has become an indispensable tool for the engineer.

This chapter is evenly divided between numerics for ODEs and numerics for PDEs. We start with ODEs and discuss, in Sec. 21.1, methods for first-order ODEs. The main initial idea is that we can obtain approximations to the solution of such an ODE at points that are a distance h apart by using the first two terms of Taylor's formula from calculus. We use these approximations to construct the iteration formula for a method known as Euler's method. While this method is rather unstable and of little practical use, it serves as a pedagogical tool and a starting point toward understanding more sophisticated methods such as the Runge–Kutta method and its variant the Runga–Kutta–Fehlberg (RKF) method, which are popular and useful in practice. As is usual in mathematics, one tends to generalize mathematical ideas. The methods of Sec. 21.1 are one-step methods, that is, the current approximation uses only the approximation from the previous step. Multistep methods, such as the Adams–Bashforth methods and Adams–Moulton methods, use values computed from several previous steps. We conclude numerics for ODEs with applying Runge–Kutta–Nyström methods and other methods to higher order ODEs and systems of ODEs.

Numerics for PDEs are perhaps even more exciting and ingenious than those for ODEs. We first consider PDEs of the elliptic type (Laplace, Poisson). Again, Taylor's formula serves as a starting point and lets us replace partial derivatives by difference quotients. The end result leads to a mesh and an evaluation scheme that uses the Gauss–Seidel method (here also know as Liebmann's method). We continue with methods that use grids to solve Neuman and mixed problems (Sec. 21.5) and conclude with the important Crank–Nicholson method for parabolic PDEs in Sec. 21.6.

Sections 21.1 and 21.2 may be studied immediately after Chap. 1 and Sec. 21.3 immediately after Chaps. 2–4, because these sections are independent of Chaps. 19 and 20.

Sections 21.4–21.7 on PDEs may be studied immediately after Chap. 12 if students have some knowledge of linear systems of algebraic equations.

Prerequisite: Secs. 1.1–1.5 for ODEs, Secs. 12.1–12.3, 12.5, 12.10 for PDEs.

References and Answers to Problems: App. 1 Part E (see also Parts A and C), App. 2.

21.1 Methods for First-Order ODEs

Take a look at Sec. 1.2, where we briefly introduced Euler's method with an example. We shall develop Euler's method more rigorously. Pay close attention to the derivation that uses Taylor's formula from calculus to approximate the solution to a first-order ODE at points that are a distance h apart. If you understand this approach, which is typical for numerics for ODEs, then you will understand other methods more easily.

From Chap. 1 we know that an ODE of the first order is of the form F(x, y, y′) = 0 and can often be written in the explicit form y′ = f(x, y). An initial value problem for this equation is of the form

where x₀ and y₀ are given and we assume that the problem has a unique solution on some open interval a < x < b containing x₀.

In this section we shall discuss methods of computing approximate numeric values of the solution y(x) of (1) at the equidistant points on the x-axis

where the step size h is a fixed number, for instance, 0.2 or 0.1 or 0.01, whose choice we discuss later in this section. Those methods are step-by-step methods, using the same formula in each step. Such formulas are suggested by the Taylor series

Formula (2) is the key idea that lets us develop Euler's method and its variant called—you guessed it—improved Euler method, also known as Heun's method. Let us start by deriving Euler's method.

For small h³, h³, … in (2) are very small. Dropping all of them gives the crude approximation

and the corresponding Euler method (or Euler–Cauchy method)

discussed in Sec. 1.2. Geometrically, this is an approximation of the curve of by a polygon whose first side is tangent to this curve at (see Fig. 8 in Sec. 1.2).

Error of the Euler Method. Recall from calculus that Taylor's formula with remainder has the form

(where x ξ x + h). It shows that, in the Euler method, the truncation error in each step or local truncation error is proportional to h², written O(h²), where O suggests order (see also Sec. 20.1). Now, over a fixed x-interval in which we want to solve an ODE, the number of steps is proportional to 1/h. Hence the total error or global error is proportional to h²(1/h) = h¹. For this reason, the Euler method is called a first-order method. In addition, there are roundoff errors in this and other methods, which may affect the accuracy of the values y₁, y₂, … more and more as n increases.

Automatic Variable Step Size Selection in Modern Software. The idea of adaptive integration, as motivated and explained in Sec. 19.5, applies equally well to the numeric solution of ODEs. It now concerns automatically changing the step size h depending on the variability of y′ = f determined by

Accordingly, modern software automatically selects variable step sizes h_n so that the error of the solution will not exceed a given maximum size TOL (suggesting tolerance). Now for the Euler method, when the step size is h = h_n, the local error at is x_n is about . We require that this be equal to a given tolerance TOL,

y″(x) must not be zero on the interval J: x₀ x = x_N on which the solution is wanted. Let K be the minimum of |y″(x)| on J and assume that K > 0. Minimum |y″(x)| corresponds to maximum by (4). Thus, . We can insert this into (4b), obtaining by straightforward algebra

For other methods, automatic step size selection is based on the same principle.

Improved Euler Method. Predictor, Corrector. Euler's method is generally much too inaccurate. For a large h (0.2) this is illustrated in Sec. 1.2 by the computation for

And for small h the computation becomes prohibitive; also, roundoff in so many steps may result in meaningless results. Clearly, methods of higher order and precision are obtained by taking more terms in (2) into account. But this involves an important practical problem. Namely, if we substitute y′ = f(x, y(x)) into (2), we have

Now y in f depends on x, so that we have f′ as shown in (4*) and f″, f″′ even much more cumbersome. The general strategy now is to avoid the computation of these derivatives and to replace it by computing f for one or several suitably chosen auxiliary values of (x, y). “Suitably” means that these values are chosen to make the order of the method as high as possible (to have high accuracy). Let us discuss two such methods that are of practical importance, namely, the improved Euler method and the (classical) Runge–Kutta method.

In each step of the improved Euler method we compute two values, first the predictor

which is an auxiliary value, and then the new y-value, the corrector

Hence the improved Euler method is a predictor–corrector method: In each step we predict a value (7a) and then we correct it by (7b).

In algorithmic form, using the notations k₁ = hf(x_n, y_n) in (7a) and in (7b), we can write this method as shown in Table 21.1.

Table 21.1 Improved Euler Method (Heun's Method)

Table 21.2 Improved Euler Method for (6). Errors

Error of the Improved Euler Method. The local error is of order h³ and the global error of order h², so that the method is a second-order method.

Since the Euler method was an attractive pedagogical tool to teach the beginning of solving first-order ODEs numerically but had its drawbacks in terms of accuracy and could even produce wrong answers, we studied the improved Euler method and thereby introduced the idea of a predictor–corrector method. Although improved Euler is better than Euler, there are better methods that are used in industrial settings. Thus the practicing engineer has to know about the Runga–Kutta methods and its variants.

Runge–Kutta Methods (RK Methods)

A method of great practical importance and much greater accuracy than that of the improved Euler method is the classical Runge–Kutta method of fourth order, which we call briefly the Runge–Kutta method.¹ It is shown in Table 21.3. We see that in each step we first compute four auxiliary quantities k₁, k₂, k₃, k₄ and then the new value y_n+1. The method is well suited to the computer because it needs no special starting procedure, makes light demand on storage, and repeatedly uses the same straightforward computational procedure. It is numerically stable.

Note that, if f depends only on x, this method reduces to Simpson's rule of integration (Sec. 19.5). Note further that k₁, …, k₄ depend on n and generally change from step to step.

Table 21.3 Classical Runge–Kutta Method of Fourth Order

Table 21.4 Runge–Kutta Method Applied to (4)

Table 21.5 Comparison of the Accuracy of the Three Methods under Consideration in the Case of the Initial Value Problem (4), with h = 0.2

Error and Step Size Control.
RKF (Runge–Kutta–Fehlberg)

The idea of adaptive integration (Sec. 19.5) has analogs for Runge–Kutta (and other) methods. In Table 21.3 for RK (Runge–Kutta), if we compute in each step approximations and with step sizes h and 2h, respectively, the latter has error per step equal to 2⁵ = 32 times that of the former; however, since we have only half as many steps for 2h, the actual factor is 2⁵/2 = 16, so that, say,

Hence the error = ^(h) for step size h is about

where , as said before. Table 21.6 illustrates (10) for the initial value problem

the step size h = 0.1 and 0 x 0.4. We see that the estimate is close to the actual error. This method of error estimation is simple but may be unstable.

Table 21.6 Runge–Kutta Method Applied to the Initial Value Problem (11) and Error Estimate (10). Exact Solution y = tan x + x + 1

RKF. E. Fehlberg [Computing 6 (1970), 61–71] proposed and developed error control by using two RK methods of different orders to go from (x_n, y_n) to (x_n+1, y_n+1). The difference of the computed y-values at x_n+1 gives an error estimate to be used for step size control. Fehlberg discovered two RK formulas that together need only six function evaluations per step. We present these formulas here because RKF has become quite popular. For instance, Maple uses it (also for systems of ODEs).

Fehlberg's fifth-order RK method is

with coefficient vector γ = [γ₁ … γ₆],

His fourth-order RK method is

with coefficient vector

In both formulas we use only six different function evaluations altogether, namely,

The difference of (12) and (13) gives the error estimate

Table 21.7 summarizes essential features of the methods in this section. It can be shown that these methods are numerically stable (definition in Sec. 19.1). They are one-step methods because in each step we use the data of just one preceding step, in contrast to multistep methods where in each step we use data from several preceding steps, as we shall see in the next section.

Table 21.7 Methods Considered and Their Order (= Their Global Error)

Backward Euler Method. Stiff ODEs

The backward Euler formula for numerically solving (1) is

This formula is obtained by evaluating the right side at the new location (x_n+1, y_n+1); this is called the backward Euler scheme. For known y_n it gives y_n+1 implicitly, so it defines an implicit method, in contrast to the Euler method (3), which gives y_n+1 explicitly. Hence (16) must be solved for y_n+1. How difficult this is depends on f in (1). For a linear ODE this provides no problem, as Example 4 (below) illustrates. The method is particularly useful for “stiff” ODEs, as they occur quite frequently in the study of vibrations, electric circuits, chemical reactions, etc. The situation of stiffness is roughly as follows; for details, see, for example, [E5], [E25], [E26] in App. 1.

Error terms of the methods considered so far involve a higher derivative. And we ask what happens if we let h increase. Now if the error (the derivative) grows fast but the desired solution also grows fast, nothing will happen. However, if that solution does not grow fast, then with growing h the error term can take over to an extent that the numeric result becomes completely nonsensical, as in Fig. 451. Such an ODE for which h must thus be restricted to small values, and the physical system the ODE models, are called stiff. This term is suggested by a mass–spring system with a stiff spring (spring with a large k; see Sec. 2.4). Example 4 illustrates that implicit methods remove the difficulty of increasing h in the case of stiffness: It can be shown that in the application of an implicit method the solution remains stable under any increase of h, although the accuracy decreases with increasing h.

Stiffness will be considered further in Sec. 21.3 in connection with systems of ODEs.

Fig. 451. Euler method with h = 0.1 for the stiff ODE in Example 4 and exact solution

Table 21.8 Backward Euler Method (BEM) for Example 6. Comparison with Euler and RK

21.2 Multistep Methods

In a one-step method we compute y_n+1 using only a single step, namely, the previous value y_n. One-step methods are “self-starting,” they need no help to get going because they obtain from the initial value etc. All methods in Sec. 21.1 are one-step.

In contrast, a multistep method uses, in each step, values from two or more previous steps. These methods are motivated by the expectation that the additional information will increase accuracy and stability. But to get started, one needs values, say, y₀, y₁, y₂, y₃ in a 4-step method, obtained by Runge–Kutta or another accurate method. Thus, multistep methods are not self-starting. Such methods are obtained as follows.

Adams–Bashforth Methods

We consider an initial value problem

as before, with f such that the problem has a unique solution on some open interval containing x₀. We integrate y′ = f(x, y) from x_n to x_n+1 = x_n + h. This gives

Now comes the main idea. We replace f(x, y(x)) by an interpolation polynomial p(x) (see Sec. 19.3), so that we can later integrate. This gives approximations y_n+1 of y(x_n+1)and y_n of y(x_n),

Different choices of p(x) will now produce different methods. We explain the principle by taking a cubic polynomial, namely, the polynomial p₃(x) that at (equidistant)

has the respective values

This will lead to a practically useful formula. We can obtain p₃(x) from Newton's backward difference formula (18), Sec. 19.3:

where

We integrate p₃(x) over x from x_n to x_n+1 = x_n + h, thus over r from 0 to 1. Since

The integral of is and that of is . We thus obtain

It is practical to replace these differences by their expressions in terms of f:

We substitute this into (4) and collect terms. This gives the multistep formula of the Adams–Bashforth method²of fourth order

It expresses the new value y_n+1 [approximation of the solution y of (1) at x_n+1] in terms of 4 values of f computed from the y-values obtained in the preceding 4 steps. The local truncation error is of order h⁵, as can be shown, so that the global error is of order h⁴; hence (5) does define a fourth-order method.

Adams–Moulton Methods

Adams–Moulton methods are obtained if for p(x) in (2) we choose a polynomial that interpolates f(x, y(x)) at x_n+1,x_n, x_n−1, … (as opposed to x_n, x_n−1, … used before; this is the main point). We explain the principle for the cubic polynomial that interpolates at x_n+1, x_n, x_n−1, x_n−2. (Before we had x_n, x_n−1, x_n−2, x_n−3.) Again using (18) in Sec. 19.3 but now setting r = (x − x_n+1)/h, we have

We now integrate over x from x_n to x_n+1 as before. This corresponds to integrating over r from −1 to 0. We obtain

Replacing the differences as before gives

This is usually called an Adams–Moulton formula.³ It is an implicit formula because f_n+1 = f(x_n+1, y_n+1) appears on the right, so that it defines y_n+1 only implicitly, in contrast to (5), which is an explicit formula, not involving y_n+1 on the right. To use (6) we must predict a value , for instance, by using (5), that is,

The corrected new value y_n+1 is then obtained from (6) with f_n+1 replaced by and the other f’s as in (6); thus,

This predictor–corrector method (7a), (7b) is usually called the Adams–Moulton method of fourth order. It has the advantage over RK that (7) gives the error estimate

as can be shown. This is the analog of (10) in Sec. 21.1.

Sometimes the name Adams–Moulton method is reserved for the method with several corrections per step by (7b) until a specific accuracy is reached. Popular codes exist for both versions of the method.

Getting Started. In (5) we need f₀,f₁,f₂,f₃. Hence from (3) we see that we must first compute y₁, y², y³ by some other method of comparable accuracy, for instance, by RK or by RKF. For other choices see Ref. [E26] listed in App. 1.

Table 21.9 Adams–Moulton Method Applied to the Initial Value Problem (8); Predicted Values Computed by (7a) and Corrected Values by (7b)

Comments on Comparison of Methods. An Adams–Moulton formula is generally much more accurate than an Adams–Bashforth formula of the same order. This justifies the greater complication and expense in using the former. The method (7a), (7b) is numerically stable, whereas the exclusive use of (7a) might cause instability. Step size control is relatively simple. If |Corrector − Predictor| > TOL, use interpolation to generate “old” results at half the current step size and then try h/2 as the new step.

Whereas the Adams–Moulton formula (7a), (7b) needs only 2 evaluations per step, Runge–Kutta needs 4; however, with Runge–Kutta one may be able to take a step size more than twice as large, so that a comparison of this kind (widespread in the literature) is meaningless.

For more details, see Refs. [E25], [E26] listed in App. 1.

21.3 Methods for Systems
and Higher Order ODEs

Initial value problems for first-order systems of ODEs are of the form

in components

Here, f is assumed to be such that the problem has a unique solution y(x) on some open x-interval containing x₀. Our discussion will be independent of Chap. 4 on systems.

Before explaining solution methods it is important to note that (1) includes initial value problems for single m th-order ODEs,

and initial conditions y(x₀) = k₁, y′ (x₀) = k₂, …, y^(m−1)(x₀) = K_m as special cases.

Indeed, the connection is achieved by setting

Then we obtain the system

and the initial conditions y₁(x₀) = K₁, y₂(x₀) = K₂, …, y_m(x₀) = K_m.

Euler Method for Systems

Methods for single first-order ODEs can be extended to systems (1) simply by writing vector functions y and f instead of scalar functions y and f, whereas x remains a scalar variable.

We begin with the Euler method. Just as for a single ODE, this method will not be accurate enough for practical purposes, but it nicely illustrates the extension principle.

Table 21.10 Euler Method for Systems in Example 1 (Mass–Spring System)

Runge–Kutta Methods for Systems

As for Euler methods, we obtain RK methods for an initial value problem (1) simply by writing vector formulas for vectors with m components, which, for m = 1, reduce to the previous scalar formulas.

Thus, for the classical RK method of fourth order in Table 21.3, we obtain

and for each step n = 0, 1, …, N − 1 we obtain the 4 auxiliary quantities

and the new value [approximation of the solution y(x) at x_n+1 = x 0 + (n + 1)h]

Table 21.11 RK Method for Systems: Values y_1,n (x_n) of the Airy Function Ai(x) in Example 2

Runge–Kutta–Nyström Methods (RKN Methods)

RKN methods are direct extensions of RK methods (Runge–Kutta methods) to second-order ODEs y″ = f(x, y, y′), as given by the Finnish mathematician E. J. Nyström [Acta Soc. Sci. fenn., 1925, L, No. 13]. The best known of these uses the following formulas, where n = 0, 1, …, N − 1 (N the number of steps):

From this we compute the approximation y_n+1 of y(x_n+1) at x_n+1 = x₀ + (n + 1)h,

and the approximation of the derivative y′(x_n +1) needed in the next step,

RKN for ODEs y″ = f(x, y) Not Containing y′. Then k₂ = k₃ in (7), which makes the method particularly advantageous and reduces (7a)–(7c) to

Table 21.12 Runge–Kutta–Nyström Method Applied to Airy's Equation, Computation of the Airy Function y = Ai(x)

Our work in Examples 2 and 3 also illustrates that usefulness of methods for ODEs in the computation of values of “higher transcendental functions.”

Backward Euler Method for Systems. Stiff Systems

The backward Euler formula (16) in Sec. 21.1 generalizes to systems in the form

This is again an implicit method, giving y_n+1 implicitly for given y_n. Hence (8) must be solved for y_n+1. For a linear system this is shown in the next example. This example also illustrates that, similar to the case of a single ODE in Sec. 21.1, the method is very useful for stiff systems. These are systems of ODEs whose matrix has eigenvalues of very different magnitudes, having the effect that, just as in Sec. 21.1, the step in direct methods, RK for example, cannot be increased beyond a certain threshold without losing stability. (λ = −1 and − 10 in Example 4, but larger differences do occur in applications.)

Fig. 452. Euler method with h = 0.18 in Example 4

21.4 Methods for Elliptic PDEs

We have arrived at the second half of this chapter, which is devoted to numerics for partial differential equations (PDEs). As we have seen in Chap. 12, there are many applications to PDEs, such as in dynamics, elasticity, heat transfer, electromagnetic theory, quantum mechanics, and others. Selected because of their importance in applications, the PDEs covered here include the Laplace equation, the Poisson equation, the heat equation, and the wave equation. By covering these equations based on their importance in applications we also selected equations that are important for theoretical considerations. Indeed, these equations serve as models for elliptic, parabolic, and hyperbolic PDEs. For example, the Laplace equation is a representative example of an elliptic type of PDE, and so forth.

Recall, from Sec. 12.4, that a PDE is called quasilinear if it is linear in the highest derivatives. Hence a second-order quasilinear PDE in two independent variables x, y is of the form

u is an unknown function of x and y (a solution sought). F is a given function of the indicated variables.

Depending on the discriminant ac − b², the PDE (1) is said to be of

Here, in the heat and wave equations, y is time t. The coefficients a, b, c may be functions of x, y, so that the type of (1) may be different in different regions of the xy-plane. This classification is not merely a formal matter but is of great practical importance because the general behavior of solutions differs from type to type and so do the additional conditions (boundary and initial conditions) that must be taken into account.

Applications involving elliptic equations usually lead to boundary value problems in a region R, called a first boundary value problem or Dirichlet problem if u is prescribed on the boundary curve C of R, a second boundary value problem or Neumann problem if u_n = ∂u/∂n (normal derivative of u) is prescribed on C, and a third or mixed problem if u is prescribed on a part of C and u_n on the remaining part. C usually is a closed curve (or sometimes consists of two or more such curves).

Difference Equations
for the Laplace and Poisson Equations

In this section we develop numeric methods for the two most important elliptic PDEs that appear in applications. The two PDEs are the Laplace equation

and the Poisson equation

The starting point for developing our numeric methods is the idea that we can replace the partial derivatives of these PDEs by corresponding difference quotients. Details are as follows:

To develop this idea, we start with the Taylor formula and obtain

We subtract (4b) from (4a), neglect terms in h³, h⁴, …, and solve for u_x. Then

Similarly,

and

By subtracting, neglecting terms in k³, k⁴, …, and solving for u_y we obtain

We now turn to second derivatives. Adding (4a) and (4b) and neglecting terms in h⁴, h⁵, …, we obtain u(x + h, y) + u(x − h, y) ≈ 2u(x, y) + h²u_xx(x, y). Solving for u_xx we have

Similarly,

We shall not need (see Prob. 1)

Figure 453a shows the points (x + h, y), (x − h, y), … in (5) and (6).

We now substitute (6a) and (6b) into the Poisson equation (3), choosing k = h to obtain a simple formula:

This is a difference equation corresponding to (3). Hence for the Laplace equation (2) the corresponding difference equation is

h is called the mesh size. Equation (8) relates u at (x, y) to u at the four neighboring points shown in Fig. 453b. It has a remarkable interpretation: u at (x, y) equals the mean of the values of u at the four neighboring points. This is an analog of the mean value property of harmonic functions (Sec. 18.6).

Those neighbors are often called E (East), N (North), W (West), S (South). Then Fig. 453b becomes Fig. 453c and (7) is

Fig. 453. Points and notation in (5)–(8) and (7*)

Our approximation of in (7) and (8) is a 5-point approximation with the coefficient scheme or stencil (also called pattern, molecule, or star)

Dirichlet Problem

In numerics for the Dirichlet problem in a region R we choose an h and introduce a square grid of horizontal and vertical straight lines of distance h. Their intersections are called mesh points (or lattice points or nodes). See Fig. 454.

Then we approximate the given PDE by a difference equation [(8) for the Laplace equation], which relates the unknown values of u at the mesh points in R to each other and to the given boundary values (details in Example 1). This gives a linear system of algebraic equations. By solving it we get approximations of the unknown values of u at the mesh points in R.

We shall see that the number of equations equals the number of unknowns. Now comes an important point. If the number of internal mesh points, call it p, is small, say, p < 100, then a direct solution method may be applied to that linear system of p < 100 equations in p unknowns. However, if p is large, a storage problem will arise. Now since each unknown u is related to only 4 of its neighbors, the coefficient matrix of the system is a sparse matrix, that is, a matrix with relatively few nonzero entries (for instance, 500 of 10,000 when p = 100). Hence for large p we may avoid storage difficulties by using an iteration method, notably the Gauss–Seidel method (Sec. 20.3), which in PDEs is also called Liebmann's method (note the strict diagonal dominance). Remember that in this method we have the storage convenience that we can overwrite any solution component (value of u) as soon as a “new” value is available.

Both cases, large p and small p, are of interest to the engineer, large p if a fine grid is used to achieve high accuracy, and small p if the boundary values are known only rather inaccurately, so that a coarse grid will do it because in this case it would be meaningless to try for great accuracy in the interior of the region R.

We illustrate this approach with an example, keeping the number of equations small, for simplicity. As convenient notations for mesh points and corresponding values of the solution (and of approximate solutions) we use (see also Fig. 454)

Fig. 454. Region in the xy-plane covered by a grid of mesh h, also showing mesh points p₁₁ = (h, h), …, p_ij = (ih, jh), …

With this notation we can write (8) for any mesh point P_ij in the form

Remark. Our current discussion and the example that follows illustrate what we may call the reuseability of mathematical ideas and methods. Recall that we applied the Gauss–Seidel method to a system of ODEs in Sec. 20.3 and that we can now apply it again to elliptic PDEs. This shows that engineering mathematics has a structure and important mathematical ideas and methods will appear again and again in different situations. The student should find this attractive in that previous knowledge can be reapplied.

A matrix is called a band matrix if it has all its nonzero entries on the main diagonal and on sloping lines parallel to it (separated by sloping lines of zeros or not). For example, A in (13) is a band matrix. Although the Gauss elimination does not preserve zeros between bands, it does not introduce nonzero entries outside the limits defined by the original bands. Hence a band structure is advantageous. In (13) it has been achieved by carefully ordering the mesh points.

ADI Method

A matrix is called a tridiagonal matrix if it has all its nonzero entries on the main diagonal and on the two sloping parallels immediately above or below the diagonal. (See also Sec. 20.9.) In this case the Gauss elimination is particularly simple.

This raises the question of whether, in the solution of the Dirichlet problem for the Laplace or Poisson equations, one could obtain a system of equations whose coefficient matrix is tridiagonal. The answer is yes, and a popular method of that kind, called the ADI method (alternating direction implicit method) was developed by Peaceman and Rachford. The idea is as follows. The stencil in (9) shows that we could obtain a tridiagonal matrix if there were only the three points in a row (or only the three points in a column). This suggests that we write (11) in the form

so that the left side belongs to y-Row j only and the right side to x-Column i. Of course, we can also write (11) in the form

so that the left side belongs to Column i and the right side to Row j. In the ADI method we proceed by iteration. At every mesh point we choose an arbitrary starting value . In each step we compute new values at all mesh points. In one step we use an iteration formula resulting from (14a) and in the next step an iteration formula resulting from (14b), and so on in alternating order.

In detail: suppose approximations have been computed. Then, to obtain the next approximations , we substitute the on the right side of (14a) and solve for the on the left side; that is, we use

We use (15a) for a fixed j, that is, for a fixed rowj, and for all internal mesh points in this row. This gives a linear system of N algebraic equations (N = number of internal mesh points per row) in N unknowns, the new approximations of u at these mesh points. Note that (15a) involves not only approximations computed in the previous step but also given boundary values. We solve the system (15a) (j fixed!) by Gauss elimination. Then we go to the next row, obtain another system of N equations and solve it by Gauss, and so on, until all rows are done. In the next step we alternate direction, that is, we compute the next approximations column by column from the and the given boundary values, using a formula obtained from (14b) by substituting the on the right:

For each fixed i, that is, for each column, this is a system of M equations (M = number of internal mesh points per column) in M unknowns, which we solve by Gauss elimination. Then we go to the next column, and so on, until all columns are done.

Let us consider an example that merely serves to explain the entire method.

Improving Convergence. Additional improvement of the convergence of the ADI method results from the following interesting idea. Introducing a parameter p, we can also write (11) in the form

This gives the more general ADI iteration formulas

For p = 2, this is (15). The parameter p may be used for improving convergence. Indeed, one can show that the ADI method converges for positive p, and that the optimum value for maximum rate of convergence is

where K is the larger of M + 1 and N + 1 (see above). Even better results can be achieved by letting p vary from step to step. More details of the ADI method and variants are discussed in Ref. [E25] listed in App. 1.

21.5 Neumann and Mixed Problems.
Irregular Boundary

We continue our discussion of boundary value problems for elliptic PDEs in a region R in the xy-plane. The Dirichlet problem was studied in the last section. In solving Neumann and mixed problems (defined in the last section) we are confronted with a new situation, because there are boundary points at which the (outer) normal derivative u_n = ∂u/∂n of the solution is given, but u itself is unknown since it is not given. To handle such points we need a new idea. This idea is the same for Neumann and mixed problems. Hence we may explain it in connection with one of these two types of problems. We shall do so and consider a typical example as follows.

Irregular Boundary

We continue our discussion of boundary value problems for elliptic PDEs in a region R in the xy-plane. If R has a simple geometric shape, we can usually arrange for certain mesh points to lie on the boundary C of R, and then we can approximate partial derivatives as explained in the last section. However, if C intersects the grid at points that are not mesh points, then at points close to the boundary we must proceed differently, as follows.

The mesh point O in Fig. 459 is of that kind. For O and its neighbors A and P we obtain from Taylor's theorem

We disregard the terms marked by dots and eliminate ∂u_O/∂x. Equation (4b) times a plus equation (4a) gives

Fig. 459. Curved boundary C of a region R, a mesh point O near C, and neighbors A, B, P, Q

We solve this last equation algebraically for the derivative, obtaining

Similarly, by considering the points O, B, and Q,

By addition,

For example, if , instead of the stencil (see Sec. 21.4)

because , etc. The sum of all five terms still being zero (which is useful for checking).

Using the same ideas, you may show that in the case of Fig. 460.

a formula that takes care of all conceivable cases.

Fig. 460. Neighboring points A, B, P, Q of a mesh point O and notations in formula (6)

21.6 Methods for Parabolic PDEs

The last two sections concerned elliptic PDEs, and we now turn to parabolic PDEs. Recall that the definitions of elliptic, parabolic, and hyperbolic PDEs were given in Sec. 21.4. There it was also mentioned that the general behavior of solutions differs from type to type, and so do the problems of practical interest. This reflects on numerics as follows.

For all three types, one replaces the PDE by a corresponding difference equation, but for parabolic and hyperbolic PDEs this does not automatically guarantee the convergence of the approximate solution to the exact solution as the mesh h → 0; in fact, it does not even guarantee convergence at all. For these two types of PDEs one needs additional conditions (inequalities) to assure convergence and stability, the latter meaning that small perturbations in the initial data (or small errors at any time) cause only small changes at later times.

In this section we explain the numeric solution of the prototype of parabolic PDEs, the one-dimensional heat equation

This PDE is usually considered for x in some fixed interval, say, 0 x L, and time t 0, and one prescribes the initial temperature u(x, 0) = f(x) (f given) and boundary conditions at x = 0 and x = L for all t 0, for instance, u(0, t) = 0, u(L, t) = 0. We may assume c = 1 and L = 1; this can always be accomplished by a linear transformation of x and t (Prob. 1). Then the heat equation and those conditions are

A simple finite difference approximation of (1) is [see (6a) in Sec. 21.4; j is the number of the time step]

Figure 465 shows a corresponding grid and mesh points. The mesh size is h in the x-direction and k in the t-direction. Formula (4) involves the four points shown in Fig. 466. On the left in (4) we have used a forward difference quotient since we have no information for negative t at the start. From (4) we calculate u_i,j+1, which corresponds to time row j + 1, in terms of the three other u that correspond to time row j. Solving (4) for u_i,j+1, we have

Computations by this explicit method based on (5) are simple. However, it can be shown that crucial to the convergence of this method is the condition

Fig. 465. Grid and mesh points corresponding to (4), (5)

Fig. 466. The four points in (4) and (5)

That is, u_ij should have a positive coefficient in (5) or (for r = ) be absent from (5). Intuitively, (6) means that we should not move too fast in the t-direction. An example is given below.

Crank–Nicolson Method

Condition (6) is a handicap in practice. Indeed, to attain sufficient accuracy, we have to choose h small, which makes k very small by (6). For example, if h = 0.1, then k 0.005. Accordingly, we should look for a more satisfactory discretization of the heat equation.

A method that imposes no restriction on r = k/h² is the Crank–Nicolson (CN) method,⁵ which uses values of u at the six points in Fig. 467. The idea of the method is the replacement of the difference quotient on the right side of (4) by times the sum of two such difference quotients at two time rows (see Fig. 467). Instead of (4) we then have

Multiplying by 2k and writing r = k/h² as before, we collect the terms corresponding to time row j + 1 on the left and the terms corresponding to time row j on the right:

How do we use (8)? In general, the three values on the left are unknown, whereas the three values on the right are known. If we divide the x-interval 0 x 1 in (1) into n equal intervals, we have n − 1 internal mesh points per time row (see Fig. 465, where n = 4). Then for j = 0 and i = 1, …, n − 1, formula (8) gives a linear system of n − 1 equations for the n − 1 unknown values u₁₁, u₂₁, …, u_n−1,1 in the first time row in terms of the initial values u₀₀, u₁₀, …, u_n0 and the boundary values u₀₁(= 0), u_n1 (= 0). Similarly for j = 1, j = 2, and so on; that is, for each time row we have to solve such a linear system of n − 1 equations resulting from (8).

Although r = k/h² is no longer restricted, smaller r will still give better results. In practice, one chooses a k by which one can save a considerable amount of work, without making r too large. For instance, often a good choice is r = 1 (which would be impossible in the previous method). Then (8) becomes simply

Fig. 467. The six points in the Crank–Nicolson formulas (7) and (8)

Fig. 468. Grid in Example 1

21.7 Method for Hyperbolic PDEs

In this section we consider the numeric solution of problems involving hyperbolic PDEs. We explain a standard method in terms of a typical setting for the prototype of a hyperbolic PDE, the wave equation:

Note that an equation u_tt = c²u_xx and another x-interval can be reduced to the form (1) by a linear transformation of x and t. This is similar to Sec. 21.6, Prob. 1.

For instance, (1)–(4) is the model of a vibrating elastic string with fixed ends at x = 0 and x = 1 (see Sec. 12.2). Although an analytic solution of the problem is given in (13), Sec. 12.4, we use the problem for explaining basic ideas of the numeric approach that are also relevant for more complicated hyperbolic PDEs.

Replacing the derivatives by difference quotients as before, we obtain from (1) [see (6) in Sec. 21.4 with y = t]

where h is the mesh size in x, and k is the mesh size in t. This difference equation relates 5 points as shown in Fig. 470a. It suggests a rectangular grid similar to the grids for parabolic equations in the preceding section. We choose r* = k²/h² = 1. Then u_ij drops out and we have

It can be shown that for 0 < r* 1 the present explicit method is stable, so that from (6) we may expect reasonable results for initial data that have no discontinuities. (For a hyperbolic PDE the latter would propagate into the solution domain—a phenomenon that would be difficult to deal with on our present grid. For unconditionally stable implicit methods see [E1] in App. 1.)

Fig. 470. Mesh points used in (5) and (6)

Equation (6) still involves 3 time steps j − 1,j,j + 1, whereas the formulas in the parabolic case involved only 2 time steps. Furthermore, we now have 2 initial conditions. So we ask how we get started and how we can use the initial condition (3). This can be done as follows.

From u_t(x, 0) = g(x) we derive the difference formula

where. g_i = g(ih). For t = 0, that is, j = 0, equation (6) is

Into this we substitute u_{i, −1} as given in (7). We obtain u_i1 = u_i−1,0 + u_i+1,0 − u_i1 + 2kg_i and by simplification

This expresses u_i1 in terms of the initial data. It is for the beginning only. Then use (6).

This is the end of Chap. 21 on numerics for ODEs and PDEs, a field that continues to develop rapidly in both applications and theoretical research. Much of the activity in the field is due to the computer serving as an invaluable tool for solving large-scale and complicated practical problems as well as for testing and experimenting with innovative ideas. These ideas could be small or major improvements on existing numeric algorithms or testing new algorithms as well as other ideas.

CHAPTER 21 REVIEW QUESTIONS AND PROBLEMS

1. Explain the Euler and improved Euler methods in geometrical terms. Why did we consider these methods?
2. How did we obtain numeric methods from the Taylor series?
3. What are the local and the global orders of a method? Give examples.
4. Why did we compute auxiliary values in each Runge–Kutta step? How many?
5. What is adaptive integration? How does its idea extend to Runge–Kutta?
6. What are one-step methods? Multistep methods? The underlying ideas? Give examples.
7. What does it mean that a method is not self-starting? How do we overcome this problem?
8. What is a predictor–corrector method? Give an important example.
9. What is automatic step size control? When is it needed? How is it done in practice?
10. How do we extend Runge–Kutta to systems of ODEs?
11. Why did we have to treat the main types of PDEs in separate sections? Make a list of types of problems and numeric methods.
12. When and how did we use finite differences? Give as many details as you can remember without looking into the text.
13. How did we approximate the Laplace and Poisson equations?
14. How many initial conditions did we prescribe for the wave equation? For the heat equation?
15. Can we expect a difference equation to give the exact solution of the corresponding PDE?
16. In what method for PDEs did we have convergence problems?
17. Solve y′ = y, y(0) = 1 by Euler's method, 10 steps, h = 0.1.
18. Do Prob. 17 with h = 0.01, 10 steps. Compute the errors. Compare the error for x = 0.1 with that in Prob. 17.
19. Solve y′ = 1 + y², y(0) = 3 by the improved Euler method, 10 steps.
20. Solve y′ = y = (x + 1)², y(0) = 3 by the improved Euler method, 10 steps with h = 0.1. Determine the errors.
21. Solve Prob. 19 by RK with h = 0.1, 5 steps. Compute the error. Compare with Prob. 19.
22. Fair comparison. Solve , y(1) = 0 for 1 x 1.8 (a) by the Euler method with h = 0.1, (b) by the improved Euler method with h = 0.2, and (c) by RK with h = 0.4. Verify that the exact solution is y = (In x)² + In x. Compute and compare the errors. Why is the comparison fair?
23. Apply the Adams–Moulton method to , y(0) = 0, h = 0.2, x = 0, …, 1, starting with 0.198668, 0.389416, 0.564637.
24. Apply the A–M method to y′ = (x + y − 4)², y(0) = 4, h = 0.2, x = 0, …, 1, starting with 4.00271, 4.02279, 4.08413.
25. Apply Euler's method for systems to y″ = x²y, y(0) = 1, y′(0) = 0, h = 0.1, 5 steps.
26. Apply Euler's method for systems to , y₁(0) = 2, y₂(0) = 0, h = 0.2, 10 steps. Sketch the solution.
27. Apply Runge–Kutta for systems to y″ + y = 2e^x, y(0) = 0, y′(0) = 1, h = 0.2, 5 steps. Determine the errors.
28. Apply Runge–Kutta for systems to , , y₁(0) = −3, y₂(0) = −3, h = 0.05, 3 steps.
29. Find rough approximate values of the electrostatic potential at p₁₁, p₁₂, p₁₃ in Fig. 471 that lie in a field between conducting plates (in Fig. 471 appearing as sides of a rectangle) kept at potentials 0 and 220 V as shown. (Use the indicated grid.)

    

    Fig. 471. Problem 29

30. A laterally insulated homogeneous bar with ends at x = 0 and x = 1 has initial temperature 0. Its left end is kept at 0, whereas the temperature at the right end varies sinusoidally according to

    

    Find the temperature u(x, t) in the bar [solution of (1) in Sec. 21.6] by the explicit method with h = 0.2 and r = 0.5 (one period, that is, 0 t 0.24).

31. Find the solution of the vibrating string problem u_tt = u_xx, u(x, 0) = x(1 − x), u_t = 0, u(0, t) = u(1, t) = 0 by the method in Sec. 21.7 with h = 0.1 and k = 0.1 for t = 0.3.

32–34 POTENTIAL

Find the potential in Fig. 472, using the given grid and the boundary values:

• 32.
• 33. u(p₁₀) = u(p₃₀) = 960, u(p₂₀) = −480, u = 0 elsewhere on the boundary
• 34. u = 70 on the upper and left sides, u = 0 on the lower and right sides

  

  Fig. 472. Problems 32–34

• 35. Solve u_t = u_xx(0 x 1, t 0), u(x, 0) = x²(1 − x), u(0, t) = u(1, t) = 0 by Crank–Nicolson with h = 0.2, k = 0.04, 5 time steps.

SUMMARY OF CHAPTER 21

Numerics for ODEs and PDEs

In this chapter we discussed numerics for ODEs (Secs. 21.1–21.3) and PDEs (Secs. 21.4–21.7). Methods for initial value problems

involving a first-order ODE are obtained by truncating the Taylor series

where, by (1), y′ = f, y″ = f′ = ∂f/∂x + (∂f/∂y)y′, etc. Truncating after the term hy′, we get the Euler method, in which we compute step by step

Taking one more term into account, we obtain the improved Euler method. Both methods show the basic idea but are too inaccurate in most cases.

Truncating after the term in h⁴, we get the important classical Runge–Kutta (RK) method of fourth order. The crucial idea in this method is the replacement of the cumbersome evaluation of derivatives by the evaluation of f(x, y) at suitable points (x, y); thus in each step we first compute four auxiliary quantities (Sec. 21.1)

and then the new value

Error and step size control are possible by step halving or by RKF (Runge–Kutta–Fehlberg).

The methods in Sec. 21.1 are one-step methods since they get y_n+1 from the result y_n of a single step. A multistep method (Sec. 21.2) uses the values of y_n, y_n−1, … of several steps for computing y_n+1. Integrating cubic interpolation polynomials gives the Adams–Bashforth predictor (Sec. 21.2)

where f_j = f(x_j, y_j), and an Adams–Moulton corrector (the actual new value)

where . Here, to get started, y₁, y₂, y₃ must be computed by the Runge–Kutta method or by some other accurate method.

Section 19.3 concerned the extension of Euler and RK methods to systems

This includes single m th-order ODEs, which are reduced to systems. Second-order equations can also be solved by RKN (Runge–Kutta–Nyström) methods. These are particularly advantageous for y″ = f(x, y) with f not containing y′.

Numeric methods for PDEs are obtained by replacing partial derivatives by difference quotients. This leads to approximating difference equations, for the Laplace equation to

for the heat equation to

and for the wave equation to

here h and k are the mesh sizes of a grid in the x- and y-directions, respectively, where in (6) and (7) the variable y is time t.

These PDEs are elliptic, parabolic, and hyperbolic, respectively. Corresponding numeric methods differ, for the following reason. For elliptic PDEs we have boundary value problems, and we discussed for them the Gauss–Seidel method (also known as Liebmann's method) and the ADI method (Secs. 21.4, 21.5). For parabolic PDEs we are given one initial condition and boundary conditions, and we discussed an explicit method and the Crank–Nicolson method (Sec. 21.6). For hyperbolic PDEs, the problems are similar but we are given a second initial condition (Sec. 21.7).