Efficient numerical methods for pricing American options under stochastic volatility

Five numerical methods for pricing American put options under Heston's stochastic volatility model are described and compared. The option prices are obtained as the solution of a two‐dimensional parabolic partial differential inequality. A finite difference discretization on nonuniform grids leading to linear complementarity problems with M‐matrices is proposed. The projected SOR, a projected multigrid method, an operator splitting method, a penalty method, and a componentwise splitting method are considered. The last one is a direct method while all other methods are iterative. The resulting systems of linear equations in the operator splitting method and in the penalty method are solved using a multigrid method. The projected multigrid method and the componentwise splitting method lead to a sequence of linear complementarity problems with one‐dimensional differential operators that are solved using the Brennan and Schwartz algorithm. The numerical experiments compare the accuracy and speed of the considered methods. The accuracies of all methods appear to be similar. Thus, the additional approximations made in the operator splitting method, in the penalty method, and in the componentwise splitting method do not increase the error essentially. The componentwise splitting method is the fastest one. All multigrid‐based methods have similar rapid grid independent convergence rates. They are about two or three times slower that the componentwise splitting method. On the coarsest grid the speed of the projected SOR is comparable with the multigrid methods while on finer grids it is several times slower. ©John Wiley & Sons, Inc. © 2007 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2007     

速度追踪问题中鞍点系统的新分裂迭代

 有限元离散一类速度追踪问题后得到具有鞍点结构的线性系统,针对该鞍点系统,本文提出了一种新的分裂迭代技术.证明了新的分裂迭代方法的无条件收敛性,详细分析了新的分裂预条件子对应的预处理矩阵的谱性质.数值结果验证了对于大范围的网格参数和正则参数,新的分裂预条件子在求解有限元离散速度追踪问题得到的鞍点系统时的可行性和有效性.     

The splitting finite-difference time-domain methods for Maxwell's equations in two dimensions

In this paper, we consider splitting methods for Maxwell's equations in two dimensions. A new kind of splitting finite-difference time-domain methods on a staggered grid is developed. The corresponding schemes consist of only two stages for each time step, which are very simple in computation. The rigorous analysis of the schemes is given. By the energy method, it is proved that the scheme is unconditionally stable and convergent for the problems with perfectly conducting boundary conditions. Numerical dispersion analysis and numerical experiments are presented to show the efficient performance of the proposed methods. Furthermore, the methods are also applied to solve a scattering problem successfully.     

Time stepping for vectorial operator splitting

We present a fully implicit finite difference method for the unsteady incompressible Navier-Stokes equations. It is based on the one-step θ-method for discretization in time and a special coordinate splitting (called vectorial operator splitting) for efficiently solving the nonlinear stationary problems for the solution at each new time level. The resulting system is solved in a fully coupled approach that does not require a boundary condition for the pressure. A staggered arrangement of velocity and pressure on a structured Cartesian grid combined with the fully implicit treatment of the boundary conditions helps us to preserve the properties of the differential operators and thus leads to excellent stability of the overall algorithm. The convergence properties of the method are confirmed via numerical experiments.     

On exact dimensional splitting for a multidimensional scalar quasilinear hyperbolic conservation law

A dimensional splitting scheme is applied to a multidimensional scalar homogeneous quasilinear hyperbolic equation (conservation law). It is proved that the splitting error is zero. The proof is presented for the above partial differential equation in an arbitrary number of dimensions. A numerical example is given that illustrates the proved accuracy of the splitting scheme. In the example, the grid convergence of split (locally one-dimensional) compact and bicompact difference schemes and unsplit bicompact schemes combined with high-order accurate time-stepping schemes (namely, Runge–Kutta methods of order 3, 4, and 5) is analyzed. The errors of the numerical solutions produced by these schemes are compared. It is shown that the orders of convergence of the split schemes remain high, which agrees with the conclusion that the splitting error is zero.     

Application of operator splitting in the solution of reaction-diffusion equations

Operator splitting is a widely used method in the numerical solution of partial differential equations. A comparison of the different splitting techniques in the solution of 1 and 2 dimensional reaction-diffusion equations is made. The process of the solution is a composition of certain splitting procedure and a given numerical method. We study the interaction between the different splitting procedures and different numerical schemes. The order of the convergence of this composed method is calculated. The error of the approximate solution is characterized as a funct ion of the applied splitting and numerical scheme. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Nonstandard methods for the convective transport equation with nonlinear reactions

