Von Neumann stability analysis
Encyclopedia
In numerical analysis
, von Neumann stability analysis (also known as Fourier stability analysis) is a procedure used to check the stability
of finite difference schemes as applied to linear partial differential equation
s. The analysis is based on the Fourier decomposition of numerical error
and was developed at Los Alamos National Laboratory
after having been briefly described in a 1947 article by British
researchers Crank
and Nicolson
.
Later, the method was given a more rigorous treatment in an article co-authored by von Neumann
.
Unfortunately, von Neumann stability is necessary and sufficient for stability in the sense of Lax–Richtmyer (as used in the Lax equivalence theorem
) only in certain cases: The PDE the finite difference scheme models must be linear; the PDE must be constant-coefficient with periodic boundary conditions and have only two independent variables; and the scheme must use no more than two time levels. It is necessary in a much wider variety of cases, however, and due to its relative simplicity it is often used in place of a more detailed stability analysis as a good guess at the restrictions (if any) on the step sizes used in the scheme.
. To illustrate the procedure, consider the one-dimensional heat equation
defined on the spatial interval
, and its FTCS discretization
where
and the solution
of the discrete equation approximates the analytical solution 
of the PDE on the grid.
Define the round-off error
as
where
is the solution of the discretized equation (1) that would be computed in the absence of round-off error, and 
is the numerical solution obtained in finite precision arithmetic
. Since the exact solution
must satisfy the discretized equation exactly, the error 
must also satisfy the discretized equation.
Thus
is a recurrence relation for the error. Equations (1) and (2) show that both the error and the numerical solution have the same growth or decay behavior with respect to time. For linear differential equations with periodic boundary condition, the spatial variation of error may be expanded in a finite Fourier series, in the interval
, as
where the wavenumber
with 
and 
. The time dependence of the error is included by assuming that the amplitude of error 
is a function of time. Since the error tends to grow or decay exponentially with time, it is reasonable to assume that the amplitude varies exponentially with time; hence
where
is a constant.
Since the difference equation for error is linear (the behavior of each term of the series is the same as series itself), it is enough to consider the growth of error of a typical term:
The stability characteristics can be studied using just this form for the error with no loss in generality. To find out how error varies in steps of time, substitute equation (5) into equation (2), after noting that
Numerical analysis
Numerical analysis is the study of algorithms that use numerical approximation for the problems of mathematical analysis ....
, von Neumann stability analysis (also known as Fourier stability analysis) is a procedure used to check the stability
Numerical stability
In the mathematical subfield of numerical analysis, numerical stability is a desirable property of numerical algorithms. The precise definition of stability depends on the context, but it is related to the accuracy of the algorithm....
of finite difference schemes as applied to linear partial differential equation
Partial differential equation
In mathematics, partial differential equations are a type of differential equation, i.e., a relation involving an unknown function of several independent variables and their partial derivatives with respect to those variables...
s. The analysis is based on the Fourier decomposition of numerical error
Numerical error
In software engineering and mathematics, numerical error is the combined effect of two kinds of error in a calculation. The first is caused by the finite precision of computations involving floating-point or integer values...
and was developed at Los Alamos National Laboratory
Los Alamos National Laboratory
Los Alamos National Laboratory is a United States Department of Energy national laboratory, managed and operated by Los Alamos National Security , located in Los Alamos, New Mexico...
after having been briefly described in a 1947 article by British
British people
The British are citizens of the United Kingdom, of the Isle of Man, any of the Channel Islands, or of any of the British overseas territories, and their descendants...
researchers Crank
John Crank
John Crank was a mathematical physicist, best known for his work on the numerical solution of partial differential equations....
and Nicolson
Phyllis Nicolson
Phyllis Nicolson was a British mathematician most known for her work on the Crank–Nicolson scheme together with John Crank....
.
Later, the method was given a more rigorous treatment in an article co-authored by von Neumann
John von Neumann
John von Neumann was a Hungarian-American mathematician and polymath who made major contributions to a vast number of fields, including set theory, functional analysis, quantum mechanics, ergodic theory, geometry, fluid dynamics, economics and game theory, computer science, numerical analysis,...
.
Numerical stability
The stability of numerical schemes is closely associated with numerical error. A finite difference scheme is stable if the errors made at one time step of the calculation do not cause the errors to increase as the computations are continued. A neutrally stable scheme is one in which errors remain constant as the computations are carried forward. If the errors decay and eventually damp out, the numerical scheme is said to be stable. If, on the contrary, the errors grow with time the numerical solution diverges from the true, correct answer and thus the numerical scheme is said to be unstable. The stability of numerical schemes can be investigated by performing von Neumann stability analysis. For time-dependent problems, stability guarantees that the numerical method produces a bounded solution whenever the solution of the exact differential equation is bounded. Stability, in general, can be difficult to investigate, especially when equation under consideration is nonlinear.Unfortunately, von Neumann stability is necessary and sufficient for stability in the sense of Lax–Richtmyer (as used in the Lax equivalence theorem
Lax equivalence theorem
In numerical analysis, the Lax equivalence theorem is the fundamental theorem in the analysis of finite difference methods for the numerical solution of partial differential equations...
) only in certain cases: The PDE the finite difference scheme models must be linear; the PDE must be constant-coefficient with periodic boundary conditions and have only two independent variables; and the scheme must use no more than two time levels. It is necessary in a much wider variety of cases, however, and due to its relative simplicity it is often used in place of a more detailed stability analysis as a good guess at the restrictions (if any) on the step sizes used in the scheme.
Illustration of the Method
The von Neumann method is based on the decomposition of the errors into Fourier seriesFourier series
In mathematics, a Fourier series decomposes periodic functions or periodic signals into the sum of a set of simple oscillating functions, namely sines and cosines...
. To illustrate the procedure, consider the one-dimensional heat equation
Heat equation
The heat equation is an important partial differential equation which describes the distribution of heat in a given region over time...
defined on the spatial interval
, and its FTCS discretizationwhere
and the solution
of the discrete equation approximates the analytical solution of the PDE on the grid.Define the round-off error
Round-off error
A round-off error, also called rounding error, is the difference between the calculated approximation of a number and its exact mathematical value. Numerical analysis specifically tries to estimate this error when using approximation equations and/or algorithms, especially when using finitely many...
aswhere
is the solution of the discretized equation (1) that would be computed in the absence of round-off error, and is the numerical solution obtained in finite precision arithmeticFloating point
In computing, floating point describes a method of representing real numbers in a way that can support a wide range of values. Numbers are, in general, represented approximately to a fixed number of significant digits and scaled using an exponent. The base for the scaling is normally 2, 10 or 16...
. Since the exact solution
must satisfy the discretized equation exactly, the error must also satisfy the discretized equation.Thus
is a recurrence relation for the error. Equations (1) and (2) show that both the error and the numerical solution have the same growth or decay behavior with respect to time. For linear differential equations with periodic boundary condition, the spatial variation of error may be expanded in a finite Fourier series, in the interval
, aswhere the wavenumber
Wavenumber
In the physical sciences, the wavenumber is a property of a wave, its spatial frequency, that is proportional to the reciprocal of the wavelength. It is also the magnitude of the wave vector...
with and . The time dependence of the error is included by assuming that the amplitude of error is a function of time. Since the error tends to grow or decay exponentially with time, it is reasonable to assume that the amplitude varies exponentially with time; hencewhere
is a constant.Since the difference equation for error is linear (the behavior of each term of the series is the same as series itself), it is enough to consider the growth of error of a typical term:
The stability characteristics can be studied using just this form for the error with no loss in generality. To find out how error varies in steps of time, substitute equation (5) into equation (2), after noting that
-
to yield (after simplification)
Using the identities
equation (6) may be written as
Define the amplification factor
The necessary and sufficient condition for the error to remain bounded is that,
However,
Thus, from equations (7) and (8), the condition for stability is given by
For the above condition to hold,
Equation (10) gives the stability requirement for the FTCS scheme as applied to one-dimensional heat equation. It says that for a given
, the allowed value of 
must be small enough to satisfy equation (10).