5 ms·

How does it follow that the mediant (a+c)/(b+d) is a better approximation than both a/b and c/d? One of the bounds could be very close to the quantity you are t

How does it follow that the mediant (a+c)/(b+d) is a better approximation than both a/b and c/d? One of the bounds could be very close to the quantity you are trying to approximate already.

GuB-42 4y ago
Looking at the comments, you can iterate this, and eventually you will get a better approximation than both a/b and c/d. But sure enough, after a single iteration, (a+c)/(b+d) is not always better.
- madcaptenor 4y ago
  If you iterate this, I think you get the continued fraction convergents, which are the "best" rational approximation to the irrational you're trying to approximate. (I did some numerical experiments and this looks true; I didn't prove it.)
- geysersam 4y ago
  I found the thing about iteration quite strange. To iterate, we need to know if our mediant is larger or smaller than the true value. How do we know that? Edit: elsewhere in the thread someone explained that the purpose of iterating is to find an approximation with small denominator.
  - madcaptenor 4y ago
    e isn't the best example for this, because you would need a good decimal expansion. But say we're trying to approximate sqrt(2) by this method. Say we've already established that it's in the interval [7/5, 10/7]. We can verify because 7^2 < 2*5^2 and 10^2 > 2*7^2. Then the mediant is 17/12, and since 17^2 = 289 > 288 = 2*12^2, we know 17/12 > sqrt(2). So [7/5, 17/12] is a smaller interval containing sqrt(2). Repeating this, [24/17, 17/12] is even better, and so on.
ggeorgovassilis 4y ago
That was also a (up to now) unanswered question a reader posted.
geysersam 4y ago
It doesn't. Neither is the average. To say such a thing, we need: 1. Some assumption about the distribution of the true value. 2. And a metric measuring the "cost" of being wrong. Assuming a uniform distribution, and measuring cost as the expected absolute value of the error, we find that the average of the interval is the best guess. Using the same assumptions, any number in the interval is a better estimate than the endpoints. From that it (obviously) follows that the mediant is a better approximation than both endpoints.
- madcaptenor 4y ago
  The average of the interval is the best guess if you are only trying to minimize the error. But if you want to also keep the denominator small that's when the problem gets more interesting.
madcaptenor 4y ago
Maybe it's better to formalize this in terms of having a rational interval as the approximation of an irrational - for example the interval [19/7, 87/32] approximates e. That's an interval of width 1/224. Then if [a/b, c/d] contains the irrational number x, then: - either [a/b, (a+c)/(b+d)] or [(a+c)/(b+d), b/d] contains x, and - whichever one contains x is smaller than the original. Written that way it's trivial, though. The real meat, I suppose, is that using the mediant keeps the numerators and denominators small. In this case, [106/39, 87/32] has width 1/1248 and contains e, whereas using the mean would give you the interval [1217/448, 87/32] of width 1/448.

How does it follow that the mediant (a+c)/(b+d) is a better approximation than both a/b and c/d? One of the bounds could be very close to the quantity you are trying to approximate already.

GuB-42 4y ago

Looking at the comments, you can iterate this, and eventually you will get a better approximation than both a/b and c/d. But sure enough, after a single iteration, (a+c)/(b+d) is not always better.

madcaptenor 4y ago
If you iterate this, I think you get the continued fraction convergents, which are the "best" rational approximation to the irrational you're trying to approximate. (I did some numerical experiments and this looks true; I didn't prove it.)
geysersam 4y ago
I found the thing about iteration quite strange. To iterate, we need to know if our mediant is larger or smaller than the true value. How do we know that? Edit: elsewhere in the thread someone explained that the purpose of iterating is to find an approximation with small denominator.
- madcaptenor 4y ago
  e isn't the best example for this, because you would need a good decimal expansion. But say we're trying to approximate sqrt(2) by this method. Say we've already established that it's in the interval [7/5, 10/7]. We can verify because 7^2 < 2*5^2 and 10^2 > 2*7^2. Then the mediant is 17/12, and since 17^2 = 289 > 288 = 2*12^2, we know 17/12 > sqrt(2). So [7/5, 17/12] is a smaller interval containing sqrt(2). Repeating this, [24/17, 17/12] is even better, and so on.

ggeorgovassilis 4y ago

That was also a (up to now) unanswered question a reader posted.

geysersam 4y ago

It doesn't. Neither is the average. To say such a thing, we need: 1. Some assumption about the distribution of the true value. 2. And a metric measuring the "cost" of being wrong. Assuming a uniform distribution, and measuring cost as the expected absolute value of the error, we find that the average of the interval is the best guess. Using the same assumptions, any number in the interval is a better estimate than the endpoints. From that it (obviously) follows that the mediant is a better approximation than both endpoints.

madcaptenor 4y ago
The average of the interval is the best guess if you are only trying to minimize the error. But if you want to also keep the denominator small that's when the problem gets more interesting.

madcaptenor 4y ago

Maybe it's better to formalize this in terms of having a rational interval as the approximation of an irrational - for example the interval [19/7, 87/32] approximates e. That's an interval of width 1/224. Then if [a/b, c/d] contains the irrational number x, then: - either [a/b, (a+c)/(b+d)] or [(a+c)/(b+d), b/d] contains x, and - whichever one contains x is smaller than the original. Written that way it's trivial, though. The real meat, I suppose, is that using the mediant keeps the numerators and denominators small. In this case, [106/39, 87/32] has width 1/1248 and contains e, whereas using the mean would give you the interval [1217/448, 87/32] of width 1/448.