Читать книгу Numerical Methods in Computational Finance - Daniel J. Duffy - Страница 45

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:

(2.39)

The solution of Equation (2.39) is given by:

We see that is bounded if and only if and this implies (recall that is a complex number) where means ‘real part of ’.

This example leads us to our first encounter with the concept of stability of finite difference schemes. In particular, we define the region of absolute stability of a numerical method for an IVP as the set of complex values of for which all discrete approximations to the test problem (2.37) remain bounded when tends to infinity. For example, for the trapezoidal method (2.39) the left-half plane is the stability region.

Theorem 2.1 (The Root Condition). A necessary and sufficient condition for the stability of a linear multistep method (2.32) is that all the roots of the polynomial defined by Equation (2.34) are located inside or on the unit circle and that the roots of modulus 1 are simple.

We now discuss convergence issues. We say that a difference scheme has order of accuracy if:

where approximate solution of (2.32), exact solution of (2.31), and is independent of .

We conclude this section by stating a convergence result that allows us to estimate the error between the exact solution of an initial value problem and the solution of a multistep scheme that approximates it. To this end, we consider the -dimensional autonomous initial value problem:

By autonomous we mean that is a function of the dependent variable only and is thus not of the form . The latter form is called non-autonomous.

We approximate this IVP using the multistep method (2.32). We recall:

Theorem 2.2 Assume that the solution of the is times differentiable with and assume that is differentiable for all .

Suppose furthermore that the sequence is defined by the equations:

If the multistep method is stable and satisfies:

where C is a positive constant independent of , then there exist constants and such that for all :

In all cases we define the norm for a vector as:

We state this theorem in more general terms: consistency and stability of a multistep scheme are sufficient for convergence.

Finally, the discussion in this section is also applicable to systems of ODEs. For more discussions, we recommend Henrici (1962) and Lambert (1991).

Finally, we present four finite difference schemes for the IVP (2.31) and their generating polynomials as defined by Equations (2.34):

We recommend that you verify the results using the forms of the generating polynomials for one-step and two-step methods, respectively. The general forms are: