{VERSION 2 3 "SUN SPARC SOLARIS" "2.3" } {USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 1 0 0 0 0 }{CSTYLE "2D Math" -1 2 "Times" 0 1 0 0 0 0 0 0 2 0 0 0 0 0 0 }{CSTYLE "Hyperlink" -1 17 "" 0 1 0 128 128 1 0 0 1 0 0 0 0 0 0 } {CSTYLE "2D Comment" 2 18 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }{PSTYLE "N ormal" -1 0 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }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 0 0 0 6 6 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 }0 0 0 -1 4 4 0 0 0 0 0 0 -1 0 }{PSTYLE "Title" 0 18 1 {CSTYLE "" -1 -1 "" 1 18 0 0 0 0 0 1 1 0 0 0 0 0 0 }3 0 0 -1 12 12 0 0 0 0 0 0 19 0 }{PSTYLE "Author" 0 19 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }3 0 0 -1 8 8 0 0 0 0 0 0 -1 0 }} {SECT 0 {EXCHG {PARA 18 "" 0 "" {TEXT -1 25 "Orthonormal Bases and the " }}{PARA 18 "" 0 "" {TEXT -1 16 "QR Decomposition" }}{PARA 19 "" 0 " " {TEXT -1 14 "April 14, 1998" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 9 " Load the " }{HYPERLNK 17 "Linalg" 2 "linalg" "" }{TEXT -1 9 " package. " }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "with(linalg):" }}}} {SECT 1 {PARA 3 "" 0 "" {TEXT -1 24 "The Gram-Schmidt process" }} {SECT 1 {PARA 4 "" 0 "" {TEXT -1 28 "As demonstrated in the text." }} {EXCHG {PARA 0 "" 0 "" {TEXT -1 50 "First put in three vectors to use \+ for Gram-Schmidt" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 81 "v1 := vector([1 ,2,1,2,1]);\nv2 := vector([2,1,3,1,0]);\nv3 := vector([-1,1,0,2,1]);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 60 "Now one does the Gram-Schmidt p rocess. The first vector is " }{XPPEDIT 18 0 "v1" "I#v1G6\"" }{TEXT -1 1 "." }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "w1 := v1;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 20 "Next one calculates " }{XPPEDIT 18 0 "w2 " "I#w2G6\"" }{TEXT -1 1 "." }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 57 "w2 : = evalm(v2 - (innerprod(v2,w1)/innerprod(w1,w1))*w1);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 23 "Finally one calculates " }{XPPEDIT 18 0 " w3" "I#w3G6\"" }{TEXT -1 1 "." }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 113 "w 3 := evalm(v3 - (innerprod(v3,w1)/innerprod(w1,w1))*w1\n \+ - (innerprod(v3,w2)/innerprod(w2,w2))*w2);" }}}{EXCHG {PARA 0 "" 0 " " {TEXT -1 84 "Now we can check our results. The easiest way is to fo rm a matrix whose columns are" }}{PARA 0 "" 0 "" {TEXT -1 4 "the " } {XPPEDIT 18 0 "w" "I\"wG6\"" }{TEXT -1 17 "'s and calculate " } {XPPEDIT 18 0 "transpose(G) * G" "*&-%*transposeG6#%\"GG\"\"\"F&F'" } {TEXT -1 52 ". If the vectors are orthogonal, the result will be" }} {PARA 0 "" 0 "" {TEXT -1 18 "a diagonal matrix." }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 49 "G := augment(w1,w2,w3);\nevalm(transpose(G) &* G);" } }}}{SECT 1 {PARA 4 "" 0 "" {TEXT -1 24 "Using the Maple routine " } {HYPERLNK 17 "GramSchmidt" 2 "linalg,GramSchmidt" "" }{TEXT -1 1 "." } }{EXCHG {PARA 0 "" 0 "" {TEXT -1 67 "The GramSchmidt routine requires \+ a list or set of vectors as input." }}{PARA 0 "" 0 "" {TEXT -1 69 "One simply puts the desired vectors in as a list and gets the output." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 43 "Compare t he output with what you got above." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "GramSchmidt([v1,v2,v3]);" }}}}} {SECT 1 {PARA 3 "" 0 "" {TEXT -1 21 "The QR decomposition." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 46 "Earlier in the te xt we decomposed a matrix as " }{XPPEDIT 18 0 "PA=LU" "/%#PAG%#LUG" } {TEXT -1 22 ". Here is another way" }}{PARA 0 "" 0 "" {TEXT -1 66 "of decomposing a matrix. This is done in Section 4.5 of the text." }} {SECT 1 {PARA 4 "" 0 "" {TEXT -1 31 "Using the Gram-Schmidt process." }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 67 "First one gets a random 4 by 4 m atrix. This should be nonsingular!" }}{PARA 0 "" 0 "" {TEXT -1 0 "" } }{PARA 0 "> " 0 "" {MPLTEXT 1 0 28 "A := evalf(randmatrix(4,4));" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 33 "Now we get the columns as a list. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 43 "colBasis := [seq(col(A,i),i=1..coldim(A))];" }}}{EXCHG {PARA 0 "" 0 " " {TEXT -1 66 "One can use the Gram-Schmidt process to convert this ba sis into an" }}{PARA 0 "" 0 "" {TEXT -1 17 "orthogonal basis." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 35 "OCo lBasis := GramSchmidt(colBasis);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 71 "For this work we need an orthonormal basis, i.e. an orthogonal bas is of" }}{PARA 0 "" 0 "" {TEXT -1 59 "unit vectors. This simply divid es each vector by its norm." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 52 "The vectors are then put as the coulmns of a ma trix " }{XPPEDIT 18 0 "Q" "I\"QG6\"" }{TEXT -1 10 " and it is" }} {PARA 0 "" 0 "" {TEXT -1 35 "checked to see that the columns of " } {XPPEDIT 18 0 "Q" "I\"QG6\"" }{TEXT -1 23 " are orthonormal. (Are" }} {PARA 0 "" 0 "" {TEXT -1 18 "they orthonormal?)" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 106 "ONColBasis := map( x -> (1/norm(x,2))*x,OColBasis);\nQ := augment(op(ONColBasis));\nevalm (transpose(Q) &* Q);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 25 "Now one c an generate the " }{XPPEDIT 18 0 "R" "I\"RG6\"" }{TEXT -1 58 " matrix. Only the entries above the diagonal are nonzero." }}{PARA 0 "" 0 "" {TEXT -1 4 "The " }{XPPEDIT 18 0 "i" "I\"iG6\"" }{TEXT -1 16 "th entry in the " }{XPPEDIT 18 0 "j" "I\"jG6\"" }{TEXT -1 37 "th column is the innerproduct of the " }{XPPEDIT 18 0 "i" "I\"iG6\"" }{TEXT -1 13 "th \+ column of " }{XPPEDIT 18 0 "Q" "I\"QG6\"" }{TEXT -1 10 " with the " }} {PARA 0 "" 0 "" {XPPEDIT 18 0 "j" "I\"jG6\"" }{TEXT -1 13 "th column o f " }{XPPEDIT 18 0 "A" "I\"AG6\"" }{TEXT -1 1 "." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 177 "R := matrix(rowdim (A),coldim(A),0):\nfor i from 1 to coldim(A) do\n for j from i to \+ coldim(A) do\n R[i,j] := innerprod(col(A,j),col(Q,i));\n \+ od:\n od:\nevalm(R);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 21 "Now \+ one can check if " }{XPPEDIT 18 0 "QR" "I#QRG6\"" }{TEXT -1 16 " is th e same as " }{XPPEDIT 18 0 "A" "I\"AG6\"" }{TEXT -1 1 "." }}{PARA 0 " " 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "evalm((Q &* \+ R));" }}}}{SECT 1 {PARA 4 "" 0 "" {TEXT -1 17 "Maple's routine, " } {HYPERLNK 17 "QRdecomp" 2 "linalg,QRdecomp" "" }{TEXT -1 1 "." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 79 "The linal g package has a built in QR decomposition routine. It is easy to use. " }}{PARA 0 "" 0 "" {TEXT -1 35 "The only major problem is that the " }{XPPEDIT 18 0 "Q" "I\"QG6\"" }{TEXT -1 40 " matrix must be returned a s a parameter." }}{PARA 0 "" 0 "" {TEXT -1 24 "This is a little tricky ." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 51 "Comp are this decomposition with the one from above." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 55 "R1 := QRdeco mp(A,Q = 'Q1');\nevalm(Q1);\nevalm(Q1 &* R1);" }}}}}{SECT 1 {PARA 3 " " 0 "" {TEXT -1 9 "Exercises" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 23 "Ex plain why the matrix " }{XPPEDIT 18 0 "transpose(G) * G" "*&-%*transpo seG6#%\"GG\"\"\"F&F'" }{TEXT -1 33 " from above is a diagonal matrix. " }{MPLTEXT 1 0 1 " " }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 12 "If a matr ix " }{XPPEDIT 18 0 "Q" "I\"QG6\"" }{TEXT -1 33 " has orthonormal colu mns, why is " }{XPPEDIT 18 0 "transpose(Q) * Q" "*&-%*transposeG6#%\"Q G\"\"\"F&F'" }{TEXT -1 7 " always" }}{PARA 0 "" 0 "" {TEXT -1 19 "an i dentity matrix?" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 7 "Find a " } {XPPEDIT 18 0 "QR" "I#QRG6\"" }{TEXT -1 28 " decompostion of the matri x " }{XPPEDIT 18 0 "A =MATRIX([[1,2,-1],[2,1,0],[3,2,-2]])" "/%\"AG-%' MATRIXG6#7%7%\"\"\"\"\"#,$\"\"\"!\"\"7%\"\"#\"\"\"\"\"!7%\"\"$\"\"#,$ \"\"#F-" }{TEXT -1 1 "." }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 9 "Use thi s " }{XPPEDIT 18 0 "QR" "I#QRG6\"" }{TEXT -1 24 " decomposition to sol ve " }}{PARA 0 "" 0 "" {TEXT -1 7 " " }{XPPEDIT 18 0 "MATRIX([[1 ,2,-1],[2,1,0],[3,2,-2]]) *x = MATRIX([[1],[1],[1]])" "/*&-%'MATRIXG6# 7%7%\"\"\"\"\"#,$\"\"\"!\"\"7%\"\"#\"\"\"\"\"!7%\"\"$\"\"#,$\"\"#F-\" \"\"%\"xGF7-F%6#7%7#\"\"\"7#\"\"\"7#\"\"\"" }{TEXT -1 1 "." }}}}} {MARK "4 0 0" 9 }{VIEWOPTS 1 1 0 1 1 1803 }