Optimal accuracy approximation of functions and their derivatives

We consider the approximation of the function (x) and its derivative '(x) on [a, b] given that (x)C _2,N, i.e., belongs to the class of functions f(x) that satisfy the conditions f(x)L, f(x_i)=y_i, i=1,,N, where L and y_i are given real numbers and x_i are the nodes of an arbitrary grid, a=x₁<x₂<<X_N=b. A solution algorithm on the class of functions C_2,L,N is proposed which has optimal accuracy with a constant not exceeding 2. A bound on the approximation error of the function and its derivative is derived.Translated from Vychislitel'naya i Prikladnaya Matematika, No. 56, pp. 57–61, 1985     

A structure theorem for sum form functional equations

Summary It is proved that, iff _ij:]0, 1[ C (i = 1, ,k;j = 1, ,l) are measurable, satisfy the equation (1) (with some functionsg _it, h_jt:]0, 1[ C), then eachf _ij is in a linear space (called Euler space) spanned by the functionsx x ^j(logx) ^k (x ]0, 1[;j = 1, ,M;k = 0, ,m _j – 1), where ₁, , _M are distinct complex numbers andm ₁, , m_M natural numbers. The dimension of this linear space is bounded by a linear function ofN.     

The Braided product of Ockham algebras

In this paper we introduce an algebraic concept of the product of Ockham algebras called the Braided product. We show that ifL _i MS(i=1, 2, ,n) then the Braided product ofL _i(i=1, 2, ,n) exists if and only ifL ₁, ,L _n have isomorphic skeletons.     

Monomial gorenstein curves in A4 as set-theoretic complete intersections

It is shown that if the prime ideal ,, x₄], k an arbitrary field, has generic zero x_i=tⁿ _i, n_i positive integers with g.c.d. equal l, l i 4, then P(S) is a set-theoretic complete intersection if the numerical semigroup S=1,, n₄> is symmetric (i.e. if the extension of P(S) in k[[x₁,, x₄]] is a Gorenstein ideal).     

On a characterization of polynomials by divided differences

Summary We consider the functional equationf[x ₁,x ₂,, x _n ] =h(x ₁ + +x _n ) (x ₁,,x _n K, x _j x _k forj k), (D) wheref[x ₁,x ₂,,x _n ] denotes the (n – 1)-st divided difference off and prove Theorem. Let n be an integer, n 2, let K be a field, char(K) 2, with # K 8(n – 2) + 2. Let, furthermore, f, h: K K be functions. Then we have that f, h fulfil (D) if, and only if, there are constants a_j K, 0 j n (a := a_n, b := a_{n – 1}) such thatf = ax ⁿ +bx ^{n – 1} + +a ₀ and h = ax + b.     

Differential geometry of tensor product immersions II

In the first part of this series, we prove that the tensor product immersionf ₁ f _2k of2k isometric spherical immersions of a Riemannian manifoldM in Euclidean space is of-type with k and classify tensor product immersionsf ₁ f _2k which are ofk-type. In this article we investigate the tensor product immersionsf ₁ f _2k which are of (k+1)-type. Several classification theorems are obtained.     

Two-sided polynomial approximation of functions

