Understanding SOR & Conjugate Gradient Methods

Welcome to an in-depth exploration of two powerful iterative techniques in numerical methods: the Successive Over-Relaxation (SOR) method and the Conjugate Gradient Method. These methods are essential tools for solving large systems of linear equations, particularly those arising from the discretization of partial differential equations.

The Problem: Poisson’s Equation

We begin with a concrete problem: solving Poisson’s equation on a unit square domain. This equation appears frequently in physics and engineering, making it an excellent test case for our numerical methods.

Setup

Domain: Unit square [0,1] × [0,1]
Grid: Uniform discretization with step size h = Δx = Δy
Boundary Conditions: Dirichlet conditions from known exact solution

The SOR Method: Accelerating Convergence

The SOR method builds upon simpler iterative techniques, introducing a clever acceleration parameter to speed up convergence.

How SOR Works

Basic Principle: SOR combines the previous iteration’s value with a Gauss-Seidel update:
```
U_{ij}^{new} = (1 - ω)U_{ij}^{old} + ω U_{ij}^{GS}
```
The Magic Parameter ω: For our unit square problem, the optimal relaxation parameter is:
```
ω = \frac{2}{1 + π h}
```

Why It Works

When ω < 1: Under-relaxation (more stable, slower convergence)
When ω > 1: Over-relaxation (faster convergence, potential instability)
Optimal ω: Balances speed and stability

The Conjugate Gradient Method: A Modern Approach

The Conjugate Gradient method represents a more sophisticated approach, drawing inspiration from optimization techniques.

Key Concepts

Residual: Measures how far we are from the solution:
```
r^{(n)} = f - Av^{(n)}
```
Search Directions: Each iteration moves along conjugate directions

The Algorithm

Initialize:
- Set initial guess v⁽⁰⁾
- Compute r⁽⁰⁾ = f - Av⁽⁰⁾
- Set q⁽⁰⁾ = r⁽⁰⁾

Iterate:

α_p = \frac{r_p^T r_p}{q_p^T A q_p}
v_{p+1} = v_p + α_p q_p
r_{p+1} = r_p - α_p A q_p
β_p = \frac{r_{p+1}^T r_{p+1}}{r_p^T r_p}
q_{p+1} = r_{p+1} + β_p q_p

Practical Implementation Tips

Matrix-Free Operations

Instead of storing the full matrix A, we can compute matrix-vector products directly:

(Av)_{ij} = \frac{v_{i+1,j} + v_{i-1,j} + v_{i,j+1} + v_{i,j-1} - 4v_{i,j}}{h^2}

Convergence Criteria

Monitor the relative residual:

\frac{\|r^{(k)}\|}{\|r^{(0)}\|} < tolerance

Method Comparison

Aspect	SOR	Conjugate Gradient
Setup Complexity	Simple	Moderate
Memory Usage	Low	Low
Convergence Speed	Good with optimal ω	Excellent for symmetric positive-definite systems
Parameter Tuning	Requires optimal ω	Parameter-free

Conclusion

Both methods have their place in numerical computing:

SOR: Simple to implement, effective with proper tuning
Conjugate Gradient: Faster convergence, especially for well-conditioned systems

The choice between them often depends on:

Problem structure (symmetry, positive-definiteness)
Implementation constraints
Required accuracy
Available computational resources

Understanding SOR & Conjugate Gradient Methods: A Deep Dive