Assignment 2 - 2010 - Solution/Question 5

From Process Model Formulation and Solution: 3E4
Jump to navigation Jump to search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.
← Question 4 (previous step) Back to all questions Next step: Bonus question →

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

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