\include{style.htm} \include{head.m4} \head{4,Linear algebraic equations and QR decomposition} \strong{\i{Matrix allocation in different systems:}} \center
FortranCC++
\small parameter(nmax=100)\br dimension a(nmax,nmax) \br a(1,1)=1\br call my_sub(a,n,nmax) \xsmall \small float **a;\br a = (float **)malloc(n*sizeof(float *)); \br for ( i=0; i<n ; i++ )\br a[i] = (float *)malloc(n*sizeof(float)); \br a[0][0]=1; my_function(a,n); \xsmall \small A=new double*[m]; \br for(i=0; i<m; i++)\br A[i]=new double[n];\br a[0][0]=1; my_function(A,n); \xsmall
\xcenter \br\strong{\i{QR decomposition and back-substitution.}} 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\^{T}Q~=~\b{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 determinats; linear least-squares fits; and diagonalization of matrices. \br\br \strong{\i{Gram-Schmidt orthogonalization}} is a method to perform QR decomposition of a matrix A by orthogonalization of its column-vectors \b{a}\^{(i)}:
do i=1, m
   R\_{i,i}=\sqrt{\b{a}\^{(i)}\dot\b{a}\^{(i)}}; \b{q}\^{(i)}=\b{a}\^{(i)}/R\_{i,i}  #normalization
   do j=i+1,m
      R\_{i,j}=\b{q}\^{(i)}\cdot\b{a}\^{(j)}; \b{a}\^{(j)}=\b{a}\^{(j)}-\b{q}\^{(i)}R\_{i,j}  #orthogonalization
The matrix Q made of columns \b{q}\^{(i)} is orthogonal, R is right triangular and A~=~QR. \p \strong{\i{QR back-substitution}} is a method to solve the linear system QR~x~=~b by transforming it into a triangular system R~x~=~Q\^{T}~b
b = Q\^{T}b
for i = m: -1: 1
	x\_{i} = (b\_{i} - \sum{k=i+1,m} R\_{i,k} x\_{k})/R\_{i,i}
\p\strong{\i{Determinant}} det(A)~=~\pm~Π\_{ i=1,m }(R\_{i,i}) \p \strong{\u{Problems}} \ol \li Find out how a matrix can be allocated, accessed and passed as a parameter in your programming language. \li Implement a function for QR decomposition by a modified Gram-Schmidt method. \li Implement a function for QR back-substitution. \li Implement a function to calculate determinant of a matrix. \li Non-obligatory: implement pivoting. \xol \include{footer.m4}