A new trust region method for nonlinear equations

In this paper, a new trust region method for the system of nonlinear equations is presented in which the determining of the trust region radius incorporates the information of its natural residual. The global convergence is obtained under mild conditions. Unlike traditional trust region method, the superlinear convergence of the method is proven under the local error bound condition. This condition is weaker than the nondegeneracy assumption which is necessary for superlinear convergence of traditional trust region method. We also propose an approximate algorithm for the trust region subproblem. Preliminary numerical experiments are reported. Acknowledgements.The authors are indebted to our supervisor, Professor Y.-X. Yuan, for his excellent guidance and Jorge J. Moré for his subroutine. And we would like to thank the referees for their valuable suggestions and comments.     

Convergence properties of the Runge-Kutta-Chebyshev method

Summary The Runge-Kutta-Chebyshev method is ans-stage Runge-Kutta method designed for the explicit integration of stiff systems of ordinary differential equations originating from spatial discretization of parabolic partial differential equations (method of lines). The method possesses an extended real stability interval with a length proportional tos ². The method can be applied withs arbitrarily large, which is an attractive feature due to the proportionality of withs ². The involved stability property here is internal stability. Internal stability has to do with the propagation of errors over the stages within one single integration step. This internal stability property plays an important role in our examination of full convergence properties of a class of 1st and 2nd order schemes. Full convergence means convergence of the fully discrete solution to the solution of the partial differential equation upon simultaneous space-time grid refinement. For a model class of linear problems we prove convergence under the sole condition that the necessary time-step restriction for stability is satisfied. These error bounds are valid for anys and independent of the stiffness of the problem. Numerical examples are given to illustrate the theoretical results.Dedicated to Peter van der Houwen for his numerous contributions in the field of numerical integration of differential equations.Paper presented at the symposium Construction of Stable Numerical Methods for Differential and Integral Equations, held at CWI, March 29, 1989, in honor of Prof. Dr. P.J. van der Houwen to celebrate the twenty-fifth anniversary of his stay at CWI     

Über Konvergenz von Spektralfolgen der stabilen Homotopietheorie

We discuss the problem of convergence of spectral sequences that arise from a filtration of a spectrum in Boardman's stable homotopy category by applying a generalized homology, homotopy or cohomology theory. The criteria we get give e.g. the convergence of the Adams spectral sequence for a generalized homology theory in certain cases (using similar methods this equestion has been considered independently by J. F. Adams in his forthcoming Chicago lecture notes), and some results on the Adams cohomology spectral sequence including the well-known convergence properties in case of singular cohomology with Z_p-coefficients and complex cobordism.     

The convergence of trigonometric series to functions of bounded variation

Necessary and sufficient conditions are derived for the convergence of a trigonometric series to a function of bounded variation on the interval (, ) [-, ]. For the case in which the coefficients satisfy certain conditions, the continuity of the sum function is investigated.Translated from Matematicheskie Zametki, Vol. 8, No. 1, pp. 47–58, July, 1970.The author wishes to thank his scientific supervisor S. A. Telyakovskii for suggesting this problem and for his interest in the work.     

A cutting-plane algorithm with linear and geometric rates of convergence

This paper presents a cutting-plane algorithm for nonlinear programming which, under suitable conditions, exhibits a linear or geometric global rate of convergence. Other known rates of convergence for cutting-plane algorithms are no better than arithmetic for problems not satisfying a Haar condition. The feature responsible for this improved rate of convergence is the addition at each iteration of a new cut for each constraint, rather than adding only one new cut corresponding to the most violated constraint as is typically the case. Certain cuts can be dropped at each iteration, and there is a uniform upper bound on the number of old cuts retained. Geometric convergence is maintained if the subproblems at each iteration are approximated, rather than solved exactly, so the algorithm is implementable. The algorithm is flexible with respect to the point used to generate new cuts.The author is grateful to W. Oettli for bringing to his attention the linearly convergent cutting-plane algorithm of Ref. 15 and to the referee for a comment that stimulated an extension of the convergence rate results from an earlier version where _k depended on certain parameters of the problem.     

Local convergence analysis of a grouped variable version of coordinate descent

LetF(x,y) be a function of the vector variablesxR ⁿ andyR ^m . One possible scheme for minimizingF(x,y) is to successively alternate minimizations in one vector variable while holding the other fixed. Local convergence analysis is done for this vector (grouped variable) version of coordinate descent, and assuming certain regularity conditions, it is shown that such an approach is locally convergent to a minimizer and that the rate of convergence in each vector variable is linear. Examples where the algorithm is useful in clustering and mixture density decomposition are given, and global convergence properties are briefly discussed.This research was supported in part by NSF Grant No. IST-84-07860. The authors are indebted to Professor R. A. Tapia for his help in improving this paper.     

Analysis of Atkinson’s variable transformation for numerical integration over smooth surfaces in ℝ3

Summary Recently, a variable transformation for integrals over smooth surfaces in ³ was introduced in a paper by Atkinson. This interesting transformation, which includes a grading parameter that can be fixed by the user, makes it possible to compute these integrals numerically via the product trapezoidal rule in an efficient manner. Some analysis of the approximations thus produced was provided by Atkinson, who also stated some conjectures concerning the unusually fast convergence of his quadrature formulas observed for certain values of the grading parameter. In a recent report by Atkinson and Sommariva, this analysis is continued for the case in which the integral is over the surface of a sphere and the integrand is smooth over this surface, and optimal results are given for special values of the grading parameter. In the present work, we give a complete analysis of Atkinsons method over arbitrary smooth surfaces that are homeomorphic to the surface of the unit sphere. We obtain optimal results that explain the actual rates of convergence, and we achieve this for all values of the grading parameter.     

A convergence theory for an overlapping Schwarz algorithm using discontinuous iterates

Summary. A new type of overlapping Schwarz methods, using discontinuous iterates, is constructed by modifying the classical overlapping Schwarz algorithm. This new algorithm allows for discontinuous iterates across the artificial interface. For Poissons equation, this algorithm can be considered as an overlapping version of Lions Robin iteration method for which little is known concerning the rate of convergence. Since overlap improves the performance of the classical algorithms considerably, the existence of a uniform convergence factor is the fundamental question for our algorithm. A new theory using Lagrange multipliers is developed and conditions are found for the existence of an almost uniform convergence factor for the dual variables, which implies rapid convergence of the primal variables, in the two overlapping subdomain case. Our result also shows a relation between the boundary conditions of the given problem and the artificial interface condition. Numerical results for the general case with cross points are also presented. They indicate possible extensions of our results to this more general case.Mathematics Subject Classification (2000): 65F10, 65N30, 65N55Acknowledgement I would like to thank my advisor Olof Widlund for suggesting this problem, for many helpful and interesting discussions, and for all his encouragement. I also thank the referees for their helpful corrections and suggestions.     

Expandibility in eigenfunctions of the Laplacian in a two-dimension region

The convergence is established of the expansion of functions of H _p not satisfying any boundary conditions, in Fourier series with respect to a fundamental system of functions of the Laplace operator in any two-dimensional region with a rectifiable boundary.Translated from Matematicheskie Zametki, Vol. 9, No. 6, pp. 609–616, June, 1971.The author expresses his gratitude to V. A. II'in for suggesting this problem and for his interest in the work.     

Where there’s a Will there’s a way – the research of Will Light

This paper describes the work of Will Light, who died on December 8th, 2002. It highlights his contributions in the study of minimal norm projections, tensor product approximation (including the convergence of the Diliberto–Straus algorithm), proximinality, radial and ridge function approximation, both via quasi-interpolation and interpolation. My aim is not only to describe the impact of Wills work, but also to convey some of his impact as a person.     

A global Newton method II: Analytic centers

This paper modifies the convergence conditions of a back-tracking global Newton method announced in Goldstein (1991), making them sharper and easier to apply. A new version of the Kantorovich inequalities is presented that is simple to state and prove. An application is made to the centering problem for polytopes. Based on an idea of Ye (1989), an algorithm is given for the feasibility problem of linear inequalities.This paper is dedicated to Phil Wolfe on the occasion of his 65th birthday.     

On weak convergence of stocastic processes with Lusin path spaces

Under the assumption that a sequence of stochastic processes has paths in a Lusin function space we can prove the following. If convergence in the path space implies stochastic convergence, then tightness and convergence of the finite dimensional distributions of the stochastic processes are sufficient for weak convergence. The result in many cases implies a unification of the weak convergence proof. Demonstrably, such cases are C, D, Lip, L_p and , the space of distribution functions of finite measures.     

Compactness of probability measures and the uniform convergence of certain stochastic series

We give the conditions which ensure the compactness of the probability measures _n, n1, generated by Gaussian processes the realizations of which are continuous with unit probability in [0, 1]. We also give the conditions for the uniform convergence of stochastic series of the form _{k=1 2k}(t), where the _k(t) are independent Gaussian processes the realizations of which are continuous with unit probability in [0, 1].Translated from Matematicheskie Zametki, Vol. 12, No. 4, pp. 443–451, October, 1972.In conclusion the author wishes to express his deep gratitude to Yu. V. Kozachenko for formulating the problem and for his attention to the paper.     

μ-Statistically Convergent Function Sequences

