三维泊松方程基于Richardson外推法的高阶紧致差分方法

基于Richardson外推法提出了数值求解三维泊松方程的高阶紧致差分方法.方法通过利用四阶和六阶紧致差分格式,分别在细网格和粗网格上求解,然后利用Richardson外推技术和算子插值方法,得到三维泊松方程在细网格上的六阶和八阶精度的数值解.数值实验结果验证了该方法的精确性和有效性.     

三维泊松方程的高精度多重网格解法

利用对称网格点泰勒展开式中各阶导数项明显的对称性,得到了数值求解三维泊松方程的四阶和六阶精度的紧致差分格式,其推导过程简便直接.为了克服传统迭代法在求解高维问题时计算量大、收敛速度慢的缺陷,采用了多重网格加速技术,设计了相应的多重网格算法,求解了三维泊松方程的Dirichlet边值问题.数值实验结果表明,本文所提出的高精度紧致格式达到了期望的精度并且多重网格方法的加速效果是非常显著的.     

Fourier analysis of a robust multigrid method for convection-diffusion equations

Summary. We consider a two-grid method for solving 2D convection-diffusion problems. The coarse grid correction is based on approximation of the Schur complement. As a preconditioner of the Schur complement we use the exact Schur complement of modified fine grid equations. We assume constant coefficients and periodic boundary conditions and apply Fourier analysis. We prove an upper bound for the spectral radius of the two-grid iteration matrix that is smaller than one and independent of the mesh size, the convection/diffusion ratio and the flow direction; i.e. we have a (strong) robustness result. Numerical results illustrating the robustness of the corresponding multigrid -cycle are given. Received October 14, 1994     

A characterization of mapping unstructured grids onto structured grids and using multigrid as a preconditioner

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.     

Numerical pricing of options using high-order compact finite difference schemes

We consider high-order compact (HOC) schemes for quasilinear parabolic partial differential equations to discretise the Black–Scholes PDE for the numerical pricing of European and American options. We show that for the heat equation with smooth initial conditions, the HOC schemes attain clear fourth-order convergence but fail if non-smooth payoff conditions are used. To restore the fourth-order convergence, we use a grid stretching that concentrates grid nodes at the strike price for European options. For an American option, an efficient procedure is also described to compute the option price, Greeks and the optimal exercise curve. Comparisons with a fourth-order non-compact scheme are also done. However, fourth-order convergence is not experienced with this strategy. To improve the convergence rate for American options, we discuss the use of a front-fixing transformation with the HOC scheme. We also show that the HOC scheme with grid stretching along the asset price dimension gives accurate numerical solutions for European options under stochastic volatility.     

Multigrid and multilevel methods for quadratic spline collocation

Multigrid methods are developed and analyzed for quadratic spline collocation equations arising from the discretization of one-dimensional second-order differential equations. The rate of convergence of the two-grid method integrated with a damped Richardson relaxation scheme as smoother is shown to be faster than 1/2, independently of the step-size. The additive multilevel versions of the algorithms are also analyzed. The development of quadratic spline collocation multigrid methods is extended to two-dimensional elliptic partial differential equations. Multigrid methods for quadratic spline collocation methods are not straightforward: because the basis functions used with quadratic spline collocation are not nodal basis functions, the design of efficient restriction and extension operators is nontrivial. Experimental results, with V-cycle and full multigrid, indicate that suitably chosen multigrid iteration is a very efficient solver for the quadratic spline collocation equations. Supported by Communications and Information Technology Ontario (CITO), Canada. Supported by the Mathematical, Information, and Computational Sciences Division subprogram of the Office of Computational and Technology Research, U.S. Department of Energy, under Contract W-31-109-Eng-38.     

Convergence analysis of a multigrid method for convection–diffusion equations

Summary. This paper is concerned with the convergence analysis of robust multigrid methods for convection-diffusion problems. We consider a finite difference discretization of a 2D model convection-diffusion problem with constant coefficients and Dirichlet boundary conditions. For the approximate solution of this discrete problem a multigrid method based on semicoarsening, matrix-dependent prolongation and restriction and line smoothers is applied. For a multigrid W-cycle we prove an upper bound for the contraction number in the euclidean norm which is smaller than one and independent of the mesh size and the diffusion/convection ratio. For the contraction number of a multigrid V-cycle a bound is proved which is uniform for a class of convection-dominated problems. The analysis is based on linear algebra arguments only. Received April 26, 2000 / Published online June 20, 2001     

Patch-adaptive multilevel iteration

