Approximate a derivative for a continuous function throughout certain step intervals

Question

I am looking to write a method in Java which finds a derivative for a continuous function. These are some assumptions which have been made for the method -

1. The function is continuous from x = 0 to x = infinity.
2. The derivative exists at every interval.
3. A step size needs to be defined as a parameter.
4. The method will find the max/min for the continuous function over a given interval [a:b].

As an example, the function cos(x) can be shown to have maximum or minimums at 0, pi, 2pi, 3pi, ... npi.

I am looking to write a method that will find all of these maximums or minimums provided a function, lowerBound, upperBound, and step size are given.

To simplify my test code, I wrote a program for cos(x). The function I am using is very similar to cos(x) (at least graphically). Here is some Test code that I wrote -

public class Test {
    public static void main(String[] args){
        Function cos = new Function () 
        {
        public double f(double x) {
        return Math.cos(x);
        }
    };

        findDerivative(cos, 1, 100, 0.01);      
    }

    // Needed as a reference for the interpolation function.
    public static interface Function {
    public double f(double x);
    }

     private static int sign(double x) {
    if (x < 0.0)
            return -1;
        else if (x > 0.0)
            return 1;
        else
            return 0;
    }

     // Finds the roots of the specified function passed in with a lower bound,
    // upper bound, and step size.
    public static void findRoots(Function f, double lowerBound,
                  double upperBound, double step) {
    double x = lowerBound, next_x = x;
    double y = f.f(x), next_y = y;
    int s = sign(y), next_s = s;

    for (x = lowerBound; x <= upperBound ; x += step) {
        s = sign(y = f.f(x));
        if (s == 0) {
        System.out.println(x);
        } else if (s != next_s) {
        double dx = x - next_x;
        double dy = y - next_y;
        double cx = x - dx * (y / dy);
        System.out.println(cx);
        }
        next_x = x; next_y = y; next_s = s;
    }
    }

    public static void findDerivative(Function f, double lowerBound, double 
            upperBound, double step) {
    double x = lowerBound, next_x = x;
    double dy = (f.f(x+step) - f.f(x)) / step;

    for (x = lowerBound; x <= upperBound; x += step) {
        double dx = x - next_x;
        dy = (f.f(x+step) - f.f(x)) / step;
        if (dy < 0.01 && dy > -0.01) {
            System.out.println("The x value is " + x + ". The value of the "
                    + "derivative is "+ dy);
            }
        next_x = x;
        }
    }   
}

The method for finding roots is used for finding zeroes (this definitely works). I only included it inside my test program because I thought that I could somehow use similar logic inside the method which finds derivatives.

The method for

public static void findDerivative(Function f, double lowerBound, double 
            upperBound, double step) {
    double x = lowerBound, next_x = x;
    double dy = (f.f(x+step) - f.f(x)) / step;

    for (x = lowerBound; x <= upperBound; x += step) {
        double dx = x - next_x;
        dy = (f.f(x+step) - f.f(x)) / step;
        if (dy < 0.01 && dy > -0.01) {
            System.out.println("The x value is " + x + ". The value of the "
                    + "derivative is "+ dy);
            }
        next_x = x;
        }
    }   

could definitely be improved. How could I write this differently? Here is sample output.

The x value is 3.129999999999977. The value of the derivative is -0.006592578364594814
The x value is 3.1399999999999766. The value of the derivative is 0.0034073256197308943
The x value is 6.26999999999991. The value of the derivative is 0.008185181673381337
The x value is 6.27999999999991. The value of the derivative is -0.0018146842631128202
The x value is 9.409999999999844. The value of the derivative is -0.009777764220086915
The x value is 9.419999999999844. The value of the derivative is 2.2203830347677922E-4
The x value is 12.559999999999777. The value of the derivative is 0.0013706082193754021
The x value is 12.569999999999776. The value of the derivative is -0.00862924258597797
The x value is 15.69999999999971. The value of the derivative is -0.002963251265619693
The x value is 15.70999999999971. The value of the derivative is 0.007036644660118885
The x value is 18.840000000000146. The value of the derivative is 0.004555886794943564
The x value is 18.850000000000147. The value of the derivative is -0.005444028885981389
The x value is 21.980000000000636. The value of the derivative is -0.006148510767989279
The x value is 21.990000000000638. The value of the derivative is 0.0038513993028788107
The x value is 25.120000000001127. The value of the derivative is 0.0077411191450771355
The x value is 25.13000000000113. The value of the derivative is -0.0022587599505241585

