Componentwise inclusion and exclusion sets for solutions of quadratic equations in finite dimensional spaces

Summary In this paper we use interval arithmetic tools for the computation of componentwise inclusion and exclusion sets for solutions of quadratic equations in finite dimensional spaces. We define a mapping for which under certain assumptions we can construct an interval vector which is mapped into itself. Using Brouwer's fixed point theorem we conclude the existence of a solution of the original equation in this interval vector. Under different assumptions we can construct an interval vector such that the range of the mapping has no point in common with this interval vector. This implies that there is no solution in this interval vector. Furthermore we consider an iteration method which improves componentwise errorbounds for a solution of a quadratic. The theoretical results of this paper are demonstrated by some numerical examples using the algebraic eigenvalue problem which is probably the best known example of a quadratic equation.This paper contains the main results of a talk given by the author on the occasion of the 25th anniversary of the founding of Numerische Mathematik, March 19–21, 1984 at the Technische Universität of Munich, Germany     

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     

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.     

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     

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.     

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.     

Convergence of Newton-like-iterative methods

Summary Newton-like methods in which the intermediate systems of linear equations are solved by iterative techniques are examined. By applying the theory of inexact Newton methods radius of convergence and rate of convergence results are easily obtained. The analysis is carried out in affine invariant terms. The results are applicable to cases where the underlying Newton-like method is, for example, a difference Newton-like or update-Newton method.     

Consistent approximations in Newton-type decomposition methods

Summary A class of Newton-type decomposition methods for the solution of large systems of nonlinear equations recently introduced by the first two authors is extended in such a way that consistent approximations to the derivatives by appropriate difference quotients are permitted. Concrete realizations with essential merits for practical computation and a rigorous convergence analysis are given. For special choices of the discretization parameterR-orders greater than one are derived.Dedicated to Prof. Dr. Dr. h.c. 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.     

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     

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.     

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     

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.     

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     

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.     

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.     

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     

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     

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 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