Monotonicity and boundedness in implicit Runge-Kutta methods

Summary This paper concerns the analysis of implicit Runge-Kutta methods for approximating the solutions to stiff initial value problems. The analysis includes the case of (nonlinear) systems of differential equations that are essentially more general than the classical test equationU=U (with a complex constant). The properties of monotonicity and boundedness of a method refer to specific moderate rates of growth of the approximations during the numerical calculations. This paper provides necessary conditions for these properties by using the important concept of algebraic stability (introduced by Burrage, Butcher and by Crouzeix). These properties will also be related to the concept of contractivity (B-stability) and to a weakened version of contractivity.     

Polynomial Filtrations and Lannes'' T Functor

This paper defines and studies the polynomial filtration [p_k ] of the shift functor : F , where F is the category of functors between F-vector spaces over a finite field F. The functors [p_k ] correspond to a system of functors (p_k T):U U, related to Lannes'T-functor on the category U of unstable modules over the Steenrod algebra. The main results concern the behaviour of the quotients ~ _s:=~/[p_s-1~ filtrations by ~_s-nilpotent functors are introduced and it is shown that the full subcategory of _s-nilpotent functors is thick.     

Joint torsion of Toeplitz operators with H∞ symbols

We give a new² index theorem for the basic example of Toeplitz operators on the circle. The joint torsion, a non zero complex valued analytic index, of a pair of Fredholm Toeplitz operatorsT andT withH symbols is computed by residues in the disk, and is determined by a monodromy integral which specifies the isomorphism class of a flat line bundle on the circle. When the symbols and are rational a product of joint torsions identifies the isomorphism class of the bundle inH ¹ (S ¹,C ^*), and the identification extends by rational approximation to the case of smooth symbols defined on the circle.Partially supported by National Science Foundation grants to both authors.     

Absolute monotonicity of rational functions occurring in the numerical solution of initial value problems

Summary This paper deals with rational functions ø(z) approximating the exponential function exp(z) related to numerical procedures for solving initial value problems. Motivated by positivity and contractivity requirements imposed on these numerical procedures we study the greatest nonnegative numberR, denoted byR(ø), such that ø is absolutely monotonic on (–R, 0]. An algorithm for the computation ofR(ø) is presented. Application of this algorithm yields the valueR(ø) for the well-known Padé approximations to exp(z). For some specific values ofm, n andp we determine the maximum ofR(ø) when ø varies over the class of all rational functions ø with degree of the numerator m, degree of the denominator n and ø(z)=exp(z)+(z ^p+1 ) (forz0).     

Orthogonal least squares fitting with linear manifolds

Summary The problem is considered of fitting a linear manifold of dimensions with 1sn–1 to a given set of points in ⁿ such that the sum of orthogonal squared distances attains a minimum.     

Méthodes multipas pour des équations paraboliques non linéaires

Summary We study the error due to the discretization in time of a nonlinear parabolic problem by a multistep method. Error estimates are obtained if the method is of the orderp (p>1) and stronglyA()-stable . The method is also applied to the Navier-Stokes equations in two dimensions.

     

On Dirichlet Processes Associated with Second Order Divergence Form Operators

Let be a d - dimensional Markov family corresponding to a uniformly elliptic second order divergence form operator. We show that for any quasi continuous in the Sobolev space the process (X) admits under P ^x a decomposition into a martingale additive functional (AF) M and a continuous AF A of zero quadratic variation for almost every starting point x if q=2, for quasi every x if q>2 and for every if is continuous, d=1 and or d>1 and q>d. Our decomposition enables us to show that in the case of symmetric operator the energy of A equals zero if q=2 and that the decomposition of (X) into the martingale AF M and the AF of zero energy A is strict if for some q>d. Moreover, our decomposition provides a probabilistic representation of A .     

Das asymptotische Verhalten der Peanokerne einiger interpolatorischer Quadraturverfahren

Summary Interpolatory quadrature formulae consist in replacing by wherep _f denotes the interpolating polynomial off with respect to a certain knot setX. The remainder may in many cases be written as wherem=n resp. (n+1) forn even and odd, respectively. We determine the asymptotic behaviour of the Peano kernelP _X (t) forn for the quadrature formulae of Filippi, Polya and Clenshaw-Curtis.

     

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.     

Zur Interpolation und Integration differenzierbarer periodischer Funktionen

Summary Letx ₀<x ₁<...<x _n–1<x ₀+2 be nodes having multiplicitiesv ₀,...,v _n–1, 1v _k r (0k<n). We approximate the evaluation functional ,x fixed, and the integral respectively by linear functionals of the form and determine optimal weights for the Favard classesW _r C ₂. In the even case of optimal interpolation these weights are unique except forr=1,x(x _k +x _k–1)/2 mod 2. Moreover we get periodic polynomial splinesw _{k, j} (0k<n, 0j<v _k ) of orderr such that are the optimal weights. Certain optimal quadrature formulas are shown to be of interpolatory type with respect to these splines. For the odd case of optimal interpolation we merely have obtained a partial solution.

Bojanov hat in [4, 5] ähnliche Resultate wie wir erzielt. Um Wiederholungen zu vermeiden, werden Resultate, deren Beweise man bereits in [4, 5] findet, nur zitiert     

Stability of a spline collocation method for strongly elliptic multidimensional singular integral equations

