# Difference between revisions of "Assignment 2 - 2010 - Solution/Question 5"

 ← Question 4 (previous step) Back to all questions Next step: Bonus question →

# Question 5 [2]

Note

From a previous exam, 5 marks out of 50, 3 hours. This question should be solved by hand, and is a typical question you can expect in the midterm and final.

For the following system of linear algebraic equations:

$\begin{split}-5x_1 + 0x_2 + 12x_3 =&\ 80 \\ 4x_1 -x_2 - x_3 =&\ -2 \\ 6x_1 + 8x_2 +0x_3 =&\ 45\end{split}$
1. Use the Jacobi method to compute $$x^{(1)}$$ starting from $$x^{(0)} = \bf 0$$.
2. Use the Gauss-Seidel method to compute $$x^{(1)}$$ starting from $$x^{(0)} = \bf 0$$.
3. Use the Gauss-Seidel method with relaxation, $$\omega=0.9$$, to compute $$x^{(1)}$$ starting from $$x^{(0)} = \bf 0$$.

## Solution

We start this problem by converting the system to the form $$Ax = b$$.

$\begin{split}\left[\begin{array}{rrr} -5 & 0 & 12\\ 4 & -1 & -1\\ 6 & 8 & 0\\ \end{array}\right] \left[\begin{array}{r} x_{1}\\ x_{2}\\ x_{3}\\ \end{array}\right] = \left[\begin{array}{r} 80\\ -2\\ 45\\ \end{array}\right]\end{split}$

Next we rearrange the system so that it is diagonally dominant (i.e. $$|a_{ii}| \geq \sum^{n}_{j=1,j \neq i} |a_{ij}|$$ where ever possible). To achieve this we rearrange the equation order to equation 2, equation 3, equation 1.

$\begin{split}\left[\begin{array}{rrr} 4 & -1 & -1\\ 6 & 8 & 0\\ -5 & 0 & 12\\ \end{array}\right] \left[\begin{array}{r} x_{1}\\ x_{2}\\ x_{3}\\ \end{array}\right] = \left[\begin{array}{r} -2\\ 45\\ 80\\ \end{array}\right]\end{split}$

Now we are ready to attack this problem.

1. The Jacobi method uses the following update algorithm:

$x_{i}^{(k+1)} = \frac{1}{a_{ii}} \left[ b_{i} - \sum^{n}_{j=1,j \neq i} a_{ij}x_{j}^{(k)} \right]$

Using a starting value of $$x^{(0)} = [0,0,0]$$ we calculate the next iterate using the above equation.

$\begin{split}\begin{array}{rcl} x_{1}^{(1)} & = & \frac{1}{a_{11}} \left[ b_{1} - \left( a_{12}x_{2}^{(0)} + a_{13}x_{3}^{(0)} \right) \right]\\ x_{1}^{(1)} & = & \frac{1}{(4)} \left[ (-2) - \left( (-1)(0) + (-1)(0) \right) \right]\\ x_{1}^{(1)} & = & -0.5\\ \end{array}\end{split}$
$\begin{split}\begin{array}{rcl} x_{2}^{(1)} & = & \frac{1}{a_{22}}\left[b_{2} - \left(a_{21}x_{1}^{(0)}+a_{23}x_{3}^{(0)}\right)\right]\\ x_{2}^{(1)} & = & \frac{1}{(8)}\left[(45) - \left((6)(0)+(0)(0)\right)\right]\\ x_{2}^{(1)} & = & 5.625\\ \end{array}\end{split}$
$\begin{split}\begin{array}{rcl} x_{3}^{(1)} & = & \frac{1}{a_{33}}\left[b_{3} - \left(a_{31}x_{1}^{(0)}+a_{32}x_{2}^{(0)}\right)\right]\\ x_{3}^{(1)} & = & \frac{1}{(12)}\left[(80) - \left((-5)(0)+(0)(0)\right)\right]\\ x_{3}^{(1)} & = & 6.6667\\ \end{array}\end{split}$

Therefore $$x^{(1)} = [-0.5,5.625,6.6667]$$

2. The Gauss-Seidel method uses the following update algorithm:

