LU DECOMPOSITION OF SOLVING SIMULTANEOUS LINEAR EQUATIONS AN INTERACTIVE EBOOK
On non Internet Explorer browsers, the equations may not show up. As an alternative or if you prefer, you can see the pdf version of the ebook instead
Title	An interactive e-book for illustrating the LU Decomposition of Solving Simultaneous Linear Equations
Creator	Autar K Kaw
Subject and Keywords	LU Decomposition, Simultaneous Linear Equations, Mathcad, Maple, Mathematica, Matlab, Simulations.
Description	This is an interactive E-book for illustrating Simultaneous Linear Equations. It includes links to simulations in Mathcad, Maple, Mathematica, and Matlab for the algorithm, multiple-choice quizzes, problem set, and a PowerPoint presentation.
Publisher	Holistic Numerical Methods Institute, College of Engineering, University of South Florida, Tampa, FL 33620-5350.
Contributors	Autar Kaw
Format	Text/HTML
Last Revised	Wednesday, March 12, 2008
Identifier	http://numericalmethods.eng.usf.edu/ebooks/ludecomposition_04sle_ebook.pdf
Language	English
Rights	http://numericalmethods.eng.usf.edu/rights.htm

After reading this chapter, you should be able to:

Learn when LU Decomposition is numerically more efficient than Gaussian Elimination,
Decompose a nonsingular matrix into LU,
Show how LU Decomposition is used to find matrix inverse

Table of Contents

I hear about LU Decomposition used as a method to solve a set of simultaneous linear equations? What is it and why do we need to learn different methods of solving a set of simultaneous linear equations?. 129

How do I decompose a non-singular matrix [A], that is, how do I find ?. 132

Example 1. 133

Example 2. 135

Simulation (Mathcad Maple Mathematica Matlab)

How do I find the inverse of a square matrix using LU Decomposition?. 138

Example 3. 139

Exercise: 143 Multiple choice question examination

I hear about LU Decomposition used as a method to solve a set of simultaneous linear equations? What is it and why do we need to learn different methods of solving a set of simultaneous linear equations?

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).

Back to TOC

How do I decompose a non-singular matrix [A], that is, how do I find ?

If forward elimination steps of Naïve Gauss elimination methods can be applied on a nonsingular matrix, then can be decomposed into LU as

1. The elements of the matrix are exactly the same as the coefficient matrix one obtains at the end of the forward elimination steps in Naïve Gauss Elimination.

2. The lower triangular matrix has 1 in its diagonal entries. The non zero elements on the non-diagonal elements in are multipliers that made the corresponding entries zero in the upper triangular matrix during forward elimination.