Riemann sums and optimization

Question

I have a question that is related to a question asked on another stackexchange page: integral partition, real analysis

The question on the other page is written out here:

If we have $f(x) = x^2 $ and $P_n $ which partitions $[1,3]$ into $n$ sub-intervals, each equal in length,how can I write the formulas for $L(f,P_n)$ and $U(f,P_n)$ in terms of $n$? Do they converge to the same limit as $n$ goes to infinity?
How large does $n$ need to be so that $U(f,P_n)$ is within $0.01$ of $\int_1^3 \! f(x) \, \mathrm{d}x$ ?

My question is about the last part. I have set up the following

$$\text{min $n$ such that} \frac{26}{3} - (2 + \frac{8(n+1)}{2n} + \frac{4}{3} \cdot \frac{2n^3 + 3n^2 +n}{n^3 } ) \leq 0.01$$

Is there some intuition from the Riemann Integrability of this function that will help me solve for n in a quick way? What is the standard way to do this?

Thanks.

Answer 1

There are error calculations for most of the standard numerical methods of computing integrals, such as the trapezoid rule, Simpson's rule, and yes, even the rectangle rule. These depend both on n and f.

For example for the trapezoid rule the error term on the interval [a,b] can be given as :
E = $\frac {(b-a)^3}{12n^2} f''(c)$ where $a \le c \le b$.

This formula assumes that f'' exists. So for your case the error above would work. Of course you have to assume something about f, or there is no way to bound the error. Assumptions based on the smoothness of f are natural; also easy to prove.

There is a nice write up of this material here: http://pages.cs.wisc.edu/~amos/412/lecture-notes/lecture19.pdf.

Answer 2

You are asking about error estimates for Riemann sums in particular. For some reason the error estimate for the endpoint sums is typically missing from the standard, calculus-level discussion of numerical integration which usually includes the trapezoidal, midpoint and Simpson approximations. I think this is a shame because the endpoint error esimate is simpler -- so simple that when I taught second semester calculus this past semester, I decided that it was worth including a derivation of this error estimate (and it certainly was not for the other error estimates). Here is the result:

Endpoint Approximation Theorem: Let $f: [a,b] \rightarrow \mathbb{R}$ be differentiable, with bounded derivative: there is $M \geq 0$ such that $|f'(x)| \leq M$ for all $x \in [a,b]$. Let $L_n(f)$ be the left endpoint sum -- i..e, the Riemann sum obtained by dividing $[a,b]$ into $n$ equally spaced subintervals and taking the left endpoint of each subinterval as the sample point. Then

$\left| \int_a^b f - L_n(f) \right| \leq \left(\frac{(b-a)^2M}{2} \right) \frac{1}{n}$.

Exactly the same result holds for the right endpoint sums.

For a proof, see Section 9.3 of these notes. (See Section 7.1 for the Racetrack Principle.) Let me say though that they are for a more advanced course. In my freshman calculus course I eventually gave a derivation like that, but I spent much more time motivating the basic idea: imagine that you are an FBI agent trying to capture an escaped criminal. The key questions to ask are: (i) Where did he escape? (ii) When did he escape? (iii) What kind of transportation might he have access to? Or in mathematical terms, (iii$'$): What is an upper bound on his maximum speed? If you know where someone starts, how fast they could possibly be travelling, and how much time has elapsed, you can draw a circular disk on your map in which your criminal must lie. If you want to think of the disk as expanding as a function of time then you get a cone. (This is similar to what is studied in physics, the light cone.) This is for two-dimensional motion. Here we have a real-valued function which corresponds to motion on a line, so the picture is simpler: using the initial position and the maximum speed, you can draw a triangle in which the graph of the function must lie. This is the basic idea which gives you an estimate for a single subinterval. Adding this up over all the subintervals you get the result.

The FBI business is less silly than it sounds: the idea is to get you to see intuitively that the maximum value of $|f'(x)|$ must be taken into account in order to get any bound. As long as $f'$ is continuous, it is bounded on the closed interval $[a,b]$, and that happens e.g. if $f''$ exists. So the hypothesis is mild. And getting bounds on $|f'|$ are exactly what the methods of differential calculus (using $f''$ and perhaps $f'''$) will do for you. The shape of the bound though is that you should expect the error to be about a constant times $\frac{1}{n}$. Note also that this formula is sharp in the sense that it is an equality when $f$ is linear, so it really is "the truth" in some reasonable sense.

You can absolutely use this formula to answer your question about how large $n$ needs to be to get the error less than $.01.$ Try it! I just did a quick mental calcuation and got $n \geq 1200$, but you should check me on that. Here, since $f$ is increasing, the upper sum is just the right endpoint sum. Actually, when $f$ is increasing you know that the error is at most the difference between the upper sum and the lower sum, which is just $(f(b)-f(a))(b-a)) \cdot \frac{1}{n}$, which is an even easier way to see that the error is on the order of $\frac{1}{n}$. But for a non-monotone function the upper and lower sums are rather theoretical: you will need to solve $n$ different optimization problems to compute them exactly...good luck with that. Thus we estimate the error with endpoint sums instead because we can actually compute them.

Notice though that all this says that in order to get $k$ decimal places of accuracy for $\int_a^b f$ we will need to add together some constant times $10^k$ terms. Do we really need to compute so many terms to get $k$ decimal places of accuracy? No, at least as long as $f$ is reasonably smooth. This is where the other numerical integration (or quadrature) methods come in. They are cleverly weighted averages of the endpoint sums which converge much faster. For instance, Simpson's Rule says that if $f$ has a bounded fourth derivative then some slightly strange-looking variant $S_n(f)$ of the endpoint sum approximates $f$ to within $C \frac{1}{n^4}$, where the constant $C$ depends upon the size of $|f''''(x)|$. There are infinitely many more rules: in other words, if $f$ has a bounded $k$th derivative, then there is some weighted average of Riemann sums that when you add up $n$ terms of it, you will approximate $\int_a^b f$ to within $C \frac{1}{n^k}$, where the constant $C$ depends upon the maximum value of $|f^{(k)}|$ on $[a,b]$.

Note finally that there is a version of all of these rules which gives an equality for the error rather than the inequality. This expression for the error is in terms of a certain derivative of $f$ at an unknown point $c \in [a,b]$. These types of results come from a similar exact expression of the error in Taylor's Theorem and ultimately are just souped up versions of the Mean Value Theorem: $f(b) = f(a) + (b-a)f'(c)$. However, in general you don't know what $c$ is, so the only obvious way to use these expressions is to get an upper bound for the error by bounding $|f^{(n)}(x)|$ on $[a,b]$. Thus although in some sense the exact expressions look more elegant, in practice I don't know a single situation in which it is helpful to the have them rather than the corresponding inequality. I would be very interested to learn of such an instance.