On the Local and Superlinear Convergence of Quasi-Newton Methods

This paper presents a local convergence analysis for severalwell-known quasi-Newton methods when used, without line searches,in an iteration of the form to solve for x^* such that Fx^* = 0. The basic idea behind theproofs is that under certain reasonable conditions on x_o, Fand x_o, the errors in the sequence of approximations {H_k} toF'(x^*)^–1 can be shown to be of bounded deterioration inthat these errors, while not ensured to decrease, can increaseonly in a controlled way. Despite the fact that H_k is not shownto approach F'(x^*)^–1, the methods considered, includingthose based on the single-rank Broyden and double-rank Davidon-Fletcher-Powellformulae, generate locally Q-superlinearly convergent sequences{x_k}.     

Multiquadratic Extensions, Rigid Fields and Pythagorean Fields

Let F be a field of characteristic other than 2. Let F⁽²⁾ denotethe compositum over F of all quadratic extensions of F, letF⁽³⁾ denote the compositum over F⁽²⁾ of all quadratic extensionsof F⁽²⁾ that are Galois over F, and let F^{3} denote the compositumover F⁽²⁾ of all quadratic extensions of F⁽²⁾. This paper showsthat F⁽³⁾ = F^{3} if and only if F is a rigid field, and thatF⁽³⁾ = K⁽³⁾ for some extension K of F if and only if F is Pythagoreanand . The proofs depend mainly on the behavior of quadratic forms over quadratic extensions,and the corresponding norm maps.     

Arithmetical Results on Certain Multivariate Power Series

Power series with non-zero convergence radius R(f) are considered, and the arithmeticalnature (that is, irrationality, or even transcendence) of thecorresponding multivariate series is studied if x₁, ..., x_m and the sequence (f(n)) satisfy appropriatearithmetical conditions. It follows that such arithmetical resultscan be written down easily if linear independence results onthe function F(x), defined in |x| < R(f) by the originalone-dimensional power series, and possibly its derivatives atthe points x_µ are known. Some typical applications areexplicitly stated. 2000 Mathematics Subject Classification 11J72.     

On the Convergence of Newton’s Method for Polynomial Equations and Applications in Radiative Transfer

 Newton’s method is used to approximate a locally unique zero of a polynomial operator F of degree in Banach space. So far, convergence conditions have been found for Newton’s method based on the Newton-Kantorovich hypothesis that uses Lipschitz-type conditions and information only on the first Fréchet-derivative of F. Here we provide a new semilocal convergence theorem for Newton’s method that uses information on all Fréchet-derivatives of F except the first. This way, we obtain sufficient convergence conditions different from the Newton-Kantorovich hypothesis. Our results are extended to include the case when F is a nonlinear operator whose kth Fréchet-derivative satisfies a H?lder continuity condition. An example is provided to show that our conditions hold where all previous ones fail. Moreover, some applications of our results to the solution of polynomial systems and differential equations are suggested. Furthermore, our results apply to solve a nonlinear integral equation appearing in radiative transfer in connection with the problem of determination of the angular distribution of the radiant-flux emerging from a plane radiation field. Received 9 December 1997 in revised form 30 March 1998     

Cerf Theory for Graphs

We develop a deformation theory for k-parameter families ofpointed marked graphs with fixed fundamental group F_n. Applicationsinclude a simple geometric proof of stability of the rationalhomology of Aut(F_n), computations of the rational homology insmall dimensions, proofs that various natural complexes of freefactorizations of F_n are highly connected, and an improvementon the stability range for the integral homology of Aut(F_n).     

Optimal rates of convergence in the Weibull model based on kernel-type estimators

Let F be a distribution function in the maximal domain of attraction of the Gumbel distribution such that −log(1−F(x))=x^1/θL(x) for a positive real number θ, called the Weibull tail index, and a slowly varying function L. It is well known that the estimators of θ have a very slow rate of convergence. We establish here a sharp optimality result in the minimax sense, that is when L is treated as an infinite dimensional nuisance parameter belonging to some functional class. We also establish the rate optimal asymptotic property of a data-driven choice of the sample fraction that is used for estimation.     

Some Properties of Free Groups of Some Soluble Varieties of Groups

Let F be a free group, and let _n(F) be the nth term of the lowercentral series of F. It is proved that F/[_j(F), _i(F), _k(F)]and F/[_j(F), _i(F), _k(F), _l(F)] are torsion free and residuallynilpotent for certain values of i, j, k and i, j, k, l, respectively.In the process of proving this, it is proved that the analogousLie rings are torsion free.     

State models and asymptotic behaviour of 2D positive systems

Homogeneous 2D positive systems are 2D state-space models whosevariables are alwalys nonnegative and, consequently, are describedby a pair of nonnegative square matrices (A, B). In the paper,the properties of these pairs are discussed both in the generalcase and under particular assumptions like finite memory, separability,and property L. Various aspects of the positive asymptotic dynamic are considered;in particular, sufficient conditions are provided guaranteeingthat the local states are eventually strictly positive. Finally,some results on the convergence of the states towards a constantasymptotic distribution are presented.     

Elliptic and Hyperelliptic Curves Over Supersimple Fields

It is proved that if F is an infinite field with characteristicdifferent from 2, whose theory is supersimple, and C is an ellipticor hyperelliptic curve over F with generic ‘modulus’,then C has a generic F-rational point. The notion of generityhere is in the sense of the supersimple field F.     

A sharp convergence estimate for the method of subspace corrections for singular systems of equations

