31 Linear Operators and the Poisson Equation
Transitioning from finite matrices to infinite-dimensional operators.
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.
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.
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} \]
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\)).
We verify \(\bT\bv_k = \lambda_k \bv_k\) by component-wise substitution. The \(j\)-th entry of \(\bT\bv_k\) is: \[ \begin{align} (\bT\bv_k)_j = \frac{1}{h^2} \left[ -\sin((j-1)kh\pi) + 2\sin(jkh\pi) - \sin((j+1)kh\pi) \right]. \end{align} \] Applying the trigonometric identity \(\sin(A-B) + \sin(A+B) = 2\sin A \cos B\) with \(A = jkh\pi\) and \(B = kh\pi\): \[ \begin{align} (\bT\bv_k)_j &= \frac{1}{h^2} \left[ 2\sin(jkh\pi) - 2\sin(jkh\pi) \cos(kh\pi) \right] \\ &= \frac{2}{h^2} (1 - \cos(kh\pi)) \sin(jkh\pi). \end{align} \] Using the half-angle identity \(1 - \cos\theta = 2\sin^2(\theta/2)\): \[ \begin{align} (\bT\bv_k)_j &= \frac{4}{h^2} \sin^2\left(\frac{kh\pi}{2}\right) \sin(jkh\pi) \\ &= \lambda_k (\bv_k)_j. \end{align} \] As \(h = 1/(n+1) \to 0\), using the small-angle approximation \(\sin \theta \approx \theta\): \[ \begin{align} \lambda_k \approx \frac{4}{h^2} \left( \frac{k\pi h}{2} \right)^2 = k^2\pi^2. \end{align} \]
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.
31.3 Exercises
Build \(\bT\) for \(n=50\) and plot its eigenvalues vs. \(k^2 \pi^2\).
Show that \(\kappa(\bT) \to \infty\) as \(n \to \infty\).
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)\).