Editing Polynomial interpolation (section)

=== Lozenge Diagram ===
A Lozenge diagram is a diagram that is used to describe different interpolation formulas that can be constructed for a given data set. A line starting on the left edge and tracing across the diagram to the right can be used to represent an interpolation formula if the following rules are followed:<ref name=":0">{{Cite book |last=Hamming |first=Richard W. |title=Numerical methods for scientists and engineers |date=1986 |publisher=Dover |isbn=978-0-486-65241-2 |edition=Unabridged republ. of the 2. ed. (1973) |location=New York}}</ref>
[[File:Lozenge_Diagram.svg|thumb|Lozenge Diagram: geometric representation of polynomial interpolations.]]

# Left to right steps indicate addition whereas right to left steps indicate subtraction
# If the slope of a step is positive, the term to be used is the product of the difference and the factor immediately below it. If the slope of a step is negative, the term to be used is the product of the difference and the factor immediately above it.
# If a step is horizontal and passes through a factor, use the product of the factor and the average of the two terms immediately above and below it. If a step is horizontal and passes through a difference, use the product of the difference and the average of the two terms immediately above and below it.

The factors are expressed using the formula:<math display="block">C(u+k,n)=\frac{(u+k)(u+k-1)\cdots(u+k-n+1)}{n!} </math>

==== Proof of equivalence ====
If a path goes from <math>\Delta^{n-1}y_s    </math> to <math>\Delta^{n+1}y_{s-1}    </math>, it can connect through three intermediate steps, (a) through <math>\Delta^{n}y_{s-1}    </math>, (b) through <math display="inline">C(u-s ,n) </math> or (c) through <math>\Delta^{n}y_s </math>. Proving the equivalence of these three two-step paths should prove that all (n-step) paths can be morphed with the same starting and ending, all of which represents the same formula.

Path (a):

<math>C(u-s, n) \Delta^n y_{s-1}+C(u-s+1, n+1) \Delta^{n+1} y_{s-1}    </math>

Path (b):

<math>C(u-s, n) \Delta^n y_s + C(u-s, n+1) \Delta^{n+1} y_{s-1}            </math>

Path (c):

<math>C(u-s, n) \frac{\Delta^n y_{s-1}+\Delta^n y_{s}}{2} \quad+\frac{C(u-s+1, n+1)+C(u-s, n+1)}{2} \Delta^{n+1} y_{s-1}    </math>

Subtracting contributions from path a and b:

<math>\begin{aligned}
\text{Path a - Path b}= & C(u-s, n)(\Delta^n y_{s-1}-\Delta^n y_s) +(C(u-s+1, n+1)-C(u-s, n-1)) \Delta^{n+1} y_{s-1} \\
= & - C(u-s, n)\Delta^{n+1} y_{s-1} + C(u-s, n) \frac{(u-s+1)-(u-s-n)}{n+1} \Delta^{n+1} y_{s-1}  \\
= & C(u-s, n)(-\Delta^{n+1} y_{s-1}+\Delta^{n+1} y_{s-1} )=0 \\ 
\end{aligned}    </math>

Thus, the contribution of either path (a) or path (b) is the same. Since path (c) is the average of path (a) and (b), it also contributes identical function to the polynomial. Hence the equivalence of paths with same starting and ending points is shown. To check if the paths can be shifted to different values in the leftmost corner, taking only two step paths is sufficient: (a) <math>y_{s+1}          </math> to <math>y_{s}          </math> through <math>\Delta y_{s}          </math> or (b) factor between <math>y_{s+1}          </math> and <math>y_{s}          </math>, to <math>y_{s}          </math> through <math>\Delta y_{s}          </math> or (c) starting from <math>y_{s}          </math>.

Path (a)

<math>y_{s+1}+C(u-s-1,1) \Delta y_s - C(u-s, 1) \Delta y_s         </math>

Path (b)

<math>\frac{y_{s+1}+y_s}{2}+\frac{C(u-s-1,1)+C(u-s, 1)}{2} \Delta y_s - C(u-s, 1) \Delta y_s         </math>

Path (c)

<math>y_{s}          </math>

Since <math>\Delta y_{s} = y_{s+1}-y_s    </math>, substituting in the above equations shows that all the above terms reduce to <math>y_{s}          </math> and are hence equivalent. Hence these paths can be morphed to start from the leftmost corner and end in a common point.<ref name=":0" />

==== Newton formula ====
Taking negative slope transversal from <math>y_0 </math> to <math>\Delta^n y_0 </math> gives the interpolation formula of all the <math>n+1 </math> consecutively arranged points, equivalent to Newton's forward interpolation formula:

