General explicit solution to polynomial interpolation

[FranzS]

TL;DR Summary

Searching for a proper notation to express the general explicit solution of the linear system of equation for solving polynomial interpolation.

In order to interpolate a number ##m## of points ##(x_i,y_i)## with a polynomial ##P_n(x)## of grade ##n = m-1## (assuming all ##x_i## have different values), one has to solve the linear system...

$$

\begin{flalign*}

& y_i = \sum_{k=0}^n \beta_k \, {x_i}^k \quad \quad \forall \, i=1,2,...,m &
\end{flalign*}

$$

... and find the coefficients ##\beta_k## which define the interpolating polynomial itself.I'm well aware this linear system can be represented in matrix/vector form and solved as such with dedicated calculations (for example, with Excel's array formulas), but I have always been interested in a general solution that could be written down explicitly.

That should be pretty trivial, but I couldn't find any specific info on the internet. So, I spent myself some hours solving such linear systems. Hereafter I'm listing the solutions for some values of ##m## (or, equivalently, ##n=m-1##), which easily reveal the pattern of the general solution (which is discussed further down below):

Case with ##\; m=1 \; \; (n=0)##
Relevant polynomial monomial: ##\; P_0(x)=\beta_0##
Equivalent statement: "a single point is interpolated by a unique constant function"
Solution:
\begin{flalign*}
& \beta_0 = y_1 &
\end{flalign*}
Case with ##\; m=2 \; \; (n=1)##
Relevant polynomial: ##\; P_1(x)=\beta_0+\beta_1 x##
Equivalent statement: "there is only one line that can pass through any two given points"
Solutions:
\begin{flalign*}
& \beta_0 = - \left( \frac{ y_1 x_2 }{ x_1 - x_2} + \frac{ y_2 x_1 }{ x_2 - x_1} \right) \\
& \\
& \beta_1 = \frac{ y_1 }{ x_1 - x_2} + \frac{ y_2 }{ x_2 - x_1} &
\end{flalign*}
Case with ##\; m=3 \; \; (n=2)##
Relevant polynomial: ##\; P_2(x)=\beta_0+\beta_1 x + \beta_2 x^2##
Equivalent statement: "there is only one parabola that can pass through any three given (non-aligned) points"
Solutions:
\begin{flalign*}
& \beta_0 = \frac{ y_1 x_2 x_3}{ (x_1 - x_2)(x_1 - x_3) } + \frac{ y_2 x_1 x_3}{ (x_2 - x_1)(x_2 - x_3) } + \frac{ y_3 x_1 x_2}{ (x_3 - x_1)(x_3 - x_2) } \\
& \\
& \beta_1 = - \left( \frac{ y_1 (x_2 + x_3)}{ (x_1 - x_2)(x_1 - x_3) } + \frac{ y_2 (x_1 + x_3)}{ (x_2 - x_1)(x_2 - x_3) } + \frac{ y_3 (x_1 + x_2)}{ (x_3 - x_1)(x_3 - x_2) } \right) \\
& \\
& \beta_2 = \frac{ y_1 }{ (x_1 - x_2)(x_1 - x_3) } + \frac{ y_2 }{ (x_2 - x_1)(x_2 - x_3) } + \frac{ y_3 }{ (x_3 - x_1)(x_3 - x_2) } &
\end{flalign*}
Case with ##\; m=4 \; \; (n=3)##
Relevant polynomial: ##\; P_3(x)=\beta_0+\beta_1 x + \beta_2 x^2 + \beta_3 x^3##
Solutions:
\begin{flalign*}
& \beta_0 = - \left( \frac{ y_1 x_2 x_3 x_4}{ (x_1 - x_2)(x_1 - x_3)(x_1 - x_4) } + \frac{ y_2 x_1 x_3 x_4}{ (x_2 - x_1)(x_2 - x_3)(x_2 - x_4) } + \frac{ y_3 x_1 x_2 x_4}{ (x_3 - x_1)(x_3 - x_2)(x_3 - x_4) } + \frac{ y_4 x_1 x_2 x_3}{ (x_4 - x_1)(x_4 - x_2)(x_4 - x_3) } \right) \\
& \\
& \beta_1 = \frac{ y_1 (x_2 x_3 + x_2 x_4 + x_3 x_4)}{ (x_1 - x_2)(x_1 - x_3)(x_1 - x_4) } + \frac{ y_2 (x_1 x_3 + x_1 x_4 + x_3 x_4)}{ (x_2 - x_1)(x_2 - x_3)(x_2 - x_4) } + \frac{ y_3 (x_1 x_2 + x_1 x_4 + x_2 x_4)}{ (x_3 - x_1)(x_3 - x_2)(x_3 - x_4) } + \frac{ y_4 (x_1 x_2 + x_1 x_3 + x_2 x_3)}{ (x_4 - x_1)(x_4 - x_2)(x_4 - x_3) } \\
& \\
& \beta_2 = - \left( \frac{ y_1 (x_2+x_3+x_4)}{ (x_1 - x_2)(x_1 - x_3)(x_1 - x_4) } + \frac{ y_2 (x_1+x_3+x_4)}{ (x_2 - x_1)(x_2 - x_3)(x_2 - x_4) } + \frac{ y_3 (x_1+x_2+x_4)}{ (x_3 - x_1)(x_3 - x_2)(x_3 - x_4) } + \frac{ y_4 (x_1+x_2+x_3)}{ (x_4 - x_1)(x_4 - x_2)(x_4 - x_3) } \right) \\
& \\
& \beta_3 = \frac{ y_1 }{ (x_1 - x_2)(x_1 - x_3)(x_1 - x_4) } + \frac{ y_2 }{ (x_2 - x_1)(x_2 - x_3)(x_2 - x_4) } + \frac{ y_3 }{ (x_3 - x_1)(x_3 - x_2)(x_3 - x_4) } + \frac{ y_4 }{ (x_4 - x_1)(x_4 - x_2)(x_4 - x_3) } &
\end{flalign*}
... and let me write down one more, for a better understanding of how the pattern evolves...

