Optimal semi-iterative methods for complex SOR with results from potential theory

Abstract

We consider the application of semi-iterative methods (SIM) to the standard (SOR) method with complex relaxation parameter ω, under the following two assumptions: (1) the associated Jacobi matrix J is consistently ordered and weakly cyclic of index 2, and (2) the spectrum σ(J) of J belongs to a compact subset ∑ of the complex plane ℂ, which is symmetric with respect to the origin. By using results from potential theory, we determine the region of optimal choice of ω ∈ ℂ for the combination SIM-SOR and settle, for a large class of compact sets ∑, the classical problem of characterising completely all the cases for which the use of the SIM-SOR is advantageous over the sole use of SOR, under the hypothesis that σ (J) ⊂ Σ. In particular, our results show that, unless the outer boundary of ∑ is an ellipse, SIM-SOR is always better and, furthermore, one of the best possible choices is an asymptotically optimal SIM applied to the Gauss-Seidel method. In addition, we derive the optimal complex SOR parameters for all ellipses which are symmetric with respect to the origin. Our work was motivated by recent results of M.Eiermann and R.S. Varga.