An Introduction to Numerical Methods and Analysis, 2nd Edition

CHAPTER 2

A SURVEY OF SIMPLE METHODS AND TOOLS

In this chapter we want to offer a few very simple examples of approximations, algorithms, and error estimates, partly because they will be useful in developing or implementing some of the methods presented in later chapters, and partly to ease our way into the subject material. What we want to do is to acclimate the student into the broad area of numerical computations without restricting ourselves to one small corner of the subject. In addition, we show how some of the simplest approximation techniques (difference methods for derivative approximation, linear interpolation, solution of tridiagonal systems) can be used as the basis for computational schemes in more involved settings (Euler’s method for the initial value problem, the trapezoid rule for numerical integration, the approximate solution of two-point boundary value problems). The goal here is to introduce the reader to the basic ideas of numerical method and analysis by looking at simple techniques across a broad spectrum of problem areas.

2.1 HORNER’S RULE AND NESTED MULTIPLICATION

In Chapter 1 we devoted some time to the construction of polynomial approximations to given functions. It might be good if we discussed the best way to evaluate those approximations efficiently; hence this section.

The most efficient way to evaluate a polynomial is by nested multiplication. If we have

then we factor out each power of x as far as it will go, thus getting

Computation with the ...