1
$\begingroup$

We want to compute the relative condition number of:

$$x_1+x_2+x_3+\cdots$$

We assume all values are positive, and we will do a limit of a large $x_1=10^{8}$, and smaller values for all the other numbers $x_2=x_3=\cdots=10^{-3}$, as a worse-case scenario:

1 term

For

$$f(x_1) = x_1$$

the relative condition number is:

$$\kappa={\|J\|\|x\|\over \|f(x)\|}={1\cdot x \over x} = 1$$

2 terms

For

$$f(x_1, x_2) = x_1+x_2$$

we get in the infinity norm:

$$\kappa={\|J\|_\infty \|x\|_\infty\over \|f(x)\|}={2\cdot \max(x_1, x_2) \over x_1 + x_2} \rightarrow 2$$

Which for $x_1=10^{8}$ and $x_2=10^{-3}$ approaches 2.

The exact value is:

In [1]: x1 = 1e8; x2 = 1e-3; 2*max(x1, x2)/(x1+x2)
Out[1]: 1.99999999998

3 terms

For

$$f(x_1, x_2, x_3) = x_1+x_2+x_3$$

we get in the infinity norm:

$$\kappa={\|J\|_\infty \|x\|_\infty\over \|f(x)\|}={3\cdot \max(x_1, x_2, x_3) \over x_1 + x_2 + x_3} \rightarrow 3$$

Which for $x_1=10^{8}$ and $x_2=x_3=10^{-3}$ approaches 3. The exact value is:

In [2]: x1 = 1e8; x2 = 1e-3; x3 = 1e-3; 3*max(x1, x2, x3)/(x1+x2+x3)
Out[2]: 2.99999999994

n terms

The relative condition number for summing n-terms of the type:

$$10^8 + 10^{-3} + 10^{-3} + \cdots$$

is

$$\kappa=n$$

Is that correct? So for large $n$, the sum of such values becomes ill-conditioned?

And the only way it becomes well-conditioned is if the magnitude of the numbers is similar, since then the condition number seems to stay low even for large $n$, e.g.:

In [3]: x1 = 1e-3; x2 = 2e-3; x3 = 3e-3; x4 = 4e-3; 4*max(x1, x2, x3, x4)/(x1+x2+x3+x4)
Out[3]: 1.6
$\endgroup$
1
$\begingroup$

The mistake I made is that the Jacobian in the infinity norm is equal to 1, not $n$. As such, the relative condition number of the sum is:

$$\kappa=1$$

and as such is always well-conditioned, no matter what magnitudes the values are.

$\endgroup$
2
  • $\begingroup$ I have shown that this answer is not correct. Why is it still up? $\endgroup$ May 28 '20 at 18:10
  • $\begingroup$ I removed this answer as correct. $\endgroup$ May 29 '20 at 19:17
1
$\begingroup$

I don't think your own answer is correct, though my method somewhat differs in so far as I use a different norm than you - the Euclidean norm. My result:

The relative condition for the sum of two numbers $x+y$ is $$\kappa_R = \dfrac{\sqrt{2x^2+2y^2}}{|x+y|}.$$ The absolute condition is $$\kappa_A = \sqrt 2\approx 1.41.$$

Hence the sum is very poorly conditioned if $x\approx -y$, which is somewhat to be expected.

$\textbf{Proof:}$ Consider the function $f:\mathbb{R}\to\mathbb{R}:(x,y)\mapsto x+y$. Then $\nabla f = (1,1)$. Hence $$\kappa_A = ||\nabla f|| = \sqrt 2,$$ where we use the Euclidean norm. Then we can calculate the relative condition number as $$\kappa_R = \dfrac{||\nabla f||\cdot||(x,y)||}{||f(x,y)||}= \dfrac{\sqrt{2x^2+2y^2}}{|x+y|}.$$

The conclusion of the elementary operation $x+y$ is that though it is a $\textit{stable}$ numerical problem (Indeed, the only $\textbf{new}$ errors made by $+$ if we consider no input-errors are bounded by $\varepsilon_{\text{machine}}$), it is not a well-conditioned operation for relative errors i.e it propagates existing errors by making them bigger.

Also note that from https://en.wikipedia.org/wiki/Condition_number#One_variable you can already see that your answer $\kappa_R = 1$ cannnot be right. If we exchange $y$ for $a\in\mathbb{R}$ your answer does not change, while mine indeed conforms to the condition number (then $\kappa_A = 1$)$$\kappa_R=\dfrac{|x|}{|x+a|}.$$

$\endgroup$
4
  • $\begingroup$ I should say that I'm actually quite new to thinking about condition and stability of algorithms, so any feedback on my answer is more than welcome. $\endgroup$ May 12 '20 at 8:09
  • $\begingroup$ Thanks for the answer. I am new to this too. So is your view that the relative condition number is equal to "n", as in my original question? $\endgroup$ May 13 '20 at 16:47
  • $\begingroup$ @OndřejČertík no it is not, you should read my answer. It cannot just depend on $n$, it has to depend on the magnitudes of the summands $x$ and $y$ as well. For instante - as I explained - you can have catostrophic cancelling when $x\approx -y$, so it definitely cannot be just $n$. $\endgroup$ May 16 '20 at 6:30
  • $\begingroup$ Note that all the values are positive. So the case x ~ -y cannot happen. $\endgroup$ May 29 '20 at 19:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.