Numerical Solution of Parabolic Equations

Finite Differences, Global error estimation, ADI methods, Partial Differential Equations

These lecture notes are designed for a one-semester course on finite-difference methods for parabolic equations. These equations which traditionally are used for describing diffusion and heat-conduction problems in Geology, Physics, and Chemistry have recently found applications in Finance Theory.

Among the special features of this book can be mentioned the presentation of a practical approach to reliable estimates of the global error, including warning signals if the reliability is questionable. The technique is generally applicable for estimating the discretization error in numerical approximations which depend on a step size, such as numerical integration and solution of ordinary and partial differential equations. An integral part of the error estimation is the estimation of the order of the method and can thus satisfy the inquisitive mind: Is the order what we expect it to be from theopry ? and how do boundary value approximations affect the overall order of the method. Knowledge of a reliable order and error estimate enables us to determine (near-)optimal step sizes to meet a prescribed error tolerance, and possibly to extrapolate to get (higher order and) better accuracy at a minimal expense.

Problems in two space dimensions are effectively handled using the Alternating Direction Implicit (ADI) technique. We present a systematic way of incorporating inhomogeneous terms and derivative boundary conditions in ADI methods as well as mixed derivative terms.

A. C. Aitken, On Bernoulli's numerical solution of algebraic equations, Proc. Roy. Soc. Edinburgh, 46 (1926), pp. 289–305.

V. A. Barker, Extrapolation, Hæfte 31, Numerisk Institut, DtH, Lyngby, 1974.

M. J. Brennan and E. S. Schwartz, A continuous time approach to the pricing of bonds, Journal of Banking and Finance, 3 (1979), pp. 133–155.

M. J. Brennan and E. S. Schwartz, The valuation of American put options, Journal of Finance, 32 (1977), pp. 449–462.

G. G. O'Brien, M. A. Hyman, and S. Kaplan, A Study of the Numerical Solution of Partial Differential Equations, J. Math. Phys., 29 (1951), pp. 223–251.

D. Britz and O. Østerby, Some numerical investigations of the stability of electrochemical digital simulation, particularly as affected by first-order homogeneous reactions, J. Electroanal. Chem., 368 (1994), pp. 143–147.

E. T. Copson and P. Keast, On a boundary-value problem for the equation of heat, J. Inst. Maths. Applics, 2 (1966), pp. 358–363.

J. Crank and 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. Reprinted in Adv. Comput. Math., 6 (1996), pp. 207–226.

J. Douglas and T. M. Gallie, On the numerical integration of a parabolic differential equation subject to a moving boundary condition, Duke Math. J., 22 (1955), pp. 557-571.

J. Douglas and H. H. Rachford, On the numerical solution of heat conduction problems in two and three space variables, Trans. Amer. Math. Soc., 82 (1956), pp. 421–439.203

E. C. Du Fort and S. P. Frankel, Stability Conditions in the Numerical Treatment of Parabolic Differential Equations, Math. Tables Aid Comput., 7, (1953), pp. 135–152.

A. R. Gourlay and J. Ll. Morris, The extrapolation of first order methods for parabolic partial differential equations II, SIAM J. Numer. Anal., 17, (1980), pp. 641–655.

P. M. Gresho and R. L. Lee, Don't suppress the wiggles – they're telling you something, Computers and Fluids, 9 (1981), pp. 223–253.

Asbjørn Trolle Hansen, Martingale Methods in Contingent Claim Pricing and Asymmetric Financial Markets, Ph.D. thesis, Dept. Oper. Research, Aarhus University, 1998.

Asbjørn Trolle Hansen and Ole Østerby, Accelerating the Crank-Nicolson method in American option pricing, Dept. Oper. Research, Aarhus University, 1998.

D. R. Hartree and J. R. Womersley, A Method for the Numerical or Mechanical Solution of Certain Types of Partial Differential Equations, Proc. Royal Soc. London, Ser. A, 161 (1937), pp. 353–366.

