Root Configurations for Hyperbolic Polynomials of Degree 3, 4, and 5

A real polynomial of one real variable is (strictly) hyperbolic if it has only real (and distinct) roots. There are 10 (resp. 116) possible non-degenerate configurations between the roots of a strictly hyperbolic polynomial of degree 4 (resp. 5) and of its derivatives (i.e., configurations without equalities between roots). The standard Rolle theorem allows 12 (resp. 286) such configurations. The result is based on the study of the hyperbolicity domain of the family P(x,a)=x ⁿ+a ₁ x ^n-1+...+a _n for n=4,5 (i.e., of the set of values of aⁿ for which the polynomial is hyperbolic) and its stratification defined by the discriminant sets Res(P ⁽ⁱ⁾,P ^(j))=0, 0 i < jn-1.     

A convexity-preservingC 2 parametric rational cubic interpolation

Summary AC ² parametric rational cubic interpolantr(t)=x(t) i+y(t) j,t[t ₁,t _n] to data S={(x_j, y_j)|j=1,...,n} is defined in terms of non-negative tension parameters _j ,j=1,...,n–1. LetP be the polygonal line defined by the directed line segments joining the points (x _j ,y _j ),t=1,...,n. Sufficient conditions are derived which ensure thatr(t) is a strictly convex function on strictly left/right winding polygonal line segmentsP. It is then proved that there always exist _j ,j=1,...,n–1 for whichr(t) preserves the local left/righ winding properties of any polygonal lineP. An example application is discussed.This research was supported in part by the natural Sciences and Engineering Research Council of Canada.     

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.     

A sixth order tridiagonal finite difference method for non-linear two-point boundary value problems

We present a new sixth order finite difference method for the second order differential equationy=f(x,y) subject to the boundary conditionsy(a)=A,y(b)=B. An interesting feature of our method is that each discretization of the differential equation at an interior grid point is based onfive evaluations off; the classical second order method is based on one and the well-known fourth order method of Noumerov is based on three evaluations off. In case of linear differential equations, our finite difference scheme leads to tridiagonal linear systems. We establish, under appropriate conditions, the sixth order convergence of the finite difference method. Numerical examples are considered to demonstrate computationally the sixth order of the method.     

A singular boundary value problem for odd-order differential equations

The odd-order differential equation (−1)ⁿx⁽²ⁿ⁺¹⁾=f(t,x,…,x⁽²ⁿ⁾) together with the Lidstone boundary conditions x^(2j)(0)=x^(2j)(T)=0, 0?j?n−1, and the next condition x⁽²ⁿ⁾(0)=0 is discussed. Here f satisfying the local Carathéodory conditions can have singularities at the value zero of all its phase variables. Existence result for the above problem is proved by the general existence principle for singular boundary value problems.     

A parallel selection algorithm

The problem of selecting thekth largest or smallest element of {x _i +y _j |x _i X andy _j Y i,j} whereX=(x ₁,x ₂, ..,x _n ) andY=(y ₁,y ₂, ...,y _n ) are two arrays ofn elements each, is considered. Certain improvements to an existing algorithm are proposed. An algorithm requiringO(logk·logn) units of time on a Shared Memory Model of a parallel computer havingO(n ^1+1/) processors is presented where is a pre-assigned constant lying between 1 and 2.     

Positive definite dot product kernels in learning theory

In the classical support vector machines, linear polynomials corresponding to the reproducing kernel K(x,y)=xy are used. In many models of learning theory, polynomial kernels K(x,y)=_l=0^Na_l(xy)^l generating polynomials of degree N, and dot product kernels K(x,y)=_l=0⁺a_l(xy)^l are involved. For corresponding learning algorithms, properties of these kernels need to be understood. In this paper, we consider their positive definiteness. A necessary and sufficient condition for the dot product kernel K to be positive definite is given. Generally, we present a characterization of a function f:RR such that the matrix [f(xⁱx^j)]_i,j=1^m is positive semi-definite for any x¹,x²,...,x^mRⁿ, n2. Supported by CERG Grant No. CityU 1144/01P and City University of Hong Kong Grant No. 7001342.AMS subject classification 42A82, 41A05     

