Pertubation bounds for the definite generalized eigenvalue problem

Let A and B be Hermitian matrices, and let c(A, B) = inf{|x^H(A + iB)x|:6 = 1}. The eigenvalue problem Ax = λBx is called definite if c(A, B)>0. It is shown that a definite problem has a complete system of eigenvectors and that its eigenvalues are real. Under pertubations of A and B, the eigenvalues behave like the eigenvalues of a Hermitian matrix in the sense that there is a 1-1 pairing of the eigenvalues with the perturbed eigenvalues and a uniform bound for their differences (in this case in the chordal metric). Pertubation bounds are also developed for eigenvectors and eigenspaces.     

Finite element interpolation error bounds with applications to eigenvalue problems

Optimal finite element interpolation eror bounds are presented for piecewise linear, quadratic and Hermite-cubic elements in one dimenson. These bounds can be used to compute upper and lower bounds for eigenvalues of second and fourth order elliptic problems. Numerical computations demonstrate the usefulness of the theoretical results.

---

Zusammenfassung Es werden optimale Fehlerschranken für die eindimensionale finite Element-Interpolation mit stückweise linearen, quadratischen und Hermite-kubischen Elementen angegeben. Diese Schranken können dazu verwendet werden, unter und obere Schranken für Eigenwerte von elliptischen Problemen 2. und 4. Ordnung zu berechnen. Dazu werden numerische Resultate angeführt, welche die Nützlichkeit der theoretischen Resultate zeigen.

     

Residual algorithm for large-scale positive definite generalized eigenvalue problems

In the positive definite case, the extreme generalized eigenvalues can be obtained by solving a suitable nonlinear system of equations. In this work, we adapt and study the use of recently developed low-cost derivative-free residual schemes for nonlinear systems, to solve large-scale generalized eigenvalue problems. We demonstrate the effectiveness of our approach on some standard test problems, and also on a problem associated with the vibration analysis of large structures. In our numerical results we use preconditioning strategies based on incomplete factorizations, and we compare with and without preconditioning with a well-known available package.     

Realistic error bounds for a simple eigenvalue and its associated eigenvector

Summary An algorithm is described which, given an approximate simple eigenvalue and a corresponding approximate eigenvector, provides rigorous error bounds for improved versions of them. No information is required on the rest of the eigenvalues, which may indeed correspond to non-linear elementary divisors. A second algorithm is described which gives more accurate improved versions than the first but provides only error estimates rather than rigorous bounds. Both algorithms extend immediately to the generalized eigenvalue problem.Dedicated to A.S. Householder on his 75th birthday     

Merit functions and error bounds for generalized variational inequalities

We consider the generalized variational inequality and construct certain merit functions associated with this problem. In particular, those merit functions are everywhere nonnegative and their zero-sets are precisely solutions of the variational inequality. We further use those functions to obtain error bounds, i.e., upper estimates for the distance to solutions of the problem.     

Improving eigenvalue bounds using extra bounds

Bounds for various functions of the eigenvalues of a Hermitian matrix A, based on the traces of A and A², are improved. A technique is presented whereby these bounds can be improved by combining them with other bounds. In particular, the diagonal of A, in conjunction with majorization, is used to improve the bounds. These bounds all require O(n²) multiplications.     

Using error bounds to compare aggregated generalized transportation models

A comparative study of aggregation error bounds for the generalized transportation problem is presented. A priori and a posteriori error bounds were derived and a computational study was performed to (a) test the correlation between the a priori, the a posteriori, and the actual error and (b) quantify the difference of the error bounds from the actual error. Based on the results we conclude that calculating the a priori error bound can be considered as a useful strategy to select the appropriate aggregation level. The a posteriori error bound provides a good quantitative measure of the actual error.     

Gap functions and error bounds for generalized vector variational inequalities

This paper deals with generalized vector variational inequalities. Without any scalarization approach, the gap functions and their regularized versions for generalized vector variational inequalities are first obtained. Then, in the absence of the projection operator method, some error bounds for generalized vector variational inequalities are established in terms of these regularized gap functions. Further, the results obtained in this paper are more simpler from the computational view.     

On error bounds and Newton-type methods for generalized Nash equilibrium problems

Error bounds (estimates for the distance to the solution set of a given problem) are key to analyzing convergence rates of computational methods for solving the problem in question, or sometimes even to justifying convergence itself. That said, for the generalized Nash equilibrium problems (GNEP), the theory of error bounds had not been developed in depth comparable to the fields of optimization and variational problems. In this paper, we provide a systematic approach which should be useful for verifying error bounds for both specific instances of GNEPs and for classes of GNEPs. These error bounds for GNEPs are based on more general results for constraints that involve complementarity relations and cover those (few) GNEP error bounds that existed previously, and go beyond. In addition, they readily imply a Lipschitzian stability result for solutions of GNEPs, a subject where again very little had been known. As a specific application of error bounds, we discuss Newtonian methods for solving GNEPs. While we do not propose any significantly new methods in this respect, some new insights into applicability to GNEPs of various approaches and into their convergence properties are presented.     

