{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 "2D Math" -1 2 "Times" 0 1 0 0 0 0 0 0 2 0 0 0 0 0 0 1 }{CSTYLE "2D Comment" 2 18 "" 0 1 0 0 0 0 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 "Title" 0 18 1 {CSTYLE "" -1 -1 "" 1 18 0 0 0 0 0 1 1 0 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 0 }3 0 0 -1 8 8 0 0 0 0 0 0 -1 0 }} {SECT 0 {EXCHG {PARA 18 "" 0 "" {TEXT -1 40 "Orthogonal Projections an d Least Squares" }}{PARA 19 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "with(stats): with(LinearAlgebra):with(linalg) :" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 547 "Suppose \{u_1, ..., u_n\} is an orthonormal basis f or an inner product space V. Then it can be shown (check this is true ) that every element of V can be written as a linear combination of t he form v=(v,u_1) u_1 + ... + (v,u_n) u_n . If W is the subspace f ormed by the first k vectors of the basis (which in our notation means W=Span(\{u_1, ..., u_k\}) then the linear combination we've given c an be viewed in two parts: The sum of the first k terms (called the o rthogonal projection of v onto W) and then the sum of the remaining n- k terms. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 96 "In R_2, we use the GramSchmidt procedure to change u=<1,-1>, v =<1,2> to an orthornormal basis. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 67 "u:=<1,-1>;v:=<1,2>;A:=Linear Algebra[GramSchmidt](\{u,v\},normalized);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 66 "Check that these vectors do form an orthonormal basis for V=R_2. " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 84 "U:=A[1];V:=A[2 ];DotProduct(U,V);DotProduct(U,U);DotProduct(V,V);Norm(U,2);Norm(V,2); " }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 754 "Next find the coordinates of the vector v=<1,3> with respect to the orthonormal basis you've just \+ constructed. Use that to find the projection of v onto the line which is the span of your first basis vector. One way to find the coordin ates is by making the vectors produced by GramSchmidt the columns of a matrix C, and then solving Cx=v which shows how to write v as a combi nation of the columns. (There is a little complication -- GramSchmidt \+ returned a list of vectors, we want to make them the columns of a matr ix. This list was called A, we want to make the j-th vector in the li st, A[j], the j-th column. That is effected by the (i,j)->A[j][i] bel ow. You'll have to vary the size of the matrix depending on the number and size of the vectors.)" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 53 "A;b:=<1,3>;LinearSolve(Matrix(2,2,( i,j)->A[j][i]),b);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 346 "Next let V =R_3 and let W=Span(\{<1,1,0>, <0,1,1>\}). Find an orthonormal basis \+ B for W and then use ideas from class to extend B to an orthonormal ba sis for V. \nCheck that your set is an orthonormal basis for V. Use L inearSolve to find the coordinates of v=<1,-2,3> with respect to your \+ orthonormal basis for v. Find the projection of v onto W. " }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }{TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }{TEXT -1 0 "" }}}{EXCHG {PARA 0 " " 0 "" {TEXT -1 1322 "Okay, now let's return to the information given \+ at the beginning. Let W=Span(\{u_1, ..., u_k\}) where the vectors f orm an orthonormal basis for W and let \{u_1, ..., u_n\} be the extens ion of this basis to an orthonormal basis for the inner product space \+ V. Then we know that every element of V can be written as a linear c ombination of the form v=(v,u_1) u_1 + ... + (v,u_n) u_n, that is, the coordinates of v with respect to this orthonormal basis have the spec ial form < (v,u_1), ... ,(v,u_n) >. (Be especially careful to sort o ut what's an inner product here.) Also, the first k coordinates of t he projection of v onto W are (v,u_1), ... ,(v,u_k) and the remaining coordinates are zero. This observation gives an easier way to obtain this projection when W is a subspace of R_n and the inner product is \+ the dot product. Form the n by k matrix A in which the j-th column \+ is u_j, the j-th vector in our orthonormal basis for W. Then from the definition of matrix multiplication you know that the i-th entry in \+ the matrix-vector product Transpose(A)v is the dot product of the vec tor u_i with v, and so gives the i-th coordinate of v with respect to \+ the basis. Multiplying on the left by A gives the sum of the columns t imes the corresponding coefficients. This is exactly the projection of v on W. Thus " }{XPPEDIT 18 0 "Pv = A*A^t*v;" "6#/%#PvG*(%\"AG\" \"\")F&%\"tGF'%\"vGF'" }{TEXT -1 40 ", where A is the matrix described above." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 " " 0 "" {TEXT -1 896 "Suppose A is an m by n matrix, and the associated matrix function T(x)=Ax is a linear transformation which maps R_n int o R_m. Also, a vector b is in the column space of A if and only if Ax =b has a solution. (This is the same as saying that b is in the Range (T).) Rather than writing Range(T), let's refer to it as the subspace W. If the linear transformation is not onto, there are vectors in R_ m which are not in W. If b is such a vector, then we can never hope t o make Ax-b equal to zero. Using the dot product to define the lengt h, we can ask which values of x make Ax-b as small as possible. This \+ is the same as asking for an element Ax in W which is as close as poss ible to our vector b. The procedure that does this is called the Leas t-Squares Solution, or the Method of Best Approximation. For the formu lation below, we assume that the nullspace of T(x)=Ax is just the 0 \+ vector." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 124 "Let's do an example. For the matrix A and the vector b given bel ow, we first check that b is not in the column space of A. " }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 78 "A:=SubMatrix(HilbertMatrix(6 ,6),1..6,1..4); b:=<0,1,2,0,0,0>;LinearSolve(A,b);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 297 "So, setting W=ColumnSpace(A), we have just show n that b is not in W and we would like to find a solution X* for which AX*-b is as small as possible. This holds if AX* is the orthogonal \+ projection of b onto W, for the \"residual vector\" AX*-b must then b e orthogonal to every element of W. (If " }{XPPEDIT 18 0 "w*epsilon*W ;" "6#*(%\"wG\"\"\"%(epsilonGF%%\"WGF%" }{TEXT -1 4 " th" }{TEXT -1 773 "en ||w-b||^2 = ||w -AX* +AX* -b||^2 =||w-AX*||^2 +||AX*-b||^2 sin ce the vectors w-AX* and AX*-b are orthogonal. This is least when w= AX* and the first term in the last expression is equal to 0.) Remember that W is the column space of the matrix A, so the elements of W have the form AX, and since the nullspace of A is assumed to just be 0, th ere is just one X. Therefore, the fact that AX*-b is orthogonal to ev ery element of W means that for every X the dot product (AX, AX*-b) e quals zero. We can then write this requirement as a matrix equation: \+ Transpose(AX) (AX*-b)= 0, the zero matrix. From this we can do som e matrix operations to get that X* is a solution to the matrix equati on CX*= Transpose(A) b where C is the symmetric matrix C= Transpose (A) A. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 104 "Let's now find the Least Squares Solution to the equation AX=b fo r the matrix A and b just used above. " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 117 "A:=SubMatrix(HilbertMatrix(6,6),1..6,1..4): b:=<0,1, 2,0,0,0>:\nC:=Transpose(A).A; c:=Transpose(A).b; LinearSolve(C,c);" }} }{EXCHG {PARA 0 "" 0 "" {TEXT -1 136 "You should have invoked the stat s package above. There's a command in there which gives the Least Squ ares approximation in one command." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "LeastSquares(A,b);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 324 "You should have gotten the same answer. We want you to unders tand the linear algebra involved, but you can use the stats package as a good check of your work.\nNow find the best approximation to AX=b \+ for the same vector b, but change A to the submatrix which uses only t he first three columns of the 6 by 6 Hilbert matrix." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{MARK "18 0 3" 193 }{VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 }