An interval branch and bound algorithm for bound constrained optimization problems

In this paper, we propose modifications to a prototypical branch and bound algorithm for nonlinear optimization so that the algorithm efficiently handles constrained problems with constant bound constraints. The modifications involve treating subregions of the boundary identically to interior regions during the branch and bound process, but using reduced gradients for the interval Newton method. The modifications also involve preconditioners for the interval Gauss-Seidel method which are optimal in the sense that their application selectively gives a coordinate bound of minimum width, a coordinate bound whose left endpoint is as large as possible, or a coordinate bound whose right endpoint is as small as possible. We give experimental results on a selection of problems with different properties.     

Parallel interval multisplittings

Summary We introduce interval multisplittings to enclose the setS={A^–1b|A[A], b[b]}, where [A] denotes an interval matrix and [b] an interval vector. The resulting iterative multisplitting methods have a natural parallelism. We investigate these methods with respect to convergence, speed of convergence and quality of the resulting enclosure forS.Dedicated to the memory of Peter Henrici     

Error analysis of a pairwise summation algorithm to compute the sample variance

Summary We give an error analysis of an algorithm for computing the sample variance due to Chan, Golub, and LeVeque [The American Statistician 7 (1983), pp. 242–247]. It is shown that this algorithm is numerically stable. The algorithm computes the sample variance (and the sample mean) using just one pass through the sample data. It is amenable to pairwise summation and thus requires onlyO(logn) parallel steps.Research supported by the Air Force Office of Scientific Research under grant no. AFOSR-88-0161 and by the Office of Naval Research under grant no. N00024-85-C-6041     

Numerical analysis of oscillations in nonconvex problems

Summary We study numerically the pattern of the minimizing sequences of nonconvex problems which do not admit a minimizer.     

Towards a computer-assisted proof for chaos in a forced damped pendulum equation

We report on the first steps made towards the computational proof of the chaotic behaviour of the forced damped pendulum. Although, chaos for this pendulum was being conjectured for long, and it has been plausible on the basis of numerical simulations, there is no rigorous proof for it. In the present paper we provide computational details on a fitting model and on a verified method of solution. We also give guaranteed reliability solutions showing some trajectory properties necessary for complicate chaotic behaviour.     

Componentwise inclusion and exclusion sets for solutions of quadratic equations in finite dimensional spaces

Summary In this paper we use interval arithmetic tools for the computation of componentwise inclusion and exclusion sets for solutions of quadratic equations in finite dimensional spaces. We define a mapping for which under certain assumptions we can construct an interval vector which is mapped into itself. Using Brouwer's fixed point theorem we conclude the existence of a solution of the original equation in this interval vector. Under different assumptions we can construct an interval vector such that the range of the mapping has no point in common with this interval vector. This implies that there is no solution in this interval vector. Furthermore we consider an iteration method which improves componentwise errorbounds for a solution of a quadratic. The theoretical results of this paper are demonstrated by some numerical examples using the algebraic eigenvalue problem which is probably the best known example of a quadratic equation.This paper contains the main results of a talk given by the author on the occasion of the 25th anniversary of the founding of Numerische Mathematik, March 19–21, 1984 at the Technische Universität of Munich, Germany     

On a theorem of Stein-Rosenberg type in interval analysis

Summary In classical numerical analysis the asymptotic convergence factor (R ₁-factor) of an iterative processx ^m+1=Ax^m+b coincides with the spectral radius of then×n iteration matrixA. Thus the famous Theorem of Stein and Rosenberg can at least be partly reformulated in terms of asymptotic convergence factor. Forn×n interval matricesA with irreducible upper bound and nonnegative lower bound we compare the asymptotic convergence factor ( _T ) of the total step method in interval analysis with the factor _S of the corresponding single step method. We derive a result similar to that of the Theorem of Stein and Rosenberg. Furthermore we show that _S can be less than the spectral radius of the real single step matrix corresponding to the total step matrix |A| where |A| is the absolute value ofA. This answers an old question in interval analysis.     

Spectral approximation of the periodic-nonperiodic Navier-Stokes equations

Summary In order to approximate the Navier-Stokes equations with periodic boundary conditions in two directions and a no-slip boundary condition in the third direction by spectral methods, we justify by theoretical arguments an appropriate choice of discrete spaces for the velocity and the pressure. The compatibility between these two spaces is checked via an infsup condition. We analyze a spectral and a collocation pseudo-spectral method for the Stokes problem and a collocation pseudo-spectral method for the Navier-Stokes equations. We derive error bounds of spectral type, i.e. which behave likeM ^– whereM depends on the number of degrees of freedom of the method and represents the regularity of the data.     

On regular and singular interval systems

We give a survey on interval linear systems discussing problems for regular systems as well as for singular ones. We consider several solution sets and direct methods to enclose them. Moreover we study iterative methods, particularly the total step method as the basis for other ones. We also use this method for enclosing solutions of singular linear systems.     

A multidomain spectral collocation method for the Stokes problem

Summary We propose a multidomain spectral collocation scheme for the approximation of the two-dimensional Stokes problem. We show that the discrete velocity vector field is exactly divergence-free and we prove error estimates both for the velocity and the pressure.Deceased     

Numerical methods for reaction-diffusion problems with non-differentiable kinetics

Summary We consider a class of steady-state semilinear reaction-diffusion problems with non-differentiable kinetics. The analytical properties of these problems have received considerable attention in the literature. We take a first step in analyzing their numerical approximation. We present a finite element method and establish error bounds which are optimal for some of the problems. In addition, we also discuss a finite difference approach. Numerical experiments for one- and two-dimensional problems are reported.Dedicated to Ivo Babuka on his sixtieth birthdayResearch partially supported by the Air Force Office of Scientific Research, Air Force Systems Command, USAF under Grant Number AFOSR 85-0322     

A class of iterative methods for solving saddle point problems

Summary We consider the numerical solution of indefinite systems of linear equations arising in the calculation of saddle points. We are mainly concerned with sparse systems of this type resulting from certain discretizations of partial differential equations. We present an iterative method involving two levels of iteration, similar in some respects to the Uzawa algorithm. We relate the rates of convergence of the outer and inner iterations, proving that, under natural hypotheses, the outer iteration achieves the rate of convergence of the inner iteration. The technique is applied to finite element approximations of the Stokes equations.The work of this author was supported by the Office of Naval Research under contract N00014-82K-0197, by Avions Marcel Dassault, 78 Quai Marcel Dassault, 92214 St Cloud, France, and by Direction des Recherches Etudes et Techniques, 26 boulevard Victor, F-75996 Paris Armées, FranceThe work of this author was supported by Avions Marcel Daussault-Breguet Aviation, 78 quai Marcel Daussault, F-92214 St Cloud, France and by Direction des Recherches Etudes et Techniques, 26 boulevard Victor, F-75996 Paris Armées, FranceThe work of this author was supported by Konrad-Zuse-Zentrum für Informationstechnik Berlin, Federal Republic of Germany     

The serial test for pseudo-random numbers generated by the linear congruential method

Summary We consider the linear congruential method for pseudo-random number generation and establish effective criteria for the choice of parameters in this method which guarantee statistical almost-independence of successive pseudo-random numbers. Applications to numerical integration are also discussed.     

Domain imbedding methods for the Stokes equations

Summary We study direct and iterative domain imbedding methods for the Stokes equations on certain non-rectangular domains in two space dimensions. We analyze a continuous analog of numerical domain imbedding for bounded, smooth domains, and give an example of a simple numerical algorithm suggested by the continuous analysis. This algorithms is applicable for simply connected domains which can be covered by rectangular grids, with uniformly spaced grid lines in at least one coordinate direction. We also discuss a related FFT-based fast solver for Stokes problems with physical boundary conditions on rectangles, and present some numerical results.     

