On some asymptotic uncertainty bounds in recursive least squaresidentification

This note deals with the performance of the recursive least squares algorithm when it is applied to problems where the measured signal is corrupted by bounded noise. Using ideas from bounding ellipsoid algorithms we derive an asymptotic expression for the bound on the uncertainty of the parameter estimate for a simple choice of design variables. This bound is also transformed to a bound on the uncertainty of the transfer function estimate     

Decision methods for some optimization problems in recognition theory

By optimizing different models of recognition algorithms, a number of discrete extreme problems appear. The search for the maximum solvable subsystem of the system of linear inequalities is one of these tasks. In certain cases additional requirements on a desired solvable subsystem can be imposed. The solution methods for some types of such tasks are proposed.     

Decision methods for some discrete extreme problems in recognition theory

By optimizing different models of recognition algorithms, a number of discrete extreme problems appear. The search for the maximum solvable subsystem of the system of linear inequalities is one of these tasks. The solution algorithm for this problem is described. This algorithm is effective for linear systems of small ranks. Also, an approximate method that is effective for systems of large dimensionality is proposed. The text was submitted by the author in English. Natalja N. Katerinochkina. Born 1945. Graduated from the Faculty of Mechanics and Mathematics, Moscow State University, in 1967. Received candidates degree in Physics and Mathematics in 1978. The senior scientific worker at the Dorodnicyn Computing Centre, Russian Academy of Science. Scientific interests: discrete mathematics, mathematical cybernetics, pattern recognition, discrete optimization. Author of 35 publications.     

On consistency for the method of least squares using martingale theory

Least squares identification is considered from the Bayesian point of view. A necessary and sufficient condition for consistency almost everywhere is given under the assumption that the data are generated by a regression model with white and Ganssian noise.     

Accuracy of preconditioned CG-type methods for least squares problems

The conjugate gradient method with IMGS, an incomplete modified version of Gram-Schmidt orthogonalization to obtain an incomplete orthogonal factorization preconditioner, applied to the normal equations (PCGLS) is often used as the basic iterative method to solve the linear least squares problems. In this paper, a detailed analysis is given for understanding the effect of rounding errors on IMGS and determining the accuracy of computed solutions of PCGLS with IMGS for linear least squares problems in finite precision. It is shown that for a consistent system, the difference between the true residuals and the updated approximate residual vectors generated depends on the machine precision ε, on the maximum growth in norm of the iterates over their initial values, the norm of the true solution, and the condition number of R which is affected by the drop set in incomplete Gram-Schmidt factorization. Similar results are obtained for the difference between the true and computed solution for inconsistent systems. Numerical tests are carried out to confirm the theoretical conclusions.     

The complexity of some polynomial network consistency algorithms for constraint satisfaction problems

Constraint satisfaction problems play a central role in artificial intelligence. A class of network consistency algorithms for eliminating local inconsistencies in such problems has previously been described. We analyze the time complexity of several node, arc and path consistency algorithms and prove that arc consistency is achievable in time linear in the number of binary constraints. The Waltz filtering algorithm is a special case of the arc consistency algorithm. In the edge labelling computational vision application the constraint graph is planar and so the time complexity is linear in the number of variables.     

Block SOR methods for the solution of indefinite least squares problems

This paper describes a technique for constructing block SOR methods for the solution of the large and sparse indefinite least squares problem which involves minimizing a certain type of indefinite quadratic form. Two block SOR-based algorithms and convergence results are presented. The optimum parameters for the methods are also given. It has been shown both theoretically and numerically that the optimum block SOR methods have a faster convergence than block Jacobi and Gauss–Seidel methods.     

Efficient Parallel Algorithms for Some Graph Theory Problems

In this paper,a sequential algorithm computing the aww vertex pair distance matrix D and the path matrix Pis given.On a PRAM EREW model with p,1≤p≤n^2,processors,a parallel version of the sequential algorithm is shown.This method can also be used to get a parallel algorithm to compute transitive closure array A^* of an undirected graph.The time complexity of the parallel algorithm is O(n^3/p).If D,P and A^* are known,it is shown that the problems to find all connected components,to compute the diameter of an undirected graph,to determine the center of a directed graph and to search for a directed cycle with the minimum(maximum)length in a directed graph can all be solved in O(n^2/p logp)time.     

Preconditioned conjugate gradient methods for the solution of indefinite least squares problems

The conjugate gradient (CG) method is considered for solving the large and sparse indefinite least squares (ILS) problem min  _x (b−Ax) ^T J(b−Ax) where J=diag (I _p ,−I _q ) is a signature matrix. However the rate of convergence becomes slow for ill-conditioned problems. The QR-based preconditioner is found to be effective in accelerating the convergence. Numerical results show that the sparse Householder QR-based preconditioner is superior to the CG method especially for sparse and ill-conditioned problems.     

