On the convergence of multipoint iterations

Summary. This note gives a new convergence proof for iterations based on multipoint formulas. It rests on the very general assumption that if the desired fixed point appears as an argument in the formula then the formula returns the fixed point. Received March 24, 1993 / Revised version received January 1994     

Tangent Graeffe iteration

Summary.   Graeffe iteration was the choice algorithm for solving univariate polynomials in the XIX-th and early XX-th century. In this paper, a new variation of Graeffe iteration is given, suitable to IEEE floating-point arithmetics of modern digital computers. We prove that under a certain generic assumption the proposed algorithm converges. We also estimate the error after N iterations and the running cost. The main ideas from which this algorithm is built are: classical Graeffe iteration and Newton Diagrams, changes of scale (renormalization), and replacement of a difference technique by a differentiation one. The algorithm was implemented successfully and a number of numerical experiments are displayed. Received May 29, 1998 / Revised version received September 13, 1999 / Published online April 5, 2001     

Weierstrass formula and zero-finding methods

Summary. Classical Weierstrass' formula [29] has been often the subject of investigation of many authors. In this paper we give some further applications of this formula for finding the zeros of polynomials and analytic functions. We are concerned with the problems of localization of polynomial zeros and the construction of iterative methods for the simultaneous approximation and inclusion of these zeros. Conditions for the safe convergence of Weierstrass' method, depending only on initial approximations, are given. In particular, we study polynomials with interval coefficients. Using an interval version of Weierstrass' method enclosures in the form of disks for the complex-valued set containing all zeros of a polynomial with varying coefficients are obtained. We also present Weierstrass-like algorithm for approximating, simultaneously, all zeros of a class of analytic functions in a given closed region. To demonstrate the proposed algorithms, three numerical examples are included. Received September 13, 1993     

A Bairstow's type method for trigonometric polynomials

Summary. We construct in this paper an analogous method to Bairstow's one, for trigonometric polynomials with real coefficients. We also present some numerical examples which illustrate this method. Received November 11, 1992/Revised version received May 13, 1993     

An inexactQP-based method for nonlinear complementarity problems

Summary. We consider a quadratic programming-based method for nonlinear complementarity problems which allows inexact solutions of the quadratic subproblems. The main features of this method are that all iterates stay in the feasible set and that the method has some strong global and local convergence properties. Numerical results for all complementarity problems from the MCPLIB test problem collection are also reported. Received February 24, 1997 / Revised version received September 5, 1997     

A Cholesky dual method for proximal piecewise linear programming

Summary. A quadratic programming method is given for minimizing a sum of piecewise linear functions and a proximal quadratic term, subject to simple bounds on variables. It may be used for search direction finding in nondifferentiable optimization algorithms. An efficient implementation is described that updates a Cholesky factorization of active constraints and provides good accuracy via iterative refinement. Numerical experience is reported for some large problems. Received March 29, 1993 / Revised version received December 18, 1993     

Factorization of analytic functions by means of Koenig's theorem and Toeplitz computations

Summary. By providing a matrix version of Koenig's theorem we reduce the problem of evaluating the coefficients of a monic factor r(z) of degree h of a power series f(z) to that of approximating the first h entries in the first column of the inverse of an Toeplitz matrix in block Hessenberg form for sufficiently large values of n. This matrix is reduced to a band matrix if f(z) is a polynomial. We prove that the factorization problem can be also reduced to solving a matrix equation for an matrix X, where is a matrix power series whose coefficients are Toeplitz matrices. The function is reduced to a matrix polynomial of degree 2 if f(z) is a polynomial of degreeN and . These reductions allow us to devise a suitable algorithm, based on cyclic reduction and on the concept of displacement rank, for generating a sequence of vectors that quadratically converges to the vector having as components the coefficients of the factor r(z). In the case of a polynomial f(z) of degree N, the cost of computing the entries of given is arithmetic operations, where is the cost of solving an Toeplitz-like system. In the case of analytic functions the cost depends on the numerical degree of the power series involved in the computation. From the numerical experiments performed with several test polynomials and power series, the algorithm has shown good numerical properties and promises to be a good candidate for implementing polynomial root-finders based on recursive splitting strategies. Applications to solving spectral factorization problems and Markov chains are also shown. Received September 9, 1998 / Revised version received November 14, 1999 / Published online February 5, 2001     