A new nonstandard Lagrangian method is constructed for the one-dimensional, transient convective transport equation with nonlinear reaction terms. An “exact” time-stepping scheme is developed with zero local truncation error with respect to time. The scheme is based on nonlocal treatment of nonlinear reactions, and when applied at each spatial grid point gives the new fully discrete numerical method. This approach leads to solutions free from the numerical instabilities that arise because of incorrect modeling of derivatives and nonlinear reaction terms. Algorithms are developed that preserve the properties of the numerical solution in the case of variable velocity fields by using nonuniform spatial grids. Effects of different interpolation techniques are examined and numerical results are presented to demonstrate the performance of the proposed new method. © 1998 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 14: 467–485, 1998     

Front tracking and two-dimensional Riemann problems

A substantial improvement in resolution has been achieved for the computation of jump discontinuities in gas dynamics using the method of front tracking. The essential feature of this method is that a lower dimensional grid is fitted to and follows the discontinuous waves. At the intersection points of these discontinuities, two-dimensional Riemann problems occur. In this paper we study such two-dimensional Riemann problems from both numerical and theoretical points of view. Specifically included is a numerical solution for the Mach reflection, a general classification scheme for two-dimensional elementary waves, and a discussion of problems and conjectures in this area.     

Numerical integration using sparse grids

We present new and review existing algorithms for the numerical integration of multivariate functions defined over d-dimensional cubes using several variants of the sparse grid method first introduced by Smolyak [49]. In this approach, multivariate quadrature formulas are constructed using combinations of tensor products of suitable one-dimensional formulas. The computing cost is almost independent of the dimension of the problem if the function under consideration has bounded mixed derivatives. We suggest the usage of extended Gauss (Patterson) quadrature formulas as the one‐dimensional basis of the construction and show their superiority in comparison to previously used sparse grid approaches based on the trapezoidal, Clenshaw–Curtis and Gauss rules in several numerical experiments and applications. For the computation of path integrals further improvements can be obtained by combining generalized Smolyak quadrature with the Brownian bridge construction. This revised version was published online in August 2006 with corrections to the Cover Date.     

A new two grid variational multiscale method for steady‐state natural convection problem

A two‐grid variational multiscale method based on two local Gauss integrations for solving the stationary natural convection problem is presented in this article. A significant feature of the method is that we solve the natural convection problem on a coarse mesh using finite element variational multiscale method based on two local Gauss integrations firstly, and then find a fine grid solution by solving a linearized problem on a fine grid. In the computation, we introduce two local Gauss integrations as a stabilizing term to replace the projection operator without adding other variables. The stability estimates and convergence analysis of the new method are derived. Ample numerical experiments are performed to validate the theoretical predictions and demonstrate the efficiency of the new method. Copyright © 2016 John Wiley & Sons, Ltd.     

The segment projection method for interface tracking

There has recently been important progress in the development of front tracking and level set methods for the numerical simulation of moving interfaces. The segment projection method is a new technique for computational geometry. It can be seen as a compromise between front tracking and level set methods. It is based on the regular mathematical representation of a manifold as an atlas of charts. Each chart or segment is evolved independently by a partial differential equation that is discretized on an Eulerian grid. The connectivity of the segments is handled by an appropriate data structure and by numerical interpolation. The method is presented and its properties are analyzed. Applications to multiphase flow, epitaxial growth, and high‐frequency wave propagation are given. © 2002 Wiley Periodicals, Inc.     

Global energy‐tracking identities and global energy‐tracking splitting FDTD schemes for the Drude Models of Maxwell's equations in three‐dimensional metamaterials

In this article, we study the Drude models of Maxwell's equations in three‐dimensional metamaterials. We derive new global energy‐tracking identities for the three dimensional electromagnetic problems in the Drude metamaterials, which describe the invariance of global electromagnetic energy in variation forms. We propose the time second‐order global energy‐tracking splitting FDTD schemes for the Drude model in three dimensions. The significant feature is that the developed schemes are global energy‐preserving, unconditionally stable, second‐order accurate both in time and space, and computationally efficient. We rigorously prove that the new schemes satisfy these energy‐tracking identities in the discrete form and the discrete variation form and are unconditionally stable. We prove that the schemes in metamaterials are second order both in time and space. The superconvergence of the schemes in the discrete H¹ norm is further obtained to be second order both in time and space. Their approximations of divergence‐free are also analyzed to have second‐order accuracy both in time and space. Numerical experiments confirm our theoretical analysis results. © 2017 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 33: 763–785, 2017     

