# What is a relative condition number of a sum of positive values?

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


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.

• I have shown that this answer is not correct. Why is it still up? – PaleBlueDot May 28 '20 at 18:10
• I removed this answer as correct. – Ondřej Čertík May 29 '20 at 19:17

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

• 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. – PaleBlueDot May 12 '20 at 8:09
• 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? – Ondřej Čertík May 13 '20 at 16:47
• @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$. – PaleBlueDot May 16 '20 at 6:30
• Note that all the values are positive. So the case x ~ -y cannot happen. – Ondřej Čertík May 29 '20 at 19:14