Editing Lagrange polynomial (section)

==A perspective from linear algebra==

Solving an [[Polynomial interpolation#Constructing the interpolation polynomial|interpolation problem]] leads to a problem in [[linear algebra]] amounting to inversion of a matrix. Using a standard [[monomial basis]] for our interpolation polynomial <math display="inline">L(x) = \sum_{j=0}^k x^j m_j</math>, we must invert the [[Vandermonde matrix]] <math>(x_i)^j</math> to solve <math>L(x_i) = y_i</math> for the coefficients <math>m_j</math> of <math>L(x)</math>. By choosing a better basis, the Lagrange basis,  <math display="inline">L(x) = \sum_{j=0}^k l_j(x) y_j</math>, we merely get the [[identity matrix]], [[Kronecker delta|<math>\delta_{ij}</math>]], which is its own inverse: the Lagrange basis automatically ''inverts'' the analog of the Vandermonde matrix.

This construction is analogous to the [[Chinese remainder theorem]]. Instead of checking for remainders of integers modulo prime numbers, we are checking for remainders of polynomials when divided by linears.

Furthermore, when the order is large, [[Fast Fourier transform]]ation can be used to solve for the coefficients of the interpolated polynomial.