LU Factorization & Matrix Decomposition: Methods, Applications & Theory

1. Introduction to Matrix Decomposition

Matrix decomposition breaks a matrix into simpler, factorizable components for easier computation. The LU decomposition expresses a matrix $A$ as: $$A=LU$$ where:

• $L$ = Lower triangular matrix (diagonal entries = 1)
• $U$ = Upper triangular matrix

Why Decompose?

• Solves $Ax=b$ efficiently via forward/backward substitution (O(n²) vs. O(n³) for Gaussian elimination).
• Computes determinant as $\det (A)=\det (L)\det (U)={\prod }_{i=1}^n{u}_{ii}$.
• Finds inverse without direct inversion.
• Used in least squares, eigenvalue problems, and numerical stability.

2. LU Decomposition Methods

(a) Doolittle’s Algorithm (Standard LU)

For a square matrix $A$, compute $L$ and $U$ such that: $$A=LU$$ Steps:

1. For $j=1$ to $n$:
   • For $i=j$ to $n$: $$u_{ij}=a_{ij}-\sum _{k=1}^{j-1}{l}_{ik}{u}_{kj}$$
   • For $i=j+1$ to $n$: $$l_{ij}=\frac{1}{u_{jj}}\left(a_{ij}-\sum _{k=1}^{j-1}{l}_{ik}{u}_{kj}\right)$$

Example: Decompose $A=\left[\begin{array}{ccc}2& 1& 1\\ 4& 7& 0\\ -2& 3& 5\end{array}\right]$.

Solution:

1. First column (j=1):
   • $u_{11}=2$, $l_{21}=4/2=2$, $l_{31}=-2/2=-1$.
2. Second column (j=2):
   • $u_{22}=7-(2)(1)=5$, $u_{32}=3-(-1)(1)=4$.
   • $l_{32}=4/5=0.8$.
3. Third column (j=3):
   • $u_{33}=5-(-1)(1)-(0.8)(4)=2$.

Result: $$L=\left[\begin{array}{ccc}1& 0& 0\\ 2& 1& 0\\ -1& 0.8& 1\end{array}\right],U=\left[\begin{array}{ccc}2& 1& 1\\ 0& 5& 4\\ 0& 0& 2\end{array}\right]$$

(b) Crout’s Algorithm (Alternative LU)

Modifies Doolittle by storing $L$ with non-unit diagonal and $U$ with zeros below diagonal: $$A=LU$$ where:

• $L$ has arbitrary diagonal entries.
• $U$ is upper triangular with $u_{ii}=1$.

Advantage: Useful when $L$’s diagonal entries are needed explicitly.

(c) Cholesky Decomposition (for Symmetric Positive-Definite Matrices)

For $A=A^T>0$, decompose as: $$A=L{L}^T$$ where $L$ is lower triangular.

Steps:

1. For $j=1$ to $n$:
   • $l_{jj}=\sqrt{a_{jj}-{\sum }_{k=1}^{j-1}{l}_{jk}^2}$
   • For $i=j+1$ to $n$: $$l_{ij}=\frac{1}{l_{jj}}\left(a_{ij}-\sum _{k=1}^{j-1}{l}_{ik}{l}_{jk}\right)$$

Example: Decompose $A=\left[\begin{array}{ccc}4& 2& 2\\ 2& 5& 3\\ 2& 3& 7\end{array}\right]$.

Solution:

1. $l_{11}=\sqrt{4}=2$
2. $l_{21}=2/2=1$, $l_{31}=2/2=1$
3. $l_{22}=\sqrt{5-1}=2$, $l_{32}=(3-1)/2=1$
4. $l_{33}=\sqrt{7-1-1}=\sqrt{5}$

Result: $$L=\left[\begin{array}{ccc}2& 0& 0\\ 1& 2& 0\\ 1& 1& \sqrt{5}\end{array}\right]$$

3. Partial Pivoting for Numerical Stability

Without pivoting, LU decomposition can fail or introduce large errors for ill-conditioned matrices. Partial pivoting reorders rows to ensure: $$|u_{jj}|=\underset{i\ge j}{\max }|a_{ii}^{(j)}|$$ where $a^{(j)}$ is the matrix after $j-1$ steps.

