文章

径向基函数法文献总结

总结使用径向基函数求解 PDE 的相关文献。

发表于 更新于
作者 徐瑞龙
23 分钟阅读

径向基函数法文献总结

概述

大部分衍生品定价问题最终归结为求解 PDE 的数值解，最常见的数值方法莫过于 FDM。假设定价问题对应的 PDE 问题如下：

\[\begin{align*} \frac{\partial U(\bar{x},t)}{\partial t} + LU(\bar{x},t) &= 0 ,& \bar{x} \in \Omega \\ BU(\bar{x},t) &= f(\bar{x},t),& \bar{x} \in \partial \Omega \\ U(\bar{x},T) &= g(\bar{x}) \end{align*} \tag{1}\]

$L$ 是关于 $\bar{x}$ 的微分算子，$B$ 表示边界条件对应的微分算子。

FDM 首先在一个规则的求解域 $\Omega$ 内划定网格，并在网格上对 $L$ 和 $B$ 做差分近似。其次在时间 $t$ 维度上做一阶差分近似，以隐式欧拉格式为例，FDM 的整个计算过程被分解为求解一连串的线性方程组。现实中求解域 $\Omega$ 的形状通常是线段、矩形和（超）立方体。

FDM 中线性方程组的尺寸和求解域 $\Omega$ 维度成指数关系，这使得 FDM 较难处理两维以上的 PDE。举个例子，一个表示三标的篮子期权的 BS-PDE，$(x_1,x_2,x_3)$ 三个维度分别划分为 100 份，那么线性方程组中的矩阵的维度将会是 $10^6$，尽管这个矩阵是高度稀疏的，求解起来依旧耗时。

既然作为网格法代表的 FDM 无力解决较高维度的 PDE，一个自然的想法是用无网格法求解 PDE，衍生品定价领域中无网格法的代表就是基于径向基函数（Radial Basis Function）衍生出的一系列数值方法（关于径向基函数更具体的介绍参考文献1）。

将径向基函数用于计算 PDE 数值解的想法最早由 Kansa 在文献2和3中以“全局 RBF 法”的形式引入，经过几十年的发展，全局 RBF 法及其衍生出的一系列数值方法（包括 RBF-PU、RBF-QI、RBF-FD、RBF-DQ）已经在计算流体力学、电磁学、热力学、工业设计和衍生品定价等领域有了成熟的应用。

全局 RBF 法

在问题（1）将 $U(\bar{x}, t)$ 中 $t$ 的动态部分分离出来，而 $\bar{x}$ 的部分用 RBF 拟合近似，这便是全局 RBF 法的基本思想。

在求解域 $\Omega$ 中选定一组支点 $x_i(i = 1,\dots,N)$，将 $U$ 表示为

\[U(\bar{x},t) = \sum_{i=1}^N \alpha_i(t) \phi(\parallel \bar{x} - x_i \parallel)\]

其中 $\phi(r)$ 就是径向基函数，$\parallel \parallel$ 表示空间向量的范数，于是问题（1）表示为

\[\sum_{i=1}^N \frac{d \alpha_i(t)}{dt} \phi(\parallel \bar{x} - x_i \parallel) + \sum_{i=1}^N \frac{d \alpha_i(t)}{dt} L \phi(\parallel \bar{x} - x_i \parallel) = 0 \tag{2}\]

将 $x_i(i = 1,\dots,N)$ 代入到等式（2）中得到

\[\Phi \frac{d\alpha(t)}{dt} + L_{\Phi} \alpha(t)=0\]

其中 $\alpha(t)=[\alpha_1(t),\dots,\alpha_N(t)]^T$ ，$\Phi$ 和 $L_{\Phi}$ 都是矩阵，$\Phi(i,j) = \phi(\parallel x_i - x_j \parallel)$，$L_{\Phi}(i,j) = L\phi(\parallel \bar{x} - x_i \parallel)\mid_{\bar{x}=x_j}$。如此一来求解 PDE 的问题便转化成了求解一个 N 维 ODE 问题，这便是全局 RBF 法的基本思路。

