Description
Book SynopsisThis book is a detailed and step-by-step introduction to the mathematical foundations of ordinary and partial differential equations, their approximation by the finite difference method and applications to computational finance. The book is structured so that it can be read by beginners, novices and expert users. Part A Mathematical Foundation for One-Factor Problems Chapters 1 to 7 introduce the mathematical and numerical analysis concepts that are needed to understand the finite difference method and its application to computational finance. Part B Mathematical Foundation for Two-Factor Problems Chapters 8 to 13 discuss a number of rigorous mathematical techniques relating to elliptic and parabolic partial differential equations in two space variables. In particular, we develop strategies to preprocess and modify a PDE before we approximate it by the finite difference method, thus avoiding ad-hoc and heuristic tricks. Part C The Foundations of the Finite Difference Method (FDM) Chapters 14 to 17 introduce the mathematical background to the finite difference method for initial boundary value problems for parabolic PDEs. It encapsulates all the background information to construct stable and accurate finite difference schemes. Part D Advanced Finite Difference Schemes for Two-Factor Problems Chapters 18 to 22 introduce a number of modern finite difference methods to approximate the solution of two factor partial differential equations. This is the only book we know of that discusses these methods in any detail. Part E Test Cases in Computational Finance Chapters 23 to 26 are concerned with applications based on previous chapters. We discuss finite difference schemes for a wide range of one-factor and two-factor problems. This book is suitable as an entry-level introduction as well as a detailed treatment of modern methods as used by industry quants and MSc/MFE students in finance. The topics have applications to numerical analysis, science and engineering. More on computational finance and the author's online courses, see www.datasim.nl.
Table of ContentsPreface xix
Who Should Read this Book? xxiii
Part A : Mathematical Foundation for One-Factor Problems
Chapter 1 : Real Analysis Foundations for this Book 3
1.1 Introduction and Objectives 3
1.2 Continuous Functions 4
1.2.1 Formal Definition of Continuity 5
1.2.2 An Example 6
1.2.3 Uniform Continuity 6
1.2.4 Classes of Discontinuous Functions 7
1.3 Differential Calculus 8
1.3.1 Taylor’s Theorem 9
1.3.2 Big O and Little o Notation 10
1.4 Partial Derivatives 11
1.5 Functions and Implicit Forms 13
1.6 Metric Spaces and Cauchy Sequences 14
1.6.1 Metric Spaces 15
1.6.2 Cauchy Sequences 16
1.6.3 Lipschitz Continuous Functions 17
1.7 Summary and Conclusions 19
Chapter 2 : Ordinary Differential Equations (ODEs), Part 1 21
2.1 Introduction and Objectives 21
2.2 Background and Problem Statement 22
2.2.1 Qualitative Properties of the Solution and Maximum Principle 22
2.2.2 Rationale and Generalisations 24
2.3 Discretisation of Initial Value Problems: Fundamentals 25
2.3.1 Common Schemes 26
2.3.2 Discrete Maximum Principle 28
2.4 Special Schemes 29
2.4.1 Exponential Fitting 29
2.4.2 Scalar Non-Linear Problems and Predictor-Corrector Method 31
2.4.3 Extrapolation 31
2.5 Foundations of Discrete Time Approximations 32
2.6 Stiff ODEs 37
2.7 Intermezzo: Explicit Solutions 39
2.8 Summary and Conclusions 41
Chapter 3 : Ordinary Differential Equations (ODEs), Part 2 43
3.1 Introduction and Objectives 43
3.2 Existence and Uniqueness Results 43
3.2.1 An Example 45
3.3 Other Model Examples 45
3.3.1 Bernoulli ODE 45
3.3.2 Riccati ODE 46
3.3.3 Predator-Prey Models 47
3.3.4 Logistic Function 48
3.4 Existence Theorems for Stochastic Differential Equations (SDEs) 48
3.4.1 Stochastic Differential Equations (SDEs) 49
3.5 Numerical Methods for ODEs 51
3.5.1 Code Samples in Python 52
3.6 The Riccati Equation 55
3.6.1 Finite Difference Schemes 57
3.7 Matrix Differential Equations 59
3.7.1 Transition Rate Matrices and Continuous Time Markov Chains 61
3.8 Summary and Conclusions 62
Chapter 4 : An Introduction to Finite Dimensional Vector Spaces 63
4.1 Short Introduction and Objectives 63
4.1.1 Notation 64
4.2 What Is a Vector Space? 65
4.3 Subspaces 67
4.4 Linear Independence and Bases 68
4.5 Linear Transformations 69
4.5.1 Invariant Subspaces 70
4.5.2 Rank and Nullity 71
4.6 Summary and Conclusions 72
Chapter 5 : Guide to Matrix Theory and Numerical Linear Algebra 73
5.1 Introduction and Objectives 73
5.2 From Vector Spaces to Matrices 73
5.2.1 Sums and Scalar Products of Linear Transformations 73
5.3 Inner Product Spaces 74
5.3.1 Orthonormal Basis 75
5.4 From Vector Spaces to Matrices 76
5.4.1 Some Examples 76
5.5 Fundamental Matrix Properties 77
5.6 Essential Matrix Types 80
5.6.1 Nilpotent and Related Matrices 80
5.6.2 Normal Matrices 81
5.6.3 Unitary and Orthogonal Matrices 82
5.6.4 Positive Definite Matrices 82
5.6.5 Non-Negative Matrices 83
5.6.6 Irreducible Matrices 83
5.6.7 Other Kinds of Matrices 84
5.7 The Cayley Transform 84
5.8 Summary and Conclusions 86
Chapter 6 : Numerical Solutions of Boundary Value Problems 87
6.1 Introduction and Objectives 87
6.2 An Introduction to Numerical Linear Algebra 87
6.2.1 BLAS (Basic Linear Algebra Subprograms) 90
6.3 Direct Methods for Linear Systems 92
6.3.1 LU Decomposition 92
6.3.2 Cholesky Decomposition 94
6.4 Solving Tridiagonal Systems 94
6.4.1 Double Sweep Method 94
6.4.2 Thomas Algorithm 96
6.4.3 Block Tridiagonal Systems 97
6.5 Two-Point Boundary Value Problems 99
6.5.1 Finite Difference Approximation 100
6.5.2 Approximation of Boundary Conditions 102
6.6 Iterative Matrix Solvers 103
6.6.1 Iterative Methods 103
6.6.2 Jacobi Method 104
6.6.3 Gauss–Seidel Method 104
6.6.4 Successive Over-Relaxation (SOR) 105
6.6.5 Other Methods 105
6.7 Example: Iterative Solvers for Elliptic PDEs 106
6.8 Summary and Conclusions 107
Chapter 7 : Black–Scholes Finite Differences for the Impatient 109
7.1 Introduction and Objectives 109
7.2 The Black–Scholes Equation: Fully Implicit and Crank–Nicolson Methods 110
7.2.1 Fully Implicit Method 110
7.2.2 Crank–Nicolson Method 111
7.2.3 Final Remarks 114
7.3 The Black–Scholes Equation: Trinomial Method 115
7.3.1 Comparison with Other Methods 115
7.4 The Heat Equation and Alternating Direction Explicit (ADE) Method 120
7.4.1 Background and Motivation 120
7.5 ADE for Black–Scholes: Some Test Results 121
7.6 Summary and Conclusions 126
Part B : Mathematical Foundation for Two-Factor Problems
Chapter 8 : Classifying and Transforming Partial Differential Equations 129
8.1 Introduction and Objectives 129
8.2 Background and Problem Statement 129
8.3 Introduction to Elliptic Equations 130
8.3.1 What is an Elliptic Operator? 130
8.3.2 Total and Principal Symbols 131
8.3.3 The Adjoint Equation 132
8.3.4 Self-Adjoint Operators and Equations 133
8.3.5 Numerical Approximation of PDEs in Adjoint Form 134
8.3.6 Elliptic Equations with Non-Negative Characteristic Form 135
8.4 Classification of Second-Order Equations 135
8.4.1 Characteristics 136
8.4.2 Model Example 137
8.4.3 Test your Knowledge 138
8.5 Examples of Two-Factor Models from Computational Finance 139
8.5.1 Multi-Asset Options 139
8.5.2 Stochastic Dividend PDE 140
8.6 Summary and Conclusions 141
Chapter 9 : Transforming Partial Differential Equations to a Bounded Domain 143
9.1 Introduction and Objectives 143
9.2 The Domain in Which a PDE Is Defined: Preamble 143
9.2.1 Background and Specific Mappings 144
9.2.2 Initial Examples 146
9.3 Other Examples 147
9.4 Hotspots 148
9.5 What Happened to Domain Truncation? 148
9.6 Another Way to Remove Mixed Derivative Terms 149
9.7 Summary and Conclusions 151
Chapter 10 : Boundary Value Problems for Elliptic and Parabolic Partial Differential Equations 153
10.1 Introduction and Objectives 153
10.2 Notation and Prerequisites 154
10.3 The Laplace Equation 154
10.3.1 Harmonic Functions and the Cauchy–Riemann Equations 154
10.4 Properties of The Laplace Equation 156
10.4.1 Maximum-Minimum Principle for Laplace’s Equation 158
10.5 Some Elliptic Boundary Value Problems 159
10.5.1 Some Motivating Examples 159
10.6 Extended Maximum-Minimum Principles 159
10.6.1 An Example 161
10.7 Summary and Conclusions 162
Chapter 11 : Fichera Theory, Energy Inequalities and Integral Relations 163
11.1 Introduction and Objectives 163
11.2 Background and Problem Statement 163
11.2.1 The ‘Big Bang’: Cauchy–Euler Equation 163
11.3 Well-Posed Problems and Energy Estimates 165
11.3.1 Time to Reflect: What Have We Achieved and What’s Next? 167
11.4 The Fichera Theory: Overview 168
11.5 The Fichera Theory: The Core Business 168
11.6 The Fichera Theory: Further Examples and Applications 171
11.6.1 Cox–Ingersoll–Ross (CIR) 171
11.6.2 Heston Model Fundamenals 172
11.6.3 Heston Model by Fichera Theory 176
11.6.4 First-Order Hyperbolic PDE in One and Two Space Variables 177
11.7 Some Useful Theorems 178
11.7.1 Divergence (Gauss–Ostrogradsky) Theorem 179
11.7.2 Green’s Theorem/Formula 180
11.7.3 Green’s First and Second Identities 180
11.8 Summary and Conclusions 180
Chapter 12 : An Introduction to Time-Dependent Partial Differential Equations 181
12.1 Introduction and Objectives 181
12.2 Notation and Prerequisites 181
12.3 Preamble: Separation of Variables for the Heat Equation 182
12.4 Well-Posed Problems 184
12.4.1 Examples of an ill-posed Problem 185
12.4.2 The Importance of Proving that Problems Are Well-Posed 187
12.5 Variations on Initial Boundary Value Problem for the Heat Equation 188
12.5.1 Smoothness and Compatibility Conditions 188
12.6 Maximum-Minimum Principles for Parabolic PDEs 189
12.7 Parabolic Equations with Time-Dependent Boundaries 190
12.8 Uniqueness Theorems for Boundary Value Problems in Two Dimensions 192
12.8.1 Laplace Equation 192
12.8.2 Heat Equation 193
12.9 Summary and Conclusions 193
Chapter 13 : Stochastics Representations of PDEs and Applications 195
13.1 Introduction and Objectives 195
13.2 Background, Requirements and Problem Statement 196
13.3 An Overview of Stochastic Differential Equations (SDEs) 196
13.4 An Introduction to One-Dimensional Random Processes 196
13.5 An Introduction to the Numerical Approximation of SDEs 199
13.5.1 Euler–Maruyama Method 199
13.5.2 Milstein Method 201
13.5.3 Predictor-Corrector Method 201
13.5.4 Drift-Adjusted Predictor-Corrector Method 202
13.6 Path Evolution and Monte Carlo Option Pricing 203
13.6.1 Monte Carlo Option Pricing 204
13.6.2 Some C++ Code 205
13.7 Two-Factor Problems 209
13.7.1 Spread Options with Stochastic Volatility 209
13.7.2 Heston Stochastic Volatility Model 211
13.8 The Ito Formula 215
13.9 Stochastics Meets PDEs 215
13.9.1 A Statistics Refresher 215
13.9.2 The Feynman–Kac Formula 217
13.9.3 Kolmogorov Equations 218
13.9.4 Kolmogorov Forward (Fokker–Planck (FPE)) Equation 218
13.9.5 Multi-Dimensional Problems and Boundary Conditions 219
13.9.6 Kolmogorov Backward Equation (KBE) 220
13.10 First Exit-Time Problems 221
13.11 Summary and Conclusions 222
Part C : The Foundations of the Finite Difference Method (FDM)
Chapter 14 : Mathematical and Numerical Foundations of the Finite Difference Method, Part I 225
14.1 Introduction and Objectives 225
14.2 Notation and Prerequisites 226
14.3 What Is the Finite Difference Method, Really? 227
14.4 Fourier Analysis of Linear PDEs 227
14.4.1 Fourier Transform for Advection Equation 229
14.4.2 Fourier Transform for Diffusion Equation 230
14.5 Discrete Fourier Transform 232
14.5.1 Finite and Infinite Dimensional Sequences and Their Norms 232
14.5.2 Discrete Fourier Transform (DFT) 233
14.5.3 Discrete von Neumann Stability Criterion 235
14.5.4 Some More Examples 235
14.6 Theoretical Considerations 237
14.6.1 Consistency 237
14.6.2 Stability 238
14.6.3 Convergence 239
14.7 First-Order Partial Differential Equations 239
14.7.1 Why First-Order Equations are Different: Essential Difficulties 242
14.7.2 A Simple Explicit Scheme 243
14.7.3 Some Common Schemes for Initial Value Problems 245
14.7.4 Some Other Schemes 246
14.7.5 General Linear Problems 248
14.8 Summary and Conclusions 248
Chapter 15: Mathematical and Numerical Foundations of the Finite Difference Method, Part II 249
15.1 Introduction and Objectives 249
15.2 A Short History of Numerical Methods for CDR Equations 250
15.2.1 Temporal and Spatial Stability 251
15.2.2 Motivating Exponential Fitting Methods 253
15.2.3 Eliminating Temporal and Spatial Stability Problems 254
15.3 Exponential Fitting and Time-Dependent Convection-Diffusion 257
15.4 Stability and Convergence Analysis 258
15.5 Special Limiting Cases 260
15.6 Stability for Initial Boundary Value Problems 260
15.6.1 Gerschgorin’s Circle Theorem 261
15.7 Semi-Discretisation for Convection-Diffusion Problems 264
15.7.1 Essentially Positive Matrices 265
15.7.2 Fully Discrete Schemes 267
15.8 Padé Matrix Approximation 269
15.8.1 Padé Matrix Approximations 270
15.9 Time-Dependent Convection-Diffusion Equations 275
15.9.1 Fully Discrete Schemes 275
15.10 Summary and Conclusions 276
Chapter 16 Sensitivity Analysis, Option Greeks and Parameter Optimisation, Part I 277
16.1 Introduction and Objectives 277
16.2 Helicopter View of Sensitivity Analysis 278
16.3 Black–Scholes–Merton Greeks 279
16.3.1 Higher-Order and Mixed Greeks 282
16.4 Divided Differences 282
16.4.1 Approximation to First and Second Derivatives 282
16.4.2 Black–Scholes Numeric Greeks and Divided Differences 285
16.5 Cubic Spline Interpolation 286
16.5.1 Caveat: Cubic Splines with Sparse Input Data 289
16.5.2 Cubic Splines for Option Greeks 290
16.5.3 Boundary Conditions 291
16.6 Some Complex Function Theory 292
16.6.1 Curves and Regions 293
16.6.2 Taylor’s Theorem and Series 294
16.6.3 Laurent’s Theorem and Series 295
16.6.4 Cauchy–Goursat Theorem 296
16.6.5 Cauchy’s Integral Formula 297
16.6.6 Cauchy’s Residue Theorem 298
16.6.7 Gauss’s Mean Value Theorem 299
16.7 The Complex Step Method (CSM) 299
16.7.1 Caveats 302
16.8 Summary and Conclusions 302
Chapter 17 Advanced Topics in Sensitivity Analysis 305
17.1 Introduction and Objectives 305
17.2 Examples of CSE 305
17.2.1 Simple Initial Value Problem 306
17.2.2 Population Dynamics 307
17.2.3 Comparing CSE and Complex Step Method (CSM) 310
17.3 CSE and Black–Scholes PDE 310
17.3.1 Black–Scholes Greeks: Algorithms and Design 311
17.3.2 Some Specific Black–Scholes Greeks 312
17.4 Using Operator Calculus to Compute Greeks 313
17.5 An Introduction to Automatic Differentiation (AD) for the Impatient 314
17.5.1 What Is Automatic Differentiation: The Details 316
17.6 Dual Numbers 317
17.7 Automatic Differentiation in C++ 318
17.8 Summary and Conclusions 319
Part D : Advanced Finite Difference Schemes for Two-Factor Problems
Chapter 18 : Splitting Methods, Part I 323
18.1 Introduction and Objectives 323
18.2 Background and History 324
18.3 Notation, Prerequisites and Model Problems 325
18.4 Motivation: Two-Dimensional Heat Equation 328
18.4.1 Alternating Direction Implicit (ADI) Method 328
18.4.2 Soviet (Operator) Splitting 330
18.4.3 Mixed Derivative and Yanenko Scheme 331
18.5 Other Related Schemes for the Heat Equation 333
18.5.1 D’Yakonov Method 333
18.5.2 Approximate Factorisation of Operators 334
18.5.3 Predictor-Corrector Methods 337
18.5.4 Partial Integro Differential Equations (PIDEs) 338
18.6 Boundary Conditions 339
18.7 Two-Dimensional Convection PDEs 341
18.8 Three-Dimensional Problems 343
18.9 The Hopscotch Method 344
18.10 Software Design and Implementation Guidelines 346
18.11 The Future: Convection-Diffusion Equations 346
18.12 Summary and Conclusions 347
Chapter 19 : The Alternating Direction Explicit (ADE) Method 349
19.1 Introduction and Objectives 349
19.2 Background and Problem Statement 351
19.3 Global Overview and Applicability of ADE 351
19.4 Motivating Examples: One-Dimensional and Two-Dimensional Diffusion Equations 352
19.4.1 Barakat and Clark (B&C) Method 353
19.4.2 Saul’yev Method 354
19.4.3 Larkin Method 355
19.4.4 Two-Dimensional Diffusion Problems 355
19.5 ADE for Convection (Advection) Equation 356
19.6 Convection-Diffusion PDEs 358
19.6.1 Example: Black–Scholes PDE 359
19.6.2 Boundary Conditions 360
19.6.3 Spatial Amplification Errors 361
19.7 Attention Points with ADE 362
The Consequences of Conditional Consistency 362
Call Pay-Off Behaviour at the Far Field 362
19.7.1 General Formulation of the ADE Method 362
19.8 Summary and Conclusions 364
Chapter 20 : The Method of Lines (MOL), Splitting and the Matrix Exponential 365
20.1 Introduction and Objectives 365
20.2 Notation and Prerequisites: The Exponential Function 366
20.2.1 Initial Results 367
20.2.2 The Exponential of a Matrix 367
20.3 The Exponential of a Matrix: Advanced Topics 368
20.3.1 Fundamental Theorem for Linear Systems 368
Proof of Theorem 20.1. 369
20.3.2 An Example 369
20.4 Motivation: One-Dimensional Heat Equation 370
20.5 Semi-Linear Problems 373
20.6 Test Case: Double-Barrier Options 375
20.6.1 PDE Formulation 376
20.6.2 Using Exponential Fitting of Barrier Options 377
20.6.3 Performing MOL with Boost C++ odeint 378
20.6.4 Computing Sensitivities 381
20.6.5 American Options 384
20.7 Summary and Conclusions 384
Chapter 21 : Free and Moving Boundary Value Problems 387
21.1 Introduction and Objectives 387
21.2 Background, Problem Statement and Formulations 388
21.3 Notation and Prerequisites 388
21.4 Some Initial Examples of Free and Moving Boundary Value Problems 389
21.4.1 Single-Phase Melting Ice 389
21.4.2 Oxygen Diffusion 390
21.4.3 American Option Pricing 391
21.4.4 Two-Phase Melting Ice 392
21.5 An Introduction to Parabolic Variational Inequalities 392
21.5.1 Formulation of Problem: Test Case 392
21.5.2 Examples of Initial Boundary Value Problems 395
21.6 An Introduction to Front-Fixing 399
21.6.1 Front-Fixing for the Heat Equation 399
21.7 Python Code Example: ADE for American Option Pricing 400
21.8 Summary and Conclusions 405
Chapter 22 : Splitting Methods, Part II 407
22.1 Introduction and Objectives 407
22.2 Background and Problem Statement: The Essence of Sequential Splitting 408
22.3 Notation and Mathematical Formulation 408
22.3.1 C0 Semigroups 408
22.3.2 Abstract Cauchy Problem 409
22.3.3 Examples 410
22.4 Mathematical Foundations of Splitting Methods 411
22.4.1 Lie (Trotter) Product Formula 411
22.4.2 Splitting Error 411
22.4.3 Component Splitting and Operator Splitting 413
22.4.4 Splitting as a Discretisation Method 413
22.5 Some Popular Splitting Methods 414
22.5.1 First-Order (Lie–Trotter) Splitting 415
22.5.2 Predictor-Corrector Splitting 415
22.5.3 Marchuk’s Two-Cycle (1-2-2-1) Method 416
22.5.4 Strang Splitting 417
22.6 Applications and Relationships to Computational Finance 417
22.7 Software Design and Implementation Guidelines 418
22.8 Experience Report: Comparing ADI and Splitting 419
22.9 Summary and Conclusions 421
Part E : Test Cases in Computational Finance
Chapter 23 : Multi-Asset Options 425
23.1 Introduction and Objectives 425
23.2 Background and Goals 426
23.3 The Bivariate Normal Distribution (BVN) and its Applications 427
23.3.1 Computing BVN by Solving a Hyperbolic PDE 430
23.3.2 Analytical Solutions of Multi-Asset and Basket Options 433
23.4 PDE Models for Multi-Asset Option Problems: Requirements and Design 435
23.4.1 Domain Transformation 435
23.4.2 Numerical Boundary Conditions 435
23.5 An Overview of Finite Difference Schemes for Multi-Asset Option Problems 436
23.5.1 Common Design Principles 436
23.5.2 Detailed Design 438
23.5.3 Testing the Software 440
23.6 American Spread Options 440
23.7 Appendices 442
23.7.1 Traditional Approach to Numerical Boundary Conditions 442
23.7.2 Top-Down Design of Monte Carlo Applications 443
23.8 Summary and Conclusions 444
Chapter 24 : Asian (Average Value) Options 447
24.1 Introduction and Objectives 447
24.2 Background and Problem Statement 448
24.2.1 Challenges 449
24.3 Prototype PDE Model 450
24.3.1 Similarity Reduction 451
24.4 The Many Ways to Handle the Convective Term 452
24.4.1 Method of Lines (MOL) 452
24.4.2 Other Schemes 454
24.4.3 A Stable Monotone Upwind Scheme 455
24.5 ADE for Asian Options 455
24.6 ADI for Asian Options 456
24.6.1 Modern ADI Variations 458
24.7 Summary and Conclusions 459
Chapter 25 : Interest Rate Models 461
25.1 Introduction and Objectives 461
25.2 Main Use Cases 462
25.3 The CIR Model 462
25.3.1 Analytic Solutions 463
25.3.2 Initial Boundary Value Problem 466
25.4 Well-Posedness of the CIRPDE Model 466
25.4.1 Gronwall’s Inequalities 467
25.4.2 Energy Inequalities 468
25.5 Finite Difference Methods for the CIR Model 469
25.5.1 Numerical Boundary Conditions 470
25.6 Heston Model and the Feller Condition 471
25.7 Summary and Conclusion 475
Chapter 26 : Epilogue Models Follow-Up Chapters 1 to 25 477
26.1 Introduction and Objectives 477
26.2 Mixed Derivatives and Monotone Schemes 478
26.2.1 The Maximum Principle and Mixed Derivatives 478
26.2.2 Some Examples 480
26.2.3 Code Sample Method of Lines (MOL) for Two-Factor Hull–White Model 481
26.3 The Complex Step Method (CSM) Revisited 483
26.3.1 Black–Scholes Greeks Using CSM and the Faddeeva Function 483
26.3.2 CSM and Functions of Several Complex Variables 487
26.3.3 C++ Code for Extended CSM 488
26.3.4 CSM for Non-Linear Solvers 492
26.4 Extending the Hull–White: Possible Projects 493
26.5 Summary and Conclusions 495
Bibliography 497
Index 505
