Convergence of linear multistep methods for differential equations with discontinuities

Summary A new stability functional is introduced for analyzing the stability and consistency of linear multistep methods. Using it and the general theory of [1] we prove that a linear multistep method of design orderqp1 which satisfies the weak stability root condition, applied to the differential equationy (t)=f (t, y (t)) wheref is Lipschitz continuous in its second argument, will exhibit actual convergence of ordero(h ^p–1) ify has a (p–1)th derivativey ^(p–1) that is a Riemann integral and ordero(h ^p) ify ^(p–1) is the integral of a function of bounded variation. This result applies for a functiony taking on values in any real vector space, finite or infinite dimensional.This work was supported by Grant GJ-938 from the National Science Foundation     

On the uniform nonsingularity of matrices of search directions and the rate of convergence in minimization algorithms

A convergent minimization algorithm made up of repetitive line searches is considered in ⁿ . It is shown that the uniform nonsingularity of the matrices consisting ofn successive normalized search directions guarantees a speed of convergence which is at leastn-step Q-linear. Consequences are given for multistep methods, including Powell's 1964 procedure for function minimization without calculating derivatives as well as Zangwill's modifications of this procedure.The authors wish to thank the Namur Department of Mathematics, especially its optimization group, for many discussions and encouragement. They also thank the reviewers for many helpful suggestions.     

Contractivity preserving explicit linear multistep methods

Summary We investigate contractivity properties of explicit linear multistep methods in the numerical solution of ordinary differential equations. The emphasis is on the general test-equation , whereA is a square matrix of arbitrary orders1. The contractivity is analysed with respect to arbitrary norms in thes-dimensional space (which are not necessarily generated by an inner product). For given order and stepnumber we construct optimal multistep methods allowing the use of a maximal stepsize.This research has been supported by the Netherlands organisation for scientific research (NWO)     

A 0-stable linear multistep formulas of theα-type

The-type linear multistep formulas are a generalization of the Adams-type formulas. This paper is concerned with completely characterizing theA ₀-stability of thek-step, orderk -type formulas. Specifically, all such formulas of orders 4 or less are identified and it is shown that no-type formulas of order 5 or more exist. These theorems generalize some previous results.     

Calculation of linear bestL p -approximations

In this paper we are concerned with finding theL _p -solution (i.e. minimizing theL _p -norm of the residual vector) to a linear approximation problem or, equivalenty, to an overdetermined system of linear equations. An embedding method is described in which the damped Newton iteration is applied to a series of perturbed problems in order to guarantee convergence and also increase the convergence rate.     

The finite element method with nodes moving along the characteristics for convection-diffusion equations

Summary We examine the convergence properties of the finite element method with nodes moving along the characteristics for one-dimensional convection-diffusion equations. For linear elements, we demonstrate optimal rates of convergence in theL ²,H ¹ andL norms. Both linear and nonlinear problems are considered.This work forms part of the research programme of the Oxford/Reading Institute for Computational Dynamics.     

Solution of nonsymmetric linear complementarity problems by iterative methods

Convergence is established for iterative algorithms for the solution of the nonsymmetric linear complementarity problem of findingz such thatMz+q0,z0,z ^T(Mz+q)=0, whereM is a givenn×n real matrix, not necessarily symmeetric, andq is a givenn-vector. It is first shown that, if the spectral radius of a matrix related toM is less than one, then the iterates generated by the general algorithm converge to a solution of the linear complementarity problem. It turns out that convergence properties are quite similar to those of linear systems of equations. As specific cases, two important classes of matrices, Minkowski matrices and quasi-dominant diagonal matrices, are shown to satisfy this convergence condition.The author is grateful to Professor O. L. Mangasarian and the referees for their substantive suggestions and corrections.     

Algorithms for non-convexS n -games

We considerS-games in which the setS is the parametric curve{(p ₁ (t),, p _n(t)): t [0, 1]} and thep _i(t) are real polynomials. These games will be referred to asS _n -games. Two iterative algorithms are given in the case ofn = 2. One gives linear convergence to an optimal of player I, and the other gives monotone convergence. In the case of arbitraryn we give an algorithm of the cutting plane family converging to the value. The principal features of this algorithm are that the hyperplanes arise intrinsically as tangents to an associated concave function which is not in general differentiable, and the linear subproblems arise as matrix games. Because of the latter property inactive constraints are in principle automatically dropped. We give a game theoretic convergence proof. This algorithm may be used multiply for bounding optimals of player I.     

Acceleration Scheme for Parallel Projected Aggregation Methods for Solving Large Linear Systems

The Projected Aggregation methods generate the new point x ^k+1 as the projection of x ^k onto an aggregate hyperplane usually arising from linear combinations of the hyperplanes defined by the blocks. The aim of this paper is to improve the speed of convergence of a particular kind of them by projecting the directions given by the blocks onto the aggregate hyperplane defined in the last iteration. For that purpose we apply the scheme introduced in A new method for solving large sparse systems of linear equations using row projections [11], for a given block projection algorithm, to some new methods here introduced whose main features are related to the fact that the projections do not need to be accurately computed. Adaptative splitting schemes are applied which take into account the structure and conditioning of the matrix. It is proved that these new highly parallel algorithms improve the original convergence rate and present numerical results which show their computational efficiency.     

Deconvolving a density from contaminated dependent observations

The paper studies the performance of deconvoluting kernel density estimators for estimating the marginal density of a linear process. The data stem from the linear process and are partially, respectively fully contaminated by iid errors with a known distribution. If 1–p denotes the proportion of contaminated observations (and it is, of course, unknown which observations are contaminated and which are not) then for 1–p (0, 1) and under mild conditions almost sure deconvolution rates of orderO(n ^–2/5(logn)^9/10) can be achieved for convergence in . This rate compares well with the existing rates foriid uncontaminated observations. Forp=0 and exponentially decreasing error characteristic function the corresponding rates are of merely logarithmic order. As a by-product the paper also gives a rate of convergence result for the empirical characteristic function in the linear process context and utilizes this to demonstrate that deconvoluting kernel density estimators attain the optimal rate in the dependence case with exponentially decreasing error characteristic function.This work was partially supported by a grant from the Deutsche Forschungsgemeinschaft.     

A parallel algorithm for the eigenvalues and eigenvectors of a general complex matrix

Summary A new parallel Jacobi-like algorithm is developed for computing the eigenvalues of a general complex matrix. Most parallel methods for this problem typically display only linear convergence, Sequential norm-reducing algorithms also exist and they display quadratic convergence in most cases. The new algorithm is a parallel form of the norm-reducing algorithm due to Eberlein. It is proven that the asymptotic convergence rate of this algorithm is quadratic. Numerical experiments are presented which demonstrate the quadratic convergence of the algorithm and certain situations where the convergence is slow are also identified. The algorithm promises to be very competitive on a variety of parallel architectures. In particular, the algorithm can be implemented usingn ²/4 processors, takingO(n log² n) time for random matrices.This research was supported by the Office of Naval Research under Contract N00014-86-k-0610 and by the U.S. Army Research Office under Contract DAAL 03-86-K-0112. A portion of this research was carried out while the author was visiting RIACS, Nasa Ames Research Center     

P-stable andP[α, β]-stable integration/interpolation methods in the solution of retarded differential-difference equations

The equationu(t)=pu(t)+qu(t-) is presented as an archetype (scalar) equation for assessing the quality of integrator/interpolator pairs used to solve retarded differential-difference equations. The relationships ofP-stability andP[, ]-stability, defined with respect to this archetype equation, to stability and order of multistep integrators and to passivity and order of Lagrange interpolators are developed. Composite multistep integrators and composite Lagrange interpolators are considered as a means of obtaining high order pairs stable for all step-sizes over a large portion, if not all, of the (p, q)-domain on which the archetype equation is stable.The research reported herein was supported by grant MCS-7815396 from the National Science Foundation.     

Convergence of intermediate rows of minimal polynomial and reduced rank extrapolation tables

Let {x _m} _m ^=0/ be a vector sequence obtained from a linear fixed point iterative technique in a general inner product space. In two previous papers [6,9] the convergence properties of the minimal polynomial and reduced rank extrapolation methods, as they are applied to the vector sequence above, were analyzed. In particular, asymptotically optimal convergence results pertaining to some of the rows of the tables associated with these two methods were obtained. In the present work we continue this analysis and provide analogous results for the remaining (intermediate) rows of these tables. In particular, when {x _m} _m ^=0/ is a convergent sequence, the main result of this paper says, roughly speaking, that all of the rows converge, and it also gives the rate of convergence for each row. The results are demonstrated numerically through an example.     

Asymptotically efficient autoregressive model selection for multistep prediction

A direct method for multistep prediction of a stationary time series involves fitting, by linear regression, a different autoregression for each lead time, h, and to select the order to be fitted, % MathType!MTEF!2!1!+-% feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXafv3ySLgzGmvETj2BSbqefm0B1jxALjhiov2D% aebbfv3ySLgzGueE0jxyaibaiGc9yrFr0xXdbba91rFfpec8Eeeu0x% Xdbba9frFj0-OqFfea0dXdd9vqaq-JfrVkFHe9pgea0dXdar-Jb9hs% 0dXdbPYxe9vr0-vr0-vqpWqaaeaabiGaaiaacaqabeaadaqaaqGaaO% qaaiqadUgagaacamaaBaaaleaacaWGObaabeaaaaa!3E44!\[\tilde k_h\], from the data. By contrast, a more usual plug-in method involves the least-squares fitting of an initial k-th order autoregression, with k itself selected by an order selection criterion. A bound for the mean squared error of prediction of the direct method is derived and employed for defining an asymptotically efficient order selection for h-step prediction, h > 1; the S _h(k) criterion of Shibata (1980) is asymptotically efficient according to this definition. A bound for the mean squared error of prediction of the plug-in method is also derived and used for a comparison of these two alternative methods of multistep prediction. Examples illustrating the results are given.     

A <Emphasis Type="Italic">V</Emphasis>-cycle Multigrid for multilevel matrix algebras: proof of optimality

We analyze the convergence rate of a multigrid method for multilevel linear systems whose coefficient matrices are generated by a real and nonnegative multivariate polynomial f and belong to multilevel matrix algebras like circulant, tau, Hartley, or are of Toeplitz type. In the case of matrix algebra linear systems, we prove that the convergence rate is independent of the system dimension even in presence of asymptotical ill-conditioning (this happens iff f takes the zero value). More precisely, if the d-level coefficient matrix has partial dimension n _r at level r, with , then the size of the system is , , and O(N(n)) operations are required by the considered V-cycle Multigrid in order to compute the solution within a fixed accuracy. Since the total arithmetic cost is asymptotically equivalent to the one of a matrix-vector product, the proposed method is optimal. Some numerical experiments concerning linear systems arising in 2D and 3D applications are considered and discussed.     

A Petrov‐Galerkin method with quadrature for semi‐linear second‐order hyperbolic problems

We propose and analyze a Crank–Nicolson quadrature Petrov–Galerkin (CNQPG) ‐spline method for solving semi‐linear second‐order hyperbolic initial‐boundary value problems. We prove second‐order convergence in time and optimal order H² norm convergence in space for the CNQPG scheme that requires only linear algebraic solvers. We demonstrate numerically optimal order H^k, k = 0,1,2, norm convergence of the scheme for some test problems with smooth and nonsmooth nonlinearities. © 2006 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2006     

Circle contractive linear multistep methods

Linear multistep methods satisfying a non-linear circle contractivity condition when the step-ratios are less than some 1+,>0, are shown to exist for any order. Methods with formulas of order 1 to 12 are given.     

An Incomplete Function Space

In this paper we construct complete, regular convergence vector spaces E and F such that _c(E,F), the space of all continuous linear mappings from E to F, endowed with the continuous convergence structure, is not complete.     

Quadratically and superlinearly convergent algorithms for the solution of inequality constrained minimization problems

In this paper, some Newton and quasi-Newton algorithms for the solution of inequality constrained minimization problems are considered. All the algorithms described produce sequences {x _k } convergingq-superlinearly to the solution. Furthermore, under mild assumptions, aq-quadratic convergence rate inx is also attained. Other features of these algorithms are that only the solution of linear systems of equations is required at each iteration and that the strict complementarity assumption is never invoked. First, the superlinear or quadratic convergence rate of a Newton-like algorithm is proved. Then, a simpler version of this algorithm is studied, and it is shown that it is superlinearly convergent. Finally, quasi-Newton versions of the previous algorithms are considered and, provided the sequence defined by the algorithms converges, a characterization of superlinear convergence extending the result of Boggs, Tolle, and Wang is given.This research was supported by the National Research Program Metodi di Ottimizzazione per la Decisioni, MURST, Roma, Italy.     

Convergence Analysis of an Infeasible Interior Point Algorithm Based on a Regularized Central Path for Linear Complementarity Problems

Most existing interior-point methods for a linear complementarity problem (LCP) require the existence of a strictly feasible point to guarantee that the iterates are bounded. Based on a regularized central path, we present an infeasible interior-point algorithm for LCPs without requiring the strict feasibility condition. The iterates generated by the algorithm are bounded when the problem is a P _* LCP and has a solution. Moreover, when the problem is a monotone LCP and has a solution, we prove that the convergence rate is globally linear and it achieves `-feasibility and `-complementarity in at most O(n ² ln(1/`)) iterations with a properly chosen starting point.