首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 31 毫秒
1.
In this paper we present a novel numerical method for a degeneratepartial differential equation, called the Black–Scholesequation, governing option pricing. The method is based on afitted finite volume spatial discretization and an implicittime stepping technique. To derive the error bounds for thespatial discretization of the method, we formulate it as a Petrov–Galerkinfinite element method with each basis function of the trialspace being determined by a set of two-point boundary valueproblems defined on element edges. Stability of the discretizationis proved and an error bound for the spatial discretizationis established. It is also shown that the system matrix of thediscretization is an M-matrix so that the discrete maximum principleis satisfied by the discretization. Numerical experiments areperformed to demonstrate the effectiveness of the method. Received 6 January 2003. Revised 15 January 2004.  相似文献   

2.
A cascadic multigrid algorithm for semilinear elliptic problems   总被引:12,自引:0,他引:12  
Summary. We propose a cascadic multigrid algorithm for a semilinear elliptic problem. The nonlinear equations arising from linear finite element discretizations are solved by Newton's method. Given an approximate solution on the coarsest grid on each finer grid we perform exactly one Newton step taking the approximate solution from the previous grid as initial guess. The Newton systems are solved iteratively by an appropriate smoothing method. We prove that the algorithm yields an approximate solution within the discretization error on the finest grid provided that the start approximation is sufficiently accurate and that the initial grid size is sufficiently small. Moreover, we show that the method has multigrid complexity. Received February 12, 1998 / Revised version received July 22, 1999 / Published online June 8, 2000  相似文献   

3.
We consider a conservative nonlinear multigrid method for the Cahn–Hilliard equation with a variable mobility of a model for phase separation in a binary mixture. The method uses the standard finite difference approximation in spatial discretization and the Crank–Nicholson semi-implicit scheme in temporal discretization. And the resulting discretized equations are solved by an efficient nonlinear multigrid method. The continuous problem has the conservation of mass and the decrease of the total energy. It is proved that these properties hold for the discrete problem. Also, we show the proposed scheme has a second-order convergence in space and time numerically. For numerical experiments, we investigate the effects of a variable mobility.  相似文献   

4.
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  相似文献   

5.
Many problems based on unstructured grids provide a natural multigrid framework due to using an adaptive gridding procedure. When the grids are saved, even starting from just a fine grid problem poses no serious theoretical difficulties in applying multigrid. A more difficult case occurs when a highly unstructured grid problem is to be solved with no hints how the grid was produced. Here, there may be no natural multigrid structure and applying such a solver may be quite difficult to do. Since unstructured grids play a vital role in scientific computing, many modifications have been proposed in order to apply a fast, robust multigrid solver. One suggested solution is to map the unstructured grid onto a structured grid and then apply multigrid to a sequence of structured grids as a preconditioner. In this paper, we derive both general upper and lower bounds on the condition number of this procedure in terms of computable grid parameters. We provide examples to illuminate when this preconditioner is a useful (e. g.,p orh-p formulated finite element problems on semi-structured grids) or should be avoided (e.g., typical computational fluid dynamics (CFD) or boundary layer problems). We show that unless great care is taken, this mapping can lead to a system with a high condition number which eliminates the advantage of the multigrid method. This work was partially supported by ONR Grant # N0014-91-J-1576.  相似文献   

6.
Time discretization of an evolution equation via Laplace transforms   总被引:4,自引:0,他引:4  
Following earlier work by Sheen, Sloan, and Thomée concerningparabolic equations we study the discretization in time of aVolterra type integro-differential equation in which the integraloperator is a convolution of a weakly singular function andan elliptic differential operator in space. The time discretizationis accomplished by using a modified Laplace transform in timeto represent the solution as an integral along a smooth curveextending into the left half of the complex plane, which isthen evaluated by quadrature. This reduces the problem to afinite set of elliptic equations with complex coefficients,which may be solved in parallel. Stability and error boundsof high order are derived for two different choices of the quadraturerule. The method is combined with finite-element discretizationin the spatial variables.  相似文献   

7.
A fully discrete stabilized finite-element method is presentedfor the two-dimensional time-dependent Navier–Stokes problem.The spatial discretization is based on a finite-element spacepair (Xh, Mh) for the approximation of the velocity and thepressure, constructed by using the Q1P0 quadrilateralelement or the P1P0 triangular element; the time discretizationis based on the Euler semi-implicit scheme. It is shown thatthe proposed fully discrete stabilized finite-element methodresults in the optimal order error bounds for the velocity andthe pressure.  相似文献   

8.
In this paper, we present a multigrid V‐cycle preconditioner for the linear system arising from piecewise linear nonconforming Crouzeix–Raviart discretization of second‐order elliptic problems with jump coefficients. The preconditioner uses standard conforming subspaces as coarse spaces. We showed that the convergence rates of the (multiplicative) two‐grid and multigrid V‐cycle algorithms will deteriorate rapidly because of large jumps in coefficient. However, the preconditioned systems have only a fixed number of small eigenvalues depending on the large jump in coefficient, and the effective condition numbers are independent of the coefficient and bounded logarithmically with respect to the mesh size. As a result, the two‐grid or multigrid preconditioned conjugate gradient algorithm converges nearly uniformly. We also comment on some major differences of the convergence theory between the nonconforming case and the standard conforming case. Numerical experiments support the theoretical results. Copyright © 2012 John Wiley & Sons, Ltd.  相似文献   

