A unified approach to methods for the simultaneous computation of all zeros of generalized polynomials

Summary Applying Newton's method to a particular system of nonlinear equations we derive methods for the simultaneous computation of all zeros of generalized polynomials. These generalized polynomials are from a function space satisfying a condition similar to Haar's condition. By this approach we bring together recent methods for trigonometric and exponential polynomials and a well-known method for ordinary polynomials. The quadratic convergence of these methods is an immediate consequence of our approach and needs not to be proved explicitly. Moreover, our approach yields new interesting methods for ordinary, trigonometric and exponential polynomials and methods for other functions occuring in approximation theory.     

A note on Halley's method

Summary We introduce the degree of logarithmic convexity which provides a measure of the convexity of a function at each point. Making use of this concept we obtain a new theorem of global convergence for Halley's method.     

On a computational method for the second fundamental tensor and its application to bifurcation problems

Summary An algorithm is presented for the computation of the second fundamental tensorV of a Riemannian submanifoldM ofR ⁿ . FromV the riemann curvature tensor ofM is easily obtained. Moreover,V has a close relation to the second derivative of certain functionals onM which, in turn, provides a powerful new tool for the computational determination of multiple bifurcation directions. Frequently, in applications, thed-dimensional manifoldM is defined implicitly as the zero set of a submersionF onR ⁿ . In this case, the principal cost of the algorithm for computingV(p) at a given pointpM involves only the decomposition of the JacobianDF(p) ofF atp and the projection ofd(d+1) neighboring points ontoM by means of a local iterative process usingDF(p). Several numerical examples are given which show the efficiency and dependability of the method.Dedicated to R. S. Varga on the occasion of his sixtieth birthdayThis work was in part supported by the National Science Foundation (DCR-8309926) and the Office of Naval Research (N-00014-80-C09455). The second author began some of the work while visiting the University of Heidelberg/Germany as an Alexander von Humboldt Senior U.S. Scientist     

On the convergence and divergence of Bairstow's method

Summary Necessary and sufficient condition of algebraic character is given for the invertibility of the Jacobian matrix in Bairstow's method. This leads to a sufficient condition for local quadratic convergence. Results also yield the rank of the Jacobian, when it is singular. In the second part of the paper we give several examples for two step cyclization and more complicated kind of divergence. Some of the polynomials in divergence examples are proved to be irreducible over the field of rational numbers.     

A reliable argument principle algorithm to find the number of zeros of an analytic function in a bounded domain

Summary The argument principle is a natural and simple method to determine the number of zeros of an analytic functionf(z) in a bounded domainD. N, the number of zeros (counting multiplicities) off(z), is 1/2 times the change in Argf(z) asz moves along the closed contour D. Since the range of Argf(z) is (–, ] a critical point in the computational procedure is to assure that the discretization of D, {z _i ,i=1, ...,M}, is such that . Discretization control which may violate this inequality can lead to an unreliable algorithm. Mathematical theorems derived for the discretization of D lead to a completely reliable algorithm to computeN. This algorithm also treats in an elementary way the case when a zero is on or near the contour D. Numerical examples are given for the reliable algorithm formulated here and it is pointed out in these examples how inadequate discretization control can lead to failure of other algorithms.Dedicated to Professor Ivo Babuka in commemoration of his sixtieth birthdayThis research is part of the doctoral dissertation of this author     

On the solution of nonlinear inequalities in a finite number of iterations

Summary We present a new algorithm based on Newton's method for solving a finite number of inequalities in a finite number of iterations. The algorithm uses an auxiliary variable for systematic expansion, when necessary, of the linear feasible set to ensure a feasible direction vector.     

On quadratic-like convergence of the means for two methods for simultaneous rootfinding of polynomials

Durand-Kerner's method for simultaneous rootfinding of a polynomial is locally second order convergent if all the zeros are simple. If this condition is violated numerical experiences still show linear convergence. For this case of multiple roots, Fraigniaud [4] proves that the means of clustering approximants for a multiple root is a better approximant for the zero and called this Quadratic-Like-Convergence of the Means.This note gives a new proof and a refinement of this property. The proof is based on the related Grau's method for simultaneous factoring of a polynomial. A similar property of some coefficients of the third order method due to Börsch-Supan, Maehly, Ehrlich, Aberth and others is proved.     

The Durand-Kerner polynomials roots-finding method in case of multiple roots

The convergence of the Durand-Kerner algorithm is quadratic in case of simple roots but only linear in case of multiple roots. This paper shows that, at each step, the mean of the components converging to the same root approaches it with an error proportional to the square of the error at the previous step. Since it is also shown that it is possible to estimate the multiplicity order of the roots during the algorithm, a modification of the Durand-Kerner iteration is proposed to preserve a quadratic-like convergence even in case of multiple zeros.This work is supported in part by the Research Program C3 of the French CNRS and MEN, and by the Direction des Recherches et Etudes Techniques (DGA).     

A projected Newton method for minimization problems with nonlinear inequality constraints

Summary Recently developed projected Newton methods for minimization problems in polyhedrons and Cartesian products of Euclidean balls are extended here to general convex feasible sets defined by finitely many smooth nonlinear inequalities. Iterate sequences generated by this scheme are shown to be locally superlinearly convergent to nonsingular extremals , and more specifically, to local minimizers satisfying the standard second order Kuhn-Tucker sufficient conditions; moreover, all such convergent iterate sequences eventually enter and remain within the smooth manifold defined by the active constraints at . Implementation issues are considered for large scale specially structured nonlinear programs, and in particular, for multistage discrete-time optimal control problems; in the latter case, overall per iteration computational costs will typically increase only linearly with the number of stages. Sample calculations are presented for nonlinear programs in a right circular cylinder in ³.Investigation supported by NSF Research Grant #DMS-85-03746     

Newton's method for gradient equations based upon the fixed point map: Convergence and complexity study

Summary An approximate Newton method, based upon the fixed point mapT, is introduced for scalar gradient equations. Although the exact Newton method coincides for such scalar equations with the standard iteration, the structure of the fixed point map provides a way of defining anR-quadratically convergent finite element iteration in the spirit of the Kantorovich theory. The loss of derivatives phenomenon, typically experienced in approximate Newton methods, is thereby avoided. It is found that two grid parameters are sssential,h and . The latter is used to calculate the approximate residual, and is isolated as a fractional step; it is equivalent to the approximation ofT. The former is used to calculate the Newton increment, and this is equivalent to the approximation ofT. The complexity of the finite element computation for the Newton increment is shown to be of optimal order, via the Vitukin inequality relating metric entropy andn-widths.Research supported by National Science Foundation grant DMS-8721742     

Asymptotic near optimality of the bisection method

Summary We seek a approximation to a zero of an infinitely differentiable functionf: [0, 1] such thatf(0)0 andf(1)0. It is known that the error of the bisection method usingn function evaluations is 2^–(n+1). If the information used are function values, then it is known that bisection information and the bisection algorithm are optimal. Traub and Woniakowski conjectured in [5] that the bisection information and algorithm are optimal even if far more general information is permitted. They permit adaptive (sequential) evaluations of arbitrary linear functionals and arbitrary transformations of this information as algorithms. This conjecture was established in [2]. That is forn fixed, the bisection information and algorithm are optimal in the worst case setting. Thus nothing is lost by restricting oneself to function values.One may then ask whether bisection is nearly optimal in theasymptotic worst case sense, that is,possesses asymptotically nearly the best rate of convergence. Methods converging fast asymptotically, like Newton or secant type, are of course, widely used in scientific computation. We prove that the answer to this question is positive for the classF of functions having zeros ofinfinite multiplicity and information consisting of evaluations of continuous linear functionals. Assuming that everyf inF has zeroes withbounded multiplicity, there are known hybrid methods which have at least quadratic rate of convergence asn tends to infinity, see e.g., Brent [1], Traub [4] and Sect. 1.     

Bisection is not optimal on the average

Summary We seek the zero of a continuous increasing functionf: [0, 1] [–1, 1] such thatf(0)=–1 andf(1)=1. It is known that the bisection method makes optimal use ofn function evaluations within a worst case analysis. In this paper we study the average error with respect to the natural measure of Graf et al. (1986). We prove that the bisection method is not optimal on the average. Actually, the average error of the bisection method is about (1/2) ⁿ , while the average error of the optimal method is less than ⁿ with some <1/2.     