Themultilevel adaptive iteration is an attempt to improve both the robustness and efficiency of iterative sparse system solvers. Unlike in most other iterative methods, the order of processing and sequence of operations is not determined a priori. The method consists of a relaxation scheme with an active set strategy and can be viewed as an efficient implementation of the Gauß-Southwell relaxation. With this strategy, computational work is focused on where it can efficiently improve the solution quality. To obtain full efficiency, the algorithm must be used on a multilevel structure. This algorithm is then closely related to multigrid or multilevel preconditioning algorithms, and can be shown to have asymptotically optimal convergence. In this paper the focus is on a variant that uses data structures with a locally uniform grid refinement. The resulting grid system consists of a collection of patches where each patch is a uniform rectangular grid and where adaptive refinement is accomplished by arranging the patches flexibly in space. This construction permits improved implementations that better exploit high performance computer designs. This will be demonstrated by numerical examples.     

Multigrid Methods with Newton-Gauss-Seidel Smoothing and Constraint Preserving Interpolation for Obstacle Problems

In this paper, we propose a multigrid algorithm based on the full approximate scheme for solving the membrane constrained obstacle problems and the minimal surface obstacle problems in the formulations of HJB equations. A Newton-Gauss-Seidel (NGS) method is used as smoother. A Galerkin coarse grid operator is proposed for the membrane constrained obstacle problem. Comparing with standard FAS with the direct discretization coarse grid operator, the FAS with the proposed operator converges faster. A special prolongation operator is used to interpolate functions accurately from the coarse grid to the fine grid at the boundary between the active and inactive sets. We will demonstrate the fast convergence of the proposed multigrid method for solving two model obstacle problems and compare the results with other multigrid methods.     

Efficient geometric multigrid implementation for triangular grids

This paper deals with a stencil-based implementation of a geometric multigrid method on semi-structured triangular grids (triangulations obtained by regular refinement of an irregular coarse triangulation) for linear finite element methods. An efficient and elegant procedure to construct these stencils using a reference stencil associated to a canonical hexagon is proposed. Local Fourier Analysis (LFA) is applied to obtain asymptotic convergence estimates. Numerical experiments are presented to illustrate the efficiency of this geometric multigrid algorithm, which is based on a three-color smoother.     

Integrated fast and high‐accuracy computation of convection diffusion equations using multiscale multigrid method

We present an explicit sixth‐order compact finite difference scheme for fast high‐accuracy numerical solutions of the two‐dimensional convection diffusion equation with variable coefficients. The sixth‐order scheme is based on the well‐known fourth‐order compact (FOC) scheme, the Richardson extrapolation technique, and an operator interpolation scheme. For a particular implementation, we use multiscale multigrid method to compute the fourth‐order solutions on both the coarse grid and the fine grid. Then, an operator interpolation scheme combined with the Richardson extrapolation technique is used to compute a sixth‐order accurate fine grid solution. We compare the computed accuracy and the implementation cost of the new scheme with the standard nine‐point FOC scheme and Sun–Zhang's sixth‐order method. Two convection diffusion problems are solved numerically to validate our proposed sixth‐order scheme. © 2009 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2011     

High Accuracy Solution of Three-Dimensional Biharmonic Equations

In this paper, we consider several finite-difference approximations for the three-dimensional biharmonic equation. A symbolic algebra package is utilized to derive a family of finite-difference approximations for the biharmonic equation on a 27 point compact stencil. The unknown solution and its first derivatives are carried as unknowns at selected grid points. This formulation allows us to incorporate the Dirichlet boundary conditions automatically and there is no need to define special formulas near the boundaries, as is the case with the standard discretizations of biharmonic equations. We exhibit the standard second-order, finite-difference approximation that requires 25 grid points. We also exhibit two compact formulations of the 3D biharmonic equations; these compact formulas are defined on a 27 point cubic grid. The fourth-order approximations are used to solve a set of test problems and produce high accuracy numerical solutions. The system of linear equations is solved using a variety of iterative methods. We employ multigrid and preconditioned Krylov iterative methods to solve the system of equations. Test results from two test problems are reported. In these experiments, the multigrid method gives excellent results. The multigrid preconditioning also gives good results using Krylov methods.     

Multigrid method for solving convection-diffusion problems with dominant convection

A modification of the multigrid method for the solution of linear algebraic equation systems with a strongly nonsymmetric matrix obtained after difference approximation of the convection-diffusion equation with dominant convection is proposed. Specially created triangular iterative methods have been used as the smoothers of the multigrid method. Some theoretical and numerical results are presented.     

A fourth-order method of the convection-diffusion equations with Neumann boundary conditions