Convergence and order reduction of Runge-Kutta schemes applied to evolutionary problems in partial differential equations

Summary We address the question of convergence of fully discrete Runge-Kutta approximations. We prove that, under certain conditions, the order in time of the fully discrete scheme equals the conventional order of the Runge-Kutta formula being used. However, these conditions, which are necessary for the result to hold, are not natural. As a result, in many problems the order in time will be strictly smaller than the conventional one, a phenomenon called order reduction. This phenomenon is extensively discussed, both analytically and numerically. As distinct from earlier contributions we here treat explicit Runge-Kutta schemes. Although our results are valid for both parabolic and hyperbolic problems, the examples we present are therefore taken from the hyperbolic field, as it is in this area that explicit discretizations are most appealing.     

Rehabilitation of the Gauss-Jordan algorithm

Summary In this paper a Gauss-Jordan algorithm with column interchanges is presented and analysed. We show that, in contrast with Gaussian elimination, the Gauss-Jordan algorithm has essentially differing properties when using column interchanges instead of row interchanges for improving the numerical stability. For solutions obtained by Gauss-Jordan with column interchanges, a more satisfactory bound for the residual norm can be given. The analysis gives theoretical evidence that the algorithm yields numerical solutions as good as those obtained by Gaussian elimination and that, in most practical situations, the residuals are equally small. This is confirmed by numerical experiments. Moreover, timing experiments on a Cyber 205 vector computer show that the algorithm presented has good vectorisation properties.     

On generalized successive overrelaxation methods for augmented linear systems

For the augmented system of linear equations, Golub, Wu and Yuan recently studied an SOR-like method (BIT 41(2001)71–85). By further accelerating it with another parameter, in this paper we present a generalized SOR (GSOR) method for the augmented linear system. We prove its convergence under suitable restrictions on the iteration parameters, and determine its optimal iteration parameters and the corresponding optimal convergence factor. Theoretical analyses show that the GSOR method has faster asymptotic convergence rate than the SOR-like method. Also numerical results show that the GSOR method is more effective than the SOR-like method when they are applied to solve the augmented linear system. This GSOR method is further generalized to obtain a framework of the relaxed splitting iterative methods for solving both symmetric and nonsymmetric augmented linear systems by using the techniques of vector extrapolation, matrix relaxation and inexact iteration. Besides, we also demonstrate a complete version about the convergence theory of the SOR-like method. Subsidized by The Special Funds For Major State Basic Research Projects (No. G1999032803) and The National Natural Science Foundation (No. 10471146), P.R. China     

Accuracy and stability of multistage multistep formulas

Summary We continue our research concerning relations between accuracy and stability of time discretizations. Here we concentrate, rather than on the size and shape of the stability region, on the obtainable accuracy when the number of parameters in the formulas is large.     

A generalization of the schwarz alternating method to an arbitrary number of subdomains

Summary We give a generalization of the Schwarz alternating method to an arbitrary number of subdomains. As applications, we prove that the method converges for the main second-order boundary value problems, as well as for the system of linear elasticity.For the Dirichlet problems it is proved that the method converges geometrically and some numerical examples are given.     

A convergence analysis of hopscotch methods for fourth order parabolic equations

Summary Consider the ODE (ordinary differential equation) that arises from a semi-discretization (discretization of the spatial coordinates) of a first order system form of a fourth order parabolic PDE (partial differential equation). We analyse the stability of the finite difference methods for this fourth order parabolic PDE that arise if one applies the hopscotch idea to this ODE.Often the error propagation of these methods can be represented by a three terms matrix-vector recursion in which the matrices have a certain anti-hermitian structure. We find a (uniform) expression for the stability bound (or error propagation bound) of this recursion in terms of the norms of the matrices. This result yields conditions under which these methods are strongly asymptotically stable (i.e. the stability is uniform both with respect to the spatial and the time stepsizes (tending to 0) and the time level (tending to infinity)), also in case the PDE has (spatial) variable coefficients. A convergence theorem follows immediately.