D. C. Joyce, Survey of extrapolation processes in numerical analysis, SIAM Review, 13 (1971), pp. 435–490.

P. Keast and A. R. Mitchell, Finite difference solution of the third boundary problem in elliptic and parabolic equations, Numer. Math., 10, (1967), pp. 67–75.

P. Laasonen, Über eine Methode zur Lösung der Wärmeleitungsgleichung, Acta Math., 81 (1949), pp. 309–317.

J. D. Lawson and J. Ll. Morris, The extrapolation of first order methods forparabolic partial differential equations I, SIAM J. Numer. Anal., 15, (1978), pp. 1212–1224.

P. D. Lax and R. D. Richtmyer, Survey of the Stability of Linear Finite Difference Equations, Comm. Pure Appl. Math., 9, (1956), pp. 267–293.

P. D. Lax and B. Wendroff, Systems of conservation laws, Comm. Pure Appl. Math., 13, (1960), pp. 217–237.

B. Lindberg, On smoothing and extrapolation for the trapezoidal rule, BIT, 11 (1971), pp. 29–52.204

F. A. Longstaff and E. S. Schwartz, Interest rate volatility and the termstructure: A two-factor general equilibrium model, J. Finance, 47 (1992), pp. 1259–1282. See also Journal of Fixed Income (1993), pp. 7–14.

A. R. Mitchell and D. F. Griffiths, The Finite Difference Method in Partial Differential Equations, John Wiley, Chichester, 1980.

P. L. J. van Moerbeke, On optimal stopping and free boundary problems, Arch. Rational Mech. Anal., 60 (1976), pp. 101–148.

D. W. Peaceman and H. H. Rachford, The numerical solution of parabolicand elliptic differential equations, J. SIAM, 3 (1955), pp. 28–41.

C. E. Pearson, Impulsive end condition for diffusion equation, Math. Comp., 19 (1965), pp. 570–576.

Lewis F. Richardson, The Approximate Numerical Solution by Finite Differences of Physical Problems Involving Differential Equations, Phil. Trans. Roy. Soc. London, Series A, 210 (1910), pp. 307–357.

Lewis F. Richardson and J. Arthur Gaunt, The Deferred Approach to the Limit I - II, Phil. Trans. Roy. Soc. London, Series A, 226 (1927), pp. 299–361.

Robert D. Richtmyer, Difference Methods for Initial-Value Problems, Interscience, New York, 1957.

Werner Romberg, Vereinfachte Numerische Integration, Norske Vid. Selsk. Forh., Trondheim, 28 (1955), pp. 30–36.

J. Stefan, Über die Theorie der Eisbildung, insbesondere über die Eisbildungim Polarmeere, Akad. Wiss. Wien, Mat. Nat. Classe, Sitzungsberichte, 98(1889), pp. 965–983.

G. W. Stewart, Introduction to Matrix Computations, Academic Press, New York, 1973.

J. C. Strikwerda, Finite Difference Schemes and Partial Differential Equations, Wadsworth and Brooks/Cole, Pacific Grove, CA, 1989.

Øystein Tødenes, On the numerical solution of the diffusion equation, Math. Comp., 24, (1970), pp. 621–627.

J. H. Wilkinson, Rounding Errors in Algebraic Processes, HMSO, London, 1963.205

W. L. Wood and R. W. Lewis, A comparison of time marching schemes for the transient heat conduction equation, Int. J. Num. Meth. Engrg., 9, (1975), 679–689.

Y. G. D'Yakonov,On the application of disintegrating difference operators, USSR Comp. Math., 3 (1963), 511–515. See also vol. 2 (1962), pp. 55–77 and pp. 581–607.

O. Østerby, Stability of finite difference formulas for linear parabolic equations, 2nd Int. Coll. on Numerical Analysis, Plovdiv, D. Bainov and V.Covachev (eds.), VSP Press, Utrecht (1994), pp. 165–176.

O. Østerby, Five ways of reducing the Crank-Nicolson oscillations, BIT, 43 (2003), pp. 811–822.206