Conditions are established when the collocation polynomials P_m(x) and P_M(x), m M, constructed respectively using the system of nodes x_j of multiplicities a_j 1, j = O,, n, and the system of nodes x_-r,,x_o,,x_n,,x_n+r1, r O, r₁ O, of multiplicities a_-r,,(a_o + y_o),,(a_n + y_n),,a_n+r1, a_j + y_j 1, are two sided-approximations of the function f on the intervals , x_j[, j = O,...,n + 1, and on unions of any number of these intervals. In this case, the polynomials P_m (x), P_M ^(l) (x) with l a_j are two-sided approximations of the function f⁽¹⁾ in the neighborhood of the node x_j and the integrals of the polynomials P_m(x), P_M(x) over D_j are two-sided approximations of the integral of the function f (over D_j). If the multiplicities a_j a_j + y_j of the nodes x_j are even, then this is also true for integrals over the set _j= _µ ^k D_j µ 1, k n. It is shown that noncollocation polynomials (Fourier polynomials, etc.) do not have these properties.Kiev University. Translated from Vychislitel'naya i Prikladnaya Matematika, No. 67, pp. 31–37, 1989.     

On bounds for the range of ordered variates II

Letx ₁, ,x _n be real numbers with ₁ ⁿ x _j =0, |x ₁ ||x ₂ ||x _n |, and ₁ ⁿ f(|x _i |)=A>0, wheref is a continuous, strictly increasing function on [0, ) withf(0)=0. Using a generalized Chebycheff inequality (or directly) it is easy to see that an upper bound for |x _m | isf ^–1 (A/(n–m+1)). If (n–m+1) is even, this bound is best possible, but not otherwise. Best upper bounds are obtained in case (n–m+1) is odd provided either (i)f is strictly convex on [0, ), or (ii)f is strictly concave on [0, ). Explicit best bounds are given as examples of (i) and (ii), namely the casesf(x)=x ^p forp>1 and 0<p<1 respectively.     

Decomposing symmetric exchanges in matroid bases

LetB,B be bases of a matroid, withX B, X B. SetsX,X are asymmetric exchange if(B – X) X and(B – X) X are bases. SetsX,X are astrong serial B-exchange if there is a bijectionf: X X, where for any ordering of the elements ofX, sayx _i ,i = 1, , m, bases are formed by the sets B₀ = B, B_i = (B_i–1 – x_i) f(x _i), fori = 1, , m. Any symmetric exchangeX,X can be decomposed by partitioning X = _i=1 ^m Y_i, X = _i=1 ^m Y_i, X, where (1) bases are formed by the setsB ₀ =B, B _i = (B _i–1 –Y _i ) Y _i ; (2) setsY _i ,Y _i are a strong serialB _i–1 -exchange; (3) properties analogous to (1) and (2) hold for baseB and setsY _i ,Y _i .     

A basis for the type 〈n〉 hyperidentities of the medial variety of semigroups

Summary The medical varietyMV of semigroups is the variety defined by the medial identityxyzw = xzyw. This variety is known to satisfy the medial hyperidentitiesF(G(x ₁₁ ,, x _1n ),, G(x _n1 ,, x _nn )) = G(F(x ₁₁ ,, x _n1 ),, F(x _1n ,, x _nn )), forn 1. Taylor has observed in [2] thatMV also satisfies some other hyperidentities, which are not consequences of the medial ones. In [4] the author introduced a countably infinite family of binary hyperidentities called transposition hyperidentities, which are natural generalizations of then = 2 medial hyperidentity. It was shown that this family is irredundant, and that no finite basis is possible for theMV hyperidentities with one binary operation symbol.In this paper, we generalize the concept of a transposition hyperidentity, and extend it to cover arbitrary arityn 2. We show that theMV hyperidentities with onen-ary operation symbol have no finite basis, but do have a countably infinite basis consisting of these transposition hyperidentities.Research supported by NSERC of Canada.     

A “from scratch” proof of a theorem of Rockafellar and Fulkerson

The theorem of this paper is of the same general class as Farkas' Lemma, Stiemke's Theorem, and the Kuhn—Fourier Theorem in the theory of linear inequalities. LetV be a vector subspace ofR ⁿ , and let intervalsI ¹,, I ⁿ of real numbers be prescribed. A necessary and sufficient condition is given for existence of a vector (x ¹ ,, x ⁿ ) inV such thatx ⁱ I ⁱ (i = 1, ,n); this condition involves the elementary vectors (nonzero vectors with minimal support) ofV . The proof of the theorem uses only elementary linear algebra.The author at present holds a Senior Scientist Award of the Alexander von Humboldt Stiftung.     

A functional inequality for real-analytic functions

Summary Forf ( C ⁿ() and 0 t x letJ _n (f, t, x) = (–1)ⁿ f(–x)f ⁽ⁿ⁾(t) +f(x)f ⁽ⁿ⁾ (–t). We prove that the only real-analytic functions satisfyingJ _n (f, t, x) 0 for alln = 0, 1, 2, are the exponential functionsf(x) = c e ^x,c, . Further we present a nontrivial class of real-analytic functions satisfying the inequalitiesJ ₀ (f, x, x) 0 and ₀ ^x (x – t)^{n – 1}J_n(f, t, x)dt 0 (n 1).     

Mathematical expectations of functions of sums of a random number of independent terms

Conditions are found which must be imposed on a function g(x) in order that M g(₁+₂+ + _v < if M g(_i) < and M g(v) < ,, ₁, ₂, , _n, ... being non-negative and independent, being integral, and {_i} being identically distributed. The result is applied to the theory of branching processes.Translated from Matematicheskie Zametki, Vol. 3, No. 4, pp. 387–394, April, 1968.     

Quadratic spline interpolation on uniform meshes

The interpolation problem at uniform mesh points of a quadratic splines(x _i)=f _i,i=0, 1,...,N ands(x ₀)=f₀ is considered. It is known that s–f=O(h ³) and s–f=O(h ²), whereh is the step size, and that these orders cannot be improved. Contrary to recently published results we prove that superconvergence cannot occur for any particular point independent off other than mesh points wheres=f by assumption. Best error bounds for some compound formulae approximatingf _i andf _i ⁽³⁾ are also derived.     

On some functional equations of Goląb-Schinzel type

Summary LetE be a real Hausdorff topological vector space. We consider the following binary law * on ·E:(, ) * (, ) = (, ^k + ) for(, ), (, ) × E where is a nonnegative real number,k andl are integers.In order to find all subgroupoids of ( ·E, *) which depend faithfully on a set of parameters, we have to solve the following functional equation:f(f(y) ^k x +f(x) ^l y) =f(x)f(y) (x, y E). (1)In this paper, all solutionsf: of (1) which are in the Baire class I and have the Darboux property are obtained. We obtain also all continuous solutionsf: E of (1). The subgroupoids of (^* ·E, *) which dapend faithfully and continuously on a set of parameters are then determined in different cases. We also deduce from this that the only subsemigroup ofL _n ¹ of the form {(F(x ₂,x ₃, ,x _n ),x ₂,x ₃, ,x _n ); (x ₂, ,x _n ) ^{n – 1} }, where the mappingF: ^{n – 1 *} has some regularity property, is {1} × ^{n – 1} .We may noitice that the Gob-Schinzel functional equation is a particular case of equation (1)(k = 0, l = 1, = 1). So we can say that (1) is of Gob—Schinzel type. More generally, whenE is a real algebra, we shall say that a functional equation is of Gob—Schinzel type if it is of the form:f(f(y) ^k x +f(x) ^l y) =F(x,y,f(x),f(y),f(xy)) wherek andl are integers andF is a given function in five variables. In this category of functional equations, we study here the equation:f(f(y) ^k x +f(x) ^l y) =f(xy) (x, y f: ). (4)This paper extends the results obtained by N. Brillouët and J. Dhombres in [3] and completes some results obtained by P. Urban in his Ph.D. thesis [11] (this work has not yet been published).Dedicated to the memory of Alexander M. Ostrowski on the occasion of the 100th anniversary of his birth     

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.     

Penalty function versus non-penalty function methods for constrained nonlinear programming problems

The relative merits of using sequential unconstrained methods for solving: minimizef(x) subject tog _i (x) 0, i = 1, , m, h _j (x) = 0, j = 1, , p versus methods which handle the constraints directly are explored. Nonlinearly constrained problems are emphasized. Both classes of methods are analyzed as to parameter selection requirements, convergence to first and second-order Kuhn-Tucker Points, rate of convergence, matrix conditioning problems and computations required.This paper was presented at the 7th Mathematical Programming Symposium 1970, The Hague, The Netherlands.     

A statistical estimate of the structure of multi-extremal problems

The solution of ak-extremal problem is defined as the set of pairs (x _i ^* , _i),i = 1, ,k, where x _t ^* isi ^th local minimum and _i is the volume of the set of attraction of this minimum. A Bayesian estimate ofk and ( ₁ , , _k ) is constructed.This paper has been written while the author was a CNR visiting professor at the Institute of Mathematics of the Milano University.     

On the singular graph and the Weyr characteristic of anM-matrix

LetA be anM-matrix in standard lower block triangular form, with diagonal blocksA _ii irreducible. LetS be the set of indices such that the diagonal blockA is singular. We define the singular graph ofA to be the setS with partial order defined by > if there exists a chain of non-zero blocksA _i, A_ij, , A_l.Let ₁ be the set of maximal elements ofS, and define thep-th level _p ,p = 2, 3, , inductively as the set of maximal elements ofS \( _{1 p-1}). Denote by _p the number of elements in _p . The Weyr characteristic (associated with 0) ofA is defined to be (A) = ( ₁, ₂,, _h ), where ₁ + + _p = dim KerA ^p ,p = 1, 2, , and _h > 0, _h+1 = 0.Using a special type of basis, called anS-basis, for the generalized eigenspaceE(A) of 0 ofA, we associate a matrixD withA. We show that(A) = ( ₁, , _h) if and only if certain submatricesD _p,p+1 ,p = 1, , h – 1, ofD have full column rank. This condition is also necessary and sufficient forE(A) to have a basis consisting of non-negative vectors, which is a Jordan basis for –A. We also consider a given finite partially ordered setS, and we find a necessary and sufficient condition that allM-matricesA with singular graphS have(A) = ( ₁, , _h). This condition is satisfied ifS is a rooted forest.The work of the second-named author was partly supported by the National Science Foundation, under grant MPS-08618 A02.     

Convex minimization under Lipschitz constraints

We consider the problem of minimizing a convex functionf(x) under Lipschitz constraintsf _i (x)0,i=1,...,m. By transforming a system of Lipschitz constraintsf _i (x)0,i=l,...,m, into a single constraints of the formh(x)-x²0, withh(·) being a closed convex function, we convert the problem into a convex program with an additional reverse convex constraint. Under a regularity assumption, we apply Tuy's method for convex programs with an additional reverse convex constraint to solve the converted problem. By this way, we construct an algorithm which reduces the problem to a sequence of subproblems of minimizing a concave, quadratic, separable function over a polytope. Finally, we show how the algorithm can be used for the decomposition of Lipschitz optimization problems involving relatively few nonconvex variables.