9.
We present a sixth-order explicit compact finite difference scheme to solve the three-dimensional (3D) convection-diffusion equation. We first use a multiscale multigrid method to solve the linear systems arising from a 19-point fourth-order discretization scheme to compute the fourth-order solutions on both a coarse grid and a fine grid. Then an operator-based interpolation scheme combined with an extrapolation technique is used to approximate the sixth-order accurate solution on the fine grid. Since the multigrid method using a standard point relaxation smoother may fail to achieve the optimal grid-independent convergence rate for solving convection-diffusion equations with a high Reynolds number, we implement the plane relaxation smoother in the multigrid solver to achieve better grid independency. Supporting numerical results are presented to demonstrate the efficiency and accuracy of the sixth-order compact (SOC) scheme, compared with the previously published fourth-order compact (FOC) scheme.  相似文献   

10.
A cascadic multigrid algorithm is substantiated for a grid problem obtained by discretization of a second-order elliptic equation with second-order finite elements on triangles. The efficiency of the algorithm is proved. In particular, it is shown that the number of arithmetic operations required to achieve the order of accuracy of an approximate solution equal to that of the discretization error depends linearly on the number of unknowns. The rate of convergence is found to be higher than one for linear finite elements despite achieving a higher order of accuracy.  相似文献   

11.

We consider a two-stage stochastic variational inequality arising from a general convex two-stage stochastic programming problem, where the random variables have continuous distributions. The equivalence between the two problems is shown under some moderate conditions, and the monotonicity of the two-stage stochastic variational inequality is discussed under additional conditions. We provide a discretization scheme with convergence results and employ the progressive hedging method with double parameterization to solve the discretized stochastic variational inequality. As an application, we show how the water resources management problem under uncertainty can be transformed from a two-stage stochastic programming problem to a two-stage stochastic variational inequality, and how to solve it, using the discretization scheme and the progressive hedging method with double parameterization.

  相似文献   

12.
F. Ben Belgacem The mortar spectral element method is a domain decompositiontechnique that allows for discretizing second- or fourth-orderelliptic equations when set in standard Sobolev spaces. Theaim of this paper is to extend this method to problems formulatedin the space of square-integrable vector fields with square-integrablecurl. We consider the problem of computing the vector potentialassociated with a divergence-free function in 3D and proposea discretization of it. The numerical analysis of the discreteproblem is performed and numerical experiments are presented;they turn out to be in good agreement with the theoretical results.  相似文献   

13.
Coarse grid projection (CGP) methodology is a novel multigrid method for systems involving decoupled nonlinear evolution equations and linear elliptic Poisson equations. The nonlinear equations are solved on a fine grid and the linear equations are solved on a corresponding coarsened grid. Mapping operators execute data transfer between the grids. The CGP framework is constructed upon spatial and temporal discretization schemes. This framework has been established for finite volume/difference discretizations as well as explicit time integration methods. In this article we present for the first time a version of CGP for finite element discretizations, which uses a semi-implicit time integration scheme. The mapping functions correspond to the finite-element shape functions. With the novel data structure introduced, the mapping computational cost becomes insignificant. We apply CGP to pressure-correction schemes used for the incompressible Navier-Stokes flow computations. This version is validated on standard test cases with realistic boundary conditions using unstructured triangular meshes. We also pioneer investigations of the effects of CGP on the accuracy of the pressure field. It is found that although CGP reduces the pressure field accuracy, it preserves the accuracy of the pressure gradient and thus the velocity field, while achieving speedup factors ranging from approximately 2 to 30. The minimum speedup occurs for velocity Dirichlet boundary conditions, while the maximum speedup occurs for open boundary conditions.  相似文献   

14.
In this paper, we employ local Fourier analysis (LFA) to analyze the convergence properties of multigrid methods for higher‐order finite‐element approximations to the Laplacian problem. We find that the classical LFA smoothing factor, where the coarse‐grid correction is assumed to be an ideal operator that annihilates the low‐frequency error components and leaves the high‐frequency components unchanged, fails to accurately predict the observed multigrid performance and, consequently, cannot be a reliable analysis tool to give good performance estimates of the two‐grid convergence factor. While two‐grid LFA still offers a reliable prediction, it leads to more complex symbols that are cumbersome to use to optimize parameters of the relaxation scheme, as is often needed for complex problems. For the purposes of this analytical optimization as well as to have simple predictive analysis, we propose a modification that is “between” two‐grid LFA and smoothing analysis, which yields reasonable predictions to help choose correct damping parameters for relaxation. This exploration may help us better understand multigrid performance for higher‐order finite element discretizations, including for Q2Q1 (Taylor‐Hood) elements for the Stokes equations. Finally, we present two‐grid and multigrid experiments, where the corrected parameter choice is shown to yield significant improvements in the resulting two‐grid and multigrid convergence factors.  相似文献   

