Gram-Schmidt Orthogonalization - USM

1 Jim LambersMAT 415/515 Fall Semester 2013-14 Lecture 3 NotesThese notes correspond to Section in the OrthogonalizationWe have seen that it can be very convenient to have an orthonormal basis for a given vectorspace, in order to compute expansions of arbitrary vectors within that space. Therefore, given anon-orthonormal basis, it is desirable to have a process for obtaining an orthonormal basis from , we have such a process, known asGram-Schmidt Orthogonalization . Suppose thatwe have a linearly independent, but not orthonormal, set of functions{ 1, 2,..}that span a givenvector spaceV. To construct an orthonormal set{ 1, 2,..}from this set, we proceed as , to obtain 1, we simply normalize 1: 1= 1 1 .Next, to obtain 2, we need to ensure that it is orthogonal to 1, and then normalize an intermediate step, we seek a function 2of the form 2= 2+c12 1such that 1| 2 = 0. Then, we can set 2= 2/ 2 . Taking the scalar product of both sides ofthe above equation with 1, we obtain0 = 1| 2 = 1| 2 +c12 1| 1.

2 Because the jare orthonormal, it follows thatc12= 1| 2 .We conclude that 2can be obtained as follows: 2= 2 1| 2 1 2= 2 2 .We now have a set of two functions that is , to obtain 3, we must ensure that it is orthogonal to 1and 2, and then that end, we seek a function 3of the form 3= 3+c13 1+c23 2such that 1| 3 = 2| 3 = 0. Then, we can set 3= 3/ 3 . Taking the scalar product ofboth sides of the above equation with 1, and then separately, 2, we obtain0 = 1| 3 = 1| 3 +c13 1| 1 +c23 1| 2 0 = 2| 3 = 2| 3 +c13 2| 1 +c23 2| 2 .1 Because the jare orthonormal, it follows thatc13= 1| 3 , c23= 2| 3 .We conclude that 3can be obtained as follows: 3= 3 1| 3 1 2| 3 2 3= 3 3 .We now have a set of three functions that are this process, we see that we can obtain each function jas follows: j= j j 1 k=0 k| j k j= j j .This yields a set of functions{ 1, 2,..}that is an orthonormal basis of the space spanned by{ 1, 2,..}, with respect to the scalar product that is wish to obtain a set of orthonormal polynomials with respect to the scalar product f|g = 1 1f (s)g(s) will be accomplished by applying Gram-Schmidt Orthogonalization to the set{1,x,x2,x3.}

3 }.Setting j(x) =xjforj= 0,1,2,..,our orthogonal set{ j},j= 0,1,2,..,, is obtained as follows: 0(x) = 0(x)= 1, 0(x) = 0(x) 0 =1 1|1 1/2=1[ 1 11ds]1/2=1 2, 1(x) = 1(x) 0| 1 0(x)=x 1 2 x 1 2=x 12 1 1sds=x 120=x,2 1(x) = 1(x) 1 =x x|x 1/2=x[ 1 1s2ds]1/2= 32x, 2(x) = 2(x) 0| 2 0(x) 1| 2 1(x)=x2 1 2 x2 1 2 32x x2 32x=x2 12 1 1s2ds 32x 1 1s3ds=x2 1223 320=x2 13, 2(x) = 2(x) 2 =x2 13 x2 13 x2 13 1/2=x2 13[ 1 1(x 13)2ds]1/2= 52(32x2 12).Continuing this process, we obtain 3(x) = 72(52x3 32x).In general, n(x) = 2n+ 12Pn(x),wherePn(x) is theLegendre polynomialofnth degree. We will learn more about these orthogonal (but not orthonormal) polynomials later in this Gram-Schmidt Orthogonalization can be applied to themonomial bais{1,x,x2,x3,..}to obtain an orthonormal sequence of polynomials , it can be quite cumbersome, as can be seen fromthe preceding example. However, a modification of this procedure can yield a much more that we have already generated a sequence ofnorthonormal polynomials 0, 1, 2.

4 , n 1with respect to some scalar product f|g = baf (x)g(x)w(x)dx,3where jis of degreejforj= 0,1,2,..,n 1. Then, to obtain n, which of degreen, weorthogonalizex n 1(x), which is of degreen, against 0, 1,.., n 1using the same approach asin Gram-Schmidt Orthogonalization . That is, we compute n(x) =x n 1(x) n 1 j=0 j|x n 1 j(x), n(x) = n(x) n .Now, consider the scalar product j|x n 1 . Using the properties of the scalar product, wehave j|x n 1 = x j| n 1 .However, because 0, 1,.., n 1are orthonormal, p| n 1 = 0 ifp(x) isanypolynomial ofdegree less thann 1. Becausex j(x) is of degreej+ 1, it follows that j|x n 1 = 0 wheneverj+ 1< n 1, orj < n 2. Therefore, our Orthogonalization procedure simplifies to n(x) =x n 1(x) n 2|x n 1 n 2(x) n 1|x n 1 n 1(x), n(x) = n(x) n .That is, any family of orthogonal polynomials satisfies athree-term recurrence relation, in whicheach polynomial depends on the previous two.

5 Table lists several families of orthogonal polynomialsthat can be generated from such a recurrence relation; we will see some of these families later inthe ProductLegendre 1 1Pn(x)Pm(x)dx= 2 mn/(2n+ 1)Shifted legendre 10P n(x)P m(x)dx= mn/(2n+ 1)Chebyshev, first kind 1 1Tn(x)Tm(x)(1 x2) 1/2dx= mn /(2 n0)Shifted Chebyshev, first kind 10T n(x)T m(x)[x(1 x)] 1/2dx= mn /(2 n0)Chebyshev, second kind 1 1Un(x)Um(x)(1 x2)1/2dx= mn /2 Leguerre 0Ln(x)Lm(x)e xdx= mnAssociated Laguerre 0 Lkn(x)Lkm(x)e xdx= mn(n+k)!/n!Hermite Hn(x)Hm(x)e x2dx= 2n mn n!As can be seen in the following example, Gram-Schmidt Orthogonalization can be applied tovectors inanyinner product space, such as vectors the vectors inR3,|a1 = 11 2 ,|a2 = 12 3 ,|a3 = 011 ,we will use Gram-Schmidt Orthogonalization to obtain an orthonormal set of vectors,{|b1 ,|b2 ,|b3 }.We have|b1 =|a1 a1|a1 1/24=161/2|a1 =1 6 11 2 ,|b 2 =|a2 b1|a2 |b1 = 12 3 9 61 6 11 2 = 1/21/20 ,|b2 =|b 2 b 2|b 2 1/2=1(12)1/2|b 2 =1 2 110 ,|b 3 =|a3 b1|a3 |b1 b2|a3 |b2 = 011 ( 1 6)1 6 11 2 1 21 2 110 = 011 +16 11 2 12 110 =23 111 ,|b3 =|b 3 b 3|b 3 1/2=1(43)1/2|b 3 =1 3 111.

6 We conclude that our orthonormal set of vectors is|b1 =1 6 11 2 ,|b2 =1 2 110 ,|b3 =1 3 111 .25