4
$\begingroup$

The Chudnovsky formula $$\frac{1}{\pi} = 12 \sum^\infty_{k=0} \frac{(-1)^k (6k)! (545140134k + 13591409)}{(3k)!(k!)^3 \left(640320\right)^{3k + 3/2}}$$ is generally quoted as converging towards $\pi$ with a linear rate of convergence of 14 decimal places per iteration. However, when having looked for the exact analytic value, I can't seem to find a proof of this anywhere, or even an asymptotic error function describing it, having searched in a proof of the formula for the words 'convergence' and 'error', and only having found unrelated results. I considered the method proposed at the bottom of this page, however the method posted here only works for superlinear formulae - a category into which this shouldn't fall, unless all the sites claiming it to be linear are completely wrong. My final idea was to use a method I'd seen once using the Taylor series to prove the rate of convergence of the Newton Raphson method. However this method appears to require that the function be expressed in the form:

$$x_{n+1} = g(x_n)$$

Which means I can't really see any obvious way of rewriting so as to exclude $n$ from the formula.

And pretty much any variation on the word 'error' I enter into Google tends to come up with people trying to find errors in their algorithm.

Any direction on how to solve this, or to a paper which includes a proof of it, would be greatly appreciated. Thank you for your time!

EDIT: Having written this, I since found the following comment, which relates to my question of finding an exact value for asymptotic convergence, but I still don't know why this would be true. From further testing the value given in the linked comment seems to be derived from the reciprocal of the value found in the ratio test, but I still have little idea as to why this is true!

$\endgroup$
0

2 Answers 2

5
$\begingroup$

A digit is gained 'linearly' if the summand behaves as $10^{-k}.$ (In many contexts this would be considered exponential convergence.) As I understand the question, we want to show the summand behaves as $(10^{14})^{-k}.$ The constant factors and (-1)^k are immaterial, so we write, (with $a$ and $b$ easily pulled from above) $$ S:=\frac{(6k)!(a\,k+b)}{(3k)!k!^3} (640320)^{-3k} = \binom{6k}{3k}\binom{2k}{k}\binom{3k}{k}(ak+b) (640320)^{-3k}$$ where binomials have been inserted to make the asymptotic expansion a little simpler. Use $$ \binom{2k}{k} \sim \frac{2^{2k}}{\sqrt{\pi\,k}} \quad \text{ and } \quad \binom{3k}{k} \sim \frac{\sqrt{3}}{2} \,\frac{3^{3k}\,2^{-2k}}{\sqrt{\pi\,k}}$$ which are derivable by Stirling's formula. The $\binom{6k}{3k}$ can use the first asymptotic formula. Thus we have $$ S \sim \bigg\{ \frac{a+b/k}{2\pi\,\sqrt{\pi\,k}} \bigg\} \,\bigg(\frac{12}{640320}\bigg)^{3k}$$ The expression in curly brackets can be ignored as ratio of polynomials won't get you 'linear' convergence. Then it's a simple manner of seeing that $$ (53360)^{-3k} \sim (1.52\,\text{x}\,10^{14})^{ -k} .$$

$\endgroup$
2
$\begingroup$

While Stirling's formula yields an approximation of the error, Binet's Formula yields an error bound for the Chudnovsky Formula:

First we observe that the series is an alternating series whose absolute values are strictly decreasing to zero. Thus, the Alternating series test tells that the error you produce by summing only until $k=N$ is smaller than the next term's absolute value: $$\left|\frac{1}{\pi}-\frac{1}{\pi_N}\right| = \left|12\sum_{k=N+1}^\infty s_k\right| < 12\left| s_{N+1} \right|.$$

But since it holds $$\frac{1}{\pi}-\frac{1}{\pi_N}=\frac{\pi_N-\pi}{\pi~\pi_N},$$ we have proven $$\left|\pi_N-\pi\right| < \left|12\pi~\pi_N~s_{N+1} \right|.$$

Second we use Binet's Formula for $n!$, which says $$\exp\left(\frac{1}{12n}-\frac{1}{360n^3}\right) < \frac{n!}{\sqrt{2\pi n}\cdot(n/e)^n} < \exp\left(\frac{1}{12n}\right)$$ This yields $$\frac{(6k)!}{(3k)!(k!)^3} < \frac{1728^k}{2(\pi k)^{3/2}}.$$ Using $545140134k+13591409\leq 545140134k+13591409k=558731543k$ yields $$|s_k|<\frac{1728^k}{2(\pi k)^{3/2}}\cdot\frac{558731543k}{640320^{3k+3/2}}<\frac{1}{10~\sqrt{k}~53360^{3k}}$$ and thus the following error bound for the Chudnovsky Formula (where $N\geq 0$): $$\left|\pi_N-\pi\right| < \left|12\pi~\pi_N~s_{N+1} \right|<\frac{12}{\sqrt{N+1}~53360^{3(N+1)}}$$

Remark: For $N\geq 128$, using $13591409\leq 13591409k/128$, we obtain with the same method: $$\left|\pi_N-\pi\right| < \frac{11.317}{\sqrt{N+1}~53360^{3(N+1)}} < 53360^{-3(N+1)}$$ Thus every term of the summation reduces the error by a factor of $53360^{-3}=10^{-14.1816}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.