## 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 and the R part is computed by and the original matrix A can be computed from the product , where Q is an orthogonal matrix and R is upper triangular matrix. Q satisfies .

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).

January 16th, 2009 at 12:00 pm

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

February 9th, 2009 at 4:24 pm

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

May 9th, 2011 at 10:26 pm

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