The linear system $V p = f$ can be solved to find coefficients of the polynomial $P(x) = a_0 + a_1 x + a_2 x^2 + a_3 x^3 $ that interpolates the points $(-1,f_1), (2,f_2), (1,f_3), (0,f_4)$, where $V$ is the Vandermonde matrix, $p$ contains the coefficients, and $f$ contains the function outputs. See below:
$$\begin{bmatrix}
1&-1&1&-1\\
1&2&4&8\\
1&1&1&1\\
1&0&0&0
\end{bmatrix}
\begin{bmatrix}
a_0\\
a_1\\
a_2\\
a_3\\
\end{bmatrix} =
\begin{bmatrix}
f_1\\
f_2\\
f_3\\
f_4\\
\end{bmatrix}$$
One can use $LU$-decomposition of the Vandermonde matrix to solve this system for any given coefficients of $a_i$ for $i = 1,\dots, 4$ whereby:
$$ L = \begin{bmatrix}
1&0&0&0\\
1&1&0&0\\
1&2/3&1&0\\
1&1/3&1&1
\end{bmatrix}, \, \, \, \,
U = \begin{bmatrix}
1&-1&1&-1\\
0&3&3&9\\
0&0&-2&-4\\
0&0&0&2
\end{bmatrix} $$
My question is: how could one calculate the Lagrange polynomials to interpolate this polynomial $\textbf{without}$ explicitly using the formula for the Lagrange Polynomials? I am told this is possible using the results from the $LU$-decomposition, however I am not sure where the link between the two methods are? Might anyone have any suggestions how this would be possible?
Best Answer
The Lagrange polynomials, $L_i(x)$ are in this case polynomials of degree $\leq 3$ satisfying $L_i(x_j)=\delta_{ij}$. You can use the $LU$ decomposition to solve the systems $V p = e_i$, yielding the coefficients of $L_i(x)$.