CS223 · Iterative Methods · Annotated SlidesIterative Methods for Linear Systems
Original
Overview

Iterative Methods for Linear Systems

Why iterative methods for large sparse systems, convergence and diagonal dominance, the Jacobi and Gauss–Seidel methods with worked examples, and successive over-relaxation (SOR).

How to read this page

Every original slide is shown unchanged. Yellow marks on a slide point to a numbered note: hover or tap a mark to jump to its note, and hover a note to see its marks. Questions tagged Past exam appeared on a real paper; Prediction questions are likely angles, not confirmed. Pick an answer to each question: a wrong pick tells you why it is wrong, so you can try again.

All 25 slides
  1. 1 Slide 1
  2. 2 Solving linear systems
  3. 3 Why to use iterative methods?
  4. 4 What are iterative methods?
  5. 5 What are iterative methods?
  6. 6 What are iterative methods?
  7. 7 What are iterative methods?
  8. 8 What are iterative methods?
  9. 9 What are iterative methods?
  10. 10 What are iterative methods?
  11. 11 What is convergence?
  12. 12 What is a diagonally dominant matrix?
  13. 13 Example:
  14. 14 Popular iterative methods
  15. 15 Jacobi method
  16. 16 Jacobi method (example)
  17. 17 Jacobi method (example)
  18. 18 Jacobi method (example)
  19. 19 Gauss-Seidel method
  20. 20 Gauss-Seidel method
  21. 21 Gauss-Seidel method (example)
  22. 22 Gauss-Seidel method (example 2)
  23. 23 Successive over relaxation method
  24. 24 Successive over relaxation method
  25. 25 Beyond basic methods
Slide 1 / 25

Slide 1

Slide 1: Slide 1
Slide 2 / 25

Solving linear systems

Slide 2: Solving linear systems
Slide 3 / 25

Why to use iterative methods?

Slide 3: Why to use iterative methods?

Notes

  1. Iterative methods start from a guess and improve it; good for large sparse systems where elimination is too costly.

Slide 4 / 25

What are iterative methods?

Slide 4: What are iterative methods?
Slide 5 / 25

What are iterative methods?

Slide 5: What are iterative methods?
Slide 6 / 25

What are iterative methods?

Slide 6: What are iterative methods?
Slide 7 / 25

What are iterative methods?

Slide 7: What are iterative methods?
Slide 8 / 25

What are iterative methods?

Slide 8: What are iterative methods?
Slide 9 / 25

What are iterative methods?

Slide 9: What are iterative methods?
Slide 10 / 25

What are iterative methods?

Slide 10: What are iterative methods?
Slide 11 / 25

What is convergence?

Slide 11: What is convergence?
Slide 12 / 25

What is a diagonally dominant matrix?

Slide 12: What is a diagonally dominant matrix?

Notes

  1. Strictly diagonally dominant: |aᵢᵢ| > Σ_{j≠i} |aᵢⱼ| in every row. Then Jacobi and Gauss–Seidel converge for any starting vector.

Exam angle

PredictionQ1

Which matrix is strictly diagonally dominant?

Slide 13 / 25

Example:

Slide 13: Example:
Slide 14 / 25

Popular iterative methods

Slide 14: Popular iterative methods
Slide 15 / 25

Jacobi method

Slide 15: Jacobi method

Notes

  1. Jacobi: xᵢ⁽ᵏ⁺¹⁾ = (bᵢ − Σ_{j≠i} aᵢⱼxⱼ⁽ᵏ⁾)/aᵢᵢ: every component uses the OLD vector.

Slide 16 / 25

Jacobi method (example)

Slide 16: Jacobi method (example)
Slide 17 / 25

Jacobi method (example)

Slide 17: Jacobi method (example)
Slide 18 / 25

Jacobi method (example)

Slide 18: Jacobi method (example)
Slide 19 / 25

Gauss-Seidel method

Slide 19: Gauss-Seidel method

Notes

  1. Gauss–Seidel: same formula but uses each NEW component as soon as it is computed; usually converges faster.

  2. Memory trick Jacobi = all old values; Gauss–Seidel = newest values immediately.

Exam angle

PredictionQ1

One Jacobi step for 4x − y = 3, x + 5y = 6 from (0, 0).

Compare with the model answer

x = (3 + y)/4 = 0.75, y = (6 − x)/5 = 1.2 using the old x = 0, so (0.75, 1.2). (Gauss–Seidel would use x = 0.75: y = (6 − 0.75)/5 = 1.05.)

Slide 20 / 25

Gauss-Seidel method

Slide 20: Gauss-Seidel method
Slide 21 / 25

Gauss-Seidel method (example)

Slide 21: Gauss-Seidel method (example)
Slide 22 / 25

Gauss-Seidel method (example 2)

Slide 22: Gauss-Seidel method (example 2)
Slide 23 / 25

Successive over relaxation method

Slide 23: Successive over relaxation method
Slide 24 / 25

Successive over relaxation method

Slide 24: Successive over relaxation method
Slide 25 / 25

Beyond basic methods

Slide 25: Beyond basic methods