Fourth-Order Splitting Methods for Time-Dependant Differential Equations

This study was suggested by previous work on the simulation of evolution equations with scale-dependent processes,e.g.,wave-propagation or heat-transfer,that are modeled by wave equations or heat equations.Here,we study both parabolic and hyperbolic equations.We focus on ADI (alternating direction implicit) methods and LOD (locally one-dimensional) methods,which are standard splitting methods of lower order,e.g.second-order.Our aim is to develop higher-order ADI methods,which are performed by Richardson extrapolation,Crank-Nicolson methods and higher-order LOD methods,based on locally higher-order methods.We discuss the new theoretical results of the stability and consistency of the ADI methods.The main idea is to apply a higher- order time discretization and combine it with the ADI methods.We also discuss the dis- cretization and splitting methods for first-order and second-order evolution equations. The stability analysis is given for the ADI method for first-order time derivatives and for the LOD (locally one-dimensional) methods for second-order time derivatives.The higher-order methods are unconditionally stable.Some numerical experiments verify our results.     

Quasi-Newton ABS methods for solving nonlinear algebraic systems of equations

This paper is concerned with the solution of nonlinear algebraic systems of equations. For this problem, we suggest new methods, which are combinations of the nonlinear ABS methods and quasi-Newton methods. Extensive numerical experiments compare particular algorithms and show the efficiency of the proposed methods.The authors are grateful to Professors C. G. Broyden and E. Spedicato for many helpful discussions.     

预估-校正方法的绝对稳定性讨论

预估-校正方法,即PECE方法,常被用于求解常微分方程的初值问题.而一般文献中常只讨论了单个线性多步法公式的稳定性问题,很少涉及由一个显式公式和一个隐式公式组合而成的PECE方法的稳定性.本文应用根轨迹法和对分法讨论了常用的PECE方法的稳定性,求出了一些常用PECE方法的组合公式的绝对稳定区间和绝对稳定区域,并用数值...     

Decomposition methods in stochastic programming

Stochastic programming problems have very large dimension and characteristic structures which are tractable by decomposition. We review basic ideas of cutting plane methods, augmented Lagrangian and splitting methods, and stochastic decomposition methods for convex polyhedral multi-stage stochastic programming problems.     

Arbitrary-order functionally fitted energy-diminishing methods for gradient systems

It is well known that for gradient systems in Euclidean space or on a Riemannian manifold, the energy decreases monotonically along solutions. In this letter we derive and analyse functionally fitted energy-diminishing methods to preserve this key property of gradient systems. It is proved that the novel methods are energy-diminishing and can achieve damping for very stiff gradient systems. We also show that the methods can be of arbitrarily high order and discuss their implementations. A numerical test is reported to illustrate the efficiency of the new methods in comparison with three existing numerical methods in the literature.     

A semi-lagrangian numerical method for geometric optics type problems

Linear multistep methods (LMMs) are written as irreducible general linear methods (GLMs). A-stable LMMs are shown to be algebraically stable GLMs for strictly positive definite G-matrices. Optimal order error bounds, independent of stiffness, are derived for A-stable methods, without considering one-leg methods (OLMs). As a GLM, the OLM is shown to be the transpose of the LMM. For A-stable methods, the LMM G-matrix is the inverse of the OLM G-matrix. Examples of G-symplectic LMMs are given. AMS subject classification (2000) 65L20     

Imbedding methods for integral equations with applications

During the last decade or two, significant progress has been made in the development of imbedding methods for the analytical and computational treatment of integral equations. These methods are now well known in radiative transfer, neutron transport, optimal filtering, and other fields. In this review paper, we describe the current status of imbedding methods for integral equations. The paper emphasizes new analytical and computational developments in control and filtering, multiple scattering, inverse problems of wave propagation, and solid and fluid mechanics. Efficient computer programs for the determination of complex eigenvalues of integral operators, analytical investigations of stability for significant underlying Riccati integrodifferential equations, and comparisons against other methods are described.     

New splitting methods for two-dimensional evolutionary equations

