Gram-Schmidt Orthogonalization Process

1 Gram-Schmidt Orthogonalization ProcessP. Sam JohnsonNovember 16, 2014P. Sam Johnson (NITK) Gram-Schmidt Orthogonalization ProcessNovember 16, 20141 / 31 DefinitionLet V be an inner product space, x,y V . Let A,B be subsets of V . x,y = 0(we write x y)x and y areorthogonalto each otherx y for every pair of distinct vectorsx,y in AA isorthogonalA is orthogonal and every vector in A hasnorm1A isorthonormalevery vector in A is orthogonal to everyvector in BA isorthogonalto BDefinitionLet S be a subspace of an inner product space. We say that B is anorthogonal basis(resp. anorthonormal basis) of S if B is a basis of Sand B is an orthonormal (resp.)

2 An orthonormal) Sam Johnson (NITK) Gram-Schmidt Orthogonalization ProcessNovember 16, 20142 / 31 TheoremEvery inner product space has an orthogonal (orthonormal) by selecting any nonzero vectorv1inV. IfVcontains anonzero vectorv2that is orthogonal tov1, put it in the basis. IfVcontainsa nonzero vectorv3that is orthogonal tov1andv2, put it in the in this way. The chosen pointsv1,v2, ..will be mutuallyorthogonal. The generated set is an orthogonal set, which is also a linearlyindependent. Thus, ifVisndimensional, the selection Process certainlymust stop after n each vectorviis normalized, then the set is anorthonormalbasis a vectorvmeans replacingvbyv/ v.

3 The norm of a vectoris derived from the inner product : x = x,x .A concrete realilzation of a Process similar to the one just described is theGram- schmidt Process . It operates in any finite dimensional innerproduct space and produces an orthonormal Sam Johnson (NITK) Gram-Schmidt Orthogonalization ProcessNovember 16, 20143 / 31 Little information about Erhard SchmidtErhard schmidt (1876-1959) was another importantmathematician who serves as a professor of mathe-matics in several German universities. His advisor wasDavid Hilbert (who formulated the theory of Hilbertspaces). schmidt became an expert in the eigen func-tions that arise in the study of integral equations andpartial differntial equations, and he was one of thefirst to make use of infinite dimensional vector spacesin his SchmidtHe introduced the notation.

4 For the magnitude of a vector, x,y forthe inner product. He proved the Phythagorean theorem in abstract innerproduct spaces and many other results in this subject while it was in itsinfancy and new to almost all mathematicians. In a 1907 paper, Schmidtdescribed what is now called theGram- schmidt Sam Johnson (NITK) Gram-Schmidt Orthogonalization ProcessNovember 16, 20144 / 31 Little information about Jorgen Pedersen GramJorgen Pedersen gram (1850-1916) published his first importantmathematical paper while still a university student! Rather than teachingmathematics at a university he became a research mathematicianemployed by an insurance company.

5 He published papers, gave lectures,and won awards for his mathematical research. At the age of 65, Gramwas killed after being struck by a Pedersen GramP. Sam Johnson (NITK) Gram-Schmidt Orthogonalization ProcessNovember 16, 20145 / 31 Gram-Schmidt AlgorithmSuppose{v1,v2, .. ,vn}is a basis of an inner product spaceV. For thefrst step, we definew1to be the normalized version ofv1; that is,w1=v1/ v1 .For an inductive definition, suppose that we have constructed anorthonormal systemw1,w2, .. ,wk 1whose span is the same as spanspan{v1,v2, .. ,vk 1}. To getwk, subtract fromvkits projection on thespan of{w1,w2, .. ,wk 1}, and then normallize formula for this Process iswk=vk k 1j=1 vk,wj wj vk k 1j=1 vk,wj wj (k= 2,3.)