In this paper, we have developed a fourth-order compact finite difference scheme for solving the convection-diffusion equation with Neumann boundary conditions. Firstly, we apply the compact finite difference scheme of fourth-order to discrete spatial derivatives at the interior points. Then, we present a new compact finite difference scheme for the boundary points, which is also fourth-order accurate. Finally, we use a Padé approximation method for the resulting linear system of ordinary differential equations. The presented scheme has fifth-order accuracy in the time direction and fourth-order accuracy in the space direction. It is shown through analysis that the scheme is unconditionally stable. Numerical results show that the compact finite difference scheme gives an efficient method for solving the convection-diffusion equations with Neumann boundary conditions.     

A multigrid method for constrained optimal control problems

We consider the fast and efficient numerical solution of linear-quadratic optimal control problems with additional constraints on the control. Discretization of the first-order conditions leads to an indefinite linear system of saddle point type with additional complementarity conditions due to the control constraints. The complementarity conditions are treated by a primal-dual active set strategy that serves as outer iteration. At each iteration step, a KKT system has to be solved. Here, we develop a multigrid method for its fast solution. To this end, we use a smoother which is based on an inexact constraint preconditioner.We present numerical results which show that the proposed multigrid method possesses convergence rates of the same order as for the underlying (elliptic) PDE problem. Furthermore, when combined with a nested iteration, the solver is of optimal complexity and achieves the solution of the optimization problem at only a small multiple of the cost for the PDE solution.     

Monotone multigrid methods for elliptic variational inequalities II

Summary. We derive globally convergent multigrid methods for discrete elliptic variational inequalities of the second kind as obtained from the approximation of related continuous problems by piecewise linear finite elements. The coarse grid corrections are computed from certain obstacle problems. The actual constraints are fixed by the preceding nonlinear fine grid smoothing. This new approach allows the implementation as a classical V-cycle and preserves the usual multigrid efficiency. We give estimates for the asymptotic convergence rates. The numerical results indicate a significant improvement as compared with previous multigrid approaches. Received March 26, 1994 / Revised version received September 22, 1994     

Multigrid solution of high order discretisation for three-dimensional biharmonic equation with Dirichlet boundary conditions of second kind

In this paper, we propose two compact finite difference approximations for three-dimensional biharmonic equation with Dirichlet boundary conditions of second kind. In these methods there is no need to define special formulas near the boundaries and boundary conditions are incorporated with these techniques. The unknown solution and its second derivatives are carried as unknowns at grid points. We derive second-order and fourth-order approximations on a 27 point compact stencil. Classical iteration methods such as Gauss–Seidel and SOR for solving the linear system arising from the second-order and fourth-order discretisation suffer from slow convergence. In order to overcome this problem we use multigrid method which exhibit grid-independent convergence and solve the linear system of equations in small amount of computer time. The fourth-order finite difference approximations are used to solve several test problems and produce high accurate numerical solutions.     

A cascadic multigrid algorithm for semilinear elliptic problems

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     

Sixth-Order Compact Extended Trapezoidal Rules for 2D Schrödinger Equation

Based on high-order linear multistep methods (LMMs), we use the class of extended trapezoidal rules (ETRs) to solve boundary value problems of ordinary differential equations (ODEs), whose numerical solutions can be approximated by boundary value methods (BVMs). Then we combine this technique with fourth-order Padé compact approximation to discrete 2D Schrödinger equation. We propose a scheme with sixth-order accuracy in time and fourth-order accuracy in space. It is unconditionally stable due to the favourable property of BVMs and ETRs. Furthermore, with Richardson extrapolation, we can increase the scheme to order 6 accuracy both in time and space. Numerical results are presented to illustrate the accuracy of our scheme.     

Error analysis for a potential problem on locally refined grids

Summary. For the simulation of biomolecular systems in an aqueous solvent a continuum model is often used for the solvent. The accurate evaluation of the so-called solvation energy coming from the electrostatic interaction between the solute and the surrounding water molecules is the main issue in this paper. In these simulations, we deal with a potential problem with jumping coefficients and with a known boundary condition at infinity. One of the advanced ways to solve the problem is to use a multigrid method on locally refined grids around the solute molecule. In this paper, we focus on the error analysis of the numerical solution and the numerical solvation energy obtained on the locally refined grids. Based on a rigorous error analysis via a discrete approximation of the Greens function, we show how to construct the composite grid, to discretize the discontinuity of the diffusion coefficient and to interpolate the solutions at interfaces between the fine and coarse grids. The error analysis developed is confirmed by numerical experiments. Received June 25, 1998 / Revised version received July 14, 1999 / Published online June 8, 2000