Microworld: Method
of Bisection: (All-in-One)
Click the Hyperlink above
to visit the Microworld.
Author:
Kwok-Wai Mok (Munsang
College, Hong Kong)
Commentary by: James E. White
The
method of bisection is one of the simplest and most reliable ways to find
numerical solutions to equations.
Suppose
you want to solve an equation in the form: f(x) = 0 for x. We assume that
f is a continuous function on an interval of numbers [a, b]. Suppose also
that f(a) is a negative number and that f(b) is a positive number as in the
picture above. Then since f is continuous on the interval by assumption, we
may conclude that the graph crosses the x axis at some point (z,0). This means
that f(z) = 0, and z is a solution to the equation f(x) = 0.
Of
course, there may be many such solutions, but we are not greedy. We seek only
one. How
can we approximate it? The Bisection method gives a simple (foolproof) recipe.
If we bisect the interval [a,b] at the point m = (a+b)/2 then either
f(m) will be 0, or the sign of f(m) will be different from that of f(a) or
of f(b). In the first case, m would be a solution, so we would be done. And
in the second case, we have two possibilities. If f(m) > 0 then we begin
again with the interval [a, m] and we know that since f(a) and f(m) have different
signs, there is a solution in the smaller interval, [a,m]. On the other hand,
if f(m) < 0, then we begin again with [m, b] and we know again that since
f(m) and f(b) have different signs, there is a solution in that interval.
Since
the new interval has half the size of the original, we have now narrowed the
search for a root to a smaller interval. If we choose any tolerance e >
0 whatever, we know that after N steps (where 2^N * e > b-a) this process
will bring us to within tolerance e of a solution to the equation. It always
works!
This
Microworld makes use of a Database as Active Data Object. This means that
you do not have to have a database program to use these data bases, but you
should have the MS Access Database or the MS Access 97 Database
installed as a Data Source Name. So be sure that your setup is ready
to use them.
In
Windows 95/98/ME, just go to the Control Panel, and under ODBC Data Sources,
select the User DSN tab. If MS Access Database or MS Access
97 Database is already installed, you are all set! Otherwise, press the
Add... button, and double-click on the Microsoft Access Driver (*.mdb)
entry. Then, in the Data Source Name, type MS Access Database.
Return to the listing of MathwrightWeb Microworlds
| - James E. White, Ph.D. , Library Director, | ||
| author of this website, Mathwright 2000, MindScapes, | ||
| MathwrightWeb, and Mathwright32 |
