Homework 5, due in class 2016-02-26ΒΆ

Banded systems and PDE

Let \(f\in C_{[0,1]}\) be given, and \(u\) solve

\[\begin{equation} -u_{xx} = f~,\quad x\in [0, 1]~, \quad u(0) = u(1) = 0. \end{equation}\]

For given \(N\), an approximation \(v_i\) of \(u(x_i), x_i=ih, h=1/(N+1)\) is given by

\[\begin{split}\begin{eqnarray} -v_{i+1} + 2 v_{i} - v_{i-1} &=& h^2 f_i~, \quad i = 1,\ldots, N~, \quad h = 1 / (N+1),\\ &&v_0 = v_{N+1}=0 \end{eqnarray}\end{split}\]

where \(f_i=f(x_i)\). The above equations form a linear system in \(v_i\) which can be written as

\[\begin{equation} T_N [v_1,\ldots,v_N]^T = h^2 [f_1,\ldots,f_N]^T. \end{equation}\]
  1. Show that the eigenvalues and eigenvectors of \(T_N\) are \(\lambda_j = 2(1-\cos ( \frac{\pi j }{N+1}))\) and \(z_j\), with components \(z_j^k = \sqrt{\frac{2}{N+1}} \sin ( \frac{\pi j k}{N+1})\).

  2. Let \(Z = [z_1, z_2, \ldots, z_N]\), and \(T_N = Z \Lambda Z^T\), and consider the equivalent problem in 2D,

    \[\begin{equation} u_{xx}+u_{yy}=f(x,y), \end{equation}\]

    where \((x,y)\in D=[0,1]\times[0,1]\), and \(u=0 \, {\rm on} \, \partial D\) with the approximation \(v_{i,j}\) of \(u(x_i,y_j)\) given by

    \[\begin{split}\begin{eqnarray} -v_{i+1,j} - v_{i-1,j} -v_{i,j+1} - v_{i,j-1} + 4 v_{i,j} = h^2 f_{i,j}, \\ v_{i,0}=v_{i,N+1}=v_{0,j}=v_{N+1,j}=0, \\ i,j = 1,\ldots,N, \end{eqnarray}\end{split}\]

    where \(f_{i,j}=f(x_i,y_j)\), \(x_i=ih, y_j=jh, h=1/(N+1)\). Show that equations the above equations can be written as a matrix equation

    \[\begin{eqnarray} T_N V + V T_N = h^2 F. \end{eqnarray}\]

    Here \(V_{i,j} = v_{i,j}\) and \(F_{i,j} = f_{i,j}\).

  3. Let \(V' = Z^TVZ\). Show that the solution \(V\) can be found by the following steps

    \[\begin{split}\begin{eqnarray} F' = Z^T F Z, \\ v'_{j,k} = \frac{h^2 f'_{j,k}}{\lambda_j + \lambda_k}, \\ V = ZV'V^T. \end{eqnarray}\end{split}\]
  4. To leading order in \(N\), how many operations does it require to solve as described above? (Later we will see how this system can be solved with complexity \(O (N^2 \log N)\).)

Cholesky

A real square matrix \(A\) is called positive definite symmetric (PDS) if it is symmetric, \(A=A^T\), and for any vector \(x\neq0\):

\[\begin{split}\begin{eqnarray} x^TAx > 0. \end{eqnarray}\end{split}\]
  1. Show that all the eigenvalues of a PDS are real and positive.
  2. Let \(A^{(k)}\) be the principal leading submatrix of \(A\). Show that \(A^{(k)}\) is also PDS.
  3. Use the results above to show that if Gaussian elimination without pivoting is applied to a PDS matrix, only positive pivots are encountered. Hint: consider the relationship between the pivots, the determinant and the eigenvalues.
  4. Use 3. to prove the existence of the Cholesky decomposition of a PDS matrix: \(A=LL^T\) where \(L\) is lower triangular.

Banded systems

A band matix \(A\) is a matrix whose nonzero elements are located in a band centered along the principal diagonal. For such matrices only a small portion of the \(n^2\) elements are nonzero. A square matrix \(A\) has lower bandwidth \(r < n\) and upper bandwidth \(s<n\) if

\[\begin{split}\begin{eqnarray} a_{ij} = 0, i > j+r, \ \ \ \ a_{ij} =0 j > i+s. \end{eqnarray}\end{split}\]

Let \(A_1, A_2 \in \mathbb{R}^{n \times n}\) have lower bandwidth \(r_1\) and \(r_2\) and upper bandwidth \(s_1\) and \(s_2\) respectively. What is the bandwidths of \(A_1+A_2\), \(A_1A_2\) and \(A_2A_1\)?