3

Suppose we have the polynomial $f(x)=x^3$. We can now interpolate it using the values: $$f(1)=1,f(2)=8,f(3)=27,...$$ Using only one value, we get a constant: $$f_1(x)=1,\;\{1,1,1,...\}$$ Now using two values, we can get a linear: $$f_2(x)=7x-6,\;\{1,8,15,...\}$$ Proceeding in a similar manner, we get the following: $$f_3(x)=6x^2-11x+6,\;\{1,8,27,58,...\}$$ $$f_4(x)=x^3,\;\{1,8,27,...\}$$ Obviously $f_n(x)$ for a polynomial $f(x)$ of degree $n-1$ will be same, now int he above case remaining interpolations at some point give incorrect values and taking these first values we have $\{1,15,58\}$ with sum $74$ We can also interpolate it using Lagrange interpolations: $$f(n)=\sum_{k=0}^{\infty}{}^{n-1}{\mathbb C}_{k}\Delta^kt_k\;,\Delta^{n+1}t_k:=\Delta^{n}t_{k+1}-\Delta^{n}t_{0}\;,\Delta^0t_n:=f(n)$$ Now when we interpolate it using Lagrange interpolation, we get $\Delta^kt_0$'s as $\{1,7,12,6\}$ and thus: $$f_1(x)=1{}^{x-1}{\mathbb C}_{0}=1\\ f_2(x)=f_1(x)+7{}^{x-1}{\mathbb C}_{1}=1+7x-7=7x-6\\ f_3(x)=f_2(x)+12{}^{x-1}{\mathbb C}_{2}=7x-6+6(x-1)(x-2)=6x^2-11x+6\\ f_4(x)=f_3(x)+6{}^{x-1}{\mathbb C}_{3}=6x^2-11x+6+(x-1)(x-2)(x-3)=x^3\\ $$ Now I was thinking of making the binomials into a polynomial for which I found that binomial coefficients have a direct relation to polynomials via Stirling Numbers of First Kind. Now I want to ask:

Also Lagrange method would be a little fast as we don't waste our time with matrices.

(Note that I am computing all this with a program (in a programming language) I am writing)

  • Is there a direct way of computing the incorrect terms' sum?
  • If not, then is this the best method for this approach? I think that maybe polynomial conversion would be necessary and we just find the values of function for each interpolations with subset of Lagrange coefficients via $\mathbb {{}^{n}C_r}$ and sum up incorrect values.
  • Is there a direct way of computing Stirling Numbers of first kind?

I need to find a method that should be ideal for large polynomials such as $f(x)=1+2x+3x^2+4x^3+...11x^{10}$ (at max maybe?).

RE60K
  • 17,716

1 Answers1

1

You can tabulate the correction terms once for all for the monomials $f(x)=1,x,x^2,x^3\cdots x^{10}$. Then the correction terms for an arbitrary polynomial will be the linear combination of the correction polynomials, weighted by the coefficients of the target polynomial.

The interpolating polynomials are $$1,x\\ 1,3x-2,x^2\\ 1,7x-6,6x^2-11x+6,x^3\\ 1,15x-14,25x^2-60x+36,10x^3-35x^2+5x-24,x^4\\ \cdots$$ and the correction polynomials by difference $$1,x-1\\ 1,3x-3,x^2-3x+2\\ 1,7x-7,6x^2-18x+12,x^3-6x^2+11x-6\\ 1,15x-15,25x^2-75x+50,10x^3-60x^2+65x-60,x^4-10x^3+35x^2-5x+24\\ \cdots$$

Then the corrections for, say, $x^3-2x$ are $$1-2(1),7x-7-2(x-1),6x^2-18x+12-2(0),\cdots$$