Case with ##\; m=5 \; \; (n=4)##
Relevant polynomial: ##\; P_4(x)=\beta_0+\beta_1 x + \beta_2 x^2 + \beta_3 x^3 + \beta_4 x^4##
Solutions:
\begin{flalign*}
&
\beta_0 =
\frac{ y_1 x_2 x_3 x_4 x_5}{ (x_1 - x_2)(x_1 - x_3)(x_1 - x_4)(x_1-x_5) }
+
\frac{ y_2 x_1 x_3 x_4 x_5}{ (x_2 - x_1)(x_2 - x_3)(x_2 - x_4)(x_2-x_5)}
+
\frac{ y_3 x_1 x_2 x_4 x_5}{ (x_3 - x_1)(x_3 - x_2)(x_3 - x_4)(x_3-x_5)}
+
\frac{ y_4 x_1 x_2 x_3 x_5}{ (x_4 - x_1)(x_4 - x_2)(x_4 - x_3)(x_4-x_5)}
+
\frac{ y_5 x_1 x_2 x_3 x_4}{ (x_5 - x_1)(x_5 - x_2)(x_5 - x_3)(x_5-x_4)}
\\
& \\
&
\beta_1 =
- \left(
\frac{ y_1 (x_2 x_3 x_4 + x_2 x_3 x_5 + x_2 x_4 x_5 + x_3 x_4 x_5)}{ (x_1 - x_2)(x_1 - x_3)(x_1 - x_4)(x_1-x_5) }
+
\frac{ y_2 (x_1 x_3 x_4 + x_1 x_3 x_5 + x_1 x_4 x_5 + x_3 x_4 x_5)}{ (x_2 - x_1)(x_2 - x_3)(x_2 - x_4)(x_2-x_5)}
+
\frac{ y_3 (x_1 x_2 x_4 + x_1 x_2 x_5 + x_1 x_4 x_5 + x_2 x_4 x_5)}{ (x_3 - x_1)(x_3 - x_2)(x_3 - x_4)(x_3-x_5)}
+
\frac{ y_4 (x_1 x_2 x_3 + x_1 x_2 x_5 + x_1 x_3 x_5 + x_2 x_3 x_5)}{ (x_4 - x_1)(x_4 - x_2)(x_4 - x_3)(x_4-x_5)}
+
\frac{ y_5 (x_1 x_2 x_3 + x_1 x_2 x_4 + x_1 x_3 x_4 + x_2 x_3 x_4)}{ (x_5 - x_1)(x_5 - x_2)(x_5 - x_3)(x_5-x_4)}
\right)
\\
& \\
&
\beta_2 =
\frac{ y_1 (x_2 x_3 + x_2 x_4 + x_2 x_5 + x_3 x_4 + x_3 x_5 + x_4 x5)}{ (x_1 - x_2)(x_1 - x_3)(x_1 - x_4)(x_1-x_5) }
+
\frac{ y_2 (x_1x_3 + x_1 x_4 + x_1x_5 + x_3x_4 + x_3x_5 + x_4x_5)}{ (x_2 - x_1)(x_2 - x_3)(x_2 - x_4)(x_2-x_5)}
+
\frac{ y_3 (x_1x_2 + x_1 x_4 + x_1x_5 + x_2x_4 + x_2x_5 + x_4x_5)}{ (x_3 - x_1)(x_3 - x_2)(x_3 - x_4)(x_3-x_5)}
+
\frac{ y_4 (x_1x_2 + x_ 1x_3 + x_1x_5 + x_2x_3 + x_2x_5 + x_3x_5)}{ (x_4 - x_1)(x_4 - x_2)(x_4 - x_3)(x_4-x_5)}
+
\frac{ y_5 (x_1x_2 + x_1 x_3 + x_1x_4 + x_2x_3 + x_2x_4 + x_3x_4)}{ (x_5 - x_1)(x_5 - x_2)(x_5 - x_3)(x_5-x_4)}
\\
& \\
&
\beta_3 =
- \left(
\frac{ y_1 (x_2 + x_3 + x_4 + x_5)}{ (x_1 - x_2)(x_1 - x_3)(x_1 - x_4)(x_1-x_5) }
+
\frac{ y_2 (x_1 + x_3 + x_4 + x_5)}{ (x_2 - x_1)(x_2 - x_3)(x_2 - x_4)(x_2-x_5)}
+
\frac{ y_3 (x_1 + x_2 + x_4 + x_5)}{ (x_3 - x_1)(x_3 - x_2)(x_3 - x_4)(x_3-x_5)}
+
\frac{ y_4 (x_1 + x_2 + x_3 + x_5)}{ (x_4 - x_1)(x_4 - x_2)(x_4 - x_3)(x_4-x_5)}
+
\frac{ y_5 (x_1 + x_2 + x_3 + x_4)}{ (x_5 - x_1)(x_5 - x_2)(x_5 - x_3)(x_5-x_4)}
\right)
\\
& \\
&
\beta_4 =
\frac{ y_1 }{ (x_1 - x_2)(x_1 - x_3)(x_1 - x_4)(x_1-x_5) }
+
\frac{ y_2 }{ (x_2 - x_1)(x_2 - x_3)(x_2 - x_4)(x_2-x_5)}
+
\frac{ y_3 }{ (x_3 - x_1)(x_3 - x_2)(x_3 - x_4)(x_3-x_5)}
+
\frac{ y_4 }{ (x_4 - x_1)(x_4 - x_2)(x_4 - x_3)(x_4-x_5)}
+
\frac{ y_5 }{ (x_5 - x_1)(x_5 - x_2)(x_5 - x_3)(x_5-x_4)}
&
\end{flalign*}

