On the convergence rate of SOR: A worst case estimate

Abstract

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.

Zusammenfassung

Sei A eine reelle symmetrische positiv definiten×n Matrix mit Spektralkonditionszahl κ. Wir zeigen, daß für die optimale Konvergenzrate

$$\rho _{SOR}^* = \mathop {\min }\limits_{0< \omega< 2} \rho (M_{SOR,\omega } )$$

der Methode der sukzessiven Überrelaxation (SOR) gilt:

$$\rho _{SOR}^* \leqslant 1 - \frac{1}{{\alpha _n \kappa (A)}}, \alpha _n \approx \log n.$$

Diese worst-case-Abschätzung ist asymptotisch scharf fürn→∞. Die entsprechenden Beispiele werden von gewissen Toeplitz-Matrizen geliefert.