Integrating Lagrange polynomials

Question

Could you suggest some efficient way to numerically compute $\int\limits_0^{t_i}l^N_j(t)dt$, where $l^N_j(t)$ is the $j$th N-point Lagrange polynomial and $t_i$ is the $i$th interpolation point?

Answer 1

You are willing to integrate the polynomials $\dfrac{P_j(x)}{P_j(x_i)}$, which are defined as

$$P_j(x)=\prod_{k=1,k\ne j}^n(x-x_k)=\frac{P(x)}{x-x_j}.$$

The coefficients of the global polynomial $P$ can be computed in $O(N^2)$ operations by multiplying all monomials iteratively.

Then the coefficients of a $P_j$ are obtained by long division by the monomial $x-x_j$, in $O(N)$ operations. The denominator is then computed in $N$ operations by Horner, and so is the antiderivative at $x_i$.

Hence the evaluation of the coefficients has complexity $O(N^2)$, which is optimal. Unfortunately, if you are willing to compute all the $\int P_j(x_i)$, every evaluation costs $O(N)$, for a total of $O(N^3)$.