Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Keywords:
$LR$ transformation; totally nonnegative matrix; Newton shift; convergence rate
$LR$ transformation; totally nonnegative matrix; Newton shift; convergence rate
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$.
References:
[1] Bauer, F. L.: qd-method with Newton shift. Technical Report 56. Computer Science Department, Stanford University, Stanford (1967).
[2] Fernando, K. V., Parlett, B. N.: Accurate singular values and differential qd algorithms. Numer. Math. 67 (1994), 191-229. DOI 10.1007/s002110050024 | MR 1262781 | Zbl 0814.65036
[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. DOI 10.1007/s10231-011-0231-0 | MR 3061107 | Zbl 1349.37064
[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. DOI 10.1007/s11075-012-9606-6 | MR 2969294 | Zbl 1257.65019
[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. DOI 10.1007/s00605-012-0404-y | MR 3032671 | Zbl 1311.65036
[6] Golub, G. H., Loan, C. F. Van: Matrix Computations. Johns Hopkins Studies in the Mathematical Sciences. The Johns Hopkins University Press, Baltimore (2013). MR 3024913 | Zbl 1268.65037
[7] Horn, R. A., Johnson, C. R.: Matrix Analysis. Cambridge University Press, Cambridge (1985). DOI 10.1017/CBO9780511810817 | MR 0832183 | Zbl 0576.15001
[8] Team, LAPACK: LAPACK: Linear Algebra PACKage. Available at http://www.netlib.org/lapack/
[9] Li, C.-K., Mathias, R.: Interlacing inequalities for totally nonnegative matrices. Linear Algebra Appl. 341 (2002), 35-44. DOI 10.1016/S0024-3795(01)00240-3 | MR 1873607 | Zbl 0997.15014
[10] Parlett, B. N.: The new qd algorithms. Acta Numerica 4 (1995), 459-491. DOI 10.1017/S0962492900002580 | MR 1352476 | Zbl 0835.65059
[11] Pinkus, A.: Totally Positive Matrices. Cambridge Tracts in Mathematics 181. Cambridge University Press, Cambridge (2009). DOI 10.1017/CBO9780511691713 | MR 2584277 | Zbl 1185.15028
[12] Reinsch, C., Bauer, F. L.: Rational QR transformation with Newton shift for symmetric tridiagonal matrices. Numer. Math. 11 (1968), 264-272. DOI 10.1007/BF02161847 | MR 1553960 | Zbl 0164.45201
[13] Rutishauser, H.: Lectures on Numerical Mathematics. Birkhäuser, Boston (1990). DOI 10.1007/978-1-4612-3468-5 | MR 1102678 | Zbl 0699.65002
[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. DOI 10.1002/nla.754 | MR 2791246 | Zbl 1249.65079
[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. DOI 10.1088/0266-5611/15/6/314 | MR 1733220 | Zbl 1138.37341
Search
Partner of
