Error analysis for matrix eigenvalue algorithm based on the discrete hungry Toda equation

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...

Full description

Saved in:
Bibliographic Details
Published in:Numerical algorithms 2012-10, Vol.61 (2), p.243-260
Main Authors: Fukuda, Akiko, Yamamoto, Yusaku, Iwasaki, Masashi, Ishiwata, Emiko, Nakamura, Yoshimasa
Format: Article
Language:English
Subjects:
Algebra
Algorithms
Computation
Computer Science
Eigenvalues
Error analysis
Floating point arithmetic
Numeric Computing
Numerical Analysis
Numerical stability
Original Paper
Stability analysis
Theory of Computation
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1017-1398
1572-9265
DOI:10.1007/s11075-012-9606-6