Gaussian-Seidel Iteration

Abigail Huettig

47 Gaussian-Seidel Iteration

Recall that in Part VI: Chapter 27, we discussed how to solve a system of linear equations by using Gaussian elimination. In this section, we will discuss the Gaussian-Seidel Iteration process which is another method we can use to solve systems of linear equations.

When working with only a few equations, Gaussian elimination is preferred between the two methods. But when working with many equations, the Gaussian-Seidel iteration method may actually be the better method [9].

With this method, it is necessary that we arrange the equations in the proper order [9]. Consider the following matrix representation of a system of linear equations.

$\begin{bmatrix} a_{11}x_1 & a_{12}x_2 & \cdots & a_{1n}x_n & c_1 \\ a_{21}x_1 & a_{22}x_2 & \cdots & a_{2n}x_n & c_2 \\ \vdots & \vdots & & \vdots &\vdots \\ a_{n1}x_1 & a_{n2}x_2 & \cdots & a_{nn}x_n & c_n \\ \end{bmatrix}$

Looking at all of the coefficents for $x_1$ ( $a_{11}, a_{21},\cdots, a_{n1}$ ), we want to find the coefficient with the largest magnitude (farthest from zero). The equation that contains the coefficient of $x_1$ that has the largest magnitude is then moved to row 1. Looking at all of the coefficents for $x_2$ ( $a_{12}, a_{22},\cdots, a_{n2}$ ), we want the coefficient with the largest magnitude. The equation that contains the coefficient of $x_2$ that has the largest magnitude is then moved to row 2. This process is continued for each independent variable.

It is important to realize that this method will not work for every system of linear equations. Sometimes, each iteration will actually lead us farther away from the solution (diverge) rather than lead us closer (converge). This is why it is a good idea to perform the Diagonal Dominance test before beginning the iterations. Supposing that our matrix above has been properly ordered, consider the following inequalities.

$\begin{align*} |a_{11}|&\geq |a_{12}+a_{13}...+a_{1n}|\\ |a_{22}|&\geq |a_{21}+a_{23}+...+a_{2n}|\\ &\vdots\\ |a_{nn}|&\geq |a_{n1}+a_{n2}+...+a_{n,n-1}+|\\ \end{align*}$

If at least $n-1$ of these inequalities are true and at least one of these inequalities can be strictly greater than and still true, then we are guaranteed that the Gaussian-Seidel iteration method will converge to the solution [9]. However, it is not the case that failing to pass this test guarantees divergence. It is possible to fail the test and still converge [9].

After rearranging our equations, we must pick some initial values, one for each independent variable, to start the iterations. However, unlike the Newton-Raphson or Secant rule methods, our choices for the initial values will not make a difference in whether we get closer to the solution with each iteration or not [9].

After reordering equations, performing the Diagonal Dominance test, and choosing initial values, we are ready to begin our iterations. Consider this properly-ordered matrix.

$\begin{bmatrix} a_{11}x_1 & a_{12}x_2 & \cdots & a_{1n}x_n & c_1 \\ a_{21}x_1 & a_{22}x_2 & \cdots & a_{2n}x_n & c_2 \\ \vdots & \vdots & & \vdots &\vdots \\ a_{n1}x_1 & a_{n2}x_2 & \cdots & a_{nn}x_n & c_n \\ \end{bmatrix}$

The iteration for finding $x_1$ proceeds as follows.

$x_1=\frac{c_1-a_{12}x_2-a_{13}x_3-\cdots-a_{1n}x_n}{a_{11}}$

Basically, we solve the first of our ordered equations for $x_1$ and substitute in our values for every other variable. To find $x_2$ , we solve the second of our ordered equations for $x_2$ and substitute in our values for every other variable. Once this is done for every variable, our first iteration is complete. We then do this process again for our second iteration and so on.

Let’s work through an example to clarify this process along with the Diagonal Dominance test. This problem is one I completed for this paper and comes from Hiestand [9].

Example 83
Consider the equation set

$\begin{align*} 4x_1+8x_2+2x_3=2\\ 9x_1+5x_2+x_3=6\\ 7x_1+3x_2-10x_3=7\\ \end{align*}$

Show that this satisfies the convergence criteria for the Gaussian-Seidel method of solving equations. Rearrange the equations as needed. Then, assume starting values of $x_1=x_2=x_3=1$ . Then perform three iterations of Gaussian-Seidel.

