# Optimal integration rule for square of derivative

Say I have a function $f:[0,1]\to \mathbb{R}$, such that $f^{(3)}$ exists and is bounded. I want to approximate $\int_{0}^{1} (f'(x))^2 dx$ using the values $f(\frac{i}{n})$, $0 \le i \le n$. (we'll denote $\frac{1}{n}$ by $h$ for readability.)

The naive approximation is $f'(x) \sim \frac{f(ih)-f((i-1)h)}{ih-(i-1)h}$ on $[(i-1)h,ih]$, which gives $\int_{0}^{1} (f'(x))^2 dx \sim h\sum_{i=1}^{n} (\frac{f(ih)-f((i-1)h)}{h})^2$. Using the Taylor expansion of $f$ and $f'$ gives that the error term is $O(h^2)$ with constant depending on the maximum of $|f^{(i)}|$ on $[0,1], 1\le i \le 3$.

My question is: can we do better? Is there an integration rule using $f(ih)$ with error of order $O(h^p), p>2$?

-

Not quite an answer, but Cruz-Uribe and Neugebauer analyzed and obtained sharp error bounds of the trapezoidal and Simpson's rules for low regularity functions. They don't actually consider $C^2$ functions; but their results apply to the Sobolev space $W^{2,\infty}$, which is essentially the same norm you use in the $C^2$ estimate anyway. (By doing a transformation $f(x) \to f(x) + Cx$ for large $C$, you see that issues with regards to error estimates for your original problem is identical to issues for error estimates for integrals of generic twice differentiable functions.) They showed that in the scale of $O(h^s)$, $s = 2$ is sharp for both trapezoidal and Simpson's rules. Their analysis likely can carry over also for all numerical integration schemes in the Newton-Cotes series, yielding the same result.
But particularly interesting is Theorem 1.23, which shows that using Simpson's rule for the twice differentiable case the error is actually $o(h^2)$, while trapezoidal rule is bona fide $O(h^2)$ (unless your function is linear). In view of their previous theorem, this suggests that there may be a further logarithmic correction available in the error estimate if you use Simpson's rule. (On the other hand, it is most likely that higher order Newton-Cotes schemes won't do better [and possibly will do even worse; in the paper it was shown that for once differentiable or merely Hölder continuous functions, trapezoidal rule actually out performs Simpson, since the latter may pick up high frequency artifacts] for only twice differentiable functions.)
Note that there are two errors in your problem, one coming from approximating $f'$ using discrete values of $f$, and another from approximating $\int (f')^2 dx$ using some numerical integration rules. The above says that the second approximation cannot really do better than $O(h^2)$, so it doesn't really matter how well you can get the first approximation. – Willie Wong Jun 25 '11 at 16:33