Offers Interval Bisection Method which is certain to converge once the initial bracketing interval is given.
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.
Given a range in which a solution exists (i.e. a bracketing interval), the method finds the solution to an arbitrary degree of accuracy and/or algorithm iterations. The algorithm keeps shrinking the given interval until a specified precision range has been reached. The solution to the equation will be returned if either the solution has been found to the level of precision required or if the maximum number of iterations has been reached.
Recall that a bracketing interval [x, y], in which a solution is known
to lie 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 less efficient implementation of the Interval Bisection algorithm which does not require the user to provide an interval.