Summary We consider a spline collocation method for strongly elliptic zero order pseudodifferential equationsp _gw Au=f on a cube =(0, 1) ^m . Utilizing multilinear spline functions which are zero at the boundary we collocate at the meshpoints inside . For classical strongly elliptic translation invariant pseudodifferential operators, we verify the stability of the considered collocation method inL ²(). Afterwards, form2 and a right hand sidefH ⁸(),s>m/2, we prove an asymptotic convergence estimate.The author has been supported by a grant of Deutsche Forschungsgemeinschaft under grant number Ko 634/32-1     

Foliations with One-Sided Branching

We generalize the main results from the author's paper in Geom. Topol. 4 (2000), 457–515 and from Thurston's eprint math.GT/9712268 to taut foliations with one-sided branching. First constructed by Meigniez, these foliations occupy an intermediate position between -covered foliations and arbitrary taut foliations of 3-manifolds. We show that for a taut foliation with one-sided branching of an atoroidal 3-manifold M, one can construct a pair of genuine laminations ^± of M transverse to with solid torus complementary regions which bind every leaf of in a geodesic lamination. These laminations come from a universal circle, a refinement of the universal circles proposed by Thurston (unpublished), which maps monotonely and ₁(M)-equivariantly to each of the circles at infinity of the leaves of , and is minimal with respect to this property. This circle is intimately bound up with the extrinsic geometry of the leaves of . In particular, let denote the pulled-back foliation of the universal cover, and co-orient so that the leaf space branches in the negative direction. Then for any pair of leaves of with , the leaf is asymptotic to in a dense set of directions at infinity. This is a macroscopic version of an infinitesimal result from Thurston and gives much more drastic control over the topology and geometry of , than is achieved by him. The pair of laminations ^± can be used to produce a pseudo-Anosov flow transverse to which is regulating in the nonbranching direction. Rigidity results for ^± in the -covered case are extended to the case of one-sided branching. In particular, an -covered foliation can only be deformed to a foliation with one-sided branching along one of the two laminations canonically associated to the -coveredfoliation constructed in Geom. Topol. 4 (2000), 457–515, and these laminations become exactly the laminations ^± for the new branched foliation. Other corollaries include that the ambient manifold is -hyperbolic in the sense of Gromov, and that a self-homeomorphism of this manifold homotopic to the identity is isotopic to the identity.     

On the acceleration of limit periodic continued fractions

Summary A continued fraction (c.f.)K(a _n /1) is called limit periodic if . Fora anda(–,–1/4],a0, Thron-Waadeland (1980) examined a modification of a limit periodic c.f. for accelerating the convergence. This acceleration remains modest if thea _n converge only logarithmically. Thus it is proposed to apply an Euler summability method to the series equivalent to the c.f. Properties of the equivalent function are derived. These properties are used for choosing appropriate parameters for the summability method such that a considerable acceleration can be expected even if thea _n converge logarithmically.Dedicated to Prof. F.L. Bauer on the occasion of his 60th birthday     

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).     

Generalizations of the projection method with applications to SOR theory for hermitian positive semidefinite linear systems

Summary Ann×n complex matrixB is calledparacontracting if B₂1 and 0x[N(I-B)]Bx₂<x₂. We show that a productB=B _k B _k–1 ...B ₁ ofk paracontracting matrices is semiconvergent and give upper bounds on the subdominant eigenvalue ofB in terms of the subdominant singular values of theB _i 's and in terms of the angles between certain subspaces. Our results here extend earlier results due to Halperin and due to Smith, Solomon and Wagner. We also determine necessary and sufficient conditions forn numbers in the interval [0, 1] to form the spectrum of a product of two orthogonal projections and hence characterize the subdominant eigenvalue of such a product. In the final part of the paper we apply the upper bounds mentioned earlier to provide an estimate on the subdominant eigenvalue of the SOR iteration matrix associated with ann×n hermitian positive semidefinite matrixA none of whose diagonal entries vanish.The work of this author was supported in part by NSF Research Grant No. MCS-8400879     

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.     

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 Gauss quadrature formulas with equal weights

Summary It is well known that the Chebyshev weight function (1–x ²)^–1/2 is the only weight function (up to a linear transformation) for which then point Gauss quadrature formula has equal weights for alln. In this paper we describe all weight functions for which thenm point Gauss quadrature formula has equal weights for alln, wherem is fixed.     

On Compensated Compactness for Nonlinear Elliptic Problems in Perforated Domains

We consider a sequence of Dirichlet problems for a nonlinear divergent operator A: W _m ¹( _s ) [W _m ¹( _s )]^* in a sequence of perforated domains _s . Under a certain condition imposed on the local capacity of the set \ _s , we prove the following principle of compensated compactness: , where r _s(x) and z _s(x) are sequences weakly convergent in W _m ¹() and such that r _s(x) is an analog of a corrector for a homogenization problem and z _s(x) is an arbitrary sequence from whose weak limit is equal to zero.     

A-stable spline-collocation methods of multivalue type

In this paper the general classV of spline-collocation methods presented by Mülthei is investigated. The methods ofV approximate solutions of first order initial value problems. ClassV contains as subclass the methods of so-called multivalue type, and in particular contains the generalized singly-implicit methods treated by Butcher.Any multivalue type representativeU V yields a matrix valued function corresponding toU, which characterizes the region of absolute stability ofU. If a sequence (U()) of multivalue type representatives ofV tending to some singlevalue type representative V is considered, it can easily be seen by the structure of , that the sequence of the greatest eigenvalues of the (.,) tends to the stability function corresponding to . This fact allows one to construct one-parameter families of A-stable methods of multivalue type.