| Title:
|
Convergence acceleration of shifted $LR$ transformations for totally nonnegative Hessenberg matrices (English) |
| Author:
|
Fukuda, Akiko |
| Author:
|
Yamamoto, Yusaku |
| Author:
|
Iwasaki, Masashi |
| Author:
|
Ishiwata, Emiko |
| Author:
|
Nakamura, Yoshimasa |
| Language:
|
English |
| Journal:
|
Applications of Mathematics |
| ISSN:
|
0862-7940 (print) |
| ISSN:
|
1572-9109 (online) |
| Volume:
|
65 |
| Issue:
|
5 |
| Year:
|
2020 |
| Pages:
|
677-702 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
We design shifted $LR$ transformations based on the integrable discrete hungry Toda equation to compute eigenvalues of totally nonnegative matrices of the banded Hessenberg form. The shifted $LR$ transformation can be regarded as an extension of the extension employed in the well-known dqds algorithm for the symmetric tridiagonal eigenvalue problem. In this paper, we propose a new and effective shift strategy for the sequence of shifted $LR$ transformations by considering the concept of the Newton shift. We show that the shifted $LR$ transformations with the resulting shift strategy converge with order $2-\epsilon $ for arbitrary $\epsilon >0$. (English) |
| Keyword:
|
$LR$ transformation |
| Keyword:
|
totally nonnegative matrix |
| Keyword:
|
Newton shift |
| Keyword:
|
convergence rate |
| MSC:
|
34B16 |
| MSC:
|
34C25 |
| idZBL:
|
07285952 |
| idMR:
|
MR4160788 |
| DOI:
|
10.21136/AM.2020.0378-19 |
| . |
| Date available:
|
2020-09-23T13:51:18Z |
| Last updated:
|
2022-11-07 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/148372 |
| . |
| Reference:
|
[1] Bauer, F. L.: qd-method with Newton shift.Technical Report 56. Computer Science Department, Stanford University, Stanford (1967). |
| Reference:
|
[2] 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:
|
[3] Fukuda, A., Ishiwata, E., Yamamoto, Y., Iwasaki, M., Nakamura, Y.: Integrable discrete hungry systems and their related matrix eigenvalues.Ann. Mat. Pura Appl. 192 (2013), 423-445. Zbl 1349.37064, MR 3061107, 10.1007/s10231-011-0231-0 |
| Reference:
|
[4] Fukuda, A., Yamamoto, Y., Iwasaki, M., Ishiwata, E., Nakamura, Y.: Error analysis for matrix eigenvalue algorithm based on the discrete hungry Toda equation.Numer. Algorithms 61 (2012), 243-260. Zbl 1257.65019, MR 2969294, 10.1007/s11075-012-9606-6 |
| Reference:
|
[5] Fukuda, A., Yamamoto, Y., Iwasaki, M., Ishiwata, E., Nakamura, Y.: On a shifted $LR$ transformation derived from the discrete hungry Toda equation.Monatsh. Math. 170 (2013), 11-26. Zbl 1311.65036, MR 3032671, 10.1007/s00605-012-0404-y |
| Reference:
|
[6] Golub, G. H., Loan, C. F. Van: Matrix Computations.Johns Hopkins Studies in the Mathematical Sciences. The Johns Hopkins University Press, Baltimore (2013). Zbl 1268.65037, MR 3024913 |
| Reference:
|
[7] Horn, R. A., Johnson, C. R.: Matrix Analysis.Cambridge University Press, Cambridge (1985). Zbl 0576.15001, MR 0832183, 10.1017/CBO9780511810817 |
| Reference:
|
[8] Team, LAPACK: LAPACK: Linear Algebra PACKage.Available at http://www.netlib.org/lapack/. |
| Reference:
|
[9] Li, C.-K., Mathias, R.: Interlacing inequalities for totally nonnegative matrices.Linear Algebra Appl. 341 (2002), 35-44. Zbl 0997.15014, MR 1873607, 10.1016/S0024-3795(01)00240-3 |
| Reference:
|
[10] Parlett, B. N.: The new qd algorithms.Acta Numerica 4 (1995), 459-491. Zbl 0835.65059, MR 1352476, 10.1017/S0962492900002580 |
| Reference:
|
[11] Pinkus, A.: Totally Positive Matrices.Cambridge Tracts in Mathematics 181. Cambridge University Press, Cambridge (2009). Zbl 1185.15028, MR 2584277, 10.1017/CBO9780511691713 |
| Reference:
|
[12] Reinsch, C., Bauer, F. L.: Rational QR transformation with Newton shift for symmetric tridiagonal matrices.Numer. Math. 11 (1968), 264-272. Zbl 0164.45201, MR 1553960, 10.1007/BF02161847 |
| Reference:
|
[13] Rutishauser, H.: Lectures on Numerical Mathematics.Birkhäuser, Boston (1990). Zbl 0699.65002, MR 1102678, 10.1007/978-1-4612-3468-5 |
| Reference:
|
[14] Sun, J.-Q., Hu, X.-B., Tam, H.-W.: Short note: An integrable numerical algorithm for computing eigenvalues of a specially structured matrix.Numer. Linear Algebra Appl. 18 (2011), 261-274. Zbl 1249.65079, MR 2791246, 10.1002/nla.754 |
| Reference:
|
[15] Tokihiro, T., Nagai, A., Satsuma, J.: Proof of solitonical nature of box and ball systems by means of inverse ultra-discretization.Inverse Probl. 15 (1999), 1639-1662. Zbl 1138.37341, MR 1733220, 10.1088/0266-5611/15/6/314 |
| . |
