Namespaces
Variants
Actions

Difference between revisions of "Closure of a computational algorithm"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (label)
 
(One intermediate revision by one other user not shown)
Line 2: Line 2:
 
A system of equations
 
A system of equations
  
$$L_zu=f_z,\quad0\leq z\leq Z,\tag{1}$$
+
$$L_zu=f_z,\quad0\leq z\leq Z,\label{1}\tag{1}$$
  
 
obtained as the limit as $h\to0$, $z(m,h)\to z$ of a system of partially solved equations
 
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}$$
+
$$L_m^hu^h=f_m^h,\quad m=0,\dots,M,\label{2}\tag{2}$$
  
 
describing the successive steps of a computational algorithm for the solution of an equation
 
describing the successive steps of a computational algorithm for the solution of an equation
  
$$L^hu^h=f^h\tag{3}$$
+
$$L^hu^h=f^h\label{3}\tag{3}$$
  
 
(for example, a finite-difference equation, in which case $h$ is the grid spacing), which approximates the equation
 
(for example, a finite-difference equation, in which case $h$ is the grid spacing), which approximates the equation
  
$$Lu=f\tag{4}$$
+
$$Lu=f\label{4}\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}.
+
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 \eqref{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 \eqref{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 [[#References|[3]]], [[#References|[4]]]).
+
If the operators $L_z$ in equation \eqref{1} are uniformly bounded in $z$, one says that algorithm \eqref{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 [[#References|[3]]], [[#References|[4]]]).
  
The concept of a closed algorithm was introduced in [[#References|[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 concept of a closed algorithm was introduced in [[#References|[1]]]. There the closure of an algorithm for successive elimination of unknowns, when solving finite-difference equations that approximate an equation \eqref{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 [[#References|[5]]]).
 
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 [[#References|[5]]]).
  
 
====References====
 
====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  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)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  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)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  N.S. Bakhalov,  "Computational methods for the solution of ordinary differential equations" , Kiev  (1970)  (In Russian)</TD></TR><TR><TD valign="top">[4]</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">[5]</TD> <TD valign="top">  V.K. Saul'ev,  "Integration of equations of parabolic type by the method of nets" , Pergamon  (1964)  (Translated from Russian)</TD></TR><TR><TD valign="top">[6]</TD> <TD valign="top">  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)</TD></TR></table>
+
<table>
 
+
<TR><TD valign="top">[1]</TD> <TD valign="top">  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).  Zbl 0074.11004.</TD></TR>
 
+
<TR><TD valign="top">[2]</TD> <TD valign="top">  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)</TD></TR>
 +
<TR><TD valign="top">[3]</TD> <TD valign="top">  N.S. Bakhalov,  "Computational methods for the solution of ordinary differential equations" , Kiev  (1970)  (In Russian)</TD></TR>
 +
<TR><TD valign="top">[4]</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">[5]</TD> <TD valign="top">  V.K. Saul'ev,  "Integration of equations of parabolic type by the method of nets" , Pergamon  (1964)  (Translated from Russian)</TD></TR>
 +
<TR><TD valign="top">[6]</TD> <TD valign="top">  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)</TD></TR>
 +
</table>
  
 
====Comments====
 
====Comments====

Latest revision as of 17:23, 14 February 2020

A system of equations

$$L_zu=f_z,\quad0\leq z\leq Z,\label{1}\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,\label{2}\tag{2}$$

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

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

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

$$Lu=f\label{4}\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 \eqref{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 \eqref{3}.

If the operators $L_z$ in equation \eqref{1} are uniformly bounded in $z$, one says that algorithm \eqref{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 \eqref{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). Zbl 0074.11004.
[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)

Comments

References

[a1] I. [I. Babushka] Babuška, M. Práger, E. Vitásek, "Numerical processes in differential equations" , Wiley (1966). Zbl 0156.16003
How to Cite This Entry:
Closure of a computational algorithm. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Closure_of_a_computational_algorithm&oldid=33550
This article was adapted from an original article by A.F. Shapkin (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article