1. INTRODUCTION

Let \({\mathbb E}\) denote a Euclidean space of dimension \(\dim {\mathbb E}\) with inner product \(\left (\mathrm{u},\mathrm{v}\right )\) of vectors \(\mathrm{u},\mathrm{v}\in {\mathbb E}\); \(\left\| \mathrm{u}\right\| =\sqrt{\left ( \mathrm{u},\mathrm{u}\right ) }\) is the length of a vector \(\mathrm{u}\).

Let \({\mathbb V}\) be a subspace of \({\mathbb E}\), \(\dim {\mathbb V}< \dim {\mathbb E}\); and let \({\mathbb V}^{\bot }\) be its orthogonal complement to \({\mathbb E}\), that is, the annihilator [2] of the set \({\mathbb V}\). Then \({\mathbb E}\) is a direct sum \({\mathbb V}\oplus {\mathbb V}^{\bot }\) and for any vector \(\mathrm{u}\in {\mathbb E}\) there exists a unique representation

$$\mathrm{u}=\mathrm{u}_{\mathbb V} +\mathrm{u}_{\mathbb V}^{\bot } :\; \; \mathrm{u}_{\mathbb V} \in {\mathbb V},\; \mathrm{u}_{\mathbb V}^{\bot } \in {\mathbb V}^{\bot }; \ \ {(1)}$$

\(\mathrm{u}_{\mathbb V}\) is called [2] the orthogonal projection, and \(\mathrm{u}_{\mathbb V}^{\bot}\) is the orthogonal component of the vector \(\mathrm{u}\) with respect to \({\mathbb V}\). Let \({\mathcal P}\) and \({\mathcal P}^{\bot }\) be the orthogonal projectors of the Euclidean space \({\mathbb E}\) onto \({\mathbb V}\) and \({\mathbb V}^{\bot }\), respectively. Then

$$\mathrm{u}_{\mathbb V} = {\mathcal P} \mathrm{u},\; \; \mathrm{u}_{\mathbb V}^{\bot } = {\mathcal P}^{\bot } \mathrm{u}.$$

The problem of determining \({\mathcal P} \mathrm{u}\) for a given vector \(\mathrm{u}\) is one of the key problems of computational linear algebra. In particular, solving a system of linear algebraic equations can be reduced to this problem. An iterative algorithm (in operator form) for constructing an orthogonal projection of a vector onto a subspace and a method based on this algorithm for numerically solving a consistent system of linear algebraic equations will be considered below.

2. CALCULATION OF THE ORTHOGONAL PROJECTION OF A VECTOR ONTO A SUBSPACE

In what follows, any self-adjoint nonnegative definite transformation \({\mathcal A}\) of the subspace \({\mathbb E}\) whose range is \({\mathbb V}^{\bot }\) will be called an annihilating transformation of the subspace \({\mathbb V}\). Thus, \({\mathbb V}\) coincides with the kernel of its annihilator \({\mathcal A}\). Its condition number \({æ}_{\mathcal A}\) will be called the condition number of restriction of the operator \({\mathcal A}\) on \({\mathbb V}^{\bot }\). With no rounding errors, the following theorem is valid:

Theorem 1. For any annihilator \({\mathcal A}\)of a subspace \({\mathbb V}\subset {\mathbb E}\)and any vector \(\mathrm{u}\notin {\mathbb V}\)consider the iterative process \(\mathrm{u}^{0} :=\mathrm{u},\)\(\mathrm{s}^{1} :={\mathcal A}\mathrm{u}^{0}\)for \(n\ge 1\):

$$\mathrm{u}^{n} :=\mathrm{u}^{n-1} - \frac{\left(\mathrm{u}^{n-1},\mathrm{s}^n\right )}{\left ( \mathrm{s}^{n} ,\mathrm{s}^n\right)} \mathrm{s}^{n};\qquad \mathrm{s}^{n+1} :={\mathcal A}\mathrm{u}^{n} - \frac{\left({\mathcal A}\mathrm{u}^n,\mathrm{s}^n\right)}{\left(\mathrm{s}^n,\mathrm{s}^n\right)} \mathrm{s}^{n} . \ \ {(2)}$$

In less than \(\dim{\mathbb V}^{\bot }\)steps, this will lead to a construction of an orthogonal projection \({\mathcal P} \mathrm{u}\)of the vector \(\mathrm{u}\)onto the subspace \({\mathbb V},\)that is, a natural number \(k\le \dim {\mathbb V}^{\bot }\)will be found so that \(\mathrm{u}^{k} = {\mathcal P} \mathrm{u}\).The vectors \(\mathrm{s}^{1} ,\mathrm{s}^{2} ,\ldots ,\mathrm{s}^{n}\)will be mutually orthogonal, and

$$\left\| \mathrm{u}^{n} - {\mathcal P} \mathrm{u}\right\| \le T_{n}^{-1}\! \left(\frac{{æ}_{\mathcal A}+1}{{æ}_{\mathcal A}-1} \right) \left\| \mathrm{u} - {\mathcal P} \mathrm{u} \right\|. \ \ {(3)}$$

Here \(T_{n} (x)\)is a Chebyshev polynomial of the first kind, and \({æ}_{\mathcal A}\)is the condition number of \({\mathcal A}\).

A proof of the first part of this theorem is given in [3], where an algorithm for solving a partial problem of eigenvalues and vectors on the basis of the process (2) is proposed. According to a general theory of conjugate gradient methods (see [1, 4]), at each step of the process (2) \(\left\|{\mathcal P}^{\bot }\mathrm{u}^n \right\|\) is minimized on a corresponding Krylov subspace generated by \({\mathcal A}\). Hence, we have the inequality (3).

The relation (3) means that the construction of an orthogonal projection of a vector onto a subspace \({\mathbb V}\) can be efficiently numerically solved by the process (2) if an annihilator \({\mathcal A}\) with a small condition number \({æ}_{\mathcal A}\) can be constructed for \({\mathbb V}\). If the orthogonal projector \({\mathbb P}_{\mathbb V}^{\bot }\) of the Euclidean space \({\mathbb E}\) onto \({\mathbb V}^{\bot }\) is taken as \({\mathcal A}\), the solution \({\mathcal P} \mathrm{u}\) is obtained in one iteration. An annihilator for \({\mathbb V}\) will be the sum of all orthogonal projectors onto each of vectors with a linear span equal to \(\mathrm{{\mathbb V}}^{\bot }\). The following statement may be useful in constructing the annihilators:

Theorem 2. Let \(\mathrm{{\mathbb V}}^{\bot } ={\mathbb V}_\mathrm{a}^{\bot } \oplus {\mathbb V}_\mathrm{b}^{\bot }\)be the direct sum of subspaces with an angle between them \([5, 6]\)equal to \(\theta;\)\({\mathcal P}_\mathrm{a}^{\bot }\)and \({\mathcal P}_\mathrm{b}^{\bot }\)are the orthogonal projectors of \({\mathbb E}\)onto the subspaces \({\mathbb V}_\mathrm{a}^{\bot }\)and \({\mathbb V}_\mathrm{b}^{\bot }\),respectively. Then for any positive \(\alpha\)and \(\beta\)the operator \({\mathcal A}=\alpha{\mathcal P}_\mathrm{a}^{\bot } +\beta{\mathcal P}_\mathrm{b}^{\bot }\)is an annihilator of \({\mathbb V}\)whose condition number

$${æ}_{\mathcal A} = \frac{\alpha+\beta+\sqrt{(\alpha-\beta)^2+4\alpha\beta\cos^2 \theta}}{\alpha+\beta-\sqrt{(\alpha-\beta)^2+4\alpha\beta\cos^2 \theta}}$$

and satisfies the exact inequality \({æ}_{\mathcal A}\geq \cot^2({\theta}/{2})\), which turns into the equality at \(\alpha=\beta\).

Proof. It is obvious that \({\mathcal A}\) is an annihilating transformation of the space \({\mathbb V}\). Let us calculate the ends of the spectrum of its restriction to \(\mathrm{{\mathbb V}}^{\bot }\). For definiteness, assume that \(\dim{\mathbb V}_\mathrm{a}^{\bot } = k\le \dim{\mathbb V}_\mathrm{b}^{\bot } =l\).

