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.     

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     

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     

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 method for finding sharp error bounds for Newton's method under the Kantorovich assumptions

Summary This paper gives a method for finding sharpa posteriori error bounds for Newton's method under the assumptions of Kantorovich's theorem. On the basis of this method, new error bounds are derived, and comparison is made among the known bounds of Dennis [2], Döring [4], Gragg-Tapia [5], Kantorovich [6, 7], Kornstaedt [9], Lancaster [10], Miel [11–13], Moret [14], Ostrowski [17, 18], Potra [19], and Potra-Pták [20].This paper was written while the author was visiting the Mathematics Research Center, University of Wisconsin-Madison, U.S.A. from March 29, 1985 to October 21, 1985Sponsored by the Ministry of Education in Japan and the United States Army under Contract No. DAAG 29-80-C-0041     

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.     

Aitken's and Steffensen's accelerations in several variables

Summary Aitken's acceleration of scalar sequences extends to sequences of vectors that behave asymptotically as iterations of a linear transformation. However, the minimal and characteristic polynomials of that transformation must coincide (but the initial sequence of vectors need not converge) for a numerically stable convergence of Aitken's acceleration to occur. Similar results hold for Steffensen's acceleration of the iterations of a function of several variables. First, the iterated function need not be a contracting map in any neighbourhood of its fixed point. Instead, the second partial derivatives need only remain bounded in such a neighbourhood for Steffensen's acceleration to converge quadratically, even if ordinary iterations diverge. Second, at the fixed point the minimal and characteristic polynomials of the Jacobian matrix must coincide to ensure a numerically stable convergence. By generalizing the work that Noda did on the subject between 1981 and 1986, the results presented here explain the numerical observations reported by Henrici in 1964 and 1982.This work was supported by a grant from the Northwest Institute for Advanced Study, an organ of Eastern Washington University     

Regular splittings and monotone iteration functions

Summary In this paper we introduce the set of so-called monotone iteration functions (MI-functions) belonging to a given function. We prove necessary and sufficient conditions in order that a given MI-function is (in a precisely defined sense) at least as fast as a second one.Regular splittings of a function which were initially introduced for linear functions by R.S. Varga in 1960 are generating MI-functions in a natural manner.For linear functions every MI-function is generated by a regular splitting. For nonlinear functions, however, this is generally not the case.     

Convergence analysis of the general Gauss-Newton algorithm

Summary The convergence of the Gauss-Newton algorithm for solving discrete nonlinear approximation problems is analyzed for general norms and families of functions. Aquantitative global convergence theorem and several theorems on the rate of local convergence are derived. A general stepsize control procedure and two regularization principles are incorporated. Examples indicate the limits of the convergence theorems.     

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     

The approximation of generalized turning points by projection methods with superconvergence to the critical parameter

Summary A procedure is given that generates characterizations of singular manifolds for mildly nonlinear mappings between Banach spaces. This characterization is used to develop a method for determining generalized turning points by using projection methods as a discretization. Applications are given to parameter dependent two-point boundary value problems. In particular, collocation at Gauss points is shown to achieve superconvergence in approximating the parameter at simple turning points.     

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.     

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.     

Parametrization via secant length and application to path following

Summary A possible way for parametrizing the solution path of the nonlinear systemH(u)=0, H: ^{n+1 n} consists of using the secant length as parameter. This idea leads to a quadratic constraint by which the parameter is introduced. A Newton-like method for computing the solution for a given parameter is proposed where the nonlinear system is linearized at each iterate, but the quadratic parametrizing equation is exactly satisfied. The localQ-quadratic convergence of the method is proved and some hints for implementing the algorithm are givenDedicated to Professor Lothar Collatz on the occasion of his 75th birthday     

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.     

Chord techniques and Newton's method for discrete bifurcation problems

Summary The numerical treatment of discrete bifurcation problems (2) with chord methods or Newton's method is a question of constructing appropriate initial approximations to prevent the sequence from converging to the trivial solution. This problem is being discussed under conditions which are satisfied for quite a few examples arising in applications (see Sect. 3).     

Sharp error bounds for Newton's process

Summary The method of nondiscrete mathematical induction is applied to the Newton process. The method yields a very simple proof of the convergence and sharp apriori estimates; it also gives aposteriori bounds which are, in general, better than those given in [1].     

Computing singular solutions to nonlinear analytic systems

Summary A method to generate an accurate approximation to a singular solution of a system of complex analytic equations is presented. Since manyreal systems extend naturally tocomplex analytic systems, this porvides a method for generating approximations to singular solutions to real systems. Examples include systems of polynomials and systems made up of trigonometric, exponential, and polynomial terms. The theorem on which the method is based is proven using results from several complex variables. No special conditions on the derivatives of the system, such as restrictions on the rank of the Jacobian matrix at the solution, are required. The numerical method itself is developed from techniques of homotopy continuation and 1-dimensional quadrature. A specific implementation is given, and the results of numerical experiments in solving five test problems are presented.     

An adaptive Newton algorithm based on numerical inversion: Regularization as postconditioner

Summary We examine a class of approximate inversion processes, satisfying estimates similar to those defined by finite element or truncated spectral approximations; these are to be used as approximate right inverses for Newton iteration methods. When viewed at the operator level, these approximations introduce a defect, or loss of derivatives, of order one or more. Regularization is introduced as a form of defect correction. A superlinearly convergent, approximate Newton iteration is thereby obtained by using the numerical inversion adaptively, i.e., with spectral or grid parameters correlated to the magnitude of the current residual in an intermediate norm defined by the defect. This adaptive choice makes possible ascribing an order to the convergent process, and this is identified as essentially optimal for elliptic problems, relative to complexity. The design of the algorithm involves multi-parameter selection, thereby opening up interesting avenues for elliptic problems, relative to complexity. This applies also to the regularization which may be carried out in the Fourier transform space, and is band-limited in the language of Whittaker-Shannon sampling theory. The norms employed in the analysis are of Hölder space type; the iteration is an adaptation of Nash-Moser interation; and, the complexity studies use Vitukin's theory of information processing. Computational experience is described in the final section.Research supported by National Science Foundation grant MCS-8218041. This is the second part of work in progress during the author's visit to the Institute for Mathematics and its Applications, University of Minnesota, Minneapolis, USA