CHAPTER 1
INTRODUCTORY CONCEPTS AND CALCULUS REVIEW

It is best to start this book with a question: What do we mean by "Numerical Methods and Analysis"? What kind of mathematics is this book about?

Generally and broadly speaking, this book covers the mathematics and methodologies that underlie the techniques of scientific computation. More prosaically, consider the button on your calculator app that computes the sine of the number in the display. Exactly how does the calculator know that correct value? When we speak of using the computer to solve a complicated mathematics or engineering problem, exactly what is involved in making that happen? Are computers "born" with the knowledge of how to solve complicated mathematical and engineering problems? No, of course not. Mostly they are programmed to do it, and the programs implement algorithms that are based on the kinds of things we talk about in this book.

Textbooks and courses in this area generally follow one of two main themes: Those titled "Numerical Methods" tend to emphasize the implementation of the algorithms, perhaps at the expense of the underlying mathematical theory that explains why the methods work; those titled "Numerical Analysis" tend to emphasize this underlying mathematical theory, perhaps at the expense of some of the implementation issues. The best approach, of course, is to properly mix the study of the algorithms and their implementation ("methods") with the study of the mathematical theory ("analysis") that supports them. This is our goal in this book.

Whenever someone speaks of using a computer to design an airplane, predict the weather, or otherwise solve a complex science or engineering problem, that person is talking about using numerical methods and analysis. The problems and areas of endeavor that use these kinds of techniques are continually expanding. For example, computational mathematics-another name for the material that we consider here-is now commonly used in the study of financial markets and investment structures, an area of study that does not ordinarily come to mind when we think of "scientific" computation. Similarly, the increasingly frequent use of computer-generated animation in film production is based on a heavy dose of spline approximations, which we introduce in §4.8. And modern weather prediction is based on using numerical methods and analysis to solve the very complicated equations governing fluid flow and heat transfer between and within the atmosphere, oceans, and ground [27].

There are a number of different ways to break the subject down into component parts. We will discuss the derivation and implementation of the algorithms, and we will also analyze the algorithms, mathematically, in order to learn how best to use them and how best to implement them. In our study of each technique, we will usually be concerned with two issues that often are in competition with each other:

• Accuracy: Very few of our computations will yield the exact answer to a problem, so we will have to understand how much error is made, and how to control (or even diminish) that error.
• Efficiency: Does the algorithm take an inordinate amount of computer time? This might seem to be an odd question to concern ourselves with-after all, computers are fast, right?-but there are slow ways to do things and fast ways to do things. All else being equal (it rarely is), we prefer the fast ways.

We say that these two issues compete with each other because, generally speaking, the steps that can be taken to make an algorithm more accurate usually make it more costly, that is, less efficient.

There is a third issue of importance, but it does not become as evident as the others (although it is still present) until Chapter 6:

• Stability: Does the method produce similar results for similar data? If we change the data by a small amount, do we get vastly different results? If so, we say that the method is unstable, and unstable methods tend to produce unreliable results. It is entirely possible to have an accurate method that is efficiently implemented, yet is horribly unstable; see §6.4.4 for an example of this.

1.1 BASIC TOOLS OF CALCULUS

1.1.1 Taylor's Theorem

Computational mathematics does not require a large amount of background, but it does require a good knowledge of that background. The most important single result in numerical computations, from all of the calculus, is Taylor's Theorem,1 which we now state:

The point is usually chosen at the discretion of the user, and is often taken to be 0. Note that the two forms of the remainder are equivalent: The "pointwise" form 1.3 can be derived from the "integral" form 1.2; see Problem 23.

Taylor's Theorem is important because it allows us to represent, exactly, fairly general functions in terms of polynomials with a known, specified, boundable error. This allows us to replace, in a computational setting, these same general functions with something that is much simpler-a polynomial-yet at the same time we are able to bound the error that is made. No other tool will be as important to us as Taylor's Theorem, so it is worth spending some time on it here at the outset.

The usual calculus treatment of Taylor's Theorem should leave the student familiar with three particular expansions (for all three of these we have used , which means we really should call them Maclaurin2 series, but we won't):

(Strictly speaking, the indices on the last two remainders should be and , because those are the exponents in the last terms of the expansion, but it is commonplace to present them as we did here.) In fact, Taylor's Theorem provides us with our first and simplest example of an approximation and an error estimate. Consider the problem of approximating the exponential function on the interval . Taylor's Theorem tells us that we can represent using a polynomial with a (known) remainder:

where is an unknown point between and 0. Since we want to consider the most general case, where can be any point in , we have to consider that can be any point in , as well. For simplicity, let's denote the polynomial by , and the remainder by , so that the equation above becomes

Suppose that we want this approximation to be accurate to within in absolute error, i.e., we want

for all in the interval . Note that if we can make for all , then we will have

so that the error in the approximation will be less than . The best way to proceed is to create a simple upper bound for , and then use that to determine the number of terms necessary to make this upper bound less than .

Thus, we proceed as follows:

Thus, if we find such that

then we will have

and we will know that the error is less than the desired tolerance, for all values of of interest to us, i.e., all . A little bit of exercise with a calculator shows us that we need to use to get the desired accuracy. Figure 1.1 shows a plot of the exponential function , the approximation , as well as the less accurate ; since it is impossible to distinguish by eye between the plots for and , we have also provided Figure 1.2, which is a plot of the error ; note that we begin to lose accuracy as we get away from the interval . This is not surprising. Since the Taylor polynomial is constructed to match and its first derivatives at , it ought to be the case that is a good approximation to only when is near .

Here we are in the first section of the text, and we have already constructed our first approximation and proved our first theoretical result. Theoretical result? Where? Why, the error estimate, of course. The material in the previous several lines is a proof of Proposition 1.1.

Although this result is not of major significance to our work-the exponential function is approximated more efficiently by different means-it does illustrate one of the most important aspects of the subject. The result tells us, ahead of time, that we can approximate the exponential function to within accuracy using a specific polynomial, and this accuracy holds for all in a specified interval. That is the kind of thing we will be doing throughout the text-constructing approximations to difficult computations that are accurate in some sense, and we know how accurate they are.

Figure 1.1 Taylor approximation: (solid line), (circles), and (dashed line). Note that and are indistinguishable on this plot.

Figure 1.2 Error in Taylor approximation: .

Figure 1.3 Error in Taylor approximation to over .

Although the usual approach is to construct Taylor expansions by directly computing the necessary derivatives of the function , sometimes a more subtle approach can be used. Consider...