I'm aware that both Leibniz's formula and Willis' product formula for $\pi$ converges at a logarithmic rate.

In a French paper, this formula was given as: "The slowest and heaviest formula imaginable to access $\pi,$ developed to verify a hypothesis on the volume of the sphere"

$S_m = \frac{4}{2^{m+1}} + \frac{4}{2^m}\sum\limits_{n=1}^{2^m-1}\sqrt{1-\left(\frac{n}{2^m}\right)^2} \enspace ; \enspace S_m \rightarrow \pi \enspace ; \enspace m \rightarrow \infty$

How slowly does the above formula converge? Is it slower than the more classical formulas? Are there formulas that converge even slower than the logarithmic rate? Are there any good examples?


How slowly does the above formula converge?

Not so slow, actually. But that's because one takes a subsequence with exponentially growing indices from a sequence that converges slower. Let $f(x) = \sqrt{1 - x^2}$, and for a positive integer $k$, define

$$T_k = \frac{1}{2k} \sum_{n = 1}^k \Biggl(f\biggl(\frac{n-1}{k}\biggr) + f\biggl(\frac{n}{k}\biggr)\Biggr).$$

Then $T_k$ is a trapezium sum for the integral $\int_0^1 f(x)\,dx$, for an equidistant partition of $[0,1]$ into $k$ subintervals. And, as is readily seen, $S_m = 4T_{2^m}$.

Trapezium sums for integrals of sufficiently smooth functions don't converge too badly. If $g$ is twice continuously differentiable on $[a,b]$, then one has

$$\Biggl\lvert \int_a^b g(x)\,dx - \frac{1}{2k}\sum_{n = 1}^k \Biggl(g\biggl(\frac{n-1}{k}\biggr) + g\biggl(\frac{n}{k}\biggr)\Biggr)\Biggr\rvert \leqslant \frac{(b-a)^3}{12k^2}\lVert g''\rVert_{\infty}.$$

Now, here the integrand is smooth on $[0,1)$, but the graph of $f$ has a vertical tangent at $1$, whence $f''$ is unbounded and the above doesn't tell us how good the convergence actually is. And indeed the convergence is slower, but not catastrophically so. We have $\pi - 4T_k \in \Theta(k^{-3/2})$. (Rough outline of argument: The area of a circular segment with angle $0 < \varphi \leqslant \pi$ is $\frac{1}{2}(\varphi - \sin \varphi) \in \Theta(\varphi^3)$, and the angle of the segment between $\frac{n}{k}$ and $\frac{n+1}{k}$ is $\arccos \frac{n}{k} - \arccos \frac{n+1}{k} \in \Theta\bigl(\frac{1}{\sqrt{k}\,\sqrt{k-n}}\bigr)$. Since $\sum j^{-3/2}$ is convergent, we get an overall difference in $\Theta(k^{-3/2})$.)

Thus $T_k$ converges to $\pi/4$ faster than the Leibniz series or the Wallis product. But in terms of rate of convergence, all are logarithmic. And it's easy to modify the Leibniz series to get more accurate approximations, while that's not so easy for $T_k$.

Now, since $S_m = 4T_{2^m}$ we have

$$\pi - S_m \in \Theta\bigl(2^{-3m/2}\bigr),$$

and that means $S_m$ converges linearly to $\pi$, with rate of convergence $\frac{1}{\sqrt{8}}$. But unless $m$ is small, computing $S_m$ is rather cumbersome, so computing $\pi$ via $S_m$ is not a very attractive option.

Still, "The slowest and heaviest formula imaginable" seems to be an exaggeration.

  • $\begingroup$ Awesome, this definitely answers most of my question. Are there any notable sublogarithmic formulas for pi? $\endgroup$ – OmnipotentEntity May 25 '17 at 4:02
  • $\begingroup$ I don't know of any. Of course one can devise arbitrarily slowly converging formulae, but among the "naturally" occurring ones, I don't know any where the convergence is worse than $\lvert a_n - \pi\rvert \sim c/n^{\alpha}$ for some positive $\alpha$. Taking the left-hand Riemann sums for $$\int_0^1 \frac{dt}{\sqrt{1-t^2}}$$ gives a pretty slowly converging approximation. I don't know exactly how slowly, but the last subinterval alone gives a $\Theta(n^{-1/2})$ difference. $\endgroup$ – Daniel Fischer May 25 '17 at 11:13

Given a sequence $a_n$ converging to $x$, we can always make $b_n=a_{\lfloor \frac{n}{2}\rfloor}$, that will also converge to $x$, but more slowly.

  • $\begingroup$ However, does this dramatically change the convergence rate? It seems that this would convert a linearly converging formula into another linearly converging formula. I'm looking for a formula that is dramatically slower. Like going from O(log n) to O(log log n) or something similar. $\endgroup$ – OmnipotentEntity May 24 '17 at 13:10
  • $\begingroup$ For clarity, I'm not asking for "the slowest" converging formula. I know that there is no such thing. I'm asking for good examples of extremely slowly converging formulas. Ones that are at least sublogarithmic. $\endgroup$ – OmnipotentEntity May 24 '17 at 13:12
  • 1
    $\begingroup$ @OmnipotentEntity Then use $b_n = a_{\lfloor \log(\log(n)) \rfloor}$ $\endgroup$ – Omnomnomnom May 24 '17 at 13:12
  • $\begingroup$ @Omnomnomnom, hahaha, ok you got me there. $\endgroup$ – OmnipotentEntity May 24 '17 at 13:13
  • $\begingroup$ Correct, but you can obviously put more complicated expressions in the index to duplicate each value more times as $n$ increases, and basically achieve what ever you want. I'm no expert on converge rates, but you could try things like $a_{\lfloor\log\log n\rfloor}$. $\endgroup$ – Henrik May 24 '17 at 13:15

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.