The Power of the 2-gon: Extrapolation to Evaluate Pi

Lewis Fry Richardson

Richardson’s extrapolation procedure yields a significant increase in the accuracy of numerical solutions of differential equations. We consider his elegant illustration of the technique, the evaluation of ${\pi}$ , and show how the estimates improve dramatically with higher order extrapolation.

[This post is a condensed version of a paper in Mathematics Today (Lynch, 2003).]

The Deferred Approach to the Limit

The finite difference method was developed by Lewis Fry Richardson in his study of stresses in masonry dams. The derivative ${dy/dx}$ of a function ${y(x)}$ exists if the ratio ${[(y(x+h)-y(x)]/{h}}$ tends to a definite limit as the increment ${h}$ tends to zero. Differential calculus depends upon justifying the limiting process ${h\rightarrow 0}$ . In approximating a differential equation by finite differences, we reverse the procedure, and replace derivatives by corresponding ratios of increments of the dependent and independent variables. Richardson described the procedure thus:

“Although the infinitesimal calculus has been a splendid success, yet there remain problems in which it is cumbrous or unworkable. When such difficulties are encountered it may be well to return to the manner in which they did things before the calculus was invented, postponing the passage to the limit until after the problem has been solved for a moderate number of moderately small differences.”

Richardson called this postponement of the process ${h\rightarrow 0}$ `the deferred approach to the limit’. The accuracy of the finite difference approximation depends on the grid size ${h}$ . Richardson was one of the first to analyse the behaviour of the errors. He was careful to use centered differences wherever possible, so the derivative ${dy/dx}$ would be replaced by ${[y(x+h)-y(x-h)]/{2h}}$ . For centered differences, the accuracy is typically of the second order; that is, the error diminishes like ${h^2}$ as ${h\rightarrow 0}$ .

The quadratic behaviour of the errors provides a universal means of checking and correcting them. If the quantity ${f(x)}$ to be evaluated is estimated by ${F(x,h)}$ , we assume

$\displaystyle F(x,h) = f(x) + k_2(x)h^2 + k_4(x)h^4 + k_6(x)h^6 + \cdots \,, \ \ \ \ \ (1)$

where the functions ${k_n(x)}$ are generally unknown and where odd powers of ${h}$ are absent. For small ${h}$ it may be sufficient to retain only the first two terms, ${F(x,h) = f(x) + k_2(x)h^2}$ . Then if ${F}$ is computed for two different grid sizes, ${h_1}$ and ${h_2}$ , the solutions being denoted ${F_1}$ and ${F_2}$ , we can eliminate ${k_2}$ and obtain

$\displaystyle f(x) = F_2 + \frac{\rho^2}{1-\rho^2}(F_2-F_1) \ \ \ \ \ (2)$

where ${\rho=h_2/h_1}$ . This is what Richardson calls ${h^2}$ -extrapolation. He notes that the method may be refined: if the solution is calculated for three values of ${h}$ , the ${k_4}$ term may also be eliminated; this is ${h^4}$ -extrapolation. The extension to higher orders is obvious. The \hbox{ ${h^{2n}}$ -extrapolation} requires the solution of a system of ${n+1}$ simultaneous linear equations

$\displaystyle F_k = f(x) + k_2h_k^2 + k_4h_k^4 + \cdots + k_{2n}h_k^{2n}\,, \quad k=1,2,\dots ,n+1 \,.$

It is an arithmetic burden, but an elementary task, to solve for ${f(x)}$ .

Estimating ${\pi}$ by Extrapolation

To illustrate the power of his extrapolation method, Richardson considered the ancient problem of evaluating ${\pi}$ . The approximation of ${\pi}$ by inscribing and circumscribing polygons in a unit circle goes back at least to Archimedes. By an ${N}$ -gon, we mean a regular polygon having ${N}$ sides. In Measurement of a Circle, Archimedes squeezed the unit circle between two 96-gons, bounding ${\pi}$ within the interval ${[3.141, 3.143]}$ . Let us denote the estimate of ${\pi}$ from an inscribed ${N}$ -gon as ${\Pi(N)}$ . A square inscribed in the unit circle has perimeter ${4\sqrt{2}}$ , giving a crude estimate ${\Pi(4)= 2\sqrt{2} \approx 2.828}$ . An inscribed hexagon has unit side, giving ${\Pi(6) = 3}$ , better but still pretty poor. We define the resolution by ${h=1/N}$ so that ${\rho=h_2/h_1=\frac{2}{3}}$ . Assuming the error is proportional to the square of the resolution, the errors in the two estimates are in the ratio ${1/4^2}$ to ${1/6^2}$ or ${9 : 4}$ . Richardson’s ${h^2}$ -extrapolation formula (2) then gives:

$\displaystyle \Pi(4,6) = 3 +\textstyle{\frac{4}{5}}(3-2\sqrt{2}) = 3.137 \,,$

which is correct to three figures. This is a dramatic improvement on the two estimates from which it is constructed. As Richardson noted, a single inscribed ${N}$ -gon would require 35 sides to produce such accuracy.

The Power of the 2-gon

We may wonder if even better estimates of ${\pi}$ can be obtained without recourse to trigonometry, using Richardson’s approach. Indeed this is the case. An inscribed 2-gon is the degenerate polygon comprising two coincident diameters. It yields the unimpressive estimate ${\Pi(2)=2}$ . However, when used in conjunction with ${\Pi(4)}$ and ${\Pi(6)}$ in a ${h^4}$ -extrapolation, it leads to the estimate ${\Pi(2,4,6) = 3.14134}$ , correct to four digits. A single ${N}$ -gon of order 145 is required to give similar precision.

Spurred by this success, we consider higher order extrapolations. Retaining the simple spirit of Richardson, we `return to the manner in which they did things before trigonometry was invented’, and use only polygons whose sides can be computed by elementary geometry. An inscribed equilateral triangle has side ${\sqrt{3}}$ . A pentagon requires more ingenuity, but can be drawn with ruler and compass and its edge length shown by elementary methods to be ${\frac{1}{2}\sqrt{10-2\sqrt{5}}}$ .Table 1 gives estimates of ${\pi}$ for extrapolation using various combinations of polygons. We see that using four polygons, an estimate ${\Pi(3,4,5,6) = 3.14159}$ is obtained, correct to six figures and equivalent to a single ${N}$ -gon with 2887 sides. However, the most surprising result is that obtained by adding in the 2-gon. The estimate then improves to ${\Pi(2,3,4,5,6) = 3.14159264}$ which has eight good digits and gives a result similar to an inscribed 19364-gon.

Discussion

The estimation of ${\pi}$ is no longer a major concern of mainstream mathematics, although ever-higher accuracy is a challenge for computer scientists. A simple estimate such as ${\frac{355}{113}}$ gives seven correct digits, adequate for most problems. Moreover, Richardson’s extrapolation process requires us to solve a linear system of equations, whose order increases with the order of the extrapolation.

However, the important conclusion from the above results is that the extrapolation procedure can dramatically improve accuracy. Thus, combining the abysmally poor estimate ${\Pi(2)}$ with ${\Pi(4,6)}$ reduced the error by a factor of 17, and combining it with ${\Pi(3,4,5,6)}$ resulted in a 45-fold reduction. The implication is that even a rough-and-ready estimate can enhance our knowledge if we have an understanding of the pattern of errors.

Sources

${\bullet}$ Lynch, Peter, 2003: Richardson Extrapolation: The Power of the 2-gon. Mathematics Today, 39(5), 159–160. PDF.

${\bullet}$ Richardson, Lewis F., 1927: The deferred approach to the limit. Part I: Single lattice. Phil. Trans. Roy. Soc., London, A226, 299–349.

ThatsMaths