 Crank–Nicolson method

In numerical analysis, the Crank–Nicolson method is a finite difference method used for numerically solving the heat equation and similar partial differential equations.^{[1]} It is a secondorder method in time, implicit in time, and is numerically stable. The method was developed by John Crank and Phyllis Nicolson in the mid 20th century.^{[2]}
For diffusion equations (and many other equations), it can be shown the Crank–Nicolson method is unconditionally stable.^{[3]} However, the approximate solutions can still contain (decaying) spurious oscillations if the ratio of time step to the square of space step is large (typically larger than 1/2). For this reason, whenever large time steps or high spatial resolution is necessary, the less accurate backward Euler method is often used, which is both stable and immune to oscillations.
Contents
The method
The Crank–Nicolson method is based on central difference in space, and the trapezoidal rule in time, giving secondorder convergence in time. For example, in one dimension, if the partial differential equation is
then, letting , the equation for Crank–Nicolson method is a combination of the forward Euler method at n and the backward Euler method at n + 1 (note, however, that the method itself is not simply the average of those two methods, as the equation has an implicit dependence on the solution):
The function F must be discretized spatially with a central difference.
Note that this is an implicit method: to get the "next" value of u in time, a system of algebraic equations must be solved. If the partial differential equation is nonlinear, the discretization will also be nonlinear so that advancing in time will involve the solution of a system of nonlinear algebraic equations, though linearizations are possible. In many problems, especially linear diffusion, the algebraic problem is tridiagonal and may be efficiently solved with the tridiagonal matrix algorithm, which gives a fast direct solution as opposed to the usual for a full matrix.
Example: 1D diffusion
The Crank–Nicolson method is often applied to diffusion problems. As an example, for linear diffusion,
whose Crank–Nicolson discretization is then:
or, letting :
which is a tridiagonal problem, so that may be efficiently solved by using the tridiagonal matrix algorithm in favor of a much more costly matrix inversion.
A quasilinear equation, such as (this is a minimalistic example and not general)
would lead to a nonlinear system of algebraic equations which could not be easily solved as above; however, it is possible in some cases to linearize the problem by using the old value for a, that is instead of . Other times, it may be possible to estimate using an explicit method and maintain stability.
Example: 1D diffusion with advection for steady flow, with multiple channel connections
This is a solution usually employed for many purposes when there's a contamination problem in streams or rivers under steady flow conditions but information is given in one dimension only. Often the problem can be simplified into a 1dimensional problem and still yield useful information.
Here we model the concentration of a solute contaminant in water. This problem is composed of three parts: the known diffusion equation (D_{x} chosen as constant), an advective component (which means the system is evolving in space due to a velocity field), which we choose to be a constant Ux, and a lateral interaction between longitudinal channels (k).
where C is the concentration of the contaminant and subscripts N and M correspond to previous and next channel.
The Crank–Nicolson method (where i represents position and j time) transforms each component of the PDE into the following:
Now we create the following constants to simplify the algebra:
and substitute <1>, <2>, <3>, <4>, <5>, <6>, α, β and λ into <0>. We then put the new time terms on the left (j + 1) and the present time terms on the right (j) to get:
To model the first channel, we realize that it can only be in contact with the following channel (M), so the expression is simplified to:
In the same way, to model the last channel, we realize that it can only be in contact with the previous channel (N), so the expression is simplified to:
To solve this linear system of equations we must now see that boundary conditions must be given first to the beginning of the channels:
: initial condition for the channel at present time step
: initial condition for the channel at next time step
: initial condition for the previous channel to the one analyzed at present time step
: initial condition for the next channel to the one analyzed at present time stepFor the last cell of the channels (z) the most convenient condition becomes an adiabatic one, so
This condition is satisfied if and only if (regardless of a null value)
Let us solve this problem (in a matrix form) for the case of 3 channels and 5 nodes (including the initial boundary condition). We express this as a linear system problem:
where
 and
Now we must realize that AA and BB should be arrays made of four different subarrays (remember that only three channels are considered for this example but it covers the main part discussed above).
 and
where the elements mentioned above correspond to the next arrays and an additional 4x4 full of zeros. Please note that the sizes of AA and BB are 12x12:
 ,
 ,
 ,
 &
The d vector here is used to hold the boundary conditions. In this example it is a 12x1 vector:
To find the concentration at any time, one must iterate the following equation:
Example: 2D diffusion
When extending into two dimensions on a uniform Cartesian grid, the derivation is similar and the results may lead to a system of banddiagonal equations rather than tridiagonal ones. The twodimensional heat equation
can be solved with the Crank–Nicolson discretization of
assuming that a square grid is used so that Δx = Δy. This equation can be simplified somewhat by rearranging terms and using the CFL number
For the Crank–Nicolson numerical scheme, a low CFL number is not required for stability, however it is required for numerical accuracy. We can now write the scheme as:
Application in financial mathematics
Further information: Finite difference methods for option pricingBecause a number of other phenomena can be modeled with the heat equation (often called the diffusion equation in financial mathematics), the Crank–Nicolson method has been applied to those areas as well.^{[4]} Particularly, the BlackScholes option pricing model's differential equation can be transformed into the heat equation, and thus numerical solutions for option pricing can be obtained with the Crank–Nicolson method.
The importance of this for finance, is that option pricing problems, when extended beyond the standard assumptions (e.g. incorporating changing dividends), cannot be solved in closed form, but can be solved using this method. Note however, that for nonsmooth final conditions (which happen for most financial instruments), the Crank–Nicolson method is not satisfactory as numerical oscillations are not damped. For vanilla options, this results in oscillation in the gamma value around the strike price. Therefore, special damping initialization steps are necessary (e.g., fully implicit finite difference method).
See also
 Financial mathematics
 Partial differential equations