On Halley iteration

This paper proposes some modified Halley iterations for finding the zeros of polynomials. We investigate the non-overshoot properties of the modified Halley iterations and other important properties that play key roles in solving symmetric eigenproblems. We also extend Halley iteration to systems of polynomial equations in several variables. Received March 20, 1996 / Revised version received December 5, 1997     

Improved smoothing-type methods for the solution of linear programs

Summary. We consider a smoothing-type method for the solution of linear programs. Its main idea is to reformulate the primal-dual optimality conditions as a nonlinear and nonsmooth system of equations, and to apply a Newton-type method to a smooth approximation of this nonsmooth system. The method presented here is a predictor-corrector method, and is closely related to some methods recently proposed by Burke and Xu on the one hand, and by the authors on the other hand. However, here we state stronger global and/or local convergence properties. Moreover, we present quite promising numerical results for the whole netlib test problem collection. Received August 9, 2000 / Revised version received September 28, 2000 / Published online June 7, 2001     

Relative-error bounds for the LU decomposition via the GTH algorithm

Summary. Recently the author showed that the Grassmann-Taksar-Heyman (GTH) algorithm computes the steady-state distribution of a finite-state Markov chain with low relative error. Here it is shown that the LU decomposition computed in the course of the GTH algorithm also has low relative error. The proof requires a refinement of the methods used in the earlier paper. Received September 2, 1994 / Revised version received July 17, 1995     

Polynomials on the Cauchy circle

Summary. Let be a complex polynomial of degree with and Cauchy radius 1 about the origin. We discuss the order of magnitude of the minimal number such that Previous estimates of are improved to . Some other related properties of these polynomials are also exhibited. Received March 3, 1993     

Integration methods based on canonical coordinates of the second kind

Summary.   We present a new class of integration methods for differential equations on manifolds, in the framework of Lie group actions. Canonical coordinates of the second kind is used for representing the Lie group locally by means of its corresponding Lie algebra. The coordinate map itself can, in many cases, be computed inexpensively, but the approach also involves the inversion of its differential, a task that can be challenging. To succeed, it is necessary to consider carefully how to choose a basis for the Lie algebra, and the ordering of the basis is important as well. For semisimple Lie algebras, one may take advantage of the root space decomposition to provide a basis with desirable properties. The problem of ordering leads us to introduce the concept of an admissible ordered basis (AOB). The existence of an AOB is established for some of the most important Lie algebras. The computational cost analysis shows that the approach may lead to more efficient solvers for ODEs on manifolds than those based on canonical coordinates of the first kind presented by Munthe-Kaas. Numerical experiments verify the derived properties of the new methods. Received April 2, 1999 / Revised version received January 18, 2000 / Published online August 2, 2000     

Asymptotic formula for the error in cardinal interpolation

Summary. We give the asymptotic formula for the error in cardinal interpolation. We generalize the Mazur Orlicz Theorem for periodic function. Received February 22, 1999 / Revised version received October 15, 1999 / Published online March 20, 2001     

Is the polynomial so perfidious?

