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

Applications of Mathematics (2017)

- Volume: 62, Issue: 4, page 319-331
- ISSN: 0862-7940

## Access Full Article

top## Abstract

top## How to cite

topYamamoto, 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 -

## References

top- Aishima, K., Matsuo, T., Murota, K., Sugihara, M., A survey on convergence theorems of the dqds algorithm for computing singular values, J. Math-for-Ind. 2 (2010), 1-11. (2010) Zbl1210.65088MR2639360
- Alefeld, G., 10.2307/2321760, Am. Math. Monthly 88 (1981), 530-536. (1981) Zbl0486.65035MR0628022DOI10.2307/2321760
- Fernando, K. V., Parlett, B. N., 10.1007/s002110050024, Numer. Math. 67 (1994), 191-229. (1994) Zbl0814.65036MR1262781DOI10.1007/s002110050024
- Golub, G. H., Loan, C. F. Van, Matrix Computations, Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore (2013). (2013) Zbl1268.65037MR3024913
- Householder, A. S., The Numerical Treatment of a Single Nonlinear Equation, International Series in Pure and Applied Mathematics, McGraw-Hill Book, New York (1970). (1970) Zbl0242.65047MR0388759
- Iwasaki, M., Nakamura, Y., 10.1007/BF03167593, Japan J. Ind. Appl. Math. 23 (2006), 239-259. (2006) Zbl1117.65055MR2281507DOI10.1007/BF03167593
- Johnson, C. R., 10.1016/0024-3795(89)90583-1, Linear Algebra Appl. 112 (1989), 1-7. (1989) Zbl0723.15013MR0976325DOI10.1016/0024-3795(89)90583-1
- Johnson, C. R., Szulc, T., 10.1016/S0024-3795(97)00330-3, Linear Algebra Appl. 272 (1998), 169-179. (1998) Zbl0891.15013MR1489385DOI10.1016/S0024-3795(97)00330-3
- Kimura, K., Yamashita, T., Nakamura, Y., 10.1088/1751-8113/44/28/285207, J. Phys. A, Math. Theor. 44 (2011), Article ID 285207, 12 pages. (2011) Zbl1223.37068MR2812341DOI10.1088/1751-8113/44/28/285207
- Matt, U. von, 10.1137/S1064827594274887, SIAM J. Sci. Comput. 18 (1997), 1163-1186. (1997) Zbl0895.65014MR1453563DOI10.1137/S1064827594274887
- Yamashita, T., Kimura, K., Nakamura, Y., Subtraction-free recurrence relations for lower bounds of the minimal singular value of an upper bidiagonal matrix, J. Math-for-Ind. 4 (2012), 55-71. (2012) Zbl1302.15012MR2912032
- Yamashita, T., Kimura, K., Takata, M., Nakamura, Y., 10.14495/jsiaml.5.21, JSIAM Lett. 5 (2013), 21-24. (2013) MR3035546DOI10.14495/jsiaml.5.21
- Yamashita, T., Kimura, K., Yamamoto, Y., 10.1007/s11075-014-9931-z, Numer. Algorithms 69 (2015), 893-912. (2015) Zbl1329.65079MR3374105DOI10.1007/s11075-014-9931-z
- Wilkinson, J. H., The Algebraic Eigenvalue Problem, Monographs on Numerical Analysis, Oxford Science Publications, Clarendon Press, Oxford (1988). (1988) Zbl0626.65029MR0950175

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.