Modified Gram-Schmidt Orthogonalization in Matlab
Without any ado at all, I present Matlab 6.5 code to do Modified Gram-Schmidt Orthogonalization, otherwise known as QR Factorization. You can use a QR factorization to compute a number of things, the least of which is the least squares solution, which can be computed in the following manner:
- Start with Ax ~= b, where A is mxn, m > n (overdetermined system)
- Compute A = Q * [R O]^T^, where Q is an orthogonal mxn matrix and R is an nxn upper triangular matrix
- Multiply Q^T^ * b to find new right hand side [c1 … cn]^T^
- Use back-substitution to solve R * x = [c1 … cn]^T^ for x
Great!! Now you can find your own best fit lines. Here’s the QR factorization algorithm:
function [q, r] = QR(A)
[m, n] = size(A);
q = zeros(m, n);
r = zeros(n, n);
for k = 1:n
r(k,k) = norm(A(1:m, k));
if r(k,k) == 0
break;
end
q(1:m, k) = A(1:m, k) / r(k,k);
for j = k+1:n
r(k, j) = dot(q(1:m, k), A(1:m, j));
A(1:m, j) = A(1:m, j) - r(k, j) * q(1:m, k);
end
end
This entry was posted on Saturday, October 16th, 2004 at 5:50 pm and is tagged with nbsp nbsp nbsp nbsp nbsp, squares solution, qr factorization, least squares, gram schmidt, orthogonalization, back substitution, zeros, best fit, orthogonal, matlab, algorithm, norm, cn, matrix. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback.
on May 9th, 2005 at 4:35 pm
??? Index exceeds matrix dimensions.
on July 3rd, 2005 at 6:41 am
function Q = mgs(A)
n = size(A,2);
Q = A;
for k = 1:n-1,
Q(:,k) = A(:,k) ./ norm(A(:,k));
A(:,k+1:n) = A(:,k+1:n) - Q(:,k) * (Q(:,k)’ * A(:,k+1:n));
end;
Q(:,n) = A(:,n) ./ norm(A(:,n));
on January 21st, 2008 at 6:10 am
Can this Modified Gram-Schmidt Orthogonalization be applicable to linearly dependent vectors ?
on January 21st, 2008 at 10:09 am
Yes, but it won’t give anything useful to you; you’ll end up with output like an identity matrix.