A simple method for smoothing functions and compressing Hermite data

Let =(a=x₀<x₁<<x_n=b) be a partition of an interval [a,b] of R, and let f be a piecewise function of class C^k on [a,b] except at knots x_i where it is only of class , k_ik. We study in this paper a novel method which smooth the function f at x_i, 0in. We first define a new basis of the space of polynomials of degree 2k+1, and we describe algorithms for smoothing the function f. Then, as an application, we give a recursive computation of classical Hermite spline interpolants, and we present a method which allows us to compress Hermite data. The most part of these results are illustrated by some numerical examples. AMS subject classification 41A05, 41A15, 65D05, 65D07, 65D10     

Some localized separation axioms and their implications

In a topological spaceX, a T₂-distinct pointx means that for anyyX xy, there exist disjoint open neighbourhoods ofx andy. Similarly, T₀-distinct points and T₁distinct points are defined. In a T_i-distinct point-setA, we assume that eachxA is a T _i -distinct point (i=0, 1, 2). In the present paper some implications of these notions which localize the T _i -separation axioms (i=0, 1, 2) requirement, are studied. Suitable variants of regularity and normality in terms of T₂-distinct points are shown hold in a paracompact space (without the assumption of any separation axioms). Later T₀-distinct points are used to give two characterizations of the R _D -axiom.¹ In the end, some simple results are presented including a condition under which an almost compact set is closed and a result regarding two continuous functions from a topological space into a Hausdorff space is sharpened. A result which relates a limit pointv to an -limit point is stated.     

Stochastic processes with Gaussian interaction of components

Summary LetU(x), x ^d-|0}, be a nonnegative even function such that _x 0U(x)1. In this paper, we consider an infinite system of stochastic process _t (x); x ^d with the following mechanism: at each sitex, after mean 1 exponential waiting time, _t(x) is replaced by a Gaussian random variable with mean _{yx t} (y) U(y-x) and variance 1. It is understood here that all the interactions are independent of one another. The behavior of this system will be investigated and some ergodic theorems will be derived. The results strongly depend whether _{x 0} U(x)<1 or =1.     

On one representation of analytic functions by harmonic functions

Let u(x) be a function analytic in some neighborhood D about the origin, $ \mathcal{D} Let u(x) be a function analytic in some neighborhood D about the origin, ⊂ ℝ ⁿ . We study the representation of this function in the form of a series u(x) = u ₀(x) + |x|² u ₁(x) + |x|⁴ u ₂(x) + …, where u _k (x) are functions harmonic in . This representation is a generalization of the well-known Almansi formula. Original Russian Text ? V. V. Karachik, 2007, published in Matematicheskie Trudy, 2007, Vol. 10, No. 2, pp. 142–162.     

Zu Fragen der Analysis im Zusammenhang mit der Gleichungx 1 2 +...+x n 2 —ax 1...x n =b

x ₁ ² +...+x _n ² —ax ₁...x _n =b. First we describe a combinatorial presentation of a group of automorphisms of this equation, ifn=3, then we getPGL (2, ) as such a group of automorphisms of this equation. This gives analytical applications becausePGL (2, ) acts discontinously on the set {(x ₁,x ₂,x ₃)0<x ₁,x ₂,x ₃ andx ₁ ² +x ₂ ² +x ₃ ² –x ₁ x ₂ x ₃=b0}³. Further we ask for fundamental solutions of this equation. Finally, letx ₁,x ₂,x ₃ withx ¹ x ₂ ² +x ₃ ² ––x ₁ x ₂ x ₃=0 Then there areA, BSL(2, ) with trA=x ₁, trB=x ₂ and trA B=x ₃, and the group (A, B) is a discrete free group of rank two. In analysis we are interested in the question whether there are evenA, BSL(2, ) with trA=x ₁, trB=x ₂ and trA B=x ₃. We give necessary and sufficient conditions for that and remark that this question is connected with the ternary quadratic formk1p ²+k2q ²–r ²,k ¹=x ₁ ² ,k ₂=16(x ₂ ² +x ₁ ² +x ₃ ² –x ₁ x ₂ x ₃–4), which has some invariant properties.     

Theq-gamma function forx<0

