Coefficients of Lagrange polynomials

Question

Let $n\in\mathbb{N}^*,A=(a_1,\dots,a_n)\in\mathbb{K}[X]^n$ all different numbers and $B=(b_1,...,b_n)\in\mathbb{K}[X]^n$ all different numbers.

Let $L_{A,B}$ be the polynomial of degree $n-1$ verifying $\forall i\in[|1,n|],L_{A,B}(a_i)=b_i$. ($[|1,n|]=\{1,2,\dots,n\}$)

We know that this is a Lagrange interpolation polynomial and can be written $\displaystyle L_{A,B}(X)=\sum_{i=1}^n b_i\prod_{k=1,k\neq i}^n\dfrac{X-a_k}{a_i-a_k}$

However, that gives us a pretty 'abstract' definition of the polynomial. What is a good formula of the coefficient $C_k$ before $X^k$ in $L_{A,B}(X)$ ?

Answer 1

You can get a closed-form expression for Lagrange coefficients if you use a different representation. "Beginner's guide to mapping simplexes affinely", section "Lagrange interpolation", describes a determinant form of Lagrange polynomial that interpolates $(a_0;b_0)$, $\dots$, $(a_n;b_n)$ $$ P(x) = (-1) \frac{ \det \begin{pmatrix} 0 & b_0 & b_1 & \cdots & b_n \\ x^n & a_0^n & a_1^n & \cdots & a_n^n \\ x^{n-1} & a_0^{n-1} & a_1^{n-1} & \cdots & a_n^{n-1} \\ \cdots & \cdots & \cdots & \cdots & \cdots \\ 1 & 1 & 1 & \cdots & 1 \\ \end{pmatrix} }{ \det \begin{pmatrix} a_0^n & a_1^n & \cdots & a_n^n \\ a_0^{n-1} & a_1^{n-1} & \cdots & a_n^{n-1} \\ \cdots & \cdots & \cdots & \cdots \\ 1 & 1 & \cdots & 1 \\ \end{pmatrix} }. $$ Using Laplace expansion along the first column in the numerator you can get expressions for coefficients at $x^i$. Result should look as follows $$ c_i = (-1)^{n-i} \frac{ \det \begin{pmatrix} b_0 & b_1 & \cdots & b_n \\ a_0^n & a_1^n & \cdots & a_n^n \\ % x_0^{n-1} & x_1^{n-1} & \cdots & x_n^{n-1} \\ \cdots & \cdots & \cdots & \cdots \\ a_0^{i+1} & a_1^{i+1} & \cdots & a_n^{i+1} \\ a_0^{i-1} & a_1^{i-1} & \cdots & a_n^{i-1} \\ \cdots & \cdots & \cdots & \cdots \\ 1 & 1 & \cdots & 1 \\ \end{pmatrix} }{ \det \begin{pmatrix} a_0^n & a_1^n & \cdots & a_n^n \\ a_0^{n-1} & a_1^{n-1} & \cdots & a_n^{n-1} \\ \cdots & \cdots & \cdots & \cdots \\ 1 & 1 & \cdots & 1 \\ \end{pmatrix} }, $$ where $c_i$ is coefficient at $x^i$ in the polynomial. For practical example you may want to check "Workbook on mapping simplexes affinely", section "Lagrange interpolation".

Answer 2

Take a polynome P of degree n, it could be writen:

$P(x) = c_nx^n + c_{n-1}x^{n-1} + \cdots + c_0 $

or

$ P(x) = c_n(x-r_1)(x-r_2)\cdots(x-r_n)\ $

You can then define symetrical polynome:

$\sigma_1(r_1,...,r_n)=\sum_{i=1}^n r_i = r_1 + \cdots + r_n$

$\sigma_2(r_1,...,r_n)=\sum_{1\le i<j\le n} r_ir_j = r_1 r_2 + \cdots + r_{n-1} r_n $

$\sigma_k(r_1,...,r_n)=\sum_{1\le i_1<\cdots<i_k\le n} r_{i_1}r_{i_2}\ldots r_{i_k} $

$\sigma_n(r_1,...,r_n)=r_1r_2\ldots r_n$

Or in other words, $\sigma_k$ is the sum of products of k roots.

Then you have the relatonship:

$\sigma_{k}=(-1)^{k}\cdot\frac{c_{n-k}}{c_{n}}$

Keeping in mind that the lagrange polynomes are of degree n-1, the coefficient for $X^k$ in $L_i = b_i \prod_{k=1,k\neq i}^n\dfrac{X-a_k}{a_i-a_k}$ is given by:

$c_{n-1} = b_i \prod_{k=1,k\neq i}^n\dfrac{1}{a_i-a_k}$

$ c_k = c_{n-1} (-1)^{n-1-k} \sigma_{n-1-k}(a_1,..., a_{i-1},a_{i+1},...,a_n)$ $ = b_i (\prod_{k=1,k\neq i}^n\dfrac{1}{a_i-a_k})(-1)^{n-1-k} \sigma_{n-1-k} (a_1,..., a_{i-1},a_{i+1},...,a_n)$

Then you can sum for i:

$c_{n-1} = \sum_{i=1}^n b_i \prod_{k=1,k\neq i}^n\dfrac{1}{a_i-a_k}$

$ c_k = \sum_{i=1}^n b_i (\prod_{k=1,k\neq i}^n\dfrac{1}{a_i-a_k})(-1)^{n-1-k} \sigma_{n-1-k} (a_1,..., a_{i-1},a_{i+1},...,a_n)$

Note: I can't think of a situation where this would be handy.