Numerical methods. Note 2

[ Home ]

Linear algebraic equations

Numerical Methods. Note « 2 »

Matrix allocation in different systems:

Haskell	C	C++
a = [[i+j \| i <- [1..n] ] \| j <- [1..n]]	float a = (float )malloc(nsizeof(float )); for ( i=0; i<n ; i++ ) a[i] = (float )malloc(nsizeof(float)); a[0][0]=1; ...; QR(a,n); ...	A=new double*[m]; for(i=0; i<m; i++) A[i]=new double[n]; a[0][0]=1; ...; QR(A,n); ...

QR decomposition. A rectangular n-by-m matrix A has a QR decomposition, A = Q R, into the product of an orthogonal n-by-m matrix Q, Q^TQ = 1, and an m-by-m right-triangular matrix R. This decomposition can be used to convert the linear system A x = b into the triangular system R x = Q^T b, which can be solved by back-substitution. QR decomposition can be also used for calculating for linear least-squares fits and diagonalization of matrices.

Gram-Schmidt orthogonalization is a method to perform QR decomposition of a matrix A by orthogonalization of its column-vectors a⁽ⁱ⁾:

for i=1:m
	R_i,i=√(a⁽ⁱ⁾⋅a⁽ⁱ⁾); q⁽ⁱ⁾=a⁽ⁱ⁾/R_i,i  #normalization
	for j=i+1:m 
		R_i,j=q⁽ⁱ⁾⋅a^(j); a^(j)=a^(j)-q⁽ⁱ⁾R_i,j  #orthogonalization

The matrix Q made of columns q⁽ⁱ⁾ is orthogonal, R is right triangular and A = QR.

QR back-substitution is a method to solve the linear system QRx=b by transforming it into a triangular system Rx=Q^Tb

b = Q^Tb
for i = m: -1: 1
	x_i = (b_i - ∑_k=i+1,m R_i,k x_k)/R_i,i

LU decomposition is the decomposition of a matrix A into a product of a lower triangular matrix L and an upper triangular matrix U, A = LU. The equation Ax=b, ie LUx=b, can then be solved by first solving for Ly=b and then for Ux=y by two runs of backward and forward substitutions.

Determinant of a triangular matrix is a product of its diagonal elements.

Problems

Find out how a matrix can be allocated, accessed and passed as a parameter in your programming language.
Implement a function for QR decomposition by a modified Gram-Schmidt method.
Implement a function for QR back-substitution.
Non-obligatory: implement pivoting.
Non-obligatory: implement LU decomposition.