Matrix equations over rings

The main purpose of this work is to establish necessary conditions and sufficient conditions for the existence of a solution of matrix equations whose coefficient matrices have elements belonging to the ring $\text{R=}\text{C}\text{[z}{}_1\text{,z}{}_2\text{,…z}{}_{\mathrm{n}}\text{]}$ of polynomials in n variables with complex coefficients and the ring $\text{R=}\text{R}\text{[z}{}_1\text{,z}{}_2\text{,…z}{}_{\mathrm{n}}\text{]}{}^{\mathrm{n}}$ of rational functions a(z₁,z₂,…z_n)b(z₁,z₂,…,z_n)^?1 with real coefficients and b(z₁,z₂,…,z_n)≠0 for all (z₁,z₂,…,z_n) in Rⁿ. Results obtained are useful in multidimensional systems theory and elsewhere.     

Existence of multiple solutions for second-order discrete boundary value problems

We give conditions on ƒ involving pairs of discrete lower and discrete upper solutions which lead to the existence of at least three solutions of the discrete two-point boundary value problem $\text{y}{}_{\mathrm{<mtext>k</mtext><mtext>+1</mtext>}}\text{− 2y}{}_{\mathrm{k}}\text{+ y}{}_{\mathrm{<mtext>k</mtext><mtext>-1</mtext>}}\text{+ ƒ(k,y}{}_{\mathrm{k}}\text{,v}{}_{\mathrm{k}}\text{) = 0, for k = 1,…, n − 1, y}{}_0\text{= 0 = y}{}_{\mathrm{n}}$, where ƒ is continuous and v_k = y_k − y_k−1, for k = 1,…,n. In the special case $\text{ƒ(k,t,p) = ƒ(t) ≥ 0}$, we give growth conditions on ƒ and apply our general result to show the existence of three positive solutions. We give an example showing this latter result is sharp. Our results extend those of Avery and Peterson and are in the spirit of our results for the continuous analogue.     

Optimal minimal order N-State estimators for linear stochastic systems

This paper presents the general solution to the problem of designing minimal order estimators to optimally estimate the state vector x_k of a linear discrete-time stochastic system with time invariant dynamics. The estimators differ depending on the number N of stages over which the estimates $\text{X}\text{?}{}_{\mathrm{1N\; +\; 1}}\text{, …,}\text{X}\text{?}{}_{\mathrm{1N\; +\; N}}$ are to be recursively determined for l= 0, 1, 2, . … The optimal steady state estimator is obtained in the limit as N goes to infinity.     

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

Point pattern matching by relaxation

Let $\text{P}\text{= P}{}_1\text{, …, P}{}_{\mathrm{m}}$ and $\text{Q}\text{= Q}{}_1\text{, …, Q}{}_{\mathrm{n}}$ be two patterns of points. Each pairing (P_i, Q_j) of a point of $\text{P}$ with a point of $\text{Q}$ defines a relative displacement δ_ij of the two patterns. We can define a figure of merit for δ_ij according to how closely other point pairs coincide under δ_ij. If there exists a displacement δ₀ for which $\text{P}$ and $\text{Q}$ match reasonably well, the pairings for which δ_ij ? δ₀ will have high merit scores, while other pairings will not. The scores can then be recomputed, giving weights to the other point pairs based on their own scores; and this process can be iterated. When this is done, the scores of pairs that correspond under δ₀ remain relatively high, while those of other pairs become low. Examples of this method of point pattern matching are given, and its possible advantages relative to other methods are discussed.     

Some remarks on a conjecture in parameter adaptive control

A.S. Morse has raised the following question: Do there exist differentiable functions

$\text{f:R}{}^2\text{→ R}\text{and}\text{g:R}{}^2\text{→ R}$

with the property that for every nonzero real number λ and every (x₀, y₀) ∈ $\text{R}$² the solution (x(t),y(t)) of

$\text{x}\text{?}\text{(t) = x(t) + λf(x(t),y(t))}$

,

$\text{y}\text{?}\text{(t) = g(x(t),y(t))}$

,

$\text{x(0) = x}{}_0\text{, y(0) = y}{}_0$

, is defined for all t ? 0 and satisfies

$\text{lim}\text{t → + ∞}$

and y(t) is bounded on [0,∞)? We prove that the answer is yes, and we give explicit real analytic functions f and g which work. However, we prove that if f and g are restricted to be rational functions, the answer is no.     

The decentralized stabilization and control of a class of unknown non-linear time-varying systems

The following problem is considered in this paper. Suppose a system S consists of a set of arbitrary interconnected subsystems S_i, i = 1, 2, …, Ω; is it possible to stabilize and satisfactorily control the whole system S by using only local controllers about the individual subsystems without a knowledge of the manner of the actual interconnections of the whole system? Sufficient conditions are obtained for such a result to hold true; in particular it is shown that a system S consisting of a number of subsystems S_i connected in an arbitrary way between themselves with finite gains: $\text{S}{}_{\mathrm{i}}\text{:}\text{x}\text{?}{}_{\mathrm{i}}\text{=}\text{A}{}_{\mathrm{i}}\text{(}\text{x}{}_{\mathrm{i}}\text{, t)}\text{x}{}_{\mathrm{i}}\text{+}\text{b}{}_{\mathrm{i}}\text{(}\text{x}{}_{\mathrm{i}}\text{, t)u}{}_{\mathrm{i}}\text{, y}{}_{\mathrm{i}}\text{=}\text{c}\text{′}{}_{\mathrm{i}}\text{(}\text{x}{}_{\mathrm{i}}\text{, t)}\text{x}{}_{\mathrm{i}}$ where A_i and b_i have a particular structure, may be satisfactorily controlled by applying only local controllers C_i about the individual subsystems: C_i: u_i = K′_i(?)x_i where K_i is a constant gain matrix with the scalar ? appearing as a parameter, provided ? is large enough.     

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.     

On the stability of convolution feedback systems with dynamical feedback

This paper considers distributed n-inputn-output convolution feedback systems characterized by $\text{y = G}{}_1\text{1e}$, $\text{z = G}{}_2\text{1y}$ and e = u ? z, where the forward path transfer function $\text{G}\text{?}{}_1$ and the feedback path transfer function $\text{G}\text{?}{}_2$ both contain a real single unstable pole at different locations. Theorem 1 gives necessary and sufficient conditions for both input-error and input-output stability. In addition to usual conditions that guarantee input-error stability a new condition is found which results in the fact that input-error stability will guarantee input-output stability. These conditions require to investigate only the open-loop characteristics. A basic device is the consideration of the residues of different transfer functions at the open-loop unstable poles. An example is given.     

On the time-space tradeoff for sorting with linear queries

Extending a result of Borodin et al. [1], we show that any branching program using linear queries “∑_iλ_ix_i:c” to sort n numbers x₁, x₂,…,x_n must satisfy the time-space tradeoff relation $\text{TS = Ω(n}{}^2\text{)}$. The same relation is also shown to be true for branching programs that uses queries “min R = ?” where R is any subset of {x₁, x₂,…,x_n}.     

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.