| Title:
|
On the optimality and sharpness of Laguerre's lower bound on the smallest eigenvalue of a symmetric positive definite matrix (English) |
| Author:
|
Yamamoto, Yusaku |
| Language:
|
English |
| Journal:
|
Applications of Mathematics |
| ISSN:
|
0862-7940 (print) |
| ISSN:
|
1572-9109 (online) |
| Volume:
|
62 |
| Issue:
|
4 |
| Year:
|
2017 |
| Pages:
|
319-331 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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 $\{{\rm Tr}(A^{-1})\}^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. (English) |
| Keyword:
|
eigenvalue bound |
| Keyword:
|
symmetric positive definite matrix |
| Keyword:
|
Laguerre bound |
| Keyword:
|
singular value computation |
| Keyword:
|
dqds algorithm |
| MSC:
|
15A18 |
| MSC:
|
15A42 |
| idZBL:
|
Zbl 06770047 |
| idMR:
|
MR3686420 |
| DOI:
|
10.21136/AM.2017.0022-17 |
| . |
| Date available:
|
2017-08-31T12:43:58Z |
| Last updated:
|
2020-07-02 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/146832 |
| . |
| Reference:
|
[1] 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. Zbl 1210.65088, MR 2639360 |
| Reference:
|
[2] Alefeld, G.: On the convergence of Halley's method.Am. Math. Monthly 88 (1981), 530-536. Zbl 0486.65035, MR 0628022, 10.2307/2321760 |
| Reference:
|
[3] Fernando, K. V., Parlett, B. N.: Accurate singular values and differential qd algorithms.Numer. Math. 67 (1994), 191-229. Zbl 0814.65036, MR 1262781, 10.1007/s002110050024 |
| Reference:
|
[4] Golub, G. H., Loan, C. F. Van: Matrix Computations.Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore (2013). Zbl 1268.65037, MR 3024913 |
| Reference:
|
[5] Householder, A. S.: The Numerical Treatment of a Single Nonlinear Equation.International Series in Pure and Applied Mathematics, McGraw-Hill Book, New York (1970). Zbl 0242.65047, MR 0388759 |
| Reference:
|
[6] Iwasaki, M., Nakamura, Y.: Accurate computation of singular values in terms of shifted integrable schemes.Japan J. Ind. Appl. Math. 23 (2006), 239-259. Zbl 1117.65055, MR 2281507, 10.1007/BF03167593 |
| Reference:
|
[7] Johnson, C. R.: A Gersgorin-type lower bound for the smallest singular value.Linear Algebra Appl. 112 (1989), 1-7. Zbl 0723.15013, MR 0976325, 10.1016/0024-3795(89)90583-1 |
| Reference:
|
[8] Johnson, C. R., Szulc, T.: Further lower bounds for the smallest singular value.Linear Algebra Appl. 272 (1998), 169-179. Zbl 0891.15013, MR 1489385, 10.1016/S0024-3795(97)00330-3 |
| Reference:
|
[9] Kimura, K., Yamashita, T., Nakamura, Y.: Conserved quantities of the discrete finite Toda equation and lower bounds of the minimal singular value of upper bidiagonal matrices.J. Phys. A, Math. Theor. 44 (2011), Article ID 285207, 12 pages. Zbl 1223.37068, MR 2812341, 10.1088/1751-8113/44/28/285207 |
| Reference:
|
[10] Matt, U. von: The orthogonal qd-algorithm.SIAM J. Sci. Comput. 18 (1997), 1163-1186. Zbl 0895.65014, MR 1453563, 10.1137/S1064827594274887 |
| Reference:
|
[11] 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. Zbl 1302.15012, MR 2912032 |
| Reference:
|
[12] Yamashita, T., Kimura, K., Takata, M., Nakamura, Y.: An application of the Kato-Temple inequality on matrix eigenvalues to the dqds algorithm for singular values.JSIAM Lett. 5 (2013), 21-24. MR 3035546, 10.14495/jsiaml.5.21 |
| Reference:
|
[13] Yamashita, T., Kimura, K., Yamamoto, Y.: A new subtraction-free formula for lower bounds of the minimal singular value of an upper bidiagonal matrix.Numer. Algorithms 69 (2015), 893-912. Zbl 1329.65079, MR 3374105, 10.1007/s11075-014-9931-z |
| Reference:
|
[14] Wilkinson, J. H.: The Algebraic Eigenvalue Problem.Monographs on Numerical Analysis, Oxford Science Publications, Clarendon Press, Oxford (1988). Zbl 0626.65029, MR 0950175 |
| . |