New second- and third-order splitting methods are proposed for evolutionary-type partial differential equations in a two-dimensional space. These methods are derived on the basis of diagonally implicit methods applied to the numerical analysis of stiff ordinary differential equations. The splitting methods are found to be absolutely unconditionally stable. Test calculations are presented.     

The composite Milstein methods for the numerical solution of Stratonovich stochastic differential equations

In this paper, we present two composite Milstein methods for the strong solution of Stratonovich stochastic differential equations driven by d-dimensional Wiener processes. The composite Milstein methods are a combination of semi-implicit and implicit Milstein methods. The criterion for choosing either the implicit or the semi-implicit method at each step of the numerical solution is given. The stability and convergence properties of the proposed methods are analyzed for the linear test equation. It is shown that the proposed methods converge to the exact solution in Stratonovich sense. In addition, the stability properties of our methods are found to be superior to those of the Milstein and the composite Euler methods. The convergence properties for the nonlinear case are shown numerically to be the same as the linear case. Hence, the proposed methods are a good candidate for the solution of stiff SDEs.     

Numerical Experience with Multiple Update Quasi-Newton Methods for Unconstrained Optimization

The authors have derived what they termed quasi-Newton multi step methods in [2]. These methods have demonstrated substantial numerical improvements over the standard single step Secant-based BFGS. Such methods use a variant of the Secant equation that the updated Hessian (or its inverse) satisfies at each iteration. In this paper, new methods will be explored for which the updated Hessians satisfy multiple relations of the Secant-type. A rational model is employed in developing the new methods. The model hosts a free parameter which is exploited in enforcing symmetry on the updated Hessian approximation matrix thus obtained. The numerical performance of such techniques is then investigated and compared to other methods. Our results are encouraging and the improvements incurred supercede those obtained from other existing methods at minimal extra storage and computational overhead.     

Parallel Newton Two-Stage Multisplitting Iterative Methods for Nonlinear Systems

Parallel Newton two-stage iterative methods to solve nonlinear systems are studied. These algorithms are based on both the multisplitting technique and the two-stage iterative methods. Convergence properties of these methods are studied when the Jacobian matrix is either monotone or an H-matrix. Furthermore, in order to illustrate the performance of the algorithms studied, computational results about these methods on a distributed memory multiprocessor are discussed.This revised version was published online in October 2005 with corrections to the Cover Date.     

Newton-type methods for constrained optimization with nonregular constraints

The most important classes of Newton-type methods for solving constrained optimization problems are discussed. These are the sequential quadratic programming methods, active set methods, and semismooth Newton methods for Karush-Kuhn-Tucker systems. The emphasis is placed on the behavior of these methods and their special modifications in the case where assumptions concerning constraint qualifications are relaxed or altogether dropped. Applications to optimization problems with complementarity constraints are examined.     

Numerical solution of the finite horizon stochastic linear quadratic control problem

The treatment of the stochastic linear quadratic optimal control problem with finite time horizon requires the solution of stochastic differential Riccati equations. We propose efficient numerical methods, which exploit the particular structure and can be applied for large‐scale systems. They are based on numerical methods for ordinary differential equations such as Rosenbrock methods, backward differentiation formulas, and splitting methods. The performance of our approach is tested in numerical experiments.     

On the choice of correctors for semi-implicit Picard deferred correction methods

The goal of this study is to assess the implications of the choice of correctors for semi-implicit Picard integral deferred correction (SIPIDC) methods. The SIPIDC methods previously developed compute a high-order approximation by first computing a low-order provisional solution using a semi-implicit method and then using a first-order semi-implicit method to solve a series of correction equations, each of which raises the order of accuracy of the solution by one. In this study, we examine the efficiency of SIPIDC methods that instead use standard second-order semi-implicit methods to solve the correction equations. The accuracy, efficiency, and stability of the resulting methods are compared to previously developed methods, in the context of both nonstiff and stiff problems.     

Hybrid methods for large sparse nonlinear least squares

