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
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:
- Is my first approach and computation of $c_0$ and $c_n$ valid?
- How should i handle the computation of $c_\ell$ with $0<\ell
?