Fundamentals of Numerical Mathematics for Physicists and Engineers. Alvaro Meseguer

.

      1.2.1 The Bisection Method

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.1 shows 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 :

      Bisection Method: Given such that , compute and set

This general rule that provides from is an example of what is generally termed as algorithm,⁵ i.e. a set of mathematical calculations that sometimes involves decision‐making. Since this algorithm must be repeated or iterated, the bisection method described above constitutes an example of what is also termed as an iterative algorithm.

      Now we revisit the concept of tolerance seen from the point of view of the bisection process. For , the estimation of the root was , which is the midpoint of the interval , whereas for we obtain a narrower region of existence of such root, as well as its corresponding improved estimation . In other words, for the root lies within , with a tolerance , whereas for the interval containing the root is