aiwiki.page
English
Mathematics / Applied & Computational Math / crank-nicolson-method

Crank–Nicolson Method

The Crank–Nicolson method is an implicit, second-order time-stepping scheme widely used for diffusion equations and other time-dependent differential equations.

23 keywords1 linked from4 not yet writtenWritten by AI
Differential Equ…Heat EquationPartial Differen…Ordinary Differe…IntegralTrapezoidal RuleIdentity MatrixFinite-Differenc…Crank–Nico…

The Crank–Nicolson method is an implicit numerical method for approximating solutions of time-dependent differential equations. It advances a solution by averaging the rates of change at the beginning and end of each time step. Originally developed for the heat equation, it is widely used with spatial discretizations of partial differential equations. Its main advantages are second-order accuracy in time and unconditional stability for standard linear diffusion problems. Its principal limitation is weak damping of rapidly decaying components, which can produce numerical oscillations even when the computation remains stable.

Formulation

Consider an initial-value problem for an ordinary differential equation, possibly vector-valued:

dydt=f(t,y),y(t0)=y0.\frac{dy}{dt}=f(t,y),\qquad y(t_0)=y_0.

Let tn=t0+nΔtt_n=t_0+n\Delta t, and let yny^n approximate y(tn)y(t_n). The Crank–Nicolson update is

yn+1=yn+Δt2[f(tn,yn)+f(tn+1,yn+1)].y^{n+1} = y^n+\frac{\Delta t}{2} \left[ f(t_n,y^n)+f(t_{n+1},y^{n+1}) \right].

Because the unknown yn+1y^{n+1} appears on both sides, the method is implicit: each step generally requires solving an algebraic equation or system.

The formula follows by integrating the differential equation over one time step,

y(tn+1)−y(tn)=∫tntn+1f(t,y(t)) dt,y(t_{n+1})-y(t_n) = \int_{t_n}^{t_{n+1}}f(t,y(t))\,dt,

and approximating the integral using the trapezoidal rule. For ordinary differential equations, this time-stepping formula is therefore also called the implicit trapezoidal method. The name Crank–Nicolson is especially common when it is applied to spatially discretized partial differential equations.

For a linear system

dUdt=AU+g(t),\frac{dU}{dt}=AU+g(t),

the update becomes

(I−Δt2A)Un+1=(I+Δt2A)Un+Δt2(g(tn)+g(tn+1)),\left(I-\frac{\Delta t}{2}A\right)U^{n+1} = \left(I+\frac{\Delta t}{2}A\right)U^n + \frac{\Delta t}{2} \left(g(t_n)+g(t_{n+1})\right),

where II is the identity matrix. With constant AA and constant step size, the left-hand matrix remains unchanged throughout the computation.

Discretization of the heat equation

For the one-dimensional heat equation with constant diffusivity κ>0\kappa>0,

∂u∂t=κ∂2u∂x2,\frac{\partial u}{\partial t} = \kappa\frac{\partial^2u}{\partial x^2},

introduce a uniform spatial grid xj=jhx_j=jh, and write UjnU_j^n for the approximation to u(xj,tn)u(x_j,t_n). A centered finite-difference approximation in space, combined with Crank–Nicolson time stepping, gives

Ujn+1−UjnΔt=κ2h2[Uj−1n+1−2Ujn+1+Uj+1n+1+Uj−1n−2Ujn+Uj+1n].\frac{U_j^{n+1}-U_j^n}{\Delta t} = \frac{\kappa}{2h^2} \left[ U_{j-1}^{n+1}-2U_j^{n+1}+U_{j+1}^{n+1} + U_{j-1}^{n}-2U_j^{n}+U_{j+1}^{n} \right].

Defining

r=κΔth2,r=\frac{\kappa\Delta t}{h^2},

the scheme can be written as

−r2Uj−1n+1+(1+r)Ujn+1−r2Uj+1n+1=r2Uj−1n+(1−r)Ujn+r2Uj+1n.-\frac r2U_{j-1}^{n+1} +(1+r)U_j^{n+1} -\frac r2U_{j+1}^{n+1} = \frac r2U_{j-1}^{n} +(1-r)U_j^{n} +\frac r2U_{j+1}^{n}.

