# Computation of coefficients of Lagrange polynomials

For our homework we should write a program, that creates Lagrange base polynomials $L_k(x)$ based on a few sampling points $x_i$. Now i am eager to develop a formula to be able to compute the $\ell$-th coefficient of the polynomial $L_k(x)$ (with $\deg L_k(x)=n$) which is defined as

$$L_k(x)=\prod\limits_{i=0,\;i\neq k}^n \frac{x-x_i}{x_k-x_i}.$$

Let $n=2$ and we receive for example

$$L_0(x)=\prod\limits_{i=0,\;i\neq 0}^2 \frac{x-x_i}{x_k-x_i}=\frac{x-x_1}{x_0-x_1}\cdot \frac{x-x_2}{x_0-x_2}$$ $$=\left[x\cdot\underbrace{\left(\frac{1}{x_0-x_1}\right)}_{=:\;a}-\underbrace{\frac{x_1}{x_0-x_1}}_{=:\;c}\right] \cdot \left[x\cdot\underbrace{\left(\frac{1}{x_0-x_2}\right)}_{=:\;b}-\underbrace{\frac{x_2}{x_0-x_2}}_{=:\;d}\right]$$

and with the ability to separate the variables to be able to see what variable "takes part" in the computation of $x^0,\ldots,x^n$ we receive:

$$L_0(x) = abx^2+(ad+bc)x^1+cdx^0.$$

I tried this for $n=3$ and $n=4$ and received the following explicit formulas:

$$c_0=\prod\limits_{i=0,\;i\neq k}^n\left(\frac{x_i}{x_k-x_i}\right),\qquad c_n = \prod\limits_{i=0,\;i\neq k}^n\left(\frac{1}{x_k-x_i}\right)$$

where $c_\ell$ denotes the $\ell$-th coefficient of the Lagrange polynomial $L_k(x)$ with $\deg L_k(x)=n$. The next step would be to understand how to compute this for $0<\ell<n$. I did understand that i need to choose $\ell$ out of $n$ factors "bound" to $x$ (like $a$ and $b$ in the upper example) and $n-\ell$ out of $n$ of the other factors which are not bound to $x$ directly.

My first brainstorming results had the form of $c_\ell=\sum\limits_{i=0}^n\left(\ldots\right)$. For $n=3$ i had $a,b,c$ as factors bound to $x$ and $d,e,f$ unbounded. For $c_1$ i then needed to sum up products of one bounded and two unbounded variables: $aef+bdf+cde$. This seems to be done with binomial coefficients, isn't it?

My questions here:

1. Is my first approach and computation of $c_0$ and $c_n$ valid?
2. How should i handle the computation of $c_\ell$ with $0<\ell<n$?
• Here's an idea to get you started: can you figure out a general expression for the $n$-th derivative of the Lagrange polynomial? Dec 4 '11 at 13:44
• I could do that, but want to avoid that. We should implement this in Java for our Numerics lecture and we learned that it is a pain to derive as there many small errors can extremely influence the result! So i wanted a "small" expression that can be easily evaluted. Dec 4 '11 at 13:46
• "many small errors can extremely influence the result" - I agree; that's why one rarely bothers with deriving the coefficients of an interpolating polynomial, or the Lagrange basis polynomials. One can evaluate the polynomial without having to convert to the monomial basis. Dec 4 '11 at 13:49
• I have implemented a Polynomial class which has the eval method based on the Horner scheme. Do you think, that i should use this? My first thought was to check whether i can get the coefficients with a more efficient algorithm rather then evaluating something... furthermore, while writing this, i need to remember the exact task. We must create the polynomial without a specific $x$. That is the reason why we have a Polynomial class. This is where my intention comes from to directly compute the coeffs. Dec 4 '11 at 13:55
• I would say that the conventional "efficient" methods use divided differences instead of Lagrange basis polynomials. However, if you really need to take the Lagrange route, I suggest looking at this paper. Dec 4 '11 at 14:01

I guess, the easiest way to get expression for Lagrange coefficients is to use a determinant representation. "Beginner's guide to mapping simplexes affinely", section "Lagrange interpolation", describes a general formula 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} }.$$ The standard representation can be obtained from this expression by Laplace expansion along the first row. But we can do Laplace expansion along the first column as well and it will lead us to formula 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".