High-accuracy Tridiagonal Finite Difference Approximations for Non-linear Two-point Boundary Value Problems

We discuss the construction of finite difference approximationsfor the non-linear two-point boundary value problem: y" = f(x,y), y(a)=A, y(b)=B. In the case of linear differential equations,the resulting finite difference schemes lead to tridiagonallinear systems. Approximations of orders higher than four involvederivatives of f. While several approximations of a particularorder are possible, we obtain the "simplest" of these approximationsleading to two high-accuracy methods of orders six and eight.These two methods are described and their convergence is established;numerical results are given to illustrate the order of accuracyachieved.     

Asymptotics of the fundamental system of solutions of a linear functional-differential equation with respect to a parameter

We study a functional-differential equation, whereF is a linear operator acting from the Hölder spaceH into the Sobolev space W _p ^s [0, 1] and is a complex parameter. For large absolute values of , we construct a one-to-one correspondence between the solutionsx(;t) andy(;t) of the equations andy ⁽ⁿ⁾+y ⁿ=0. We also establish conditions that should be imposed on the operatorF in order that specially selected fundamental systems of solutions of these equationsx _j (;t) andy _j (;t), j=1,...,n, satisfy the estimate with constantsc, >0 for the functional space=W _q ^l [0, 1] or.Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 47, No. 6, pp. 811–836, June, 1995.This work was financially supported by the International Science Foundation and the Foundation for Fundamental Research of the Ukrainian State Committee on Science and Technology.     

Triple Positive Solutions for Multipoint Conjugate Boundary Value Problems

For the nth order nonlinear differential equation y ⁽ⁿ⁾(t)=f(y(t)), t [0,1], satisfying the multipoint conjugate boundary conditions, y ^(j)(a_i) = 0,1 i k, 0 j n _i - 1, 0 =a ₁ < a ₂ < < a _k = 1, and _i=1 ^k n _i =n, where f: [0, ) is continuous, growth condtions are imposed on f which yield the existence of at least three solutions that belong to a cone.     

Positive periodic solutions of higher-dimensional functional difference equations with a parameter

By using Krasnoselskii's fixed point theorem and upper and lower solutions method, we find some sets of positive values λ determining that there exist positive T-periodic solutions to the higher-dimensional functional difference equations of the form where A(n)=diag[a₁(n),a₂(n),…,a_m(n)], h(n)=diag[h₁(n),h₂(n),…,h_m(n)], a_j,h_j :Z→R⁺, τ :Z→Z are T -periodic, j=1,2,…,m, T1, λ>0, x :Z→R^m, f :R₊^m→R₊^m, where R₊^m={(x₁,…,x_m)^TR^m, x_j0, j=1,2,…,m}, R⁺={xR, x>0}.     

On the algebraic structure of Abelian integrals for a kind of perturbed cubic Hamiltonian systems

The finite generators of Abelian integral are obtained, where Γh is a family of closed ovals defined by H(x,y)=x²+y²+ax⁴+bx²y²+cy⁴=h, h∈Σ, ac(4ac−b²)≠0, Σ=(0,h₁) is the open interval on which Γh is defined, f(x,y), g(x,y) are real polynomials in x and y with degree 2n+1 (n?2). And an upper bound of the number of zeros of Abelian integral I(h) is given by its algebraic structure for a special case a>0, b=0, c=1.     

Partitions of bi-partite numbers into at mostj parts

The number of partitions of a bi-partite number into at mostj parts is studied. We consider this function,p _j (x, y), on the linex+y=2n. Forj4, we show that this function is maximized whenx=y. Forj>4 we provide an explicit formula forn _j so that, for allnn _j ,x=y yields a maximum forp _j (x,y).     

High order stiffly stable composite multistep methods for numerical integration of stiff differential equations

