Daniel J. Duffy - Numerical Methods in Computational Finance

In general, with extrapolation methods we state what accuracy we desire, and the algorithm divides the interval into smaller subintervals until the difference between the solutions on consecutive meshes is less than a given tolerance.

A thorough introduction to extrapolation techniques for ordinary and partial differential equations (including one-factor and multifactor parabolic equations) can be found in Marchuk and Shaidurov (1983).

We discuss the following properties of a finite difference approximation to an ODE:

Consistency

Stability

Convergence.

These topics are also relevant when we discuss numerical methods for partial differential equations.

In order to reduce the scope of the problem (for the moment), we examine the simple scalar non-linear initial value problem (IVP) defined by:

(2.31)

We assume that this system has a unique solution in the interval . In general it is impossible to find an exact solution of Equation (2.31), and we resort to some kind of numerical scheme. To this end, we can write a generic -step method in the form (Henrici (1962), Lambert (1991)):

(2.32)

where and are constants, , and is the constant step-size.

Since this is a -step method, we need to give initial conditions :

(2.33)

We note that the first initial condition is known from the continuous problem (2.31)while the determination of the other numerical initial conditions is a part of the numerical problem. These numerical initial conditions must be chosen with care if we wish to avoid producing unstable schemes. In general, we compute these values by using Taylor's series expansions or by one-step methods.

We discuss consistency of scheme (2.32). This is a measure of how well the exact solution of (2.31)satisfies (2.32). Consistency states that the difference Equation (2.32)formally converges to the differential equation in (2.31)when tends to zero. In order to determine if a finite difference scheme is consistent, we define the generating polynomials :

(2.34)

It can be shown that consistency (see Henrici (1962), Dahlquist and Björck (1974)) is equivalent to the following conditions:

(2.35)

Let us take the explicit Euler method applied to IVP (2.31):

The reader can check the following:

(2.36)

from which we deduce that the explicit Euler scheme is consistent with the IVP (2.31)by checking with Equation (2.35).

The class of difference schemes (2.32)subsumes well-known specific schemes, for example:

The one-step () explicit and implicit Euler schemes.

The two-step () leapfrog scheme.

The three-step () Adams–Bashforth scheme.

The one-step trapezoidal () scheme.

Each of these schemes is consistent with the IVP (2.31), as can be checked by calculating their generating polynomials.

We now discuss what is meant by the stability of a finite difference scheme. To take a simple counterexample, a scheme whose solution is exponentially increasing or oscillating in time while the exact solution is decreasing in time cannot be stable. In order to define stability, it is common practice to examine model problems (whose solutions are known) and apply various finite difference schemes to them. We then examine the stability properties of the schemes. The model problem in this case is the constant-coefficient scalar IVP in which the coefficient is a complex number:

(2.37)

and whose solution is given by:

(2.38)

Thus, the solution is increasing when is positive and real and decreasing when is negative and real. The corresponding finite difference schemes should have similar properties. We take an example of the one-step trapezoidal method :