This paper is devoted to the convergence rate estimate for the method of successive subspace corrections applied to symmetric and positive semidefinite (singular) problems. In a general Hilbert space setting, a convergence rate identity is obtained for the method of subspace corrections in terms of the subspace solvers. As an illustration, the new abstract theory is used to show uniform convergence of a multigrid method applied to the solution of the Laplace equation with pure Neumann boundary conditions.

     

A Sixth-order Tridiagonal Finite Difference Method for General Non-linear Two-point Boundary Value Problems

We present a sixth-order finite difference method for the generalsecond-order non-linear differential equation Y"=f(x, y, y')subject to the boundary conditions y(a) = A, y(b) = B. In thecase of linear differential equations, our finite differencescheme leads to tridiagonal linear systems. We establish, underappropriate conditions, O(h⁶)-convergence of the finite differencescheme. Numerical examples are given to illustrate the methodand its sixth-order convergence.     

On the Geometry of the Automorphism Group of a Free Group

The groups Aut(F₃) and Out(F₃) satisfy strictly exponentialisoperimetric inequalities; in particular, they are not automatic.For n 3, Aut (F_n) and Out (F_n) do not admit bounded bicombingsof sub-exponential length, hence they cannot act properly andcocompactly by isometries on any simply-connected space of non-positivecurvature, and they are not biautomatic.     

Complex Dynamics of Convergence Acceleration

Generalized Steffensen methods are nonderivative algorithmsfor the computation of fixed points of a function f. They replacethe functional iteration Z_m+1=f(Z_m) with Z_m+1=F_n(Z_m, where F_nis explicitly provided for every n 1 as a quotient of two Hankeldeterminants. In this paper we derive rules pertaining to thelocal behaviour of these methods. Specifically, and subjectto analyticity, given that is a bounded fixed point of f, thenit is also a fixed point of F_n. Moreover, unless f'() vanishesor is a root of unity, becomes a superattractive fixed pointof F_n of degree n; if f'() is a root of unity of minimal degreeq2, then is (as a fixed point of F_n) superattractive of degreemin {q-1, n}; if f'()=1, then is attractive for F_n; and, finally,if is superattractive of degree s (as a fixed point of f),then it becomes superattractive of degree (s + 1)^n–1(ns+ s + 1)–1. Attractivity rules change at infinity (providedthat f()=). Broadly speaking, infinity becomes less attractivefor F_n, Since one is interested in convergence to finite fixedpoints, this further enhances the appeal of generalized Steffensenmethods.     

Rigidity of Continuous Coboundaries

We consider the functional equation F_oT–F=f, where T isa measure-preserving transformation and f is a continuous function.We show that if there is an L function F which satisfies thisequation, then F is constrained to satisfy a number of regularityconditions, and, in particular, if T is a one-sided Bernoullishift, then we show that there is a continuous function F satisfyingthis equation. We show that this is not the case for the two-sidedshift. 1991 Mathematics Subject Classification 28D05, 58F11.     

Ergodicity and mixing of non-commuting epimorphisms

We study mixing properties of epimorphisms of a compact connectedfinite-dimensional abelian group X. In particular, we show thata set F, with |F| > dim X, of epimorphisms of X is mixingif and only if every subset of F of cardinality (dim X) + 1is mixing. We also construct examples of free non-abelian groupsof automorphisms of tori which are mixing, but not mixing oforder 3, and show that, under some irreducibility assumptions,ergodic groups of automorphisms contain mixing subgroups andfree non-abelian mixing subsemigroups.     

Binary Quadratic Forms with Large Discriminants and Sums of Two Squareful Numbers II

Let F = (F₁, ..., F_m) be an m-tuple of primitive positive binaryquadratic forms and let U_F(x) be the number of integers notexceeding x that can be represented simultaneously by all theforms F_j, j = 1, ... , m. Sharp upper and lower bounds for U_F(x)are given uniformly in the discriminants of the quadratic forms. As an application, a problem of Erds is considered. Let V(x)be the number of integers not exceeding x that are representableas a sum of two squareful numbers. Then V(x) = x(log x)^–+o(1)with = 1 – 2^–1/3 = 0.206....     

Some Remarks on p-Adic Analytic Groups

A theorem of Maranda [1, Section 30] states that if F is a finitegroup, p is a prime and p^e exactly divides |F|, then a Z_pF-latticeM is determined up to isomorphism by its finite quotient M/p^e+1M.If M is a free Z_p-module of rank d, this is equivalent to sayingthat representations of F in GL_d(Z_p) are determined up to equivalenceby their images modulo p^e+1. 1991 Mathematics Subject Classification20E18, 22E20.     

Self-Similarity and Probability: Parameters Describing the Geometry of Cantor Sets

A deterministic self-similar Cantor set F defines a naturalprobability space, the elements of which are neighbourhoodsof various sizes of all points in F. Considering random variableson this probability space, some porosity and density parametersare explicitly calculated. 1991 Mathematics Subject Classification28A80, 60D05.     

Invariant Curves by Vector Fields on Algebraic Varieties

If C is a reduced curve which is invariant by a one-dimensionalfoliation F of degree d_F on the projective space then it isshown that d_F–1+a is a bound for the quotient of the twocoefficients of the Hilbert–Samuel polynomial for C, wherea is an integer obtained from a concrete problem of imposingsingularities to projective hypersurfaces, and so a bound isobtained for the degree of C when it is a complete intersection.Concrete values of a can be derived for several interestingapplications. The results are presented in the form of intersection-theoreticalinequalities for one-dimensional foliations on arbitrary smoothalgebraic varieties.