A New Multisection Technique in Interval Methods for Global Optimization

A new multisection technique in interval methods for global optimization is investigated, and numerical tests demonstrate that the efficiency of the underlying global optimization method can be improved substantially. The heuristic rule is based on experiences that suggest the subdivision of the current subinterval into a larger number of pieces only if it is located in the neighbourhood of a minimizer point. An estimator of the proximity of a subinterval to the region of attraction to a minimizer point is utilized. According to the numerical study made, the new multisection strategies seem to be indispensable, and can improve both the computational and the memory complexity substantially. Received May 31, 1999; revised January 20, 2000     

Derivative Free Inclusion Methods for Polynomial Zeros

Two iterative methods for the simultaneous inclusion of complex zeros of a polynomial are presented. Both methods are realized in circular interval arithmetic and do not use polynomial derivatives. The first method of the fourth order is composed as a combination of interval methods with the order of convergence two and three. The second method is constructed using double application of the inclusion method of Weierstrass’ type in serial mode. It is shown that its R-order of convergence is bounded below by the spectral radius of the corresponding matrix. Numerical examples illustrate the convergence rate of the presented methods     

Weierstrass-like Methods with Corrections for the Inclusion of Polynomial Zeros

In this paper, we present iterative methods of Weierstress’ type for the simultaneous inclusion of all simple zeros of a polynomial. The main advantage of the proposed methods is the increase of the convergence rate attained by applying suitable correction terms. Using the concept of the R-order of convergence of mutually dependent sequences, we present the convergence analysis for the total-step and the single-step methods. Numerical examples are given.     

Iterative Methods for Linear Complementarity Problems with Interval Data

A ] and an interval vector [b]. If all A∈[A] are H-matrices with positive diagonal elements, these methods are all convergent to the same interval vector [x ^*]. This interval vector includes the solution x of the linear complementarity problem defined by any fixed A∈[A] and any fixed b∈[b]. If all A∈[A] are M-matrices, then we will show, that [x ^*] is optimal in a precisely defined sense. We also consider modifications of those methods, which under certain assumptions on the starting vector deliver nested sequences converging to [x ^*]. We close our paper with some examples which illustrate our theoretical results. Received October 7, 2002; revised April 15, 2003 Published online: June 23, 2003 RID="*" ID="*" Dedicated to U. Kulisch on the occasion of his 70th birthday. We are grateful to the referee who has given a series of valuable comments.     

Validation and enclosure of solutions of linear complementarity problems

An inclusion condition is presented to guarantee the existence of the solution of the linear complementarity problem in a given domain. The condition can be tested numerically with very small computational cost. Based on the condition algorithms are designed to compute an interval to enclose the unknown solution. Numerical results are reported to support the theoretical analysis in the paper.     

A Refined Finite Element Convergence Theory for Highly Indefinite Helmholtz Problems

It is well known that standard h-version finite element discretisations using lowest order elements for Helmholtz' equation suffer from the following stability condition: ``The mesh width h of the finite element mesh has to satisfy k <sup>2</sup> h≲1', where k denotes the wave number. This condition rules out the reliable numerical solution of Helmholtz equation in three dimensions for large wave numbers k≳50. In our paper, we will present a refined finite element theory for highly indefinite Helmholtz problems where the stability of the discretisation can be checked through an ``almost invariance' condition. As an application, we will consider a one-dimensional finite element space for the Helmholtz equation and apply our theory to prove stability under the weakened condition hk≲1 and optimal convergence estimates. Dedicated to Prof. Dr. Ivo Babuška on the occasion of his 80th birthday.     

Superconvergence of a Mixed Covolume Method for Elliptic Problems

We consider a mixed covolume method for a system of first order partial differential equations resulting from the mixed formulation of a general self-adjoint elliptic problem with a variable full diffusion tensor. The system can be used to model the transport of a contaminant carried by a flow. We use the lowest order Raviart-Thomas mixed finite element space. We show the first order convergence in L ² norm and the superconvergence in certain discrete norms both for the pressure and velocity. Finally some numerical examples illustrating the error behavior of the scheme are provided. Supported by the National Natural Science Foundation of China under grant No. 10071044 and the Research Fund of Doctoral Program of High Education by State Education Ministry of China.     

