Matrix Factorization & Special Methods: LU, Cholesky, Crout, Doolittle

Matrix Factorization: Overview and Importance

Matrix factorization decomposes a matrix into simpler matrices whose product reconstructs the original matrix. This is crucial for:

• Solving linear systems efficiently.
• Improving numerical stability.
• Reducing computational cost in iterative methods.

Why Factorize?

• Efficiency: Solving $Ax=b$ via factorization is often faster than direct methods like Gaussian elimination.
• Stability: Some factorizations (e.g., LU with partial pivoting) improve numerical accuracy.
• Reusability: If $A$ is fixed but $b$ changes, factorization allows solving multiple systems cheaply.

---

1. LU Decomposition

LU decomposition expresses a matrix $A$ as the product of a lower triangular (L) and an upper triangular (U) matrix: $$A=LU$$ where:

• $L$ has unit diagonal (1s) and sub-diagonal elements.
• $U$ is upper triangular.

Methods of LU Decomposition

Three common variants differ in how $L$ is structured:

---

1.1 Doolittle’s LU Decomposition

Algorithm: For an $n\times n$ matrix $A$, compute $L$ and $U$ such that: $$A=LU$$ with:

• $L_{ii}=1$ (unit diagonal),
• $U_{ij}=0$ for $i>j$ (upper triangular),
• $L_{ij}=0$ for $i<j$ (lower triangular).

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: Factorize: $$A=\left[\begin{array}{ccc}2& 1& 1\\ 4& -2& 5\\ -2& 3& 11\end{array}\right]$$

Solution:

1. First column (j=1):

   • $U_{11}=A_{11}=2$
   • $L_{21}=A_{21}/U_{11}=4/2=2$
   • $L_{31}=A_{31}/U_{11}=-2/2=-1$

2. Second column (j=2):

   • $U_{22}=A_{22}-L_{21}{U}_{12}=-2-(2)(1)=-4$
   • $U_{12}=A_{12}=1$
   • $L_{32}=(A_{32}-L_{31}{U}_{12})/U_{22}=(3-(-1)(1))/(-4)=-1$

3. Third column (j=3):

   • $U_{33}=A_{33}-L_{31}{U}_{13}-L_{32}{U}_{23}=11-(-1)(1)-(-1)(5)=17$
   • $U_{13}=A_{13}-L_{11}{U}_{13}=1-(1)(1)=0$ (but corrected via formula) (Note: $U_{13}=A_{13}-{\sum }_{k=1}^2{L}_{1k}{U}_{k3}=1-0=1$)
   • $U_{23}=A_{23}-L_{21}{U}_{13}-L_{22}{U}_{23}=5-(2)(1)=3$

Final Factorization: $$L=\left[\begin{array}{ccc}1& 0& 0\\ 2& 1& 0\\ -1& -1& 1\end{array}\right],U=\left[\begin{array}{ccc}2& 1& 1\\ 0& -4& 3\\ 0& 0& 17\end{array}\right]$$

Verification: $$LU=\left[\begin{array}{ccc}2& 1& 1\\ 4& -2& 5\\ -2& 3& 11\end{array}\right]=A$$

---

1.2 Solving $Ax=b$ Using LU Decomposition

Once $A=LU$, solve $Ax=b$ in two steps:

1. Forward substitution: Solve $Ly=b$ for $y$.
2. Backward substitution: Solve $Ux=y$ for $x$.

Example: Solve $Ax=b$ where: $$b=\left[\begin{array}{c}0\\ 16\\ 20\end{array}\right]$$

Step 1: Solve $Ly=b$ $$\left[\begin{array}{ccc}1& 0& 0\\ 2& 1& 0\\ -1& -1& 1\end{array}\right]\left[\begin{array}{c}{y}_1\\ y_2\\ y_3\end{array}\right]=\left[\begin{array}{c}0\\ 16\\ 20\end{array}\right]$$

• $y_1=0$
• $2y_1+y_2=16⟹y_2=16$
• $-y_1-y_2+y_3=20⟹y_3=36$