15.
The discretization of the double‐layer potential integral equation for the interior Dirichlet–Laplace problem in a domain with smooth boundary results in a linear system that has a bounded condition number. Thus, the number of iterations required for the convergence of a Krylov method is, asymptotically, independent of the discretization size N. Using the fast multipole method to accelerate the matrix–vector products, we obtain an optimal solver. In practice, however, when the geometry is complicated, the number of Krylov iterations can be quite large—to the extend that necessitates the use of preconditioning. We summarize the different methodologies that have appeared in the literature (single‐grid, multigrid, approximate sparse inverses), and we propose a new class of preconditioners based on a fast multipole method‐based spatial decomposition of the double‐layer operator. We present an experimental study in which we compare the different approaches, and we discuss the merits and shortcomings of our approach. Our method can be easily extended to other second‐kind integral equations with non‐oscillatory kernels in two and three dimensions. Copyright © 2014 John Wiley & Sons, Ltd.  相似文献   

16.
We consider the numerical pricing of American options under Heston’s stochastic volatility model. The price is given by a linear complementarity problem with a two-dimensional parabolic partial differential operator. We propose operator splitting methods for performing time stepping after a finite difference space discretization. The idea is to decouple the treatment of the early exercise constraint and the solution of the system of linear equations into separate fractional time steps. With this approach an efficient numerical method can be chosen for solving the system of linear equations in the first fractional step before making a simple update to satisfy the early exercise constraint. Our analysis suggests that the Crank–Nicolson method and the operator splitting method based on it have the same asymptotic order of accuracy. The numerical experiments show that the operator splitting methods have comparable discretization errors. They also demonstrate the efficiency of the operator splitting methods when a multigrid method is used for solving the systems of linear equations.  相似文献   

17.
Algebraic multigrid (AMG) preconditioners are considered for discretized systems of partial differential equations (PDEs) where unknowns associated with different physical quantities are not necessarily colocated at mesh points. Specifically, we investigate a Q 2? Q 1 mixed finite element discretization of the incompressible Navier–Stokes equations where the number of velocity nodes is much greater than the number of pressure nodes. Consequently, some velocity degrees of freedom (DOFs) are defined at spatial locations where there are no corresponding pressure DOFs. Thus, AMG approaches leveraging this colocated structure are not applicable. This paper instead proposes an automatic AMG coarsening that mimics certain pressure/velocity DOF relationships of the Q 2? Q 1 discretization. The main idea is to first automatically define coarse pressures in a somewhat standard AMG fashion and then to carefully (but automatically) choose coarse velocity unknowns so that the spatial location relationship between pressure and velocity DOFs resembles that on the finest grid. To define coefficients within the intergrid transfers, an energy minimization AMG (EMIN‐AMG) is utilized. EMIN‐AMG is not tied to specific coarsening schemes and grid transfer sparsity patterns, and so it is applicable to the proposed coarsening. Numerical results highlighting solver performance are given on Stokes and incompressible Navier–Stokes problems.  相似文献   

18.
Yiqi Qiu We examine the use of nonmatching, overlapping grids for theapproximate solution of time-dependent diffusion problems withNeumann boundary conditions. This problem arises as a modelof the so-called well test analysis of oil and gas reservoirs,which has geometry modelling requirements that make overlappinggrids particularly suitable. We describe the problem and theoverlapping grid approximation, and then carry out a stabilityand convergence analysis in one space dimension (1D). We showthat for suitable schemes, stability is relatively easy to establishin much more general situations. Convergence is less easy togeneralise, but we demonstrate that 2D approximations appearto have the same convergence behaviour as their 1D counterparts.  相似文献   

19.
This paper is on the convergence analysis for two‐grid and multigrid methods for linear systems arising from conforming linear finite element discretization of the second‐order elliptic equations with anisotropic diffusion. The multigrid algorithm with a line smoother is known to behave well when the discretization grid is aligned with the anisotropic direction; however, this is not the case with a nonaligned grid. The analysis in this paper is mainly focused on two‐level algorithms. For aligned grids, a lower bound is given for a pointwise smoother, and this bound shows a deterioration in the convergence rate, whereas for ‘maximally’ nonaligned grids (with no edges in the triangulation parallel to the direction of the anisotropy), the pointwise smoother results in a robust convergence. With a specially designed block smoother, we show that, for both aligned and nonaligned grids, the convergence is uniform with respect to the anisotropy ratio and the mesh size in the energy norm. The analysis is complemented by numerical experiments that confirm the theoretical results. Copyright © 2012 John Wiley & Sons, Ltd.  相似文献   

20.
Stefan Sauter Institute for Mathematics, University of Zürich, Winterthurerstrasse 190, CH-8057 Zürich, Switzerland We consider the wave equation in a boundary integral formulation.The discretization in time is done by using convolution quadraturetechniques and a Galerkin boundary element method for the spatialdiscretization. In a previous paper, we have introduced a sparseapproximation of the system matrix by cut-off, in order to reducethe storage costs. In this paper, we extend this approach byintroducing a panel clustering method to further reduce thesecosts.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号