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

Generalized Padé approximations to the exponential function

The stability properties of the Padé rational approximations to the exponential function are of importance in determining the linear stability properties of several classes of Runge-Kutta methods. It is well known that the Padé approximationR _n,m (z) =N _n,m (z)/M _n,m (z), whereN _n,m (z) is of degreen andM _n,m (z) is of degreem, is A-stable if and only if 0 m – n 2, a result first conjectured by Ehle. In the study of the linear stability properties of the broader class of general linear methods one must generalize these rational approximations. In this paper we introduce a generalization of the Padé approximations to the exponential function and present a method of constructing these approximations for arbitrary order and degree. A generalization of the Ehle inequality is considered and, in the case of the quadratic Padé approximations, evidence is presented that suggests the inequality is both necessary and sufficient for A-stability. However, in the case of the cubic Padé approximations, the inequality is shown to be insufficient for A-stability. A generalization of the restricted Padé approximation, in which the denominator has a singlem-fold zero, is also introduced. A procedure for the construction of these restricted approximations is described, and results are presented on the A-stability of the restricted quadratic Padé approximations. Finally, to demonstrate the connection between a generalized Padé approximation and a general linear method, a specific general linear method is constructed with a stability region corresponding to a given quadratic Padé approximation.     

A new continuation method for complementarity problems with uniformP-functions

The complementarity problem with a nonlinear continuous mappingf from the nonnegative orthantR ₊ ⁿ ofR ⁿ intoR ⁿ can be written as the system of equationsF(x, y) = 0 and(x, y) R ₊ ²ⁿ , whereF denotes the mapping from the nonnegative orthantR ₊ ²ⁿ ofR ²ⁿ intoR ₊ ⁿ × Rⁿ defined byF(x, y) = (x ₁y₁,,x_ny_n, f₁(x) – y₁,, f_n(x) – y_n) for every(x, y) R ₊ ²ⁿ . Under the assumption thatf is a uniformP-function, this paper establishes that the mappingF is a homeomorphism ofR ₊ ²ⁿ ontoR ₊ ⁿ × Rⁿ. This result provides a theoretical basis for a new continuation method of tracing the solution curve of the one parameter family of systems of equationsF(x, y) = tF(x ⁰, y⁰) and(x, y) R ₊ ²ⁿ from an arbitrary initial point(x ⁰, y⁰) R ₊ ²ⁿ witht = 1 until the parametert attains 0. This approach is an extension of the one used in the polynomially bounded algorithm recently given by Kojima, Mizuno and Yoshise for solving linear complementarity problems with positive semi-definite matrices.     

Order-constrained uniform approximations to the exponential based on restricted rationals

LetR _n/m(z∶γ)=P _n(z∶γ)/(1?γz) ^m be a rational approximation to exp (z),z ∈C, of ordern for all real positiveγ. In this paper we show there exists exactly one value ofγ in each of min(n+1,m) interpolation intervals such that the uniform error overR ^? is at a local minimum.     

Some properties of rational approximations of degree (k, 1) in the hardy spaceH 2(D)

We prove that the well-known interpolation conditions for rational approximations with free poles are not sufficient for finding a rational function of the least deviation. For rational approximations of degree (k, 1), we establish that these interpolation conditions are equivalent to the assertion that the interpolation pointc is a stationary point of the functionk(c) defined as the squared deviation off from the subspace of rational functions with numerator of degree k and with a given pole 1/¯c. For any positive integersk ands, we construct a functiong H₂(D) such thatR _k ,1(g)=R _k +s,1(g) > 0. whereR _k ,1(g) is the least deviation ofg from the class of rational function of degree (k, 1).Translated fromMatematicheskie Zametki, Vol. 64, No. 2, pp. 251–259, August, 1998.The author is keenly grateful to N. S. Vyacheslavov, E. P. Dolzhenko, and V. G. Zinov for useful discussions.     

An implicit function theorem

Suppose thatF:DR ⁿ×R^mRⁿ, withF(x ⁰,y ⁰)=0. The classical implicit function theorem requires thatF is differentiable with respect tox and moreover that ₁ F(x ⁰,y ⁰) is nonsingular. We strengthen this theorem by removing the nonsingularity and differentiability requirements and by replacing them with a one-to-one condition onF as a function ofx.     

Laurent-Padé approximants to four kinds of Chebyshev polynomial expansions. Part I. Maehly type approximants

