Numerical analysis Iterative methods for linear systems Theorem

Symmetric successive over-relaxation

Builds on System of linear equations Positive definite matrix Spectral radius Successive over-relaxation Iterative method Preconditioner

Statement

Let $A$ be a real symmetric $n \times n$ matrix with positive diagonal entries, and let $b \in \R^n$ . Write $A = D + L + L^T$ , with $D$ diagonal and $L$ strictly lower triangular, and let $0 < \omega < 2$ . One step of symmetric successive over-relaxation (SSOR) is a forward SOR sweep in the order $1, \dots, n$ . It is followed by a backward SOR sweep in the order $n, \dots, 1$ . In matrix form it is $x^{(k+1)} = x^{(k)} + M_\omega^{-1} \left( b - A x^{(k)} \right)$ , where $M_\omega = \frac{1}{\omega (2 - \omega)} \, (D + \omega L) \, D^{-1} \, (D + \omega L^T).$ Then $M_\omega$ is symmetric and positive definite. If moreover $A$ is positive definite, then the iteration matrix $I - M_\omega^{-1} A$ has spectral radius less than $1$ . So for every $b$ and every $x^{(0)}$ the iterates converge to $A^{-1} b$ .

Remarks

The matrix $M_\omega$ is symmetric by its form, and it is positive definite because $D$ is and $D + \omega L$ is invertible. When $A$ is positive definite, each of the two SOR sweeps strictly decreases the energy norm $\norm{e}_A$ of the error, so their product contracts too. Example: for $n = 1$ and $A = (a)$ with $a > 0$ , one has $M_\omega = a / (\omega (2 - \omega))$ . The iteration matrix is $1 - \omega (2 - \omega) = (1 - \omega)^2$ , which lies in $[0, 1)$ exactly when $0 < \omega < 2$ . As a stand-alone method, SSOR is usually no faster than SOR. Its value is that $M_\omega$ is a symmetric positive definite preconditioner, so it can be combined with the conjugate gradient method, unlike plain SOR.

Going deeper

For a student

The formula for $M_\omega$ shows that applying SSOR costs one forward and one backward triangular solve with the sparsity of $A$ . For $\omega = 1$ the method is symmetric Gauss–Seidel, with $M_1 = (D + L) D^{-1} (D + L^T)$ . SSOR belongs to the family of stationary iterative methods given by a splitting $A = M_\omega - (M_\omega - A)$ .

Tag	`Y1G3NNJSQH`
URI	`m2://Y1G3NNJSQH`
Kind	statement, theorem
Writing	W0 stub
MSC	65F10, 65F08
Status	This copy of the site has no build data. Run `m2 status Y1G3NNJSQH`.
About	Successive over-relaxation, Preconditioner
Uses	System of linear equations, Positive definite matrix, Spectral radius, Successive over-relaxation, Iterative method, Preconditioner
Same as	Wikidata Q16937163 Wikipedia Symmetric successive over-relaxation

Markdown · JSON · Edit on GitHub

What this page needs for W1

an inventory row: the row of the inventory that the node accounts for (0 of 1)
a source with a locator (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.