CHAPTER 07.04: ROMBERG INTEGRATION: Richardsons Extrapolation of Trapezoidal Rule: Theory

In this segment, we're going to talk about Richardson's extrapolation formula for integration. I'm going to discuss the theory in this segment, we will take an example in the next segment.  Now, what is the Richardson's extrapolation formula based on?  It is that the true error . . . that the true error in trapezoidal rule, in multiple segment trapezoidal rule, is proportional to 1 by n squared.  What that basically means is that the true error is proportional to 1 divided by the square of the number of segments which you are choosing for the trapezoidal rule, so this is for the trapezoidal rule, we have already derived this particular formula here. So what that means is that as you . . . so in layman's language, what we can say is that if we double the number of segments in trapezoidal rule, what's going to happen to the true error is it's going to get quartered.  So it's not simply a linear proportional relationship, that if you double the number of segments that the true error gets halved, no. If you double the number of segments in multiple segment trapezoidal rule, what's going to happen is that true error is going to get quartered, and what we want to do in the Richardson's extrapolation formula is take advantage of this particular relationship, that the true error is approximately proportional to 1 by n squared, to be able to come up with a better estimate of our integrals base on what we have already calculated for a certain number of segments, and we'll see that through an example, also. So for example, what we can do is we can say that the true error is approximately, then c by n squared.  Again, the reason why it's approximately, because this true error is not exactly proportional to 1 by n squared, so we're going to use c as a constant of proportionality saying that the true error is approximately proportional to c by n squared, to get rid of this proportional term.  So we already know that the true value, which I have called as TV, so TV is . . . if TV is the true value, then we know that the true value is always defined as approximate value . . . or let's go ahead and look at the definition of true error. We already know that the true error is defined as true value minus approximate value, that's the very definition of true error, that if you know the approximate value and you subtract that approximate value from the true value, you get what the true error is.  So what that implies is that true value is same as the approximate value plus the . . . plus the true error, right?  Now, if we know that the true error is approximately proportional to c by n squared, what we can do is we can say that, hey, the true value of the integral is approximately equal to the approximate value of the integral which you are getting by using n segments, plus the true error which you get by using n segments, so this is exactly equal to, okay?  So the true value is equal to the approximate value which you are getting by using n segment trapezoidal rule, plus the true error associated with the n segment trapezoidal rule, because this is the definition of true value, approximate value plus true error, or it's coming from the definition of true error, which is simply true value minus approximate value. Now, this will, if I substitute, if I say, okay, this is the approximate value which I get by using n segments by using the n segment trapezoidal rule formula, and if I say c divided by n squared here, then this true value becomes approximately equal to that, because I am substituting an approximation for the true error, so it becomes plus c divided by n squared.  Now, the way I take advantage of this particular formula here, that the true value of the integral is the approximate value which I get by using n segments, plus some c divided by n squared, is that I'm going to say, okay, I'm going to double the number of segments.  I'm going to still use the same multiple segment trapezoidal rule formula, I'm going to double the number of segments. Then what will be the true value equal to by using the same definition here? It will be true value will be approximately equal to AV, the approximate value obtained by 2 n segments, plus c divided by 2 n, squared, because that's the only difference, you are doubling the number of segments, so that makes it same as AV 2 n, plus c divided by 4 n squared. So if this is equation number 1, and this is approximate equation number 2, you can very well see that there are only two unknowns in these two equations.  So between this equation and this equation, there are only two unknowns.  What are the two unknowns?  They're c and the true value, because we know what the approximate value of the integral is by using n segments or by using double the number of segments, we also know what the value of n is, because we are choosing how many segments we're going to use, so we know that there are two unknowns, true value and c, but what I'm going to do is I'm going to try to get rid of this c here, because that will allow me to figure out what the true value approximately will be equal to. So what I'm going to do is I'm going to take equation number 1, I'm going to subtract 4 times equation number 2, that's what I'm going to do. So I'm going to take equation number 1, and I'm going to subtract 4 times equation number 2, because if I multiply this by 4, this will become same as this. So what that tells me is that I'll get true value, this is the first equation, approximate value of n, plus c divided by n squared, so that's my first equation, and the second equation, by multiplying by 4, becomes 4 times true value is approximately 4 times AV 2n, plus c by n squared, and that's equation number 2 multiplied by 4, that's what I get. I'm going to subtract it, so when I subtract it, that cancels, and I get -3 TV is equal to AV of n, minus 4 AV 2 n, so that's what I get.  So I'm going to write it again here. So I get -3 true value is approximately equal to, this is approximately, approximately equal to AV of n, minus 4 AV of 2 n, and then that gives me true value is equal to, when I'm going to divided by -3, I'm going to get 4 AV 2 n divided by 3, minus AV of n divided by 3, and this I can write as 3 AV of 2n, plus AV of 2n, minus AV of n, divided by 3, I'm just breaking the 4 into 3 plus 1, which is 4, and that gives me AV of 2 n, this is approximately equal to, AV of 2 n, plus 1/3 of AV of 2 n minus AV of n.  It's just a different way of writing it, the reason why it's written like this is because it basically says that, hey, whatever is the approximate value which you obtained by doubling the number of segments, in order to get a more refined value, all you have to do is to take the difference between what you got with doubling the segments and what you had with the n segments, you take the difference of the two, take one third of that, and that's going to be the refinement, which will give you a better estimate of the true value.  And that's the Richardson's extrapolation formula, and what you can do is you can choose n to be any number of segments, and continue to do this as you double the number of segments.  So you can start with n equal to 2, let's suppose, or 1, so you can go from n equal to 1, then 2, then 4, then 8, then 16, and you can always get a better estimate from here, then a better estimate from here, then a better estimate from here, and a better estimate from here, and that's what Richardson's formula is.  What Romberg is that it then starts going like this, getting a better estimate like this, then getting a better estimate like this, and then getting a better estimate like this, and that's something which we will talk about in a separate segment, but Richardson's extrapolation formula just is up to the first, go 1 and 2, 2 and 4, 4 and 8, 8 and 16, and calculate a better estimate.  What Romberg does is that it takes these better estimates now, and further refines them by using the true error principle to get a better and better estimate of the integral. So in the next segment, what we're going to do is we're going to take an example to show how this Richardson's extrapolation formula works on a simple integral.  And that's the end of this segment.