A Historical Mystery — Did Liu Hui Use Extrapolation?

历史上的谜案——刘徽有没有使用外推法？ 苏剑林 · 2011-03-12 · Mathematics mystery circumference extrapolation method recursion

Liu Hui

Back in the day, the story of how the ancient Chinese mathematician Liu Hui invented the "circle-cutting method" (割圆术) to calculate the value of π is now known to many students; while it may not be a household name, textbooks and teachers alike still enjoy recounting it. Much like Archimedes, the "god of mathematics" of ancient Greece, Liu Hui also used inscribed and circumscribed regular polygons to approximate a circle. The difference is that Liu Hui's method computed the areas of the inscribed and circumscribed regular polygons of a circle with radius 1, whereas Archimedes computed the perimeters of the inscribed and circumscribed regular polygons of a circle with diameter 1. What's the difference in efficiency between the two approaches? Archimedes's method is actually somewhat faster: the value Archimedes obtains at the regular n-gon corresponds to what Liu Hui would obtain at the regular 2n-gon.

Here we won't dwell on distinguishing the two methods in detail, since they are essentially the same in nature. Written in modern mathematical notation, the theoretical basis of the "circle-cutting method" is

$$lim_{n\to \infty} n \sin(\frac{\pi}{n})=\pi\tag{1}$$

Of course, Liu Hui could not possibly have had access to a modern formula for computing the value of the sine function (nowadays the sine function is generally computed via a Taylor series expansion, which requires the value of $\pi$), and in his era there was not even pen and ink to speak of — as far as I know, even later, when Zu Chongzhi computed π, his only computational tool was what we now call "counting rods," small sticks used for calculation. Nevertheless, relying on sheer perseverance, Liu Hui used a recursive method to gradually compute π. more

Let $\pi(n)=n sin(\frac{\pi}{n})=2n sin(\frac{\pi}{2n})cos(\frac{\pi}{2n})$, and $\pi(2n)=2n sin(\frac{\pi}{2n})$; combining this with $sin^2 \theta+cos^2 \theta=1$, it is not hard to solve for

$$\pi(2n)=n\sqrt{2-2\sqrt{1-(\frac{\pi(n)}{n})^2}}\tag{2}$$

This is the recursion formula required by the circle-cutting method.

Liu Hui kept computing with formula (2), starting from n = 6, all the way to the area of the 192-gon, which corresponds to the value of $\pi(96)$, namely 3.14103.... Following normal logic, Liu Hui could at most take the value 3.14 or 3.141 — there would be no point in taking more digits, since they would not be accurate. However, Liu Hui devised a "shortcut method" that allowed him to obtain an even better approximation of π. First he computed the area of the inscribed regular 96-gon of a circle with radius 10 as $313\frac{584}{625}$, and the area of the inscribed regular 192-gon as $314\frac{64}{625}$ (corresponding respectively to $\pi(48),\pi(92)$), and took their difference

$$314\frac{64}{625}-313\frac{584}{625}=\frac{105}{625}$$

Then, "using the area of the dodecagon as a proportional reference to make an adjustment" ("以十二觚之幂为率消息"), he "took thirty-six parts of this difference" ("取此分寸之三十六"), i.e., $\frac{36}{625}$, and added it to the area of the 192-gon, obtaining

$$314\frac{64}{625}+\frac{36}{625}=314.16$$

In this way he obtained a value of π accurate to 5 decimal places! The phrases in quotation marks are Liu Hui's own words, and no one knows exactly what his shortcut method actually was. All we know is that this kind of method can, from a finite number of terms of a sequence, deduce the limit of that sequence. This does sound a bit like the idea now known as "extrapolation." Hence some people believe that Liu Hui had already made use of extrapolation! Moreover, it is claimed that Zu Chongzhi later derived his famous value of π = 3.1415926 by improving upon the extrapolation method (rather than improving the circle-cutting method itself) — otherwise, given the computational capabilities of the time, such a result would hardly have been possible. Is this really the case? We simply don't know.

Accelerating π via Extrapolation

How does extrapolation actually work? We know that:

$$\sin x=x-\frac{x^3}{3!}+\frac{x^5}{5!}-\frac{x^7}{7!}+...$$

Let $h=\frac{1}{n}$; then we have

$$\begin{aligned}\pi(n)=\pi-\frac{h^2 \pi^3}{3!}+\frac{h^4 \pi^5}{5!}-\frac{h^6 \pi^7}{7!}+... \\ \pi(2n)=\pi-(\frac{1}{2})^2 \frac{h^2 \pi^3}{3!}+(\frac{1}{2})^4 \frac{h^4 \pi^5}{5!}-(\frac{1}{2})^6 \frac{h^6 \pi^7}{7!}+...\end{aligned}$$

which gives us $4\pi(2n)-\pi(n)=3\pi-(\frac{3}{4})\frac{h^4 \pi^5}{7!}...$. As the reader can see, we've eliminated the $h^2$ term, bringing the precision up to $O(h^3)$. We can therefore use

$$\pi^{\cdot \cdot }=\frac{1}{3}[4\pi(2n)-\pi(n)]$$

to correct an already-computed approximation. Plugging in Liu Hui's data, we immediately get $\pi^{**}=3.141584$, which is close to 3.1416 — no wonder some people think Liu Hui used extrapolation!

We can go further and write

$$\pi(4n)=\pi-(\frac{1}{4})^2 \frac{h^2 \pi^3}{3!}+(\frac{1}{4})^4 \frac{h^4 \pi^5}{5!}-(\frac{1}{4})^6 \frac{h^6 \pi^7}{7!}+...$$

Using a linear combination of the three terms $\pi(n),\pi(2n),\pi(4n)$ to eliminate the $h^2,h^4$ term, we obtain

$$\pi^{\cdot \cdot }=\frac{1}{45}[64\pi(4n)-20\pi(2n)+\pi(n)]$$

This formula has precision $O(h^5)$. If that's still not enough for you, we can write

$$\pi^{\cdot \cdot }=\frac{1}{2835}[4096\pi(8n)-1344\pi(4n)+84\pi(2n)-\pi(n)]$$

For this last formula, the precision is $O(h^7)$, and if we simply set n = 3, we obtain $\pi^{**}=3.141592651...$. In other words, computing up to the regular 24-gon is enough to match Zu Chongzhi's precision!

A Survey of Extrapolation

In the age of electronic computers, using extrapolation to compute π via the circle-cutting method still feels rather "outdated." The purpose of this post is to use this example to summarize some of my modest research into extrapolation this past week. The mathematician Romberg is generally credited as the founder of extrapolation methods; the genuine extrapolation method does not, in fact, improve precision by adding more terms to a linear combination as shown above, but rather by repeatedly "re-correcting" the corrected values over multiple iterations. For the specific details, readers may refer to Extrapolation Methods and Their Applications.

As for the applications of extrapolation, they are extremely, extremely broad. Since improving precision via extrapolation only involves the basic operation of taking linear combinations, it has significant implications for numerical computation. Many formulas found in Introduction to Numerical Methods — such as Simpson's rule for integration, and the Runge-Kutta (RK) methods for solving ordinary differential equations — are all instances of extrapolation. Readers interested in the specifics can consult relevant books, such as Extrapolation Methods and Their Applications.