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.     

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.     

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 .     

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.     

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 universal constant for the convergence of Newton's method and an application to the classical homotopy method

We give a new theorem concerning the convergence of Newton's method to compute an approximate zero of a system of equations. In this result, the constanth ₀=0.162434... appears, which plays a fundamental role in the localization of good initial points for the Newton iteration. We apply it to the determination of an appropriate discretization of the time interval in the classical homotopy method.     

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.     

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.     

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     

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.     

求解方程的一类迭代公式

Using the forms of Newton iterative function, the iterative function of Newton's method to handle the problem of multiple roots and the Halley iterative function, we give a class of iterative formulae for solving equations in one variable in this paper and show that their convergence order is at least quadratic. At last we employ our methods to solve some non-linear equations and compare them with Newton's method and Halley's method. Numerical results show that our iteration schemes are convergent if we choose two suitable parametric functions λ(x) and μ(x). Therefore, our iteration schemes are feasible and effective.     

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.     

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.     

Efficient dynamic programming implementations of Newton's method for unconstrained optimal control problems

Naive implementations of Newton's method for unconstrainedN-stage discrete-time optimal control problems with Bolza objective functions tend to increase in cost likeN ³ asN increases. However, if the inherent recursive structure of the Bolza problem is properly exploited, the cost of computing a Newton step will increase only linearly withN. The efficient Newton implementation scheme proposed here is similar to Mayne's DDP (differential dynamic programming) method but produces the Newton step exactly, even when the dynamical equations are nonlinear. The proposed scheme is also related to a Riccati treatment of the linear, two-point boundary-value problems that characterize optimal solutions. For discrete-time problems, the dynamic programming approach and the Riccati substitution differ in an interesting way; however, these differences essentially vanish in the continuous-time limit.This work was supported by the National Science Foundation, Grant No. DMS-85-03746.     

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.     

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.     

Globally Convergent Algorithms for Unconstrained Optimization

A new globalization strategy for solving an unconstrained minimization problem is proposed based on the idea of combining Newton's direction and the steepest descent direction WITHIN each iteration. Global convergence is guaranteed with an arbitrary initial point. The search direction in each iteration is chosen to be as close to the Newton's direction as possible and could be the Newton's direction itself. Asymptotically the Newton step will be taken in each iteration and thus the local convergence is quadratic. Numerical experiments are also reported. Possible combination of a Quasi-Newton direction with the steepest descent direction is also considered in our numerical experiments. The differences between the proposed strategy and a few other strategies are also discussed.     

An efficient trust region method for unconstrained discrete-time optimal control problems

Discrete-time optimal control (DTOC) problems are large-scale optimization problems with a dynamic structure. In previous work this structure has been exploited to provide very fast and efficient local procedures. Two examples are the differential dynamic programming algorithm (DDP) and the stagewise Newton procedure—both require onlyO(N) operations per iteration, whereN is the number of timesteps. Both exhibit a quadratic convergence rate. However, most algorithms in this category do not have a satisfactory global convergence strategy. The most popular global strategy is shifting: this sometimes works poorly due to the lack of automatic adjustment to the shifting element.In this paper we propose a method that incorporates the trust region idea with the local stagewise Newton's method. This method possesses advantages of both the trust region idea and the stagewise Newton's method, i.e., our proposed method has strong global and local convergence properties yet remains economical. Preliminary numerical results are presented to illustrate the behavior of the proposed algorithm. We also collect in the Appendix some DTOC problems that have appeared in the literature.Partially supported by the Cornell Theory Center, which receives major funding from the National Science Foundation and IBM Corporation, with additional support from the State of New York and its Corporate Research Institutes; and by NSF, AFOSR, and ONR through grant DMS-8920550.     

On Newton''s method under Hölder continuous derivative

A Mysovskii-type theorem for Newton's method under (k,p)-Hölder continuous derivative is considered in this paper. For the application studied by others, the new condition is weaker than ones in the literature. Also we prove that the optimal convergent order is p+1 for 0<p<1.