Root finding implementation in C#

[Schizoid Man]

Hi,

I'm trying to implement a root finding solver in C# using Newton's Methods
and Numerical Recipes as a reference for the algorithm, and I have the
algorithm part of the solver up and running.

My problem is that I'm not sure how I can use this solver for any generic
function that requires a one-dimensional solver. All the examples I have
seen on the web hard the function f(x) that is being solved. I would like to
re-use this same solver code applied to a large set of functions, each with
it's own combination of input parameters - the common theme being that they
all required a one-dimensional solver.

It looks using an abstract class is the way to go, but I was hoping that
someone could give me some ideas.

Thanks,
Schiz

 

[Arne Vajhøj]

I'm trying to implement a root finding solver in C# using Newton's
Methods and Numerical Recipes as a reference for the algorithm, and I
have the algorithm part of the solver up and running.

My problem is that I'm not sure how I can use this solver for any
generic function that requires a one-dimensional solver. All the
examples I have seen on the web hard the function f(x) that is being
solved. I would like to re-use this same solver code applied to a large
set of functions, each with it's own combination of input parameters -
the common theme being that they all required a one-dimensional solver.

It looks using an abstract class is the way to go, but I was hoping that
someone could give me some ideas.

I use delegate.

Very simple implementation.

..NET 1.1 way:

using System;

public class Solv
{
// Newtons formel for iterativ lignings løsning
private const double DELTA = 0.0000001;
public delegate double FX(double x);
public static double FindZero(FX f)
{
double x, xnext = 0;
do
{
x = xnext;
xnext = x - f(x) / ((f(x + DELTA) - f(x)) / DELTA);
} while(Math.Abs(xnext - x) > DELTA);
return xnext;
}
// simple trediegrads polynomium y=x^3+x-30 med en enkelt løsning x=3
public static double MyPoly(double x)
{
return x * x * x + x - 30;
}
// løs
public static void Main(string[] args)
{
Console.WriteLine(Solv.FindZero(MyPoly));
}
}

..NET 2.0 way:

using System;

public class Solv
{
// Newtons formel for iterativ lignings løsning
private const double DELTA = 0.0000001;
public delegate double FX(double x);
public static double FindZero(FX f)
{
double x, xnext = 0;
do
{
x = xnext;
xnext = x - f(x) / ((f(x + DELTA) - f(x)) / DELTA);
} while(Math.Abs(xnext - x) > DELTA);
return xnext;
}
// løs simple trediegrads polynomium y=x^3+x-30 med en enkelt
løsning x=3
public static void Main(string[] args)
{
Console.WriteLine(Solv.FindZero(delegate(double x) { return x *
x * x + x - 30; }));
}
}

..NET 3.5 way:

using System;

public class Solv
{
// Newtons formel for iterativ lignings løsning
private const double DELTA = 0.0000001;
public delegate double FX(double x);
public static double FindZero(FX f)
{
double x, xnext = 0;
do
{
x = xnext;
xnext = x - f(x) / ((f(x + DELTA) - f(x)) / DELTA);
} while(Math.Abs(xnext - x) > DELTA);
return xnext;
}
// løs simple trediegrads polynomium y=x^3+x-30 med en enkelt
løsning x=3
public static void Main(string[] args)
{
Console.WriteLine(Solv.FindZero((double x) => x * x * x + x -
30 ));
}
}

Arne

PS: The comments are in Danish, but the code should be selfexplaining.

 

[Schizoid Man]

It's hard to say, without a concise-but-complete code example to reference
that clearly illustrates how you've implemented your "solver". One
particularly important detail that's not clear in your post is just how
the "combination of input parameters" find their way to the function.

But, it seems likely that you could take advantage of anonymous methods in
the form of a lambda expression. A very simple example:

// A very simple "solver" method
int Method1(Func<int> func)
{
int i;

for (int j = 0; j < 10; j++)
{
i = func(j);
}

return i;
}

