The QR decomposition, also known as the QR factorization, is another method of solving linear systems of equations using matrices, very much like the LU decomposition. The equation to solve is in the form of 
, where matrix 
. Except in this case, A is a product of an orthogonal matrix Q and upper triangular matrix R. The QR algorithm is commonly used to solve the linear least squares problem.
An orthogonal matrix exhibits the following properties:
- It is a square matrix
- Multiplying an orthogonal matrix by its transpose returns the identity matrix:
- The inverse of an orthogonal matrix equals its transpose:
An identity matrix is also a square matrix with its main diagonal containing ones and zeros elsewhere.
We can now restate the problem as follows:
Using the same variables in the LU decomposition example, we will use the qr function of scipy.linalg to compute our values of Q and R, and let the variable y represent our value of 
with the following code:
""" QR decomposition with scipy """
import scipy.linalg as linalg
import numpy as np
A = np.array([
[2., 1., 1.],
[1., 3., 2.],
[1., 0., 0]])
B = np.array([4., 5., 6.])
Q, R = scipy.linalg.qr(A) # QR decomposition
y = np.dot(Q.T, B) # Let y=Q'.B
x = scipy.linalg.solve(R, y) # Solve Rx=yNote that Q.T is simply the transpose of Q, which is also the same as the inverse of Q.
>>> print x [ 6. 15. -23.]
We get the same answers similar to those in the LU decomposition example.
So far, we have looked at the use of matrix inversion, the LU decomposition, the Cholesky decomposition, and QR decomposition to solve for systems of linear equations. Should the size of our financial data in matrix A be large, it can be broken down by a number of schemes so that the solution can converge more quickly using matrix algebra. Quantitative portfolio analysts ought to be familiar with these discussed methods.
In some circumstances, the solution that we are looking for might not converge. Therefore, one might consider the use of iterative methods. The common methods of solving systems of linear equations iteratively are the Jacobi method, the Gauss-Seidel method, and the SOR method. We will take a brief look at the examples in implementing the Jacobi and the Gauss-Seidel method.
The Jacobi method solves a system of linear equations iteratively along its diagonal elements. The iteration procedure terminates when the solution converges. Again, the equation to solve is in the form of , where A can be decomposed into a diagonal component D and remainder R such that 
. Let's take a look at the example of a 4 by 4 matrix A:
The solution is then obtained iteratively as follows:
As opposed to the Gauss-Siedel method, the value of 
in the Jacobi method is needed during each iteration in order to compute 
and cannot be overwritten. This would take up twice the amount of storage. However, the computations for each element can be done in parallel, which is useful for faster computations.
If matrix A is strictly irreducibly diagonally dominant, this method is guaranteed to converge. A strictly irreducibly diagonally dominant matrix is one where the absolute diagonal element in every row is greater than the sum of the absolute values of other terms.
In some circumstances, the Jacobi method can converge even if these conditions are not met. The Python code is given as follows:
""" Solve Ax=B with the Jacobi method """
import numpy as np
def jacobi(A, B, n, tol=1e-10):
# Initializes x with zeroes with same shape and type as B
x = np.zeros_like(B)
for it_count in range(n):
x_new = np.zeros_like(x)
for i in range(A.shape[0]):
s1 = np.dot(A[i, :i], x[:i])
s2 = np.dot(A[i, i + 1:], x[i + 1:])
x_new[i] = (B[i] - s1 - s2) / A[i, i]
if np.allclose(x, x_new, tol):
break
x = x_new
return xConsider the same matrix values in the Cholesky decomposition example. We will use 25 iterations in our jacobi function to find the values of 
.
A = np.array([[10., -1., 2., 0.],
[-1., 11., -1., 3.],
[2., -1., 10., -1.],
[0.0, 3., -1., 8.]])
B = np.array([6., 25., -11., 15.])
n = 25After initializing the values, we can now call the function and solve for x:
>>> x = jacobi(A, B, n) >>> print "x =", x x = [ 1. 2. -1. 1.]
We solved for the values of , which are similar to the answers from the Cholesky decomposition.
The Gauss-Seidel method works very much like the Jacobi method. It is another way of solving a square system of linear equations using an iterative procedure with the equation in the form of . Here, the matrix A is decomposed as 
, where the matrix A is a sum of a lower triangular matrix L and an upper triangular matrix U. Let's take a look at the example of a 4 by 4 matrix A:
The solution is then obtained iteratively as follows:
Using a lower triangular matrix L, where zeroes fill up the upper triangle, the elements of can be overwritten in each iteration in order to compute . This results in the advantage of needing half the storage required when using the Jacobi method.
The rate of convergence in the Gauss-Seidel method largely lies in the properties of matrix A, especially if matrix A is needed to be strictly diagonally dominant or symmetric positive definite. Even if these conditions are not met, the Gauss-Seidel method may converge.
The Python implementation of the Gauss-Seidel method is given as follows:
""" Solve Ax=B with the Gauss-Seidel method """
import numpy as np
def gauss(A, B, n, tol=1e-10):
L = np.tril(A) # Returns the lower triangular matrix of A
U = A - L # Decompose A = L + U
L_inv = np.linalg.inv(L)
x = np.zeros_like(B)
for i in range(n):
Ux = np.dot(U, x)
x_new = np.dot(L_inv, B - Ux)
if np.allclose(x, x_new, tol):
break
x = x_new
return x Here, the tril function of NumPy returns the lower triangular matrix A from which we can find the lower triangular matrix U. Plugging the remaining values into iteratively would lead us to the solution below with some tolerance defined by tol.
Let's consider the same matrix values in the Jacobi method and Cholesky decomposition example. We will use a maximum of 100 iterations in our guass function to find the values of as follows:
A = np.array([[10., -1., 2., 0.],
[-1., 11., -1., 3.],
[2., -1., 10., -1.],
[0.0, 3., -1., 8.]])
B = np.array([6., 25., -11., 15.])
n = 100
x = gauss(A, B, n) Let's see if our x values match with those as before:
>>>print "x =", x x = [ 1. 2. -1. 1.]
We solved for the values of , which are similar to the answers from the Jacobi method and Cholesky decomposition.