- 著者
-
KITAMOTO Takuya
YAMAGUCHI Tetsu
- 出版者
- The Institute of Electronics, Information and Communication Engineers
- 雑誌
- IEICE transactions on fundamentals of electronics, communications and computer sciences (ISSN:09168508)
- 巻号頁・発行日
- vol.91, no.8, pp.2101-2110, 2008-08-01
Let <i>M</i>(<i>y</i>) be a matrix whose entries are polynomial in <i>y</i>, λ(<i>y</i>) and υ(<i>y</i>) be a set of eigenvalue and eigenvector of <i>M</i>(<i>y</i>). Then, λ(<i>y</i>) and υ(<i>y</i>) are algebraic functions of <i>y</i>, and λ(<i>y</i>) and υ(<i>y</i>) have their power, series expansions<br>λ(<i>y</i>)=β<sub>0</sub>+β<sub>1</sub><i>y</i>+…+β<sub><i>k</i></sub><i>y</i><sup><i>k</i></sup>+…(β<sub><i>j</i></sub>∈<b>C</b>), (1)<br>υ(<i>y</i>)=γ<sub>0</sub>+γ<sub>1</sub><i>y</i>+…+γ<sub><i>k</i></sub><i>y<sup>k</sup></i>+…(γ<sub><i>j</i></sub>∈<b>C</b><sup><i>n</i></sup>), (2)<br>provided that <i>y</i>=0 is not a singular point of λ(<i>y</i>) or υ(<i>y</i>). Several algorithms are already proposed to compute the above power series expansions using Newton's method (the algorithm in [4]) or the Hensel construction (the algorithm in [5], [12]). The algorithms proposed so far compute high degree coefficients, β<sub><i>k</i></sub> and γ<sub><i>k</i></sub>, using lower degree coefficien β<sub><i>j</i></sub> and γ<sub><i>j</i></sub>(<i>j</i>=0,1,…,<i>k</i>-1). Thus with floating point arithmetic, the numerical errors in the coefficients can accumulate as index <i>k</i> increases. This can cause serious deterioration of the numerical accuracy of high degree coefficients β<sub><i>k</i></sub> and γ<sub><i>k</i></sub>, and we need to check the accuracy. In this paper, we assume that given matrix <i>M</i>(<i>y</i>) does not have multiple eigenvalues at <i>y</i>=0 (this implies that <i>y</i>=0 is not singular point of γ(<i>y</i>) or υ(<i>y</i>)), and presents an algorithm to estimate the accuracy of the computed power series β<sub><i>i</i></sub>, γ<sub><i>j</i></sub> in (1) and (2). The estimation process employs the idea in [9] which computes a coefficient of a power series with Cauchy's integral formula and numerical integrations. We present an efficient implementation of the algorithm that utilizes Newton's method. We also present a modification of Newton's method to speed up the procedure, introducing tuning parameter <i>p</i>. Numerical experiments of the paper indicates that we can enhance the performance of the algorithm by 12-16%, choosing the optimal tuning parameter <i>p</i>.