Bisection method is used for finding root of the function in given interval.
Algorithm:
IN: Function f, which is continous function and interval [a,b]. Function must satisfy given equation: f(a) * f(b) < 0 - signs of that values are different, which means that given function in given interval has at least one root in interval [a,b]. OUT: Root in given interval. 1. Calculate c - midpoint of given interval using formula: c = (a + b) / 2. 2. Calculate f(c). 3. If b - a is small enough or abs(f(c)) is small enough: return c - which is the root we were searching for; 4. If(f(a) * f(c) < 0) assign c to b, else assign c to a. 5. Go to step 1.
Step By Step:
Sample Output:
f(x) = x * (x * (x * (x * (x)) + 2)) - 2 [0,2] root: 0.8515625
Bisection Method Step By Step
Iteration Number | a | c | b | f(cn) |
---|---|---|---|---|
1 | 0 | 1 | 2 | 1 |
2 | 0 | 0.5 | 1 | -1.4375 |
3 | 0.5 | 0.75 | 1 | -0.55859375 |
4 | 0.75 | 0.875 | 1 | 0.117431640625 |
5 | 0.75 | 0.8125 | 0.875 | -0.2438812255859375 |
6 | 0.8125 | 0.84375 | 0.875 | -0.0693502426147461 |
7 | 0.84375 | 0.859375 | 0.875 | 0.022470533847808838 |
8 | 0.84375 | 0.8515625 | 0.859375 | -0.023827489465475082 |
Pros:
- easy to implement.
- no need to calculate derivative of given function.
Cons:
- slow compared to other methods.