Certain modifications of the AB-algorithm

One considers various modifications of the AB-algorithm for the solution of the complete (partial) eigenvalue problem of a regular pencil A-B of square matrices. A modification of the AB-algorithm is suggested which allows to eliminate in a finite number of steps the zero and the infinite eigenvalues of the pencil A-B and to lower its dimensions. For regular pencils with real eigenvalues a modification ot the AB-algorithm with a shift is presented. For a well-defined choice of the shifts one proves the quadratic convergence of the algorithm, successively to each eigenvalue of the pencil, starting with the smallest one. For a pencil whose eigenvalues can be divided into the groups of large and small eigenvalues, one considers a modification of the AB-algorithm, allowing to obtain approximations to the indicated groups of eigenvalues as solutions of a problem for pencils of lower dimensions.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 111, pp. 117–136, 1981     

Construction of a fundamental series of solutions of a pencil of matrices

Solution of spectral problems for a singular polynomial pencil of matrices D () of degree s1 and sizem×n is considered. Two algorithms for constructing polynomials solutions of pencils D () are considered: the first is a modification of an algorithm proposed earlier by one of the authors for determining polynomial solutions of a linear pencil; the second algorithm is based on other ideas and consists of two steps. At the first step a finite sequence of auxiliary pencils is constructed for each of which a basis of polynomial solutions of degree zero is found. At the second step the basis so constructed are rearranged into polynomial solutions of the original polynomial pencil D(). Both algorithms make it possible to find solutions of the original pencil in order of increasing degrees. For constructing a fundamental series of solutions of the pencil D() two new algorithms are proposed which work independently with either of the algorithms mentioned above for constructing polynomial solutions by rearranging them into linearly independent solutions of the pencil.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 139, pp. 74–93, 1984.     

Probabilist,possibilist and belief objects for knowledge analysis

The main aim of the symbolic approach in data analysis is to extend problems, methods and algorithms used on classical data to more complex data called symbolic objects which are well adapted to representing knowledge and which are generic unlike usual observations which characterize individual things. We introduce several kinds of symbolic objects: Boolean, possibilist, probabilist and belief. We briefly present some of their qualities and properties; three theorems show how Probability, Possibility and Evidence theories may be extended on these objects. Finally, four kinds of data analysis problems including the symbolic extension are illustrated by several algorithms which induce knowledge from classical data or from a set of symbolic objects.     

On a Unitary Transform in the Space L2(Ω\ℝ3) Connected with the Weyl Decomposition

In papers devoted to the dynamical inverse problem for the Naxwell system, in the context of the BC method, a unitary transform M: solenoidal field transversal field was introduced. In this paper, M is complemented by a transform N: potential field longitudinal field. Isometry and completeness of N are established. The transform U = M N mentioned in the title, turns out to be a unitary oprator. Bibliography: 5 titles.     

Die windschiefen Flächen konstanten Dralls in der Normalenkongruenz einer Fläche

In the congruence of surface normals of a given surface, the ruled surfaces for which the parameter of distribution has the constant value =0 or = are known to be developables and their base curves on the surface are the lines of curvature. In this paper a characterization is given of the ruled surfaces in the congruence of normals for which the parameter of distribution has a constant value (o,). If the given surface is developable the base curves may be characterized by a simple integral representation. If the given surface is not developable a characterization of the base curves is possible by means of the strips circumscribed along the base curves. Moreover the striction lines and torsal generators of these ruled surfaces are studied.

---

---

Herrn Professor Dr. W. Wunderlich zum 60. Geburtstag gewidmet     

Ergodic properties of certain surjective cellular automata

