Convergence of multistep discretizations of DAEs

Standard ODE methods such as linear multistep methods encounter difficulties when applied to differential-algebraic equations (DAEs) of index greater than 1. In particular, previous results for index 2 DAEs have practically ruled out the use of all explicit methods and of implicit multistep methods other than backward difference formulas (BDFs) because of stability considerations. In this paper we embed known results for semi-explicit index 1 and 2 DAEs in a more comprehensive theory based on compound multistep and one-leg discretizations. This explains and characterizes the necessary requirements that a method must fulfill in order to be applicable to semi-explicit DAEs. Thus we conclude that the most useful discretizations are those that avoid discretization of the constraint. A freer use of e.g. explicit methods for the non-stiff differential part of the DAE is then possible.Dedicated to Germund Dahlquist on the occasion of his 70th birthdayThis author thanks the Centro de Estadística y Software Matemático de la Universidad Simón Bolivar (CESMa) for permitting her free use of its research facilities.Partial support by the Swedish Research Council for Engineering Sciences TFR under contract no. 222/91-405.     

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.     

On the derivation of explicit two-step peer methods

The so-called two-step peer methods for the numerical solution of Initial Value Problems (IVP) in differential systems were introduced by R. Weiner, B.A. Schmitt and coworkers as a tool to solve different types of IVPs either in sequential or parallel computers. These methods combine the advantages of Runge-Kutta (RK) and multistep methods to obtain high stage order and therefore provide in a natural way a dense output. In particular, several explicit peer methods have been proved to be competitive with standard RK methods in a wide selection of non-stiff test problems.The aim of this paper is to propose an alternative procedure to construct families of explicit two step peer methods in which the available parameters appear in a transparent way. This allows us to obtain families of fixed stepsize s stage methods with stage order 2s−1, which provide dense output without extra cost, depending on some free parameters that can be selected taking into account the stability properties and leading error terms. A study of the extension of these methods to variable stepsize is also carried out. Optimal s stage methods with s=2,3 are derived.     

Primal—dual methods for linear programming

Many interior-point methods for linear programming are based on the properties of the logarithmic barrier function. After a preliminary discussion of the convergence of the (primal) projected Newton barrier method, three types of barrier method are analyzed. These methods may be categorized as primal, dual and primal—dual, and may be derived from the application of Newton's method to different variants of the same system of nonlinear equations. A fourth variant of the same equations leads to a new primal—dual method.In each of the methods discussed, convergence is demonstrated without the need for a nondegeneracy assumption or a transformation that makes the provision of a feasible point trivial. In particular, convergence is established for a primal—dual algorithm that allows a different step in the primal and dual variables and does not require primal and dual feasibility.Finally, a new method for treating free variables is proposed.Presented at the Second Asilomar Workshop on Progress in Mathematical Programming, February 1990, Asilomar, CA, United StatesThe material contained in this paper is based upon research supported by the National Science Foundation Grant DDM-9204208 and the Office of Naval Research Grant N00014-90-J-1242.     

Twostep-by-twostep continuous PIRKN-type PC methods for nonstiff IVPs

In this paper, we start with the consideration of direct collocation-based Runge-Kutta-Nyström (RKN) methods with continuous output formulas for solving nonstiff initial-value problems (IVPs) for systems of special second-order differential equations y″(t) = f(t, y(t)). At nth step, the continuous output formulas can be used for calculating the step values at (n + 2)th step and the integration processes can be proceeded twostep-by-twostep. In this case, we obtain twostep-by-twostep RKN methods with continuous output formulas (continuous TBTRKN methods). Furthermore, we consider a parallel predictor-corrector (PC) iteration scheme using the continuous TBTRKN methods as corrector methods with predictor methods defined by the continuous output formulas. The resulting twostep-by-twostep parallel-iterated RKN-type PC methods with continuous output formulas (twostep-by-twostep continuous PIRKN-type PC methods or TBTCPIRKN methods) give us a faster integration processes. Numerical comparisons based on the solution of a few widely-used test problems show that the new TBTCPIRKN methods are much more efficient than the well-known PIRKN methods, the famous nonstiff sequential ODEX2, DOP853 codes and comparable with the CPIRKN methods.     

Metric-Based Parameterizations for Multi-Step Unconstrained Optimization

