Bisection Method Program In C

The Bisection method works by repeatedly dividing the interval and selecting a subinterval where the root of the given equation lies. This method is also called the Bolzano, Half Interval, or Binary Search methods. That is because it effectively narrows down the range by half to find the root of the equation. 

In simple terms, if a function f(x) is continuous on a closed interval [a,b], the values of f(a) and f(b) have opposite signs. It indicates that at least one real root of f(x) = 0 exists between a and b.

Here is a step-by-step outline of the Bisection Method algorithm:

1. Start the program.
2. Input the initial guesses X1 and X2 and the desired absolute error e for accuracy.
3. Compute the function values: f1 = f(X1) and f2 = f(X2) 
4. Check the signs of f1 and f2: 

• If f1 x f2 > 0, display an error message indicating incorrect initial guesses and go to step 11.

5. Compute the midpoint: X = (X1+X2)/2
6. Check for convergence:

• If ∣(X1-X2)/X∣ < e, print the value of X as the root and go to step 11.

7. Evaluate the function at the midpoint: f = f(X)
8. Update the interval:

• If f x f1 > 0, set X1 = X and f1 = f
• Otherwise, set X2 = X and f2 = f

9. Repeat: Go back to step 5.
10. Continue the loop until the desired accuracy is achieved.
11. Terminate the program.

Here’s the implementation of the above algorithm in code for Fx=x3-4x-9

/* Program to demonstrate the usage of the bisection method in C. */
#include <stdio.h>
#include <math.h>  // Include math.h for the fabs() function

// Function definitions
void bisect(float *mid_pt, float int_st, float int_end, int *iter_cnt);
double get_fun(double res);

int main()
{
    // Declaration of the variables
    int iter_cnt = 0, mx_iter_cnt;
    float mid_pt, int_st, int_end, err_all, root;

    printf("\nEnter the first starting point: ");
    scanf("%f", &int_st);
    printf("\nEnter the second ending point: ");
    scanf("%f", &int_end);

    // Declare the maximum number of iterations allowed
    printf("\nEnter the maximum number of iterations allowed: ");
    scanf("%d", &mx_iter_cnt);

    // Input the allowed error tolerance
    printf("Input the allowed error tolerance: ");
    scanf("%f", &err_all);

    // Check if the initial guesses are valid
    if (get_fun(int_st) * get_fun(int_end) >= 0)
    {
        printf("\nInvalid initial guesses. The function values at the endpoints must have opposite signs.\n");
        return 1;
    }

    // Call bisect() function to get the initial midpoint
    bisect(&mid_pt, int_st, int_end, &iter_cnt);

    // For loop to perform bisection iterations
    for (; iter_cnt < mx_iter_cnt; )
    {
        // Check if the function at int_st and mid_pt have opposite signs
        if (get_fun(int_st) * get_fun(mid_pt) < 0)
        {
            int_end = mid_pt; // Assign mid_pt to int_end
        }
        else
        {
            int_st = mid_pt; // Assign mid_pt to int_st
        }

        // Call bisect() to calculate the new midpoint
        bisect(&root, int_st, int_end, &iter_cnt);

        // Check if the error tolerance is met
        if (fabs(root - mid_pt) < err_all)
        {
            printf("\nThe approximated root is: %f\n", root);
            return 0;
        }

        mid_pt = root; // Update mid_pt for the next iteration
    }

    // If the loop completes without finding a root within the allowed error tolerance
   printf("The iterations are insufficient to find the root.\n");
    return 0;
}

// Function to calculate the midpoint and increment the iteration count
void bisect(float *mid_pt, float int_st, float int_end, int *iter_cnt)
{
    *mid_pt = (int_st + int_end) / 2; // Calculate the middle value
    ++(*iter_cnt); // Increment the iteration count
    printf("Iteration %d: %f\n", *iter_cnt, *mid_pt);
}

// Function to define the equation: f(x) = x^3 - 4x - 9
double get_fun(double res)
{
    return (res * res * res - 4 * res - 9);
}

Output:

Enter the first starting point: 2

Enter the second ending point: 3

Enter the maximum number of iterations allowed: 20
Input the allowed error tolerance: 0.001
Iteration 1: 2.500000
Iteration 2: 2.750000
Iteration 3: 2.625000
Iteration 4: 2.687500
Iteration 5: 2.718750
Iteration 6: 2.703125
Iteration 7: 2.710938
Iteration 8: 2.707031
Iteration 9: 2.705078
Iteration 10: 2.706055

The approximated root is: 2.706055


=== Code Execution Successful ===

How it works: 

1. Function Definitions:

• get_fun() calculates the function Fx=x3-4x-9.
• bisect() finds the midpoint of the interval and counts the iterations.

2. Main Flow:

• Input: The user provides the starting point, ending point, maximum iterations, and error tolerance.
• Initial Check: The program verifies if the function values at the starting and ending points have opposite signs (ensuring a root exists in the interval).

3. Iteration Loop:

• The loop runs until the maximum iteration count is reached.
• The interval is narrowed down based on the midpoint’s function value:

If f (start) x f( midpoint) < 0, update the end.

Otherwise, update the start.

• A new midpoint is calculated in each iteration.

Convergence Check:

• The root is printed if the difference between the new and previous midpoints is within the error tolerance.

Termination:

• A message indicates insufficient iterations if the loop completes without meeting the tolerance.

Now, let’s look at another example. 

The equation this time is: x3 + 3x - 5 = 0

#include <stdio.h>
#include <math.h>

// Function to evaluate the given equation
double bisect(double num)
{
    return (pow(num, 3) + 3 * num - 5);
}
int main()
{
    printf("\nDisplay the real roots of the given equation using the Bisection method:");
    printf("\nEquation: x^3 + 3x - 5 = 0\n");

    double x0, x1;
    printf("\nEnter the first approximation of the root: ");
    scanf("%lf", &x0);

    printf("\nEnter the second approximation of the root: ");
    scanf("%lf", &x1);

    int iterate;
    printf("\nInput the number of iterations you want to perform: ");
    scanf("%d", &iterate);

    int count = 1;
    double l1 = x0;
    double l2 = x1;
    double r, f1, f2;

    // Check if the initial guesses are roots
    if (bisect(l1) == 0.0)
    {
        r = l1;
        printf("\nThe root is: %lf\n", r);
        return 0;
    }
    else if (bisect(l2) == 0.0)
    {
        r = l2;
        printf("\nThe root is: %lf\n", r);
        return 0;
    }

    // Perform iterations to find the root
    while (count <= iterate)
    {
        f1 = bisect(l1);
        r = (l1 + l2) / 2.0;  // Midpoint of l1 and l2
        f2 = bisect(r);

        printf("\nIteration %d: Approximate root = %lf", count, r);

        // Check if the midpoint is sufficiently close to the root
        if (fabs(f2) < 1e-6)
        {
            break;
        }

        // Update the interval based on the sign of f1 and f2
        if (f1 * f2 < 0)
        {
            l2 = r;
        }
        else
        {
            l1 = r;
        }

        count++;
    }

    // Return the final approximate root
    printf("\n\nThe approximation of the root is: %lf\n", r);
    return 0;
}

Output:

Display the real roots of the given equation using the Bisection method:
Equation: x^3 + 3x - 5 = 0

Enter the first approximation of the root: 1

Enter the second approximation of the root: 2

Input the number of iterations you want to perform: 10

Iteration 1: Approximate root = 1.500000
Iteration 2: Approximate root = 1.250000
Iteration 3: Approximate root = 1.125000
Iteration 4: Approximate root = 1.187500
Iteration 5: Approximate root = 1.156250
Iteration 6: Approximate root = 1.140625
Iteration 7: Approximate root = 1.148438
Iteration 8: Approximate root = 1.152344
Iteration 9: Approximate root = 1.154297
Iteration 10: Approximate root = 1.153320

The approximation of the root is: 1.153320


=== Code Execution Successful ===

Similar to the last one, this program starts by taking two initial guesses where the function values have opposite signs, ensuring a root lies between them. The program then repeatedly calculates the midpoint of the interval and checks if the function value at the midpoint is close enough to zero. If not, it updates the interval based on the midpoint's function value sign and continues iterating until the desired accuracy or maximum iteration limit is reached. This systematic halving of the interval makes the Bisection method a reliable approach for finding roots of continuous functions.

Advantages:

• Simple and Easy to Implement: The Bisection method is straightforward and requires minimal computational resources.
• Guaranteed Convergence: If the function is continuous and the initial guesses bracket a root, it always converges to that root.
• Reliable for Continuous Functions: Works well when the function has opposite signs at the two initial guesses.

Disadvantages:

• Slow Convergence: The method can be slow, especially if the root is far from the initial guesses.
• Requires Bracketing: It needs two initial guesses that enclose a root, which may not always be easy to identify.‍
• Limited to One Root: The method only finds one root at a time, even if multiple roots exist within the interval.

In software development, students must learn how to code the Bisection method. The concepts of iterative algorithms, numerical methods and problem-solving in real life are introduced. The program understands that such algorithms improve code writing and critical thinking and gives great insight into how the software performs mathematical calculations and solves root problems, which are very important in developing a good software engineering background. To learn more and build a strong foundation, enroll into the CCBP Academy 4.0 program.

1. What is the Bisection Method?

The Bisection Method is a computational technique for approximating the root of a continuous function. It cuts the interval repeatedly and chooses a subinterval in that interval at which the function changes sign to help define a better root.

2. What are the conditions necessary for the application of the Bisection Method?

The method uses two first guesses, X0 and X1, where the function values at these points will always have opposite signs. Also, it is necessary that the function is continuous in the interval.

3. What is the Bisection Method, and how does it intervene?

The method involves the middle of the interval, computing the function at the middle of the interval and then modifying the interval depending on the sign of the function in the middle of the interval as compared to endpoints.

4. What are the drawbacks or disadvantages of the Bisection Method?

The Bisection Method is slow because it only cuts the interval in half in each iteration through the function. It also needs a starting guess to be selected such that the initial guess has to lie on either side of the root, and it also finds only one root at a time.

5. Can the Bisection Method be used for all types of functions?

No, the Bisection Method can only be used for continuous functions where the initial interval contains a root. It requires the function to have opposite signs at the two initial guesses and doesn’t work for functions with multiple roots or discontinuities in the interval.