Absolute monotonicity of polynomials occurring in the numerical solution of initial value problems

Summary This paper deals with polynomial approximations ø(x) to the exponential function exp(x) related to numerical procedures for solving initial value problems. Motivated by positivity and contractivity requirements imposed on these numerical procedures we study the smallest negative argument, denoted by –R(ø), at which ø is absolutely monotonic. For given integersp1,m1 we determine the maximum ofR(ø) when ø varies over the class of all polynomials of a degree m with (forx0).     

A finite element method for a singularly perturbed boundary value problem

Summary We examine the problem:u+a(x)u–b(x)u=f(x) for 0<x<1,a(x)>0,b(x)>, ² = 4>0,a, b andf inC ² [0, 1], in (0, 1],u(0) andu(1) given. Using finite elements and a discretized Green's function, we show that the El-Mistikawy and Werle difference scheme on an equidistant mesh of widthh is uniformly second order accurate for this problem (i.e., the nodal errors are bounded byCh ², whereC is independent ofh and ). With a natural choice of trial functions, uniform first order accuracy is obtained in theL (0, 1) norm. On choosing piecewise linear trial functions (hat functions), uniform first order accuracy is obtained in theL ¹ (0, 1) norm.     

Constructive characterization ofA-stable approximations to exp(z) and its connection with algebraically stable Runge-Kutta methods

Summary All rational approximations to exp(z) of order 2m– (m denotes the maximal degree of nominator and denominator) are given by a closed formula involving real parameters. Using the theory of order stars [9], necessary and sufficient conditions forA-stability (respectivelyI-stability) are given. On the basis of this characterization relations between the concepts ofA-stability and algebraic stability (for implicit Runge-Kutta methods) are investigated. In particular we can partly prove the conjecture that to any irreducibleA-stableR(z) of oderp0 there exist algebraically stable Runge-Kutta methods of the same order withR(z) as stability function.     

Small potential corrections for the discrete eigenvalues of the Sturm-Liouville problem

Summary The inverse Sturm-Liouville problem is the problem of finding a good approximation of a potential functionq such that the eigenvalue problem (^*)–y +qy=y holds on (0, ) fory(0)=y()=0 and a set of given eigenvalues . Since this problem has to be solved numerically by discretization and since the higher discrete eigenvalues strongly deviate from the corresponding Sturm-Liouville eigenvalues , asymptotic corrections for the 's serve to get better estimates forq. Let _k (1kn) be the first eigenvalues of (^*), let _k be the corresponding discrete eigenvalues obtained by the finite element method for (^*) and let _{k k} for the special caseq=0. Then, starting from an asymptotic correction technique proposed by Paine, de Hoog and Anderssen, new estimates for the errors of the corrected discrete eigenvalues are obtained and confirm and improve the knownO(kh ²)(h:=/(n+1)) behaviour. The estimates are based on new Sobolev inequalities and on Fourier analysis and it is shown that for 4+c ₂ k(n+1)/2, wherec ₁ andc ₂ are constants depending onq which tend to 0 for vanishingq.     

Black holes on the plane drawn by a Wiener process

Summary We say that the discD()R ², of radius , located around the origin isp-covered in timeT by a Wiener processW(·) if for anyzD() there exists a 0tT such thatW(t) is a point of the disc of radiusp, located aroundz. The supremum of those 's (0) is studied for which,D() isp-covered inT.     

Pointwise accuracy of a finite element method for nonlinear variational inequalities

Summary Consider the following quasilinear elliptic PDE, which is equivalent to a nonlinear variational inequality: –divF(u)+(u)f. Here is a singular maximal monotone graph and the nonlinear differential operator is only assumed to be monotone; surfaces of prescribed mean curvature over obstacles may thus be viewed as relevant examples. The numerical approximation proposed in this paper consists of combining continuous piecewise linear finite elements with a preliminary regularization of . The resulting scheme is shown to be quasi-optimally accurate inL . The underlying analysis makes use of both a topological technique and a sharpL ^p -duality argument.This work was partially supported by Consiglio Nazionale delle Ricerche of Italy while the author was in residence at the Istituto di Analisi Numerica del C.N.R. di Pavia     

Numerical application of Euler's series transformation and its generalizations

Summary A nonlinear generalizationÊ _z of Euler's series transformation is compared with the (linear) Euler-Knopp transformationE _z and a twoparametric methodE . It is shown how to applyE orE _, to compute the valuef(z_o) of a functionf from the power series at 0 iff is holomorphic in a half plane or in the cut plane. BothE andE _, are superior toÊ _z . A compact recursive algorithm is given for computingE andE _,.     

