Assignment 2 - 2010 - Solution/Question 1

<rst> <rst-options: 'toc' = False/> <rst-options: 'reset-figures' = False/>

Question 1 [1]

====

The Gauss elimination method is an effective algorithm for solving a set of linear equations, :math:`Ax = b`. Solve this set of equations by hand, showing the steps taken.

.. math::

\left\{\begin{array}{r} x_1 + x_2 + x_3 + x_4 = 0\hphantom{-}\\ x_1 - 2x_2 - 2x_3 - 2x_4 = 4\hphantom{-}\\ x_1 + 4x_2 - 4x_3 + x_4 = 2\hphantom{-}\\ x_1 - 5x_2 - 5x_3 - 3x_4 = -4\\ \end{array}\right.\\

Solution

---

We start by converting the system of equations to the form :math:`Ax = b`.

.. math::

\begin{array}{ccccccccc} x_{1} & + & x_{2} & + & x_{3} & + & x_{4} & = & 0\hphantom{-}\\ x_{1} & - & 2x_{2} & - & 2x_{3} & - & 2x_{4} & = & 4\hphantom{-}\\ x_{1} & + & 4x_{2} & - & 4x_{3} & + & x_{4} & = & 2\hphantom{-}\\ x_{1} & - & 5x_{2} & - & 5x_{3} & - & 3x_{4} & = & -4\\ \end{array} \;\; \Longrightarrow \;\; \left[\begin{array}{cccc} 1 & 1 & 1 & 1\\ 1 & -2 & -2 & -2\\ 1 & 4 & -4 & 1\\ 1 & -5 & -5 & -3\\ \end{array} \right] \left[\begin{array}{c} x_{1}\\ x_{2}\\ x_{3}\\ x_{4}\\ \end{array} \right] = \left[\begin{array}{c} 0\\ 4\\ 2\\ -4\\ \end{array} \right]

• • Forward elimination**

Recall that the basic algorithm for the forward elimination step of naive Gauss elimination is:

1. . Divide the current row :math:`i` by the :math:`i\text{th}` diagonal element.
2. . Eliminate all elements in the :math:`i\text{th}` column below the :math:`i\text{th}` diagonal element (i.e. rows :math:`j` > :math:`i`) by subtracting :math:`n` times the :math:`i\text{th}` row from the :math:`j\text{th}` row (where :math:`n` is the current value of value in the :math:`i\text{th}` column of the :math:`j\text{th}` row, i.e. element ( :math:`i` , :math:`j` )). Do not forget to subtract the :math:`b` vector elements as well.
3. . Move to the next row.
4. . Repeat steps 1 - 3 until the A matrix is upper triangular (i.e. you have eliminated all elements below the diagonal).

Therefore our first step is to divide row 1 by the it's diagonal element (in this case the first value), which is equal to 1 (easy enough)

.. math::

\left[\begin{array}{rrrr} \frac{1}{(1)} & \frac{1}{(1)} & \frac{1}{(1)} & \frac{1}{(1)}\\ 1 & -2 & -2 & -2\\ 1 & 4 & -4 & 1\\ 1 & -5 & -5 & -3\\ \end{array} \right] \left[\begin{array}{r} x_{1}\\ x_{2}\\ x_{3}\\ x_{4}\\ \end{array} \right] = \left[\begin{array}{r} \frac{0}{(1)}\\ 4\\ 2\\ -4\\ \end{array} \right] \;\; \Longrightarrow \;\; \left[\begin{array}{rrrr} 1 & 1 & 1 & 1\\ 1 & -2 & -2 & -2\\ 1 & 4 & -4 & 1\\ 1 & -5 & -5 & -3\\ \end{array} \right] \left[\begin{array}{r} x_{1}\\ x_{2}\\ x_{3}\\ x_{4}\\ \end{array} \right] = \left[\begin{array}{r} 0\\ 4\\ 2\\ -4\\ \end{array} \right]

Next we subtract row 1 from rows 2, 3, and 4 using :math:`n` values equal to the coefficients in the first column of each row. In thise case the all the column coefficients are equal to 1, which makes our lives easy again.

.. math::

\left[\begin{array}{rrrr} 1 & 1 & 1 & 1\\ 1 - (1)(1) & -2 - (1)(1) & -2 - (1)(1) & -2 - (1)(1)\\ 1 - (1)(1) & 4 - (1)(1) & -4 - (1)(1) & 1 - (1)(1)\\ 1 - (1)(1) & -5 - (1)(1) & -5 - (1)(1) & -3 - (1)(1)\\ \end{array} \right] \left[\begin{array}{r} x_{1}\\ x_{2}\\ x_{3}\\ x_{4}\\ \end{array} \right] = \left[\begin{array}{r} 0\\ 4 - (1)(0)\\ 2 - (1)(0)\\ -4 - (1)(0)\\ \end{array} \right] \;\; \Longrightarrow \;\; \left[\begin{array}{rrrr} 1 & 1 & 1 & 1\\ 0 & -3 & -3 & -3\\ 0 & 3 & -5 & 0\\ 0 & -6 & -6 & -4\\ \end{array} \right] \left[\begin{array}{r} x_{1}\\ x_{2}\\ x_{3}\\ x_{4}\\ \end{array} \right] = \left[\begin{array}{r} 0\\ 4\\ 2\\ -4\\ \end{array} \right]

Having eliminated all elements in the first column, we move to the second row/column. Once again we start by dividing the current row (row 2) by its diagonal element.

.. math::

\left[\begin{array}{rrrr} 1 & 1 & 1 & 1\\ 0 & \frac{-3}{(-3)} & \frac{-3}{(-3)} & \frac{-3}{(-3)}\\ 0 & 3 & -5 & 0\\ 0 & -6 & -6 & -4\\ \end{array} \right] \left[\begin{array}{r} x_{1}\\ x_{2}\\ x_{3}\\ x_{4}\\ \end{array} \right] = \left[\begin{array}{r} 0\\ \frac{4}{(-3)}\\ 2\\ -4\\ \end{array} \right] \;\; \Longrightarrow \;\; \left[\begin{array}{rrrr} 1 & 1 & 1 & 1\\ 0 & 1 & 1 & 1\\ 0 & 3 & -5 & 0\\ 0 & -6 & -6 & -4\\ \end{array} \right] \left[\begin{array}{r} x_{1}\\ x_{2}\\ x_{3}\\ x_{4}\\ \end{array} \right] = \left[\begin{array}{r} 0\\ -4/3\\ 2\\ -4\\ \end{array} \right]

Next we eliminate all elements below row 2 in column 2 by subtracting 3 times row 2 from row 3 and (-6) times row 2 from row 4.

.. math::

\left[\begin{array}{rrrr} 1 & 1 & 1 & 1\\ 0 & 1 & 1 & 1\\ 0 & 3 - (3)(1) & -5 - (3)(1) & 0 - (3)(1)\\ 0 & -6 - (-6)(1) & -6 - (-6)(1) & -4 - (-6)(1)\\ \end{array} \right] \left[\begin{array}{r} x_{1}\\ x_{2}\\ x_{3}\\ x_{4}\\ \end{array} \right] = \left[\begin{array}{r} 0\\ -4/3\\ 2 - (3)(-4/3)\\ -4 - (-6)(-4/3)\\ \end{array} \right] \;\; \Longrightarrow \;\; \left[\begin{array}{rrrr} 1 & 1 & 1 & 1\\ 0 & 1 & 1 & 1\\ 0 & 0 & -8 & -3\\ 0 & 0 & 0 & 2\\ \end{array} \right] \left[\begin{array}{r} x_{1}\\ x_{2}\\ x_{3}\\ x_{4}\\ \end{array} \right] = \left[\begin{array}{r} 0\\ -4/3\\ 6\\ -12\\ \end{array} \right]

Moving to row 3 we notice that the previous elimination step removed all values below the 3rd column diagonal. Therefore all we do is divide row 3 by its diagonal element and move on.

.. math::

\left[\begin{array}{rrrr} 1 & 1 & 1 & 1\\ 0 & 1 & 1 & 1\\ 0 & 0 & \frac{-8}{(-8)} & \frac{-3}{(-8)}\\ 0 & 0 & 0 & 2\\ \end{array} \right] \left[\begin{array}{r} x_{1}\\ x_{2}\\ x_{3}\\ x_{4}\\ \end{array} \right] = \left[\begin{array}{r} 0\\ -4/3\\ \frac{6}{(-8)}\\ -12\\ \end{array} \right] \;\; \Longrightarrow \;\; \left[\begin{array}{rrrr} 1 & 1 & 1 & 1\\ 0 & 1 & 1 & 1\\ 0 & 0 & 1 & 3/8\\ 0 & 0 & 0 & 2\\ \end{array} \right] \left[\begin{array}{r} x_{1}\\ x_{2}\\ x_{3}\\ x_{4}\\ \end{array} \right] = \left[\begin{array}{r} 0\\ -4/3\\ -3/4\\ -12\\ \end{array} \right]

Similarly, since row 4 is the final row of our matrix, there exist no elements under the diagonal to eliminate so we simply divide through by the row diagonal element and then move on to perform backwards substitution.

.. math::

\left[\begin{array}{rrrr} 1 & 1 & 1 & 1\\ 0 & 1 & 1 & 1\\ 0 & 0 & 1 & 3/8\\ 0 & 0 & 0 & \frac{2}{(2)}\\ \end{array} \right] \left[\begin{array}{r} x_{1}\\ x_{2}\\ x_{3}\\ x_{4}\\ \end{array} \right] = \left[\begin{array}{r} 0\\ -4/3\\ -3/4\\ \frac{-12}{(2)}\\ \end{array} \right] \;\; \Longrightarrow \;\; \left[\begin{array}{rrrr} 1 & 1 & 1 & 1\\ 0 & 1 & 1 & 1\\ 0 & 0 & 1 & 3/8\\ 0 & 0 & 0 & 1\\ \end{array} \right] \left[\begin{array}{r} x_{1}\\ x_{2}\\ x_{3}\\ x_{4}\\ \end{array} \right] = \left[\begin{array}{r} 0\\ -4/3\\ -3/4\\ -6\\ \end{array} \right]

• • Backward substitution**

Recall that the basic algorithm for the backwards substitution step of naive Gauss elimination is:

1. . Eliminate all elements in the :math:`i\text{th}` column above the :math:`i\text{th}` diagonal element (i.e. rows :math:`j` < :math:`i`) by subtracting :math:`n` times the :math:`i\text{th}` row from the :math:`j\text{th}` row (where :math:`n` is the current value of value in the :math:`i\text{th}` column of the :math:`j\text{th}` row, i.e. element ( :math:`i` , :math:`j` )). Do not forget to subtract the :math:`b` vector elements as well.
2. . Move to the next row.
3. . Repeat steps 1 - 2 until the A matrix becomes the identity matrix (i.e. you have eliminated all elements above the diagonal).

Therefore we start by subtracting 1 times row 4 from row 1, 1 times row 4 from row 2, and (3/8) times row 4 from row 3.

.. math::

\left[\begin{array}{rrrr} 1 & 1 & 1 & 1 - (1)(1)\\ 0 & 1 & 1 & 1 - (1)(1)\\ 0 & 0 & 1 & 3/8 - (3/8)(1)\\ 0 & 0 & 0 & 1\\ \end{array} \right] \left[\begin{array}{r} x_{1}\\ x_{2}\\ x_{3}\\ x_{4}\\ \end{array} \right] = \left[\begin{array}{r} 0 - (1)(-6)\\ -4/3 - (1)(-6)\\ -3/4 - (3/8)(-6)\\ -6\\ \end{array} \right] \;\; \Longrightarrow \;\; \left[\begin{array}{rrrr} 1 & 1 & 1 & 0\\ 0 & 1 & 1 & 0\\ 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 1\\ \end{array} \right] \left[\begin{array}{r} x_{1}\\ x_{2}\\ x_{3}\\ x_{4}\\ \end{array} \right] = \left[\begin{array}{r} 6\\ 14/3\\ 3/2\\ -6\\ \end{array} \right]

Moving to next row, in order to eliminate all elements above the 3rd diagonal element we subtract 1 times row 3 from row 1 and 1 times row 3 from row 2.

.. math::

\left[\begin{array}{rrrr} 1 & 1 & 1 - (1)(1) & 0\\ 0 & 1 & 1 - (1)(1) & 0\\ 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 1\\ \end{array} \right] \left[\begin{array}{r} x_{1}\\ x_{2}\\ x_{3}\\ x_{4}\\ \end{array} \right] = \left[\begin{array}{r} 6 - (1)(3/2)\\ 14/3 - (1)(3/2)\\ 3/2\\ -6\\ \end{array} \right] \;\; \Longrightarrow \;\; \left[\begin{array}{rrrr} 1 & 1 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 1\\ \end{array} \right] \left[\begin{array}{r} x_{1}\\ x_{2}\\ x_{3}\\ x_{4}\\ \end{array} \right] = \left[\begin{array}{r} 9/2\\ 19/6\\ 3/2\\ -6\\ \end{array} \right]

Finally, we move to row 2 and eliminate all elements above the 2nd diagonal element by subtracting 1 times row 2 from row 1.

.. math::

\left[\begin{array}{rrrr} 1 & 1 - (1)(1) & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 1\\ \end{array} \right] \left[\begin{array}{r} x_{1}\\ x_{2}\\ x_{3}\\ x_{4}\\ \end{array} \right] = \left[\begin{array}{r} 9/2 - (1)(19/6)\\ 19/6\\ 3/2\\ -6\\ \end{array} \right] \;\; \Longrightarrow \;\; \left[\begin{array}{rrrr} 1 & 1 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 1\\ \end{array} \right] \left[\begin{array}{r} x_{1}\\ x_{2}\\ x_{3}\\ x_{4}\\ \end{array} \right] = \left[\begin{array}{r} 4/3\\ 19/6\\ 3/2\\ -6\\ \end{array} \right]

Therefore the solution, arrived at using naive Gauss elimination, is:

.. math::

\left[\begin{array}{r} x_{1}\\ x_{2}\\ x_{3}\\ x_{4}\\ \end{array} \right] = \left[\begin{array}{r} 4/3\\ 19/6\\ 3/2\\ -6\\ \end{array} \right] </rst>