|
WebCab Functions v2.0 (J2SE Edition) |
|||||||||
| PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
| SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD | |||||||||
java.lang.Object | +--webcab.lib.math.equationsolver.EquationSolver
The Equation Solver class offers a range of procedures for finding the solutions
of (continuous) equations on one real variable. Formally, we find the value of the
real variable x, such that ƒ(x) = 0, to a given level of
precision.
Below we describe two important factors which will effects algorithm you choose to use will most likely be effected by the following two factors:
Bisection,
Secant, Ridders, Brent,
Regula-Falsi, Newton-Raphson,
and Fail-Safe Newton-Raphson) are offered
in two forms. One where the initial bracketing interval must be given and another where
the initial bracketing interval is not given by the user. For example algorithm if the
bracketing is handled internally then only the desired precision will be required to be
passed, whereas in the alternative version the bracketing interval end-points and the
maximum number of iterations will also need to be passed. In cases where the bracketing
interval cannot be found either by inspection or by the internal algorithms then the Newton-Raphson
approach should be applied since it only requires an initial starting point from which a solution
will be sort.
Newton-Raphson,
and Fail-Safe Newton-Raphson internally differentiate the function
being considered. The evaluation of the derivative can be expensive and hence the viability or these
two approaches over the others with be determined primarily by this factor.
The function is defined in the Function interface located
in the same package. The way to define a function is by implementing the
Function interface and defining the getValueAt
method, which should return the value at any point x on the real line.
The functionality provided within this class uses two basic techniques:
Below we list all the algorithms which are offered within this class:
bisection(double)
bisection(double, ...)
secant(double)secant(double, ...)brent(double)brent(double, ...)Secant method which is less efficient but more stable.regulaFalsi(double)
regulaFalsi(double, ...)
Secant method which is less efficient but more stable than the Secant method.
ridders(double)
ridders(double, ...)
newtonRaphson(double)
newtonRaphson(double, ...)
newtonRaphsonFailSafe(double)newtonRaphsonFailSafe(double, ...)By following the below steps you will be able to set the equation ƒ(x),
which you wish to solve and then select the algorithm which will return a solution:
setFunctionFor further details on exact how the equation is set we refer the reader to the
documentation of setFunction. In the following discussion we consider the
differences between the different algorithms which are offer and provide advice to the
user for the select for an appropriate algorithm.
| Constructor Summary | |
EquationSolver()
Creates an Equation Solver instance without registering a function. |
|
EquationSolver(Function instanceOfFunction)
Creates an Equation Solver instance and assigns to it the specified function. |
|
| Method Summary | |
double |
bisection(double precision)
Implements the Interval Bisection Method which will converge if the algorithm is able to find an initial bracketing interval. |
double |
bisection(double beginningOfInterval,
double endOfInterval,
double precision,
long maxIterations)
Offers Interval Bisection Method which is certain to converge once the initial bracketing interval is given. |
double |
brent(double precision)
Implements the Van Wijngaarden-Dekker-Brent Method the recommended approach in order to find the solution for a general one-dimensional function where the function's values only (and not its derivative or functional form) are available. |
double |
brent(double beginningOfInterval,
double endOfInterval,
double precision,
long maxIterations)
Implements the Van Wijngaarden-Dekker-Brent Method the recommended choice for general one-dimensional root finding where a function's values only (and not its derivative or functional form) are available. |
double |
newtonRaphson(double precision)
Implements the Newton-Raphson method where the initial point is taken to be the origin and the maximum number of iterations is 1,000. |
double |
newtonRaphson(double startingPoint,
double precision,
long maxIterations)
Implements the Newton-Raphson method where the initial point, maximum number of iterations and the precision are passed by the user. |
double |
newtonRaphsonFailSafe(double precision)
Implements the Fail-Safe Newton-Raphson Method with a zero initial value and the maximum number of Raphson-Newton steps being 1,000. |
double |
newtonRaphsonFailSafe(double beginningOfInterval,
double endOfInterval,
double precision,
long maxIterations)
Fail-Safe Newton-Raphson Method in which the initial point and maximum number of iterations must be given. |
double |
regulaFalsi(double precision)
Implements Regula Falsi (or Method of False Position) which is a variant of the secant method which is less efficient but more stable.
|
double |
regulaFalsi(double beginningOfInterval,
double endOfInterval,
double precision,
long maxIterations)
Implements Regula Falsi (or Method of False Position) which is a variant of the secant method which is less efficient
but more stable.
|
double |
ridders(double precision)
Implements Ridders' Method which is a powerful variant of the secant
method, without asking for an initial bracketing interval to be set.
|
double |
ridders(double beginningOfInterval,
double endOfInterval,
double precision,
long maxIterations)
Implements Ridders' Method which is a powerful variant of the secant
method. |
double |
secant(double precision)
Implements the Secant Method without the initial bracketing interval needing to be given. |
double |
secant(double beginningOfInterval,
double endOfInterval,
double precision,
long maxIterations)
Implements the Secant Method where the initial bracketing interval needs to be given. |
void |
setFunction(Function instanceOfFunction)
Submits a new function for analysis. |
| Methods inherited from class java.lang.Object |
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
| Constructor Detail |
public EquationSolver()
public EquationSolver(Function instanceOfFunction)
| Method Detail |
public void setFunction(Function instanceOfFunction)
Note: This method is not synchronized with the other methods (that is, it is not thread-safe).
In order to provide a function which is to be used within the algorithms
contained within this class you are required to implement the
Function interface. For further details concerning how this interface
is to be implemented (including source code) please see the documentation
accompanying the Function interface.
public double bisection(double precision)
throws EquationSolverException
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.
precision - The level of precision of a solution required before it is returned and the algorithm exists. That is, if the precision is set to 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.
setFunction, to the given level of precision
required or NaN if the algorithm fails to produce such a solution.
EquationSolverExceptionBisection - A more efficient implementation
of the Bisection algorithm but requires the user to provide an initial interval
over which the solution is sort.
public double bisection(double beginningOfInterval,
double endOfInterval,
double precision,
long maxIterations)
throws EquationSolverException
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.
beginningOfInterval - the coordinate value of the lower bound of the interval over which a solution to the equation is known to exist.endOfInterval - the coordinate value of the upper bound of the interval over which a solution to the equation is known to exist.precision - The level of precision of a solution required before it is returned and the algorithm exists. That is, if the precision is set to 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.maxIterations - The maximum number of iterations performed by the algorithm before the solution found will be returned. Note that the solution will be returned if either the precision of the solution has been reached or the number of iterations has been exceeded.
setFunction, to the given level of precision
required or NaN if the algorithm fails to produce such a solution.
EquationSolverExceptionBisection - A less efficient implementation of the Interval
Bisection algorithm which does not require the user to provide an interval.
public double secant(double precision)
throws EquationSolverException
Though the Secant method will bracket the root (i.e. [x1, x2]),
before being applied this bracketing does not ensure that the algorithm will
converge. However assuming that the algorithm converges this algorithm can be
very efficient and particularly applicable when the equation considered
exhibits linear characteristics.
The main idea behind this algorithm is to assume that the function is linear in the neighborhood of interest. We then use a linear approximation of the function and get an improved bound by replacing one of the bracketed bounds with the root of the linear equation in order to produce an interval which we hope is a smaller bracketing interval. After which we just then repeat this process until the solution has been found to a given level of accuracy or the maximum number of iterations has been exceeded.
Remark: This approach is closely related to the Newton-Raphson approach where the linear approximation takes the place of the derivative within the Newton-Raphson approach.
Formally, we use the following relationship to calculate successive approximations:
xn = xn-1 - ƒ(xn-1).(xn-1 - xn-2) / ƒ(xn-1) - ƒ(xn-2), for n > 2.
until the desired level of tolerance has been achieved.
Speed of Convergence: It can be shown that the order of convergence is the golden ratio 1.618..., so that:
limk → ∞ | ek+1 | ≈ c.| ek |1.618
where c is a constant and en is the order of error after n iterations.
The disadvantage with the secant method is that if the equation is insufficiently linear in the neighborhood of interest then the root may not lie within the bracketed region and hence the method will not always converge is such cases. However, when the equation being considered is linear in nature then the Secant method is a very efficient and robust approach to use.
precision - The level of precision of a solution required before it is returned and the algorithm exists. That is, if the precision is set to 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.
setFunction, to the given level of precision
required or NaN if the algorithm fails to produce such a solution.
EquationSolverExceptionSecant - Implementation of the Secant method which allows
the initial bracketing interval and the maximum number of iterations to be set.
public double secant(double beginningOfInterval,
double endOfInterval,
double precision,
long maxIterations)
throws EquationSolverException
Though the Secant method will bracket the root (i.e. [x1, x2]),
before being applied this bracketing does not ensure that the algorithm will
converge. However assuming that the algorithm converges this algorithm can be
very efficient and particularly applicable when the equation considered
exhibits linear characteristics.
The main idea behind this algorithm is to assume that the function is linear in the neighborhood of interest. We then use a linear approximation of the function and get an improved bound by replacing one of the bracketed bounds with the root of the linear equation in order to produce an interval which we hope is a smaller bracketing interval. After which we just then repeat this process until the solution has been found to a given level of accuracy or the maximum number of iterations has been exceeded.
Remark: This approach is closely related to the Newton-Raphson approach where the linear approximation takes the place of the derivative within the Newton-Raphson approach.
Formally, we use the following relationship to calculate successive approximations:
xn = xn-1 - ƒ(xn-1).(xn-1 - xn-2) / ƒ(xn-1) - ƒ(xn-2), for n ≥ 2.
until the desired level of tolerance has been achieved.
Speed of Convergence: It can be shown that the order of convergence is the golden ratio 1.618..., so that:
limk → ∞ | ek+1 | ≈ c.| ek |1.618
where c is a constant and en is the order of error after n iterations.
The disadvantage with the secant method is that if the equation is insufficiently linear in the neighborhood of interest then the root may not lie within the bracketed region and hence the method will not always converge is such cases. However, when the equation being considered is linear in nature then the Secant method is a very efficient and robust approach to use.
beginningOfInterval - the coordinate value of the lower bound of the interval over which a solution to the equation is known to exist.endOfInterval - the coordinate value of the upper bound of the interval over which a solution to the equation is known to exist.precision - The level of precision of a solution required before it is returned and the algorithm exists. That is, if the precision is set to 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.maxIterations - The maximum number of iterations performed before the result will be returned. If the method fails for a given level of precision you may need to increase the maximum number of iterations.
setFunction, to the given level of precision
required or NaN if the algorithm fails to produce such a solution.
EquationSolverExceptionSecant - Applies the Secant algorithm without the need to provide the initial
bracketing algorithm or maximum number of iterations.
public double ridders(double precision)
throws EquationSolverException
secant
method, without asking for an initial bracketing interval to be set.
This powerful variant on the Secant method was developed by C.J.F.Ridders in the article: Ridders, C.J.F. 1979, IEEE
Transactions on Circuits and Systems, vol. CAS-26, pp. 979-980}. The basic idea is to improve the initial bracketing
interval by the following procedure. If the root is bracketed between x1 and x2, Ridders'
method first evaluates function at the midpoint:
x3 = (x1 + x2)/2
Then we update our initial bracketed interval by:
x4 = x3 + (x3 - x1) . (sign[ƒ(x1)- ƒ(x2)]ƒ(x3))/(√{ƒ(x3)2 - ƒ(x1)ƒ(x2)}),
where sign[...] is the sign function and √{...} is the square root. The
new estimate x4 is guaranteed to lie in the bracketed interval and therefore this approach
can be seen as a variant of the bisection method.
The speed at which Ridders' method converges is given by:
limk → ∞ | ek+1 | ≈ c.| ek |√2,
where c is a constant, en is the order of the error after n iterations.
Ridders' method given an initial bracketing interval is certain to converge. Moreover, Ridders' method is a powerful variant of the Secant method which is most case is the preferred choice.
precision - The level of precision of a solution required before it is returned and the algorithm exists. That is, if the precision is set to 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.
setFunction, to the given level of precision
required or NaN if the algorithm fails to produce such a solution.
EquationSolverExceptionRidders - Offers Ridders' Method where you are able to set
the initial bracketing interval and the maximum number of iterations used.
public double ridders(double beginningOfInterval,
double endOfInterval,
double precision,
long maxIterations)
throws EquationSolverException
secant
method. This implementation allows the user to provide the initial bracketing interval and set the number of iterations,
in contrast with ridders which does not.
This powerful variant on the Secant method was developed by C.J.F.Ridders in the article: Ridders, C.J.F. 1979, IEEE
Transactions on Circuits and Systems, vol. CAS-26, pp. 979-980}. The basic idea is to improve the initial bracketing
interval by the following procedure. If the root is bracketed between x1 and x2, Ridders' method first evaluates
function at the midpoint:
x3 = (x1 + x2)/2
Then we update our initial bracketed interval by:
x4 = x3 + (x3 - x1) . (sign[ƒ(x1)-ƒ(x2)]ƒ(x3))/(√{ƒ(x3)2 - ƒ(x1)ƒ(x2)}),
where sign[...] is the sign function and √{...} is the square root. The
new estimate x4 is guaranteed to lie in the bracketed interval and therefore this approach
can be seen as a variant of the bisection method.
The speed at which Ridders' method converges is given by:
limk → ∞ | ek+1 | ≈ c.| ek |√2,
where c is a constant, en is the order of the error after n iterations.
Ridders' method given an initial bracketing interval is certain to converge. Moreover, Ridders' method is a powerful variant of the Secant method which is most case is the preferred choice.
beginningOfInterval - the coordinate value of the lower bound of the interval over which a solution to the equation is known to exist.endOfInterval - the coordinate value of the upper bound of the interval over which a solution to the equation is known to exist.precision - The level of precision of a solution required before it is returned and the algorithm exists. That is, if the precision is set to 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.maxIterations - The maximum number of iterations performed before the result will be returned. If the method fails for a given level of precision you may need to increase the maximum number of iterations.
setFunction, to the given level of precision
required or NaN if the algorithm fails to produce such a solution.
EquationSolverExceptionRidders - Applies Ridders' algorithm without the need to provide the initial bracketing
algorithm or maximum number of iterations.
public double brent(double precision)
throws EquationSolverException
Brent's method combines root bracketing, bisection, and inverse quadratic
interpolation to converge from the neighborhood of a zero crossing. While
the false position and secant methods assume approximately linear behavior
between two prior root estimates, inverse quadratic interpolation uses three
prior points to fit an inverse quadratic function (i.e. x as a quadratic
function of y) whose value at y = 0, is taken as the next estimate of the
root x. Of course one must have contingency plans in case the root falls
outside the bracketing interval, which Brent's method does by ensuring that
Bisection is applied at is very worst.
Brent's method combines the sureness of bisection
with the speed of a higher-order method when appropriate. It is recommended as the method of
choice for general one-dimensional root finding where a function's values
only (and not its derivative or functional form) are available.
precision - The level of precision of a solution required before it is returned and the algorithm exists. That is, if the precision is set to 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.
setFunction, to the given level of precision
required or NaN if the algorithm fails to produce such a solution.
EquationSolverExceptionBrent - An implementation of the Brent algorithm which
allows the initial bracketing interval and the maximum number of iterations to be set.
public double brent(double beginningOfInterval,
double endOfInterval,
double precision,
long maxIterations)
throws EquationSolverException
Brent's method combines root bracketing, bisection, and inverse quadratic
interpolation to converge from the neighborhood of a zero crossing. While
the false position and secant methods assume approximately linear behavior
between two prior root estimates, inverse quadratic interpolation uses three
prior points to fit an inverse quadratic function (i.e. x as a quadratic
function of y) whose value at y = 0, is taken as the next estimate of the
root x. Of course one must have contingency plans in case the root falls
outside the bracketing interval, which Brent's method does by ensuring that
Bisection is applied at is very worst.
Brent's method combines the sureness of bisection
with the speed of a higher-order method when appropriate. It is recommended as the method of
choice for general one-dimensional root finding where a function's values
only (and not its derivative or functional form) are available.
beginningOfInterval - the coordinate value of the lower bound of the interval over which a solution to the equation is known to exist.endOfInterval - the coordinate value of the upper bound of the interval over which a solution to the equation is known to exist.precision - The level of precision of a solution required before it is returned and the algorithm exists. That is, if the precision is set to 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.maxIterations - The maximum number of iterations performed before the result will be returned. If the method fails for a given level of precision you may need to increase the maximum number of iterations.
setFunction, to the given level of precision
required or NaN if the algorithm fails to produce such a solution.
EquationSolverExceptionBrent - Applies the Brent algorithm without the need to provide the initial bracketing
algorithm or maximum number of iterations.
public double regulaFalsi(double precision)
throws EquationSolverException
secant method which is less efficient but more stable.
Note that this implementation of Regula Falsi does not require an initial bracketing
interval is passed as a parameter.
The Regula-Falsi (or false position) method is based on the same
algorithm implemented by the secant method. The only difference between the
methods is that secant retains the most recent of the prior estimates; this
requires an arbitrary choice on the first iteration, while false position
retains that prior estimate for which the function value has opposite sign
from the function value at the current best estimate of the root, so that
the two points continue to bracket the root.
The term false position refers to the fact that the method can use an older rather than newer function evaluation and hence has a lower order of convergence than the Secant method. Since the newer function value will sometimes be kept, the method is often super-linear.
precision - The level of precision of a solution required before it is returned and the algorithm exists. That is, if the precision is set to 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.
setFunction, to the given level of precision
required or NaN if the algorithm fails to produce such a solution.
EquationSolverExceptionRegula-Falsi - Implements the Method of False Proposition
and allows the user to set the initial bracketing interval and the maximum number of iterations
used.
public double regulaFalsi(double beginningOfInterval,
double endOfInterval,
double precision,
long maxIterations)
throws EquationSolverException
secant method which is less efficient
but more stable.
The Regula-Falsi (or false position) method is based on the same
algorithm implemented by the secant method. The
only difference between the methods is that secant retains the most recent of the prior
estimates; this requires an arbitrary choice on the first iteration, while false position
retains that prior estimate for which the function value has opposite sign
from the function value at the current best estimate of the root, so that
the two points continue to bracket the root.
The term false position refers to the fact that the method can use an older rather than newer function evaluation and hence has a lower order of convergence. Since the newer function value will sometimes be kept, the method is often super-linear.
beginningOfInterval - the coordinate value of the lower bound of the interval over which a solution to the equation is known to exist.endOfInterval - the coordinate value of the upper bound of the interval over which a solution to the equation is known to exist.precision - The level of precision of a solution required before it is returned and the algorithm exits. That is, if the precision is set to 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, which requires 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.maxIterations - The maximum number of iterations performed before the result will be returned. If the method fails for a given level of precision you may need to increase the maximum number of iterations.
setFunction, to the given level of precision
required or NaN if the algorithm fails to produce such a solution.
EquationSolverExceptionRegula-Falsi - Applies the Regula-Falsi algorithm without the need to provide the initial
bracketing algorithm or maximum number of iterations.
public double newtonRaphson(double precision)
throws EquationSolverException
The Newton-Raphson method is the mostly widely used method for finding the roots of an equation of one real variable. The Newton-Raphson approach does not depend on bracketing the solution (unlike the other algorithms provided) and instead will locally approximate the equation by a linear equation and then solve this approximation which will provide the next point within the iterative sequence which will lead to a solution. The successful application of this approach will depend on:
Assuming that an initial starting point x0, from which a solution to an equation
ƒ(x)=0 has been given, the Newton-Raphson method will produce a sequence of points:
x0, x1, ..., xn,..., using the iterative formula:
xn+1 = xn - ƒ(xn) / ƒ'(xn),
where ƒ'(xn) is the derivative of the equation ƒ, evaluated at the point xn.
The idea behind the above formula is to draw the tangent to the curve at xn and then
trace this line down to the x-axis which will give us our next estimate of the solution
xn+1. By repeating this process the resulting sequence of points will converge to
a solution of the equation in question.
The Newton-Raphson method requires that the derivative is evaluated at a sequence of points and therefore often the viability of this approach will depend on how expensive it is to evaluate the derivative for the equation being considered. However, if the derivative is not particularly expensive to evaluate then the Newton-Raphson approach is generally a very efficient approach.
precision - The level of precision of a solution required before it is returned and the algorithm exists. That is, if the precision is set to 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 a precision of 0.00001, we require t ms; then using a precision of 0.001, will require 0.6t ms, and using a precision of 0.0000001, will require 1.4t.
setFunction(webcab.lib.math.equationsolver.Function), to the given level of
precision required or NaN if the algorithm fails to produce such a solution.
EquationSolverExceptionNewton-Raphson - Offers the Newton-Raphson method which allows
the initial point and the maximum number of iterations to be set.
public double newtonRaphson(double startingPoint,
double precision,
long maxIterations)
throws EquationSolverException
The Newton-Raphson method is the mostly widely used method for finding the roots of an equation of one real variable. The Newton-Raphson approach does not depend on bracketing the solution (unlike the other algorithms provided) and instead will locally approximate the equation by a linear equation and then solve this approximation which will provide the next point within the iterative sequence which will lead to a solution. The successful application of this approach will depend on:
Assuming that an initial starting point x0, from which a solution to an equation
ƒ(x)=0 has been given, the Newton-Raphson method will produce a sequence of points:
x0, x1, ..., xn,..., using the iterative formula:
xn+1 = xn - ƒ(xn) / ƒ'(xn),
where ƒ'(xn) is the derivative of the equation ƒ, evaluated at the point xn.
The idea behind the above formula is to draw the tangent to the curve at xn and then
trace this line down to the x-axis which will give us our next estimate of the solution
xn+1. By repeating this process the resulting sequence of points will converge to
a solution of the equation in question.
The Newton-Raphson method requires that the derivative is evaluated at a sequence of points and therefore often the viability of this approach will depend on how expensive it is to evaluate the derivative for the equation being considered. However, if the derivative is not particularly expensive to evaluate then the Newton-Raphson approach is generally a very efficient approach.
startingPoint - The starting point from which a solution of the equation considered is sort. As a rule of thumb this initial point ideally should be as close to the solution as possible.precision - The level of precision of a solution required before it is returned and the algorithm exists. That is, if the precision is set to 0.0001 then the result will be returned to within 0.0001 etc, assuming that a 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 when using a 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 require 1.4t.maxIterations - The maximum number of iterations performed before the result will be returned. If the method fails for a given level of precision you may need to increase the maximum number of iterations.
setFunction(webcab.lib.math.equationsolver.Function), to the given level of precision
required or NaN if the algorithm fails to produce such a solution.
EquationSolverExceptionNewton-Raphson - Applies the Fail-Safe Newton-Raphson method without the need to provide
the initial starting point or maximum number of iterations.
public double newtonRaphsonFailSafe(double precision)
throws EquationSolverException
This method combines the Interval Bisection method
and the Newton-Raphson method, by taking a bisection step
whenever the Newton-Raphson takes the solution off bounds or is not bracketing the
solution fast enough. This approach in many ways combines the best of the Bisection and
Newton-Raphson method and unlike the pure Newton-Raphson methods is certain to converge.
That is, assuming that the internal bisection method is able to bracket a solution once
it is called. For further details on the bisection algorithm we refer the reader
to the Bisection API Docs, below we provide further details
on the Newton-Raphson algorithm.
The Newton-Raphson method is the mostly widely used method for finding the roots of an equation of one real variable. The Newton-Raphson approach does not depend on bracketing the solution (unlike the other algorithms provided) and instead will locally approximate the equation by a linear equation and then solve this approximation which will provide the next point within the iterative sequence which will lead to a solution. The successful application of this approach will depend on:
Assuming that an initial starting point x0, from which a solution to an equation
ƒ(x)=0 has been given, the Newton-Raphson method will produce a sequence of points:
x0, x1, ..., xn,..., using the iterative formula:
xn+1 = xn - ƒ(xn) / ƒ'(xn),
where ƒ'(xn) is the derivative of the equation f, evaluated at the point xn.
The idea behind the above formula is to draw the tangent to the curve at xn and then
trace this line down to the x-axis which will give us our next estimate of the solution
xn+1. By repeating this process the resulting sequence of points will converge to
a solution of the equation in question.
As mentioned above the Fail Safe Newton-Raphson method in many ways offers a good balance between the speed of the Newton-Raphson method and the security of the bisection method. Though the method may not be as fast as a pure Newton-Raphson approach it is certain to converge once a bracketing interval has been established. As is the case with a pure Newton-Raphson approach it requires that the derivative is evaluated at a sequence of points and therefore often the viability of this approach will depend on how expensive it is to evaluate the derivative for the equation being considered. However, if the derivative is not particularly expensive to evaluate then this approach is ideal for those who want almost the speed of the Newton-Raphson approach with the security of convergence of the Bisection approach.
precision - The level of precision of a solution required before it is returned and the algorithm exists. That is, if the precision is set to 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.
setFunction, to the given level of precision
required or NaN if the algorithm fails to produce such a solution.
EquationSolverExceptionNewton-Raphson Fail Safe - Applies the Newton-Raphson method
where the initial point and the maximum number of iterations can be set.
public double newtonRaphsonFailSafe(double beginningOfInterval,
double endOfInterval,
double precision,
long maxIterations)
throws EquationSolverException
This method combines the Interval Bisection method
and the Newton-Raphson method, by taking a bisection step
whenever the Newton-Raphson takes the solution off bounds or is not bracketing the solution fast enough.
This approach in many ways combines the best of the Bisection and Newton-Raphson method and unlike the
pure Newton-Raphson methods is certain to converge. For further details on the bisection algorithm we
refer the reader to the Bisection API Docs, below we
provide further details on the Newton-Raphson algorithm.
The Newton-Raphson method is the mostly widely used method for finding the roots of an equation of one real variable. The Newton-Raphson approach does not depend on bracketing the solution (unlike the other algorithms provided) and instead will locally approximate the equation by a linear equation and then solve this approximation which will provide the next point within the iterative sequence which will lead to a solution. The successful application of this approach will depend on:
Assuming that an initial starting point x0, from which a solution to an equation ƒ(x)=0
has been given, the Newton-Raphson method will produce a sequence of points: x0, x1, ..., xn,...,
using the iterative formula:
xn+1 = xn - ƒ(xn) / ƒ'(xn),
where ƒ'(xn) is the derivative of the equation ƒ, evaluated at the point xn.
The idea behind the above formula is to draw the tangent to the curve at xn and then
trace this line down to the x-axis which will give us our next estimate of the solution
xn+1. By repeating this process the resulting sequence of points will converge to
a solution of the equation in question.
As mentioned above the Fail Safe Newton-Raphson method in many ways offers a good balance between the speed of the Newton-Raphson method and the security of the bisection method. Though the method may not be as fast as a pure Newton-Raphson approach it is certain to converge once a bracketing interval has been established. As is the case with a pure Newton-Raphson approach it requires that the derivative is evaluated at a sequence of points and therefore often the viability of this approach will depend on how expensive it is to evaluate the derivative for the equation being considered. However, if the derivative is not particularly expensive to evaluate then this approach is ideal for those who want almost the speed of the Newton-Raphson approach with the security of convergence of the Bisection approach.
beginningOfInterval - the coordinate value of the lower bound of the interval over which a solution to the equation is known to exist.endOfInterval - the coordinate value of the upper bound of the interval over which a solution to the equation is known to exist.precision - The level of precision of a solution required before it is returned and the algorithm exists. That is, if the precision is set to 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.maxIterations - The maximum number of iterations performed before the result will be returned. If the method fails for a given level of precision you may need to increase the maximum number of iterations.
setFunction, to the given level of precision
required or NaN if the algorithm fails to produce such a solution.
EquationSolverExceptionNewton-Raphson Fail Safe - Applies the Newton-Raphson method without the need to provide
the initial starting point or maximum number of iterations.
|
WebCab Functions v2.0 (J2SE Edition) |
|||||||||
| PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
| SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD | |||||||||