$x_{i}^{(k+1)} = \frac{1}{a_{ii}}\left[b_{i} - \sum^{i-1}_{j=1}a_{ij}x_{j}^{(k+1)} - \sum^{n}_{j=i+1}a_{ij}x_{j}^{(k)}\right]$

Using a starting value of $$x^{(0)} = [0,0,0]$$ we calculate the next iterate using the above equation.

$\begin{split}\begin{array}{rcl} x_{1}^{(1)} & = & \frac{1}{a_{11}}\left[b_{1} - \left(a_{12}x_{2}^{(0)}+a_{13}x_{3}^{(0)}\right)\right]\\ x_{1}^{(1)} & = & \frac{1}{(4)}\left[(-2) - \left((-1)(0)+(-1)(0)\right)\right]\\ x_{1}^{(1)} & = & -0.5\\ \end{array}\end{split}$
$\begin{split}\begin{array}{rcl} x_{2}^{(1)} & = & \frac{1}{a_{22}}\left[b_{2} - \left(a_{21}x_{1}^{(1)}+a_{23}x_{3}^{(0)}\right)\right]\\ x_{2}^{(1)} & = & \frac{1}{(8)}\left[(45) - \left((6)(-0.5)+(0)(0)\right)\right]\\ x_{2}^{(1)} & = & 6\\ \end{array}\end{split}$
$\begin{split}\begin{array}{rcl} x_{3}^{(1)} & = & \frac{1}{a_{33}}\left[b_{3} - \left(a_{31}x_{1}^{(1)}+a_{32}x_{2}^{(1)}\right)\right]\\ x_{3}^{(1)} & = & \frac{1}{(12)}\left[(80) - \left((-5)(-0.5)+(0)(6)\right)\right]\\ x_{3}^{(1)} & = & 6.4583\\ \end{array}\end{split}$

Therefore $$x^{(1)} = [-0.5,6,6.4583]$$

3. The Gauss-Seidel method with relaxation uses the following update algorithm:

$x_{i}^{(k+1)} = (1-\omega)x_{i}^{(k)} + \frac{\omega}{a_{ii}}\left[b_{i} - \sum^{i-1}_{j=1}a_{ij}x_{j}^{(k+1)} - \sum^{n}_{j=i+1}a_{ij}x_{j}^{(k)}\right]$

Using a starting value of $$x^{(0)} = [0,0,0]$$ we calculate the next iterate using the above equation.

$\begin{split}\begin{array}{rcl} x_{1}^{(1)} & = & (1-\omega)x_{1}^{(0)} + \frac{\omega}{a_{11}}\left[b_{1} - \left(a_{12}x_{2}^{(0)}+a_{13}x_{3}^{(0)}\right)\right]\\ x_{1}^{(1)} & = & (1-(0.9))(0) + \frac{(0.9)}{(4)}\left[(-2) - \left((-1)(0)+(-1)(0)\right)\right]\\ x_{1}^{(1)} & = & -0.45\\ \end{array}\end{split}$
$\begin{split}\begin{array}{rcl} x_{2}^{(1)} & = & (1-\omega)x_{2}^{(0)} + \frac{\omega}{a_{22}}\left[b_{2} - \left(a_{21}x_{1}^{(1)}+a_{23}x_{3}^{(0)}\right)\right]\\ x_{2}^{(1)} & = & (1-(0.9))(0) + \frac{(0.9)}{(8)}\left[(45) - \left((6)(-0.45)+(0)(0)\right)\right]\\ x_{2}^{(1)} & = & 5.36625\\ \end{array}\end{split}$
$\begin{split}\begin{array}{rcl} x_{3}^{(1)} & = & (1-\omega)x_{3}^{(0)} + \frac{\omega}{a_{33}}\left[b_{3} - \left(a_{31}x_{1}^{(1)}+a_{32}x_{2}^{(1)}\right)\right]\\ x_{3}^{(1)} & = & (1-(0.9))(0) + \frac{(0.9)}{(12)}\left[(80) - \left((-5)(-0.45)+(0)(5.36625)\right)\right]\\ x_{3}^{(1)} & = & 5.83125\\ \end{array}\end{split}$

Therefore $$x^{(1)} = [-0.45,5.36625,5.83125]$$

 ← Question 4 (previous step) Back to all questions Next step: Bonus question →