3
$\begingroup$

I was studying what it means for a problem to be well- and ill- conditioned and for an algorithm to be stable and unstable.

Of course the concepts are somehow related, but I always forget the difference and their meaning, maybe because I didn't actually understand their meaning fully? Yes.


According to this paper an algorithm is stable if small changes in the input produce only small changes in the output. To analize if a algorithm is stable we must analyze every step of the algorithm which could introduce errors, i.e. we must look at divisions, subtractions, square roots, etc. Then, at the end, it is stated that an algorithm is stable if it's well condition at each of this steps.


So what does it mean for a problem to be well-condition according to the same paper?

It starts by saying that every problem is based on an expression. If a problem is well-conditioned, then small changes in the input to the expression, will lead to small changes in the results.

Honestly this seems to be the definition of a stable algorithm. Why wouldn't this be?


Moreover, I think it seems that in this last definition the author mixed what's the problem and what's the expression.

And by the way, what's exactly this expression? Isn't it also an algorithm?


The author gives an example. We want to evaluate the expression:

$$y = \frac{x}{1 − x}$$

Is this the problem or the algorithm, or both?

Assuming this is an algorithm, to state if it is stable we should verify if all "atomic" (for simplicity, not in the sense of CPU atomic operations) operations are stable. Operations include $t = 1 - x$ and $\frac{1}{t}$ (are there any others?).

Assuming it's a problem, the author inserts some values in $x$ and states that "we may say that this algorithm is well condition or not around a certain $x_0$".

This means a problem can be well condition or ill condition depending on the input range? So why talking about well condition problem at all and in a general sense?


Maybe the only problem that I've is to distinguish between what's meant by a problem and an algorithm, what is the difference between the two.

$\endgroup$
2
$\begingroup$

Consider a linear problem $$Ax = b \tag{1}$$ This problem is well conditioned if difference between $\textbf{exact}$ solution to this problem and $\textbf{exact}$ solution of a slighty perturbed problem $(A+\delta A)y = b+\delta b$ is small for any small perturbations $\delta A$, $\delta b$. If the problem is badly conditioned, then there exists some small perturbations $\delta A$, $\delta b$ such that difference between $x$ and $y$ is large.

Suppose, that the problem (1) is solved using some algorithm and denote the solution by $\hat{x}$. Usually $\hat{x}$ is not an exact solution to (1). A method used to solve (1) is called backward stable if for any $A$ and $b$ it computes a solution $\hat{x}$ with small backward error, that is $\hat{x}$ is an exact solution of some slightly perturbed problem $(A+\delta A)\hat{x} = b+\delta b$. For a problem (1), the backward error is closely related to norm of residuals $r = A\hat{x} - b$.

Forward error is defined as a distance between true solution $x$ to (1) and solution computed by given method $\hat{x}$. This forward error can be estimated as $$\text{forward error} \leq \text{condition number} \times \text{backward error} \tag{2}$$

The backward error and condition number are completely unrelated. It is possible to have small backward error for badly conditioned problem or large backward error for well conditioned problem. For example consider a problem $$\left[\begin{array}{cc}\epsilon & 1\\1 &\epsilon\end{array}\right]x = b$$ for some small $\epsilon$. This problem is well conditioned. However if this problem is solved using LU method without pivoting, then the backward error is large and computed solution is highly inaccurate.

If condition number is low and a stable algorithm is used (thus the backward error is also small), then we can be sure, that (1) is solved accurately. It is however possible, that an unstable algorithm applied to badly conditioned problem gives an accurate solution. It is always possible to estimate the forward error for a given problem (1) using aposteriori error analysis, which do not use (2).

$\endgroup$
  • $\begingroup$ Reading the second chapter of the book "Numerical Analysis in Modern Scientific Computing: An Introduction" by P. Deuflhard and A. Hohmann, we see a description of problem (well- or ill-conditioned) and of the algorithm (stable or unstable) similar to what you're saying. But you talk about exact solutions to the initial problem and a slightly perturbed problem. This slightly perturbed problem arises because of errors in the input, right? $\endgroup$ – nbro Sep 8 '16 at 12:49
  • $\begingroup$ To make things clearer, they use the example of a problem that is not stated as an equation and thus that we can't immediately associate (at least me) with an algorithm, but they use a geometric example of two lines that intersect.. $\endgroup$ – nbro Sep 8 '16 at 12:52
  • $\begingroup$ Unfortunately you can't find this book on the web for free, indeed I borrowed it from the library. Anyway, in addition to this answer, I may add their description and introduction to condition of a problem with the example that I mentioned above... $\endgroup$ – nbro Sep 8 '16 at 12:57
  • $\begingroup$ Perturbations may come from inexact inputs. There is however much more important source of perturbations, i.e. perturbations created by the algorithm used to solve the problem. When we solve a problem then we have an inexact solution to given problem but exact solution to perturbed problem. Additionally from the backward error analysis we know how large these perturbations are. When we know perturbations we can estimate distance between two exact solution, unknown exact solution to given problem and known solution (returned by the algorithm) to perturbed problem. $\endgroup$ – Pawel Kowal Sep 8 '16 at 13:08
  • $\begingroup$ But backward analysis only works if we know the perturbations, right? $\endgroup$ – nbro Sep 8 '16 at 14:00
-1
$\begingroup$

It's not a good example, but it works. Usually the conditionning is defined for the stability of linear inversion problems. $$ y=Ax $$ We the conditioning of $A$ is bad, the algorithm won't matter, because the exact solution $A^{-1}y$ (if we could get it) differs a lot if the input $x$ varries a little. This means the problem is unlikley to be of practicle interest, because of inevitable noise in measurment/data.

$\endgroup$
  • $\begingroup$ In this case the problem is described by an equation/algorithm, which is unstable. So, when we talk about the condition of a problem we're talking about the stability of a specific algorithm/function that describes the problem, apparently. But the condition of the problem or specific algorithm that describes it seems not to take into account every "atomic" operation, but it's seems like an high level, general and imprecise description of how that same algorithm behaves. $\endgroup$ – nbro Sep 6 '16 at 15:05
  • $\begingroup$ Yes usually the problem itself can be rewritten to aquire stability (see prewhitening in signal processing, variance normalization step before EM algorithm for gaussian fitting) $\endgroup$ – marmouset Sep 6 '16 at 15:09
  • $\begingroup$ So, my claim is that it's not necessary to talk about "condition of a problem" but just about stability of algorithms (for solving a particular problem). Or, if this was an exam, what would you say about the difference between condition of a problem and stability of an algorithm? I still wouldn't be able to say something, honestly. $\endgroup$ – nbro Sep 6 '16 at 15:11
  • $\begingroup$ Bad conditionning of a problem implies unstability of the algorithm I don't see it. $\endgroup$ – marmouset Sep 6 '16 at 15:16
  • $\begingroup$ Stability is a property of an algorithm, conditioning is a property of a problem. For example LU with pivoting is a backward stable algorithm, but applied to badly conditioned problem can give large forward error. $\endgroup$ – Pawel Kowal Sep 7 '16 at 12:21

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.