Let \(\dot y\) =f(y,t) withy(t ₀)=y ₀ possess a solutiony(t) fort≧t ₀. Sett _n=t ₀+nh, n=1, 2,.... Lety ₀ denote the approximate solution ofy(t _n) defined by the composite multistep method with \(\dot y_n \) =f(y _n ,t _n ) andN=1, 2,.... It is conjectured that the method is stiffly stable with orderp=l for alll≧1 and shown to be so forl=1,..., 25. The method is intrinsically efficient in thatl future approximate solution values are established simultaneously in an iterative solution process with only one function evaluation per iteration for each of thel future time points. Step and order control are easily implemented, in that the approximate solution at only one past point appears in each component multistep formula of the method and in that the local truncation error for the first component multistep formula of the method is easily evaluated as $$T^{[l]} = \frac{h}{{t_{Nl} - t_{(N - 1)l - 1} }}\{ y_{Nl}^{PRED} - y_{Nl} \} ,$$ wherey _Nl ^PRED denotes the value att _Nl of the Lagrange interpolating polynomial passing through the pointsy _(N?1)l+j att _(N?1)l+j withj=?1, 0,...,l ? 1.     

On the Baire Classification of Positive Characteristic Exponents in the Perron Effect of Change of Their Values

In the complete Perron effect of change of values of characteristic exponents, where all nontrivial solutions y(t, y₀) of the perturbed two-dimensional differential system are infinitely extendible and have finite positive exponents (the exponents of the linear approximation system being negative), we prove that the Lyapunov exponent λ[y(·, y₀)] of these solutions is a function of the second Baire class of their initial vectors y₀ ∈ ?ⁿ {0}.     

Oscillation and Nonoscillation of Higher Order Self-Adjoint Differential Equations

Oscillation and nonoscillation criteria for the higher order self-adjoint differential equation (-1)ⁿ(t^alphay⁽ⁿ⁾)⁽ⁿ⁾+q(t)y = 0 (*) are established. In these criteria, equation (*) is viewed as a perturbation of the conditionally oscillatory equation (-1)ⁿ(t^alphay⁽ⁿ⁾)⁽ⁿ⁾ - µ,t^2n-y = 0, where _n, is the critical constant in conditional oscillation. Some open problems in the theory of conditionally oscillatory, even order, self-adjoint equations are also discussed.     

Prophet Regions for Independent [0, 1]-Valued Random Variables with Random Discounting

Abstract

Let X ₁, X ₂… and B ₁, B ₂… be mutually independent [0, 1]-valued random variables, with EB _j  = β > 0 for all j. Let Y _j  = B ₁ … sB _j?1 X _j for j ≥ 1. A complete comparison is made between the optimal stopping value V(Y ₁,…,Y _n ):=sup{EY _τ:τ is a stopping rule for Y ₁,…,Y _n } and E(max _1≤j≤n Y _j ). It is shown that the set of ordered pairs {(x, y):x = V(Y ₁,…,Y _n ), y = E(max _1≤j≤n Y _j ) for some sequence Y ₁,…,Y _n obtained as described} is precisely the set {(x, y):0 ≤ x ≤ 1, x ≤ y ≤ Ψ _{n, β}(x)}, where Ψ _{n, β}(x) = [(1 ? β)n + 2β]x ? β^?(n?2) x ² if x ≤ β ^n?1, and Ψ _{n, β}(x) = min _j≥1{(1 ? β)jx + β ^j } otherwise. Sharp difference and ratio prophet inequalities are derived from this result, and an analogous comparison for infinite sequences is obtained.     

Singular Nonlinear (n − 1,1) Conjugate Boundary Value Problems

Solutions are obtained for the boundary value problem, y ⁽ⁿ⁾ + f(x,y) = 0, y ⁽ⁱ⁾(0) = y(1) = 0, 0 i n – 2, where f(x,y) is singular at y = 0. An application is made of a fixed point theorem for operators that are decreasing with respect to a cone.     

Linear stability of stiff differential equation solvers

When a linear multistep method is used to solve a stiff differential equationy(x)=f(y(x)), producing an approximationy _n toy(x _n ), it is preferable to approximate the valuey(x _n ) in subsequent formulae by a value which exactly satisfies the corrector equation used, rather than by the valuef(y _n ). We prove that the resulting method is stable if the underlying corrector equation is absolutely stable, provided that the residuals obtained in solving successive nonlinear equations remain uniformly bounded.     

The asymptotic behavior of nonoscillatory solutions of nonlinear neutral type difference equations

In this paper, the authors study the asymptotic behavior of solutions of second-order neutral type difference equations of the form

Δ²(y_n+py_n−k)+f(n,y_n−ℓ)=0,n