An optimal triangulation for second-order elliptic problems

Let Ω be a polygonal domain in $\text{R}{}^{\mathrm{n}}$, τ_h an associated triangulation and u_h the finite element solution of a well-posed second-order elliptic problem on (Ω, τ_h). Let M = {M_i}^{p + q}_{i = 1} be the set of nodes which defines the vertices of the triangulation τ_h: for each i,$\text{M}{}_{\mathrm{i}}\text{= {x}{}_{\mathrm{i}}{}^{\mathrm{l}}\text{¦1 ? l ?n}}$ in Rⁿ. The object of this paper is to provide a computational tool to approximate the best set of positions M? of the nodes and hence the best triangulation $\text{}\text{?}\text{gt}{}_{\mathrm{h}}$ which minimizes the solution error in the natural norm associated with the problem.The main result of this paper are theorems which provide explicit expressions for the partial derivatives of the associated energy functional with respect to the coordinates x_i^l, 1 ? l ? n, of each of the variable nodes M_i, i = 1,…, p.     

On n-Dimensional Sequences. I

Let R be a commutative ring and let n ≥ 1. We study Γ(s), the generating function and Ann(s), the ideal of characteristic polynomials of s, an n-dimensional sequence over R .We express f(X₁,…,X_n) · Γ(s)(X^-1₁,…,X^-1_n) as a partitioned sum. That is, we give (i) a 2ⁿ-fold "border" partition (ii) an explicit expression for the product as a 2ⁿ-fold sum; the support of each summand is contained in precisely one member of the partition. A key summand is βo(f, s), the "border polynomial" of f and s, which is divisible by X₁ … X_n.We say that s is eventually rectilinear if the elimination ideals Ann(s)∩R[X_i] contain an f_i (X_i) for 1 ≤ i ≤ n. In this case, we show that Ann(s) is the ideal quotient ($\text{∑}{}^{\mathrm{n}}{}_{\mathrm{i}}\text{=1(fi) : βo(f, s)/(X}{}_1\text{… X}{}_{\mathrm{n}}\text{)}$).When R and R[[X₁, X₂ ,…, X_n]] are factorial domains (e.g. R a principal ideal domain or F [X₁,…, X_n]), we compute the monic generator γ_i of Ann(s) ∩ R[X_i] from known f_i ϵ Ann(s) ∩ R[X_i] or from a finite number of 1-dimensional linear recurring sequences over R. Over a field F this gives an O($\text{∏}{}_{\mathrm{n}}{}^{\mathrm{i}}\text{=1 δγ}{}^3{}_{\mathrm{i}}$) algorithm to compute an F-basis for Ann(s).     

Averaging shifted histograms

A method which consists in shifting different histograms of the same spectrum and then taking their average is presented in order to smooth the data and to increase the localization accuracy and separation of the peaks. The statistical properties of this method are investigated. The average of two histograms with shifted bin limits is studied. It is shown that for histograms with random bin limits, distributed according to

$\text{F}{}_{\mathrm{i}}\text{(x)=}\text{∫}\text{?∞}\text{x}\text{?}{}_{\mathrm{i}}\text{(ξ, μ}{}_{\mathrm{i}}\text{, σ)}\text{d}\text{ξ}$

; where the standard deviation σ is very small compared to the difference of the means (μ_i+1 ? μ_i) for ll i the zero order approximation to the variance of this histogram is given by:

$\text{var}\text{∽}\text{(H)=}\text{∑}\text{i=0}\text{m}\text{(A}{}_{\mathrm{i+1}}\text{?a}{}_{\mathrm{i}}\text{)}{}^2\text{F}{}_{\mathrm{i+1}}\text{(x)(1?F}{}_{\mathrm{i+1}}\text{(x))}$

, where

$\text{a}{}_{\mathrm{i}}\text{=}\text{1}\text{x}{}_{\mathrm{i=1}}\text{?x}{}_{\mathrm{i}}\text{∫}\text{x}{}_{\mathrm{i}}\text{x}{}_{\mathrm{i+1}}\text{g(ξ)}\text{d}\text{ξ}$

and g is an unknown function fitted by the histogram. Formula (1) gives also the relation:

$\text{v}\text{a}\text{?}\text{r}\text{(}\text{(H}{}_1\text{+ H}{}_2\text{)}\text{2}\text{) =}\text{1}\text{4}\text{(}\text{v}\text{a}\text{?}\text{r}\text{(H}{}_1\text{(x)) +}\text{v}\text{a}\text{?}\text{r}\text{(H}{}_2\text{(x))}$

, when H₁ and H₂ have stochastically independent bin limits.When the histogram H is considered as a spline function S of order one it is shown that for the minimization criterion with respect to the coefficient of the spline:

$\text{M}{}_1\text{=}\text{min}\text{∫}\text{x}{}_1\text{x}{}_{\mathrm{m+1}}\text{(g(x) ? S}{}_1\text{(x))}{}^2\text{d}\text{x}$

, the following result holds: $\text{M}{}_{\mathrm{a}}\text{?}{}^1{}_2\text{(M}{}_1\text{+ M}{}_2\text{)}$, where $\text{S}{}_{\mathrm{a}}\text{(x) =}{}^1{}_2\text{(S}{}_1\text{(x) + S}{}_2\text{(x))}$. If the number of shifted histograms tends to infinity, then

$\text{S}{}_{\mathrm{\infty }}\text{(x) = [Γ(x + h) + Γ(x ? h) ? 2Γ(x)]/h}{}^2$

, where $\text{Γ(x) =}\text{∫}\text{?∞}\text{x}\text{∫}\text{?∞}\text{η}\text{g(ξ)}\text{d}\text{ξ}\text{d}\text{η}$, and h is a constant bin size. Then

$\text{M}{}_{\mathrm{\infty }}\text{≈}\text{h}{}^4\text{144}\text{∫}\text{x}{}_1\text{x}{}_{\mathrm{m+1}}\text{g″}{}^2\text{(x)}\text{D}\text{x}$

. Extensions to two-dimensional histograms and to higher order (empirical distributions) are presented.     

On some convergence results for FDM with irregular mesh

The proof of convergence of the finite difference method with arbitrary irregular meshes for some class of elliptic problems is presented. By the use of the truncation error technique and stability analysis it was showed that $\text{max}{}_{\mathrm{i}}\text{¦u}{}^{\mathrm{i}}\text{? u}{}_{\mathrm{h}}{}^{\mathrm{i}}\text{¦? Ch}$, i.e., the solution u_h converges linearly with the size of the star. Correctness of this theorem was also confirmed by numerical tests.     

Lower bounds for polynomials with algebraic coefficients

We give a method, based on algebraic geometry, to show lower bounds for the complexity of polynomials with algebraic coefficients. Typical examples are polynomials with coefficients which are roots of unity, such as

$\text{Σ}\text{j=1}\text{d}\text{e}{}^{\mathrm{<mtext>2\pi i</mtext><mtext>i</mtext>}}\text{X}{}^{\mathrm{i}}$

and

$\text{Σ}\text{j=i}\text{d}\text{e}{}^{\mathrm{<mtext>2\pi i</mtext><mtext>pi</mtext>}}\text{X}{}^{\mathrm{j}}$

where p_j is the jth prime number.We apply the method also to systems of linear equations.     

Normal forms for nonautonomous difference equations

We extend Henry Poincaré's normal form theory for autonomous difference equations χ_{k + 1} = f(χ_k) to nonautonomous difference equations χ_{k + 1} = f_k(χ_k). Poincaré's nonresonance condition $\text{α}{}_{\mathrm{j}}\text{-П}{}^{\mathrm{n}}{}_{\mathrm{i=1}}\text{=1α}{}^{\mathrm{qi}}{}_{\mathrm{i}}\text{≠0}$ for eigenvalues is generalized to the new nonresonance condition λ_j∪$\text{α}{}_{\mathrm{j}}\text{⊔П}{}^{\mathrm{n}}{}_{\mathrm{i=1}}\text{α}{}^{\mathrm{qi}}{}_{\mathrm{i}}\text{≠0}$ for spectral intervals.     

A distribution-free geometric upper bound for the probability of error of a minimum distance classifier

An upperbound to the probability of error per class in a multivariate pattern classification is derived. The bound, given by

$\text{P(E|class w}{}_{\mathrm{i}}\text{)≤}\text{N}\text{R}{}^2{}_{\mathrm{i}}$

is derived with minimal assumptions; specifically the mean vectors exist and are distinct and the covariance matrices exist and are non-singular. No other assumptions are made about the nature of the distributions of the classes. In equation (i) N is the number of features in the feature (vector) space and R_i is a measure of the “radial neighbourhood” of a class. An expression for R_i is developed. A comparison to the multivariate Gaussian hypothesis is presented.     

Crosscorrelation between linearly and nonlinearly distorted versions of a given signal

A given deterministic signal x(.) is distorted by passing it through a linear time-invariant filter and also by subjecting it to the action of an instantaneous nonlinearity. The resulting time crosscorrelation of the two distorted versions of the original signal is expressed by the function

$\text{R}{}_2\text{(s)?∫}{}_{\mathrm{?\infty }}{}^{\mathrm{\infty }}\text{?∫}{}_{\mathrm{?\infty }}{}^{\mathrm{\infty }}\text{g[x(t)]k(t?t′)x(t?s)dt dt′}$

, where x(.) is the given signal, k(.) is the nonnegative definite impulse response of the linear filter, and g(.) is the output-input characteristic of the zero-memory nonlinear device. The problem considered is that of determining conditions on the pair (x,g) such that R₂(s) ? R₂(0) for all s and any choice of nonnegative definite filter function k; the principal result is the formulation of a necessary and sufficient condition for R₂ to have a global maximum at the origin. In particular, the peak value occurs at the origin if and only if $\text{G}{}_{\mathrm{x}}{}^1\text{(ω)X(ω)}$ is real and nonnegative for all ω ? 0, where G_x(.) and X(.) are the Fourier transforms of g[x(.)] and x(.), respectively. An equivalent condition is that the correlation function

$\text{R}{}_2\text{(s)?∫}{}_{\mathrm{?\infty }}{}^{\mathrm{\infty }}\text{g[x(t)]x(t?s)dt}$

, previously studied by Richardson, be nonnegative definite.Several examples are given, and it is shown that, unlike the case for R₁(.), monotonicity of g(.) is not a sufficient condition for R₂(.) to have a global maximum at s = 0 independently of the choice of filter characteristic k. Certain extensions of these results are given for the case when x(.) is a Gaussian random input.     

On nonstochastic languages and homomorphic images of stochastic languages

Using a simple method we find some nonstochastic and stochastic languages related to the Dyck sets and to the languages $\text{{wcw¦w in {a, b}}{}^1\text{}}$ and $\text{{wcw}{}^{\mathrm{R}}\text{¦w in {a, b}}{}^1\text{}}$. Using the theory of uniformly distributed sequences, we present a sufficient condition for a one-letter language to be nonstochastic. Among the applications is the result that {a^p¦p is a prime} is nonstochastic. We also study the images of stochastic and rational stochastic languages under nonerasing and arbitrary homomorphisms as well as their relations to some well-known families. Finally, we introduce a large class of bounded languages and show that it is contained in /of_∩ (DUP) = the smallest intersection-closed AFL containing $\text{DUP}\text{= {a}{}^{\mathrm{n}}\text{b}{}^{\mathrm{n}}\text{¦n in N}}$, which is a subfamily of /oK(/oL_Q = the image of the family of rational stochastic languages under nonerasing homomorphisms.     

Mathematical foundations of Bézier's technique

Bezier's method is one of the most famous in computational geometry. In his book Numerical control Bezier gives excellent expositions of the mathematical foundations of this method. In this paper a new expression of the functions {f_n,i(u)}

$\text{f}{}_{\mathrm{n,i}}\text{(u)=1?}\text{Σ}\text{p=0}\text{i?1}\text{C}{}^{\mathrm{p}}{}_{\mathrm{n}}\text{u}{}^{\mathrm{p}}\text{(1?u)}{}^{\mathrm{n?p}}\text{(i=1,2,…,n)}$

is obtained.Using this formula, we have not only derived some properties of the functions {f_n,i(u)} (for instance $\text{f}{}_{\mathrm{n,n}}\text{(u) < f}{}_{\mathrm{n,n?1}}\text{(u)<...<f}{}_{\mathrm{n,1}}\text{(u)}\text{u}\text{? [0, 1]}$ and functions {f_n,i(u)} increase strictly at [0, 1] etc) but also simplified systematically all the mathematical discussions about Bezier's method.Finally we have proved the plotting theorem completely by matrix calculation.     

The relation between information theory and the differential geometry approach to statistics

?encov has shown that the Riemannian metric on the probability simplex ∑x_i = 1 defined by $\text{(ds)}{}^2\text{=}\text{∑(dx}{}_{\mathrm{i}}\text{)}{}^2\text{x}{}_{\mathrm{i}}$ has an invariance property under certain probabilistically natural mappings. No other Riemannian metric has the same property. The geometry associated with this metric is shown to lead almost automatically to measures of divergence between probability distributions which are associated with Kullback, Bhattacharyya, and Matusita. Certain vector fields are associated in a natural way with random variables. The integral curves of these vector fields yield the maximum entropy or minimum divergence estimates of probabilities. Some other consequences of this geometric view are also explored.     

Determination of a general economic location constant by monte carlo simulation

The problem of estimating the number of markets (or plants) to serve a set of sources in a given geographical area was considered. Markets were located so as to minimize total assembly cost which was considered a linear function of the weighted Euclidean distances between sources and markets. The following predictive function C_m was proposed for estimating the minimum total assembly cost for a given number of markets: $\text{C}{}_{\mathrm{m}}\text{= C}{}_1\text{?(}\text{m?1}\text{m}\text{)}{}^{\mathrm{k}}\text{(}\text{M}\text{M ? 1}\text{)}{}^{\mathrm{k}}\text{(C}{}_1\text{? C}{}_{\mathrm{M}}\text{),m = 1, 2, 3, …, M}$ where m = number of markets being located. M = maximum number of potential market sites. C₁ = minimum assembly cost when only one market is located. C_M = minimum assembly cost when all M markets are located. k = an undetermined constant which specifies the shape of the function.The validity of the C_m function and the range of the k constant were determined by computer Monte Carlo experimentation. The constant k, to a sufficient degree of approximation and ordinary use, was found independent of the number of sources and their distribution. A general economic location co     

Unbounded solutions of quasi-linear difference equations

We study positive increasing solutions of the nonlinear difference equation $\text{δ(a}{}_{\mathrm{n}}\text{φ}{}_{\mathrm{p}}\text{(δχ}{}_{\mathrm{n}}\text{))=b}{}_{\mathrm{n}}\text{f(χ}{}_{\mathrm{n+1}}\text{,}\text{φ}{}_{\mathrm{p}}\text{(u)=|u|}{}^{\mathrm{p-2}}\text{u,}\text{p>1}$ where {a_n}, {b_n} are positive real sequences for n ≥ 1, fR → R is continuous with uf(u) > 0 for u ≠ 0. A full characterization of limit behavior of all these solutions in terms of a_n, b_n is established. Examples, showing the essential role of used hypotheses, are also included. The tools used are the Schauder fixed-point theorem and a comparison method based on the reciprocity principle.     

The complexity of a multiprocessor task assignment problem without deadlines

We construct a sequence of monotone Boolean functions h_n :{0, 1}ⁿ→{0, 1}ⁿ, such that the monotone complexity of h_n is of order $\text{n}{}^2\text{log n}$. This result includes the largest known lower bound of this kind. Previously there were an $\text{Ω(n}{}^{\mathrm{<mtext>3</mtext><mtext>2</mtext>}}\text{)}$ bound for the Boolean matrix product, an $\text{Ω(n}{}^{\mathrm{<mtext>5</mtext><mtext>3</mtext>}}\text{)}$ bound for Boolean sums and an $\text{Ω(}\text{n}{}^2\text{log}{}^2\text{n}\text{)}$ bound by the author for the same functions h_n. This new lower bound is proved by new methods which probably will turn out to be useful also for other problems.     

Some polynomials that are hard to compute

Using the result of Heintz and Sieveking [1], we show that the polynomials $\text{Σ}{}_{\mathrm{1?j?d}}\text{b}{}^{\mathrm{<mtext>1</mtext><mtext>i</mtext>}}\text{X}{}^{\mathrm{j}}$ with b positive real different from one, and Σ_1?j?dj^rX^j with r rational not integer, are hard to compute.     

Asymptotic properties of minimax trees and game-searching procedures

The model most frequently used for evaluating the behavior of game-searching methods consists of a uniform tree of height h and a branching degree d, where the terminal positions are assigned random, independent and identically distributed values. This paper highlights some curious properties of such trees when h is very large and examines their implications on the complexity of various game-searching methods.If the terminal positions are assigned a WIN-LOSS status with the probabilities P₀ and 1 ? P₀, respectively, then the root node is almost a sure MIN or a sure LOSS, depending on whether P₀ is higher or lower than some fixed-point probability $\text{P1(d)}$. When the terminal positions are assigned continuous real values, the minimax value of the root node converges rapidly to a unique predetermined value $\text{v1}$, which is the $\text{(1 ? P1)-}\text{fractile}$ of the terminal distribution.Exploiting these properties we show that a game with WIN-LOSS terminals can be solved by examining, on the average, $\text{O}\text{[(d)}{}^{\mathrm{<mtext>h</mtext><mtext>2</mtext>}}\text{]}$ terminal positions if positions if $\text{P}{}_0\text{≠ P1}$ and $\text{O}\text{[(}\text{P1}\text{(1 ? P1)}\text{)}{}^{\mathrm{h}}\text{]}$ positions if $\text{P}{}_0\text{= P1}$, the former performance being optimal for all search algorithms. We further show that a game with continuous terminal values can be evaluated by examining an average of $\text{O}\text{[(}\text{P1}\text{(1 ? P1)}\text{)}{}^{\mathrm{h}}\text{]}$ positions, and that this is a lower bound for all directional algorithms. Games with discrete terminal values can, in almost all cases, be evaluated by examining an average of $\text{O}\text{[(d)}{}^{\mathrm{<mtext>h</mtext><mtext>2</mtext>}}\text{]}$ terminal positions. This performance is optimal and is also achieved by the ALPHA-BETA procedure.     

Three symmetric solutions of lidstone boundary value problems for difference and partial difference equations

We consider the boundary value problem $\text{δ}{}^{\mathrm{2m}}\text{y(k-m)=f(y(k),δ}{}^2\text{y(k-1),…,δ}{}^{\mathrm{2i}}\text{y(k-1),…,δ}{}^{\mathrm{2(m-1)}}\text{y(k-(m-1)))}\text{kϵ{a+1,…,b+1},}\text{δ}{}^{\mathrm{2i}}\text{y(a+1-m)=δ}{}^{\mathrm{2i}}\text{y(b+1+m-2i)=0,}\text{0≤i≤m-1,}$ where m ≥ 1 and (−1)^m f R^m → [0, ∞) is continuous. By using Amann and Leggett-Williams' fixed-point theorems, we develop growth conditions on f so that the boundary value problem has triple positive symmetric solutions. The results obtained are then applied in the investigation of radial solutions for certain partial difference equation subject to Lidstone type conditions.