Math 6610 • Analysis of Numerical Methods I

{Iterative Methods for Linear Systems}

\textbf{a)} (6\%) Consider the linear system \(Ax=b\) and a splitting of
\(A:A=M-K\), with \(M\) being nonsingular, an iterative method is to iterate
\[
  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.

\textbf{b)} (14\%) To solve the boundary value problem
\[
  -u''(x)=f(x),\qquad \text{for }0<x<1,
\]
with \(u'(0)=0\) and \(u(1)=0\), we use second-order central differences for the
discretization of the equation at mesh points \(x_j=j/N\):
\[
  -u_{j-1}+2u_j-u_{j+1}=f_j=\frac{f(x_j)}{N^2},
  \qquad j=0,1,\ldots,N-1
\]
and the central difference approximation for \(u'\) at \(x_0=0\): \(u_1-u_{-1}=0\), to
eliminate the ghost point.

Show that the finite difference equations and the boundary conditions lead to the
following linear system \(Au=b\), where
\[
\setlength{\arraycolsep}{5pt}
  A=
  \begin{bmatrix}
    1 & -1 & 0 & \cdots & 0 & 0\\
    -1 & 2 & -1 & \cdots & 0 & 0\\
    0 & -1 & 2 & \ddots & 0 & 0\\
    \vdots & \vdots & \ddots & \ddots & -1 & 0\\
    0 & 0 & 0 & -1 & 2 & -1\\
    0 & 0 & 0 & 0 & -1 & 2
  \end{bmatrix},
  \quad
  u=
  \begin{pmatrix}
    u_0\\
    u_1\\
    \vdots\\
    u_{N-2}\\
    u_{N-1}
  \end{pmatrix},
  \quad
  b=\frac{1}{N^2}
  \begin{pmatrix}
    \frac{1}{2}f_0\\
    f_1\\
    \vdots\\
    f_{N-2}\\
    f_{N-1}
  \end{pmatrix}.
\]
Notice that equations are scaled so that \(A\) is symmetric. Determine if \(A\) has
eigenvectors
\[
  v^{(k)}=
  \begin{bmatrix}
    1\\
    \cos\frac{1}{2}k\pi x_1\\
    \vdots\\
    \cos\frac{1}{2}k\pi x_j\\
    \vdots\\
    \cos\frac{1}{2}k\pi x_{N-2}\\
    \cos\frac{1}{2}k\pi x_{N-1}
  \end{bmatrix},
  \qquad
  k=1,3,5,\ldots,2N-3,2N-1,
\]
and use them to find the eigenvalues of the iteration matrix \(R\) for the Jacobi
method. Analyze the convergence properties of the Jacobi method applied to this
problem, and 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\)? In reality, should you use an iterative method to solve this matrix problem? If
not, what other method is preferred?