Implements the Interval Bisection Method which will converge if the algorithm is able to find an initial bracketing interval.
0.0001 then the result will be returned to within 0.0001 etc, assuming that an solution to this level of accuracy is found within the maximum number of iterations allowed. A reasonable value to take for this parameter is 0.00001. For smaller values of the precision parameter the solution will be more precise however the procedure will require more iterations and hence time in order to find the solution to the desired level of accuracy. Generally speaking, if using if for the precision 0.00001, we require t ms; then using a precision of 0.001, will take 0.6t ms, and using a precision of 0.0000001, will take 1.4t.A solution of the equation set using SetFunction, to the given level of precision required or NaN if the algorithm fails to produce such a solution.
This algorithm finds a solution by bracketing the closest region over which
a solution is supposed to be found, and then iteratively subdividing the region
and selecting the subregion where the solution is to be found. The algorithm exits
if either the solution is found to within a given level of precision or it the algorithm
fails in which case it returns NaN.
Assuming that the initial interval (i.e. bracketing interval) constructed internally
by the algorithm contains a solution of the equation considered then the algorithm will
always converge. Recall that a bracketing interval [x, y], is an interval
where the evaluation of the equation considered at x and y,
has a different sign. Now since the equation is continuous we are certain
that there exits a solution within the interval since the sign of the
function is different at the end points.
Once we obtain a bracketed interval say (x1, x2), we
proceed to iteratively constructing smaller and smaller intervals in which a solution is known
to lay. This construction performs the following steps:
x1 and x2, and evaluate the
function considered at the midpoint.
x1, then we replace x1 with the midpoint,
in order to produce an smaller interval [midpoint, x2], in which a solution
is certain to exit.
x2, then we replace x2 with the midpoint,
in order to produce an smaller interval [x1, midpoint], in which a solution
is certain to exit.
[x1, midpoint], or [midpoint, x2] and so on. The algorithm exits if
either the length of the interval is less than the precision required
or the maximum number of iterations of this loop has been reached.
Note that either x1 or x2 will have the same sign as the equation
evaluated at the midpoint since x1 and x2 have different signs.
For this reason the end points of the constructed sub-interval in which
the solution exists (i.e. [x1, midpoint], or [midpoint, x2]) will
also have different signs. Moreover, since the equation evaluated at the
end-points of the sub-interval has different signs there must exist at
least a solution within the interval since the equation is continuous.
Since the length of the interval over which the solution is known to exists
halves after each iteration. After n iterations the solution is known to
lie within an interval of width εn where:
εn = | x1 - x2 | / 2n
Thus, we have:
n = log2 (| x2 - x1 | / ε),
where ε is the desired ending tolerance.
The Bisection approach is very stable in terms of the convergence and the speed at which the convergence takes place. In instances where stability and reliability of the algorithm are an absolute then the Bisection algorithm should be preferred over all the other algorithms provided.
EquationSolver Class | WebCab.COM.Math.EquationSolver Namespace | EquationSolver.Bisection Overload List | Bisection - A more efficient implementation of the Bisection algorithm but requires the user to provide an initial interval over which the solution is sort.