= Barycentric interpolation formula
{title2=$p_n(x)=\dfrac{\sum_i w_i y_i/(x-x_i)}{\sum_i w_i/(x-x_i)}$}
The <barycentric interpolation formula> evaluates the same <Lagrange polynomial> using weights that depend only on the distinct <interpolation nodes>:
$$
w_i=\frac1{\prod_{j\ne i}(x_i-x_j)},\qquad
p_n(x)=\frac{\displaystyle\sum_{i=0}^n\frac{w_i y_i}{x-x_i}}
{\displaystyle\sum_{i=0}^n\frac{w_i}{x-x_i}},\qquad x\ne x_i.
$$
At $x=x_i$, return $y_i$ directly, before dividing; the formula has <removable singularities> at the <interpolation nodes>. Multiplying every $w_i$ by the same nonzero constant leaves the answer unchanged. Driscoll and Braun derive this formula as a more efficient, numerically stable way to evaluate <polynomial interpolation>.https://fncbook.com/barycentric/[Driscoll and Braun, Fundamentals of Numerical Computation, §9.2, Theorem 9.2.1 and Algorithm 9.2.1]{ref}
For the <interpolation nodes> $0,1,2$, the weights are $(1/2,-1,1/2)$, or equivalently $(1,-2,1)$. With data $(1,2,5)$, at $x=1/2$ the denominator using the latter weights is $2+4-2/3=16/3$ and the numerator is $2+8-10/3=20/3$, giving $p_2(1/2)=5/4$ again. For eleven <interpolation nodes> in the <Runge phenomenon> figure, the generator computes the weights by the direct products above and returns stored values exactly at every <interpolation node>.
The direct products require $O(n^2)$ <arithmetic operations> once; each subsequent value uses $O(n)$ <arithmetic operations>. Here $O$ denotes <Big O notation>. At large <polynomial degree> or on poorly scaled intervals, forming these products can exceed the range of <floating-point arithmetic>; normalization or specialized weight formulas may be needed. Stable evaluation also cannot cure sensitivity intrinsic to the chosen <interpolation nodes>, measured by the <Lebesgue constant of interpolation>, or the approximation failure in the <Runge phenomenon>.
Back to article page
