On that page,
s is -1, the solution of
x3-x=0 to which this particular sequence {
cn} converges. It is not computed from
an,
bn, or
cn.
The bisection method is very simple -- and very, very slow. Suppose you want to find a point at which some function
f(x) is zero, and suppose you have found two points
a0 and
b0 such that
f(a0) and
f(b0) have different signs. That the function has different signs at these points means that
- The function has one or more zero between a0 and b0, or
- The function has one or more discontinuity between a0 and b0 where the function changes sign across the discontinuity, or
- Both of the above are true.
If the function is known to be continuous between points
a0 and
b0 the only possibility is option #1, that the function has one or more zeros between these points.
So how to use this method? Simple. Evaluate the function at the point halfway between
a0 and
b0. Call this halfway point
c0. There are three possibilities for
f(c0):
- f(c0)=0. You have found a solution!
- f(c0) has the same sign as f(a0). This means a zero exists between points c0 and b0. Simply repeat with a1=c0 and b1=b0.
- f(c0) has the same sign as f(b0). This means a zero exists between points a0 and c0. Simply repeat with a1=a0 and b1=c0.
The beauty of the midpoint method is that it will always find a point where the function changes sign. It never fails. More powerful methods such as Newton's method can and often do fail. Many zero-finding techniques employ multiple techniques, and many of them use the midpoint method as a method of last resort when all of the more powerful techniques fail.
That they use midpoint as a method of last resort suggests that the midpoint method has some flaws. It is
slow. Newton's method, when it converges, will typically double the number of significant digits in the answer with every step. Over three steps (log(10)/log(2) steps) are needed with midpoint method to add one significant digit to the answer. That is slow.
There is another flaw to the technique: You have to somehow find those initial points
a0 and
b0 before you even start applying the technique. If you cannot find such a pair of points you cannot even start using the midpoint method.