Let \(\mathrm{a}_{1},\ldots,\mathrm{a}_{k}\) and \(\mathrm{b}_{1},\ldots,\mathrm{b}_{l}\) be consistent orthonormal bases from the principal vectors of the subspaces \({\mathbb V}_\mathrm{a}^{\bot }\) and \({\mathbb V}_\mathrm{b}^{\bot }\) (the principal vectors of the pair of spaces) [5], respectively:

$${\left (\mathrm{a}_i,\mathrm{b}_j\right)}=0,\; i\ne j;\quad {\left (\mathrm{a}_i,\mathrm{b}_i\right)}=\sigma_i\ge 0,\; i =1,\ldots,k,\; j=1,\ldots, l.$$

Since the system of vectors \(\mathrm{a}_{1},\ldots,\mathrm{a}_{k}, \mathrm{b}_{1},\ldots,\mathrm{b}_{l}\) forms a basis in the entire \({\mathbb V}^{\bot }\), according to the definition of the angle between the subspaces \({\mathbb V}_\mathrm{a}^{\bot }\) and \({\mathbb V}_\mathrm{b}^{\bot}\)

$$\cos \theta = \sup\limits_{ {\mathrm{a}\in {\mathbb V}_\mathrm{a}^{\bot },\left\| \mathrm{a}\right\|=1;} \atop { \mathrm{b}\in {\mathbb V}_\mathrm{b}^{\bot }, \left\| \mathrm{b}\right\|=1} } \!\!\!{\left (\mathrm{a},\mathrm{b}\right)} = \sup\limits_{ \sum \alpha_i^2=1;\atop \sum \beta_j^2=1 } \sum \sigma_{i}\alpha_i\beta_i = \sigma_1,$$

where \(\sigma_1\) is the largest of the singular numbers: \(\sigma_1\ge\sigma_2\ge\cdots\ge \sigma_k \ge 0\).

It is evident that \(\cos \theta\in [0,1)\), since the equality \(\cos \theta = 1\) means that \({ {\mathbb V}}^{\bot}\) is not the direct sum of the subspaces \({\mathbb V}_\mathrm{a}^{\bot}\) and \({\mathbb V}_\mathrm{b}^{\bot}\).

Let \(\lambda\) be an arbitrary eigenvalue of the transformation \({\mathcal A}=\alpha{\mathcal P}_\mathrm{a}^{\bot } +\beta{\mathcal P}_\mathrm{b}^{\bot }\). Then the coordinates of the corresponding eigenvector \(\alpha_{1},\ldots,\alpha_{k}\), \(\beta_{1},\ldots,\beta_{l}\) in the above basis satisfy the following system of equations:

$$(\lambda -\alpha)\alpha_{i} = \beta\sigma_{i}\beta_{i},\quad (\lambda-\beta)\beta_{i}= \alpha \sigma_{i}\alpha_{i},\ \; i\le k;\quad (\lambda-\beta)\beta_{j} = 0,\ \ k <j \le l.$$

Hence, we have the exact inequality

$$\frac{\alpha+\beta}{2}-\sqrt{\left(\frac{\alpha-\beta}{2} \right)^2+\alpha\beta\cos^2 \theta} \le \lambda \le \frac{\alpha+\beta}{2}+\sqrt{\left(\frac{\alpha-\beta}{2} \right)^2+\alpha\beta\cos^2 \theta }$$

for \(\lambda\) and the condition number \({æ}_{\mathcal A}\).

Eliminating the irrational expression in the denominator \({æ}_{\mathcal A}\), we have

$$\begin{aligned} {æ}_{\mathcal A} &=& \frac{1}{4(1-\cos^2 \theta)} \left[ \sqrt{\frac{\alpha}{\beta}}+\sqrt{\frac{\beta}{\alpha}} + \sqrt{ \left(\sqrt{\frac{\alpha}{\beta}}-\sqrt{\frac{\beta}{\alpha}}\right)^2 +4\cos^2 \theta }\;\right]^2 \\ &\ge &\frac{1}{4(1-\cos^2 \theta)} \left[ \sqrt{\frac{\alpha}{\beta}}+\sqrt{\frac{\beta}{\alpha}} + 2\cos \theta\;\right]^2\ge \frac{1}{4(1-\cos^2 \theta)} \left( 2 + 2\cos \theta\;\right)^2 \\ &=& \frac{1+\cos\theta}{1-\cos\theta} = \cot^2\frac{\theta}{2}.\end{aligned}$$

