# Error computing $\pi$ approximation

My book suggests the following exercise.

Which one from the following approximation of $\pi$ minimises the error propagation due to rounding errors?

$$\pi = 4(1 - 1/3 + 1/5 - 1/7 + 1/9 - \ldots)$$ or $$\pi = 6\left(0.5 + \frac{1}{2}\frac{1}{3}\left(\frac{1}{2}\right)^3 + \frac{1\cdot 3}{2\cdot 2}\frac{1}{2!}\frac{1}{5}\left(\frac{1}{2}\right)^5+\frac{1\cdot 3\cdot 5}{2\cdot 2\cdot 2}\frac{1}{3!}\frac{1}{7}\left(\frac{1}{2}\right)^7+\ldots\right)$$ Using MATLAB, compare the results obtained letting varying the number of addends.

I am not sure about the answer: in the first expansion less arithmetic operations are performed (and so there is less rounding error) but the convergence is much slower. On the other hand with the second method the convergence is fast but there are a lot of operations.

Here is the result of my simulation using OCTAVE, I post a screenshot.

You can see the number of iterations needed: i=1,2,...

• I can't figure out why someone downvoted this question.... Commented Aug 27, 2016 at 10:03
• It's kind of a strange question, because the first series (known as the Leibniz series for $\pi$) converges so slowly that error propagation shouldn't be fist on anyone's mind when deciding not to use it ... Commented Aug 27, 2016 at 10:58
• Hint: The first series is alternating, while the second is strictly positive. Commented Aug 27, 2016 at 12:15
• This is the first thing I thought: maybe the terms 1/(2n-1) - 1/(2n+1) can induce cancellation errors. But I would like to be able to quantify that. Commented Aug 27, 2016 at 12:23

For an alternating series $$S = \sum_{k = 0}^\infty (-1)^k a_k, \quad a_k \geq 0$$ the rounding errors are bounded by $$u \sum_{k = 0}^\infty |(-1)^k a_k| = u \sum_{k = 0}^\infty a_k.$$

Indeed, when we compute $$\sum_{k=0}^n c_k$$ we actually compute $$\sum_{k=0}^n fl(c_k) = \sum_{k=0}^n c_k (1 + \delta_k) = \sum_{k=0}^n c_k + \sum_{k=0}^n c_k \delta_k.$$ where $|\delta_k| < u$ and $u$ is relative rounding error. The worst cases are when $\delta_k = \pm u \operatorname{sign} c_k$ which results in error $$u \sum_{k=0}^n |c_k|.$$

In fact in real life the running sum $$S_n = \sum_{k=0}^n c_k$$ does not change after a certain term, when $S_n + c_{n+1}$ rounds back to $S_n$, that is about $|c_n| \leq \frac{u}{2}S_n$.

Note that for the first series $$\sum_{k=0}^n \frac{1}{1 + 2k} \sim \frac{1}{2} \log n \to \infty.$$

For the second series, $$S = \sum_{k=0}^{\infty} b_k, \quad b_k \geq 0$$ the error is bounded by $$u \sum_{k=0}^{\infty} |b_k| = u \sum_{k=0}^\infty = u S.$$ Thus the relative error does not exceed $u$.

• Please can you explain me why the two bounds hold? (The one for the alternating series and the other for the second series) Commented Aug 27, 2016 at 12:30
• Perfect, super clear, thank you! Commented Aug 27, 2016 at 13:00
• Please, also look at the numerical results. They are done in single-precision (unless the effect is seen only at $n \sim 10^{15}$) Commented Aug 27, 2016 at 13:05
• Thanks! One thing: Maybe in your answer $u$ should be replaced by $u/2$. in fact I have tried to calculate again myself the relative error and I find that $\tilde{\sum} a_i = (\sum a_i)(1+\delta)^2 + O(\delta^3)$. This explain why I would write $u/2$. NOTE: 1) the sum with the tilde is intended to be the sum performed by the calculator. 2) If I have not been clear you want I can post my entire calculation that led me to think about $u/2$. Commented Aug 27, 2016 at 13:30
• That's possible. I did not take into accout floating after adding each new term. Commented Aug 27, 2016 at 13:37