Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I would appreciate a definition clarification.

if a numerical method is "unstable", does it mean that if we introduce a small random error in one of the steps, the error would be magnified greatly after further steps? is this true for all unstable algorithms or are there some where the random error is never made significant, say wrt the error of the method itself?

share|improve this question
    
More or less, yes. A tiny error committed in the course of the algorithm's preceedings gets easily magnified as the algorithm marches on. But one must always keep separate the notion of an "ill-conditioned problem" and an "unstable algorithm". –  J. M. Dec 31 '11 at 13:26

2 Answers 2

Unstable means that if you change your data points by a small value then the result of your computation changes by a big value.

On the other hand what happens during the steps is called rounding errors and precision errors.

Compare to Burden/Faires "Numerical Analysis" page 33:

"...One criterion we will impose on an algorithm whenever possible is that small changes in the initial data produce correspondingly small changes in the final results. An algorithm that satisfies this property is called stable; otherwise it is unstable...."

"...As a consequence, an algorithm that exhibits linear growth of error is stable, whereas an algorithm exhibiting exponential error growth is unstable...."


Edit

What I wrote above is under the assumption that the problem you are trying to compute is well-conditioned. If it's not then whether your algorithm is stable or not doesn't matter because if you have a tiny error in your input data then the output will be greatly perturbed.

Hope this helps.

share|improve this answer
1  
"Unstable means that if you change your data points by a small value then the result of your computation changes by a big value." - that can be due to a problem being ill-conditioned rather than the algorithm being unstable. One classic example is using the Cholesky decomposition to solve a system where the coefficient matrix is the Hilbert matrix. Cholesky itself is stable, but the underlying matrices have huge condition numbers, that the matrix is effectively singular for large enough dimensions. –  J. M. Dec 31 '11 at 15:16
    
Additionally, there is a good reason why one wants to distinguish "forward" from "backward" stability. –  J. M. Dec 31 '11 at 15:17
    
@J.M. True, I forgot about ill-conditioned problems. But I've not heard of forward and backward stability I think. Yet I don't think this falsifies my answer. –  Rudy the Reindeer Dec 31 '11 at 15:24
    
It definitely doesn't; I'm just adding things here. :) –  J. M. Dec 31 '11 at 15:32
    
@J.M. Hmmm. I just re-read the question and it reads to me as "Are there any algorithms where the error of the algorithm is insignificant with respect to the method itself?" But the algorithm is the method itself. Am I confused? –  Rudy the Reindeer Dec 31 '11 at 15:41

We say a method is stable when it is capable of controlling errors introduced in each computation. Stability allows the method to converge to a certain solution. Here's a simple example: \begin{equation} u_t = -u_x \end{equation} Suppose a set of equally distanced nodes on the x-axis in 1D. We assume $U_i$ denotes approximate values of the function $u(x)$ at $i^{th}$ node. We use Forward Euler in time and Centered Differences in space: \begin{equation} U_i^{n+1} = U_i^n - \frac{\Delta t}{\Delta x} (U^n_{i+1} - U^n_{i-1}) \end{equation} Now assume at some iteration (maybe even the initial condition) the numerical solution has an oscillatory form. For simplicity assume, $U_i = (-1)^i*x_i$. Now you can clearly see that no matter what values of $\Delta t, \Delta x$ you choose, negative values of the function will get smaller and positive values will grow larger which eventually leads to unacceptable results.

This is only a simple explanation. For further reading I advise you to take a look at Computational Fluid Dynamics Vol. I, by Hoffman and Chiang. As you can see, this doesn't necessarily happen with random errors introduced intentionally, It can happen whenever there is some errors or oscillations in the solution.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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