Stability of a computational process

A property characterizing the speed of accumulation of gross computing errors. The concept of stability of a computational process was introduced because in real calculations one cannot operate with exact numbers and it is impossible to circumvent rounding, which is sometimes the cause of a fast loss of accuracy.

A computational process is a sequence of arithmetic operations on numbers. Let $ X _ {i} $ be a normed linear space and $ A _ {i} $ a continuous operator $ A _ {i} : X _ {1} \times \dots \times X _ {i} \rightarrow X _ {i + 1 } $. Then the sequence of equations

$$ \tag{1 } x _ {i + 1 } = \ A _ {i} ( x _ {1} \dots x _ {i} ), $$

$$ x _ {i + 1 } \in X _ {i + 1 } ,\ i = 1 \dots N - 1, $$

gives a computational process with original data $ x _ {1} $ and intermediate results $ x _ {i} $, $ i = 2 \dots N - 1 $. Usually $ X _ {i} = \mathbf R ^ {n} $ and the operator $ A _ {i} $ consists of a finite number of arithmetic operations. As a rule $ x _ {i + 1 } $ depends not on all the intermediate results obtained earlier. The number $ N $ may be given in advance or determined in the course of the computational process itself. In the latter case $ N $ depends on $ x _ {1} $( e.g. if $ N $ is the number of iterations needed for a given degree of accuracy).

An actual computational process may not be carried out exactly in conformity with definition (1), because in carrying out the arithmetic operations rounding errors are introduced and $ x _ {i + 1 } $ may be obtained from inexact previous results. This means that instead of $ x _ {i + 1 } $ one has actually calculated the element

$$ \tag{2 } \widetilde{x} _ {i + 1 } = \ A _ {i} ( \widetilde{x} _ {1} \dots \widetilde{x} _ {i} ) + \delta _ {i} ,\ \ \delta _ {i} \in X _ {i + 1 } , $$

where the small additive error $ \delta _ {i} $ arises by rounding in the course of applying the operator $ A _ {i} $. The value of $ \delta _ {i} $, determined from the values of $ \widetilde{x} _ {j} $, $ j = 1 \dots i $, depends on the method of rounding, the working of the machine program, etc. However, even if $ \| \delta _ {j} \| $ is small for $ j = 1 \dots i $, this by itself will not guarantee that $ \| x _ {i + 1 } - \widetilde{x} _ {i + 1 } \| $ is small. This difference will be small only for a so-called stable computational process, for which it is not strongly dependent on $ i $.

References

[1]	I. [I. Babushka] Babuška, M. Práger, E. Vitásek, "Numerical processes in differential equations" , Wiley (1966)
[2]	V.V. Voevodin, "Rounding-off errors and stability in direct methods of linear algebra" , Moscow (1969) (In Russian)
[3]	M.K. Gavurin, "Lectures on computing methods" , Moscow (1971) (In Russian)

References

[a1]	J.H. Wilkinson, "Rounding errors in algebraic processes" , Prentice-Hall (1963)