Gram-Schmidt process and QR factorization 3/8/2002 Math 21b, O. KnillHomework: Section 5.2, 2,14,16,34,40,42MOTIVATION. The Gram-Schmidt process is an algorithm to build from an arbitrary basis an orthonormalbasis. Why do we care to have an orthonormal basis?• The process of producing an orthonormal basis from a matrix A with column vectors ~vjwill be associatedto a factorization A = QR, which helps to solve linear equations. In physical problems like in astrophysics,the numerical methods to simulate the problems one needs to invert huge matrices in every time step ofthe evolution. (The reason why this is necessary sometimes is to assure the numerical method is stable(implicit methods)).• An orthonormal basis looks like the standard basis ~v1= (1, 0, ..., 0), . . . , ~vn= (0, 0, ..., 1). We actually willsee that one can turn an orthonormal basis into a standard basis or a mirror of the standard basis.• If A is written as A = QR, then the inverse of A can be found easier, because the inverse of Q and theinverse of R are easy to obtain. See later.• For many physical problems like in quantum mechanics or dynamics, matrices are symmetric A∗= A,where A∗ij= Aji. For such matrices, there is a natural orthonormal basis which has the nice property thatA~vi= λi~vi. The ~viwill be called eigenvectors and the λiare the eigenvalues. These objects will appearlater in the course.• The formula for the projection onto a linear subspace V simplifies with an orthonormal basis ~vjin V :projV(~x) = (~v1·~x) ~w1+ ··· + ( ~wn·~x) ~wn.• For practical reasons, having an orthonormal basis simplifies life - partly because the presence of manyzeros ~wj· ~wi= 0 makes computations easier. This is especially the case for problems with symmetry.• There is more behind the QR factorization: if we form A = QR in then A1= RQ, the new matrixA1= Q−1AQ shares many properties of A (like the eigenvalues about which we will learn in a few weeks).When iterating this procedure A → A1one is lead to interesting topics in differential equations (anexample is the Toda lattice).GRAM-SCHMIDT PROCESS.Let ~v1, ..., ~vnbe a basis. Let ~u1= ~v1and ~w1= ~u1/||~u1||. The Gram-Schmidt process recursively constructsfrom the already constructed orthonormal set ~w1, ..., ~wi−1which spans a linear space Vi−1the new vector~ui= (~vi− projVi−1(~vi)) which is orthogonal to Vi−1, and then normalizing ~uito to get ~wi= ~ui/||~ui||. Thevectors ~uiare orthogonal to the linear space Vi−1.EXAMPLE.Find an orthonormal basis for ~v1=200, ~v2=130and ~v3=125.SOLUTION.1. ~w1= ~v1/||~v1|| =100.2. ~u2= (~v2− projV1(~v2)) = ~v2− ( ~w1·~v2) ~w1, =030. ~w2= ~u2/||~u2|| =010.3. ~u3= (~v3− projV2(~v3)) = ~v3− ( ~w1·~v3) ~w1− ( ~w2·~v3) ~w2=005, ~w3= ~u3/||~u3|| =001.2. EXAMPLE.~v1=020~v2=202~v3=103leads toorthonormalbasis~w1=010~w2=1/√201/√2~w3=1/√20−1/√2QR FACTORIZATION.The formulas can be written as~v1= ||~v1||~w1= r11~w1···~vi= ( ~w1·~vi) ~w1+ ··· + ( ~wi−1·~vi) ~wi−1+ ||~ui||~wi= ri1~w1+ ··· + rii~wi···~vn= ( ~w1·~vn) ~w1+ ··· + ( ~wn−1·~vn) ~wn−1+ ||~un||~wn= rn1~w1+ ··· + rnn~wnwhich means in matrix formA =| | · |~v1··· · ~vm| | · |=| | · |~w1··· · ~wm| | · |r11r12· r1m0 r22· r2m0 0 · rmm= QRwhere A and Q are n × m matrices and R is a m ×m matrix.Any matrix A can be decomposed as A = QR, where Q has ascolumns orthonormal vectors and R is an upper triangular squarematrix.1. EXAMPLE. The matrix with the vectors ~v1, ~v2, ~v3is A =2 1 10 3 20 0 5.~v1= ||~v1||~w1~v2= ( ~w1·~v2) ~w1+ ||~u2||~w2~v3= ( ~w1·~v3) ~w1+ ( ~w2·~v3) ~w2+ ||~u3||~w3,so that Q =1 0 00 1 00 0 1and R =2 1 10 3 20 0 5.PRO MEMORIA.The matrix R has the ||~ui|| in the diagonal and the dot products [R]ij= ~wi·~vjin the upper right triangle.3. EXAMPLE. Make the QR decomposition of A =0 −11 1. ~w1=0−1. ~u2=−11−01=−10.~w2= ~u2. A =0 −11 01 10 1= QR.SOME HISTORY. The recursive formulae of the process were stated by Erhard Schmidt (1876-1959) in1907 Implicitly the essence of the formulae were in a 1883 paper of J.P.Gram in 1883 which Schmidt mentionsin a footnote. The process seems to be a result of Laplace (1749-1827). It was already also used by Cauchy(1789-1857) in 1836.GramSchmidtLaplace
View Full Document
Unlocking...