Existence of multiple positive solutions for functional differential equations

In this paper, the existence of at least three positive solutions for the boundary value problem (BVP) of second-order functional differential equation with the form y″(t) + f(t, y^t) = 0, for t ε [0,1], y(t) -βy′(t) =η(t), for t ε [−τ,0], −γy(t) + Δy′(t) = ζ(t), for t ε [1, 1 + a], is studied. Moreover, we investigate the existence of at least three partially symmetric positive solutions for the above BVP with Δ = βγ.     

Nonnegative solutions of singular boundary value problems with sign changing nonlinearities

The paper presents sufficient conditions for the existence of positive solutions of the equation x″(t) + q(t)f(t,x(t),x′(t)) = 0 with the Dirichlet conditions x(0) = 0, x(1) = 0 and of the equation (p(t)x′(t))′ + p(t)q(t)f(t,x(t),p(t)x′(t)) = 0 with the boundary conditions lim_t→o⁺ p(t)x′(t) = 0, x(1) = 0. Our nonlinearity f is allowed to change sign and f may be singular at x = 0. The proofs are based on a combination of the regularity and sequential techniques and the method of lower and upper functions.     

Analytic-numerical solutions with a priori error bounds for time-dependent mixed partial differential problems

The aim of this paper is double. First, we point out that the hypothesis D(t₁)D(t₂) = D(t₂)D(t₁) imposed in [1] can be removed. Second, a constructive method for obtaining analytic-numerical solutions with a prefixed accuracy in a bounded domain Ω(t₀,t₁) = [0,p] × [t₀,t₁], for mixed problems of the type u_t(x,t) − D(t)u_xx(x,t) = 0, 0 < x < p, t> 0, subject to u(0,t) = u(p,t) = 0 and u(x,0) = F(x) is proposed. Here, u(x,t) and F(x) are r-component vectors, D(t) is a C^{r × r} valued analytic function and there exists a positive number δ such that every eigenvalue z of (1/2) (D(t) + D(t)^H) is bigger than δ. An illustrative example is included.     

On the error in Padé approximations for functions defined by Stieltjes integrals

Consdier I(z) = ∫^b_a w(t)f(t, z) dt, f(t, z) = (1 + t/z)⁻¹. It is known that generalized Gaussian quadrature of I(z) leads to approximations which occupy the (n, n + r − 1) positions of the Padé matrix table for I(z). Here r is a positive integer or zero. In a previous paper the author developed a series representation for the error in Gaussian quadrature. This approach is now used to study the error in the Padé approximations noted. Three important examples are treated. Two of the examples are generalized to the case where f(t, z) = (1 + t/z)^−v.     

Tree spanners on chordal graphs: complexity and algorithms

A tree t-spanner T in a graph G is a spanning tree of G such that the distance in T between every pair of vertices is at most t times their distance in G. The T t-S problem asks whether a graph admits a tree t-spanner, given t. We substantially strengthen the hardness result of Cai and Corneil (SIAM J. Discrete Math. 8 (1995) 359–387) by showing that, for any t4, T t-S is NP-complete even on chordal graphs of diameter at most t+1 (if t is even), respectively, at most t+2 (if t is odd). Then we point out that every chordal graph of diameter at most t−1 (respectively, t−2) admits a tree t-spanner whenever t2 is even (respectively, t3 is odd), and such a tree spanner can be constructed in linear time.

The complexity status of T 3-S still remains open for chordal graphs, even on the subclass of undirected path graphs that are strongly chordal as well. For other important subclasses of chordal graphs, such as very strongly chordal graphs (containing all interval graphs), 1-split graphs (containing all split graphs) and chordal graphs of diameter at most 2, we are able to decide T 3-S efficiently.     

Remote sensing of ocean color: Assessment of the water-leaving radiance bidirectional effects on the atmospheric diffuse transmittance for SeaWiFS and MODIS intercomparisons

