QR decomposition with Gramm-Schmidt orthogonalization Python

Given a Gramm-Schmidt orthogonalization of a matrix A, the QR decomposition of A can be easily obtained.

Here the Q part is computed by Q = gramm(A) and the R part is computed by R = Q^t (A) and the original matrix A can be computed from the product A = QR , where Q is an orthogonal matrix and R is upper triangular matrix. Q satisfies QQ^t = Q^t Q=I .

For more information on the QR decomposition, consult
http://en.wikipedia.org/wiki/QR_decomposition

Here is a Python implementation using the gramm() function introduced in an earlier blog.

?View Code PYTHON
"""
File    qr.py
Author  Ernesto P. Adorio, Ph.D.
        U.P. Clarkfield, Pampanga
Version 0.0.1  2009.01.16 first version.
"""
 
from matlib import *
from gramm import gramm
 
 
def qr(A, method="gramm"):
    # Performs a QR decomposition of A
    # default is via gramm-schmidt orthogonalization.
    if method == "gramm":
       Q = gramm(A)
       R = matprod(transpose(Q),A)
    return Q,R
 
if __name__ == "__main__":
   A =[[12, -51, 4],
       [6, 167, -68],
       [-4, 24, -41]] 
 
   print "A:"
   matprint (A)
 
   Q,R = qr(A)
   print "Q:"
 
   matprint (Q)
   print "R:"
   matprint (R)
 
   print "QR:"
   matprint(matprod(Q,R))
 
 
</code>

When the above contents is saved in a file and run, it outputs

toto@toto-laptop:~/Projects/python/book$ python qr.py
A:
 12.0000 -51.0000   4.0000
  6.0000 167.0000 -68.0000
 -4.0000  24.0000 -41.0000
Q:
  0.8571  -0.3943  -0.3314
  0.4286   0.9029   0.0343
 -0.2857   0.1714  -0.9429
R:
 14.0000  21.0000 -14.0000
 -0.0000 175.0000 -70.0000
 -0.0000  -0.0000  35.0000
QR:
 12.0000 -51.0000   4.0000
  6.0000 167.0000 -68.0000
 -4.0000  24.0000 -41.0000
toto@toto-laptop:~/Projects/python/book$ python qr.py
A:
 12.0000 -51.0000   4.0000
  6.0000 167.0000 -68.0000
 -4.0000  24.0000 -41.0000
Q:
  0.8571  -0.3943  -0.3314
  0.4286   0.9029   0.0343
 -0.2857   0.1714  -0.9429
R:
 14.0000  21.0000 -14.0000
 -0.0000 175.0000 -70.0000
 -0.0000  -0.0000  35.0000
QR:
 12.0000 -51.0000   4.0000
  6.0000 167.0000 -68.0000
 -4.0000  24.0000 -41.0000
toto@toto-laptop:~/Projects/python/book$

Note that the original matrix A has been recovered from its QR factorization.

Hence we are confident that the Python implementation works as written. Next we show how to solve the least squares problem using the QR decomposition (which currently uses the Gramm-Schmidt orthogonalization).

3 Responses to “QR decomposition with Gramm-Schmidt orthogonalization Python”

  1. ernie Says:

    This works also for non-square matrices. For example:
    X:
    1.0000 1.0000
    1.0000 2.0000
    1.0000 3.0000
    1.0000 4.0000
    Q:
    0.5000 -0.6708
    0.5000 -0.2236
    0.5000 0.2236
    0.5000 0.6708
    R:
    2.0000 5.0000
    0.0000 2.2361
    QR:
    1.0000 1.0000
    1.0000 2.0000
    1.0000 3.0000
    1.0000 4.0000

  2. Carrie Says:

    I am adding this page to my bookmarks. I look forward to future articles. TY

  3. Solving least squares problem with the QR decomposition. · Digital explorations Says:

    [...] The qr.py code can be copied from /?p=185 [...]

Leave a Reply