Laurent Padé-Chebyshev rational approximants,A _m (z,z ⁻¹)/B _n (z, z ⁻¹), whose Laurent series expansions match that of a given functionf(z,z ⁻¹) up to as high a degree inz, z ⁻¹ as possible, were introduced for first kind Chebyshev polynomials by Clenshaw and Lord [2] and, using Laurent series, by Gragg and Johnson [4]. Further real and complex extensions, based mainly on trigonometric expansions, were discussed by Chisholm and Common [1]. All of these methods require knowledge of Chebyshev coefficients off up to degreem+n. Earlier, Maehly [5] introduced Padé approximants of the same form, which matched expansions betweenf(z,z ⁻¹)B _n (z, z ⁻¹)). The derivation was relatively simple but required knowledge of Chebyshev coefficients off up to degreem+2n. In the present paper, Padé-Chebyshev approximants are developed not only to first, but also to second, third and fourth kind Chebyshev polynomial series, based throughout on Laurent series representations of the Maehly type. The procedures for developing the Padé-Chebyshev coefficients are similar to that for a traditional Padé approximant based on power series [8] but with essential modifications. By equating series coefficients and combining equations appropriately, a linear system of equations is successfully developed into two sub-systems, one for determining the denominator coefficients only and one for explicitly defining the numerator coefficients in terms of the denominator coefficients. In all cases, a type (m, n) Padé-Chebyshev approximant, of degreem in the numerator andn in the denominator, is matched to the Chebyshev series up to terms of degreem+n, based on knowledge of the Chebyshev coefficients up to degreem+2n. Numerical tests are carried out on all four Padé-Chebyshev approximants, and results are outstanding, with some formidable improvements being achieved over partial sums of Laurent-Chebyshev series on a variety of functions. In part II of this paper [7] Padé-Chebyshev approximants of Clenshaw-Lord type will be developed for the four kinds of Chebyshev series and compared with those of the Maehly type.     

The Padé-Rayleigh-Ritz method for solving large hermitian eigenproblems

We make use of the Padé approximants and the Krylov sequencex, Ax,,...,A ^m–1 x in the projection methods to compute a few Ritz values of a large hermitian matrixA of ordern. This process consists in approaching the poles ofR _x()=((I–A)^–1 x,x), the mean value of the resolvant ofA, by those of [m–1/m]_Rx(), where [m–1/m]_Rx() is the Padé approximant of orderm of the functionR _x(). This is equivalent to approaching some eigenvalues ofA by the roots of the polynomial of degreem of the denominator of [m–1/m]_Rx(). This projection method, called the Padé-Rayleigh-Ritz (PRR) method, provides a simple way to determine the minimum polynomial ofx in the Krylov subspace methods for the symmetrical case. The numerical stability of the PRR method can be ensured if the projection subspacem is sufficiently small. The mainly expensive portion of this method is its projection phase, which is composed of the matrix-vector multiplications and, consequently, is well suited for parallel computing. This is also true when the matrices are sparse, as recently demonstrated, especially on massively parallel machines. This paper points out a relationship between the PRR and Lanczos methods and presents a theoretical comparison between them with regard to stability and parallelism. We then try to justify the use of this method under some assumptions.     

Remark on a Problem of Rational Approximation

We show that for any nonincreasing number sequence {a _n} _{n= 0} converging to zero, there exists a continuous 2-periodic function g such that the sequence of its best uniform trigonometric rational approximations {R _n (g,C ₂)} _{n= 0} and the sequence {a _n} _{n= 0} have the same order of decay.     

Centralizers satisfying polynomial identities

The following results are proved: IfR is a simple ring with unit, and for someaεR witha ⁿ in the center ofR, anyn, such that the centralizer ofa inR satisfies a polynomial identity of degreem, thenR satisfies the standard identity of degreenm. WhenR is not simple,R will satisfy a power of the same standard identity, provided thata andn are invertible inR. These theorems are then applied to show that ifG is a finite solvable group of automorphisms of a ringR, and the fixed points ofG inR satisfy a polynomial identity, thenR satisfies a polynomial identity, providedR has characteristic 0 or characteristicp wherep✗|G|. This research was supported in part by NSF Grant No. GP 29119X.     

On the Problem of Describing Sequences of Best Trigonometric Rational Approximations

For a strictly decreasing sequence a_{n n=0} of nonnegative real numbers converging to zero, we construct a continuous 2-periodic function f such that R^T _n(f) = a_n, n=0,1,2,..., where R^T _n(f) are best approximations of the function f in uniform norm by trigonometric rational functions of degree at most n.     

An estimate for the region of regularity of solutions of certain nonlinear differential inequalities

In the diskx ²+y ²R ² of thex, y-plane we consider the differential inequalityz _xxz_yy–z _xy ² –(1+z _x ^/2 +z _y ^/2 )^k, where the constants >0 andk>1. In the case =1 andk=2 this inequality means that the surfacez(x, y) has Gaussian curvatureK1. Efimov has shown that in this case the radius of the disk has an upper bound. In the present article we establish an analogous upper bound for the radiusR of the disk in which the functionz(x, y) satisfies the differential inequality above.Translated from Ukrainskií Geometricheskií Sbornik, Issue 28, 1985, pp. 19–21.     

Sobolev spaces associated to a polyhedron and Fourier integral operations inR n

