Improving an estimate of the convergence rate of the Seidel method by selecting the optimal order of equations in the system of linear algebraic equations (Q2357114)

The paper deals with improving the convergence rate of the Seidel method for solving the algebraic linear system \(x=Bx+f\) using a one-step cyclic (iterative) method. The paper starts with a heuristic observation from one book, published already in 1963, that states an optimality of the convergence rate estimate if the permuted matrix \(PBP\) of \(B\) leads to ascending order of \(\sum_{j=1}^n|b_{ij}|\) so that the first equation is the one for which this sum is minimal. It is shown by simple examples that this claim is wrong. The author presents a simple extension of the presented idea resulting into an iterative scheme with an optimal result. Using series of lemmas, it is shown that the new estimate is minimal between all possible estimates. This result is proved by inductive steps. The author further presents the computational complexity and computational experiments that confirm the theoretical results.