Namespaces
Variants
Actions

Difference between revisions of "Stability of a computational process"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
 
Line 1: Line 1:
 +
<!--
 +
s0870001.png
 +
$#A+1 = 27 n = 0
 +
$#C+1 = 27 : ~/encyclopedia/old_files/data/S087/S.0807000 Stability of a computational process
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
 +
 +
{{TEX|auto}}
 +
{{TEX|done}}
 +
 
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 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
+
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
  
<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>
+
$$ \tag{1 }
 +
x _ {i + 1 }  = \
 +
A _ {i} ( x _ {1} \dots x _ {i} ),
 +
$$
  
<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>
+
$$
 +
x _ {i + 1 }  \in  X _ {i + 1 }  ,\  i = 1 \dots N - 1,
 +
$$
  
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).
+
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 <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
+
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
  
<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>
+
$$ \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 <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" />.
+
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====
 
====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>
 
<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====
 
====Comments====
 
  
 
====References====
 
====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>
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  J.H. Wilkinson,  "Rounding errors in algebraic processes" , Prentice-Hall  (1963)</TD></TR></table>

Latest revision as of 08:22, 6 June 2020


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)

Comments

References

[a1] J.H. Wilkinson, "Rounding errors in algebraic processes" , Prentice-Hall (1963)
How to Cite This Entry:
Stability of a computational process. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Stability_of_a_computational_process&oldid=48792
This article was adapted from an original article by A.F. Shapkin (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article