F. H. Jackson defined aq analogue of the gamma function which extends theq-factorial (n!) _q =1(1+q)(1+q+q ²)...(1+q+q ²+...+q ^n–1) to positivex. Askey studied this function and obtained analogues of most of the classical facts about the gamma function, for 0<q<1. He proved an analogue of the Bohr-Mollerup theorem, which states that a logarithmically convex function satisfyingf(1)=1 andf(x+1)=[(q ^x –1)/(q–1)]f(x) is in fact theq-gamma function He also studied the behavior of _q asq changes and showed that asq1^–, theq-gamma function becomes the ordinary gamma function forx>0.I proved many of these results forq>1. The current paper contains a study of the behavior of _q (x) forx<0 and allq>0. In addition to some basic properties of _q , we will study the behavior of the sequence {x _n (q)} of critical points asn orq changes.     

Stochastic algorithms with armijo stepsizes for minimization of functions

Stochastic algorithms for optimization problems, where function evaluations are done by Monte Carlo simulations, are presented. At each iteratex _i, they draw a predetermined numbern(i) of sample points from an underlying probability space; based on these sample points, they compute a feasible-descent direction, an Armijo stepsize, and the next iteratex _i+1. For an appropriate optimality function , corresponding to an optimality condition, it is shown that, ifn(i) , then (x _i) 0, whereJ is a set of integers whose upper density is zero. First, convergence is shown for a general algorithm prototype: then, a steepest-descent algorithm for unconstrained problems and a feasible-direction algorithm for problems with inequality constraints are developed. A numerical example is supplied.     

Smooth Transformation of the Generalized Minimax Problem

We consider the generalized minimax problem, that is, the problem of minimizing a function (x)=F(g ₁(x),...,g _m(x)), where F is a smooth function and each g _i is the maximum of a finite number of smooth functions. We prove that, under suitable assumptions, it is possible to construct a continuously differentiable exact barrier function, whose minimizers yield the minimizers of the function . In this way, the nonsmooth original problem can be solved by usual minimization techniques for unconstrained differentiable functions.     

Chebyshev Solution of the Nearly-Singular One-Dimensional Helmholtz Equation and Related Singular Perturbation Equations: Multiple Scale Series and the Boundary Layer Rule-of-Thumb

The one-dimensional Helmholtz equation, ² u _xx –u=f(x), arises in many applications, often as a component of three-dimensional fluids codes. Unfortunately, it is difficult to solve for 1 because the homogeneous solutions are exp(±x/), which have boundary layers of thickness O(1/). By analyzing the asymptotic Chebyshev coefficients of exponentials, we rederive the Orszag–Israeli rule [16] that Chebyshev polynomials are needed to obtain an accuracy of 1% or better for the homogeneous solutions. (Interestingly, this is identical with the boundary layer rule-of-thumb in [5], which was derived for singular functions like tanh([x–1]/).) Two strategies for small are described. The first is the method of multiple scales, which is very general, and applies to variable coefficient differential equations, too. The second, when f(x) is a polynomial, is to compute an exact particular integral of the Helmholtz equation as a polynomial of the same degree in the form of a Chebyshev series by solving triangular pentadiagonal systems. This can be combined with the analytic homogeneous solutions to synthesize the general solution. However, the multiple scales method is more efficient than the Chebyshev algorithm when is very, very tiny.     

A q-Analogue of Weber-Schafheitlin Integral of Bessel Functions

In an attempt to find a q-analogue of Weber and Schafheitlin's integral ₀ x ^– J (ax) J (bx) dx which is discontinuous on the diagonal a = b the integral ₀ x ^– J ⁽²⁾ (a(1 – q)x; q)J ⁽¹⁾ (b(1 – q)x; q) dx is evaluated where J ⁽¹⁾ (x; q) and J ⁽²⁾ (x; q) are two of Jackson's three q-Bessel functions. It is found that the question of discontinuity becomes irrelevant in this case. Evaluations of this integral are also made in some interesting special cases. A biorthogonality formula is found as well as a Neumann series expansion for x in terms of J ⁽²⁾ _+1+2n ((1 – q)x; q). Finally, a q-Lommel function is introduced.     

A note onn-groupoids linearly defined on fields

On the real fieldR and the Galois fields GF(p), define operations by [x₁ x₂ ···x_n]=₁x₁+₂x₂+ ··· +_nx_n, where ₁,₂, ...,_n are elements of the relevant fields. LetB be the class of alln-groupoids defined on Galois fields in this way. In this paper, we will study the variety generated byB and the variety generated by the algebra (R, [ ]), where ₁,...,_n are algebraically independent inR. We will study also varieties defined in a similar way with the operation [x₁, x₂,..., x_n]=(x₁+x₂+ ···+x_n).Presented by Jan Mycielski.The author thanks Professor T. Evans for his suggestions in developing this article.     