Lower bounds for generalized eigenvalues of the quasilinear systems

In this paper, we establish several new Lyapunov-type inequalities for two classes of one-dimensional quasilinear elliptic systems of resonant type, which generalize or improve all related existing ones. Then we use the Lyapunov-type inequalities obtained in this paper to derive a better lower bound for the generalized eigenvalues of the one-dimensional quasilinear elliptic system with the Dirichlet boundary conditions.     

Explicit bounds of the first eigenvalue

It is proved that the general formulas, obtained recently for the lower bound of the first eigenvalue, can be further bounded by one or two constants depending on the coefficients of the corresponding operators only. Moreover, the ratio of the upper and lower bounds is no more than four.     

Condition numbers of rectangular systems and bounds for generalized inverses

A natural extension of the notion of condition number of a matrix to the class of all finite matrices is shown to enjoy properties similar to the classical condition number. For example, the relative distance to the set of all matrices of smaller rank is just the reciprocal of this generalized condition number. The question of whether a matrix with a small generalized condition number must also have a generalized inverse of small norm is then studied. The answer turns out to be norm dependent. In particular, only if p is 1 or 2 must an intrinsically well-conditioned full rank matrix in the l_p sense have a nicely bounded generalized inverse; in particular, in the l_∞ norm this need not be true. These facts are consequences of recent results in Banach space theory.     

Verified error bounds for multiple roots of systems of nonlinear equations

It is well known that it is an ill-posed problem to decide whether a function has a multiple root. Even for a univariate polynomial an arbitrary small perturbation of a polynomial coefficient may change the answer from yes to no. Let a system of nonlinear equations be given. In this paper we describe an algorithm for computing verified and narrow error bounds with the property that a slightly perturbed system is proved to have a double root within the computed bounds. For a univariate nonlinear function f we give a similar method also for a multiple root. A narrow error bound for the perturbation is computed as well. Computational results for systems with up to 1000 unknowns demonstrate the performance of the methods.     

Perturbation of error bounds

Mathematical Programming - Our aim in the current article is to extend the developments in Kruger et al. (SIAM J Optim 20(6):3280–3296, 2010. doi: 10.1137/100782206 ) and, more precisely, to...     

Perturbation analysis of global error bounds for systems of linear inequalities

This paper studies the existence of a uniform global error bound when a system of linear inequalities is under local arbitrary perturbations. Specifically, given a possibly infinite system of linear inequalities satisfying the Slater’s condition and a certain compactness condition, it is shown that for sufficiently small arbitrary perturbations the perturbed system is solvable and there exists a uniform global error bound if and only if the original system is bounded or its homogeneous system has a strict solution. Received: April 12, 1998 / Accepted: February 11, 2000?Published online July 20, 2000     

Upper eigenvalue bounds for pencils of matrices

Eigenvalue bounds are obtained for pencils of matrices A ? vB where A is a Stieltjes matrix and B is positive definite, under assumptions suitable for the estimation of asymptotic convergence rates of factorization iterative methods, where B represents the approximate factorization of A. The upper bounds obtained depend on the “connectivity” structure of the matrices involved, which enters through matrix graph considerations; in addition, a more classical argument is used to obtain a lower bound. Potential applications of these results include a partial confirmation of Gustafsson's conjecture concerning the nonnecessity of Axelsson's perturbations.     

Lower eigenvalue bounds for pencils of matrices

A procedure is set up for obtaining lower eigenvalue bounds for pencils of matrices A—vB where A is a Stieltjes matrix and B is positive definite, under assumptions suitable for the estimation of asymptotic convergence rates of locally perturbed factorization iterative schemes. Using these results and a formerly developed approach for estimating upper bounds, we widely confirm Gustafsson's conjecture concerning the nonnecessity of Axelsson's perturbations. In so doing, we however keep local perturbations, thereby enlarging the number of applications where their sufficiency is proven; their necessity remains, on the other hand, an open question.     

Numerical enclosure for each eigenvalue in generalized eigenvalue problem

An algorithm for enclosing all eigenvalues in generalized eigenvalue problem Ax=λBx is proposed. This algorithm is applicable even if A∈C^n×n is not Hermitian and/or B∈C^n×n is not Hermitian positive definite, and supplies nerror bounds while the algorithm previously developed by the author supplies a single error bound. It is proved that the error bounds obtained by the proposed algorithm are equal or smaller than that by the previous algorithm. Computational cost for the proposed algorithm is similar to that for the previous algorithm. Numerical results show the property of the proposed algorithm.     

Error bounds for non-selfadjoint PDE eigenvalue problems

We introduce a posteriori bounds for the eigenfunctions (eigenvalues) of non-selfadjoint diagonalizable PDE-eigenvalue problems which incorporates an inexact solution of the corresponding generalized matrix eigenvalue problem. The estimates combine the standard perturbation results with the saturation assumption for the eigenfunctions. (© 2010 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)