31 Linear Operators and the Poisson Equation
Differential equations become matrix problems after discretization. The finite matrix should preserve the main structure of the operator: sparsity, symmetry, definiteness, spectrum, and conditioning.
31.1 Differential Operators and Discretization
Map \(\mathcal{A}: X \to Y\) between function spaces satisfying: \[ \begin{align} \mathcal{A}(\alpha u + v) = \alpha \mathcal{A}u + \mathcal{A}v. \end{align} \] Matrices are finite-dimensional operators; \(\frac{d}{dx}\) and \(\nabla^2\) are infinite-dimensional.
The one-dimensional Poisson problem with homogeneous Dirichlet boundary data is \[ \begin{align} -u''(x)=f(x),\qquad 0<x<1,\qquad u(0)=u(1)=0. \end{align} \] The boundary conditions are part of the problem data.
For \(n\) interior grid points, let \(h=1/(n+1)\) and \(x_i=ih\), \(i=1,...,n\). A grid function is the vector \[ \begin{align} \bu=(u_1,...,u_n)^T,\qquad u_i\approx u(x_i). \end{align} \] The boundary values are fixed separately by the boundary conditions.
Approximating \(u''(x)\) on a grid with spacing \(h\): \[ \begin{align} u''(x_k) \approx \frac{u(x_{k-1}) - 2u(x_k) + u(x_{k+1})}{h^2}. \end{align} \] Accuracy: Second-order \(O(h^2)\) via Taylor expansion.
Taylor expand \(u(x+h)\) and \(u(x-h)\) about \(x\).
Add the two expansions.
Solve for \(u''(x)\).
Identify the leading error term and prove the \(O(h^2)\) claim in the result above.
Discretizing \(-d^2/dx^2\) on \([0,1]\) with \(u(0)=u(1)=0\) yields the tridiagonal system \(\bT \mathbf{u} = \mathbf{f}\): \[ \begin{align} \bT = \frac{1}{h^2} \text{tridiag}(-1, 2, -1) \in \fR^{n \times n}. \end{align} \]
(Sparsity) Each row of \(\bT\) uses only the grid point and its two neighbors. This locality is why finite difference matrices are sparse.
Eigenvalues of \(\bT\) are \(\lambda_k = \frac{4}{h^2} \sin^2(\frac{k\pi}{2(n+1)})\). As \(n \to \infty\), \(\lambda_k \to k^2 \pi^2\) (eigenvalues of continuous \(-d^2/dx^2\)).
Let \((\bv_k)_j=\sin(jk\pi h)\) with \(h=1/(n+1)\).
Compute the \(j\)-th entry of \(\bT\bv_k\).
Use \(\sin(A-B)+\sin(A+B)=2\sin A\cos B\).
Use \(1-\cos\theta=2\sin^2(\theta/2)\).
Derive the eigenvalue formula in the result above.
Let \(h\to 0\) with fixed \(k\) and recover \(k^2\pi^2\).
The matrix \(\bT\) in the result above is sparse, symmetric positive definite, and has condition number \[ \begin{align} \kappa_2(\bT)=O(h^{-2}). \end{align} \]
Sparsity and symmetry are immediate from the tridiagonal stencil. By the result above, all eigenvalues are positive because \(1\leq k\leq n\) and \(0<k\pi/(2(n+1))<\pi/2\). Thus \(\bT\) is SPD. Also \[ \begin{align} \lambda_{\min}\sim \pi^2, \qquad \lambda_{\max}\sim \frac{4}{h^2}, \end{align} \] so \(\kappa_2(\bT)=\lambda_{\max}/\lambda_{\min}=O(h^{-2})\).
Use the stencil to count the number of nonzeros in \(\bT\).
Use the quadratic form \(\bu^T\bT\bu\) to show positive definiteness for nonzero interior grid functions.
Use the result above to estimate \(\lambda_{\min}\) and \(\lambda_{\max}\).
Derive the condition number estimate in the result above.
31.2 Operator Norms and Conditioning
An operator is bounded if \(\|\mathcal{A}u\|_Y \leq C \|u\|_X\) for some \(C < \infty\).
Matrices are always bounded.
Differential operators are unbounded.
Numerical Consequence: Because the continuous Laplacian is unbounded, its discretization \(\bT\) becomes increasingly ill-conditioned as \(h \to 0\): \[ \begin{align} \kappa(\bT) = \frac{\lambda_{\max}}{\lambda_{\min}} \approx \frac{4/h^2}{\pi^2} = O(h^{-2}). \end{align} \] Refining the grid \(2\times\) quadruples the condition number.
(Solver consequence) Dense Gaussian elimination ignores sparsity. For Poisson matrices, sparse Cholesky, CG with preconditioning, multigrid, or FFT-based solvers are the natural algorithms, depending on geometry and boundary conditions.
31.3 Exercises
Build \(\bT\) for \(n=50\) and plot its eigenvalues vs. \(k^2 \pi^2\) using the result above.
Show that \(\kappa(\bT) \to \infty\) as \(n \to \infty\) using the result above.
Implement a 2-D Poisson solver on a unit square. Verify \(O(N^{3/2})\) cost for direct sparse solve.
Prove the differentiation operator is unbounded on \(L^2[0,1]\) using \(u_k(x) = \sin(k\pi x)\).