(57)【要約】【課題】実区間多項式が実係数多項式を実因子として持っているか判定する。【解決手段】実区間多項式Σ[li, hi]ei(x)を各ei(x)ごとに実係数多項式ｆで割り算して剰余ri(x)を求め、li=hiとなる番号があればそれらに対する剰余を足し合わせてr0(x)とし、ri(x)=0となるものははずすことにより、実区間多項式r0(x)+Σ[li, hi]ri(x)を生成する。生成した実区間多項式の各区間係数の区間幅を単位長に正規化してp0(x)+Σ[0, 1]pi(x)と書換え、凸多面体とみなす。超立方体からこの凸多面体への全射となるアフィン写像を取り、超立方体の面のうちアフィン写像により写したものが凸多面体のファセットとなる場合に、このファセットを含む超平面と、それと平行な超平面でファセットと平行な別のファセットを含むものを求め、この２つの超平面の間に点０が存在するか否かを判定することにより、実因子を持つか否かを判定する。【選択図】図１
2008262262.tif 000002
【特許請求の範囲】
【請求項１】
実区間多項式が実因子を持つか判定する判定方法であり、
(a) 実区間多項式[l1, h1]e1(x)＋…＋[ln, hn]en(x)と、実係数多項式と、項順序が与えられ、上記各ei(x)を上記項順序に従って上記実係数多項式により割算して剰余を求めるステップと、
(b) 上記実区間多項式において各ei(x)を上記剰余で置き換えた実区間多項式を凸多面体とみなしたとき、超立方体及び上記超立方体から上記凸多面体への全射となるアフィン写像を１つ取り、上記超立方体の面のうち上記アフィン写像により写したものが上記凸多面体のファセットとなる場合に、上記ファセットを含む超平面及び上記超平面と平行な超平面で上記凸多面体の上記ファセットと平行な上記凸多面体のファセットを含むものをすべて求め、上記２つの超平面の間に点０が存在するか否かを判定し、すべての場合に存在するときに上記実係数多項式は実因子であると判定し、そうでない場合には上記実係数多項式は実因子でないと判定し、上記判定結果を出力するステップ、
とを含むことを特徴とする実区間多項式の実因子判定方法。
【請求項２】
請求項１記載の実因子判定方法において、上記ステップ(a)の上記割算は、上記実区間多項式の区間[li, hi]の両端が一致するei(x)をまとめて割算して剰余をr0(x)とし、区間[li, hi]の両端が一致しない各ei(x)は割算の剰余をri(x)とすると、剰余ri(x)=0の項をはずして上記凸多面体を生成することを特徴とする実区間多項式の実因子判定方法。
【請求項３】
請求項２記載の実因子判定方法において、上記ステップ(a)は、上記剰余にかかる係数の区間の長さを単位長に正規化するステップを含み、上記ステップ(b)は上記実区間多項式において各ei(x)を上記剰余で置き換えた実区間多項式に対し、上記置き換えた実区間多項式の各係数を正規化した実区間多項式を凸多面体とみなしたとき、上記２つの超平面の間に点０が存在するかの判定を行うことを特徴とする実区間多項式の実因子判定方法。
【請求項４】
請求項１乃至３のいずれか記載の実因子判定方法において、上記ステップ(b)は、上記剰余を並べてできる行列の階数ｄを計算するステップと、上記剰余にかかる係数の区間が一点であるものを除いたものから取ったｄ−１個からなりかつ一次独立なすべての剰余の組についてそれぞれ上記２つの超平面の間に点０が存在するか否かの判定を行うステップを含むことを特徴とする実区間多項式の実因子判定方法。
【請求項５】
請求項３記載の実因子判定方法において、上記剰余から決まる実区間多項式を
【数１】
2008262262.tif 000046
と表すと、上記正規化は、
【数２】
2008262262.tif 000047
と書き換えるステップであることを特徴とする実区間多項式の実因子判定方法。
【請求項６】
請求項５記載の実因子判定方法において、上記ステップ(b)は、上記剰余を並べてできる行列の階数ｄを計算するステップと、
Ｉを{1, 2, …, n}の部分集合とし、その要素数をd-1とすると、aff(P)内の超平面aff({pi(x)|i∈Ｉ}∪{0})の法線ベクトルｎＩを求めるステップと、
不等式
【数３】
2008262262.tif 000048
ただしｐの和の範囲＜０は{pi(x)|i∈I, <nI, pi(x)>＜0}を表し、pの和の範囲＞０は{pi(x)|i∈I, <nI, pi(x)> ＞0}を表す、
が成立するか否かを判定し、その判定結果を上記情報として出力するステップ、
とを含むことを特徴とする実区間多項式の実因子判定方法。
【請求項７】
実区間多項式が実因子を持つか判定する実因子判定装置であり、
実区間多項式[l1, h1]e1(x)＋…＋[ln, hn]en(x)と、実係数多項式と、項順序が与えられ、各上記ei(x)を上記項順序に従って上記実係数多項式により割算して剰余を求める剰余計算手段と、
上記実区間多項式において各ei(x)を上記剰余で置き換えた実区間多項式を凸多面体とみなしたとき、超立方体及び上記超立方体から上記凸多面体への全射となるアフィン写像を１つ取り、上記超立方体の面のうち上記アフィン写像により写したものが上記凸多面体のファセットとなる場合に、上記ファセットを含む超平面及び上記超平面と平行な超平面で上記凸多面体の上記ファセットと平行な上記凸多面体のファセットを含むものをすべて求め、上記２つの超平面の間に点０が存在するか否かを判定し、すべての場合に存在するときに上記実係数多項式は実因子であると判定し、そうでない場合には上記実係数多項式は実因子でないと判定し、上記判定結果を出力する剰余判定手段、
とを含むことを特徴とする実区間多項式の実因子判定装置。
【請求項８】
請求項７記載の実因子判定装置において、上記剰余計算手段は、上記実区間多項式の区間[li, hi]の両端が一致するei(x)をまとめて割算して剰余r0(x)とし、区間[li, hi]の両端が一致しない各ei(x)は割算の剰余をri(x)とすると、剰余ri(x)=0の項をはずして上記凸多面体を生成する実区間多項式書換え部を含むことを特徴とする実区間多項式の実因子判定装置。
【請求項９】
請求項８記載の実因子判定装置において、上記実区間多項式書換え部は、上記剰余にかかる係数の区間の長さを単位長に正規化するステップを含み、上記ステップ(b)は上記実区間多項式において各ei(x)を上記剰余で置き換えた実区間多項式に対し、上記置き換えた実区間多項式の各係数を正規化した実区間多項式を凸多面体とみなしたとき、上記２つの超平面の間に点０が存在するかの判定を行うことを特徴とする実区間多項式の実因子判定装置。
【請求項１０】
請求項７乃至９のいずれか記載の実因子判定装置において、上記剰余判定手段は、上記剰余を並べてできる行列の階数ｄを計算し、上記剰余にかかる係数の区間が一点であるものを除いたものから取ったｄ−１個からなりかつ一次独立なすべての剰余の組についてそれぞれ上記２つの超平面の間に点０が存在するか否かの判定を行うようにされていることを特徴とする実区間多項式の実因子判定装置。
【請求項１１】
請求項１０記載の実因子判定装置において、上記剰余から決まる実区間多項式を
【数４】
2008262262.tif 000049
と表すと、上記正規化は、
【数５】
2008262262.tif 000050
とおいて、
【数６】
2008262262.tif 000051
と書き換えることを特徴とする実区間多項式の実因子判定装置。
【請求項１２】
請求項１１記載の実因子判定装置において、上記剰余判定手段は、上記剰余を並べてできる行列の階数ｄを計算し、
Ｉを{1, 2, , n}の部分集合とし、その要素数をｄ−１とすると、aff(P)内の超平面aff({pi(x)|i∈Ｉ}∪{0})の法線ベクトルｎＩを求めるアフィン包計算部と、
不等式
【数７】
2008262262.tif 000052
ただしｐの和の範囲＜０は{pi(x)|i∈I, <nI, pi(x)>＜0}を表し、pの和の範囲＞０は{pi(x)|i∈I, <nI, pi(x)> ＞0}を表す、
が成立するか否かを判定し、その判定結果を上記情報として出力する不等式生成判定部、
とを含むことを特徴とする実区間多項式の実因子判定装置。
【請求項１３】
請求項１乃至６のいずれかの実区間多項式の実因子判定方法をコンピュータで実行するプログラム。
【請求項１４】
請求項１３記載のプログラムを記録したコンピュータで読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
係数に誤差のある実多項式が、指定された実係数多項式を実因子として持つか否かの判定法に関係する。
【背景技術】
【０００２】
係数に誤差のある実多項式は、例えばディジタル信号処理やシステム制御の分野に現れ、その零点の位置はディジタルフィルタの周波数特性やシステムの性能に密接に関係する。多項式が一変数の場合、指定された０ではない実係数多項式f(x)を因数分解して
【数８】
2008262262.tif 000003
（ただし、γiは複素数でもよく、ｉ≠ｊならばγi≠γj）と書くと分かるように、f(x)を実因子として持つことは、γｉを少なくとも重複度ｍｉである零点として持つことと同値である。
【０００３】
実係数一変数多項式
【数９】
2008262262.tif 000004
について、各係数aiは、観測や測定によって得られたもので、誤差を含むものとする。ただし、誤差の範囲は分かっており、各aiの真の値は実の閉区間[li, hi]内にあるものと仮定する。各係数がこの誤差範囲内にある多項式で、指定された実数を零点とするものが存在するか否か判定せよ、という問題を考える。この問題に関する文献として非特許文献１がある。
【０００４】
この非特許文献１では複素係数の多項式を扱っているが、その２ページの脚注にあるように、実係数の場合にも適用できるように書き直すことができる。具体的には、各係数が上記の通り指定された誤差範囲内にある多項式で、与えられた実数γを零点とするものが存在するか否かは、
【数１０】
2008262262.tif 000005
を、端点を正確に計算する区間演算を用いて求め、その結果の区間に０が入るか否かで決まる。
【０００５】
実係数一変数多項式p(x)がγを零点として持つか否かは、p(x)が一次式x-γで割り切れるか否かと同値である。以下で、p(x)を多変数に、一次式x-γを多変数高次式に拡張した場合の判定について述べる。即ち、以下の問題を扱う。
問題１：与えられた実係数ｋ変数多項式を
【数１１】
2008262262.tif 000006
と書く。ただし、α＝(α1, …, αk)として、xαはx１α1…xkαkのことである。α1, …, αkはそれぞれ０以上の整数である。各係数aαが誤差を含み、真の値が1α≦aα≦hαなる範囲にあるとして、各係数がこの誤差範囲内にある次の多項式
【数１２】
2008262262.tif 000007
で割り切れるものが存在するか否かを判定せよ。なお、f(x)が一変数の場合、問題１は、指定した複数の零点（重複度がいくつ以上という指定可能）を持つ多項式が誤差範囲内に存在するか否かを判定することに相当する。
【０００６】
問題１に関連する文献として非特許文献２がある。
この非特許文献２では、与えられた多変数多項式p(x)に対し、因数分解可能な、p(x)に近い多項式q(x)を求める問題を扱っている。そこでは、この問題を過剰決定の双線形方程式系の近似解を求める問題として解いている。具体的には、
【数１３】
2008262262.tif 000008
としたときに、多項式p(x)とq(x)の間の距離を
【数１４】
2008262262.tif 000009
即ち、q(x)−p(x)のl２-ノルムではかり、因数分解可能なq(x)でこの距離が極小となるものを求めている。
【０００７】
なお、問題１は、非特許文献３の第242−243頁にある記述と同じ考え方で、線形計画問題としても扱える。
ただし、解法として単体法を用いる場合、多項式ステップで計算が終了する保証はない。カーマーカー法を用いるなら、多項式ステップで計算が終了する。
【非特許文献１】H.J, Stetter, The nearest polynomial with a given zero, and similar problems, ACM SIGSAM Bulletin, Vol.33, No.4, pp.2-4, 1999.
【非特許文献２】Y.Huang, W.Wu, H.J.Stetter and L.Zhi, Pseudofactors of multivariate polynomials, Proc. 2000 International Symposium on Symbolic and Algebraic Computation(ISSAC2000), pp.161-168, 2000.
【非特許文献３】M.A.Hitz and E.Kaltofen, Efficient algorithms for computing the nearest polynomial with constrained roots, Proc. 1998 International Symposium on Symbolic and Algebraic Computation(ISSAC98), pp.236-243,1998.
【発明の開示】
【発明が解決しようとする課題】
【０００８】
本発明の目的は、
・誤差範囲指定をl２-ノルムではなく、係数ごととすること、
・線形計画法とは異なる手法により多項式ステップで計算が終了すること、
を可能とした、実区間多項式の実因子判定法を提供することにある。
【課題を解決するための手段】
【０００９】
この発明による実区間多項式が実因子を持つか判定する判定方法は、
(a) 実区間多項式[l1, h1]e1(x)＋…＋[ln, hn]en(x)と、実係数多項式と、項順序が与えられ、上記各ei(x)を上記項順序に従って上記実係数多項式により割算して剰余を求めるステップと、
(b) 上記実区間多項式において各ei(x)を上記剰余で置き換えた実区間多項式を凸多面体とみなしたとき、超立方体及び上記超立方体から上記凸多面体への全射となるアフィン写像を１つ取り、上記超立方体の面のうち上記アフィン写像により写したものが上記凸多面体のファセットとなる場合に、上記ファセットを含む超平面及び上記超平面と平行な超平面で上記凸多面体の上記ファセットと平行な上記凸多面体のファセットを含むものをすべて求め、上記２つの超平面の間に点０が存在するか否かを判定し、すべての場合に存在するときに上記実係数多項式は実因子であると判定し、そうでない場合には上記実係数多項式は実因子でないと判定し、上記判定結果を出力するステップ、
とを含むことを特徴とする。
【００１０】
本手法は、実区間多項式を凸多面体と見て、凸多面体の性質を用いることを主要な特徴とする。実区間多項式は凸多面体の中でも特別な性質を持つものとなるので、凸多面体の一般の性質を利用する線形計画法の単体法とは異なる手法である。
【発明の効果】
【００１１】
非特許文献１では、誤差のある多項式ｐが一変数、ｐがｆで割り切れるかどうかのｆが一次式の場合しか扱っていない。非特許文献２では、l２-ノルムで誤差をはかっており、さらに、扱っている問題は関連があるものの、問題１を解くためには利用できない。線形計画法の単体法では、凸多面体の一般の性質を利用しているため、多項式ステップで計算が終了する保証がない。
【００１２】
一方、本手法は、実区間多項式は凸多面体の中でも特別な性質を持つものであることを利用しているため、多項式ステップで計算が終了する。
【発明を実施するための最良の形態】
【００１３】
発明を導くための理論
《実区間多項式》
まず、実区間多項式について、記法、用語、必要な性質の説明をする。
【００１４】
変数x1，…，xkをまとめてｘと書く。α＝(α1，…，αk)、ただし、αiは非負の整数として、ｘαはx1α1，…，xkαkのこととする。係数に誤差のある多項式を表す手法として、区間多項式がある。区間多項式とは、数の集合である区間数Ａｉおよび、あらかじめ指定された多項式ei(x)(１≦ｉ≦ｎ)に対し、ai∈Ａiである多項式Ｐ(x)＝Σi=1ｎaiei(x)全体の集合のことで、Σi=1ｎＡiei(x)と表記する。以下、区間数Ａｉとしては実の閉区間[li, hi]（ただし、lはローマ字のエルであり、li, hiは有理数）を用い、ei(x)は有理数係数多項式とする。このような区間多項式を実区間多項式と呼ぶ。各区間[lｉ, hi]＝{ｃ∈Ｒ｜lｉ≦ｃ≦hｉ}を区間係数と呼ぶ。以上では説明を簡単にするため区間数の端点、多項式ei(x)の係数は有理数としたが、アルゴリズムの実行のためには四則演算及び等号判定が実行できれば十分なので、例えば実代数的数（整数係数一次代数方程式の根となる実数）としてもそのまま当てはまる。
【００１５】
各ei(ｘ)がｘの単項式のとき、上記定義の実区間多項式は、普通に使われる意味での実区間多項式である。しかし、以下に提案する本発明手法では、入力される実区間多項式が普通のものであっても、途中で上記の、拡張された実区間多項式が必要となる。
実係数多項式ｆと実区間多項式Ｐに対し、Ｐに属する多項式ｐが存在してｐがｆで割り切れるとき、Ｐは擬因子ｆを持つ、あるいは、ｆはＰの擬因子である、ということにする。
【００１６】
本発明は、以下の問題に解答することを目的とする。
問題２：与えられた実係数多項式ｆと実区間多項式
【数１５】
2008262262.tif 000010
に対し、ｆがＰの擬因子であるか否かを判定せよ。
【００１７】
次に、項順序について説明する。x１, …, xｋの単項式全体の集合Ｔの全順序＜で、以下の二つの性質を満すものを項順序と呼ぶ。
・ｓ，ｔ，ｕ∈Ｔかつ、ｓ＜ｔならば、ｕｓ＜ｕｔ。
・任意のｔ∈Ｔに対し、１≦ｔ。
【００１８】
代表的な項順序として、例えば以下がある。α＝(α1, …, αk），β＝(β1, …, βk)とする。
・辞書式順序
ｘα＜ｘβとなるのは、(β1−α1, …, βk−αk)を左から見ていったとき、０ではない最初のβj−αjが正のとき、と定義する。
・全次数順序
【００１９】
ｘα＜ｘβとなるのは、以下のどちらかが成り立つとき、と定義する。
１．α1＋…＋αk＜β1＋…＋βk
２．α1＋…＋αk＝β1＋…＋βkかつ、(β1−α1, …, βk−αk)を左から見ていったとき、０ではない最初のβj−αjが正。
項順序を一つ固定しておく。
【００２０】
多項式ｇ＝Σαａαｘαに対し
【数１６】
2008262262.tif 000011
をHT(g)と書く。また、ｘα＝HT(g)のとき、aαｘαをHM(g)と書く。ｆ，ｇをｋ変数実係数多項式とする。ｇをｆで割ったときの剰余とは、以下により計算されるものである。
Step１．ｒ＝ｇとする。
Step２．ｒの項の中で、HT(f)で割り切れるものがあればその中から一つをとりＭ、その係数をｃＭとしてStep３へ。
なければ、剰余としてｒを返して終了。
Step３．以下を計算し、その結果を改めてｒと置き、Step２へ。
【数１７】
2008262262.tif 000012
【００２１】
問題２をより簡単な問題に変換するために、以下の補題を用いる。
補題１：項順序を一つ固定しておく。ｆとgｉ(i＝1, 2, …, n)をｋ変数実係数多項式とする。このとき、Σi=1ｎaｉgｉ（aｉ∈Ｒ）がｆで割り切れる必要十分条件は、Σi=1ｎaｉrｉ＝０、ただし、rｉは、各gｉをｆで、固定した項順序により割った剰余である。
【００２２】
項順次を一つ固定する。この項順序について各多項式eｉをｆで割ったときの剰余をrｉとする。もし、rｉが０となった場合は、その多項式riをはずして次の多項式のｆによる割り算の剰余をriとし、即ち番号をつけ変えて、すべての多項式eiについての割り算の結果から決まる実区間多項式を
【数１８】
2008262262.tif 000013
と書く。このとき、問題２を解くためには、以下のよりやさしい問題を解けば十分である。
【００２３】
問題３：上記の実区間多項式Ｐ′に０が入るか否か判定せよ。
ｄをr1(x), …, rn(x)の全次数の最大値とする。さらに、ｎはｄの多項式で上から押さえられると仮定する。例えば、各ri(x)が単項式のときはこの条件が満される。なぜなら、ｘ１, …, ｘｋの単項式で、その全次数がｄ以下のものの数は(d+k)!/(k!d!)であって、これは(d+k)ｋ以下であるからである。全次数順序を用いるなら、問題２から問題３への変換はｄの多項式ステップで可能である。
【００２４】
《凸多面体》
以下、凸多面体について、記法、用語、必要な性質の説明をする。ｎ次元空間Ｒn内の任意の点ｖ＝(v1, …, vn)はベクトルを表している。
【００２５】
定義１（アフィン空間）：Ｒnのアフィン部分空間とは、ｖ+Ｖ、ただし、ベクトルｖ∈Ｒnかつ、ベクトルの集合Ｖ⊂Ｒｎは部分ベクトル空間、と書ける集合である。アフィン部分空間ｖ＋Ｖの次元はＶの次元のことと定義する。
Ａ⊂Ｒｎをアフィン部分空間とする。このとき、ＶはＡから一意に決まる。さらに、任意のａ∈Ａに対しＡ＝ａ＋Ｖである。
【００２６】
定義２（アフィン包）：ＡをＲｎの部分集合とする。Ａを含むすべてのアフィン部分空間の共通部分をＡのアフィン包と呼び、aff(Ａ)と書く。
定義よりaff(Ａ)はＲｎのアフィン部分空間である。Ａ＝{a１, …, aｍ}が有限集合のとき、
aff(Ａ)＝{t１a１＋…＋tｍaｍ｜t１＋…＋tｍ＝１, tｉ∈Ｒ}            (4)
と書ける。
ｊ∈{1, 2, …, m}に対し、aff(Ａ)は以下のようにも書ける。
【数１９】
2008262262.tif 000014
【００２７】
定義３（凸多面体）：凸多面体とは、Ｒｎの有限個の点の凸包である。凸多面体Ｐの次元は、aff(Ｐ)のそれで定義する。
Ｒｎの超平面とは、アフィン部分空間で次元がｎ−１のものをいう。超平面は、ｂ∈Ｒと０ではないａ∈Ｒｎによって、
{ｘ∈Ｒｎ｜<ａ, ｘ>＝ｂ}                    (6)
と書ける。ただし、ｘ＝(x1, …, xn)およびａ＝(a1, …, an)であり、<a，x>はＲｎにおけるａとｘの内積a1x1＋…＋anxnである。Ｒｎのアフィン半空間とは、ｂ∈Ｒと０ではないａ∈Ｒｎによって、
{ｘ∈Ｒｎ｜<ａ，ｘ> ≧ｂ}                    (7)
と書けるものをいう。
【００２８】
凸多面体について、以下の基本定理が成り立つ。
定理１：Ｐ⊂Ｒｎが凸多面体となる必要十分条件は、Ｐが有界かつ、有限個のアフィン半空間の共通部分となることである。
【００２９】
定義４（面，ファセット）：Ｐ⊂Ｒｄを次元ｄの凸多面体とする。以下のいずれかが成り立つとき、Ｐの部分集合Ｆを面という。
・Ｆは空集合あるいは、Ｆ＝Ｐ
・ある超平面
Ｈ＝{ｘ∈Ｒｄ｜<ａ, ｘ>＝ｂ}                  (8)
が存在して、Ｆ＝Ｐ∩Ｈかつ、
Ｐ⊂{ｘ∈Ｒｄ｜<ａ, ｘ> ≧ｂ}                (9)
面Ｆの次元はaff(Ｆ)の次元のことと定義する。Ｐの面で次元がｄ−１のものをファセットという。
【００３０】
定理２：Ｐ⊂Ｒdを次元がｄの凸多面体とする。その共通部分がＰとなるような、アフィン半空間の最小の族は、Ｐのファセットのアフィン包を境界とする、Ｐを含むアフィン半空間の族である。
上記定理は、次の参考文献１の第３１−３２頁に記述がある。
参考文献１：B.Grunbaum,Convex Polytopes(2nd edition), Springer-Verlag, 2003.
これより、以下がいえる。
【００３１】
定理３：Ｐ⊂Ｒnを次元がｄの凸多面体とする。このとき、Ｐはaff(Ｐ)とＲｎの有限個のアフィン半空間の共通部分となる。その中で、最小の族の一つは、i＝1, …, mに対するアフィン半空間
Ｈｉ＝{ｘ∈Ｒｎ｜<ａｉ, ｘ> ≧ｂｉ｝                  (10)
である。ここで、共通部分の集合Ｈｉ∩ＰはＰのファセットであり、逆に、Ｐのすべてのファセットは、あるｉについて、Ｈｉ∩Ｐと書けている。
【００３２】
問題３を、凸多面体の理論が使える形に変形する。問題３の実区間多項式を改めて
【数２０】
2008262262.tif 000015
と書き、ri(ｘ), i=1, …, nに現れるすべての単項式ｕの集合をＭ={u1, …, um}、その要素数をｍ、単項式の係数をａu=(au1, …, aum)∈Ｒとする。すると、任意の多項式ｐ∈Ｐは、
【数２１】
2008262262.tif 000016
と書ける。任意の多項式ｐ∈Ｐを以下の写像によりＲｍの点、即ちｍ次元内の点(au1, …, aum)とみなす。
【数２２】
2008262262.tif 000017
r0(x)をΣｉliri(x)、ただし、ｉは、{i｜li＝hｉ}を走るものとする。すると、Ｐは、
【数２３】
2008262262.tif 000018
ただし、ｉは、{i｜lｉ＜hｉ}を走る、と書ける。
【００３３】
必要なら添字をつけ変えて、Ｐを、
【数２４】
2008262262.tif 000019
と書く。もしn'=0ならばＰはただ一つの多項式r0(x)から構成されるので、r0(x)がｆで割り切れるか否かを調べればよい。よって、以下、n'≧１とし、簡単にするため、n'をｎと書換える。
【００３４】
r0(x)がaff({0, r1(x), …, rn(x)})に属すか否か、即ち連立一次方程式r0(x)=Σitiri(x)を満足するti∈Ｒが存在するか否かを簡単に判定可能である。もし、r0(x)がaff({0, r1(x), …, rn(x)})に属さなければ、各多項式ri(x)の係数が区間[li, hi]のどの係数をとってもr0(x)=Σitiri(x)を満足する係数は存在しないので、０はＰに入らない。
【００３５】
よって、問題３を仮定r0(x)∈aff({0, r1(x), …, rn(x)})の下で考える。即ち、
問題４：Ｐを以下の実区間多項式とする。
【数２５】
2008262262.tif 000020
ここで、i=1, 2, …, n（ｎ≧１）に対しlｉ＜hｉであり、r0(x)∈aff({0, r1(x), …, rn(x)})としたとき、０∈Ｐとなるか否か判定せよ。
【００３６】
問題４において、ただ一つの多項式rj(x)にのみ現れる単項式があったとする。もし、j＝0ならば、直ちに０はＰに含まれないといえる。もし、j≠0ならば、そのrj(x)中の単項式を他の多項式中の単項式でキャンセルできないので、０∈Ｐとなるためには、その唯一の単項式の係数は０を取ることができなければならない。従って、rj(x)の区間係数[lj, hj]は０を含むことが必要で、このとき、問題は、
【数２６】
2008262262.tif 000021
が成立するかに帰着できる。つまり、多項式rj(x)を除いて考慮すればよい。同様にただ１つの多項式にのみ現れる他の単項式があればその多項式を除去した実区間多項式Ｐを考慮すればよく、このような処理により、問題をより簡単なものへ帰着できる。
【００３７】
実区間多項式(16)を以下の通り書く。
【数２７】
2008262262.tif 000022
ここで、
【数２８】
2008262262.tif 000023
である。式(18)中のp0(x)は単なる平行移動とみなせるので、残りの実区間多項式をＰと考え、各多項式pi(x)を１つの点aiに対応させると、以下の補題より、Ｐは有限個の点の凸包であることが分かる。
【００３８】
補題２： 各ａｉ∈Ｒｍに対し、集合
【数２９】
2008262262.tif 000024
は、以下の集合の凸包に等しい。
【００３９】
【数３０】
2008262262.tif 000025
よって、実区間多項式は凸多面体である。よって、有限個のアフィン半空間の共通部分として書ける。以下、どうやって必要なアフィン半空間を求めるか記述する。
【００４０】
Ｐ⊂Ｒｄを次元がｄで、以下の通り表現される凸多面体とする。
【数３１】
2008262262.tif 000026
Ａを{a1, …, an}，ＸをＲｄ内の超平面とし、ｎ(Ｘ)をＸの法線ベクトルとする。ｎ(Ｘ)とＡによって、以下の２つのアフィン半空間が決まる。
【数３２】
2008262262.tif 000027
すると、以下が成り立つ。
【００４１】
定理４： Ｐを以下の凸多面体とする。
【数３３】
2008262262.tif 000028
ただし、aｉ∈Ｒｄとし、Ｐの次元もｄとする。また、Ａを集合{a１, …, aｎ}とする。すると、
【数３４】
2008262262.tif 000029
ただし、ＦはＰのすべてのファセットを走る、が成り立つ。
【００４２】
よって、Ｐのすべてのファセットを見つけるのが問題となる。pi(x)を式(19), (20)により定義されている多項式とし、式(12)と同様にri(x), (i=1, …, n)に現れるすべての単項式ｕの集合をＭ、その要素数をｍとすると、i=0, 1, …, nに対するn+1個の多項式pi(x)∈Ｐは、
【数３５】
2008262262.tif 000030
と表される。ただし、Ｍ＝{u1, u2, …, um}, aiu∈Ｒである。以下の、Ｒｎ内の点ｃ＝(c1, …, cn)からＲｍへの写像を考える。
【数３６】
2008262262.tif 000031
ここで、ei∈Ｒｎは、その第ｉ成分のみが１で、他は０のベクトルである。上記式の右辺は
【数３７】
2008262262.tif 000032
で表されるｍ次元内の１つの点に対応している。この写像はアフィン写像、即ち、πは以下の通りに書ける。
π(ｖ)＝Ａｖ＋ｂ                      (30)
ここで、Ａはｍ×ｎの行列、ｂ∈Ｒｍである。すると、Ｐ⊂Ｒｍは、超立方体のアフィン写像による像である。
【００４３】
二つの凸多面体間のアフィン写像があるとき、双方の面の間には以下の関係がある。（注：凸多面体のアフィン写像による像は凸多面体である。）
補題３： Ｑ⊂ＲｎとＰ⊂Ｒｍを凸多面体とする。π：Ｒｎ→Ｒｍをアフィン写像であって、π(Ｑ)＝Ｐであるものとする。すると、Ｐのすべての面Ｆに対し、π−１(Ｆ)はＱの面である。
上記補題は、次の参考文献２のLemma 7.10（196頁）である。
参考文献２：G.M.Ziegler, Lectures on Polytopes, Springer-Verlag, 1995.  
【００４４】
Ｐ，Ｑ，πを補題３の通りとする。すると、任意のＰのファセットＦに対し、Ｑの面Ｇが存在して、Ｆ＝π(Ｇ)となる。よって、Ｐのファセットを見つけるのに、Ｑの面を利用できる。今、Ｑは超立方体だから、その面は簡単に記述できる。
【００４５】
さらに、以下により、Ｐの次元をｄとしたときＱの次元ｄ−１の面のみ調べれば十分である。
補題４： Ｐ⊂Ｒｍを凸多面体とする。超立方体
【数３８】
2008262262.tif 000033
と、πがＲｎからＲｍへのアフィン写像で、π(Ｑ)＝Ｐとする。ＦをＰの、次元ｆの任意の面としたとき、wI(1), wI(2), …, wI(f)∈{w1, w2, …, wn}とベクトルｖ∈Ｒｍが存在して、以下が成り立つ。
【００４６】
【数３９】
2008262262.tif 000034
さらに、π(ｓ)＝ｖとなる各ベクトルｓ∈Ｒｎに対し、
【数４０】
2008262262.tif 000035
は次元がｆであるＱの面である。
【００４７】
以上より、以下の定理が成り立つ。
定理５：
【数４１】
2008262262.tif 000036
を次元がｄの凸多面体とする。
【００４８】
Ｑ＝e0＋Σi=1ｎ[0, 1]eｉ⊂Ｒｎを超立方体、ここで、eｉ∈Ｒｎは、ｉ番目の要素のみが１で他が０のベクトル、πをＲｎからＲｍへのアフィン写像で、π(Ｑ)＝Ｐなるものとする。ＡとＥを集合{a１, a２, …, aｎ}と{e１, e２, …, eｎ}とする。
aff(π(Ｘ))がaff(Ｐ)の超平面となる部分集合Ｘ⊂Ｑに対し、aff(π(Ｘ))の法線ベクトルをn'(Ｘ)と書く。
【００４９】
すると、ｃ∈Ｐとなるのは、以下の二つの条件が満されることが必要十分である。
１．ｃ∈aff(Ｐ)
２．任意のＥ'⊂Ｅ、ただし、|Ｅ'|＝ｄ−１かつ、aff(π(Ｅ')∪{0})の次元がｄ−１、に対し、以下の不等式が成立する。
【数４２】
2008262262.tif 000037
【００５０】
実区間多項式の実因子判定方法
《メインアルゴリズム》
今までの結果をまとめると、問題４に回答するアルゴリズムを以下の通りとなり、図１を参照して説明する。
入力：実区間多項式Ｐ(ｘ)＝Σi=1ｎ[li, hi]ei(x)、実係数多項式f(x)、項順序。
出力：Ｐに属する多項式でｆで割り切れるものが存在するか否か。
ステップＳ１：以下の二つの書換えを行う。
【００５１】
第１の書換え：入力された項順序により各ei(x)をｆで割った剰余を求め、ri(x)とする（ステップＳ１１）。具体的な手順は以下の通り。
lｉ＝hｉとなるｉがあれば、そういうｉに対するliei(x)をまとめた上でｆで割り、剰余をr0(x)とする。
li＜hiとなるei(x)は、それぞれｆで割り、剰余をri(x)とする。ri(x)＝0となるものがあれば、それをはずして添字を付け変え、改めて
【数４３】
2008262262.tif 000038
とする。（このｎは、元のものとは違うかもしれないことに注意。）
【００５２】
ｎ＝0か判定し（ステップＳ１２）、ｎ＝0なら、Ｐ＝r0(x)は通常の多項式となるので、ｆで割り切れるか否か判定し（ステップＳ１３）、割り切れれば「存在する」を返し、割り切れなければ「存在しない」を返して終了する。
第２の書換え：区間係数の正規化。Ｐを
【数４４】
2008262262.tif 000039
と書換える（ステップＳ１４）。ただし、
【数４５】
2008262262.tif 000040
である。
【００５３】
上記ステップＳ１の詳細例を図２に示す。
ステップＳ１０でｉ＝１，ｊ＝１，z0＝0に初期化する。
ステップＳ１１における実区間多項式の書換えは以下のように行なわれる。
ステップS111でli＝hiか判定し、否であればステップS112で入力された項順序によりei(x)をｆで割算して剰余ziを求める。
【００５４】
ステップS113で剰余ziが０かチェックし、否であればステップS114でziをrjに移し、li, hiをそれぞれLj, Hjに代入する。ステップS115でi＝ｎとなったかチェックし、否であればステップS116でｊを１歩進し、ステップS117でｉを１歩進してステップS111に戻る。
【００５５】
ステップS113で剰余がzi＝0の場合は、ステップS117でｉを１歩進してステップS111に戻る。ステップS111でli＝hiの場合は、区間の幅がないのでステップS118でz0にei(x)を加算してz0を更新し、ステップS115に進む。
【００５６】
ステップS115でi＝nの場合、ステップＳ１２でj＝0かチェックし、そうであればステップＳ１３でＰがｆで割り切れるか判定し、割り切れればＰに０が「存在する」を返して終了する。ステップＳ１３で割り切れない場合は、「存在しない」を返して終了する。ステップＳ１２でｊ＝０でない場合、ステップS121で、入力された項順序によりz0をｆで割った剰余r0(x)を求める。
【００５７】
ステップＳ１４では、以下の処理により区間係数の正規化を行なう。
ｎ←ｊ
Ｐ←p0(x)+[0, 1]p1(x)+…+[0, 1]pn(x)
ただし、p0(x)＝r0+L1r1+…+Lnrn、およびpi(x)＝(Hi-Li)ri(x)
【００５８】
以下、図１に戻る。
ステップＳ２：r0(x)がaff({0, r1(x), …, rn(x)})に入るか否かを判定する。
具体的には、連立一次方程式
t1r1(x)＋…＋tnrn(x)＝r0(x)                      (40)
に解t1, …, tnが存在するか否かを判定する。前述のようにr0(x)が上記集合aff({0, r1(x), …, rn(x)})に入るのと、連立一次方程式(40)が解を持つことは同値である。
【００５９】
存在すれば次のステップＳ３へ。
存在しなければ「存在しない」を返して終了。
ステップＳ３：aff({0, r1(x), …, rn(x)})の次元を計算し、その結果をｄとする。
【００６０】
具体的な計算方法としては、行列(r1, …, rn)の階数を計算してｄとする。
ステップＳ４：次の２つの条件
・Ｉは{1, 2, …, n}の部分集合で、要素の数はｄ−１、
・｛pi(x)｜i∈I}は一次独立な多項式からなる、
を満すすべてのＩに対し、不等式
【数４６】
2008262262.tif 000041
が成り立つなら、「存在する」を返して終了。
そうでないなら、「存在しない」を返して終了。
【００６１】
ここで、不等式(41)中のｎIは、aff(Ｐ)内の超平面
aff({pi｜ｉ∈Ｉ}∪{0})                          (42)
の法線ベクトルであり、左辺中の和において、ｐは、{pi(x)｜i∈I，<nＩ, pi(x)> ＜0}を走り、右辺中の和においては{pi(x)｜i∈I，<nI, pi(x)> ＞0}を走る。
【００６２】
図３はステップＳ４の詳細実施例を示す。
ステップＳ４１で、ステップＳ３で計算された次元ｄを使って{1, 2, …, n}の部分集合Ｉで、要素数がｄ−１、かつまだ調べてないＩがあるかチェックする。なければ０はＰに「存在する」を返し終了する。ステップＳ４１で調べていないＩが残っている場合は、{pi(x)｜i∈Ｉ}は一次独立かチェックする（ステップＳ４２）。一次独立でなければステップＳ４３で次のＩを選んでステップＳ４１に戻る。
【００６３】
一次独立であれば、ステップＳ４４で法線ベクトルｎiを計算する。次にステップＳ４５で不等式(41)が成り立つかチェックし、成り立てばステップＳ４３次のＩを選択してステップＳ４１に戻る。不等式(41)が成立しなければ、０はＰに「存在しない」を返して終了する。
【００６４】
なお、不等式(41)は不等式(35)においてｃ＝0とし、中辺を左右両辺に移行したものと同等である。このことは、式(24), (25)により表される２つのアフィン半空間をそれぞれ規定する２つの超平面の間に０が存在するか否か、つまり実区間多項式が実係数多項式ｆを擬因子として持つか否か、を判定することを意味している。ステップＳ４４においてnIを求める必要があるが、これには、例えばGram-Schmidtの直交化法を利用すればよい。その際、ベクトルの長さを１に正規化するステップをはずすことにより、有理演算のみでnIを求めることが可能である。具体的には以下のサブアルゴリズムの通りである。
【００６５】
《サブアルゴリズム》
入力：上記メインアルゴリズムのステップＳ４の条件を満すp1(x), …, pn(x)およびＩ。
出力：aff({pi(x)｜i∈Ｉ}∪{0})の法線ベクトル。
ステップS441：｛pi(x)｜i∈Ｉ}に、Gram-Schmidtの直交化法を適用する。ただし、ベクトルの長さを１に正規化するステップははずす。結果をqｉ(ｉ∈Ｉ)とする。
ステップS442：Ｊ＝{1, …, n}＼Ｉとする。
ステップS443：Ｊから一つの要素ｊを取り、Ｊ＝Ｊ＼{ｊ}とする。
ステップS444：次式のｑを計算する。
【数４７】
2008262262.tif 000042
ｑ≠0であればｑを返して終了。そうでなければステップS443へ戻る。
【００６６】
実区間多項式の実因子判定装置
図４は実区間多項式の実因子判定装置の実施例を示す。この実施例は、入力部１１と、主記憶装置１２と、剰余計算部１３と、実区間多項式書換え部１４と、アフィン包計算部１５と、不等式生成判定部１６と、出力部１７とから構成されている。剰余計算部１３と実区間多項式書換え部１４は剰余計算手段２１を構成している。また、アフィン包計算部１５と不等式生成判定部１６は剰余判定手段２２を構成している。
【００６７】
入力部１１には、実区間多項式Σ[l, h]e(x)、実係数多項式ｆ、項順序が入力され、それらを主記憶装置１２に格納する。剰余計算部１３は、主記憶装置１２より実区間多項式、実係数多項式、項順序を読み出し、実区間多項式に現れる多項式を実係数多項式ｆで、指定の項順序により割った剰余r(x)を計算し、実区間多項式書換部１４に渡す（ステップＳ１１）。
【００６８】
実区間多項式書換部１４は、主記憶装置１２から実区間多項式を読み出し、それを構成する多項式を剰余計算部１３から渡された多項式に置き換え、区間係数が一点となるものをまとめ、書き換えた実区間多項式をアフィン包計算部１５に渡す（ステップＳ１４）。
【００６９】
アフィン包計算部１５は、渡された実区間多項式に対し、その先頭の多項式r0(x)がaff{0,残りの多項式}に入るか否か判定する（ステップＳ２，Ｓ３）。判定結果が
・「入らない」であれば、それを出力部１７に渡し「存在しない」を出力させる。
・「入る」であれば、アフィン包の次元ｄを計算し、不等式生成判定部１６に渡す。
【００７０】
不等式生成判定部１６は、実区間多項式に対し、不等式(41)を生成し、それが成立するか否かを判定する（ステップＳ４）。
・すべての不等式が成立するならば、「存在する」と判定し、それを出力部１７より出力させる。
・成立しない不等式が存在すれば、「存在しない」と判定し、それを出力部１７から出力させる。
【００７１】
《判定の具体例》
例１
実区間多項式Ｐを
【数４８】
2008262262.tif 000043
とする。ただし、ｆ∈Ｒ[x, y]は、x−g(y)（g∈Ｒ[y]）の形とする。このとき、ｆがＰの擬因子であるか否か判定せよ。
この例では、ｘ＞ｙである辞書式順序を用いて各ei(x)をｆで割ると、ri(x)は、ｙのみの多項式となり、一変数の場合に帰着できる。
【００７２】
例２
以下の実区間多項式Ｐεと実多項式ｆに対し、ｆが擬因子となる最小のε≧0を求めよ。
Ｐε＝[2-ε, 2+ε]x３＋[-2-ε, -2+ε]x２y＋[-4-ε, -4+ε]xy２
＋[12-ε, 12+ε]x２＋[-10-ε, -10+ε]xy＋[-7-ε, -7+ε]y２
＋[14-ε, 14+ε]x＋[-21-ε, -21+ε]y＋[-9-ε, -9+ε]・１，
ｆ＝2x２−4yx＋7x−7y−18/5
ｐを実区間多項式Ｐεの中心の多項式、即ち、
2x３−2x２y−4xy２＋12x２−10xy−7y２＋14x−21y−9
とする。前記メインアルゴリズムに、パラメータεを残したままＰを入力することで、この例に対する計算をすることが可能であり、以下に示す通り、εの最小値は7/106である。
【００７３】
全次数順序を用いることとして、実区間多項式Ｐεの定義に現れる９個の単項式x３, x２y, xy２, x２, xy, y２, x, y,１をｆで割った剰余は、
【数４９】
2008262262.tif 000044
である。
これら９個の多項式が生成する部分空間の次元は６である。これら９個の多項式のうちから選んだ５個の多項式のなす集合計9!/(5!×4!)=126個のうち、124個は線形独立な多項式からなる集合である。
【００７４】
この124個の各集合に対し、不等式(41)を満すようなεの範囲を求める。すると、すべての不等式を満すεの最小値は7/106と分かる。実際、
【数５０】
2008262262.tif 000045
である。即ち、ε＝7/106に対しｑ∈Ｐεが成り立つ。
【００７５】
以上では説明を簡単にするために区間数の端点、多項式ei(x)の係数は有理数としたが、アルゴリズムの実行のためには四則演算および等号判定が実行できれば十分なので、例えば実代数的数（整数係数一次代数方程式の根となる実数）としてもそのまま通用する。
【００７６】
図５は、本発明による実区間多項式の実因子判定装置を一般的なコンピュータで実施する場合のブロック構成例を示す。
図５に示すように、キーボードなどが接続可能な入力部３１、液晶ディスプレイなどが接続可能な出力部３６、ＣＰＵ(Central Processing Unit)３３、ＲＡＭ３４、ＲＯＭ３５、及び主記憶装置３２がバス３７を介して互いに接続されている。また、必要に応じて、図示してないＣＤ−ＲＯＭなどの記録媒体を読み書きできる装置を設けてもよい。
【００７７】
主記憶装置３２には、この発明による実区間多項式の実因子判定を行なうための図１で説明した処理を記述したプログラム及びそのプログラムの処理に必要なデータなどが格納されている。また、このプログラムの処理によって得られる判定結果であるデータはＲＡＭ３４又は主記憶装置３２に記憶される。
【００７８】
入力部３１により実区間多項式の実因子判定プログラムの実行を命令すると、主記憶装置３２に格納されている実因子判定プログラムがＲＡＭ３４に読み込まれ、判定処理開始の準備ができる。入力部３１から実区間多項式、実係数多項式、項順序が入力され、主記憶部３２に格納される。以下、ＲＡＭ３４中のプログラムがＣＰＵ３３により順次実行されることにより、図１で説明した処理が実行され、判定結果が例えば出力部３６から表示装置に出力され、入力された実区間多項式が実係数多項式を実因子として持っているか否かの判定結果が表示される。
【００７９】
図１の処理を実行するプログラムはＲＯＭ３５などの記録媒体に予め記録されているものを使用してもよい。あるいは、必要に応じて図示してない手段により外部から主記憶装置３２に読み込んで私用してもよい。
【図面の簡単な説明】
【００８０】
【図１】この発明による実区間多項式の実因子判定処理フロー図。
【図２】図１におけるステップＳ１の詳細例を示すフロー図。
【図３】図１におけるステップＳ４の詳細例を示すフロー図。
【図４】この発明による実区間多項式の実因子判定装置の機能構成図。
【図５】この発明を実施するコンピュータの構成ブロック図。
【図１】
2008262262.tif 000053
【図２】
2008262262.tif 000054
【図３】
2008262262.tif 000055
【図４】
2008262262.tif 000056
【図５】
2008262262.tif 000057
【手続補正書】
【提出日】平成19年5月2日(2007.5.2)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項１１
【補正方法】変更
【補正の内容】
【請求項１１】
請求項９記載の実因子判定装置において、上記剰余から決まる実区間多項式を
【数４】
2008262262.tif 000058
と表すと、上記正規化は、
【数５】
2008262262.tif 000059
とおいて、
【数６】
2008262262.tif 000060
と書き換えることを特徴とする実区間多項式の実因子判定装置。