Here all equalities are valid at \(\alpha=\beta\). The theorem is proved.  \(\Box\)

Since \(\cot^2({\theta}/{2})\) is the minimum value of the function \({æ}_{\mathcal A}(\alpha,\beta)\) at \(\alpha\), \(\beta >0\), it follows from Theorem 1 that for constructing an annihilator it is reasonable to consider only the case \(\alpha = \beta=1\). This particular case was investigated by a slightly different method in paper [5], in which it was proved that all eigenvalues of the transformation \({\mathcal P}_\mathrm{a}^{\bot } + {\mathcal P}_\mathrm{b}^{\bot }\) belong to the interval \(\left[1-\cos \theta, 1+\cos \theta \right]\).

Since real calculations always contain rounding errors, it is important to construct a termination criterion (see [1, 7]) for the iterative process (2), that is, determine the number of process steps after which the accuracy of approximation of the solution \({\mathcal P} \mathrm{u}\) by \(\mathrm{u}^{n}\) on a given computer cannot be considerably increased.

Let \(\mathrm{s}^{n}\) be the direction calculated at the \(n\)th iteration of (2) to which the vector \(\mathrm{u}^{n}\) must be orthogonal. Then

$$\left\| \mathrm{u}^n \right\|^2 =\left\| \mathrm{u}^{n-1} \right\| ^{2} - \frac{\left(\mathrm{u}^{n-1} ,\mathrm{s}^n\right)^{2}} {\left\| \mathrm{s}^n \right\|^2} .$$

That is, the norm \(\left\| \mathrm{u}^{n} \right\|\) can be calculated in two different ways, both recurrently and directly: \(\left\| \mathrm{u}^{n} \right\| = \sqrt{\left ( \mathrm{u}^{n} ,\mathrm{u}^{n} \right )}\). The difference between these values can characterize the error accumulated in the calculation process. These considerations lead to the following termination criterion of the algorithm (2):

set \(\eta _{0} :=\| \mathrm{u}^{0} \|\), \(\delta_0 :=0 ;\)for \(n\ge 1\)for \(\| {\mathcal A}\mathrm{u}^n\|>0\)calculate

$$\eta_{n}:=\sqrt{\eta_{n-1}^{2} -\frac{\left(\mathrm{u}^{n-1} ,\mathrm{s}^n\right)^{2}}{\left\| \mathrm{s}^n \right\|^2}} ,\quad \delta_{n}:=\max\{\delta_{n-1},\;|\|\mathrm{u}^{n}\| -\eta_{n}|\};\quad \rho_{n} := \frac{\left ( {\mathcal A}\mathrm{u}^n , \mathrm{u}^{n} \right ) }{\left\| {\mathcal A}\mathrm{u}^n \right\|}; \ \ {(4)}$$

terminate the process \((2)\)if \(\| {\mathcal A}\mathrm{u}^n\|= 0\)or the following inequality is valid:

$$\rho _{n} \le \delta_{n}. \ \ {(5)}$$

Here \(\rho _{n}\) is the numerical projection of the vector \(\mathrm{u}^{n}\) onto the direction \({\mathcal A}\mathrm{u}^{n}\). The Cauchy and Kantorovich inequalities [8] provide the following limitation:

$$\frac{2\sqrt{æ}_{\mathcal A}}{1+{æ}_{\mathcal A}} \big\|{\mathcal P}^{\bot }\mathrm{u}^n \big\| \le \rho _{n} \le \big\|{\mathcal P}^{\bot }\mathrm{u}^n \big\|. \ \ {(6)}$$

The projectors are very simple linear transformations of vector spaces, and the direct methods of computational linear algebra based on orthogonalization are most stable with respect to rounding errors. Therefore, it is natural to construct iterative methods using the process (2) for solving basic problems of computational linear algebra. One of such problems is solving systems of linear algebraic equations.

3. THE ALGORITHM FOR SOLVING SYSTEMS OF LINEAR ALGEBRAIC EQUATIONS

Let \({\mathbb R}^{m}\) denote the Euclidean space of \(m\)-dimensional real vector-columns with the inner product

