MATHEMATICS

P. S. BONDARENKO

COMPUTATIONAL ALGORITHMS FOR THE APPROXIMATE SOLUTION OF OPERATOR EQUATIONS

(Presented by Academician A. A. Dorodnitsyn, 29 X 1962)

Let abstract spaces \(M_1, M_2\) and an operator \(A\), which maps elements of \(M_1\) into elements of \(M_2\), be given. It is required, for a given element \(y \in M_2\), to find an element \(x \in M_1\) such that the equality

\[ Ax = y. \tag{1} \]

is satisfied.

Suppose that the spaces \(M_1, M_2\) and the operator \(A\) are replaced by some other spaces \(\overline{M}_1, \overline{M}_2\) and by an operator \(\overline{A}\), which maps elements of \(\overline{M}_1\) into elements of \(\overline{M}_2\), and suppose that instead of the original problem the following problem is solved: for an element \(\overline{y} \in \overline{M}_2\), it is required to find an element \(\overline{x} \in \overline{M}_1\) such that the equality

\[ \overline{A}\overline{x} = \overline{y}. \tag{2} \]

is satisfied.

Denote by \(N(\overline{A})\) the aggregate of computational operations that make it possible, from the known element \(\overline{y} \in \overline{M}_2\), to construct such an element \(\overline{x} \in \overline{M}_1\) that equality (2) is satisfied. If the existence of an operator \(\overline{A}^{-1}\), inverse with respect to \(\overline{A}\), is assumed, the symbol \(N(\overline{A})\) denotes the method of its actual construction:

\[ N(\overline{A})\overline{y} = \overline{x}. \tag{3} \]

Let, further, in the course of carrying out the method \(N(\overline{A})\), by means of computing devices computations be performed with \(s + r\) \((r \geq 0)\) digits after the decimal point, and let the result of computing the element \(\overline{x}\) be rounded to the \(s\)-th digit after the decimal point. We shall denote the element \(\overline{x}\) thus computed by \(\overline{x}^{*}\). The aggregate of computational operations performed in the course of such an implementation of the method \(N(\overline{A})\) will be denoted by \(N^{*}(\overline{A})\).

The process consisting of methods of approximating the spaces \(M_1, M_2\) by the spaces \(\overline{M}_1, \overline{M}_2\), the operator \(A\) by the operator \(\overline{A}\), of replacing equation (1) by equation (2), together with the method \(N(\overline{A})\) of solving the latter equation, will be called a computational algorithm for solving equation (1) and denoted by \(A_N(\overline{x})\). A computational algorithm \(A_N(\overline{x})\) in which the method \(N(\overline{A})\) is replaced by the method \(N^{*}(\overline{A})\) will be called a real computational algorithm for solving equation (1) and denoted by \(A_{N^{*}}(\overline{x}^{*})\).

In the present note the basic properties of computational and real computational algorithms for the solution of one sufficiently broad class of linear operator equations are considered.

1. Let \(M_1, M_2\) be linear spaces with norms \(\|\ \|_{M_1}, \|\ \|_{M_2}\). Let, further, \(A\) and \(\overline{A}_n\) \((n = 1, 2, \ldots)\) be linear operators mapping elements of \(M_1\) into elements of \(M_2\), and let equation (1)

\[ Ax = y \tag{4} \]

be replaced by the equation

\[ \overline{A}_n x_n = y, \qquad x_n \in \overline{X}_n \subset M_1. \tag{5} \]

Let the approximation be characterized by the relation

\[ \lim_{n\to\infty}\|Ax-\bar A_nx\|_{M_2}=0 \tag{6} \]

or by the relation

\[ \|Ax-\bar A_nx\|_{M_2}\leq Mn^{-k}, \tag{7} \]

where \(M>0\) is a constant independent of \(n\), valid for any \(x\) from \(M_1\).

Suppose that in the space \(M_1\) there is singled out an everywhere dense subspace \(\bar X_n\), appearing in (5), so that the solution \(\bar x_n\) of equation (4) corresponding to a given value of the parameter \(n\) belongs to \(\bar X_n\): \(x_n\in\bar X_n\). Then the convergence of the solution \(\bar x_n\) of equation (5) to the solution \(x_n\) of equation (4) is determined by the relation

\[ \lim_{n\to\infty}\|x_n-\bar x_n\|_{\bar X_n}=0. \tag{8} \]

Definition 1. Suppose that equation (4) has a unique solution \(x\in M_1\) for a given \(y\in M_2\). If the operators \(\bar A_n\) are constructed so that equation (5) has a solution \(\bar x_n\) for every \(n\), \(1\leq n<\infty\), and arbitrary \(y\in M_2\), depending continuously on \(y\), with this continuous dependence uniform in \(n\), and if this solution, as \(n\to\infty\), converges to the solution \(x_n\) of equation (4), then the computational algorithm \(A_N(\bar x_n)\) is called regularly convergent. If the operators \(\bar A_n\) are constructed so that equation (5) has a unique solution \(\bar x_n\) for all \(n\) and \(y\in M_2\), depending continuously on \(y\), but this continuous dependence is not uniform in \(n\), then, provided \(\bar x_n\) converges to \(x_n\), the computational algorithm \(A_N(\bar x_n)\) is called convergent. An element \(\bar x_n\) found by a regularly convergent (convergent) computational algorithm is called a regular approximate (approximate) solution of equation (4). An element \(\bar x_n^*\) found by the real computational algorithm \(A_{N^*}(\bar x_n^*)\) is called a real approximate solution of equation (4).