Patterns
According to the way in which I expressed the solutions, I notice that:

• For a given coefficient ##\beta_k##, there is a common factor equal to ##(-1)^{n+k}## in front of the whole expression.
• Each of the terms constituting the expression of a given coefficient ##\beta_k## has the form:

$$ \frac{y_i \cdot A_i }{ B_i } $$

• ##A_i## is constituted by all possible "product-combinations" of the ##x## values other than ##x_i##, taken ##n-k## by ##n-k## . The number of such combinations is equal to the binomial coefficient ##\binom{n}{k} = \frac{n!}{k!(n-k)!}##
• Finally, ##B_i## is equal to:

$$ B_i = \prod_{j=1, \; j \neq i}^{n+1} (x_i-x_j) $$

Question: by the way, is this last notation correct? I mean, is it legit to write the sum from ##j=1## when ##i## could also be ##1## and the requirement is ##j \neq i##?General expression of solutions
I think I can write a general expression for the coefficients ##\beta_0## and ##\beta_n## as follows:
\begin{flalign*}
& \beta_0 = (-1)^n \cdot \sum_{i=1}^{n+1} \left( y_i \cdot \prod_{j=1, \; j \neq i }^{n+1} \frac{x_j}{(x_i-x_j)} \right) \\
& \beta_n = \sum_{i=1}^{n+1} \frac{y_i}{\prod\limits_{j=1, \; j \neq i}\limits^{n+1} (x_i-x_j)} &
\end{flalign*}

Again, same question: is it legit to write the sum from ##j=1## when ##i## could also be ##1## and the requirement is ##j \neq i##?

Anyway, I can't really find a proper notation for a generic coefficient ##\beta_k \;##...
\begin{flalign*}
& \beta_k = (-1)^{(n+k)} \cdot \sum_{i=1}^{n+1} \left( y_i \cdot \frac{???}{\prod\limits_{j=1, \; j \neq i }\limits^{n+1} (x_i-x_j)} \right) &
\end{flalign*}

Can anyone advise me?
Thanks for your attention.

 

[FactChecker]

I'm not sure what your goal is, but two common polynomial interpolation methods use the Lagrange form and the Newton form. The Lagrange form of the interpolating polynomial is here. The Newton form is here.
You should be aware that high order polynomial interpolations can have wild behavior between the points and especially if you extrapolate beyond the points. Spline functions are better behaved that way but they are piecewise defined and will not have continuous high order derivatives.

 

[pasmith]

The idea is to construct [itex]n[/itex] polynomials [itex]\phi_1, \dots, \phi_n[/itex] such that [tex]
\phi_i(x_j) = \begin{cases} 1 & i = j, \\ 0 & i \neq j. \end{cases}[/tex] Hence [tex]
\phi_i(x) = \prod_{j\neq i} \frac{x - x_j}{x_i - x_j}[/tex] which is the Lagrange interpolating polynomial, and the interpolant [itex]\mathcal{I}(y)[/itex] of the function [itex]y[/itex] is [tex]
\left[\mathcal{I}(y)\right](x) = \sum_{i=1}^n y(x_i) \phi_i(x).[/tex]

 

[FranzS]

Thanks for the insights. I'm going to learn something new.