Acceleration of convergence for finite element solutions of the Poisson equation

Summary Letu _h be the finite element solution to–u=f with zero boundary conditions in a convex polyhedral domain . Fromu _h we calculate for eachz and ||1 an approximationu _h ^– (z) toD u(z) with |D u(z)–u _h ^– (z)|=O(h ^2k–2) wherek is the order of the finite elements. The same superconvergence order estimates are obtained also for the boundary flux. We need not work on a regular mesh but we have to compute averages ofu _h where the diameter of the domain of integration must not depend onh.     

Logarithms and imaginary powers of closed linear operators

The imaginary powersA ^it of a closed linear operatorA, with inverse, in a Banach spaceX are considered as aC ₀-group {exp(itlogA);t R} of bounded linear operators onX, with generatori logA. Here logA is defined as the closure of log(1+A) – log(1+A ^–1). LetA be a linearm-sectorial operator of typeS(tan ), 0(/2), in a Hilbert spaceX. That is, |Im(Au, u)| (tan )Re(Au, u) foru D(A). Then ±ilog(1+A) ism-accretive inX andilog(1+A) is the generator of aC ₀-group {(1+A) ^it ;t R} of bounded imaginary powers, satisfying the estimate (1+A) ^it exp(|t|),t R. In particular, ifA is invertible, then ±ilogA ism-accretive inX, where logA is exactly given by logA=log(1+A)–log(1+A ^–1), and {A ^it;t R} forms aC ₀-group onX, with the estimate A ^it exp(|t|),t R. This yields a slight improvement of the Heinz-Kato inequality.     

A priori-Schranken für diskrete Lösungen monotoner Operatorgleichungen und Anwendungen

Summary Operator equationsTu=f are approximated by Galerkin's method, whereT is a monotone operator in the sense of Browder and Minty, so that existence results are available in a reflexive Banach spaceX. In a normed spaceY error estimates are established, which require a priori bounds for the discrete solutionsu _h in the norm of a suitable space . Sufficient conditions for the uniform boundedness u _{h Z} =O(1) ash0 are proved. Well-known error estimates in [3] for the special caseX=Y=Z are generalized by this. The theory is applied to quasilinear elliptic boundary value problems of order 2m in a bounded domain . The approximating subspaces are finite element spaces. Especially the caseX=W ₀ ^{m, p} (), 1<p<,Y=W ₀ ^{m. 2} (),Z=W ₀ ^{m. max (2,p)} ()W^m, () is treated. Some examples for 1<p<2 are considered. Forp2 a refined technique is introduced in the author's paper [7].

     

Quasi-conformal mapping theorem and bifurcations

LetH be a germ of holomorphic diffeomorphism at 0 . Using the existence theorem for quasi-conformal mappings, it is possible to prove that there exists a multivalued germS at 0, such thatS(ze ²ⁱ )=HS(z) (1). IfH is an unfolding of diffeomorphisms depending on (,0), withH ₀=Id, one introduces its ideal . It is the ideal generated by the germs of coefficients (a _i (), 0) at 0 ^k , whereH (z)–z=a _i ()z ⁱ . Then one can find a parameter solutionS (z) of (1) which has at each pointz ₀ belonging to the domain of definition ofS ₀, an expansion in seriesS (z)=z+b _i ()(z–z ₀) ⁱ with , for alli.This result may be applied to the bifurcation theory of vector fields of the plane. LetX be an unfolding of analytic vector fields at 0 ² such that this point is a hyperbolic saddle point for each . LetH (z) be the holonomy map ofX at the saddle point and its associated ideal of coefficients. A consequence of the above result is that one can find analytic intervals , , transversal to the separatrices of the saddle point, such that the difference between the transition mapD (z) and the identity is divisible in the ideal . Finally, suppose thatX is an unfolding of a saddle connection for a vector fieldX ₀, with a return map equal to identity. It follows from the above result that the Bautin ideal of the unfolding, defined as the ideal of coefficients of the difference between the return map and the identity at any regular pointz, can also be computed at the singular pointz=0. From this last observation it follows easily that the cyclicity of the unfoldingX , is finite and can be computed explicity in terms of the Bautin ideal.Dedicated to the memory of R. Mañé     

Numerical treatment of O.D.Es.: The theory ofA-methods

