UNIT 1 • LINEAR SYSTEMS & ITERATIONS

SOR Method
Successive Over-Relaxation

The SOR method speeds up Gauss-Seidel by over-correcting each step: $x_i^{\text{new}} = (1 - \omega)\,x_i^{\text{old}} + \omega\,x_i^{\text{GS}}$ , where $x_i^{\text{GS}}$ is the Gauss-Seidel value and $\omega$ is the relaxation factor.

HOW SOR WORKS0 < ω < 2

x_i^{(k+1)} = (1 - \omega)\,x_i^{(k)} + \frac{\omega}{a_{ii}}\left(b_i - \sum_{j<i} a_{ij}x_j^{(k+1)} - \sum_{j>i} a_{ij}x_j^{(k)}\right)

1. Gauss-Seidel ValueWork out the usual Gauss-Seidel update, using new values as soon as you have them.

2. RelaxMix it with the old value:

(1 - \omega)

of the old,

\omega

of the new.

3. RepeatSweep through all equations again until the values stop changing.

Step-by-Step Worked Example

HAND-HOLDING TUTORIAL

OUR PROBLEM TO SOLVE

Solve $4x + 3y = 24$ , $3x + 4y - z = 30$ , $-y + 4z = -24$ by SOR with $\omega = 1.25$ , starting from $(0, 0, 0)$ .

STEP 01 • FIRST SWEEP

The old values are all 0, so $(1 - \omega) \times \text{old} = 0$ and only the Gauss-Seidel part counts:

x = \frac{1.25}{4}(24 - 0) = 7.5

y = \frac{1.25}{4}(30 - 3 \times 7.5) = 2.34375

z = \frac{1.25}{4}(-24 + 2.34375) = -6.767578

STEP 02 • SECOND SWEEP (NOW THE OLD VALUES COUNT)

x = (1 - 1.25)(7.5) + \frac{1.25}{4}(24 - 3 \times 2.34375) = 3.427734

Carry on the same way for y and z, then repeat.

STEP 03 • COMPARE WITH GAUSS-SEIDEL

To a tolerance of 0.0001, SOR with ω = 1.25 needs 10 sweeps; plain Gauss-Seidel (ω = 1) needs 20.

FINAL CONCLUSION

x = 3, y = 4, z = −5

(x, y, z) = (3, 4, -5)

The calculator below opens on this system and shows both iteration counts.

LABORATORY

Interactive SOR Calculator

LABORATORY

SOR Engine

Size of A:

A =

Right-hand side b (3 numbers)ω (0 to 2)ToleranceMax iterations

Common Questions

What is the SOR method?

Successive over-relaxation is Gauss-Seidel with a push: each new value is a mix of the old value and the Gauss-Seidel value, weighted by a relaxation factor

\omega

. With a good

\omega

it reaches the answer in far fewer iterations.

How do you choose ω?

\omega = 1

is plain Gauss-Seidel. Values between 1 and 2 over-relax and are usually faster; values between 0 and 1 under-relax, which can help a system that oscillates. The method can only converge for

0 < \omega < 2

. Try a few values and compare the iteration counts.

When does SOR converge?

It always converges for

0 < \omega < 2

when the matrix is symmetric and positive definite, and Gauss-Seidel converges when it is diagonally dominant. For other systems it may or may not converge.

PreviousGauss Seidel Method

Unit 1•7 of 63

NextNewton's Forward Formula

∑

f(x)∫dxπ

NETZ Engine

Evaluating numerical algorithm

UNIT 1 • LINEAR SYSTEMS & ITERATIONS

SOR Method
Successive Over-Relaxation

HOW SOR WORKS0 < ω < 2

x_i^{(k+1)} = (1 - \omega)\,x_i^{(k)} + \frac{\omega}{a_{ii}}\left(b_i - \sum_{j<i} a_{ij}x_j^{(k+1)} - \sum_{j>i} a_{ij}x_j^{(k)}\right)

1. Gauss-Seidel ValueWork out the usual Gauss-Seidel update, using new values as soon as you have them.

2. RelaxMix it with the old value:

(1 - \omega)

of the old,

\omega

of the new.

3. RepeatSweep through all equations again until the values stop changing.

Step-by-Step Worked Example

HAND-HOLDING TUTORIAL

OUR PROBLEM TO SOLVE

Solve $4x + 3y = 24$ , $3x + 4y - z = 30$ , $-y + 4z = -24$ by SOR with $\omega = 1.25$ , starting from $(0, 0, 0)$ .

STEP 01 • FIRST SWEEP

The old values are all 0, so $(1 - \omega) \times \text{old} = 0$ and only the Gauss-Seidel part counts:

x = \frac{1.25}{4}(24 - 0) = 7.5

y = \frac{1.25}{4}(30 - 3 \times 7.5) = 2.34375

z = \frac{1.25}{4}(-24 + 2.34375) = -6.767578

STEP 02 • SECOND SWEEP (NOW THE OLD VALUES COUNT)

x = (1 - 1.25)(7.5) + \frac{1.25}{4}(24 - 3 \times 2.34375) = 3.427734

Carry on the same way for y and z, then repeat.

STEP 03 • COMPARE WITH GAUSS-SEIDEL

To a tolerance of 0.0001, SOR with ω = 1.25 needs 10 sweeps; plain Gauss-Seidel (ω = 1) needs 20.

FINAL CONCLUSION

x = 3, y = 4, z = −5

(x, y, z) = (3, 4, -5)

The calculator below opens on this system and shows both iteration counts.

LABORATORY

Interactive SOR Calculator

LABORATORY

SOR Engine

Size of A:

A =

Right-hand side b (3 numbers)ω (0 to 2)ToleranceMax iterations

Common Questions

What is the SOR method?

Successive over-relaxation is Gauss-Seidel with a push: each new value is a mix of the old value and the Gauss-Seidel value, weighted by a relaxation factor

\omega

. With a good

\omega

it reaches the answer in far fewer iterations.

How do you choose ω?

\omega = 1

is plain Gauss-Seidel. Values between 1 and 2 over-relax and are usually faster; values between 0 and 1 under-relax, which can help a system that oscillates. The method can only converge for

0 < \omega < 2

. Try a few values and compare the iteration counts.

When does SOR converge?

It always converges for

0 < \omega < 2

when the matrix is symmetric and positive definite, and Gauss-Seidel converges when it is diagonally dominant. For other systems it may or may not converge.

PreviousGauss Seidel Method

Unit 1•7 of 63

NextNewton's Forward Formula

SOR Method Successive Over-Relaxation

Step-by-Step Worked Example

x = 3, y = 4, z = −5

Interactive SOR Calculator

SOR Engine

Common Questions

NETZ Engine

SOR Method Successive Over-Relaxation

Step-by-Step Worked Example

x = 3, y = 4, z = −5

Interactive SOR Calculator

SOR Engine

Common Questions

SOR Method
Successive Over-Relaxation

SOR Method
Successive Over-Relaxation