Received December 30, 2019. Published online September 7, 2020.
Abstract: 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$.
Keywords: $LR$ transformation; totally nonnegative matrix; Newton shift; convergence rate
Affiliations: Akiko Fukuda, Department of Mathematical Sciences, Shibaura Institute of Technology, 307 Fukasaku, Minuma-ku, Saitama 337-8570, Japan, e-mail: firstname.lastname@example.org; Yusaku Yamamoto, Department of Communication Engineering and Informatics, The University of Electro-Communications, 1-5-1 Chofugaoka, Chofu, Tokyo 182-8585, Japan, e-mail: email@example.com; Masashi Iwasaki, Department of Life and Environmental Sciences, Kyoto Prefectural University, 1-5 Shimogamo Nakaragi-cho, Sakyo-ku, Kyoto 606-8522, Japan, e-mail: firstname.lastname@example.org; Emiko Ishiwata, Department of Applied Mathematics, Tokyo University of Science, 1-3 Kagurazaka, Shinjuku-ku, Tokyo 162-8601, Japan, e-mail: email@example.com; Yoshimasa Nakamura, Graduate School of Informatics, Kyoto University, 36-1 Yoshida-Honmachi, Sakyo-ku, Kyoto 606-8501, Japan, e-mail: firstname.lastname@example.org