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

From Process Model Formulation and Solution: 3E4
Jump to navigation Jump to search
m (Created page with "{{Navigation|Book=Assignment 2 - 2010 - Solution|previous=|current=Back to all questions|next=Question 2}} <rst> <rst-options: 'toc' = False/> <rst-options: 'reset-figures' = Fa...")
 
m
 
Line 12: Line 12:
.. math::
.. math::


\left\{\begin{array}{r}
\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.\\
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
Solution
Line 26: Line 21:
.. math::
.. math::


\begin{array}{ccccccccc}
\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]
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**
**Forward elimination**
Line 62: Line 36:
.. math::
.. math::


\left[\begin{array}{rrrr}
\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]
\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.
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.
Line 99: Line 42:
.. math::
.. math::


\left[\begin{array}{rrrr}
\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]
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.
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.
Line 136: Line 48:
.. math::
.. math::


\left[\begin{array}{rrrr}
\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]
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.
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.
Line 173: Line 54:
.. math::
.. math::


\left[\begin{array}{rrrr}
\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]
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.
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.
Line 210: Line 60:
.. math::
.. math::


\left[\begin{array}{rrrr}
\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]
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.
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.
Line 247: Line 66:
.. math::
.. math::


\left[\begin{array}{rrrr}
\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]
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**
**Backward substitution**
Line 292: Line 80:
.. math::
.. math::


\left[\begin{array}{rrrr}
\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]
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.
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.
Line 329: Line 86:
.. math::
.. math::


\left[\begin{array}{rrrr}
\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]
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.
Finally, we move to row 2 and eliminate all elements above the 2nd diagonal element by subtracting 1 times row 2 from row 1.
Line 366: Line 92:
.. math::
.. math::


\left[\begin{array}{rrrr}
\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]
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:
Therefore the solution, arrived at using naive Gauss elimination, is:
Line 403: Line 98:
.. math::
.. math::


\left[\begin{array}{r}
\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]
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>
</rst>
{{Navigation|Book=Assignment 2 - 2010 - Solution|previous=|current=Back to all questions|next=Question 2}}
{{Navigation|Book=Assignment 2 - 2010 - Solution|previous=|current=Back to all questions|next=Question 2}}

Latest revision as of 08:17, 16 September 2018

Back to all questions Next step: Question 2 →

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

Back to all questions Next step: Question 2 →