Solving Linear Systems Ax = B With LU Factorization

In this article, we will explore how to solve the linear system $Ax = b$ using LU factorization. The given system of equations is:

 x_1 + x_2 - 3x_3 = -1
 -x_1 + 2x_2 = 1
 x_1 - x_2 + x_3 = 2

We will solve this system by first finding the LU-factorization of the coefficient matrix A and then solving the lower triangular system Ly = b. This method provides an efficient way to solve linear systems, especially when dealing with multiple systems with the same coefficient matrix.

a) Finding the LU-Factorization of the Coefficient Matrix A

The coefficient matrix A for the given system is:

 A = | 1  1 -3 |
     | -1 2  0 |
     | 1 -1  1 |

LU factorization involves decomposing the matrix A into two matrices: a lower triangular matrix L and an upper triangular matrix U. The process typically involves applying Gaussian elimination to transform A into an upper triangular matrix U, while keeping track of the multipliers used in the elimination process. These multipliers are then used to form the lower triangular matrix L.

The goal is to find matrices L and U such that A = LU. The lower triangular matrix L has 1s on the diagonal, and the upper triangular matrix U is the result of applying forward elimination to matrix A.

Step-by-Step Process

1. Initial Matrix A:

   A = | 1  1 -3 |
       | -1 2  0 |
       | 1 -1  1 |
   

2. Eliminate the element in the second row, first column (-1):

   To eliminate -1 in the second row, we add the first row to the second row. The multiplier is $m_{21} = 1$.

   Row2 = Row2 + 1 * Row1
   

   The matrix becomes:

   A' = | 1  1 -3 |
        | 0  3 -3 |
        | 1 -1  1 |
   

3. Eliminate the element in the third row, first column (1):

   To eliminate 1 in the third row, we subtract the first row from the third row. The multiplier is $m_{31} = -1$.

   Row3 = Row3 - 1 * Row1
   

   The matrix becomes:

   A'' = | 1  1 -3 |
         | 0  3 -3 |
         | 0 -2  4 |
   

4. Eliminate the element in the third row, second column (-2):

   To eliminate -2 in the third row, we add 2/3 times the second row to the third row. The multiplier is $m_{32} = -(-2/3) = 2/3$.

   Row3 = Row3 + (2/3) * Row2
   

   The matrix becomes:

   U = | 1  1 -3 |
       | 0  3 -3 |
       | 0  0  2 |
   

   The upper triangular matrix U is now obtained.

5. Construct the Lower Triangular Matrix L:

   The lower triangular matrix L consists of the multipliers used in the elimination process. The multipliers are placed in the corresponding positions below the diagonal, with 1s on the diagonal.

   L = | 1  0  0 |
       | 1  1  0 |
       | -1 2/3 1 |
   

Final LU Factorization

Thus, the LU factorization of the matrix A is:

 L = | 1  0  0 |
     | 1  1  0 |
     | -1 2/3 1 |

 U = | 1  1 -3 |
     | 0  3 -3 |
     | 0  0  2 |

We have successfully decomposed the coefficient matrix A into a lower triangular matrix L and an upper triangular matrix U. This decomposition is crucial for efficiently solving the system Ax = b.

This LU factorization method is essential for solving linear systems in various fields, including engineering, physics, and computer science. The decomposition simplifies the solution process by breaking it down into two simpler triangular systems. Understanding the steps involved in LU factorization provides a strong foundation for numerical linear algebra.

b) Solving the Lower Triangular System Ly = b

Now that we have the LU factorization, we can solve the system Ax = b in two steps. First, we solve the system Ly = b for y, and then we solve the system Ux = y for x. This part focuses on solving the lower triangular system Ly = b.

The given system Ax = b has the following b vector:

 b = | -1 |
     | 1  |
     | 2  |

We have the lower triangular matrix L as:

 L = | 1  0  0 |
     | 1  1  0 |
     | -1 2/3 1 |

The system Ly = b can be written as:

 | 1  0  0 | | y1 | = | -1 |
 | 1  1  0 | | y2 | = | 1  |
 | -1 2/3 1 | | y3 | = | 2  |

This corresponds to the following set of equations:

 y1 = -1
 y1 + y2 = 1
 -y1 + (2/3)y2 + y3 = 2

Solving for y using Forward Substitution

1. Solve for y1:

   From the first equation, we directly have:

   y1 = -1
   

2. Solve for y2:

   Substitute y1 into the second equation:

   -1 + y2 = 1
   y2 = 1 + 1
   y2 = 2
   

3. Solve for y3:

   Substitute y1 and y2 into the third equation:

   -(-1) + (2/3)(2) + y3 = 2
   1 + 4/3 + y3 = 2
   y3 = 2 - 1 - 4/3
   y3 = 1 - 4/3
   y3 = -1/3
   

Solution Vector y

Thus, the solution vector y is:

 y = | -1 |
     | 2  |
     | -1/3 |

We have successfully solved the lower triangular system Ly = b for y. This solution is an intermediate step in solving the original system Ax = b. The next step involves using this solution to solve the upper triangular system Ux = y.

Solving triangular systems is a fundamental technique in linear algebra, and forward substitution is an efficient method for lower triangular systems. This process significantly simplifies the overall solution of linear systems, particularly when combined with LU factorization. Understanding this method is crucial for various numerical computations and applications.

By using the forward substitution method, we efficiently found the vector y, which is a key component in solving the original linear system. This step demonstrates the practical application of LU decomposition in simplifying complex calculations.