氏名: 中川 智貴 (289734290)

論文題目: 多項式零点の精度保証付計算


論文概要

 係数が与えられた多項式の零点を数値的に計算する方法はNewton法をはじめ数多く提案されている.だが,精度に対する絶対的な保証はない.本論文では多項式の零点の存在領域を複素平面の円盤領域で与えるアルゴリズムについて述べる.

 方法として,n次多項式の近似根をAberth法で求め,その近似根を用いSmithの定理で近似根ごとに根の存在領域を示す円盤をつくる.他の円盤から完全に分離している円盤に対してはGargantini-HenriciのCircular Arithmeticで円盤を小さくする.これにより多項式の零点の存在領域を生成し,領域も丸め誤差の影響する限界まで縮められる.
 複数個の根が近接する場合,対応する円盤は分離しない.それらをClusterとして考えてその存在領域と,近接根を根とする新たな多項式の係数を与えることで対応する.Clusterごとに新たな多項式をつくるが,この多項式は係数が円盤であり元の多項式の2次以上の近似因子となる.その係数の円盤を園田法を円盤に拡張したもので縮小し,より精密な係数を作成する.

 アルゴリズムの実現には,丸め誤差,入力誤差の影響を考慮にいれ区間演算パッケージC-XSCを用いた.


目次に戻る


asakura@nuie.nagoya-u.ac.jp