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.     

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

Resolvability and the upper dimension of graphs

For an ordered set W = {w₁, w₂,…, w_k} of vertices and a vertex v in a connected graph G, the (metric) representation of v with respect to W is the k-vector r(v | W) = (d(v, w₁), d(v, w₂),…, d(v, w_k)), where d(x, y) represents the distance between the vertices x and y. The set W is a resolving set for G if distinct vertices of G have distinct representations. A new sharp lower bound for the dimension of a graph G in terms of its maximum degree is presented.

A resolving set of minimum cardinality is a basis for G and the number of vertices in a basis is its (metric) dimension dim(G). A resolving set S of G is a minimal resolving set if no proper subset of S is a resolving set. The maximum cardinality of a minimal resolving set is the upper dimension dim⁺(G). The resolving number res(G) of a connected graph G is the minimum k such that every k-set W of vertices of G is also a resolving set of G. Then 1 ≤ dim(G) ≤ dim⁺(G) ≤ res(G) ≤ n − 1 for every nontrivial connected graph G of order n. It is shown that dim⁺(G) = res(G) = n − 1 if and only if G = K_n, while dim⁺(G) = res(G) = 2 if and only if G is a path of order at least 4 or an odd cycle.

The resolving numbers and upper dimensions of some well-known graphs are determined. It is shown that for every pair a, b of integers with 2 ≤ a ≤ b, there exists a connected graph G with dim(G) = dim⁺(G) = a and res(G) = b. Also, for every positive integer N, there exists a connected graph G with res(G) − dim⁺(G) ≥ N and dim⁺(G) − dim(G) ≥ N.     

Nonexistence of finite-dimensional filters for conditional statistics of the cubic sensor problem

Consider the cubic sensor dx = dw, dy = x³dt + dv where w, v are two independent Brownian motions. Given a function φ(x) of the state x let φ_t(x) denote the conditional expectation given the observations y_s, 0 s t. This paper consists of a rather detailed discussion and outline of proof of the theorem that for nonconstant φ there cannot exist a recursive finite-dimensional filter for φ driven by the observations.     

Integral averages and oscillation of second-order nonlinear differential equations

We present some criteria for the oscillation of the second-order nonlinear differential equation

Full-size image

where a ε C¹([t₀, ∞)) is a nonnegative function, q ε C ([t₀, ∞)) are allowed to change sign on [t₀, ∞), ψ, f ε C¹ , ψ(x) > 0, xf(x) > 0, f′(x) ≥ 0 for x ≠ 0. These criteria are obtained by using a general class of the parameter functions H(t,s) in the averaging techniques and represent extension, as well as improvement of known oscillation criteria of Philos and Purnaras for the generalized Emden-Fowler equation.     

On the sensitivity of camera calibration

The orientation position errors of an object's coordinate frame are determined when the offset of image centre and lens distortion are not included in the calibration process. The orientation and position errors are [(u₀)² + (v₀)²]^0.5/f and [(u²₀+v²₀)T²_z + (u²₀T²_z + v²₀T_y²)]^0.5/f, respectively, where f is the focal length, (u₀, v₀) is the offset of image centre and (T_x T_y T_z) is the position of an object. We also obtain the following conclusions: (a) The offset of image centre has little effect on the determinations of the position and orientation of a coordinate frame; (b) the lens distortion will not dramatically change the position and orientation of a coordinate frame; (c) the scale factor has a great effect on the position of a coordinate frame, and on the accuracy of measurement; (d) the offset of image centre is more sensitive than the lens distortion on the determinations of the position and orientation of a coordinate frame. Finally, some experimental results are given to demonstrate the theoretical analysis given in this paper.     

Biinfinite words with maximal recurrent unbordered factors

A finite non-empty word z is said to be a border of a finite non-empty word w if w=uz=zv for some non-empty words u and v. A finite non-empty word is said to be bordered if it admits a border, and it is said to be unbordered otherwise. In this paper, we give two characterizations of the biinfinite words of the form ^ωuvu^ω, where u and v are finite words, in terms of its unbordered factors.

The main result of the paper states that the words of the form ^ωuvu^ω are precisely the biinfinite words w=a₋₂a₋₁a₀a₁a₂ for which there exists a pair (l₀,r₀) of integers with l₀<r₀ such that, for every integers ll₀ and rr₀, the factor a_la_l0a_r0a_r is a bordered word.

The words of the form ^ωuvu^ω are also characterized as being those biinfinite words w that admit a left recurrent unbordered factor (i.e., an unbordered factor of w that has an infinite number of occurrences “to the left” in w) of maximal length that is also a right recurrent unbordered factor of maximal length. This last result is a biinfinite analogue of a result known for infinite words.     

Order-configuration functions: Mathematical characterizations and applications to digital signal and image processing

We call a function f in n variables an order-configuration function if for any x₁,…, x_n such that x_i1 … x_in we have f(x₁,…, x_n) = x_t, where t is determined by the n-tuple (i₁,…, i_n) corresponding to that ordering. Equivalently, it is a function built as a minimum of maxima, or a maximum of minima. Well-known examples are the minimum, the maximum, the median, and more generally rank functions, or the composition of rank functions. Such types of functions are often used in nonlinear processing of digital signals or images (for example in the median or separable median filter, min-max filters, rank filters, etc.). In this paper we study the mathematical properties of order-configuration functions and of a wider class of functions that we call order-subconfiguration functions. We give several characterization theorems for them. We show through various examples how our concepts can be used in the design of digital signal filters or image transformations based on order-configuration functions.     

Bivariate hermite subdivision

A subdivision scheme for constructing smooth surfaces interpolating scattered data in R³ is proposed. It is also possible to impose derivative constraints in these points. In the case of functional data, i.e., data are given in a properly triangulated set of points {(x_i, y_i)}_i=1^N from which none of the pairs (x_i,y_i) and (x_j,y_j) with i≠j coincide, it is proved that the resulting surface (function) is C¹. The method is based on the construction of a sequence of continuous splines of degree 3. Another subdivision method, based on constructing a sequence of splines of degree 5 which are once differentiable, yields a function which is C² if the data are not ‘too irregular’. Finally the approximation properties of the methods are investigated.     

Finding the minimum vertex distance between two disjoint convex polygons in linear time

Let V = v₁, v₂, …, v_m and W = w₁, w₂, …, w_n be two linearly separable convex polygons whose vertices are specified by their cartesian coordinates in order. An algorithm with O(m + n) worst-case time complexity is described for finding the minimum euclidean distance between a vertex v₁ in V and a vertex w_j in W. It is also shown that the algorithm is optimal.     

Blended Hermite interpolants

In (Röschel, l997) B-spline technique was used for blending of Lagrange interpolants. In this paper we generalize this idea replacing Lagrange by Hermite interpolants. The generated subspline b(t) interpolates the Hermite input data consisting of parameter values t_i and corresponding derivatives a_i,j, j=0,…,_i−1, and is called blended Hermite interpolant (BHI). It has local control, is connected in affinely invariant way with the input and consists of integral (polynomial) segments of degree 2·k−1, where k−1max{_i}−1 denotes the degree of the B-spline basis functions used for the blending. This method automatically generates one of the possible interpolating subsplines of class C^k−1 with the advantage that no additional input data is necessary.     

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.     

C- and C-continuous spline-interpolation of a regular triangular net of points

The investigations focus on the construction of a C^k-continuous (k=0,1,2) interpolating spline-surface for a given data set consisting of points P_ijk arranged in a regular triangular net and corresponding barycentric parameter triples (u_i,v_j,w_k). We try to generalize an algorithm by A.W. Overhauser who solved the analogous problem for the case of a univariate data set. As a straightforward generalization does not work out we adapt the Overhauser-construction. We use some blending of basic surfaces with uniquely determined basic functions. This yields a spline-surface with a polynomial parametric representation which display C¹- or C²-continuity along the common curve of two adjacent sub-patches. Local control of the emerging spline surface is provided which means moving one data point P changes only some of the sub-patches around P and does not affect regions lying far away.     

A finite element analysis of an axisymmetrically loaded orthotropic shell of revolution

The objective of this study was to develop a finite element matrix method of analysis for symmetrically loaded orthotropic shells of revolution using closed form elasticity solutions for the element. A computer program for structural analysis was developed based on this method.