$$\left (\mathrm{v},\mathrm{u}\right ) = \sum \limits _{1\le i \le m} v_{i} u_{i} ; \quad \mathrm{v}=(v_{1} ,v_{2} ,\ldots ,v_{m} )^\mathrm{T} ,\;\ \mathrm{u}=(u_{1} ,u_{1} ,\ldots ,u_{m} )^\mathrm{T} \in {\mathbb R}^{m}.$$

Here “T” means transposition. In addition to the Euclidean norm \(\left\|\mathrm{v} \right\|\), we will use the \(1\)-norm \(\left\|\mathrm{v} \right\|_1\) and \(\infty\)-norm \(\left\|\mathrm{v} \right\|_\infty\) [1] of vectors from \({\mathbb R}^{m}\):

$$\left\| \mathrm{v} \right\|_1 = \sum\limits_{1\le i\le m}| v_{i}|, \qquad \left\| \mathrm{v} \right\|_\infty = \max\limits_{1\le i\le m}| v_{i}|; \qquad \mathrm{v}\in {\mathbb R}^{m}.$$

Let an inhomogeneous system of real linear algebraic equations

$$A\mathrm{x}=\mathrm{b} ,\quad \mathrm{b} = \left(b_{1} ,\ldots , b_{k} \right)^\mathrm{T} \in {\mathbb R}^{k},\ \ \mathrm{x} = \left(x_{1} ,\ldots ,x_{l} \right)^\mathrm{T} \in {\mathbb R}^{l}, \ \ {(7)}$$

with a rectangular matrix \(A\) of order \(k\times l\) be consistent, \(\mathrm{rang}A = k \le l\). The system (7) allows a geometric interpretation similar to that in the Kaczmarz method (see [9–13]): construct a vector \(\mathrm{y}=\left(y_{0} ,y_{1} ,\ldots ,y_{l}\right)^\mathrm{T} \in {\mathbb R}^{l+1}\)such that \(y_{0} \ne 0\)and

$$\left(\mathrm{a}_{i},\mathrm{y} \right) = 0,\quad \mathrm{a}_{i} = \left(-b_{i} ,a_{i1} ,\ldots ,a_{il} \right)^\mathrm{T} \in {\mathbb R}^{l+1},\;\ i=1,\ldots ,k. \ \ {(8)}$$

Here \(a_{ij}\) is an element of the matrix \(A\). Let the vector \(\mathrm{y}\) satisfy the relations (8). Then the vector \(\mathrm{x} = \left( y_{1} / y_{0} , \ldots ,y_{l} / y_{0} \right)^\mathrm{T}\in {\mathbb R}^{l}\) is a solution to the initial equations (7). If the system (7) is homogeneous, that is, \(\mathrm{b} = \mathrm{0}\), no additional parameter \(y_{0}\) is needed.

To solve the problem (8), the process (2) is used assuming that \({\mathbb E}= {\mathbb R}^{l+1}\) and that its subspace \({\mathbb V}\) coincides with the space of solutions of the homogeneous system (8). Then \({\mathbb V}^{\bot }\) is the linear span of the rows \(\mathrm{a}^\mathrm{T}_{1},\ldots,\mathrm{a}_{k}^\mathrm{T}\) of the extended matrix of the inhomogeneous system (7). The sum of \(k\) orthogonal projectors onto one-dimensional subspaces that are collinear to the basis vectors \({\mathbb V}^{\bot }\) can be taken as an annihilator:

$${\mathcal A} = \sum \limits _{1\le \; i\; \le k} {\mathcal P}^{\bot }_i; \qquad {\mathcal P}^{\bot }_i\mathrm{v} = \frac{\left ( \mathrm{a}_{i},\mathrm{v} \right ) }{\| \mathrm{a}_i \|^2} \cdot\mathrm{a}_{i};\;\ \mathrm{v} \in {\mathbb R}^{l+1}. \ \ {(9)}$$

If the system of linear algebraic equations (8) is represented as the union of two systems of smaller dimension, an annihilator can be constructed on the basis of Theorem 2 assuming that \(\alpha=\beta=1\). An arbitrary nonorthogonal vector \(\mathrm{y}\) can be taken as an initial approximation of the solution \(y\) to the problem (8) for any annihilator \({\mathcal A}\) of the subspace \({\mathbb V}\).

