On the Check of Accuracy of the Coefficients of Formal Power Series

Takuya KITAMOTO; Tetsu YAMAGUCHI

doi:10.1093/ietfec/e91-a.8.2101

On the Check of Accuracy of the Coefficients of Formal Power Series

Takuya KITAMOTO, Tetsu YAMAGUCHI

Full Text Views

0

Cite this

Summary :

Let M(y) be a matrix whose entries are polynomial in y, λ(y) and v(y) be a set of eigenvalue and eigenvector of M(y). Then, λ(y) and v(y) are algebraic functions of y, and λ(y) and v(y) have their power series expansions
λ(y) = β₀ + β₁ y + + β_k y^k + (β_j C),(1)
v(y) = γ₀ + γ₁ y + + γ_k y^k + (γ_j Cⁿ), (2)
provided that y=0 is not a singular point of λ(y) or v(y). 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 β_k and γ_k, using lower degree coefficients β_j and γ_j (j=0,1,,k-1). Thus with floating point arithmetic, the numerical errors in the coefficients can accumulate as index k increases. This can cause serious deterioration of the numerical accuracy of high degree coefficients β_k and γ_k, and we need to check the accuracy. In this paper, we assume that given matrix M(y) does not have multiple eigenvalues at y=0 (this implies that y=0 is not singular point of λ(y) or v(y)), and presents an algorithm to estimate the accuracy of the computed power series β_i,γ_j 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 p. Numerical experiments of the paper indicates that we can enhance the performance of the algorithm by 1216%, choosing the optimal tuning parameter p.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E91-A No.8 pp.2101-2110

Publication Date: 2008/08/01

Publicized

Online ISSN: 1745-1337

DOI: 10.1093/ietfec/e91-a.8.2101

Type of Manuscript: PAPER

Category: Numerical Analysis and Optimization

Cite this

Copy

Takuya KITAMOTO, Tetsu YAMAGUCHI, "On the Check of Accuracy of the Coefficients of Formal Power Series" in IEICE TRANSACTIONS on Fundamentals, vol. E91-A, no. 8, pp. 2101-2110, August 2008, doi: 10.1093/ietfec/e91-a.8.2101.
Abstract: Let M(y) be a matrix whose entries are polynomial in y, λ(y) and v(y) be a set of eigenvalue and eigenvector of M(y). Then, λ(y) and v(y) are algebraic functions of y, and λ(y) and v(y) have their power series expansions
λ(y) = β₀ + β₁ y + + β_k y^k + (β_j C),(1)
v(y) = γ₀ + γ₁ y + + γ_k y^k + (γ_j Cⁿ), (2)
provided that y=0 is not a singular point of λ(y) or v(y). 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 β_k and γ_k, using lower degree coefficients β_j and γ_j (j=0,1,,k-1). Thus with floating point arithmetic, the numerical errors in the coefficients can accumulate as index k increases. This can cause serious deterioration of the numerical accuracy of high degree coefficients β_k and γ_k, and we need to check the accuracy. In this paper, we assume that given matrix M(y) does not have multiple eigenvalues at y=0 (this implies that y=0 is not singular point of λ(y) or v(y)), and presents an algorithm to estimate the accuracy of the computed power series β_i,γ_j 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 p. Numerical experiments of the paper indicates that we can enhance the performance of the algorithm by 1216%, choosing the optimal tuning parameter p.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1093/ietfec/e91-a.8.2101/_p

Copy

@ARTICLE{e91-a_8_2101,
author={Takuya KITAMOTO, Tetsu YAMAGUCHI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={On the Check of Accuracy of the Coefficients of Formal Power Series},
year={2008},
volume={E91-A},
number={8},
pages={2101-2110},
abstract={Let M(y) be a matrix whose entries are polynomial in y, λ(y) and v(y) be a set of eigenvalue and eigenvector of M(y). Then, λ(y) and v(y) are algebraic functions of y, and λ(y) and v(y) have their power series expansions
λ(y) = β₀ + β₁ y + + β_k y^k + (β_j C),(1)
v(y) = γ₀ + γ₁ y + + γ_k y^k + (γ_j Cⁿ), (2)
provided that y=0 is not a singular point of λ(y) or v(y). 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 β_k and γ_k, using lower degree coefficients β_j and γ_j (j=0,1,,k-1). Thus with floating point arithmetic, the numerical errors in the coefficients can accumulate as index k increases. This can cause serious deterioration of the numerical accuracy of high degree coefficients β_k and γ_k, and we need to check the accuracy. In this paper, we assume that given matrix M(y) does not have multiple eigenvalues at y=0 (this implies that y=0 is not singular point of λ(y) or v(y)), and presents an algorithm to estimate the accuracy of the computed power series β_i,γ_j 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 p. Numerical experiments of the paper indicates that we can enhance the performance of the algorithm by 1216%, choosing the optimal tuning parameter p.},
keywords={},
doi={10.1093/ietfec/e91-a.8.2101},
ISSN={1745-1337},
month={August},}

Copy

TY - JOUR
TI - On the Check of Accuracy of the Coefficients of Formal Power Series
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 2101
EP - 2110
AU - Takuya KITAMOTO
AU - Tetsu YAMAGUCHI
PY - 2008
DO - 10.1093/ietfec/e91-a.8.2101
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E91-A
IS - 8
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - August 2008
AB - Let M(y) be a matrix whose entries are polynomial in y, λ(y) and v(y) be a set of eigenvalue and eigenvector of M(y). Then, λ(y) and v(y) are algebraic functions of y, and λ(y) and v(y) have their power series expansions
λ(y) = β₀ + β₁ y + + β_k y^k + (β_j C),(1)
v(y) = γ₀ + γ₁ y + + γ_k y^k + (γ_j Cⁿ), (2)
provided that y=0 is not a singular point of λ(y) or v(y). 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 β_k and γ_k, using lower degree coefficients β_j and γ_j (j=0,1,,k-1). Thus with floating point arithmetic, the numerical errors in the coefficients can accumulate as index k increases. This can cause serious deterioration of the numerical accuracy of high degree coefficients β_k and γ_k, and we need to check the accuracy. In this paper, we assume that given matrix M(y) does not have multiple eigenvalues at y=0 (this implies that y=0 is not singular point of λ(y) or v(y)), and presents an algorithm to estimate the accuracy of the computed power series β_i,γ_j 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 p. Numerical experiments of the paper indicates that we can enhance the performance of the algorithm by 1216%, choosing the optimal tuning parameter p.
ER -