Gauss-Seidel with Relaxation

Definition

This is a method of changing the convergence rate of Gauss-Seidel by including a relaxation parameter $\omega$. In general, you do:

$$x_n^{new}=\omega x_n^{\text{GS}}+(1-\omega )x_n^{\text{old}}$$

or:

$$x_n^{i^{\prime }}=\omega x_n^i+(1-\omega )x_n^{i-1}$$

where $n$ is the variable number and $i$ is the iteration number.

Let’s look at Row 1 for Gauss-Seidel:

$$\begin{array}{rl}{x}_1^0& =1.0(\text{Initial guess})\\ x_1^1& =\frac{1}{a_{11}}[b_1-a_{12}{x}_2^0-a_{13}{x}_3^0]\end{array}$$

Adding the relaxation parameter ($\omega$) to weight the previous and current values of $x_1$:

$$x_1^{1^{\prime }}=\omega x_1^1+(1-\omega )x_1^0$$

So the previous row equations can also be written as:

$$\begin{array}{rl}\text{Row \#1:}& x_1^{\text{new}}=\frac{\omega }{a_{11}}[b_1-a_{12}{x}_2-a_{13}{x}_3]+(1-\omega )x_1\\ \text{Row \#2:}& x_2^{\text{new}}=\frac{\omega }{a_{22}}[b_2-a_{21}{x}_1-a_{23}{x}_3]+(1-\omega )x_2\\ \text{Row \#2:}& x_3^{\text{new}}=\frac{\omega }{a_{33}}[b_3-a_{31}{x}_2-a_{32}{x}_2]+(1-\omega )x_3\end{array}$$

Parameter Settings

There are some cases for parameter settings:

• $\omega =1.0$ - This is Gauss-Seidel, no relaxation
• $\omega <1.0$ - Under-relaxation, slows convergence and controls divergence
• $\omega >1.0$ - Over-relaxation, speeds convergence
  • Can become divergent when $\omega >2$ or close to $2$

The idea is that the new value is found by moving in the direction of $x$. The relaxation parameter controls the step that you take toward this.

Example with different parameter settings: