Suppose we have a problem that can be modeled by the system of equations Ax = b with a matrix A and a vector b. We have already shown how to use Gaussian Elimination to solve these methods, but I would like to introduce you to another method – QR decomposition. In addition to solving the general system of equations, this method can also be used in a number of other algorithms including the linear regression analysis to solve the least squares problem and to find the eigenvalues of a matrix.

Generally, when we see a system of equations, the best way to proceed in solving it is Gaussian elimination, or LU decomposition. However, there are some very special matrices where this method can lead to rounding errors. In such cases, we need a better, or more stable algorithm, which is when the QR decomposition method becomes important.

Any matrix A, of dimensions m by n with m >= n, can be represented as the product of two matrices, an m by m orthogonal matrix Q, i.e. Q^TQ = I, and an m by n upper triangular matrix R with the form [R 0]^T. We perform this decomposition by will first converting the columns of the matrix A into vectors. Then, for each vector a_k, we will calculate the vectors u_k and e_k given by

u_k = _{i = 1 to k-1}proj_ej a_k
and
e_k = u_k / ||u_k||
Then Q = [e₁, …, e_n] and

R =	<e1, a1> <e1, a2> <e1, a3> 0 <e2, a2> <e2, a3> 0 0 <e3, a3>

Here is a link to the JavaScript program I wrote to show how QR Decomposition works.

Similar Posts:

• Gaussian Elimination
• The Gram-Schmidt Process and Orthogonal Vectors
• Covariance of Vectors
• The Assignment Problem
• Discrete-time Markov Chains