On the convergence rate of SOR: A worst case estimate

LetA be any real symmetric positive definiten×n matrix, and κ(A) its spectral condition number. It is shown that the optimal convergence rate $$\rho _{SOR}^* = \mathop {\min }\limits_{0< \omega< 2} \rho (M_{SOR,\omega } )$$ of the successive overrelaxation (SOR) method satisfies $$\rho _{SOR}^* \leqslant 1 - \frac{1}{{\alpha _n \kappa (A)}}, \alpha _n \approx \log n.$$ This worst case estimate is asymptotically sharp asn→∞. The corresponding examples are given by certain Toeplitz matrices.