Extraneous fixed points,basin boundaries and chaotic dynamics for Schröder and König rational iteration functions

Summary The Schröder and König iteration schemes to find the zeros of a (polynomial) functiong(z) represent generalizations of Newton's method. In both schemes, iteration functionsf _m (z) are constructed so that sequencesz _n+1 =f _m (z _n ) converge locally to a rootz ^* ofg(z) asO(|z _n –z ^*|^m). It is well known that attractive cycles, other than the zerosz ^*, may exist for Newton's method (m=2). Asm increases, the iteration functions add extraneous fixed points and cycles. Whether attractive or repulsive, they affect the Julia set basin boundaries. The König functionsK _m (z) appear to minimize such perturbations. In the case of two roots, e.g.g(z)=z ²–1, Cayley's classical result for the basins of attraction of Newton's method is extended for allK _m (z). The existence of chaotic {z _n } sequences is also demonstrated for these iteration methods.     

On the solution of nonlinear equations in interval arithmetic

We consider the problem of finding a simple zero of a continuously differentiable functionf:R ⁿ R ⁿ . There is given an intervalvectorX ₀ ^I containing one zero off, and we will construct a contracting sequence of intervalvectors enclosing this zero. This can be done by Newton's method, which gives quadratic convergence, but requires inversion of an intervalmatrix at each step of the iteration. Alefeld and Herzberger, [1], give a modification of Newton's method, without the necessity of inversion, the convergence being superlinear. We give a slight modification of the latter method, with the property that the sequence of interval widths is dominated by a quadratically convergent sequence.     

How to be sure of finding a root of a complex polynomial using Newton's method

The trouble with Newton's method for finding the roots of a complex polynomial is knowing where to start the iteration. In this paper we apply the theory of rational maps and some estimates based on distortion theorems for univalent functions to find lower bounds, depending only on the degreed, for the size of regions from which the iteration will certainly converge to a root. We can also bound the number of iterations required and we give a method that works for every polynomial and takes at most some constant timesd ²(logd)² log(d ³/) iterations to find one root to within an accuracy of .     

Grouped coordinate minimization using Newton's method for inexact minimization in one vector coordinate

Letf(x,y) be a function of the vector variablesx R ⁿ andy R ^m. The grouped (variable) coordinate minimization (GCM) method for minimizingf consists of alternating exact minimizations in either of the two vector variables, while holding the other fixed at the most recent value. This scheme is known to be locally,q-linearly convergent, and is most useful in certain types of statistical and pattern recognition problems where the necessary coordinate minimizers are available explicitly. In some important cases, the exact minimizer in one of the vector variables is not explicitly available, so that an iterative technique such as Newton's method must be employed. The main result proved here shows that a single iteration of Newton's method solves the coordinate minimization problem sufficiently well to preserve the overall rate of convergence of the GCM sequence.The authors are indebted to Professor R. A. Tapia for his help in improving this paper.     

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 nonsmooth version of Newton's method

Newton's method for solving a nonlinear equation of several variables is extended to a nonsmooth case by using the generalized Jacobian instead of the derivative. This extension includes the B-derivative version of Newton's method as a special case. Convergence theorems are proved under the condition of semismoothness. It is shown that the gradient function of the augmented Lagrangian forC ²-nonlinear programming is semismooth. Thus, the extended Newton's method can be used in the augmented Lagrangian method for solving nonlinear programs.This author's work is supported in part by the Australian Research Council.This author's work is supported in part by the National Science Foundation under grant DDM-8721709.     

Solving Toeplitz Least Squares Problems by Means of Newton's Iteration

We extend the algorithm of [4], based on Newton's iteration and on the concept of -displacement rank, to the computation of the generalized inverse A ⁺ of an m×n Toeplitz matrix A. We introduce new strategies for the dynamical control of the truncation level at each step of the iteration. Numerical experiments and an application to a problem of image restoration are shown. An object-oriented implementation in C++ is described.     

On fully discrete Galerkin methods of second-order temporal accuracy for the nonlinear Schrödinger equation

Summary We approximate the solutions of an initial- and boundary-value problem for nonlinear Schrödinger equations (with emphasis on the cubic nonlinearity) by two fully discrete finite element schemes based on the standard Galerkin method in space and two implicit. Crank-Nicolson-type second-order accurate temporal discretizations. For both schemes we study the existence and uniqueness of their solutions and proveL ² error bounds of optimal order of accuracy. For one of the schemes we also analyze one step of Newton's method for solving the nonlinear systems that arise at every time step. We then implement this scheme using an iterative modification of Newton's method that, at each time stept ⁿ , requires solving a number of sparse complex linear systems with a matrix that does not change withn. The effect of this inner iteration is studied theoretically and numerically.The work of these authors was supported by the Institute of Applied and Computational Mathematics of the Research Center of Crete-FORTH and the Science Alliance program of the University of TennesseeThe work of this author was supported by the AFOSR Grant 88-0019     

