On the global convergence of path-following methods to determine all solutions to a system of nonlinear equations

In this paper we prove a general theorem stating a sufficient condition for the inverse image of a point under a continuously differentiable map from ℝ ⁿ to ℝ ^k to be connected. This result is applied to the trajectories generated by the Newton flow. Several examples demonstrate the applicability of the results to nontrivial problems. This work was supported by the Deutsche Forschungsgemeinschaft.     

Interval solution of nonlinear equations using linear programming

A new computational test is proposed for nonexistence of a solution to a system of nonlinear equations in a convex polyhedral regionX. The basic idea proposed here is to formulate a linear programming problem whose feasible region contains all solutions inX. Therefore, if the feasible region is empty (which can be easily checked by Phase I of the simplex method), then the system of nonlinear equations has no solution inX. The linear programming problem is formulated by surrounding the component nonlinear functions by rectangles using interval extensions. This test is much more powerful than the conventional test if the system of nonlinear equations consists of many linear terms and a relatively small number of nonlinear terms. By introducing the proposed test to interval analysis, all solutions of nonlinear equations can be found very efficently. This work was partially supported by the Japanese Ministry of Education.     

Frozen divided difference scheme for solving systems of nonlinear equations

The development of an inverse first-order divided difference operator for functions of several variables, as well as a direct computation of the local order of convergence of an iterative method is presented. A generalized algorithm of the secant method for solving a system of nonlinear equations is studied and the maximum computational efficiency is computed. Furthermore, a sequence that approximates the order of convergence is generated for the examples and it confirms in a numerical way that the order of the methods is well deduced.     

Solution of finite systems of equations by interval iteration

In actual practice, iteration methods applied to the solution of finite systems of equations yield inconclusive results as to the existence or nonexistence of solutions and the accuracy of any approximate solutions obtained. On the other hand, construction of interval extensions of ordinary iteration operators permits one to carry out interval iteration computationally, with results which can give rigorous guarantees of existence or nonexistence of solutions, and error bounds for approximate solutions. Examples are given of the solution of a nonlinear system of equations and the calculation of eigenvalues and eigenvectors of a matrix by interval iteration. Several ways to obtain lower and upper bounds for eigenvalues are given.Sponsored by the United States Army under Contract No. DAAG29-80-C-0041.     

BFGS trust-region method for symmetric nonlinear equations

In this paper, we propose a BFGS trust-region method for solving symmetric nonlinear equations. The global convergence and the superlinear convergence of the presented method will be established under favorable conditions. Numerical results show that the new algorithm is effective.     

Analysis of two Chebyshev-like third order methods free from second derivatives for solving systems of nonlinear equations

In this paper, two Chebyshev-like third order methods free from second derivatives are considered and analyzed for systems of nonlinear equations. The methods can be obtained by having different approximations to the second derivatives present in the Chebyshev method. We study the local and third order convergence of the methods using the point of attraction theory. The computational aspects of the methods are also studied using some numerical experiments including an application to the Chandrasekhar integral equations in Radiative Transfer.     

Study the stability of solutions of functional differential equations via fixed points

In this paper, we study the stability properties of solutions of a class of functional differential equations with variable delay. By using the fixed point theory under an exponentially weighted metric, we obtain some interesting sufficient conditions ensuring that the zero solution of the equations is stable and asymptotically stable.     

Partitioned quasi-Newton methods for nonlinear equality constrained optimization

We derive new quasi-Newton updates for the (nonlinear) equality constrained minimization problem. The new updates satisfy a quasi-Newton equation, maintain positive definiteness on the null space of the active constraint matrix, and satisfy a minimum change condition. The application of the updates is not restricted to a small neighbourhood of the solution. In addition to derivation and motivational remarks, we discuss various numerical subtleties and provide results of numerical experiments.Research partially supported by the Applied Mathematical Sciences Research Program (KC-04-02) of the Office of Energy Research of the US Department of Energy under grant DE-FG02-86ER25013.A000, and by the US Army Research Office through the Mathematical Sciences Institute, Cornell University.     

A globally and quadratically convergent affine scaling method for linearℓ 1 problems

Recently, various interior point algorithms related to the Karmarkar algorithm have been developed for linear programming. In this paper, we first show how this interior point philosophy can be adapted to the linear ₁ problem (in which there are no feasibility constraints) to yield a globally and linearly convergent algorithm. We then show that the linear algorithm can be modified to provide aglobally and ultimatelyquadratically convergent algorithm. This modified algorithm appears to be significantly more efficient in practise than a more straightforward interior point approach via a linear programming formulation: we present numerical results to support this claim.This paper was presented at the Third SIAM Conference on Optimization, in Boston, April 1989.Research partially supported by the Applied Mathematical Sciences Research Program (KC-04-02) of the Office of Energy Research of the U.S. Department of Energy under grant DE-FG02-86ER25013.A000, by the U.S. Army Research Office through the Mathematical Sciences Institute, Cornell University, and by the Computational Mathematics Program of the National Science Foundation under grant DMS-8706133.Research partially supported by the U.S. Army Research Office through the Mathematical Sciences Institute, Cornell University and by the Computational Mathematics Program of the National Science Foundation under grant DMS-8706133.     

Interval iteration for zeros of systems of equations

Easily verifiable existence and convergence conditions are given for a class of interval iteration algorithms for the enclosure of a zero of a system of nonlinear equations. In particular, a quadratically convergent method is obtained which throughout the iteration uses the same interval enclosure of the derivative.     

