Math 6610 • Analysis of Numerical Methods I

{Iterative Methods for Linear Systems}
Consider the linear system \(Ax=b\) and a splitting of \(A:A=M-K\), with \(M\)
nonsingular, and the iteration
\[
  x_{m+1}=Rx_m+c,
\]
where \(R=M^{-1}K\) and \(c=M^{-1}b\). Show that the method converges for any \(x_0\) if
\(\lVert R\rVert<1\) where \(\lVert\cdot\rVert\) is any operator norm.

Given an \((N-1)\times(N-1)\)
\[
\setlength{\arraycolsep}{5pt}
  A=
  \begin{bmatrix}
    2 & -1 & 0 & \cdots & 0\\
    -1 & 2 & -1 & \ddots & 0\\
    0 & -1 & \ddots & \ddots & 0\\
    \vdots & \ddots & -1 & 2 & -1\\
    0 & \cdots & 0 & -1 & 2
  \end{bmatrix},
  \qquad
  b=\frac{1}{N^2}
  \begin{pmatrix}
    f_1\\
    f_2\\
    \cdot\\
    f_{N-2}\\
    f_{N-1}
  \end{pmatrix}.
\]
Analyze the convergence properties of the Jacobi and Gauss-Seidel methods for this
problem. For each method, express the convergence speed as a function of \(N\). How
does the number of iterations required to reduce the initial error by a factor of
\(\delta\) depend on \(N\) for each method?