What is LU decomposition?

LU decomposition stands for Lower-Upper decomposition. LU decomposition is the factorization of the lower triangular matrix and an upper triangular matrix. It is very useful in linear algebra and numerical analysis. A permutation matrix is usually included in the product. Gaussian elimination in a matrix form is known as LU decomposition, When inverting a matrix or evaluating its determinant, this is a crucial step. Tadeusz Banachiewicz, a Polish mathematician, first proposed the LU decomposition in 1938.

Alan Turing, who also made the Turing machine, created LU decomposition in 1948 as an alternative to Gaussian elimination by factoring the coefficient matrix into an upper triangular and lower triangular matrix production. It is represented in the form:

A = LU

Users can use the LU decomposition to analyze linear equations and determine the inverse (for example, the inverse function in MATLAB), and obtain the determinant of a matrix (a triangular matrix's determinant is obtained from by using the product of its diagonal entries).

Definition of LU decomposition

Let's consider A as a square matrix. The two ingredients combine to form a LU. A lower triangular matrix is the first ingredient, and an upper triangular matrix is the second. The L is the identification of the lower triangular matrix and The upper triangular is represented by the U.

A = LU

In the lower triangular matrix, all components above the diagonal are zero, while in the upper triangular matrix, all components below the diagonal are zero. For example, an LU decomposition done in a 3x3 matrix:

a11a12a13a21a22a23a31a32a33=l1100l21l220l31l32l33u11u12u130u22u2300u33

To get a11, use a11 = l11·u11,  That means it is obtained by using the production of the first row of L and first column of R. if a11=0 it represents one of the l11 or u11 is zero, which denotes the singularity of either l or u. This is invertible if A is not singular. It's a procedural issue that can be solved by reordering the rows of A in such a way that the first element of the permuted matrix is non-zero. 

Partial pivoting LU factorization

A partial pivoting LU factorization only uses row permutations. It uses the factorization technique. When P (permutation matrix) is left-multiplied by a square matrix A, it reorders the elements of row A. It is done in row permutation only.

PA = LU

Here, L is the lower and U is the upper triangular matrices, respectively, and p denotes a permutation matrix. A square binary matrix with one 1 entry in each row and column and 0s everywhere else is known as a permutation matrix. Factorization is possible for all square matrices. As a result, the factorization of LU is numerically constant in the actual world. As a result, LUP decomposition is a useful technique.

Example of partial pivoting

In a linear system,

AX = B

A = 2-6-1-3-17-81-2

If LU decomposition is used with partial pivoting, it gives the first column of the inverse matrix A-1.

 A = 2-6-1-3-17-81-2   R1R3=-81-2-3-172-6-1

Because R1 and R3 are swapped, keep in mind that b1 and b3 will be swapped in the solution vector.

The solution vector's order will be b3b2b1.

To find the matrix U, use Gauss Elimination.

-81-2-3-172-6-1 R2--3/-8R1,,,R3-2/-8R1-81-20-1.3757.7500-5.750-1.500 R2R3..So, the -order-vectorb3b2b1-81-20-5.750-1.5000-1.3757.500R3--1.375/-5.750R2U=-81-20-5.750-1.500008.109

After pivoting, consider L21 and L31.

L13= -3/-8 = 0.375L12= 2/-8 = -0.25L32 = -1.375/-5.75=0.2391L = 100-0.25100.3750.23911

To find the inverse's first column. Remember that the identity's first column is 100. As a result, we're looking for X something that will fulfill us.

Ax1x2x3=100

However, keep in mind that after performing the LU Decomposition with partial pivoting, the solution order is b3b1b2.

As a result, we'd like to solve for b3=0b1=0b2=0 that is 010 the vector LD=B.

100-0.25100.3750.23911d1d2d3=010D=01-0.2391UX=D-81-20-5.750-1.500008.109x1x2x3=01-0.2391 By Backward substitutionx=-0.0134-0.1662-0.0295

which is the first column of A-1.

Full pivoting LU factorization

Full pivoting LU factorization is dependent upon row permutations as well as column permutations.

PAQ = LU

Here, a permutation matrix Q rearranges A's columns.

Common Mistakes

Students may be confused by the following questions regarding LU decomposition:

  • Is LU decomposition always present in matrices?

No. It's not always possible to write a matrix in the "lower triangular" x "upper triangular" format.

  • Which conditions prove that the LU decomposition is unique?

To achieve uniqueness, you must first ensure that L is a unit triangular (or that U is), which means that it contains all 1s on the diagonal and that A = LU is invertible. If the LU factorization exists, it is unique.

  • Which matrices are not amenable to LU decomposition?

LU decomposition is not possible if the matrix loses a pivot while being changed to U through row reductions, and this cannot be repaired without a row shuffle operation.

Context and Applications

This topic is critical for the professional exams in both undergraduate and graduate courses, especially for:

  • Bachelors in Computer Science.
  • Masters in Computer Science.
  • LU decomposition applications.
  • LU decomposition calculator.
  • Gaussian elimination.

Practice Problems

Q1. Gaussian elimination in a matrix form is known as _______________.

  1. LU decomposition
  2. identity matrix
  3. square matrix
  4. vector matrix

Correct Answer: (1) LU decomposition

Explanation: LU decomposition is a more efficient approach to use Gaussian elimination, mainly when solving several equations with the same left-hand side.

Q2. LU decomposition is a factorization of _____________.

  1. lower and upper triangular matrix
  2. two vector matrices
  3. vector matrix and lower triangular matrix
  4. vector matrix and upper triangular matrix

Correct Answer: (1) lower and upper triangular matrix

Explanation: LU decomposition stands for Lower-Upper decomposition. LU decomposition is the factorization of the lower triangular matrix and an upper triangular matrix.

 

Q3. Which of these is a lower triangular matrix:

  1. l11l12l130l22l2300l33
  2. l11l12l130l22l23000
  3. l11l1200l22l2300l33
  4. l1100l21l220l31l32l33

Correct Answer: (4)

l1100l21l220l31l32l33

Explanation: In the lower triangular matrix, all components above the diagonal are zero.

 

Q4. Definition of LU decomposition is if A is a square matrix, a lower triangular matrix is L and an upper triangular matrix is U -____________.

  1. A = LU
  2. L = AU
  3. U = AU
  4. None

Correct Answer: (1) 

A=LU

Explanation: The two ingredients combine to form a LU. A lower triangular matrix is the first ingredient, and an upper triangular matrix is the second. The L is the identification of the lower triangular matrix and The upper triangular is represented by the U.

Q5. What does a permutation matrix property contain?

  1. A square binary matrix with 1s in each row and column and 0s everywhere else is known as a permutation matrix.
  2. A square binary matrix with 0s everywhere is known as a permutation matrix.
  3. A square binary matrix with 1s everywhere is known as a permutation matrix.
  4. None

Correct Answer: (1) A square binary matrix with 1s in each row and column and 0s everywhere else is known as a permutation matrix.

Explanation: A permutation matrix property contains 1s in each row and column and 0s everywhere.

Want more help with your computer science homework?

We've got you covered with step-by-step solutions to millions of textbook problems, subject matter experts on standby 24/7 when you're stumped, and more.
Check out a sample computer science Q&A solution here!

*Response times may vary by subject and question complexity. Median response time is 34 minutes for paid subscribers and may be longer for promotional offers.

Search. Solve. Succeed!

Study smarter access to millions of step-by step textbook solutions, our Q&A library, and AI powered Math Solver. Plus, you get 30 questions to ask an expert each month.

Tagged in
EngineeringComputer Science

Algorithms

Matrix

LUP Decomposition

Search. Solve. Succeed!

Study smarter access to millions of step-by step textbook solutions, our Q&A library, and AI powered Math Solver. Plus, you get 30 questions to ask an expert each month.

Tagged in
EngineeringComputer Science

Algorithms

Matrix

LUP Decomposition