A class of root finding methods

A one-parameter family of iterative methods is presented for finding the roots of transcendental equations. For a class of entire functions this family is shown to converge monotonically and globally. We also establish that for simple roots, when a model parameterh is sufficiently small, the convergence is at a linear rate with orderh ².This work is supported in part by NSERC Grant No. 079-6016.     

Comparison of Brown's and Newton's method in the monotone case

Summary In many cases when Newton's method, applied to a nonlinear sytemF(x)=0, produces a monotonically decreasing sequence of iterates, Brown's method converges monotonically, too. We compare the iterates of Brown's and Newton's method in these monotone cases with respect to the natural partial ordering. It turns out that in most of the cases arising in applications Brown's method then produces better iterates than Newton's method.     

On the computation of multi-dimensional solution manifolds of parametrized equations

Summary A new algorithm is presented for computing vertices of a simplicial triangulation of thep-dimensional solution manifold of a parametrized equationF(x)=0, whereF is a nonlinear mapping fromR ⁿ toR ^m ,p=n–m>1. An essential part of the method is a constructive algorithm for computing moving frames on the manifold; that is, of orthonormal bases of the tangent spaces that vary smoothly with their points of contact. The triangulation algorithm uses these bases, together with a chord form of the Gauss-Newton process as corrector, to compute the desired vertices. The Jacobian matrix of the mapping is not required at all the vertices but only at the centers of certain local triangulation patches. Several numerical examples show that the method is very efficient in computing triangulations, even around singularities such as limit points and bifurcation points. This opens up new possibilities for determining the form and special features of such solution manifolds.Dedicated to Professor Ivo Babuka on the occasion of his sixtieth birthdayThis work was supported in part by the National Science Foundation under Grant DCR-8309926, the Office of Naval Research under contract N-00014-80-C-9455, and the Air Force Office of Scientific Research under Grant 84-0131     

On the solutions to polynomial systems obtained by homotopy methods

Summary A natural class of homotopy methods for solving polynomial systems is considered. It is shown that at least one solution from each connected component of the solution set is obtained. This generalizes the results of previous papers which concentrated on isolated solutions, i.e. connected components with one single point. The number of solution paths ending in a connected component is independent of the particular homotopy in use and defines in a natural way the multiplicity of the connected component. A few numerical experiments illustrate the obtained results.     

Regularity results for solving systems of polynomials by homotopy method

Summary The homotopy method for solving systems of polynomial equations proposed by Li (also Morgan) is believed to be one of the simplest for computer implementation. It is shown here that the parameters of the homotopy can be chosen from an open and dense set such that all isolated solutions of polynomial systems can be obtained.This research was supported in part by National Science Foundation under Grant DMS 8416503 and DARPA     

Error analysis of splitting algorithms for polynomials

An error analysis is given for the general splitting algorithm, proposed by Shaw and Traub, for evaluating a polynomial and some of its derivatives. The results show that the usual synthetic division is least likely to be affected by round-off errors if only single-precision arithmetic is available for all the algorithms. However, the new splitting algorithms are better than the synthetic division if extended-precision arithmetic is available for the evaluation of powers ofx.This work supported in part by the United States Air Force under grant AFOSR 76-3020     

A Kantorovich-type convergence analysis for the Gauss-Newton-Method

Summary We present a (semilocal) Kantorovich-type convergence analysis for the Gauss-Newton-Method which reduces to the wellknown Newton-Kantorovich-Theorem for the Newton-Method in a natural way. Additionnally a classification of the nonlinear regression problem into adequate and not-adequate models is obtained.     

A rapid Generalized Method of Bisection for solving Systems of Non-linear Equations

Summary A rapid Generalized Method of Bisection for solving Systems of Non-linear Equations is presented in this paper, based on the non-zero value of the topological degree. Further, while the method does not compute the topological degree, it takes care of keeping its non-zero value during the bisections and thus results in a fast bisection algorithm.