Accurate Computation of a High Degree Coefficient of a Power Series Root
Accurate Computation of a High Degree Coefficient of a Power Series Root
复制标题
幂级数根高次系数的精确计算
DOI：
10.1093/ietfec/e88-a.3.718
复制
发表时间：
2005
影响因子：
0.5
通讯作者：
T. Kitamoto
中科院分区：
文献类型：
--
作者：
T. Kitamoto
给定二元多项式f(x, y)，设Φ(y)是f(x, y) = 0关于x的一个根，即Φ(y)是y的一个函数，使得f（Φ(y),y） = 0。如果Φ(y)在y = 0时是解析的，那么我们得到它的幂级数展开式
Given the bivariate polynomial f(x, y), let Φ(y) be a root of f(x, y) = 0 with respect to x, i.e. Φ(y) is a function of y such that f(Φ(y),y) = 0. If Φ(y) is analytic at y = 0, then we have its power series expansion
Φ(y) = α0 + α1y + α2y2 + ··· + αpyp + ···. (1)
Let Φ(p)(y) denote Φ(y) truncated at yp, i.e.
Φ(p)(y) = α0 + α1y + α2y2 + ··· + αpyp. (2)
It is well-known that we can compute power series roots Φ(p)(y) by Newton's method. In fact, given the initial value Φ(0)(y) = α0 ∈ C, the following Newton's method
Φ(k)(y) ← Φ(k-1)(y) - f(Φ(k-1)(y), y)/∂f/∂x(α0, 0) (mod yk+1) (3)
computes Φ(k)(y) (1 ≤ k) in expression (2) efficiently (applying the above formula for k = 1,2,..., we can compute the power series root Φ(p)(y) of any degree p). The above formula (3) is referred to as "symbolic Newton's method" in this paper. From this formula (3), we can see that the numerical errors in the coefficients αs (s = 0,1, ..., k - 1) directly affect the numerical error in the coefficient αk. This implies that the symbolic Newton's method is numerically unstable, i.e., a numerical error in the coefficient αk accumulates as the index k increases. Moreover, with the symbolic Newton's method, even if we need only one coefficient αk, we must compute all coefficients αs (s = 0,1, ..., k - 1). Thus when we require only one high degree coefficient αk, the symbolic Newton's method is numerically unstable and inefficient. In this paper, given the integer k (> 0), we present a new algorithm to compute the coefficient αk of (1). The new algorithm is numerically stable and requires no computation of the coefficients other than αk itself.