Editing Polynomial interpolation (section)

== Interpolations as linear combinations of values ==
Given a set of (position, value) data points <math>(x_0, y_0), \ldots, (x_j, y_j), \ldots, (x_n, y_n)</math> where no two positions <math>x_j</math> are the same, the interpolating polynomial <math>y(x)</math> may be considered as a [[linear combination]] of the values <math>y_j</math>, using coefficients which are polynomials in <math>x</math> depending on the <math>x_j</math>. For example, the interpolation polynomial in the [[Lagrange form]] is the linear combination
<math display="block">y(x) := \sum_{j=0}^{k} y_j c_j(x)</math>
with each coefficient <math>c_j(x)</math> given by the corresponding Lagrange basis polynomial on the given positions <math>x_j</math>:
<math display="block">c_j(x) = L_j(x_0,\ldots,x_n;x) = \prod_{ 0 \le i \le n \atop i \neq j } \frac{x-x_i}{x_j-x_i} 
= \frac{(x-x_0)}{(x_j-x_0)} \cdots \frac{(x-x_{j-1})}{(x_j-x_{j-1})} \frac{(x-x_{j+1})}{(x_j-x_{j+1})} \cdots 
\frac{(x-x_n)}{(x_j-x_n)}.</math>

Since the coefficients depend only on the positions <math>x_j</math>, not the values <math>y_j</math>, we can use the ''same coefficients'' to find the interpolating polynomial for a second set of data points <math>(x_0, v_0), \ldots, (x_n, v_n)</math> at the same positions:
<math display="block">v(x) := \sum_{j=0}^{k} v_j c_j(x).</math>

Furthermore, the coefficients <math>c_j(x)</math> only depend on the relative spaces <math>x_i-x_j</math> between the positions. Thus, given a third set of data whose points are given by the new variable  <math>t = ax+b</math> (an [[affine transformation]] of <math>x</math>, inverted by <math>x=\tfrac{t-b}{a}</math>):
<math display="block">(t_0, w_0), \ldots, (t_j, w_j) \ldots, (t_n, w_n) \qquad \text{with}\qquad t_j = ax_j + b,</math>
we can use a transformed version of the previous coefficient polynomials:<blockquote><math>\tilde c_j(t) :=  c_j(\tfrac{t-b}{a}) = c_j(x),</math> </blockquote>and write the interpolation polynomial as:<blockquote><math display="inline">w(t) := \sum_{j=0}^{k} w_j \tilde c_j(t).</math></blockquote>Data points <math>(x_j,y_j)</math> often have ''equally spaced positions'', which may be normalized by an affine transformation to <math>x_j = j</math>. For example, consider the data points<blockquote><math>(0,y_0), (1,y_1), (2,y_2)</math>.</blockquote>The interpolation polynomial in the Lagrange form is the [[linear combination]]
<math display="block">\begin{align}
y(x) := \sum_{j=0}^2 y_j c_j(x)
&= y_0 \frac{(x-1)(x-2)}{(0-1)(0-2)} + y_1 \frac{(x-0)(x-2)}{(1-0)(1-2)} + y_2 \frac{(x-0)(x-1)}{(2-0)(2-1)} \\
&= \tfrac12 y_0 (x-1)(x-2) - y_1 (x-0)(x-2) + \tfrac12 y_2 (x-0)(x-1).
\end{align} </math>

For example, <math>y(3) = y_3 = y_0 - 3y_1 + 3y_2 </math> and  <math>y(1.5) = y_{1.5} = \tfrac18 (-y_0 + 6y_1 + 3y_2)</math>.

