Overview
This lecture introduces LU factorization—expressing a matrix as the product of a lower and an upper triangular matrix—and explains its application in efficiently solving systems of linear equations.
LU Factorization Basics
- LU factorization writes a matrix as the product of a lower triangular matrix (L) and an upper triangular matrix (U).
- Lower triangular matrix: all entries above the main diagonal are zero.
- Upper triangular matrix: all entries below the main diagonal are zero.
- Not every matrix can be written in LU form; a matrix must meet specific conditions.
Triangular Matrices Explained
- Main diagonal: diagonal running from top-left to bottom-right of the matrix.
- Upper triangular: nonzero values above the main diagonal, zeros below (e.g., for 3x3: a, b, c in first row; 0, d, e in second; 0, 0, f in third).
- Lower triangular: nonzero values below the main diagonal, zeros above.
Direct Method for LU Factorization
- Multiply generic forms of L and U matrices and equate to the original matrix.
- Solve the resulting system of equations to find the unknowns in L and U.
- For simplicity, the lower triangular matrix can have ones on the diagonal.
- If no valid solution exists, LU factorization is not possible for that matrix.
Conditions for LU Factorization
- A matrix has an LU factorization if its row echelon form can be achieved without row swaps (interchanging rows).
- Only type 2 and type 3 row operations are allowed: scaling a row by a nonzero number and adding a multiple of one row to another.
Two Methods for Finding LU Factorization
- Method by inspection: brute force element-wise matching of products.
- Multiplier (computational) method: perform allowed row operations on the matrix and the identity matrix in parallel until the original becomes upper triangular and the identity becomes lower triangular.
Using LU Factorization to Solve Linear Systems
- Transform Ax = b into (LU)x = b.
- Let Ux = y, so the system becomes two simpler systems: Ly = b (solve for y), then Ux = y (solve for x).
- Both systems use triangular matrices, so back substitution solves them efficiently.
Key Terms & Definitions
- LU Factorization — Decomposition of a matrix into the product of a lower and upper triangular matrix.
- Lower Triangular Matrix — Square matrix with zeros above the main diagonal.
- Upper Triangular Matrix — Square matrix with zeros below the main diagonal.
- Back Substitution — Method for solving triangular systems of equations starting from the bottom row.
Action Items / Next Steps
- Review chapter on triangular matrices and back substitution (see chapter 1 if needed).
- Prepare for next lecture on determinants.
- Contact instructor via email for questions or to set up Zoom office hours.