e-mail:anina@EUnet.yu
LU decompisition reduces matrix to product of lower
triangular matrix L which diagonal elements are units and upper
triangular matrix U.If during the time of algoritm realization
permutations of matrix A are done we will get decomposition of
matrix P*A.We get matrix of permutation(P) by permutation
rows of unity matrix.Any non singular matrix A (or permutation
of matrix A)can be expressed as a product A=L*U (P*A=L*U).
Proces of calculation elements of matrices L and U can be different.
In Crout's method we calculate elements in first row of matrix U,
elements in first column of matrix L,elements in second row in matrix U,
elements in second column of matrix L... Algoritm for calculate of these
elements is folowing:
u(1,k)=a(1,k) k=i,...,n
u(i,k)=a(i,k)-(l(i,1)*u(1,k)+l(i,2)*u(2,k)+...+l(i.i-1)*u(i-1,k)) i=2,...,n
l(k,1)=a(k,1)\u(1,1) k=i+1,...n
l(k,i)=1\u(i,i)*((a(k,i)-(l(k,1)*u(1,i)+...+l(k,i-1)u(i-1,i)))
LU decomposition is useful,for the solution of the exactly determined
system linear equations A*x=b,when there is more then one right side b.
With LU=A the system can be showed as two triangular systems :
(1) L*y=b
(2) U*x=y
The first triangular system can be solwed by forward substitution:
y(1)=b(1)\l(1,1) i=2,3...,n
y(i)=1\l(i,i)*(b(i)-(l(i,1)*y(1)+...+l(i,i-1)*y(i-1))
The second triangular system can be solved by backward substitution.
x(n)=y(n)\u(n,n) i=n-1,...,1
x(i)=1\b(i,i)*(y(i)-(u(i,i+1)*x(i+1)+...+u(i,n)*x(n)))
The determinant of LU decomposed matrix is just the product of the diagonal
elements of matrix U.
Inverse matrix of matrix A(n*n) is solution of the system which right side is
n vectors columns of unity matrix.