<?xml version="1.0" encoding="UTF-8"?>
<quiz>
  <question type="stack">
    <name>
      <text>8.3.2.1 General Gauss Elimination + Final exercise on back substitution</text>
    </name>
    <questiontext format="html">
      <text><![CDATA[<h5> The general system of three simultaneous linear equations </h5>

<p>In the previous section we met systems of equations which could be solved by back-substitution alone. In this Section we meet systems which are not so amenable and where preliminary work must be done before back-substitution can be used.</p>
<p>Consider the system <span class="math display">\[\begin{matrix}
    x_1 &amp; + &amp; 3x_2 &amp; + &amp; 5x_3 &amp; = &amp; 14 \\
    2x_1 &amp; - &amp; x_2 &amp; - &amp; 3x_3 &amp; = &amp; 3 \\
    4x_1 &amp; + &amp; 5x_2 &amp; - &amp; x_3 &amp; = &amp; 7 \\
\end{matrix}\]</span> We will use the solution method known as <span><strong>Gauss elimination</strong></span>, which has three stages. In the first stage the equations are written in matrix form. In the second stage the matrix equations are replaced by a system of equations having the same solution but which are in <span><strong>triangular form</strong></span>. In the final stage the new system is solved by <span><strong>back-substitution</strong></span>.</p>

<p><span><strong>Stage 1</strong></span>: Matrix Formulation</p>
<p>The first step is to write the equations in matrix form:</p>

<p><span class="math display">\[\left[\begin{matrix}
    1&amp;3&amp;5\\ 
    2&amp;-1&amp;-3\\
    4&amp;5&amp;-1 \\
\end{matrix}\right]
\left[\begin{matrix}
    x_1\\
    x_2\\
    x_3 \\
\end{matrix}\right] = 
\left[\begin{matrix} 
    14\\
    3\\
    7\\
\end{matrix}\right].\]</span> Then, for conciseness, we combine the matrix of coefficients with the column vector of right-hand sides to produce the <span><strong>augmented matrix</strong></span>:</p>

<p>\[\left[\begin{array}{rrr|r}
    1 &amp; 3 &amp; 5 &amp; 14 \\
    2 &amp; -1 &amp; -3 &amp; 3 \\
    4 &amp; 5 &amp; -1 &amp; 7 \\
\end{array}\right].\]</p>

<p>If the general system of equations is written <span class="math inline">\(A X =B\)</span> then the augmented matrix is written <span class="math inline">\([A|B]\)</span>. Hence the first equation <span class="math display">\[x_1+3x_2+5x_3=14\]</span> is replaced by the first row of the augmented matrix, <span class="math display">\[1 \qquad 3\qquad 5\qquad |\qquad 14\]</span> and so on. Stage 1 has now been completed. We will next triangularise the matrix of coefficients by means of <span><strong>row operations</strong></span>. There are three possible row operations:</p>

<ul>
<li><p>interchange two rows;</p></li>
<li><p>multiply or divide a row by a non-zero constant factor;</p></li>
<li><p>add to, or subtract from, one row a multiple of another row.</p></li>
</ul>
<p>Note that interchanging two rows of the augmented matrix is equivalent to interchanging the two corresponding equations. The shorthand notation we use is introduced by example. To interchange row 1 and row 3 we write <span class="math inline">\(R1\leftrightarrow R3\)</span>. To divide row 2 by 5 we write <span class="math inline">\(R2\div 5\)</span>. To add three times row 1 to row 2, we write <span class="math inline">\(R2+3R1\)</span>. In the Task which follows you will see where these annotations are placed.</p>
<p>Note that these operations neither create nor destroy solutions so that at every step the system of equations has the same solution as the original system.</p>

<p><span><strong>Stage 2</strong></span>: Triangularisation </p>
<p>The second stage proceeds by first eliminating <span class="math inline">\(x_1\)</span> from the second and third equations using row operations.</p>
<p><span class="math display">\[\left[\begin{array}{rrr|r} 
    1 &amp; 3 &amp; 5 &amp; 14 \\
    2 &amp; -1 &amp; -3 &amp; 3 \\
    4 &amp; 5 &amp; -1 &amp; 7 
\end{array}\right]
\begin{array}{c}
    \\ R2-2 \times R1 \\
    R3-4 \times R1 \\
\end{array}
\Rightarrow 
\left[\begin{array}{rrr|r}
    1 &amp; 3 &amp; 5 &amp; 14 \\
    0 &amp; -7 &amp; -13 &amp; -25 \\
    0 &amp; -7 &amp; -21 &amp; -49 \\
\end{array}\right]\]</span></p>
<p>In the above we have subtracted twice row (equation) 1 from row (equation) 2.</p>
<p>In full these operations would be written, respectively, as <span class="math display">\[(2x_1-x_2-3x_3)-2(x_1+3x_2+5x_3)=3-2\times 14 \qquad \text{or} \qquad -7x_2-13x_3=-25\]</span> and <span class="math display">\[(4x_1+5x_2-x_3)-4(x_1+3x_2+5x_3)=7-4\times 14 \qquad \text{or} \qquad -7x_2-21x_3=-49.\]</span></p>
<p>Now since all the elements in rows 2 and 3 are negative we multiply throughout by <span class="math inline">\(-1\), this is not really necessary but it will clean up the matrix a bit</span>: <span class="math display">\[\left[\begin{array}{rrr|r} 
    1 &amp; 3 &amp; 5 &amp; 14 \\
    0 &amp; -7 &amp; -13 &amp; -25 \\
    0 &amp; -7 &amp; -21 &amp; -49 
\end{array}\right]
\begin{array}{c}
    \\ 
    R2\times (-1) \\
    R3\times (-1) \\
\end{array}
\Rightarrow
\left[\begin{array}{rrr|r}
    1 &amp; 3 &amp; 5 &amp; 14 \\
    0 &amp; 7 &amp; 13 &amp; 25 \\
    0 &amp; 7 &amp; 21 &amp; 49 
\end{array}\right]\]</span></p>
<p>Finally, we eliminate <span class="math inline">\(x_2\)</span> from the third equation by subtracting equation 2 from equation 3, i.e., <span class="math inline">\(R3-R2\)</span>: <span class="math display">\[\left[\begin{array}{rrr|r}
    1&amp;3&amp;5&amp;14\\
    0&amp;7&amp;13&amp;25\\
    0&amp;7&amp;21&amp;49 \\
\end{array}\right]
\begin{array}{c}
    \\
    \\
    R3-R2 \\
\end{array}
\Rightarrow
\left[\begin{array}{rrr|r}
    1&amp;3&amp;5&amp;14\\
    0&amp;7&amp;13&amp;25\\
    0&amp;0&amp;8&amp;24 \\
\end{array}\right]\]</span></p>
<p>The system is now in triangular form.</p>
<p><span><strong>Stage 3</strong></span>: Back Substitution</p>
<p>Here we solve the equations from bottom to top. At each step of the back substitution process we encounter equations which only have a <span><strong>single</strong></span> unknown and so can be easily solved.</p>

<hr>

<p class="HELM_exercise">Exercise</p>

<p> Complete the solution to the above system by back-substitution. </p>

<div>\(x=\) [[input:ans1]] [[validation:ans1]]</div><div><br></div>

<p> Check that these values satisfy the original system of equations. </p><p>[[feedback:prt1]]<br></p>

<hr>

<p>You should always check your solution in the original equations to ensure that the equations balance.</p>
<p>Again we emphasise that we chose a particular set of procedures in Stage 1. This was chosen mainly to keep the arithmetic simple by delaying the introduction of fractions. Sometimes we are courageous and take fewer, harder steps.</p>
<p>An important point to note is that when in Stage 2 we wrote <span class="math inline">\(R2-2R1\)</span> against row 2; what we meant is that row 2 is replaced by the combination (row <span class="math inline">\(2)-2\times\)</span>(row 1).</p>

<div class="HELM_keypoint">
<h4>Key Point: Elementary Row Operations</h4>
<p>The operation <span class="math display">\[\text{ row } i-\alpha \times \text{ row }\ j\]</span> means replace <span><strong>row <span class="math inline">\(i\)</span></strong></span> by the combination <span class="math display">\[\text{ row } i-\alpha \times \text{ row } j.\]</span></p>
</div>]]></text>
    </questiontext>
    <generalfeedback format="html">
      <text><![CDATA[<p>In full the equations are <span class="math display">\[\begin{matrix}
    x_1 &amp; + &amp; 3x_2 &amp; + &amp; 5x_3 &amp; = &amp; 14 \\
    &amp; &amp; 7x_2 &amp; + &amp; 13x_3 &amp; = &amp; 25 \\
    &amp; &amp; &amp; &amp; 8x_3 &amp; = &amp; 24 \\
\end{matrix}\]</span> From the last equation we see that <span class="math inline">\(x_3=3\)</span>. Substituting this value into the second equation gives <span class="math display">\[7x_2+39=25 \qquad \text{or} \qquad 7x_2=-14 \qquad \text{so that} \qquad x_2=-2\]</span>    Finally, using these values for <span class="math inline">\(x_2\)</span> and <span class="math inline">\(x_3\)</span> in equation 1 gives <span class="math display">\[x_1-6+15=14.\]</span> Hence <span class="math inline">\(x_1=5\)</span>. The solution
    is therefore <span class="math inline">\([x_1,x_2,x_3]^T=[5,-2,3]^T\)</span>. You can check that these values satisfy the original system of equations.</p>]]></text>
    </generalfeedback>
    <defaultgrade>1</defaultgrade>
    <penalty>0.1</penalty>
    <hidden>0</hidden>
    <idnumber/>
    <stackversion>
      <text>2020120600</text>
    </stackversion>
    <questionvariables>
      <text>ordergreat(x, y, z);
