Namespaces
Variants
Actions

Difference between revisions of "Stability of difference schemes"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (Undo revision 48795 by Ulf Rehmann (talk))
Tag: Undo
m (tex encoded by computer)
Line 1: Line 1:
One of the important concepts in the theory of difference (grid) methods, characterizing the continuous dependence of the solution of a difference scheme on the input information. More precisely, suppose that a difference scheme (a difference or grid analogue of the original problem) is constructed on a set of grids <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s0870301.png" />, with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s0870302.png" />, in the space of the independent variable for the original problem, where the parameter <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s0870303.png" /> is an element of a certain normed linear space and characterizes the concrete grid being used. Suppose that to each such grid <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s0870304.png" /> corresponds an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s0870305.png" />-dimensional linear space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s0870306.png" /> and an operator equation in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s0870307.png" /> (a system of difference equations)
+
<!--
 +
s0870301.png
 +
$#A+1 = 113 n = 0
 +
$#C+1 = 113 : ~/encyclopedia/old_files/data/S087/S.0807030 Stability of difference schemes
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
  
<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/s087030/s0870308.png" /></td> <td valign="top" style="width:5%;text-align:right;">(1)</td></tr></table>
+
{{TEX|auto}}
 +
{{TEX|done}}
  
for which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s0870309.png" /> and the operator <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703010.png" /> is given. Usually <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703011.png" /> is connected with the dimensions of a cell of the grid and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703012.png" /> increases without bound as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703013.png" />. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703014.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703015.png" /> be elements of the normed spaces <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703016.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703017.png" />, while the operator <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703018.png" /> is linear. Then the difference scheme is said to be stable if: 1) for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703019.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703020.png" /> exists; and 2) there exists a constant <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703021.png" />, not depending on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703022.png" /> and such that
+
One of the important concepts in the theory of difference (grid) methods, characterizing the continuous dependence of the solution of a difference scheme on the input information. More precisely, suppose that a difference scheme (a difference or grid analogue of the original problem) is constructed on a set of grids  $  \Omega _ {h} $,
 +
with  $  h \in \{ h \} $,
 +
in the space of the independent variable for the original problem, where the parameter  $  h $
 +
is an element of a certain normed linear space and characterizes the concrete grid being used. Suppose that to each such grid  $  \Omega _ {h} $
 +
corresponds an  $  N _ {h} $-
 +
dimensional linear space  $  U _ {h} $
 +
and an operator equation in  $  U _ {h} $(
 +
a system of difference 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/s087030/s08703023.png" /></td> <td valign="top" style="width:5%;text-align:right;">(2)</td></tr></table>
+
$$ \tag{1 }
 +
L _ {h} ( u _ {h} ) =  f _ {h} ,\ \
 +
h \in \{ h \} ,
 +
$$
  
This definition is equivalent to the well-posedness (correctness) of (1): A solution of (1) exists and is unique for any right-hand side <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703024.png" /> and its dependence on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703025.png" /> is uniformly continuous (in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703026.png" />) in the sense of the spaces <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703027.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703028.png" />. In the language of a priori estimates this means that there exists a constant <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703029.png" />, not depending on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703030.png" />, such that for any solution (1) there holds the a priori estimate
+
for which  $  f _ {h} \in U _ {h} $
 +
and the operator  $  L _ {h} $
 +
is given. Usually  $  h $
 +
is connected with the dimensions of a cell of the grid and $  N _ {h} $
 +
increases without bound as  $  \| h \| \rightarrow 0 $.  
 +
Let  $  u _ {h} $
 +
and  $  f _ {h} $
 +
be elements of the normed spaces  $  H _ {h} $
 +
and $  F _ {h} $,
 +
while the operator  $  L _ {h} $
 +
is linear. Then the difference scheme is said to be stable if: 1) for any  $  h \in \{ h \} $,
 +
$  L _ {h}  ^ {-} 1 $
 +
exists; and 2) there exists a constant $  K > 0 $,  
 +
not depending on $  h $
 +
and such that
  
<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/s087030/s08703031.png" /></td> <td valign="top" style="width:5%;text-align:right;">(3)</td></tr></table>
+
$$ \tag{2 }
 +
\| L _ {h}  ^ {-} 1 \| _ {F _ {h}  \rightarrow H _ {h} }  \leq  K,\ \
 +
h \in \{ h \} .
 +
$$
  
Thus, if for a stable difference scheme, for one reason or another (e.g. by means of an approximate solution of (1)), one actually determines not the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703032.png" /> in (1) but a function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703033.png" /> of the perturbed equation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703034.png" />, then it is easy to find an upper estimate for the error:
+
This definition is equivalent to the well-posedness (correctness) of (1): A solution of (1) exists and is unique for any right-hand side  $  f _ {h} $
 +
and its dependence on  $  f _ {h} $
 +
is uniformly continuous (in  $  h $)  
 +
in the sense of the spaces  $  H _ {h} $
 +
and  $  F _ {h} $.
 +
In the language of a priori estimates this means that there exists a constant  $  K $,  
 +
not depending on  $  h $,
 +
such that for any solution (1) there holds the a priori estimate
  
<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/s087030/s08703035.png" /></td> <td valign="top" style="width:5%;text-align:right;">(4)</td></tr></table>
+
$$ \tag{3 }
 +
\| u _ {h} \| _ {H _ {h}  }  \leq  \
 +
K  \| f _ {h} \| _ {F _ {h}  } .
 +
$$
  
Moreover, if the difference scheme is stable and approximates the original problem in the sense of the space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703036.png" />, then it is convergent, with an estimate of the error:
+
Thus, if for a stable difference scheme, for one reason or another (e.g. by means of an approximate solution of (1)), one actually determines not the function  $  u _ {h} $
 +
in (1) but a function  $  \widetilde{u}  _ {h} $
 +
