Ch20.3 Linear Systems: Solution by Iteration

Solving Linear Systems Iteratively

  • Using Gauss elimination to solve \( A\mathbf{x} = \mathbf{b} \) can be costly in terms of flop count, and hence slow and possibly inaccurate.
    • For an \( n \times n \) system, the flop count is \( O(n^3) \).
  • Jacobi Iteration is a good introduction to iterative methods.
  • Gauss-Seidel iteration is an improvement on Jacobi method.
  • Convergence is guaranteed if \( A \) is diagonally dominant.

\[ \begin{bmatrix} 1.0 & 0.5 \\ 0.4 & 1.0 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} = \begin{bmatrix} 2 \\ 3 \end{bmatrix} \]

Humor



When's the best time to go to the dentist?

Tooth-hurtie!

Example 1: Jacobi Iteration (p1)

Example 1: Jacobi Iteration (p2)

Example 1: Jacobi Iteration (p3)

Example 2: Jacobi Iteration (p1)

Example 2: Jacobi Iteration (p2)

Example 2: Jacobi Iteration (p3)

Example 3: Jacobi Iteration (p1)

Example 3: Jacobi Iteration (p2)

Example 3: Jacobi Iteration (p3)

Example 3: Jacobi Iteration (p4)

Example 4: Gauss-Seidel Iteration (p1)

Example 4: Gauss-Seidel Iteration (p2)

Example 4: Gauss-Seidel Iteration (p3)

Example 5: Gauss-Seidel Iteration (p1)

Example 5: Gauss-Seidel Iteration (p2)

Example 5: Gauss-Seidel Iteration (p3)

Example 6: Gauss-Seidel Iteration (p1)

Example 6: Gauss-Seidel Iteration (p2)

Example 6: Gauss-Seidel Iteration (p3)

Convergence of Iterative Methods

Matrix Norm Examples

Diagonal Dominance & Convergence

Diagonal Dominance & Row Swap

Octave Example

Use Jacobi iteration to solve \( A \mathbf{x} = \mathbf{b} \) where

\[ A = \begin{bmatrix} 1.0 & 0.2 \\ 0.3 & 1.0 \end{bmatrix}, \,\,\,\, \mathbf{b} = \begin{bmatrix} 3 \\ 4 \end{bmatrix} \]

Since \( A \) is diagonally dominant, we iterate as follows:

\[ \mathbf{x}^{(k+1)} = \mathbf{b} + C\mathbf{x}^{(k)} \]

where

\[ C = I - A = \begin{bmatrix} 0 & -0.2 \\ -0.3 & 0 \end{bmatrix} \]

Outline of Octave Program

See Notes for the Octave program and results.

  • Using Octave, we will see that \( \lVert C \rVert <1 \).
  • Choose initial vector to be

\[ \mathbf{x}^{(0)} = \begin{bmatrix} 1 \\ 2 \end{bmatrix} \]

  • Compare results of iteration to \( \mathbf{u} = A^{-1} \mathbf{b} \).

  • There will be some error between early iterates \( \mathbf{x}^{(k)} \) and \( \mathbf{u} \).

  • Measure \( \mathbf{e}^{(k)} = \mathbf{u}- \mathbf{x}^{(k)} \) using Frobenius vector norm.