On the convergence rate of SOR: A worst case estimate (Q1332342)

Let \(A\) be any real symmetric positive definite \(n \times n\) matrix, and \(\kappa (A)\) its spectral condition number. It is shown that the optimal convergence rate \(\rho^*_{\text{SOR}} = \min_{0 < \omega < 2} \rho (M_{\text{SOR}, \omega})\) of the succesive overrelaxation (SOR) method satisfies \(\rho^*_{\text{SOR}} \leq 1 - 1/(\alpha_ n \kappa (A))\), \(\alpha_ n \approx \log n\). The worst case estimate is asymptotically sharp as \(n \to \infty\). The corresponding examples are given by certain Toeplitz matrices.