These two approaches have been implemented in numerical experiments that showed that the termination criterion (4), (5) of iterations of (2) is efficient if \(\left\|\mathrm{b}\right\|_1\) is comparable to the maximum \(1\)-norm of the columns of the matrix \(A\) in the system (7). In this case the numerical projection \(\rho _{n}\) correlates well with the \(\infty\)-norm of the vector \({\mathcal P}^{\bot }\mathrm{u}^n\) satisfying the evident inequality, which is similar to (6):

$$\frac{1}{\sqrt{l+1}} \| {\mathcal P}^{\bot }\mathrm{u}^n \| \le\| {\mathcal P}^{\bot }\mathrm{u}^n \|_\infty\le \| {\mathcal P}^{\bot }\mathrm{u}^n \|.$$

It is well known [14] that the accumulation of rounding errors in iterative orthogonalization algorithms in Krylov subspaces violates the mutual orthogonality of the vectors \(\mathrm{s}^n\). In this case the process ceases to be “finite,” but the calculated \(\mathrm{s}^n\) usually remain practically important [15]. The calculations have shown that if the relations (2) are calculated inaccurately, the inclusion \(\mathrm{s}^n\in \mathrm{{\mathbb V}}^{\bot }\) after some step may be violated. However, this can be avoided by regularizing the process (2) as follows:

$$\mathrm{u}^{n} := \mathrm{u}^{n-1} - \frac{\left(\mathrm{u}^{n-1},{\mathcal A}\mathrm{t}^n\right )}{\left\|{\mathcal A}\mathrm{t}^n\right\|^2} {\mathcal A}\mathrm{t}^{n}; \quad \mathrm{t}^{n+1} :=\mathrm{u}^{n} - \frac{\left({\mathcal A}\mathrm{u}^n,{\mathcal A}\mathrm{t}^n\right)}{\left\|{\mathcal A}\mathrm{t}^n\right\|^2}\mathrm{t}^{n}. \ \ {(10)}$$

In this case the total number of operations is almost doubled, since annihilators of the vectors \(\mathrm{u}^n\) and \(\mathrm{t}^n\) are calculated at each step (10). If the calculations are exact, the vector \(\mathrm{s}^n\) in (2) is collinear to the vector \({\mathcal A}\mathrm{t}^n\), and the process is finite. In real calculations, the version (10) of the process (2) guarantees that the vector \(\mathrm{s}^{n}\) belongs to the subspace \({\mathbb V}^{\bot }\) with maximum possible accuracy.

If the subspace \({\mathbb V}^{\bot }\) is generated by a system of generators \(\mathrm{a}_{1},\ldots,\mathrm{a}_{k}\) (as in the problem (8)), an alternative form of the process (10) that is similar to the method of \(AA^*\)-minimum iterations is possible [1]. Let \(A_\mathrm{b}\) denote the extended matrix of the system (8), and let \(A^\mathrm{T}_\mathrm{b}\) be its transpose:

$$\left(A_\mathrm{b}\right)_{ij} = \left(\mathrm{a}_{i}\right)_{j}=\left(A^\mathrm{T}_\mathrm{b}\right)_{ji};\quad i=1,\ldots ,k;\; \ j=1,\ldots ,l+1.$$

Assuming that the initial approximation \(\mathrm{y}^0\) to the solution \(\mathrm{y}\) of the problem (8) is known,

set \(\mathrm{r}^0 = A_\mathrm{b}\mathrm{y}^0,\) \(\mathrm{t}^1 = \mathrm{r}^0;\) and for \(n\ge 1\) calculate

$$\begin{array}{c} \mathrm{s}^{n} := A^\mathrm{T}_\mathrm{b}\mathrm{t}^{n};\quad \mathrm{y}^n := \mathrm{y}^{n-1} - \dfrac{( \mathrm{y}^{n-1} , \mathrm{s}^n)}{\left(\mathrm{s}^{n} ,\mathrm{s}^n\right)}\mathrm{s}^n; \\[1.5ex] \mathrm{r}^n := \mathrm{r}^{n-1} - \dfrac{( \mathrm{y}^{n-1} , \mathrm{s}^n)}{\left(\mathrm{s}^{n} ,\mathrm{s}^n\right)}A_\mathrm{b}\mathrm{s}^n;\qquad \mathrm{t}^{n+1} := \mathrm{r}^{n} - \dfrac{(\mathrm{r}^{n} , A_\mathrm{b}\mathrm{s}^n)}{\left(\mathrm{s}^{n} ,\mathrm{s}^n\right)}\mathrm{t}^n. \end{array} \ \ {(11)}$$