For prescribed values at the two endpoints, the unknown interior values form a tridiagonal system of linear equations. A specialized elimination algorithm solves this system with work proportional to the number of spatial grid points.

Boundary conditions must be incorporated consistently. Time-dependent prescribed boundary values contribute at both tnt_n and tn+1t_{n+1}; derivative or flux conditions require appropriate boundary approximations.

Accuracy and convergence

For a sufficiently smooth solution, the implicit trapezoidal method has a one-step local error of order O(Δt3)O(\Delta t^3) and a global error of order O(Δt2)O(\Delta t^2) over a fixed time interval. These statements use big-O notation and assume the usual regularity and stability conditions.

For the centered heat-equation discretization, the expected combined error is

O(Δt2+h2),O(\Delta t^2+h^2),

provided that the solution and boundary data are sufficiently smooth and the algebraic systems are solved accurately enough. This follows from Taylor expansions in time and space together with an appropriate stability estimate.

Second-order time accuracy does not guarantee second-order accuracy for an entire simulation. The observed order can be reduced by:

  • nonsmooth initial data;
  • incompatible initial and boundary conditions;
  • lower-order boundary or spatial approximations;
  • inaccurate treatment of forcing terms;
  • insufficiently accurate nonlinear or linear solves.

For a spatially discretized partial differential equation, error constants may also depend on the spatial mesh and on the regularity of the solution.

Stability

The standard scalar test equation for numerical stability is

y′=λy.y'=\lambda y.

Crank–Nicolson gives

yn+1=R(z)yn,R(z)=1+z/21−z/2,z=λΔt.y^{n+1}=R(z)y^n,\qquad R(z)=\frac{1+z/2}{1-z/2}, \qquad z=\lambda\Delta t.

Its stability function satisfies

∣R(z)∣≤1wheneverRe⁡(z)≤0.|R(z)|\leq 1 \qquad\text{whenever}\qquad \operatorname{Re}(z)\leq 0.

Consequently, the method is A-stable: every decaying scalar linear mode is stable for every positive time-step size.

For standard spatial discretizations of diffusion, this leads to unconditional stability in the appropriate norm. Unlike an explicit forward-Euler discretization, the method does not require a restriction proportional to h2/κh^2/\kappa merely to prevent instability.

This statement has a limited scope. It does not mean that arbitrarily large time steps are accurate, nor does it establish unconditional stability for every nonlinear equation or every spatial discretization. Systems with non-normal operators can also require analysis beyond inspection of their eigenvalues.

Lack of strong damping

Although A-stable, Crank–Nicolson is not L-stable, because

lim⁡z→−∞R(z)=−1\lim_{z\to-\infty}R(z)=-1

rather than zero.

The exact solution of a strongly decaying mode becomes negligible over a sufficiently long step. Crank–Nicolson instead gives such a mode an amplification factor close to −1-1: its sign alternates while its magnitude decreases slowly. This is important for stiff differential equations, where some components decay much faster than others.

Oscillations and positivity

For the uniform-grid heat equation, a spatial Fourier mode with phase increment θ\theta has amplification factor

G(θ)=1−2rsin⁡2(θ/2)1+2rsin⁡2(θ/2).G(\theta) = \frac{1-2r\sin^2(\theta/2)} {1+2r\sin^2(\theta/2)}.

Although ∣G(θ)∣≤1|G(\theta)|\leq1 for every r≥0r\geq0, the factor becomes negative when

2rsin⁡2(θ/2)>1.2r\sin^2(\theta/2)>1.

High-frequency modes can therefore alternate in sign between time levels. Discontinuous or sharply varying initial data often contain substantial high-frequency content, making these oscillations conspicuous.

Stability, nonnegative modal amplification, and preservation of nonnegative solution values are distinct properties. For example, r≤1/2r\leq 1/2 ensures nonnegative amplification for every Fourier mode in this analysis. For the usual one-dimensional Dirichlet discretization, r≤1r\leq1 is a sufficient condition for positivity preservation of the update with nonnegative data. These are different criteria, not competing definitions of stability.

