View source for 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087000/s0870001.png" /> be a normed linear space and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087000/s0870002.png" /> a continuous operator <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087000/s0870003.png" />. Then the sequence of equations

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087000/s0870004.png" /></td> <td valign="top" style="width:5%;text-align:right;">(1)</td></tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087000/s0870005.png" /></td> </tr></table>

gives a computational process with original data <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087000/s0870006.png" /> and intermediate results <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087000/s0870007.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087000/s0870008.png" />. Usually <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087000/s0870009.png" /> and the operator <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087000/s08700010.png" /> consists of a finite number of arithmetic operations. As a rule <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087000/s08700011.png" /> depends not on all the intermediate results obtained earlier. The number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087000/s08700012.png" /> may be given in advance or determined in the course of the computational process itself. In the latter case <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087000/s08700013.png" /> depends on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087000/s08700014.png" /> (e.g. if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087000/s08700015.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087000/s08700016.png" /> may be obtained from inexact previous results. This means that instead of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087000/s08700017.png" /> one has actually calculated the element

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087000/s08700018.png" /></td> <td valign="top" style="width:5%;text-align:right;">(2)</td></tr></table>

where the small additive error <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087000/s08700019.png" /> arises by rounding in the course of applying the operator <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087000/s08700020.png" />. The value of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087000/s08700021.png" />, determined from the values of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087000/s08700022.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087000/s08700023.png" />, depends on the method of rounding, the working of the machine program, etc. However, even if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087000/s08700024.png" /> is small for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087000/s08700025.png" />, this by itself will not guarantee that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087000/s08700026.png" /> is small. This difference will be small only for a so-called stable computational process, for which it is not strongly dependent on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087000/s08700027.png" />.

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



====Comments====


====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  J.H. Wilkinson,   "Rounding errors in algebraic processes" , Prentice-Hall  (1963)</TD></TR></table>