Abstract
Based on the integrable discrete hungry Toda (dhToda) equation, the authors designed an algorithm for computing eigenvalues of a class of totally nonnegative matrices (Ann Mat Pura Appl, doi:10.1007/s10231-011-0231-0). This is named the dhToda algorithm, and can be regarded as an extension of the well-known qd algorithm. The shifted dhToda algorithm has been also designed by introducing the origin shift in order to accelerate the convergence. In this paper, we first propose the differential form of the shifted dhToda algorithm, by referring to that of the qds (dqds) algorithm. The number of subtractions is then reduced and the effect of cancellation in floating point arithmetic is minimized. Next, from the viewpoint of mixed error analysis, we investigate numerical stability of the proposed algorithm in floating point arithmetic. Based on this result, we give a relative perturbation bound for eigenvalues computed by the new algorithm. Thus it is verified that the eigenvalues computed by the proposed algorithm have high relative accuracy. Numerical examples agree with our error analysis for the algorithm.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Gasca, M., Micchelli, C.A. (eds.): Total Positivity and Its Applications, Math. Appl., vol. 359. Kluwer Academic, Dordrecht (1996)
Golub, G.H., Van Loan, C.F.: Matrix Computations, 3rd edn. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, Baltimore (1996)
Fernando, K.V., Parlett, B.N.: Accurate singular values and differential qd algorithms. Numer. Math. 25, 191–229 (1994)
Fukuda, A., Ishiwata, E., Iwasaki, M., Yamamoto, Y., Nakamura, Y.: Integrable discrete hungry systems and their related matrix eigenvalues. Ann. Mat. Pura Appl. (2012). doi:10.1007/s10231-011-0231-0
Fukuda, A., Yamamoto, Y., Iwasaki, M., Ishiwata, E., Nakamura, Y.: On a shifted LR transformation derived from the discrete hungry Toda equation. Monat. Math. (2012). doi:10.1007/s00605-012-0404-y
Higham, N.J.: Accuracy and Stability of Numerical Algorithms. SIAM, Philadelphia (1996)
Koev, P.: Accurate eigenvalues and SVDs of totally nonnegative matrices. SIAM J. Matrix Anal. Appl. 27, 1–23 (2005)
Parlett, B.N.: The new qd algorithms. Acta Numer. 4, 459–491 (1995)
Pinkus, A.: Totally Positive Matrices. Cambridge University Press, New York (2009)
Rutishauser, H.: Ein infinitesimales Analogon zum Quotienten-Differenzen-Algorithmus. Arch. Math. 5, 132–137 (1954) (in German)
Rutishauser, H.: Lectures on Numerical Mathematics. Birkhäuser, Boston (1990)
Tokihiro, T., Nagai, A., Satsuma, J.: Proof of solitonical nature of box and ball systems by means of inverse ultra-discretization. Inverse Probl. 15, 1639–1662 (1999)
Author information
Authors and Affiliations
Corresponding author
Additional information
This was partially supported by Grants-in-Aid for Young Scientists (B) No. 24740110, Scientific Research (A) No. 20246027 and Scientific Research (C) No. 23540163 from the Japan Society for the Promotion of Science, and Core Research for Evolutional Science and Technology (CREST) Program “Highly Productive, High Performance Application Frameworks for Post Petascale Computing” of Japan Science and Technology Agency (JST).
Rights and permissions
About this article
Cite this article
Fukuda, A., Yamamoto, Y., Iwasaki, M. et al. Error analysis for matrix eigenvalue algorithm based on the discrete hungry Toda equation. Numer Algor 61, 243–260 (2012). https://doi.org/10.1007/s11075-012-9606-6
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11075-012-9606-6