Solution
We first need to rearrange our equations. The coefficients of $x_1$ are 4, 9, and 7. Because 9 is the furthest from 0, the equation containing $9x_1$ should be the first equation. Of the coefficients of $x_2$ , 8 is the furthest from 0 so the equation containing $8x_2$ should be the second equation. Finally, of the coefficients of $x_3$ , -10 is the furthest from 0 so the equation containing $-10x_3$ should be the third equation. Thus, our ordered system of equations is

$\begin{align*} 9x_1+5x_2+x_3=6\\ 4x_1+8x_2+2x_3=2\\ 7x_1+3x_2-10x_3=7 \end{align*}$

Now that we have reordered our equations, we are ready for the Diagonal Dominance test. We have that

$\begin{align*} 9&>5+1\\ 8&>4+2\\ 10&=7+3 \end{align*}$

Because we have at least two equations where the left side is greater than or equal to the right side and at least one equation where the left side is strictly greater than the right side, this system satisfies the convergence criteria for the Gaussian-Seidel method by the Diagonal Dominance test.

With starting values $x_1=x_2=x_3=1$ , our first iteration for $x_1$ is

$\begin{align*} x_1&=\frac{6-5x_2-x_3}{9}\\ &=\frac{6-5(1)-1}{9}\\ &=0 \end{align*}$

Because $x_1$ is now 0, our first iteration for $x_2$ is

$\begin{align*} x_2&=\frac{2-4x_1-2x_3}{8}\\ &=\frac{2-4(0)-2(1)}{8}\\ &=0 \end{align*}$

Because $x_1=x_2=0$ , our first iteration for $x_3$ is

$\begin{align*} x_3&=\frac{7-7x_1-3x_2}{-10}\\ &=\frac{7-7(0)-3(0)}{-10}\\ &=-0.7 \end{align*}$

Let’s now plug these values into our original equations to see how accurate they are.

$\begin{align*} 9(0)+5(0)-0.7&=-0.7\\ 4(0)+8(0)+2(-0.7)&=-1.4\\ 7(0)+3(0)-10(-0.7)&=7 \end{align*}$

Starting our second iteration, we have $x_1=0$ , $x_2=0$ , and $x_3=-0.7$ .

$\begin{align*} x_1&=\frac{6-5x_2-x_3}{9}\\ &=\frac{6-5(0)+0.7}{9}\\ &=0.7444 \\ \text{}\\ x_2&=\frac{2-4x_1-2x_3}{8}\\ &=\frac{2-4(0.7444)-2(-0.7)}{8}\\ &=0.0528\\ \text{}\\ x_3&=\frac{7-7x_1-3x_2}{-10}\\ &=\frac{7-7(0.7444)-3(0.0528)}{-10}\\ &=-0.1631 \end{align*}$

Plugging in these values to our original equations, we have

$\begin{align*} 9(0.7444)+5(0.0528)-0.1631&=6.8008\\ 4(0.7444)+8(0.0528)+2(-0.1631)&=3.0739\\ 7(0.7444)+3(0.0528)-10(-0.1631)&=7 \end{align*}$

For our third iteration, we have $x_1=0.7444$ , $x_2=0.0528$ , and $x_3=-0.1631$ .

$\begin{align*} x_1&=\frac{6-5x_2-x_3}{9}\\ &=\frac{6-5(0.0528)+0.1631}{9}\\ &=0.6555 \\ \text{}\\ x_2&=\frac{2-4x_1-2x_3}{8}\\ &=\frac{2-4(0.6555)-2(-0.1631)}{8}\\ &=-0.037\\ \text{}\\ x_3&=\frac{7-7x_1-3x_2}{-10}\\ &=\frac{7-7(0.6555)-3(-0.037)}{-10}\\ &=-0.2523 \end{align*}$

Plugging in these values to our original equations, we have

$\begin{align*} 9(0.6555)+5(-0.037)-0.2523&=5.4621\\ 4(0.6555)+8(-0.037)+2(-0.2523)&=1.8216\\ 7(0.6555)+3(-0.037)-10(-0.2523)&=7 \end{align*}$

As we can see, each iteration brings us closer to the solution of this equation, and after three iterations we have

$\begin{align*} x_1&\approx 0.6555\\ x_2&\approx -0.037\\ x_3&\approx -0.2523 \end{align*}$

47 Gaussian-Seidel Iteration

License

Share This Book