A comparison of error bounds for linear complementarity problems of H-matrices

We give new error bounds for the linear complementarity problem when the involved matrix is an H-matrix with positive diagonals. We find classes of H-matrices for which the new bounds improve considerably other previous bounds. We also show advantages of these new bounds with respect the computational cost. A new perturbation bound of H-matrices linear complementarity problems is also presented.     

A characteristic quantity of P-matrices

In this note, we develop some new properties of a fundamental quantity associated with a P-matrix introduced by Mathias and Pang [1]. Also, based on extensions of such a quantity, we obtain global error bounds for the vertical and horizontal linear complementarity problems.     

ON THE ACCURACY OF THE LEAST SQUARES AND THE TOTAL LEAST SQUARES METHODS

Consider solving an overdetermined system of linear algebraic equations by both the least squares method (LS) and the total least squares method (TLS). Extensive published computational evidence shows that when the original system is consistent. one often obtains more accurate solutions by using the TLS method rather than the LS method. These numerical observations contrast with existing analytic perturbation theories for the LS and TLS methods which show that the upper bounds for the LS solution are always smaller than the corresponding upper bounds for the TLS solutions. In this paper we derive a new upper bound for the TLS solution and indicate when the TLS method can be more accurate than the LS method.Many applied problems in signal processing lead to overdetermined systems of linear equations where the matrix and right hand side are determined by the experimental observations (usually in the form of a lime series). It often happens that as the number of columns of the matrix becomes larger, the ra     

On the Complexity of Computing Error Bounds

We consider the cost of estimating an error bound for the computed solution of a system of linear equations, i.e., estimating the norm of a matrix inverse. Under some technical assumptions we show that computing even a coarse error bound for the solution of a triangular system of equations costs at least as much as testing whether the product of two matrices is zero. The complexity of the latter problem is in turn conjectured to be the same as matrix multiplication, matrix inversion, etc. Since most error bounds in practical use have much lower complexity, this means they should sometimes exhibit large errors. In particular, it is shown that condition estimators that: (1) perform at least one operation on each matrix entry; and (2) are asymptotically faster than any zero tester, must sometimes over or underestimate the inverse norm by a factor of at least , where n is the dimension of the input matrix, k is the bitsize, and where either or grows faster than any polynomial in n . Our results hold for the RAM model with bit complexity, as well as computations over rational and algebraic numbers, but not real or complex numbers. Our results also extend to estimating error bounds or condition numbers for other linear algebra problems such as computing eigenvectors. September 10, 1999. Final version received: August 23, 2000.     

Estimation of systems with statistically-constrained inputs

This paper discusses the estimation of a class of discrete-time linear stochastic systems with statistically-constrained unknown inputs (UI), which can represent an arbitrary combination of a class of un-modeled dynamics, random UI with unknown covariance matrix and deterministic UI. In filter design, an upper bound filter is explored to compute, recursively and adaptively, the upper bounds of covariance matrices of the state prediction error, innovation and state estimate error. Furthermore, the minimum upper bound filter (MUBF) is obtained via online scalar parameter convex optimization in pursuit of the minimum upper bounds. Two examples, a system with multiple piecewise UIs and a continuous stirred tank reactor (CSTR), are used to illustrate the proposed MUBF scheme and verify its performance.     

Error bounds for linear complementarity problems of DB-matrices

Doubly B-matrices (DB-matrices), which properly contain B-matrices, are introduced by Peña (2003) [2]. In this paper we present error bounds for the linear complementarity problem when the matrix involved is a DB-matrix and a new bound for linear complementarity problem of a B-matrix. The numerical examples show that the bounds are sharp.     

Global error bounds for the extended vertical LCP

A new necessary and sufficient condition for the row -property is given. By using this new condition and a special row rearrangement, we provide two global error bounds for the extended vertical linear complementarity problem under the row -property, which extend the error bounds given in Chen and Xiang (Math. Program. 106:513–525, 2006) and Mathias and Pang (Linear Algebra Appl. 132:123–136, 1990) for the P-matrix linear complementarity problem, respectively. We show that one of the new error bounds is sharper than the other, and it can be computed easily for some special class of the row -property block matrix. Numerical examples are given to illustrate the error bounds. The work was in part supported by a Grant-in-Aid from Japan Society for the Promotion of Science, and the National Natural Science Foundation of China (10671010).     