Definition 2. The real computational algorithm \(A_{N^*}(\bar x_n^*)\) for solving equation (4) is called stable if there exists an integer \(r_n^*(s)\geq 0\) such that the inequality

\[ a_n(s,r)=\|\bar x_n-\bar x_n^*\|\leq \frac12\,\omega\beta^{-s}, \tag{9} \]

where \(\beta>0\) is the base of the number system, \(\frac12\leq\omega\leq 1\), is satisfied for any independently fixed \(n\) and \(s\), \(0\leq s<\infty\), \(1\leq n<\infty\), and for all \(r\), \(r_n^*(s)\leq r<\infty\), in the process of computation by the algorithm \(A_{N^*}(\bar x_n^*)\) with \(r+s\) digits after the decimal point. The integer \(r_n^*(s)\) is called the characteristic of the stability region of the algorithm \(A_{N^*}(\bar x_n^*)\).

Remark. For the computational algorithm \(A_N(\bar x_n)\), for any fixed \(n\) and \(s\), the characteristic of its stability region is \(r_n^*(s)=\infty\) by definition.

Let \(x_n\) be the solution of equation (4), and let \(\bar x_n^*\) be a real approximate solution of this equation. We call the difference \(x_n-\bar x_n^*\) the true error of the real approximate solution \(\bar x_n^*\). If the computational algorithm \(A_N(\bar x_n)\) is convergent (regularly convergent) and the number \(s\) is given: \(s=s^*\), then there exists a natural number \(n_0\) such that for all \(n\geq n_0\) the inequality

\[ \|x_n-\bar x_n^*\|\leq \frac12\,\omega\beta^{-s^*}. \tag{10} \]

If the real computational algorithm \(A_{N^*}(\bar x_n^*)\) is stable, then there exists an integer \(r_{n_0}^*(s^*)\) such that the inequality

\[ \left\|\bar x_{n_0}-\bar x_{n_0}^{\,*}\right\| \leqslant \frac{1}{2}\omega \beta^{-s^*}. \tag{11} \]

holds.

From (10) and (11), obviously, the inequality follows

\[ \left\|x_{n_0}-\bar x_{n_0}^{\,*}\right\| \leqslant \omega \beta^{-s^*}. \tag{12} \]

Definition 3. Let the means of computation by the algorithm \(A_{N^*}(\bar x_n^*)\) be known. If, for the given \(s=s^*\), computations with \(s^*+r_{n_0}^*(s^*)\) digits after the decimal point are feasible with the aid of these means, then we call the computational algorithm \(A_{N^*}(\bar x_n^*)\) really stable.

2. The following theorems contain criteria for regularly convergent, convergent computational algorithms, as well as criteria for stable real computational algorithms.

Theorem 1. Suppose:

1) equation (4) has a unique solution from \(M_1\) for the given \(y\) from \(M_2\);

2) equation (5) approximates equation (4) on elements \(x\) from \(M_1\);

3) the operators \(\bar A_n\) \((n=1,2,\ldots)\) have inverses, bounded in the aggregate:

\[ \left\|\bar A_n^{-1}y\right\|_{\bar X} \leqslant K\|y\|_{M_2}; \]

4) the operator \(\bar A_n\) is such that for any \(\bar x_n\) from its domain the inequality is fulfilled

\[ \left\|\bar A_n \bar x_n\right\|_{\bar X_n} \leqslant Cn^m\left\|\bar x_n\right\|_{\bar X_n}, \]

where \(C>0\) is a constant independent of \(n\) and \(\bar x_n\), and \(m\geqslant 0\) is an integer;

5) the method \(N^*(\bar A_n)\) is characterized by the relation

\[ \alpha_n(s,r)=\left\|N(\bar A_n)y-N^*(\bar A_n)y\right\|_{\bar X_n} =\left\|\bar x_n-\bar x_n^{\,*}\right\|_{\bar X_n}\to 0 \]

as \(s+r\to\infty\) and for any independently fixed \(s\) and \(n\).

Then the computational algorithm \(A_N(\bar x_n)\) is regularly convergent, and the real computational algorithm \(A_{N^*}(\bar x_n^*)\) is stable.

Theorem 2. Suppose:

1) equation (5) approximates equation (4), and the order of this approximation is \(k>0\);

2) the operators \(\bar A_n\) \((n=1,2,\ldots)\) have inverses satisfying the condition

\[ \left\|\bar A_n^{-1}y\right\|_{\bar X_n} \leqslant Pn^l\|y\|_{M_2}, \]

and the number \(l>0\) satisfies the condition \(k-l>0\);

3) conditions 1), 4) (with \(m=0\)) and 5) of Theorem 1 are fulfilled.

Then the computational algorithm \(A_N(\bar x_n)\) is convergent, and the real computational algorithm \(A_{N^*}(\bar x_n^*)\) is stable.

If the computational means are known, then, on the basis of Theorems 1 and 2, one can single out from the real computational algorithms \(A_{N^*}(\bar x_n^*)\) the really stable computational algorithms for solving the considered class of operator equations.

Kyiv State University
named after T. G. Shevchenko

Received
25 X 1962