Questions: Successive Over-Relaxation (SOR)

Question 1

SOR is applied with ω = 1.5 to solve a linear system. At one update step, the Gauss-Seidel formula gives x_i^{GS} = 3.0 and the current value is x_i^{(k)} = 2.0. What is x_i^{(k+1)}?

• A. 3.0 — SOR with ω > 1 just accepts the Gauss-Seidel update directly
• B. 3.5 — SOR extrapolates past the Gauss-Seidel update in the direction of improvement
• C. 2.5 — SOR averages the current value and the Gauss-Seidel update
• D. 1.5 — SOR scales the Gauss-Seidel update by ω

Answer: (B)

Applying the SOR formula: x_i^{(k+1)} = (1 − ω)x_i^{(k)} + ω·x_i^{GS} = (1 − 1.5)(2.0) + (1.5)(3.0) = (−0.5)(2.0) + (1.5)(3.0) = −1.0 + 4.5 = 3.5. With ω = 1.5, SOR overshoots the Gauss-Seidel value: the current value is 2.0, G-S says go to 3.0 (a step of +1.0), and SOR goes to 3.5 (a step of +1.5 = ω × the G-S step). This extrapolation is the essence of over-relaxation — it 'leaps' further in the direction Gauss-Seidel is heading, betting that direction is toward the solution.

Question 2

Why is finding the optimal relaxation parameter ω difficult for general matrices in practice?

• A. The SOR formula becomes unstable for arbitrary ω, so numerical experiments are too risky
• B. The optimal ω formula requires the spectral radius of the Gauss-Seidel iteration matrix, which is only analytically available for matrices with special structure (like Property A)
• C. General matrices require ω < 1 (under-relaxation), which is never beneficial
• D. The optimal ω depends on the right-hand side vector b, which changes with each problem

Answer: (B)

The formula ω_opt = 2 / (1 + √(1 − ρ²)) requires knowing ρ, the spectral radius of the Gauss-Seidel iteration matrix. For special matrix structures — like those arising from the five-point stencil discretization of Poisson's equation — ρ can be computed analytically. For general sparse matrices, no such formula exists. In practice, ω must be estimated by running several iterations and measuring the observed convergence rate, or through adaptive algorithms. This is why SOR is most powerful when the matrix has exploitable structure.

Question 3

Setting ω = 1 in the SOR update formula x_i^{(k+1)} = (1−ω)x_i^{(k)} + ω·x_i^{GS} recovers plain Gauss-Seidel iteration.

• T. True
• F. False

Answer: True

Substituting ω = 1: x_i^{(k+1)} = (1 − 1)x_i^{(k)} + 1·x_i^{GS} = 0 + x_i^{GS} = x_i^{GS}. The current value is ignored and the update is exactly the Gauss-Seidel step. This shows that SOR is a generalization of Gauss-Seidel, with ω = 1 as the special case. The ω parameter blends the current value with the Gauss-Seidel update, and ω = 1 means 'take the G-S update with weight 1 and the current value with weight 0.'

Question 4

SOR is very likely to converge for any positive value of ω, provided the system Ax = b has a unique solution.

• T. True
• F. False

Answer: False

SOR is only guaranteed to converge when 0 < ω < 2. Outside this range — particularly for ω ≥ 2 — the iteration diverges regardless of the matrix properties. Within (0, 2), convergence still depends on the matrix (diagonal dominance or positive definiteness are sufficient conditions). The bound ω < 2 is a hard theoretical requirement, not a practical guideline. Choosing ω = 2.1, for example, will cause the iterates to grow without bound even for well-conditioned systems.

Question 5

Why does over-relaxation (ω > 1) speed up convergence compared to plain Gauss-Seidel, and what property of the iteration determines the optimal ω?

Model answer: Convergence rate is governed by the spectral radius ρ of the iteration matrix — the magnitude of its largest eigenvalue. For Gauss-Seidel applied to problems like discretized PDEs, ρ is close to 1, meaning slow convergence. Over-relaxation with the optimal ω reduces ρ substantially: the optimal SOR iteration matrix has a much smaller spectral radius, cutting the number of iterations needed from O(N²) to O(N) for an N×N grid. Geometrically, over-relaxation 'leaps' further in the direction of improvement at each step, reducing the number of steps needed to reach the solution to within tolerance.

The key insight is that Gauss-Seidel is already moving in the right direction — toward the solution. SOR asks: if we know the direction is right, why not take a bigger step? The answer is that bigger steps reduce the spectral radius of the iteration matrix, which is the mathematical quantity governing how quickly errors shrink. The optimal ω makes the spectral radius as small as possible, which is why knowing ρ of the Gauss-Seidel matrix is the key to computing ω_opt.