Bisection Method

We'll start with one of the most basic algorithms to solve a root-finding problem. A root finding problem is finding the x such that f(x) = 0, for a given function f. The Bisection method is based on the Intermediate Value Theorem, that says there must exist at least one root on the interval (a,b) for f(x), if a and b have different signs and f(x) is continuous on the interval (a,b).
To begin set a1 = a and b1 = b, and let p1 be the midpoint of [a,b]: $$p_1 = \frac{a_1 + b_1}{2}$$ • if f(p1) and f(a1) have the same sign, set a2 = p1 and b2 = b1
• if f(p1) and f(b1) have the same sign, set b2 = p1 and a2 = a1

Keep iterating until f(pi) = 0 or |f(pi) - 0| < tolerance

Examples

Find a root for f(x) = x3 + x - 4 that agrees to the fifth decimal place

1st find an interval to begin iterations on

Find an interval on [a, b] where f(a) and f(b) have different signs
f(0) = -2 & f(2) = 6 so on [0, 2] using the Intermediate Value Theorem, we know there exists some value c for which f(c) = 0

Run Iterations until f(pi) = 0 or |f(pi) - 0| < tolerance

i ai bi pi f(pi)
1 0 2 1 -2
2 1 2 1.5 0.875
3 1 1.5 1.25 -0.796875
4 1.250000 1.500000 1.375000 -0.025391
17 1.378784 1.378815 1.378799 0.000018
18 1.378784 1.378799 1.378792 -0.000033

So after 18 iterations we found a root at 1.378792, so while simple to implement there are better algorithms that can be used.


Code for C++ 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
// Bisection Method
// Implementation for c++
// Code by Austin Wimberley

#include <bits/stdc++.h>
using namespace std;

static int counter = 1;

// Main function to find the root of
// MODIFY HERE TO IMPLEMENT FOR YOUR FUNCTION
double fun(double x) {
    double ans = pow(x, 3.0) + x - 4;
    return ans;
}

double applyFormula(double a, double b, double const TOL) {
    double p = (a+b) / 2;
    while (abs(fun(p)) > TOL && counter < 1000) {
        printf("%4d\t%10f\t%10f\t%10f\t%10f\n", counter++, a, b, p, fun(p));
        if (fun(a) > 0 && fun(p) > 0 || fun(a) < 0 && fun(p) < 0) {
            a = p;
        } else {
            b = p;
        }
        p = (a+b) / 2;
    }
    return p;
}

// Driver Function
int main()
{
    // MODIFY HERE FOR INITIAL INTERVAL AND TOLERANCE
    double a0 = 0.0;
    double b0 = 2.0;
    double const TOL = 0.00001;
    double ans = applyFormula(a0, b0, TOL);
    cout << "\nRoot found at " << ans;
    return 0;
}



Newton's Method