The story of how the ancient Chinese mathematician Liu Hui created the "Cyclotomic Method" (Geyuan Shu) to calculate the value of \pi is well-known to many students today. While perhaps not a household name to everyone, it is a topic frequently discussed in textbooks and by teachers. Much like Archimedes, the "God of Mathematics" in Ancient Greece, Liu Hui used inscribed and circumscribed regular polygons to approximate the circle. The difference is that Liu Hui calculated the area of inscribed and circumscribed regular polygons for a circle with a radius of 1, whereas Archimedes calculated the perimeter of inscribed and circumscribed regular polygons for a circle with a diameter of 1. What is the difference in their computational efficiency? In fact, Archimedes’ method is slightly faster; the value Archimedes obtained by calculating up to a regular n-sided polygon is equivalent to what Liu Hui obtained by calculating up to a regular 2n-sided polygon.
We will not further differentiate between the two methods here, as their essence is the same. In modern mathematical notation, the theoretical basis of the Cyclotomic Method is: \lim_{n\to \infty} n \sin\left(\frac{\pi}{n}\right) = \pi \tag{1} Of course, Liu Hui could not have had modern formulas for calculating sine values (nowadays, sine values are generally calculated using Taylor series expansions, which themselves require the value of \pi). In his era, even ink and brushes were not common; as far as I know, even when Zu Chongzhi later calculated \pi, his only computing tool was the small rods now known as "counting rods" (suanchou). Nevertheless, with extraordinary perseverance, Liu Hui used a recursive method to gradually find the value of \pi.
Let \pi(n) = n \sin\left(\frac{\pi}{n}\right) = 2n \sin\left(\frac{\pi}{2n}\right) \cos\left(\frac{\pi}{2n}\right), and \pi(2n) = 2n \sin\left(\frac{\pi}{2n}\right). Combined with \sin^2 \theta + \cos^2 \theta = 1, it is not difficult to solve for: \pi(2n) = n\sqrt{2-2\sqrt{1-\left(\frac{\pi(n)}{n}\right)^2}} \tag{2} This is the recurrence formula required for the Cyclotomic Method.
Liu Hui continued calculating with formula (2), starting from n=6 and reaching the area of a 192-sided polygon, which corresponds to the value of \pi(96), approximately 3.14103... According to normal logic, Liu Hui’s maximum precision would be 3.14 or 3.141, and it could not be more accurate; taking more digits would be meaningless. However, Liu Hui created a "shortcut" (jie fa) to further obtain a more precise approximation of \pi. First, he calculated the area of an inscribed regular 96-sided polygon for a circle with a radius of 10 as 313\frac{584}{625}, and the area of an inscribed regular 192-sided polygon as 314\frac{64}{625} (corresponding to \pi(48) and \pi(96) respectively, scaled by 100). He then found the difference between the two: 314\frac{64}{625} - 313\frac{584}{625} = \frac{105}{625}
Then, "using the area of the 12-sided polygon as the rate of change" and "taking thirty-six parts of this difference," i.e., \frac{36}{625}, and adding it to the area of the regular 192-sided polygon, he obtained: 314\frac{64}{625} + \frac{36}{625} = 314.16 Thus, he calculated \pi to a precision of five decimal places! The phrases in quotes are Liu Hui’s original words, and no one knows exactly what his "shortcut" was. We only know that this method can derive the limit of a sequence based on a finite number of its values. This is somewhat similar to the idea now known as the "extrapolation method." Consequently, some believe that Liu Hui already used the extrapolation method! Furthermore, it is suggested that Zu Chongzhi later improved the extrapolation method (rather than the Cyclotomic Method) to derive \pi as 3.1415926; otherwise, given the computing power of that time, such a result would have been highly unlikely. Whether this is the truth remains unknown.
Accelerating \pi with Extrapolation
How does the extrapolation method work? We know that: \sin x = x - \frac{x^3}{3!} + \frac{x^5}{5!} - \frac{x^7}{7!} + \dots 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!} + \dots \\ \pi(2n) &= \pi - \left(\frac{1}{2}\right)^2 \frac{h^2 \pi^3}{3!} + \left(\frac{1}{2}\right)^4 \frac{h^4 \pi^5}{5!} - \left(\frac{1}{2}\right)^6 \frac{h^6 \pi^7}{7!} + \dots \end{aligned}
Thus, 4\pi(2n) - \pi(n) = 3\pi - \left(\frac{3}{4}\right)\frac{h^4 \pi^5}{5!} \dots. As the reader can see, we have eliminated the h^2 term, bringing the precision to O(h^4). Therefore, we can use: \pi^{**} = \frac{1}{3}[4\pi(2n) - \pi(n)] to correct the already obtained approximate values. Using Liu Hui’s data, we can immediately find \pi^{**} = 3.141584, which is very close to 3.1416. No wonder some believe Liu Hui used extrapolation!
We can continue to write: \pi(4n) = \pi - \left(\frac{1}{4}\right)^2 \frac{h^2 \pi^3}{3!} + \left(\frac{1}{4}\right)^4 \frac{h^4 \pi^5}{5!} - \left(\frac{1}{4}\right)^6 \frac{h^6 \pi^7}{7!} + \dots By using a linear combination of \pi(n), \pi(2n), \pi(4n) to eliminate the h^2 and h^4 terms, we get: \pi^{**} = \frac{1}{45}[64\pi(4n) - 20\pi(2n) + \pi(n)]
This formula has a precision of O(h^6). If that is still not enough, I can also write: \pi^{**} = \frac{1}{2835}[4096\pi(8n) - 1344\pi(4n) + 84\pi(2n) - \pi(n)]
For this last formula, the precision is O(h^8). We only need to set n=3 to obtain \pi^{**} = 3.141592651.... In other words, calculating up to a regular 24-sided polygon can achieve the precision of Zu Chongzhi!
Overview of the Extrapolation Method
In the era of electronic computers, even using the extrapolation method, the Cyclotomic Method for calculating \pi still seems "outdated." The purpose of this article is to use this example to summarize some superficial research on the extrapolation method conducted this week. The mathematician Romberg is widely recognized as the founder of the extrapolation method. The true extrapolation method is not implemented by increasing the terms of the linear combination as shown above, but through repeated "re-correction" of the corrected values. For specific details, one can refer to Extrapolation Methods and Their Applications.
As for the applications of the extrapolation method, they are extremely extensive. Because improving precision with extrapolation only involves the basic operation of linear combination, it is of great significance for numerical computation. Many formulas in "Introduction to Computational Methods," such as Simpson’s rule for integration and the Runge-Kutta (RK) methods for solving ordinary differential equations, are instances of the extrapolation method. For details, readers can refer to relevant books such as "Extrapolation Methods and Their Applications."
When reposting, please include the original address: https://kexue.fm/archives/1292
For more detailed reposting matters, please refer to: Scientific Space FAQ