Work-efficient BSR-based parallel algorithms for some fundamental problems in graph theory

This paper presents BSR-parallel algorithms for some problems in fundamental graph theory : transitive closure, connected components, spanning tree, bridges and articulation points of a graph and bipartite graph recognition. There already exist constant time algorithms to solve these problems on a mesh with reconfigurable bus system using O(N ⁴) processors. Here we show that these problems can be solved in constant time using only O(N ²) processors on the BSR model (N is the number of vertices of the graph G). Therefore, our algorithms are more work-efficient. These new results suggest that many other problems in graph theory can be solved in constant time using the BSR model.     

Fast projection methods for minimal design problems in linear system theory

The so-called minimal design problem (or MDP) of linear system theory is to find a proper minimal degree rational matrix solution of the equation H(z)D(z)=N(z), where {N(z),D(z)} are given p×r and m×r polynomial matrices with D(z) of full rank r≦m.We describe some solution algorithms that appear to be more efficient (in terms of number of computations and of potential numerical stability) than those presently known. The algorithms are based on the structure of a polynomial echelon form of the left minimal basis of the so-called generalized Sylvester resultant matrix of {N(z), D(z)}. Orthogonal projection algorithms that exploit the Toeplitz structure of this resultant matrix are used to reduce the number of computations needed for the solution.     

Control and optimization methods in communication network problems

The authors focus on two areas of communication network design in which methods of control and optimization theory have proven useful. These are the area of multiple access communication (for networks with shared links such as radio networks and local area networks) and the area of network routing (for networks with point-to-point interconnections). They review a few selected problems in each area to show the role of the control concepts involved and then proceed to identify other areas of communication network design in which the same control theoretic and optimization methodology may be applicable and useful. They attempt to bring to the attention of the control systems community the numerous instances of problems arising in the pure communication network design process that can benefit from the attention and the capabilities of this community     

逻辑理论的随机相容度

在[n]值Lukasiewicz命题逻辑系统中,提出理论的随机相容度的概念,并指出理论的随机相容度是和概率分布列的选取相关的。最后证明了理论的随机相容度在[n]值随机逻辑度量空间中,同样保持经典逻辑度量空间中的基本性质。     

Solution of some boundary value problems in applied mechanics by the collocation least square method

The conventional simple but crude method of collocation is greatly improved by a least square augmentation. Simplicity in application and good accuracy of the proposed collocation least square scheme is demonstrated by the solution of some complex problems in applied mechanics.Example solutions of such problems include the linear and nonlinear analyses of isotropic plates, orthotropic plates and plates on elastic foundations. Numerical and graphical results are presented and compared with existing solutions. For the problems considered herein, the present method proves to be much less laborious than other numerical methods frequently employed by previous investigators.     

Applications of Newton's method to some numerical problems in matrix theory

Newton's classical method is applied to the map (Λ, X)→XΛX^T-A (with Λ diagonal and X orthogonal) for the simultaneous computation of the eigenvalues and the eigenvectors of a symmetric matrix A. It is proved that the method is applicable also to matrices with multiple eigenvalues with the same rate of convergence as for the case of simple eigenvalues. The problem of determining the Schur triangular form of a generic matrix by the same approach is also discussed.     

On some numerical methods for spectral computations in λ-rational Sturm–Liouville problems

This paper is concerned with the numerical solution of a λ-rational Sturm–Liouville problem. Classical methods are considered in connection with the shooting technique used via the method of Magnus series and boundary value methods. We prove that, in the presence of an eigenvalue embedded in the essential spectrum, these methods exhibit a decay in their performance. Nevertheless some boundary value methods used in a non-standard form behave as in the standard form in regular problems preserving a high order of convergence. Numerical experiments confirm the theory. Received: November 2001 / Accepted: February 2002 Work supported by the Italian MURST.     

Solution of some symmetrical plane thermal problems by the boundary point least squares method

The present work is devoted to the collocation solution of some stationary temperature problems in regions with geometrical symmetry, temperature symmetry and/or antisymmetry with respect to 2 and 4 axes. Such problems are encountered e.g. in solving tube sheets of heat exchangers. The success of collocation solution depends on the suitability of the temperature function used. At first, two (auxiliary) temperature functions are derived using the simple harmonic series, one being symmetrical and the other antisymmetrical about the x-axis. Further, the method of deriving 7 harmonic temperature functions and their resulting forms is given for 3 (4) types of problems with geometrical symmetry about 2 (4) axes. The obtained functions satisfy a priori all conditions of symmetry and/or antisymmetry of the problem. The coefficients of the temperature functions are determined by the boundary point least squares method. KOLOKT, a program set up for the desk computer HP 9845 is described and some results are given. The technique described can be applied also to the derivation of stress functions and to the solution of thermal stresses.