S2013, Section 3.2: 10,14,18,24,26,28 3.2-10 x1-5x2+2x3-7x4+11x5=0, x2-13x3+3x4-7x5=0, x4-5x5=0. Solve ====== the echelon system by back-substitution. BACK SUBSTITUTION. The idea of "back-substitution" is to arrive at the last frame of a frame sequence by aborting the standard algorithm which looks at the variable list from its original ordering, and taking up a new ordering temporarily, namely a reversed variable list, in order to invent a sequence of simplified combos to reach the last frame. The number of combos used is the same as with the original list order. The back-substitution algorithm has limited use for humans and good use on machines, where it could reduce arithmetic overhead. WHAT CAN YOU LEARN FROM ALL THIS? It teaches you to be clever about the choice of the next step in a frame sequence. It is not always best to follow the variable list order, even though that is the plan, eventually. A frame sequence step can take things out of order, to advantage. The signal: you look at the current frame and see that all lead variables are known. A departure from the standard algorithm might then prove to be advantageous. The 3 equations in 5 unknowns have infinitely many solutions. We know this because there are at most three lead variables, hence at least two free variables. The given system is not the last frame in a frame sequence, but very close. All lead variables are already known: x1,x2,x4. Consider the variable list in reverse order: x5,x4,x3,x2,x1. The lead variables are going to be x1,x2,x4. We go down the list x5,x4,x3,x2,x1 starting with x5. It is free, so skip it. Go next to x4. It will be a lead variable, so eliminate x4 from equations 1 and 2. It takes two combos to do it, and these operations are arithmetically identical to "back-substitution". We leave equation 3 in place, as the last equation. Then repeat for x3. It is a free variable, skip it. Go next to x2. It will be a lead variable, so eliminate x2 from equation 1, with a combo. The system is now in reduced row echelon form, that is, the last frame has been found. MAPLE ANSWER CHECK. # We find the last frame directly as the rref of the first frame A:=Matrix([[1,-5,2,-7,11],[1,-13,3,-7],[0,0,0,1,-5]]); linalg[rref](A); # Answer: # Matrix([[1,0,11/8,0,-137/8],[0,1,-1/8,0,11/8],[0,0,0,1,-5]]); x1 + (11/8)x3 - 7x4 - (137/8)x5=0 This is the Last Frame x2 - (1/8)x3 + (11/8)x5=0 Not done. Now apply the x4 - 5x5=0 Last Frame Algorithm The general solution is obtained by applying the Last Frame Algorithm. There is no shortcut for this algorithm, it is not included in back-substitution, nor does the textbook say otherwise. Expected solution steps: Last Frame Algorithm 0. Justify that this is indeed the last frame, by applying the Last Frame Test. 1. Identify lead variables. 2. Identify free variables. Assign invented symbols t1, t2, t3, ... 3. Back-substitute the free variables into the lead variable equations. 4. Report the solution as the list of variables, each followed by an equal sign. Each equal sign is followed by a constant or else an expression in the invented symbols. 3.2-14 3x1-6x2-2x3=1, 2x1-4x2+x3=17, x1-2x2-2x3=-9. Transform to ====== echelon form and solve by back-substitution. Remarks from 3.2-10 apply. Please read them if you skipped that problem. This problem differs from 3.2-10, in that the system is not in triangular form, hence we don't know the lead variables (yet). WHAT CAN YOU LEARN FROM THIS EXAMPLE? Learn that the frame sequence starts with the original system and ends with the last frame, which is uniquely determined, and that back-substitution guides us to find a triangular system in the first frames, in order to organize the final frames into combo steps applied to the lead variables (which were already known from the triangular form). You are actually learning some details of numerical analysis, because in that subject efficiency is important. The 3 equations in 3 unknowns require a number of toolkit steps: combo, swap, mult. Write a frame sequence, one toolkit operation per frame, ending with an intermediate frame in triangular form. This is the important sequence of steps. Then go on to find the last frame, which has one free variable and two lead variables. Justify that this is indeed the last frame, that it passes the Last Frame Test. Then carry out the Last Frame Algorithm to display the solution. MAPLE ANSWER CHECK. # We find the last frame directly as the rref of the first frame A:=Matrix([[3,-6,-2],[2,-4,1],[1,-2,-2]]); b:=<1,17,-9>; C:=; # First Frame linalg[rref](C); # Last Frame # Answer: # Matrix([[1,-2,0,5],[0,0,1,7],[0,0,0,0]]); x1 - 2x2 = 5 This is the Last Frame x3 = 7 Not done. Now apply the 0 = 0 Last Frame Algorithm Expected solution steps: Last Frame Algorithm 0. Justify that this is indeed the last frame, by applying the Last Frame Test. 1. Identify lead variables. 2. Identify free variables. Assign invented symbols t1, t2, t3, ... 3. Back-substitute the free variables into the lead variable equations. 4. Report the solution as the list of variables, each followed by an equal sign. Each equal sign is followed by a constant or else an expression in the invented symbols. 3.2-18 3x1 - 6x2 + x3 + 13x4 = 15 Transform to echelon form, then ===== 3x1 - 6x2 + 3x3 + 21x4 = 21 solve by back-substitution. 2x1 - 4x2 + 5x3 + 26x4 = 23 There are 3 equations and 4 unknowns, therefore at most 3 lead variables and at least one free variable. This implies infinitely many solutions. Like 3.2-14 above, you must display a frame sequence whose intermediate frame is a triangular system. The last frame is a reduced echelon system. Then proceed to apply the Last Frame Algorithm in order to write out the general solution, as in 3.2-14. MAPLE ANSWER CHECK. # We find the last frame directly as the rref of the first frame A:=Matrix([[3, -6, 1, 13],[3, -6, 3, 21],[2, -4, 5, 26]]); b:= <15,21,23>; C:=; # First Frame linalg[rref](C); # Last Frame # Answer: # Matrix([[1, -2, 0, 3, 4], [0, 0, 1, 4, 3], [0, 0, 0, 0, 0]]); x1 - 2x2 + 3x4 = 4 This is the Last Frame x3 + 4x4 = 3 Not done. Now apply the 0 = 0 Last Frame Algorithm 3.2-24 3x+2y=0, 6x+ky=0. Classify according to symbol k the Three ====== Possibilities: (a) Unique solution, (b) No solution, (c) Infinitely many solutions. Because the equations have symbol k appearing in the coefficients, there will in general be infinitely frame sequences, one for each value of k. The last frame of any such sequence can theoretically have a signal equation, or zero free variables, or at least one free variable, which classifies the problem as No Sol, Infinitely Many Solutions or a Unique Solution. The class (a,b,c) the last frame falls into depends on the value of k, and not all classifications need be represented. Display as many complete frame sequences as necessary, each depending on a range of values of k, such that the last frame determines one of the three possibilities. Clearly state assumptions used for each frame sequence. See web references for similar problems, which give further hints on how to organize the work and draw conclusions. 3.2-26 3x+2y=1, 7x+5y=k. Classify according to symbol k the Three ====== Possibilities: (a) Unique solution, (b) No solution, (c) Infinitely many solutions. The advice for 3.2-24 applies, but this problem is considerably simpler, due to there being just one frame sequence reported, valid for all values of k. Conclusion: there are zero free variables and a unique solution. 3.2-28 2x-y+3z=a, x+2y+z=b, 7x+4y+9z=c. Classify according to ====== symbols a,b,c the Three Possibilities: (a) Unique solution, (b) No solutuion, (c) Infinitely many solutions. The basic advice given in 3.2-26 applies. There is just one frame sequence whose last frame has 2 lead variables and one free variable. However, it may have a signal equation if c-2a-3b is nonzero. The unique solution case can never happen, because there always exactly 2 lead variables. MAPLE ANSWER CHECK. # Use maple to find a triangular frame, from which # the result can be deduced. A:=Matrix([[2-1,3],[1,2,1],[7,4,9]]); B:= ; C:=; # First Frame # The maple steps have to be carried out by hand, using # swap, combo, mult [linalg: swaprow, addrow, mulrow] C1:=linalg[swaprow](C,1,2); C2:=linalg[addrow](C1,1,2,-2); C3:=linalg[addrow](C2,1,3,-7); C4:=linalg[addrow](C3,2,3,-2); # Triangular frame is # Matrix([[1,2,1,b],[0,-5,1,-2*b+a],[0,0,0,c-2*a-3*b]]); The conclusion: Two lead variables. Row 3 is zero if and only if the entry c-2*a-3*b is zero. Then the system has no signal equation.