9
$\begingroup$

Dear computational scientists,

I have the following formula that I need to rewrite in order to avoid catastrophic cancellation.

$y =\sqrt{\frac{1}{2}(1-\sqrt{1-x^{2})}}$

As x becomes smaller $\sqrt{1-x^{2}}$ approaches 1 so you will get 1 - 1.000000000......1 what will result in a catastrophic cancellation. I tried to rewrite the formula myself in a few different ways, but didn't manage yet to avoid the catastrophic cancellation.

The goal is to approximate pi:

import numpy as np


tn = 0.5
for i in range(1,100):
    tn1 = np.sqrt(0.5*(1-np.sqrt(1-tn**2)))
    print(i, 6*2**i*tn1)
    tn = tn1

output

1 3.1058285412302498
2 3.132628613281237
3 3.139350203046872
4 3.14103195089053
5 3.1414524722853443
6 3.141557607911622
7 3.141583892148936
8 3.1415904632367617
9 3.1415921060430483
10 3.1415925165881546
11 3.1415926186407894
12 3.1415926453212157
13 3.1415926453212157
14 3.1415926453212157
15 3.1415926453212157
16 3.141593669849427
17 3.1415923038117377
18 3.1416086962248038
19 3.1415868396550413
20 3.1416742650217575
21 3.1416742650217575
22 3.1430727401700396
23 3.1598061649411346
24 3.181980515339464
25 3.3541019662496847
26 4.242640687119286
27 6.0
28 0.0
29 0.0
30 0.0
31 0.0
32 0.0

Question: How should I rewrite the formula to avoid catastrophic cancellation?

$\endgroup$
7
  • 1
    $\begingroup$ i dont get where the cancellation happens... are you tying to find a limit? $\endgroup$
    – sai-kartik
    Sep 22, 2020 at 7:54
  • $\begingroup$ Yes, x goes to zero. I thouht of catastrophic cancellation: losing accuracy as result of substracting two almost equal numbers. That happens when sqrt(1-x^2) becomes almost (but not exactly) 1. $\endgroup$
    – Tim
    Sep 22, 2020 at 7:57
  • $\begingroup$ looks like i don't know much about this topic.. $\endgroup$
    – sai-kartik
    Sep 22, 2020 at 8:03
  • 5
    $\begingroup$ Old trick $(a-b)=\dfrac{(a-b)(a+b)}{a+b}$ $\endgroup$ Sep 22, 2020 at 8:08
  • 1
    $\begingroup$ You have cross-posted this answer on the comp sci SE site. Please do not do this. $\endgroup$
    – Xander Henderson
    Sep 23, 2020 at 21:04

2 Answers 2

9
$\begingroup$

To avoid catastrophic cancellation occurring when $x \to 0$, then as Raymond Manzoni's question comment suggests, rationalize $1 - \sqrt{1 - x^2}$ to get

$$\begin{equation}\begin{aligned} 1 - \sqrt{1 - x^2} & = (1 - \sqrt{1 - x^2})\left(\frac{1 + \sqrt{1 - x^2}}{1 + \sqrt{1 - x^2}}\right) \\ & = \frac{1 - (1 - x^2)}{1 + \sqrt{1 - x^2}} \\ & = \frac{x^2}{1 + \sqrt{1 - x^2}} \end{aligned}\end{equation}\tag{1}\label{eq1A}$$

$\endgroup$
0
1
$\begingroup$

Your $y$ is a root of a biquadratic equation:

$$y^4-y^2+\frac{x^2}2=0$$ hence a quadratic in terms of $y^2$.

You need to be aware of the stable "citardauq" formula for the roots of a quadratic: "Citardauq" formula derivation?

$\endgroup$

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