The Method of False Position

Each successive pair of approximations in the Bisection method brackets a root $p$ of the equation; that is, for each positive integer $n$, a root lies between $a_n$ and $b_n$. This implies that, for each $n$, the Bisection method iterations satisfy  

\[|p_n - p| < \tfrac{1}{2} |a_n - b_n|,\]

which provides an easily calculated error bound for the approximations.  

Root bracketing is not guaranteed for either Newton’s method or the Secant method. In Example 1, Newton’s method was applied to $f(x) = \cos x - x$, and an approximate root was found to be $0.7390851332$. Table 2.5 shows that this root is not bracketed by either $p_0$ and $p_1$ or $p_1$ and $p_2$. The Secant method approximations for this problem are also given in Table 2.5. In this case the initial approximations $p_0$ and $p_1$ bracket the root, but the pair of approximations $p_3$ and $p_4$ fail to do so.  

The method of False Position (also called Regula Falsi) generates approximations in the same manner as the Secant method, but it includes a test to ensure that the root is always bracketed between successive iterations. Although it is not a method we generally recommend, it illustrates how bracketing can be incorporated.  

First choose initial approximations $p_0$ and $p_1$ with $f(p_0) \cdot f(p_1) < 0$. The approximation $p_2$ is chosen in the same manner as in the Secant method, as the $x$-intercept of the line joining $(p_0, f(p_0))$ and $(p_1, f(p_1))$. To decide which secant line to use to compute $p_3$, consider $f(p_2) \cdot f(p_1)$, or more correctly $\text{sgn } f(p_2) \cdot \text{sgn } f(p_1)$.  

• If $\text{sgn } f(p_2) \cdot \text{sgn } f(p_1) < 0$, then $p_1$ and $p_2$ bracket a root. Choose $p_3$ as the $x$-intercept of the line joining $(p_1, f(p_1))$ and $(p_2, f(p_2))$.  
• If not, choose $p_3$ as the $x$-intercept of the line joining $(p_0, f(p_0))$ and $(p_2, f(p_2))$, and then interchange the indices on $p_0$ and $p_1$.  

In a similar manner, once $p_3$ is found, the sign of $f(p_3) \cdot f(p_2)$ determines whether we use $p_2$ and $p_3$ or $p_3$ and $p_1$ to compute $p_4$. In the latter case a relabeling of $p_2$ and $p_1$ is performed. The relabeling ensures that the root is bracketed between successive iterations. The process is described in Algorithm 2.5, and Figure 2.11 shows how the iterations can be determined from those of the Secant method. In this illustration, the first three approximations are the same, but the fourth approximations differ.  

False Position

To find a solution to $f(x) = 0$ given the continuous function $f$ on the interval $[p_0, p_1]$ where $f(p_0)$ and $f(p_1)$ have opposite signs:  

INPUT initial approximations $p_0, p_1$; tolerance $TOL$; maximum number of iterations $N_0$.  

OUTPUT approximate solution $p$ or message of failure.  

• Step 1 Set $i = 2$,  \[q_0 = f(p_0); \quad q_1 = f(p_1).\]
• Step 2 While $i \leq N_0$ do Steps 3–7.  
• Step 3 Set\[p = p_1 - q_1 \frac{(p_1 - p_0)}{(q_1 - q_0)}. \quad \text{(Compute $p_i$.)}\]
• Step 4 If $|p - p_1| < TOL$ then 
  OUTPUT $(p;$ The procedure was successful.) 
  STOP.  
• Step 5 Set $i = i + 1$;  \[q = f(p).\]
• Step 6 If $q \cdot q_1 < 0$ then set $p_0 = p_1$;  \[q_0 = q_1.\]
• Step 7 Set $p_1 = p$;  \[q_1 = q.\]
• Step 8 OUTPUT (‘Method failed after $N_0$ iterations, $N_0 =$’, $N_0$; The procedure unsuccessful.) 
  STOP

Use the method of False Position to find a solution to $x = \cos x$, and compare the approximations with those given in Example 1 which applied fixed-point iteration and Newton’s method, and to those found in Example 2 which applied the Secant method.  

Solution To make a reasonable comparison we will use the same initial approximations as in the Secant method, that is, $p_0 = 0.5$ and $p_1 = \pi/4$. Table 2.6 shows the results of the method of False Position applied to $f(x) = \cos x - x$ together with those we obtained using the Secant and Newton’s methods. Notice that the False Position and Secant approximations agree through $p_3$ and that the method of False Position requires an additional iteration to obtain the same accuracy as the Secant method.  

The added insurance of the method of False Position commonly requires more calculation than the Secant method, just as the simplification that the Secant method provides over Newton’s method usually comes at the expense of additional iterations