The portion of the radiance exiting the ocean and transmitted to the top of the atmosphere (TOA) in a particular direction depends on the angular distribution of the exiting radiance, not just the radiance exiting in the direction of interest. The diffuse transmittance t relates the water component of the TOA radiance to that exiting the water in the same direction. As such t is a property of the ocean–atmosphere system and not just the atmosphere. Its computation requires not only the properties of the atmosphere but the angular distribution of the exiting radiance as well. The latter is not known until a determination of the water properties can be made (which is the point of measuring the radiance in the first place). Because of this, it has been customary to assume an angular distribution (uniform upward radiance beneath the water surface) in the computation of t, which is referred to as t. However, it is known that replacing t with t can result in an error of several percent in the retrieved water-leaving radiance. Since the error depends on sun-viewing direction, this error could be particularly important when water-leaving radiance from two or more sensors in different orbits are compared. Even given an estimate of the angular distribution of the water-leaving radiance, computation of t using full radiative transfer theory in an image processing environment is not practical. Thus, we developed a first-order correction to t for bidirectional effects in the water-leaving radiance that captures much of the variability of t with viewing direction. The correction computed across a SeaWiFS scan line shows that a t-induced error of as much as 5–6% could occur near the edges of the scan; however, limiting the scan to polar viewing angles (θ) < 60° reduces the error to ~ 1%. Direct application to SeaWIFS and MODIS (AQUA) suggests that the bidirectionally-induced error in the diffuse transmittance will result in an error less than about 1% in the comparison of their normalized water-leaving radiances, as long as θ is less than about 60°. We conclude that, given this constraint, the normalized water-leaving retrievals from these two sensors at a given location can be merged without regard for the bidirectionally-induced error in the diffuse transmittance, as the resulting uncertainty is well below that from other sources. It is important to note that this result is likely to apply to any other polar-orbiting sensor with equatorial crossing times (similar to SeaWiFS and MODIS) between 1030 and 1330 h (local time).     

New results on oscillation for delay differential equations with piecewise constant argument

We introduce a new technique to obtain some new oscillation criteria for the oscillating coefficients delay differential equation with piecewise constant argument of the form x′(t) + a(t)x(t) + b(t)x({t − k}) = 0, where a(t) and b(t) are right continuous functions on [−k, ∞), k is a positive integer, and [·] denotes the greatest integer function. Our results improve and generalize the known results in the literature. Some examples are also given to demonstrate the advantage of our results.     

Constructible functions in cellular automata and their applications to hierarchy results

We investigate time-constructible functions in one-dimensional cellular automata (CA). It is shown that (i) if a function t(n) is computable by an O(t(n)−n)-time Turing machine, then t(n) is time constructible by CA and (ii) if two functions are time constructible by CA, then the sum, product, and exponential functions of them are time constructible by CA. As an application, it is shown that if t₁(n) and t₂(n) are time constructible functions such that lim_n→∞ t₁(n)/t₂(n) = 0 and t₁(n)n, then there is a language which can be recognized by a CA in t₂(n) time but not by any CA in t₁(n) time.     

Analytic numerical solution of coupled semi-infinite diffusion problems

