An automatic search procedure for finding real zeros

Summary The paper describes the implementation of a globally convergent iterative algorithm for determining all the real zeros of certain classes of functions in any given interval. The algorithm is developed in terms of Ostrowski's square root formula and in the case of polynomials the relation with Laguerre's formula is obtained. A device is incorporated for overcoming the problem of numerical instability together with a number of associated devices for ensuring that no zeros have been missed. Application of the method is illustrated by two examples having clustered zeros.     

A method of solving nonlinear variational problems by nonlinear transformation of the objective functional. Part I

Summary A general globally convergent iterative method for solving nonlinear variational problems is introduced. The method is applied to a temperature control problem and to the minimal surface problem. Several aspects of finite element implementation of the method are discussed.     

The Durand-Kerner polynomials roots-finding method in case of multiple roots

The convergence of the Durand-Kerner algorithm is quadratic in case of simple roots but only linear in case of multiple roots. This paper shows that, at each step, the mean of the components converging to the same root approaches it with an error proportional to the square of the error at the previous step. Since it is also shown that it is possible to estimate the multiplicity order of the roots during the algorithm, a modification of the Durand-Kerner iteration is proposed to preserve a quadratic-like convergence even in case of multiple zeros.This work is supported in part by the Research Program C3 of the French CNRS and MEN, and by the Direction des Recherches et Etudes Techniques (DGA).     

On the relation between quadratic termination and convergence properties of minimization algorithms

Summary It is shown that the theory developed in part I of this paper [22] can be applied to some well-known minimization algorithms with the quadratic termination property to prove theirn-step quadratic convergence. In particular, some conjugate gradient methods, the rank-1-methods of Pearson and McCormick (see Pearson [18]) and the large class of rank-2-methods described by Oren and Luenberger [16, 17] are investigated.This work was supported in part at Stanford University, Stanford, California, under Energy Research and Development Administration, Contract E(04-3) 326 PA No. 30, and National Science Foundation Grant DCR 71-01996 A04 and in part by the Deutsche Forschungsgemeinschaft     

Superlinear convergence of symmetric Huang's class of methods

Summary In this paper the problem of minimizing the functionalf:DR ⁿ R is considered. Typical assumptions onf are assumed. A class of Quasi-Newton methods, namely Huang's class of methods is used for finding an optimal solution of this problem. A new theorem connected with this class is presented. By means of this theorem some convergence results known up till now only for the methods which satisfy Quasi-Newton condition are extended, that is the results of superlinear convergence of variable metric methods in the cases of exact and asymptotically exact minimization and the so-called direct-prediction case. This theorem allows to interpretate one of the parameters as the scaling parameter.     

Imperfect conjugate gradient algorithms for extended quadratic functions

Summary Generalized conjugate gradient algorithms which are invariant to a nonlinear scaling of a strictly convex quadratic function are described. The algorithms when applied to scaled quadratic functionsfR _n R ₁ of the formf(x)=h(F(x)) withF(x) strictly convex quadratic andhC ¹(R ₁) an arbitrary strictly monotone functionh generate the same direction vectors as for the functionF without perfect steps.     

A generalized conjugate gradient algorithm for minimization

Summary A generalized conjugate gradient algorithm which is invariant to a nonlinear scaling of a strictly convex quadratic function is described, which terminates after at mostn steps when applied to scaled quadratic functionsf: R _n R₁ of the formf(x)=h(F(x)) withF(x) strictly convex quadratic andhC ¹ (R₁) an arbitrary strictly monotone functionh. The algorithm does not suppose the knowledge ofh orF but only off(x) and its gradientg(x).     

Ein Abstiegsverfahren für Approximationsaufgaben in normierten Räumen

Summary A numerical method for constrained approximation problems in normed linear spaces is presented. The method uses extremal subgradients of the norms or sublinear functionals involved in the approximation problem considered. Under certain weak assumptions the convergence of the method is proved. For various normed spaces hints for practical realization are given and several numerical examples are described.

---

Ein Abstiegsverfahren für Approximationsaufgaben in normierten Räumen

     

Local convergence analysis for partitioned quasi-Newton updates

Summary This paper considers local convergence properties of inexact partitioned quasi-Newton algorithms for the solution of certain non-linear equations and, in particular, the optimization of partially separable objective functions. Using the bounded deterioration principle, one obtains local and linear convergence, which impliesQ-superlinear convergence under the usual conditions on the quasi-Newton updates. For the optimization case, these conditions are shown to be satisfied by any sequence of updates within the convex Broyden class, even if some Hessians are singular at the minimizer. Finally, local andQ-superlinear convergence is established for an inexact partitioned variable metric method under mild assumptions on the initial Hessian approximations.Work supported by a research grant of the Deutsche Forschungsgemeinschaft, Bonn and carried out at the Department of Applied Mathematics and Theoretical Physics Cambridge (United Kingdom)     

Sur la convergence théorique de la méthode du gradient réduit généralisé

Summary The theoretical convergence of Generalized Reduced Gradient Method (GRG) has not been proved; the purpose of this paper is to propose two theoritical and general variants of the original method and a proof of their convergence.

     

Über die globale Konvergenz von Variable-Metrik-Verfahren mit nicht-exakter Schrittweitenbestimmung

