Closure of a computational algorithm

A system of equations

$$L_zu=f_z,\quad0\leq z\leq Z,\tag{1}$$

obtained as the limit as $h\to0$, $z(m,h)\to z$ of a system of partially solved equations

$$L_m^hu^h=f_m^h,\quad m=0,\dots,M,\tag{2}$$

describing the successive steps of a computational algorithm for the solution of an equation

$$L^hu^h=f^h\tag{3}$$

(for example, a finite-difference equation, in which case $h$ is the grid spacing), which approximates the equation

$$Lu=f\tag{4}$$

as $h\to0$. It is assumed here that $L_0^h=L^h$, $f_0^h=f^h$, $L_M^h$ is the identity operator, and that $f_M^h=(L^h)^{-1}f^h=u^h$, i.e. the $M$-th step of the algorithm yields a final solution of the approximate equation \ref{3}. The function $z(m,h)$ is assumed to increase with $m$ (e.g. is a linearly increasing function) and to satisfy the boundary conditions $z(0,h)=0$, $z(M,h)=Z$. The case $M=\infty$ is admissible; then $L_\infty^h$, $f_\infty^h$, $z(\infty,h)$ are interpreted as the limits of the variables $L_m^h$, $f_m^h$, $z(m,h)$ as $m\to\infty$. The case $M=\infty$ corresponds to iteration methods for solving equation \ref{3}.

If the operators $L_z$ in equation \ref{1} are uniformly bounded in $z$, one says that algorithm \ref{2} admits a regular closure. Although the set of algorithms with regular closure does not coincide with the set of actually stable algorithms, construction of a closed algorithm frequently helps in investigating the stability of an algorithm under various perturbations (in particular computational errors) (see [3], [4]).

The concept of a closed algorithm was introduced in [1]. There the closure of an algorithm for successive elimination of unknowns, when solving finite-difference equations that approximate an equation \ref{4} with $Lu=u-Au$, where $A$ is a Fredholm integral operator, was obtained and investigated.

The construction of the closure of an algorithm and the inverse operation — the construction of a discrete algorithm the closure of which is a given continuous process — proves useful in designing new methods for the solution of problems. In particular, a large number of iteration methods admit closures which are steady processes. For example, the simple iteration method for the solution of the Laplace difference equation corresponds to the steady process $u_t=\Delta u$; and the two-step iteration method corresponds to the steady process $u_{tt}+\alpha u_t=\Delta u$, $\alpha>0$ (see [5]).

References

[1]	S.L. Sobolev, "Some remarks on the numerical solution of integral equations" Izv. Akad. Nauk SSSR Ser. Mat. , 20 : 4 (1956) pp. 413–436 (In Russian)
[2]	I. [I. Babushka] Babuška, M. Práger, E. Vitásek, "Closure of computational processes and the double-sweep method" Zh. Vychisl. Mat. i Mat. Fiz. , 4 : 2 (1964) pp. 351–353 (In Russian)
[3]	N.S. Bakhalov, "Computational methods for the solution of ordinary differential equations" , Kiev (1970) (In Russian)
[4]	N.S. Bakhvalov, "Numerical methods: analysis, algebra, ordinary differential equations" , MIR (1977) (Translated from Russian)
[5]	V.K. Saul'ev, "Integration of equations of parabolic type by the method of nets" , Pergamon (1964) (Translated from Russian)
[6]	A.F. Shapkin, "Closure of two computational algorithms, based on the idea of orthogonalization" Zh. Vychisl. Mat. i Mat. Fiz. , 7 : 2 (1967) pp. 411–416 (In Russian)

References

[a1]	I. [I. Babushka] Babuška, M. Práger, E. Vitásek, "Numerical processes in differential equations" , Wiley (1966)