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.     

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.     

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.     

Dimension–Adaptive Tensor–Product Quadrature

We consider the numerical integration of multivariate functions defined over the unit hypercube. Here, we especially address the high–dimensional case, where in general the curse of dimension is encountered. Due to the concentration of measure phenomenon, such functions can often be well approximated by sums of lower–dimensional terms. The problem, however, is to find a good expansion given little knowledge of the integrand itself. The dimension–adaptive quadrature method which is developed and presented in this paper aims to find such an expansion automatically. It is based on the sparse grid method which has been shown to give good results for low- and moderate–dimensional problems. The dimension–adaptive quadrature method tries to find important dimensions and adaptively refines in this respect guided by suitable error estimators. This leads to an approach which is based on generalized sparse grid index sets. We propose efficient data structures for the storage and traversal of the index sets and discuss an efficient implementation of the algorithm. The performance of the method is illustrated by several numerical examples from computational physics and finance where dimension reduction is obtained from the Brownian bridge discretization of the underlying stochastic process.     

Regularization methods for a problem of analytic continuation

In this paper, we prove a sharp stability estimate for the problem of analytic continuation. Based on the obtained stability estimate, a generalized Tikhonov regularization is provided and the corresponding error estimate is obtained. Moreover, we give many other regularization methods. For illustration, a numerical experiment is constructed to demonstrate the feasibility and efficiency of the proposed method.     

PHoMpara – Parallel Implementation of the Polyhedral Homotopy Continuation Method for Polynomial Systems

The polyhedral homotopy continuation method is known to be a successful method for finding all isolated solutions of a system of polynomial equations. PHoM, an implementation of the method in C++, finds all isolated solutions of a polynomial system by constructing a family of modified polyhedral homotopy functions, tracing the solution curves of the homotopy equations, and verifying the obtained solutions. A software package PHoMpara parallelizes PHoM to solve a polynomial system of large size. Many characteristics of the polyhedral homotopy continuation method make parallel implementation efficient and provide excellent scalability. Numerical results include some large polynomial systems that had not been solved.     

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     

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     

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.     

Application of the Polynomial Chaos Expansion to the simulation of chemical reactors with uncertainties

In this paper we consider the simulation of probabilistic chemical reactions in isothermal and adiabatic conditions. Models for reactions under isothermal conditions result in advection equations, adiabatic conditions yield the reactive Euler equations. In order to treat with scattering data, the equations are projected onto the polynomial chaos space. Scattering data can largely affect the estimation of quantities in the system, including variable optimization. This is demonstrated on a selective non-catalytic reduction of nitric oxide.     

Halley-Like Method with Corrections for the Inclusion of Polynomial Zeros

In this paper we present iteration methods of Halley's type for the simultaneous inclusion of all zeros of a polynomial. 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 with Newton's corrections. The suggested algorithms possess a great computational efficiency since the increase of the convergence rate is attained without additional calculations. A numerical example is given. Received: June 23, 1998     

A closed-form expression for the quantile function of the Gompertz–Makeham distribution

In this note, we give a closed-form expression in terms of the Lambert W function for the quantile function of the Gompertz–Makeham distribution. This probability distribution has frequently been used to describe human mortality and to establish actuarial tables. The analytical expression provided for the quantile function is helpful to generate random samples drawn from the Gompertz–Makeham distribution by means of the inverse transform method.     

Solution of Polynomial Systems Derived from Differential Equations

Nonlinear two-point boundary value problems arise in numerous areas of application. The existence and number of solutions for various cases has been studied from a theoretical standpoint. These results generally rely upon growth conditions of the nonlinearity. However, in general, one cannot forecast how many solutions a boundary value problem may possess or even determine the existence of a solution. In recent years numerical continuation methods have been developed which permit the numerical approximation of all complex solutions of systems of polynomial equations. In this paper, numerical continuation methods are adapted to numerically calculate the solutions of finite difference discretizations of nonlinear two-point boundary value problems. The approach taken here is to perform a homotopy deformation to successively refine discretizations. In this way additional new solutions on finer meshes are obtained from solutions on coarser meshes. The complicating issue which the complex polynomial system setting introduces is that the number of solutions grows with the number of mesh points of the discretization. To counter this, the use of filters to limit the number of paths to be followed at each stage is considered.     

Computer generation of random variables with Lindley or Poisson-Lindley distribution via the Lambert W function

We provide procedures to generate random variables with Lindley distribution, and also with Poisson-Lindley or zero-truncated Poisson-Lindley distribution, as simple alternatives to the existing algorithms. Our procedures are based on the fact that the quantile functions of these probability distributions can be expressed in closed form in terms of the Lambert W function. As a consequence, the extreme order statistics from the above distributions can also be computer generated in a straightforward manner.     

Adams methods for the efficient solution of stochastic differential equations with additive noise

The application of Adams methods for the numerical solution of stochastic differential equations is considered. Especially we discuss the path-wise (strong) solutions of stochastic differential equations with additive noise and their numerical computation. The special structure of these problems suggests the application of Adams methods, which are used for deterministic differential equations very successfully. Applications to circuit simulation are presented.     

Optimal design and operation of a wastewater purification system

Due to the importance of coastal areas, is of the highest interest to implement purification systems that with minimum cost are able to assure water quality standards in agreement with the regional legislations. This work addresses the optimal design (outfall locations) and optimal operation (level of oxygen discharges) of a wastewater treatment system. This problem can be mathematically formulated as a two-objective mixed design and optimal control problem with constraints on the states and the design and control variables.