// A method that uses the "solver" method twice, each time with
// a different lambda expression to control the actual results
void Method2()
{
int i;

i = int.MaxValue;
Console.WriteLine("Result: {0}", Method1(x => i = Math.Min(i,
x)));

i = int.MinValue;
Console.WriteLine("Result: {0}", Method1(x => i = Math.Max(i,
x)));
}

This particular example also takes advantage of a "captured" variable ("i"
in "Method2()") to provide the lambda expression a store the current state
of the calculation.

This is just a simple example; lambda expressions, and anonymous methods
more generally, can be very powerful. It's just a matter of figuring out
how they fit into what you've already done. But without knowing what
you've already done, it's not possible to provide anything more specific
than that.

An abstract class could certainly work as well. But if you're just
dealing with a single function that has to be evaluated, the use of a
delegate type with a lamdba expression can accomplish the same behavior in
a simpler way.

Thanks for the very useful suggestions, Peter and Arne. It does look like
delegate is the way to go. Let's say I am trying to solve for a bond yield
given a bond price using Newton's method. The equation is of the form:

Bond Price = \sum_{n=0}^N \frac{C}{1 + y^n} + \frac{P}{1 + y^N}

and I want to solve for y given the Bond Price. If I have the following
method

public static double SolveNewton(FX f)
{
....
return answer;
}

How would I declare the delegate type and the lambda expression? I
understand Arne's post about declaring:

public delegate double FX(double x);

However to the function FX, I will still need to pass in the Bond object,
because in order to calculate the yield I still access to the Bond.N and
Bond.C properties.

Thanks,
Schiz

 

[Schizoid Man]

Schizoid Man wrote:

I use delegate.

Very simple implementation.

.NET 1.1 way:

using System;

public class Solv
{
// Newtons formel for iterativ lignings løsning
private const double DELTA = 0.0000001;
public delegate double FX(double x);
public static double FindZero(FX f)
{
double x, xnext = 0;
do
{
x = xnext;
xnext = x - f(x) / ((f(x + DELTA) - f(x)) / DELTA);
} while(Math.Abs(xnext - x) > DELTA);
return xnext;
}
// simple trediegrads polynomium y=x^3+x-30 med en enkelt løsning x=3
public static double MyPoly(double x)
{
return x * x * x + x - 30;
}
// løs
public static void Main(string[] args)
{
Console.WriteLine(Solv.FindZero(MyPoly));
}
}

.NET 2.0 way:

using System;

public class Solv
{
// Newtons formel for iterativ lignings løsning
private const double DELTA = 0.0000001;
public delegate double FX(double x);
public static double FindZero(FX f)
{
double x, xnext = 0;
do
{
x = xnext;
xnext = x - f(x) / ((f(x + DELTA) - f(x)) / DELTA);
} while(Math.Abs(xnext - x) > DELTA);
return xnext;
}
// løs simple trediegrads polynomium y=x^3+x-30 med en enkelt løsning
x=3
public static void Main(string[] args)
{
Console.WriteLine(Solv.FindZero(delegate(double x) { return x * x
* x + x - 30; }));
}
}

.NET 3.5 way:

using System;

public class Solv
{
// Newtons formel for iterativ lignings løsning
private const double DELTA = 0.0000001;
public delegate double FX(double x);
public static double FindZero(FX f)
{
double x, xnext = 0;
do
{
x = xnext;
xnext = x - f(x) / ((f(x + DELTA) - f(x)) / DELTA);
} while(Math.Abs(xnext - x) > DELTA);
return xnext;
}
// løs simple trediegrads polynomium y=x^3+x-30 med en enkelt løsning
x=3
public static void Main(string[] args)
{
Console.WriteLine(Solv.FindZero((double x) => x * x * x + x -
30 ));
}
}

Arne

PS: The comments are in Danish, but the code should be selfexplaining.

Hello Arne,

Thank you for the suggestions. I have implemented the Newton solver and am
trying to use delegate to call the solver, but am running into a problem. I
have implemented the solver exactly as you suggested above, and
independently tested it so that I at least know that it solves correctly.
The code looks like this:

class Program
{

public delegate double FX(double x);

public static void Main (string[] args)
{
Bond james;
james = new Bond(0.10, 2, 5); // Create a bond - this
constructor forces yield and price of zero
james.BondPrice = 95; // Set the bond price
// Solve for yield that will replicate the specified bond price
above
FX f = delegate(double x)
{
james.BondYield = x;
return BondPricer.PriceBond(james) - james.BondPrice;
};
double ans = NewtonMethod.SolveNewton(f);
Console.ReadLine();
}
}

However, when I try to compile this I get the following errors:
The best overloaded method match for
'BondPricingConsole.NewtonMethod.SolveNewton(BondPricingConsole.NewtonMethod.FX)'
has some invalid arguments
Argument '1': cannot convert from 'BondPricingConsole.Program.FX' to
'BondPricingConsole.NewtonMethod.FX'

The solver code is:

public class NewtonMethod
{

public delegate double FX(double x);

// Define h step for finite differences
private const double h = 1.0e-10;

public static double SolveNewton(FX f)
{
double x;
double xNext = 2;
do
{
x = xNext;
xNext = x - f(x) / ((f(x + h) - f(x)) / h);
} while (Math.Abs(xNext-x)>h);
return xNext;
}
}

Would appreciate any pointers (no pun intended).

Thanks,
Schiz

 

[Schizoid Man]

I'm trying to implement a root finding solver in C# using Newton's
Methods and Numerical Recipes as a reference for the algorithm, and I
have the algorithm part of the solver up and running.

My problem is that I'm not sure how I can use this solver for any generic
function that requires a one-dimensional solver. All the examples I have
seen on the web hard the function f(x) that is being solved. I would like
to re-use this same solver code applied to a large set of functions, each
with it's own combination of input parameters - the common theme being
that they all required a one-dimensional solver.

It looks using an abstract class is the way to go, but I was hoping that
someone could give me some ideas.

I use delegate.

Very simple implementation.

.NET 1.1 way:

using System;

public class Solv
{
// Newtons formel for iterativ lignings løsning
private const double DELTA = 0.0000001;
public delegate double FX(double x);
public static double FindZero(FX f)
{
double x, xnext = 0;
do
{
x = xnext;
xnext = x - f(x) / ((f(x + DELTA) - f(x)) / DELTA);
} while(Math.Abs(xnext - x) > DELTA);
return xnext;
}
// simple trediegrads polynomium y=x^3+x-30 med en enkelt løsning x=3
public static double MyPoly(double x)
{
return x * x * x + x - 30;
}
// løs
public static void Main(string[] args)
{
Console.WriteLine(Solv.FindZero(MyPoly));
}
}

.NET 2.0 way:

using System;

public class Solv
{
// Newtons formel for iterativ lignings løsning
private const double DELTA = 0.0000001;
public delegate double FX(double x);
public static double FindZero(FX f)
{
double x, xnext = 0;
do
{
x = xnext;
xnext = x - f(x) / ((f(x + DELTA) - f(x)) / DELTA);
} while(Math.Abs(xnext - x) > DELTA);
return xnext;
}
// løs simple trediegrads polynomium y=x^3+x-30 med en enkelt løsning
x=3
public static void Main(string[] args)
{
Console.WriteLine(Solv.FindZero(delegate(double x) { return x * x
* x + x - 30; }));
}
}

.NET 3.5 way:

using System;

public class Solv
{
// Newtons formel for iterativ lignings løsning
private const double DELTA = 0.0000001;
public delegate double FX(double x);
public static double FindZero(FX f)
{
double x, xnext = 0;
do
{
x = xnext;
xnext = x - f(x) / ((f(x + DELTA) - f(x)) / DELTA);
} while(Math.Abs(xnext - x) > DELTA);
return xnext;
}
// løs simple trediegrads polynomium y=x^3+x-30 med en enkelt løsning
x=3
public static void Main(string[] args)
{
Console.WriteLine(Solv.FindZero((double x) => x * x * x + x -
30 ));
}
}

