4

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?

Dmitry
  • 1,337
  • 1
    What about computing the coefficients of the $N$ polynomials iteratively (i.e. adding one point at a time). I guess that this will take $O(N^3)$ operations. Then by Horner the evaluation of the integrals will take $O(N^2)$. –  Apr 15 '16 at 10:53
  • Thank you, Yves. Indeed, I use a similar approach. I was thinking though that there might be some more specific algorithm for doing this... – Dmitry Apr 15 '16 at 14:37
  • You are willing to compute $N^2$ numbers from $2N$ input values. Intuitively there is a hope that $O(N^3)$ is overkill. –  Apr 15 '16 at 15:04

1 Answers1

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)$.