An Introduction to Numerical Methods and Analysis, 2nd Edition

CHAPTER 3

ROOT-FINDING

A problem that most students should be familiar with from ordinary algebra is that of finding the root of an equation f(x) = 0, i.e., the value of the argument that makes f zero. More precisely, if the function is defined as y = f(x), we seek the value α such that

The precise terminology is that α is a zero of the function f, or a root of the equation f(x) = 0.¹ Note that we have not yet specified what kind of function f is. The obvious case is when f is an ordinary real-valued function of a single real variable x, but we can also consider the problem when f is a vector-valued function of a vector-valued variable, in which case the expression above is a system of equations; this more complicated case is discussed in Chapter 7.

In this chapter we consider only the simple case where f is a scalar real-valued function of a single real-valued variable. We will discuss three basic methods for finding the point α: the bisection method, Newton’s method, and the secant method. We then consider a broad class of ideas coming under the heading of fixed-point theory, which will enable us to broaden and extend our understanding of iterations in general, whether applied to root-finding problems or not. Finally, we will discuss some variants of Newton’s method and other advanced topics.

3.1 THE BISECTION METHOD

Bisection is a marvelously simple idea that is based on little ...