Oratory

Nit: Use Math.signum instead of your sign function. – Mefford

The findRoots algorithm is based off of rosettacode.org/wiki/Roots_of_a_function. I am only printing out those values for testing purposes. – Oratory

If you have a formula that can be differentiated analytically, you can use the analytical formula. – Kermanshah

If you are looking to write a method that will find all maximums or minimums provided a function, there is not need for the derivative, it's too expensive this way – Caraway

What is the alternative? The program would need to find all local maximums and minimums. The easiest way I can think of is through setting the derivative to zero. – Oratory

Answer 1

The main thing that I can see to improve performance in the case that f is expensive to compute, you could save the previous value of f(x) instead of computing it twice for each iteration. Also dx is never used and would always be equal to step anyway. next_x also never used. Some variable can be declare inside the loop. Moving the variable declarations inside improves readability but not performance.

public static void findDerivative(Function f, double lowerBound, double upperBound, double step) {
    double fxstep = f.f(x);

    for (double x = lowerBound; x <= upperBound; x += step) {
        double fx = fxstep;
        fxstep = f.f(x+step);
        double dy = (fxstep - fx) / step;
        if (dy < 0.01 && dy > -0.01) {
            System.out.println("The x value is " + x + ". The value of the "
                    + "derivative is " + dy);
        }
    }
}

Celina

Answer 2

The java code you based on (from rosettacode) is not OK, do not depend on it.

• it's expecting y (a double value) will become exactly zero.
  You need a tolerance value for such kind of tests.
• it's calculating derivative, and using Newton's Method to calculate next x value,
  but not using it to update x, there is not any optimization there.

Here there is an example of Newton's Method in Java

Yes you can optimize your code using Newton's method,
Since it can solve f(x) = 0 when f'(x) given,
also can solve f'(x) = 0 when f''(x) given, same thing.

Firework

Testing seemed to work fine. I haven't seen a better way of writing the findRoots() method. That doesn't work, I need to write it in the format of findRoots(function, integral start, integral end, step size). The method needs to find all of the zeroes inside a given interval. – Oratory

it seems working because it's using too many initial points, and stepping is adjusted for the problem, so one optimization iteration seems enough. Try bigger steps, it will produce wrong results. You can use same stepping logic, to give some initial points over the range to the real algorithm, it will converge much faster and will give correct results. – Firework

Answer 3

To clarify my comment, I modified the code in the link.
I used step = 2, and got correct results. Check how fast it's, compared to other.
That's why optimization is used,
otherwise reducing the step size and using brute force would do the job.

class Test {

    static double f(double x) {
        return Math.sin(x);
    }

    static double fprime(double x) {
        return Math.cos(x);
    }

    public static void main(String argv[]) {

        double tolerance = .000000001; // Our approximation of zero
        int max_count = 200; // Maximum number of Newton's method iterations

        /*
         * x is our current guess. If no command line guess is given, we take 0
         * as our starting point.
         */

        double x = 0.6;
        double low = -4;
        double high = 4;
        double step = 2;
        int inner_count = 0;

        for (double initial = low; initial <= high; initial += step) {
            x = initial;
            for (int count = 1; (Math.abs(f(x)) > tolerance)
                    && (count < max_count); count++) {
                inner_count++;
                x = x - f(x) / fprime(x);
            }

            if (Math.abs(f(x)) <= tolerance) {
                System.out.println("Step: " + inner_count + ", x = " + x);
            } else {
                System.out.println("Failed to find a zero");
            }
        }
    }

}

Firework

Unfortunately, I cannot apply similar logic in the program. I don't know the exact value of the derivative. – Oratory

You can change the fprime, return (Math.sin(x) - Math.sin(x+delta)) / delta, calculate the delta similar way or use a constant value, this constant delta may be very low (not important as it was in the code you found), because it doesn't need to use delta for stepping. Step and delta is serving different purposes here, step is for giving initial values to the algorithm, delta will be used to approximate the derivative. – Firework