Assignment 2 - 2010 - Solution/Question 5

<rst> <rst-options: 'toc' = False/> <rst-options: 'reset-figures' = False/> 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:

.. math:: -5x_1 + 0x_2 + 12x_3 =&\ 80 \\ 4x_1 -x_2 - x_3 =&\ -2 \\ 6x_1 + 8x_2 +0x_3 =&\ 45

1. . Use the Jacobi method to compute :math:`x^{(1)}` starting from :math:`x^{(0)} = \bf 0`.
2. . Use the Gauss-Seidel method to compute :math:`x^{(1)}` starting from :math:`x^{(0)} = \bf 0`.
3. . Use the Gauss-Seidel method with relaxation, :math:`\omega=0.9`, to compute :math:`x^{(1)}` starting from :math:`x^{(0)} = \bf 0`.

Solution

---

We start this problem by converting the system to the form :math:`Ax = b`.

.. math::

\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]

Next we rearrange the system so that it is diagonally dominant (i.e. :math:`|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.

.. math::

\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]

Now we are ready to attack this problem.

1. .

The Jacobi method uses the following update algorithm:

.. math::

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 :math:`x^{(0)} = [0,0,0]` we calculate the next iterate using the above equation.

.. math::

\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}

.. math::

\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}

.. math::

\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}

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

1. .

The Gauss-Seidel method uses the following update algorithm:

.. math::

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 :math:`x^{(0)} = [0,0,0]` we calculate the next iterate using the above equation.

.. math::

\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}

.. math::

\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}

.. math::

\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}

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

1. .

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

.. math::

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 :math:`x^{(0)} = [0,0,0]` we calculate the next iterate using the above equation.

.. math::

\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}

.. math::

\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}

.. math::

\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}

Therefore :math:`x^{(1)} = [-0.45,5.36625,5.83125]` </rst>