Abstract Generated abstract
The paper addresses the slow convergence of successive approximation methods for solving linear systems of the form x = Bx + b when the norm of B is close to one or high accuracy is required. It derives a transformation of the finite matrix geometric sum appearing after n iterations, factoring it into products involving powers B, B squared, B fourth, and so on, so that repeated squaring yields the effect of 2^(s-1) ordinary iterations in s accelerated steps. The same recurrence is presented as a practical way to compute the corresponding approximants and to determine the inverse matrix (E - B)^(-1). The method is also noted to extend to functional equations when the required operator powers and sums can be computed effectively.
Full Text
MATHEMATICS
A. B. NAISHUL
IMPROVING THE CONVERGENCE OF METHODS OF SUCCESSIVE APPROXIMATIONS FOR LINEAR EQUATIONS
(Presented by Academician A. Yu. Ishlinskii, December 30, 1963)
The number of approximations required in solving a system of linear equations
\[ \bar{x}=B\bar{x}+\bar{b} \tag{1} \]
by the method of successive approximations
\[ \bar{x}_{n+1}=B\bar{x}_{n}+\bar{b} \tag{2} \]
may be large if the norm of the matrix \(B\) is close to 1, the initial approximation \(\bar{x}_0\) is far from the solution, and the result must be obtained with high accuracy. Below a method is proposed for improving convergence, in which \(s\) approximations are equivalent to \(n=2^{s-1}\) ordinary approximations.
Solving equation (1) by successive approximations, we obtain:
\[ \begin{aligned} \bar{x}_1&=B\bar{x}_0+\bar{b},\\ \bar{x}_2&=B^2\bar{x}_0+(E+B)\bar{b},\\ &\ldots\\ \bar{x}_n&=B^n\bar{x}_0+(E+B+B^2+\ldots+B^{n-1})\bar{b}. \end{aligned} \tag{3} \]
Transform the expression
\[ \begin{aligned} U_n&=E+B+B^2+\ldots+B^{n-1},\\ U_n&=(E+B)+B^2(E+B)+B^4(E+B)+\ldots+B^{n-2}(E+B)=\\ &=(E+B^2+B^4+\ldots+B^{n-2})(E+B)=\\ &=((E+B^2)+B^4(E+B^2)+\ldots+B^{n-4}(E+B^2))(E+B)=\\ &=(E+B^4+B^8+\ldots+B^{n-4})(E+B^2)(E+B). \end{aligned} \tag{4} \]
Continuing the process, we obtain
\[ U_n=(E+B^{2^{s-2}})(E+B^{2^{s-3}})\ldots(E+B^2)(E+B). \tag{5} \]
Of course, in this case
\[ n=2^{s-1}. \tag{6} \]
Using relations (3), we obtain
\[ \bar{x}_{2^{s-1}} = B^{2^{(s-1)}}\bar{x}_0 + (E+B^{2^{s-2}})(E+B^{2^{s-3}})\ldots(E+B^4)(E+B^2)(E+B)\bar{b} = \]
\[ = B^{2^{s-1}}\bar{x}_0+U_{2^{s-1}}\bar{b}. \tag{7} \]
The sequence of matrices \(U_{2^s-1}\) is easily computed, since
\[ U_{2^s-1}=\left(E+B^{2^{s-2}}\right)U_{2^{s-2}},\qquad U_1=E; \tag{8} \]
\[ B^{2^s-1}=\left(B^{2^{s-2}}\right)^2. \tag{9} \]
The same method gives a way of determining the inverse matrix
\[ G=(E-B)^{-1}, \]
\[ G_{2^s-1}=B^{2^s-1}G_0+U_{2^s-1}. \]
It should be noted that the method can also be applied to functional equations, provided it is possible to construct an effective process for computing the operators \(B^{2^s-1}\) and \(U_{2^s-1}\).
Received
14 X 1963