The theory of the Sobolev spacesH _m ^p (R ⁿ ) (mR,p polyhedron in R ²ⁿ )of [BG]is revisited here in the frame of new classes of pseudodifferential operators related to the same polyhedron p.These operators generalize to corresponding classes of Fourier integral operators, for which we present the main lines of a symbolic calculus and results of continuity on the H _m ^p (R ⁿ ) spaces.     

Lower-semicontinuity result for the two-scale convergence

Let (m, n) ∈ ℕ², Ω an open bounded domain in ℝ^m , Y = [0, 1]^m ; u^ε in (L²(Ω))ⁿ which is two-scale converges to some u in (L²(Ω × Y))ⁿ . Let φ: Ω × ℝ^m × ℝⁿ → ℝ such that: φ(x, ·, ·) is continuous a.e. x ∈ Ω φ(·, y, z) is measurable for all (y, z) in ℝ^m × ℝⁿ , φ(x, ·, z) is 1-periodic in y, φ(x, y, ·) is convex in z. Assume that there exist a constant C₁ > 0 and a function C₂ ∈ L²(Ω) such that

     

Integer points on hypersurfaces

Very general hypersurfaces in ⁴ contain r ^2+(4/9) integer points in any ball of radiusr>1. As a consequence, an irreducible algebraic hypersurface in ⁿ (wheren4) which is not a cylinder and is of degreed, contains c(d, n)r ^{n–1–(5/9)} integer points in a ball of radiusr. This improves on the known boundc(d, n)r ^n–(3/2).Meinem verehrten Lehrer Professor E. Hlawka zum siebzigsten Geburtstag gewidmetWritten with partial support from NSF-MCS-8211461.     

Bitableaux Bases for the Diagonally Invariant Polynomial Quotient Rings

LetR=Q[x₁, x₂, …, x_n,y₁, y₂, …, y_n,z₁, …, z_n,w₁, …, w_n], letR^S_n={P∈R:σP=P∀σ∈S_n} and letμandνbe hook shape partitions ofn. WithΔ_μ(X, Y) andΔ_ν(Z, W) being appropriately defined determinants, ∂_xibeing the partial derivative operator with respect tox_iandP(∂)=P(∂_x1, …, ∂_xn, ∂_y1, …, ∂_wn), define _{μ, ν}={P∈R^S_n:P(∂)Δ_μ(X, Y)Δ_ν(Z, W)=0}. A basis is constructed for the polynomial quotient ringR^S_n/_{μ, ν}that is indexed by pairs of standard tableaux. The Hilbert series ofR^S_n/_{μ, ν}is related to the Macdonaldq, t-Kostka coefficients.     

A fast algorithm for scalar Nevanlinna-Pick interpolation

Summary In this paper, we derive a fast algorithm for the scalar Nevanlinna-Pick interpolation. Givenn distinct pointsz _i in the unit disk |z|<1 andn complex numbersw _i satisfying the Pick condition for 1in, the new Nevanlinna-Pick interpolation algorithm requires onlyO(n) arithmetic operations to evaluate the interpolatory rational function at a particular value ofz, in contrast to the classical algorithm which requiresO(n ²) arithmetic operations to compute the so-called Fenyves array (which is inherent in the classical algorithm). The new algorithm bypasses the generation of the Fenyves array to speed up the computation, and also yields a parallel scheme requiring onlyO(logn) arithmetic operations on a concurrent-read, exclusive-write parallel random access machine withn processors. We must remark that the rational functionf(z) computed by the new algorithm is one degree higher than the function computed by the classical algorithm.Supported in part by the US Army Research Office Grant No. DAAL03-91-G-0106     

Solving minimax problems by interval methods

Interval methods are used to compute the minimax problem of a twice continuously differentiable functionf(y, z),y ^m ,z ⁿ ofm+n variables over anm+n-dimensional interval. The method provides bounds on both the minimax value of the function and the localizations of the minimax points. Numerical examples, arising in both mathematics and physics, show that the method works well.This paper has been written while the first author worked as a visiting professor at the Institut für Angewandte Mathematik of the University of Freiburg i.Br., West Germany. It has been sponsored by Stiftung Volkswagenwerk, number I/63 064. He wishes to thank Professor Dr. K. Nickel for helping him to make his stay possible.     

An implicit function theorem: Comment

In Ref. 1, Jittorntrum proposed an implicit function theorem for a continuous mappingF:R ⁿ ×R ^m R ⁿ, withF(x ⁰,y ⁰)=0, that requires neither differentiability ofF nor nonsingularity of _x F(x ⁰,y ⁰). In the proof, the local one-to-one condition forF(·,y):A R ⁿ R ⁿ for ally B is consciously or unconsciously treated as implying thatF(·,y) mapsA one-to-one ontoF(A, y) for ally B, and the proof is not perfect. A proof can be given directly, and the theorem is shown to be the strongest, in the sense that the condition is truly if and only if.