Modifications and extensions of the conjugate gradient-restoration algorithm for mathematical programming problems

In this paper, the problem of minimizing a functionf(x) subject to a constraint (x)=0 is considered, wheref is a scalar,x ann-vector, and aq-vector, withq <n. Several conjugate gradient-restoration algorithms are analyzed: these algorithms are composed of the alternate succession of conjugate gradient phases and restoration phases. In the conjugate gradient phase, one tries to improve the value of the function while avoiding excessive constraint violation. In the restoration phase, one tries to reduce the constraint error, while avoiding excessive change in the value of the function.Concerning the conjugate gradient phase, two classes of algorithms are considered: for algorithms of Class I, the multiplier is determined so that the error in the optimum condition is minimized for givenx; for algorithms of Class II, the multiplier is determined so that the constraint is satisfied to first order. Concerning the restoration phase, two topics are investigated: (a) restoration type, that is, complete restoration vs incomplete restoration and (b) restoration frequency, that is, frequent restoration vs infrequent restoration.Depending on the combination of type and frequency of restoration, four algorithms are generated within Class I and within Class II, respectively: Algorithm () is characterized by complete and frequent restoration; Algorithm () is characterized by incomplete and frequent restoration; Algorithm () is characterized by complete and infrequent restoration; and Algorithm () is characterized by incomplete and infrequent restoration.If the functionf(x) is quadratic and the constraint (x) is linear, all of the previous algorithms are identical, that is, they produce the same sequence of points and converge to the solution in the same number of iterations. This number of iterations is at mostN* =n –q if the starting pointx _s is such that (x _s)=0, and at mostN*=1+n –q if the starting pointx _s is such that (x _s) 0.In order to illustrate the theory, five numerical examples are developed. The first example refers to a quadratic function and a linear constraint. The remaining examples refer to a nonquadratic function and a nonlinear constraint. For the linear-quadratic example, all the algorithms behave identically, as predicted by the theory. For the nonlinear-nonquadratic examples, Algorithm (II-), which is characterized by incomplete and infrequent restoration, exhibits superior convergence characteristics.It is of interest to compare Algorithm (II-) with Algorithm (I-), which is the sequential conjugate gradient-restoration algorithm of Ref. 1 and is characterized by complete and frequent restoration. For the nonlinear-nonquadratic examples, Algorithm (II-) converges to the solution in a number of iterations which is about one-half to two-thirds that of Algorithm (I-).This research was supported by the Office of Scientific Research, Office of Aerospace Research, United States Air Force, Grant No. AF-AFOSR-828-67.     

On Transformations and Determinants of Wishart Variables on Symmetric Cones

Let x and y be independent Wishart random variables on a simple Jordan algebra V. If c is a given idempotent of V, write for the decomposition of x in where V(c,) equals the set of v such that cv=v. In this paper we compute E(det(ax+by)) and some generalizations of it (Theorems 5 and 6). We give the joint distribution of (x ₁, x ₁₂, y ₀) where and P is the quadratic representation in V. In statistics, if x is a real positive definite matrix divided into the blocks x ₁₁, x ₁₂, x ₂₁, x ₂₂, then y ₀ is equal to . We also compute the joint distribution of the eigenvalues of x (Theorem 9). These results have been known only when V is the algebra of Hermitian matrices with entries in the real or the complex field. To obtain our results, we need to prove several new results on determinants in Jordan algebras. They include in particular extensions of some classical parts of linear algebra like Leibnitz's determinant formula (Proposition 2) or Schur's complement (Eqs. (3.3) and (3.6)).     

A Complexity Analysis of a Smoothing Method Using CHKS-functions for Monotone Linear Complementarity Problems

We consider the standard linear complementarity problem (LCP): Find (x, y) R ²ⁿ such that y = M x + q, (x, y) 0 and x _i y _i = 0 (i = 1, 2, ... , n), where M is an n × n matrix and q is an n-dimensional vector. Recently several smoothing methods have been developed for solving monotone and/or P ₀ LCPs. The aim of this paper is to derive a complexity bound of smoothing methods using Chen-Harker-Kanzow-Smale functions in the case where the monotone LCP has a feasible interior point. After a smoothing method is provided, some properties of the CHKS-function are described. As a consequence, we show that the algorithm terminates in Newton iterations where is a number which depends on the problem and the initial point. We also discuss some relationships between the interior point methods and the smoothing methods.     

