We already studied two numerical methods of finding the solution to simultaneous linear equations – Naïve Gauss Elimination and Gaussian Elimination with Partial Pivoting. Then, why do we need to learn another method? To appreciate why LU Decomposition could be a better choice than the Gauss Elimination techniques in some cases, let us discuss first what LU Decomposition is about.

For any nonsingular matrix on which one can conduct Naïve Gauss Elimination forward elimination steps, one can always write it as

where

[L] = Lower triangular matrix

[U] = Upper triangular matrix

Then if one is solving a set of equations

[A] [X] = [C],

then

Multiplying both side by ,

=

Let

then

(1)

and

(2)

So we can solve equation (1) first for and then use equation (2) to calculate .

This is all exciting but this looks more complicated than the Gaussian elimination techniques!! I know but I cannot tease you any longer. So here we go!

Without proof, the computational time required to decompose the matrix to [L] [U] form is proportional to , where n is the number of equations (size of matrix). Then to solve the , the computational time is proportional to . Then to solve the , the computational time is proportional to . So the total computational time to solve a set of equations by LU decomposition is proportional to .

In comparison, Gaussian elimination is computationally more efficient. It takes a computational time proportional to , where the computational time for forward elimination is proportional toand for the back substitution the time is proportional to .

This has confused me further! Gaussian elimination takes less time than LU Decomposition method and you are trying to convince me then LU Decomposition has its place in solving linear equations! Yes, it does.

Remember in trying to find the inverse of the matrix in Chapter 5, the problem reduces to solving ‘n’ sets of equations with the ‘n’ columns of the identity matrix as the RHS vector. For calculations of each column of the inverse of the matrix, the coefficient matrix matrix in the set of equation does not change. So if we use LU Decomposition method, the decomposition needs to be done only once and the use of equations (1) and (2) still needs to be done ‘n’ times.

So the total computational time required to find the inverse of a matrix using LU decomposition is proportional to .

In comparison, if Gaussian elimination method were applied to find the inverse of a matrix, the time would be proportional to

.

For large values of n

Are you now convinced now that LU decomposition has its place in solving systems of equations? We are now ready to answer other questions - how do I find LU matrices for a nonsingular matrix [A] and how do I solve equations (1) and (2).