On a fourth-order unconditionally stable scheme for damped second-order systems

We consider the damped second-order system $\text{M}\text{u}\text{?}\text{+ C/.u + Ku = F(t)}$ (M, C, K symmetric, positive definite n × n matrices) by conversion to an equivalent first-order system

$\text{I}\text{O}\text{O}\text{M}\text{d}\text{d}\text{t}\text{O}\text{?K}\text{I}\text{?C}\text{u}\text{u}\text{?}\text{+}\text{o}\text{F(t)}$

We demonstrate that an algorithm proposed by Fairweather for the implementation of the (2, 2) Padé approximation of the exponential matrix for approximating the solution of homogeneous first-order systems extends advantageously to this case, yielding an unconditionally stable fourth-order scheme with the feature that the approximating equations decouple. As a result we are required only to solve one symmetric complex n × n system of linear algebraic equations at each time step, with a fixed matrix which may be decomposed into triangular factors at the outset. We also consider iterative schemes involving only real, positive definite, symmetric n × n matrices. Numerical results are included.     

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.     

Remarks on the adaptive control of linear plants with unknown high-frequency gain

Adaptive control of first-order linear systems of the form $\text{x}\text{?}\text{= ax + bu}$ with the sign of b unknown is considered. It is shown that stabilizing adaptive controllers exist that have globally bounded gain and prespecified terminal dynamics.     

Random functions with given time correlation

First, on any sequence of real numbers (x_λ), $\text{λ ? [? Λ}{}_1\text{+ Λ] ?}\text{Z}$, the pseudo probability Pr(x, x′) of the event x_λ?[x, x′[ is defined to be the limit when Λ → ∞ of the ratio of the number of x_λ?[x, x′[ to the total number of x_λ. The a.d.f. (asymptotic distribution function) of the sequence is then defined by F(x) = Pr(? ∞, x); it possesses the properties of a d.f. (distribution function). Consequently, what is said below applies equally to a sequence of r.v. (random variables) or to a sequence of p.r.v. (pseudorandom variables) consisting of a sequence (_nx_λ), $\text{n ? [? N, + N] ?}\text{Z}$ of sequences _nx_λ, $\text{λ ? [? Λ, + Λ] ?}\text{Z}$.A weyl's polynomial ?_n(λ) is a polynomial such that one of its coefficieints other than ?(0) is irrational. Then any sequence, the fractional part of ?_n(λ), $\text{λ ? [? Λ, + Λ] ?}\text{Z}$, is asymptotically equidistributed on [0, 1].A property is given which permits the construction of a sequence (_nx_λ), $\text{n ? [? N, + N] ?}\text{Z}$ of pseudostochastically independent sequences _nx_λ, $\text{λ ? [? Λ, + Λ] ?}\text{Z}$.It is known that setting Y_n = F^{(? 1)}(X_n), it is possible to transform any sequence of r.v. X_n     

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.     

Information storage and retrieval — mathematical foundations II (combinatorial problems)

The following combinatorial problem is fundamental for the design of file organizations minimizing simultaneously the storage space and the access time: For a given family $\text{M}$ of subsets of a finite set X, find a partial function S:X→X (if there is one), such that every M?$\text{M}$ can be written as M=lcubx,S(x),?,S^|M|-1 (x)rcub for a suitable x?X. We study the class of families admitting such a function S, as well as some of its subclasses defined by imposing certain restrictions on S (these restrictions reflect the structure of the storage medium to be used for storing a file).     

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.     

Decidable sentences of Church-Rosser congruences

A decision procedure for a class of true sentences of congruences generated by finite monadic Church-Rosser systems is developed. Using this decision procedure it is shown that if $\text{M}$_T is the monoid presented by such a system T, then (i) it is decidable given T whether $\text{M}$_T is a group, (ii) it is decidable given T and a finite set A whether the submonoid generated by A is a group or a left (right, two-sided) ideal, and (iii) Green's relations for $\text{M}$_T are decidable.     

Darboux transformations for factorable Laplace operators

Factorable Laplace operators of the form L = ? _x ? _y + a? _x + b? _y + c, where the coefficients a, b, c are not necessarily constants, are considered. For these operators, the Darboux transformations \(L\xrightarrow{M}L_1\) , M ∈ K[? _x ], defined by the intertwining relation NL = L ₁ M are considered. It is shown that only the following cases are possible: either (1) M ∩ ker? _x + b = {0} and L ₁ is also factorable or (2) M ∩ ker? _x + b contains a nonzero element. We prove that, in both cases, the Darboux transformation can be represented as a product of first-order Darboux transformations. For case (2), the proof is based on the fact that the Darboux transformation of operator L can be reduced to Darboux transformations of first-order operators.     

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.     

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.     

An algorithm for the computation of the transfer function matrix for singular systems

For singular systems, i.e. for systems of the form $\text{E}\text{x}\text{?}\text{= Ax + Bu}$, with E singular, the problem of computing the transfer function matrix has been solved. An algorithm is developed which uses the Souriau-Frame-Faddeev algorithm for regular systems. The final expression is suitable for computer use.     

Improving loops and vanishing variables in long transportation problems

In this paper the following two results are presented: (1)A method which determines the optimal values of certain variables during the iterative solution process. The closer the current primal feasible solution is to the optimal solution, the greater the number of variables which may be determined. (2) For each current feasible solution (X_ij) of the given m × n transportation problem A, a feasible solution ($\text{X}\text{?}{}_{\mathrm{ij}}$) of an auxiliary m × m(m ?1) transportation problem $\text{A}\text{?}$ is constructed. Problem $\text{A}\text{?}$ is shown to be equivalent to an m(m ? 1) × m(m ? 1) assignment problem with two admissible cells per column. The optimally of (X_ij) is shown to imply the optimality of ($\text{X}\text{?}{}_{\mathrm{ij}}$) and conversely. The best “improving loops” (including the improving loops used in MODI) of $\text{A}\text{?}$ are shown to be the best “improving loops” of A as well.     

Kleene chain completeness and fixedpoint properties

Let L denote the nonscalar complexity in k(x₁,…, x_n). We prove $\text{L(?,??/?x}{}_1\text{,…,??/?x}{}_{\mathrm{n}}\text{)?3L(?)}$. Using this we determine the complexity of single power sums, single elementary symmetric functions, the resultant and the discriminant as root functions, up to order of magnitude. Also we linearly reduce matrix inversion to computing the determinant.     

Connective stability of competitive equilibrium

The purpose of this paper is to derive necessary and sufficient conditions for connective stability of non-linear matrix systems described by the equation $\text{x}\text{?}\text{= A(t, x) x}$, where the matrix A(t, x) has time-varying nonlinear elements. The obtained results can be used to study stability of competitive equilibrium in as diverse fields as economics and engineering, model ecosystems and arms races.     

Independent tracking and regulation adaptive control with forgetting factor

This paper considers a discrete-time adaptive control algorithm with a forgetting factor applicable to minimum phase plants. The tracking and regulation objectives are independently specified. The relevance of the eigenvalues of the gain matrix (F_k) used in the updating equation for the adaptive parameters ($\text{}\text{?}\text{gq(k)}$) is shown. It is proved that if the maximum eigenvalue of the inverse of the gain matrix F_k has an upper bound and a non-zero lower bound then the global convergence of the control algorithm is insured. The result of the design is a simple control scheme using a linear constant feedforward controller and a nonlinear feedback controller. The performance of the control structure in tracking and regulation are evaluated by simulations.     

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