Implicit function theorems for generalized equations

We show that Lipschitz and differentiability properties of a solution to a parameterized generalized equation 0 f(x, y) + F(x), wheref is a function andF is a set-valued map acting in Banach spaces, are determined by the corresponding Lipschitz and differentiability properties of a solution toz g(x) + F(x), whereg strongly approximatesf in the sense of Robinson. In particular, the inverse map (f + F)^–1 has a local selection which is Lipschitz continuous nearx ₀ and Fréchet (Gateaux, Bouligand, directionally) differentiable atx ₀ if and only if the linearization inverse (f (x ₀) + f (x₀) (× – x₀) + F(×))^–1 has the same properties. As an application, we study directional differentiability of a solution to a variational inequality.This work was supported by National Science Foundation Grant Number DMS 9404431.     

A derivative free iterative method for finding multiple roots of nonlinear equations

For an equation f(x)=0 having a multiple root of multiplicity m>1 unknown, we propose a transformation which converts the multiple root to a simple root of H(x)=0. The transformed function H(x) of f(x) with a small >0 has appropriate properties in applying a derivative free iterative method to find the root. Moreover, there is no need to choose a proper initial approximation. We show that the proposed method is superior to the existing methods by several numerical examples.     

On graphs that can be oriented as diagrams of ordered sets

We study some equivalent and necessary conditions for a finite graph to be the covering graph of a (partially) ordered set. For each 1, M. Aigner and G. Prins have introduced a notion of a vertex colouring, here called -good colouring, such that a 1-good colouring is the usual concept and graphs that have a 2-good colouring are precisely covering graphs. We present some inequalities for the corresponding chromatic numbers , especially for x ₂. There exist graphs that satisfy these inequalities for =2 but are not covering graphs. We show also that x ₂ cannot be bounded by a function of x=x ₁. A construction of Neetil and Rödl is used to show that x ₂ is not bounded by a function of the girth.     

Superconvergence for galerkin methods for the two point boundary problem via local projections

The two point boundary problemy'-a(x)y–b(x)y=-f(x), o<x<1,y(0)=y(1)=0, is first solved approximately by the standard Galerkin method, (Y, ) + (aY+bY, )=(f, ), ₁ ⁰ (r, ), for a function Y ₁ ⁰ (r, ), the space ofC ¹-piecewise--degree-polynomials vanishing atx=0 andx=1 and having knots at {x ₀ ,x ₁ , ...,x _M }=. ThenY is projected locally into a polynomial of higher degree by means of one of several projections. It is then shown that higher-order convergence results locally, provided thaty is locally smooth and is quasi-uniform.This research was supported in part by the National Science Foundation.     

On the approximation of plane curves by parametric cubic splines

A plane curveC can be approximated by a parametric cubic spline as follows. Points (x _i ,y _i ) are chosen in order alongC and a monotonically increasing variable is assigned values _i at the points (x _i ,y _i ): _i = the cumulative chordal distance from (x ₁ ,y ₁ ). The points ( _i ,x _i ) and ( _i ,y _i ) are then fitted separately by cubic splinesx() andy(), to obtain : (x(),y()). This paper establishes estimates for the errors involved in approximatingC by . It is found that the error in position betweenC and decreases likeh ³, whereh is the maximum length of arc between consecutive knots onC. For first derivatives, the error behaves likeh ²; for second derivatives, likeh.     

Ein konvergentes Iterationsverfahren zur Bestimmung der Nullstellen eines Polynoms

Summary In order to determine the roots of a polynomialp, a sequence of numbers {x _k} is constructed such that the associated sequence {|p(x _k)|} decreases monotonically. To determine a new iteration pointx _k+1 such that |p(x _k+1)|<-|p(x _k)| ( is a positive real constant, <1, depending only on the degree ofp), we determine a circleK aroundx _k which contains no root ofp and compute the values ofp atN points which are distributed equally on the circumference ofK (N again depends only on the degree ofp); at least one of theN points is shown to satisfy the given condition. Computing the function values by means of Fourier synthesis according to Cooley-Tukey [2] and combining our iteration step with the normal step of the method of Nickel [1], we obtain a numerically safe and fast algorithm for determining the roots of arbitrary polynomials.