Math 6610 • Analysis of Numerical Methods I

{Finite-Difference Methods}
Consider the initial boundary value problem
\[
  v_t=\beta v_{xx},\qquad 0<x<1,\qquad 0<t,\qquad v(x,0)=f(x)
\]
with Dirichlet boundary conditions
\[
  v(0,t)=0,\qquad v(1,t)=0.
\]

Suppose that the interval \([0,1]\) is partitioned by meshpoints \(x_j=jh\) for
\(j=0,1,\ldots,N\) and \(h=1/N\). A possible discretization of the above problem uses
the Crank-Nicolson scheme for the differential equation:
\[
  \left(I-\frac{\beta k}{2}D_+D_-\right)u_j^{n+1}
  =
  \left(I+\frac{\beta k}{2}D_+D_-\right)u_j^n
\]
for \(j=1,\ldots,N-1\), combined with the boundary conditions:
\[
  u_0^n=0\qquad \text{and}\qquad u_N^n=0
\]
for each time level \(n\). Initial data is obtained from by setting \(u_j^0=f_j\) for
\(j=0,1,\ldots,N\). (Note that \(D_+\) and \(D_-\) are the usual forward and backward
difference operators.)

Set up the matrix system that must be solved in order to advance the numerical
solution from time level \(n\) to time level \(n+1\). Show that the suggested
discretization is stable in the \(\ell_2\) norm
\[
  \lVert u\rVert_2=
  \left(\sum_{j=0}^N h\lvert u_j\rvert^2\right)^{1/2}
\]
for \textit{all} choices of timestep \(k\) and spacestep \(h\). What other issues should
be considered in deciding whether the suggested scheme is a good choice for the
problem?

\fact{1} A real symmetric \(n\times n\) matrix \(A\) can be diagonalized by an
orthogonal similarity transformation, and \(A\)'s eigenvalues are real.

\fact{2} The \((N-1)\times(N-1)\) matrix \(M\) defined by
\[
  M=
  \begin{bmatrix}
    -2 & 1 & 0 & \cdots & 0 & 0\\
    1 & -2 & 1 & \ddots & 0 & 0\\
    0 & 1 & -2 & \ddots & 0 & 0\\
    \vdots & \ddots & \ddots & \ddots & 1 & 0\\
    0 & 0 & 0 & 1 & -2 & 1\\
    0 & 0 & 0 & 0 & 1 & -2
  \end{bmatrix}
\]
has eigenvalues
\[
  \mu_l=-4\sin^2\left(\frac{\pi l}{2N}\right),\qquad l=1,2,\ldots,N-1.
\]

\fact{3} The \((N+1)\times(N+1)\) matrix:
\[
  \begin{bmatrix}
    -1 & 1 & 0 & \cdots & 0 & 0\\
    1 & -2 & 1 & \ddots & 0 & 0\\
    0 & 1 & -2 & \ddots & 0 & 0\\
    \vdots & \ddots & \ddots & \ddots & 1 & 0\\
    0 & 0 & 0 & 1 & -2 & 1\\
    0 & 0 & 0 & 0 & 1 & -1
  \end{bmatrix}
\]
has eigenvalues
\[
  \mu_l=-4\sin^2\left(\frac{\pi l}{2(N+1)}\right),\qquad l=0,1,\ldots,N.
\]

\fact{4} For a real \(n\times n\) matrix \(A\), the Rayleigh quotient of a vector
\(x\in\R^n\) is the scalar
\[
  r(x)=\frac{x^TAx}{x^Tx}.
\]
The gradient of \(r(x)\) is
\[
  \nabla r(x)=\frac{2}{x^Tx}(Ax-r(x)x).
\]
If \(x\) is an eigenvector of \(A\) then \(r(x)\) is the corresponding eigenvalue and
\(\nabla r(x)=0\).