文献4最早将全局 RBF 法引入到单标的欧式和美式期权的求解中，文章总结出应用 RBF 的一般流程；文献5将全局 RBF 法应用于双标的欧式和美式期权，并讨论了边界条件和支点布局对结果的影响；文献6对全局 RBF 法做了误差分析；文献7在用全局 RBF 法计算美式期权时采用了“惩罚法”技术，将自由边界问题转化为非线性 PDE，发挥了 RBF 处理非线性 PDE 的优势；文献8提出了处理不光滑初始条件的特殊算法，即一个计算矩阵指数的简单快速的方法；文献9将全局 RBF 法与广义傅里叶变换结合以提高计算速度；文献10讨论了全局 RBF 法用于多标的欧式期权定价时，边界条件、支点的分布和形状参数对定价精度的影响；文献11和文献12将全局 RBF 法用于跳扩散模型的求解；文献13全局 RBF 法与算子分离结合求解多维 PDE；文献14总结了全局 RBF 在期权定价中的应用，并和 FDM \ FEM 比较。

总结文献可以发现全局 RBF 法相较于 FDM 有以下优点：

  • 维度无关，全局 RBF 法的计算量由 $x_i(i = 1,\dots,N)$ 的数量决定，不依赖于问题的维度；
  • 对求解域 $\Omega$ 的形状没有严格要求，FDM 通常要求求解域是一个矩形或立方体，事实上应用 RBF 时，不少文献的求解域是一个三角形或四面体（例如文献10）；
  • 收敛迅速，精度高（文献6和文献10）。

全局 RBF 法也有一些缺点：

  • 矩阵 $\Phi$ 和 $L_{\Phi}$ 都是稠密矩阵，导致计算效率较低；
  • 大部分基函数的形状依赖于事先选定的“形状参数”，形状参数的选择会显著影响结果的精度，但最优形状参数的选择并没有固定方法；
  • 研究表明基函数形状趋于“扁平”时（即形状参数趋于 0）可以提高结果的精度，但也会导致矩阵 $\Phi$ 趋于病态（条件数巨大），致使求解线性代数问题的稳定性下降。

处理病态矩阵

为处理病态矩阵，需要研究矩阵 $\Phi$ 在形状参数趋于 0 时的渐进行为，并作出特殊处理。

文献15第一个细致的研究了这个问题，提出用 提出 Contour-Pade 算法解决形状函数趋于 0 时矩阵病态的问题；文献16提出了 RBF-QR 算法专门用于球面上的全局 RBF 法；文献17又将 RBF-QR 算法推广到一维和三维；文献18提出 RBF-GA 算法，作为 RBF-QR 的推广，但仅限于高斯基函数；文献19提出 RBF-RA 算法，推广了 RBF-QR 和 RBF-GA，可以适应多种类型的基函数。

稀疏化策略

全局 RBF 法的一项重要发展是局部化。通过局部化，矩阵 $\Phi$ 和 $L_{\Phi}$ 变为稀疏矩阵（带状矩阵），一方面提高了代数计算的效率，另一方面较少了矩阵的病态。

RBF 法的稀疏化策略有以下几种：

  • 借助单位分解法（Partition of Unity Method），仅通过局部的支点近似 PDE，称为 RBF-PU；
  • 借助拟插值（Quasi Interpolation），通过舍弃接近 0 的数直接稀疏化矩阵 $\Phi$ 和 $L_{\Phi}$，称为 RBF-QI。

RBF-PU

在 RBF-PU 法中，除了原有的密集支点 $x_i(i = 1,\dots,N)$ 外，还规定了一组稀疏的支点 $y_j(j = 1,\dots,M)$ 以及对应的半径 $R$。若 $x_i$ 落在了 $y_j$ 划定的圆或球内部，划定范围内部的支点会用来近似 PDE，范围外的支点不起作用，这就是 RBF-PU 法的基本思想。

文献20、文献21和文献22介绍了如何将 RBF-PU 用于多标的的欧式和美式期权定价，其中美式采用了“惩罚法”技术和算子分离技术；文献23将 RBF-PU 用于跳扩散模型以及局部波动率模型；文献24将 RBF-PU 用于随机波动率下的美式期权定价；文献25讨论了 RBF-PU 在复杂定价模型中的应用（包括 Quadratic SLV、SABR、Heston-Hull-White、Heston-Cox-Ingersoll-Ross 模型）；文献26和文献27分别提出并推广了 D-RBF-PU 法，以提高 RBF-PU 的计算效率。

RBF-PU 对矩阵的稀疏化效果可以参考文献20的图 5、文献22的图 1、文献24的图 4。

RBF-QI

拟插值（Quasi-Interpolation）是一类基于 RBF 的特殊插值方法，问题（1）中将 $U(\bar{x},t)$ 用拟插值近似

\[U(\bar{x}, t) = \sum_{i=1}^N \alpha_i(t) \Phi_i(x)\]

