Proof of correctness of an algorithm that enhances the estimate of the rate of Seidel method convergence

Abstract

The article discusses the Seidel method for solving a system of linear algebraic equations x = Ax + f. It is a continuation of the previous paper by the author, where an algorithm for obtaining an estimate of the rate of Seidel method convergence was proposed. A more exhaustive proof of correctness of the algorithm is presented. The estimate given by this algorithm is better, than the estimate from the monograph “Computational methods of linear algebra” by Faddeev D.K., Faddeeva V.N. “Computational methods of linear algebra” although one needs an additional iterative process to obtain it. It is shown that this iterative process has at least linear rate of convergence, and its single step needs O(n) operations. The rate of convergence is estimated by the inequality |μ(A_k+1)-μ∗| < C|μ(A_k)-μ∗|, where C = 1- m5/12 , m is the smallest by absolute value element of matrix A, μ∗ is the limit value of the iterative process (the best estimate of the rate of Seidel method convergence), μ(A_k) and μ(A_k+1) are estimates obtained at k-th and (k + 1)-th steps of the iterative process, respectively.