Lab 14: Iterative Methods Lab · Numerical Methods

Type a 2×2 system as "a₁₁ a₁₂ b₁; a₂₁ a₂₂ b₂". Choose the method and step through. The note under the table gives diagonal dominance and the spectral radius ρ.

Jacobi, Gauss–Seidel and SOR on an N × N grid. Change N, the edge temperatures and ω. Which ω gives the fewest sweeps?

Jacobi and Gauss–Seidel

Try this

Run it. How many iterations does each method need?
Swap the first two equations (and b). What happens, and why?
Change tol to 1e-10. How many more iterations?

SOR on the plate

Try this

Run it. Which ω is best? Compare with the formula.
Set N = 20 (Python: N = 20; C: #define N 20). How do the counts change?

Q1 Distinguish the Jacobi and Gauss–Seidel methods.

Both solve equation

i

for

x_i

. Jacobi uses only values from the previous iteration (two vectors, easy to parallelise); Gauss–Seidel uses each new value as soon as it is computed (one vector, usually about twice as fast).

Q2 State a sufficient condition for convergence of the Jacobi and Gauss–Seidel methods.

Strict diagonal dominance:

|a_{ii}| > \sum_{j\ne i}|a_{ij}|

for every row. More generally, the iteration converges for every start iff the spectral radius of the iteration matrix is less than 1.

Q3 Solve

10x + y + z = 12

,

x + 10y + z = 12

,

x + y + 10z = 12

by Gauss–Seidel.

From 0:

(1.2, 1.08, 0.972)

,

(0.9948, 1.0033, 1.0002)

,

(0.9996, 1.0000, 1.0000)

, then

(1.0000, 1.0000, 1.0000)

. Solution

(1, 1, 1)

.

Q4 Find the spectral radius of

T_J

for

\begin{pmatrix} 5 & 2 \\ 3 & 6\end{pmatrix}

.

T_J = \begin{pmatrix} 0 & -0.4 \\ -0.5 & 0\end{pmatrix}

,

\lambda^2 = 0.2

,

\rho = 0.4472

. For Gauss–Seidel

\rho = 0.2

.

Q5 What is SOR and what does ω do?

Successive over-relaxation:

x_i \leftarrow (1 - \omega)x_i + \omega\,\tilde x_i

, where

\tilde x_i

is the Gauss–Seidel value.

\omega = 1

is Gauss–Seidel;

1 < \omega < 2

over-relaxes and, with a good choice (for the plate

2/(1 + \sin(\pi/(N+1)))

), reduces the number of sweeps dramatically. It diverges for

\omega \ge 2

.