We consider multi-step quasi-Newton methods for unconstrained optimization. These methods were introduced by Ford and Moghrabi (Appl. Math., vol. 50, pp. 305–323, 1994; Optimization Methods and Software, vol. 2, pp. 357–370, 1993), who showed how interpolating curves could be used to derive a generalization of the Secant Equation (the relation normally employed in the construction of quasi-Newton methods). One of the most successful of these multi-step methods makes use of the current approximation to the Hessian to determine the parameterization of the interpolating curve in the variable-space and, hence, the generalized updating formula. In this paper, we investigate new parameterization techniques to the approximate Hessian, in an attempt to determine a better Hessian approximation at each iteration and, thus, improve the numerical performance of such algorithms.     

Statistical gap Tauberian theorems in metric spaces

By using the concept of statistical convergence we present statistical Tauberian theorems of gap type for the Cesàro, Euler-Borel family and the Hausdorff families applicable in arbitrary metric spaces. In contrast to the classical gap Tauberian theorems, we show that such theorems exist in the statistical sense for the convolution methods which include the Taylor and the Borel matrix methods. We further provide statistical analogs of the gap Tauberian theorems for the Hausdorff methods and provide an explanation as to how the Tauberian rates over the gaps may differ from those of the classical Tauberian theorems.     

An inexact proximal point method for solving generalized fractional programs

In this paper, we present several new implementable methods for solving a generalized fractional program with convex data. They are Dinkelbach-type methods where a prox-regularization term is added to avoid the numerical difficulties arising when the solution of the problem is not unique. In these methods, at each iteration a regularized parametric problem is solved inexactly to obtain an approximation of the optimal value of the problem. Since the parametric problem is nonsmooth and convex, we propose to solve it by using a classical bundle method where the parameter is updated after each ‘serious step’. We mainly study two kinds of such steps, and we prove the convergence and the rate of convergence of each of the corresponding methods. Finally, we present some numerical experience to illustrate the behavior of the proposed algorithms, and we discuss the practical efficiency of each one.      

An ODE-Based Trust Region Filter Algorithm for Unconstrained Optimization

In this article, an ODE-based trust region filter algorithm for unconstrained optimization is proposed. It can be regarded as a combination of trust region and filter techniques with ODE-based methods. Unlike the existing trust-region-filter methods and ODE-based methods, a distinct feature of this method is that at each iteration, a reduced linear system is solved to obtain a trial step, thus avoiding solving a trust region subproblem. Under some standard assumptions, it is proven that the algorithm is globally convergent. Preliminary numerical results show that the new algorithm is efficient for large scale problems.     

New eighth-order iterative methods for solving nonlinear equations

In this paper, three new families of eighth-order iterative methods for solving simple roots of nonlinear equations are developed by using weight function methods. Per iteration these iterative methods require three evaluations of the function and one evaluation of the first derivative. This implies that the efficiency index of the developed methods is 1.682, which is optimal according to Kung and Traub’s conjecture [7] for four function evaluations per iteration. Notice that Bi et al.’s method in [2] and [3] are special cases of the developed families of methods. In this study, several new examples of eighth-order methods with efficiency index 1.682 are provided after the development of each family of methods. Numerical comparisons are made with several other existing methods to show the performance of the presented methods.     

Comparison of Two Kinds of Prediction-Correction Methods for Monotone Variational Inequalities

In this paper, we study the relationship between the forward-backward splitting method and the extra-gradient method for monotone variational inequalities. Both of the methods can be viewed as prediction-correction methods. The only difference is that they use different search directions in the correction-step. Our analysis explains theoretically why the extra-gradient methods usually outperform the forward-backward splitting methods. We suggest some modifications for the two methods and numerical results are given to verify the superiority of the modified methods.     

A Survey of Algebraic Multilevel Iteration (AMLI) Methods

For the solution by preconditioned conjugate gradient methods of symmetric positive definite equations as arising in boundary value problems we consider preconditioning methods of AMLI type. Particular attention is devoted to providing methods of optimal order of computational complexity which in addition promise to be robust, i.e. with a convergence rate which is bounded above independently of size of discretization parameter h, jumps in problem coefficients, and shape of finite elements or, equivalently, anisotropy of problem coefficients. In addition, the computational cost per iteration step must have optimal order.New results on upper bounds of one of the important parameters in the methods, the Cauchy—Bunyakowski—Schwarz constant are given and an algebraic method how to improve its value is presented.This revised version was published online in October 2005 with corrections to the Cover Date.     

