[Solved] ALGEBRA LU Decomposition

Note: Instructions given here are subject to change if it is determined that additional structure or clarity is warranted.

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 = b_k 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 b_k 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 2n² 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 b_k to a solution x_k 24 times, the operation count drops by about 76% to ∼ 5600 total operations.

Carry out the following activities.

• Write a brief introduction to the topic of LU 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 .
• 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 Illustrate by decomposing

−3A =  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 k^th step.)

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

What to turn in: Please provide a typed paper or report that integrates activities (1), (2), (3), and (5). If possible, use a type setting tool or word processor that can format mathematical symbolism. If necessary, mathematical symbols can be neatly written in by hand. Displayed output from the program from (4) can be integrated into the narrative or included as an appendix. The report is due TBD.

Citation Format: References should be listed in alphabetical order by principle author surname. To cite a reference, include the reference number in square brackets to the right of the end of the citation.

For example

In vitro studies of LDL modification indicate that the process occurs over time periods of minutes [2, 16] whereas MRCT occurs over hours and days [23] (again in vitro).

The notations [2, 16] and [23] appearing in this sentence indicate to the reader that the first result cited can be found in references 2 and 16, and that the second result cited can be found in reference 23. Below you will find the requested format for any references that you use. The format is given for articles, books, and for websites/web-based documents.

Format for referencing an article:

Author(s), (year) title. journal volume/issue pages.

For example:

• Stocker, R. and Keaney, J., (2004) Role of Oxidative Modifications in Atherosclerosis.

Rev. 84 1381-1478.

Format for referencing a book:

Author(s), (year) title, publisher, location.

For example:

• Brandrup J. and Immergut E. H., (1989) Polymer Handbook, Wiley, New York.

Format for referencing a website:

Author(s)(if known), (date accessed) Webpage title, Organization/publisher(in any). URL

For example:

• Landsberger, J. (accessed Aug. 25, 2010) Study Guides and Strategies, University of XYZ. http://www.studygs.net/citation.htm .

If the website author is not known, just write Web Contributor