Step 2: Solve $Ux=y$ $$\left[\begin{array}{ccc}2& 1& 1\\ 0& -4& 3\\ 0& 0& 17\end{array}\right]\left[\begin{array}{c}{x}_1\\ x_2\\ x_3\end{array}\right]=\left[\begin{array}{c}0\\ 16\\ 36\end{array}\right]$$

• $17x_3=36⟹x_3=36/17$
• $-4x_2+3x_3=16⟹x_2=(16-3(36/17))/(-4)=11/17$
• $2x_1+x_2+x_3=0⟹x_1=-(x_2+x_3)/2=-(11/17+36/17)/2=-23.5/17$

Solution: $$x=\left[\begin{array}{c}-23.5/17\\ 11/17\\ 36/17\end{array}\right]$$

---

1.3 Partial Pivoting in LU Decomposition

Problem: Without pivoting, large errors can occur if $U_{jj}$ is small (near zero). Solution: Partial pivoting swaps rows to ensure $|U_{jj}|$ is maximized in its column.

Modified Doolittle with Partial Pivoting:

1. For each column $j$, find the row $k\ge j$ with the largest $|A_{kj}|$ (pivot element).
2. Swap rows $j$ and $k$ in $A$ (and update $L$ accordingly).
3. Proceed with decomposition.

Example: Apply partial pivoting to the previous $A$:

• Column 1: Max $|A_{k1}|$ is $A_{21}=4$ (row 2). Swap row 1 and 2.
• Updated $A$: $$\left[\begin{array}{ccc}4& -2& 5\\ 2& 1& 1\\ -2& 3& 11\end{array}\right]$$
• Proceed with decomposition (resulting $L$ and $U$ will differ from above).

---

2. Cholesky Decomposition

For symmetric positive definite (SPD) matrices $A$ (i.e., $A=A^T$ and $x^{T}Ax>0$ for all $x\ne 0$), Cholesky decomposition is: $$A=L{L}^T$$ where $L$ is lower triangular with positive diagonal entries.

Why Cholesky?

• Faster: Avoids complex arithmetic (unlike LU for non-SPD matrices).
• Numerically stable: For SPD matrices, no pivoting is needed.

Algorithm

For $A=[a_{ij}]$, compute $L=[l_{ij}]$ where:

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

Factorize: $$A=\left[\begin{array}{ccc}4& 2& 2\\ 2& 5& 4\\ 2& 4& 11\end{array}\right]$$

Step 1 (j=1):

• $l_{11}=\sqrt{4}=2$

Step 2 (j=2):

• $l_{22}=\sqrt{5-(2{)}^2}=\sqrt{1}=1$
• $l_{21}=(2-0)/2=1$

Step 3 (j=3):

• $l_{33}=\sqrt{11-(2{)}^2-(4{)}^2}=\sqrt{11-4-16}=\sqrt{-9}$ → Error! (This matrix is not positive definite. Check: $A$ must satisfy $x^{T}Ax>0$ for all $x\ne 0$.)

Correction: Use a matrix that is SPD, e.g.: $$A=\left[\begin{array}{ccc}4& 1& 1\\ 1& 4& 1\\ 1& 1& 4\end{array}\right]$$

Recomputing:

1. $l_{11}=\sqrt{4}=2$
2. $l_{22}=\sqrt{4-1}=\sqrt{3}$ $l_{21}=(1)/2=0.5$
3. $l_{33}=\sqrt{4-1-1}=\sqrt{2}$ $l_{31}=(1)/2=0.5$ $l_{32}=(1-(0.5)(0.5))/\sqrt{3}=(1-0.25)/\sqrt{3}=0.75/\sqrt{3}$

Final $L$: $$L=\left[\begin{array}{ccc}2& 0& 0\\ 0.5& \sqrt{3}& 0\\ 0.5& 0.75/\sqrt{3}& \sqrt{2}\end{array}\right]$$

Verification: $$L{L}^T=A$$

---

3. Crout’s LU Decomposition

Crout’s method is similar to Doolittle but forces $U$ to have unit diagonal (1s): $$A=LU$$ where:

• $U_{ii}=1$,
• $L_{ij}=0$ for $i<j$.

Algorithm:

