Editing Newton polynomial (section)

==Derivation==

While the interpolation formula can be found by solving a linear system of equations, there is a loss of intuition in what the formula is showing and why Newton's interpolation formula works is not readily apparent. To begin, we will need to establish two facts first:

'''Fact 1.'''   Reversing the terms of a divided difference leaves it unchanged: <math>[y_0, \ldots, y_n] = [y_n, \ldots, y_0].</math> 
 
The proof of this is an easy induction: for <math>n=1</math> we compute   <math display="block">[y_0, y_1] = \frac{[y_1] - [y_0]}{x_1-x_0} = \frac{[y_0] - [y_1]}{x_0 - x_1} = [y_1, y_0].</math>   
     
Induction step: Suppose the result holds for any divided difference involving at most <math>n+1</math> terms. 
Then using the induction hypothesis in the  following 2nd equality we see that for a divided difference involving <math>n+2</math> terms we have 
 
<math display="block">[y_0, \ldots, y_{n+1}] = \frac{[y_1, \ldots, y_{n+1}] - [y_0, \ldots, y_n]}{x_{n+1} - x_0} = \frac{[y_n, \ldots, y_0] - [y_{n+1}, \ldots, y_1]}{x_0 - x_{n+1}} = [y_{n+1}, \ldots, y_0].</math>  

We formulate next Fact 2 which for purposes of induction and clarity  we also call  Statement <math>n</math>
(<math>\text{Stm}_n</math>) :

'''Fact 2.''' (<math>\text{Stm}_n</math>) : If  <math>(x_0, y_0), \ldots, (x_{n-1}, y_{n-1})</math> are any <math>n</math> points with distinct <math>x</math>-coordinates and  <math>P=P(x)</math> is the  unique polynomial of degree (at most) 
<math>n-1</math> whose graph passes through these <math>n</math> points then there holds the relation
<math display="block">[y_0, \ldots, y_n](x_n - x_0)\cdot\ldots\cdot(x_n-x_{n-1}) = y_n - P(x_n)</math>  

Proof. (It will be helpful for fluent reading of the proof to have the precise statement and its subtlety in mind: <math>P</math> is defined by passing through <math>(x_0,y_0),. . . ,(x_{n-1},y_{n-1})</math> but the formula also speaks at both sides of an additional arbitrary point  <math>(x_n,y_n)</math> with <math>x</math>-coordinate distinct from the other <math> x_i </math>.)  

We again prove these statements  by induction.
To show  <math>\text{Stm}_1,</math> let <math>(x_0,y_0)</math> be any one point and     let <math>P(x)</math> be  the unique polynomial of degree 0 passing through <math>(x_0, y_0)</math>. Then evidently <math>P(x)=y_0</math> and we can write  <math display="block">[y_0, y_1](x_1 - x_0) = \frac{y_1 - y_0}{x_1 - x_0} (x_1-x_0) = y_1 - y_0 = y_1 - P(x_1)</math> as wanted.

Proof of  <math>\text{Stm}_{n+1},</math>  assuming  <math>\text{Stm}_{n}</math> already established: Let <math>P(x)</math> be the polynomial of degree (at most) <math>n</math> passing through  <math>(x_0, y_0), \ldots, (x_n, y_n).</math>

With  <math>Q(x)</math> being the unique polynomial of degree (at most) <math>n-1</math> passing through the points <math>(x_1, y_1), \ldots, (x_n, y_n)</math>, we can write  the following chain of equalities, where we use in the 
penultimate equality that Stm<math>_n</math> applies to <math>Q</math>: 


<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)).
\end{align} </math>

The induction hypothesis for <math>Q</math> also applies to the second equality in the following computation, where 
<math>(x_0,y_0)</math> is added to the points defining <math>Q</math> :

<math display="block">\begin{align}
& Q(x_0) + [y_0,\ldots,y_n](x_0 - x_1)\cdot\ldots\cdot(x_0 - x_n) \\
&= Q(x_0) + [y_n,\ldots,y_0](x_0 - x_n)\cdot\ldots\cdot(x_0 - x_1) \\
& = Q(x_0) + y_0 - Q(x_0) \\
&= y_0 \\
&= P(x_0). \\
\end{align} </math> 

Now look at  <math>Q(x)+ [y_0,\ldots,y_n](x - x_1)\cdot\ldots\cdot(x - x_n).</math> By the definition of <math>Q</math> 
this polynomial passes through <math>(x_1,y_1), . . ., (x_n,y_n)</math> and, as we have just shown, it also passes 
through <math>(x_0,y_0).</math>  Thus it is the unique polynomial of degree <math>\leq n</math> which passes through these points. Therefore this polynomial is <math>P(x);</math> i.e.:  <math>P(x)= Q(x)+ [y_0,\ldots,y_n](x - x_1)\cdot\ldots\cdot(x - x_n).</math>

Thus we can write the last line in the first chain of equalities as   `<math> y_{n+1}-P(x_{n+1})</math>'   and have thus established that
<math display="block"> [y_0,\ldots,y_{n+1}](x_{n+1} - x_0)\cdot\ldots\cdot(x_{n+1} - x_n)=y_{n+1}-P(x_{n+1}).</math> So we 
established <math>\text{Stm}_{n+1}</math>, and hence  completed the proof of Fact 2.  

Now look at Fact 2: It can be formulated this way: If <math>P</math> is the unique polynomial of degree at most <math>n-1</math> whose graph passes through the points <math>(x_0, y_0), . . . , (x_{n-1}, y_{n-1}),</math> then <math>P(x)+ [y_0, \ldots, y_n](x - x_0)\cdot\ldots\cdot(x-x_{n-1})</math> is the unique polynomial of degree at most <math>n</math> passing 
through points  <math>(x_0, y_0), . . . , (x_{n-1}, y_{n-1}), (x_n, y_n).</math>  So we see Newton interpolation  permits indeed to add new interpolation points without destroying what has already been computed.