Editing Lagrange polynomial (section)

==Barycentric form==

Each Lagrange basis polynomial <math display=inline>\ell_j(x)</math> can be rewritten as the product of three parts, a function <math display=inline>\ell(x) = \prod_m (x - x_m)</math> common to every basis polynomial, a node-specific constant <math display=inline>w_j = \prod_{m\neq j}(x_j - x_m)^{-1}</math> (called the ''barycentric weight''), and a part representing the displacement from <math display=inline>x_j</math> to <math display=inline>x</math>:<ref>{{cite journal
 | first1 = Jean-Paul | last1 = Berrut
 | first2 = Lloyd N. | last2 = Trefethen |author-link = Lloyd N. Trefethen
 | year = 2004
 | title = Barycentric Lagrange Interpolation
 | journal = SIAM Review
 | volume = 46
 | issue = 3
 | pages = 501&ndash;517
 | doi = 10.1137/S0036144502417715
 | bibcode = 2004SIAMR..46..501B
 | url = https://people.maths.ox.ac.uk/trefethen/barycentric.pdf
 | doi-access = free
 }}</ref>

<math display=block>\ell_j(x) = \ell(x) \dfrac{w_j}{x - x_j}</math>

By factoring <math display=inline>\ell(x)</math> out from the sum, we can write the Lagrange polynomial in the so-called ''first barycentric form'':

:<math>L(x) = \ell(x) \sum_{j=0}^k \frac{w_j}{x-x_j}y_j.</math>

If the weights <math>w_j</math> have been pre-computed, this requires only <math>\mathcal O(k)</math> operations compared to <math>\mathcal O(k^2)</math> for evaluating each Lagrange basis polynomial <math>\ell_j(x)</math> individually.

The barycentric interpolation formula can also easily be updated to incorporate a new node <math>x_{k+1}</math> by dividing each of the <math>w_j</math>, <math>j=0 \dots k</math> by <math>(x_j - x_{k+1})</math> and constructing the new <math>w_{k+1}</math> as above.

For any <math display=inline>x,</math> <math display=inline>\sum_{j=0}^k \ell_j(x) = 1</math> because the constant function <math display=inline>g(x) = 1</math> is the unique polynomial of degree <math>\leq k</math> interpolating the data <math display=inline>\{(x_0, 1), (x_1, 1), \ldots, (x_k, 1) \}.</math> We can thus further simplify the barycentric formula by dividing <math>L(x) = L(x) / g(x)\colon</math>

:<math>\begin{aligned}
L(x) &= \ell(x) \sum_{j=0}^k \frac{w_j}{x-x_j}y_j \Bigg/ \ell(x) \sum_{j=0}^k \frac{w_j}{x-x_j} \\[10mu]
&= \sum_{j=0}^k \frac{w_j}{x-x_j}y_j \Bigg/ \sum_{j=0}^k \frac{w_j}{x-x_j}.
\end{aligned}</math>

This is called the ''second form'' or ''true form'' of the barycentric interpolation formula.

This second form has advantages in computation cost and accuracy: it avoids evaluation of <math>\ell(x)</math>; the work to compute each term in the denominator <math>w_j/(x-x_j)</math> has already been done in computing <math>\bigl(w_j/(x-x_j)\bigr)y_j</math> and so computing the sum in the denominator costs only <math display=inline>k</math> addition operations; for evaluation points <math display=inline>x</math> which are close to one of the nodes <math display=inline>x_j</math>, [[catastrophic cancelation]] would ordinarily be a problem for the value <math display=inline>(x-x_j)</math>, however this quantity appears in both numerator and denominator and the two cancel leaving good relative accuracy in the final result.

Using this formula to evaluate <math>L(x)</math> at one of the nodes <math>x_j</math> will result in the [[indeterminate form|indeterminate]] <math>\infty y_j/\infty</math>; computer implementations must replace such results by <math>L(x_j) = y_j.</math>

Each Lagrange basis polynomial can also be written in barycentric form:

:<math>
\ell_j(x) = \frac{w_j}{x-x_j} \Bigg/ \sum_{m=0}^k \frac{w_m}{x-x_m}.
</math>