# Recursive scheme for trapezoidal rule

I was supposed to derive the recursive scheme for the trapezoid rule. I know that this is the formula:

$$T_m (f;P) = \frac{1}{2} T_{m-1}(f;P) + \cdots$$ Initialization: $$T_0 (f;P) = \frac{h}{2}(f(a) + f(h))$$

I came across a sample solution: $$T_m = C + h \sum\limits_{i=1}^{2^m -1} f(x_i)$$

$$T_{m+1} = \frac{C}{2} + \frac{h}{2} \sum\limits_{i=1}^{2^{m+1} -1} f(x_i)$$

$$T_m - 2T_{m+1} = C + h \sum\limits_{i=1}^{2^m -1} f(x_i) - \frac{C}{2}2 -2h\sum\limits_{i=1}^{2^{m+1} -1} f(x_i)$$ (3)

$$T_m - 2T_{m+1} = h \sum\limits_{i=1}^{2^m -1} f(a+(2i-1)h)$$ (4)

Firstly, I cant understand why we're calculating $$T_m - 2T_{m+1}$$ while the original formula is different. How is this derived? Why do we write f(a+(2i-1)h?

Secondly, how is equation 3 changed to equation 4? If we subtract the h values, the Cs cancel out but shouldn't we get a -h value?

• I don't really understand what you're trying to do, I guess $T_m$ is the trapezoidal rule on $2^m$ nodes? Anyway, just following what you already wrote, there's a $\frac{h}{2}$ there with $T_{m+1}$, so you should have a coefficient of $-h$ outside that last sum. Then the values of $f(x_i)$ common to both sums will cancel, while the terms that are an odd number of steps from $a$ will only be in the second sum, so there should be a minus sign in equation (4).
– Ian
May 10 '20 at 1:58
• This is a sample solution that I came across. It didn't look correct me to and I also thought there should be a - sign. But then I'm still don't know how to derive the recursive scheme @Ian
– x89
May 10 '20 at 2:02
• There are some minor errors but the general idea seems right. Basically you start with $\frac{b-a}{2}(f(a)+f(b))$, then you take half of that and add $h=\frac{b-a}{2}$ times the value at the midpoint, then you take half of that and add $h=\frac{b-a}{4}$ times the values at the intermediate midpoints, and so forth. The result is just the ordinary composite trapezoidal rule on $2^m$ nodes. The only reason you would do this recursively is to dynamically decide how many nodes to use (perhaps because you're trying to do adaptive quadrature without a uniform mesh size everywhere).
– Ian
May 10 '20 at 2:27
• Additionally, I am unable to comment here but could you please explain how the identity matrix is involved then? math.stackexchange.com/questions/3613065/…
– x89
May 11 '20 at 1:54
• You have a difference of two sums, one has all the terms, one has just the terms an even number of steps from $a$, so the difference has just the terms an odd number of steps from $a$. Again this is an insignificant optimization by itself but they are using it to motivate more useful ideas like Romberg integration.
– Ian
May 11 '20 at 10:54

You could simply put $$T_{m+1}=\frac12(T_m+M_m)$$ where $$M_m$$ is the composite midpoint quadrature rule for the same step size. Then the two terms on the right side are both approximations of the integral, which makes it natural that you have to divide their sum by 2 to get another approximation of the integral.
More specifically, your last formula is wrong on two counts, you lost the minus sign, and the step size for the $$x_i$$ in $$T_{m+1}$$ is $$\frac h2$$, ... three counts, the sum over the odd-index points has to start at index $$i=0$$ so that $$2i+1=1$$ is the lowest index, ... no wait, four counts, in the formula before the point sequences are different in the first and second sum, one for step size $$h$$, the other for step size $$\frac h2$$, make the first the subsequence $$x_{2i}$$ of the second, ... so that in total \begin{align} T_m-2T_{m+1} &=C + h \sum\limits_{i=1}^{2^m -1} f(x_{2i}) - 2\frac{C}{2} -2\frac h2\sum\limits_{i=1}^{2^{m+1} -1} f(x_i) \\ &=-h\sum\limits_{i=0}^{2^m -1} f(x_{2i+1}) \\ &=-h\sum_{i=0}^{2^m-1}f(a+(i+\tfrac12)h)=-M_m \end{align}
• The points of $T_m$ are $(a+ih)$. The points for $T_{m-1}$ are $(a+j(2h))=(a+(2j)h)$, so that these are at the same time the even points of the first sequence. The set difference of both are the odd points of the first sequence. May 11 '20 at 5:12