# Coefficients of Lagrange polynomials

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)$ ?

• Solve the set of equations in the unknown coefficients given by all the $f(a_i) = b_i$. While theoretically possible, it is probably not worth it to write down general forms if $n$ is much bigger than $4$ or so. Also, you probably mean that $(a_1, \ldots, a_n) \in \Bbb K^n$, while $L_{A, B} \in \Bbb K[X]$. – Arthur Sep 24 '14 at 15:50
• @Arthur I know the end result is likely to be slightly ugly, but I am still interested in knowing it. – Hippalectryon Sep 24 '14 at 19:42

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.

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".