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.
Best Answer
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).