Alvaro Meseguer - Fundamentals of Numerical Mathematics for Physicists and Engineers

Suppose we want to locate the zeros or roots of a given function that is continuous within the interval . Mathematically, the main goal of exact root‐finding of in is as follows:

Root‐finding (Exact): Find such that .

However, computers work with finite precision and the condition cannot be exactly satisfied, in general. Therefore, we need to reformulate our problem:

Root‐finding (Approximate): For a given , find such that for some .

This reformulation introduces a new component in the problem: the positive constant , usually termed as tolerance , whose meaning is outlined in the plot on the right. Since the root condition cannot be satisfied exactly, we must provide an interval containing the root . In the figure on the right, the root lies within the interval .

In order to clarify the concept of tolerance we introduce here the bisection method (also called the interval halving method ). Let us assume that is a continuous function within the interval within which the function has a single root . Since the function is continuous, . First, we define , , and as the starting interval whose midpoint is . The main goal of the bisection method consists in identifying that half of in which the change of sign of actually takes place. Use the simple rules:

Bisection Rules:

Finally set and .

Figure 1.1(a) A simple exploration of reveals a change of sign within the interval (the root has been depicted with a gray bullet). (b) We start the bisection considering the initial interval . The bisection rule provides the new halved interval .

Figure 1.1shows the result of applying the bisection rule to find roots of the cubic polynomial already studied in Eq. ( 1.2). As shown in Figure 1.1a, this polynomial takes values of opposite sign, and , at the endpoints of the interval whose midpoint is . Since , the new (halved) interval provided by the bisection rules is . The midpoint of (white triangle in Figure 1.1b) provides a new estimation of the root of the polynomial. We could resume the process by checking whether or in order to obtain the new interval containing the root and so on. After bisections we have determined the interval with midpoint . In general, the interval will be obtained by applying the same rules to the previous interval :