Difference between revisions of "Crank-Nicolson method"
Ulf Rehmann (talk | contribs) m (moved Crank–Nicolson method to Crank-Nicolson method: ascii title) |
m (links) |
||
Line 69: | Line 69: | ||
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c120/c120260/c12026063.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c120/c120260/c12026064.png" />. This estimate is still valid with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c120/c120260/c12026065.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c120/c120260/c12026066.png" /> (see [[#References|[a4]]]), and also it holds without any restriction between the step sizes but then a value <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c120/c120260/c12026067.png" /> has to be accepted in the bound ([[#References|[a3]]], [[#References|[a5]]]). | where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c120/c120260/c12026063.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c120/c120260/c12026064.png" />. This estimate is still valid with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c120/c120260/c12026065.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c120/c120260/c12026066.png" /> (see [[#References|[a4]]]), and also it holds without any restriction between the step sizes but then a value <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c120/c120260/c12026067.png" /> has to be accepted in the bound ([[#References|[a3]]], [[#References|[a5]]]). | ||
− | From a computational point of view, the Crank–Nicolson method involves a tridiagonal linear system to be solved at each time step. This can be carried out efficiently by Gaussian elimination techniques [[#References|[a2]]]. Because of that and its accuracy and stability properties, the Crank–Nicolson method is a competitive algorithm for the numerical solution of one-dimensional problems for the heat equation. | + | From a computational point of view, the Crank–Nicolson method involves a [[tridiagonal matrix|tridiagonal linear system]] to be solved at each time step. This can be carried out efficiently by Gaussian elimination techniques [[#References|[a2]]]. Because of that and its accuracy and stability properties, the Crank–Nicolson method is a competitive algorithm for the numerical solution of one-dimensional problems for the heat equation. |
− | The Crank–Nicolson method can be used for multi-dimensional problems as well. For example, in the integration of an homogeneous [[ | + | The Crank–Nicolson method can be used for multi-dimensional problems as well. For example, in the integration of an homogeneous [[Dirichlet problem]] in a rectangle for the heat equation, the scheme is still unconditionally stable and second-order accurate. Also, the system to be solved at each time step has a large and sparse matrix, but it does not have a tridiagonal form, so it is usually solved by iterative methods. The amount of work required to solve such a system is sufficiently large, so other numerical schemes are also taken into account here, such as alternating-direction implicit methods [[#References|[a6]]] or fractional-steps methods [[#References|[a7]]]. On the other hand, it should be noted that, for multi-dimensional problems in general domains, the finite-element method is better suited for the spatial discretization than the finite-difference method is. |
The Crank–Nicolson method can be considered for the numerical solution of a wide variety of time-dependent partial differential equations. Consider the [[Abstract Cauchy problem|abstract Cauchy problem]] | The Crank–Nicolson method can be considered for the numerical solution of a wide variety of time-dependent partial differential equations. Consider the [[Abstract Cauchy problem|abstract Cauchy problem]] |
Revision as of 17:32, 30 November 2014
One of the most popular methods for the numerical integration (cf. Integration, numerical) of diffusion problems, introduced by J. Crank and P. Nicolson [a1] in 1947. They considered an implicit finite difference scheme to approximate the solution of a non-linear differential system of the type which arises in problems of heat flow.
In order to illustrate the main properties of the Crank–Nicolson method, consider the following initial-boundary value problem for the heat equation
![]() |
To approximate the solution of this model problem on
, one introduces the grid
![]() |
where and
are positive integers, and
and
are the step sizes in space and time, respectively. One looks for approximations
to
, and to this end one replaces derivatives by finite-difference formulas. Setting
, then the Crank–Nicolson method for the considered problem takes the form
![]() |
,
, with boundary conditions
![]() |
and numerical initial condition
![]() |
where is an approximation to
. Note that each term in the difference equation can be interpreted as an approximation to the corresponding one in the differential equation at
.
Whenever the theoretical solution is sufficiently smooth, it can be proved, by Taylor series expansions that there exists a positive constant
, which depends only on
and
, such that the truncation error
![]() |
satisfies
![]() |
,
. Thus, the Crank–Nicolson scheme is consistent of second order both in time and space.
The stability study ([a2], [a3]) in the discrete -norm can be made by Fourier analysis or by the energy method. One introduces the discrete operator
![]() |
,
, where it is assumed that
; and sets
. There exists a positive constant
, which is independent of
and
, such that
![]() |
. The stability estimate holds without any restriction on the step sizes
and
; thus, the Crank–Nicolson method is said to be unconditionally stable. Convergence is derived by consistency and stability and, as
and
, one finds
![]() |
. Stability can also be established in the discrete
-norm by means of an energy argument [a3]. Denoting
, and
, where
, then the following stability estimate holds:
![]() |
. Therefore, if the theoretical solution
is sufficiently smooth, then
![]() |
. Note that the above inequality implies a convergence estimate in the maximum norm.
An important question is to establish a maximum principle for the approximations obtained with the Crank–Nicolson method, similar to the one satisfied by the solutions of the heat equation. Related topics are monotonicity properties and, in particular, the non-negativity (or non-positivity) of the numerical approximations. Maximum-principle and monotonicity arguments can be used to derive convergence in the -norm. It can be proved ([a2], [a3]) that a choice of the step sizes such that
and the condition
![]() |
imply
![]() |
,
. Note that if
and
, then the following stability estimate in the maximum norm holds:
![]() |
where and
. This estimate is still valid with
if
(see [a4]), and also it holds without any restriction between the step sizes but then a value
has to be accepted in the bound ([a3], [a5]).
From a computational point of view, the Crank–Nicolson method involves a tridiagonal linear system to be solved at each time step. This can be carried out efficiently by Gaussian elimination techniques [a2]. Because of that and its accuracy and stability properties, the Crank–Nicolson method is a competitive algorithm for the numerical solution of one-dimensional problems for the heat equation.
The Crank–Nicolson method can be used for multi-dimensional problems as well. For example, in the integration of an homogeneous Dirichlet problem in a rectangle for the heat equation, the scheme is still unconditionally stable and second-order accurate. Also, the system to be solved at each time step has a large and sparse matrix, but it does not have a tridiagonal form, so it is usually solved by iterative methods. The amount of work required to solve such a system is sufficiently large, so other numerical schemes are also taken into account here, such as alternating-direction implicit methods [a6] or fractional-steps methods [a7]. On the other hand, it should be noted that, for multi-dimensional problems in general domains, the finite-element method is better suited for the spatial discretization than the finite-difference method is.
The Crank–Nicolson method can be considered for the numerical solution of a wide variety of time-dependent partial differential equations. Consider the abstract Cauchy problem
![]() |
where represents a partial differential operator (cf. also Differential equation, partial; Differential operator) which differentiates the unknown function
with respect to the space variable
in its space domain in
, and
may be a vector function. In the numerical integration of such problem, one can distinguish two stages: space discretization and time integration.
For the spatial discretization one can use finite differences, finite elements, spectral techniques, etc., and then a system of ordinary differential equations is obtained, which can be written as
![]() |
where is the space discretization parameter (the spatial grid size of a finite-difference or finite-element scheme, the inverse of the highest frequency of a spectral scheme, etc.) and
is a suitable approximation to the theoretical initial condition
.
The phrase "Crank–Nicolson method" is used to express that the time integration is carried out in a particular way. However, there is no agreement in the literature as to what time integrator is called the Crank–Nicolson method, and the phrase sometimes means the trapezoidal rule [a8] or the implicit midpoint method [a6]. Let be the time step and introduce the discrete time levels
,
. If one uses the trapezoidal rule, then the full discrete method takes the form
![]() |
while when the implicit midpoint method is considered, one obtains
![]() |
where , and
is the approximation to
. Both methods coincide for linear autonomous problems, but they are different in general. For instance, the midpoint rule is symplectic [a9], while the trapezoidal rule does not satisfy this property.
The Crank–Nicolson method applied to several problems can be found in [a8], [a10], [a11], [a12], [a13] and [a14].
References
[a1] | J. Crank, P. Nicolson, "A practical method for numerical evaluation of solutions of partial differential equations of the heat-conduction type" Proc. Cambridge Philos. Soc. , 43 (1947) pp. 50–67 |
[a2] | K.W. Morton, D.F. Mayers, "Numerical solution of partial differential equations" , Cambridge Univ. Press (1994) |
[a3] | V. Thomee, "Finite difference methods for linear parabolic equations" P.G. Ciarlet (ed.) J.L. Lions (ed.) , Handbook of Numerical Analysis , 1 , Elsevier (1990) pp. 9–196 |
[a4] | J.F.B.M. Kraaijevanger, "Maximum norm contractivity of discretization schemes for the heat equation" Appl. Numer. Math. , 9 (1992) pp. 475–496 |
[a5] | C. Palencia, "A stability result for sectorial operators in Banach spaces" SIAM J. Numer. Anal. , 30 (1993) pp. 1373–1384 |
[a6] | A.R. Mitchell, D.F. Griffiths, "The finite difference method in partial differential equations" , Wiley (1980) |
[a7] | N.N. Yanenko, "The method of fractional steps" , Springer (1971) |
[a8] | J.G. Verwer, J.M. Sanz-Serna, "Convergence of method of lines approximations to partial differential equations" Computing , 33 (1984) pp. 297–313 |
[a9] | J.M. Sanz-Serna, M.P. Calvo, "Numerical Hamiltonian problems" , Chapman&Hall (1994) |
[a10] | Y. Tourigny, "Optimal ![]() |
[a11] | G.D. Akrivis, "Finite difference discretization of the Kuramoto–Sivashinsky equation" Numer. Math. , 63 (1992) pp. 1–11 |
[a12] | S.K. Chung, S.N. Ha, "Finite element Galerkin solutions for the Rosenau equation" Appl. Anal. , 54 (1994) pp. 39–56 |
[a13] | I.M. Kuria, P.E. Raad, "An implicit multidomain spectral collocation method for stiff highly nonlinear fluid dynamics problems" Comput. Meth. Appl. Mech. Eng. , 120 (1995) pp. 163–182 |
[a14] | G. Fairweather, J.C. Lopez-Marcos, "Galerkin methods for a semilinear parabolic problem with nonlocal boundary conditions" Adv. Comput. Math. , 6 (1996) pp. 243–262 |
Crank-Nicolson method. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Crank-Nicolson_method&oldid=35206