Project 2 Matrix
Project 2: LU Decomposition Linear Algebra The Overview: There are many ways to solve systems of equations. Primarily, we use the process of Gauss-Jordan Elimination to solve the systems that we come across in this course. There are other exact methods and also many numerical or estimation methods that are broadly used to solve systems. Why you might ask would we use a different method? The answer is two fold. First, some methods are more computational efficient compared to GJ elimination, though they are also more restrictive, which is why we don’t use them for our general method in this course. Second, some methods are what we call more numerically stable. Meaning that if we are working with machine precision or rounding during each step of the method, which of course we are if we are using technology to execute it, some methods are more prone to wild errors due to that rounding while other are less prone. One method that is more numerically stable that Gauss Jordan Elimination is what we will study in this project. It uses a process called LU decomposition. The Process: The following is an outline of the process: 1. We have a matrix equation to solve: A~x = ~b, where the matrix A is square and invertible. 2. We want to “factor” A into a lower triangular matrix L times an upper triangular matrix U . Triangular matrices are those whose non-zero elements are restricted to just one diagonal part of the matrix. A = LU 3. This will then allow use to solve the new system of (LU )~x = ~b with quick and simple forward and backward substitution. (See the example problem for details on this.) 4. We can reduce the matrix using only Gaussian Elimination down to a row echelon form, U , and keep track of the steps that we take. We can represent this reduction using multiplication by elementary matrices for the row operations as En En−1 . . . E2 E1 A = U where n is the number of operations it takes to do the reduction. 5. We can then calculate L by moving all of those elementary (and therefore invertible matrices) to the other side of the equation. A = (En En−1 . . . E2 E1 )−1 U −1 L = (En En−1 . . . E2 E1 )−1 = E1−1 E2−1 . . . En−1 En−1 Warning: When finding L, make sure to take the inverse of each of the elementary matrices individually and then multiply them together. Finding the inverse after multiplying defeats the purpose since it is numerically unstable. A note about this process: This is not the only way to find an L and U from a matrix A nor is it even the most efficient way, but it is certainly the way that is most understandable by newly minted linear algebra students. The Example: Use the process outlined above to find an LU -decomposition of the matrix A and solve the newly formed system using only forward and backward substitution. 1 1 2 6 ~ A = 1 2 2 and b = 5 1 3 1 1 Here is the row reduction of A to U via Gaussian Elimination: 1 1 2 1 1 2 1 1 2 1 1 2 −−−−−−−−−−−→ −−−−−−−−−−−→ −−−−−−−−−−−−→ A = 1 2 2 −R1 + R2 → R2 0 1 0 −R1 + R3 → R3 0 1 0 −2R2 + R3 → R3 0 1 0 1 3 1 1 3 1 0 2 −1 0 0 −1 Here is the representation of this reduction in terms of elementary matrices: 1 0 0 1 0 0 1 0 0 1 1 2 1 1 2 0 1 0 · 0 1 0 · −1 1 0 · 1 2 2 = 0 1 0 0 −2 1 −1 0 1 0 0 1 1 3 1 0 0 −1 Remember that the inverse of an elementary matrix is simply the matrix that would undo that elementary row operation. You should definitely not need a calculator to find each of those. L would be calculated as follows for this example: 1 0 0 1 0 0 1 0 0 1 0 0 L = 1 1 0 · 0 1 0 · 0 1 0 = 1 1 0 0 0 1 1 0 1 0 2 1 1 2 1 Note: It is easy to check if we did the work correctly by simply calculating LU . It should equal the A matrix we started with. Notice now that our original system can be thought of two systems that are easily solvable. LU~x = ~b can be broken up by thinking of it as U~x = ~y and L~y = ~b. First, L~y = ~b can be solved very quickly with forward substitution, and then U~x = ~y can be solved very quickly using backwards substitution. 1 0 0 6 1 1 0 ~y = 5 1 2 1 1 y1 = 6 y1 + y2 = 5 → y2 = −1 y1 + 2y2 + y3 = 1 → y3 = −3 6 1 1 2 0 1 0 ~x = −1 −3 0 0 −1 −x3 = −3 → x3 = 3 x2 = −1 x1 + x2 + 2×3 = 6 → x1 = 1 Thus, our solution to the original equation of A~x = ~b is 1 ~x = −1 3 You may think that this was WAY more complicated than just doing our usual Gauss-Jordan Elimination. That is because IT IS in fact more complicated, BUT it is also more numerically stable. In the real world we do not have nice whole numbers that work out so well. This process helps reduce error when rounding is used in applications. The Assignment: Here it is. It had to happen some time didn’t it? Your job is to perform this process with at least as much detail as was provided in the example on the following system. 1 −4 2 3 1 3 −9 5 8 1 A= 2 −2 −2 −1 3 1 −7 3 9 1 −3 3 3 4 1 2 8 ~b = 5 1 6
Collepals.com Plagiarism Free Papers
Are you looking for custom essay writing service or even dissertation writing services? Just request for our write my paper service, and we'll match you with the best essay writer in your subject! With an exceptional team of professional academic experts in a wide range of subjects, we can guarantee you an unrivaled quality of custom-written papers.
Get ZERO PLAGIARISM, HUMAN WRITTEN ESSAYS
Why Hire Collepals.com writers to do your paper?
Quality- We are experienced and have access to ample research materials.
We write plagiarism Free Content
Confidential- We never share or sell your personal information to third parties.
Support-Chat with us today! We are always waiting to answer all your questions.