The program was used to analyze orthotropic cylindrical shells with edge loads, orthotropic spherical shells with edge loads, and pressurized ellipsoidal shells.

For the ellipsoidal shells, the ratio of the major to minor axis (a/b) varied from 0.2 to 1.8. The orthotropic materials used had ratios of Young's modulus in the meridional direction to Young's modulus in a direction tangent to a parallel circle (E₁/E₂) that ranged from 0.2 to 1.8.

For the structures and orthotropic materials studied, it was found that the edge effect, as signified by the meridional moment, was affected by the Young's moduli ratio E₁/E₂, the radius of curvature R₂ in the plane containing a normal to the shell surface and a tangent to a parallel circle, and Poisson's ratio v₂, the latter being more prominent for large E₁/E₂ values. The range of the E₁/E₂ ratio caused the meridional edge moment to double, increasing as the E₁/E₂ ratios increased from 0.2 to 1.8, for pressurized ellipsoidal shells. The meridional edge moment more than doubled as the ellipsoidal axes ratio, a/b, ranged from 0.2 to 1.8.     

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.     

Efficient enumeration of all minimal separators in a graph

This paper presents an efficient algorithm for enumerating all minimal a-b separators separating given non-adjacent vertices a and b in an undirected connected simple graph G = (V, E), Our algorithm requires O(n³R_ab) time, which improves the known result of O(n⁴R_ab) time for solving this problem, where ¦V¦= n and R_ab is the number of minimal a-b separators. The algorithm can be generalized for enumerating all minimal A-B separators that separate non-adjacent vertex sets A, B < V, and it requires O(n²(n − n_A − n_b)R_AB) time in this case, where n_a = ¦A¦, n_B = ¦B¦ and r_AB is the number of all minimal A−B separators. Using the algorithm above as a routine, an efficient algorithm for enumerating all minimal separators of G separating G into at least two connected components is constructed. The algorithm runs in time O(n³R⁺_Σ + n⁴R_Σ), which improves the known result of O(n⁶R_Σ) time, where R_σ is the number of all minimal separators of G and R_ΣR⁺_Σ = ∑_1i, v_j) ER_vivj n − 1)/2 − m)R_Σ. Efficient parallelization of these algorithms is also discussed. It is shown that the first algorithm requires at most O((n/log n)R_ab) time and the second one runs in time O((n/log n)R⁺_Σ+n log nR_Σ) on a CREW PRAM with O(n³) processors.     

An element for static, vibration and buckling analysis of thick laminated plates

A conforming finite element formulation of the equations governing composite multilayered plates using Reddy's higher-order theory is presented. The element has eight degrees of freedom, u₀, v₀, w, ∂w/∂x, ∂w/∂y, ∂²w/∂x∂y, γ_x, γ_y, per node. The transverse displacement of the present element is described by a modified bicubic displacement function while the in-plane displacements and shear-rotations are interpolated quadraticly. The element is evaluated for its accuracy in the analysis of static, vibration, and buckling of anisotropic rectangular plates with different lamination schemes and boundary conditions. The conforming finite element described here for the higher-order theory gives fairly accurate results for displacements, stresses, buckling loads, and natural frequencies.     

Algorithms of discretization of algebraic spatial curves on homogeneous cubical grids

In this paper new methods of discretization (integer approximation) of algebraic spatial curves in the form of intersecting surfaces P(x, y, z) = 0 and Q(x, y, z) = 0 are analyzed.

The use of homogeneous cubical grids G(h³) to discretize a curve is the essence of the method. Two new algorithms of discretization (on 6-connected grid G_6c(h³) and 26-connected grid G₂₆(h³)) are presented based on the method above. Implementation of the algorithms for algebraic spatial curves is suggested. The elaborated algorithms are adjusted for application in computer graphics and numerical control of machine tools.     

Infinite words and biprefix codes

Let A be an alphabet and ƒ be a right infinite word on A. If ƒ is not ultimately periodic then there exists an infinite set {v_ii0} of (finite) words on A such that ƒ=v₀v₁…v_i…, {v_ii1} is a biprefix code and v_i≠v_j for positive integers i≠j.     

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.