与P矩阵和LCP有关的量(英文)

发展了与P矩阵有关的基本量的一些新性质,并且改进了由Xiu和Zhang[A characteristic quantity ofP-matrices,Appl.Math.Lett.,2002,15:41-46]提出的水平线性余问题全局误差上限.     

Error bounds for linear complementarity problems of Nekrasov matrices

We present error bounds for the linear complementarity problem when the involved matrix is a Nekrasov matrix and also when it is a \(\Sigma \) -Nekrasov matrix. The new bounds can improve considerably other previous bounds.     

ARNOLDI TYPE ALGORITHMS FOR LARGE UNSYMMETRIC MULTIPLE EIGENVALUE PROBLEMS

1.IntroductionTheLanczosalgorithm[Zo]isaverypowerfultoolforextractingafewextremeeigenvaluesandassociatedeigenvectorsoflargesymmetricmatrices[4'5'22].Sincethe1980's,considerableattentionhasbeenpaidtogeneralizingittolargeunsymmetricproblems.Oneofitsgen...     

Circuit lower bounds and linear codes

In 1977, Valiant proposed a graph-theoretical method for proving lower bounds on algebraic circuits with gates computing linear functions. He used this method to reduce the problem of proving lower bounds on circuits with linear gates to proving lower bounds on the rigidity of a matrix, a notion that he introduced in that paper. The largest lower bound for an explicitly given matrix is due to J. Friedman, who proved a lower bound on the rigidity of the generator matrices of error-correcting codes over finite fields. He showed that the proof can be interpreted as a bound on a certain parameter defined for all linear spaces of finite dimension. In this note, we define another parameter that can be used to prove lower bounds on circuits with linear gates. Our parameter may be larger than Friedman’s, and it seems incomparable with rigidity, hence it may be easier to prove a lower bound using this notion. Bibliography: 14 titles. Published in Zapiski Nauchnykh Seminarov POMI, Vol. 316, 2004, pp. 188–204.     

B-矩阵线性互补问题的误差界估计

利用严格对角占优M-矩阵的逆矩阵的无穷大范数的范围,给出了B-矩阵线性互补问题误差界新的估计式.相应数值算例表明了结果的有效性.     

Trigonometric spline and spectral bounds for the solution of linear time-periodic systems

Linear time-periodic systems arise whenever a nonlinear system is linearized about a periodic trajectory. Examples include anisotropic rotor-bearing systems and parametrically excited systems. The structure of the solution to linear time-periodic systems is known due to Floquet’s Theorem. We use this information to derive a new norm which yields two-sided bounds on the solution and in this norm vibrations of the solution are suppressed. The obtained results are a generalization for linear time-invariant systems. Since Floquet’s Theorem is non-constructive, the applicability of the aforementioned results suffers in general from an unknown Floquet normal form. Hence, we discuss trigonometric splines and spectral methods that are both equipped with rigorous bounds on the solution. The methodology differs systematically for the two methods. While in the first method the solution is approximated by trigonometric splines and the upper bound depends on the approximation quality, in the second method the linear time-periodic system is approximated and its solution is represented as an infinite series. Depending on the smoothness of the time-periodic system, we formulate two upper bounds which incorporate the approximation error of the linear time-periodic system and the truncation error of the series representation. Rigorous bounds on the solution are necessary whenever reliable results are needed, and hence they can support the analysis and, e.g., stability or robustness of the solution may be proven or falsified. The theoretical results are illustrated and compared to trigonometric spline bounds and spectral bounds by means of three examples that include an anisotropic rotor-bearing system and a parametrically excited Cantilever beam.     

New error bounds for the linear complementarity problem of <Emphasis Type="Italic">QN</Emphasis>-matrices

