\include{style.htm}
\include{head.m4}
\head{4,Linear algebraic equations and QR decomposition}
\strong{\i{Matrix allocation in different systems:}}
\center
Fortran | C | C++ |
\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}