How to obtain Lagrange interpolation formula from Vandermonde's determinant

Question

Assume that we have

1. An interval $[a,b]$
2. A function $f(x)$ that is continuous on $[a,b]$
3. $n+1$ distinct points $a = x_0<x_1<x_2<\cdots<x_n = b$
4. And $f(x_0),f(x_1),\ldots,f(x_n)$

Now we want to find the polynomial $$P(x)=a_0+a_{1}x+a_{2}x^2+\cdots+a_{n}x^n$$ which satisfies the conditions $$P(x_i)=f(x_i) \qquad for \qquad i=0,1,\ldots,n$$ Substituting the conditions, we obtain the system of equations $$a_{0}+a_{1}x_{0}+a_{2}x^{2}_{0}+\cdots+a_{n}x^{n}_{0}=f(x_0)$$ $$a_{0}+a_{1}x_{1}+a_{2}x^{2}_{1}+\cdots+a_{n}x^{n}_{1}=f(x_1)$$ $$\vdots$$ $$a_{0}+a_{1}x_{n}+a_{2}x^{2}_{n}+\cdots+a_{n}x^{n}_{n}=f(x_n)$$ Solution of this system of equations is unique, or $P(x)$ exists because the Vandermonde's determinant $$ \begin{pmatrix} 1 & x_{0} & x^{2}_{0} & \cdots & x^{n}_{0} \\ 1 & x_{1} & x^{2}_{1} & \cdots & x^{n}_{1} \\ \vdots & & & & \\ 1 & x_{n} & x^{2}_{n} & \cdots & x^{n}_{n} \\ \end{pmatrix} = \prod_{i,j=0, i>j}^n(x_i-x_j) \neq 0 $$ Assume $n=2$, then we want to determine $$P_{2}(x)=a_{0}+a_{1}x+a_{2}x^{2}$$ where $a_0,a_1,a_2$ are arbitary constants that satisfies the conditions $$f(x_0)=P_{2}(x_0), f(x_1)=P_{2}(x_1) \quad and \quad f(x_2)=P_{2}(x_2)$$ Now we have $$f(x_0)=a_{0}+a_{1}x_{0}+a_{2}x^{2}_{0}$$ $$f(x_1)=a_{0}+a_{1}x_{1}+a_{2}x^{2}_{1}$$ $$f(x_2)=a_{0}+a_{1}x_{2}+a_{2}x^{2}_{2}$$ Eliminating $a_0,a_1,a_2$ we obtain $$ \begin{pmatrix} P_2(x) & 1 & x & x^{2} \\ f(x_0) & 1 & x_0 & x^{2}_{0} \\ f(x_1) & 1 & x_1 & x^{2}_{1} \\ f(x_2) & 1 & x_2 & x^{2}_{2} \end{pmatrix} = 0 $$ Expanding the determinant, we obtain $$P_2(x)C_0-f(x_0)C_1+f(x_1)C_2-f(x_2)C_3=0$$ where $$ C_0=\begin{pmatrix} 1 & x_0 & x^{2}_{0} \\ 1 & x_1 & x^{2}_{1} \\ 1 & x_2 & x^{2}_{2} \end{pmatrix} = (x_0-x_1)(x_1-x_2)(x_2-x_0) $$ $$ C_1=\begin{pmatrix} 1 & x & x^{2} \\ 1 & x_1 & x^{2}_{1} \\ 1 & x_2 & x^{2}_{2} \\ \end{pmatrix} = (x-x_1)(x_1-x_2)(x_2-x) $$ $$ C_2=\begin{pmatrix} 1 & x & x^{2} \\ 1 & x_0 & x^{2}_{0} \\ 1 & x_2 & x^{2}_{2} \end{pmatrix} = (x-x_0)(x_0-x_2)(x_2-x) $$ $$ C_3=\begin{pmatrix} 1 & x & x^{2} \\ 1 & x_0 & x^{2}_{0} \\ 1 & x_1 & x^{2}_{1} \end{pmatrix} = (x-x_0)(x_0-x_1)(x_1-x) $$ Therefore $$P_2(x)=\frac{C_1}{C_0}f(x_0)-\frac{C_2}{C_0}f(x_1)+\frac{C_3}{C_0}f(x_2)$$ $$=\frac{(x-x_1)(x-x_2)}{(x_0-x_1)(x_0-x_2)}f(x_0)+\frac{(x-x_0)(x-x_2)}{(x_1-x_0)(x_1-x_2)}f(x_1)+\frac{(x-x_0)(x-x_1)}{(x_2-x_0)(x_2-x_1)}f(x_2)$$ $$=l_0(x)f(x_0)+l_1(x)f(x_1)+l_2(x)f(x_2)$$ I understand the above, but how eliminating $a_0,a_1,a_2$ to obtain $$ \begin{pmatrix} P_2(x) & 1 & x & x^{2} \\ f(x_0) & 1 & x_0 & x^{2}_{0} \\ f(x_1) & 1 & x_1 & x^{2}_{1} \\ f(x_2) & 1 & x_2 & x^{2}_{2} \end{pmatrix} = 0 $$ whereas we know $P_2(x),f(x_0),f(x_1)$ and $f(x_2)$ are not coefficients?

Reference: Numerical Methods For Scientific And Engineering Computation By M.K. Jain

Answer 1

I think you should have:

$\left( \begin{array}{ccc} 1 & x_0 & x_0^2 \\ 1 & x_1 & x_1^2 \\ 1 & x_2 & x_2^2 \end{array} \right)\left( \begin{array}{ccc} a_0 \\ a_1 \\ a_2 \end{array} \right)=\left( \begin{array}{ccc} f(x_0) \\ f(x_1) \\ f(x_2) \end{array} \right)$, then you solve for the coefficients right?

Answer 2

The Lagrange interpolation formula does not give you the $a_i$ directly; instead, it expresses $P(x)$ as weighted sum of Lagrange interpolation polynomials where the given values of the $f(x_i)$ are the weights. That is,

$$P(x) = \sum_{j=0}^n f(x_{j})L_j(x) = \sum_{j=0}^n f(x_{j}) \prod_{\ell = 0, \ell \neq j}^n \frac{(x - x_{\ell})}{(x_{j} - x_{\ell})},$$ where $L_j(x) = \sum_{i=0}^n L_{j,i}x^i$ has value $1$ when $x = x_j$ and value $0$ when $x = x_{\ell}$ for any $\ell \neq j$. Note that the inverse of the Vandermonde matrix has as its columns the coefficients of the Lagrange interpolation polynomials, that is,

$$\begin{align} \begin{pmatrix} 1 & x_{0} & x^{2}_{0} & \cdots & x^{n}_{0} \\ 1 & x_{1} & x^{2}_{1} & \cdots & x^{n}_{1} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & x_{n} & x^{2}_{n} & \cdots & x^{n}_{n} \\ \end{pmatrix} \begin{pmatrix}a_0\\a_1\\\vdots\\a_n\end{pmatrix} &= \begin{pmatrix}f(x_0)\\f(x_1)\\\vdots\\f(x_n)\end{pmatrix}\\ ~\Rightarrow~ \begin{pmatrix}a_0\\a_1\\\vdots\\a_n\end{pmatrix} = \begin{pmatrix} 1 & x_{0} & x^{2}_{0} & \cdots & x^{n}_{0} \\ 1 & x_{1} & x^{2}_{1} & \cdots & x^{n}_{1} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & x_{n} & x^{2}_{n} & \cdots & x^{n}_{n} \\ \end{pmatrix}^{-1} \begin{pmatrix}f(x_0)\\f(x_1)\\\vdots\\f(x_n)\end{pmatrix} &= \begin{pmatrix} L_{0,0} & L_{1,0} & L_{2,0} & \cdots & L_{n,0} \\ L_{0,1} & L_{1,1} & L_{2,1} & \cdots & L_{n,1} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ L_{0,n} & L_{1,n} & L_{2,n} & \cdots & L_{n,n} \\ \end{pmatrix} \begin{pmatrix}f(x_0)\\f(x_1)\\\vdots\\f(x_n)\end{pmatrix}. \end{align}$$ In other words, the inverse of the Vandermonde matrix is giving you the coefficients of the Lagrange interpolation polynomials. Notice, for example, that in your $$P_2(x)=\frac{C_1}{C_0}f(x_0)-\frac{C_2}{C_0}f(x_1)+\frac{C_3}{C_0}f(x_3),$$ the quantity $\frac{C_1}{C_0}$ works out to be $$\frac{C_1}{C_0} = \frac{(x-x_1)(x_1-x_2)(x_2-x)}{(x_0-x_1)(x_1-x_2)(x_2-x_0)} = \frac{(x-x_1)(x-x_2)}{(x_0-x_1)(x_0-x_2)}$$ which is precisely the Lagrange interpolation polynomial $$L_0(x) = \prod_{\ell = 0, \ell \neq 0}^n \frac{(x - x_{\ell})}{(x_{0} - x_{\ell})} = \prod_{\ell=1}^2 \frac{(x - x_{\ell})}{(x_{0} - x_{\ell})} = \frac{(x-x_1)(x-x_2)}{(x_0-x_1)(x_0-x_2)}$$ and similarly for $L_1(x)$ and $L_2(x)$.

Answer 3

This is a dated question, but it appears that the OP's primary question is why $a_0, a_1, a_2$ are eliminated to obtain $$\det \left [ \begin{array}{cccc} P_2(x) & 1 & x & x^{2} \\ f(x_0) & 1 & x_0 & x^{2}_{0} \\ f(x_1) & 1 & x_1 & x^{2}_{1} \\ f(x_2) & 1 & x_2 & x^{2}_{2} \end{array}\right] = 0?\qquad (\textrm{Eq. 1})$$

The reason is that the equation above gives solution to the original problem, i.e. finding $P_2(x)=a_0 + a_1x+a_2x^2$ satisfying $P_2(x_i)=f(x_i), i=0, 1, 2.$

To see this, first note that the last 3 columns of the matrix in (Eq. 1) are linearly independent. So (Eq. 1) is equivalent to requiring the first column to be a (unique) linear combination the last three columns, i.e. there exist some $a_0, a_1, a_2$ s.t.

$$ \left [ \begin{array}{cccc} P_2(x) & 1 & x & x^{2} \\ f(x_0) & 1 & x_0 & x^{2}_{0} \\ f(x_1) & 1 & x_1 & x^{2}_{1} \\ f(x_2) & 1 & x_2 & x^{2}_{2} \end{array}\right]\left[\begin{array}{c} -1 \\ a_0\\ a_1\\ a_2 \end{array}\right]=0 \qquad (\textrm{Eq. 2}) $$

Since $\left [ \begin{array}{ccc} 1 & x_0 & x^{2}_{0} \\ 1 & x_1 & x^{2}_{1} \\ 1 & x_2 & x^{2}_{2} \end{array}\right]$ is nonsingular, $a_0, a_1, a_2$ do exist and are uniquely determined by the bottom 3 lines of (Eq. 2). Moreover, (Eq. 2) also requires $P_2(x)$ to be the linear combination of $1, x, x^2$ of the same coefficients, i.e. $P_2(x)=a_0+a_1x+a_2x^2.$ This is exactly the desired solution of the original problem.

Secondly, consider the determinant in (Eq. 1). We may expand the determinant along the first row of the matrix, or the first column. It's easily verified that the former leads to $P_2(x)=a_0+a_1x+a_2x^2,$ where $a_0, a_1, a_2$ are precisely those obtained from (Eq. 2). The latter, on other hand, leads to Lagrange interpolation formula, i.e. $P_2(x)=l_0(x)f(x_0)+l_1(x)f(x_1)+l_2(x)f(x_2)$. Moreover, both expansions must be equal, so we can also be sure that

$$P_2(x)=a_0+a_1x+a_2x^2=l_0(x)f(x_0)+l_1(x)f(x_1)+l_2(x)f(x_2).$$