4
$\begingroup$

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

$\endgroup$
7
$\begingroup$

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)$.

$\endgroup$
0
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ No. Now I will edit my post. Thank you. $\endgroup$
    – Dante
    Apr 9 '14 at 21:55
  • $\begingroup$ was I right? it has been a while since I have done these $\endgroup$
    – Ellya
    Apr 9 '14 at 21:56
0
$\begingroup$

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).$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.