CS223 · Annotated SlidesIterative Methods — Iterative Methods for Linear Systems
Iterative Methods · Annotated slides

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).

Slide text Study notes Highlight: key words Tips, tricks & traps Seen again elsewhere How it can come up
Slide 1: Slide 1
Exam weight Low
    Slide 2: Solving linear systems
    Exam weight Low
      Slide 3: Why to use iterative methods?
      Exam weight Low
      1. Iterative methods start from a guess and improve it; good for large sparse systems where elimination is too costly.
      Slide 4: What are iterative methods?
      Exam weight Low
        Slide 5: What are iterative methods?
        Exam weight Low
          Slide 6: What are iterative methods?
          Exam weight Low
            Slide 7: What are iterative methods?
            Exam weight Low
              Slide 8: What are iterative methods?
              Exam weight Low
                Slide 9: What are iterative methods?
                Exam weight Low
                  Slide 10: What are iterative methods?
                  Exam weight Low
                    Slide 11: What is convergence?
                    Exam weight Low
                      Slide 12: What is a diagonally dominant matrix?
                      Exam weight High
                      1. Strictly diagonally dominant: |aᵢᵢ| > Σ_{j≠i} |aᵢⱼ| in every row. Then Jacobi and Gauss–Seidel converge for any starting vector.
                      🎯 How this can come up · 1 question
                      MCQ

                      Which matrix is strictly diagonally dominant?

                      Slide 13: Example:
                      Exam weight Low
                        Slide 14: Popular iterative methods
                        Exam weight Low
                          Slide 15: Jacobi method
                          Exam weight Low
                          1. Jacobi: xᵢ⁽ᵏ⁺¹⁾ = (bᵢ − Σ_{j≠i} aᵢⱼxⱼ⁽ᵏ⁾)/aᵢᵢ: every component uses the OLD vector.
                          Slide 16: Jacobi method (example)
                          Exam weight Low
                            Slide 17: Jacobi method (example)
                            Exam weight Low
                              Slide 18: Jacobi method (example)
                              Exam weight Low
                                Slide 19: Gauss-Seidel method
                                Exam weight High
                                1. Gauss–Seidel: same formula but uses each NEW component as soon as it is computed; usually converges faster.
                                Memory trickJacobi = all old values; Gauss–Seidel = newest values immediately.
                                🎯 How this can come up · 1 question
                                Written

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

                                Slide 20: Gauss-Seidel method
                                Exam weight Low
                                  Slide 21: Gauss-Seidel method (example)
                                  Exam weight Low
                                    Slide 22: Gauss-Seidel method (example 2)
                                    Exam weight Low
                                      Slide 23: Successive over relaxation method
                                      Exam weight Low
                                      1. SOR: Gauss–Seidel with a relaxation factor ω (1 < ω < 2 over-relaxes to speed convergence; ω = 1 is Gauss–Seidel).
                                      Slide 24: Successive over relaxation method
                                      Exam weight Low
                                        Slide 25: Beyond basic methods
                                        Exam weight Low