[Math] Algorithm to compute Newton polynomial derivative

derivativespolynomials

I'm unable to find a clean solution to this problem and hope someone here can help me.
Given a list of x-values: $x_0, x_1, x_2, … x_n$ and a value $x$, I want to determine the accompanying parts of each coefficient for the derivative of a Newton polynomial.

Given a Newton polynomial of degree 2, defined as:

$f(x) = a_0 + a_1(x – x_0) + a_2(x – x_0)(x – x_1) = a_0 + a_1x + a_1x_0 + a_2x^2 – a_2xx_0 – a_2xx_1 + a_2x_0x_1$

where the first derivative is given as:

$f'(x) = a_1 + 2a_2x – a_2x_0 – a_2x_1 = a_1 + a_2(2x – x_0 – x_1)$

If we have values $x_0 = 1, x_1 = 5$ with $x = 2$, the equation above changes to:

$f'(2) = a_1 + a_2(2(2) – (1) – (5)) = a_1 – 2a_2$

Hence, the values I'm interested in are 1 and -2, the values preceding the coefficients. I want to write a programming function (in C++) that will calculate these values for ANY input series $x_n$, ANY $x$ and ANY polynomial order/degree. So I want a function similar to this:

void firstDerivative(double input[], double x, int degree, double output[])
{
   // Code here
}

The function takes the input x-values (with a size of $degree$), the x-value we are interested in, and the output that takes the preceding values of the coefficients.

At the moment I' trying to figure this one out for the first derivative, but at the end I want the function to take an additional parameter with holds the derivative. So the function should be able to calculate these values for ANY derivative (first, second, etc).

Can anyone help me with this?

Best Answer

You compute the value of the polynomial at some point x as

p=a[n];
for k=n-1 downto 0 do
    p = p * (x-x[k]);
    p = p + a[k];
next k;
return p;

The direct, stepwise derivative of this algorithm is

dp = 0; p=a[n];
for k=n-1 downto 0 do
    dp = dp * (x-x[k]);
    dp = dp + p;
    p = p * (x-x[k]); 
    p = p + a[k];
next k
return p, dp
Related Question