# Are there quadrature methods allowing to track current progress, converging faster than Monte-Carlo?

Consider an integral to evaluate:

$$I=\int_a^b f(x)\,\mathrm dx.\tag1$$

In the Monte-Carlo quadrature, if $$I_n$$ is $$n$$th estimate of $$I$$, then for $$(n+1)$$th estimate we have:

$$I_{n+1}=\frac{nI_n+f(\operatorname{rand}())(b-a)}{n+1}.\tag2$$

This lets one track current estimate at each step, with constant rate of updating.

Monte-Carlo quadrature converges as $$\delta I_n=O(n^{-1/2})$$, which is quite slow. A faster approach could be the trapezoidal rule. With it, if we define (for $$n$$ being number of points)

$$S_{n+1,\,\alpha,\,\beta}=\sum_{k=1}^{n-1+\beta} f\left(a+\frac{b-a}n (k+\alpha)\right),$$

then

\begin{align} I_{n+1} &=\frac{b-a}{n }\left(\frac{f(a)+f(b)}2+S_{n+1,\,0,\,0}\right),\\ I_{2n+1}&=\frac{I_{n+1}}2+\frac{b-a}{2n}S_{n+1,\,0.5,\,1}. \end{align} \tag3

Its convergence in the number of points taken is better: $$\delta I_n=O(n^2)$$. But to update without needless re-evaluation of $$f$$ and without storing most of its values (except $$f(a)+f(b)$$), we have to do twofold increase of $$n$$ each time. This means that rate of updating drops exponentially each update, although the precision does increase quadratically with number of points.

I'm looking for a quadrature method, which would combine the good properties of the two methods described above:

1. Rapid convergence (quadratic in number of points or better),
2. Reuse of previous result without storing most of the values of integrand,

Is there any such method?

• Well you could always do trapezoidal with $2$ steps, then $4$ steps, then $8$ etc. This allows you to use the previous computed values and you still have quadratic convergence. Wouldn't this satisfy all your requirements? Apr 7, 2019 at 19:58
• @Winther this will not satisfy requirement #3: doing more steps means taking more time for an update. Apr 7, 2019 at 20:31