# RichardsonianExtrapolation

How can you measure something wiggly? For example, what's the length of a path that isn't a straight line? Sure, some curves have computable lengths: the circumference of a circle, the arc of a parabola, and so forth. But those are special cases, mathematically simple in one way or another.

For an arbitrary shape, in real life the best that one can do is to take samples --- points every so often along the route --- and then do a connect-the-dots game between those points (or maybe even fit a smoother curve through them). If the sample points are close enough together they may track the actual path pretty accurately. But how accurately? And can one do better without laboriously gathering a hugely greater number of data points?

Lewis Richardson, a computational meteorologist of the early 20th Century (see CookingTheBooks (8 Jun 2001) and ForecastFactory = http://www.his.com/~z/weather.html ) had a smart idea: take giant steps and make a crude estimate of the curve's length. Then try again, with baby steps. Compare the results for various step sizes, and extrapolate the answer to the impossible ideal of infinitesimally tiny increments.

The answer might not converge. Some shapes get wigglier as one looks at them more and more closely; they're called "fractals" in the mathematical limit. But for many practical purposes Richardson's trick can be a good way to get a sharp estimate of path length.

The idea of Richardsonian extrapolation came to mind recently in the context of measuring my jogging trails around the neighborhood (see GlobalPositioningSystemRuns (16 Feb 2002) and RaggedRunner (23 Mar 2002)). My GPS-based estimates always seemed to come out ~10% short compared to the distance that I thought I had run. Was the problem related to the fact that my path was curvy?

To test the hypothesis that Richardsonian extrapolation could give a more precise answer, last week I took coordinate readings every 2 minutes as I ran along the last few miles of the Montgomery County "Marathon in the Parks" route near my home. I lost the satellite signals, of course, at several places (e.g., going through a long tunnel under a major urban thoroughfare). But I ended up with over 40 good latitude-longitude pairs, recorded to within a few seconds of arc.

A simpleminded connect-the-dots between 2-minute markers yielded a distance of 7.7 miles --- suspiciously low even when allowing for (a) my snail-like pace, (b) delays while I waited to cross streets through heavy traffic, and (c) the time I spent locating the finish line of the marathon in front of a swanky sidewalk café in downtown Bethesda. (I wonder what the diners thought of me, sweaty and clutching my GPS receiver while I looked at parking meter serial numbers to find the exact endpoint of the race?)

So I modified my spreadsheet to compute the distance based upon twice the step size, using the samples taken every 4 minutes. The result: 7.0 miles for odd-numbered coordinate pairs, and 7.3 miles for even ones. Shorter yet, because the larger spacing missed many more curves and jitters in my path.

But now apply Richardson's magic: average the 4-minute estimates, extrapolate through the 2-minute estimate, and you come out with, voila, a figure of 8.2 miles for an imaginary "0-minute" continuous sampling rate. And that 8.2 mile value fits quite well with the measured course markers painted on the road and my time between them. Maybe this approach is worth testing in other contexts.

True confession: I haven't ever seen the above tactic for path-length estimation published anywhere. It came to me while I was out running. (An original ^z thought? --- stop the presses!) But really it's a pretty obvious hack, and probably can be derived as a special case of the more general Richardsonian method for the numerical solution of systems of differential equations. If anybody is curious about the equations, please contact me and I'll bore you with the gory details.