With no rounding errors this process is finite, at each step the equality \(\mathrm{r}^n=A_\mathrm{b}\mathrm{y}^n\) is satisfied, and at \({\mathcal A} = A^\mathrm{T}_\mathrm{b}\cdot A_\mathrm{b}\) the vectors \(\mathrm{s}^{n}\) in (2) and (11) coincide. For a normalized system of generators \(\{\mathrm{a}_{i}:\, \|\mathrm{a}_{i}\|=1\}\) of the subspace \({\mathbb V}^{\bot }\) the multiplication of a vector \(\mathrm{v}\) by the matrix \(A^\mathrm{T}_\mathrm{b} A_\mathrm{b}\) is equivalent to calculating the sum (9) of all one-dimensional orthogonal projectors \({\mathcal P}^{\bot }_i\mathrm{v}\). Owing to the recurrent calculation of the residual \(\mathrm{r}^n\) at each iteration, the numbers of operations in the processes (2) and (11) differ only slightly.

4. THE COMPUTATIONAL EXPERIMENTS

Consider, on a uniform grid, a discrete analog of the first boundary value problem for the following elliptic equation with constant coefficients:

$$\begin{array}{c} -\Delta u\left(x,y\right)+c\cdot u\left(x,y\right) = f\left(x,y\right);\quad x\in \left(0,1\right),\ y\in \left(0,1\right);\; c\ge 0, \\ u(x,0)=u(x,1)\equiv 0,\ x\in \left[0,1\right];\quad u(0,y)=u(1,y)\equiv0,\ y\in \left[0,1\right]. \end{array} \ \ {(12)}$$

Using a finite element \(Q_{1}\)-type Lagrangian approximation (16) of the sought-for function \(u\left(x,y\right)\) with its node values

$$u_{ij} = u\left(M_{ij} \right),\;\ M_{ij}\left(x_i ,y_j \right),\;\ x_i =i/N_x,\; y_j = j/N_y,\; i\in \left\{0,\ldots ,N_{x} \right\},\ j\in \left\{0,\ldots ,N_{y} \right\}, \ \ {(13)}$$

we obtain, for the sought-for quantities \(u_{ij}\), a system of \(m=(N_{x} -1)(N_{y}-1)\) linear algebraic equations (7) \((k = l = m)\) with a positive definite symmetric square matrix \(A\). Systems of linear algebraic equations of this type have been thoroughly studied (see [17]) as basic systems for testing “solvers” of the Krylov type.

figure 1

Fig. 1. \({\mathcal A} = \sum {\mathcal P}^{\bot}_i\).

figure 2

Fig. 2. \({\mathcal A} = {\mathcal P}^{\bot }_a + {\mathcal P}^{\bot }_b\).

figure 3

Fig. 3. \({\mathcal A} = {\mathcal P}^{\bot }_a + {\mathcal P}^{\bot}_b\; \&\) regularization.

figure 4

Fig. 4. Convergence of the various algorithms.

A series of numerical calculations has been performed in the double precision mode [1] with various values of the parameters \(c\) and \(m\). The node values of a randomly chosen smooth function satisfying the homogeneous boundary conditions in (12) are taken as an exact solution \(\mathrm{x}\) of the system (7). To provide graphical representation of the calculation results, the exact solution of the system (7) is normalized by unity in the \(\infty\)-norm, and then the right-hand side \(\mathrm{b}\) is determined. In all numerical experiments, \(\delta_{n}\), \(\rho _{n}\), and \(\|\mathrm{x}^{n} - \mathrm{x}\|_\infty\) as functions of \(n\) vary in a similar way; here \(\mathrm{x}^n\) is an approximation to the solution of Eq. (7): \(x_{i}^n= y_{i}^n/y_{0}^n\), \(i = 1,\ldots, l\). Figures 1–4 show in graphical form the results of calculations for \(N_{x}= N_{y} = 100\), \(c=10\) and a zero initial approximation (\(\mathrm{x}^0 = \mathrm{0}\)).

