Correcting Error in the Leibniz $\pi$ formula... why does it work?

Question

You are probably familiar with the Leibniz $\pi$ formula:

$$ 1 - \frac{1}{3} + \frac{1}{5} - \frac{1}{7} + \frac{1}{9} - \cdots = \frac{\pi}{4} $$

For a CS homework assignment I had to write a program to compute the sum of the first $n$ iterations.

I noticed the following (let $p_n$ equal the approximated value of $\pi$ after $n$ iterations):

$$ |p_n-\pi| \approx \frac{1}{n} $$

That is, the error in my approximation, after $n$ iterations, was extremely close to $n^{-1}$.

I took this one step further, by adding (or subtracting, depending whether $n$ was even or odd) $n^{-1}$ to my approximation $p_n$. And the resulting value was considerably more accurate.

However, I should note that for very large values on $n$ (such as $10^9$), this "fix" becomes less accurate than the regular harmonic series itself.

Here's some example runs. Note that for 1 part in x, x is $n^{-1}$, rounded.

$n = 5$, no correction:

Computed value: 3.33968248963356
Actual value:   3.141592653589793
∆ = 0.19808983604376706 (1 part in 5)

$n = 5$, with correction:

Computed value: 3.13968248963356
Actual value:   3.141592653589793
∆ = 0.001910163956233113 (1 part in 524)

$n = 200$, no correction:

Computed value: 3.1365926219150424
Actual value:   3.141592653589793
∆ = 0.005000031674750716 (1 part in 200)

$n = 200$, with correction:

Computed value: 3.1415926219150423
Actual value:   3.141592653589793
∆ = 3.1674750822219266E-8 (1 part in 31570888)

Does anyone have any ideas on why or how this works, or at least shed some light on it?

If it would be helpful, I can post my code or more test cases.

Thanks.

Answer 1

If we define

$$p_n = 4 \sum_{k=1}^n \frac{(-1)^{k-1}}{2k-1},$$

then we have

$$\lvert p_n - \pi\rvert = 4\sum_{k=n+1}^\infty \frac{(-1)^{k-n-1}}{2k-1}.$$

Grouping two consecutive terms in the remainder, we can write it as

$$4\sum_{m = \frac{n+1}{2}}^\infty \left(\frac{1}{4m-1} - \frac{1}{4m+1}\right) = \sum_{m = \frac{n+1}{2}}^\infty \frac{8}{16m^2-1}$$

if $n$ is odd, and as

$$4\sum_{m=\frac{n}{2}+1}^\infty \left(\frac{1}{4m-3}-\frac{1}{4m-1}\right) = \sum_{m=\frac{n}{2}+1}^\infty \frac{8}{16m^2-4m+3}$$

for even $n$.

Approximating both remainder terms by

$$\sum_{m = \left\lceil \frac{n+1}{2}\right\rceil}^\infty \frac{1}{2m^2},$$

one can further approximate that sum by an integral to obtain

$$\lvert p_n - \pi \rvert = \frac{1}{2\frac{n}{2}} + O(n^{-2}).$$

A more careful evaluation of the sums can get you the next terms in the asymptotic development

$$\pi = p_n + \frac{(-1)^n}{n} + \frac{c_2}{n^2} + \dotsc.$$

Answer 2

Are you familiar with how to approximate an error bound for alternating series? Given a sequence $\{a_n \}$ where $s = \sum_{i=1}^\infty a_n$ is a convergent alternating series and $s_n$ denotes the $n^{th}$ partial sum, then $$|s-s_n| \leq |s_n-s_{n+1}|= |a_{n+1}|$$ Hence, the quantity $|p_n-\pi|$ should be very close to $|a_{n+1}| = \frac{1}{2(n+1)+1} = \frac{1}{2n+3}$ the larger $n$ gets.