You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@commons.apache.org by Matt Cliff <ma...@mattcliff.com> on 2003/11/11 23:50:18 UTC
[math] Numerical Derivative pattern q.
I have been scratching out an implementation of a numerical derivative to
add to the commons-math and keep going back and forth between two
approaches.
(all this would be in the o.a.c.math.analysis package)
(for brevity I have omitted the prefix UnivariateReal* )
--------------------------------------------------------------------
(1) a couple classes like Differentiator (interface) and
DifferentiatorFactory (class), where we have a method like
"Differentiator DifferentiatorFactory.getDefaultDifferentiator(
Function f )"
and another method like "double Differentiator.derivate( double x)"
or "double Differentiator.value(double x)"
this keeps the same type of pattern as that of the *Solver
OR
(2) Add a class like DerivativeFactory which has a method like
"Function DerivativeFactory.getDefaultDerivative( Function f )"
and use the existing "double Function.value( double x)" to obtain the
numerical estimate.
I first implemented it using approach (1) but as the code and usage
turned out, it seems that (2) was easier to use (and numerically has the
same number or operations and function evaluations).
----------------------------------------------------------------------
using (2) the client code would look like
public myMethod() {
UnivariateRealFunction f = new SomeUserDefinedFunction();
UnivariateRealFunction fprime =
DerivativeFactory.newInstance().getDefaultDerivative( f );
System.out.println( "f'(1.0) = "+ fprime.value(1.0) );
}
-------------------------------------------------------------------------
of course the Factory could allow for multiple types of Derivatives, the
one I have currently implemented is a centered 5-point algorithm, which
has an operational parameter of h (or a step-size), there may also be
parameters to handle "infinite" derivative or jumps.
--
Matt Cliff
Cliff Consulting
The label said install Windows 98 or better so I installed Linux.
---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org
Re: [math] Numerical Derivative pattern q.
Posted by "Mark R. Diggory" <md...@latte.harvard.edu>.
Matt Cliff wrote:
> The numerical root solving methods are completely independant of the
> numerical derivative routines.
>
> This doesnt quite make sense to me. The Solver implemenations are Root
> solver routines which address the question of which value for x exists
> between (min,max) such that f(x) = 0.
>
On a programmatic level its even more abstract than that A solver simply
is solving for UnivariateRealFunction.value(double d) so the function
you could be solving for could represent a Cubic or Polynomial or a
derivative of that Cubic/Polynomial.
Now I think I'm grasping this better, in your case, you do not actually
have an analytical solution for what we are identifying as the functions
getFirstDerivative or getSecondDerivative.
> The numerical derivative routines estimate the value of the limit of
> (f(x+h)-f(x))/h as h approaches 0.
>
> I dont understand why (or how) a Bisection Solver routine would address
> the question of approximating the derivative of a function at a point.
>
No, this just me misinterpreting the problem. I went back and reviewed
Numerical Derivations And understand I misinterpreted you.
>
> How would the BisectionSolver be related to an estimate for the
> Derivative?
>
Ignore that from algorithm standpoint, lets think more about how
Numerical Derivation fits into or existing infrastructure.
> I was thinking along the lines of having an implementation of a
> numerical derivative solver that take a function and a value of h as a
> parameter and return a function. something like
> ----------------------------------------------------
> public class DefaultForwardDerivative {
> private Function f = null;
> private double h = 0.0;
> public DefaultForwardDerivative( Function f, double h ) {
> this.f = f;
> this.h = h;
> }
>
> // this should also have some upper limit on the
> // absolute value of the return function
> // so we dont introduce singularities
> public double value( double x ) throws MathException {
> double y0 = f.value( x );
> double y1 = f.value( x + h);
>
> return (( y1 - y0 ) / h);
> }
>
> }
Yes, this fits in very well architecturally with the idea Brent is
discussion about "decorator" functions. Is this an implementation of
UnivariateRealFunction?
> --------------------------------------------------
>
> A Factory could be placed in front to pull this or a backward (use -h
> value), or centered, or multi-point estimate for the derivative. The
> factory would hide the 'h' value with some default.
>
> The second (or higher) derivative could be obtained as follows
>
> ------------------------------------
> DerivativeFactory factory = DeriviateFactory.getInstance();
>
> Function f = new SomeUserFunction();
> Function g = factory.derivative( f );
> Function h = factory.deritivate( g );
Is this factory.derivative vs. factory.deritivate a typo or intentional?
Are these both t he same method?
>
> ------------------------------------
> In this example, f' = g, and g' = h, and f'' = h...
>
>
I agree with Brent that these should be "Decorators" or Functions that
wrap another function. Much in the way your suggesting yourself. I think
there should be a means of making the code thats going to be Numerically
approximating this solution more transparent to the user. Take for
instance our current "Solver" strategy. Maybe solvers should just be
"Functions" in and of themselves. This means that a Solver would look
more like this:
UnivariateRealSolver solver =
UnivariateRealSolverFactory.newInstance().newSecantSolver(somefunction);
/* this factory instantiation pattern is a little verbose */
solver.setMin(...);
solver.setMax(...);
solver.setStartingPoint(...);
double d = solver.value(x); /*where x = 0 or any other value you want to
solve for.*/
But, lets try not to let the "Factory" design pattern get in the way
here. Lets look at your above example and rework it without factory
pattern, just using constructors this would look like this (I changed
the variables so I can use "h" again.
Function e = new SomeUserFunction();
Function f = new CenteredDerivative();
f.setFunction(e);
Function g = new CenteredDerivative();
g.setFunction(f);
double result = g.value(x);
then calling g.value(x) would use Centered approaches to Numerically
estimate e'' = g.
So for:
(f(x+h)-f(x))/h
you would need to set a property of the "CenteredDerivative" that may be
adjusted. I suspect this property is actually setting the starting "h"
value? This could be done, as a property, or in the constructor, but I
would approach the initial implementations very much as beans.
double h = ...;
Function e = new SomeUserFunction();
Function f = new CenteredDerivative();
f.setFunction(e);
f.setInterval(h);
Function g = new CenteredDerivative();
g.setFunction(f);
g.setInterval(h);
double result = g.value(x);
Then you'd use a factory to set this "globally" or "transparently" to
the user.
DerviativeFactory factory = DerviativeFactory.newInstance();
factory.setInterval(0.5);
Function e = new SomeUserFunction();
Function f = DerviativeFactory.newCenteredDerivative(e);
Function g = DerviativeFactory.newCenteredDerivative(f);
double result = g.value(x);
Then the factory becomes a wrapper that simply constructs beans and sets
their properties. The user can use the factory or the beans directly.
This is the same way that allot of factory api's do work, for instance
in SAX or JAXP you could instantiate the XMLReaders, Transformers,
Documents by hand (which may be tedious for some, but necessary for
others) or you can use the Factory to instantiate an object with a bunch
of predetermined defaults. Currently this is the way much of the stats
package is working.
So yes, in your first email I would approach (2) over (1) and I would
recommend that Solvers go in the same direction and have solvers be
Functions too. But I would also recommend first approaching the actual
"Derivative Functions" as Beans that can be instantiated and configured
easily using properties and default constructors. Then the Factories are
more flexible and less restrictive to advanced users.
>
> On Tue, 11 Nov 2003, Mark R. Diggory wrote:
>
>
>>Bear with me, I'm trying to catchup a little bit here.
>>
>>My first thought here is, how is calling Function.value(x) different
>>from calling Function.firstDerivative(x)? We don't really implement a
>>"Evaluator" or "EvaluatorFactory" for returning a function's
>>Function.value(x). We only provide Solvers and Solver factories for
>>different ways of Numerically solving the Functions value(x) method for 0.
>>
>>Will a Differentiator/Factory be solving for the derivative? In which
>>case, as the algorithms used are really already implemented in the
>>solvers, wouldn't we just expand them with methods that allow us to
>>solve for the derivatives? For Example:
>>
>>UnivariateRealSolver bs = new BisectionSolver(...);
>>
>>double d = bs.solveFirstDerivative(min,max);
>>
>>and
>>
>>double d = bs.solveSecondDerivative(min,max);
>>
>>-Mark
>>
>>Matt Cliff wrote:
>>
>>>I have been scratching out an implementation of a numerical derivative to
>>>add to the commons-math and keep going back and forth between two
>>>approaches.
>>>
>>> (all this would be in the o.a.c.math.analysis package)
>>> (for brevity I have omitted the prefix UnivariateReal* )
>>>--------------------------------------------------------------------
>>> (1) a couple classes like Differentiator (interface) and
>>>DifferentiatorFactory (class), where we have a method like
>>> "Differentiator DifferentiatorFactory.getDefaultDifferentiator(
>>>Function f )"
>>>
>>> and another method like "double Differentiator.derivate( double x)"
>>> or "double Differentiator.value(double x)"
>>>
>>>
>>> this keeps the same type of pattern as that of the *Solver
>>>
>>>OR
>>>
>>> (2) Add a class like DerivativeFactory which has a method like
>>> "Function DerivativeFactory.getDefaultDerivative( Function f )"
>>>
>>> and use the existing "double Function.value( double x)" to obtain the
>>>numerical estimate.
>>>
>>>
>>> I first implemented it using approach (1) but as the code and usage
>>>turned out, it seems that (2) was easier to use (and numerically has the
>>>same number or operations and function evaluations).
>>>
>>>
>>>
>>>
>>>----------------------------------------------------------------------
>>>using (2) the client code would look like
>>>
>>>public myMethod() {
>>> UnivariateRealFunction f = new SomeUserDefinedFunction();
>>>
>>> UnivariateRealFunction fprime =
>>> DerivativeFactory.newInstance().getDefaultDerivative( f );
>>>
>>> System.out.println( "f'(1.0) = "+ fprime.value(1.0) );
>>>}
>>>
>>>
>>>-------------------------------------------------------------------------
>>>
>>> of course the Factory could allow for multiple types of Derivatives, the
>>>one I have currently implemented is a centered 5-point algorithm, which
>>>has an operational parameter of h (or a step-size), there may also be
>>>parameters to handle "infinite" derivative or jumps.
>>>
>>>
>>>
>>
>>
>
--
Mark Diggory
Software Developer
Harvard MIT Data Center
http://osprey.hmdc.harvard.edu
---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org
Re: [math] Numerical Derivative pattern q.
Posted by Matt Cliff <ma...@mattcliff.com>.
The numerical root solving methods are completely independant of the
numerical derivative routines.
This doesnt quite make sense to me. The Solver implemenations are Root
solver routines which address the question of which value for x exists
between (min,max) such that f(x) = 0.
The numerical derivative routines estimate the value of the limit of
(f(x+h)-f(x))/h as h approaches 0.
I dont understand why (or how) a Bisection Solver routine would address
the question of approximating the derivative of a function at a point.
How would the BisectionSolver be related to an estimate for the
Derivative?
I was thinking along the lines of having an implementation of a
numerical derivative solver that take a function and a value of h as a
parameter and return a function. something like
----------------------------------------------------
public class DefaultForwardDerivative {
private Function f = null;
private double h = 0.0;
public DefaultForwardDerivative( Function f, double h ) {
this.f = f;
this.h = h;
}
// this should also have some upper limit on the
// absolute value of the return function
// so we dont introduce singularities
public double value( double x ) throws MathException {
double y0 = f.value( x );
double y1 = f.value( x + h);
return (( y1 - y0 ) / h);
}
}
--------------------------------------------------
A Factory could be placed in front to pull this or a backward (use -h
value), or centered, or multi-point estimate for the derivative. The
factory would hide the 'h' value with some default.
The second (or higher) derivative could be obtained as follows
------------------------------------
DerivativeFactory factory = DeriviateFactory.getInstance();
Function f = new SomeUserFunction();
Function g = factory.derivative( f );
Function h = factory.deritivate( g );
------------------------------------
In this example, f' = g, and g' = h, and f'' = h...
On Tue, 11 Nov 2003, Mark R. Diggory wrote:
> Bear with me, I'm trying to catchup a little bit here.
>
> My first thought here is, how is calling Function.value(x) different
> from calling Function.firstDerivative(x)? We don't really implement a
> "Evaluator" or "EvaluatorFactory" for returning a function's
> Function.value(x). We only provide Solvers and Solver factories for
> different ways of Numerically solving the Functions value(x) method for 0.
>
> Will a Differentiator/Factory be solving for the derivative? In which
> case, as the algorithms used are really already implemented in the
> solvers, wouldn't we just expand them with methods that allow us to
> solve for the derivatives? For Example:
>
> UnivariateRealSolver bs = new BisectionSolver(...);
>
> double d = bs.solveFirstDerivative(min,max);
>
> and
>
> double d = bs.solveSecondDerivative(min,max);
>
> -Mark
>
> Matt Cliff wrote:
> > I have been scratching out an implementation of a numerical derivative to
> > add to the commons-math and keep going back and forth between two
> > approaches.
> >
> > (all this would be in the o.a.c.math.analysis package)
> > (for brevity I have omitted the prefix UnivariateReal* )
> > --------------------------------------------------------------------
> > (1) a couple classes like Differentiator (interface) and
> > DifferentiatorFactory (class), where we have a method like
> > "Differentiator DifferentiatorFactory.getDefaultDifferentiator(
> > Function f )"
> >
> > and another method like "double Differentiator.derivate( double x)"
> > or "double Differentiator.value(double x)"
> >
> >
> > this keeps the same type of pattern as that of the *Solver
> >
> > OR
> >
> > (2) Add a class like DerivativeFactory which has a method like
> > "Function DerivativeFactory.getDefaultDerivative( Function f )"
> >
> > and use the existing "double Function.value( double x)" to obtain the
> > numerical estimate.
> >
> >
> > I first implemented it using approach (1) but as the code and usage
> > turned out, it seems that (2) was easier to use (and numerically has the
> > same number or operations and function evaluations).
> >
> >
> >
> >
> > ----------------------------------------------------------------------
> > using (2) the client code would look like
> >
> > public myMethod() {
> > UnivariateRealFunction f = new SomeUserDefinedFunction();
> >
> > UnivariateRealFunction fprime =
> > DerivativeFactory.newInstance().getDefaultDerivative( f );
> >
> > System.out.println( "f'(1.0) = "+ fprime.value(1.0) );
> > }
> >
> >
> > -------------------------------------------------------------------------
> >
> > of course the Factory could allow for multiple types of Derivatives, the
> > one I have currently implemented is a centered 5-point algorithm, which
> > has an operational parameter of h (or a step-size), there may also be
> > parameters to handle "infinite" derivative or jumps.
> >
> >
> >
>
>
--
Matt Cliff
Cliff Consulting
303.757.4912
720.280.6324 (c)
The label said install Windows 98 or better so I installed Linux.
---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org
RE: [math] Numerical Derivative pattern q.
Posted by Brent Worden <br...@worden.org>.
>
> Will a Differentiator/Factory be solving for the derivative? In which
> case, as the algorithms used are really already implemented in the
> solvers, wouldn't we just expand them with methods that allow us to
> solve for the derivatives? For Example:
>
> UnivariateRealSolver bs = new BisectionSolver(...);
>
> double d = bs.solveFirstDerivative(min,max);
>
> and
>
> double d = bs.solveSecondDerivative(min,max);
>
> -Mark
I'm not too keen to the explicit method calls because it seems so limiting.
How about using decorators much like commons-collections? We could apply a
DerivativeFunctionDecorator which alters the Function.evaluate method to
return the derivate evaluation using center differences or something
similar. Then the decorated function could be used in the solvers or any
other place a Function object is accepted.
If someone wanted to solve for the second derivate, apply the decorator to
the original function twice.
Brent Worden
http://www.brent.worden.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org
Re: [math] Numerical Derivative pattern q.
Posted by "Mark R. Diggory" <md...@latte.harvard.edu>.
Bear with me, I'm trying to catchup a little bit here.
My first thought here is, how is calling Function.value(x) different
from calling Function.firstDerivative(x)? We don't really implement a
"Evaluator" or "EvaluatorFactory" for returning a function's
Function.value(x). We only provide Solvers and Solver factories for
different ways of Numerically solving the Functions value(x) method for 0.
Will a Differentiator/Factory be solving for the derivative? In which
case, as the algorithms used are really already implemented in the
solvers, wouldn't we just expand them with methods that allow us to
solve for the derivatives? For Example:
UnivariateRealSolver bs = new BisectionSolver(...);
double d = bs.solveFirstDerivative(min,max);
and
double d = bs.solveSecondDerivative(min,max);
-Mark
Matt Cliff wrote:
> I have been scratching out an implementation of a numerical derivative to
> add to the commons-math and keep going back and forth between two
> approaches.
>
> (all this would be in the o.a.c.math.analysis package)
> (for brevity I have omitted the prefix UnivariateReal* )
> --------------------------------------------------------------------
> (1) a couple classes like Differentiator (interface) and
> DifferentiatorFactory (class), where we have a method like
> "Differentiator DifferentiatorFactory.getDefaultDifferentiator(
> Function f )"
>
> and another method like "double Differentiator.derivate( double x)"
> or "double Differentiator.value(double x)"
>
>
> this keeps the same type of pattern as that of the *Solver
>
> OR
>
> (2) Add a class like DerivativeFactory which has a method like
> "Function DerivativeFactory.getDefaultDerivative( Function f )"
>
> and use the existing "double Function.value( double x)" to obtain the
> numerical estimate.
>
>
> I first implemented it using approach (1) but as the code and usage
> turned out, it seems that (2) was easier to use (and numerically has the
> same number or operations and function evaluations).
>
>
>
>
> ----------------------------------------------------------------------
> using (2) the client code would look like
>
> public myMethod() {
> UnivariateRealFunction f = new SomeUserDefinedFunction();
>
> UnivariateRealFunction fprime =
> DerivativeFactory.newInstance().getDefaultDerivative( f );
>
> System.out.println( "f'(1.0) = "+ fprime.value(1.0) );
> }
>
>
> -------------------------------------------------------------------------
>
> of course the Factory could allow for multiple types of Derivatives, the
> one I have currently implemented is a centered 5-point algorithm, which
> has an operational parameter of h (or a step-size), there may also be
> parameters to handle "infinite" derivative or jumps.
>
>
>
--
Mark Diggory
Software Developer
Harvard MIT Data Center
http://osprey.hmdc.harvard.edu
---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org