# 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. –  Christian Ivicevic 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. –  Christian Ivicevic 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