Accurate Computation of a High Degree Coefficient of a Power Series Root(Algorithms and Data Structures)
スポンサーリンク
概要
- 論文の詳細を見る
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+α_2y^2+…+α_py^p+….(1) Let φ^<(p)>(y) denote φ(y) truncated at y^p, i.e. φ^<(p)>(y)=α_0+α_1y+α_2y^2+…+α_py^p.(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 y^<k+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.
- 一般社団法人電子情報通信学会の論文
- 2005-03-01
著者
関連論文
- The Optimal H_∞ Norm of a Parametric System Achievable by an Output Feedback Controller
- On the Check of Accuracy of the Coefficients of Formal Power Series
- The Optimal H_∞ Norm of a Parametric System Achievable Using a Static Feedback Controller(Systems and Control)
- Extension of the Algorithm to Compute H_∞ Norm of a Parametric System
- Efficient Computation of the Characteristic Polynomial of a Polynomial Matrix
- On Efficient Computations of Approximate Roots
- Accurate Computation of a High Degree Coefficient of a Power Series Root(Algorithms and Data Structures)
- On Computation of Approximate Eigenvalues and Eigenvectors
- On Computation of a Power Series Root with Arbitrary Degree of Convergence
- Computation of the Peak of Time Response in the Form of Formal Power Series(Systems and Control)