flowchart TD
    A[Original Matrix A] --> B[Check if a11 = 0]
    B -->|Yes| C[Swap Rows]
    B -->|No| D[Proceed with LU]
    C --> D
    D --> E[Continue Decomposition]
    E --> F[Stable LU Decomposition]
    style C fill:#f9f,stroke:#333

Partial Pivoting Decision Flowchart

Example: Apply partial pivoting to $A=\left[\begin{array}{ccc}0& 1& 2\\ 1& 2& 3\\ 4& 5& 6\end{array}\right]$.

Steps:

1. Swap Row 1 and Row 2 (since $|1|>|0|$): $$A^{(1)}=\left[\begin{array}{ccc}1& 2& 3\\ 0& 1& 2\\ 4& 5& 6\end{array}\right]$$
2. Proceed with LU decomposition on $A^{(1)}$.

4. Applications of LU Decomposition

5. Comparison of Decomposition Methods

6. Worked Example: Solving $Ax=b$ Using LU

Given: $$A=\left[\begin{array}{ccc}2& 1& 1\\ 4& 7& 0\\ -2& 3& 5\end{array}\right],b=\left[\begin{array}{c}1\\ 2\\ 3\end{array}\right]$$

Step 1: LU decomposition (from earlier): $$L=\left[\begin{array}{ccc}1& 0& 0\\ 2& 1& 0\\ -1& 0.8& 1\end{array}\right],U=\left[\begin{array}{ccc}2& 1& 1\\ 0& 5& 4\\ 0& 0& 2\end{array}\right]$$

Step 2: Solve $Ly=b$: $$y_1=1$$ $$2y_1+y_2=2\Rightarrow y_2=0$$ $$-y_1+0.8y_2+y_3=3\Rightarrow y_3=4$$

Step 3: Solve $Ux=y$: $$2x_1+x_2+x_3=1$$ $$5x_2+4x_3=0$$ $$2x_3=4\Rightarrow x_3=2$$ Back-substitute: $$x_2=-4/5$$ $$x_1=(1-(-4/5)-2)/2=-1/2$$

Solution: $x=\left[\begin{array}{c}-0.5\\ -0.8\\ 2\end{array}\right]$

7. Determinant via LU Decomposition

For $A=LU$, $\det (A)=\det (L)\det (U)$. Since $\det (L)=1$ (unit diagonal), $\det (A)={\prod }_{i=1}^n{u}_{ii}$.

Example: For the earlier $U$: $$\det (A)=(2)(5)(2)=20$$

8. Limitations and Challenges

• Singular Matrices: LU fails if any $u_{jj}=0$ (requires pivoting).
• Non-Square Matrices: LU is defined only for square matrices (use QR for rectangular).
• Computational Overhead: Pivoting adds complexity but ensures stability.
• Memory: Stores two matrices $L$ and $U$ instead of one.

Exam Tip

1. Understand the Process:

   • Memorize Doolittle/Crout steps but focus on pattern recognition (e.g., $u_{ij}$ vs. $l_{ij}$ formulas).
   • For Cholesky, verify $A$ is symmetric positive-definite first ($x^{T}Ax>0$).

2. Pivoting is Key:

   • Always check if pivoting is needed (e.g., if $a_{11}=0$).
   • Partial pivoting swaps rows to maximize $|u_{jj}|$.

3. Applications Over Theory:

   • Exams often ask to solve $Ax=b$ or compute determinant using LU.
   • Show all steps of forward/backward substitution.

4. Common Pitfalls:

   • Forgetting $L$ has 1s on diagonal (Doolittle) or zeros above (Crout).
   • Misapplying Cholesky to non-SPD matrices (check $A=A^T$ and $\det (A)>0$).
   • Arithmetic errors in manual decomposition (double-check calculations).

5. Past Exam Patterns:

   • Part (a): Decompose a 3×3 matrix (Doolittle/Crout).
   • Part (b): Solve $Ax=b$ using the LU factors.
   • Part (c): Compute determinant/inverse via LU.
   • Bonus: Prove Cholesky conditions or discuss pivoting necessity.

Note: For numerical methods, always assume partial pivoting unless stated otherwise. Use symbolic computation for small matrices (3×3) and practical software (MATLAB, Python) for larger ones in real-world applications.```