Direct Methods for Linear Algebraic Equations: Gaussian Elimination, LU Decomposition, Cholesky Factorization

1. Introduction to Direct Methods

Direct methods solve linear systems $Ax=b$ by transforming the system into an equivalent form that can be solved exactly (in theory). Unlike iterative methods, they provide the solution in a finite number of steps but may be computationally expensive for large systems.

Key Characteristics

• Exact solution (ignoring rounding errors).
• Three phases:
  1. Factorization: Decompose $A$ into simpler matrices (e.g., $A=LU$).
  2. Forward/back substitution: Solve $Ly=b$ and $Ux=y$.
• Time complexity: $O(n^3)$ for $n\times n$ matrices (dominant in numerical linear algebra).

---

2. Gaussian Elimination (GE) and Back Substitution

2.1 Algorithm Overview

Gaussian elimination transforms $A$ into upper triangular form $U$ via row operations:

1. Forward elimination: Create zeros below the diagonal using row additions/subtractions.
2. Back substitution: Solve $Ux=y$ (where $y$ is the transformed RHS).

Example: Solve

$$\{\begin{array}{l}2x+y-z=8\\ -3x-y+2z=-11\\ -2x+y+2z=-3\end{array}$$

Step-by-Step Trace

1. Augmented matrix: $$\left[\begin{array}{ccccc}2& 1& -1& |& 8\\ -3& -1& 2& |& -11\\ -2& 1& 2& |& -3\end{array}\right]$$
2. Eliminate $x$ from rows 2 and 3:
   • Row2 = Row2 + (3/2)Row1
   • Row3 = Row3 + Row1 $$\left[\begin{array}{ccccc}2& 1& -1& |& 8\\ 0& 0.5& 0.5& |& 1\\ 0& 2& 1& |& 5\end{array}\right]$$
3. Eliminate $y$ from row 3:
   • Row3 = Row3 - 4×Row2 $$\left[\begin{array}{ccccc}2& 1& -1& |& 8\\ 0& 0.5& 0.5& |& 1\\ 0& 0& 0& |& 1\end{array}\right]$$ Observation: Last row is $0=1$ → no solution (inconsistent system).

Pivoting for Numerical Stability

• Partial pivoting: Swap rows to place the largest absolute value in the pivot position.
• Scaled partial pivoting: Use row norms to avoid division by small numbers.
• Why? Prevents large rounding errors (e.g., dividing by near-zero pivots).

---

3. LU Decomposition

Factorize $A=LU$, where:

• $L$: Lower triangular with unit diagonal (or 1s).
• $U$: Upper triangular.

3.1 Doolittle’s Algorithm

For $A=LU$:

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}{cc}4& 3\\ 6& 3\end{array}\right]$$ Steps:

1. $U_{11}=4$, $L_{21}=6/4=1.5$
2. $U_{12}=3$, $U_{22}=3-(1.5)(3)=-1.5$
3. Final: $$L=\left[\begin{array}{cc}1& 0\\ 1.5& 1\end{array}\right],U=\left[\begin{array}{cc}4& 3\\ 0& -1.5\end{array}\right]$$

3.2 Crout’s Algorithm

Similar to Doolittle but stores $L$ with 1s on the diagonal in $U$ (less common in practice).

3.3 Applications

• Solve $Ax=b$ via:
  1. Solve $Ly=b$ (forward substitution).
  2. Solve $Ux=y$ (back substitution).
• Efficiency: $O(n^3)$ for decomposition, $O(n^2)$ per RHS (useful for multiple RHS vectors).

---

4. Cholesky Factorization

For symmetric positive-definite (SPD) matrices $A=L{L}^T$, where $L$ is lower triangular.

4.1 Algorithm

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

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

Example: Factorize

$$A=\left[\begin{array}{cc}4& 2\\ 2& 1\end{array}\right]$$ Steps:

1. $L_{11}=\sqrt{4}=2$
2. $L_{21}=2/2=1$
3. $L_{22}=\sqrt{1-1^2}=0$ Correction: $L_{22}=\sqrt{1-1}=0$ → Error! Recompute: $L_{22}=\sqrt{1-(1{)}^2}=0$ → Singular matrix? No, correct calculation: $L_{22}=\sqrt{1-1}=0$ is invalid. Actual: $L_{22}=\sqrt{1-(2/2{)}^2}=0$ → Issue: Matrix is not SPD (det(A) = 0). Valid SPD Example: Let $A=\left[\begin{array}{cc}5& 1\\ 1& 1\end{array}\right]$
   • $L_{11}=\sqrt{5}$
   • $L_{21}=1/\sqrt{5}$
   • $L_{22}=\sqrt{1-(1/\sqrt{5}{)}^2}=2/\sqrt{5}$

