A further result on the oscillation of delay difference equations

In this paper, we are concerned with the delay difference equations of the form

(*)

y_n+1 − y_n + p_ny_n−k = 0, N = 0, 1, 2, …,

(*)where p_n ≥ 0 and k is a positive integer. We prove by using a new technique that

guarantees that all solutions of equation (*) oscillate, which improves many previous well-known results. In particular, our theorems also fit the case where Σⁿ⁻¹_i=n−kp_i ≤ k^k+1/(k + 1)^k+1. In addition, we present a nonoscillation sufficient condition for equation (*).     

Maximum flow and critical cutset as descriptors of multi-state systems with randomly capacitated components

Let G = (V, E, s, t) denote a directed network with node set V, arc set E = {1,…, n}, source node s and sink node t. Let Γ denote the set of all minimal s−t cutsets and b₁(τ), …, B_n(τ), the random arc capacities at time τ with known joint probability distribution function. Let Λ(τ) denote the maximum s−t flow at time τ and D(τ), the corresponding critical minimal s−t cutset. Let Ω denote a set of minimal s−t cutsets. This paper describes a comprehensive Monte Carlo sampling plan for efficiently estimating the probability that D(τ)εΩ-Γ and x<λ(τ)y at time τ and the probability that D(τ) Ω given that x < Λ(τ) y at time τ. The proposed method makes use of a readily obtainable upper bound on the probability that Λ(τ) > x to gain its computational advantage. Techniques are described for computing confidence intervals and credibility measures for assessing that specified accuracies have been achieved. The paper includes an algorithm for performing the Monte Carlo sampling experiment, an example to illustrate the technique and a listing of all steps needed for implementation.     

Generalized dilations and the stabilization of uncertain systems via measurement feedback

We study the problem of semiglobally stabilizing uncertain nonlinear system

Full-size image

, with (A,B) in Brunowski form. We prove that if p₁(z,u,t)u and p₂(z,u,t)u are of order greater than 1 and 0, respectively, with “generalized” dilation δ_l(z,u)=(l¹⁻ⁿz₁,…,l⁻¹z_n−1,z_n,lu) and uniformly with respect to t, where z_i is the ith component of z, then we can achieve semiglobal stabilization via arbitrarily bounded linear measurement feedback.     

Control of singular problem via differentiation of a Min-Max

