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

Banded systems and PDE

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

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

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

$$$T_N [v_1,\ldots,v_N]^T = h^2 [f_1,\ldots,f_N]^T.$$$
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,

$$$u_{xx}+u_{yy}=f(x,y),$$$

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$$?