10
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Hi foobarbaz, and welcome to scicomp! I assume your that the problem you're solving has no source terms, correct? $\endgroup$ – Paul May 10 '13 at 20:40
8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks! Do you happen to know of another reference besides Morton? I can't access those Sections or the Theorem in the Google book preview. I'd like to understand the proof. $\endgroup$ – foobarbaz May 13 '13 at 19:14
  • $\begingroup$ @foobarbaz I don't have another reference handy, but I added an outline of the proof. Let me know if I can make it clearer. $\endgroup$ – Ben May 13 '13 at 20:35
0
$\begingroup$

Stability means that a perturbation remains bounded in time. It doesn't mean that the maximum principle is satisfied on the discrete level, that's a different issue. Satisfying the discrete maximum principle is sufficient but not necessary for stability.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.