Home > K25104 > LinearSystems > Gram_Schmidt.m

Gram_Schmidt

PURPOSE ^

Computes the QR factorization of A via the Gram-Schmidt process

SYNOPSIS ^

function [ Q,R ] = Gram_Schmidt( A )

DESCRIPTION ^

 Computes the QR factorization of A via the Gram-Schmidt process
 Input arguments:
   A, matrix
 Output arguments:
   Q, orthogonal matrix
   R, upper triangular matrix

CROSS-REFERENCE INFORMATION ^

This function calls: This function is called by:

SOURCE CODE ^

0001 function [ Q,R ] = Gram_Schmidt( A )
0002 % Computes the QR factorization of A via the Gram-Schmidt process
0003 % Input arguments:
0004 %   A, matrix
0005 % Output arguments:
0006 %   Q, orthogonal matrix
0007 %   R, upper triangular matrix
0008 
0009 [n,m]=size(A);  % finding the size of A
0010 Q = zeros(n,n); % preallocating matrices R and Q
0011 R = zeros(n,m);
0012 
0013 k=0;    % initializing k to zero
0014 for j=1:m
0015     if k==0;
0016         w=A(:,j);   % initially take w to be the first column of A
0017     else
0018         w=A(:,j);
0019         for i=1:k;
0020             % by this construction w is orthogonal to first k columns of Q
0021             w=w-(Q(:,i)'*A(:,j))*Q(:,i); 
0022         end
0023     end                          
0024     
0025     % if |w| is zero then no new column of Q is constructed
0026     if abs(w)<1e-12;
0027         if abs(A(:,j))<1e-12;
0028             R(:,j)=0;
0029         else
0030             for i=1:k;
0031                 R(i,j)=(Q(:,i)'*A(:,j));
0032             end
0033             for i=k+1:n;
0034                 R(i,j)=0;
0035             end
0036         end
0037     else
0038         k=k+1;  % increment k
0039         Q(:,k)=w/sqrt(w'*w);   
0040         for i=1:k-1;
0041             R(i,j)=(Q(:,i)'*A(:,j));
0042         end
0043         R(k,j)=sqrt(w'*w);
0044         for i=k+1:n;
0045             R(i,j)=0;
0046         end
0047     end
0048 end
0049 
0050 % if k<n then we need to construct more columns for Q
0051 if k<n;         
0052     for i=k+1:n;
0053         % Find row of Q where the row sum is less than 1
0054         S = sum(Q,2);
0055         j=1;
0056         while S(j) >= 1
0057             j=j+1;
0058         end
0059         % construct new column from j-th standard unit vector
0060         x=zeros(n,1);
0061         x(j) = 1;
0062         for j=1:i;
0063             x=x-(x'*Q(:,j))*Q(:,j);
0064         end
0065         x=x/sqrt(x'*x); % normalize
0066         Q(:,i)=x;
0067     end
0068 end
0069 
0070 end
0071         
0072 
0073 
0074     
0075     
0076             
0077

Generated on Mon 18-Jan-2016 10:25:49 by m2html © 2005