其中 $\Phi_i(x)$ 是基函数 $\phi$ 的线性组合，利用 $\Phi_i(x)$ 会衰减至 0 的特性，通过舍弃接近 0 的参数直接稀疏化矩阵 $\Phi$ 和 $L_{\Phi}$。

文献28首次使用拟插值技术求解单标的欧式和美式期权；文献29和文献30将 RBF-QI 法扩展到多标的期权上。

RBF-FD

全局 RBF 法的另一项重要发展是 RBF-FD 法。回想 FDM，对于求解域 $\Omega$ 中的一个特定支点 $x_i$，存在若干围绕 $x_i$ 的支点 $x_j^i$（成为 stencil），FDM 的一个基本理念是用 $U(x_j^i,t)$ 的线性组合来近似 $LU(x_i,t)$。将 RBF 的无网格拟合能力与 FDM 格式结合起来，令

\[LU(x_i,t) = \sum_{j=1}^N w_j U(\parallel x_j^i - x_i \parallel)\]

为得到 $w$，可以要求临近支点 $x_j^i$ 代入 $x$ 后均满足下面的等式

\[L \phi(x,t) = \sum_{j=1}^N w_j^i \phi(\parallel x - x_j^i \parallel)\]

最终，问题（1）将得到类似 FDM 形式的离散近似，

\[\frac{\partial U(\bar{x},t)}{\partial t} = W U(\bar{x},t)\]

和 FDM 的情况类似，$W$ 将会是一个带状矩阵，这就是 RBF-FD 的基本想法。

文献31最早提出了 RBF-FD 的概念；文献32分析了 RBF-FD 的收敛性；文献33和文献34用 RBF-FD 求解跳扩散模型；文献35总结了全局 RBF 和 RBF-FD 在求解 PDE 中的应用；文献25讨论了 RBF-FD 在复杂定价模型中的应用；文献36提出重合 RBF-FD 的概念，改进了传统的 RBF-FD，大幅提高速度和准确性。文献37在 RBF-FD 法中添加 Polyharmonic Splines（PHS）以提高近似的精度，并讨论了支点的分布问题；RBF-FD 结合 PHS 更细致的内容参考文献38、文献39和文献40；文献41和文献42 RBF-FD 法配合算子分离技术分别计算美式期权和机制转换跳扩散模型；文献43用 RBF-FD 解随机利率随机波动率的外汇期权（产生一个 4D-PDE），为提高计算精度采用了非均匀布点，解 ODE 的时候用了 Krylov 法计算矩阵的指数；文献44将 RBF-FD 用于双标的期权，并讨论了平滑初始状态的方法、非均匀布点、stencil 大小的选择；文献45和文献46分别用 RBF-FD 解 Heston-Hull-White 模型和 Hexton-CIR 模型；文献47和文献48总结了 RBF-FD。

目前，RBF-FD 可能是径向基函数法家族中使用最广泛、最成功的一个。

RBF-DQ

正如 RBF 与 FDM 结合产生了 RBF-FD 法，RBF 与 Differential Quadrature 的结合产生了 RBF-DQ 法。和 RBF-FD 类似，RBF-DQ 中 $U$ 的一二阶导数值被要求用 $U$ 在支点值的线性组合表示，

\[\frac{\partial U(\bar{x},t)}{\partial x_i} = \sum_{j=1}^N \alpha_j^i U(x_j,t)\\ \frac{\partial^2 U(\bar{x},t)}{\partial x_i^2} = \sum_{j=1}^N \beta_j^i U(x_j,t)\]

为得到 $\alpha_j^i$ 和 $\beta_j^i$，将 $U$ 替换成基函数 $\phi$，并遍历所有支点可以解出 $\alpha$ 和 $\beta$ 组成的矩阵。

文献49提出 RBF-DQ 法；文献50用 RBF-DQ 求解跳扩散模型；传统的 RBF-DQ 法无法处理混合导数，文献51改进了 RBF-DQ 法，以处理混合导数项并提高了计算速度；文献52主张通过对坐标线性变化以消除 PDE 中的混合导数。

RBF-DQ 也可以通过局部化提升效率和稳定性，文献53、54、55和56分别介绍了 RBF-DQ 的局部化。文献57将局部 RBF-DQ 用于多标的期权定价。

形状参数的选择

前面提到形状参数的选择对结果的精度有显著影响，但是最优形状参数的选择并没有确定性的方法，通常是基于实验和统计的方法的到特定 PDE 问题对应的最优形状参数。

文献58主张用统计学习中的技术 Leave-One-Out Cross Validation（LOOCV）选择最优形状参数。

支点布局和 Stencil 的选择

