\include{style.htm}
\include{head.m4}
\head{4,Linear algebraic equations and QR decomposition}


\strong{\i{Matrix allocation in different systems:}}
\center
<table border=0 cellpadding=5>
<tr align=center><td>Fortran</td><td>C</td><td>C++</td></tr>
<tr><td> \small
parameter(nmax=100)\br
dimension a(nmax,nmax) \br
a(1,1)=1\br
call my_sub(a,n,nmax)
\xsmall </td><td> \small
	float **a;\br
	a = (float **)malloc(n*sizeof(float *)); \br
	for ( i=0; i&lt;n ; i++ )\br
	a[i] = (float *)malloc(n*sizeof(float)); \br
	a[0][0]=1; my_function(a,n);
\xsmall </td><td> \small
A=new double*[m]; \br
for(i=0; i&lt;m; i++)\br A[i]=new double[n];\br
	a[0][0]=1; my_function(A,n);
\xsmall </tr></table>
\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)}:

<pre>
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
</pre>

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
<pre>
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}
</pre>

\p\strong{\i{Determinant}} det(A)~=~\pm~&Pi;\_{ 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}