MAT208Gram-Schmidt ProcessFall 2009Orthonormal Basis• Let S = { v1, v2, …, vn} be a basis for an inner product space V. Then S is an orthonormal basis for V if a) (vi, vj) = 0 for i ≠ jb) (vi, vi) = 1 for all iTheoremLet S = { v1, v2, …, vn} be an orthonormal basis for an inner product space V and let v be any vector in V. Then v = c1v1+ c2v2+ … + cnvnwhere ci= ( v,vi) for all i1 1 2 21 1 2 21 1 2 212,,, , , ,, , , ,0 0 1 0nni i i inni i i i i inni i i i i iniic c c cc c c cc c c cc c c ccv v v v v v vv v v v v v v vv v v v v v v vProof -Gram-Schmidt Process• There is more at issue here than just convenience in computing coefficients. Orthogonal bases can make computations more numerically stable.• If S = { u1, u2, …, un} is a basis (not orthonormal) for an inner product space V, is there a way to convert it to an orthonormal basis?Gram-Schmidt Process• Replace the basis with an orthonormal basis1 2 31 1 2S , , 0 , 0 , 1100u u u1 2 3,,w w w11 1 1 112012v u w v v2 2 1 2 11 1 2 1 21, 0 0 020 1 212v u w u w2 2 212012w v vGram-Schmidt ProcessExample (continued)3 3 3 1 1 3 2 2,,2 1 2 1 2 01 2 0 2 0 1001 2 1 2v u u w w u w w1 2 1 2 00 , 0 , 101 2 1 2Orthonormal set is3 3 3010w v vComments• Key idea in Gram-Schmidt is to subtract from every new vector, uk, its components in the directions already determined, {v1,v2, …, vk–1} • When doing Gram-Schmidt by hand, it simplifies the calculation to multiply the newly computed vkby an appropriate scalar to clear fractions in its components. The resulting vectors are normalized at the end of the computationQR Factorization• In the Gram-Schmidt example, the basis is transformed to Interpreting these vectors as column vectors of matrices, the following result holds1 1 20 , 0 , 11001 2 1 2 00 , 0 , 101 2 1 22 1 2 21 1 2 1 2 1 2 00 0 1 0 0 1 1 2 21 0 0 0 11 2 1 2A QRThis is called the QR-Factorization of AComments• Computer programs that compute the QR Factorization use an algorithm that is different from that of the proof, which is essentially Gram-Schmidt.• MATLAB’s implementation of QR-Factorization of an m x n matrix A returns an m x m matrix Qwith orthonormal columns and an m x n matrix R of the form The first n columns of Q form a basis for the column space of AandA = QR* * * *0 * * *0 0 *0 0 00 0 0RDefinitions• A square matrix Q that has orthonormal columns is called an orthogonal matrix• Because of the orthonormal columns,QTQ = I. Therefore Q–1=