連立代数方程式の係数に対する許容誤差限界評価装置、方法、プログラム
【課題】連立方程式~f(x,y)=~g(x,y)=0が可解であることを保証する許容誤差限界を下から評価する技術を提供する。
【解決手段】体Ｋ上の二変数多項式f(x,y),g(x,y)∈Ｋ[x,y]を以下のように書く。f(x,y) = ad(y)xd + … + a1(y)x + a0(y),g(x,y) = be(y)xe + … + b1(y)x + b0(y)。ただし、ad(y), be(y)は定数0ではないとする。このとき、条件１[ad(y)とbe(y)が共通零点を持たない]および条件２[Resx(f,g)が定数ではない]を共に満たすならば、f(x,y)=g(x,y)=0には（複素数体上に）解が存在する。Resx(f,g)はf(x,y)とg(x,y)のxに関する終結式である。この証明された事実を係数に誤差を含む二変数多項式~f(x,y),~g(x,y)に適用する。
【解決手段】体Ｋ上の二変数多項式f(x,y),g(x,y)∈Ｋ[x,y]を以下のように書く。f(x,y) = ad(y)xd + … + a1(y)x + a0(y),g(x,y) = be(y)xe + … + b1(y)x + b0(y)。ただし、ad(y), be(y)は定数0ではないとする。このとき、条件１[ad(y)とbe(y)が共通零点を持たない]および条件２[Resx(f,g)が定数ではない]を共に満たすならば、f(x,y)=g(x,y)=0には（複素数体上に）解が存在する。Resx(f,g)はf(x,y)とg(x,y)のxに関する終結式である。この証明された事実を係数に誤差を含む二変数多項式~f(x,y),~g(x,y)に適用する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、連立代数方程式（以下、単に連立方程式ともいう）の係数に対する許容誤差限界評価技術に関する。
【背景技術】
【０００２】
体Ｋを実数体Ｒあるいは複素数体Ｃとする。Ｋ[x]をＫ上の一変数多項式環、Ｋ[x,y]をＫ上の二変数多項式環とする。
【０００３】
f(x,y),g(x,y)∈Ｋ[x,y]に対し、二元連立方程式f(x,y)=g(x,y)=0を複素数体Ｃ上で解くことを考える。f(x,y),g(x,y)の係数が誤差を含まなければ、終結式を用いる方法、グレブナー基底を用いる方法、Ｒｉｔ−Ｗｕ法などを用いればよい。
【０００４】
今、f(x,y),g(x,y)の係数が観測や測定により得られたため、あるいは、何らかの近似計算による処理を行った結果得られたため、測定誤差や近似誤差などにより係数が真の値からずれてしまったとする。すると、本来は解が存在する連立方程式f(x,y)=g(x,y)=0が、係数のずれのために解が存在しなくなる場合が生じる(連立方程式が可解でなくなる)。したがって、二変数多項式f(x,y),g(x,y)に対して、どの程度の誤差までなら係数がずれても連立方程式f(x,y)=g(x,y)=0が常に可解であるか、すなわち、解が存在するかを知りたい場合が生じる。例えばロボットなどの制御の安定性にこのような要請がある。
【０００５】
この問題は、より詳しくは次のように記述される。
f(x,y)=Σj,k ajkxjyk∈Ｋ[x,y], g(x,y)=Σm,n bmnxmyn∈Ｋ[x,y]に対して、下記条件１を満たす0<τ∈Ｒを求めよ。
[条件１]
T(f),T(g)をそれぞれ、f(x,y),g(x,y)の係数のうち誤差を含むものの添字の集合とする。f(x,y),g(x,y)について、少なくともいずれかの係数に誤差を含む任意の多項式をそれぞれ~f(x,y),~g(x,y)とし、式（１）のように表す。このとき、連立方程式（２）は解を持つ。なお、この明細書中において記号〜は直後の文字の頭上に附されるものとする。
【数１】
【０００６】
このようなτが存在する場合、最大のものをf(x,y)=g(x,y)=0の解が存在する許容誤差限界と呼ぶことにする（任意のτ>0が条件１を満たす場合は、許容誤差限界は無限大とする）。
【０００７】
連立一次方程式の場合、すなわちf(x,y),g(x,y)がそれぞれax+by+cの形の場合は、二変数に限らず三変数以上の場合も含めて、連立一次方程式を、係数行列Ａを用いてＡｘ→＝ｂ→と書き、Ａの行列ノルムや条件数を用いて上記τを評価することが可能である（例えば非特許文献１ 定理２．８）
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】G. W. Stewart, Ji-guang Sun, “Matrix Perturbation Theory”, Academic Press, 1990.
【発明の概要】
【発明が解決しようとする課題】
【０００９】
本発明の目的は、f(x,y),g(x,y)が一次の場合に限らず高次の場合も含め、連立方程式~f(x,y)=~g(x,y)=0が可解であることを保証する許容誤差限界^εを下から評価する、すなわち0＜ε≦^εを満たす、できるだけ大きなεを求める技術（連立代数方程式の係数に対する許容誤差限界評価技術）を提供することにある。
【課題を解決するための手段】
【００１０】
本発明の許容誤差限界評価技術は、次のとおりである。すなわち、Ｋを実数体Ｒまたは複素数体とし、Ｋ[x,y]をxとyを変数とするＫ上の二変数多項式環とし、二変数多項式h(x,y)=Σj,k cjkxjyk∈Ｋ[x,y]に対して、多項式h(x,y)をxの多項式と見たときの次数をΩ、多項式h(x,y)をyの多項式と見たときの次数をΘとして、有限集合S(h)をS(h)={(j,k)|0≦j＜Ω, 0≦k≦Θ}∪{(Ω,k)|あるk’≧kが存在してcΩk’≠0}と定義し、二変数多項式f(x,y)=Σj,k ajkxjyk∈Ｋ[x,y], g(x,y)=Σm,n bmnxmyn∈Ｋ[x,y]について、T(f)⊂S(f),T(g)⊂S(g)をそれぞれf(x,y),g(x,y)の係数のうち誤差を含むものの添字の集合とし、f(x,y),g(x,y)について、少なくともいずれかの係数に誤差を含む任意の多項式をそれぞれ
【数２】
としたとき、連立代数方程式~f(x,y)=~g(x,y)=0が複素数体上に解を持つような0<τ∈Ｒの最大値を許容誤差限界^εとして、当該許容誤差限界^εの下からの評価εを求める許容誤差限界評価技術であって、
二変数多項式f(x,y),g(x,y)は、
f(x,y) = ad(y)xd + … + a1(y)x + a0(y),
g(x,y) = be(y)xe + … + b1(y)x + b0(y)
と表したときに主係数ad(y)および主係数be(y)が定数0ではなく且つ主係数ad(y)および主係数be(y)は共通零点を持たないとし、二変数多項式f(x,y)とg(x,y)のxに関する終結式Resx(f,g)は定数ではないとし、予め定められた初期値をε0,1,ε0,2>0とし、予め定められた閾値をδ1,δ2>0として、
~f(x,y)と、~g(x,y)と、~f(x,y)をxの多項式と見たときの主係数
【数３】
と、~g(x,y)をxの多項式と見たときの主係数
【数４】
と、主係数A(y,sdk)と主係数B(y,ten)とのyに関する終結式
【数５】
と、~f(x,y)と~g(x,y)のxに関する終結式
【数６】
を計算し[多項式計算処理]、
多項式計算処理にて得られた終結式R1(sdk,ten)が定数であるか否かを判定し、終結式R1(sdk,ten)が定数であればε1を∞とし、終結式R1(sdk,ten)が定数でなければ、初期値ε0,1と閾値δ1を用いて、
＜Ｐ１＞：ε1=ε0,1, L=0とし、
＜Ｐ２＞：I(ε1)をＫが実数体のとき実閉区間[-ε1,ε1]としＫが複素数体のとき原点中心、半径ε1の閉円板{z∈C | |z|≦ε1}として、条件１[終結式R1(sdk,ten)において、変数sdk ((d,k)∈Ｔ(f)), ten ((e,n)∈Ｔ(g))に当該I(ε1)を代入して区間演算を行った結果の区間が０を含まない]を満たすか否かを判定し、条件１を満たさないならば＜Ｐ３＞へ移行し、条件１を満たすならばL=ε1と置き、ε1を2ε1で置き換え再度＜Ｐ２＞を実行し、
＜Ｐ３＞：U=ε1と置き、ε1を(ε1+L)/2で置き換え、
＜Ｐ４＞：＜Ｐ３＞で置き換えたε1について、条件１を満たすか否かを判定し、ε1が条件１を満たすならばL=ε1と置き、ε1を(ε1+U)/2で置き換え、そうでなければU=ε1と置き、ε1を(ε1+L)/2で置き換え、
＜Ｐ５＞： U-L≧δ1ならば＜Ｐ４＞に移行し、それ以外の場合には＜Ｐ６＞へ移行し、
＜Ｐ６＞：L≠0の場合にLの値をε1とする、
処理を行い[区間計算処理]、
終結式R2(y,sjk,tmn)をyの多項式と見たとき、
（Ｉ）定数項が０である、
（ＩＩ）あるj≧1が存在して、yjの係数は0ではない定数である、
の少なくとも一方が成り立つか否かを判定し、少なくとも一方が成り立つならばε2を∞とし、二つの条件（Ｉ）（ＩＩ）がどちらも成り立たない場合には、初期値ε0,2と閾値δ2を用いて、
＜Ｑ１＞：ε2=ε0,2, L=0とし、
＜Ｑ２＞：I(ε2)をＫが実数体のとき実閉区間[-ε2,ε2]としＫが複素数体のとき原点中心、半径ε2の閉円板{z∈C | |z|≦ε2}として、条件２[終結式R2(y,sjk,tmn)において、変数sjk ((j,k)∈Ｔ(f)), tmn((m,n)∈Ｔ(g))に当該I(ε2)を代入し、区間演算を行った結果の区間多項式が定数を含まない]を満たすか否かを判定し、条件２を満たさないならば＜Ｑ３＞へ移行し、条件２を満たすならばL=ε2と置き、ε2を2ε2で置き換え再度＜Ｑ２＞を実行し、
＜Ｑ３＞：U=ε2と置き、ε2を(ε2+L)/2で置き換え、
＜Ｑ４＞：＜Ｑ３＞で置き換えた後のε2について、条件２を満たすか否かを判定し、条件２を満たすならばL=ε2と置き、ε2を(ε2+U)/2で置き換え、そうでなければU=ε2と置き、ε2を(ε2+L)/2で置き換え、
＜Ｑ５＞：U-L≧δ2ならば＜Ｑ４＞に移行し、それ以外の場合には＜Ｑ６＞へ移行し、
＜Ｑ６＞：L≠0の場合にLの値をε2とする、
処理を行い[区間多項式計算処理]、
区間計算処理にて得られたε1と区間多項式計算処理にて得られたε2を取得し、小さい方の値min{ε1,ε2}を許容誤差限界の下からの評価εとして出力する[出力処理]。
【００１１】
あるいは、本発明の許容誤差限界評価技術は、次のとおりである。すなわち、Ｋを実数体Ｒまたは複素数体とし、Ｋ[x,y]をxとyを変数とするＫ上の二変数多項式環とし、二変数多項式h(x,y)=Σj,k cjkxjyk∈Ｋ[x,y]に対して、多項式h(x,y)をxの多項式と見たときの次数をΩ、多項式h(x,y)をyの多項式と見たときの次数をΘとして、有限集合S(h)をS(h)={(j,k)|0≦j＜Ω, 0≦k≦Θ}∪{(Ω,k)|あるk’≧kが存在してcΩk’≠0}、二変数多項式f(x,y)=Σj,k ajkxjyk∈Ｋ[x,y], g(x,y)=Σm,n bmnxmyn∈Ｋ[x,y]について、T(f)⊂S(f),T(g)⊂S(g)をそれぞれf(x,y),g(x,y)の係数のうち誤差を含むものの添字の集合とし、f(x,y),g(x,y)について、少なくともいずれかの係数に誤差を含む任意の多項式をそれぞれ
【数７】
としたとき、連立代数方程式~f(x,y)=~g(x,y)=0が複素数体上に解を持つような0<τ∈Ｒの最大値を許容誤差限界^εとして、当該許容誤差限界^εの下からの評価εを求める許容誤差限界評価技術であって、
二変数多項式f(x,y),g(x,y)は、
f(x,y) = ad(y)xd + … + a1(y)x + a0(y),
g(x,y) = be(y)xe + … + b1(y)x + b0(y)
と表したときに主係数ad(y)および主係数be(y)が定数0ではなく且つ主係数ad(y)および主係数be(y)は共通零点を持たないとし、二変数多項式f(x,y)とg(x,y)のxに関する終結式Resx(f,g)は定数ではないとし、予め定められた初期値をε0,1,ε0,2>0とし、予め定められた閾値をδ1,δ2>0として、
~f(x,y)と、~g(x,y)と、~f(x,y)をxの多項式と見たときの主係数
【数８】
と、~g(x,y)をxの多項式と見たときの主係数
【数９】
と、主係数A(y,sdk)と主係数B(y,ten)とのyに関する終結式
【数１０】
と、~f(x,y)と~g(x,y)のxに関する終結式
【数１１】
を計算し[多項式計算処理]、
多項式計算処理にて得られた終結式R1(sdk,ten)が定数であるか否かを判定し、終結式R1(sdk,ten)が定数であればε1を∞とし、終結式R1(sdk,ten)が定数でなければ、初期値ε0,1と閾値δ1を用いて、
＜Ｐ１＞：ε1=ε0,1, L=0とし、
＜Ｐ２＞：I(ε1)をＫが実数体のとき実閉区間[-ε1,ε1]としＫが複素数体のとき原点中心、半径ε1の閉円板{z∈C | |z|≦ε1}として、条件１[終結式R1(sdk,ten)において、変数sdk ((d,k)∈Ｔ(f)), ten ((e,n)∈Ｔ(g))に当該I(ε1)を代入して区間演算を行った結果の区間が０を含まない]を満たすか否かを判定し、条件１を満たさないならば＜Ｐ３＞へ移行し、条件１を満たすならばL=ε1と置き、ε1を2ε1で置き換え再度＜Ｐ２＞を実行し、
＜Ｐ３＞：U=ε1と置き、ε1を(ε1+L)/2で置き換え、
＜Ｐ４＞：＜Ｐ３＞で置き換えたε1について、条件１を満たすか否かを判定し、ε1が条件１を満たすならばL=ε1と置き、ε1を(ε1+U)/2で置き換え、そうでなければU=ε1と置き、ε1を(ε1+L)/2で置き換え、
＜Ｐ５＞： U-L≧δ1ならば＜Ｐ４＞に移行し、それ以外の場合には＜Ｐ６＞へ移行し、
＜Ｐ６＞：L≠0の場合にLの値をε1とする、
処理を行い[区間計算処理]、
区間計算処理にて得られたε1が∞であるか否かを判定し[判定処理]、
区間計算処理にて得られたε1が∞である場合に、終結式R2(y,sjk,tmn)をyの多項式と見たとき、
（Ｉ）定数項が０である、
（ＩＩ）あるj≧1が存在して、yjの係数は0ではない定数である、
の少なくとも一方が成り立つか否かを判定し、少なくとも一方が成り立つならばε2を∞とし、二つの条件（Ｉ）（ＩＩ）がどちらも成り立たなければ、初期値ε0,2と閾値δ2を用いて、
＜Ｑ１＞：ε2=ε0,2, L=0とし、
＜Ｑ２＞：I(ε2)をＫが実数体のとき実閉区間[-ε2,ε2]としＫが複素数体のとき原点中心、半径ε2の閉円板{z∈C | |z|≦ε2}として、条件２[終結式R2(y,sjk,tmn)において、変数sjk ((j,k)∈Ｔ(f)), tmn((m,n)∈Ｔ(g))に当該I(ε2)を代入し、区間演算を行った結果の区間多項式が定数を含まない]を満たすか否かを判定し、条件２を満たさないならば＜Ｑ３＞へ移行し、条件２を満たすならばL=ε2と置き、ε2を2ε2で置き換え再度＜Ｑ２＞を実行し、
＜Ｑ３＞：U=ε2と置き、ε2を(ε2+L)/2で置き換え、
＜Ｑ４＞：＜Ｑ３＞で置き換えた後のε2について、条件２を満たすか否かを判定し、条件２を満たすならばL=ε2と置き、ε2を(ε2+U)/2で置き換え、そうでなければU=ε2と置き、ε2を(ε2+L)/2で置き換え、
＜Ｑ５＞：U-L≧δ2ならば＜Ｑ４＞に移行し、それ以外の場合には＜Ｑ６＞へ移行し、
＜Ｑ６＞：L≠0の場合にLの値をε2とする、
処理を行い[第１区間多項式計算処理]、
区間計算処理にて得られたε1が∞でない場合に、I(ε1)をＫが実数体のとき実閉区間[-ε1,ε1]としＫが複素数体のとき原点中心、半径ε1の閉円板{z∈C | |z|≦ε1}として、多項式計算処理にて得られた終結式R2(y,sjk,tmn)において、変数sdk((d,k)∈T(f)), ten((e,n)∈T(g))にI(ε1)を代入し、区間演算を行った結果の区間多項式が定数を含むか否かを判定し、区間演算の結果の区間多項式が定数を含まない場合にはそのままε1を出力し、区間演算の結果の区間多項式が定数を含む場合には閾値δ2を用いて、
＜Ｗ１＞：L=0, U=ε1と置き、ε1を(ε1+L)/2で置き換え、
＜Ｗ２＞：＜Ｗ１＞で置き換えた後のε1について、条件２を満たすか否かを判定し、条件２を満たすならばL=ε1と置き、ε1を(ε1+U)/2で置き換え、そうでなければU=ε1と置き、ε1を(ε1+L)/2で置き換え、
＜Ｗ３＞：U-L≧δ2ならば＜Ｗ２＞に移行し、それ以外の場合には＜Ｗ４＞へ移行し、
＜Ｗ４＞：L≠0の場合にLの値をε1とする、
処理を行い[第２区間多項式計算処理]、
第１区間多項式計算処理にてε２が得られた場合には、当該ε2を許容誤差限界の下からの評価εとして出力し、第２区間多項式計算処理にてε1が得られた場合には、当該ε1を許容誤差限界の下からの評価εとして出力する[出力処理]。
【発明の効果】
【００１２】
本発明に拠れば、詳しくは後述する理論に基づくが、要すれば~f(x,y),~g(x,y)をxの多項式(係数はyの多項式となる)と見て、~f(x,y)と~g(x,y)の終結式を用いることにより、~f(x,y),~g(x,y)が一次の場合に限らず高次の場合も含め、連立方程式~f(x,y)=~g(x,y)=0が可解であることを保証する許容誤差限界を下から評価することができる。
【図面の簡単な説明】
【００１３】
【図１】実施形態１の許容誤差限界評価装置のハードウェア構成を示す機能ブロック図。
【図２】実施形態１の許容誤差限界評価処理のフローチャート。
【図３】実施形態２の許容誤差限界評価装置のハードウェア構成を示す機能ブロック図。
【図４】実施形態２の許容誤差限界評価処理のフローチャート。
【発明を実施するための形態】
【００１４】
《実施形態１》
図面を参照して本発明の実施形態１を説明する。図１は、実施形態１に係わる許容誤差限界評価装置１００のハードウェア構成を例示した構成ブロック図である。
図１に例示するように、許容誤差限界評価装置１００は、入力部１、多項式計算部２、区間計算部３、区間多項式計算部４、出力処理部５、記憶部６を有する。
図１、図２を参照して、本実施形態における許容誤差限界評価処理について説明する。
【００１５】
＜ステップＳ１−入力処理＞
入力部１には、多項式f(x,y),g(x,y)∈Ｋ[x,y]と、許容誤差限界の下からの評価εの初期値ε0,1,ε0,2>0、閾値δ1,δ2>0、および、f(x,y)の係数のうち誤差を有する係数の添字の集合T(f)⊂S(f)と、g(x,y)の係数のうち誤差を有する係数の添え字の集合T(g)⊂S(g)が入力される。なお、二変数多項式h(x,y)=Σj,k cjkxjyk∈Ｋ[x,y]に対して、多項式h(x,y)をxの多項式と見たときの次数をΩ、多項式h(x,y)をyの多項式と見たときの次数をΘとして、有限集合S(h)をS(h)={(j,k)|0≦j＜Ω, 0≦k≦Θ}∪{(Ω,k)|あるk’≧kが存在してcΩk’≠0}と定義する。
【００１６】
ここで、f(x,y)とg(x,y)は、xの多項式と見ることにより、
f(x,y) = ad(y)xd + … + a1(y)x + a0(y),
g(x,y) = be(y)xe + … + b1(y)x + b0(y)
の形式で表せるものであり、ad(y)およびbe(y)は定数0ではなく且つad(y)およびbe(y)は共通零点を持たないとする。また、f(x,y)とg(x,y)のxに関する終結式Resx(f,g)は定数ではないとする。終結式については後述する。
【００１７】
ad(y),be(y)が定数0であるか否かは、例えば「ad(y)のi次(0≦i≦d)の項の係数が全て0であり、かつ、be(y)のi次(0≦i≦e)の項の係数が全て0である」の成否の判定により達成される。また、ad(y)およびbe(y)が共通零点を持たないか否かは、例えばad(y)とbe(y)の終結式Res(ad,be)が0であるか否かの判定により達成される。
【００１８】
読み込んだ各多項式f(x,y)、g(x,y)及び各パラメータε0,1,ε0,2,δ1,δ2は記憶部６に記憶される。なお、各パラメータε0,1,ε0,2,δ1,δ2は入力部１から入力してもよいし、予め記憶部６内に初期値として登録しておいてもよい。また、許容誤差限界の下からの評価εの初期値ε0,1,ε0,2と閾値δ1,δ2は0より大きい任意の値を設定してよい。
【００１９】
＜ステップＳ２−多項式計算処理＞
多項式計算部２は、入力部１ないし記憶部６から受け取った多項式f(x,y),g(x,y)∈Ｋ[x,y]について、sjk ((j,k)∈T(f)), tmn ((m,n)∈T(g))を変数する多項式~f(x,y),~g(x,y)を計算し（式（３）参照）、さらに式（４）−（７）で定義されるＡ(・),Ｂ(・),Ｒ1(・),Ｒ2(・)を計算する。これら計算結果は記憶部６に記憶される。
【数１２】
【００２０】
ここで、A(・)は~f(x,y)をxの多項式と見たときの主係数（最高次の係数）であり、B(・)は~g(x,y)をxの多項式と見たときの主係数（最高次の係数）である。また、R１(・)は~f(x,y)をxの多項式と見たときの主係数と~g(x,y)をxの多項式と見たときの主係数とのyに関する終結式であり、R２(・)は~f(x,y)と~g(x,y)のxに関する終結式である。なお、例えば終結式R２(・)の右辺は正確には~f(x,y)と~g(x,y)が二変数多項式であることを明示すべくRx(~f(x,y),~g(x,y))と書くべきであろうものの、前後関係からそれが明らかな場合には特に明示せずに式（７）のように表すことに留意されたい。
【００２１】
終結式Res(f,g)は、一変数多項式f=Σdj=0 ajxj, g=Σek=0 bkxk∈Ｋ[x]（ただし、ad≠0,be≠0とする）とすると、シルベスター行列（８）の行列式で定義される。なお、aj,bkの現れるところ以外の成分は0である。このシルベスター行列（８）は(d+e)×(d+e)の正方行列で、ajの現れる行はe個,bkの現れる行はd個である。
【数１３】
【００２２】
＜ステップＳ３−区間計算処理＞
区間計算部３は、多項式計算部２が計算した~f(x,y)をxの多項式と見たときの主係数A(y,sdk)と~g(x,y)をxの多項式と見たときの主係数B(y,ten)とのyに関する終結式R1(sdk,ten)が定数であるか否かを判定する。区間計算部３は、R1(sdk,ten)が定数であればε1を∞とし、R1(sdk,ten)が定数でなければ記憶部６からε0,1とδ1を取得して、以下の手順によりε1を計算する。得られたε1は記憶部６に記憶される。
【００２３】
＜プロセスＰ１＞
ε1=ε0,1, L=0とする。
【００２４】
＜プロセスＰ２＞
下記条件２を満たすか否かを判定し、もし条件２を満たさないならばプロセスＰ３へ移行し、もし条件２を満たすならばL=ε1と置き、ε1を2ε1で置き換え再度プロセスＰ２を実行する。
[条件２]
終結式R1(sdk,ten)において、変数sdk ((d,k)∈T(f)), ten ((e,n)∈T(g))にI(ε1)を代入して区間演算を行った結果の区間が0を含まない。
【００２５】
＜プロセスＰ３＞
U=ε1と置き、ε1を(ε1+L)/2で置き換える。
【００２６】
＜プロセスＰ４＞
プロセスＰ３で置き換えたε1について、上記条件２を満たすか否かを判定し、ε1が条件２を満たすならばL=ε1と置き、ε1を(ε1+U)/2で置き換える。そうでなければU=ε1と置き、ε1を(ε1+L)/2で置き換える。
【００２７】
＜プロセスＰ５＞
もしU-L≧δ1ならばプロセスＰ４に処理を移行し、それ以外の場合にはプロセスＰ６へ処理を移行する。
【００２８】
＜プロセスＰ６＞
もし、L≠0ならばLの値をε1とする。もしL=0ならば「δ1の値が大き過ぎる」ことを通知するメッセージ（または値）を出力処理部５に送る（閾値δ1の値が大きすぎる場合には、許容誤差限界評価装置１００によって許容誤差限界εを評価することができないため、処理を終了（中断）する）。
【００２９】
上記手順において，プロセスＰ３以降では、Uは調べた値のうち上記条件２を満たさないものの中で最小の値である。もしL>0ならばLは調べた値のうち上記条件２を満たすものの中で最大の値である。δ1が大きいと上記条件２を満たす値が現れる前に終了条件U-L<δ1が成立してしまうことがあるので注意しなければならない。
【００３０】
また、プロセスＰ２におけるI(ε1)（ただしε1>0）はＫ＝Ｒ（実数体）のとき実閉区間[-ε1,ε1]とし、Ｋ＝Ｃ（複素数体）のとき原点中心、半径ε1の閉円板{z∈C | |z|≦ε1}とする。また、プロセスＰ２,Ｐ３に現れる区間演算については、Ｋ＝Ｒの場合は例えば参考文献１の「１.３.２ 区間解析」の節を、Ｋ＝Ｃの場合は例えば参考文献２を参照のこと。
（参考文献１）大石進一著, 「精度保証付き数値計算」, コロナ社, 2000.
（参考文献２）I. Gargantini and P. Henrici, “Circular arithmetic and the determination of polynomial zeros”, Numer. Math., Vol. 18, pp. 305--320, 1972.
【００３１】
＜ステップＳ４−区間多項式計算処理＞
区間多項式計算部４は、多項式計算部２が計算した~f(x,y)と~g(x,y)のxに関する終結式R2(y,sjk,tmn)をyの多項式と見たとき、
（Ｉ）定数項が0である、
（ＩＩ）あるj≧1が存在して、yjの係数は0ではない定数である、
の少なくとも一方が成り立つか否かを判定し、少なくとも一方が成り立つならばε2を∞とする。これら二つの条件（Ｉ）（ＩＩ）の少なくとも一方が成り立つ場合、後述の定理２における仮定が満たされる、つまりResx(f,g)の零点の存在が肯定されるので、入力条件を考慮すれば定理２の条件（２）が成立することが容易に分かる。二つの条件（Ｉ）（ＩＩ）がどちらも成り立たない場合には、記憶部６からε0,2とδ2を取得して以下の手順によりε2を計算する。
【００３２】
＜プロセスＱ１＞
ε2=ε0,2, L=0とする。
【００３３】
＜プロセスＱ２＞
下記条件３を満たすか否かを判定し、条件３を満たさないならばプロセスＱ３へ移行する。条件３を満たすならばL=ε2と置き、ε2を2ε2で置き換え再度プロセスＱ２を実行する。
[条件３]
終結式R2(y,sjk,tmn)において、変数sjk ((j,k)∈T(f)), tmn((m,n)∈T(g))にI(ε2)を代入し、区間演算を行った結果の区間多項式が定数を含まない（つまり区間演算の結果である区間多項式において、１次以上の係数である区間のうち少なくとも一つの区間は０を含まない）。
【００３４】
＜プロセスＱ３＞
U=ε2と置き、ε2を(ε2+L)/2で置き換える。
【００３５】
＜プロセスＱ４＞
プロセスＱ３で置き換えた後のε2について、上記条件３を満たすか否かを判定し、もし条件３を満たすならばL=ε2と置き、ε2を(ε2+U)/2で置き換える。そうでなければU=ε2と置き、ε2を(ε2+L)/2で置き換える。
【００３６】
＜プロセスＱ５＞
もしU-L≧δ2ならばプロセスＱ４に処理を移行し、それ以外の場合にはプロセスＱ６へ処理を移行する。
【００３７】
＜プロセスＱ６＞
もしL≠0ならばLの値をε2とする。このε2は記憶部６に記憶される。もしL=0ならば「δ2の値が大き過ぎる」ことを通知するメッセージ（または値）を出力処理部５に送る（閾値δ2の値が大きすぎる場合には、許容誤差限界評価装置１００によって許容誤差限界の下からの評価εを求めることができないため、処理を終了（中断）する）。
【００３８】
プロセスＱ２,Ｑ３に現れる区間の定義及び区間演算については、ステップ３の説明で記述したとおりである。
【００３９】
＜ステップＳ５−出力処理＞
出力処理部５は、区間計算部３が計算したε1と区間多項式計算部４が計算したε2を取得し、小さい方の値（min{ε1,ε2}）を許容誤差限界の下からの評価εとして出力する。
【００４０】
《実施形態２》
図面を参照して本発明の実施形態２を説明する。実施形態２に係わる許容誤差限界評価装置２００のハードウェア構成を図３に示す。
【００４１】
実施形態２は、実施形態１の許容誤差限界評価装置１００の各部の構成のうち、区間多項式計算部４を、判定部７０、第１区間多項式計算部７１、第２区間多項式計算部７２に置き換えたものである。
【００４２】
図３、図４を参照して、本実施形態における許容誤差限界評価処理について説明する。
【００４３】
ステップＳ１,Ｓ２,Ｓ３は実施形態１と同じである。
【００４４】
＜ステップＳ４ａ−判定処理＞
判定部７０は、区間計算部３が計算したε1が∞であるか否かを判定し、∞であればステップＳ４ｂへ処理を移行する制御を行い、それ以外の場合にはステップＳ４ｃへ処理を移行する制御を行う。
【００４５】
＜ステップＳ４ｂ−第１区間多項式計算処理＞
第１区間多項式計算部７１による処理は、実施形態１の区間多項式計算部４による処理と同じであるから重複説明を省略する。
【００４６】
＜ステップＳ４ｃ−第２区間多項式計算処理＞
第２区間多項式計算部７２は、まず、多項式計算部２が計算した終結式R2(y,sjk,tmn)において、変数sdk((d,k)∈T(f)), ten((e,n)∈T(g))にI(ε1)を代入し、区間演算を行った結果の区間多項式が定数を含むか否か（つまり区間演算の結果である区間多項式において、１次以上の係数の区間がすべて０を含むか否か）を判定する。区間演算の結果の区間多項式が定数を含まない場合にはε1を出力処理部５へ送る。
【００４７】
第２区間多項式計算部７２は、区間演算を行った結果の区間多項式が定数を含む場合には、記憶部６からδ2を取得して、以下の手順によりε1を計算し、求めたε1を出力処理部５へ送る。
【００４８】
＜プロセスＷ１＞
L=0, U=ε1と置き、ε1を(ε1+L)/2で置き換える。
【００４９】
＜プロセスＷ２＞
プロセスＷ１で置き換えた後のε1について、上記条件３を満たすか否かを判定し、もし条件３を満たすならばL=ε1と置き、ε1を(ε1+U)/2で置き換える。そうでなければU=ε1と置き、ε1を(ε1+L)/2で置き換える。
【００５０】
＜プロセスＷ３＞
もしU-L≧δ2ならばプロセスＷ２に処理を移行し、それ以外の場合にはプロセスＷ４へ処理を移行する。
【００５１】
＜プロセスＷ４＞
もしL≠0ならばLの値をε1とする。このε1は記憶部６に記憶される。もしL=0ならば「δ2の値が大き過ぎる」ことを通知するメッセージ（または値）を出力処理部５に送る。
【００５２】
＜ステップ５ａ−出力処理＞
第２区間多項式計算部７２は区間計算部３が計算したε１の値を更新する形で計算を行うためε２の値は存在しない。したがって、第１区間多項式計算部７１からε２の値が出力された場合には、出力処理部５は当該ε2を許容誤差限界の下からの評価εとして出力する。
一方、第２区間多項式計算部７２からε1の値が出力された場合には、出力処理部５は当該ε1を許容誤差限界の下からの評価εとして出力する。
【００５３】
《理論》
一変数多項式に関する終結式に関しては、定理１が知られている（詳細は、例えば参考文献３の補題２.２６を参照のこと）。
（参考文献３）野呂正行, 横山和弘, 「グレブナー基底の計算基礎篇」, 東京大学出版会, ２００３．
[定理１]
Res(f,g)=0となる必要十分条件は、f(x)とg(x)の共通零点が存在すること、すなわち、ある複素数αが存在してf(α)=g(α)=0となることである。
【００５４】
次に、二変数多項式f(x,y),g(x,y)∈Ｋ[x,y]について、f(x,y),g(x,y)をxの多項式と見て、
f(x,y) = ad(y)xd + … + a1(y)x + a0(y),
g(x,y) = be(y)xe + … + b1(y)x + b0(y),
と表し、f(x,y)とg(x,y)の終結式を考える。ただし、ad(y),be(y)は定数0ではないとする。この終結式は上述の終結式の定義においてシルベスター行列（８）の成分がＫの元ではなく、Ｋ[x]に属する多項式となったものである。これをf(x,y),g(x,y)のxに関する終結式と呼び、Resx(f,g)と書く。
【００５５】
二変数多項式に対する終結式に関しては、定理２が知られている。
[定理２]
複素数βをResx(f,g)の零点とする。このとき、次のいずれかが成り立つ。
（１）ad(β)=be(β)=0
（２）ある複素数αが存在して、f(α,β)=g(α,β)=0
【００５６】
参考文献３の補題２.３１では、定理２の（１）が「ad(β)=0またはbe(β)=0」となっているが、より強い上記定理２が成り立つことが知られている。証明は以下の通り。
[証明]
ad(β),be(β)のうち少なくとも一方が0ではないとき、上記（２）が成り立つことを言えばよい。
どちらでも証明は同じなので、ad(β)≠0と仮定する。
（Ａ）be(β)≠0の場合、参考文献３の補題２．３１の証明より主張は成り立つ。
（Ｂ）be(β)=…=bu-1(β)=0, bu(β)≠0の場合、h(x)=Σuk=0bk(β)xkと置くと、終結式の定義より、
0=Resx(f,g)(β)=ad(β)e-uRes(f(x,β),h(x))
が成立する。
ここで、ad(β)≠0よりRes(f(x,β),h(x))=0である。また、f(x,β)の最高次の係数ad(β), h(x)の最高次の係数bu(β)はどちらも0ではないから、定理１より或る複素数αが存在してf(α,β)=h(α)=0となる。h(x)=g(x,β)だから、f(α,β)=g(α,β)=0が成り立つ。
（Ｃ）be(β)=…=b0(β)=0の場合、g(x,β)は恒等的に0である。よって、f(x,β)(仮定ad(β)≠0より定数ではない)の任意の零点αに対し、f(α,β)=g(α,β)=0が成り立つ。
(証明終)
【００５７】
定理２より系１が成り立つのは明らかである。
[系１]
f(x,y),g(x,y)∈Ｋ[x,y]を以下のように書く。
f(x,y) = ad(y)xd + … + a1(y)x + a0(y),
g(x,y) = be(y)xe + … + b1(y)x + b0(y).
ただし、ad(y), be(y)は定数0ではないとする。
このとき、下記条件（１）および（２）を共に満たすならば、f(x,y)=g(x,y)=0には（複素数体上に）解が存在する。
（１）ad(y)とbe(y)が共通零点を持たない。
（２）Resx(f,g)が定数ではない。
【００５８】
定理１、定理２および系１から、許容誤差限界の下からの評価εを求めることができる。
【００５９】
(*1)まず、系１の条件（１）に関する成否について。
入力されるf(x,y)及びg(x,y)について、ad(y)とbe(y)はいずれも0ではなく、共通零点を持たないことを仮定しているから、Res(ad,be)≠0である。式（９）で与えられる任意の~f(x,y),~g(x,y)に対し、~f(x,y)をxの多項式と見たときの主係数を式（１０）、~g(x,y)をxの多項式と見たときの主係数を式（１１）と置くと、~ad(y),~be(y)においてT(f),T(g)に属する添え字を持つ係数は変数sdk,ten∈Ｋによる連続関数だから或るε1>0が存在し、式（１２）と式（１３）を満足する式（９）の任意の~f(x,y),~g(x,y)について、Res(~ad,~be)≠0、すわなち~ad(y)と~be(y)は共通零点を持たないことが言える。
このε1の算出は上記実施形態中のステップ３の処理に該当する。
【数１４】
【００６０】
(*2)次に、系１の条件（２）に関する成否について。
入力されるf(x,y)及びg(x,y)について、Resx(f,g)は定数ではないことを仮定しているから、Resx(~f,~g)=ΣDj=0 ~rjyj(~rD≠0)と書くと、各係数~rjは、~ajk(y) ((j,k)∈S(f)),~bmn(y) ((m,n)∈S(g))を含み得て、さらに~ajk(y) ((j,k) ∈T(f)),~bmn(y) ((m,n) ∈T(g))は変数sjk,tmn∈Ｋによる連続関数であるから、各係数~rjは変数sjk,tmn∈Ｋによる連続関数と言えることにより或るε2>0が存在し、式（１４）と式（１５）を満足する式（９）の任意の~f(x,y),~g(x,y)について、或るj(1≦j≦D)が存在して~rj(y)≠0である、すなわちResx(~f,~g)は定数ではないことが言える。
このε2の算出は上記実施形態１のステップ４、上記実施形態２のステップ４ａ-４ｃの各処理に該当する。
【数１５】
【００６１】
よって、ε=min{ε1,ε2}とすると、定理２より式（１６）の任意の~f(x,y)および~g(x,y)について連立方程式~f(x,y)=~g(x,y)=0には解が存在することが言える。このときεが求めるべき許容誤差限界の下からの評価である。
【数１６】
【００６２】
＜補記＞
本発明は上述の実施形態に限定されるものではなく、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。また、上記実施形態において説明した処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されるとしてもよい。
【００６３】
また、上記実施形態において説明したハードウェアエンティティ（許容誤差限界評価装置）における処理機能をコンピュータによって実現する場合、ハードウェアエンティティが有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記ハードウェアエンティティにおける処理機能がコンピュータ上で実現される。
【００６４】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ（Random Access Memory）、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）等を、光磁気記録媒体として、ＭＯ（Magneto-Optical disc）等を、半導体メモリとしてＥＥＰ−ＲＯＭ（Electronically Erasable and Programmable-Read Only Memory）等を用いることができる。
【００６５】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００６６】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００６７】
なお、本発明の細部においては、数値計算処理のみならず有理式や多項式などの数式処理も必要となるが、数値計算処理および数式処理自体は、周知技術と同様にして達成されるので、その演算処理方法などの詳細な説明は省略した（この点の技術水準を示す数式処理が可能なソフトウェアとしては、例えば、Risa/Asir、Maple（登録商標）、MATHEMATICA（登録商標第2312968号）、Gnuplotなどが挙げられる。Risa/Asirについては、例えばインターネット〈URL:http://www.math.kobe-u.ac.jp/Asir/asir-ja.html〉［平成22年3月11日検索］を参照のこと。Mapleについては、例えばインターネット〈URL:http://www.cybernet.co.jp/maple/〉［平成22年3月11日検索］を参照のこと。Gnuplotについては、例えばインターネット〈URL: http://www.gnuplot.info/〉［平成22年3月11日検索］を参照のこと。）。
【実施例】
【００６８】
[例１]
K=R, f=x2+y2-1, g=x+y-1とし、fの係数は誤差を含まず、gの係数のみ誤差を含むものとする。すなわち、T(f)=φ（空集合）、T(g)={(1,0),(0,1),(0,0)}である。ε0,1=ε0,2=1とし、（１）δ1=δ2=1/100、（２）δ1=δ2=1/10000の２つの場合について、実施形態１の許容誤差限界評価装置により許容誤差限界の下からの評価εを求める。なお、区間演算において、区間の端点は有理数とし、端点間の計算は正確に行うものとする。
【００６９】
＜ステップＳ１＞
上述のとおり設定された多項式f,gと、評価εの初期値ε0,1=ε0,2と、閾値δ1,δ2、添字集合T(f),T(g)が入力される。
【００７０】
＜ステップＳ２＞
計算結果である~f, ~g, R1, R2 は以下の通りである。
【数１７】
【００７１】
＜ステップＳ３＞
R1が定数なので、ε1=∞となる。
【００７２】
＜ステップＳ４＞
（１）の場合：ε2=53/128である。
（２）の場合：ε2=3393/8192である。
【００７３】
＜ステップＳ５＞
（１）の場合：min{∞,53/128}=53/128より、ε=53/128となる。
（２）の場合：min{∞,3393/8192}=3393/8192より、ε=3393/8192となる。
【００７４】
なお、この例の場合は、区間計算部３が計算したε1が∞なので、実施形態２に拠っても、途中経過、出力とも上記と同じとなる。
【００７５】
[例２]
K=R, f=x2y+xy2-1, g=xy+x+y+1とし、T(f)={(2,1),(1,2)}, T(g)={(1,1),(1,0),(0,1)}とする。ε0,1=ε0,2=1とし、（１）δ1=δ2=1/100、（２）δ1=δ2=1/10000のそれぞれの場合について、実施形態１の許容誤差限界評価装置により許容誤差限界の下からの評価εを求める。なお、区間演算において、区間の端点は有理数とし、端点間の計算は正確に行うものとする。
【００７６】
＜ステップＳ１＞
上述のとおり設定された多項式f,gと、評価εの初期値ε0,1=ε0,2と、閾値δ1,δ2、添字集合T(f),T(g)が入力される。
【００７７】
＜ステップＳ２＞
計算結果である~f, ~g, R1, R2は以下の通り。
【数１８】
【００７８】
＜ステップＳ３＞
（１）の場合：ε1=53/128である。
（２）の場合：ε1=3393/8192である。
【００７９】
＜ステップＳ４＞
（１）の場合：ε2=33/128である。
（２）の場合：ε2=2129/8192である。
【００８０】
＜ステップＳ５＞
（１）の場合：min{53/128,33/128}=33/128より、ε=33/128となる。
（２）の場合：min{3393/8192,2129/8192}=2129/8192より、ε=2129/8192となる。
【００８１】
なお、この例の場合、実施形態２に拠ると、（１）の場合はε=265/1024、（２）の場合はε=4360005/16777216が出力となる。
【産業上の利用可能性】
【００８２】
連立代数方程式の係数の誤差に関する可解性は、ロボットなどの制御の安定性と密接に関係がある。例えば、ロボットアームの制御では、ロボットアームを構成する各関節の角度と手先位置との関係を連立方程式で表すことができ、これを解くことにより、所望の手先位置に到達させるための各関節角度を求める。しかし、このときの連立方程式には、例えばロボットの各関節間の長さのように何らかの計測装置で計測した値が係数として使用されることが多い。すると、係数には誤差が含まれてしまうため、連立方程式の可解性の問題が生じる。本発明によると、連立方程式が可解であることを保証する許容誤差限界を求めることができるので、これにより測定誤差がどの程まで許容されるかを知ることができる。
【技術分野】
【０００１】
本発明は、連立代数方程式（以下、単に連立方程式ともいう）の係数に対する許容誤差限界評価技術に関する。
【背景技術】
【０００２】
体Ｋを実数体Ｒあるいは複素数体Ｃとする。Ｋ[x]をＫ上の一変数多項式環、Ｋ[x,y]をＫ上の二変数多項式環とする。
【０００３】
f(x,y),g(x,y)∈Ｋ[x,y]に対し、二元連立方程式f(x,y)=g(x,y)=0を複素数体Ｃ上で解くことを考える。f(x,y),g(x,y)の係数が誤差を含まなければ、終結式を用いる方法、グレブナー基底を用いる方法、Ｒｉｔ−Ｗｕ法などを用いればよい。
【０００４】
今、f(x,y),g(x,y)の係数が観測や測定により得られたため、あるいは、何らかの近似計算による処理を行った結果得られたため、測定誤差や近似誤差などにより係数が真の値からずれてしまったとする。すると、本来は解が存在する連立方程式f(x,y)=g(x,y)=0が、係数のずれのために解が存在しなくなる場合が生じる(連立方程式が可解でなくなる)。したがって、二変数多項式f(x,y),g(x,y)に対して、どの程度の誤差までなら係数がずれても連立方程式f(x,y)=g(x,y)=0が常に可解であるか、すなわち、解が存在するかを知りたい場合が生じる。例えばロボットなどの制御の安定性にこのような要請がある。
【０００５】
この問題は、より詳しくは次のように記述される。
f(x,y)=Σj,k ajkxjyk∈Ｋ[x,y], g(x,y)=Σm,n bmnxmyn∈Ｋ[x,y]に対して、下記条件１を満たす0<τ∈Ｒを求めよ。
[条件１]
T(f),T(g)をそれぞれ、f(x,y),g(x,y)の係数のうち誤差を含むものの添字の集合とする。f(x,y),g(x,y)について、少なくともいずれかの係数に誤差を含む任意の多項式をそれぞれ~f(x,y),~g(x,y)とし、式（１）のように表す。このとき、連立方程式（２）は解を持つ。なお、この明細書中において記号〜は直後の文字の頭上に附されるものとする。
【数１】
【０００６】
このようなτが存在する場合、最大のものをf(x,y)=g(x,y)=0の解が存在する許容誤差限界と呼ぶことにする（任意のτ>0が条件１を満たす場合は、許容誤差限界は無限大とする）。
【０００７】
連立一次方程式の場合、すなわちf(x,y),g(x,y)がそれぞれax+by+cの形の場合は、二変数に限らず三変数以上の場合も含めて、連立一次方程式を、係数行列Ａを用いてＡｘ→＝ｂ→と書き、Ａの行列ノルムや条件数を用いて上記τを評価することが可能である（例えば非特許文献１ 定理２．８）
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】G. W. Stewart, Ji-guang Sun, “Matrix Perturbation Theory”, Academic Press, 1990.
【発明の概要】
【発明が解決しようとする課題】
【０００９】
本発明の目的は、f(x,y),g(x,y)が一次の場合に限らず高次の場合も含め、連立方程式~f(x,y)=~g(x,y)=0が可解であることを保証する許容誤差限界^εを下から評価する、すなわち0＜ε≦^εを満たす、できるだけ大きなεを求める技術（連立代数方程式の係数に対する許容誤差限界評価技術）を提供することにある。
【課題を解決するための手段】
【００１０】
本発明の許容誤差限界評価技術は、次のとおりである。すなわち、Ｋを実数体Ｒまたは複素数体とし、Ｋ[x,y]をxとyを変数とするＫ上の二変数多項式環とし、二変数多項式h(x,y)=Σj,k cjkxjyk∈Ｋ[x,y]に対して、多項式h(x,y)をxの多項式と見たときの次数をΩ、多項式h(x,y)をyの多項式と見たときの次数をΘとして、有限集合S(h)をS(h)={(j,k)|0≦j＜Ω, 0≦k≦Θ}∪{(Ω,k)|あるk’≧kが存在してcΩk’≠0}と定義し、二変数多項式f(x,y)=Σj,k ajkxjyk∈Ｋ[x,y], g(x,y)=Σm,n bmnxmyn∈Ｋ[x,y]について、T(f)⊂S(f),T(g)⊂S(g)をそれぞれf(x,y),g(x,y)の係数のうち誤差を含むものの添字の集合とし、f(x,y),g(x,y)について、少なくともいずれかの係数に誤差を含む任意の多項式をそれぞれ
【数２】
としたとき、連立代数方程式~f(x,y)=~g(x,y)=0が複素数体上に解を持つような0<τ∈Ｒの最大値を許容誤差限界^εとして、当該許容誤差限界^εの下からの評価εを求める許容誤差限界評価技術であって、
二変数多項式f(x,y),g(x,y)は、
f(x,y) = ad(y)xd + … + a1(y)x + a0(y),
g(x,y) = be(y)xe + … + b1(y)x + b0(y)
と表したときに主係数ad(y)および主係数be(y)が定数0ではなく且つ主係数ad(y)および主係数be(y)は共通零点を持たないとし、二変数多項式f(x,y)とg(x,y)のxに関する終結式Resx(f,g)は定数ではないとし、予め定められた初期値をε0,1,ε0,2>0とし、予め定められた閾値をδ1,δ2>0として、
~f(x,y)と、~g(x,y)と、~f(x,y)をxの多項式と見たときの主係数
【数３】
と、~g(x,y)をxの多項式と見たときの主係数
【数４】
と、主係数A(y,sdk)と主係数B(y,ten)とのyに関する終結式
【数５】
と、~f(x,y)と~g(x,y)のxに関する終結式
【数６】
を計算し[多項式計算処理]、
多項式計算処理にて得られた終結式R1(sdk,ten)が定数であるか否かを判定し、終結式R1(sdk,ten)が定数であればε1を∞とし、終結式R1(sdk,ten)が定数でなければ、初期値ε0,1と閾値δ1を用いて、
＜Ｐ１＞：ε1=ε0,1, L=0とし、
＜Ｐ２＞：I(ε1)をＫが実数体のとき実閉区間[-ε1,ε1]としＫが複素数体のとき原点中心、半径ε1の閉円板{z∈C | |z|≦ε1}として、条件１[終結式R1(sdk,ten)において、変数sdk ((d,k)∈Ｔ(f)), ten ((e,n)∈Ｔ(g))に当該I(ε1)を代入して区間演算を行った結果の区間が０を含まない]を満たすか否かを判定し、条件１を満たさないならば＜Ｐ３＞へ移行し、条件１を満たすならばL=ε1と置き、ε1を2ε1で置き換え再度＜Ｐ２＞を実行し、
＜Ｐ３＞：U=ε1と置き、ε1を(ε1+L)/2で置き換え、
＜Ｐ４＞：＜Ｐ３＞で置き換えたε1について、条件１を満たすか否かを判定し、ε1が条件１を満たすならばL=ε1と置き、ε1を(ε1+U)/2で置き換え、そうでなければU=ε1と置き、ε1を(ε1+L)/2で置き換え、
＜Ｐ５＞： U-L≧δ1ならば＜Ｐ４＞に移行し、それ以外の場合には＜Ｐ６＞へ移行し、
＜Ｐ６＞：L≠0の場合にLの値をε1とする、
処理を行い[区間計算処理]、
終結式R2(y,sjk,tmn)をyの多項式と見たとき、
（Ｉ）定数項が０である、
（ＩＩ）あるj≧1が存在して、yjの係数は0ではない定数である、
の少なくとも一方が成り立つか否かを判定し、少なくとも一方が成り立つならばε2を∞とし、二つの条件（Ｉ）（ＩＩ）がどちらも成り立たない場合には、初期値ε0,2と閾値δ2を用いて、
＜Ｑ１＞：ε2=ε0,2, L=0とし、
＜Ｑ２＞：I(ε2)をＫが実数体のとき実閉区間[-ε2,ε2]としＫが複素数体のとき原点中心、半径ε2の閉円板{z∈C | |z|≦ε2}として、条件２[終結式R2(y,sjk,tmn)において、変数sjk ((j,k)∈Ｔ(f)), tmn((m,n)∈Ｔ(g))に当該I(ε2)を代入し、区間演算を行った結果の区間多項式が定数を含まない]を満たすか否かを判定し、条件２を満たさないならば＜Ｑ３＞へ移行し、条件２を満たすならばL=ε2と置き、ε2を2ε2で置き換え再度＜Ｑ２＞を実行し、
＜Ｑ３＞：U=ε2と置き、ε2を(ε2+L)/2で置き換え、
＜Ｑ４＞：＜Ｑ３＞で置き換えた後のε2について、条件２を満たすか否かを判定し、条件２を満たすならばL=ε2と置き、ε2を(ε2+U)/2で置き換え、そうでなければU=ε2と置き、ε2を(ε2+L)/2で置き換え、
＜Ｑ５＞：U-L≧δ2ならば＜Ｑ４＞に移行し、それ以外の場合には＜Ｑ６＞へ移行し、
＜Ｑ６＞：L≠0の場合にLの値をε2とする、
処理を行い[区間多項式計算処理]、
区間計算処理にて得られたε1と区間多項式計算処理にて得られたε2を取得し、小さい方の値min{ε1,ε2}を許容誤差限界の下からの評価εとして出力する[出力処理]。
【００１１】
あるいは、本発明の許容誤差限界評価技術は、次のとおりである。すなわち、Ｋを実数体Ｒまたは複素数体とし、Ｋ[x,y]をxとyを変数とするＫ上の二変数多項式環とし、二変数多項式h(x,y)=Σj,k cjkxjyk∈Ｋ[x,y]に対して、多項式h(x,y)をxの多項式と見たときの次数をΩ、多項式h(x,y)をyの多項式と見たときの次数をΘとして、有限集合S(h)をS(h)={(j,k)|0≦j＜Ω, 0≦k≦Θ}∪{(Ω,k)|あるk’≧kが存在してcΩk’≠0}、二変数多項式f(x,y)=Σj,k ajkxjyk∈Ｋ[x,y], g(x,y)=Σm,n bmnxmyn∈Ｋ[x,y]について、T(f)⊂S(f),T(g)⊂S(g)をそれぞれf(x,y),g(x,y)の係数のうち誤差を含むものの添字の集合とし、f(x,y),g(x,y)について、少なくともいずれかの係数に誤差を含む任意の多項式をそれぞれ
【数７】
としたとき、連立代数方程式~f(x,y)=~g(x,y)=0が複素数体上に解を持つような0<τ∈Ｒの最大値を許容誤差限界^εとして、当該許容誤差限界^εの下からの評価εを求める許容誤差限界評価技術であって、
二変数多項式f(x,y),g(x,y)は、
f(x,y) = ad(y)xd + … + a1(y)x + a0(y),
g(x,y) = be(y)xe + … + b1(y)x + b0(y)
と表したときに主係数ad(y)および主係数be(y)が定数0ではなく且つ主係数ad(y)および主係数be(y)は共通零点を持たないとし、二変数多項式f(x,y)とg(x,y)のxに関する終結式Resx(f,g)は定数ではないとし、予め定められた初期値をε0,1,ε0,2>0とし、予め定められた閾値をδ1,δ2>0として、
~f(x,y)と、~g(x,y)と、~f(x,y)をxの多項式と見たときの主係数
【数８】
と、~g(x,y)をxの多項式と見たときの主係数
【数９】
と、主係数A(y,sdk)と主係数B(y,ten)とのyに関する終結式
【数１０】
と、~f(x,y)と~g(x,y)のxに関する終結式
【数１１】
を計算し[多項式計算処理]、
多項式計算処理にて得られた終結式R1(sdk,ten)が定数であるか否かを判定し、終結式R1(sdk,ten)が定数であればε1を∞とし、終結式R1(sdk,ten)が定数でなければ、初期値ε0,1と閾値δ1を用いて、
＜Ｐ１＞：ε1=ε0,1, L=0とし、
＜Ｐ２＞：I(ε1)をＫが実数体のとき実閉区間[-ε1,ε1]としＫが複素数体のとき原点中心、半径ε1の閉円板{z∈C | |z|≦ε1}として、条件１[終結式R1(sdk,ten)において、変数sdk ((d,k)∈Ｔ(f)), ten ((e,n)∈Ｔ(g))に当該I(ε1)を代入して区間演算を行った結果の区間が０を含まない]を満たすか否かを判定し、条件１を満たさないならば＜Ｐ３＞へ移行し、条件１を満たすならばL=ε1と置き、ε1を2ε1で置き換え再度＜Ｐ２＞を実行し、
＜Ｐ３＞：U=ε1と置き、ε1を(ε1+L)/2で置き換え、
＜Ｐ４＞：＜Ｐ３＞で置き換えたε1について、条件１を満たすか否かを判定し、ε1が条件１を満たすならばL=ε1と置き、ε1を(ε1+U)/2で置き換え、そうでなければU=ε1と置き、ε1を(ε1+L)/2で置き換え、
＜Ｐ５＞： U-L≧δ1ならば＜Ｐ４＞に移行し、それ以外の場合には＜Ｐ６＞へ移行し、
＜Ｐ６＞：L≠0の場合にLの値をε1とする、
処理を行い[区間計算処理]、
区間計算処理にて得られたε1が∞であるか否かを判定し[判定処理]、
区間計算処理にて得られたε1が∞である場合に、終結式R2(y,sjk,tmn)をyの多項式と見たとき、
（Ｉ）定数項が０である、
（ＩＩ）あるj≧1が存在して、yjの係数は0ではない定数である、
の少なくとも一方が成り立つか否かを判定し、少なくとも一方が成り立つならばε2を∞とし、二つの条件（Ｉ）（ＩＩ）がどちらも成り立たなければ、初期値ε0,2と閾値δ2を用いて、
＜Ｑ１＞：ε2=ε0,2, L=0とし、
＜Ｑ２＞：I(ε2)をＫが実数体のとき実閉区間[-ε2,ε2]としＫが複素数体のとき原点中心、半径ε2の閉円板{z∈C | |z|≦ε2}として、条件２[終結式R2(y,sjk,tmn)において、変数sjk ((j,k)∈Ｔ(f)), tmn((m,n)∈Ｔ(g))に当該I(ε2)を代入し、区間演算を行った結果の区間多項式が定数を含まない]を満たすか否かを判定し、条件２を満たさないならば＜Ｑ３＞へ移行し、条件２を満たすならばL=ε2と置き、ε2を2ε2で置き換え再度＜Ｑ２＞を実行し、
＜Ｑ３＞：U=ε2と置き、ε2を(ε2+L)/2で置き換え、
＜Ｑ４＞：＜Ｑ３＞で置き換えた後のε2について、条件２を満たすか否かを判定し、条件２を満たすならばL=ε2と置き、ε2を(ε2+U)/2で置き換え、そうでなければU=ε2と置き、ε2を(ε2+L)/2で置き換え、
＜Ｑ５＞：U-L≧δ2ならば＜Ｑ４＞に移行し、それ以外の場合には＜Ｑ６＞へ移行し、
＜Ｑ６＞：L≠0の場合にLの値をε2とする、
処理を行い[第１区間多項式計算処理]、
区間計算処理にて得られたε1が∞でない場合に、I(ε1)をＫが実数体のとき実閉区間[-ε1,ε1]としＫが複素数体のとき原点中心、半径ε1の閉円板{z∈C | |z|≦ε1}として、多項式計算処理にて得られた終結式R2(y,sjk,tmn)において、変数sdk((d,k)∈T(f)), ten((e,n)∈T(g))にI(ε1)を代入し、区間演算を行った結果の区間多項式が定数を含むか否かを判定し、区間演算の結果の区間多項式が定数を含まない場合にはそのままε1を出力し、区間演算の結果の区間多項式が定数を含む場合には閾値δ2を用いて、
＜Ｗ１＞：L=0, U=ε1と置き、ε1を(ε1+L)/2で置き換え、
＜Ｗ２＞：＜Ｗ１＞で置き換えた後のε1について、条件２を満たすか否かを判定し、条件２を満たすならばL=ε1と置き、ε1を(ε1+U)/2で置き換え、そうでなければU=ε1と置き、ε1を(ε1+L)/2で置き換え、
＜Ｗ３＞：U-L≧δ2ならば＜Ｗ２＞に移行し、それ以外の場合には＜Ｗ４＞へ移行し、
＜Ｗ４＞：L≠0の場合にLの値をε1とする、
処理を行い[第２区間多項式計算処理]、
第１区間多項式計算処理にてε２が得られた場合には、当該ε2を許容誤差限界の下からの評価εとして出力し、第２区間多項式計算処理にてε1が得られた場合には、当該ε1を許容誤差限界の下からの評価εとして出力する[出力処理]。
【発明の効果】
【００１２】
本発明に拠れば、詳しくは後述する理論に基づくが、要すれば~f(x,y),~g(x,y)をxの多項式(係数はyの多項式となる)と見て、~f(x,y)と~g(x,y)の終結式を用いることにより、~f(x,y),~g(x,y)が一次の場合に限らず高次の場合も含め、連立方程式~f(x,y)=~g(x,y)=0が可解であることを保証する許容誤差限界を下から評価することができる。
【図面の簡単な説明】
【００１３】
【図１】実施形態１の許容誤差限界評価装置のハードウェア構成を示す機能ブロック図。
【図２】実施形態１の許容誤差限界評価処理のフローチャート。
【図３】実施形態２の許容誤差限界評価装置のハードウェア構成を示す機能ブロック図。
【図４】実施形態２の許容誤差限界評価処理のフローチャート。
【発明を実施するための形態】
【００１４】
《実施形態１》
図面を参照して本発明の実施形態１を説明する。図１は、実施形態１に係わる許容誤差限界評価装置１００のハードウェア構成を例示した構成ブロック図である。
図１に例示するように、許容誤差限界評価装置１００は、入力部１、多項式計算部２、区間計算部３、区間多項式計算部４、出力処理部５、記憶部６を有する。
図１、図２を参照して、本実施形態における許容誤差限界評価処理について説明する。
【００１５】
＜ステップＳ１−入力処理＞
入力部１には、多項式f(x,y),g(x,y)∈Ｋ[x,y]と、許容誤差限界の下からの評価εの初期値ε0,1,ε0,2>0、閾値δ1,δ2>0、および、f(x,y)の係数のうち誤差を有する係数の添字の集合T(f)⊂S(f)と、g(x,y)の係数のうち誤差を有する係数の添え字の集合T(g)⊂S(g)が入力される。なお、二変数多項式h(x,y)=Σj,k cjkxjyk∈Ｋ[x,y]に対して、多項式h(x,y)をxの多項式と見たときの次数をΩ、多項式h(x,y)をyの多項式と見たときの次数をΘとして、有限集合S(h)をS(h)={(j,k)|0≦j＜Ω, 0≦k≦Θ}∪{(Ω,k)|あるk’≧kが存在してcΩk’≠0}と定義する。
【００１６】
ここで、f(x,y)とg(x,y)は、xの多項式と見ることにより、
f(x,y) = ad(y)xd + … + a1(y)x + a0(y),
g(x,y) = be(y)xe + … + b1(y)x + b0(y)
の形式で表せるものであり、ad(y)およびbe(y)は定数0ではなく且つad(y)およびbe(y)は共通零点を持たないとする。また、f(x,y)とg(x,y)のxに関する終結式Resx(f,g)は定数ではないとする。終結式については後述する。
【００１７】
ad(y),be(y)が定数0であるか否かは、例えば「ad(y)のi次(0≦i≦d)の項の係数が全て0であり、かつ、be(y)のi次(0≦i≦e)の項の係数が全て0である」の成否の判定により達成される。また、ad(y)およびbe(y)が共通零点を持たないか否かは、例えばad(y)とbe(y)の終結式Res(ad,be)が0であるか否かの判定により達成される。
【００１８】
読み込んだ各多項式f(x,y)、g(x,y)及び各パラメータε0,1,ε0,2,δ1,δ2は記憶部６に記憶される。なお、各パラメータε0,1,ε0,2,δ1,δ2は入力部１から入力してもよいし、予め記憶部６内に初期値として登録しておいてもよい。また、許容誤差限界の下からの評価εの初期値ε0,1,ε0,2と閾値δ1,δ2は0より大きい任意の値を設定してよい。
【００１９】
＜ステップＳ２−多項式計算処理＞
多項式計算部２は、入力部１ないし記憶部６から受け取った多項式f(x,y),g(x,y)∈Ｋ[x,y]について、sjk ((j,k)∈T(f)), tmn ((m,n)∈T(g))を変数する多項式~f(x,y),~g(x,y)を計算し（式（３）参照）、さらに式（４）−（７）で定義されるＡ(・),Ｂ(・),Ｒ1(・),Ｒ2(・)を計算する。これら計算結果は記憶部６に記憶される。
【数１２】
【００２０】
ここで、A(・)は~f(x,y)をxの多項式と見たときの主係数（最高次の係数）であり、B(・)は~g(x,y)をxの多項式と見たときの主係数（最高次の係数）である。また、R１(・)は~f(x,y)をxの多項式と見たときの主係数と~g(x,y)をxの多項式と見たときの主係数とのyに関する終結式であり、R２(・)は~f(x,y)と~g(x,y)のxに関する終結式である。なお、例えば終結式R２(・)の右辺は正確には~f(x,y)と~g(x,y)が二変数多項式であることを明示すべくRx(~f(x,y),~g(x,y))と書くべきであろうものの、前後関係からそれが明らかな場合には特に明示せずに式（７）のように表すことに留意されたい。
【００２１】
終結式Res(f,g)は、一変数多項式f=Σdj=0 ajxj, g=Σek=0 bkxk∈Ｋ[x]（ただし、ad≠0,be≠0とする）とすると、シルベスター行列（８）の行列式で定義される。なお、aj,bkの現れるところ以外の成分は0である。このシルベスター行列（８）は(d+e)×(d+e)の正方行列で、ajの現れる行はe個,bkの現れる行はd個である。
【数１３】
【００２２】
＜ステップＳ３−区間計算処理＞
区間計算部３は、多項式計算部２が計算した~f(x,y)をxの多項式と見たときの主係数A(y,sdk)と~g(x,y)をxの多項式と見たときの主係数B(y,ten)とのyに関する終結式R1(sdk,ten)が定数であるか否かを判定する。区間計算部３は、R1(sdk,ten)が定数であればε1を∞とし、R1(sdk,ten)が定数でなければ記憶部６からε0,1とδ1を取得して、以下の手順によりε1を計算する。得られたε1は記憶部６に記憶される。
【００２３】
＜プロセスＰ１＞
ε1=ε0,1, L=0とする。
【００２４】
＜プロセスＰ２＞
下記条件２を満たすか否かを判定し、もし条件２を満たさないならばプロセスＰ３へ移行し、もし条件２を満たすならばL=ε1と置き、ε1を2ε1で置き換え再度プロセスＰ２を実行する。
[条件２]
終結式R1(sdk,ten)において、変数sdk ((d,k)∈T(f)), ten ((e,n)∈T(g))にI(ε1)を代入して区間演算を行った結果の区間が0を含まない。
【００２５】
＜プロセスＰ３＞
U=ε1と置き、ε1を(ε1+L)/2で置き換える。
【００２６】
＜プロセスＰ４＞
プロセスＰ３で置き換えたε1について、上記条件２を満たすか否かを判定し、ε1が条件２を満たすならばL=ε1と置き、ε1を(ε1+U)/2で置き換える。そうでなければU=ε1と置き、ε1を(ε1+L)/2で置き換える。
【００２７】
＜プロセスＰ５＞
もしU-L≧δ1ならばプロセスＰ４に処理を移行し、それ以外の場合にはプロセスＰ６へ処理を移行する。
【００２８】
＜プロセスＰ６＞
もし、L≠0ならばLの値をε1とする。もしL=0ならば「δ1の値が大き過ぎる」ことを通知するメッセージ（または値）を出力処理部５に送る（閾値δ1の値が大きすぎる場合には、許容誤差限界評価装置１００によって許容誤差限界εを評価することができないため、処理を終了（中断）する）。
【００２９】
上記手順において，プロセスＰ３以降では、Uは調べた値のうち上記条件２を満たさないものの中で最小の値である。もしL>0ならばLは調べた値のうち上記条件２を満たすものの中で最大の値である。δ1が大きいと上記条件２を満たす値が現れる前に終了条件U-L<δ1が成立してしまうことがあるので注意しなければならない。
【００３０】
また、プロセスＰ２におけるI(ε1)（ただしε1>0）はＫ＝Ｒ（実数体）のとき実閉区間[-ε1,ε1]とし、Ｋ＝Ｃ（複素数体）のとき原点中心、半径ε1の閉円板{z∈C | |z|≦ε1}とする。また、プロセスＰ２,Ｐ３に現れる区間演算については、Ｋ＝Ｒの場合は例えば参考文献１の「１.３.２ 区間解析」の節を、Ｋ＝Ｃの場合は例えば参考文献２を参照のこと。
（参考文献１）大石進一著, 「精度保証付き数値計算」, コロナ社, 2000.
（参考文献２）I. Gargantini and P. Henrici, “Circular arithmetic and the determination of polynomial zeros”, Numer. Math., Vol. 18, pp. 305--320, 1972.
【００３１】
＜ステップＳ４−区間多項式計算処理＞
区間多項式計算部４は、多項式計算部２が計算した~f(x,y)と~g(x,y)のxに関する終結式R2(y,sjk,tmn)をyの多項式と見たとき、
（Ｉ）定数項が0である、
（ＩＩ）あるj≧1が存在して、yjの係数は0ではない定数である、
の少なくとも一方が成り立つか否かを判定し、少なくとも一方が成り立つならばε2を∞とする。これら二つの条件（Ｉ）（ＩＩ）の少なくとも一方が成り立つ場合、後述の定理２における仮定が満たされる、つまりResx(f,g)の零点の存在が肯定されるので、入力条件を考慮すれば定理２の条件（２）が成立することが容易に分かる。二つの条件（Ｉ）（ＩＩ）がどちらも成り立たない場合には、記憶部６からε0,2とδ2を取得して以下の手順によりε2を計算する。
【００３２】
＜プロセスＱ１＞
ε2=ε0,2, L=0とする。
【００３３】
＜プロセスＱ２＞
下記条件３を満たすか否かを判定し、条件３を満たさないならばプロセスＱ３へ移行する。条件３を満たすならばL=ε2と置き、ε2を2ε2で置き換え再度プロセスＱ２を実行する。
[条件３]
終結式R2(y,sjk,tmn)において、変数sjk ((j,k)∈T(f)), tmn((m,n)∈T(g))にI(ε2)を代入し、区間演算を行った結果の区間多項式が定数を含まない（つまり区間演算の結果である区間多項式において、１次以上の係数である区間のうち少なくとも一つの区間は０を含まない）。
【００３４】
＜プロセスＱ３＞
U=ε2と置き、ε2を(ε2+L)/2で置き換える。
【００３５】
＜プロセスＱ４＞
プロセスＱ３で置き換えた後のε2について、上記条件３を満たすか否かを判定し、もし条件３を満たすならばL=ε2と置き、ε2を(ε2+U)/2で置き換える。そうでなければU=ε2と置き、ε2を(ε2+L)/2で置き換える。
【００３６】
＜プロセスＱ５＞
もしU-L≧δ2ならばプロセスＱ４に処理を移行し、それ以外の場合にはプロセスＱ６へ処理を移行する。
【００３７】
＜プロセスＱ６＞
もしL≠0ならばLの値をε2とする。このε2は記憶部６に記憶される。もしL=0ならば「δ2の値が大き過ぎる」ことを通知するメッセージ（または値）を出力処理部５に送る（閾値δ2の値が大きすぎる場合には、許容誤差限界評価装置１００によって許容誤差限界の下からの評価εを求めることができないため、処理を終了（中断）する）。
【００３８】
プロセスＱ２,Ｑ３に現れる区間の定義及び区間演算については、ステップ３の説明で記述したとおりである。
【００３９】
＜ステップＳ５−出力処理＞
出力処理部５は、区間計算部３が計算したε1と区間多項式計算部４が計算したε2を取得し、小さい方の値（min{ε1,ε2}）を許容誤差限界の下からの評価εとして出力する。
【００４０】
《実施形態２》
図面を参照して本発明の実施形態２を説明する。実施形態２に係わる許容誤差限界評価装置２００のハードウェア構成を図３に示す。
【００４１】
実施形態２は、実施形態１の許容誤差限界評価装置１００の各部の構成のうち、区間多項式計算部４を、判定部７０、第１区間多項式計算部７１、第２区間多項式計算部７２に置き換えたものである。
【００４２】
図３、図４を参照して、本実施形態における許容誤差限界評価処理について説明する。
【００４３】
ステップＳ１,Ｓ２,Ｓ３は実施形態１と同じである。
【００４４】
＜ステップＳ４ａ−判定処理＞
判定部７０は、区間計算部３が計算したε1が∞であるか否かを判定し、∞であればステップＳ４ｂへ処理を移行する制御を行い、それ以外の場合にはステップＳ４ｃへ処理を移行する制御を行う。
【００４５】
＜ステップＳ４ｂ−第１区間多項式計算処理＞
第１区間多項式計算部７１による処理は、実施形態１の区間多項式計算部４による処理と同じであるから重複説明を省略する。
【００４６】
＜ステップＳ４ｃ−第２区間多項式計算処理＞
第２区間多項式計算部７２は、まず、多項式計算部２が計算した終結式R2(y,sjk,tmn)において、変数sdk((d,k)∈T(f)), ten((e,n)∈T(g))にI(ε1)を代入し、区間演算を行った結果の区間多項式が定数を含むか否か（つまり区間演算の結果である区間多項式において、１次以上の係数の区間がすべて０を含むか否か）を判定する。区間演算の結果の区間多項式が定数を含まない場合にはε1を出力処理部５へ送る。
【００４７】
第２区間多項式計算部７２は、区間演算を行った結果の区間多項式が定数を含む場合には、記憶部６からδ2を取得して、以下の手順によりε1を計算し、求めたε1を出力処理部５へ送る。
【００４８】
＜プロセスＷ１＞
L=0, U=ε1と置き、ε1を(ε1+L)/2で置き換える。
【００４９】
＜プロセスＷ２＞
プロセスＷ１で置き換えた後のε1について、上記条件３を満たすか否かを判定し、もし条件３を満たすならばL=ε1と置き、ε1を(ε1+U)/2で置き換える。そうでなければU=ε1と置き、ε1を(ε1+L)/2で置き換える。
【００５０】
＜プロセスＷ３＞
もしU-L≧δ2ならばプロセスＷ２に処理を移行し、それ以外の場合にはプロセスＷ４へ処理を移行する。
【００５１】
＜プロセスＷ４＞
もしL≠0ならばLの値をε1とする。このε1は記憶部６に記憶される。もしL=0ならば「δ2の値が大き過ぎる」ことを通知するメッセージ（または値）を出力処理部５に送る。
【００５２】
＜ステップ５ａ−出力処理＞
第２区間多項式計算部７２は区間計算部３が計算したε１の値を更新する形で計算を行うためε２の値は存在しない。したがって、第１区間多項式計算部７１からε２の値が出力された場合には、出力処理部５は当該ε2を許容誤差限界の下からの評価εとして出力する。
一方、第２区間多項式計算部７２からε1の値が出力された場合には、出力処理部５は当該ε1を許容誤差限界の下からの評価εとして出力する。
【００５３】
《理論》
一変数多項式に関する終結式に関しては、定理１が知られている（詳細は、例えば参考文献３の補題２.２６を参照のこと）。
（参考文献３）野呂正行, 横山和弘, 「グレブナー基底の計算基礎篇」, 東京大学出版会, ２００３．
[定理１]
Res(f,g)=0となる必要十分条件は、f(x)とg(x)の共通零点が存在すること、すなわち、ある複素数αが存在してf(α)=g(α)=0となることである。
【００５４】
次に、二変数多項式f(x,y),g(x,y)∈Ｋ[x,y]について、f(x,y),g(x,y)をxの多項式と見て、
f(x,y) = ad(y)xd + … + a1(y)x + a0(y),
g(x,y) = be(y)xe + … + b1(y)x + b0(y),
と表し、f(x,y)とg(x,y)の終結式を考える。ただし、ad(y),be(y)は定数0ではないとする。この終結式は上述の終結式の定義においてシルベスター行列（８）の成分がＫの元ではなく、Ｋ[x]に属する多項式となったものである。これをf(x,y),g(x,y)のxに関する終結式と呼び、Resx(f,g)と書く。
【００５５】
二変数多項式に対する終結式に関しては、定理２が知られている。
[定理２]
複素数βをResx(f,g)の零点とする。このとき、次のいずれかが成り立つ。
（１）ad(β)=be(β)=0
（２）ある複素数αが存在して、f(α,β)=g(α,β)=0
【００５６】
参考文献３の補題２.３１では、定理２の（１）が「ad(β)=0またはbe(β)=0」となっているが、より強い上記定理２が成り立つことが知られている。証明は以下の通り。
[証明]
ad(β),be(β)のうち少なくとも一方が0ではないとき、上記（２）が成り立つことを言えばよい。
どちらでも証明は同じなので、ad(β)≠0と仮定する。
（Ａ）be(β)≠0の場合、参考文献３の補題２．３１の証明より主張は成り立つ。
（Ｂ）be(β)=…=bu-1(β)=0, bu(β)≠0の場合、h(x)=Σuk=0bk(β)xkと置くと、終結式の定義より、
0=Resx(f,g)(β)=ad(β)e-uRes(f(x,β),h(x))
が成立する。
ここで、ad(β)≠0よりRes(f(x,β),h(x))=0である。また、f(x,β)の最高次の係数ad(β), h(x)の最高次の係数bu(β)はどちらも0ではないから、定理１より或る複素数αが存在してf(α,β)=h(α)=0となる。h(x)=g(x,β)だから、f(α,β)=g(α,β)=0が成り立つ。
（Ｃ）be(β)=…=b0(β)=0の場合、g(x,β)は恒等的に0である。よって、f(x,β)(仮定ad(β)≠0より定数ではない)の任意の零点αに対し、f(α,β)=g(α,β)=0が成り立つ。
(証明終)
【００５７】
定理２より系１が成り立つのは明らかである。
[系１]
f(x,y),g(x,y)∈Ｋ[x,y]を以下のように書く。
f(x,y) = ad(y)xd + … + a1(y)x + a0(y),
g(x,y) = be(y)xe + … + b1(y)x + b0(y).
ただし、ad(y), be(y)は定数0ではないとする。
このとき、下記条件（１）および（２）を共に満たすならば、f(x,y)=g(x,y)=0には（複素数体上に）解が存在する。
（１）ad(y)とbe(y)が共通零点を持たない。
（２）Resx(f,g)が定数ではない。
【００５８】
定理１、定理２および系１から、許容誤差限界の下からの評価εを求めることができる。
【００５９】
(*1)まず、系１の条件（１）に関する成否について。
入力されるf(x,y)及びg(x,y)について、ad(y)とbe(y)はいずれも0ではなく、共通零点を持たないことを仮定しているから、Res(ad,be)≠0である。式（９）で与えられる任意の~f(x,y),~g(x,y)に対し、~f(x,y)をxの多項式と見たときの主係数を式（１０）、~g(x,y)をxの多項式と見たときの主係数を式（１１）と置くと、~ad(y),~be(y)においてT(f),T(g)に属する添え字を持つ係数は変数sdk,ten∈Ｋによる連続関数だから或るε1>0が存在し、式（１２）と式（１３）を満足する式（９）の任意の~f(x,y),~g(x,y)について、Res(~ad,~be)≠0、すわなち~ad(y)と~be(y)は共通零点を持たないことが言える。
このε1の算出は上記実施形態中のステップ３の処理に該当する。
【数１４】
【００６０】
(*2)次に、系１の条件（２）に関する成否について。
入力されるf(x,y)及びg(x,y)について、Resx(f,g)は定数ではないことを仮定しているから、Resx(~f,~g)=ΣDj=0 ~rjyj(~rD≠0)と書くと、各係数~rjは、~ajk(y) ((j,k)∈S(f)),~bmn(y) ((m,n)∈S(g))を含み得て、さらに~ajk(y) ((j,k) ∈T(f)),~bmn(y) ((m,n) ∈T(g))は変数sjk,tmn∈Ｋによる連続関数であるから、各係数~rjは変数sjk,tmn∈Ｋによる連続関数と言えることにより或るε2>0が存在し、式（１４）と式（１５）を満足する式（９）の任意の~f(x,y),~g(x,y)について、或るj(1≦j≦D)が存在して~rj(y)≠0である、すなわちResx(~f,~g)は定数ではないことが言える。
このε2の算出は上記実施形態１のステップ４、上記実施形態２のステップ４ａ-４ｃの各処理に該当する。
【数１５】
【００６１】
よって、ε=min{ε1,ε2}とすると、定理２より式（１６）の任意の~f(x,y)および~g(x,y)について連立方程式~f(x,y)=~g(x,y)=0には解が存在することが言える。このときεが求めるべき許容誤差限界の下からの評価である。
【数１６】
【００６２】
＜補記＞
本発明は上述の実施形態に限定されるものではなく、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。また、上記実施形態において説明した処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されるとしてもよい。
【００６３】
また、上記実施形態において説明したハードウェアエンティティ（許容誤差限界評価装置）における処理機能をコンピュータによって実現する場合、ハードウェアエンティティが有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記ハードウェアエンティティにおける処理機能がコンピュータ上で実現される。
【００６４】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ（Random Access Memory）、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）等を、光磁気記録媒体として、ＭＯ（Magneto-Optical disc）等を、半導体メモリとしてＥＥＰ−ＲＯＭ（Electronically Erasable and Programmable-Read Only Memory）等を用いることができる。
【００６５】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００６６】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００６７】
なお、本発明の細部においては、数値計算処理のみならず有理式や多項式などの数式処理も必要となるが、数値計算処理および数式処理自体は、周知技術と同様にして達成されるので、その演算処理方法などの詳細な説明は省略した（この点の技術水準を示す数式処理が可能なソフトウェアとしては、例えば、Risa/Asir、Maple（登録商標）、MATHEMATICA（登録商標第2312968号）、Gnuplotなどが挙げられる。Risa/Asirについては、例えばインターネット〈URL:http://www.math.kobe-u.ac.jp/Asir/asir-ja.html〉［平成22年3月11日検索］を参照のこと。Mapleについては、例えばインターネット〈URL:http://www.cybernet.co.jp/maple/〉［平成22年3月11日検索］を参照のこと。Gnuplotについては、例えばインターネット〈URL: http://www.gnuplot.info/〉［平成22年3月11日検索］を参照のこと。）。
【実施例】
【００６８】
[例１]
K=R, f=x2+y2-1, g=x+y-1とし、fの係数は誤差を含まず、gの係数のみ誤差を含むものとする。すなわち、T(f)=φ（空集合）、T(g)={(1,0),(0,1),(0,0)}である。ε0,1=ε0,2=1とし、（１）δ1=δ2=1/100、（２）δ1=δ2=1/10000の２つの場合について、実施形態１の許容誤差限界評価装置により許容誤差限界の下からの評価εを求める。なお、区間演算において、区間の端点は有理数とし、端点間の計算は正確に行うものとする。
【００６９】
＜ステップＳ１＞
上述のとおり設定された多項式f,gと、評価εの初期値ε0,1=ε0,2と、閾値δ1,δ2、添字集合T(f),T(g)が入力される。
【００７０】
＜ステップＳ２＞
計算結果である~f, ~g, R1, R2 は以下の通りである。
【数１７】
【００７１】
＜ステップＳ３＞
R1が定数なので、ε1=∞となる。
【００７２】
＜ステップＳ４＞
（１）の場合：ε2=53/128である。
（２）の場合：ε2=3393/8192である。
【００７３】
＜ステップＳ５＞
（１）の場合：min{∞,53/128}=53/128より、ε=53/128となる。
（２）の場合：min{∞,3393/8192}=3393/8192より、ε=3393/8192となる。
【００７４】
なお、この例の場合は、区間計算部３が計算したε1が∞なので、実施形態２に拠っても、途中経過、出力とも上記と同じとなる。
【００７５】
[例２]
K=R, f=x2y+xy2-1, g=xy+x+y+1とし、T(f)={(2,1),(1,2)}, T(g)={(1,1),(1,0),(0,1)}とする。ε0,1=ε0,2=1とし、（１）δ1=δ2=1/100、（２）δ1=δ2=1/10000のそれぞれの場合について、実施形態１の許容誤差限界評価装置により許容誤差限界の下からの評価εを求める。なお、区間演算において、区間の端点は有理数とし、端点間の計算は正確に行うものとする。
【００７６】
＜ステップＳ１＞
上述のとおり設定された多項式f,gと、評価εの初期値ε0,1=ε0,2と、閾値δ1,δ2、添字集合T(f),T(g)が入力される。
【００７７】
＜ステップＳ２＞
計算結果である~f, ~g, R1, R2は以下の通り。
【数１８】
【００７８】
＜ステップＳ３＞
（１）の場合：ε1=53/128である。
（２）の場合：ε1=3393/8192である。
【００７９】
＜ステップＳ４＞
（１）の場合：ε2=33/128である。
（２）の場合：ε2=2129/8192である。
【００８０】
＜ステップＳ５＞
（１）の場合：min{53/128,33/128}=33/128より、ε=33/128となる。
（２）の場合：min{3393/8192,2129/8192}=2129/8192より、ε=2129/8192となる。
【００８１】
なお、この例の場合、実施形態２に拠ると、（１）の場合はε=265/1024、（２）の場合はε=4360005/16777216が出力となる。
【産業上の利用可能性】
【００８２】
連立代数方程式の係数の誤差に関する可解性は、ロボットなどの制御の安定性と密接に関係がある。例えば、ロボットアームの制御では、ロボットアームを構成する各関節の角度と手先位置との関係を連立方程式で表すことができ、これを解くことにより、所望の手先位置に到達させるための各関節角度を求める。しかし、このときの連立方程式には、例えばロボットの各関節間の長さのように何らかの計測装置で計測した値が係数として使用されることが多い。すると、係数には誤差が含まれてしまうため、連立方程式の可解性の問題が生じる。本発明によると、連立方程式が可解であることを保証する許容誤差限界を求めることができるので、これにより測定誤差がどの程まで許容されるかを知ることができる。
【特許請求の範囲】
【請求項１】
Ｋを実数体Ｒまたは複素数体とし、
Ｋ[x,y]をxとyを変数とするＫ上の二変数多項式環とし、
二変数多項式h(x,y)=Σj,k cjkxjyk∈Ｋ[x,y]に対して、多項式h(x,y)をxの多項式と見たときの次数をΩ、多項式h(x,y)をyの多項式と見たときの次数をΘとして、有限集合S(h)をS(h)={(j,k)|0≦j＜Ω, 0≦k≦Θ}∪{(Ω,k)|あるk’≧kが存在してcΩk’≠0}と定義し、
二変数多項式f(x,y)=Σj,k ajkxjyk∈Ｋ[x,y], g(x,y)=Σm,n bmnxmyn∈Ｋ[x,y]について、T(f)⊂S(f),T(g)⊂S(g)をそれぞれf(x,y),g(x,y)の係数のうち誤差を含むものの添字の集合とし、
f(x,y),g(x,y)について、少なくともいずれかの係数に誤差を含む任意の多項式をそれぞれ
【数１９】
としたとき、連立代数方程式~f(x,y)=~g(x,y)=0が複素数体上に解を持つような0<τ∈Ｒの最大値を許容誤差限界^εとして、当該許容誤差限界^εの下からの評価εを求める許容誤差限界評価装置であって、
上記二変数多項式f(x,y),g(x,y)は、
f(x,y) = ad(y)xd + … + a1(y)x + a0(y),
g(x,y) = be(y)xe + … + b1(y)x + b0(y)
と表したときに主係数ad(y)および主係数be(y)が定数0ではなく且つ主係数ad(y)および主係数be(y)は共通零点を持たないとし、
上記二変数多項式f(x,y)とg(x,y)のxに関する終結式Resx(f,g)は定数ではないとし、
予め定められた初期値をε0,1,ε0,2>0とし、
予め定められた閾値をδ1,δ2>0として、
上記~f(x,y)と、上記~g(x,y)と、~f(x,y)をxの多項式と見たときの主係数
【数２０】
と、~g(x,y)をxの多項式と見たときの主係数
【数２１】
と、主係数A(y,sdk)と主係数B(y,ten)とのyに関する終結式
【数２２】
と、~f(x,y)と~g(x,y)のxに関する終結式
【数２３】
を計算する多項式計算部と、
上記多項式計算部によって得られた上記終結式R1(sdk,ten)が定数であるか否かを判定し、上記終結式R1(sdk,ten)が定数であればε1を∞とし、上記終結式R1(sdk,ten)が定数でなければ、上記初期値ε0,1と上記閾値δ1を用いて、
＜Ｐ１＞：ε1=ε0,1, L=0とし、
＜Ｐ２＞：I(ε1)を上記Ｋが実数体のとき実閉区間[-ε1,ε1]とし上記Ｋが複素数体のとき原点中心、半径ε1の閉円板{z∈C | |z|≦ε1}として、条件１[上記終結式R1(sdk,ten)において、変数sdk ((d,k)∈Ｔ(f)), ten ((e,n)∈Ｔ(g))に当該I(ε1)を代入して区間演算を行った結果の区間が０を含まない]を満たすか否かを判定し、条件１を満たさないならば＜Ｐ３＞へ移行し、条件１を満たすならばL=ε1と置き、ε1を2ε1で置き換え再度＜Ｐ２＞を実行し、
＜Ｐ３＞：U=ε1と置き、ε1を(ε1+L)/2で置き換え、
＜Ｐ４＞：＜Ｐ３＞で置き換えたε1について、上記条件１を満たすか否かを判定し、ε1が上記条件１を満たすならばL=ε1と置き、ε1を(ε1+U)/2で置き換え、そうでなければU=ε1と置き、ε1を(ε1+L)/2で置き換え、
＜Ｐ５＞： U-L≧δ1ならば＜Ｐ４＞に移行し、それ以外の場合には＜Ｐ６＞へ移行し、
＜Ｐ６＞：L≠0の場合にLの値をε1とする、
処理を行う区間計算部と、
上記終結式R2(y,sjk,tmn)をyの多項式と見たとき、
（Ｉ）定数項が０である、
（ＩＩ）あるj≧1が存在して、yjの係数は0ではない定数である、
の少なくとも一方が成り立つか否かを判定し、少なくとも一方が成り立つならばε2を∞とし、二つの条件（Ｉ）（ＩＩ）がどちらも成り立たない場合には、上記初期値ε0,2と上記閾値δ2を用いて、
＜Ｑ１＞：ε2=ε0,2, L=0とし、
＜Ｑ２＞：I(ε2)を上記Ｋが実数体のとき実閉区間[-ε2,ε2]とし上記Ｋが複素数体のとき原点中心、半径ε2の閉円板{z∈C | |z|≦ε2}として、条件２[上記終結式R2(y,sjk,tmn)において、変数sjk ((j,k)∈Ｔ(f)), tmn((m,n)∈Ｔ(g))に当該I(ε2)を代入し、区間演算を行った結果の区間多項式が定数を含まない]を満たすか否かを判定し、条件２を満たさないならば＜Ｑ３＞へ移行し、条件２を満たすならばL=ε2と置き、ε2を2ε2で置き換え再度＜Ｑ２＞を実行し、
＜Ｑ３＞：U=ε2と置き、ε2を(ε2+L)/2で置き換え、
＜Ｑ４＞：＜Ｑ３＞で置き換えた後のε2について、上記条件２を満たすか否かを判定し、上記条件２を満たすならばL=ε2と置き、ε2を(ε2+U)/2で置き換え、そうでなければU=ε2と置き、ε2を(ε2+L)/2で置き換え、
＜Ｑ５＞：U-L≧δ2ならば＜Ｑ４＞に移行し、それ以外の場合には＜Ｑ６＞へ移行し、
＜Ｑ６＞：L≠0の場合にLの値をε2とする、
処理を行う区間多項式計算部と、
上記区間計算部が計算したε1と上記区間多項式計算部が計算したε2を取得し、小さい方の値min{ε1,ε2}を許容誤差限界の下からの評価εとして出力する出力処理部と
を含む許容誤差限界評価装置。
【請求項２】
Ｋを実数体Ｒまたは複素数体とし、
Ｋ[x,y]をxとyを変数とするＫ上の二変数多項式環とし、
二変数多項式h(x,y)=Σj,k cjkxjyk∈Ｋ[x,y]に対して、多項式h(x,y)をxの多項式と見たときの次数をΩ、多項式h(x,y)をyの多項式と見たときの次数をΘとして、有限集合S(h)をS(h)={(j,k)|0≦j＜Ω, 0≦k≦Θ}∪{(Ω,k)|あるk’≧kが存在してcΩk’≠0}と定義し、
二変数多項式f(x,y)=Σj,k ajkxjyk∈Ｋ[x,y], g(x,y)=Σm,n bmnxmyn∈Ｋ[x,y]について、T(f)⊂S(f),T(g)⊂S(g)をそれぞれf(x,y),g(x,y)の係数のうち誤差を含むものの添字の集合とし、
f(x,y),g(x,y)について、少なくともいずれかの係数に誤差を含む任意の多項式をそれぞれ
【数２４】
としたとき、連立代数方程式~f(x,y)=~g(x,y)=0が複素数体上に解を持つような0<τ∈Ｒの最大値を許容誤差限界^εとして、当該許容誤差限界^εの下からの評価εを求める許容誤差限界評価装置であって、
上記二変数多項式f(x,y),g(x,y)は、
f(x,y) = ad(y)xd + … + a1(y)x + a0(y),
g(x,y) = be(y)xe + … + b1(y)x + b0(y)
と表したときに主係数ad(y)および主係数be(y)が定数0ではなく且つ主係数ad(y)および主係数be(y)は共通零点を持たないとし、
上記二変数多項式f(x,y)とg(x,y)のxに関する終結式Resx(f,g)は定数ではないとし、
予め定められた初期値をε0,1,ε0,2>0とし、
予め定められた閾値をδ1,δ2>0として、
上記~f(x,y)と、上記~g(x,y)と、~f(x,y)をxの多項式と見たときの主係数
【数２５】
と、~g(x,y)をxの多項式と見たときの主係数
【数２６】
と、主係数A(y,sdk)と主係数B(y,ten)とのyに関する終結式
【数２７】
と、~f(x,y)と~g(x,y)のxに関する終結式
【数２８】
を計算する多項式計算部と、
上記多項式計算部によって得られた上記終結式R1(sdk,ten)が定数であるか否かを判定し、上記終結式R1(sdk,ten)が定数であればε1を∞とし、上記終結式R1(sdk,ten)が定数でなければ、上記初期値ε0,1と上記閾値δ1を用いて、
＜Ｐ１＞：ε1=ε0,1, L=0とし、
＜Ｐ２＞：I(ε1)を上記Ｋが実数体のとき実閉区間[-ε1,ε1]とし上記Ｋが複素数体のとき原点中心、半径ε1の閉円板{z∈C | |z|≦ε1}として、条件１[上記終結式R1(sdk,ten)において、変数sdk ((d,k)∈Ｔ(f)), ten ((e,n)∈Ｔ(g))に当該I(ε1)を代入して区間演算を行った結果の区間が０を含まない]を満たすか否かを判定し、条件１を満たさないならば＜Ｐ３＞へ移行し、条件１を満たすならばL=ε1と置き、ε1を2ε1で置き換え再度＜Ｐ２＞を実行し、
＜Ｐ３＞：U=ε1と置き、ε1を(ε1+L)/2で置き換え、
＜Ｐ４＞：＜Ｐ３＞で置き換えたε1について、上記条件１を満たすか否かを判定し、ε1が上記条件１を満たすならばL=ε1と置き、ε1を(ε1+U)/2で置き換え、そうでなければU=ε1と置き、ε1を(ε1+L)/2で置き換え、
＜Ｐ５＞： U-L≧δ1ならば＜Ｐ４＞に移行し、それ以外の場合には＜Ｐ６＞へ移行し、
＜Ｐ６＞：L≠0の場合にLの値をε1とする、
処理を行う区間計算部と、
上記区間計算部が計算した上記ε1が∞であるか否かを判定する判定部と
上記区間計算部が計算した上記ε1が∞である場合に、上記終結式R2(y,sjk,tmn)をyの多項式と見たとき、
（Ｉ）定数項が０である、
（ＩＩ）あるj≧1が存在して、yjの係数は0ではない定数である、
の少なくとも一方が成り立つか否かを判定し、少なくとも一方が成り立つならばε2を∞とし、二つの条件（Ｉ）（ＩＩ）がどちらも成り立たなければ、上記初期値ε0,2と上記閾値δ2を用いて、
＜Ｑ１＞：ε2=ε0,2, L=0とし、
＜Ｑ２＞：I(ε2)を上記Ｋが実数体のとき実閉区間[-ε2,ε2]とし上記Ｋが複素数体のとき原点中心、半径ε2の閉円板{z∈C | |z|≦ε2}として、条件２[上記終結式R2(y,sjk,tmn)において、変数sjk ((j,k)∈Ｔ(f)), tmn((m,n)∈Ｔ(g))に当該I(ε2)を代入し、区間演算を行った結果の区間多項式が定数を含まない]を満たすか否かを判定し、条件２を満たさないならば＜Ｑ３＞へ移行し、条件２を満たすならばL=ε2と置き、ε2を2ε2で置き換え再度＜Ｑ２＞を実行し、
＜Ｑ３＞：U=ε2と置き、ε2を(ε2+L)/2で置き換え、
＜Ｑ４＞：＜Ｑ３＞で置き換えた後のε2について、上記条件２を満たすか否かを判定し、上記条件２を満たすならばL=ε2と置き、ε2を(ε2+U)/2で置き換え、そうでなければU=ε2と置き、ε2を(ε2+L)/2で置き換え、
＜Ｑ５＞：U-L≧δ2ならば＜Ｑ４＞に移行し、それ以外の場合には＜Ｑ６＞へ移行し、
＜Ｑ６＞：L≠0の場合にLの値をε2とする、
処理を行う第１区間多項式計算部と、
上記区間計算部が計算した上記ε1が∞でない場合に、I(ε1)を上記Ｋが実数体のとき実閉区間[-ε1,ε1]とし上記Ｋが複素数体のとき原点中心、半径ε1の閉円板{z∈C | |z|≦ε1}として、上記多項式計算部によって得られた上記終結式R2(y,sjk,tmn)において、変数sdk((d,k)∈T(f)), ten((e,n)∈T(g))にI(ε1)を代入し、区間演算を行った結果の区間多項式が定数を含むか否かを判定し、区間演算の結果の区間多項式が定数を含まない場合にはそのままε1を出力し、区間演算の結果の区間多項式が定数を含む場合には上記閾値δ2を用いて、
＜Ｗ１＞：L=0, U=ε1と置き、ε1を(ε1+L)/2で置き換え、
＜Ｗ２＞：＜Ｗ１＞で置き換えた後のε1について、上記条件２を満たすか否かを判定し、上記条件２を満たすならばL=ε1と置き、ε1を(ε1+U)/2で置き換え、そうでなければU=ε1と置き、ε1を(ε1+L)/2で置き換え、
＜Ｗ３＞：U-L≧δ2ならば＜Ｗ２＞に移行し、それ以外の場合には＜Ｗ４＞へ移行し、
＜Ｗ４＞：L≠0の場合にLの値をε1とする、
処理を行う第２区間多項式計算部と、
上記第１区間多項式計算部からε２が出力された場合には、当該ε2を許容誤差限界の下からの評価εとして出力し、上記第２区間多項式計算部からε1が出力された場合には、当該ε1を許容誤差限界の下からの評価εとして出力する出力処理部と
を含む許容誤差限界評価装置。
【請求項３】
Ｋを実数体Ｒまたは複素数体とし、
Ｋ[x,y]をxとyを変数とするＫ上の二変数多項式環とし、
二変数多項式h(x,y)=Σj,k cjkxjyk∈Ｋ[x,y]に対して、多項式h(x,y)をxの多項式と見たときの次数をΩ、多項式h(x,y)をyの多項式と見たときの次数をΘとして、有限集合S(h)をS(h)={(j,k)|0≦j＜Ω, 0≦k≦Θ}∪{(Ω,k)|あるk’≧kが存在してcΩk’≠0}と定義し、
二変数多項式f(x,y)=Σj,k ajkxjyk∈Ｋ[x,y], g(x,y)=Σm,n bmnxmyn∈Ｋ[x,y]について、T(f)⊂S(f),T(g)⊂S(g)をそれぞれf(x,y),g(x,y)の係数のうち誤差を含むものの添字の集合とし、
f(x,y),g(x,y)について、少なくともいずれかの係数に誤差を含む任意の多項式をそれぞれ
【数２９】
としたとき、連立代数方程式~f(x,y)=~g(x,y)=0が複素数体上に解を持つような0<τ∈Ｒの最大値を許容誤差限界^εとして、当該許容誤差限界^εの下からの評価εを求める許容誤差限界評価方法であって、
上記二変数多項式f(x,y),g(x,y)は、
f(x,y) = ad(y)xd + … + a1(y)x + a0(y),
g(x,y) = be(y)xe + … + b1(y)x + b0(y)
と表したときに主係数ad(y)および主係数be(y)が定数0ではなく且つ主係数ad(y)および主係数be(y)は共通零点を持たないとし、
上記二変数多項式f(x,y)とg(x,y)のxに関する終結式Resx(f,g)は定数ではないとし、
予め定められた初期値をε0,1,ε0,2>0とし、
予め定められた閾値をδ1,δ2>0として、
多項式計算部が、上記~f(x,y)と、上記~g(x,y)と、~f(x,y)をxの多項式と見たときの主係数
【数３０】
と、~g(x,y)をxの多項式と見たときの主係数
【数３１】
と、主係数A(y,sdk)と主係数B(y,ten)とのyに関する終結式
【数３２】
と、~f(x,y)と~g(x,y)のxに関する終結式
【数３３】
を計算する多項式計算ステップと、
区間計算部が、上記多項式計算ステップにおいて得られた上記終結式R1(sdk,ten)が定数であるか否かを判定し、上記終結式R1(sdk,ten)が定数であればε1を∞とし、上記終結式R1(sdk,ten)が定数でなければ、上記初期値ε0,1と上記閾値δ1を用いて、
＜Ｐ１＞：ε1=ε0,1, L=0とし、
＜Ｐ２＞：I(ε1)を上記Ｋが実数体のとき実閉区間[-ε1,ε1]とし上記Ｋが複素数体のとき原点中心、半径ε1の閉円板{z∈C | |z|≦ε1}として、条件１[上記終結式R1(sdk,ten)において、変数sdk ((d,k)∈Ｔ(f)), ten ((e,n)∈Ｔ(g))に当該I(ε1)を代入して区間演算を行った結果の区間が０を含まない]を満たすか否かを判定し、条件１を満たさないならば＜Ｐ３＞へ移行し、条件１を満たすならばL=ε1と置き、ε1を2ε1で置き換え再度＜Ｐ２＞を実行し、
＜Ｐ３＞：U=ε1と置き、ε1を(ε1+L)/2で置き換え、
＜Ｐ４＞：＜Ｐ３＞で置き換えたε1について、上記条件１を満たすか否かを判定し、ε1が上記条件１を満たすならばL=ε1と置き、ε1を(ε1+U)/2で置き換え、そうでなければU=ε1と置き、ε1を(ε1+L)/2で置き換え、
＜Ｐ５＞： U-L≧δ1ならば＜Ｐ４＞に移行し、それ以外の場合には＜Ｐ６＞へ移行し、
＜Ｐ６＞：L≠0の場合にLの値をε1とする、
処理を行う区間計算ステップと、
区間多項式計算部が、上記終結式R2(y,sjk,tmn)をyの多項式と見たとき、
（Ｉ）定数項が０である、
（ＩＩ）あるj≧1が存在して、yjの係数は0ではない定数である、
の少なくとも一方が成り立つか否かを判定し、少なくとも一方が成り立つならばε2を∞とし、二つの条件（Ｉ）（ＩＩ）がどちらも成り立たない場合には、上記初期値ε0,2と上記閾値δ2を用いて、
＜Ｑ１＞：ε2=ε0,2, L=0とし、
＜Ｑ２＞：I(ε2)を上記Ｋが実数体のとき実閉区間[-ε2,ε2]とし上記Ｋが複素数体のとき原点中心、半径ε2の閉円板{z∈C | |z|≦ε2}として、条件２[上記終結式R2(y,sjk,tmn)において、変数sjk ((j,k)∈Ｔ(f)), tmn((m,n)∈Ｔ(g))に当該I(ε2)を代入し、区間演算を行った結果の区間多項式が定数を含まない]を満たすか否かを判定し、条件２を満たさないならば＜Ｑ３＞へ移行し、条件２を満たすならばL=ε2と置き、ε2を2ε2で置き換え再度＜Ｑ２＞を実行し、
＜Ｑ３＞：U=ε2と置き、ε2を(ε2+L)/2で置き換え、
＜Ｑ４＞：＜Ｑ３＞で置き換えた後のε2について、上記条件２を満たすか否かを判定し、上記条件２を満たすならばL=ε2と置き、ε2を(ε2+U)/2で置き換え、そうでなければU=ε2と置き、ε2を(ε2+L)/2で置き換え、
＜Ｑ５＞：U-L≧δ2ならば＜Ｑ４＞に移行し、それ以外の場合には＜Ｑ６＞へ移行し、
＜Ｑ６＞：L≠0の場合にLの値をε2とする、
処理を行う区間多項式計算ステップと、
出力処理部が、上記区間計算ステップにおいて求められたε1と上記区間多項式計算ステップにおいて求められたε2を取得し、小さい方の値min{ε1,ε2}を許容誤差限界の下からの評価εとして出力する出力処理ステップと
を有する許容誤差限界評価方法。
【請求項４】
Ｋを実数体Ｒまたは複素数体とし、
Ｋ[x,y]をxとyを変数とするＫ上の二変数多項式環とし、
二変数多項式h(x,y)=Σj,k cjkxjyk∈Ｋ[x,y]に対して、多項式h(x,y)をxの多項式と見たときの次数をΩ、多項式h(x,y)をyの多項式と見たときの次数をΘとして、有限集合S(h)をS(h)={(j,k)|0≦j＜Ω, 0≦k≦Θ}∪{(Ω,k)|あるk’≧kが存在してcΩk’≠0}と定義し、
二変数多項式f(x,y)=Σj,k ajkxjyk∈Ｋ[x,y], g(x,y)=Σm,n bmnxmyn∈Ｋ[x,y]について、T(f)⊂S(f),T(g)⊂S(g)をそれぞれf(x,y),g(x,y)の係数のうち誤差を含むものの添字の集合とし、
f(x,y),g(x,y)について、少なくともいずれかの係数に誤差を含む任意の多項式をそれぞれ
【数３４】
としたとき、連立代数方程式~f(x,y)=~g(x,y)=0が複素数体上に解を持つような0<τ∈Ｒの最大値を許容誤差限界^εとして、当該許容誤差限界^εの下からの評価εを求める許容誤差限界評価方法であって、
上記二変数多項式f(x,y),g(x,y)は、
f(x,y) = ad(y)xd + … + a1(y)x + a0(y),
g(x,y) = be(y)xe + … + b1(y)x + b0(y)
と表したときに主係数ad(y)および主係数be(y)が定数0ではなく且つ主係数ad(y)および主係数be(y)は共通零点を持たないとし、
上記二変数多項式f(x,y)とg(x,y)のxに関する終結式Resx(f,g)は定数ではないとし、
予め定められた初期値をε0,1,ε0,2>0とし、
予め定められた閾値をδ1,δ2>0として、
多項式計算部が、上記~f(x,y)と、上記~g(x,y)と、~f(x,y)をxの多項式と見たときの主係数
【数３５】
と、~g(x,y)をxの多項式と見たときの主係数
【数３６】
と、主係数A(y,sdk)と主係数B(y,ten)とのyに関する終結式
【数３７】
と、~f(x,y)と~g(x,y)のxに関する終結式
【数３８】
を計算する多項式計算ステップと、
区間計算部が、上記多項式計算ステップにおいて得られた上記終結式R1(sdk,ten)が定数であるか否かを判定し、上記終結式R1(sdk,ten)が定数であればε1を∞とし、上記終結式R1(sdk,ten)が定数でなければ、上記初期値ε0,1と上記閾値δ1を用いて、
＜Ｐ１＞：ε1=ε0,1, L=0とし、
＜Ｐ２＞：I(ε1)を上記Ｋが実数体のとき実閉区間[-ε1,ε1]とし上記Ｋが複素数体のとき原点中心、半径ε1の閉円板{z∈C | |z|≦ε1}として、条件１[上記終結式R1(sdk,ten)において、変数sdk ((d,k)∈Ｔ(f)), ten ((e,n)∈Ｔ(g))に当該I(ε1)を代入して区間演算を行った結果の区間が０を含まない]を満たすか否かを判定し、条件１を満たさないならば＜Ｐ３＞へ移行し、条件１を満たすならばL=ε1と置き、ε1を2ε1で置き換え再度＜Ｐ２＞を実行し、
＜Ｐ３＞：U=ε1と置き、ε1を(ε1+L)/2で置き換え、
＜Ｐ４＞：＜Ｐ３＞で置き換えたε1について、上記条件１を満たすか否かを判定し、ε1が上記条件１を満たすならばL=ε1と置き、ε1を(ε1+U)/2で置き換え、そうでなければU=ε1と置き、ε1を(ε1+L)/2で置き換え、
＜Ｐ５＞： U-L≧δ1ならば＜Ｐ４＞に移行し、それ以外の場合には＜Ｐ６＞へ移行し、
＜Ｐ６＞：L≠0の場合にLの値をε1とする、
処理を行う区間計算ステップと、
判定部が、上記区間計算ステップにおいて得られた上記ε1が∞であるか否かを判定する判定ステップと、
第１区間多項式計算部が、上記区間計算ステップにおいて得られた上記ε1が∞である場合に、上記終結式R2(y,sjk,tmn)をyの多項式と見たとき、
（Ｉ）定数項が０である、
（ＩＩ）あるj≧1が存在して、yjの係数は0ではない定数である、
の少なくとも一方が成り立つか否かを判定し、少なくとも一方が成り立つならばε2を∞とし、二つの条件（Ｉ）（ＩＩ）がどちらも成り立たなければ、上記初期値ε0,2と上記閾値δ2を用いて、
＜Ｑ１＞：ε2=ε0,2, L=0とし、
＜Ｑ２＞：I(ε2)を上記Ｋが実数体のとき実閉区間[-ε2,ε2]とし上記Ｋが複素数体のとき原点中心、半径ε2の閉円板{z∈C | |z|≦ε2}として、条件２[上記終結式R2(y,sjk,tmn)において、変数sjk ((j,k)∈Ｔ(f)), tmn((m,n)∈Ｔ(g))に当該I(ε2)を代入し、区間演算を行った結果の区間多項式が定数を含まない]を満たすか否かを判定し、条件２を満たさないならば＜Ｑ３＞へ移行し、条件２を満たすならばL=ε2と置き、ε2を2ε2で置き換え再度＜Ｑ２＞を実行し、
＜Ｑ３＞：U=ε2と置き、ε2を(ε2+L)/2で置き換え、
＜Ｑ４＞：＜Ｑ３＞で置き換えた後のε2について、上記条件２を満たすか否かを判定し、上記条件２を満たすならばL=ε2と置き、ε2を(ε2+U)/2で置き換え、そうでなければU=ε2と置き、ε2を(ε2+L)/2で置き換え、
＜Ｑ５＞：U-L≧δ2ならば＜Ｑ４＞に移行し、それ以外の場合には＜Ｑ６＞へ移行し、
＜Ｑ６＞：L≠0の場合にLの値をε2とする、
処理を行う第１区間多項式計算ステップと、
第２区間多項式計算部が、上記区間計算ステップにおいて得られた上記ε1が∞でない場合に、I(ε1)を上記Ｋが実数体のとき実閉区間[-ε1,ε1]とし上記Ｋが複素数体のとき原点中心、半径ε1の閉円板{z∈C | |z|≦ε1}として、上記多項式計算ステップにおいて得られた上記終結式R2(y,sjk,tmn)において、変数sdk((d,k)∈T(f)), ten((e,n)∈T(g))にI(ε1)を代入し、区間演算を行った結果の区間多項式が定数を含むか否かを判定し、区間演算の結果の区間多項式が定数を含まない場合にはそのままε1を出力し、区間演算の結果の区間多項式が定数を含む場合には上記閾値δ2を用いて、
＜Ｗ１＞：L=0, U=ε1と置き、ε1を(ε1+L)/2で置き換え、
＜Ｗ２＞：＜Ｗ１＞で置き換えた後のε1について、上記条件２を満たすか否かを判定し、上記条件２を満たすならばL=ε1と置き、ε1を(ε1+U)/2で置き換え、そうでなければU=ε1と置き、ε1を(ε1+L)/2で置き換え、
＜Ｗ３＞：U-L≧δ2ならば＜Ｗ２＞に移行し、それ以外の場合には＜Ｗ４＞へ移行し、
＜Ｗ４＞：L≠0の場合にLの値をε1とする、
処理を行う第２区間多項式計算ステップと、
出力処理部が、上記第１区間多項式計算ステップにおいてε２が求められた場合には、当該ε2を許容誤差限界の下からの評価εとして出力し、上記第２区間多項式計算ステップにおいてε1が求められた場合には、当該ε1を許容誤差限界の下からの評価εとして出力する出力処理ステップと
を有する許容誤差限界評価方法。
【請求項５】
請求項１または請求項２に記載の許容誤差限界評価装置として、コンピュータを機能させるためのプログラム。
【請求項１】
Ｋを実数体Ｒまたは複素数体とし、
Ｋ[x,y]をxとyを変数とするＫ上の二変数多項式環とし、
二変数多項式h(x,y)=Σj,k cjkxjyk∈Ｋ[x,y]に対して、多項式h(x,y)をxの多項式と見たときの次数をΩ、多項式h(x,y)をyの多項式と見たときの次数をΘとして、有限集合S(h)をS(h)={(j,k)|0≦j＜Ω, 0≦k≦Θ}∪{(Ω,k)|あるk’≧kが存在してcΩk’≠0}と定義し、
二変数多項式f(x,y)=Σj,k ajkxjyk∈Ｋ[x,y], g(x,y)=Σm,n bmnxmyn∈Ｋ[x,y]について、T(f)⊂S(f),T(g)⊂S(g)をそれぞれf(x,y),g(x,y)の係数のうち誤差を含むものの添字の集合とし、
f(x,y),g(x,y)について、少なくともいずれかの係数に誤差を含む任意の多項式をそれぞれ
【数１９】
としたとき、連立代数方程式~f(x,y)=~g(x,y)=0が複素数体上に解を持つような0<τ∈Ｒの最大値を許容誤差限界^εとして、当該許容誤差限界^εの下からの評価εを求める許容誤差限界評価装置であって、
上記二変数多項式f(x,y),g(x,y)は、
f(x,y) = ad(y)xd + … + a1(y)x + a0(y),
g(x,y) = be(y)xe + … + b1(y)x + b0(y)
と表したときに主係数ad(y)および主係数be(y)が定数0ではなく且つ主係数ad(y)および主係数be(y)は共通零点を持たないとし、
上記二変数多項式f(x,y)とg(x,y)のxに関する終結式Resx(f,g)は定数ではないとし、
予め定められた初期値をε0,1,ε0,2>0とし、
予め定められた閾値をδ1,δ2>0として、
上記~f(x,y)と、上記~g(x,y)と、~f(x,y)をxの多項式と見たときの主係数
【数２０】
と、~g(x,y)をxの多項式と見たときの主係数
【数２１】
と、主係数A(y,sdk)と主係数B(y,ten)とのyに関する終結式
【数２２】
と、~f(x,y)と~g(x,y)のxに関する終結式
【数２３】
を計算する多項式計算部と、
上記多項式計算部によって得られた上記終結式R1(sdk,ten)が定数であるか否かを判定し、上記終結式R1(sdk,ten)が定数であればε1を∞とし、上記終結式R1(sdk,ten)が定数でなければ、上記初期値ε0,1と上記閾値δ1を用いて、
＜Ｐ１＞：ε1=ε0,1, L=0とし、
＜Ｐ２＞：I(ε1)を上記Ｋが実数体のとき実閉区間[-ε1,ε1]とし上記Ｋが複素数体のとき原点中心、半径ε1の閉円板{z∈C | |z|≦ε1}として、条件１[上記終結式R1(sdk,ten)において、変数sdk ((d,k)∈Ｔ(f)), ten ((e,n)∈Ｔ(g))に当該I(ε1)を代入して区間演算を行った結果の区間が０を含まない]を満たすか否かを判定し、条件１を満たさないならば＜Ｐ３＞へ移行し、条件１を満たすならばL=ε1と置き、ε1を2ε1で置き換え再度＜Ｐ２＞を実行し、
＜Ｐ３＞：U=ε1と置き、ε1を(ε1+L)/2で置き換え、
＜Ｐ４＞：＜Ｐ３＞で置き換えたε1について、上記条件１を満たすか否かを判定し、ε1が上記条件１を満たすならばL=ε1と置き、ε1を(ε1+U)/2で置き換え、そうでなければU=ε1と置き、ε1を(ε1+L)/2で置き換え、
＜Ｐ５＞： U-L≧δ1ならば＜Ｐ４＞に移行し、それ以外の場合には＜Ｐ６＞へ移行し、
＜Ｐ６＞：L≠0の場合にLの値をε1とする、
処理を行う区間計算部と、
上記終結式R2(y,sjk,tmn)をyの多項式と見たとき、
（Ｉ）定数項が０である、
（ＩＩ）あるj≧1が存在して、yjの係数は0ではない定数である、
の少なくとも一方が成り立つか否かを判定し、少なくとも一方が成り立つならばε2を∞とし、二つの条件（Ｉ）（ＩＩ）がどちらも成り立たない場合には、上記初期値ε0,2と上記閾値δ2を用いて、
＜Ｑ１＞：ε2=ε0,2, L=0とし、
＜Ｑ２＞：I(ε2)を上記Ｋが実数体のとき実閉区間[-ε2,ε2]とし上記Ｋが複素数体のとき原点中心、半径ε2の閉円板{z∈C | |z|≦ε2}として、条件２[上記終結式R2(y,sjk,tmn)において、変数sjk ((j,k)∈Ｔ(f)), tmn((m,n)∈Ｔ(g))に当該I(ε2)を代入し、区間演算を行った結果の区間多項式が定数を含まない]を満たすか否かを判定し、条件２を満たさないならば＜Ｑ３＞へ移行し、条件２を満たすならばL=ε2と置き、ε2を2ε2で置き換え再度＜Ｑ２＞を実行し、
＜Ｑ３＞：U=ε2と置き、ε2を(ε2+L)/2で置き換え、
＜Ｑ４＞：＜Ｑ３＞で置き換えた後のε2について、上記条件２を満たすか否かを判定し、上記条件２を満たすならばL=ε2と置き、ε2を(ε2+U)/2で置き換え、そうでなければU=ε2と置き、ε2を(ε2+L)/2で置き換え、
＜Ｑ５＞：U-L≧δ2ならば＜Ｑ４＞に移行し、それ以外の場合には＜Ｑ６＞へ移行し、
＜Ｑ６＞：L≠0の場合にLの値をε2とする、
処理を行う区間多項式計算部と、
上記区間計算部が計算したε1と上記区間多項式計算部が計算したε2を取得し、小さい方の値min{ε1,ε2}を許容誤差限界の下からの評価εとして出力する出力処理部と
を含む許容誤差限界評価装置。
【請求項２】
Ｋを実数体Ｒまたは複素数体とし、
Ｋ[x,y]をxとyを変数とするＫ上の二変数多項式環とし、
二変数多項式h(x,y)=Σj,k cjkxjyk∈Ｋ[x,y]に対して、多項式h(x,y)をxの多項式と見たときの次数をΩ、多項式h(x,y)をyの多項式と見たときの次数をΘとして、有限集合S(h)をS(h)={(j,k)|0≦j＜Ω, 0≦k≦Θ}∪{(Ω,k)|あるk’≧kが存在してcΩk’≠0}と定義し、
二変数多項式f(x,y)=Σj,k ajkxjyk∈Ｋ[x,y], g(x,y)=Σm,n bmnxmyn∈Ｋ[x,y]について、T(f)⊂S(f),T(g)⊂S(g)をそれぞれf(x,y),g(x,y)の係数のうち誤差を含むものの添字の集合とし、
f(x,y),g(x,y)について、少なくともいずれかの係数に誤差を含む任意の多項式をそれぞれ
【数２４】
としたとき、連立代数方程式~f(x,y)=~g(x,y)=0が複素数体上に解を持つような0<τ∈Ｒの最大値を許容誤差限界^εとして、当該許容誤差限界^εの下からの評価εを求める許容誤差限界評価装置であって、
上記二変数多項式f(x,y),g(x,y)は、
f(x,y) = ad(y)xd + … + a1(y)x + a0(y),
g(x,y) = be(y)xe + … + b1(y)x + b0(y)
と表したときに主係数ad(y)および主係数be(y)が定数0ではなく且つ主係数ad(y)および主係数be(y)は共通零点を持たないとし、
上記二変数多項式f(x,y)とg(x,y)のxに関する終結式Resx(f,g)は定数ではないとし、
予め定められた初期値をε0,1,ε0,2>0とし、
予め定められた閾値をδ1,δ2>0として、
上記~f(x,y)と、上記~g(x,y)と、~f(x,y)をxの多項式と見たときの主係数
【数２５】
と、~g(x,y)をxの多項式と見たときの主係数
【数２６】
と、主係数A(y,sdk)と主係数B(y,ten)とのyに関する終結式
【数２７】
と、~f(x,y)と~g(x,y)のxに関する終結式
【数２８】
を計算する多項式計算部と、
上記多項式計算部によって得られた上記終結式R1(sdk,ten)が定数であるか否かを判定し、上記終結式R1(sdk,ten)が定数であればε1を∞とし、上記終結式R1(sdk,ten)が定数でなければ、上記初期値ε0,1と上記閾値δ1を用いて、
＜Ｐ１＞：ε1=ε0,1, L=0とし、
＜Ｐ２＞：I(ε1)を上記Ｋが実数体のとき実閉区間[-ε1,ε1]とし上記Ｋが複素数体のとき原点中心、半径ε1の閉円板{z∈C | |z|≦ε1}として、条件１[上記終結式R1(sdk,ten)において、変数sdk ((d,k)∈Ｔ(f)), ten ((e,n)∈Ｔ(g))に当該I(ε1)を代入して区間演算を行った結果の区間が０を含まない]を満たすか否かを判定し、条件１を満たさないならば＜Ｐ３＞へ移行し、条件１を満たすならばL=ε1と置き、ε1を2ε1で置き換え再度＜Ｐ２＞を実行し、
＜Ｐ３＞：U=ε1と置き、ε1を(ε1+L)/2で置き換え、
＜Ｐ４＞：＜Ｐ３＞で置き換えたε1について、上記条件１を満たすか否かを判定し、ε1が上記条件１を満たすならばL=ε1と置き、ε1を(ε1+U)/2で置き換え、そうでなければU=ε1と置き、ε1を(ε1+L)/2で置き換え、
＜Ｐ５＞： U-L≧δ1ならば＜Ｐ４＞に移行し、それ以外の場合には＜Ｐ６＞へ移行し、
＜Ｐ６＞：L≠0の場合にLの値をε1とする、
処理を行う区間計算部と、
上記区間計算部が計算した上記ε1が∞であるか否かを判定する判定部と
上記区間計算部が計算した上記ε1が∞である場合に、上記終結式R2(y,sjk,tmn)をyの多項式と見たとき、
（Ｉ）定数項が０である、
（ＩＩ）あるj≧1が存在して、yjの係数は0ではない定数である、
の少なくとも一方が成り立つか否かを判定し、少なくとも一方が成り立つならばε2を∞とし、二つの条件（Ｉ）（ＩＩ）がどちらも成り立たなければ、上記初期値ε0,2と上記閾値δ2を用いて、
＜Ｑ１＞：ε2=ε0,2, L=0とし、
＜Ｑ２＞：I(ε2)を上記Ｋが実数体のとき実閉区間[-ε2,ε2]とし上記Ｋが複素数体のとき原点中心、半径ε2の閉円板{z∈C | |z|≦ε2}として、条件２[上記終結式R2(y,sjk,tmn)において、変数sjk ((j,k)∈Ｔ(f)), tmn((m,n)∈Ｔ(g))に当該I(ε2)を代入し、区間演算を行った結果の区間多項式が定数を含まない]を満たすか否かを判定し、条件２を満たさないならば＜Ｑ３＞へ移行し、条件２を満たすならばL=ε2と置き、ε2を2ε2で置き換え再度＜Ｑ２＞を実行し、
＜Ｑ３＞：U=ε2と置き、ε2を(ε2+L)/2で置き換え、
＜Ｑ４＞：＜Ｑ３＞で置き換えた後のε2について、上記条件２を満たすか否かを判定し、上記条件２を満たすならばL=ε2と置き、ε2を(ε2+U)/2で置き換え、そうでなければU=ε2と置き、ε2を(ε2+L)/2で置き換え、
＜Ｑ５＞：U-L≧δ2ならば＜Ｑ４＞に移行し、それ以外の場合には＜Ｑ６＞へ移行し、
＜Ｑ６＞：L≠0の場合にLの値をε2とする、
処理を行う第１区間多項式計算部と、
上記区間計算部が計算した上記ε1が∞でない場合に、I(ε1)を上記Ｋが実数体のとき実閉区間[-ε1,ε1]とし上記Ｋが複素数体のとき原点中心、半径ε1の閉円板{z∈C | |z|≦ε1}として、上記多項式計算部によって得られた上記終結式R2(y,sjk,tmn)において、変数sdk((d,k)∈T(f)), ten((e,n)∈T(g))にI(ε1)を代入し、区間演算を行った結果の区間多項式が定数を含むか否かを判定し、区間演算の結果の区間多項式が定数を含まない場合にはそのままε1を出力し、区間演算の結果の区間多項式が定数を含む場合には上記閾値δ2を用いて、
＜Ｗ１＞：L=0, U=ε1と置き、ε1を(ε1+L)/2で置き換え、
＜Ｗ２＞：＜Ｗ１＞で置き換えた後のε1について、上記条件２を満たすか否かを判定し、上記条件２を満たすならばL=ε1と置き、ε1を(ε1+U)/2で置き換え、そうでなければU=ε1と置き、ε1を(ε1+L)/2で置き換え、
＜Ｗ３＞：U-L≧δ2ならば＜Ｗ２＞に移行し、それ以外の場合には＜Ｗ４＞へ移行し、
＜Ｗ４＞：L≠0の場合にLの値をε1とする、
処理を行う第２区間多項式計算部と、
上記第１区間多項式計算部からε２が出力された場合には、当該ε2を許容誤差限界の下からの評価εとして出力し、上記第２区間多項式計算部からε1が出力された場合には、当該ε1を許容誤差限界の下からの評価εとして出力する出力処理部と
を含む許容誤差限界評価装置。
【請求項３】
Ｋを実数体Ｒまたは複素数体とし、
Ｋ[x,y]をxとyを変数とするＫ上の二変数多項式環とし、
二変数多項式h(x,y)=Σj,k cjkxjyk∈Ｋ[x,y]に対して、多項式h(x,y)をxの多項式と見たときの次数をΩ、多項式h(x,y)をyの多項式と見たときの次数をΘとして、有限集合S(h)をS(h)={(j,k)|0≦j＜Ω, 0≦k≦Θ}∪{(Ω,k)|あるk’≧kが存在してcΩk’≠0}と定義し、
二変数多項式f(x,y)=Σj,k ajkxjyk∈Ｋ[x,y], g(x,y)=Σm,n bmnxmyn∈Ｋ[x,y]について、T(f)⊂S(f),T(g)⊂S(g)をそれぞれf(x,y),g(x,y)の係数のうち誤差を含むものの添字の集合とし、
f(x,y),g(x,y)について、少なくともいずれかの係数に誤差を含む任意の多項式をそれぞれ
【数２９】
としたとき、連立代数方程式~f(x,y)=~g(x,y)=0が複素数体上に解を持つような0<τ∈Ｒの最大値を許容誤差限界^εとして、当該許容誤差限界^εの下からの評価εを求める許容誤差限界評価方法であって、
上記二変数多項式f(x,y),g(x,y)は、
f(x,y) = ad(y)xd + … + a1(y)x + a0(y),
g(x,y) = be(y)xe + … + b1(y)x + b0(y)
と表したときに主係数ad(y)および主係数be(y)が定数0ではなく且つ主係数ad(y)および主係数be(y)は共通零点を持たないとし、
上記二変数多項式f(x,y)とg(x,y)のxに関する終結式Resx(f,g)は定数ではないとし、
予め定められた初期値をε0,1,ε0,2>0とし、
予め定められた閾値をδ1,δ2>0として、
多項式計算部が、上記~f(x,y)と、上記~g(x,y)と、~f(x,y)をxの多項式と見たときの主係数
【数３０】
と、~g(x,y)をxの多項式と見たときの主係数
【数３１】
と、主係数A(y,sdk)と主係数B(y,ten)とのyに関する終結式
【数３２】
と、~f(x,y)と~g(x,y)のxに関する終結式
【数３３】
を計算する多項式計算ステップと、
区間計算部が、上記多項式計算ステップにおいて得られた上記終結式R1(sdk,ten)が定数であるか否かを判定し、上記終結式R1(sdk,ten)が定数であればε1を∞とし、上記終結式R1(sdk,ten)が定数でなければ、上記初期値ε0,1と上記閾値δ1を用いて、
＜Ｐ１＞：ε1=ε0,1, L=0とし、
＜Ｐ２＞：I(ε1)を上記Ｋが実数体のとき実閉区間[-ε1,ε1]とし上記Ｋが複素数体のとき原点中心、半径ε1の閉円板{z∈C | |z|≦ε1}として、条件１[上記終結式R1(sdk,ten)において、変数sdk ((d,k)∈Ｔ(f)), ten ((e,n)∈Ｔ(g))に当該I(ε1)を代入して区間演算を行った結果の区間が０を含まない]を満たすか否かを判定し、条件１を満たさないならば＜Ｐ３＞へ移行し、条件１を満たすならばL=ε1と置き、ε1を2ε1で置き換え再度＜Ｐ２＞を実行し、
＜Ｐ３＞：U=ε1と置き、ε1を(ε1+L)/2で置き換え、
＜Ｐ４＞：＜Ｐ３＞で置き換えたε1について、上記条件１を満たすか否かを判定し、ε1が上記条件１を満たすならばL=ε1と置き、ε1を(ε1+U)/2で置き換え、そうでなければU=ε1と置き、ε1を(ε1+L)/2で置き換え、
＜Ｐ５＞： U-L≧δ1ならば＜Ｐ４＞に移行し、それ以外の場合には＜Ｐ６＞へ移行し、
＜Ｐ６＞：L≠0の場合にLの値をε1とする、
処理を行う区間計算ステップと、
区間多項式計算部が、上記終結式R2(y,sjk,tmn)をyの多項式と見たとき、
（Ｉ）定数項が０である、
（ＩＩ）あるj≧1が存在して、yjの係数は0ではない定数である、
の少なくとも一方が成り立つか否かを判定し、少なくとも一方が成り立つならばε2を∞とし、二つの条件（Ｉ）（ＩＩ）がどちらも成り立たない場合には、上記初期値ε0,2と上記閾値δ2を用いて、
＜Ｑ１＞：ε2=ε0,2, L=0とし、
＜Ｑ２＞：I(ε2)を上記Ｋが実数体のとき実閉区間[-ε2,ε2]とし上記Ｋが複素数体のとき原点中心、半径ε2の閉円板{z∈C | |z|≦ε2}として、条件２[上記終結式R2(y,sjk,tmn)において、変数sjk ((j,k)∈Ｔ(f)), tmn((m,n)∈Ｔ(g))に当該I(ε2)を代入し、区間演算を行った結果の区間多項式が定数を含まない]を満たすか否かを判定し、条件２を満たさないならば＜Ｑ３＞へ移行し、条件２を満たすならばL=ε2と置き、ε2を2ε2で置き換え再度＜Ｑ２＞を実行し、
＜Ｑ３＞：U=ε2と置き、ε2を(ε2+L)/2で置き換え、
＜Ｑ４＞：＜Ｑ３＞で置き換えた後のε2について、上記条件２を満たすか否かを判定し、上記条件２を満たすならばL=ε2と置き、ε2を(ε2+U)/2で置き換え、そうでなければU=ε2と置き、ε2を(ε2+L)/2で置き換え、
＜Ｑ５＞：U-L≧δ2ならば＜Ｑ４＞に移行し、それ以外の場合には＜Ｑ６＞へ移行し、
＜Ｑ６＞：L≠0の場合にLの値をε2とする、
処理を行う区間多項式計算ステップと、
出力処理部が、上記区間計算ステップにおいて求められたε1と上記区間多項式計算ステップにおいて求められたε2を取得し、小さい方の値min{ε1,ε2}を許容誤差限界の下からの評価εとして出力する出力処理ステップと
を有する許容誤差限界評価方法。
【請求項４】
Ｋを実数体Ｒまたは複素数体とし、
Ｋ[x,y]をxとyを変数とするＫ上の二変数多項式環とし、
二変数多項式h(x,y)=Σj,k cjkxjyk∈Ｋ[x,y]に対して、多項式h(x,y)をxの多項式と見たときの次数をΩ、多項式h(x,y)をyの多項式と見たときの次数をΘとして、有限集合S(h)をS(h)={(j,k)|0≦j＜Ω, 0≦k≦Θ}∪{(Ω,k)|あるk’≧kが存在してcΩk’≠0}と定義し、
二変数多項式f(x,y)=Σj,k ajkxjyk∈Ｋ[x,y], g(x,y)=Σm,n bmnxmyn∈Ｋ[x,y]について、T(f)⊂S(f),T(g)⊂S(g)をそれぞれf(x,y),g(x,y)の係数のうち誤差を含むものの添字の集合とし、
f(x,y),g(x,y)について、少なくともいずれかの係数に誤差を含む任意の多項式をそれぞれ
【数３４】
としたとき、連立代数方程式~f(x,y)=~g(x,y)=0が複素数体上に解を持つような0<τ∈Ｒの最大値を許容誤差限界^εとして、当該許容誤差限界^εの下からの評価εを求める許容誤差限界評価方法であって、
上記二変数多項式f(x,y),g(x,y)は、
f(x,y) = ad(y)xd + … + a1(y)x + a0(y),
g(x,y) = be(y)xe + … + b1(y)x + b0(y)
と表したときに主係数ad(y)および主係数be(y)が定数0ではなく且つ主係数ad(y)および主係数be(y)は共通零点を持たないとし、
上記二変数多項式f(x,y)とg(x,y)のxに関する終結式Resx(f,g)は定数ではないとし、
予め定められた初期値をε0,1,ε0,2>0とし、
予め定められた閾値をδ1,δ2>0として、
多項式計算部が、上記~f(x,y)と、上記~g(x,y)と、~f(x,y)をxの多項式と見たときの主係数
【数３５】
と、~g(x,y)をxの多項式と見たときの主係数
【数３６】
と、主係数A(y,sdk)と主係数B(y,ten)とのyに関する終結式
【数３７】
と、~f(x,y)と~g(x,y)のxに関する終結式
【数３８】
を計算する多項式計算ステップと、
区間計算部が、上記多項式計算ステップにおいて得られた上記終結式R1(sdk,ten)が定数であるか否かを判定し、上記終結式R1(sdk,ten)が定数であればε1を∞とし、上記終結式R1(sdk,ten)が定数でなければ、上記初期値ε0,1と上記閾値δ1を用いて、
＜Ｐ１＞：ε1=ε0,1, L=0とし、
＜Ｐ２＞：I(ε1)を上記Ｋが実数体のとき実閉区間[-ε1,ε1]とし上記Ｋが複素数体のとき原点中心、半径ε1の閉円板{z∈C | |z|≦ε1}として、条件１[上記終結式R1(sdk,ten)において、変数sdk ((d,k)∈Ｔ(f)), ten ((e,n)∈Ｔ(g))に当該I(ε1)を代入して区間演算を行った結果の区間が０を含まない]を満たすか否かを判定し、条件１を満たさないならば＜Ｐ３＞へ移行し、条件１を満たすならばL=ε1と置き、ε1を2ε1で置き換え再度＜Ｐ２＞を実行し、
＜Ｐ３＞：U=ε1と置き、ε1を(ε1+L)/2で置き換え、
＜Ｐ４＞：＜Ｐ３＞で置き換えたε1について、上記条件１を満たすか否かを判定し、ε1が上記条件１を満たすならばL=ε1と置き、ε1を(ε1+U)/2で置き換え、そうでなければU=ε1と置き、ε1を(ε1+L)/2で置き換え、
＜Ｐ５＞： U-L≧δ1ならば＜Ｐ４＞に移行し、それ以外の場合には＜Ｐ６＞へ移行し、
＜Ｐ６＞：L≠0の場合にLの値をε1とする、
処理を行う区間計算ステップと、
判定部が、上記区間計算ステップにおいて得られた上記ε1が∞であるか否かを判定する判定ステップと、
第１区間多項式計算部が、上記区間計算ステップにおいて得られた上記ε1が∞である場合に、上記終結式R2(y,sjk,tmn)をyの多項式と見たとき、
（Ｉ）定数項が０である、
（ＩＩ）あるj≧1が存在して、yjの係数は0ではない定数である、
の少なくとも一方が成り立つか否かを判定し、少なくとも一方が成り立つならばε2を∞とし、二つの条件（Ｉ）（ＩＩ）がどちらも成り立たなければ、上記初期値ε0,2と上記閾値δ2を用いて、
＜Ｑ１＞：ε2=ε0,2, L=0とし、
＜Ｑ２＞：I(ε2)を上記Ｋが実数体のとき実閉区間[-ε2,ε2]とし上記Ｋが複素数体のとき原点中心、半径ε2の閉円板{z∈C | |z|≦ε2}として、条件２[上記終結式R2(y,sjk,tmn)において、変数sjk ((j,k)∈Ｔ(f)), tmn((m,n)∈Ｔ(g))に当該I(ε2)を代入し、区間演算を行った結果の区間多項式が定数を含まない]を満たすか否かを判定し、条件２を満たさないならば＜Ｑ３＞へ移行し、条件２を満たすならばL=ε2と置き、ε2を2ε2で置き換え再度＜Ｑ２＞を実行し、
＜Ｑ３＞：U=ε2と置き、ε2を(ε2+L)/2で置き換え、
＜Ｑ４＞：＜Ｑ３＞で置き換えた後のε2について、上記条件２を満たすか否かを判定し、上記条件２を満たすならばL=ε2と置き、ε2を(ε2+U)/2で置き換え、そうでなければU=ε2と置き、ε2を(ε2+L)/2で置き換え、
＜Ｑ５＞：U-L≧δ2ならば＜Ｑ４＞に移行し、それ以外の場合には＜Ｑ６＞へ移行し、
＜Ｑ６＞：L≠0の場合にLの値をε2とする、
処理を行う第１区間多項式計算ステップと、
第２区間多項式計算部が、上記区間計算ステップにおいて得られた上記ε1が∞でない場合に、I(ε1)を上記Ｋが実数体のとき実閉区間[-ε1,ε1]とし上記Ｋが複素数体のとき原点中心、半径ε1の閉円板{z∈C | |z|≦ε1}として、上記多項式計算ステップにおいて得られた上記終結式R2(y,sjk,tmn)において、変数sdk((d,k)∈T(f)), ten((e,n)∈T(g))にI(ε1)を代入し、区間演算を行った結果の区間多項式が定数を含むか否かを判定し、区間演算の結果の区間多項式が定数を含まない場合にはそのままε1を出力し、区間演算の結果の区間多項式が定数を含む場合には上記閾値δ2を用いて、
＜Ｗ１＞：L=0, U=ε1と置き、ε1を(ε1+L)/2で置き換え、
＜Ｗ２＞：＜Ｗ１＞で置き換えた後のε1について、上記条件２を満たすか否かを判定し、上記条件２を満たすならばL=ε1と置き、ε1を(ε1+U)/2で置き換え、そうでなければU=ε1と置き、ε1を(ε1+L)/2で置き換え、
＜Ｗ３＞：U-L≧δ2ならば＜Ｗ２＞に移行し、それ以外の場合には＜Ｗ４＞へ移行し、
＜Ｗ４＞：L≠0の場合にLの値をε1とする、
処理を行う第２区間多項式計算ステップと、
出力処理部が、上記第１区間多項式計算ステップにおいてε２が求められた場合には、当該ε2を許容誤差限界の下からの評価εとして出力し、上記第２区間多項式計算ステップにおいてε1が求められた場合には、当該ε1を許容誤差限界の下からの評価εとして出力する出力処理ステップと
を有する許容誤差限界評価方法。
【請求項５】
請求項１または請求項２に記載の許容誤差限界評価装置として、コンピュータを機能させるためのプログラム。
【図１】
【図２】
【図３】
【図４】
【図２】
【図３】
【図４】
【公開番号】特開２０１１−１９２１９９（Ｐ２０１１−１９２１９９Ａ）
【公開日】平成２３年９月２９日（２０１１．９．２９）
【国際特許分類】
【出願番号】特願２０１０−５９７６３（Ｐ２０１０−５９７６３）
【出願日】平成２２年３月１６日（２０１０．３．１６）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２３年９月２９日（２０１１．９．２９）
【国際特許分類】
【出願日】平成２２年３月１６日（２０１０．３．１６）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]