6 ,n).In this algorithm, the vectors are normalized as we go along. The newbasis has the property that for eachk n,span{w1,w2, .. ,wk}= span{v1,v2, .. ,vk}.P. Sam Johnson (NITK) Gram-Schmidt Orthogonalization ProcessNovember 16, 20146 / 31 Unnormalized Gram-Schmidt AlgorithTheoremLet{v1,v2, .. ,vn}be a basis of a subspace S of an inner product spaceV . Define z1,z2, .. ,zk, .. ,zninductively by :zk=vk k 1 j=1 vk,zj zj,zj zj(k= 1,2, .. ,n).Then z1,z2, .. ,znis anorthogonal basisof S .An orthonormal basis of V can be obtained by normalizing the zi from any basis of an inner product spaceV, we can construct anorthonormal basis by the Gram-Schmidt Process :Everyfinite-dimensional inner product space has an orthonormal Sam Johnson (NITK) Gram-Schmidt Orthogonalization ProcessNovember 16, 20147 / 31An Advantage in Unnormalized Gram-Schmidt AlgorithmThe main difference between the algorithms for thewk(normalized) andzk(unnormalized) is that the vectorswkare normalized after each step,where thezkare not.

7 Hence, they remain unnormalized! Avoiding thecalculation of square root is another hand calculations, it is easier to construct an orthonormal basis by firstconstructing an orthogonal basis and then normalizing the vectors all atonce at the few slides are showing the Gram-Schmidt Orthogonalization processin plane and Sam Johnson (NITK) Gram-Schmidt Orthogonalization ProcessNovember 16, 20148 / 31 Gram-Schmidt Process in planeP. Sam Johnson (NITK) Gram-Schmidt Orthogonalization ProcessNovember 16, 20149 / 31 Gram-Schmidt Process in planeP. Sam Johnson (NITK) Gram-Schmidt Orthogonalization ProcessNovember 16, 201410 / 31 Gram-Schmidt Process in planeP.

8 Sam Johnson (NITK) Gram-Schmidt Orthogonalization ProcessNovember 16, 201411 / 31 Gram-Schmidt Process in planeP. Sam Johnson (NITK) Gram-Schmidt Orthogonalization ProcessNovember 16, 201412 / 31 Gram-Schmidt Process in planeP. Sam Johnson (NITK) Gram-Schmidt Orthogonalization ProcessNovember 16, 201413 / 31 Gram-Schmidt Process in planeP. Sam Johnson (NITK) Gram-Schmidt Orthogonalization ProcessNovember 16, 201414 / 31 Gram-Schmidt Process in spaceP. Sam Johnson (NITK) Gram-Schmidt Orthogonalization ProcessNovember 16, 201415 / 31 Gram-Schmidt Process in spaceP. Sam Johnson (NITK) Gram-Schmidt Orthogonalization ProcessNovember 16, 201416 / 31 Gram-Schmidt Process in spaceP.

9 Sam Johnson (NITK) Gram-Schmidt Orthogonalization ProcessNovember 16, 201417 / 31 Gram-Schmidt Process in spaceP. Sam Johnson (NITK) Gram-Schmidt Orthogonalization ProcessNovember 16, 201418 / 31 Gram-Schmidt Process in spaceP. Sam Johnson (NITK) Gram-Schmidt Orthogonalization ProcessNovember 16, 201419 / 31 Gram-Schmidt Process in spaceP. Sam Johnson (NITK) Gram-Schmidt Orthogonalization ProcessNovember 16, 201420 / 31 Gram-Schmidt Process in spaceP. Sam Johnson (NITK) Gram-Schmidt Orthogonalization ProcessNovember 16, 201421 / 31 Gram-Schmidt Process in spaceP. Sam Johnson (NITK) Gram-Schmidt Orthogonalization ProcessNovember 16, 201422 / 31 Generalized Gram-Schmidt ProcessLetx1,x2.

10 ,xsbe a given vectors inV, not necessarily 1:Setk= 2:Computezk=xk k 1j=1 xk,yj 3:Computeyk:=zk zk or 0 according aszk6= 0 orzk= 4:Ifk<s, increasekby 1 and go to Step 2. Otherwise go toStep 5:Fori= 1,2, .. ,s, the setBiof all non-null vectorsamongy1,y2, .. ,yiis an orthonormal basis of the spanSiof{x1,x2, ,xi}.Ifx1,x2, .. ,x`form an orthonormal set thenyj=xjforj= 1,2, .. , `.P. Sam Johnson (NITK) Gram-Schmidt Orthogonalization ProcessNovember 16, 201423 / 31 TheoremLet S be a subspace of a finite-dimensional inner product space V . Anyorthonormal subset of S can be extended to an orthonormal basis of S . {x1,x2.}