对于 FDM 来说，对求解域划分网格非常简单，难点在于在网格上构造 PDE 算子的离散近似。而 RBF 法则相反，构造 PDE 算子的离散近似不难，难点反而在于生成合适的支点布局，现实中生成支点是一个重要但常被忽略的问题。直接沿用 FDM 的网格划分是最容易实现的布局方法，但通常不能达到很好的收敛性；采用伪随机数或拟随机数生成的支点无法避免支点出现局部的聚集（使用伪随机数时情况更严重），当支点距离过近可能会使矩阵的条件数增大，带来意外的不稳定性；生成非均匀的支点布局本身就是一个有挑战性的问题。

文献59最早关注了这个问题，介绍了 2D 平面上支点布局的一般方法（即 Fornberg-Flyer 法）；文献60介绍了 2D 平面和 3D 曲面上支点布局的一般方法（即 Shankar-Kirby-Fogelson 法），推广了 Fornberg-Flyer 法；文献61改进了 Fornberg-Flyer 法的实现，提高生成速度，并适用于高维求解域，另外提出了基于 Poisson Disk Sampling 的布局生成法；文献62推广了 Fornberg-Flyer 法和 Shankar-Kirby-Fogelson 法，可用于更高维度的解域。上述提到的生成法大多支持生成非均匀的支点布局。

对于 RBF-FD 而言，除了支点的生成问题，stencil 的选择也很重要。文献63、文献64和文献65分别研究了这个问题。

其他

  • 开源项目——RBF，用 Python 实现了 RBF 插值、RBF-FD 求解 PDE 等功能。
  • 开源项目——Medusa，用 C++ 实现了 RBF-FD 以及二维、三维空间中支点布局的算法，应用于工业设计。
  • 学术团体——Uppsala 大学的 RBF 组。

