Today we will continue to learn about polynomial interpolation. In the last post, we have learned about Newton's interpolation formula, today we will learn a different interpolation formula called the Lagrange interpolation formula.
We will use the following example $$P(x) = 2x^2 - 3x + 3$$
This polynomial $P(x)$ is a polynomial of degree $2$ and we can calculate that $$P(1) = 2, ~~P(2) = 5, ~~P(3) = 12.$$
The polynomial interpolation problem is the problem of reconstructing the polynomial $P(x)$, given the condition that $P(1) = 2$, $P(2) = 5$, and $P(3) = 12$.
In a previous post, I say that in mathematics, when we want to solve a problem and we don't know where to start, it is always helpful to look at some special cases first. By looking at special cases, we may understand the problem better, and it will give us hint to solve the problem in its general form.
We observe that if $f(x)$ is a polynomial and $f(u) = 0$ then $u$ is a root of the polynomial and we can write $f(x)$ as the following form $$f(x) = (x-u)g(x).$$
Using this observation, we will solve the following simple problem of constructing a polynomial $A(x)$ that satisfies the following condition $$A(1) = 1, ~~A(2) = 0, ~~A(3) = 0.$$
Clearly, $A(x)$ will be in the following form $$A(x) = a (x-2)(x-3)$$
The two conditions $A(2) = 0$, $A(3) = 0$ are readily satisfied. What about the condition $A(1) = 1$?
Substituting $x=1$, we have $$A(1) = a (1-2)(1-3) = 1$$
So we can choose $$a = \frac{1}{(1-2)(1-3)},$$ and obtain the polynomial $$A(x) = \frac{(x-2)(x-3)}{(1-2)(1-3)}$$ that satisfies the conditions $$A(1) = 1, ~~A(2) = 0, ~~A(3) = 0.$$
Similarly, we can find a polynomial $B(x)$ that satisfies the condition $$B(1) = 0, ~~B(2) = 1, ~~B(3) = 0,$$ it is $$B(x) = \frac{(x-1)(x-3)}{(2-1)(2-3)}.$$
And a polynomial $C(x)$ satisfying $$C(1) = 0, ~~C(2) = 0, ~~C(3) = 1$$ is $$C(x) = \frac{(x-1)(x-2)}{(3-1)(3-2)}.$$
We have solved some special cases of the interpolation problem. We have found three polynomials, $A(x)$, $B(x)$ and $C(x)$, that satisfy the following conditions $$A(1) = 1, ~~A(2) = 0, ~~A(3) = 0$$ $$B(1) = 0, ~~B(2) = 1, ~~B(3) = 0$$ $$C(1) = 0, ~~C(2) = 0, ~~C(3) = 1$$
Now, can we find a polynomial $P(x)$ so that $P(1) = 2$, $P(2) = 5$, $P(3) = 12$?
Can you see any connection between $P(x)$ and the three polynomials $A(x)$, $B(x)$, $C(x)$?
Well, if we let $$P(x) = 2 ~A(x) + 5 ~B(x) + 12 ~C(x)$$
then $$P(1) = 2 ~A(1) + 5 ~B(1) + 12 ~C(1) = 2 + 0 + 0 = 2,$$ $$P(2) = 2 ~A(2) + 5 ~B(2) + 12 ~C(2) = 0 + 5 + 0 = 5,$$ $$P(3) = 2 ~A(3) + 5 ~B(3) + 12 ~C(3) = 0 + 0 + 12 = 12.$$
So we have found $P(x)$, it is $$P(x) = 2 ~A(x) + 5 ~B(x) + 12 ~C(x)$$ $$ = 2 \frac{(x-2)(x-3)}{(1-2)(1-3)} + 5 \frac{(x-1)(x-3)}{(2-1)(2-3)} + 12 \frac{(x-1)(x-2)}{(3-1)(3-2)}$$ $$ = (x-2)(x-3) - 5(x-1)(x-3)+ 6(x-1)(x-2) = 2x^2 - 3x + 3$$
How amazing is that! By solving the problem in very simple cases for $A(x)$, $B(x)$, $C(x)$, we have found a solution to a general problem for $P(x)$!
We are now ready to state the Lagrange interpolation formula.
Let $x_1$, $x_2$, $\dots$, $x_n$, $x_{n+1}$ be $n+1$ distinct numbers, and $y_1$, $y_2$, $\dots$, $y_n$, $y_{n+1}$ be $n+1$ arbitrary numbers. We will construct a polynomial $P(x)$ of degree less than or equal to $n$ such that $$P(x_1) = y_1, ~~P(x_2) = y_2, \dots, ~~P(x_n) = y_n, ~~P(x_{n+1})=y_{n+1}.$$
The polynomial $P(x)$ is constructed from the polynomials $P_1(x)$, $P_2(x)$, $\dots$, $P_n(x)$, $P_{n+1}(x)$ as follows $$P(x) = y_1 ~P_1(x) + y_2 ~P_2(x) + \dots + y_n ~P_n(x) + y_{n+1} ~P_{n+1}(x),$$ here $P_1(x)$, $\dots$, $P_{n+1}(x)$ are the following polynomials.
$$P_1(x) = \frac{(x-x_2)(x-x_3) \dots (x-x_n)(x-x_{n+1})}{(x_1-x_2)(x_1-x_3) \dots (x_1-x_n)(x_1-x_{n+1})}$$ $$P_2(x) = \frac{(x-x_1)(x-x_3) \dots (x-x_n)(x-x_{n+1})}{(x_2-x_1)(x_2-x_3) \dots (x_2-x_n)(x_2-x_{n+1})}$$ $$\dots$$ $$P_n(x) = \frac{(x-x_1)(x-x_2) \dots (x-x_{n-1})(x-x_{n+1})}{(x_n-x_1)(x_n-x_2) \dots (x_n-x_{n-1})(x_n-x_{n+1})}$$ $$P_{n+1}(x) = \frac{(x-x_1)(x-x_2) \dots (x-x_{n-1})(x-x_n)}{(x_{n+1}-x_1)(x_{n+1}-x_2) \dots (x_{n+1}-x_{n-1})(x_{n+1}-x_{n})}$$
These polynomials satisfy the following conditions $$P_1(x_1) = 1, ~~P_1(x_2) = 0, ~~P_1(x_3) = 0, \dots, ~~P_1(x_n) = 0, ~~P_1(x_{n+1}) = 0.$$ $$P_2(x_1) = 0, ~~P_2(x_2) = 1, ~~P_2(x_3) = 0, \dots, ~~P_2(x_n) = 0, ~~P_2(x_{n+1}) = 0.$$ $$\dots$$ $$P_n(x_1) = 0, ~~P_n(x_2) = 0, ~~P_n(x_3) = 0, \dots, ~~P_n(x_{n}) = 1, ~~P_n(x_{n+1}) = 0.$$ $$P_{n+1}(x_1) = 0, ~~P_{n+1}(x_2) = 0, ~~P_{n+1}(x_3) = 0, \dots, ~~P_{n+1}(x_n) = 0, ~~P_{n+1}(x_{n+1}) = 1.$$
So, we have $$P(x) = y_1 \frac{(x-x_2)(x-x_3) \dots (x-x_n)(x-x_{n+1})}{(x_1-x_2)(x_1-x_3) \dots (x_1-x_n)(x_1-x_{n+1})} + y_2 \frac{(x-x_1)(x-x_3) \dots (x-x_n)(x-x_{n+1})}{(x_2-x_1)(x_2-x_3) \dots (x_2-x_n)(x_2-x_{n+1})}$$ $$ + \dots + y_n \frac{(x-x_1)(x-x_2) \dots (x-x_{n-1})(x-x_{n+1})}{(x_n-x_1)(x_n-x_2) \dots (x_n-x_{n-1})(x_n-x_{n+1})} + y_{n+1} \frac{(x-x_1)(x-x_2) \dots (x-x_{n-1})(x-x_n)}{(x_{n+1}-x_1)(x_{n+1}-x_2) \dots (x_{n+1}-x_{n-1})(x_{n+1}-x_{n})},$$
In a shorter notation, $$P(x) = \sum_{i=1}^{n+1} y_i \prod_{j \neq i}\frac{x-x_j}{x_i-x_j}$$
This is called the Lagrange's interpolation formula.
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 Lagrange's interpolation formula $$P(x) = \frac{(x-2)(x-3)(x-4)(x-5)}{(1-2)(1-3)(1-4)(1-5)} + \frac{(x-1)(x-3)(x-4)(x-5)}{(2-1)(2-3)(2-4)(2-5)}$$ $$+ 2 \frac{(x-1)(x-2)(x-4)(x-5)}{(3-1)(3-2)(3-4)(3-5)} + 3 \frac{(x-1)(x-2)(x-3)(x-5)}{(4-1)(4-2)(4-3)(4-5)} + 5 \frac{(x-1)(x-2)(x-3)(x-4)}{(5-1)(5-2)(5-3)(5-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 Lagrange's interpolation formula, $$P(x) = \frac{(x-2)(x-3)(x-4)(x-5)}{(1-2)(1-3)(1-4)(1-5)} + 4 \frac{(x-1)(x-3)(x-4)(x-5)}{(2-1)(2-3)(2-4)(2-5)}$$ $$+ 9 \frac{(x-1)(x-2)(x-4)(x-5)}{(3-1)(3-2)(3-4)(3-5)} + 16 \frac{(x-1)(x-2)(x-3)(x-5)}{(4-1)(4-2)(4-3)(4-5)} + 25 \frac{(x-1)(x-2)(x-3)(x-4)}{(5-1)(5-2)(5-3)(5-4)} $$
By expanding it out, we can verify that $$P(x) = x^2$$
Let us stop here for now. See you again next time.
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$.
