New error bound for linear complementarity problems for B-matrices

A new error bound for the linear complementarity problem is obtained when the involved matrix is a B-matrix. This bound improves existing results. Finally, two numerical examples are also given to show that the bound is better than some previous results.     

矩阵方程ATXA=D的条件数与向后扰动分析

讨论矩阵方程ATXA=D,该方程源于振动反问题和结构模型修正.本文利用Moore-Penrose广义逆的性质,给出该方程解的条件数的上、下界估计.同时,利用Schauder不动点理论给出该方程的向后扰动界,这些结果可用于该矩阵方程的数值计算.     

A note on upper bounds on the cp-rank

Hanna and Laffey gave an upper bound on the cp-rank of a completely positive matrix, in terms of its rank and the number of zeros in a full rank principal submatrix. This bound, for the case that the matrix is positive, was improved by Barioli and Berman. In this paper a new straightforward proof of both results is given, and the same approach is used to improve Hanna and Laffey’s bound in the case that the matrix has a zero entry.     

ESTIMATES OF THE DOUBLE DETERMINANTS OF QUATERNION MATRICES

An estimate of the upper bound is given for the double determinant of the sum of two arbitrary quaternion matrices, and meanwhile the lower bound on the double determinant is established especially for the sum of two quaternion matrices which form an assortive pair. As applications, some known results are obtained as corollaries and a question in the matrix determinant theory is answered completely.     

Novel delay-dependent asymptotic stability criteria for neural networks with time-varying delays

The problem of delay-dependent asymptotic stability criteria for neural networks (NNs) with time-varying delays is investigated. An improved linear matrix inequality based on delay-dependent stability test is introduced to ensure a large upper bound for time-delay. A new class of Lyapunov function is constructed to derive a novel delay-dependent stability criteria. Finally, numerical examples are given to indicate significant improvement over some existing results.     

严格对角占优M-矩阵的逆矩阵的无穷大范数的新上界

给出了严格对角占优M-矩阵的逆矩阵的无穷大范数上界新的估计式,进而给出严格对角占优M-矩阵的最小特征值下界的估计式.新估计式改进了已有文献的结果.     

Estimates for the density of a nonlinear Landau process

The aim of this paper is to obtain estimates for the density of the law of a specific nonlinear diffusion process at any positive bounded time. This process is issued from kinetic theory and is called Landau process, by analogy with the associated deterministic Fokker-Planck-Landau equation. It is not Markovian, its coefficients are not bounded and the diffusion matrix is degenerate. Nevertheless, the specific form of the diffusion matrix and the nonlinearity imply the non-degeneracy of the Malliavin matrix and then the existence and smoothness of the density. In order to obtain a lower bound for the density, the known results do not apply. However, our approach follows the main idea consisting in discretizing the interval time and developing a recursive method. To this aim, we prove and use refined results on conditional Malliavin calculus. The lower bound implies the positivity of the solution of the Landau equation, and partially answers to an analytical conjecture. We also obtain an upper bound for the density, which again leads to an unusual estimate due to the bad behavior of the coefficients.     

On computation of the steady-state probability distribution of probabilistic Boolean networks with gene perturbation

Given a Probabilistic Boolean Network (PBN), an important problem is to study its steady-state probability distribution for network analysis. In this paper, we present a new perturbation bound of the steady-state probability distribution of PBNs with gene perturbation. The main contribution of our results is that this new bound is established without additional condition required by the existing method. The other contribution of this paper is to propose a fast algorithm based on the special structure of a transition probability matrix of PBNs with gene perturbation to compute its steady-state probability distribution. Experimental results are given to demonstrate the effectiveness of the new bound, and the efficiency of the proposed method.     

An approximate solution for linear boundary-value problems with slowly varying coefficients

In this paper, an approximate closed-form solution for linear boundary-value problems with slowly varying coefficient matrices is obtained. The derivation of the approximate solution is based on the freezing technique, which is commonly used in analyzing the stability of slowly varying initial-value problems as well as solving them. The error between the approximate and the exact solutions is given, and an upper bound on the norm of the error is obtained. This upper bound is proportional to the rate of change of the coefficient matrix of the boundary-value problem. The proposed approximate solution is obtained for a two-point boundary-value problem and is compared to its solution obtained numerically. Good agreement is observed between the approximate and the numerical solutions, when the rate of change of the coefficient matrix is small.     

关于Wielandt-Hoffman定理

关于正规矩阵的任意扰动,有下述定理成立. 定理1.设A为n阶正规矩阵,C为n阶任一矩阵.A的特征值为λ_1,…,λ_n,C的特征值为μ_1…,μ_n.C~H表示C的转置共轭,||·||_2与||·||_F分别表示矩阵的谱范数与Frobenius范数.记     

A new operational matrix based on Bernoulli wavelets for solving fractional delay differential equations

In this research, a Bernoulli wavelet operational matrix of fractional integration is presented. Bernoulli wavelets and their properties are employed for deriving a general procedure for forming this matrix. The application of the proposed operational matrix for solving the fractional delay differential equations is explained. Also, upper bound for the error of operational matrix of the fractional integration is given. This operational matrix is utilized to transform the problem to a set of algebraic equations with unknown Bernoulli wavelet coefficients. Several numerical examples are solved to demonstrate the validity and applicability of the presented technique.     

Bounds for the extremal eigenvalues of a class of symmetric tridiagonal matrices with applications

We consider a class of symmetric tridiagonal matrices which may be viewed as perturbations of Toeplitz matrices. The Toeplitz structure is destroyed since two elements on each off-diagonal are perturbed. Based on a careful analysis, we derive sharp bounds for the extremal eigenvalues of this class of matrices in terms of the original data of the given matrix. In this way, we also obtain a lower bound for the smallest singular value of certain matrices. Some numerical results indicate that our bounds are extremely good.     