For Ω a smooth domain in Rⁿ with boundary Λ = Λ₀Λ₁, we are concerned with the wave equation y″ − Δy = S in Q_T =]0, T[ × Ω with = ∂/∂t, at source term satisfying S, S′ ε L¹(0, T L² (Ω)). A Dirichlet condition is imposed on Λ₀ and we consider an absorbing condition ∂y/∂n + uy′ = 0 in [0, T] × gL₁ where u is the control.parameter. We introduce the cost function. and using the Min-Max formulation of J we by-pasas the sensitivity analysis of u → y and obtain the gradient of J with a usual adjoint problem. We first present an abstract frame for this kind of problems. using the differentiability results of a Min-Max [1,2], which we very shortly deduce here, we show that the well posedness of the adjoint equation implies differentiability of the cost function governed by a linear well posed problem.     

Nonlinear eigenvalue problems for quasilinear systems

The paper deals with the existence of positive solutions for the quasilinear system (Φ(u'))' + λh(t)f(u) = 0,0 < t < 1 with the boundary condition u(0) = u(1) = 0. The vector-valued function Φ is defined by Φ(u) = (q(t)(p(t)u₁), …, q(t)(p(t)u_n)), where u = (u₁, …, u_n), andcovers the two important cases (u) = u and (u) = up > 1, h(t) = diag[h₁(t), …, h_n(t)] and f(u) = (f¹(u), …, fⁿ (u)). Assume that fⁱ and h_i are nonnegative continuous. For u = (u₁, …, u_n), let

, f₀ = maxf¹₀, …, fⁿ₀ and f_∞ = maxf¹_∞, …, fⁿ_∞. We prove that the boundary value problem has a positive solution, for certain finite intervals of λ, if one of f₀ and f_∞ is large enough and the other one is small enough. Our methods employ fixed-point theorem in a cone.     

New explicit filters and smoothers for diffusions with nonlinear drift and measurements

The optimal least-squares filtering of a diffusion x(t) from its noisy measurements {y(τ); 0 τ t} is given by the conditional mean E[x(t)|y(τ); 0 τ t]. When x(t) satisfies the stochastic diffusion equation dx(t) = f(x(t)) dt + dw(t) and y(t) = ∫₀^tx(s) ds + b(t), where f(·) is a global solution of the Riccati equation /xf(x) + f(x)² = f(x)² = αx² + βx + γ, for some , and w(·), b(·) are independent Brownian motions, Benes gave an explicit formula for computing the conditional mean. This paper extends Benes results to measurements y(t) = ∫₀^tx(s) ds + ∫₀^t dx(s) + b(t) (and its multidimensional version) without imposing additional conditions on f(·). Analogous results are also derived for the optimal least-squares smoothed estimate E[x(s)|y(τ); 0 τ t], s < t. The methodology relies on Girsanov's measure transformations, gauge transformations, function space integrations, Lie algebras, and the Duncan-Mortensen-Zakai equation.     

The μ-basis of a planar rational curve—properties and computation

A moving line L(x,y;t)=0 is a family of lines with one parameter t in a plane. A moving line L(x,y;t)=0 is said to follow a rational curve P(t) if the point P(t₀) is on the line L(x,y;t₀)=0 for any parameter value t₀. A μ-basis of a rational curve P(t) is a pair of lowest degree moving lines that constitute a basis of the module formed by all the moving lines following P(t), which is the syzygy module of P(t). The study of moving lines, especially the μ-basis, has recently led to an efficient method, called the moving line method, for computing the implicit equation of a rational curve [3 and 6]. In this paper, we present properties and equivalent definitions of a μ-basis of a planar rational curve. Several of these properties and definitions are new, and they help to clarify an earlier definition of the μ-basis [3]. Furthermore, based on some of these newly established properties, an efficient algorithm is presented to compute a μ-basis of a planar rational curve. This algorithm applies vector elimination to the moving line module of P(t), and has O(n²) time complexity, where n is the degree of P(t). We show that the new algorithm is more efficient than the fastest previous algorithm [7].     

The query complexity of order-finding

We consider the problem where π is an unknown permutation on {0,1,…,2ⁿ−1}, y₀{0,1,…,2ⁿ−1}, and the goal is to determine the minimum r>0 such that π^r(y₀)=1. Information about π is available only via queries that yield π^x(y) from any x{0,1,…,2^m−1} and y{0,1,…,2ⁿ−1} (where m is polynomial in n). The main resource under consideration is the number of these queries. We show that the number of queries necessary to solve the problem in the classical probabilistic bounded-error model is exponential in n. This contrasts sharply with the quantum bounded-error model, where a constant number of queries suffices.     

A generalization of concavity for finite differences

The concept of concavity is generalized to discrete functions, u, satisfying the n^th-order difference inequality, (−1)^n−kΔⁿu(m) ≥ 0, M = 0, 1,..., N and the homogeneous boundary conditions, u(0) = … = u(k−1) = 0, u(N + k + 1) = … = u(N + n) = 0 for some k “1, …, n − 1”. A piecewise polynomial is constructed which bounds u below. The piecewise polynomial is employed to obtain a positive lower bound on u(m) for m = k, …, N + k, where the lower bound is proportional to the supremum of u. An analogous bound is obtained for a related Green's function.     

Asymptotic and oscillatory behavior of solutions of general nonlinear difference equations of second order

The asymptotic and oscillatory behavior of solutions of some general second-order nonlinear difference equations of the form

δ(a_nh(y_n+1)δy_n)+p_nδy_n+q_n+1f(y_σ(n+1))=0 nZ,

is studied. Oscillation criteria for their solutions, when “p_n” is of constant sign, are established. Results are also presented for the damped-forced equation

δ(a_nh(y_n+1)δy_n)+p_nδy_n+q_n+1f(y_σ(n+1))=e_n nZ.

Examples are inserted in the text for illustrative purposes.     

Oscillation criteria of certain nonlinear partial difference equations

This paper is concerned with the nonlinear partial difference equation with continuous variables

,where a, σ_i, τ_i are positive numbers, h_i(x, y, u) ε C(R⁺ × R⁺ × R, R), uh_i(x, y, u) > 0 for u ≠ 0, h_i is nondecreasing in u, i = 1, …, m. Some oscillation criteria of this equation are obtained.     

QFT template generation for time-delay plants based on zero-inclusion test

Plant template generation is the key step in applying quantitative feedback theory (QFT) to design robust control for uncertain systems. In this paper we propose a technique for generating plant templates for a class of linear systems with an uncertain time delay and affine parameter perturbations in coefficients. The main contribution lies in presenting a necessary and sufficient condition for the zero inclusion of the value set f(T,Q)={f(τ,q): τT[τ⁻,τ⁺], qQ∏_k=0^m−1[q_k⁻,q_k⁺]}, where f(τ,q)=g(q)+h(q)e^−jτω*, g(q) and h(q) are both complex-valued affine functions of the m-dimensional real vector q, and ω^* is a fixed frequency. Based on this condition, an efficient algorithm which involves, in the worst case, evaluation of m algebraic inequalities and solution of m2^m−1 one-variable quadratic equations, is developed for testing the zero inclusion of the value set f(T,Q). This zero-inclusion test algorithm allows one to utilize a pivoting procedure to generate the outer boundary of a plant template with a prescribed accuracy or resolution. The proposed template generation technique has a linear computational complexity in resolution and is, therefore, more efficient than the parameter gridding and interval methods. A numerical example illustrating the proposed technique and its computational superiority over the interval method is included.     

Empirical Bayes estimation of the scale parameter in a Pareto distribution

Let f(xθ) = αθ^αx^−(α+1)I(x>θ) be the pdf of a Pareto distribution with known shape parameter α>0, and unknown scale parameter θ. Let {(X_i, θ_i)} be a sequence of independent random pairs, where X_i's are independent with pdf f(xα_i), and θ_i are iid according to an unknown distribution G in a class of distributions whose supports are included in an interval (0, m), where m is a positive finite number. Under some assumption on the class and squared error loss, at (n + 1)th stage we construct a sequence of empirical Bayes estimators of θ_n+1 based on the past n independent observations X₁,…, X_n and the present observation X_n+1. This empirical Bayes estimator is shown to be asymptotically optimal with rate of convergence O(n^−1/2). It is also exhibited that this convergence rate cannot be improved beyond n^−1/2 for the priors in class .     

Monoid-labeled transition systems

Given a -complete (semi)lattice , we consider -labeled transition systems as coalgebras of a functor ⁽⁻⁾, associating with a set X the set ^X of all -fuzzy subsets. We describe simulations and bisimulations of -coalgebras to show that L⁽⁻⁾ weakly preserves nonempty kernel pairs iff it weakly preserves nonempty pullbacks iff L is join infinitely distributive (JID).Exchanging for a commutative monoid , we consider the functor ⁽⁻⁾_ω which associates with a set X all finite multisets containing elements of X with multiplicities m M. The corresponding functor weakly preserves nonempty pullbacks along injectives iff 0 is the only invertible element of , and it preserves nonempty kernel pairs iff is refinable, in the sense that two sum representations of the same value, r₁ + … + r_m = c₁ + … + c_n, have a common refinement matrix (m_{(i, j)}) whose k-th row sums to r_k and whose l-th column sums to c_l for any 1≤ k ≤ m and 1 ≤ l ≤ n.     

On the Attainable Order of Collocation Methods for the Neutral Functional-Differential Equations with Proportional Delays

In this paper, we extend the recent results of H. Brunner in BIT (1997) for the DDE y′(t)= by(qt), y(0)=1 and the DVIE y(t)=1+∫₀ ^t by(qs)ds with proportional delay qt, 0<q≤1, to the neutral functional-differential equation (NFDE): and the delay Volterra integro-differential equation (DVIDE) : with proportional delays p _i t and q _i t, 0<p _i ,q _i ≤1 and complex numbers a,b _i and c _i . We analyze the attainable order of m-stage implicit (collocation-based) Runge-Kutta methods at the first mesh point t=h for the collocation solution v(t) of the NFDE and the `iterated collocation solution u _it (t)' of the DVIDE to the solution y(t), and investigate the existence of the collocation polynomials M _m (t) of v(th) or M^ _m (t) of u _it (th), t∈[0,1] such that the rational approximant v(h) or u _it (h) is the (m,m)-Padé approximant to y(h) and satisfies |v(h)−y(h)|=O(h ^{2 m +1}). If they exist, then we actually give the conditions of M _m (t) and M^ _m (t), respectively. Received September 17, 1998; revised September 30, 1999     

A note on two-sided stochastic control problems

We consider a class of two-sided stochastic control problems. For each continuous process π_t = π_t⁺ − π_t⁻ with bounded variation, the state process (x_t) is defined by x_t = B_t + f₀^t I(x_s - a)^d_πs+ − f₀^t I(x_s a)^dπ_s−, where a is a positive constant and (B_t) is a standard Brownian motion. We show the existence of an optimal policy so as to minimize the cost function J(π) = E [f₀^∞ e^−αsX_s² ds], with discount rate α > 0, associated with π.     

Improved upper bounds on the L(2,1) -labeling of the skew and converse skew product graphs

An L(2,1)-labeling of a graph G is a function f from the vertex set V(G) to the set of all nonnegative integers such that |f(x)−f(y)|≥2 if d(x,y)=1 and |f(x)−f(y)|≥1 if d(x,y)=2, where d(x,y) denotes the distance between x and y in G. The L(2,1)-labeling number λ(G) of G is the smallest number k such that G has an L(2,1)-labeling with max{f(v):vV(G)}=k. Griggs and Yeh conjecture that λ(G)≤Δ² for any simple graph with maximum degree Δ≥2. This paper considers the graph formed by the skew product and the converse skew product of two graphs with a new approach on the analysis of adjacency matrices of the graphs as in [W.C. Shiu, Z. Shao, K.K. Poon, D. Zhang, A new approach to the L(2,1)-labeling of some products of graphs, IEEE Trans. Circuits Syst. II: Express Briefs (to appear)] and improves the previous upper bounds significantly.     

On the joint nonlinear filtering-smoothing of diffusion processes

The smoothing of diffusions dx_t = f(x_t) dt + σ(x_t) dw_t, measured by a noisy sensor dy_t = h(x_t) dt + dv_t, where w_t and v_t are independent Wiener processes, is considered in this paper. By focussing our attention on the joint p.d.f. of (x_τ x_t), 0 ≤ τ < t, conditioned on the observation path {y_s, 0 ≤ s ≤ t}, the smoothing problem is represented as a solution of an appropriate joint filtering problem of the process, together with its random initial conditions. The filtering problem thus obtained possesses a solution represented by a Zakai-type forward equation. This solution of the smoothing problem differs from the common approach where, by concentrating on the conditional p.d.f. of x_τ alone, a set of ‘forward and reverse’ equations needs to be solved.     

The asymptotic self-similar behavior for the quasilinear heat equation with nonlinear boundary condition

In this paper the quasilinear heat equation with the nonlinear boundary condition is studied. The blow-up rate and existence of a self-similar solution are obtained. It is proved that the rescaled function

v(y,t)=(T−t)^{1/(2p+α−2)}u((T−t)^{(p−1)/(2p+α−2)}y,t),