A first-second order splitting method for a third-order partial differential equation

A splitting of a third order partial differential equation into a first-order and a second-order one is proposed as the basis for a mixed finite element method to approximate its solution. A time-continuous numerical method is described and error estimates for its solution are demonstrated. Finally, a full discretization is described based on backward Euler finite differences in time, and error estimates for the resulting approximation are established. © 1998 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 14: 89–96, 1998     

A Dimensional Splitting Method for Quasilinear Hyperbolic Equations with Variable Coefficients

A numerical method is presented for the variable coefficient, nonlinear hyperbolic equation u _t + _i=1 ^d V _i(x, t)f _i(u) _{x i} = 0 in arbitrary space dimension for bounded velocities that are Lipschitz continuous in the x variable. The method is based on dimensional splitting and uses a recent front tracking method to solve the resulting one-dimensional non-conservative equations. The method is unconditionally stable, and it produces a subsequence that converges to the entropy solution as the discretization of time and space tends to zero. Four numerical examples are presented; numerical error mechanisms are illustrated for two linear equations, the efficiency of the method compared with a high-resolution TVD method is discussed for a nonlinear problem, and finally, applications to reservoir simulation are presented.     

A note on Hermitian splitting induced relaxation methods for convection-diffusion equations

The solution of the linear system Ax = b by iterative methods requires a splitting of the coefficient matrix in the form A = M − N where M is usually chosen to be a diagonal or a triangular matrix. In this article we study relaxation methods induced by the Hermitian and skew-Hermitian splittings for the solution of the linear system arising from a compact fourth order approximation to the one dimensional convection-diffusion equation and compare the convergence rates of these relaxation methods to that of the widely used successive overrelaxation (SOR) method. Optimal convergence parameters are derived for each method and numerical experiments are given to supplement the theoretical estimates. For certain values of the diffusion parameter, a relaxation method based on the Hermitian splitting converges faster than SOR. For two-dimensional problems a block form of the iterative algorithm is presented. © 1998 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 14: 581–591, 1998     

Unconditionally Stable Splitting Methods for the Shallow Water Equations

The front-tracking method for hyperbolic conservation laws is combined with operator splitting to study the shallow water equations. Furthermore, the method includes adaptive grid refinement in multidimensions and shock tracking in one dimension. The front-tracking method is unconditionally stable, but for practical computations feasible CFL numbers are moderately above unity (typically between 1 and 5). The method resolves shocks sharply and is highly efficient. The numerical technique is applied to four test cases, the first being an expanding bore with rotational symmetry. The second problem addresses the question of describing the time development of two constant water levels separated by a dam that breaks instantaneously. The third problem compares the front-tracking method with an explicit analytic solution of water waves rotating over a parabolic bottom profile. Finally, we study flow over an obstacle in one dimension.     

Gas-Kinetic BGK Scheme for Three Dimensional Magnetohydrodynamics

<正>The gas-kinetic theory based flux splitting method has been successfully proposed for solving one-and two-dimensional ideal magnetohydrodynamics by Xu et al. [J.Comput.Phys.,1999;2000],respectively.This paper extends the kinetic method to solve three-dimensional ideal magnetohydrodynamics equations,where an adaptive parameter 17 is used to control the numerical dissipation in the flux splitting method. Several numerical examples are given to demonstrate that the proposed method can achieve high numerical accuracy and resolve strong discontinuous waves in three dimensional ideal MHD problems.     

数值解多维问题的外推与组合技术的若干新进展

本文综述近年来数值解多维问题的外推与组合技术的新进展，内容包括分裂外推及其在偏微分方程、多堆积分方程、多维数值积分中的应用；Ｃ．Ｚｅｎｇｅｒ的稀疏网格法与组合求解技术；以及解边界积分方程的组合方法，本文通过算例表明这些方法是非常有效的，是解多维问题的钥匙。     

Two‐grid method for two‐dimensional nonlinear Schrödinger equation by finite element method

A conservative two‐grid finite element scheme is presented for the two‐dimensional nonlinear Schrödinger equation. One Newton iteration is applied on the fine grid to linearize the fully discrete problem using the coarse‐grid solution as the initial guess. Moreover, error estimates are conducted for the two‐grid method. It is shown that the coarse space can be extremely coarse, with no loss in the order of accuracy, and still achieve the asymptotically optimal approximation as long as the mesh sizes satisfy in the two‐grid method. The numerical results show that this method is very effective.