Summary. Wilkinson, in [1], has given a comprehensive account of the numerical difficulties of working with polynomials on a floating point computer. The object of this note is to attempt to rehabilitate the polynomial to a certain extent. In particular it is shown here that polynomial deflation can be performed satisfactorily by a method akin to `backward recursion'. Error analyses and examples are given to illustrate the stability of the process. Received October 4, 1993 / Revised version received July 14, 1993     

A new line-search step based on the Weierstrass \wp-function for minimizing a class of logarithmic barrier functions

Summary. We define the notion of self-concordance of order two for the restriction of a logarithmic barrier function to a given line. Based on this notion we prove an inner approximation of the domain of , as well as a lower bound of the distance from a point $t$ to the minimum of . These results provide the theoretical tools to develop a simple and efficient search step for finding the minimum of the barrier function along a given line. The new bound on the size of the line-search step is better than the optimal bound known for the case of a self-concordant function (of order one). We conclude with some numerical examples that illustrate the promise of the new line-search step. Received May 24, 1993 / Revised version received February 1994     

An acceleration theorem for the ρ-algorithm

Summary. The ρ-algorithm of Wynn is an excellent device for accelerating the convergence of some logarithmically convergent sequences. Until now a convergence theorem and an acceleration theorem for the ρ-algorithm have not been obtained. The purpose of this paper is to give an acceleration theorem for the ρ-algorithm. Moreover, it is proved that the ρ-algorithm cannot accelerate linear convergence. Numerical examples are given. Received October 20, 1994 / Revised version received July 2, 1995     

Quadratic convergence of scaled matrices in Jacobi method

Summary. A quadratic convergence bound for scaled Jacobi iterates is proved provided the initial symmetric positive definite matrix has simple eigenvalues. The bound is expressed in terms of the off-norm of the scaled initial matrix and the minimum relative gap in the spectrum. The obtained result can be used to predict the stopping moment in the two-sided and especially in the one-sided Jacobi method. Received October 31, 1997 / Revised version received March 8, 1999 / Published online July 12, 2000     

Numerical solution of a secular equation

Summary. A method is proposed for the solution of a secular equation, arising in modified symmetric eigenvalue problems and in several other areas. This equation has singularities which make the application of standard root-finding methods difficult. In order to solve the equation, a class of transformations of variables is considered, which transform the equation into one for which Newton's method converges from any point in a certain given interval. In addition, the form of the transformed equation suggests a convergence accelerating modification of Newton's method. The same ideas are applied to the secant method and numerical results are presented. Received July 1, 1994     

Analysis of a coupled finite-infinite element method for exterior Helmholtz problems

Summary. This analysis of convergence of a coupled FEM-IEM is based on our previous work on the FEM and the IEM for exterior Helmholtz problems. The key idea is to represent both the exact and the numerical solution by the Dirichlet-to-Neumann operators that they induce on the coupling hypersurface in the exterior of an obstacle. The investigation of convergence can then be related to a spectral analysis of these DtN operators. We give a general outline of our method and then proceed to a detailed investigation of the case that the coupling surface is a sphere. Our main goal is to explore the convergence mechanism. In this context, we show well-posedness of both the continuous and the discrete models. We further show that the discrete inf-sup constants have a positive lower bound that does not depend on the number of DOF of the IEM. The proofs are based on lemmas on the spectra of the continuous and the discrete DtN operators, where the spectral characterization of the discrete DtN operator is given as a conjecture from numerical experiments. In our convergence analysis, we show algebraic (in terms of N) convergence of arbitrary order and generalize this result to exponential convergence. Received April 10, 1999 / Revised version received November 10, 1999 / Published online October 16, 2000     

Block LU factorizations of M–matrices

Summary. It is well known that any nonsingular M–matrix admits an LU factorization into M–matrices (with L and U lower and upper triangular respectively) and any singular M–matrix is permutation similar to an M–matrix which admits an LU factorization into M–matrices. Varga and Cai establish necessary and sufficient conditions for a singular M–matrix (without permutation) to allow an LU factorization with L nonsingular. We generalize these results in two directions. First, we find necessary and sufficient conditions for the existence of an LU factorization of a singular M-matrix where L and U are both permitted to be singular. Second, we establish the minimal block structure that a block LU factorization of a singular M–matrix can have when L and U are M–matrices. Received November 21, 1994 / Revised version received August 4, 1997