Linear Algebra Project-LU Decomposition Solved

The purpose of this project is to explore a means of solving a matrix equation Ax = b by decomposing the coefficient matrix A. Under appropriate circumstance, such an approach may provide a methodology that has advantages in terms of computational efficiency.

Suppose we have an application that gives rise to a sequence of n × n linear systems Ax = bk for k = 1,...K. An example may be a flow network (e.g. a shipping channel) in which the inflow and outflow data that determines bk changes each hour while the network structure in A remains fixed. If A is n × n, a reduction of A to an echelon form requires about   operations. Back substitution to determine x requires another roughly 2n2 operations. If n = 10, solving the system 24 times in a day requires ∼ 24000 operations. If we can perform the reduction of A once, and use this to convert bk to a solution xk 24 times, the operation count drops by about 76% to ∼ 5600 total operations.

Carry out the following activities.

(1)             Write a brief introduction to the topic of LU decomposition. Be sure to include definitions of any new or significant terms. (Here, I would advise considering how you would present this to your classmates who are not likely to be familiar with terms like upper triangular matrix.) Also include some explanation of the steps inherent in solving Ax = b in the new form LUx = b .

(2)             Assuming that a given matrix A can be reduced to an echelon form without requiring a row swap at any point in the reduction process, describe an algorithm to obtain an LU decomposition. Illustrate by decomposing



−3

A =  6



9
1           2 

2           −5 .

 5 −6
Demonstrate the system solution process on the sytem Ax = b for this matrix A and b = [0 3 8]T.



2 (3) Show that −4



6
1          −1 

−2             5  does not have an LU decomposition. Discuss the condition that



2          11
causes the problem here. (This would have obvious ramifications for a program with a naive command to “divide by the pivot” at the kth step.)

(4)             Using the language of your choice write a program to perform and return an LU decomposition on a square matrix of arbitrary size. Include an exit strategy that can detect when the process (without pivoting) will fail. You may wish to return some indicative message to the user in this case. Choose some examples to demonstrate what your program produces. If reasonable, write a routine that can solve an equation Ax = b by calling your LU decomposition routine and performing the back substitution processes with the returned matrices L and U. Choose an example to demonstrate what your program produces.

Write a brief conclusion or reflection on the LU decomposition and your experience. Consider strengths and weaknesses of the LU decomposition as a practical tool. You may find information in the literature on issues with numerical error, alternative algorithms, PLU or LDU decompositions, and existence and uniqueness considerations. (It is not necessary that you touch on all of these things, they are just examples of topics that you may come across and would like to include.) Use the format described on the following page if you include citations