CHAPTER 07.04: ROMBERG INTEGRATION: Theory: Part 1 of 2

In this segment, we’re going to talk about Romberg integration, and we'll talk about the theory or the background behind how Romberg integration works.  We are limiting our discussion to trapezoidal rule, so far as what the Romberg integration is based on, because Romberg integration can be based on other rules as well, such as Simpson's 1/3 rule or Simpson's 3/8 rule, so we're going to limit our discussion on the Romberg integration based on trapezoidal rule. As we have seen, we already talked in the last segment, about Richardson's extrapolation formula. In the Richardson's extrapolation formula, we basically said that if we have n segments, and somebody is using 2 n segments for the trapezoidal rule, whatever numbers we get for the approximate value by using n segments and 2 n segments, we can take those two values, so let's suppose if we call this In, we call this I2n, so this is what we get by using the multiple segment trapezoidal rule using n segments, and this is the multiple segment trapezoidal rue approximation which we get for an integral, which is of the form a to b, f of x dx, of course, and we get the value to be I2n, then we can find a better value for the true value of this integral.  It's still approximate, but through extrapolation, we can find this to be I2n, plus I2n minus In, divided by 3. What this was based on the fact was that the true error in trapezoidal rule is approximately proportional to 1 by n squared. So as you keep on doubling the number of segments, for example, your true error gets quartered.  So based on that, we were able to derive this particular formula here, and that's how we are able to get a better approximation of this particular integral here. Now, what Romberg says is that we can . . . what we can do is we can take these . . . these approximations which we're getting for the true value based on these two numbers, and we can continue to make better approximations by getting more values for, let's suppose if we get an approximation with n segments, then 2 n segments, then we can get 4 n segments, then 8 n segments, and so on and forth, we can use that to . . . to get better approximations.  What I mean by that is that, let's suppose somebody is using n segments, then they use 2 n segments, then they use 2 n segments, then they use 4 n segments, then they use 8 n segments, we can always calculate the Richardson's extrapolation formula based on these numbers which we are getting for the approximate values.  So let's suppose this is In, this is I2n, this is I4n, this is I8n, the subscripts standing for how many segments you are using for developing the approximation, you can take this value and this value, and get a better approximation right here, then you can take this value and this value, and get a better approximation here, you can take this value and this value, and get a better approximation here. What Romberg is saying that let's take a step further, or several steps further, is that we can take these two values, and get a better approximation.  So we take these two values, get a better approximation, take these two values, get a better approximation, so we're going to get a value here and a value here, then we can take those two approximations, and get a better value there, and that's how it will work.  In fact, if we had more values from, let's suppose 16 n segments and 32 n segments, this tree can keep on going.  Now, what is that based on?  It is that we got this particular . . . this first-order . . .  first-order extrapolation which we had, this first-order extrapolation which we had by Richardson's extrapolation formula, it was based on that the true error is approximately proportional to c h squared, so that's . . . or, let me not write down c h squared, because we are not talking about like that, that the true error is approximately proportional to 1 by n squared, so that's what we had obtained there. Now, what's going to happen is that the way come up with better approximations, because we tried to see that, hey what is the true error approximately proportional to in this case? And then when we are trying to find some other values, or when we go down the tree here, what is the true error approximately proportional to?  So that's what we need to look at and be able to figure out that how can we get better approximations, because we cannot simply get this approximation and this approximation based on the same formula as we obtained these approximations, where we had simply I2n, plus I2n . . . so here we had I2n, plus . . . let me just write it down here, so here we had I2n, plus I2n minus In, divided by 3, that's what we had there, but it doesn't meant that this formula is going to be the similar kind of formula, or this formula here, by which you're going to be calculating here will be by the same formula. So that's not true, so we'll see that how that works out.  So what it is based on is as follows, that if we know that the true error for Richardson's extrapolation formula is proportional to 1 by n squared.  That means the same thing as saying that it's approximately proportional to h squared, where h is the width of the segment, because we'll know that n squared, 1 by n squared is simply a measure of how many, 1 by n is basically a measure of how many segments do I have, or what the segment width is, so we know that the true error then will be proportional to, approximately proportional to h squared. It so happens that, without proof I'm showing it to you, that the true error in . . . in the trapezoidal rule is basically of this form.  It is proportional to h squared, but if you look at the next terms which come into the true error formula here, again, I'm showing it to you without proof, the proof is out of the scope of this particular class here, this is what it turns out to be.  It turns out to be that the first order of the true error is proportional to h squared, just like we have shown it here, but the second term skips the cubic . . . the cubic term, which is the h cubed term, and go simply to h to the power 4, and the next one goes to h to the power 6, and so on and so forth.  So this is what the true error of the multiple segment trapezoidal rule.  Now, keep in mind that A1, A2, A3, they are not necessarily constants, they are based on the derivatives of the function which you . . . which you are integrating, and it's based on where you are calculating those derivatives. So it's a little bit more complicated than I would like to talk about, so that's why I'm skipping it.  So A1, A2, A3 are not necessarily constants, but what you have to basically concentrate on is that the true error is proportional to h squared, the term will be proportional to h to the power 4, and the next term, the true error will be proportional to h to the power 6. So what happens is that once you have, let's suppose, once you have, let's suppose calculated the value with n and 2 n segments, so you have calculated this value with n and 2 n segments, which we'll call it In and I2n, then you are using this particular formula, based on that the true error is proportional to h squared, we said that the new value which we get is I2n, plus I2n minus In, divided by 3.  Now, if are going to, let's suppose, calculate 4 n here, we get I4n here, and I can calculate the value here to be I4n, plus I4n minus I2n, divided by 3, a better approximation of the integral. So what happens is that, how do I refine this value? I don't use 3 as the denominator, but what I'm going to do is I'm going to say whatever this value is, let's suppose I call this to be J2n, and I call this to be . . . let me call this Jn, and let me call this J2n, these numbers, for the time being. So what will happen is that this number here, in order to get the better approximation, that'll be based on J2n, plus J2n minus Jn, divided by 15, not 3.  Now, where does this 15 come from?  It is basically that, hey, that the error for these terms, that the error, the true error in these terms is now proportional to h to the power 4, and that's where this 15 comes from.  So the error in Jn and J2n is proportional to the h to the power 4, so that's why once you start developing the equations for it, you get this 15 here.