4
$\begingroup$

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.

$\endgroup$
3
  • 2
    $\begingroup$ Your observation for large $n$ is simply due to floating point arithmetic and its limited precision. $\endgroup$ Oct 16, 2014 at 19:23
  • $\begingroup$ Ah, yes good point. I may re-write my program with Java BigDecimal. Any thoughts to why it (perhaps always) works? $\endgroup$
    – baum
    Oct 16, 2014 at 19:24
  • $\begingroup$ ...and even after switching to type double, results are much more accurate. $\endgroup$
    – baum
    Oct 16, 2014 at 19:27

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ So is it only close to $n^{-1}$ because $n$ is small? $\endgroup$
    – baum
    Oct 16, 2014 at 19:36
  • $\begingroup$ No, @baum, $n^{-1}$ is fine, it's the exact $C\cdot n^{-1}$ term in the development. $\endgroup$ Oct 16, 2014 at 19:38
  • 1
    $\begingroup$ Since two consecutive terms have almost the same size, the error is roughly half the first omitted term. But Since we're multiplying th Leibniz series by $4$, the error is roughly $4\cdot\frac{1}{2} \cdot\frac{1}{2n+1}$. $\endgroup$ Oct 16, 2014 at 19:40
  • 1
    $\begingroup$ @DanielFischer thanks for pointing that out. Also baum I realized I may have caused some confusion with my $\frac{1}{2n+3}$ versus your $\frac{1}{n}$. I noticed that your series is an alternating sum of just the odd integers which is why I wrote what I did. I'm should have said something along the lines of "$|p_n-\pi|$ should be very close to $\frac{1}{n+1}$ where $\frac{1}{n+1} = \frac{1}{2m+3}$ for some $m \in \Bbb{N}$" $\endgroup$
    – graydad
    Oct 16, 2014 at 19:48
2
$\begingroup$

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.$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .