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.     

A new family of symmetric linear four-step methods for the efficient integration of the Schrödinger equation and related oscillatory problems

In this article we develop a family of three explicit symmetric linear four-step methods. The new methods, with nullified phase-lag, are optimized for the efficient solution of the Schrödinger equation and related oscillatory problems. We perform an analysis of the local truncation error of the methods for the general case and for the special case of the Schrödinger equation, where we show the decrease of the maximum power of the energy in relation to the corresponding classical methods. We also perform a periodicity analysis, where we find that there is a direct relationship between the periodicity intervals of the methods and their local truncation errors. In addition we determine their periodicity regions. We finally compare the new methods to the corresponding classical ones and other known methods from the literature, where we show the high efficiency of the new methods.     

Iterative algorithms for large partitioned linear systems,with applications to image reconstruction

We present a unifying framework for a wide class of iterative methods in numerical linear algebra. In particular, the class of algorithms contains Kaczmarz's and Richardson's methods for the regularized weighted least squares problem with weighted norm. The convergence theory for this class of algorithms yields as corollaries the usual convergence conditions for Kaczmarz's and Richardson's methods. The algorithms in the class may be characterized as being group-iterative, and incorporate relaxation matrices, as opposed to a single relaxation parameter. We show that some well-known iterative methods of image reconstruction fall into the class of algorithms under consideration, and are thus covered by the convergence theory. We also describe a novel application to truly three-dimensional image reconstruction.     

On the pursuit problem for linear differential games with distinct constraints on the players’ controls

Pontryagin’s first and second (direct) methods and the so-called third pursuit method are the basic methods of the theory of differential games. We present various modifications of these methods. We analyze linear differential pursuit games for a delay equation under distinct constraints on the players’ control parameters. We give sufficient conditions for the solvability of the pursuit problem in finite time.     

On the Riemannian Geometry Defined by Self-Concordant Barriers and Interior-Point Methods

Abstract. We consider the Riemannian geometry defined on a convex set by the Hessian of a self-concordant barrier function, and its associated geodesic curves. These provide guidance for the construction of efficient interior-point methods for optimizing a linear function over the intersection of the set with an affine manifold. We show that algorithms that follow the primal—dual central path are in some sense close to optimal. The same is true for methods that follow the shifted primal—dual central path among certain infeasible-interior-point methods. We also compute the geodesics in several simple sets.     

On algebraic multi-level methods for non-symmetric systems - Comparison results

We establish theoretical comparison results for algebraic multi-level methods applied to non-singular non-symmetric M-matrices. We consider two types of multi-level approximate block factorizations or AMG methods, the AMLI and the MAMLI method. We compare the spectral radii of the iteration matrices of these methods. This comparison shows, that the spectral radius of the MAMLI method is less than or equal to the spectral radius of the AMLI method. Moreover, we establish how the quality of the approximations in the block factorization effects the spectral radii of the iteration matrices. We prove comparisons results for different approximations of the fine grid block as well as for the used Schur complement. We also establish a theoretical comparison between the AMG methods and the classical block Jacobi and block Gauss-Seidel methods.     

Variational iteration technique for solving nonlinear equations

In this paper, we use the variational iteration technique to suggest some new iterative methods for solving nonlinear equations f(x)=0. We also discuss the convergence criteria of these new iterative methods. Comparison with other similar methods is also given. These new methods can be considered as an alternative to the Newton method. We also give several examples to illustrate the efficiency of these methods. This technique can be used to suggest a wide class of new iterative methods for solving system of nonlinear equations.     

Economical Iterative Algorithms for Solving Stationary Problems of Mathematical Physics

We construct and investigate additive iterative methods of complete approximation for solving stationary problems of mathematical physics. We prove the convergence of the proposed methods and obtain error estimates without the requirement of commutativity of the decomposition operators. We provide the results of a computational experiment for a three-dimensional boundary-value problem. We consider possible generalizations of algorithms for equations with mixed derivatives and Navier–Stokes equation systems.     

Third order iterative methods free from second derivative for nonlinear systems

In this work we present a family of predictor-corrector methods free from second derivative for solving nonlinear systems. We prove that the methods of this family are of third order convergence. We also perform numerical tests that allow us to compare these methods with Newton’s method. In addition, the numerical examples improve theoretical results, showing super cubic convergence for some methods of this family.     

Singly-implicit stabilized extended one-step methods for second-order initial-value problems with oscillating solutions

We introduce a new class of singly-implicit extended one-step methods for the numerical integration of second-order initial-value problems y″ = f(t, y), y(t₀) = η₀, y′(t₀) = η₁, with oscillating solutions. We first show that for third order, with two stages there exists a uniquely determined ‘almost’ P-stable method. We then investigate stability of the general class of fourth-order one-step methods. We first look for stabilized fourth-order methods with two stages, and show the interesting result that there exist families of two-stage fourth-order P-stable methods. We also obtain some families of three-stage fourth-order P-stable methods. The obtained methods are computationally tested on problems of practical interest.     

Iterative regularization with minimum-residual methods

We study the regularization properties of iterative minimum-residual methods applied to discrete ill-posed problems. In these methods, the projection onto the underlying Krylov subspace acts as a regularizer, and the emphasis of this work is on the role played by the basis vectors of these Krylov subspaces. We provide a combination of theory and numerical examples, and our analysis confirms the experience that MINRES and MR-II can work as general regularization methods. We also demonstrate theoretically and experimentally that the same is not true, in general, for GMRES and RRGMRES – their success as regularization methods is highly problem dependent. AMS subject classification (2000)  65F22, 65F10     

Exponentially-fitted methods and their stability functions

We investigate the properties of stability functions of exponentially-fitted Runge–Kutta methods, and we show that it is possible (to some extent) to determine the stability function of a method without actually constructing the method itself. To focus attention, examples are given for the case of one-stage methods. We also make the connection with so-called integrating factor methods and exponential collocation methods. Various approaches are given to construct these methods.     

Clustering and classification based on the L1 data depth

Clustering and classification are important tasks for the analysis of microarray gene expression data. Classification of tissue samples can be a valuable diagnostic tool for diseases such as cancer. Clustering samples or experiments may lead to the discovery of subclasses of diseases. Clustering genes can help identify groups of genes that respond similarly to a set of experimental conditions. We also need validation tools for clustering and classification. Here, we focus on the identification of outliers—units that may have been misallocated, or mislabeled, or are not representative of the classes or clusters.We present two new methods: DDclust and DDclass, for clustering and classification. These non-parametric methods are based on the intuitively simple concept of data depth. We apply the methods to several gene expression and simulated data sets. We also discuss a convenient visualization and validation tool—the relative data depth plot.     

Efficient high-order methods based on golden ratio for nonlinear systems

We derive new iterative methods with order of convergence four or higher, for solving nonlinear systems, by composing iteratively golden ratio methods with a modified Newton’s method. We use different efficiency indices in order to compare the new methods with other ones and present several numerical tests which confirm the theoretical results.     

A comparative study of efficient iterative solvers for generalized Stokes equations

We consider a generalized Stokes equation with problem parameters ξ?0 (size of the reaction term) and ν>0 (size of the diffusion term). We apply a standard finite element method for discretization. The main topic of the paper is a study of efficient iterative solvers for the resulting discrete saddle point problem. We investigate a coupled multigrid method with Braess–Sarazin and Vanka‐type smoothers, a preconditioned MINRES method and an inexact Uzawa method. We present a comparative study of these methods. An important issue is the dependence of the rate of convergence of these methods on the mesh size parameter and on the problem parameters ξ and ν. We give an overview of the main theoretical convergence results known for these methods. For a three‐dimensional problem, discretized by the Hood–Taylor ??₂–??₁ pair, we give results of numerical experiments. Copyright © 2007 John Wiley & Sons, Ltd.     

Coaxing a planar curve to comply

A long-standing problem in computer graphics is to find a planar curve that is shaped the way you want it to be shaped. A selection of various methods for achieving this goal is presented. The focus is on mathematical conditions that we can use to control curves while still allowing the curves some freedom. We start with methods invented by Newton (1643–1727) and Lagrange (1736–1813) and proceed to recent methods that are the subject of current research. We illustrate almost all the methods discussed with diagrams. Three methods of control that are of special interest are interpolation methods, global minimization methods (such as least squares), and (Bézier) control points. We concentrate on the first of these, interpolation methods.     

Proximal-type methods with generalized Bregman functions and applications to generalized fractional programming

We analyse proximal-type minimization methods with generalized Bregman functions by considering a general scheme based on the one studied by Kiwiel [K.C. Kiwiel, Proximal minimization methods with generalized Bregman functions, SIAM J. Control Optim. 35(4) (1997), pp. 1142–1168.] and on successive approximation methods. We apply this scheme to construct methods for generalized fractional programmes.     

New fifth‐order two‐derivative Runge‐Kutta methods with constant and frequency‐dependent coefficients

Two‐derivative Runge‐Kutta methods are Runge‐Kutta methods for problems of the form y′ = f(y) that include the second derivative y′′ = g(y) = f ′(y)f(y) and were developed in the work of Chan and Tsai. In this work, we consider explicit methods and construct a family of fifth‐order methods with three stages of the general case that use several evaluations of f and g per step. For problems with oscillatory solution and in the case that a good estimate of the dominant frequency is known, methods with frequency‐dependent coefficients are used; there are several procedures for constructing such methods. We give the general framework for the construction of methods with variable coefficients following the approach of Simos. We modify the above family to derive methods with frequency‐dependent coefficients following this approach as well as the approach given by Vanden Berghe. We provide numerical results to demonstrate the efficiency of the new methods using three test problems.     

Convergence of nested classical iterative methods for linear systems

Summary Classical iterative methods for the solution of algebraic linear systems of equations proceed by solving at each step a simpler system of equations. When this system is itself solved by an (inner) iterative method, the global method is called a two-stage iterative method. If this process is repeated, then the resulting method is called a nested iterative method. We study the convergence of such methods and present conditions on the splittings corresponding to the iterative methods to guarantee convergence forany number of inner iterations. We also show that under the conditions presented, the spectral radii of the global iteration matrices decrease when the number of inner iterations increases. The proof uses a new comparison theorem for weak regular splittings. We extend our results to larger classes of iterative methods, which include iterative block Gauss-Seidel. We develop a theory for the concatenation of such iterative methods. This concatenation appears when different numbers of inner interations are performed at each outer step. We also analyze block methods, where different numbers of inner iterations are performed for different diagonal blocks.Dedicated to Richard S. Varga on the occasion of his sixtieth birthdayP.J. Lanzkron was supported by Exxon Foundation Educational grant 12663 and the UNISYS Corporation; D.J. Rose was supported by AT&T Bell Laboratories, the Microelectronic Center of North Carolina and the Office of Naval Research under contract number N00014-85-K-0487; D.B. Szyld was supported by the National Science Foundation grant DMS-8807338.     

When can we improve on sample average approximation for stochastic optimization?

We explore the performance of sample average approximation in comparison with several other methods for stochastic optimization. The methods we evaluate are (a) bagging; (b) kernel density estimation; (c) maximum likelihood estimation; and (d) a Bayesian approach. We use two test sets: first a set of quadratic objective functions allowing different types of interaction between the random component and the univariate decision variable; and second a set of portfolio optimization problems. We make recommendations for effective approaches.