Today, we will learn about polynomial interpolation.
Suppose we have the following polynomial $$P(x) = 2x^2 - 3x + 3$$
Let us calculate the values of the polynomial $P(x)$ for a few values of $x$ as follows $$P(1) = 2 - 3 + 3 = 2,$$ $$P(2) = 8 - 6 + 3 = 5,$$ $$P(3) = 18 - 9 + 3 = 12, \dots$$
Now, suppose that we are given the following information $$P(1) = 2, ~~P(2) = 5, ~~P(3) = 12,$$ can we reconstruct the polynomial $P(x)$?
The answer is, yes, we can. An interpolation formula enables us to reconstruct the polynomial $P(x)$ based on its values. Today, we will learn about Newton's interpolation formula, and in the next post, we will cover Lagrange's interpolation.
First, let us make the following important observations.
Observation 1. If we do not impose any constraint on the degree of the polynomial $P(x)$ then there will exist infinitely many polynomials $P(x)$ that satisfy the condition $$P(1) = 2, ~~P(2) = 5, ~~P(3) = 12.$$
Why is that? It is because if we can find one polynomial $P(x)$ that satisfies the condition, then we can form many other polynomials $G(x)$ that also satisfy the condition by setting
$$G(x) = P(x) + (x-1)(x-2)(x-3)H(x),$$ and we have $$G(1) = P(1), ~~G(2) = P(2), ~~G(3) = P(3).$$
Observation 2. If we impose a constraint on the degree of the polynomial and require that the degree of $P(x)$ must be less than or equal to $2$, then there exists a unique polynomial $P(x)$ that has degree less than or equal to $2$ that satisfies the condition $$P(1) = 2, ~~P(2) = 5, ~~P(3) = 12.$$
This is because, if $G(x)$ is another polynomial that has degree less than or equal to $2$ and satisfies the condition $$G(1) = 2, ~~G(2) = 5, ~~G(3) = 12,$$ then we can form $$D(x) = G(x) - P(x),$$ $D(x)$ will be a polynomial of degree less than or equal to $2$ and $$D(1) = D(2) = D(3) = 0,$$ this shows that the polynomial $D(x)$ has at least $3$ roots, however, its degree is less than or equal to $2$, so $D(x)$ must be the constant zero polynomial. So $G(x) = P(x)$, and this proves the uniqueness of the polynomial $P(x)$.
Let us state the above observation as a general theorem as follows.
Theorem. If $x_1, x_2, \dots, x_n, x_{n+1}$ are $n+1$ distinct real numbers. And $y_1$, $y_2$, $\dots$, $y_n$, $y_{n+1}$ are $n+1$ arbitrary real numbers. Then there exists a unique polynomial $P(x)$ that has degree less than or equal to $n$ and satisfies the following condition $$P(x_1) = y_1, ~~P(x_2) = y_2, \dots, ~~P(x_n) = y_n, ~~P(x_{n+1})=y_{n+1}.$$
The above theorem tells us that a polynomial of degree less than or equal to $n$ will be uniquely determined by its $n+1$ values.
Let us now formulate the Newton's polynomial interpolation. We will do that through our original example. Let us reconstruct the polynomial $P(x)$ from the following information $$P(1) = 2, ~~P(2) = 5, ~~P(3) = 12.$$
In a previous post, I say that one of the lessons I have learned is that, when facing a problem that we do not know where to start, the first thing we can do is to look at special cases of the problem and try to solve them first. In this case, we can start from a simple case and proceed up to more complex case.
First, if we have only one condition $P(1) = 2$, can we find the polynomial $P(x)$? Obviously, the simplest polynomial is the constant polynomial $A(x) = 2$.
Next, suppose we want to find polynomial $B(x)$ so that $B(1) = 2$ and $B(2) = 5$. We can consider polynomials of the following form $$B(x) = A(x) + \alpha (x-1) = 2 + \alpha (x-1)$$
This form is useful because we immediately have $B(1) = A(1) = 2$. Other requirement is $B(2) = 2 + \alpha = 5$, so we need to choose $\alpha = 3$, and we obtain $$B(x) = 2 + 3(x-1)$$
Similarly, if we want to find polynomial $P(x)$ such that $P(1) = 2$, $P(2) = 5$, and $P(3) = 12$, we consider polynomials of the form $$P(x) = B(x) + \alpha (x-1)(x-2) = 2 + 3(x-1) + \alpha (x-1)(x-2)$$
Since $P(x) = B(x) + \alpha (x-1)(x-2)$, we immediately have $$P(1) = B(1) = 2, ~~P(2) = B(2) = 5. $$ The other requirement $P(3) = 8 + 2 \alpha = 12$ makes $\alpha = 2$, and we obtain $$P(x) = 2 + 3(x-1) + 2 (x-1)(x-2)$$
So we have reconstructed the polynomial $P(x)$ that satisfies $$P(1) = 2, ~~P(2) = 5, ~~P(3) = 12.$$ It is $$P(x) = 2 + 3(x-1) + 2 (x-1)(x-2) = 2x^2 - 3x + 3$$
In general, if $x_1$, $x_2$, $\dots$, $x_n$, $x_{n+1}$ are $n+1$ distinct real numbers, and $y_1$, $y_2$, $\dots$, $y_n$, $y_{n+1}$ are $n+1$ arbitrary real numbers, then we can find a polynomial $P(x)$ of degree less than or equal to $n$ that satisfies the condition $$P(x_1) = y_1, ~~P(x_2) = y_2, \dots, ~~P(x_n) = y_n, ~~P(x_{n+1})=y_{n+1}.$$
By following the above construction, the polynomial $P(x)$ will have the form $$P(x) = \alpha_1 + \alpha_2 (x-x_1) + \alpha_3 (x-x_1)(x-x_2) + \dots + \alpha_{n+1} (x-x_1)(x-x_2)\dots(x-x_n)$$
The above equation is called the Newton's interpolation formula for polynomials. Substituting $x=x_1$ into the formula gives us the value of the coefficient $\alpha_1$. Next, if we substitute $x =x_2$ into the formula, we can determine the value of $\alpha_2$. Similarly, the last coefficient $\alpha_{n+1}$ is determined by substituting $x=x_{n+1}$.
Let us consider some examples.
Example 1. Find the polynomial $P(x)$ of degree less than or equal to $4$ such that $$P(1) = 1, ~~P(2) = 1, ~~P(3) = 2, ~~P(4) = 3, ~~P(5) = 5$$
We use Newton's interpolation formula $$P(x) = \alpha_1 + \alpha_2 (x-1) + \alpha_3 (x-1)(x-2) + \alpha_4 (x-1)(x-2)(x-3) + \alpha_5 (x-1)(x-2)(x-3)(x-4)$$
Substitute $x=1$ into the above formula, we have $P(1) = \alpha_1 = 1$, so $$P(x) = 1 + \alpha_2 (x-1) + \alpha_3 (x-1)(x-2) + \alpha_4 (x-1)(x-2)(x-3) + \alpha_5 (x-1)(x-2)(x-3)(x-4)$$
Take $x=2$, we have $P(2) = 1 + \alpha_2 = 1$, so $\alpha_2 = 0$, thus, $$P(x) = 1 + \alpha_3 (x-1)(x-2) + \alpha_4 (x-1)(x-2)(x-3) + \alpha_5 (x-1)(x-2)(x-3)(x-4)$$
Take $x=3$, we have $P(3) = 1 + 2 \alpha_3 = 2$, so $\alpha_3 = \frac{1}{2}$, thus, $$P(x) = 1 + \frac{1}{2} (x-1)(x-2) + \alpha_4 (x-1)(x-2)(x-3) + \alpha_5 (x-1)(x-2)(x-3)(x-4)$$
Take $x=4$, we have $P(4) = 4 + 6 \alpha_4 = 3$, so $\alpha_4 = -\frac{1}{6}$, thus, $$P(x) = 1 + \frac{1}{2} (x-1)(x-2) -\frac{1}{6} (x-1)(x-2)(x-3) + \alpha_5 (x-1)(x-2)(x-3)(x-4)$$
Take $x=5$, we have $P(5) = 3 + 24 \alpha_5 = 5$, so $\alpha_5 = \frac{1}{12}$.
The required polynomial is $$P(x) = 1 + \frac{1}{2} (x-1)(x-2) - \frac{1}{6} (x-1)(x-2)(x-3) + \frac{1}{12} (x-1)(x-2)(x-3)(x-4).$$
Example 2. Find the polynomial $P(x)$ of degree less than or equal to $4$ such that $$P(1) = 1, ~~P(2) = 4, ~~P(3) = 9, ~~P(4) = 16, ~~P(5) = 25$$
Again, we use Newton's interpolation formula $$P(x) = \alpha_1 + \alpha_2 (x-1) + \alpha_3 (x-1)(x-2) + \alpha_4 (x-1)(x-2)(x-3) + \alpha_5 (x-1)(x-2)(x-3)(x-4)$$
Substituting $x=1$, we have $P(1) = \alpha_1 = 1$, so $$P(x) = 1 + \alpha_2 (x-1) + \alpha_3 (x-1)(x-2) + \alpha_4 (x-1)(x-2)(x-3) + \alpha_5 (x-1)(x-2)(x-3)(x-4)$$
With $x=2$, $P(2) = 1 + \alpha_2 = 4$, so $\alpha_2 = 3$, thus, $$P(x) = 1 + 3 (x-1) + \alpha_3 (x-1)(x-2) + \alpha_4 (x-1)(x-2)(x-3) + \alpha_5 (x-1)(x-2)(x-3)(x-4)$$
With $x=3$, $P(3) = 7 + 2 \alpha_3 = 9$, so $\alpha_3 = 1$, thus, $$P(x) = 1 + 3 (x-1) + (x-1)(x-2) + \alpha_4 (x-1)(x-2)(x-3) + \alpha_5 (x-1)(x-2)(x-3)(x-4)$$
With $x=4$, $P(4) = 16 + 6 \alpha_4 = 16$, so $\alpha_4 = 0$, thus, $$P(x) = 1 + 3 (x-1) + (x-1)(x-2) + \alpha_5 (x-1)(x-2)(x-3)(x-4)$$
With $x=5$, $P(5) = 25 + 24 \alpha_5 = 25$, so $\alpha_5 = 0$.
The required polynomial is $$P(x) = 1 + 3(x-1) + (x-1)(x-2) = x^2$$
From the above two examples, we can see that the polynomial $P(x)$ determined by the condition $$P(x_1) = y_1, ~~P(x_2) = y_2, \dots, ~~P(x_n) = y_n, ~~P(x_{n+1})=y_{n+1},$$ may have degree equal to $n$ (as in the example 1), and also may have degree less than $n$ (as in the example 2).
Let us stop here for now. There is another interpolation formula called the Lagrange's interpolation formula that we will study in the next post. See you again then.
Homework.
1. Find the polynomial $P(x)$ that has degree less than or equal to $4$ such that $$P(1) = 2, ~~P(2) = 4, ~~P(3) = 6, ~~P(4) = 8, ~~P(5) = 10$$
2. The Fibonacci sequence is determined as: $F_0=0$, $F_1=1$, $F_{n+1}=F_n+F_{n−1}$. So $$F_0=0, ~F_1=1, ~F_2=1, ~F_3=2, ~F_4=3, ~F_5=5, ~F_6=8, \dots$$
Let $P(x)$ be a polynomial that satisfies the following condition $$P(0) = 2011^{F_{2012}}, ~~P(1) = 2011^{F_{2011}}, ~~P(2) = 2011^{F_{2010}}, \dots $$ $$P(2010) = 2011^{F_{2}}, ~~P(2011) = 2011^{F_{1}}. $$
Prove that the degree of the polynomial $P(x)$ must be greater than or equal to $2011$.