References
 ^ Tuncer Cebeci (2002). Convective Heat Transfer. Springer. ISBN 0966846141. http://books.google.com/?id=xfkgT9Fd4t4C&pg=PA257&dq=%22CrankNicolson+method%22.
 ^ Crank, J.; Nicolson, P. (1947). "A practical method for numerical evaluation of solutions of partial differential equations of the heat conduction type". Proc. Camb. Phil. Soc. 43 (1): 50–67. doi:10.1007/BF02127704..
 ^ Thomas, J. W. (1995). Numerical Partial Differential Equations: Finite Difference Methods. Texts in Applied Mathematics. 22. Berlin, New York: SpringerVerlag. ISBN 9780387979991.. Example 3.3.2 shows that Crank–Nicolson is unconditionally stable when applied to u_{t} = au_{xx}.
 ^ Wilmott, P.; Howison, S.; Dewynne, J. (1995). The Mathematics of Financial Derivatives: A Student Introduction. Cambridge Univ. Press. ISBN 0521497892. http://books.google.co.in/books?hl=en&q=The%20Mathematics%20of%20Financial%20Derivatives%20Wilmott&um=1&ie=UTF8&sa=N&tab=wp.
External links
First order methods Second order methods Verlet integration · Velocity Verlet · Crank–Nicolson method · Beeman's algorithm · Midpoint method · Heun's method · Newmarkbeta method · Leapfrog integrationHigher order methods Finite difference methods Heat Equation and related: FTCS scheme · Crank–Nicolson method Hyperbolic: Lax–Friedrichs method · Lax–Wendroff method · MacCormack method · Upwind scheme · Other: Alternating direction implicit method · Finitedifference timedomain methodFinite volume methods Finite element methods Other methods Spectral method · Pseudospectral method · Method of lines · Multigrid methods · Collocation method · Level set method · Boundary element method · Immersed boundary method · Analytic element method · Particleincell · Isogeometric analysisDomain decomposition methods Schur complement method · Fictitious domain method · Schwarz alternating method · Additive Schwarz method · Abstract additive Schwarz method · Neumann–Dirichlet method · Neumann–Neumann methods · Poincaré–Steklov operator · Balancing domain decomposition · BDDC · FETI · FETIDPCategories: Mathematical finance
 Numerical differential equations
Wikimedia Foundation. 2010.
Look at other dictionaries:
CrankNicolson — Das Crank Nicolson Verfahren ist in der numerischen Mathematik eine Finite Differenzen Methode zur Lösung der Wärmeleitungsgleichung und ähnlicher partieller Differentialgleichungen.[1] Es ist ein implizites Verfahren 2. Ordnung und numerisch… … Deutsch Wikipedia
CrankNicolsonMethode — Das Crank Nicolson Verfahren ist in der numerischen Mathematik eine Finite Differenzen Methode zur Lösung der Wärmeleitungsgleichung und ähnlicher partieller Differentialgleichungen.[1] Es ist ein implizites Verfahren 2. Ordnung und numerisch… … Deutsch Wikipedia
CrankNicolsonVerfahren — Das Crank Nicolson Verfahren ist in der numerischen Mathematik eine Finite Differenzen Methode zur Lösung der Wärmeleitungsgleichung und ähnlicher partieller Differentialgleichungen.[1] Es ist ein implizites Verfahren 2. Ordnung und numerisch… … Deutsch Wikipedia
Methode de CrankNicolson — Méthode de Crank Nicolson Simulation de l expérience des fentes de Young pour un électron, avec la méthode de Crank Nicolson. En mathématiques, en analyse numérique, la méthode de Crank Nicolson est un algorithme simple permettant de résoudre des … Wikipédia en Français
Méthode De CrankNicolson — Simulation de l expérience des fentes de Young pour un électron, avec la méthode de Crank Nicolson. En mathématiques, en analyse numérique, la méthode de Crank Nicolson est un algorithme simple permettant de résoudre des systèmes d équations aux… … Wikipédia en Français
Méthode de cranknicolson — Simulation de l expérience des fentes de Young pour un électron, avec la méthode de Crank Nicolson. En mathématiques, en analyse numérique, la méthode de Crank Nicolson est un algorithme simple permettant de résoudre des systèmes d équations aux… … Wikipédia en Français
Méthode de CrankNicolson — Pour les articles homonymes, voir Nicolson. Simulation de l expérience des fentes de Young pour un électron, avec la méthode de Crank Nicolson. En mathématiques, en analyse numérique, la méthode de Crank Nicolson est un algorithme simple… … Wikipédia en Français
Method of lines — The method of lines (MOL, NMOL, NUMOL) (Schiesser, 1991; Hamdi, et al., 2007; Schiesser, 2009 ) is a technique for solving partial differential equations (PDEs) in which all but one dimension is discretized. MOL allows standard, general purpose… … Wikipedia
Finite difference method — In mathematics, finite difference methods are numerical methods for approximating the solutions to differential equations using finite difference equations to approximate derivatives. Intuitive derivation Finite difference methods approximate the … Wikipedia
Alternating direction implicit method — In mathematics, the alternating direction implicit (ADI) method [Peaceman, D. W. and Rachford, H. H., Jr., The numerical solution of parabolic and elliptic differential equations ,SIAM J. 3 (1955), 28 41, [http://www.ams.org/mathscinet getitem?mr … Wikipedia