High order iterative methods for approximating square roots

Given any natural numberm 2, we describe an iteration functiong _m (x) having the property that for any initial iterate \sqrt \alpha $$ " align="middle" border="0"> , the sequence of fixed-point iterationx _k +1 =g _m (x _k ) converges monotonically to having anm-th order rate of convergence. Form = 2 and 3,g _m (x) coincides with Newton's and Halley's iteration functions, respectively, as applied top(x) =x ² – .This research is supported in part by the National Science Foundation under Grant No. CCR-9208371.     

On multiply-connected Fatou components in iteration of meromorphic functions

Let be a transcendental meromorphic function with at most finitely many poles. We mainly investigated the existence of the Baker wandering domains of f(z) and proved, among others, that if f(z) has a Baker wandering domain U, then for all sufficiently large n, fn(U) contains a round annulus whose module tends to infinity as n→∞ and so for some 0<d<1,

     

Improvement of convergence of an iterative method for finding polynomial factors of analytic functions

In this paper, we consider an iterative method for evaluating the coefficients of a monic factor of an analytic function using complex circular arithmetic. In a previous paper, the authors presented a factoring method that finds a cluster of zeros as a polynomial factor. We analyze the convergence behavior of this method and discuss a technique for improving convergence. Numerical examples illustrate the aspects of the improved method.     

A modified Newton's method for minimizing factorable functions

Many functions of several variables used in nonlinear programming are factorable, i.e., complicated compositions of transformed sums and products of functions of a single variable. The Hessian matrices of twice-differentiable factorable functions can easily be expressed as sums of outer products (dyads) of vectors. A modified Newton's method for minimizing unconstrained factorable functions which exploits this special form of the Hessian is developed. Computational experience with the method is presented.This material is based upon work supported by the National Science Foundation under Grant No. MCS-79-04106.The author would like to thank Professor G. P. McCormick, George Washington University, for several enlightening discussions on factorable programming and for his valuable comments which improved an earlier version of this paper.     

A PL homotopy for finding all the roots of a polynomial

This paper presents a constructive method which gives, for any polynomialF(Z) of the degreen, approximate values of all the roots ofF(Z).. The point of the method is on the use of a piecewise linear function (Z, t) which approximates a homotopyH(Z, t) betweenF(Z) and a polynomialG(Z) of the degreen withn known simple roots. It is shown that the set of solutions to (Z, t) = 0 includesn distinct paths,m of which converges to a root ofF(Z) if and only if the root has the multiplicitym. Starting from givenn roots ofG(Z), a complementary pivot algorithm generates thosen paths.This work was supported by grants from Management Science Development Foundation and Takeda Science Foundation.     

Bounded iteration and unary functions

The set of unary functions of complexity classes defined by using bounded primitive recursion is inductively characterized by means of bounded iteration. Elementary unary functions, linear space computable unary functions and polynomial space computable unary functions are then inductively characterized using only composition and bounded iteration. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

A family of root finding methods

Summary A one parameter family of iteration functions for finding roots is derived. The family includes the Laguerre, Halley, Ostrowski and Euler methods and, as a limiting case, Newton's method. All the methods of the family are cubically convergent for a simple root (except Newton's which is quadratically convergent). The superior behavior of Laguerre's method, when starting from a pointz for which |z| is large, is explained. It is shown that other methods of the family are superior if |z| is not large. It is also shown that a continuum of methods for the family exhibit global and monotonic convergence to roots of polynomials (and certain other functions) if all the roots are real.This research was supported by the National Science Foundation under grant number NSF-DCR-74-10042.     

A three-stage variable-shift iteration for polynomial zeros and its relation to generalized rayleigh iteration

Summary We introduce a new three-stage process for calculating the zeros of a polynomial with complex coefficients. The algorithm is similar in spirit to the two stage algorithms studied by Traub in a series of papers. We prove that the mathematical algorithm always converges and show that the rate of convergence of the third stage is faster than second order. To obtain additional insight we recast the problem and algorithm into matrix form. The third stage is inverse iteration with the companion matrix, followed by generalized Rayleigh iteration.This work was supported in part by the National Science Foundation and the Office of Naval Research.     

A family of crooked functions

It has been proved in Bierbrauer and Kyureghyan (Des. Codes Cryptogr. 46:269–301, 2008) that a binomial function aX ⁱ  + bX ^j can be crooked only if both exponents i, j have 2-weight  ≤2. In the present paper we give a brief construction for all known examples of crooked binomial functions. These consist of an infinite family and one sporadic example. The construction of the sporadic example uses the properties of an algebraic curve of genus 3. Computer experiments support the conjecture that each crooked binomial is equivalent either to a member of the family or to the sporadic example.      

Penalty functions,Newton's method,and quadratic programming

In this paper, the search directions computed by two versions of the sequential quadratic programming (SQP) algorithm are compared with that computed by attempting to minimize a quadratic penalty function by Newton's method, and it is shown that the differences are attributable to ignoring certain terms in the equation for the Newton correction. Since the effect of ignoring these terms may be to make the resultant direction a poor descent direction for the quadratic penalty function, it is argued that the latter is an inappropriate merit function for use with SQP. A method is then suggested by which these terms may be included without losing the benefits gained from the use of the orthogonal transformations derived from the constraints Jacobian.The authors wish to thank A. R. Conn and N. I. M. Gould for spirited discussions which took place when the second author spent some time at Waterloo, Ontario, Canada; they also thank L. C. W. Dixon for the clarifications that he suggested to the penultimate draft of this paper.     