A scaling technique for finding the weighted analytic center of a polytope

Let a bounded full dimensional polytope be defined by the systemAx b whereA is anm × n matrix. Leta _i denote theith row of the matrixA, and define theweighted analytic center of the polytope to be the point that minimizes the strictly convex barrier function – _i=1 ^m w _i ln(a _i ^T x –b _i ). The proper selection of weightsw _i can make any desired point in the interior of the polytope become the weighted analytic center. As a result, the weighted analytic center has applications in both linear and general convex programming. For simplicity we assume that the weights are positive integers.If some of thew _i 's are much larger than others, then Newton's method for minimizing the resulting barrier function is very unstable and can be very slow. Previous methods for finding the weighted analytic center relied upon a rather direct application of Newton's method potentially resulting in very slow global convergence. We present a method for finding the weighted analytic center that is based on the scaling technique of Edmonds and Karp and is an enhancement of Newton's method. The scaling algorithm runs in iterations, wherem is the number of constraints defining the polytope andW is the largest weight given on any constraint. Each iteration involves taking a step in the Newton direction and its complexity is dominated by the time needed to solve a system of linear equations.Supported by the Campus Research Board, University of Illinois at Urbana-Champaign.Supported by the National Science Foundation under Grants CCR-9057481 and CCR-9007195.     

A computational comparison of the first nine members of a determinantal family of root-finding methods

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, B_m^(k) defined as the ratio of two determinants that depend on the first m−k derivatives of the given function. This infinite family is derived in Kalantari (J. Comput. Appl. Math. 126 (2000) 287–318) and its order of convergence is analyzed in Kalantari (BIT 39 (1999) 96–109). In this paper we give a computational study of the first nine root-finding methods. These include Newton, secant, and Halley methods. Our computational results with polynomials of degree up to 30 reveal that for small degree polynomials B_m^(k−1) is more efficient than B_m^(k), but as the degree increases, B_m^(k) becomes more efficient than B_m^(k−1). The most efficient of the nine methods is B₄⁽⁴⁾, having theoretical order of convergence equal to 1.927. Newton's method which is often viewed as the method of choice is in fact the least efficient method.     

An operator Newton method for the Stefan problem based on smoothing: A local perspective

The initial/Neumann boundary-value enthalpy formulation for the two-phase Stefan problem is regularized by smoothing. Known estimates predict a convergence rate of ^1/2, and this result is extended in this paper to include the case of a (nonzero) residual in the regularized problem. A modified Newton Kantorovich framework is established, whereby the exact solution of the regularized problem is replaced by one Newton iteration. It is shown that a consistent theory requires measure-theoretic hypotheses on the starting guess and the Newton iterate, otherwise residual decrease is not expected. The circle closes in one spatial dimension, where it is shown that the residual decrease of Newton's method correlates precisely with the ^1/2 convergence theory.     

Newton's method for nonlinear ordinary and partial differential equations

A unified approach is presented for proving the local, uniform and quadratic convergence of the approximate solutions and a-posteriori error bounds obtained by Newton's method for systems of nonlinear ordinary or partial differential equations satisfying an inverse-positive property. An important step is to show that, at each iteration, the linearized problem is inverse-positive. Many classes of problems are shown to satisfy this property. The convergence proofs depend crucially on an error bound derived previously by Rosen and the author for quasilinear elliptic, parabolic and hyperbolic problems.     

Newton's solution to the equiangular spiral problem and a new solution using only the equiangular property

This paper is a study of Proposition IX of Book I of Newton's Principia, the problem of determining the centripetal force for an equiangular spiral. In Newton's main proof of this proposition there is an error concerning his reason for the figure SPRQT being “given in kind,” and a very interesting technique of varying things in the neighborhood of a limit. This main proof utilized Newton's formula for the limit of SP²QT²/QR given in Corollary I to Proposition VI of the Principia. Newton also gave an alternate proof which utilized his formula for SY²PV given in Corollary III to Proposition VI. The “given” of Proposition IX was “a spiral PQS, cutting all the radii SP, SQ, &c., in a given angle.” Both the main proof and the alternate proof implicitly depend on the property of the equiangular spiral that the radius of curvature at any point is proportional to the pole distance SP. We here offer a new proof of Newton's proposition which does not depend on this implicit assumption.     

