Math 6610 • Analysis of Numerical Methods I

{Elliptic Problems}

Consider the standard five-point difference approximation (centered difference
for both the gradient and divergence operators) for the variable coefficient
Poisson equation
\[
  -\nabla\cdot(a\nabla v)=f
\]
with Dirichlet boundary conditions, in a two-dimensional rectangular region. We
assume that \(a(x,y)\geq a_0>0\). The approximate solution \(\{u_{i,j}\}\) satisfies
a linear system \(Au=b\).

\textbf{1.} State and prove the maximum principle for the numerical solution
\(u_{i,j}\).

\textbf{2.} Derive the matrix \(A\) in the one-dimensional case and show that it
is symmetric and positive definite.

\textbf{3.} For the one-dimensional and constant-coefficient case, show that
the global error \(e_j=v(x_j)-u_j\) satisfies \(\|e\|_2=O(h^2)\) as the space step
\(h\to0\).

\textbf{4.} Discuss the advantages and disadvantages of trying to solve the
system for the two-dimensional problem using \textbf{(i)} the SOR (Successive
Over Relaxation) method and \textbf{(ii)} the (preconditioned) Conjugate
Gradient method.

\newpage

\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 & \vdots & \vdots\\
    0 & 1 & -2 & \ddots & 0 & 0\\
    \vdots & \ddots & \ddots & \ddots & 1 & 0\\
    0 & \cdots & 0 & 1 & -2 & 1\\
    0 & \cdots & 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 & \vdots & \vdots\\
    0 & 1 & -2 & \ddots & 0 & 0\\
    \vdots & \ddots & \ddots & \ddots & 1 & 0\\
    0 & \cdots & 0 & 1 & -2 & 1\\
    0 & \cdots & 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\).