In this paper, we consider coupled semi-infinite diffusion problems of the form u_t(x, t)− A² u_xx(x,t) = 0, x> 0, t> 0, subject to u(0,t)=B and u(x,0)=0, where A is a matrix in , and u(x,t), and B are vectors in . Using the Fourier sine transform, an explicit exact solution of the problem is proposed. Given an admissible error and a domain D(x₀,t₀)={(x,t);0≤x≤x₀, t≥t₀ > 0, an analytic approximate solution is constructed so that the error with respect to the exact solution is uniformly upper bounded by in D(x₀, t₀).     

Blossoms are polar forms

Consider the functions H(t):=t² and h(u,v):=uv. The identity H(t)=h(t,t) shows that h is the restriction of h to the diagonal u=v in the uv-plane. Yet, in many ways, a bilinear function like h is simpler than a homogeneous quadratic function like H. More generally, if F(t) is some n-ic polynomial function, it is often helpful to study the polar form of F, which is the unique symmetric, multiaffine function ƒ(u_1,…u_n) satisfying the identity F(t)=f(t,…,t). The mathematical theory underlying splines is one area where polar forms can be particularly helpful, because two pieces F and G of an n-ic spline meet at a point r with C^k parametric continuity if and only if their polar forms ƒ and g agree on all sequences of n arguments that contain at least n-k copies of r.

The polar approach to the theory of splines emerged in rather different guises in three independent research efforts: Paul de Faget Casteljau called it ‘shapes through poles’; Carl de Boor called it ‘B-splines without divided differences’; and Lyle Ramshaw called it ‘blossoming’. This paper reviews the work of de Casteljau, de Boor, and Ramshaw in an attempt to clarify the basic principles that underly the polar approach. It also proposes a consistent system of nomenclature as a possible standard.     

A Product–Delay algorithm for graphic design

A Product–Delay algorithm is presented for creating graphic designs on a computer. In this algorithm two functions u(t) and v(t) are multiplied yielding a function x(t). Another function y(t) is formed by delaying or advancing x(t) by a fixed amount of time t. These functions are evaluated over a suitable time interval and the results are plotted in the x–y plane. For appropriate choices of the functions and parameters, the x–y displays exhibit interesting geometric patterns. In this paper the algorithm is illustrated with a pair of sine and square waves. It is shown that a wide variety of graphic designs can be created with these simple waveforms. By virtue of its simplicity this algorithm can be programmed easily and quickly using general purpose software such as Maple, Matlab or Mathematica. It can be executed on standard platforms such as IBM PC compatibles, Macintosh computers or workstations. Some results in polar coordinates are also given.     

t-Spanners for metric space searching

The problem of Proximity Searching in Metric Spaces consists in finding the elements of a set which are close to a given query under some similarity criterion. In this paper we present a new methodology to solve this problem, which uses a t-spanner G′(V, E) as the representation of the metric database. A t-spanner is a subgraph G′(V, E) of a graph G(V, A), such that E  A and G′ approximates the shortest path costs over G within a precision factor t.

Our key idea is to regard the t-spanner as an approximation to the complete graph of distances among the objects, and to use it as a compact device to simulate the large matrix of distances required by successful search algorithms such as AESA. The t-spanner properties imply that we can use shortest paths over G′ to estimate any distance with bounded-error factor t.

For this sake, several t-spanner construction, updating, and search algorithms are proposed and experimentally evaluated. We show that our technique is competitive against current approaches. For example, in a metric space of documents our search time is only 9% over AESA, yet we need just 4% of its space requirement. Similar results are obtained in other metric spaces.

Finally, we conjecture that the essential metric space property to obtain good t-spanner performance is the existence of clusters of elements, and enough empirical evidence is given to support this claim. This property holds in most real-world metric spaces, so we expect that t-spanners will display good behavior in most practical applications. Furthermore, we show that t-spanners have a great potential for improvements.     

p-Moment stability of functional differential equations with random impulses

By means of Liapunov's direct method coupled with Razumikhin technique some sufficient conditions for (uniform, uniform and globally asymptotic, uniformly globally asymptotic, and globally exponential) p-moment stability of the zero solution of functional differential equations with random impulses are presented, where the parameter λ(t) in (dV(t, x(t)))/dt is not required to be negative definite. Thus the obtained results are convenient to apply.     

On-line parallel heuristics, processor scheduling and robot searching under the competitive framework

In this paper we investigate parallel searches on m concurrent rays for a point target t located at some unknown distance along one of the rays. A group of p agents or robots moving at unit speed searches for t. The search succeeds when an agent reaches the point t. Given a strategy S the competitive ratio is the ratio of the time needed by the agents to find t using S and the time needed if the location of t had been known in advance. We provide a strategy with competitive ratio of 1+2(m/p−1)(m/(m−p))^m/p and prove that this is optimal. This problem has applications in multiple heuristic searches in AI as well as robot motion planning. The case p = 1 is known in the literature as the cow path problem.     

Bisector curves of planar rational curves

This paper presents a simple and robust method for computing the bisector of two planar rational curves. We represent the correspondence between the foot points on two planar rational curves C₁(t) and C₂(r) as an implicit curve (t,r)=0, where (t,r) is a bivariate polynomial B-spline function. Given two rational curves of degree m in the xy-plane, the curve (t,r)=0 has degree 4m−2, which is considerably lower than that of the corresponding bisector curve in the xy-plane.     

Quasi-steady friction in transient polytropic flow

An accurate method of integrating quasi-steady friction in transient polytropic flows is introduced and is justified both physically and analytically. When applied to subsonic flows, it is found to be especially informative at higher Mach numbers where existing methods of integration can lead to serious errors in mass conservation. The method is used herein to assess the accuracy of widely used finite difference representations of quasi-steady friction, attention focusing principally on solutions obtained using the method of characteristics.

The new method is exact in the special case of steady flows. Of the approximate methods considered, the popular approximation V_t¦V_{t − Δt}¦Δt is found to perform well. A modification introduced by Karney and McInnis (Journal of Hydology Engineering, ACSE, 1992, 118(7), 1014–1030 [1]) improves the correlation for downstream characteristic lines, but has the opposite effect for upstream characteristics. A simple cubic scheme, loosely related to a more complex one used successfully by Murray (Proceedings of the International Conference on Unsteady Flow and Fluid Transients, 29 September–1 October. Balkema, Amsterdam, 1992, pp. 143–157 [2]), illustrates difficulties in higher-order schemes.

The new method is not exact in transient flows, but it gives good accuracy in slowly varying flows and it is plausible in rapidly varying flows. Using it as a benchmark, the approximation V_t¦V_{t − Δt}¦Δt is again shown to perform well. All of the schemes considered are unreliable when the flow is about to become choked within the region of integration     

Periodic solutions of a class of nonlinear difference equations via critical point method

In this paper, we obtain some new sufficient conditions for the existence of nontrivial m-periodic solutions of the following nonlinear difference equation

by using the critical point method, where f: Z × R → R is continuous in the second variable, m ≥ 2 is a given positive integer, p_n+m = p_n for any n  Z and f(t + m, z) = f(t, z) for any (t, z)  Z × R, (−1)^δ = −1 and δ > 0.     

Input constrained funnel control with applications to chemical reactor models

Error feedback control (in the presence of input constraints) is considered for a class of exothermic chemical reactor models. The primary control objective is regulation of a setpoint temperature T^* with prescribed accuracy: given λ>0 (arbitrarily small), ensure that, for every admissible system and reference setpoint, the regulation error e=T−T^* is ultimately smaller than λ (that is, ||e(t)||<λ for all t sufficiently large). The second objective is guaranteed transient performance: the evolution of the regulation error should be contained in a prescribed performance funnel F around the setpoint temperature T^*. A simple error feedback control with input constraints of the form

Full-size image

, u^* an offset, is introduced which achieves the objective in the presence of disturbances corrupting the measurement. The gain k(t) is a function of the error e(t)=T(t)−T^* and its distance to the funnel boundary. The input constraints have to satisfy certain feasibility assumptions in terms of the model data and the operating point T^*.     

A fast algorithm for parametric curve plotting

In parametric curve plotting by means of line segments, a curve r = r(t), t[t₀, t_u] is given, and a set of ordered points r(t_i, iN, t_ie[t₀, t_u] is specified as the vertices of an inscribed polygon of the curve. There are several, analytical, numerical or intuitive ways to derive these vertices obtaining a smooth polygonal approximation. The methods, which can be found in the literature, either belong to some special curves or involve a considerable waste of computing time.

In this paper, we consider an algorithm that appears as a subroutine in the whole program. The subroutine allows the main program to space points as a function of a distance interval for any parametric curve. The design of the routine for performing this spacing is outlined and two examples are shown.     

Computer study of bubble motion in a rotating liquid

The motion of a small, shape-preserving gas bubble through a rotating, homogeneous, incompressible, viscous liquid is investigated numerically be means of the Runge-Kutta-Nyström method. The fluid (liquid-gas) system spins about a fixed horizontal axis with constant angular velocity. Computer solutions are compared with experimental observations, and numerical experiences concerning step widths and computer accuracy are described.