In the present paper we are concerned with convergence in -density and -statistical convergence of sequences of functions defined on a subset D of real numbers, where is a finitely additive measure. Particularly, we introduce the concepts of -statistical uniform convergence and -statistical pointwise convergence, and observe that -statistical uniform convergence inherits the basic properties of uniform convergence.     

On the convergence of the projected gradient method

We study the projected gradient algorithm for linearly constrained optimization. Wolfe (Ref. 1) has produced a counterexample to show that this algorithm can jam. However, his counterexample is only ¹( ⁿ ), and it is conjectured that the algorithm is convergent for ²-functions. We show that this conjecture is partly right. We also show that one needs more assumptions to prove convergence, since we present a family of counterexamples. We finally give a demonstration that no jamming can occur for quadratic objective functions.This work was supported by the Natural Sciences and Engineering Research Council of Canada     

On the Convergence Behaviour of Variable Stepsize Multistep Methods for Singularly Perturbed Problems

In this note, we investigate the convergence behaviour of linear multistep discretizations for singularly perturbed systems, emphasising the features of variable stepsizes. We derive a convergence result for A()-stable linear multistep methods and specify a refined error estimate for backward differentiation formulas. Important ingredients in our convergence analysis are stability bounds for non-autonomous linear problems that are obtained by perturbation techniques.     

Etude de l'algorithme de Rémès en l'absence de condition de Haar

Summary Using a geometric interpretation, the unicity of a best approximation and the convergence of the Remes-algorithm without the Haar-condition are investigated (in the case of the Tchebycheff-approximation of a continuous function by a linear combination of two continuous functions). Replacing the Haar-condition by a weaker one which is generally satisfied, one obtains a convergence theorem that is weaker than the classical convergence theorem but is sufficient for the applicatons. A generalization of these results is indicated.     

Global and Superlinear Convergence of a Restricted Class of Self-Scaling Methods with Inexact Line Searches, for Convex Functions

This paper studies the convergence properties of algorithms belonging to the class of self-scaling (SS) quasi-Newton methods for unconstrained optimization. This class depends on two parameters, say _k and _k , for which the choice _k =1 gives the Broyden family of unscaled methods, where _k =1 corresponds to the well known DFP method. We propose simple conditions on these parameters that give rise to global convergence with inexact line searches, for convex objective functions. The q-superlinear convergence is achieved if further restrictions on the scaling parameter are introduced. These convergence results are an extension of the known results for the unscaled methods. Because the scaling parameter is heavily restricted, we consider a subclass of SS methods which satisfies the required conditions. Although convergence for the unscaled methods with _k 1 is still an open question, we show that the global and superlinear convergence for SS methods is possible and present, in particular, a new SS-DFP method.     

Derivative free two-point methods with and without memory for solving nonlinear equations

Two families of derivative free two-point iterative methods for solving nonlinear equations are constructed. These methods use a suitable parametric function and an arbitrary real parameter. It is proved that the first family has the convergence order four requiring only three function evaluations per iteration. In this way it is demonstrated that the proposed family without memory supports the Kung-Traub hypothesis (1974) on the upper bound 2ⁿ of the order of multipoint methods based on n + 1 function evaluations. Further acceleration of the convergence rate is attained by varying a free parameter from step to step using information available from the previous step. This approach leads to a family of two-step self-accelerating methods with memory whose order of convergence is at least and even in special cases. The increase of convergence order is attained without any additional calculations so that the family of methods with memory possesses a very high computational efficiency. Numerical examples are included to demonstrate exceptional convergence speed of the proposed methods using only few function evaluations.     

The convergence of spline collocation for strongly elliptic equations on curves

Summary Most boundary element methods for two-dimensional boundary value problems are based on point collocation on the boundary and the use of splines as trial functions. Here we present a unified asymptotic error analysis for even as well as for odd degree splines subordinate to uniform or smoothly graded meshes and prove asymptotic convergence of optimal order. The equations are collocated at the breakpoints for odd degree and the internodal midpoints for even degree splines. The crucial assumption for the generalized boundary integral and integro-differential operators is strong ellipticity. Our analysis is based on simple Fourier expansions. In particular, we extend results by J. Saranen and W.L. Wendland from constant to variable coefficient equations. Our results include the first convergence proof of midpoint collocation with piecewise constant functions, i.e., the panel method for solving systems of Cauchy singular integral equations.Dedicated to Prof. Dr. Dr. h.c. mult. Lothar Collatz on the occasion of his 75th birthdayThis work was begun at the Technische Hochschule Darmstadt where Professor Arnold was supported by a North Atlantic Treaty Organization Postdoctoral Fellowship. The work of Professor Arnold is supported by NSF grant BMS-8313247. The work of Professor Wendland was supported by the Stiftung Volkswagenwerk