Hybrid methods are developed for improving the Gauss-Newton method in the case of large residual or ill-conditioned nonlinear least-square problems. These methods are used usually in a form suitable for dense problems. But some standard approaches are unsuitable, and some new possibilities appear in the sparse case. We propose efficient hybrid methods for various representations of the sparse problems. After describing the basic ideas that help deriving new hybrid methods, we are concerned with designing hybrid methods for sparse Jacobian and sparse Hessian representations of the least-square problems. The efficiency of hybrid methods is demonstrated by extensive numerical experiments.This work was supported by the Czech Republic Grant Agency, Grant 201/93/0129. The author is indebted to Jan Vlek for his comments on the first draft of this paper and to anonymous referees for many useful remarks.     

A family of Numerov-type exponentially fitted predictor-corrector methods for the numerical integration of the radial Schrödinger equation

A family of predictor-corrector exponential Numerov-type methods is developed for the numerical integration of the one-dimensional Schrödinger equation. The formula considered contains certain free parameters which allow it to be fitted automatically to exponential functions. The new methods are very simple and integrate more exponential functions than both the well-known fourth-order Numerov-type exponentially fitted methods and the sixth algebraic order Runge-Kutta-type methods. Numerical results also indicate that the new methods are much more accurate than the other exponentially fitted methods mentioned above.     

Two-step-by-two-step PIRK-type PC methods based on Gauss-Legendre collocation points

This paper concerns with parallel predictor-corrector (PC) iteration methods for solving nonstiff initial-value problems (IVPs) for systems of first-order differential equations. The predictor methods are based on Adams-type formulas. The corrector methods are constructed by using coefficients of s-stage collocation Gauss-Legendre Runge-Kutta (RK) methods based on c₁,…,c_s and the 2s-stage collocation RK methods based on c₁,…,c_s,1+c₁,…,1+c_s. At nth integration step, the stage values of the 2s-stage collocation RK methods evaluated at t_n+(1+c₁)h,…,t_n+(1+c_s)h can be used as the stage values of the collocation Gauss-Legendre RK method for (n+2)th integration step. By this way, we obtain the corrector methods in which the integration processes can be proceeded two-step-by-two-step. The resulting parallel PC iteration methods which are called two-step-by-two-step (TBT) parallel-iterated RK-type (PIRK-type) PC methods based on Gauss-Legendre collocation points (two-step-by-two-step PIRKG methods or TBTPIRKG methods) give us a faster integration process. Fixed step size applications of these TBTPIRKG methods to the three widely used test problems reveal that the new parallel PC iteration methods are much more efficient when compared with the well-known parallel-iterated RK methods (PIRK methods) and sequential codes ODEX, DOPRI5 and DOP853 available from the literature.     

On the cibstryctuib of discretizations of elliptic partial differential equations

Algorithmic aspects of a class of finite element collocation methods for the approximate numerical solution of elliptic partial differential equations are described Locall for each finite element the approximate solution is a polynomial. polynomials corresponding toadjacent finite elements need not match continuously but their values and noumal derivatives match at a discrete set of points on the common boundary.High order accuracy can be attained by increasing the number of mathching points and the number of colloction points for each finite element.Forlinear equations the collocation methods can be equivalently definde as generlized finite difference methods. The linear (or linearzed )equations that arise from the discretization lend themselves well to solution by the methods of the methods nested dissection.An implememtation is described and some numerical results are givevn.     

关于求解二维三温热传导问题的一点探讨

本文首先给出了二维三温热传导问题的数学模型和有关数据,在单层三角形网格剖分下,讨论了牛顿和固结系数两种线性化方法,经典的和保对称的两种有限体离散方法,并获得了对比数值结果.     

A General Family of Pseudo Two-step Runge-Kutta Methods

The aim of this paper is to design a new family of numerical methods of arbitrarily high order for systems of first-order differential equations which are to be termed pseudo two-step Runge-Kutta methods. By using collocation techniques, we can obtain an arbitrarily high-order stable pseudo two-step Runge-Kutta method with any desired number of implicit stages in retaining the two-step nature. In very first investigations, the pseudo two-step Runge-Kutta methods are shown to be promising numerical integration methods.AMS(MOS) subject classifications (1991) 65M12 65M20CR subject classifications G.1.7This work was partly supported by DAAD, N.R.P.F.S. and QG-96-02