Bisection Method with Scilab

The Bisection Method

     Suppose $f$ is a continuous function defined on the interval $[a, b]$, with $f(a)$ and $f(b)$ of opposite sign. The Intermediate Value Theorem implies that a number p exists in (a, b) with $f( p) = 0$. Although the procedure will work when there is more than one root in the interval $(a, b)$, we assume for simplicity that the root in this interval is unique. The method calls for a repeated halving (or bisecting) of subintervals of $[a, b]$ and, at each step, locating the half containing p.

Algorithm

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

INPUT endpoints a, b; tolerance TOL; maximum number of iterations $N_0$.

STEP 1 Set $i = 1$
                     $FA = f(a)$.

STEP 2 While $i \le N_0$ do Steps 3-6.

        STEP 3 Set $p = a + (b - a)/2$
                               $FP = f(p)$

        STEP 4 If $FP = 0$ or $(b-a)/2 < TOL$ then
                         STOP
                     else OUTPUT(P)
                   
        STEP 5 Set $i = i + 1$

       STEP 6 If $FA \times FP > 0$ then set $a = p$;
                          $FA = FP$
                     else set $b = p$.

STEP 7 Display("Method failed after $N_0$")

Sample Problem:

Show that $f(x) = x^3 + 4x^2 - 10 = 0$ has a root in $[1, 2]$, and use the Bisection method to determine an approximation to the root that is accurate to at least within $10^-4$.

Solution: Because $f(1) = -5$ and $f(2) = 14$ the Intermediate Value Theorem ensures that this continuous function has a root in $[1, 2]$.

For the approximation, see the outpout below:

    n       $a_n$                   $b_n$                $p_n$                   $f(p_n)$

    1.      1.                   2.                  1.5                  2.375    
    1.      1.                   2.                  1.5                  2.375    
    2.      1.                   1.5                1.25                - 1.796875
    3.      1.25               1.5                1.375              0.1621094
    4.      1.25               1.375            1.3125            - 0.8483887
    5.      1.3125           1.375            1.34375          - 0.3509827
    6.      1.34375         1.375            1.359375        - 0.0964088
    7.      1.359375       1.375            1.3671875      0.0323558
    8.      1.359375       1.3671875    1.3632812      - 0.0321500
    9.      1.3632812     1.3671875    1.3652344      0.0000720
    10.    1.3632812     1.3652344    1.3642578      - 0.0160467
    11.    1.3642578     1.3652344    1.3647461      - 0.0079893
    12.    1.3647461     1.3652344    1.3649902      - 0.0039591
    13.    1.3649902     1.3652344    1.3651123      - 0.0019437

Scilab Code:

clear
clc

function f = f(x)
    f = x^3 + 4*x^2 - 10
endfunction


disp("Sample input: bisectionMethod(1,2,10^-4, 100)")

function bisectionMethod(a,b,TOL,N)
    i = 1
    FA = f(a)
    finalOutput = [i, a, b, a + (b-a)/2, f(a + (b-a)/2)]
    
    disp("   n      a_n          b_n          p_n         f(p_n)")
    
    while(i <= N), 
        p = a + (b-a)/2
        FP = f(p)
        
        if(FP == 0 | (b-a)/2 < TOL) then
            break
        else
             finalOutput = [finalOutput; i, a, b, p, f(p)]
        end
        
        i = i + 1
        
        if(FA*FP > 0) then
            a = p
        else
            b = p
        end
    end
    
    disp(finalOutput)
    
endfunction

Final Note: 

The Bisection method, though conceptually clear, has significant drawbacks. It is relatively
slow to converge (that is, N may become quite large before $| p − p_N|$ is sufficiently
small), and a good intermediate approximation might be inadvertently discarded. However,
the method has the important property that it always converges to a solution, and for that
reason it is often used as a starter for the more efficient methods