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

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
    Here's an idea to get you started: can you figure out a general expression for the $n$-th derivative of the Lagrange polynomial?2011-12-04
  • 0
    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.2011-12-04
  • 0
    "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.2011-12-04
  • 0
    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.2011-12-04
  • 1
    I would say that the conventional "efficient" methods use [divided differences](http://dx.doi.org/10.1090/S0025-5718-1970-0258240-X) instead of Lagrange basis polynomials. However, if you really need to take the Lagrange route, I suggest looking at [this paper](http://people.maths.ox.ac.uk/trefethen/barycentric.pdf).2011-12-04
  • 0
    Our homework is divided into the Lagrage part and then the Aitken-Neville and then Newton part. Therefore we need to try all methods ;-) But i will have a look at the paper you provided!2011-12-04
  • 0
    By the way: you'll also want to see [this](http://math.stackexchange.com/questions/30807).2011-12-04

0 Answers 0