I'm using the Crank-Nicolson finite difference scheme to solve a 1D heat equation. I'm wondering if the maximum/minimum principle of the heat equation (i.e. that the maximum/minimum occurs at the initial condition or on the boundaries) also holds for the discretized solution. This is probably implied by the fact that Crank-Nicolson is a stable and convergent scheme. But it seems that you might be able to prove this directly via a linear algebra argument using the matrices created from the Crank-Nicolson stencil.I'd appreciate any pointers to literature on this. Thanks.
Is the maximum/minimum principle of the heat equation maintained by the Crank-Nicolson discretization?
linear algebra;pde;numerics;finite difference;crank nicolson
The maximum principle for Crank-Nicolson will hold if$$\mu \doteq \frac{k}{h^2} \leq 1$$for timestep $k$ and grid spacing $h$. In general, we can consider a $\theta$-scheme of the form$$u^{n+1} = u^n + \frac{\mu}{2}\left( (1-\theta)Au^n + \theta Au^{n+1}\right)$$where $A$ is the standard Laplacian matrix and $0 \leq \theta \leq 1$. If $\mu(1-2\theta) \leq \frac{1}{2}$, then the scheme is stable. (This can easily be shown by Fourier techniques.) However, the stronger criterion that $\mu(1-\theta) \leq \frac{1}{2}$ is needed for the maximum principle to hold in general.For a proof, see Numerical Solutions of Partial Differential Equations by K. W. Morton. In particular, look at Sections 2.10 and 2.11 and Theorem 2.2.There's also a nice way to see that the maximum principle will not hold in general for Crank-Nicolson without a constraint on $\mu$.Consider the heat equation on $[0,1]$ with a discretization containing 3 points, including the boundary. Let $u_i^k$ denote the discretization at timestep $k$ and grid point $i$. Assume Dirichlet boundary, so that $u^k_0 = u^k_2 = 0$ for all $k$. Then Crank-Nicolson reduces to$$\left(1 - \frac{\mu}{2}(-2)\right)u^{n+1}_1 = \left(1 + \frac{\mu}{2}(-2)\right)u^n_1,$$which can be further reduced to$$u^{n+1}_1 = \left(\frac{1-\mu}{1+\mu}\right)u^n_1.$$If we consider the initial condition of $u_1^0 = 1$, then we have$$u^n_1 = \left(\frac{1-\mu}{1+\mu}\right)^n,$$and though it will always be the case that $u^n_1 \leq 1$, we will nonetheless have that $u^n_1 < 0$ for odd $n$ unless $\mu \leq 1$. Thus the maximum/minimum principle is violated unless $\mu \leq 1$. This is particularly noteworthy in light of the fact that Crank-Nicolson is stable for any $\mu$.In response to foobarbaz's request, I've added a sketch of the proof.The key is to write the scheme in the form\begin{align*}(1+2\theta\mu)u^{n+1}_j &= \theta\mu(u^{n+1}_{j-1} + u^{n+1}_{j+1})\\                        &+ (1-\theta)\mu(u^n_{j-1} + u^n_{j+1})\\                        &+ [1-2(1-\theta)\mu]u^n_j\end{align*}The hypothesis that $\mu(1-\theta)\leq \frac{1}{2}$ is exactly equivalent to the fact that all of the above coefficients are nonnegative.Now suppose that the maximum is attained at an interior point $u^{n+1}_j$. Note that all of $u^{n+1}_{j-1}$, $u^{n+1}_{j+1}$, $u^n_{j-1}$, $u^n_{j+1}$, $u^n_j$ are less than or equal to $u^{n+1}_j$ by assumption. If any of these is strictly less than $u^{n+1}_j$, then the above equality and the nonnegativity of the coefficients imply that\begin{align*}(1+2\theta\mu)u^{n+1}_j &> \theta\mu(u^{n+1}_{j-1} + u^{n+1}_{j+1})\\                        &+ (1-\theta)\mu(u^n_{j-1} + u^n_{j+1})\\                        &+ [1-2(1-\theta)\mu]u^n_j\\                        &= (1+2\theta\mu)u^{n+1}_j\end{align*}which is a contradiction. It follows that the maximum must also be attained at all of the temporal and spatial neighbors of $u^{n+1}_j$, and a connectedness argument then implies that the discretization of $u$ must be constant in space and time, so that the maximum is still attained on the boundary. Note that this connectedness argument mirrors the proof of the analytic (i.e., not discretized) maximum principle.