Heuristic solutions to polynomial moment problems with some convex entropic objectives

We are asking to estimate a nonnegative density on ^m , given some of its algebraic or trigonometric moments. The maximum entropy method is to introduce an entropy-like objective function and then solve a convex minimization programming with some linear constraints. In the existing literature, Newton's method or some other iteration methods are used to solve its dual problem. In this paper, special structures of the problem have been discovered when we use some particular entropies, which include Boltzmann-Shannon entropy and Burg's entropy. Useful linear relationships among the moments help us to set up very fast and effective algorithms. Numerical computations and comparison are also presented.     

One-step jackknife for M-estimators computed using Newton's method

To estimate the dispersion of an M-estimator computed using Newton's iterative method, the jackknife method usually requires to repeat the iterative process n times, where n is the sample size. To simplify the computation, one-step jackknife estimators, which require no iteration, are proposed in this paper. Asymptotic properties of the one-step jackknife estimators are obtained under some regularity conditions in the i.i.d. case and in a linear or nonlinear model. All the one-step jackknife estimators are shown to be asymptotically equivalent and they are also asymptotically equivalent to the original jackknife estimator. Hence one may use a dispersion estimator whose computation is the simplest. Finite sample properties of several one-step jackknife estimators are examined in a simulation study.The research was supported by Natural Sciences and Engineering Research Council of Canada.     

Starlike domains of convergence for Newton's method at singularities

Summary Given a solutionx ^* of a system of nonlinear equationsf with singular Jacobian f(x ^*) we construct an open starlike domainR of initial points, from which Newton's method converges linearly tox ^*. Under certain conditions the union of those straight lines throughx ^*, that do not intersect withR is shown to form a closed set of measure zero, which is necessarily disjoint from any starlike domain of convergence. The results apply to first and higher order singularities.     

A Fast Implicit Numerical Method for Time Dependent Viscous Flows

The iterative method used by Esch (1964) and Pearson (1964, 1965a, b), for the solution of an implicit finite difference approximation to the Navier Stokes equation, is analysed. A more general iteration method is suggested that may require many iteration parameters, and it is shown how these parameters can be computed. It was found that when the non-dimensional number vΔt/2L² is small, a single optimum iteration parameter exists (v being the kinematic viscosity, Δt the time step and L a characteristic length). An approximate expression for the “best” parameter is developed, and a procedure is described for improving that estimate. With the improved estimate and extrapolation in time, convergence is achieved in one or two iterations per time step on the average. In some cases the time step used was 200 times bigger than the time step required for stability of explicit schemes.     

Discrete versus continuous Newton's method: A case study

We consider the damped Newton's method N _h (z) = z – hp(z)/p(z), 0<h<1 for polynomialsp(z) with complex coefficients. For the usual Newton's method (h=1) and polynomialsp(z), it is known that the method may fail to converge to a root ofp and rather leads to an attractive periodic cycle.N _h(z) may be interpreted as an Euler step for the differential equation =–p(z)/p(z) with step sizeh. In contrast to the possible failure of Newton's method, we have that for almost all initial conditions to the differential equation that the solutions converge to a root ofp. We show that this property generally carries over to Newton's methodN _h(z) only for certain nondegenerate polynomials and for sufficiently small step sizesh>0. Further we discuss the damped Newton's method applied to the family of polynomials of degree 3.     

Newton's method for sections on Riemannian manifolds: Generalized covariant -theory

One kind of the L-average Lipschitz condition is introduced to covariant derivatives of sections on Riemannian manifolds. A convergence criterion of Newton's method and the radii of the uniqueness balls of the singular points for sections on Riemannian manifolds, which is independent of the curvatures, are established under the assumption that the covariant derivatives of the sections satisfy this kind of the L-average Lipschitz condition. Some applications to special cases including Kantorovich's condition and the γ-condition as well as Smale's α-theory are provided. In particular, the result due to Ferreira and Svaiter [Kantorovich's Theorem on Newton's method in Riemannian manifolds, J. Complexity 18 (2002) 304–329] is extended while the results due to Dedieu Priouret, Malajovich [Newton's method on Riemannian manifolds: covariant alpha theory, IMA J. Numer. Anal. 23 (2003) 395–419] are improved significantly. Moreover, the corresponding results due to Alvarez, Bolter, Munier [A unifying local convergence result for Newton's method in Riemannian manifolds, Found. Comput. Math. to appear] for vector fields and mappings on Riemannian manifolds are also extended.     

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.