On the Quadratic Convergence of the Levenberg-Marquardt Method without Nonsingularity Assumption

Recently, Yamashita and Fukushima [11] established an interesting quadratic convergence result for the Levenberg-Marquardt method without the nonsingularity assumption. This paper extends the result of Yamashita and Fukushima by using _k=||F(x_k)||, where [1,2], instead of _k=||F(x_k)||² as the Levenberg-Marquardt parameter. If ||F(x)|| provides a local error bound for the system of nonlinear equations F(x)=0, it is shown that the sequence {x_k} generated by the new method converges to a solution quadratically, which is stronger than dist(x_k,X^*)0 given by Yamashita and Fukushima. Numerical results show that the method performs well for singular problems.     

Blending Set and Interval Arithmetic for Maximal Reliability

In both [3] and [8], the authors review the implementation of the basic operations in interval arithmetic, and in particular discuss the different approaches given in the literature for interval division when the divisor interval contains zero. In these papers, and in the references therein, the basic operations are defined for real or extended real interval operands.Division by an interval containing zero is a special case of an interval function for which the input arguments contain points outside the domain of the underlying point function. A number of approaches exist in the literature, [7], [12], to remove restrictions on the domain of interval functions and hence obtain a closed, exception-free interval system.In this paper, we present an alternative approach to remove restrictions on the domain of interval functions and to guarantee the inclusion property in all situations, even when some input intervals contain points that lie outside the domain of the underlying point function. To achieve this, we allow for the (efficient) set-based representation of non-real results. The computed intervals are sharp, yet contain more information and the resulting interval system is closed and exception-free. We also show how the presented ideas can be implemented in an interval arithmetic library. The performance overhead is negligible compared to the fact that the implementation using the new approach offers 100% reliability in return.The structure of the paper is as follows. We set off with a motivating example in Sect. 1. In Sect. 2, we review various approaches to interval division and then introduce vset-division of real intervals, based on the newly introduced concept of value set or vset. In Sect. 3, we give a formal definition of real vset-intervals and arithmetic on these intervals. We prove a number of essential properties and point out the likenesses and differences with other approaches. Finally, in Sect. 4, we discuss the implementation of vset-interval arithmetic in a floating-point context.Research assistant FWO Vlaanderen.     

Reliable Approximation of Weight Factors Entering Residual-based Error Bounds for FE-discretisations

In this note we refine strategies of the so called dual-weighted-residual (DWR) approach to a posteriori error control for FE-schemes. We derive rigorous error bounds, especially we control the approximation process of the (unknown) dual solution entering the proposed estimate.     

On the Stability of the Direct Elimination Method for Equality Constrained Least Squares Problems

A backward error analysis of the direct elimination method for linear equality constrained least squares problems is presented. It is proved that the solution computed by the method is the exact solution of a perturbed problem and bounds for data perturbations are given. The numerical stability of the method is related to the way in which the constraints are used to eliminate variables and these theoretical conclusions are confirmed by a numerical example. Received February 15, 1999; revised December 10, 1999     

Composite Finite Elements for Elliptic Boundary Value Problems with Discontinuous Coefficients

In this paper, we will introduce composite finite elements for solving elliptic boundary value problems with discontinuous coefficients. The focus is on problems where the geometry of the interfaces between the smooth regions of the coefficients is very complicated. On the other hand, efficient numerical methods such as, e.g., multigrid methods, wavelets, extrapolation, are based on a multi-scale discretization of the problem. In standard finite element methods, the grids have to resolve the structure of the discontinuous coefficients. Thus, straightforward coarse scale discretizations of problems with complicated coefficient jumps are not obvious. In this paper, we define composite finite elements for problems with discontinuous coefficients. These finite elements allow the coarsening of finite element spaces independently of the structure of the discontinuous coefficients. Thus, the multigrid method can be applied to solve the linear system on the fine scale. We focus on the construction of the composite finite elements and the efficient, hierarchical realization of the intergrid transfer operators. Finally, we present some numerical results for the multigrid method based on the composite finite elements (CFE–MG).     

Multilevel Stabilization of Convection–Diffusion Problems by Variable-Order Inner Products