Asymptotic theory for robust principal components

The asymptotic distribution of the eigenvalues and eigenvectors of the robust scatter matrix proposed by R. Maronna in 1976 is given when the observations are from an ellipsoidal distribution. The elements of each characteristic vector are the coefficients of a robustified version of principal components. We give a definition for the asymptotic efficiency of these estimators and we evaluate their influence curve. The problem of maximizing the efficiency under a bound on the influence curve is solved. Numerically, we calibrate the optimal estimators under the multivariate normal distribution and we evaluate their sensitivity.     

The Worst-Case GMRES for Normal Matrices

We study the convergence of GMRES for linear algebraic systems with normal matrices. In particular, we explore the standard bound based on a min-max approximation problem on the discrete set of the matrix eigenvalues. This bound is sharp, i.e. it is attainable by the GMRES residual norm. The question is how to evaluate or estimate the standard bound, and if it is possible to characterize the GMRES-related quantities for which this bound is attained (worst-case GMRES). In this paper we completely characterize the worst-case GMRES-related quantities in the next-to-last iteration step and evaluate the standard bound in terms of explicit polynomials involving the matrix eigenvalues. For a general iteration step, we develop a computable lower and upper bound on the standard bound. Our bounds allow us to study the worst-case GMRES residual norm as a function of the eigenvalue distribution. For hermitian matrices the lower bound is equal to the worst-case residual norm. In addition, numerical experiments show that the lower bound is generally very tight, and support our conjecture that it is to within a factor of 4/π of the actual worst-case residual norm. Since the worst-case residual norm in each step is to within a factor of the square root of the matrix size to what is considered an “average” residual norm, our results are of relevance beyond the worst case. This revised version was published online in July 2006 with corrections to the Cover Date.     

Solution Bounds for the Discrete Riccati Equation and Its Applications

In this paper, we address the estimation problem for the solution of the discrete algebraic matrix Riccati equation. Both upper and lower bounds are measured. Compared to the majority of the approaches proposed in the literature, the present results are sharper. We also apply the results obtained to solve the robust stabilization problem of discrete time-delay systems. A robust stabilizability criterion and the corresponding state feedback control law are proposed. Furthermore, the tolerable bound of the delay term is also estimated. Finally, numerical examples are given to demonstrate the applications of the results.     

Stability of rootfinding for barycentric Lagrange interpolants

Computing the roots of a univariate polynomial can be reduced to computing the eigenvalues of an associated companion matrix. For the monomial basis, these computations have been shown to be numerically stable under certain conditions. However, for certain applications, polynomials are more naturally expressed in other bases, such as the Lagrange basis or orthogonal polynomial bases. For the Lagrange basis, the equivalent stability results have not been published. We show that computing the roots of a polynomial expressed in barycentric form via the eigenvalues of an associated companion matrix pair is numerically stable, and give a bound for the backward error. Numerical experiments show that the error bound is approximately an order of magnitude larger than the backward error. We also discuss the matter of scaling and balancing the companion matrix to bring it closer to a normal pair. With balancing, we are able to produce roots with small backward error.     

A parallel branch and bound algorithm for solving large asymmetric traveling salesman problems

A parallel branch and bound algorithm that solves the asymmetric traveling salesman problem to optimality is described. The algorithm uses an assignment problem based lower bounding technique, subtour elimination branching rules, and a subtour patching algorithm as an upper bounding procedure. The algorithm is organized around a data flow framework for parallel branch and bound. The algorithm begins by converting the cost matrix to a sparser version in such a fashion as to retain the optimality of the final solution. Computational results are presented for three different classes of problem instances: (1) matrix elements drawn from a uniform distribution of integers for instances of size 250 to 10 000 cities, (2) instances of size 250 to 1000 cities that concentrate small elements in the upper left portion of the cost matrix, and (3) instances of size 300 to 3000 cities that are designed to confound neighborhood search heuristics.     

A branch and bound algorithm for the matrix bandwidth minimization

In this article, we first review previous exact approaches as well as theoretical contributions for the problem of reducing the bandwidth of a matrix. This problem consists of finding a permutation of the rows and columns of a given matrix which keeps the non-zero elements in a band that is as close as possible to the main diagonal. This NP-complete problem can also be formulated as a labeling of vertices on a graph, where edges are the non-zero elements of the corresponding symmetrical matrix. We propose a new branch and bound algorithm and new expressions for known lower bounds for this problem. Empirical results with a collection of previously reported instances indicate that the proposed algorithm compares favourably to previous methods.     

Fourier analysis of a robust multigrid method for convection-diffusion equations

Summary. We consider a two-grid method for solving 2D convection-diffusion problems. The coarse grid correction is based on approximation of the Schur complement. As a preconditioner of the Schur complement we use the exact Schur complement of modified fine grid equations. We assume constant coefficients and periodic boundary conditions and apply Fourier analysis. We prove an upper bound for the spectral radius of the two-grid iteration matrix that is smaller than one and independent of the mesh size, the convection/diffusion ratio and the flow direction; i.e. we have a (strong) robustness result. Numerical results illustrating the robustness of the corresponding multigrid -cycle are given. Received October 14, 1994     

Novel robust stability criteria for uncertain systems with time-varying delay

This paper is concerned with the delay-dependent stability and robust stability criteria for linear systems with time-varying delay and norm-bounded uncertainties. Through constructing a general form of Lyapunov–Krasovskii functional, and using integral inequalities, some slack matrices and newly established convex combination condition in the calculation, the delay-dependent stability criteria are derived in terms of linear matrix inequalities. Numerical examples are given to illustrate the improvement on the conservatism of the delay bound over some reported results in the literature.