of the perturbed equation  $  L _ {h} \widetilde{u}  _ {h} = \widetilde{f}  _ {h} $,  
 +
then it is easy to find an upper estimate for the error:
  
<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/s087030/s08703037.png" /></td> <td valign="top" style="width:5%;text-align:right;">(5)</td></tr></table>
+
$$ \tag{4 }
 +
\| u _ {h} - \widetilde{u}  _ {h} \| _ {H _ {h}  }  \leq  K \
 +
\| f - \widetilde{f}  _ {h} \| _ {F _ {h}  } .
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703038.png" /> is the error of the scheme and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703039.png" /> is the error of the approximation (cf. [[#References|[1]]]–[[#References|[7]]]). The theorem mentioned explains the reason why <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703040.png" /> is considered as an element of a normed space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703041.png" />: the error of approximation depends essentially on the choice of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703042.png" />. Therefore, for a fixed space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703043.png" /> a stability theorem of type (3) should be used with the weakest norm <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703044.png" /> in which the order of approximation increases. And for a fixed <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703045.png" /> it is appropriate to study (1) by using the strongest norm <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703046.png" />. In this relation there is a complete analogy with the problem of studying the well-posedness of the original boundary value problem. Therefore the spaces <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703047.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703048.png" /> themselves are usually constructed as grid analogues of well-known function spaces (e.g. <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703049.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703050.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703051.png" />, etc., cf. [[#References|[3]]]–[[#References|[5]]]) and they admit a corresponding passage to the limit as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703052.png" />. For examples of the choice of such grid spaces, for different methods of studying the stability of difference schemes in these spaces, and other similar results cf. [[#References|[1]]]–[[#References|[15]]]. In projection-grid methods (finite-element methods) for stationary problems the most widespread is the means of studying the convergence of the basic error estimates by the distance of the solution from the approximating subspace (cf. [[#References|[3]]]–[[#References|[5]]], [[#References|[7]]], [[#References|[10]]]–[[#References|[13]]]). Then the stability theorems of type (3) are only needed to obtain the estimate (4) and their study for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703053.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703054.png" />, which now coincides with Euclidean spaces of grid functions, often invokes the traditional algebraic approach connected with studying the condition number of the matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703055.png" /> (cf. [[#References|[10]]]–[[#References|[12]]]).
+
Moreover, if the difference scheme is stable and approximates the original problem in the sense of the space  $  F _ {h} $,  
 +
then it is convergent, with an estimate of the error:
  
In non-stationary problems the role of the independent variable <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703056.png" /> is essentially different from the role of the space variables, and this circumstance forces one to consider separately a time grid <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703057.png" /> and a grid <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703058.png" /> for the space variables <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703059.png" />. In the same way one defines a specific difference scheme for non-stationary problems connected with a stratification (cf. [[#References|[1]]]–[[#References|[6]]]). For simplicity of description it is here assumed that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703060.png" /> is defined by the step <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703061.png" />, i.e.
+
$$ \tag{5 }
 +
\| z _ {h} \| _ {H _ {h}  }  \leq  K \
 +
\| \xi _ {h} \| _ {F _ {h}  } ,
 +
$$
  
<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/s087030/s08703062.png" /></td> </tr></table>
+
where  $  z _ {h} $
 +
is the error of the scheme and  $  \xi _ {h} $
 +
is the error of the approximation (cf. [[#References|[1]]]–[[#References|[7]]]). The theorem mentioned explains the reason why  $  f _ {h} $
 +
is considered as an element of a normed space  $  F _ {h} $:  
 +
the error of approximation depends essentially on the choice of  $  F _ {h} $.
 +
Therefore, for a fixed space  $  H _ {h} $
 +
a stability theorem of type (3) should be used with the weakest norm  $  \| f _ {h} \| _ {F _ {h}  } $
 +
in which the order of approximation increases. And for a fixed  $  F _ {h} $
 +
it is appropriate to study (1) by using the strongest norm  $  \| u _ {h} \| _ {H _ {h}  } $.
 +
In this relation there is a complete analogy with the problem of studying the well-posedness of the original boundary value problem. Therefore the spaces  $  H _ {h} $
 +
and  $  F _ {h} $
 +
themselves are usually constructed as grid analogues of well-known function spaces (e.g.  $  C ( \Omega ) $,
 +
$  L _ {2} ( \Omega ) $,
 +
$  W _ {2}  ^ {m} ( \Omega ) $,
 +
etc., cf. [[#References|[3]]]–[[#References|[5]]]) and they admit a corresponding passage to the limit as  $  \| h \| \rightarrow 0 $.
 +
For examples of the choice of such grid spaces, for different methods of studying the stability of difference schemes in these spaces, and other similar results cf. [[#References|[1]]]–[[#References|[15]]]. In projection-grid methods (finite-element methods) for stationary problems the most widespread is the means of studying the convergence of the basic error estimates by the distance of the solution from the approximating subspace (cf. [[#References|[3]]]–[[#References|[5]]], [[#References|[7]]], [[#References|[10]]]–[[#References|[13]]]). Then the stability theorems of type (3) are only needed to obtain the estimate (4) and their study for  $  H _ {h} $
 +
and  $  F _ {h} $,
 +
which now coincides with Euclidean spaces of grid functions, often invokes the traditional algebraic approach connected with studying the condition number of the matrix  $  L _ {h} $(
 +
cf. [[#References|[10]]]–[[#References|[12]]]).
  
while the grid <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703063.png" /> is defined by the step vector <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703064.png" /> in the space variables, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703065.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703066.png" />. Then the grid <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703067.png" /> in (1) is defined by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703068.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703069.png" /> and the space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703070.png" /> consists of the vectors <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703071.png" />, where each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703072.png" /> lies in the linear space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703073.png" /> of grid functions given on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703074.png" />. Therefore the norms in the spaces <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703075.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703076.png" /> encountered in (2)–(5) are usually defined by different norms <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703077.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703078.png" /> for the linear space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703079.png" /> of grid functions given on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703080.png" />. For example, as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703081.png" /> one often chooses an expression of the type <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703082.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703083.png" />, etc. (cf. [[#References|[1]]]–[[#References|[6]]]). The most detailed study of these cases has been when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703084.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703085.png" /> are Euclidean or unitary spaces and where it was possible to obtain estimates of the type (3) by relatively simple means. E.g. consider a linear one-level difference scheme of the form
+
In non-stationary problems the role of the independent variable  $  t $
 +
is essentially different from the role of the space variables, and this circumstance forces one to consider separately a time grid $  \omega _ {t} $
 +
and a grid $  \omega _ {x} $
 +
for the space variables  $  x _ {1} \dots x _ {d} $.  
 +
In the same way one defines a specific difference scheme for non-stationary problems connected with a stratification (cf. [[#References|[1]]]–[[#References|[6]]]). For simplicity of description it is here assumed that  $  \omega _ {t} = \omega _ {t, \tau }  $
 +
is defined by the step  $  \tau > 0 $,
 +
i.e.
  
<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/s087030/s08703086.png" /></td> <td valign="top" style="width:5%;text-align:right;">(6)</td></tr></table>
+
$$
 +
\omega _ {t}  \equiv \
 +
\{ {t = n \tau \equiv t _ {n} } : {n = 0 \dots [ T _  \tau  ^ {-} 1 ] } \}
 +
,
 +
$$
  
where the vectors <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703087.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703088.png" /> are defined by initial conditions and the right-hand sides of the equations, and where the operators <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703089.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703090.png" /> in the Euclidean space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703091.png" /> are such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703092.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703093.png" />, where the non-negative constants <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703094.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703095.png" /> do not depend on the grid. Then the following a priori estimate holds for the solution of (6):
+
while the grid  $  \omega _ {x} $
 +
is defined by the step vector  $  ( h _ {1} \dots h _ {d} ) $
 +
in the space variables,  $  h _ {r} > 0 $,
 +
$  r = 1 \dots d $.  
 +
Then the grid  $  \Omega $
 +
in (1) is defined by $  \omega _ {t} \times \omega _ {x} $,
 +
where  $  h = \{ \tau , h _ {1} \dots h _ {d} \} $
 +
and the space  $  U _ {h} $
 +
consists of the vectors  $  u \equiv \{ u ( 0), u ( \tau ) \dots u ([ T _  \tau  ^ {-} 1 ]) \} $,  
 +
where each  $  u ( n \tau ) \equiv u  ^ {n} $
 +
lies in the linear space  $  U = U ( h _ {1} \dots h _ {d} ) $
 +
of grid functions given on  $  \omega _ {x} $.  
 +
Therefore the norms in the spaces  $  H _ {h} $
 +
and $  F _ {h} $
 +
encountered in (2)–(5) are usually defined by different norms  $  \| u \| _ {H} $
 +
and  $  \| f \| _ {F} $
 +
for the linear space $  U $
 +
of grid functions given on  $  \omega _ {x} $.  
 +
For example, as  $  \| u _ {h} \| _ {H _ {n}  } $
 +
one often chooses an expression of the type  $  \max _ {t  ^ {n}  \in \omega _ {t} }  \| u  ^ {n} \| $,
 +
$  \tau \sum _ {n} \| u  ^ {n} \| _ {H} $,  
 +
etc. (cf. [[#References|[1]]]–[[#References|[6]]]). The most detailed study of these cases has been when  $  H $
 +
and  $  F $
 +
are Euclidean or unitary spaces and where it was possible to obtain estimates of the type (3) by relatively simple means. E.g. consider a linear one-level difference scheme of the form
  
<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/s087030/s08703096.png" /></td> <td valign="top" style="width:5%;text-align:right;">(7)</td></tr></table>
+
$$ \tag{6 }
 +
\left .
 +
 
 +
\begin{array}{c}
 +
A _ {1} u ^ {n + 1 }  = \
 +
A _ {0} u  ^ {n} + \tau f ^ { n + 1 } ,\ \
 +
n \geq  0,  \\
 +
u _ {0}  = \phi ,  \\
 +
\end{array}
 +
 
 +
\right \}
 +
$$
 +
 
 +
where the vectors  $  \phi $
 +
and  $  f ^ { n + 1 } $
 +
are defined by initial conditions and the right-hand sides of the equations, and where the operators  $  A _ {1} $
 +
and  $  A _ {0} $
 +
in the Euclidean space  $  H $
 +
are such that  $  \| A _ {1}  ^ {-} 1 \| \leq  C _ {0} $,
 +
$  \| A _ {1}  ^ {-} 1 A _ {0} \| \leq  1 + C _ {1} \tau $,
 +
where the non-negative constants  $  C _ {0} $
 +
and  $  C _ {1} $
 +
do not depend on the grid. Then the following a priori estimate holds for the solution of (6):
 +
 
 +
$$ \tag{7 }
 +
\max _ {\begin{array}{c}
 +
n \\
 +
t \in \omega _ {t}
 +
\end{array}
 +
}  \| u  ^ {n} \| _ {H}  \leq  \
 +
e ^ {C _ {1} T }
 +
\left \{
 +
\| \phi \| _ {H} +
 +
C _ {0} \sum _ {\begin{array}{c}
 +
n \\
 +
t _ {n + 1 }  \in \omega _ {t}
 +
\end{array}
 +
}
 +
\tau \| f ^ { n + 1 } \| _ {H} \right \} .
 +
$$
  
 
Very often the analysis of such schemes, after expressing it in the canonical form
 
Very often the analysis of such schemes, after expressing it in the canonical form
  
<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/s087030/s08703097.png" /></td> </tr></table>
+
$$
 +
B \left ( {
 +
\frac{u ^ {n + 1 } - u  ^ {n} } \tau
 +
}
 +
\right ) + Au  ^ {n}  = f ^ { n + 1 } ,
 +
$$
  
leads to a basic study of the properties of the transition operator <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703098.png" /> (where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s08703099.png" /> is the identity operator) under the assumption that there is a certain relatively simple information-type operator inequality for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s087030100.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s087030101.png" /> in the Euclidean space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s087030102.png" />. E.g. if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s087030103.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s087030104.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s087030105.png" />, then (cf. [[#References|[3]]], [[#References|[6]]]) there exists a constant <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s087030106.png" /> such that
+
leads to a basic study of the properties of the transition operator $  R = E - \tau B  ^ {-} 1 A $(
 +
where $  E $
 +
is the identity operator) under the assumption that there is a certain relatively simple information-type operator inequality for $  B $
 +
and $  A $
 +
in the Euclidean space $  H $.  
 +
E.g. if $  B = B  ^ {*} > 0 $,  
 +
$  A = A  ^ {*} $
 +
and $  B \geq  \tau ( 1 + \rho )  ^ {-} 1 A $,  
 +
then (cf. [[#References|[3]]], [[#References|[6]]]) there exists a constant $  c = C ( T, \rho ) $
 +
such that
  
<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/s087030/s087030107.png" /></td> <td valign="top" style="width:5%;text-align:right;">(8)</td></tr></table>
+
$$ \tag{8 }
 +
\| u ^ {n + 1 } \| _ {B}  \leq  C
 +
\left (
 +
\| u  ^ {0} \| _ {B} + \tau
 +
\sum _ {k = 0 } ^ { n }
 +
\| f ^ { k + 1 } \| _ {B  ^ {-}  1 }
 +
\right ) ,
 +
$$
  
<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/s087030/s087030108.png" /></td> </tr></table>
+
$$
 +
t _ {n+} 1  \in  \omega _ {t} ,
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s087030109.png" />. Similar results have been obtained for a sufficiently large class of difference schemes, including certain multi-step schemes (cf. [[#References|[6]]]). For this, certain special cases of stability have been studied (stability with respect to the initial conditions, or with respect to the right-hand side) and their interdependence. There are results connected with necessary conditions similar to stability or related to it (cf. [[#References|[3]]], [[#References|[6]]]). An application of the energy inequality (cf. [[#References|[4]]], [[#References|[5]]]) instead of (8) leads one, under related conditions, to estimates of the form
+
where $  \| u  ^ {n} \| _ {B} = ( Bu  ^ {n} , u  ^ {n} ) _ {H}  ^ {1/2} $.  
 +
Similar results have been obtained for a sufficiently large class of difference schemes, including certain multi-step schemes (cf. [[#References|[6]]]). For this, certain special cases of stability have been studied (stability with respect to the initial conditions, or with respect to the right-hand side) and their interdependence. There are results connected with necessary conditions similar to stability or related to it (cf. [[#References|[3]]], [[#References|[6]]]). An application of the energy inequality (cf. [[#References|[4]]], [[#References|[5]]]) instead of (8) leads one, under related conditions, to estimates of the form
  
<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/s087030/s087030110.png" /></td> <td valign="top" style="width:5%;text-align:right;">(9)</td></tr></table>
+
$$ \tag{9 }
 +
\| u ^ {n + 1 } \| _ {B}  ^ {2} + \tau
 +
\sum _ {k = 0 } ^ { n }
 +
\| u ^ {k + 1 } \| _ {H}  ^ {2\ } \leq
 +
$$
  
<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/s087030/s087030111.png" /></td> </tr></table>
+
$$
 +
\leq  \
 +
C _ {1} \left ( \| u  ^ {0} \| _ {B}  ^ {2} + \tau \sum _ {k = 0 } ^ { n }  \| f ^ { k + 1 } \| _ {B  ^ {-}  1 }  ^ {2} \right ) ,
 +
$$
  
which reduce to stability in a certain relatively stronger norm for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s087030112.png" />, and allows one to pass to the limit in this estimate. Such estimates are often encountered in the theory of evolution equations. Similar estimates have also been obtained for a very large class of schemes (cf. [[#References|[4]]], [[#References|[5]]], [[#References|[13]]]).
+
which reduce to stability in a certain relatively stronger norm for $  u _ {h} $,  
 +
and allows one to pass to the limit in this estimate. Such estimates are often encountered in the theory of evolution equations. Similar estimates have also been obtained for a very large class of schemes (cf. [[#References|[4]]], [[#References|[5]]], [[#References|[13]]]).
  
For a study of the stability of difference schemes one distinguishes conditionally-stable difference schemes for explicit schemes for the heat equation, in which one has stability only under conditions like <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s087/s087030/s087030113.png" />, and absolutely-stable schemes in which the steps for the time and space variables can be changed independently of each other without affecting stability. Schemes of this type are often preferred, if they do not require the solution of a complicated system at each step. Alternating-directions implicit schemes, splitting schemes, schemes with splitting operators and additive schemes, cf. [[#References|[1]]]–[[#References|[6]]], [[#References|[13]]], lead to such economic difference schemes for multi-dimensional problems.
+
For a study of the stability of difference schemes one distinguishes conditionally-stable difference schemes for explicit schemes for the heat equation, in which one has stability only under conditions like $  \tau ( h _ {s} )  ^ {-} 2 \leq  \kappa _ {0} $,  
 +
and absolutely-stable schemes in which the steps for the time and space variables can be changed independently of each other without affecting stability. Schemes of this type are often preferred, if they do not require the solution of a complicated system at each step. Alternating-directions implicit schemes, splitting schemes, schemes with splitting operators and additive schemes, cf. [[#References|[1]]]–[[#References|[6]]], [[#References|[13]]], lead to such economic difference schemes for multi-dimensional problems.
  
 
Stability theorems with estimates of the type (3), (9) are also used in cases where the degree of approximation and the estimate (5) cannot be considered, but the corresponding prolongations of solutions of the grid problems are constructed and, basically, a theorem on compact convergence to the solution of the original problem has been established (cf. [[#References|[4]]], [[#References|[5]]]). The study of various a priori estimates and the compactness principle mentioned are particular characteristics for complicated non-linear problems, in which the solution may be non-unique, and the convergence is established only for certain solutions of the original problem. Sometimes the study of non-linear problems of mathematical physics is, because of the complexity of these problems, changed to a study of linearizations of the equations, and for difference schemes main attention has been paid to grid analogues of important physical conservation laws (cf. [[#References|[8]]]). For weak non-linear problems the study of the correctness of difference schemes has often been worked out in the sufficient completeness which is characteristic for the linear case (cf. [[#References|[5]]]–[[#References|[7]]] and [[Non-linear boundary value problem, numerical methods|Non-linear boundary value problem, numerical methods]]).
 
Stability theorems with estimates of the type (3), (9) are also used in cases where the degree of approximation and the estimate (5) cannot be considered, but the corresponding prolongations of solutions of the grid problems are constructed and, basically, a theorem on compact convergence to the solution of the original problem has been established (cf. [[#References|[4]]], [[#References|[5]]]). The study of various a priori estimates and the compactness principle mentioned are particular characteristics for complicated non-linear problems, in which the solution may be non-unique, and the convergence is established only for certain solutions of the original problem. Sometimes the study of non-linear problems of mathematical physics is, because of the complexity of these problems, changed to a study of linearizations of the equations, and for difference schemes main attention has been paid to grid analogues of important physical conservation laws (cf. [[#References|[8]]]). For weak non-linear problems the study of the correctness of difference schemes has often been worked out in the sufficient completeness which is characteristic for the linear case (cf. [[#References|[5]]]–[[#References|[7]]] and [[Non-linear boundary value problem, numerical methods|Non-linear boundary value problem, numerical methods]]).
Line 59: Line 237:
 
====References====
 
====References====
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  A.R. Mitchell,  "Computational methods in partial differential equations" , Wiley  (1969)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  I.S. Berezin,  N.P. Zhidkov,  "Computing methods" , Pergamon  (1973)  (Translated from Russian)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  S.K. Godunov,  V.S. Ryaben'kii,  "The theory of difference schemes" , North-Holland  (1964)  (Translated from Russian)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  E.G. D'yakonov,  "Minimization of computational work. Asymptotically-optimal algorithms" , Moscow  (1989)  (In Russian)</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  E.G. D'yakonov,  "Difference methods for solving boundary value problems" , '''1–2''' , Moscow  (1971–1972)  (In Russian)</TD></TR><TR><TD valign="top">[6]</TD> <TD valign="top">  A.A. Samarskii,  A.V. Gulin,  "Stability of difference schemes" , Moscow  (1973)  (In Russian)</TD></TR><TR><TD valign="top">[7]</TD> <TD valign="top">  A.A. Samarskii,  V.B. Andreev,  "Méthodes aux différences pour équations elliptiques" , MIR  (1978)  (Translated from Russian)</TD></TR><TR><TD valign="top">[8]</TD> <TD valign="top">  A.A. Samarskii,  Yu.P. Poppov,  "Difference methods for the solution of problems in gas dynamics" , Moscow  (1980)  (In Russian)</TD></TR><TR><TD valign="top">[9]</TD> <TD valign="top">  O.A. Ladyzhenskaya,  "The mathematical theory of viscous incompressible flows" , Gordon &amp; Breach  (1963)  (Translated from Russian)</TD></TR><TR><TD valign="top">[10]</TD> <TD valign="top">  O. Axelson,  V.A. Barker,  "Finite element solution of boundary value problems. Theory and computation" , Acad. Press  (1984)</TD></TR><TR><TD valign="top">[11]</TD> <TD valign="top">  W. Hackbusch,  "Theorie und Numerik elliptischer Differentialgleichungen" , Teubner  (1986)</TD></TR><TR><TD valign="top">[12]</TD> <TD valign="top">  G. Strang,  J. Fix,  "An analyse of the finite element method" , Prentice-Hall  (1973)</TD></TR><TR><TD valign="top">[13]</TD> <TD valign="top">  G. Fairweather,  "Finite element Galerkin methods for differential equations" , M. Dekker  (1978)</TD></TR><TR><TD valign="top">[14]</TD> <TD valign="top">  N.S. Bakhvalov,  "Numerical methods: analysis, algebra, ordinary differential equations" , MIR  (1977)  (Translated from Russian)</TD></TR><TR><TD valign="top">[15]</TD> <TD valign="top">  Yu.V. Rakitskii,  S.M. Ustinov,  I.G. Chernorustskii,  "Computational methods for the solution of stiff systems" , Moscow  (1979)  (In Russian)</TD></TR></table>
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  A.R. Mitchell,  "Computational methods in partial differential equations" , Wiley  (1969)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  I.S. Berezin,  N.P. Zhidkov,  "Computing methods" , Pergamon  (1973)  (Translated from Russian)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  S.K. Godunov,  V.S. Ryaben'kii,  "The theory of difference schemes" , North-Holland  (1964)  (Translated from Russian)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  E.G. D'yakonov,  "Minimization of computational work. Asymptotically-optimal algorithms" , Moscow  (1989)  (In Russian)</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  E.G. D'yakonov,  "Difference methods for solving boundary value problems" , '''1–2''' , Moscow  (1971–1972)  (In Russian)</TD></TR><TR><TD valign="top">[6]</TD> <TD valign="top">  A.A. Samarskii,  A.V. Gulin,  "Stability of difference schemes" , Moscow  (1973)  (In Russian)</TD></TR><TR><TD valign="top">[7]</TD> <TD valign="top">  A.A. Samarskii,  V.B. Andreev,  "Méthodes aux différences pour équations elliptiques" , MIR  (1978)  (Translated from Russian)</TD></TR><TR><TD valign="top">[8]</TD> <TD valign="top">  A.A. Samarskii,  Yu.P. Poppov,  "Difference methods for the solution of problems in gas dynamics" , Moscow  (1980)  (In Russian)</TD></TR><TR><TD valign="top">[9]</TD> <TD valign="top">  O.A. Ladyzhenskaya,  "The mathematical theory of viscous incompressible flows" , Gordon &amp; Breach  (1963)  (Translated from Russian)</TD></TR><TR><TD valign="top">[10]</TD> <TD valign="top">  O. Axelson,  V.A. Barker,  "Finite element solution of boundary value problems. Theory and computation" , Acad. Press  (1984)</TD></TR><TR><TD valign="top">[11]</TD> <TD valign="top">  W. Hackbusch,  "Theorie und Numerik elliptischer Differentialgleichungen" , Teubner  (1986)</TD></TR><TR><TD valign="top">[12]</TD> <TD valign="top">  G. Strang,  J. Fix,  "An analyse of the finite element method" , Prentice-Hall  (1973)</TD></TR><TR><TD valign="top">[13]</TD> <TD valign="top">  G. Fairweather,  "Finite element Galerkin methods for differential equations" , M. Dekker  (1978)</TD></TR><TR><TD valign="top">[14]</TD> <TD valign="top">  N.S. Bakhvalov,  "Numerical methods: analysis, algebra, ordinary differential equations" , MIR  (1977)  (Translated from Russian)</TD></TR><TR><TD valign="top">[15]</TD> <TD valign="top">  Yu.V. Rakitskii,  S.M. Ustinov,  I.G. Chernorustskii,  "Computational methods for the solution of stiff systems" , Moscow  (1979)  (In Russian)</TD></TR></table>
 
 
  
 
====Comments====
 
====Comments====
 
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  L. Lapidus,  G.F. Pinder,  "Numerical solution of partial differential equations in science and engineering" , Wiley  (1982)</TD></TR></table>
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  L. Lapidus,  G.F. Pinder,  "Numerical solution of partial differential equations in science and engineering" , Wiley  (1982)</TD></TR></table>

Revision as of 14:55, 7 June 2020


One of the important concepts in the theory of difference (grid) methods, characterizing the continuous dependence of the solution of a difference scheme on the input information. More precisely, suppose that a difference scheme (a difference or grid analogue of the original problem) is constructed on a set of grids $ \Omega _ {h} $, with $ h \in \{ h \} $, in the space of the independent variable for the original problem, where the parameter $ h $ is an element of a certain normed linear space and characterizes the concrete grid being used. Suppose that to each such grid $ \Omega _ {h} $ corresponds an $ N _ {h} $- dimensional linear space $ U _ {h} $ and an operator equation in $ U _ {h} $( a system of difference equations)

$$ \tag{1 } L _ {h} ( u _ {h} ) = f _ {h} ,\ \ h \in \{ h \} , $$

for which $ f _ {h} \in U _ {h} $ and the operator $ L _ {h} $ is given. Usually $ h $ is connected with the dimensions of a cell of the grid and $ N _ {h} $ increases without bound as $ \| h \| \rightarrow 0 $. Let $ u _ {h} $ and $ f _ {h} $ be elements of the normed spaces $ H _ {h} $ and $ F _ {h} $, while the operator $ L _ {h} $ is linear. Then the difference scheme is said to be stable if: 1) for any $ h \in \{ h \} $, $ L _ {h} ^ {-} 1 $ exists; and 2) there exists a constant $ K > 0 $, not depending on $ h $ and such that

$$ \tag{2 } \| L _ {h} ^ {-} 1 \| _ {F _ {h} \rightarrow H _ {h} } \leq K,\ \ h \in \{ h \} . $$

This definition is equivalent to the well-posedness (correctness) of (1): A solution of (1) exists and is unique for any right-hand side $ f _ {h} $ and its dependence on $ f _ {h} $ is uniformly continuous (in $ h $) in the sense of the spaces $ H _ {h} $ and $ F _ {h} $. In the language of a priori estimates this means that there exists a constant $ K $, not depending on $ h $, such that for any solution (1) there holds the a priori estimate

$$ \tag{3 } \| u _ {h} \| _ {H _ {h} } \leq \ K \| f _ {h} \| _ {F _ {h} } . $$

Thus, if for a stable difference scheme, for one reason or another (e.g. by means of an approximate solution of (1)), one actually determines not the function $ u _ {h} $ in (1) but a function $ \widetilde{u} _ {h} $ of the perturbed equation $ L _ {h} \widetilde{u} _ {h} = \widetilde{f} _ {h} $, then it is easy to find an upper estimate for the error:

$$ \tag{4 } \| u _ {h} - \widetilde{u} _ {h} \| _ {H _ {h} } \leq K \ \| f - \widetilde{f} _ {h} \| _ {F _ {h} } . $$

Moreover, if the difference scheme is stable and approximates the original problem in the sense of the space $ F _ {h} $, then it is convergent, with an estimate of the error:

$$ \tag{5 } \| z _ {h} \| _ {H _ {h} } \leq K \ \| \xi _ {h} \| _ {F _ {h} } , $$

where $ z _ {h} $ is the error of the scheme and $ \xi _ {h} $ is the error of the approximation (cf. [1][7]). The theorem mentioned explains the reason why $ f _ {h} $ is considered as an element of a normed space $ F _ {h} $: the error of approximation depends essentially on the choice of $ F _ {h} $. Therefore, for a fixed space $ H _ {h} $ a stability theorem of type (3) should be used with the weakest norm $ \| f _ {h} \| _ {F _ {h} } $ in which the order of approximation increases. And for a fixed $ F _ {h} $ it is appropriate to study (1) by using the strongest norm $ \| u _ {h} \| _ {H _ {h} } $. In this relation there is a complete analogy with the problem of studying the well-posedness of the original boundary value problem. Therefore the spaces $ H _ {h} $ and $ F _ {h} $ themselves are usually constructed as grid analogues of well-known function spaces (e.g. $ C ( \Omega ) $, $ L _ {2} ( \Omega ) $, $ W _ {2} ^ {m} ( \Omega ) $, etc., cf. [3][5]) and they admit a corresponding passage to the limit as $ \| h \| \rightarrow 0 $. For examples of the choice of such grid spaces, for different methods of studying the stability of difference schemes in these spaces, and other similar results cf. [1][15]. In projection-grid methods (finite-element methods) for stationary problems the most widespread is the means of studying the convergence of the basic error estimates by the distance of the solution from the approximating subspace (cf. [3][5], [7], [10][13]). Then the stability theorems of type (3) are only needed to obtain the estimate (4) and their study for $ H _ {h} $ and $ F _ {h} $, which now coincides with Euclidean spaces of grid functions, often invokes the traditional algebraic approach connected with studying the condition number of the matrix $ L _ {h} $( cf. [10][12]).

In non-stationary problems the role of the independent variable $ t $ is essentially different from the role of the space variables, and this circumstance forces one to consider separately a time grid $ \omega _ {t} $ and a grid $ \omega _ {x} $ for the space variables $ x _ {1} \dots x _ {d} $. In the same way one defines a specific difference scheme for non-stationary problems connected with a stratification (cf. [1][6]). For simplicity of description it is here assumed that $ \omega _ {t} = \omega _ {t, \tau } $ is defined by the step $ \tau > 0 $, i.e.

$$ \omega _ {t} \equiv \ \{ {t = n \tau \equiv t _ {n} } : {n = 0 \dots [ T _ \tau ^ {-} 1 ] } \} , $$

while the grid $ \omega _ {x} $ is defined by the step vector $ ( h _ {1} \dots h _ {d} ) $ in the space variables, $ h _ {r} > 0 $, $ r = 1 \dots d $. Then the grid $ \Omega $ in (1) is defined by $ \omega _ {t} \times \omega _ {x} $, where $ h = \{ \tau , h _ {1} \dots h _ {d} \} $ and the space $ U _ {h} $ consists of the vectors $ u \equiv \{ u ( 0), u ( \tau ) \dots u ([ T _ \tau ^ {-} 1 ]) \} $, where each $ u ( n \tau ) \equiv u ^ {n} $ lies in the linear space $ U = U ( h _ {1} \dots h _ {d} ) $ of grid functions given on $ \omega _ {x} $. Therefore the norms in the spaces $ H _ {h} $ and $ F _ {h} $ encountered in (2)–(5) are usually defined by different norms $ \| u \| _ {H} $ and $ \| f \| _ {F} $ for the linear space $ U $ of grid functions given on $ \omega _ {x} $. For example, as $ \| u _ {h} \| _ {H _ {n} } $ one often chooses an expression of the type $ \max _ {t ^ {n} \in \omega _ {t} } \| u ^ {n} \| $, $ \tau \sum _ {n} \| u ^ {n} \| _ {H} $, etc. (cf. [1][6]). The most detailed study of these cases has been when $ H $ and $ F $ are Euclidean or unitary spaces and where it was possible to obtain estimates of the type (3) by relatively simple means. E.g. consider a linear one-level difference scheme of the form

$$ \tag{6 } \left . \begin{array}{c} A _ {1} u ^ {n + 1 } = \ A _ {0} u ^ {n} + \tau f ^ { n + 1 } ,\ \ n \geq 0, \\ u _ {0} = \phi , \\ \end{array} \right \} $$

where the vectors $ \phi $ and $ f ^ { n + 1 } $ are defined by initial conditions and the right-hand sides of the equations, and where the operators $ A _ {1} $ and $ A _ {0} $ in the Euclidean space $ H $ are such that $ \| A _ {1} ^ {-} 1 \| \leq C _ {0} $, $ \| A _ {1} ^ {-} 1 A _ {0} \| \leq 1 + C _ {1} \tau $, where the non-negative constants $ C _ {0} $ and $ C _ {1} $ do not depend on the grid. Then the following a priori estimate holds for the solution of (6):

$$ \tag{7 } \max _ {\begin{array}{c} n \\ t \in \omega _ {t} \end{array} } \| u ^ {n} \| _ {H} \leq \ e ^ {C _ {1} T } \left \{ \| \phi \| _ {H} + C _ {0} \sum _ {\begin{array}{c} n \\ t _ {n + 1 } \in \omega _ {t} \end{array} } \tau \| f ^ { n + 1 } \| _ {H} \right \} . $$

Very often the analysis of such schemes, after expressing it in the canonical form

$$ B \left ( { \frac{u ^ {n + 1 } - u ^ {n} } \tau } \right ) + Au ^ {n} = f ^ { n + 1 } , $$

leads to a basic study of the properties of the transition operator $ R = E - \tau B ^ {-} 1 A $( where $ E $ is the identity operator) under the assumption that there is a certain relatively simple information-type operator inequality for $ B $ and $ A $ in the Euclidean space $ H $. E.g. if $ B = B ^ {*} > 0 $, $ A = A ^ {*} $ and $ B \geq \tau ( 1 + \rho ) ^ {-} 1 A $, then (cf. [3], [6]) there exists a constant $ c = C ( T, \rho ) $ such that

$$ \tag{8 } \| u ^ {n + 1 } \| _ {B} \leq C \left ( \| u ^ {0} \| _ {B} + \tau \sum _ {k = 0 } ^ { n } \| f ^ { k + 1 } \| _ {B ^ {-} 1 } \right ) , $$

$$ t _ {n+} 1 \in \omega _ {t} , $$

where $ \| u ^ {n} \| _ {B} = ( Bu ^ {n} , u ^ {n} ) _ {H} ^ {1/2} $. Similar results have been obtained for a sufficiently large class of difference schemes, including certain multi-step schemes (cf. [6]). For this, certain special cases of stability have been studied (stability with respect to the initial conditions, or with respect to the right-hand side) and their interdependence. There are results connected with necessary conditions similar to stability or related to it (cf. [3], [6]). An application of the energy inequality (cf. [4], [5]) instead of (8) leads one, under related conditions, to estimates of the form

$$ \tag{9 } \| u ^ {n + 1 } \| _ {B} ^ {2} + \tau \sum _ {k = 0 } ^ { n } \| u ^ {k + 1 } \| _ {H} ^ {2\ } \leq $$

$$ \leq \ C _ {1} \left ( \| u ^ {0} \| _ {B} ^ {2} + \tau \sum _ {k = 0 } ^ { n } \| f ^ { k + 1 } \| _ {B ^ {-} 1 } ^ {2} \right ) , $$

which reduce to stability in a certain relatively stronger norm for $ u _ {h} $, and allows one to pass to the limit in this estimate. Such estimates are often encountered in the theory of evolution equations. Similar estimates have also been obtained for a very large class of schemes (cf. [4], [5], [13]).

For a study of the stability of difference schemes one distinguishes conditionally-stable difference schemes for explicit schemes for the heat equation, in which one has stability only under conditions like $ \tau ( h _ {s} ) ^ {-} 2 \leq \kappa _ {0} $, and absolutely-stable schemes in which the steps for the time and space variables can be changed independently of each other without affecting stability. Schemes of this type are often preferred, if they do not require the solution of a complicated system at each step. Alternating-directions implicit schemes, splitting schemes, schemes with splitting operators and additive schemes, cf. [1][6], [13], lead to such economic difference schemes for multi-dimensional problems.

Stability theorems with estimates of the type (3), (9) are also used in cases where the degree of approximation and the estimate (5) cannot be considered, but the corresponding prolongations of solutions of the grid problems are constructed and, basically, a theorem on compact convergence to the solution of the original problem has been established (cf. [4], [5]). The study of various a priori estimates and the compactness principle mentioned are particular characteristics for complicated non-linear problems, in which the solution may be non-unique, and the convergence is established only for certain solutions of the original problem. Sometimes the study of non-linear problems of mathematical physics is, because of the complexity of these problems, changed to a study of linearizations of the equations, and for difference schemes main attention has been paid to grid analogues of important physical conservation laws (cf. [8]). For weak non-linear problems the study of the correctness of difference schemes has often been worked out in the sufficient completeness which is characteristic for the linear case (cf. [5][7] and Non-linear boundary value problem, numerical methods).

In the case of the Cauchy problem for ordinary differential equations a study of the stability of difference schemes has often been reduced in model situations to the study of the roots of the characteristic equation (cf. [2], [14], [15]).

References

[1] A.R. Mitchell, "Computational methods in partial differential equations" , Wiley (1969)
[2] I.S. Berezin, N.P. Zhidkov, "Computing methods" , Pergamon (1973) (Translated from Russian)
[3] S.K. Godunov, V.S. Ryaben'kii, "The theory of difference schemes" , North-Holland (1964) (Translated from Russian)
[4] E.G. D'yakonov, "Minimization of computational work. Asymptotically-optimal algorithms" , Moscow (1989) (In Russian)
[5] E.G. D'yakonov, "Difference methods for solving boundary value problems" , 1–2 , Moscow (1971–1972) (In Russian)
[6] A.A. Samarskii, A.V. Gulin, "Stability of difference schemes" , Moscow (1973) (In Russian)
[7] A.A. Samarskii, V.B. Andreev, "Méthodes aux différences pour équations elliptiques" , MIR (1978) (Translated from Russian)
[8] A.A. Samarskii, Yu.P. Poppov, "Difference methods for the solution of problems in gas dynamics" , Moscow (1980) (In Russian)
[9] O.A. Ladyzhenskaya, "The mathematical theory of viscous incompressible flows" , Gordon & Breach (1963) (Translated from Russian)
[10] O. Axelson, V.A. Barker, "Finite element solution of boundary value problems. Theory and computation" , Acad. Press (1984)
[11] W. Hackbusch, "Theorie und Numerik elliptischer Differentialgleichungen" , Teubner (1986)
[12] G. Strang, J. Fix, "An analyse of the finite element method" , Prentice-Hall (1973)
[13] G. Fairweather, "Finite element Galerkin methods for differential equations" , M. Dekker (1978)
[14] N.S. Bakhvalov, "Numerical methods: analysis, algebra, ordinary differential equations" , MIR (1977) (Translated from Russian)
[15] Yu.V. Rakitskii, S.M. Ustinov, I.G. Chernorustskii, "Computational methods for the solution of stiff systems" , Moscow (1979) (In Russian)

Comments

References

[a1] L. Lapidus, G.F. Pinder, "Numerical solution of partial differential equations in science and engineering" , Wiley (1982)
How to Cite This Entry:
Stability of difference schemes. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Stability_of_difference_schemes&oldid=49440
This article was adapted from an original article by E.G. D'yakonov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article