Arne

PS: The comments are in Danish, but the code should be selfexplaining.

It seems that the problem is to do with how the delegate type FX is
declared. If I copy the NewtonMethod method to the same class as the calling
function, then it works perfectly. I'd appreciate any inputs on the delegate
declaration.

Thank you.

 

[Schizoid Man]

I use delegate.

Hello Arne,

I figured out the problem. The declaration

public delegate double FX(double x);

was made inside public class NewtonMethod. Moving the delegate declaration
outside of the class fixed my problem. However, I have another question that
perhaps you can help me with. If I implement a variety of solvers -
bisection, secant, Newton, Brent - then how would I handle the delegate
declaration?

Could I repeat the same double FX(double x) in every solver class? Or do I
need to name the delegate type differently for each solver class?

Thanks.

 

[Pavel Minaev]

The code looks like this:

class Program
    {

        public delegate double FX(double x);

        public static void Main (string[] args)
        {
            Bond james;
            james = new Bond(0.10, 2, 5);  // Create a bond - this
constructor forces yield and price of zero
            james.BondPrice = 95; // Set the bond price
            // Solve for yield that will replicate the specified bond price
above
            FX f = delegate(double x)
            {
                james.BondYield = x;
                return BondPricer.PriceBond(james) - james.BondPrice;
            };
            double ans = NewtonMethod.SolveNewton(f);
            Console.ReadLine();
        }
    }

However, when I try to compile this I get the following errors:
The best overloaded method match for
'BondPricingConsole.NewtonMethod.SolveNewton(BondPricingConsole.NewtonMetho d.FX)'
has some invalid arguments
Argument '1': cannot convert from 'BondPricingConsole.Program.FX' to
'BondPricingConsole.NewtonMethod.FX'

The reason is that you have two _different_ delegate types here named
FX. That they have the same signature is immaterial - C# uses nominal
equivalence for delegate types, not structural. So you can't cast one
to another, implicitly or explicitly. You can use "new" to create an
instance of a delegate type from a delegate of another compatible
type, but that introduces an extra indirection level at run-time.

The simplest way to work around this problem is to use the stock
generic delegate types declared in namespace System - Func<...> or
Action<...> - as needed. In your case, you could declare your function
as:

public static double SolveNewton(Func<double, double> f)

This uses System.Func<TArg, TResult>.

Otherwise (for example, if you're on .NET 2.0, which doesn't have
Func<...>), just declare a single delegate type outside classes, and
reuse that.

 

[Schizoid Man]

One approach would be for your solvers to exist within a single namespace,
and then declare the delegate type within that namespace, rather than in
each solver.

However, .NET has a good selection of generic delegate types that would be
useful here. Instead of declaring your own "delegate double FX(double x)"
type, you should just use the existing "Func<T, TResult>" delegate type,
with "double" as the type for both type parameters. Then you don't need
to declare a delegate type at all; you'd just use "Func<double, double>"
in your argument declarations for the solvers.

Thanks a lot, Peter. These suggestions are very helpful. I really appreciate
the help.

PS - I don't need help with the issue detailed in the first reply. I managed
to get the code to work.

 

[Schizoid Man]

One approach would be for your solvers to exist within a single namespace,
and then declare the delegate type within that namespace, rather than in
each solver.

However, .NET has a good selection of generic delegate types that would be
useful here. Instead of declaring your own "delegate double FX(double x)"
type, you should just use the existing "Func<T, TResult>" delegate type,
with "double" as the type for both type parameters. Then you don't need
to declare a delegate type at all; you'd just use "Func<double, double>"
in your argument declarations for the solvers.

Hi Pete,

I am a little uncertain on how to do this - could you paste a small code
snippet by any chance?

Thanks.

 

[Pavel Minaev]

I am a little uncertain on how to do this - could you paste a small code
snippet by any chance?

I have already done that in my last post to this thread. To repeat:

public static double SolveNewton(System.Func<double, double> f)
{ ... }