1. For $i=1$ to $n$:
   • $L_{ii}=A_{ii}-{\sum }_{k=1}^{i-1}{L}_{ik}{U}_{ki}$
   • For $j=i+1$ to $n$: $$U_{ij}=\frac{1}{L_{ii}}\left(A_{ij}-\sum _{k=1}^{i-1}{L}_{ik}{U}_{kj}\right)$$
   • For $j=1$ to $i-1$: $$L_{ij}=A_{ij}-\sum _{k=1}^{j-1}{L}_{ik}{U}_{kj}$$

Example: Factorize the same $A$ as in Doolittle’s example using Crout’s method.

(Note: Crout’s method is less commonly used than Doolittle but is included for completeness.)

---

4. Comparison of Factorization Methods

---

5. Special Methods for Linear Systems

Beyond factorization, other methods exist for specific cases:

5.1 Thomas Algorithm (Tridiagonal Matrices)

For tridiagonal matrices $A$ (non-zero only on main diagonal and adjacent diagonals), the Thomas algorithm is a simplified LU decomposition.

Example: Solve: $$\left[\begin{array}{ccc}2& 1& 0\\ 1& 4& 1\\ 0& 1& 3\end{array}\right]\left[\begin{array}{c}{x}_1\\ x_2\\ x_3\end{array}\right]=\left[\begin{array}{c}5\\ 6\\ 3\end{array}\right]$$

Steps:

1. Forward sweep (modify diagonals):

   • $c^{\prime }=c/b$ (where $b$ is the main diagonal)
   • $d^{\prime }=(d-a\cdot c^{\prime })/b$ (Here, $a$ is the sub-diagonal, $b$ is the main diagonal, $c$ is the super-diagonal.)

2. Backward sweep (solve for $x$):

   • $x_n=d_n^{\prime }$
   • $x_i=d_i^{\prime }-c_i^{\prime }{x}_{i+1}$

Solution: (Detailed steps omitted for brevity; result: $x\approx [1.5,1.0,0.5{]}^T$)

---

5.2 Applications of Matrix Factorization

1. Solving Linear Systems: $Ax=b$ is solved efficiently via $LUx=b$.
2. Matrix Inversion: $A^{-1}=U^{-1}{L}^{-1}$ (though inversion is rarely needed directly).
3. Eigenvalue Problems: Factorization aids in iterative methods like QR algorithm.
4. Least Squares: Used in solving overdetermined systems $A^{T}Ax=A^{T}b$.
5. Graph Theory: Adjacency matrices in networks are often factorized.

---

Exam Tip

What to Expect in Exams

1. Theoretical Questions:

   • Derive the formula for Doolittle’s LU decomposition or Cholesky decomposition.
   • Explain why Cholesky requires SPD matrices.
   • Compare LU vs. Cholesky in terms of applicability and efficiency.

2. Numerical Problems:

   • Factorize a given matrix using Doolittle, Crout, or Cholesky.
   • Solve $Ax=b$ using the factorization obtained.
   • Apply partial pivoting during LU decomposition.

3. Short Answer/Definitions:

   • Define symmetric positive definite (SPD) matrix.
   • What is the role of pivoting in LU decomposition?
   • When is Cholesky decomposition preferred?

4. Common Pitfalls:

   • Forgetting to check if a matrix is SPD before applying Cholesky.
   • Incorrectly assuming $L$ or $U$ is unit diagonal (mix-up between Doolittle and Crout).
   • Skipping partial pivoting in LU, leading to large errors.

Marks Distribution (Typical)

Recommended Approach

1. Memorize Algorithms: Write down the step-by-step formulas for LU and Cholesky.
2. Practice Factorization: Solve 2-3 numerical problems per method.
3. Understand SPD Check: For Cholesky, verify $A=A^T$ and all leading principal minors > 0.
4. Partial Pivoting: Always mention its necessity in LU unless specified otherwise.
5. Time Management: Allocate ~15-20 minutes for a 10-mark numerical question on factorization.

---

Past Exam Questions Covered in This Unit

---

Quick Revision Checklist

• Can derive Doolittle’s LU formula from scratch.
• Know when to use Cholesky vs. LU.
• Can factorize a 3x3 matrix using any method.
• Understand partial pivoting and its importance.
• Recall SPD matrix conditions.
• Can solve $Ax=b$ using forward/backward substitution.