Evaluating derivatives of a polynomial by evaluating the polynomial at multiple points

Question

Let's consider $\mathbb{R}[X]$ the vector space of real polynomials with one indeterminate and $\mathbb{R}[X]_n$ the sub-vector space of polynomials with degree at most equal to $n$. For all possible $a \in \mathbb{R}$, I'm considering the linear forms $P \mapsto P(a)$ and $P \mapsto P'(a)$ over these vector spaces.

In the case of $\mathbb{R}[X]_n$ it is obvious that for a given $b \in \mathbb{R}$ there exists a pair of families $\big((a_i)_i, (\lambda_i)_i\big)$ such that $$ P'(b) = \sum_{0 \leq i \leq n} \lambda_i \cdot P(a_i) $$

This is akin to solving the linear problem below, which involves a Vandermonde matrix. $$ \begin{bmatrix} 1 & \dots & 1 \\ a_0 & \dots & a_n \\ (a_0)^2 & \dots & (a_n)^2 \\ (a_0)^3 & \dots & (a_n)^3 \\ \vdots & \ddots & \vdots \\ (a_0)^n & \dots & (a_n)^n \\ \end{bmatrix} \cdot \begin{bmatrix} \lambda_0 \\ \lambda_1 \\ \lambda_2 \\ \lambda_3 \\ \vdots \\ \lambda_n \\ \end{bmatrix} = \begin{bmatrix} 0 \\ 1 \\ 2 \cdot b \\ 3 \cdot b^2 \\ \vdots \\ n \cdot b^{n-1} \\ \end{bmatrix} $$ Provided that the $a_i$ are all distinct, this matrix is invertible, so we have infinitely many possible solutions. Going back to the original problem, this means that for polynomials of maximum degree $n$, the operation of evaluating their derivative at any point is identical to evaluating them at sufficiently many points.

Question: Is this still true if we forget the restriction on the degree?

We now have an "infinite-dimensional" linear problem with an "infinite-dimensional" Vandermonde matrix $$ \begin{bmatrix} 1 & \dots & 1 & \dots \\ a_0 & \dots & a_i & \dots \\ (a_0)^2 & \dots & (a_i)^2 & \dots \\ (a_0)^3 & \dots & (a_i)^3 & \dots \\ \vdots & \ddots & \vdots & \\ (a_0)^j & \dots & (a_i)^j & \dots \\ \vdots & & \vdots & \ddots \\ \end{bmatrix} \cdot \begin{bmatrix} \lambda_0 \\ \lambda_1 \\ \lambda_2 \\ \lambda_3 \\ \vdots \\ \lambda_i \\ \vdots \\ \end{bmatrix} = \begin{bmatrix} 0 \\ 1 \\ 2 \cdot b \\ 3 \cdot b^2 \\ \vdots \\ i \cdot b^{i-1} \\ \vdots \\ \end{bmatrix} $$ We have many, many degrees of freedom (all the $\lambda_i$ and all the $a_i$) and intuitively, it looks like this problem should have many solutions given that a polynomial is entirely defined by the knowledge of its values at infinitely many (countable) points. However, I'm struggling to find an example of a numerical solution.

Answer 1

This can be done using finite differences. Here's a quick sketch. Define the forward difference

$$(\Delta f)(x) = f(x + 1) - f(x).$$

$\Delta$ reduces the degree of polynomials by $1$ like the ordinary derivative. Moreover on the Newton basis ${x \choose k}$ it satisfies

$$\Delta {x \choose k} = {x \choose k-1}.$$

So if we write an arbitrary polynomial in the Newton basis and solve for the coefficients (we just repeatedly apply forward differences and plug in $x = 0$) we get that any polynomial has a "Newton series" expansion

$$f(x) = \sum_{k \ge 0} (\Delta^k f)(0) {x \choose k}$$

where

$$(\Delta^k f)(0) = \sum_{i=0}^k (-1)^{k-i} {k \choose i} f(i).$$

(This can be proven by expanding out $\Delta^k = (S - I)^k$ where $S$ is the forward shift and $I$ is the identity operator.) For a polynomial of degree $d$ the Newton series has $d + 1$ terms so it is actually always finite even though the number of terms is unbounded, and it lets us express the value $f(x)$ of a polynomial at any point using the values $f(0), f(1), \dots$ on $\mathbb{N}$ (including $0$). Now to compute the derivative at any point we can just differentiate term-by-term, obtaining

$$f'(x) = \sum_{k \ge 0} (\Delta^k f)(0) {x \choose k}'$$

so the problem reduces to computing the derivatives of the Newton polynomials ${x \choose k}$; these can be computed using the product rule or logarithmic differentiation, which gives

$${x \choose k}' = {x \choose k} \sum_{i=0}^{k-1} \frac{1}{x - i}$$

so, putting it all together, we have

$$\boxed{ f'(x) = \sum_{k \ge 0} \left( \sum_{i=0}^k (-1)^{k-i} {k \choose i} f(i) \right) {x \choose k} \sum_{i=0}^{k-1} \frac{1}{x - i} }.$$

Answer 2

Given the values $P(n)$ of a polynomial $P$ at all $n\in\Bbb N$, you can find the degree $d$ of $P$ by the formula $$d=1+\max\{k\in\{-1,0\}\cup\Bbb N\colon \lim_{\substack{ n\in\Bbb N, \\ n\to\infty }}P(n)/n^k=\infty\}.$$ Then, once you know $d$, you can proceed as before.

---

Instead of $\Bbb N$, you can similarly use any unbounded countable set of real numbers.