Summary Almost all commonly used methods for O.D.Es. and their most miscellaneous compositions areA-methods, i.e. they can be reduced toz _o=;z _j =Az _j–1 +h(x _j–1 ,z _j–1 ,z _j ;h),z _j ^s ,A(s,s),j=1(1)m. This paper presents a general theory forA-methods and discusses its practical consequences. An analysis of local discretization error (l.d.e.) accumulation results in a general order criterium and reveals which part of the l.d.e. effectively influences the global error. This facilitates the comparison of methods and generalizes considerably the concept of error constants. It is shown, as a consequence, that the global error cannot be safely controlled by the size of the l.d.e. and that the conventional error control may fail in important cases. Furthermore, Butcher's effective order methods, the concept of Nordsieck forms, and Gear's interpretation of lineark-step schemes as relaxation methods are generalized. The stability of step changing is shortly discussed.     

On a global descent method for polynomials

Summary Given a complex polynomialp we determine a functionf _p : such that |p(f _p (z))||p(z)|,z withk<1. This result is used to introduce a global root-finding algorithm for polynomials.     

Some fractal sets determined by stable processes

Summary LetY _i be independent stable subordinators in (, ,P) with indices 0< _i <1 andR _i are the ranges ofY _i ,i=1, 2. We are able to find the exact Hausdorff measure and packing measure results for the product setsR ₁×R ₂, and whenever ₁ + ₂ 1/2, we deduce results for the vector sumR ₁R ₂={x+y:xR ₁,yR ₂}.     

Line search by curve fitting in minimization algorithms

Summary Consider an unconstrained minimization of an uniformly convex functionf(z). Let be an algorithm that, for solving it constructs a sequence {z _i} withz _i+1 =z _i + ⁽ⁱ⁾ h _i ,h _i R ⁿ , ⁽ⁱ⁾ R ⁼ and –h _i ^T f(z _i ) > 0. For any algorithm that converges linearly and that uses parabolic or cubic interpolations for the line search, upper bounds on the number of function evaluations needed to approximate the minimum off(z) within a given accuracy, are calculated. The obtained results allow to compare the line search procedure under investigation.     

Non polynomial splines and weakly singular two-point boundary value problems

In the present paper we shall consider an application of simple non-polynomial splines to a numerical solution of a weakly singular two-point boundary value problem:x ^– (x y)=f(x,y), (0<x1) subject toy(0)=0,y(1)=c ₁(1) ory(0)=c ₂,y(1)=c ₃(0<<1). Our collocation method gives a continuously differentiable approximation and isO(h ²)-convergent.     

Some observations on the distribution of values of continued fractions

Summary There have been many studies of the values taken on by continued fractionsK(a _n /1) when its elements are all in a prescribed setE. The set of all values taken on is the limit regionV(E). It has been conjectured that the values inV(E), are taken on with varying probabilities even when the elementsa _n are uniformly distributed overE. In this article, we present the first concrete evidence that this is indeed so. We consider two types of element regions: (A)E is an interval on the real axis. Our best results are for intervals [–(1–), (1–)], 0 <1/2. (B)E is a disk in the complex plane defined byE={z:|z|(1–)}., 0<1/2.     

Some functional inequalities and their Baire category properties

Summary In the paper we consider, from a topological point of view, the set of all continuous functionsf:I I for which the unique continuous solution:I – [0, ) of(f(x)) (x, (x)) and(x, (x)) (f(x)) (x, (x)), respectively, is the zero function. We obtain also some corollaries on the qualitative theory of the functional equation(f(x)) = g(x, (x)). No assumption on the iterative behaviour off is imposed.     

Symmetrische Permutationsmengen

A permutation set (M, I) consisting of a setM and a set of permutations ofM, is calledsymmetric, if for any two permutations, the existence of anx M with (x) (x) and ^–1 (x) = ^–1 (x) implies ^–1 = ^–1 , andsharply 3-transitive, if for any two triples (x ₁,x ₂,x ₃), (y ₁,y ₂,y ₃) M ³ with|{x ₁,x ₂,x ₃ }| = |{y ₁,y ₂,y ₃ }| = 3 there is exactly one permutation with(x ₁) =y ₁,(x ₂) =y ₂,(x ₃) =y ₃. The following theorem will be proved.THEOREM.Let (M, ) be a sharply 3-transitive symmetric permutation set with |M|3, such that contains the identity. Then is a group and there is a commutative field K such that and the projective linear group PGL(2, K) are isomorphic.     

Kite-freeP- andQ-polynomial schemes

LetY = (X, {R _i } _oid) denote aP-polynomial association scheme. By a kite of lengthi (2 i d) inY, we mean a 4-tuplexyzu (x, y, z, u X) such that(x, y) R ₁,(x, z) R ₁,(y, z) R ₁,(u, y) R _i–1,(u, z) R _i–1,(u, x) R _i. Our main result in this paper is the following.