近似根の効率的計算法について : アルゴリズムとデータ構造・計算複雑度

スポンサーリンク

概要

論文の詳細を見る
x,yを変数とする多項式f(x,y)が与えられたとき,f(x,0)=0が重根をもたなければ,f(x,y)=0のxに関する根g(y)はg(y)=α_0+α_1y+・・・+α_ky^k+・・・の形にテイラー展開できる.これをyのk次で打ち切ったものをf(x,y)のk次の近似根と呼ぶ.近似根は記号的ニュートン法を用いれば,効率的に計算できることが知られているが,本論文では通常の記号的ニュートン法に改良を加え,更に効率的な算法を提案する.具体的には,まずM.ShawとJ.F.Traubにより提案された方法による改良を述べ,その後に彼らの方法を更に改良して,より効率的な計算法を導けることを示す.計算量の解析と数値実験を行い,提案する算法が従来のものより計算量の点で優れていることを示す.
一般社団法人電子情報通信学会の論文
2002-02-01

著者

関連論文

もっと見る

スポンサーリンク