3
$\begingroup$

For my high school math project I studied polynomial interpolation: given a set of points $(x_0,y_0),...,(x_n,y_n)$, find the polynomial of degree n that passes through all points. The solutions by Newton and Lagrange are well known, but I wanted to know the coefficients of the polynomial in standard form (powers of x). Using elementary algebra I solved the cases up to $n=3$ and generalized this to

$$ V(x) = \sum^n_{i=0}(-1)^{n-i}\sum^n_{j=0}y_j\frac{e_{n-i}(x_0,...,x_{j-1},x_{j+1},...,x_n)}{\prod^n_{k=0,k\neq j}(x_j-x_k)}x^i $$

where $e_k(S)$ is the elementary symmetric polynomial (ESP) {1}. I also proved this. Later, I found out that V(x) is equivalent to the solution using Vandermonde's matrix, see the answer to exercise 40 in Knuth's The Art of Computer Programming, vol. 1, section 1.2.3. Sums and products. The only difference is that Vandermonde doesn't use the ESP. Lagrange's solution is expressed in elementary algebra, Newton's solution uses the divided differences (DD) $[y_0,...,y_n]$ {2}, and Vandermonde's solution can be expressed using ESP. So I wondered whether there is a solution using both DD and ESP. And there is. My solution is

$$H(x) = \sum^n_{i=0}\sum^n_{j=i}[y_0,...,y_j](-1)^{j-i}e_{j-i}(x_0,...,x_{j-1})x^i$$

It can be derived from Newton's solution and from Vandermonde's solution. After finding the solution tried to find it in (online) literature but I couldn't. I asked my math teacher and a university math professor and both did not know where it can be found. So here's my question: who knows where to find the solution H(x) in math literature? https://en.wikipedia.org/wiki/Elementary_symmetric_polynomial{1} https://en.wikipedia.org/wiki/Divided_differences{2}

$\endgroup$
1
$\begingroup$

Hint:

By Cramer, the coefficient of the $n^{th}$ power is the ratio of the Vandermonde determinant dividing a modified determinant where the $n^{th}$ column is replaced by the RHS. The latter can be expanded using the modified column and corresponding minors, which are of a quasi-Vandermonde type (there is a discontinuity in the exponents). These minors are still factored with the differences between two $x$'s, but there is an extra factor.

$\endgroup$
  • $\begingroup$ First of all many thanks. If I understand correctly $V(x)$ can be derived if we use Cramer's rule, $H(x)$ does not follow directly if I am not mistaken. How should we call this interpolation formula in monomial form? $\endgroup$ – Max Feb 4 at 15:00
  • $\begingroup$ @Max: actually it is unclear to me what you denote $V$ and $H$. My discussion is about the coefficients of the powers of $x$ in the final polynomial. $\endgroup$ – Yves Daoust Feb 4 at 15:09
  • $\begingroup$ Both $V$ and $H$ denote the coefficients in monomial basis, but differently. Likewise we have the Newton-interpolation and Lagrange-interpolation. $V$ follows from expanding Lagrange and $H$ follows from expanding Newton. $\endgroup$ – Max Feb 4 at 15:37

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.