We are concerned with the task of stabilizing discrete approximations to convection–diffusion problems. We propose to consistently modify the exact variational formulation of the problem by adding a fractional order inner product, involving the residual of the equation. The inner product is expressed through a multilevel decomposition of its arguments, in terms of components along a multiscale basis. The order of the inner product locally varies from −1/2 to −1, depending on the value of a suitably-defined multiscale Péclet number. Numerical approximations obtained via the Galerkin method applied to the modified formulation are analyzed. Received January 1, 2000; revised November 2, 2000     

A lipschitz operator for function strips

For function strips defined by an arithmetic interval expression, Lipschitz operators are constructed.

---

Ein Lipschitz-Operator für Funktionsstreifen

Zusammenfassung Für Funktionsstreifen, welche durch einen arithmetischen Intervallausdruck definiert sind, werden zugeordnete Lipschitzoperatoren konstruiert.

     

A review of some a posteriori error estimates for adaptive finite element methods

Recently, the adaptive finite element methods have gained a very important position among numerical procedures for solving ordinary as well as partial differential equations arising from various technical applications. While the classical a posteriori error estimates are oriented to the use in h-methods the contemporary higher order hp-methods usually require new approaches in a posteriori error estimation.     

Implementations of a New Theorem for Computing Bounds for Positive Roots of Polynomials

Finding an upper bound for the positive roots of univariate polynomials is an important step of the continued fractions real root isolation algorithm. The revived interest in this algorithm has highlighted the need for better estimations of upper bounds of positive roots. In this paper we present a new theorem, based on a generalization of a theorem by D. Stefanescu, and describe several implementations of it – including Cauchy's and Kioustelidis' rules as well as two new rules recently developed by us. From the empirical results presented here we see that applying various implementations of our theorem – and taking the minimum of the computed values – greatly improves the estimation of the upper bound and hopefully that will affect the performance of the continued fractions real root isolation method.     

An Optimal Algorithm for Bound and Equality Constrained Quadratic Programming Problems with Bounded Spectrum

An implementation of the recently proposed semi-monotonic augmented Lagrangian algorithm for solving the large convex bound and equality constrained quadratic programming problems is considered. It is proved that if the algorithm is applied to the class of problems with uniformly bounded spectrum of the Hessian matrix, then the algorithm finds an approximate solution at O(1) matrix-vector multiplications. The optimality results are presented that do not depend on conditioning of the matrix which defines the equality constraints. Theory covers also the problems with dependent constraints. Theoretical results are illustrated by numerical experiments.     

A New Well-Solvable Class of PNS Problems

A manufacturing system consists of operating units which convert their input materials into their output materials. In the problem of designing a process network, we have to find a suitable network of operating units which produces the desired products from the given raw materials. If we consider this process network design problem from a structural point of view, then we obtain a combinatorial optimization problem called the Process Network Synthesis or (PNS) problem. It is known that the PNS problem is NP-complete. Here, a new method is presented to reduce the solution of some more difficult PNS problems to the solution of simpler ones, and using this method, a new well-solvable class of PNS problems is established. Received February 12, 1999; revised October 24, 2000     

Simulated Annealing for Fitting Linear Combinations of Gaussians to Data

 It is difficult to find a good fit of a combination of Gaussians to arbitrary empirical data. The surface defined by the objective function contains many local minima, which trap gradient descent algorithms and cause stochastic methods to tarry unreasonably in the vicinity. A number of techniques for accelerating convergence when using simulated annealing are presented. These are tested on a sample of known Gaussian combinations and are compared for accuracy and resource consumption. A single `best' set of techniques is found which gives good results on the test samples and on empirical data. Received September 27, 1999; revised March 13, 2000     

A Domain Decomposition Preconditioner for p-FEM Discretizations of Two-dimensional Elliptic Problems

In this paper, a uniformly elliptic second order boundary value problem in 2-D discretized by the p-version of the finite element method is considered. An inexact Dirichlet-Dirichlet domain decomposition pre-conditioner for the system of linear algebraic equations is investigated. Two solvers for the problem in the sub-domains, a pre-conditioner for the Schur-complement and an extension operator operating from the edges of the elements into the interior are proposed as ingredients for the inexact DD-pre-conditioner. In the main part of the paper, several numerical experiments on a parallel computer are given.