maths.qr_decomposition

Functions

qr_householder(a)

Return a QR-decomposition of the matrix A using Householder reflection.

Module Contents

maths.qr_decomposition.qr_householder(a: numpy.ndarray)

Return a QR-decomposition of the matrix A using Householder reflection.

The QR-decomposition decomposes the matrix A of shape (m, n) into an orthogonal matrix Q of shape (m, m) and an upper triangular matrix R of shape (m, n). Note that the matrix A does not have to be square. This method of decomposing A uses the Householder reflection, which is numerically stable and of complexity O(n^3).

https://en.wikipedia.org/wiki/QR_decomposition#Using_Householder_reflections

Arguments: A – a numpy.ndarray of shape (m, n)

Note: several optimizations can be made for numeric efficiency, but this is intended to demonstrate how it would be represented in a mathematics textbook. In cases where efficiency is particularly important, an optimized version from BLAS should be used.

>>> A = np.array([[12, -51, 4], [6, 167, -68], [-4, 24, -41]], dtype=float)
>>> Q, R = qr_householder(A)
>>> # check that the decomposition is correct
>>> np.allclose(Q@R, A)
True
>>> # check that Q is orthogonal
>>> np.allclose(Q@Q.T, np.eye(A.shape[0]))
True
>>> np.allclose(Q.T@Q, np.eye(A.shape[0]))
True
>>> # check that R is upper triangular
>>> np.allclose(np.triu(R), R)
True