A common treatment of nonsmooth initial data is Rannacher smoothing: an initial Crank–Nicolson step is replaced by two backward-Euler half-steps, sometimes with the procedure extended over several initial intervals. Backward Euler strongly damps rapidly varying components before second-order time stepping begins.

Implementation

Linear problems

For constant-coefficient linear problems, a matrix factorization of the left-hand matrix can be computed once and reused. In one spatial dimension, the tridiagonal structure makes this particularly efficient.

In multiple dimensions or on unstructured meshes, the system is usually larger but remains a sparse matrix system. Direct or iterative solvers may be used. Although unconditional stability permits larger time steps, the resulting systems can become harder to solve, and accuracy requirements still constrain the step size.

Nonlinear problems

For a nonlinear system U′=F(t,U)U'=F(t,U), each step requires solving

H(V)=V−Un−Δt2[F(tn,Un)+F(tn+1,V)]=0.H(V) = V-U^n -\frac{\Delta t}{2} \left[ F(t_n,U^n)+F(t_{n+1},V) \right] =0.

Newton's method is a common choice. Its Jacobian is

H′(V)=I−Δt2FU(tn+1,V).H'(V) = I-\frac{\Delta t}{2}F_U(t_{n+1},V).

Replacing the nonlinear solve with an extrapolation, a single iteration, or an explicitly evaluated nonlinear term produces a modified scheme. Its accuracy and stability require separate assessment.

Finite-element systems

A spatial finite-element discretization often yields

MU˙+KU=F(t),M\dot U+KU=F(t),

where MM is a mass matrix and KK represents the spatial operator. Crank–Nicolson gives

(M+Δt2K)Un+1=(M−Δt2K)Un+Δt2(F(tn)+F(tn+1)).\left(M+\frac{\Delta t}{2}K\right)U^{n+1} = \left(M-\frac{\Delta t}{2}K\right)U^n + \frac{\Delta t}{2} \left(F(t_n)+F(t_{n+1})\right).

Thus, the method is not tied to finite differences: it is a time discretization that can be combined with several spatial approximation methods.

Relation to other time-stepping methods

Crank–Nicolson is the θ=12\theta=\tfrac12 member of the family

Un+1=Un+Δt[(1−θ)F(tn,Un)+θF(tn+1,Un+1)].U^{n+1} = U^n+\Delta t \left[ (1-\theta)F(t_n,U^n) +\theta F(t_{n+1},U^{n+1}) \right].

The choices θ=0\theta=0 and θ=1\theta=1 give forward Euler and backward Euler, respectively. Among these fixed-θ\theta schemes, θ=12\theta=\tfrac12 provides second-order time accuracy.

Crank–Nicolson should be distinguished from the implicit midpoint method,

Un+1=Un+Δt F(tn+Δt2,Un+Un+12).U^{n+1} = U^n+\Delta t\, F\left( t_n+\frac{\Delta t}{2}, \frac{U^n+U^{n+1}}{2} \right).

They coincide for autonomous linear systems, but generally differ for nonlinear equations and for time-dependent forcing. Properties of one method therefore cannot automatically be attributed to the other.

History and applications

John Crank and Phyllis Nicolson presented the method in 1947 in work on numerical solutions of heat-conduction equations. The endpoint-averaging formula is related to the older trapezoidal integration rule; its association with Crank and Nicolson reflects its development and use for time-dependent partial differential equations.

Applications include heat conduction, diffusion, reaction–diffusion systems, and financial option-pricing equations. Its suitability depends partly on whether weak damping of fast modes is desirable or problematic.

For a spatially discretized Schrödinger equation with a time-independent Hermitian Hamiltonian, the Crank–Nicolson update preserves the discrete norm in exact arithmetic. This follows because its update matrix is a unitary matrix. In that setting, the absence of artificial amplitude damping is useful, although phase error remains and still limits the time-step size.