2
$\begingroup$

I am looking for examples of poorly conditioned sums which can rapidly be evaluated, for the purposes of unit testing.

I'm currently using the series representation for $\ln(2)$:

$$ \sum_{n=1}^{\infty} \frac{(-1)^{n+1}}{n} $$ which has an infinite summation condition number, but in double precision, I can only get the condition number to ~22 after an obscene number of terms (terrible for a unit test), and the error in the naive summation is not large. So I guess that this sum is numerically well-conditioned!

$\endgroup$
  • $\begingroup$ Could you explain what you mean by the condition number of the sum? $\endgroup$ – smh Jan 29 at 14:48
  • $\begingroup$ @smh I have included a few words on the conditioning of sums in my answer. The key is that if $s = a+b \approx 0$, then relatively small changes to $a$ and $b$ can lead to a relative large change in $s$. Example: If a company is making only a small profit, then a small increase in their income can cause their profits to, say, triple. $\endgroup$ – Carl Christian Jan 30 at 14:55
9
$\begingroup$

The condition number of sum $s(x) = \sum_{j=1}^n x_j$ is given by $$ \kappa(x) = \frac{\sum_{j=1}^n |x_j|}{|\sum_{j=1}^n x_j|} = \frac{s(|x|)}{|s(x)|}$$ and reflects the sums sensitivity to small changes in the input. Specifically, we have $$ \underset{\epsilon \rightarrow 0_+}{\lim}\sup \left\{ \frac{1}{\epsilon} \left|\frac{s(x+\Delta x) - s(x)}{s(x)} \right| \: : \: |\Delta x_j| \leq \epsilon |x_j|\right\} = \kappa(x).$$ If all $x_j$ have the same sign, then the sum is well-conditioned. If the $s(x) \approx 0$, but $s(|x|)$ is large, then the sum is ill-conditioned. A good example of a sum whose conditioning is well understood is the polynomial $p_n$ given by $$ p_n(x) = \sum_{j=0}^n \frac{x^j}{j!}$$ This is the Taylor polynomial of order $n$ for the natural exponential function at the point $x_0 = 0$. The sum is ill-conditioned for large negative values of $x$ and well-conditioned for all positive values of $x$. If $x$ is positive and $n$ is so large that $p_n(x) \approx e^x$ is a good approximation, then $1/e^{x} \approx p_n(-x)$ is a good approximation as well. In short, you have an ill-conditioned sum for which a good approximation is easy to obtain.

$\endgroup$
  • $\begingroup$ Great example; easy to code. Even better that you can make the condition number arbitrarily large. $\endgroup$ – user14717 Jan 30 at 0:06
  • $\begingroup$ @user14717 You are very welcome. I have fixed the index error in the definition of $p_n$. $\endgroup$ – Carl Christian Jan 30 at 14:58

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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