We consider one-dimensional cellular automata, i.e. the mapsT:P P (P is a finite set with more than one element) which are given by (Tx) _i =F(x _i+l , ...,x _i+r ),x=(x _i )P for some integerslr and a mappingFP ^r–l+1P. We prove that ifF is right- (left-) permutative (in Hedlund's terminology) and 0l<r (resp.l<r0), then the natural extension of the dynamical system (P , , ,T) is a Bernoulli automorphism ( stands for the (1/p, ..., 1/p)-Bernoulli measure on the full shiftP ). Ifr<0 orl>0 andT is surjective, then the natural extension of the system (P , , ,T) is aK-automorphism. We also prove that the shift ²-action on a two-dimensional subshift of finite type canonically associated with the cellular automatonT is mixing, ifF is both right and left permutative. These results answer some questions raised in [SR].     

Spectral Asymptotics for a Steady-State Heat Conduction Problem in a Perforated Domain

In this paper we study the eigenvalues and eigenfunctions of a boundary-value problem for an elliptic equation of second order with oscillatory coefficients in a periodically perforated domain when the boundary condition on the external boundary is of the first type and on the boundary of holes of the third type, for the case in which the linear dimension of the perforation period tends to zero. It is proved that these eigenvalues and eigenfunctions can be determined approximately via the eigenvalues and eigenfunctions of an essentially simpler Dirichlet problem for an elliptic equation with constant coefficients in a domain without holes. Estimates of errors in these approximations are given.     

Model reduction techniques for sampled-data systems

An approximately balanced realization of linear finite-dimensional sampled-data systems is proposed. The theoretical support of the approximately balancing algorithm is represented by a result on the asymptotic expansions with respect to the sampling step of the sampled controllability and observability graminas. Reduced order models obtained as singular perturbational approximations of approximately balanced realizations of sampled-data systems are shown to be acceptable solutions to the sampled-data system model reduction problem in the sense that, enjoying some asymptotic properties, they come close to the exact solutions as the sampling step decreases. An example illustrates the results.     

A smoothing-out technique for min—max optimization

In this paper, we suggest approximations for smoothing out the kinks caused by the presence of max or min operators in many non-smooth optimization problems. We concentrate on the continuous-discrete min—max optimization problem. The new approximations replace the original problem in some neighborhoods of the kink points. These neighborhoods can be made arbitrarily small, thus leaving the original objective function unchanged at almost every point ofR ⁿ . Furthermore, the maximal possible difference between the optimal values of the approximate problem and the original one, is determined a priori by fixing the value of a single parameter. The approximations introduced preserve properties such as convexity and continuous differentiability provided that each function composing the original problem has the same properties. This enables the use of efficient gradient techniques in the solution process. Some numerical examples are presented.     

Packing random items of three colors

Consider three colors 1,2,3, and forj3, considern items (X _i,j)in of colorj. We want to pack these items inn bins of equal capacity (the bin size is not fixed, and is to be determined once all the objects are known), subject to the condition that each bin must contain exactly one item of each color, and that the total item sizes attributed to any given bin does not exceed the bin capacity. Consider the stochastic model where the random variables (X _i,jj)in,j3 are independent uniformly distributed over [0,1]. We show that there is a polynomial-time algorithm that produces a packing which has a wasted spaceK logn with overwhelming probability.Work partially supported by an N.S.F. grant.     

Spectral properties of λ-matrices

One investigates the spectral problem for polynomial -matrices of the general form (regular and singular). One establishes a relation between the elements of the complete spectral structure of the -matrix (i.e., its elementary divisors, its Jordan chains of vectors, its minimal indices and polynomial solutions) and of the matrices which occur in its transformation to the Smith canonical form. One establishes a correspondence between the complete spectral structures of a -matrix and of three linear accompanying matrix pencils. One notes the possibility of reducing the solution of the spectral problem for a -matrix to the solution of a similar problem for its accompanying pencil. One gives a factorization of a -matrix which allows to represent it by any of its considered accompanying pencils or by its Kronecker canonical form.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 111, pp. 180–194, 1981.     

Nonlinear eigenvalue approximation

Summary For each in some domainD in the complex plane, letF() be a linear, compact operator on a Banach spaceX and letF be holomorphic in . Assuming that there is a so thatI–F() is not one-to-one, we examine two local methods for approximating the nonlinear eigenvalue . In the Newton method the smallest eigenvalue of the operator pencil [I–F(),F()] is used as increment. We show that under suitable hypotheses the sequence of Newton iterates is locally, quadratically convergent. Second, suppose 0 is an eigenvalue of the operator pencil [I–F(),I] with algebraic multiplicitym. For fixed leth() denote the arithmetic mean of them eigenvalues of the pencil [I–F(),I] which are closest to 0. Thenh is holomorphic in a neighborhood of andh()=0. Under suitable hypotheses the classical Muller's method applied toh converges locally with order approximately 1.84.     

Intermediate Jacobians and Chow groups of threefolds with a pencil of del Pezzo surfaces

Summary In this paper we study threefolds with a pencil of del Pezzo surfaces with 1K²5. The curve which parametrises the exceptional curves on the fibers and the incidence correspondence on it determine a Prym-Tjurin variety which is an abelian subvariety of the Jacobian of the curve. Under certain restrictions on the singular fibers of the pencil we prove that there is a polarized isomorphism between the intermediate Jacobian of the threefold and the Prym-Tjurin variety and an isomorphism between the latter and the Chow group of algebraic one-cycles algebraically equivalent to zero.     

Über geschlossene affine Zwangläufe in der Ebene

We consider integral coverings y:{1,2,..,} of an affine plane which occur when is moved under a continuous periodic affine motion(t):. One can distinguish normal points × , i.e. is constant in a certain neighborhood of x, and singular points. If (x) is the number of times x passes through its orbit (t)x all normal points x have (x)=1, and the set of all singular points consists of a number of isolated points and lines. If (x) is the tangent rotation number of the orbit of x all singular points lie on the moving pole curve.     

Backward perturbation analysis of certain characteristic subspaces

Summary This paper gives optimal backward perturbation bounds and the accuracy of approximate solutions for subspaces associated with certain eigenvalue problems such as the eigenvalue problemAx=x, the generalized eigenvalue problem Ax=Bx, and the singular value decomposition of a matrixA. This paper also gives residual bounds for certain eigenvalues, generalized eigenvalues and singular values.This subject was supported by the Swedish Natural Science Research Council and the Institute of Information Processing of the University of Umeå.     

Computing convolutions by reciprocal search

In this paper we show how certain geometric convolution operations can be computed efficiently. Here efficiently means that our algorithms have running time proportional to the input size plus the output size. Our convolution algorithms rely on new optimal solutions for certain reciprocal search problems, such as finding intersections between blue and green intervals, and overlaying convex planar subdivisions.This research was done while on leave from Cornell at DEC/SRC.     

Continuity of the eigenvalues of self-adjoint operators with respect to the strong operator topology

Let T_n, T, and S be self-adjoint operators such that T_n converges to T in the sense of strong resolvent convergence. If S is bounded from below, _e(S) (–,O) = Ø, and T_n S for all n, then the negative eigenvalues of T_n converge to the negative eigenvalues of T. The corresponding eigenfunctions converge in norm. This generalizes a result due to T. Kato, where T_n T is assumed, and a recent result of the author for the case T_n T_n+1.     

Spektrale Invarianz bei verallgemeinerten Eigenfunktionsentwicklungen

Let T be a selfadjoint operator in a Gelfand triplet H. Examples show that there can occur generalized eigenvalues of T which are not in the Hilbert space spectrum (T) of T. Moreover, the fuction d, which assigns to each real number s the dimension of the generalized eigenspace corresponding to s, can be essentially greater then the von Neumann multiplicity function of T. We therefore construct a new triplet H, closely related to the given Gelfand triplet, according to which the set of generalized eigenvalues of T is contained in (T), and the function d essentially equals the von Neumann multiplicity function of T. Then, in particular, the closure of the set of generalized eigenvalues equals (T). The expansion theorems in H are transferred to H.

---

---

Grundlage dieser Arbeit ist ein Teil meiner Dissertation. Ich danke Herrn Prof. Dr. H.G. Tillmann für die Anregung hierzu und für viele wertvolle Hinweise.     

A result from diophantine approximation which has applications in economics

We say that a real number allows poor approximations if we can find 0<=()<1 and a sequence of integers n₁2<... such that for all rationals p/q with qn. we have |–.p/q| > Kn _j ^–l– where K is a constant depending only on .In this note we prove that the set of numbers which allow poor approximations are precisely the very well-approximable numbers.The existence of numbers with poor approximations has been used by Cheng [1] to show the existence of a dense set of economies whose cone converges to the Walras equilibrium as slowly as 0(n^–1/2–) after n replications.     

Minimality of derivative chains,corresponding to a boundary value problem on a finite segment

One investigates the minimality of derivative chains, constructed from the root vectors of polynomial pencils of operators, acting in a Hilbert space. One investigates in detail the quadratic pencil of operators. In particular, for L()=L₀+L₁+²L₂ with bounded operators L₀0, L₂0 and Re L₁0, one shows the minimality in the space_173-02 of the system {x_k, _kekx_k}, where x_k are eigenvectors of L(), corresponding to the characteristic numbers _kin the deleted neighborhoods of which one has the representation L^–1()=(–_k)^–1R_K+W_K() with one-dimensional operators R_k and operator-valued functions W_K(), k=1, 2, ..., analytic for =_k.Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 42, No. 2, pp. 195–205, February, 1990.