/* Input the system as in the example*/
a11 : 1;
a12 : 3;
a13 : 5;
a22 : 7;
a23 : 13;
a33 : 8;
matA : matrix([a11, a12, a13], [0, a22, a23], [0, 0, a33]);
vecB : matrix([14], [25], [24]);
vecX : matrix([x], [y], [z]);

/* Construct the solution */
aux_LHS : matA.vecX;
eq1 : aux_LHS[1][1] = vecB[1][1];
eq2 : aux_LHS[2][1] = vecB[2][1];
eq3 : aux_LHS[3][1] = vecB[3][1];
ta_aux : algsys([eq1, eq2, eq3], [x, y, z]);
ta : matrix([rhs(ta_aux[1][1])], [rhs(ta_aux[1][2])], [rhs(ta_aux[1][3])])</text>
    </questionvariables>
    <specificfeedback format="html">
      <text/>
    </specificfeedback>
    <questionnote format="moodle_auto_format">
      <text/>
    </questionnote>
    <questiondescription format="moodle_auto_format">
      <text/>
    </questiondescription>
    <questionsimplify>1</questionsimplify>
    <assumepositive>0</assumepositive>
    <assumereal>0</assumereal>
    <prtcorrect format="html">
      <text><![CDATA[<span style="font-size: 1.5em; color:green;"><i class="fa fa-check"></i></span> Correct answer, well done.]]></text>
    </prtcorrect>
    <prtpartiallycorrect format="html">
      <text><![CDATA[<span style="font-size: 1.5em; color:orange;"><i class="fa fa-adjust"></i></span> Your answer is partially correct.]]></text>
    </prtpartiallycorrect>
    <prtincorrect format="html">
      <text><![CDATA[<span style="font-size: 1.5em; color:red;"><i class="fa fa-times"></i></span> Incorrect answer.]]></text>
    </prtincorrect>
    <decimals>.</decimals>
    <scientificnotation>*10</scientificnotation>
    <multiplicationsign>dot</multiplicationsign>
    <sqrtsign>1</sqrtsign>
    <complexno>i</complexno>
    <inversetrig>cos-1</inversetrig>
    <logicsymbol>lang</logicsymbol>
    <matrixparens>[</matrixparens>
    <isbroken>0</isbroken>
    <variantsselectionseed/>
    <input>
      <name>ans1</name>
      <type>matrix</type>
      <tans>ta</tans>
      <boxsize>4</boxsize>
      <strictsyntax>1</strictsyntax>
      <insertstars>0</insertstars>
      <syntaxhint/>
      <syntaxattribute>0</syntaxattribute>
      <forbidwords/>
      <allowwords/>
      <forbidfloat>1</forbidfloat>
      <requirelowestterms>0</requirelowestterms>
      <checkanswertype>0</checkanswertype>
      <mustverify>1</mustverify>
      <showvalidation>3</showvalidation>
      <options/>
    </input>
    <prt>
      <name>prt1</name>
      <value>1.0000000</value>
      <autosimplify>1</autosimplify>
      <feedbackstyle>1</feedbackstyle>
      <feedbackvariables>
        <text/>
      </feedbackvariables>
      <node>
        <name>0</name>
        <description/>
        <answertest>AlgEquiv</answertest>
        <sans>ans1</sans>
        <tans>ta</tans>
        <testoptions/>
        <quiet>1</quiet>
        <truescoremode>=</truescoremode>
        <truescore>1.0000000</truescore>
        <truepenalty/>
        <truenextnode>-1</truenextnode>
        <trueanswernote>prt1-1-T</trueanswernote>
        <truefeedback format="html">
          <text>Well done!</text>
        </truefeedback>
        <falsescoremode>=</falsescoremode>
        <falsescore>0.0000000</falsescore>
        <falsepenalty/>
        <falsenextnode>-1</falsenextnode>
        <falseanswernote>prt1-1-F</falseanswernote>
        <falsefeedback format="html">
          <text>Be careful, your answer doesn't satisfy the system \[ {@matA@} {@ans1@} = {@matA . ans1@} \neq {@vecB@} \].</text>
        </falsefeedback>
      </node>
    </prt>
    <qtest>
      <testcase>1</testcase>
      <description/>
      <testinput>
        <name>ans1</name>
        <value>ta</value>
      </testinput>
      <expected>
        <name>prt1</name>
        <expectedscore>1.0000000</expectedscore>
        <expectedpenalty>0.0000000</expectedpenalty>
        <expectedanswernote>prt1-1-T</expectedanswernote>
      </expected>
    </qtest>
    <qtest>
      <testcase>2</testcase>
      <description/>
      <testinput>
        <name>ans1</name>
        <value>ev(2*ta,simp)</value>
      </testinput>
      <expected>
        <name>prt1</name>
        <expectedscore>0.0000000</expectedscore>
        <expectedpenalty>0.1000000</expectedpenalty>
        <expectedanswernote>prt1-1-F</expectedanswernote>
      </expected>
    </qtest>
  </question>
</quiz>
