Iterative Methods for Linear Systems
(a) 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.
(b) 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 at the mesh points \(x_j=j/N\): \[ -u_{j-1}+2u_j-u_{j+1}=f_j=\frac {f(x_j)}{N^2}, \qquad j=1,2,\ldots ,N \] and the central difference for \(u'\) at \(x_N\) to eliminate the ghost point \(x_{N+1}\): \[ u_{N+1}=u_{N-1}. \] Use all the finite difference equations and the boundary conditions to obtain the linear system \(Au=b\), where \[ \setlength {\arraycolsep }{5pt} A= \begin {bmatrix} 2 & -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 & -2 & 2 \end {bmatrix}, \quad u= \begin {pmatrix} u_1\\ u_2\\ \vdots \\ u_{N-1}\\ u_N \end {pmatrix}, \quad b=\frac {1}{N^2} \begin {pmatrix} f_1\\ f_2\\ \vdots \\ f_{N-1}\\ f_N \end {pmatrix}. \]
Verify that \(A\) has eigenvectors \[ v^{(k)}= \begin {bmatrix} \sin \frac {k\pi }{2}x_1\\ \sin \frac {k\pi }{2}x_2\\ \cdot \\ \cdot \\ \sin \frac {k\pi }{2}x_j\\ \cdot \\ \cdot \\ \sin \frac {k\pi }{2}x_{N-1}\\ \sin \frac {k\pi }{2}x_N \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\)?