## 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$ .

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

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: