Error computing $\pi$ approximation

247 Views Asked by At

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.

enter image description here

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

1

There are 1 best solutions below

7
On BEST ANSWER

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