The case of equally spaced points can also be treated by the [[method of finite differences]]. The first difference of a sequence of values <math>v=\{v_j\}_{j=0}^\infty</math> is the sequence <math>\Delta v = u = \{u_j\}_{j=0}^\infty </math> defined by <math>u_j = v_{j+1}-v_j </math>. Iterating this operation gives the ''n''<sup>th</sup> difference operation <math>\Delta^n v = u</math>, defined explicitly by:<math display="block">u_j = \sum_{k=0}^n (-1)^{n-k} {n\choose k} v_{j+k}, </math>where the coefficients form a signed version of Pascal's triangle, the [[Pascal's triangle#The Triangle of Binomial Transform Coefficients is like Pascal's Triangle.|triangle of binomial transform coefficients]]:
{| class="wikitable" style="text-align:center;line-height:90%;border:none;background:transparent;"
| colspan="8" style="border:none;"| || colspan="2"|1 || colspan="7" style="border:none;"| || style="text-align:left;border:none;"|Row n = 0
|- style="background:#f8f8f8;"
| colspan="7" style="border:none;"| || colspan="2"|1 || colspan="2"|&minus;1 || colspan="6" style="border:none;"| || style="border:none;"|Row ''n'' = 1 or ''d'' = 0
|-
| colspan="6" style="border:none;"| || colspan="2"|1 || colspan="2"|&minus;2 || colspan="2"|1 || colspan="5" style="border:none;"| || style="border:none;"|Row ''n'' = 2 or ''d'' = 1
|- style="background:#f8f8f8;"
| colspan="5" style="border:none;"| || colspan="2"|1 || colspan="2"|&minus;3 || colspan="2"|3 || colspan="2"|&minus;1 || colspan="4" style="border:none;"| || style="border:none;"|Row ''n'' = 3 or ''d'' = 2
|-
| colspan="4" style="border:none;"| || colspan="2"|1 || colspan="2"|&minus;4 || colspan="2"|6 || colspan="2"|&minus;4 || colspan="2"|1 || colspan="3" style="border:none;"| || style="border:none;"|Row ''n'' = 4 or ''d'' = 3
|- style="background:#f8f8f8;"
| colspan="3" style="border:none;"| || colspan="2"|1 || colspan="2"|&minus;5 || colspan="2"|10 || colspan="2"|&minus;10 || colspan="2"|5 || colspan="2"|&minus;1 || colspan="2" style="border:none;"| || style="border:none;"|Row ''n'' = 5 or ''d'' = 4
|-
| colspan="2" style="border:none;"| || colspan="2"|1 || colspan="2"|&minus;6 || colspan="2"|15 || colspan="2"|&minus;20 || colspan="2"|15 || colspan="2"|&minus;6 || colspan="2"|1 || style="border:none;"| || style="border:none;"|Row ''n'' = 6 or ''d'' = 5
|- style="background:#f8f8f8;"
| colspan="1" style="border:none;"| || colspan="2"|1 || colspan="2"|&minus;7 || colspan="2"|21 || colspan="2"|&minus;35 || colspan="2"|35 || colspan="2"|&minus;21 || colspan="2"|7 || colspan="2"|&minus;1 || style="border:none;"|Row ''n'' = 7 or ''d'' = 6
|-
| style="border:none;"|
| style="width:1em;border:none;"|
| style="width:1em;border:none;"|
| style="width:1em;border:none;"|
| style="width:1em;border:none;"|
| style="width:1em;border:none;"|
| style="width:1em;border:none;"|
| style="width:1em;border:none;"|
| style="width:1em;border:none;"|
| style="width:1em;border:none;"|
| style="width:1em;border:none;"|
| style="width:1em;border:none;"|
| style="width:1em;border:none;"|
| style="width:1em;border:none;"|
| style="width:1em;border:none;"|
| style="width:1em;border:none;"|
| style="width:1em;border:none;"|
|}

A polynomial <math>y(x)</math> of degree ''d'' defines a sequence of values at positive integer points, <math>y_j = y(j)</math>, and the <math>(d+1)^{\text{th}}</math> difference of this sequence is identically zero: <blockquote><math>\Delta^{d+1} y = 0</math>. </blockquote>Thus, given values <math>y_0,\ldots,y_n</math> at equally spaced points, where <math>n=d+1 </math>, we have: <math display="block">(-1)^n y_0 + (-1)^{n-1} \binom{n}{1} y_1 + \cdots - \binom n{n-1} y_{n-1} +  y_n= 0. </math>For example, 4 equally spaced data points <math>y_0,y_1,y_2,y_3 </math> of a quadratic <math>y(x)</math> obey <math>0 = -y_0 + 3y_1 - 3y_2 + y_3</math>, and solving for <math>y_3</math> gives the same interpolation equation obtained above using the Lagrange method.