Some characterizations of strongly preinvex functions

In this paper, a new class of generalized convex function is introduced, which is called the strongly α-preinvex function. We study some properties of strongly α-preinvex function. In particular, we establish the equivalence among the strongly α-preinvex functions, strongly α-invex functions and strongly αη-monotonicity under some suitable conditions. As special cases, one can obtain several new and previously known results for α-preinvex (invex) functions.     

On some improvements of square root iteration for polynomial complex zeros

Using Newton's and Halley's corrections, some modifications of the simultaneous method for finding polynomial complex zeros, based on square root iteration, are obtained. The convergence order of the proposed methods is five and six respectively. Further improvements of these methods are performed by applying the Gauss—Seidel approach. The lower bounds of the R-order of convergence and the convergence conditions for the accelerated (single-step) methods are given. Faster convergence is attained without additional calculations. The considered iterative procedures are illustrated numerically in the example of an algebraic equation.     

New families of perfect nonlinear polynomial functions

A new class of almost perfect nonlinear (APN) polynomial functions has been recently introduced. We give some generalizations of these functions and deduce new families of perfect nonlinear (PN) functions. We show that these PN functions are CCZ-inequivalent to the known perfect nonlinear functions.     

On the Order of Convergence of a Determinantal Family of Root-Finding Methods

Recently, we have shown that for each natural number m greater than one, and each natural number k less than or equal to m, there exists a root-finding iteration function, defined as the ratio of two determinants that depend on the first m - k derivatives of the given function. For each k the corresponding matrices are upper Hessenberg matrices. Additionally, for k = 1 these matrices are Toeplitz matrices. The goal of this paper is to analyze the order of convergence of this fundamental family. Newton's method, Halley's method, and their multi-point versions are members of this family. In this paper we also derive these special cases. We prove that for fixed m, as k increases, the order of convergence decreases from m to the positive root of the characteristic polynomial of generalized Fibonacci numbers of order m. For fixed k, the order of convergence increases in m. The asymptotic error constant is also derived in terms of special determinants.     

Bernstein polynomial and discontinuous functions

We obtain new estimates of the rate of convergence of Bernstein operators for discontinuous functions on [0,1]$[0,1]$ which can be used to derive known results for continuous functions and functions of bounded variation.     

An infinite family of bounds on zeros of analytic functions and relationship to Smale's bound

Smale's analysis of Newton's iteration function induce a lower bound on the gap between two distinct zeros of a given complex-valued analytic function . In this paper we make use of a fundamental family of iteration functions , , to derive an infinite family of lower bounds on the above gap. However, even for , where coincides with Newton's, our lower bound is more than twice as good as Smale's bound or its improved version given by Blum, Cucker, Shub, and Smale. When is a complex polynomial of degree , for small the corresponding bound is computable in arithmetic operations. For quadratic polynomials, as increases the lower bounds converge to the actual gap. We show how to use these bounds to compute lower bounds on the distance between an arbitrary point and the nearest root of . In particular, using the latter result, we show that, given a complex polynomial , , for each we can compute upper and lower bounds and such that the roots of lie in the annulus . In particular, , ; and , , where . An application of the latter bounds is within Weyl's classical quad-tree algorithm for computing all roots of a given complex polynomial.

     

On the convergence of policy iteration for controlled diffusions

The convergence of an approximation scheme known as policy iteration has been demonstrated for controlled diffusions by Fleming, Puterman, and Bismut. In this paper, we show that this approximation scheme is equivalent to the Newton-Kantorovich iteration for solving the optimality equation and exploit this equivalence to obtain a new proof of convergence. Estimates of the rate of convergence of this procedure are also obtained.This research was partially supported by NRC Grant No. A-3609.     

Second-order characterizations of pseudoconvex quadratic functions

The paper deals with strictly pseudoconvex quadratic functions on open convex sets. It presents second-order conditions in terms of an extended Hessian and in terms of bordered determinants. All of the conditions are both necessary and sufficient.The author wishes to thank Professor M. Avriel, visiting Stanford University, for helpful discussions. He is also grateful to Professor R. W. Cottle, Stanford University, for his suggestions.     

Some characterizations of duality for DC optimization with composite functions

In this paper, by virtue of the epigraph technique, we first introduce some new regularity conditions and then obtain some complete characterizations of the Fenchel–Lagrange duality and the stable Fenchel–Lagrange duality for a new class of DC optimization involving a composite function. Moreover, we apply the strong and stable strong duality results to obtain some extended (stable) Farkas lemmas and (stable) alternative type theorems for this DC optimization problem. As applications, we obtain the corresponding results for a composed convex optimization problem, a DC optimization problem, and a convex optimization problem with a linear operator, respectively.     

Asymptotic error estimates for the method of simple iteration and for the modified and generalized Newton methods

We find asymptotic error estimates for the method of simple iteration and for the modified and generalized Newton methods. The results, in contrast with the classical ones, provide explicit error estimates for these iterative processes in terms of their parameters, and this plays a decisive role not only for the proof of the convergence of combined methods, but also for determining the order of convergence. Moreover, in practice this allows us to theoretically evaluate the number of iterations sufficient for constructing the combined method of maximal order, and therefore to find the optimal number of iterations.Translated fromMatematicheskie Zametki, Vol. 63, No. 4, pp. 562–571, April, 1998.