Editing Polynomial interpolation (section)

==== Polynomial coefficients ====
To find <math>a_i</math>, we have to solve the [[lower triangular matrix]] formed by arranging <math display="inline">p_{n} (x_i)=f(x_i)=y_i  </math> from above equation in matrix form:
: <math>\begin{bmatrix}
      1 &         & \ldots &        & 0  \\
      1 & x_1-x_0 &        &        &    \\
      1 & x_2-x_0 & (x_2-x_0)(x_2-x_1) &        & \vdots   \\
 \vdots & \vdots  &        & \ddots &    \\
      1 & x_k-x_0 & \ldots & \ldots & \prod_{j=0}^{n-1}(x_n - x_j)
\end{bmatrix}
\begin{bmatrix}     a_0 \\     \\     \vdots \\     \\     a_{n} \end{bmatrix} =
\begin{bmatrix}      y_0 \\  \\  \vdots \\ \\    y_{n} \end{bmatrix}</math>

The coefficients are derived as
: <math>a_j := [y_0,\ldots,y_j]</math>

where

: <math>[y_0,\ldots,y_j]</math>

is the notation for [[divided differences]]. Thus, [[Newton polynomial]]s are used to provide a polynomial interpolation formula of n points.<ref name="Epperson 2013"/>

{| class="toccolours collapsible collapsed" width="80%" style="text-align:left"
!Proof
|-
|
The first few coefficients can be calculated using the system of equations. The form of n-th coefficient is assumed for proof by mathematical induction.

<math>\begin{align}
a_0 &= y_0 = [y_0]   \\
a_1 &= {y_1-y_0 \over x_1 - x_0}= [y_0,y_1]  \\   
\vdots\\
a_n &= [y_0,\cdots,y_n] \quad \text{(let)}\\
\end{align} </math>

Let Q be polynomial interpolation of points <math>(x_1, y_1), \ldots, (x_n, y_n)</math>. Adding <math>(x_0,y_0)</math> to the polynomial Q:

<math>Q(x)+ a'_n (x - x_1)\cdot\ldots\cdot(x - x_n) = P_{n}(x),  </math>

where <math display="inline">a'_n(x_{0} - x_1)\ldots(x_{0}-x_{n}) = y_{0} - Q(x_{0}) </math>. By uniqueness of the interpolating polynomial of the points <math>(x_0, y_0), \ldots, (x_n, y_n)</math>, equating the coefficients of <math>x^{n-1}</math> we get, <math display="inline">a'_n=[y_0, \ldots, y_{n}] </math>.

Hence the polynomial can be expressed as:<math>P_{n}(x)= Q(x)+ [y_0,\ldots,y_n](x - x_1)\cdot\ldots\cdot(x - x_n).</math>

Adding <math>(x_{n+1},y_{n+1})</math> to the polynomial Q, it has to satisfiy: <math display="inline">[y_1, \ldots,y_{n+1}](x_{n+1} - x_1)\cdot\ldots\cdot(x_{n+1}-x_{n}) = y_{n+1} - Q(x_{n+1})   </math> where the formula for <math display="inline">a_n </math> and interpolating polynomial are used.
The <math display="inline">a_{n+1} </math> term for the polynomial <math display="inline">P_{n+1}  </math> can be found by calculating:<math display="block">\begin{align}
& [y_0,\ldots,y_{n+1}](x_{n+1} - x_0)\cdot\ldots\cdot(x_{n+1} - x_n)\\
&= \frac{[y_1,\ldots,y_{n+1}] - [y_0,\ldots,y_{n}]}{x_{n+1} - x_0}(x_{n+1} - x_0)\cdot\ldots\cdot(x_{n+1} - x_n) \\
&= \left([y_1,\ldots,y_{n+1}] - [y_0,\ldots,y_{n}]\right) (x_{n+1} - x_1)\cdot\ldots\cdot(x_{n+1} - x_n) \\
&= [y_1,\ldots,y_{n+1}](x_{n+1} - x_1)\cdot\ldots\cdot(x_{n+1} - x_n) - [y_0,\ldots,y_n](x_{n+1} - x_1)\cdot\ldots\cdot(x_{n+1} - x_n) \\
&= (y_{n+1} - Q(x_{n+1})) - [y_0,\ldots,y_n](x_{n+1} - x_1)\cdot\ldots\cdot(x_{n+1} - x_n) \\
&= y_{n+1} - (Q(x_{n+1}) + [y_0,\ldots,y_n](x_{n+1} - x_1)\cdot\ldots\cdot(x_{n+1} - x_n))\\
&=y_{n+1}-P(x_{n+1}).
\end{align} </math>which implies that <math>a_{n+1}={y_{n+1}-P_n(x_{n+1}) \over w_n(x_{n+1})}   = [y_0,\ldots,y_{n+1}]</math>.

Hence it is proved by principle of mathematical induction.
|}