Editing Polynomial interpolation (section)

==Interpolation theorem==
For any <math>n+1</math> bivariate data points <math>(x_0,y_0),\dotsc,(x_n,y_n) \in \R^2</math>, where no two <math>x_j</math> are the same, there exists a unique polynomial <math>p(x)</math> of degree at most <math>n</math> that interpolates these points, i.e. <math>p(x_0)=y_0, \ldots, p(x_n)=y_n</math>.<ref>{{Cite book|title=Foundations of Applied Mathematics Volume 2: Algorithms, Approximation, Optimization | last1=Humpherys|first1=Jeffrey |last2=Jarvis|first2=Tyler J. | publisher=Society for Industrial and Applied Mathematics | year=2020 | isbn=978-1-611976-05-2 | pages=418 | chapter=9.2 - Interpolation}}</ref>

Equivalently, for a fixed choice of interpolation nodes <math>x_j</math>, polynomial interpolation defines a linear [[bijection]] <math>L_n</math> between the (''n''+1)-tuples of real-number values <math>(y_0,\ldots,y_n)\in \R^{n+1}</math> and the [[vector space]] <math>P(n)</math> of real polynomials of degree at most ''n'':
<math display="block">L_n : \mathbb{R}^{n+1}  \stackrel{\sim}{\longrightarrow}\,  P(n).</math>

This is a type of [[Unisolvent functions|unisolvence]] theorem. The theorem is also valid over any infinite [[Field (mathematics)|field]] in place of the real numbers <math>\R</math>, for example the rational or complex numbers.

===First proof===
Consider the [[Lagrange polynomials|Lagrange basis functions]] <math>L_0(x),\ldots,L_n(x)</math> given by:
<math display="block">L_j(x)=\prod_{i\neq j}\frac{x-x_i}{x_j-x_i} 
= \frac{(x-x_0)\cdots(x-x_{j-1})(x-x_{j+1})\cdots(x-x_n)}
{(x_j-x_0)\cdots(x_j-x_{j-1})(x_j-x_{j+1})\cdots(x_j-x_n)}.</math>

Notice that <math>L_j(x)</math> is a polynomial of degree <math>n</math>, and we have <math>L_j(x_k)=0</math> for each <math>j\neq k</math>, while <math>L_k(x_k)=1</math>. It follows that the linear combination:
<math display="block">p(x) = \sum_{j=0}^n y_j L_j(x)</math>
has <math>p(x_k)=\sum_j y_j \,L_j(x_k) = y_k </math>, so <math>p(x)</math> is an interpolating polynomial of degree <math>n</math>.

To prove uniqueness, assume that there exists another interpolating polynomial <math>q(x)</math> of degree at most <math>n</math>, so that  <math>p(x_k)=q(x_k)</math> for all <math>k=0,\dotsc,n</math>. Then <math>p(x)-q(x)</math> is a polynomial of degree at most <math>n</math> which has <math>n+1</math> distinct zeros (the <math>x_k</math>). But a non-zero polynomial of degree at most <math>n</math> can have at most <math>n</math> zeros,{{efn|This follows from the [[Factor theorem]] for polynomial division.}} so <math>p(x)-q(x)</math> must be the zero polynomial, i.e. <math>p(x)=q(x)</math>.<ref name="Epperson 2013">{{Cite book |last=Epperson |first=James F. |title=An introduction to numerical methods and analysis |date=2013 |publisher=Wiley |isbn=978-1-118-36759-9 |edition=2nd |location=Hoboken, NJ}}</ref>

===Second proof===
Write out the interpolation polynomial in the form
{{NumBlk||<math display="block">p(x) = a_n x^n + a_{n-1} x^{n-1} + \cdots + a_2 x^2 + a_1 x + a_0. </math>|{{EquationRef|1}}}}
Substituting this into the interpolation equations <math>p(x_j) = y_j</math>, we get a [[system of linear equations]] in the coefficients <math>a_j</math>, which reads in matrix-vector form as the following [[Matrix multiplication|multiplication]]:
<math display="block">\begin{bmatrix}
x_0^n  & x_0^{n-1} & x_0^{n-2} & \ldots & x_0 & 1 \\
x_1^n  & x_1^{n-1} & x_1^{n-2} & \ldots & x_1 & 1 \\
\vdots & \vdots    & \vdots    &        & \vdots & \vdots \\
x_n^n  & x_n^{n-1} & x_n^{n-2} & \ldots & x_n & 1
\end{bmatrix}
\begin{bmatrix} a_n \\ a_{n-1} \\ \vdots \\ a_0 \end{bmatrix}  =
\begin{bmatrix} y_0 \\ y_1 \\ \vdots \\ y_n \end{bmatrix}.</math>

An interpolant <math>p(x)</math> corresponds to a solution <math>A = (a_n,\ldots,a_0)</math> of the above matrix equation <math>X \cdot A = Y</math>.  The matrix ''X'' on the left is a [[Vandermonde matrix]], whose determinant is known to be <math>\textstyle \det(X) = \prod_{1 \le i < j \le n} (x_j - x_i), </math> which is non-zero since the nodes <math>x_j</math> are all distinct. This ensures that the matrix is [[Invertible matrix|invertible]] and the equation has the unique solution <math>A = X^{-1}\cdot Y</math>; that is, <math>p(x)</math> exists and is unique.

===Corollary===
If <math>f(x)</math> is a polynomial of degree at most <math>n</math>, then the interpolating polynomial of <math>f(x)</math> at <math>n+1</math> distinct points is <math>f(x)</math> itself.