Re: Convert coefficients from interpolated newton-polynomial to c0 +c1*x + c2*x^2 + ... form

c.j[DOT]w wrote:
> Hello,
>
> I have interpolated x1..xi, y1..yi with a newton-polynomial, which gives me
>
> p = c0 + c1(x-x1) + c2(x-x1)(x-x2) + ...
>
> Now I want to comvert this polynomial to a polynomial of the form
>
> p = d0 + d1*x + d2*x^2 + d3*x^3 + ...
>
> What formula or algoritm can I use to convert the c0, c1... to d0, 
> d1..., to get the same polynominal?
>
> Thanks in advance,
> Carl

To simplify my copying from "Efficient Algorithms for Polynomial 
Interpolation and Numerical Differentiation", Math. of Comp., Vol. 24, 
No. 109, January 1970, pp. 185-190, I will assume

p(x) = c_0 + c_1 (x-x_0) + c_2 (x-x_0) (x-x_1) + ...

     = c_0 p_0 + c_1 p_1 + c_2 p_2 + ...

The algorithm given in the paper assumes you want an expansion around x, 
in your case you have x=0, so replace x by 0 in what is below. The 
following algorithm gives new c's which correspond to your d's.
With w_k = x - x_k, p_i starting equal to w_0 w_1 ... w_{i-1}, and n = 
the degree of the polynomial

c_0 = p(x) = \sum_{k=0}^{n} c_k p_k
for k = 1, n - 1
  for i = 1, n-k
    p_i = w_{k+i-1} p_{i-1} + p_i
    c_k = c_k + p_i c_{k+i}
  end for
end for

The code in http://mathalacarte.com/cb/mom.fcg/ya58 uses this algorithm.

Regards,
    Fred