<math>\begin{aligned}
y(s)  &=y_0+C(s, 1) \Delta y_0+C(s, 2) \Delta^2 y_0+C(s, 3) \Delta^3 y_0+\cdots \\
& =y_0+s \Delta y_0+\frac{s(s-1)}{2} \Delta^2 y_0+\frac{s(s-1)(s-2)}{3 !} \Delta^3 y_0+\frac{s(s-1)(s-2)(s-3)}{4 !} \Delta^4 y_0+\cdots      
\end{aligned}    </math>

whereas, taking positive slope transversal from <math>y_n </math> to <math>\nabla^n y_n = \Delta^n y_0 </math>, gives the interpolation formula of all the <math>n+1 </math> consecutively arranged points, equivalent to Newton's backward interpolation formula:

<math>\begin{aligned}
y(u) & =  y_k+C(u-k, 1) \Delta y_{k-1}+C(u-k+1,2) \Delta^2 y_{k-2} +C(u - k+2,3) \Delta^3 y_{k-3}+\cdots \\           
& = y_k+(u-k) \Delta y_{k-1} +\frac{(u-k+1) (u-k)}{2} \Delta^2 y_{k-2}+\frac{(u-k+2)(u-k+1)(u-k)}{3 !} \Delta^3 y_{k-3}+\cdots   \\   
y(k+s) & = y_k+(s) \nabla y_{k} +\frac{(s+1) s}{2} \nabla^2 y_{k}+\frac{(s+2)(s+1) s}{3 !} \nabla^3 y_{k}+\frac{(s+3)(s+2)(s+1) s}{4 !} \nabla^4 y_{k}+\cdots \\   
\end{aligned}    </math>

where <math>s=u-k </math> is the number corresponding to that introduced in Newton interpolation.

==== Gauss formula ====
Taking a zigzag line towards the right starting from <math>y_0 </math> with negative slope, we get Gauss forward formula:

<math>y(u)=y_0+u \Delta y_0+\frac{u(u-1)}{2} \Delta^2 y_{-1} +\frac{(u+1)u\left(u-1\right)}{3 !} \Delta^3 y_{-1}+  \frac{(u+1)u\left(u-1\right)(u-2)}{4 !} \Delta^4 y_{-2} + \cdots                     </math>

whereas starting from <math>y_0 </math> with positive slope, we get Gauss backward formula:

<math>y(u)=y_0+u \Delta y_{-1}+\frac{(u+1)u}{2} \Delta^2 y_{-1} +\frac{(u+1)u\left(u-1\right)}{3 !} \Delta^3 y_{-2}+  \frac{(u+2)(u+1)u\left(u-1\right)}{4 !} \Delta^4 y_{-2} + \cdots                          </math>

==== Stirling formula ====
By taking a horizontal path towards the right starting from <math>y_0 </math>, we get Stirling formula:

<math>\begin{aligned}
y(u)&= y_0 +u \frac{\Delta y_0+\Delta y_{-1}}{2}+\frac{C(u+1,2)+C(u, 2)}{2} \Delta^2 y_{-1} +C(u+1,3) \frac{\Delta^3 y_{-2}+\Delta^3 y_{-1}}{2}+\cdots \\
& = y_0+u \frac{\Delta y_0+\Delta y_{-1}}{2}+\frac{u^2}{2} \Delta^2 y_{-1}+\frac{u(u^2-1)}{3 !} \frac{\Delta^3 y_{-2}+\Delta^3 y_{-1}}{2}+\frac{u^2(u^2-1)}{4!}\Delta^4 y_{-2}+\cdots
\end{aligned}    </math>

Stirling formula is the average of Gauss forward and Gauss backward formulas.

==== Bessel formula ====
By taking a horizontal path towards the right starting from factor between <math>y_0 </math> and <math>y_1 </math>, we get Bessel formula:

<math>\begin{align}      
y(u)&=1{\frac{y_{0}+y_{1}}{2}}+{\frac{C(u,1)+C(u-1,1)}{2}}\Delta y_{0}+C(u,2){\frac{\Delta^{2}y_{-1}+\Delta^{2}y_{0}}{2}}+\cdots\\    
    &=  \frac{y_{0}+y_{1}}{2}+\left(u-{\frac{1}{2}}\right)\Delta y_{0}+\frac{u(u-1)}{2}\frac{\Delta^{2}y_{-1}   +\Delta^{2}y_{0}}{2}+\frac{\left(u-{\frac{1}{2}}\right)u\left( u-1\right)}{3!}\Delta^{3} y_{0} 
  + \frac{(u+1)u(u-1)(u-2)}{4!}\frac{\Delta^{4}y_{-1}+\Delta^{4}y_{-2}}{2}+\cdots\\
\end{align}                      </math>