{VERSION 5 0 "IBM INTEL NT" "5.0" } {USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 1 0 0 0 0 1 }{CSTYLE "" -1 256 "" 1 12 0 0 0 0 0 0 0 0 0 0 0 0 0 0 } {PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Heading 1" 0 3 1 {CSTYLE "" -1 -1 "" 1 18 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }1 0 0 0 8 4 0 0 0 0 0 0 -1 0 }{PSTYLE "Heading 2" 3 4 1 {CSTYLE "" -1 -1 "" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }0 0 0 -1 8 2 0 0 0 0 0 0 -1 0 }{PSTYLE "Headi ng 3" 4 5 1 {CSTYLE "" -1 -1 "" 1 12 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }0 0 0 -1 0 0 0 0 0 0 0 0 -1 0 }{PSTYLE "List Item" 0 14 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }0 0 0 -1 3 3 0 0 0 0 0 0 14 5 } {PSTYLE "" 4 256 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }3 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Exercise" 0 257 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }0 0 0 -12 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 4 258 1 {CSTYLE "" -1 -1 "" 1 24 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }3 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 4 259 1 {CSTYLE "" -1 -1 "" 1 24 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }3 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }} {SECT 0 {EXCHG {PARA 259 "" 0 "" {TEXT -1 0 "" }{TEXT 256 24 "Linear A lgebra Powertool" }}{PARA 258 "" 0 "" {TEXT -1 20 "The LU Decompositio n" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 256 "" 0 "" {TEXT -1 10 "On Line 3.5" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 27 "Worksheet by Russell Blyth." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 52 "restart: with(linalg): with( plots): with(plottools):" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}} {SECT 1 {PARA 4 "" 0 "" {TEXT -1 7 "Outline" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 61 "This worksheet investigates the LU decomposition of a mat rix." }}{PARA 0 "" 0 "" {TEXT -1 25 "The basic objectives are:" }} {PARA 14 "" 0 "" {TEXT -1 46 "1) Compute the LU decomposition, if pos sible." }}{PARA 14 "" 0 "" {TEXT -1 60 "2) See how elementary matrice s are involved in the process." }}{PARA 14 "" 0 "" {TEXT -1 81 "3) Und erstand how the LU decomposition is useful in solving systems of equat ions." }}}}{SECT 1 {PARA 4 "" 0 "" {TEXT -1 27 "Finding an LU decompos ition" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 35 "First define a random 3 x 4 matrix." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 41 "A := randmatr ix(3,4,entries=rand(-5..5));" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 239 " Let's keep track of the elementary matrices corresponding to the row o perations used, as well as the cumulative product of the elementary ma trices, which we can do by starting with the matrix A augmented by the appropriate identity matrix:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 65 "Iden:=evalm(array(identity, 1..3,1..3));\nAAug := augment(A,Iden );" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 186 "Now we apply elementary ro w operations to the augmented matrix. We hope to add multiples of rows to lower rows to get a row echelon form. We exhibit the elementary ma trices at each step." }}{PARA 0 "" 0 "" {TEXT -1 419 "(Note that the m atrix A is not truly \"random\" - every time the worksheet is started, it produces the same matrix A. Thus we know in advance which row oper ations are required in this worksheet. This is handy for teaching purp oses. If you want a truly \"random\" matrix, you need to precede the r andmatrix command with a \"randomize()\", which generates a seed for t he random functions in Maple, based on the computer clock.)" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 57 "AAugR := addrow(AAug,1,2,1/4 );\nE := addrow(Iden,1,2,1/4);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 56 "AAugR := addrow(AAugR,1,3,-1);\nE := addrow(Iden,1,3,-1);" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 64 "AAugR := addrow(AAugR,2,3,5* 4/17);\nE := addrow(Iden,2,3,5*4/17);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 108 "AAugR is in row echelon form. Note we don't bother to fo rce leading ones. The matrix U can now be extracted:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "U := delcols(AAugR,5..7);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 56 "The matrix B referred to in class can als o be extracted:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "B := del cols(AAugR,1..4);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 51 "The matrix L we seek is just the inverse of this B:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "L := inverse(B);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 221 "Now note the remarkable relationship between the entries of L, th e elementary matrices, and the multipliers used in the row reductions! The matrix L can in fact be written down without actually computing t he inverse of B." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 17 "Check that A = LU" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "evalm(L &* U); evalm(A);" }} }{EXCHG {PARA 5 "" 0 "" {TEXT -1 9 "Exercise:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 146 "1) Repeat the above for a random 4 x 4 matrix AA (be \+ careful not to reuse any of the variable names used previously, since \+ some get reused below!)" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 70 "Now let's see how to use the LU decomposi tion to solve a system AX = Y" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 29 "Let's generate a RHS vector Y" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 41 "Y := randmatrix(3,1,entries=rand(-5 ..5));" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 152 "Solve LZ = Y for Z; no te this amounts to a simple forward-substitution (no further row reduc tions). We show the augmented matrix and have Maple compute." }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 31 "augment(L,Y);\nZ:=linsolve(L ,Y);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 180 "Then solve UX = Z for X; note this amounts to a simple back-substitution (no further row reduc tions). We show the augmented matrix and again have Maple compute the \+ solution for us." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 33 "augment (U,Z);\nX := linsolve(U,Z);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 73 "(U nfortunately Maple does not always select the parameter the way we do. )" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 5 "" 0 "" {TEXT -1 9 "Exercise:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 92 "2) Generate a ran dom 4 x 1 vector YY, and then repeat the steps above to solve (AA)(X) \+ = YY." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 " " 0 "" {TEXT -1 106 "3) What advantage would the LU decomposition have for computer computation of solutions to linear systems?" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 159 " 4) Use Maple's help command to find out about the LUdecomp command in the linalg package, Use the command to check your LU decomposition o f AA in exercise 1." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 0 "" }}}}{MARK "0 0 1" 24 }{VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 }