An error bound for the linear complementarity problem (LCP) when the involved matrices are QN-matrices with positive diagonal entries is presented by Dai et al. (Error bounds for the linear complementarity problem of QN-matrices. Calcolo, 53:647-657, 2016), and there are some limitations to this bound because it involves a parameter. In this paper, for LCP with the involved matrix A being a QN-matrix with positive diagonal entries an alternative bound which depends only on the entries of A is given. Numerical examples are given to show that the new bound is better than that provided by Dai et al. in some cases.     

Tikhonov solutions of approximately given systems of linear algebraic equations under finite perturbations of their matrices

The properties of a mathematical programming problem that arises in finding a stable (in the sense of Tikhonov) solution to a system of linear algebraic equations with an approximately given augmented coefficient matrix are examined. Conditions are obtained that determine whether this problem can be reduced to the minimization of a smoothing functional or to the minimal matrix correction of the underlying system of linear algebraic equations. A method for constructing (exact or approximately given) model systems of linear algebraic equations with known Tikhonov solutions is described. Sharp lower bounds are derived for the maximal error in the solution of an approximately given system of linear algebraic equations under finite perturbations of its coefficient matrix. Numerical examples are given.     

Slopes,Error Bounds and Weak Sharp Pareto Minima of a Vector-Valued Map

In this paper, we provide a detailed study of the upper and lower slopes of a vector-valued map recently introduced by Bednarczuk and Kruger. We show that these slopes enjoy most properties of the strong slope of a scalar-valued function and can be explicitly computed or estimated in the convex, strictly differentiable, linear cases. As applications, we obtain error bounds for lower level sets (in particular, a Hoffman-type error bound for a system of linear inequalities in the infinite-dimensional space setting, existence of weak sharp Pareto minima) and sufficient conditions for Pareto minima.     

New error bounds for the linear complementarity problem with an SB-matrix

Error bounds for SB-matrices linear complementarity problems are given in the paper (Dai et al., Numer Algorithms 61:121–139, 2012). In this paper, new error bounds for the linear complementarity problem when the matrix involved is an SB-matrix are presented and some sufficient conditions that new bounds are sharper than those of the previous paper under certain assumptions are provided. New perturbation bounds of SB-matrices linear complementarity problems are also considered.     

Error Bounds of Constrained Quadratic Functions and Piecewise Affine Inequality Systems

We consider the error bounds for a piecewise affine inequality system and present a necessary and sufficient condition for this system to have an error bound, which generalizes the Hoffman result. Moreover, we study the error bounds of the system determined by a quadratic function and an abstract constraint.     

Super-fast validated solution of linear systems

Validated solution of a problem means to compute error bounds for a solution in finite precision. This includes the proof of existence of a solution. The computed error bounds are to be correct including all possible effects of rounding errors. The fastest known validation algorithm for the solution of a system of linear equations requires twice the computing time of a standard (purely) numerical algorithm. In this paper we present a super-fast validation algorithm for linear systems with symmetric positive definite matrix. This means that the entire computing time for the validation algorithm including computation of an approximated solution is the same as for a standard numerical algorithm. Numerical results are presented.     

Linear programming for the 0–1 quadratic knapsack problem

In this paper we consider the quadratic knapsack problem which consists in maximizing a positive quadratic pseudo-Boolean function subject to a linear capacity constraint. We propose a new method for computing an upper bound. This method is based on the solution of a continuous linear program constructed by adding to a classical linearization of the problem some constraints rebundant in 0–1 variables but nonredundant in continuous variables. The obtained upper bound is better than the bounds given by other known methods. We also propose an algorithm for computing a good feasible solution. This algorithm is an elaboration of the heuristic methods proposed by Chaillou, Hansen and Mahieu and by Gallo, Hammer and Simeone. The relative error between this feasible solution and the optimum solution is generally less than 1%. We show how these upper and lower bounds can be efficiently used to determine the values of some variables at the optimum. Finally we propose a branch-and-bound algorithm for solving the quadratic knapsack problem and report extensive computational tests.