{VERSION 6 0 "IBM INTEL NT" "6.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 "2D Math" -1 2 "Times" 0 1 0 0 0 0 0 0 2 0 0 0 0 0 0 1 }{CSTYLE "2D Output" 2 20 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 1 } {PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }1 1 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Maple Output" -1 11 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }3 3 0 0 0 0 1 0 1 0 2 2 0 1 }} {SECT 0 {EXCHG {PARA 0 "" 0 "" {TEXT -1 72 "-------------------------- ----------------------------------------------" }}{PARA 0 "" 0 "" {TEXT -1 65 " c235-08.mws Ortho-Normal Gram Schmidt for columns of \+ a matrix" }}{PARA 0 "" 0 "" {TEXT -1 72 "----------------------------- -------------------------------------------" }}{PARA 0 "" 0 "" {TEXT -1 37 "Gram-Schmidt and the QR decomposition" }}{PARA 0 "" 0 "" {TEXT -1 43 "-------------------------------------------" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 45 "We first write a function gson that takes an " }}{PARA 0 "" 0 "" {TEXT -1 51 "(m x n) matrix w ith n linearly independent columns" }}{PARA 0 "" 0 "" {TEXT -1 57 " an d generates from it a matrix with orthonormal columns." }}{PARA 0 "" 0 "" {TEXT -1 41 "If the matrix is square, the result is an" }}{PARA 0 "" 0 "" {TEXT -1 37 "orthogonal matrix: M^tM = M M^t = I." }}{PARA 0 "" 0 "" {TEXT -1 52 "Since the columns are LI, we know n = rank(M) < = m." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 7 "N ote(1)" }}{PARA 0 "" 0 "" {TEXT -1 52 "Be careful with this syntactica l asymmetry of Maple:" }}{PARA 0 "" 0 "" {TEXT -1 40 "Extracting ith c olumn u := Column(M, i)" }}{PARA 0 "" 0 "" {TEXT -1 37 "Assigning ith column M[1..m, i] := u" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 " " 0 "" {TEXT -1 7 "Note(2)" }}{PARA 0 "" 0 "" {TEXT -1 45 "Students ar e not expected to be able to write" }}{PARA 0 "" 0 "" {TEXT -1 49 "pro cedures like this for quizzes tests and exams," }}{PARA 0 "" 0 "" {TEXT -1 46 "but they are certainly allowed to use the code" }}{PARA 0 "" 0 "" {TEXT -1 19 "whenever they wish." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "with(LinearAlgebr a):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 408 "gson:=proc(mi) loca l m,n,mo,i,j,u,ui,e,ej;\n m := Dimension(mi)[1];\n n := Dimension(mi )[2];\n mo := Matrix(m,n);\n u := Column(mi,1);\n e := u/Norm(u,2); \n mo[1..m,1] := e;\n for i from 2 to n by 1 do\n ui := Column(mi ,i);\n u := ui;\n for j from 1 by 1 to i-1 do;\n ej := Col umn(mo,j);\n u := u - (Transpose(ui).ej)*ej;\n end do;\n m o[1..m,i] := u/Norm(u,2);\n end do;\n mo;\n end proc:\n\n" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 33 "Square Test Matrix (from c235-07)" }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 31 "C := <<1,0,1>|<1,2,0>|<1,1,2>>;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"CG-%'RTABLEG6%\")ovp7-%'MATRIXG6#7%7%\"\"\"F.F.7%\"\"!\"\"#F.7% F.F0F1%'MatrixG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "gson(C); " }}{PARA 11 "" 1 "" {TEXT -1 0 "" }{XPPMATH 20 "6#-%'RTABLEG6%\")cRq7 -%'MATRIXG6#7%7%,$*&\"\"#!\"\"F.#\"\"\"F.F1,$*&\"\"'F/F.F0F1#!\"#\"\"$ 7%\"\"!,$*(F.F1F7F/F.F0F1#F1F77%F,,$*&F4F/F.F0F/#F.F7%'MatrixG" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 19 "Another test matrix" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 47 "A := < <1,1,0,0>|<1,2,1,1>|<1,1,1,3>|<1,0,1,0>>;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"AG-%'RTABLEG6%\")3aq7-%'MATRIXG6#7&7&\"\"\"F.F.F.7& F.\"\"#F.\"\"!7&F1F.F.F.7&F1F.\"\"$F1%'MatrixG" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 14 "Ao := gson(A);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#AoG-%'RTABLEG6%\")S3r7-%'MATRIXG6#7&7&,$*&\"\"#!\"\"F0#\"\"\" F0F3,$*&\"#5F1F6F2F1,$*(F0F3\"#:F1F6F2F3,$*&\"\"$F1F0F2F37&F.,$*&F6F1F 6F2F3,$*(F0F3F9F1F6F2F1,$*&F " 0 "" {MPLTEXT 1 0 17 "Transpose(Ao).Ao;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%'RTABLEG6%\")w\\r7-%'MATRIXG6#7&7&\"\"\"\"\"!F-F-7&F- F,F-F-7&F-F-F,F-7&F-F-F-F,%'MatrixG" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 53 "Since A is square, the reverse product also yields I." }}{PARA 0 "" 0 "" {TEXT -1 51 "That is to say, Ao^T = Ao^(-1); Ao is orthogo nal." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "Ao.Transpose(Ao);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6# -%'RTABLEG6%\");(=F\"-%'MATRIXG6#7&7&\"\"\"\"\"!F-F-7&F-F,F-F-7&F-F-F, F-7&F-F-F-F,%'MatrixG" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 25 " QR for \+ a square matrix A" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 30 "A = Ao.(Transpose(Ao).A) = QR" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "Q := Ao;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"QG-%'RTABLEG6%\")S3r7-%'MATRIXG6#7&7&,$* &\"\"#!\"\"F0#\"\"\"F0F3,$*&\"#5F1F6F2F1,$*(F0F3\"#:F1F6F2F3,$*&\"\"$F 1F0F2F37&F.,$*&F6F1F6F2F3,$*(F0F3F9F1F6F2F1,$*&F " 0 "" {MPLTEXT 1 0 21 "R := Transpose(Ao).A;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"RG-%'RTABLEG6%\"))=?F\"-%'MATRIX G6#7&7&*$\"\"##\"\"\"F/,$*(\"\"$F1F/!\"\"F/F0F1F.,$*&F/F5F/F0F17&\"\"! ,$*&F/F5\"#5F0F1,$*(\"\"%F1\"\"&F5F " 0 "" {MPLTEXT 1 0 4 "Q.R;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%'RTABLEG6%\" )GRs7-%'MATRIXG6#7&7&\"\"\"F,F,F,7&F,\"\"#F,\"\"!7&F/F,F,F,7&F/F,\"\"$ F/%'MatrixG" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 34 "Now we move to the non-square case" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "B:= <<1,1,1>|<2,1,2>>;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"BG-%'RTABLEG6%\")+as7-%'MATRIXG6#7%7$\"\"\"\"\"#7$F .F.F-%'MatrixG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "Bo := gso n(B);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#BoG-%'RTABLEG6%\")/1t7-%'M ATRIXG6#7%7$,$*&\"\"$!\"\"F0#\"\"\"\"\"#F3,$*&\"\"'F1F7F2F37$F.,$*&F0F 1F7F2F1F-%'MatrixG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "Trans pose(Bo).Bo;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%'RTABLEG6%\")sHt7-%' MATRIXG6#7$7$\"\"\"\"\"!7$F-F,%'MatrixG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "Bo.Transpose(Bo);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6# -%'RTABLEG6%\")kct7-%'MATRIXG6#7%7%#\"\"\"\"\"#\"\"!F,7%F/F-F/F+%'Matr ixG" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 55 " This matrix just construc ted is not the 3 x 3 identity" }}{PARA 0 "" 0 "" {TEXT -1 65 "but it b ehaves like an identity when it multiplies B on the left:" }}{PARA 0 " " 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "Bo.T ranspose(Bo).B;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%'RTABLEG6%\")!3QF \"-%'MATRIXG6#7%7$\"\"\"\"\"#7$F,F,F+%'MatrixG" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 8 "Q := Bo;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>% \"QG-%'RTABLEG6%\")/1t7-%'MATRIXG6#7%7$,$*&\"\"$!\"\"F0#\"\"\"\"\"#F3, $*&\"\"'F1F7F2F37$F.,$*&F0F1F7F2F1F-%'MatrixG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "R := Transpose(Bo).B;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"RG-%'RTABLEG6%\")s2u7-%'MATRIXG6#7$7$*$\"\"$#\"\"\" \"\"#,$*(\"\"&F1F/!\"\"F/F0F17$\"\"!,$*&F/F6\"\"'F0F1%'MatrixG" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 4 "Q.R;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%'RTABLEG6%\")Kdu7-%'MATRIXG6#7%7$\"\"\"\"\"#7$F,F,F+% 'MatrixG" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 56 "The columns of Bo are an orthonormal basis \{e\} for R^n ." }}{PARA 0 "" 0 "" {TEXT -1 58 "Transpose(Bo).v = [v]_e = coordinat es of v wrt basis \{e\}." }}{PARA 0 "" 0 "" {TEXT -1 53 "Transpose(Bo) .B has columns which are the coordinates" }}{PARA 0 "" 0 "" {TEXT -1 52 "of the original columns of B in the (new) basis \{e\}." }}{PARA 0 "" 0 "" {TEXT -1 56 "When we then multiply on the left by Bo we conver t these" }}{PARA 0 "" 0 "" {TEXT -1 54 "coordinate column vectors back to the original columns" }}{PARA 0 "" 0 "" {TEXT -1 56 "of B. That i s the whole story. The upper diagonal form" }}{PARA 0 "" 0 "" {TEXT -1 48 "of the columns of B in basis \{e\} comes from the " }}{PARA 0 " " 0 "" {TEXT -1 48 "Gram-Schmidt procedure: the first column has one" }}{PARA 0 "" 0 "" {TEXT -1 51 "non-zero element at the top; the second is a linear" }}{PARA 0 "" 0 "" {TEXT -1 51 "combination of \{e1, e2\} ; the third of \{e1, e2, e3\}," }}{PARA 0 "" 0 "" {TEXT -1 10 "and so \+ on." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}}{MARK "27 0 0" 0 }{VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 }{RTABLE_HANDLES 12697568 12703956 12705408 12710840 12714976 12718716 12720188 12723928 12725400 12730604 12732972 12735664 12738080 12740772 12745732 }{RTABLE M7R0 I5RTABLE_SAVE/12697568X,%)anythingG6"6"[gl!"%!!!#*"$"$"""""!F'F'""#F(F'F'F)6" } {RTABLE M7R0 I5RTABLE_SAVE/12703956X,%)anythingG6"6"[gl!"%!!!#*"$"$,$*$""##"""F)F*""!F',$F(# F+""',$F(#F)""$,$F(#!""F/#!"#F2#F+F2F16" } {RTABLE M7R0 I5RTABLE_SAVE/12705408X,%)anythingG6"6"[gl!"%!!!#1"%"%"""F'""!F(F'""#F'F'F'F'F' ""$F'F(F'F(6" } {RTABLE M7R0 I5RTABLE_SAVE/12710840X,%)anythingG6"6"[gl!"%!!!#1"%"%,$*$""##"""F)F*F'""!F,,$* $"#5F*#!""F/,$F.#F+F/,$F.#F+""&F4,$F.#F)"#:,$F.#!"#F9F-,$F.#""("#I,$F(#F+""$,$F (#F1FCF',$F(#F1""'6" } {RTABLE M7R0 I5RTABLE_SAVE/12714976X,%)anythingG6"6"[gl!"%!!!#1"%"%"""""!F(F(F(F'F(F(F(F(F'F (F(F(F(F'6" } {RTABLE M7R0 I5RTABLE_SAVE/12718716X,%)anythingG6"6"[gl!"%!!!#1"%"%"""""!F(F(F(F'F(F(F(F(F'F (F(F(F(F'6" } {RTABLE M7R0 I5RTABLE_SAVE/12720188X,%)anythingG6"6"[gl!"%!!!#1"%"%*$""##"""F(""!F+F+,$F'#"" $F(,$*$"#5F)F)F+F+F',$F0#""%""&,$F0#F.F5F+,$F'F),$F0#F*F1,$F0#F*"#I,$F'#F5""'6" } {RTABLE M7R0 I5RTABLE_SAVE/12723928X,%)anythingG6"6"[gl!"%!!!#1"%"%"""F'""!F(F'""#F'F'F'F'F' ""$F'F(F'F(6" } {RTABLE M7R0 I5RTABLE_SAVE/12725400X,%)anythingG6"6"[gl!"%!!!#'"$"#"""F'F'""#F'F(6" } {RTABLE M7R0 I5RTABLE_SAVE/12730604X,%)anythingG6"6"[gl!"%!!!#'"$"#,$*$""$#"""""##F+F)F'F',$ *$""'F*#F+F0,$F/#!""F)F.6" } {RTABLE M7R0 I5RTABLE_SAVE/12732972X,%)anythingG6"6"[gl!"%!!!#%"#"#"""""!F(F'6" } {RTABLE M7R0 I5RTABLE_SAVE/12735664X,%)anythingG6"6"[gl!"%!!!#*"$"$#"""""#""!F'F*F(F*F'F*F'6 " } {RTABLE M7R0 I5RTABLE_SAVE/12738080X,%)anythingG6"6"[gl!"%!!!#'"$"#"""F'F'""#F'F(6" } {RTABLE M7R0 I5RTABLE_SAVE/12740772X,%)anythingG6"6"[gl!"%!!!#%"#"#*$""$#"""""#""!,$F'#""&F( ,$*$""'F)#F*F(6" } {RTABLE M7R0 I5RTABLE_SAVE/12745732X,%)anythingG6"6"[gl!"%!!!#'"$"#"""F'F'""#F'F(6" }