Figure 1 shows the results for the process (2) with the annihilator (9). The curves in Fig. 2 result from the same algorithm, but with the annihilator based on Theorem 2 at \(\alpha=\beta=1\). The linear span of the rows of the extended matrix of the system (7) (12), (13) associated with the nodes \((x_i, y_j),\) where \(1\le i < N_x\) and \(1\le j\le N_y/2\), is used as the subspace \({\mathbb V}_\mathrm{a}^{\bot }\). The subspace \({\mathbb V}_\mathrm{b}^{\bot }\) supplements \({\mathbb V}_\mathrm{a}^{\bot }\) to the entire \({\mathbb V}^{\bot }\), and the corresponding orthogonal components are calculated by the formulas

$${\mathcal P}_\mathrm{a}^{\bot }\mathrm{u}^n = \mathrm{u}^n - {\mathcal P}_\mathrm{a}\mathrm{u}^n,\qquad {\mathcal P}_\mathrm{b}^{\bot }\mathrm{u}^n = \mathrm{u}^n - {\mathcal P}_\mathrm{b}\mathrm{u}^n.$$

To calculate the projections \({\mathcal P}_\mathrm{a}\mathrm{u}^n\) and \({\mathcal P}_\mathrm{b}\mathrm{u}^n\), the process (2), (9) with the termination criterion (4), (5), which turned out to be well-suited for this class of problems, is used: a value of \(\|\mathrm{x}^{n} -\mathrm{x}\|_\infty\) that is close to the minimum has been typically reached already at the first iteration, when the inequality (5) is satisfied.

Figure 2 shows that the behavior of the \(\infty\)-norm of the error \(\mathrm{x}^{n} -\mathrm{x}\) is not monotone and often implies an “accuracy breakdown” (a breakdown phenomenon [14]) as the number of iterations increases. In this case restarting the process once the condition (5) is satisfied does not give a significant improvement. However, calculating \({\mathcal P}_\mathrm{a}^{\bot }\mathrm{u}^n\) and \({\mathcal P}_\mathrm{b}^{\bot }\mathrm{u}^n\) directly with the algorithms (10) and (11) allows avoiding this phenomenon. The corresponding curves for these processes differ but slightly, and Fig. 3 shows the results only for the process (10).

If the subspace \({\mathbb V}_\mathrm{b}^{\bot }\) is modified by orthogonalizing its generators corresponding to the nodes \(M_{iN_y/2}\), \(1\le i < N_x,\) to the similar vectors of \({\mathbb V}_\mathrm{a}^{\bot }\) associated with the nodes \(M_{ij}\), \(1\le i < N_x\), \(j=N_y/2-2, N_y/2-1,\) the convergence of iterations to the exact solution improves significantly. This version of the algorithm can be considered as one of the domain decomposition methods [18] for solving partial differential equations. The corresponding information is shown in graphical form (2) in Fig. 4. It is a comparison of step-by-step values of \(\left\|\mathrm{x}^{n} -\mathrm{x}\right\|_\infty\) for the above processes: curve (1) is shown also in Fig. 1; curve (3) is shown in Fig. 3. For comparison, the results of the fastest implementation of the conjugate gradient method [7] for numerically solving the system (7), (12), and (13) are shown by curve (4). The regularized processes have a higher convergence rate of iterations \(\mathrm{x}^{n}\) to the exact solution \(\mathrm{x}\) than the best version of the conjugate gradient method.

5. CONCLUSIONS

This paper considered a theoretically justified iterative method for constructing orthogonal projections of a vector onto a given subspace and a procedure for determining the number of steps of the process after which calculations with this accuracy are not reasonable. With these algorithms, a method for numerically solving a consistent system of linear algebraic equations similar to the Kaczmarz method has been constructed. Various software implementations of the method were considered. The method was compared with the classical conjugate gradient method using a specific problem as an example. Numerical experiments in the double-precision mode have shown that the above-constructed algorithms are workable and efficient.