View source for Stability of difference schemes

<!--
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.
-->

{{TEX|auto}}
{{TEX|done}}

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. [[#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]]]).

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.

$$ 
\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. [[#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

$$ \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. [[#References|[3]]], [[#References|[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. [[#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

$$ \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. [[#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  $  \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]]).

In the case of the [[Cauchy problem|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. [[#References|[2]]], [[#References|[14]]], [[#References|[15]]]).

====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>
<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>