Hölder continuity of weak solutions of a class of linear equations with boundary degeneracy

This paper deals with a class of linear equations with boundary degeneracy. According to the degenerate ratio, the equations are divided into weakly degenerate ones and strongly degenerate ones, which should be supplemented by different Dirichlet boundary value conditions. After establishing some necessary existence, nonexistence and comparison principles, we investigate the optimal Hölder continuity of weak solutions in these two cases utilizing the Harnack inequality and the Morrey theorem, respectively.     

Newton's method for a class of nonsmooth functions

This paper presents and justifies a Newton iterative process for finding zeros of functions admitting a certain type of approximation. This class includes smooth functions as well as nonsmooth reformulations of variational inequalities. We prove for this method an analogue of the fundamental local convergence theorem of Kantorovich including optimal error bounds.The research reported here was sponsored by the National Science Foundation under Grants CCR-8801489 and CCR-9109345, by the Air Force Systems Command, USAF, under Grants AFOSR-88-0090 and F49620-93-1-0068, by the U. S. Army Research Office under Grant No. DAAL03-92-G-0408, and by the U. S. Army Space and Strategic Defense Command under Contract No. DASG60-91-C-0144. The U. S. Government has certain rights in this material, and is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright notation thereon.     

Potential analysis for a class of diffusion equations: A Gaussian bounds approach

We axiomatically develop a potential analysis for a general class of hypoelliptic diffusion equations under the following basic assumptions: doubling condition and segment property for an underlying distance and Gaussian bounds of the fundamental solution. Our analysis is principally aimed to obtain regularity criteria and uniform boundary estimates for the Perron-Wiener solution to the Dirichlet problem. As an example of application, we also derive an exterior cone criterion of boundary regularity and scale-invariant Harnack inequality and Hölder estimate for an important class of operators in non-divergence form with Hölder continuous coefficients, modeled on Hörmander vector fields.     

A parallel implementation of the restarted GMRES iterative algorithm for nonsymmetric systems of linear equations

We describe the parallelisation of the GMRES(c) algorithm and its implementation on distributed-memory architectures, using both networks of transputers and networks of workstations under the PVM message-passing system. The test systems of linear equations considered are those derived from five-point finite-difference discretisations of partial differential equations. A theoretical model of the computation and communication phases is presented which allows us to decide for which values of the parameterc our implementation executes efficiently. The results show that for reasonably large discretisation grids the implementations are effective on a large number of processors.     

A family of multi-point iterative methods for solving systems of nonlinear equations

We extend to n$n$-dimensional case a known multi-point family of iterative methods for solving nonlinear equations. This family includes as particular cases some well known and also some new methods. The main advantage of these methods is they have order three or four and they do not require the evaluation of any second or higher order Fréchet derivatives. A local convergence analysis and numerical examples are provided.     

Roth’s estimate of the discrepancy of integer sequences is nearly sharp

Letg be a coloring of the set {1, ...,N} = [1,N] in red and blue. For each arithmetic progressionA in [1,N], consider the absolute value of the difference of the numbers of red and of blue members ofA. LetR(g) be the maximum of this number over all arithmetic progression (thediscrepancy ofg). Set over all two-coloringsg. A remarkable result of K. F. Roth gives*R(N)≫N ^1/4. On the other hand, Roth observed thatR(N)≪N ^1/3+ɛ and suggested that this bound was nearly sharp. A. Sárk?zy disproved this by provingR(N)≪N ^1/3+ɛ. We prove thatR(N)=N ^1/4+o(1) thus showing that Roth’s original lower bound was essentially best possible. Our result is more general. We introduce the notion ofdiscrepancy of hypergraphs and derive an upper bound from which the above result follows.     

On diagonally structured problems in unconstrained optimization using an inexact super Halley method

We consider solving the unconstrained minimization problem using an iterative method derived from the third order super Halley method. Each iteration of the super Halley method requires the solution of two linear systems of equations. We show a practical implementation using an iterative method to solve the linear systems. This paper introduces an array of arrays (jagged) data structure for storing the second and third derivative of a multivariate function and suitable termination criteria for the (inner) iterative method to achieve a cubic rate of convergence. Using a jagged compressed diagonal storage of the Hessian matrices and for the tensor, numerical results show that storing the diagonals are more efficient than the row or column oriented approach when we use an iterative method for solving the linear systems of equations.     

On the computational efficiency index and some iterative methods for solving systems of nonlinear equations

In this paper two new iterative methods are built up and analyzed. A generalization of the efficiency index used in the scalar case to several variables in iterative methods for solving systems of nonlinear equations is revisited. Analytic proofs of the local order of convergence based on developments of multilineal functions and numerical concepts that will be used to illustrate the analytic results are given. An approximation of the computational order of convergence is computed independently of the knowledge of the root and the necessary time to get one correct decimal is studied in our examples.     

Incomplete Gröbner basis as a preconditioner for polynomial systems

Precondition plays a critical role in the numerical methods for large and sparse linear systems. It is also true for nonlinear algebraic systems. In this paper incomplete Gröbner basis (IGB) is proposed as a preconditioner of homotopy methods for polynomial systems of equations, which transforms a deficient system into a system with the same finite solutions, but smaller degree. The reduced system can thus be solved faster. Numerical results show the efficiency of the preconditioner.