参考文献

  1. Recent Advances in Radial Basis Function Collocation Methods ↩︎

  2. Multiquadrics - a Scattered Data Approximation Scheme with Applications to Computational Fluid Dynamics - I ↩︎

  3. Multiquadrics - a Scattered Data Approximation Scheme with Applications to Computational Fluid Dynamics - II ↩︎

  4. A Radial Basis Function Method For Solving Options Pricing Model ↩︎

  5. On the Use of Boundary Conditions for Variational Formulations Arising in Financial Mathematics ↩︎

  6. Convergence Error Estimate in Solving Free Boundary Diffusion Problem by Radial Basis Functions Method ↩︎ ↩︎2

  7. Using Meshfree Approximation for Multi‐Asset American Options ↩︎

  8. A Parallel Time Stepping Approach Using Meshfree Approximations for Pricing Options with Non-Smooth Payoffs ↩︎

  9. Multi-Dimensional Option Pricing Using Radial Basis Functions and the Generalized Fourier Transform ↩︎

  10. Improved Radial Basis Function Methods for Multi-Dimensional Option Pricing ↩︎ ↩︎2 ↩︎3

  11. Meshfree Approximation for Multi-Asset Options ↩︎

  12. Radial Basis Functions with Application to Finance: American Put Option Under Jump Diffusion ↩︎

  13. Pricing European and American Options with Two Stochastic Factors: A Highly Efficient Radial Basis Function Approach ↩︎

  14. Option Pricing Via Radial Basis Functions: Performance Comparison with Traditional Numerical Integration Scheme and Parameters Choice for a Reliable Pricing ↩︎

  15. Stable Computation of Multiquadric Interpolants for All Values of the Shape Parameter ↩︎

  16. A Stable Algorithm for Flat Radial Basis Functions on a Sphere ↩︎

  17. Stable Computations with Gaussian Radial Basis Functions ↩︎

  18. Stable Calculation of Gaussian-Based RBF-FD Stencils ↩︎

  19. Stable Computations with Flat Radial Basis Functions Using Vector-Valued Rational Approximations ↩︎

  20. A Radial Basis Function Partition of Unity Collocation Method for Convection-Diffusion Equations Arising in Financial Applications ↩︎ ↩︎2

  21. Radial Basis Function Partition of Unity Methods for Pricing Vanilla Basket Options ↩︎

  22. Radial Basis Function Partition of Unity Operator Splitting Method for Pricing Multi-Asset American Options ↩︎ ↩︎2

  23. RBF-PU Method for Pricing Options Under the Jump–Diffusion Model with Local Volatility ↩︎

  24. Radial Basis Functions with Partition of Unity Method for American Options with Stochastic Volatility ↩︎ ↩︎2

  25. Pricing Derivatives Under Multiple Stochastic Factors by Localized Radial Basis Function Methods ↩︎ ↩︎2

  26. The Direct Radial Basis Function Partition of Unity (D-RBF-PU) Method for Solving PDEs ↩︎

  27. A Compact Radial Basis Function Partition of Unity Method ↩︎

  28. A Quasi-Radial Basis Functions Method for American Options Pricing ↩︎

  29. Multivariate Option Pricing Using Quasi-interpolation Based on Radial Basis Functions ↩︎

  30. A Computationally Efficient Numerical Approach for Multi-Asset Option Pricing ↩︎

  31. On Using Radial Basis Functions in a Finite Difference Mode with Applications to Elasticity Problems ↩︎

  32. RBF-FD Formulas and Convergence Properties ↩︎

  33. An Efficient Numerical Method for Pricing Option Under Jump Diffusion Model ↩︎

  34. A Radial Basis Function Based Implicit-Explicit Method for Option Pricing Under Jump-Diffusion Models ↩︎

  35. Solving PDEs with Radial Basis Functions ↩︎

  36. The Overlapped Radial Basis Function-Finite Difference (rbf-Fd) Method: A Generalization of RBF-FD ↩︎

  37. Pricing Financial Derivatives Using Radial Basis Function Generated Finite Differences with Polyharmonic Splines on Smoothly Varying Node Layouts ↩︎

  38. On the Role of Polynomials in RBF-FD Approximations: I. Interpolation and Accuracy ↩︎

  39. On the Role of Polynomials in RBF-FD Approximations: Ii. Numerical Solution of Elliptic Pdes ↩︎

  40. On the Role of Polynomials in RBF-FD Approximations: Iii. Behavior Near Domain Boundaries ↩︎

  41. Radial-Basis-Function-Based Finite Difference Operator Splitting Method for Pricing American Options ↩︎

  42. A RBF Based Finite Difference Method for Option Pricing Under Regime-Switching Jump-Diffusion Model ↩︎

  43. Pricing Foreign Exchange Options Under Stochastic Volatility and Interest Rates Using an RBF-FD Method ↩︎

  44. A High Order Method for Pricing of Financial Derivatives Using Radial Basis Function Generated Finite Differences ↩︎

  45. An Efficient Localized RBF-FD Method to Simulate the Heston–Hull–White PDE in Finance ↩︎

  46. Numerical Investigation of the Three-Dimensional HCIR Partial Differential Equation Utilizing a New Localized RBF-FD Method ↩︎

  47. Radial Basis Function Generated Finite Difference Methods for Pricing of Financial Derivatives ↩︎

  48. Radial Basis Function Generated Finite Differences for Option Pricing Problems ↩︎

  49. Solution of Partial Differential Equations by a Global Radial Basis Function-Based Differential Quadrature Method ↩︎

  50. A New Radial Basis Functions Method for Pricing American Options Under Merton’s Jump-Diffusion Model ↩︎

  51. A Numerical Method to Approximate Multi-Asset Option Pricing Under Exponential Lévy Model ↩︎

  52. A Numerical Study of RBF-DQ Method for Multi-Asset Option Pricing Problems ↩︎

  53. Numerical Solution of the System of Second-Order Boundary Value Problems Using the Local Radial Basis Functions Based Differential Quadrature Collocation Method ↩︎

  54. Local Rbf-Based Differential Quadrature Collocation Method for the Boundary Layer Problems ↩︎

  55. Numerical Simulation of Partial Differential Equations Via Local Meshless Method ↩︎

  56. Numerical Simulation of PDEs by Local Meshless Differential Quadrature Collocation Method ↩︎

  57. Local RBF Method for Multi-Dimensional Partial Differential Equations ↩︎

  58. On Choosing Optimal Shape Parameters for RBF Approximation ↩︎

  59. Fast Generation of 2-D Node Distributions for Mesh-Free Pde Discretizations ↩︎

  60. Robust Node Generation for Mesh-free Discretizations on Irregular Domains and Surfaces ↩︎

  61. Fast Generation of Variable Density Node Distributions for Mesh-Free Methods ↩︎

  62. On Generation of Node Distributions for Meshless PDE Discretizations ↩︎

  63. Adaptive RBF-FD Method for Elliptic Problems with Point Singularities in 2D ↩︎

  64. Guidelines for RBF-FD Discretization: Numerical Experiments on the Interplay of a Multitude of Parameter Choices ↩︎

  65. Improved Stencil Selection for Meshless Finite Difference Methods in 3d ↩︎

文献总结
本文由作者按照 CC BY 4.0 进行授权