A Proof of the Correctness of an Algorithm Improving the Estimate of the Rate of Convergence of the Seidel Method

Abstract

The Seidel method for solving systems of linear algebraic equations x = Ax + f  is considered in this paper. This study is a continuation of a previous author’s work proposing an algorithm to estimate the rate of convergence of the Seidel method. A more exhaustive proof of the correctness of this algorithm is given here. The estimate obtained by the algorithm is somewhat better than the estimate in the monograph Computational Methods of Linear Algebra by D.K. Faddeev and V.N. Faddeeva; however, a separate iterative process is needed to derive it. It is shown that this iterative process has at least a linear rate of convergence and its single step requires O(n) operations. The rate of convergence can be estimated as \(\left| {\mu ({{A}_{{k + 1}}}) - \mu {\text{*}}} \right|\) < \(C\left| {\mu ({{A}_{k}}) - \mu {\text{*}}} \right|\), where C = 1 – \(\frac{{{{m}^{5}}}}{{12}}\), m is the modulus-least element of the matrix A, μ* is the limit value of the iterative process (the best estimate of the rate of convergence of the Seidel method), and μ(A_k) and μ(A_k + 1) are the estimates obtained at the kth and (k + 1)th steps of the iterative process, respectively.