Numerical Methods in Computational Finance

DANIEL DUFFY, PhD, has BA (Mod), MSc and PhD degrees in pure, applied and numerical mathematics (University of Dublin, Trinity College) and he is active in promoting partial differential equations (PDE) and the Finite Difference Method (FDM) for applications in computational finance. He was responsible for the introduction of the Fractional Step (Soviet Splitting) method and the Alternating Direction Explicit (ADE) method in computational finance. He is the originator of the exponential fitting method for convection-dominated PDEs.

• Preface xixWho Should Read this Book? xxiiiPart A : Mathematical Foundation for One-Factor ProblemsChapter 1 : Real Analysis Foundations for this Book 31.1 Introduction and Objectives 31.2 Continuous Functions 41.2.1 Formal Definition of Continuity 51.2.2 An Example 61.2.3 Uniform Continuity 61.2.4 Classes of Discontinuous Functions 71.3 Differential Calculus 81.3.1 Taylor’s Theorem 91.3.2 Big O and Little o Notation 101.4 Partial Derivatives 111.5 Functions and Implicit Forms 131.6 Metric Spaces and Cauchy Sequences 141.6.1 Metric Spaces 151.6.2 Cauchy Sequences 161.6.3 Lipschitz Continuous Functions 171.7 Summary and Conclusions 19Chapter 2 : Ordinary Differential Equations (ODEs), Part 1 212.1 Introduction and Objectives 212.2 Background and Problem Statement 222.2.1 Qualitative Properties of the Solution and Maximum Principle 222.2.2 Rationale and Generalisations 242.3 Discretisation of Initial Value Problems: Fundamentals 252.3.1 Common Schemes 262.3.2 Discrete Maximum Principle 282.4 Special Schemes 292.4.1 Exponential Fitting 292.4.2 Scalar Non-Linear Problems and Predictor-Corrector Method 312.4.3 Extrapolation 312.5 Foundations of Discrete Time Approximations 322.6 Stiff ODEs 372.7 Intermezzo: Explicit Solutions 392.8 Summary and Conclusions 41Chapter 3 : Ordinary Differential Equations (ODEs), Part 2 433.1 Introduction and Objectives 433.2 Existence and Uniqueness Results 433.2.1 An Example 453.3 Other Model Examples 453.3.1 Bernoulli ODE 453.3.2 Riccati ODE 463.3.3 Predator-Prey Models 473.3.4 Logistic Function 483.4 Existence Theorems for Stochastic Differential Equations (SDEs) 483.4.1 Stochastic Differential Equations (SDEs) 493.5 Numerical Methods for ODEs 513.5.1 Code Samples in Python 523.6 The Riccati Equation 553.6.1 Finite Difference Schemes 573.7 Matrix Differential Equations 593.7.1 Transition Rate Matrices and Continuous Time Markov Chains 613.8 Summary and Conclusions 62Chapter 4 : An Introduction to Finite Dimensional Vector Spaces 634.1 Short Introduction and Objectives 634.1.1 Notation 644.2 What Is a Vector Space? 654.3 Subspaces 674.4 Linear Independence and Bases 684.5 Linear Transformations 694.5.1 Invariant Subspaces 704.5.2 Rank and Nullity 714.6 Summary and Conclusions 72Chapter 5 : Guide to Matrix Theory and Numerical Linear Algebra 735.1 Introduction and Objectives 735.2 From Vector Spaces to Matrices 735.2.1 Sums and Scalar Products of Linear Transformations 735.3 Inner Product Spaces 745.3.1 Orthonormal Basis 755.4 From Vector Spaces to Matrices 765.4.1 Some Examples 765.5 Fundamental Matrix Properties 775.6 Essential Matrix Types 805.6.1 Nilpotent and Related Matrices 805.6.2 Normal Matrices 815.6.3 Unitary and Orthogonal Matrices 825.6.4 Positive Definite Matrices 825.6.5 Non-Negative Matrices 835.6.6 Irreducible Matrices 835.6.7 Other Kinds of Matrices 845.7 The Cayley Transform 845.8 Summary and Conclusions 86Chapter 6 : Numerical Solutions of Boundary Value Problems 876.1 Introduction and Objectives 876.2 An Introduction to Numerical Linear Algebra 876.2.1 BLAS (Basic Linear Algebra Subprograms) 906.3 Direct Methods for Linear Systems 926.3.1 LU Decomposition 926.3.2 Cholesky Decomposition 946.4 Solving Tridiagonal Systems 946.4.1 Double Sweep Method 946.4.2 Thomas Algorithm 966.4.3 Block Tridiagonal Systems 976.5 Two-Point Boundary Value Problems 996.5.1 Finite Difference Approximation 1006.5.2 Approximation of Boundary Conditions 1026.6 Iterative Matrix Solvers 1036.6.1 Iterative Methods 1036.6.2 Jacobi Method 1046.6.3 Gauss–Seidel Method 1046.6.4 Successive Over-Relaxation (SOR) 1056.6.5 Other Methods 1056.7 Example: Iterative Solvers for Elliptic PDEs 1066.8 Summary and Conclusions 107Chapter 7 : Black–Scholes Finite Differences for the Impatient 1097.1 Introduction and Objectives 1097.2 The Black–Scholes Equation: Fully Implicit and Crank–Nicolson Methods 1107.2.1 Fully Implicit Method 1107.2.2 Crank–Nicolson Method 1117.2.3 Final Remarks 1147.3 The Black–Scholes Equation: Trinomial Method 1157.3.1 Comparison with Other Methods 1157.4 The Heat Equation and Alternating Direction Explicit (ADE) Method 1207.4.1 Background and Motivation 1207.5 ADE for Black–Scholes: Some Test Results 1217.6 Summary and Conclusions 126Part B : Mathematical Foundation for Two-Factor ProblemsChapter 8 : Classifying and Transforming Partial Differential Equations 1298.1 Introduction and Objectives 1298.2 Background and Problem Statement 1298.3 Introduction to Elliptic Equations 1308.3.1 What is an Elliptic Operator? 1308.3.2 Total and Principal Symbols 1318.3.3 The Adjoint Equation 1328.3.4 Self-Adjoint Operators and Equations 1338.3.5 Numerical Approximation of PDEs in Adjoint Form 1348.3.6 Elliptic Equations with Non-Negative Characteristic Form 1358.4 Classification of Second-Order Equations 1358.4.1 Characteristics 1368.4.2 Model Example 1378.4.3 Test your Knowledge 1388.5 Examples of Two-Factor Models from Computational Finance 1398.5.1 Multi-Asset Options 1398.5.2 Stochastic Dividend PDE 1408.6 Summary and Conclusions 141Chapter 9 : Transforming Partial Differential Equations to a Bounded Domain 1439.1 Introduction and Objectives 1439.2 The Domain in Which a PDE Is Defined: Preamble 1439.2.1 Background and Specific Mappings 1449.2.2 Initial Examples 1469.3 Other Examples 1479.4 Hotspots 1489.5 What Happened to Domain Truncation? 1489.6 Another Way to Remove Mixed Derivative Terms 1499.7 Summary and Conclusions 151Chapter 10 : Boundary Value Problems for Elliptic and Parabolic Partial Differential Equations 15310.1 Introduction and Objectives 15310.2 Notation and Prerequisites 15410.3 The Laplace Equation 15410.3.1 Harmonic Functions and the Cauchy–Riemann Equations 15410.4 Properties of The Laplace Equation 15610.4.1 Maximum-Minimum Principle for Laplace’s Equation 15810.5 Some Elliptic Boundary Value Problems 15910.5.1 Some Motivating Examples 15910.6 Extended Maximum-Minimum Principles 15910.6.1 An Example 16110.7 Summary and Conclusions 162Chapter 11 : Fichera Theory, Energy Inequalities and Integral Relations 16311.1 Introduction and Objectives 16311.2 Background and Problem Statement 16311.2.1 The ‘Big Bang’: Cauchy–Euler Equation 16311.3 Well-Posed Problems and Energy Estimates 16511.3.1 Time to Reflect: What Have We Achieved and What’s Next? 16711.4 The Fichera Theory: Overview 16811.5 The Fichera Theory: The Core Business 16811.6 The Fichera Theory: Further Examples and Applications 17111.6.1 Cox–Ingersoll–Ross (CIR) 17111.6.2 Heston Model Fundamenals 17211.6.3 Heston Model by Fichera Theory 17611.6.4 First-Order Hyperbolic PDE in One and Two Space Variables 17711.7 Some Useful Theorems 17811.7.1 Divergence (Gauss–Ostrogradsky) Theorem 17911.7.2 Green’s Theorem/Formula 18011.7.3 Green’s First and Second Identities 18011.8 Summary and Conclusions 180Chapter 12 : An Introduction to Time-Dependent Partial Differential Equations 18112.1 Introduction and Objectives 18112.2 Notation and Prerequisites 18112.3 Preamble: Separation of Variables for the Heat Equation 18212.4 Well-Posed Problems 18412.4.1 Examples of an ill-posed Problem 18512.4.2 The Importance of Proving that Problems Are Well-Posed 18712.5 Variations on Initial Boundary Value Problem for the Heat Equation 18812.5.1 Smoothness and Compatibility Conditions 18812.6 Maximum-Minimum Principles for Parabolic PDEs 18912.7 Parabolic Equations with Time-Dependent Boundaries 19012.8 Uniqueness Theorems for Boundary Value Problems in Two Dimensions 19212.8.1 Laplace Equation 19212.8.2 Heat Equation 19312.9 Summary and Conclusions 193Chapter 13 : Stochastics Representations of PDEs and Applications 19513.1 Introduction and Objectives 19513.2 Background, Requirements and Problem Statement 19613.3 An Overview of Stochastic Differential Equations (SDEs) 19613.4 An Introduction to One-Dimensional Random Processes 19613.5 An Introduction to the Numerical Approximation of SDEs 19913.5.1 Euler–Maruyama Method 19913.5.2 Milstein Method 20113.5.3 Predictor-Corrector Method 20113.5.4 Drift-Adjusted Predictor-Corrector Method 20213.6 Path Evolution and Monte Carlo Option Pricing 20313.6.1 Monte Carlo Option Pricing 20413.6.2 Some C++ Code 20513.7 Two-Factor Problems 20913.7.1 Spread Options with Stochastic Volatility 20913.7.2 Heston Stochastic Volatility Model 21113.8 The Ito Formula 21513.9 Stochastics Meets PDEs 21513.9.1 A Statistics Refresher 21513.9.2 The Feynman–Kac Formula 21713.9.3 Kolmogorov Equations 21813.9.4 Kolmogorov Forward (Fokker–Planck (FPE)) Equation 21813.9.5 Multi-Dimensional Problems and Boundary Conditions 21913.9.6 Kolmogorov Backward Equation (KBE) 22013.10 First Exit-Time Problems 22113.11 Summary and Conclusions 222Part C : The Foundations of the Finite Difference Method (FDM)Chapter 14 : Mathematical and Numerical Foundations of the Finite Difference Method, Part I 22514.1 Introduction and Objectives 22514.2 Notation and Prerequisites 22614.3 What Is the Finite Difference Method, Really? 22714.4 Fourier Analysis of Linear PDEs 22714.4.1 Fourier Transform for Advection Equation 22914.4.2 Fourier Transform for Diffusion Equation 23014.5 Discrete Fourier Transform 23214.5.1 Finite and Infinite Dimensional Sequences and Their Norms 23214.5.2 Discrete Fourier Transform (DFT) 23314.5.3 Discrete von Neumann Stability Criterion 23514.5.4 Some More Examples 23514.6 Theoretical Considerations 23714.6.1 Consistency 23714.6.2 Stability 23814.6.3 Convergence 23914.7 First-Order Partial Differential Equations 23914.7.1 Why First-Order Equations are Different: Essential Difficulties 24214.7.2 A Simple Explicit Scheme 24314.7.3 Some Common Schemes for Initial Value Problems 24514.7.4 Some Other Schemes 24614.7.5 General Linear Problems 24814.8 Summary and Conclusions 248Chapter 15: Mathematical and Numerical Foundations of the Finite Difference Method, Part II 24915.1 Introduction and Objectives 24915.2 A Short History of Numerical Methods for CDR Equations 25015.2.1 Temporal and Spatial Stability 25115.2.2 Motivating Exponential Fitting Methods 25315.2.3 Eliminating Temporal and Spatial Stability Problems 25415.3 Exponential Fitting and Time-Dependent Convection-Diffusion 25715.4 Stability and Convergence Analysis 25815.5 Special Limiting Cases 26015.6 Stability for Initial Boundary Value Problems 26015.6.1 Gerschgorin’s Circle Theorem 26115.7 Semi-Discretisation for Convection-Diffusion Problems 26415.7.1 Essentially Positive Matrices 26515.7.2 Fully Discrete Schemes 26715.8 Padé Matrix Approximation 26915.8.1 Padé Matrix Approximations 27015.9 Time-Dependent Convection-Diffusion Equations 27515.9.1 Fully Discrete Schemes 27515.10 Summary and Conclusions 276Chapter 16 Sensitivity Analysis, Option Greeks and Parameter Optimisation, Part I 27716.1 Introduction and Objectives 27716.2 Helicopter View of Sensitivity Analysis 27816.3 Black–Scholes–Merton Greeks 27916.3.1 Higher-Order and Mixed Greeks 28216.4 Divided Differences 28216.4.1 Approximation to First and Second Derivatives 28216.4.2 Black–Scholes Numeric Greeks and Divided Differences 28516.5 Cubic Spline Interpolation 28616.5.1 Caveat: Cubic Splines with Sparse Input Data 28916.5.2 Cubic Splines for Option Greeks 29016.5.3 Boundary Conditions 29116.6 Some Complex Function Theory 29216.6.1 Curves and Regions 29316.6.2 Taylor’s Theorem and Series 29416.6.3 Laurent’s Theorem and Series 29516.6.4 Cauchy–Goursat Theorem 29616.6.5 Cauchy’s Integral Formula 29716.6.6 Cauchy’s Residue Theorem 29816.6.7 Gauss’s Mean Value Theorem 29916.7 The Complex Step Method (CSM) 29916.7.1 Caveats 30216.8 Summary and Conclusions 302Chapter 17 Advanced Topics in Sensitivity Analysis 30517.1 Introduction and Objectives 30517.2 Examples of CSE 30517.2.1 Simple Initial Value Problem 30617.2.2 Population Dynamics 30717.2.3 Comparing CSE and Complex Step Method (CSM) 31017.3 CSE and Black–Scholes PDE 31017.3.1 Black–Scholes Greeks: Algorithms and Design 31117.3.2 Some Specific Black–Scholes Greeks 31217.4 Using Operator Calculus to Compute Greeks 31317.5 An Introduction to Automatic Differentiation (AD) for the Impatient 31417.5.1 What Is Automatic Differentiation: The Details 31617.6 Dual Numbers 31717.7 Automatic Differentiation in C++ 31817.8 Summary and Conclusions 319Part D : Advanced Finite Difference Schemes for Two-Factor ProblemsChapter 18 : Splitting Methods, Part I 32318.1 Introduction and Objectives 32318.2 Background and History 32418.3 Notation, Prerequisites and Model Problems 32518.4 Motivation: Two-Dimensional Heat Equation 32818.4.1 Alternating Direction Implicit (ADI) Method 32818.4.2 Soviet (Operator) Splitting 33018.4.3 Mixed Derivative and Yanenko Scheme 33118.5 Other Related Schemes for the Heat Equation 33318.5.1 D’Yakonov Method 33318.5.2 Approximate Factorisation of Operators 33418.5.3 Predictor-Corrector Methods 33718.5.4 Partial Integro Differential Equations (PIDEs) 33818.6 Boundary Conditions 33918.7 Two-Dimensional Convection PDEs 34118.8 Three-Dimensional Problems 34318.9 The Hopscotch Method 34418.10 Software Design and Implementation Guidelines 34618.11 The Future: Convection-Diffusion Equations 34618.12 Summary and Conclusions 347Chapter 19 : The Alternating Direction Explicit (ADE) Method 34919.1 Introduction and Objectives 34919.2 Background and Problem Statement 35119.3 Global Overview and Applicability of ADE 35119.4 Motivating Examples: One-Dimensional and Two-Dimensional Diffusion Equations 35219.4.1 Barakat and Clark (B&C) Method 35319.4.2 Saul’yev Method 35419.4.3 Larkin Method 35519.4.4 Two-Dimensional Diffusion Problems 35519.5 ADE for Convection (Advection) Equation 35619.6 Convection-Diffusion PDEs 35819.6.1 Example: Black–Scholes PDE 35919.6.2 Boundary Conditions 36019.6.3 Spatial Amplification Errors 36119.7 Attention Points with ADE 362The Consequences of Conditional Consistency 362Call Pay-Off Behaviour at the Far Field 36219.7.1 General Formulation of the ADE Method 36219.8 Summary and Conclusions 364Chapter 20 : The Method of Lines (MOL), Splitting and the Matrix Exponential 36520.1 Introduction and Objectives 36520.2 Notation and Prerequisites: The Exponential Function 36620.2.1 Initial Results 36720.2.2 The Exponential of a Matrix 36720.3 The Exponential of a Matrix: Advanced Topics 36820.3.1 Fundamental Theorem for Linear Systems 368Proof of Theorem 20.1. 36920.3.2 An Example 36920.4 Motivation: One-Dimensional Heat Equation 37020.5 Semi-Linear Problems 37320.6 Test Case: Double-Barrier Options 37520.6.1 PDE Formulation 37620.6.2 Using Exponential Fitting of Barrier Options 37720.6.3 Performing MOL with Boost C++ odeint 37820.6.4 Computing Sensitivities 38120.6.5 American Options 38420.7 Summary and Conclusions 384Chapter 21 : Free and Moving Boundary Value Problems 38721.1 Introduction and Objectives 38721.2 Background, Problem Statement and Formulations 38821.3 Notation and Prerequisites 38821.4 Some Initial Examples of Free and Moving Boundary Value Problems 38921.4.1 Single-Phase Melting Ice 38921.4.2 Oxygen Diffusion 39021.4.3 American Option Pricing 39121.4.4 Two-Phase Melting Ice 39221.5 An Introduction to Parabolic Variational Inequalities 39221.5.1 Formulation of Problem: Test Case 39221.5.2 Examples of Initial Boundary Value Problems 39521.6 An Introduction to Front-Fixing 39921.6.1 Front-Fixing for the Heat Equation 39921.7 Python Code Example: ADE for American Option Pricing 40021.8 Summary and Conclusions 405Chapter 22 : Splitting Methods, Part II 40722.1 Introduction and Objectives 40722.2 Background and Problem Statement: The Essence of Sequential Splitting 40822.3 Notation and Mathematical Formulation 40822.3.1 C0 Semigroups 40822.3.2 Abstract Cauchy Problem 40922.3.3 Examples 41022.4 Mathematical Foundations of Splitting Methods 41122.4.1 Lie (Trotter) Product Formula 41122.4.2 Splitting Error 41122.4.3 Component Splitting and Operator Splitting 41322.4.4 Splitting as a Discretisation Method 41322.5 Some Popular Splitting Methods 41422.5.1 First-Order (Lie–Trotter) Splitting 41522.5.2 Predictor-Corrector Splitting 41522.5.3 Marchuk’s Two-Cycle (1-2-2-1) Method 41622.5.4 Strang Splitting 41722.6 Applications and Relationships to Computational Finance 41722.7 Software Design and Implementation Guidelines 41822.8 Experience Report: Comparing ADI and Splitting 41922.9 Summary and Conclusions 421Part E : Test Cases in Computational FinanceChapter 23 : Multi-Asset Options 42523.1 Introduction and Objectives 42523.2 Background and Goals 42623.3 The Bivariate Normal Distribution (BVN) and its Applications 42723.3.1 Computing BVN by Solving a Hyperbolic PDE 43023.3.2 Analytical Solutions of Multi-Asset and Basket Options 43323.4 PDE Models for Multi-Asset Option Problems: Requirements and Design 43523.4.1 Domain Transformation 43523.4.2 Numerical Boundary Conditions 43523.5 An Overview of Finite Difference Schemes for Multi-Asset Option Problems 43623.5.1 Common Design Principles 43623.5.2 Detailed Design 43823.5.3 Testing the Software 44023.6 American Spread Options 44023.7 Appendices 44223.7.1 Traditional Approach to Numerical Boundary Conditions 44223.7.2 Top-Down Design of Monte Carlo Applications 44323.8 Summary and Conclusions 444Chapter 24 : Asian (Average Value) Options 44724.1 Introduction and Objectives 44724.2 Background and Problem Statement 44824.2.1 Challenges 44924.3 Prototype PDE Model 45024.3.1 Similarity Reduction 45124.4 The Many Ways to Handle the Convective Term 45224.4.1 Method of Lines (MOL) 45224.4.2 Other Schemes 45424.4.3 A Stable Monotone Upwind Scheme 45524.5 ADE for Asian Options 45524.6 ADI for Asian Options 45624.6.1 Modern ADI Variations 45824.7 Summary and Conclusions 459Chapter 25 : Interest Rate Models 46125.1 Introduction and Objectives 46125.2 Main Use Cases 46225.3 The CIR Model 46225.3.1 Analytic Solutions 46325.3.2 Initial Boundary Value Problem 46625.4 Well-Posedness of the CIRPDE Model 46625.4.1 Gronwall’s Inequalities 46725.4.2 Energy Inequalities 46825.5 Finite Difference Methods for the CIR Model 46925.5.1 Numerical Boundary Conditions 47025.6 Heston Model and the Feller Condition 47125.7 Summary and Conclusion 475Chapter 26 : Epilogue Models Follow-Up Chapters 1 to 25 47726.1 Introduction and Objectives 47726.2 Mixed Derivatives and Monotone Schemes 47826.2.1 The Maximum Principle and Mixed Derivatives 47826.2.2 Some Examples 48026.2.3 Code Sample Method of Lines (MOL) for Two-Factor Hull–White Model 48126.3 The Complex Step Method (CSM) Revisited 48326.3.1 Black–Scholes Greeks Using CSM and the Faddeeva Function 48326.3.2 CSM and Functions of Several Complex Variables 48726.3.3 C++ Code for Extended CSM 48826.3.4 CSM for Non-Linear Solvers 49226.4 Extending the Hull–White: Possible Projects 49326.5 Summary and Conclusions 495Bibliography 497Index 505

Select Guide Rating