The impact of eigenvalue locality on the convergence behavior of the PSD method for two-cyclic matrices (Q1014459)

The authors analyze the convergence of the preconditioned simultaneous displacement (PSD) method applied to linear systems of the form \(Au=b\), where \(A\) is a two-cyclic matrix. Convergence conditions and optimum values of the parameters of the method are determined in the cases where the eigenvalues of the associated Jacobi iteration matrix are either all real or all imaginary. It is shown that the convergence behavior of the PSD method is greatly affected by the locality of the eigenvalues of the associated Jacobi iteration matrix. It is shown that when these eigenvalues are real, the PSD method degenerates into the extrapolated Gauss-Seidel method, and when they are imaginary its convergence is increased by an order of magnitude and becomes equivalent to the extrapolated successive overrelaxation (SOR) method. A comparison with the symmetric (SSOR) method is also provided and it reveals that the PSD method possesses a better convergence behavior in all cases.