Interval Halving (Bisection)
An algorithm for halving the interval (Bisection):
- Think about the multiplication factor, 2.
- The final value of approximates the root, and it is in error by not more than
- The method may produce a false root if is discontinuous on .
>> format long e
ans = 0
ans = 1
- Example: Apply Bisection to
. http://siber.cankaya.edu.tr/ozdogan/NumericalComputations/mfiles/chapter1/demoBisect.m m-file: demoBisect.m
- Example: Bracketing the roots of the function,
. http://siber.cankaya.edu.tr/ozdogan/NumericalComputations/mfiles/chapter1/brackPlot.m m-file: brackPlot.m
- Now, try with a user (you!) defined function;
In both example, try with different intervals.
The bisection method for
, starting from
, using a tolerance value of 1E-4.
- To obtain the true value for the root, which is needed to compute the actual error
- A general implementation of bisection (http://siber.cankaya.edu.tr/ozdogan/NumericalComputations//mfiles/chapter1/bisect.m m-file: bisect.m)
- It is shown above how brackPlot can be combined with bisect to find a single root of an equation.
- The same procedure can be extended to find more than one root if more than root exists. Consider the code
Use an appropriate 'myFunction', a suggestion is sine function.
The root is (almost) never known exactly, since it is extremely unlikely that a numerical procedure will find the precise value of that makes exactly zero in floating-point arithmetic.
- The main advantage of interval halving is that it is guaranteed to work (continuous & bracket).
- The algorithm must decide how close to the root the guess should be before stopping the search (see Fig. 3.3).
The stopping criterion for a root-finding procedure should involve a tolerance on , as well as a tolerance on .
- This guarantee can be avoided, if the function has a slope very near to zero at the root.