4.2 Advantages

• Faster: ~50% fewer operations than LU for SPD matrices.
• Numerically stable: No pivoting needed if $A$ is SPD.
• Applications: Least squares, quadratic optimization.

---

5. Comparison of Direct Methods

---

6. Error Analysis in Direct Methods

6.1 Sources of Error

1. Rounding errors: Accumulate during elimination/substitution.
2. Pivoting errors: Ill-conditioned matrices amplify errors.
3. Fill-in: LU decomposition may introduce non-zero entries where $A$ had zeros.

6.2 Condition Number

• Measures sensitivity to input changes: $\kappa (A)=\Vert A\Vert \Vert A^{-1}\Vert$.
• High $\kappa$: Small changes in $A$ or $b$ cause large changes in $x$.
• Example: $A=\left[\begin{array}{cc}1& 1\\ 1& 1.0001\end{array}\right]$ has $\kappa \approx 10^4$.

6.3 Partial Pivoting Impact

• Reduces error growth by ~100× in practice.
• Rule: Swap rows to maximize $|A_{kj}|$ in the pivot column.

---

7. Worked Problems (Exam-Style)

Problem 1: Gaussian Elimination with Pivoting

Solve: $$\{\begin{array}{l}0.0001x+y=1\\ x+y=2\end{array}$$ Solution:

1. Swap rows (pivoting).
2. Eliminate $x$ from row 2: $$\left[\begin{array}{cccc}1& 1& |& 2\\ 0.0001& 0.9999& |& 0.9998\end{array}\right]$$
3. Back substitution:
   • $y=0.9998/0.9999\approx 1$
   • $x=2-y=1$

Observation: Without pivoting, $x\approx 10^4$ (wrong due to division by 0.0001).

Problem 2: LU Decomposition

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

1. $U_{11}=2$, $L_{21}=4/2=2$, $L_{31}=-2/2=-1$
2. $U_{12}=1$, $U_{13}=1$
3. $U_{22}=-2-(2)(1)=-4$, $L_{32}=(1-(-1)(1))/(-4)=0.5$
4. $U_{23}=5-(2)(1)=3$, $U_{33}=-1-(-1)(1)-(0.5)(3)=-2.5$ Final: $$L=\left[\begin{array}{ccc}1& 0& 0\\ 2& 1& 0\\ -1& 0.5& 1\end{array}\right],U=\left[\begin{array}{ccc}2& 1& 1\\ 0& -4& 3\\ 0& 0& -2.5\end{array}\right]$$

---

8. Exam Tip: What to Expect

8.1 Common Question Types

1. Algorithm derivation: Derive LU decomposition steps or Gaussian elimination formulas.
2. Numerical examples: Solve systems using GE/LU/Cholesky (assume pivoting if needed).
3. Error analysis: Discuss pivoting, condition numbers, or rounding errors.
4. Comparison: Contrast LU vs. Cholesky (when to use each).
5. Theoretical questions:
   • Why is partial pivoting necessary?
   • When is Cholesky applicable?
   • What is fill-in in LU factorization?

8.2 High-Scoring Strategies

• Show all steps: Even partial credit for correct intermediate steps.
• Justify pivoting: Always mention pivoting in GE/LU unless the matrix is well-conditioned.
• Check SPD: For Cholesky, verify $A$ is symmetric and positive-definite (e.g., all leading principal minors > 0).
• Error bounds: Relate to condition number if asked about stability.
• Pseudocode: For algorithms like Doolittle’s, write 3–4 lines of pseudocode to earn marks.

8.3 Pitfalls to Avoid

• Ignoring pivoting: Solutions without pivoting may lose marks for numerical instability.
• Incorrect factorization: Double-check diagonal entries in $L$ or $U$.
• Assumptions: Never assume a matrix is SPD without verification.
• Units: In exams, state whether you’re using partial/scaled pivoting.

---

9. Summary Checklist

Before submitting, ensure your answer includes:

1. Definitions: Clear explanation of $LU$, Cholesky, and pivoting.
2. Algorithms: Step-by-step derivation or application.
3. Examples: At least one worked problem with numerical results.
4. Error discussion: Mention pivoting or condition numbers if relevant.
5. Comparisons: Tables or bullet points contrasting methods.
6. Exam tips: Highlighted key points for quick revision.

---

End of Note