Exact SOR convergence regions for a general class of \(p\)-cyclic matrices (Q1907868)

To solve the system \(Ax= b\) by successive overrelaxation (SOR), the iteration is \(x^{m+ 1}= {\mathcal L} x^m+ c\) with \({\mathcal L}= (I- \omega L)^{- 1}[(1- \omega)I+ \omega U]\), \(c= \omega(I- \omega L)^{- 1} D^{- 1} b\), with \(\omega\) the relaxation parameter. Here \(A\) is a \(p\times p\) block matrix and \(A= L+ D+ U\) is the usual decomposition in lower, diagonal and upper block parts. It is assumed that the Jacobi matrix \(B= I- D^{- 1} A\) is weakly cyclic, i.e., that it is generated from a block diagonal matrix by a cyclic permutation which can not be split in subcycles. Convergence of the SOR method depends on the spectrum \(\sigma({\mathcal L})\) of \(\mathcal L\) being inside or outside a disk centered at the origin. Since there is a relation between the spectra \(\sigma(B)\) and \(\sigma({\mathcal L})\), there is a largest region in the complex plane containing \(\sigma(B)\) for which the method converges. This region is described in this paper. Also an answer is given to the question for what pairs \((\rho(B),\omega)\) (\(\rho(B)\) is the spectral radius of \(B\)) the method does converge. To describe these regions, extensive use is made of hypocycloid curves in the complex plane. The usefulness of these curves follows naturally from the relation between \(\sigma(B)\) and \(\sigma({\mathcal L})\). Especially the case \(p= 5\) is studied in more detail and explicit formulas are given. The paper generalizes many exemplary results that were previously obtained by several authors.