On the optimality and sharpness of Laguerre's lower bound on the smallest eigenvalue of a symmetric positive definite matrix

Yamamoto, Yusaku. "On the optimality and sharpness of Laguerre's lower bound on the smallest eigenvalue of a symmetric positive definite matrix." Applications of Mathematics 62.4 (2017): 319-331. <http://eudml.org/doc/294090>.

@article{Yamamoto2017,
abstract = {Lower bounds on the smallest eigenvalue of a symmetric positive definite matrix $A\in \mathbb \{R\}^\{m\times m\}$ play an important role in condition number estimation and in iterative methods for singular value computation. In particular, the bounds based on $\{\rm Tr\}(A^\{-1\})$ and $\{\rm Tr\}(A^\{-2\})$ have attracted attention recently, because they can be computed in $O(m)$ operations when $A$ is tridiagonal. In this paper, we focus on these bounds and investigate their properties in detail. First, we consider the problem of finding the optimal bound that can be computed solely from $\{\rm Tr\}(A^\{-1\})$ and $\{\rm Tr\}(A^\{-2\})$ and show that the so called Laguerre’s lower bound is the optimal one in terms of sharpness. Next, we study the gap between the Laguerre bound and the smallest eigenvalue. We characterize the situation in which the gap becomes largest in terms of the eigenvalue distribution of $A$ and show that the gap becomes smallest when $\lbrace \{\rm Tr\}(A^\{-1\})\rbrace ^2/\{\rm Tr\}(A^\{-2\})$ approaches 1 or $m$. These results will be useful, for example, in designing efficient shift strategies for singular value computation algorithms.},
author = {Yamamoto, Yusaku},
journal = {Applications of Mathematics},
keywords = {eigenvalue bound; symmetric positive definite matrix; Laguerre bound; singular value computation; dqds algorithm},
language = {eng},
number = {4},
pages = {319-331},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {On the optimality and sharpness of Laguerre's lower bound on the smallest eigenvalue of a symmetric positive definite matrix},
url = {http://eudml.org/doc/294090},
volume = {62},
year = {2017},
}

TY - JOUR
AU - Yamamoto, Yusaku
TI - On the optimality and sharpness of Laguerre's lower bound on the smallest eigenvalue of a symmetric positive definite matrix
JO - Applications of Mathematics
PY - 2017
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 62
IS - 4
SP - 319
EP - 331
AB - Lower bounds on the smallest eigenvalue of a symmetric positive definite matrix $A\in \mathbb {R}^{m\times m}$ play an important role in condition number estimation and in iterative methods for singular value computation. In particular, the bounds based on ${\rm Tr}(A^{-1})$ and ${\rm Tr}(A^{-2})$ have attracted attention recently, because they can be computed in $O(m)$ operations when $A$ is tridiagonal. In this paper, we focus on these bounds and investigate their properties in detail. First, we consider the problem of finding the optimal bound that can be computed solely from ${\rm Tr}(A^{-1})$ and ${\rm Tr}(A^{-2})$ and show that the so called Laguerre’s lower bound is the optimal one in terms of sharpness. Next, we study the gap between the Laguerre bound and the smallest eigenvalue. We characterize the situation in which the gap becomes largest in terms of the eigenvalue distribution of $A$ and show that the gap becomes smallest when $\lbrace {\rm Tr}(A^{-1})\rbrace ^2/{\rm Tr}(A^{-2})$ approaches 1 or $m$. These results will be useful, for example, in designing efficient shift strategies for singular value computation algorithms.
LA - eng
KW - eigenvalue bound; symmetric positive definite matrix; Laguerre bound; singular value computation; dqds algorithm
UR - http://eudml.org/doc/294090
ER -