Long-step strategies in interior-point primal-dual methods

In this paper we analyze from a unique point of view the behavior of path-following and primal-dual potential reduction methods on nonlinear conic problems. We demonstrate that most interior-point methods with efficiency estimate can be considered as different strategies of minimizing aconvex primal-dual potential function in an extended primal-dual space. Their efficiency estimate is a direct consequence of large local norm of the gradient of the potential function along a central path. It is shown that the neighborhood of this path is a region of the fastest decrease of the potential. Therefore the long-step path-following methods are, in a sense, the best potential-reduction strategies. We present three examples of such long-step strategies. We prove also an efficiency estimate for a pure primal-dual potential reduction method, which can be considered as an implementation of apenalty strategy based on a functional proximity measure. Using the convex primal dual potential, we prove efficiency estimates for Karmarkar-type and Dikin-type methods as applied to a homogeneous reformulation of the initial primal-dual problem.     

On multistep interval methods for solving the initial value problem

In this paper we shortly complete our previous considerations on interval versions of Adams multistep methods [M. Jankowska, A. Marciniak, Implicit interval multistep methods for solving the initial value problem, Comput. Meth. Sci. Technol. 8(1) (2002) 17–30; M. Jankowska, A. Marciniak, On explicit interval methods of Adams–Bashforth type, Comput. Meth. Sci. Technol. 8(2) (2002) 46–57; A. Marciniak, Implicit interval methods for solving the initial value problem, Numerical Algorithms 37 (2004) 241–251]. It appears that there exist two families of implicit interval methods of this kind. More considerations are dealt with two new kinds of interval multistep methods based on conventional well-known Nyström and Milne–Simpson methods. For these new interval methods we prove that the exact solution of the initial value problem belongs to the intervals obtained. Moreover, we present some estimations of the widths of interval solutions. Some conclusions bring this paper to the end.     

Continuous extensions to Nyström methods for second order initial value problems

In this work we consider interpolants for Nyström methods, i.e., methods for solving second order initial value problems. We give a short introduction to the theory behind the discrete methods, and extend some of the work to continuous, explicit Nyström methods. Interpolants for continuous, explicit Runge-Kutta methods have been intensively studied by several authors, but there has not been much effort devoted to continuous Nyström methods. We therefore extend some of the work by Owren.     

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.     

Comments on “Embedded pair of extended Runge–Kutta–Nyström type methods for perturbed oscillators”

In a recent paper Fang [Embedded pair of extended Runge–Kutta–Nyström type methods for perturbed oscillators, Appl. Math. Modell. (2009), doi:10.1016/j.apm.2009.12.004] considered the embedded pair of extended Runge–Kutta–Nyström type methods for perturbed oscillators and analyzed numerical stability and phase properties of the methods. The authors claimed that their methods are based on the order conditions of extended Runge–Kutta–Nyström type methods presented by Yang et al. [Extended RKN-type methods for numerical integration of perturbed oscillators, Comput. Phys. Commun. 180 (2009) 1777–1794]. However, some careless mistakes have been made in that paper. For this reason we will make some comments on that paper.     

On the Vector ε-Algorithm for Solving Linear Systems of Equations

The four vector extrapolation methods, minimal polynomial extrapolation, reduced rank extrapolation, modified minimal polynomial extrapolation and the topological epsilon algorithm, when applied to linearly generated vector sequences are Krylov subspace methods and it is known that they are equivalent to some well-known conjugate gradient type methods. However, the vector -algorithm is an extrapolation method, older than the four extrapolation methods above, and no similar results are known for it. In this paper, a determinantal formula for the vector -algorithm is given. Then it is shown that, when applied to a linearly generated vector sequence, the algorithm is also a Krylov subspace method and for a class of matrices the method is equivalent to a preconditioned Lanczos method. A new determinantal formula for the CGS is given, and an algebraic comparison between the vector -algorithm for linear systems and CGS is also given.     

Order conditions for linearly implicit fractional step Runge Kutta methods

^{In this paper, we study the consistency of a variant of fractionalstep Runge–Kutta methods. These methods are designed tointegrate efficiently semi-linear multidimensional parabolicproblems by means of linearly implicit time integration processes.Such time discretization procedures are also related to a splittingof the space differential operator (or the spatial discretizationof it) as a sum of ‘simpler’ linear differentialoperators and a nonlinear term.}