4
$\begingroup$

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. 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?
  • 0
    By the way: you'll also want to see [this](http://math.stackexchange.com/questions/30807).2011-12-04

1 Answers 1