Summary We consider unconstrained minimization problems and the application of the Broyden-Fletcher-Goldfarb-Shanno variable metric algorithm without exact line searches. For a certain class of step functions the global convergence of this method is proven, generalizing a result given by Powell. Furthermore some remarks are made concerning the superlinear convergence of this particular variable metric algorithm.

     

Quasi-Newton-Verfahren vom Rang-Eins-Typ zur Lösung unrestringierter Minimierungsprobleme

Summary In this paper new Quasi-Newton methods of rank-one type for solving the unconstrained minimization problem are developed. The methods belong to the Oren-Luenberger class (for negative parameters _k ) and they generate always positive definite updating matrices. Moreover it is shown that these methods are invariant by scaling of the objective function.

     

Some supplementary results on the 1+\sqrt 2 order method for the solution of nonlinear equations

Summary Recently an iterative method for the solution of systems of nonlinear equations having at leastR-order 1+ for simple roots has been investigated by the author [7]; this method uses as many function evaluations per step as the classical Newton method. In the present note we deal with several properties of the method such as monotone convergence, asymptotic inclusion of the solution and convergence in the case of multiple roots.     

Numerical computation of branch points in nonlinear equations

Summary The numerical computation of branch points in systems of nonlinear equations is considered. A direct method is presented which requires the solution of one equation only. The branch points are indicated by suitable testfunctions. Numerical results of three examples are given.     

On quadratic-like convergence of the means for two methods for simultaneous rootfinding of polynomials

Durand-Kerner's method for simultaneous rootfinding of a polynomial is locally second order convergent if all the zeros are simple. If this condition is violated numerical experiences still show linear convergence. For this case of multiple roots, Fraigniaud [4] proves that the means of clustering approximants for a multiple root is a better approximant for the zero and called this Quadratic-Like-Convergence of the Means.This note gives a new proof and a refinement of this property. The proof is based on the related Grau's method for simultaneous factoring of a polynomial. A similar property of some coefficients of the third order method due to Börsch-Supan, Maehly, Ehrlich, Aberth and others is proved.     

On the convergence order of accelerated root iterations

Summary A Gauss-Seidel procedure for accelerating the convergence of the generalized method of the root iterations type of the (k+2)-th order (kN) for finding polynomial complex zeros, given in [7], is considered in this paper. It is shown that theR-order of convergence of the accelerated method is at leastk+1+ _n (k), where _n (k)>1 is the unique positive root of the equation ⁿ --k-1 = 0 andn is the degree of the polynomial. The examples of algebraic equations in ordinary and circular arithmetic are given.     

Optimal solution of nonlinear equations satisfying a Lipschitz condition

Summary For a given nonnegative we seek a pointx ^* such that |f(x ^*)| wheref is a nonlinear transformation of the cubeB=[0,1] ^m into (or ^p ,p>1) satisfying a Lipschitz condition with the constantK and having a zero inB.The information operator onf consists ofn values of arbitrary linear functionals which are computed adaptively. The pointx ^* is constructed by means of an algorithm which is a mapping depending on the information operator. We find an optimal algorithm, i.e., algorithm with the smallest error, which usesn function evaluations computed adaptively. We also exhibit nearly optimal information operators, i.e., the linear functionals for which the error of an optimal algorithm that uses them is almost minimal. Nearly optimal information operators consists ofn nonadaptive function evaluations at equispaced pointsx _j in the cubeB. This result exhibits the superiority of the T. Aird and J. Rice procedure ZSRCH (IMSL library [1]) over Sobol's approach [7] for solving nonlinear equations in our class of functions. We also prove that the simple search algorithm which yields a pointx ^*=x _k such that is nearly optimal. The complexity, i.e., the minimal cost of solving our problem is roughly equal to (K/) ^m .     

Root finding by divided differences

Summary A recursive method is presented for computing a simple zero of an analytic functionf from information contained in a table of divided differences of its reciprocalh=1/f. A good deal of flexibility is permitted in the choice of ordinate and derivative values, and in the choice of the number of previous points upon which to base the next estimate of the required zero.The method is shown to be equivalent to a process of fitting rational functions with linear numerators to data sampled fromf. Asymptotic and regional convergence properties of such a process have already been studied; in particular, asymptotically quadratic convergence is easily obtained, at the expense of only one function evaluation and a moderate amount of overhead computation per step. In these respects the method is comparable with the Newton form of iterated polynomial inverse interpolation, while its regional convergence characteristics may be superior in certain circum-stances.It is also shown that the method is not unduly sensitive to round-off errors.     

Über die Einzugsbereiche der Nullstellen von Polynomen beim Newton-Verfahren

Summary The region of attraction of a zero of a polynomial consists of those points from which the Newton method may be started when this zero is to be computed. The regions of attraction are approximately characterized by studying a continuous analog of the Newton method.

     

Convergence of the multigrid full approximation scheme for a class of elliptic mildly nonlinear boundary value problems

Summary The multigrid full approximation scheme (FAS MG) is a well-known solver for nonlinear boundary value problems. In this paper we restrict ourselves to a class of second order elliptic mildly nonlinear problems and we give local conditions, e.g. a local Lipschitz condition on the derivative of the continuous operator, under which the FAS MG with suitably chosen parameters locally converges. We prove quantitative convergence statements and deduce explicit bounds for important quantities such as the radius of a ball of guaranteed convergence, the number of smoothings needed, the number of coarse grid corrections needed and the number of FAS MG iterations needed in a nested iteration. These bounds show well-known features of the FAS MG scheme.