(57)【要約】【課題】実係数多項式ｐ（Ｘ）が実係数多項式ｆ（Ｘ）で割り切れるような実係数多項式ｐ（Ｘ），ｆ（Ｘ）がそれぞれ実区間多項式Ｐ（Ｘ），Ｆ（Ｘ）の中に存在するかどうかを判定するための技術を提供する。【解決手段】第一実区間多項式Ｐ（Ｘ）を第二実区間多項式Ｆ（Ｘ）で割った剰余を求める。剰余の同類項をまとめた場合に上記剰余はｍ（ｍは１以上の整数）個の項から構成されるとして、上記ｍ個の項のそれぞれの係数から成るｍ個の制約多項式Ｆ（Ｃ）を生成する。区間ヤコビ行列Ｊ（ｃ＊（ｋ），ＣＩ（ｋ））を用いてＦ（Ｃ）＝０を線形化した後に、区間ガウスの消去法を用いて連立区間多項式Ｆ（Ｃ）＝０についての緩和した解Ｎ’（ｃ＊（ｋ），ＣＩ（ｋ））を求める。Ｎ（ｃ＊（ｋ），ｑＩ（ｋ））⊆上記領域ＣＩ（ｋ）であれば、上記第一実区間多項式が上記第二実区間多項式を擬因子として持つと判定できる。【選択図】図１
2010122905.tif 000002
【特許請求の範囲】
【請求項１】
第一実区間多項式が第二実区間多項式を擬因子として持つかどうかを判定する擬因子判定装置において、
予め定められた項順序の下で第一実区間多項式を第二実区間多項式で割った剰余を求める剰余演算部と、
上記剰余の同類項をまとめた場合に上記剰余はｍ（ｍは１以上の整数）個の項から構成されるとして、上記ｍ個の項のそれぞれの係数から成る、上記第一実区間多項式及び上記第二実区間多項式の区間数の内のｎ（ｎは１以上の整数）個の区間数Ｃｉ（ｉ＝１，…，ｎ、ｌｉとｈｉをｌｉ≦ｈｉの関係を満たす有理数としてＣｉ＝［ｌｉ，ｈｉ］）を変数とするｍ個の制約多項式Ｆ（Ｃ）（Ｆ（Ｃ）＝（ｆ１（Ｃ），…，ｆｍ（Ｃ））、Ｃ＝（Ｃ１，…，Ｃｎ））を生成する制約多項式生成部と、
ｍとｎとの大小関係を判定する大小関係判定部と、
上記大小関係判定部においてｍ≧ｎと判定された場合に、ｋを０以上の整数として、上記ｎ個の区間数が作るｎ次元の領域ＣＩに含まれるｎ次元の領域ＣＩ（ｋ）に含まれる任意の一点ｃ＊（ｋ）の位置を基準として上記ｍ個の制約多項式Ｆ（Ｃ）を上記ｍ個の制約多項式Ｆ（Ｃ）についての各要素が区間数となる区間ヤコビ行列Ｊ（ｃ＊（ｋ），ＣＩ（ｋ））を用いて一次近似した式を０とするｎ次元の領域Ｎ（ｃ＊（ｋ），ＣＩ（ｋ））を含む領域Ｎ’（ｃ＊（ｋ），ＣＩ（ｋ））を区間ガウスの消去法を用いて求め、求まった領域Ｎ’（ｃ＊（ｋ），ＣＩ（ｋ））と上記領域ＣＩ（ｋ）との共通部分である領域ＣＩ（ｋ＋１）を求める第一領域縮小部と、
上記領域Ｎ’（ｃ＊（ｋ），ＣＩ（ｋ））と上記領域ＣＩ（ｋ）との包含関係を判定して、上記領域Ｎ（ｃ＊（ｋ），ＣＩ（ｋ））⊆上記領域ＣＩ（ｋ）であれば、上記第一実区間多項式が上記第二実区間多項式を擬因子として持つと判定する第一包含関係判定部と、
を含む擬因子判定装置。
【請求項２】
請求項１に記載の擬因子判定装置において、
上記大小関係判定部においてｍ＜ｎと判定された場合に、上記ｎ個の区間数が作るｎ次元の領域のある点Ｃのその領域の中点からの距離を目的関数ｇ（Ｃ）として、その目的関数ｇ（Ｃ）を極小にするための、上記ｎ個の区間数及びそのｎ個の区間数以外のｍ＋１個の区間数を変数とするｎ＋１個の制約多項式を生成する制約多項式増加部を更に含み、
上記第一領域縮小部は、ｋを０以上の整数として、上記ｍ＋ｎ＋１個の区間数が作るｍ＋ｎ＋１次元の領域ＣＩに含まれるｍ＋ｎ＋１次元の領域ＣＩ（ｋ）に含まれる任意の一点ｃ＊（ｋ）の位置を基準として上記ｍ＋ｎ＋１個の制約多項式を上記ｍ＋ｎ＋１個の制約多項式についての各要素が区間数となる区間ヤコビ行列を用いて一次近似した式を０とするｍ＋ｎ＋１次元の領域Ｎ（ｃ＊（ｋ），ＣＩ（ｋ））を含む領域Ｎ’（ｃ＊（ｋ），ＣＩ（ｋ））を区間ガウスの消去法を用いて求め、求まった領域Ｎ’（ｃ＊（ｋ），ＣＩ（ｋ））と上記領域ＣＩ（ｋ）との共通部分である領域ＣＩ（ｋ＋１）を求める部である、
ことを特徴とする擬因子判定装置。
【請求項３】
請求項１に記載の擬因子判定装置において、
上記大小関係判定部においてｍ＜ｎと判定された場合に、Ｉを単位行列、上記ｎ個の区間数が作るｎ次元の領域に含まれるｎ次元の領域をＣＩ＄＝ＣＩ＄ｂａｓｅ×ＣＩ＄ｎｏｎｂａｓｅとし、領域ＣＩ＄ｂａｓｅを上記ｎ個の変数から選択されたｍ個の基底変数ｖａｒ（Ｃｂａｓｅ）が領域ＣＩ＄において作る領域をとし、領域ＣＩ＄ｎｏｎｂａｓｅを上記ｎ個の変数の上記基底変数ｖａｒ（Ｃｂａｓｅ）以外のｎ−ｍ個の非基底変数ｖａｒ（Ｃｎｏｎｂａｓｅ）が領域ＣＩ＄において作る領域をＣＩ＄ｎｏｎｂａｓｅとし、領域ＣＩ＄ｂａｓｅに含まれる任意の一点をｃ＊＄ｂａｓｅとし、領域ＣＩ＄ｂａｓｅの中点をｃｃ＄ｂａｓｅとし、εを小さい正の数とし、領域ＣＩ＄ｂａｓｅの各成分の半径を要素とするベクトルをｒａｄ（ＣＩ＄ｂａｓｅ）とし、ｃｃ＄ｂａｓｅを中心として各成分の半径がε・ｒａｄ（ＣＩ＄ｂａｓｅ）である領域をεＣＩ＄ｂａｓｅとし、ｃ♯＄を必要に応じて選択される領域ＣＩ＄内の任意の一点とし、・を各要素が区間数である行列とし、・ｃを・の要素である各区間数の中点からなる行列とし、区間ヤコビ行列Ｊ（ｃ＃＄，ＣＩ＄）∈Ｉｍ×ｎのｉ（ｉ＝１，…，ｎ）番目の列が変数Ｃｉに対応しているとし、Ｊ（ｃ＃＄，ＣＩ＄）の中から基底変数ｖａｒ（Ｃｂａｓｅ）に対応する列を取ってきた区間行列Ｊｂａｓｅ（ｃ＃＄，ＣＩ＄）∈Ｉｍ×ｍについての線形変形行列Ｂ∈Ｒｍ×ｍをＢ＝（Ｊｂａｓｅ（ｃ＃＄，ＣＩ＄）ｃ）−１として、下記式の関係を有する領域Ｎ（ｃ♯＄，ｑＩ＄）を求める第二領域縮小部と、
Ｍ＝Ｉ−ＢＪ（ｃ＃＄，ＣＩ＄）
Ｎ（ｃ♯＄，ＣＩ＄）＝ｃ＊＄ｂａｓｅ−ＢＦ（εＣＩ＄ｂａｓｅ，ＣＩ＄ｎｏｎｂａｓｅ）＋Ｍ（ＣＩ＄ｂａｓｅ−ｃ＊＄ｂａｓｅ）
上記領域Ｎ（ｃ♯＄，ＣＩ＄）と上記領域ＣＩ＄ｂａｓｅとの包含関係を判定して、上記領域Ｎ（ｃ♯＄，ＣＩ＄）⊂上記領域ＣＩ＄ｂａｓｅであれば、上記第一実区間多項式が上記第二実区間多項式を擬因子として持つと判定する第二包含関係判定部と、
を更に含むことを特徴とする擬因子判定装置。
【請求項４】
請求項１から３の何れかに記載の擬因子判定装置において、
・は各要素が区間数である行列であり、・ｃは・の要素である各区間数の中点からなる行列とし、上記領域縮小部は、ｍ＝ｎの場合には行列Ｂ∈Ｒｍ×ｍを（Ｊ（ｃ＊（ｋ），ＣＩ（ｋ））ｃ）−１とし、ｍ＞ｎの場合には行列Ｂ∈Ｒｍ×ｍをＪ（ｃ＊（ｋ），ＣＩ（ｋ））ｃの上ｎ行が単位行列、下ｍ−ｎ行が零行列となる行列として、
上記第一領域縮小部は、上記一次近似した式に代えて、上記一次近似した式に行列Ｂをかけることにより正規化した式を０とするｎ次元の領域Ｎ（ｃ＊（ｋ），ＣＩ（ｋ））を含む領域Ｎ’（ｃ＊（ｋ），ＣＩ（ｋ））を区間ガウスの消去法を用いて求める、
ことを特徴とする擬因子判定装置。
【請求項５】
請求項１から４の何れかに記載の擬因子判定装置において、
上記領域ＣＩ（ｋ）＝上記領域ＣＩ（ｋ＋１）であるかどうかを判定する同一領域判定部を更に備え、
上記領域ＣＩ（ｋ）＝上記領域ＣＩ（ｋ＋１）であると判定された場合には、上記領域縮小部は、領域ＣＩ（ｋ）を分割した各領域を新たなｎ次元の領域ＣＩ（ｋ）として、新たな領域ＣＩ（ｋ＋１）を求める、
ことを特徴とする擬因子判定装置。
【請求項６】
請求項１から５の何れかに記載の擬因子判定装置において、
上記制約多項式Ｆ（Ｃ）の中に常に非零となる制約多項式があるかどうかを判定して、常に非零となる制約多項式がある場合には、第一実区間多項式は第二実区間多項式を擬因子として持たないと判定する判定部、
を更に含むことを特徴とする擬因子判定装置。
【請求項７】
請求項１から６の何れかに記載の擬因子判定装置において、
上記ｍ個の制約多項式が上記ｎ個の変数が線形であるかどうかを判定する線形判定部を更に含み、
上記大小関係判定部は、線形であると判定された場合に、ｍとｎとの大小関係を判定する、
ことを特徴とする擬因子判定装置。
【請求項８】
第一実区間多項式が第二実区間多項式を擬因子として持つかどうかを判定する擬因子判定方法において、
剰余演算部が、予め定められた項順序の下で第一実区間多項式を第二実区間多項式で割った剰余を求める剰余演算ステップと、
制約多項式生成部が、上記剰余の同類項をまとめた場合に上記剰余はｍ（ｍは１以上の整数）個の項から構成されるとして、上記ｍ個の項のそれぞれの係数から成る、上記第一実区間多項式及び上記第二実区間多項式の区間数の内のｎ（ｎは１以上の整数）個の区間数Ｃｉ（ｉ＝１，…，ｎ、ｌｉとｈｉをｌｉ≦ｈｉの関係を満たす有理数としてＣｉ＝［ｌｉ，ｈｉ］）を変数とするｍ個の制約多項式Ｆ（Ｃ）（Ｆ（Ｃ）＝（ｆ１（Ｃ），…，ｆｍ（Ｃ））、Ｃ＝（Ｃ１，…，Ｃｎ））を生成する制約多項式生成ステップと、
大小関係判定部が、ｍとｎとの大小関係を判定する大小関係判定ステップと、
第一領域縮小部が、上記大小関係判定ステップにおいてｍ≧ｎと判定された場合に、ｋを０以上の整数として、上記ｎ個の区間数が作るｎ次元の領域ＣＩに含まれるｎ次元の領域ＣＩ（ｋ）に含まれる任意の一点ｃ＊（ｋ）の位置を基準として上記ｍ個の制約多項式Ｆ（Ｃ）を上記ｍ個の制約多項式Ｆ（Ｃ）についての各要素が区間数となる区間ヤコビ行列Ｊ（ｃ＊（ｋ），ＣＩ（ｋ））を用いて一次近似した式を０とするｎ次元の領域Ｎ（ｃ＊（ｋ），ＣＩ（ｋ））を含む領域Ｎ’（ｃ＊（ｋ），ＣＩ（ｋ））を区間ガウスの消去法を用いて求め、求まった領域Ｎ’（ｃ＊（ｋ），ＣＩ（ｋ））と上記領域ＣＩ（ｋ）との共通部分である領域ＣＩ（ｋ＋１）を求める第一領域縮小ステップと、
第一包含関係判定部が、上記領域Ｎ’（ｃ＊（ｋ），ＣＩ（ｋ））と上記領域ＣＩ（ｋ）との包含関係を判定して、上記領域Ｎ（ｃ＊（ｋ），ＣＩ（ｋ））⊆上記領域ＣＩ（ｋ）であれば、上記第一実区間多項式が上記第二実区間多項式を擬因子として持つと判定する第一包含関係判定ステップと、
を含む擬因子判定方法。
【請求項９】
請求項１から７の何れかに記載の擬因子判定装置の各部としてコンピュータを機能させるための擬因子判定プログラム。
【請求項１０】
請求項９に記載の擬因子判定プログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータを用いて、係数に誤差のある多項式である区間多項式についての演算を行う技術に関する。より詳細には、実区間多項式Ｐ，Ｆが与えられたときに、ｆがｐの実因子であるような多項式ｆ∈Ｆ，多項式ｐ∈Ｐが存在するかどうかを判定する技術に関する。
【背景技術】
【０００２】
まず、区間多項式の記法、用語等について説明する。ｋを１以上の整数として、ｋ個の変数ｘ１，…，ｘｋをまとめてＸと書く。すなわち、Ｘ＝（ｘ１，…，ｘｋ）である。区間多項式Ｐ（Ｘ）は、数の集合である区間数Ａｉ、予め指定された多項式ｅｉ（Ｘ）（１≦ｉ≦ｎ’）に対して、ａｉ∈Ａｉである多項式Σｉ＝１ｎ’ａｉｅｉ（Ｘ）全体の集合のことであり、区間多項式Ｐ（Ｘ）をΣｉ＝１ｎ’Ａｉｅｉ（Ｘ）と表記する。以下、区間数Ａｉとして実の閉区間［ｌｉａ，ｈｉａ］（ｌはローマ字のエル、ｌｉａ，ｈｉａはｌｉａ≦ｈｉａの関係を有する有理数）を用い、ｅｉ（Ｘ）は有理係数多項式とする。各区間［ｌｉａ，ｈｉａ］＝｛ｃｉ∈Ｒ｜ｌｉａ≦ｃｉ≦ｈｉａ｝を区間数と呼ぶ。ｅｉ（Ｘ）は有理係数多項式であり、区間数Ａｉとして実数Ｒを用いるため、区間多項式Ｐ（Ｘ）は係数が実数である多項式の集合から成ることになる。したがって、区間多項式Ｐ（Ｘ）のことを、実区間多項式とも呼ぶ。
【０００３】
ここで、次の問題１を考える。以下の問題１において、ｂｊは有理数であり、ｄｊ（Ｘ）（１≦ｊ≦ｍ’）は有理係数多項式であるとする。
≪問題１≫
与えられた、実区間多項式Ｐ（Ｘ）、実係数多項式ｆ（Ｘ）
Ｐ（Ｘ）＝Σｉ＝１ｎ’Ａｉｅｉ（Ｘ），ｆ（Ｘ）＝Σｉ＝１ｍ’ｂｊｄｊ（Ｘ）
に対して、実係数多項式ｆ（Ｘ）で割り切れる多項式ｐ（Ｘ）がＰ（Ｘ）の中に存在するかどうか、すなわち実係数多項式ｆ（Ｘ）を実因子として持つｐ（Ｘ）がＰ（Ｘ）の中に存在するかどうかを判定せよ（≪問題１≫終り）。
【０００４】
この問題を解決するための解決する技術として、非特許文献１に記載された技術がある。
【非特許文献１】H.Sekigawa, “On Real Factors of Real Interval Polynomials”, Proc. International Symposium on Symbolic and Algebraic Computation (ISSAC 2007), pp.311-338, 2007
【発明の開示】
【発明が解決しようとする課題】
【０００５】
非特許文献１に記載された技術は除多項式ｆ（Ｘ）が実係数多項式であることを前提としており、除多項式が実区間多項式である場合には非特許文献１に記載された技術を用いることができない場合があるという問題があった。
【０００６】
本発明は、被除多項式Ｐ（Ｘ）及び除多項式Ｆ（Ｘ）が共に実区間多項式である場合に、実係数多項式ｐ（Ｘ）が実係数多項式ｆ（Ｘ）で割り切れるような実係数多項式ｐ（Ｘ），ｆ（Ｘ）がそれぞれ実区間多項式Ｐ（Ｘ），Ｆ（Ｘ）の中に存在するかどうか、すなわち実区間多項式Ｐ（Ｘ）が実区間多項式Ｆ（Ｘ）を擬因子として持つかどうかを判定する擬因子判定装置、方法、プログラム及びその記録媒体を提供することを目的とする。
【課題を解決するための手段】
【０００７】
本発明による、第一実区間多項式が第二実区間多項式を擬因子として持つかどうかを判定する擬因子判定装置によれば、予め定められた項順序の下で第一実区間多項式を第二実区間多項式で割った剰余を求める剰余演算部と、剰余の同類項をまとめた場合に剰余はｍ（ｍは１以上の整数）個の項から構成されるとして、ｍ個の項のそれぞれの係数から成る、第一実区間多項式及び第二実区間多項式の区間数の内のｎ（ｎは１以上の整数）個の区間数Ｃｉ（ｉ＝１，…，ｎ、ｌｉとｈｉをｌｉ≦ｈｉの関係を満たす有理数としてＣｉ＝［ｌｉ，ｈｉ］）を変数とするｍ個の制約多項式Ｆ（Ｃ）（Ｆ（Ｃ）＝（ｆ１（Ｃ），…，ｆｍ（Ｃ））、Ｃ＝（Ｃ１，…，Ｃｎ））を生成する制約多項式生成部と、ｍとｎとの大小関係を判定する大小関係判定部と、大小関係判定部においてｍ≧ｎと判定された場合に、ｋを０以上の整数として、ｎ個の区間数が作るｎ次元の領域ＣＩに含まれるｎ次元の領域ＣＩ（ｋ）に含まれる任意の一点ｃ＊（ｋ）の位置を基準としてｍ個の制約多項式Ｆ（Ｃ）をｍ個の制約多項式Ｆ（Ｃ）についての各要素が区間数となる区間ヤコビ行列Ｊ（ｃ＊（ｋ），ＣＩ（ｋ））を用いて一次近似した式を０とするｎ次元の領域Ｎ（ｃ＊（ｋ），ＣＩ（ｋ））を含む領域Ｎ’（ｃ＊（ｋ），ＣＩ（ｋ））を区間ガウスの消去法を用いて求め、求まった領域Ｎ’（ｃ＊（ｋ），ＣＩ（ｋ））と領域ＣＩ（ｋ）との共通部分である領域ＣＩ（ｋ＋１）を求める第一領域縮小部と、領域Ｎ’（ｃ＊（ｋ），ＣＩ（ｋ））と領域ＣＩ（ｋ）との包含関係を判定して、領域Ｎ（ｃ＊（ｋ），ＣＩ（ｋ））⊆領域ＣＩ（ｋ）であれば、第一実区間多項式が第二実区間多項式を擬因子として持つと判定する第一包含関係判定部と、を含む。
【発明の効果】
【０００８】
本発明によれば、実係数多項式ｐ（Ｘ）が実係数多項式ｆ（Ｘ）で割り切れるような実係数多項式ｐ（Ｘ），ｆ（Ｘ）がそれぞれ実区間多項式Ｐ（Ｘ），Ｆ（Ｘ）の中に存在するかどうかを判定することができる。
【発明を実施するための最良の形態】
【０００９】
まず、区間多項式の記法、用語等について説明する。ｋを１以上の整数として、ｋ個の変数ｘ１，…，ｘｋをまとめてＸと書く。すなわち、Ｘ＝（ｘ１，…，ｘｋ）である。区間多項式Ｐ（Ｘ）は、数の集合である区間数Ａｉ、予め指定された多項式ｅｉ（Ｘ）（１≦ｉ≦ｎ’）に対して、ａｉ∈Ａｉである多項式Σｉ＝１ｎ’ａｉｅｉ（Ｘ）全体の集合のことであり、区間多項式Ｐ（Ｘ）をΣｉ＝１ｎ’Ａｉｅｉ（Ｘ）と表記する。以下、区間数Ａｉとして実の閉区間［ｌｉａ，ｈｉａ］（ｌはローマ字のエルであり、ｌｉａ，ｈｉａはｌｉａ≦ｈｉａの関係を有する有理数）を用い、ｅｉ（Ｘ）は有理係数多項式とする。各区間［ｌｉａ，ｈｉａ］＝｛ｃｉ∈Ｒ｜ｌｉａ≦ｃｉ≦ｈｉａ｝を区間数と呼ぶ。
【００１０】
同様に、区間多項式Ｆ（Ｘ）を、数の集合Ｂｊ、予め指定された多項式ｄｊ（Ｘ）（１≦ｊ≦ｍ’）に対して、ｂｊ≦Ｂｊである多項式Σｉ＝１ｍ’ｂｊｄｊ（Ｘ）全体の集合として、区間多項式Ｆ（Ｘ）をΣｉ＝１ｍ’Ｂｊｄｊ（Ｘ）と表記する。以下、区間数Ｂｊとして実の閉区間［ｌｊｂ，ｈｊｂ］（ｌｉｂ，ｈｉｂはｌｉｂ≦ｈｉｂの関係を有する有理数）を用い、ｄｉ（Ｘ）は有理係数多項式とする。各区間［ｌｉｂ，ｈｉｂ］＝｛ｃｉ∈Ｒ｜ｌｉｂ≦ｃｉ≦ｈｉｂ｝を区間数と呼ぶ。
【００１１】
ｅｉ（Ｘ），ｄｊ（Ｘ）は有理係数多項式であり、区間数Ａｉ，Ｂｊとして実数Ｒを用いるため、区間多項式Ｐ（Ｘ），Ｆ（Ｘ）は係数が実数である多項式の集合から成ることになる。したがって、区間多項式Ｐ（Ｘ），Ｆ（Ｘ）のことを、実区間多項式とも呼ぶ。また、区間多項式Ｐ（Ｘ），Ｆ（Ｘ）のことを、それぞれ略記してＰ，Ｆと記載することもある。
【００１２】
実区間多項式Ｐ，Ｆに対して、Ｐに属する多項式ｐ及びＦに属する多項式ｆが存在して、多項式ｐが多項式ｆで割り切れるとき、すなわち多項式ｆが多項式ｐの実因子であるとき、Ｐは擬因子Ｆを持つ、ＰはＦを擬因子として持つ、又は、ＦはＰの擬因子であるということにする。
【００１３】
このとき、本発明が解決しようとする課題は、以下の≪問題２≫として記述することができる。
≪問題２≫
与えられた２つの実区間多項式
Ｐ（Ｘ）＝Σｉ＝１ｎ’Ａｉｅｉ（Ｘ），Ｆ（Ｘ）＝Σｊ＝１ｍ’Ｂｊｄｊ（Ｘ）
に対して、Ｆ（Ｘ）がＰ（Ｘ）の擬因子であるか否かを判定せよ（≪問題２≫終り）。
【００１４】
次に、項順序について説明する。ｘ１，…，ｘｋの単項式全体の集合Ｔの全順序で、以下の２つの性質を満たすものを、項順序と呼ぶ。
性質１：ｓ，ｔ，ｕ∈Ｔ、かつ、ｓ＜ｔならば、ｕｓ＜ｕｔ
性質２：任意のｔ∈Ｔに対し、１≦ｔ
代表的な項順序として、例えば以下に述べる辞書式順序、全次数順序がある。以下、αｉ（ｉ＝１，…，ｋ），βｉ（ｉ＝１，…，ｋ）を整数として、α＝（α１，…，αｋ），β＝（β１，…，βｋ）とする。また、Ｘα，Ｘβを、それぞれｘ１α１…ｘｋαｋ，ｘ１β１…ｘｋβｋのこととする。α１，…，αｋ，β１，…，βｋは、それぞれα１，…，αｋ，β１，…，βｋのことである。
【００１５】
辞書式順序とは、Ｘα＜Ｘβとなるのは、（β１−α１，…，βｋ−βｋ）を左から見ていったときに、０ではない最初のβｊ−αｊが正のときと定義する項順序である。
全次数順序とは、Ｘα＜Ｘβとなるのは、以下の（１）、（２）のどちらかが成り立つときと定義する項順序である。
（１）α１＋…＋αｋ＜β１＋…＋βｋである。
（２）α１＋…＋αｋ＝β１＋…＋βｋ、かつ、（β１−α１，…，βｋ−αｋ）を左から見ていったとき、０ではない最初のβｊ−αｊが正である。
【００１６】
ある実区間多項式を他の実区間多項式で割った剰余を求める際に、項順序を定めておく必要がある。この発明では、例えば上記辞書式順序、全次数順序の何れか一方の項順序を用いて、ある実区間多項式を他の実区間多項式で割った剰余を求めるとする。もちろん、上記辞書式順序、全次数順序以外の項順序を用いてもよい。
【００１７】
次に、予め定められた項順序の下で、多項式ｆを多項式ｇで割ったときの剰余を求める方法の例を説明する。ここでは、多項式ｆ，ｇは、実係数多項式とする。ａαを実数として、実係数多項式ｆ＝ΣαａαＸαに対して、ｍａｘａα≠０｛Ｘα｝をＨＴ（ｆ）と書く。ａαとは、ａαのことである。すなわち、ＨＴ（ｆ）とは、ａα≠０であるＸαの中で順序が最高のＸαのことである。また、Ｘα＝ＨＴ（ｆ）のとき、ａαＸαをＨＭ（ｆ）と書く。このとき、ｆをｇで割ったときの剰余は、次の（ステップＡ１）〜（ステップＡ３）により計算される。
【００１８】
（ステップＡ１）ｈ＝ｆとする。
（ステップＡ２）ｈの項の中でＨＴ（ｇ）で割り切れるものがあれば、その中から１つをとりＭとし、その係数をｃＭとして、ステップＡ３に進む。ｈの項の中でＨＴ（ｇ）で割り切れるものがなければ、剰余としてｈを出力する。
（ステップＡ３）以下の式を計算して、その計算結果を改めてｈとしてステップＡ２に進む。
【００１９】
【数１】
2010122905.tif 000003
【００２０】
なお、多項式ｆ，ｇがそれぞれ実区間多項式Ｐ（Ｘ），Ｆ（Ｘ）である場合にも、区間数Ａｉ，Ｂｊを文字係数として扱えば、これと同様にＰ（Ｘ）をＦ（Ｘ）で割ったときの剰余を求めることができる。
【００２１】
上記の準備の下に、上記≪問題２≫をより簡単な問題に変換するために、以下の補題１を用いる。
≪補題１≫
項順序＞を１つ予め定めておく。ｅｉ（Ｘ）（ｉ＝１，…，ｎ’），ｄｊ（Ｘ）（ｊ＝１，…，ｍ’）をそれぞれｋ変数実係数多項式とする。このとき、実係数多項式ｐ（Ｘ）＝Σｉ＝１ｎ’ａｉｅｉ（Ｘ）（ａｉ∈Ｒ）が実係数多項式ｆ（Ｘ）＝Σｊ＝１ｍ’ｂｊｄｊ（Ｘ）（ｂｊ∈Ｒ）で割り切れる必要十分条件は、ａｉ，ｂｉを係数と見てｐ（Ｘ）をｆ（Ｘ）で割った剰余を項ごとにまとめてＰ’（Ｘ）＝ΣαｃαＸαと書いたときに、すべての項が消えることである（≪補題１≫終り）。
【００２２】
この補題１は、区間数Ａｉ，Ｂｊを文字係数として扱えば、実区間多項式Ｐ（Ｘ），Ｆ（Ｘ）についても成立する。
【００２３】
したがって、上記≪問題２≫は、次の≪問題３≫に帰着することができる。
≪問題３≫
予め定められた１つの項順序の下でＰ（Ｘ）＝Σｉ＝１ｎ’Ａｉｅｉ（Ｘ）をＦ（Ｘ）＝Σｉ＝１ｍ’Ｂｊｄｊ（Ｘ）で割ったときの剰余を、Ａｉ，Ｂｊを文字係数と見て同類項でまとめてＰ’（Ｘ）＝ΣαｃαＸαと書いたときに、Ｐ’（Ｘ）に０が入るかどうか、すなわち任意のＸに対してＰ’（Ｘ）＝０となるａｉ∈Ａｉ，ｂｊ∈Ｂｊが存在するかどうかを判定せよ（≪問題３≫終り）。
【００２４】
Ａｉ，Ｂｊを文字係数と見てＰ（Ｘ）をＦ（Ｘ）で割ったときの剰余を同類項でまとめるとは、Ｐ（Ｘ）をＦ（Ｘ）で割ったときの剰余を変数ｘ１，…ｘｋについての多項式と見て単項Ｘαごとに文字係数Ａｉ，Ｂｊをまとめることを意味する。
【００２５】
ｃαは、単項Ｘαの係数であり、区間数Ａｉ，Ｂｊの内のｎ個の区間数Ｃｉ（ｉ＝１，…，ｎ）を変数とする多項式と見ることができる。すなわち、同類項でまとめた結果、剰余の単項Ｘαの数がｍ個である場合には、Ｃ＝（Ｃ１，…，Ｃｎ）として、ｃαを多項式ｆｊ（Ｃ）（ｊ＝１，…，ｍ）と書くことができる。
【００２６】
多項式ｆｊ（Ｃ）（ｊ＝１，…，ｍ）は、必ずしもすべての区間数Ａｉ，Ｂｊを変数とする多項式とはならない。剰余された結果、区間数Ａｉ，Ｂｊの内で消去されて残らない区間数もある。この場合、区間数Ａｉ，Ｂｊの内で消去されずに残った区間数Ｃ１，…，Ｃｎのみを用いて、多項式ｆｊ（Ｃ）（ｊ＝１，…，ｍ）を構成してもよい。したがって、この例では、多項式ｆｊ（Ｃ）（ｊ＝１，…，ｍ）を、区間数Ａｉ，Ｂｊの内の消去されずに残ったｎ個の区間数Ｃ１，…，Ｃｎを変数とする多項式と見ているのである。もちろん、ｎ＝区間数Ａｉ，Ｂｊの総数（ｎ’＋ｍ’）としてもよい。すなわち、多項式ｆｊ（Ｃ）（ｊ＝１，…，ｍ）を、区間数Ａｉ，Ｂｊを変数とする多項式として構成してもよい。
【００２７】
区間数Ｃｉは、区間数Ａｉ，Ｂｊの何れかであり、区間の範囲が定まっている。その区間数Ｃｉの区間の範囲を、［ｌｉ，ｈｉ］とする。区間数Ｃｉに含まれる数をｃｉと表記する。
【００２８】
このとき≪問題３≫は、次の≪問題４≫に帰着することができる。
≪問題４≫
ｆｊ（Ｃ）＝０  （ｊ＝１，…，ｍ）  …（１）
ｌｉ≦ｃｉ≦ｈｉ  （ｉ＝１，…，ｎ）
を満たすｃｉ（ｉ＝１，…，ｎ）が存在するかどうかを判定せよ（≪問題４≫終り）。
【００２９】
このように、本発明が解決しようとする課題である≪問題２≫は、≪問題４≫のようにｎ変数の連立多項式方程式の可解性判定問題とみなすことができる。すなわち、上記連立方程式を満たすｃｉ（ｉ＝１，…，ｎ）が存在すればＦ（Ｘ）はＰ（Ｘ）の擬因子であると判定することができ、上記連立方程式を満たすｃｉ（ｉ＝１，…，ｎ）が存在しなければＦ（Ｘ）はＰ（Ｘ）の擬因子でないと判定することができるのである。
【００３０】
上記多項式ｆｉ（Ｃ）のことを制約多項式ともいう。上記ｍは制約多項式の数であり、上記ｎは制約多項式の変数の数を意味する。Ｆ＝（ｆ１，…，ｆｍ）と書くと、上記（１）式はＦ（Ｃ）＝０と書ける。
【００３１】
除多項式が区間多項式Ｆ（Ｘ）であるとき、制約多項式ｆｉ（Ｃ）は線形関数となる場合と、非線形関数となる場合とがある。制約多項式ｆｉ（Ｃ）が線形関数となる場合には、非特許文献１に記載された方法により、区間多項式Ｆ（Ｘ）が区間多項式Ｐ（Ｘ）の擬因子となるかどうかを判定することができる。制約多項式ｆｉ（Ｃ）が非線形関数となる場合には、制約多項式の数ｍ及び区間数Ｃｉである変数の数ｎに応じて異なる以下に述べる方法により、区間多項式Ｆ（Ｘ）が区間多項式Ｐ（Ｘ）の擬因子となるかどうかを判定する。
【００３２】
［ｍ≧ｎの場合］
まず、制約多項式の数ｍが変数の数ｎ以上である場合の判定方法について説明する。各１≦ｉ≦ｎについてｌｉ≦ｃｉ≦ｈｉが成立するｎ次元直方体の領域をＣＩと書く。すなわち、ｎ個の区間数Ｃｉが作るｎ次元の領域をＣＩと書く。また、ｎ次元の領域をＩｎで表す。ｃ＊＝（ｃ１＊，…，ｃｎ＊）∈Ｒｎを、ＣＩ∈Ｉｎに含まれる任意の一点とする。例えば、ｃ＊を領域ＣＩの中点ｃｃとする。さらに、ｍ個の制約多項式についてのヤコビ行列である区間ヤコビ行列Ｊ（ｃ＊，ＣＩ）∈Ｉｍ×ｎを例えば次のように与える。下記の区間ヤコビ行列Ｊ（ｃ＊，ＣＩ）においては、区間数ＣｉのことをｃｉＩと表記する。
【００３３】
【数２】
2010122905.tif 000004
【００３４】
例えばこのように定義された区間ヤコビ行列Ｊ（ｃ＊，ＣＩ）の各要素は区間数となる。区間の評価には例えば参考文献１に記載されたアフィン演算を用いる。
〔参考文献１〕宮島信也、宮田孝富、柏木雅英、「アフィン演算における最良乗算について」、電子情報通信学会論文誌、Vol.J86-A, No.3、pp.232-240、2003
【００３５】
上記の例では、区間ヤコビ行列を求めるために、点ｃ＊＝（ｃ１＊，…，ｃｎ＊）を用いて、区間ヤコビ行列Ｊ（ｃ＊，ＣＩ）の各要素である多項式∂ｆｊ（ｃ１Ｉ，…，ｃｎＩ）／∂ｘｉの変数の一部に区間数ｃｉＩ（＝Ｃｉ）の代わりに、点ｃ＊＝（ｃ１＊，…，ｃｎ＊）を代入することにより、区間ヤコビ行列Ｊ（ｃ＊，ＣＩ）の各要素である多項式∂ｆｊ（ｃ１Ｉ，…，ｃｎＩ）／∂ｘｉに代入する区間数ｃｉＩ（＝Ｃｉ）の数を減らしている。これにより、区間ヤコビ行列Ｊ（ｃ＊，ＣＩ）の範囲を狭め得ることができ、後述する方法により求める領域の収束を早めることができるためである。しかし、点ｃ＊＝（ｃ１＊，…，ｃｎ＊）を代入しないで、区間ヤコビ行列Ｊ（ｃ＊，ＣＩ）の各要素である多項式∂ｆｊ（ｃ１Ｉ，…，ｃｎＩ）／∂ｘｉの変数のすべてに、区間数ｃｉＩ（＝Ｃｉ）をそのまま代入してもよい。
【００３６】
区間ヤコビ行列Ｊ（ｃ＊，ＣＩ）を用いることにより、点ｃ＊の位置を基準としてｍ個の制約多項式Ｆ（Ｃ）を一次近似した次の式が成立することが知られている（例えば、参考文献２参照。）。Ｄ＝（ｄ１，…，ｄｎ）∈ＣＩとする。
Ｆ（Ｄ）∈Ｆ（ｃ＊）＋Ｊ（ｃ＊，ＣＩ）・（Ｄ−ｃ＊）  …（２）
〔参考文献２〕E.Hansen, G.William Walster, “Global Optimization using Interval Analysis”, Second Edition, Pure and Applied Mathematics
【００３７】
ＤがＦの零点である場合、Ｆ（Ｄ）＝０となり、上記式（２）は次の式（３）のように書き換えられる。
Ｆ（ｃ＊）＋Ｊ（ｃ＊，ＣＩ）・（Ｄ−ｃ＊）＝０  …（３）
ｃ＊∈ＣＩが固定されているとき、上記式（３）の解の集合ｓは、
ｓ＝｛Ｄ｜Ｆ（ｃ＊）＋Ｊ（ｃ＊，ｃ’）・（Ｄ−ｃ＊）＝０，ｃ’∈ＣＩ｝
で与えられる。この解の集合ｓはＦ（Ｄ）＝０となるようなすべてのＤ∈ＣＩを含んでいる。ここで、Ｄを領域ＤＩと見なし、さらに領域ＤＩをｃ＊及びＣＩからの写像として得られる領域であることを明示してＮ（ｃ＊，ＣＩ）と書くことにする。このとき、上記式（３）は、
Ｆ（ｃ＊）＋Ｊ（ｃ＊，ＣＩ）・（Ｎ（ｃ＊，ＣＩ）−ｃ＊）＝０  …（４）
と表される。この式は、例えば次のように変形することにより、ＡＩＸ＝ｂＩという型の区間線形多項式と同型であることがわかる。ＡＩは各要素ａＩｉｊが区間数であるｍ×ｎの区間行列であり次のように変形した場合にはＡＩ＝Ｊ（ｃ＊，ＣＩ）であり、ｂＩは各要素ｂｊが区間数であるｍ次元区間ベクトルであり次のように変形した場合にはｂＩ＝−Ｆ（ｃ＊）＋Ｊ（ｃ＊，ＣＩ）であり、Ｘは各要素が区間数であるｎ次元区間ベクトルでありＸ＝Ｎ（ｃ＊，ＣＩ）である。
Ｆ（ｃ＊）＋Ｊ（ｃ＊，ＣＩ）・（Ｎ（ｃ＊，ＣＩ）−ｃ＊）＝０
Ｊ（ｃ＊，ＣＩ）・（Ｎ（ｃ＊，ＣＩ）−ｃ＊）＝−Ｆ（ｃ＊）
Ｊ（ｃ＊，ＣＩ）・Ｎ（ｃ＊，ＣＩ）＝−Ｆ（ｃ＊）＋Ｊ（ｃ＊，ＣＩ）・ｃ＊
【００３８】
ＡＩＸ＝ｂＩの型の区間線形多項式は、通常の線形方程式よりも難しいことが知られており、解の範囲を正確に効率よく得ることはできないことが知られている。しかし、次に述べるいわゆる区間版ガウスの消去法（以下、区間ガウスの消去法とする）により、緩和した解を得ることができることが知られている（例えば、参考文献３参照。）。
〔参考文献３〕A.Frommer, “A feasibility Result for Interval Gaussian Elimination Relying on Graph Structure”, Symbolic Algebraic Methods and Verification Methods, 2001
【００３９】
≪区間ガウスの消去法≫
入力：区間行列ＡＩ∈Ｉｍ×ｎ，区間ベクトルｂＩ∈Ｉｍ，ただしｍ≧ｎ
出力：ＡＸ＝ｂを満たすＡ∈ＡＩ，ｂ∈ｂＩが存在するＸ＝（ｘ１，…，ｘｍ）全体の集合
（前半のステップ）
ｆｏｒ  ｋ＝１  ｔｏ  ｎ−１
ｆｏｒ  ｉ＝ｋ＋１  ｔｏ  ｍ
ｃＩｉｋ＝ａＩ（ｋ）ｉｋ／ａＩ（ｋ）ｋｋ
ｆｏｒ  ｊ＝ｉ＋１  ｔｏ  ｎ
ａＩ（ｋ＋１）ｉｊ＝ａＩ（ｋ）ｉｊ−ｃＩｉｋａＩ（ｋ）ｋｊ
ｂＩ（ｋ＋１）ｉ＝ｂＩ（ｋ）ｉ−ｃＩｉｋｂＩ（ｋ）ｋ
（後半のステップ）
ｆｏｒ  ｉ＝ｍ  ｄｏｗｎｔｏ  ｎ
ｘｎ＝ｘｎ∩（ｂＩ（ｉ）ｉ／ａＩ（ｉ）ｉｎ）
ｆｏｒ  ｉ＝ｎ−１  ｄｏｗｎｔｏ  １
ｘｉ＝（ｂＩ（ｉ）ｉ−Σｊ＝ｉ＋１ｎａＩ（ｉ）ｉｊｘｊ）／ａＩ（ｉ）ｉｉ（≪区間ガウスの消去法≫終り）
【００４０】
上記区間ガウスの消去法において、ａＩ（１）ｉｊ＝ａＩｉｊである。上記区間ガウスの消去法の前半のステップは、行列ＡＩを上三角行列に変形するステップである。すなわち、ａＩｉｊ（ｉ＞ｊ）＝０とするステップである。後半のステップは、ｍ＞ｎの場合、過剰な制約に対応する共通部分をｘｎとした後に、後退代入によりｘｎ−１，…，ｘ１の解を順次求めるステップである。
【００４１】
上記区間ガウスの消去法を用いることにより、ＣＩが与えられたときに、ｃ＊∈ＣＩを適切に選ぶことで、ＡＩ＝Ｊ（ｃ＊，ＣＩ）、ｂＩ＝−Ｆ（ｃ＊）＋Ｊ（ｃ＊，ＣＩ）として、ＡＩＸ＝ｂＩを満たすＸを含む領域、すなわち領域Ｎ（ｃ＊，ＣＩ）を含む領域Ｎ’（ｃ＊，ＣＩ）を求めることができる。区間ガウスの消去法により求まる解は緩和した解であるため、領域Ｎ（ｃ＊，ＣＩ）自体ではなく、領域Ｎ（ｃ＊，ＣＩ）を含む領域Ｎ’（ｃ＊，ＣＩ）が求まる。
【００４２】
ここで、方程式系の正規化について説明する。ある区間行列ＡＩ∈Ｉｍ×ｎに対して、行列の各要素をその区間数の中点とした行列Ａｃ∈Ｒｍ×ｎを考える。このように、ある区間行列に対して行列の各要素をその区間数の中点とした行列のことを中点行列とする。区間行列ＡＩに対する線形変形行列Ｂ∈Ｒｍ×ｎを、ｍ＝ｎの場合は（Ａｃ）−１を、ｍ＞ｎの場合はＢＡｃの上ｎ行が単位行列、下ｍ−ｎ行が零行列となるようなＢとする。線形変形行列Ｂを左からＡＩに作用させることで、正規化された区間行列ＭＩ∈Ｉｍ×ｎを得る。区間行列ＭＩ＝ＢＡＩの中点行列Ｃｃの対角要素は１となっており、他の要素は０となっている。ＢｂＩ＝ｒＩとすると、ＡＩＸ＝ｂＩという型の方程式系を正規化することにより、ＡＩＸ＝ｂＩは、ＭＩＸ＝ｒＩと書くことができる。
【００４３】
ＡＩＸ＝ｂＩについて上記の区間ガウスの消去法を用いてＸについての緩和した解を求めても良いが、正規化されたＭＩＸ＝ｒＩについて上記の区間ガウスの消去法を用いることにより効率良く演算を行うことができるので、ここでは方程式系を正規化したのちに区間ガウスの消去法を用いることにする。
【００４４】
これをもとに、領域を狭めていくことで解の存在することが保証される範囲を求める反復アルゴリズムを説明する。
【００４５】
ｎ個の区間数Ｃｉが作るｎ次元の領域ＣＩに含まれる領域をＣＩ（ｋ）とする。ｋは０以上の整数である。初期領域ＣＩ（０）は例えばＣＩとする。また、領域ＣＩ（ｋ）に含まれる任意の一点をｃ＊（ｋ）とする。点ｃ＊（ｋ）は例えば領域ＣＩ（ｋ）の中点である。このとき、領域ＣＩ（ｋ）から領域ＣＩ（ｋ）を狭めた領域ＣＩ（ｋ＋１）を以下のように求めることができる。
【００４６】
まず、区間ヤコビ行列Ｊ（ｃ＊（ｋ），ＣＩ（ｋ））を用いることにより点ｃ＊（ｋ）の位置を基準としてｍ個の制約多項式Ｆ（Ｃ）を一次近似した式に対して、Ｊ（ｃ＊（ｋ），ＣＩ（ｋ））に対する線形変形行列Ｂを左側から作用させることにより、次式を得る。
ＢＦ（ｃ＊（ｋ））＋ＢＪ（ｃ＊（ｋ），ＣＩ（ｋ））・（Ｎ（ｃ＊（ｋ），ＣＩ（ｋ））−ｃ＊（ｋ））＝０  
【００４７】
上記式はＡＩＸ＝ｂＩと同型であるため、区間ガウスの消去法を用いて、Ｎ（ｃ＊（ｋ），ＣＩ（ｋ））についての緩和した解であるＮ’（ｃ＊（ｋ），ＣＩ（ｋ））を求めることができる。区間ガウスの消去法により、Ｎ（ｃ＊（ｋ），ＣＩ（ｋ））を含む領域Ｎ’（ｃ＊（ｋ），ＣＩ（ｋ））を求め、領域ＣＩ（ｋ＋１）＝Ｎ’（ｃ＊（ｋ），ＣＩ（ｋ））∩ＣＩ（ｋ）とする。
【００４８】
ＣＩ（ｋ＋１）⊆ＣＩ（ｋ）であるため、ＣＩ（ｋ）は初期領域ＣＩ（０）からの広義の単調減少となる。このようにして、初期領域ＣＩ（０）を狭めた領域ＣＩ（ｋ）を順次求める。このとき、以下の定理１から４が成立することが知られている（例えば参考文献２参照。）。
【００４９】
≪定理１≫
ｋ回目の反復で切り捨てられた領域ＣＩ（ｋ）／ＣＩ（ｋ＋１）の中に制約多項式Ｆ（Ｃ）の零点は存在しない（≪定理１≫終り）。
上記定理１においてＣＩ（ｋ＋１）が空集合である場合の定理が、次の定理２である。この定理２は、領域ＣＩ（ｋ）の中に制約多項式Ｆ（Ｃ）の零点が含まれていないことを保証する基準となる。
【００５０】
≪定理２≫
領域ＣＩ（ｋ＋１）が空集合である場合には、領域ＣＩ（ｋ）の中に制約多項式Ｆ（Ｃ）の零点は存在しない（≪定理２≫終り）。
一方、領域ＣＩ（ｋ）の中に制約多項式Ｆ（Ｃ）零点が含まれていることを保証する基準は、ブラウアーの不動点定理により定理３で与えられる。
【００５１】
≪定理３≫
Ｎ’（ｃ＊（ｋ），ＣＩ（ｋ））⊆ＣＩ（ｋ）であるとき、制約多項式Ｆ（Ｃ）の零点は領域Ｎ’（ｃ＊（ｋ），ＣＩ（ｋ））の中に存在する（≪定理３≫終り）。
次の定理４は、領域ＣＩ（ｋ）の中に制約多項式Ｆ（Ｃ）の零点が唯一含まれていることを保証する基準となる。なお、区間行列ＡＩ∈Ｉｍ×ｎの要素ａＩｉｊ＝［ｌｉｊ，ｈｉｊ］の絶対値｜ａＩｉｊ｜をｍａｘ（｜ｌｉ｜，｜ｈｉ｜）として、区間行列ＡＩについてのノルム‖ＡＩ‖を、‖ＡＩ‖＝ｍａｘｉΣｊ＝１ｎ｜ａＩｉｊ｜と定義し、Ｒ（ｋ）＝Ｉ−ＢＪ（ｃ＊（ｋ），ＣＩ（ｋ））とする。
【００５２】
≪定理４≫
Ｎ’（ｃ＊（ｋ），ＣＩ（ｋ））⊆ＣＩ（ｋ）であり、かつ、‖Ｒ（ｋ）‖＜１である場合には、制約多項式Ｆ（Ｃ）は領域ＣＩ（ｋ＋１）の中に唯一の零点を持つ（≪定理４≫終り）。
領域ＣＩ（ｋ）から領域ＣＩ（ｋ＋１）が求まる度に、上記定理１から４の各条件を満たすかどうかを判断することにより、制約多項式Ｆ（Ｃ）の零点の存否等を判断することができるのである。例えば、定理３の条件Ｎ’（ｃ＊（ｋ），ＣＩ（ｋ））⊆ＣＩ（ｋ）を満たす場合には、制約多項式Ｆ（Ｃ）の零点は領域Ｎ’（ｃ＊（ｋ），ＣＩ（ｋ））の中に存在することから、実区間多項式Ｐ（Ｘ）は実区間多項式Ｆ（Ｘ）を擬因子として持つと判断することができる。また、領域ＣＩ（ｋ＋１）が空集合であり定理２の条件を満たす場合には、領域ＣＩ（ｋ）の中に制約多項式Ｆ（Ｃ）の零点は存在せず、かつ、定理１よりｋ回目の反復で切り捨てられた領域ＣＩ（ｋ）／ＣＩ（ｋ＋１）の中に制約多項式Ｆ（Ｃ）の零点は存在しないため、実区間多項式Ｐ（Ｘ）は実区間多項式Ｆ（Ｘ）を擬因子として持たないと判断することができるのである。
【００５３】
なお、定理４の条件が成立した場合には、領域ＣＩ（ｋ）から縮小された領域ＣＩ（ｋ＋１）を求めることを繰り返すことにより、連立方程式の解が含まれる領域ＣＩ（ｋ）の大きさを線形以上の速さで減少させることができることが知られている（例えば、参考文献２参照。）。したがって、制約多項式Ｆ（Ｃ）の零点の存否、すなわち実区間多項式Ｐ（Ｘ）は実区間多項式Ｆ（Ｘ）を擬因子として持つか否かのみならず、零点が存在する領域、乃至、実係数多項式ｐ（Ｘ）∈Ｐ（Ｘ）の実因子となる実係数多項式ｆ（Ｘ）∈Ｆ（Ｘ）の範囲をより狭い範囲で求めたい場合には、定理４の条件であるＮ’（ｃ＊（ｋ），ＣＩ（ｋ））⊆ＣＩ（ｋ）、かつ、‖Ｒ（ｋ）‖＜１が成立した後に、領域ＣＩ（ｋ）が予め定められた範囲を下回るまで、上記の反復を繰り返せばよい。
【００５４】
また、反復において、領域ＣＩ（ｋ＋１）＝領域ＣＩ（ｋ）が成り立つときは、解が含まれる領域は減少しないため、このままでは解がこの領域ＣＩ（ｋ）に存在するかどうかを判定することができない。このような場合、領域ＣＩ（ｋ）を２つに分割して、分割された各領域を初期領域ＣＩ（０）として、上記の領域を狭めていく反復処理を行えばよい。
【００５５】
［ｍ＜ｎの場合の第１の方法］
変数の数ｎが制約多項式Ｆ（Ｃ）の数ｍより大きい場合の判定方法には２つの方法がある。まず、第１の方法について説明をする。
【００５６】
変数の数ｎが制約多項式Ｆ（Ｃ）の数ｍよりも大きい場合には、解の個数は通常無限個となる。このような場合に特に都合のよい解を１つ得るための手段として。ｌ２−ノルムにおける誤差を最小にする解を求めることを考える。そのような解を得るための手段として、いわゆるＪｏｈｎ条件がある（例えば、参考文献２参照。）。これは、連立方程式Ｆ（Ｃ）＝０及び予め適宜定められた目的関数ｇ（Ｃ）が与えられたときに、目的関数ｇ（Ｃ）が極小となるための条件を表すものであり、
ｕ＋ΣｉＥｉｖｉ＝０
ｕ∇ｇ（Ｃ）＋Σｉｖｉ∇ｆｉ（Ｃ）＝０
Ｆ（Ｃ）＝０
で与えられる。ただし、Ｅｉ∈［１，１＋ε］（εは非常に小さい正の数），ｕ≧０である。上段の式は変数ｕ，ｖ１，…，ｖｍの正規化条件であり、中段の式はｇ（Ｃ）が極値である条件でありｎ個の方程式から成り、下段の式はもともとのｍ個の制約多項式Ｆ（Ｃ）＝０に対応している。この方程式系の変数ｕ，ｖ１，…，ｖｍ，Ｃ１，…Ｃｎの個数はｍ＋ｎ＋１であり、制約多項式の総数もｍ＋ｎ＋１であり、両者は一致する。したがって、解の個数は有限個となる。目的関数ｇ（Ｃ）は、例えば、
ｇ（Ｃ）＝ｍｉｎΣｉ＝１ｎ（ｃｉ−（ｌｉ＋ｈｉ）／２）２
とする。
【００５７】
なお、目的関数ｇ（Ｃ）を最小にするＣを求めるためには、上記ｍ＋ｎ＋１個の式から成る連立方程式の解をすべて求め、各解について目的関数ｇ（Ｃ）の値を計算し、目的関数ｇ（Ｃ）の値を最も小さくする解を選べばよい。
【００５８】
上記ｍ＋ｎ＋１個の式から成る連立方程式は、ＡＩＸ＝ｂＩという型の区間線形多項式と同型であるため、上記説明した区間ガウスの消去法及び上記定理１から４を適用することにより、解の存否等を判断することが可能である。
【００５９】
［ｍ＜ｎの場合の第２の方法］
変数の数ｎが制約多項式Ｆ（Ｃ）の数ｍより大きい場合の第２の判定方法について説明をする。
変数の数ｎが制約多項式Ｆ（Ｃ）の数ｍより大きい場合には、解の空間は１次元以上となる。したがって、解の個数は無限個となり、ｍ≧ｎの場合のアルゴリズムをそのまま適用することはできない。そこで、ｎ（＞ｍ）個の変数ｖａｒ（Ｃ）＝｛Ｃ１，…，Ｃｎ｝のうちｍ個の部分集合を基底変数ｖａｒ（Ｃｂａｓｅ）、残りのｎ−ｍ個の変数を非基底変数ｖａｒ（Ｃｎｏｎｂａｓｅ）と見なす。以下、参考文献３で提案されている手法を用いる。
〔参考文献３〕神沢雄智，柏木雅英，大石進一，「パラメータ依存非線形方程式の解を含む区間の反復改良アルゴリズム」，電子情報通信学会論文誌，Ｖｏｌ．Ｊ８３−Ａ，Ｎｏ．５，ｐｐ．５１１−５１６，２０００
【００６０】
Ｉを単位行列、上記ｎ個の区間数Ｃ＝｛Ｃ１，…，Ｃｎ｝が作るｎ次元の領域ＣＩに含まれるｎ次元の領域をＣＩ＄＝ＣＩ＄ｂａｓｅ×ＣＩ＄ｎｏｎｂａｓｅとし、領域ＣＩ＄ｂａｓｅを上記ｎ個の変数から選択されたｍ個の基底変数ｖａｒ（Ｃｂａｓｅ）が領域ＣＩ＄において作る領域をとし、領域ＣＩ＄ｎｏｎｂａｓｅを上記ｎ個の変数の上記基底変数ｖａｒ（Ｃｂａｓｅ）以外のｎ−ｍ個の非基底変数ｖａｒ（Ｃｎｏｎｂａｓｅ）が領域ＣＩ＄において作る領域をＣＩ＄ｎｏｎｂａｓｅとし、領域ＣＩ＄ｂａｓｅに含まれる任意の一点をｃ＊＄ｂａｓｅとし、領域ＣＩ＄ｂａｓｅの中点をｃｃ＄ｂａｓｅとし、εを小さい正の数とし、領域ＣＩ＄ｂａｓｅの各成分の半径を要素とするベクトルをｒａｄ（ＣＩ＄ｂａｓｅ）とし、ｃｃ＄ｂａｓｅを中心として各成分の半径がε・ｒａｄ（ＣＩ＄ｂａｓｅ）である領域をεＣＩ＄ｂａｓｅとし、・を各要素が区間数である行列とし、Ｃ♯＄を必要に応じて選択される領域ＣＩ＄内の任意の一点とし、・ｃを・の要素である各区間数の中点からなる行列とし、区間ヤコビ行列Ｊ（ｃ＃＄，ＣＩ＄）∈Ｉｍ×ｎのｉ（ｉ＝１，…，ｎ）番目の列が変数Ｃｉに対応しているとして、Ｊ（ｃ＃＄，ＣＩ＄）の中から基底変数ｖａｒ（Ｃｂａｓｅ）に対応する列を取ってきた区間行列Ｊｂａｓｅ（ｃ＃＄，ＣＩ＄）∈Ｉｍ×ｍについての線形変形行列Ｂ∈Ｒｍ×ｍをＢ＝（Ｊｂａｓｅ（ｃ＃＄，ＣＩ＄）ｃ）−１として、下記式の関係を有する領域Ｎ（ｃ♯＄，ＣＩ＄）を求める。ここで、例えば、領域ＣＩ＄＝ＣＩとし、点ｃ＊＄ｂａｓｅをｃｃ＄ｂａｓｅとし、点ｃ♯＄を領域ＣＩ＄の中点ｃｃ＄とする。
Ｍ＝Ｉ−ＢＪ（ｃ＃＄，ＣＩ＄）  …（４）
Ｎ（ｃ♯＄，ＣＩ＄）＝ｃ＊＄ｂａｓｅ−ＢＦ（εＣＩ＄ｂａｓｅ，ＣＩ＄ｎｏｎｂａｓｅ）＋Ｍ（ＣＩ＄ｂａｓｅ−ｃ＊＄ｂａｓｅ）  …（５）
【００６１】
求まった領域Ｎ（ｃ♯＄，ＣＩ＄）と領域ＣＩ＄ｂａｓｅとの包含関係を判定して、領域Ｎ（ｃ♯＄，ＣＩ＄）⊂領域ＣＩ＄ｂａｓｅであれば、実区間多項式Ｐ（Ｘ）は実区間多項式Ｆ（Ｘ）を擬因子として持つことが上記参考文献３等により知られている。したがって、求まった領域Ｎ（ｃ♯＄，ＣＩ＄）と領域ＣＩ＄ｂａｓｅとの包含関係を判定することにより、実区間多項式Ｆ（Ｘ）が実区間多項式Ｐ（Ｘ）の擬因子であるかどうかを判定することができる。
【００６２】
なお、実区間多項式Ｆ（Ｘ）が実区間多項式Ｐ（Ｘ）の擬因子であるかどうかのみならず、実係数多項式ｐ（Ｘ）∈Ｐ（Ｘ）の実因子となる実係数多項式ｆ（Ｘ）∈Ｆ（Ｘ）の範囲をより狭い範囲で求めたい場合には、「任意の点ｃ＄ｎｏｎｂａｓｅ∈ＣＩ＄ｎｏｎｂａｓｅに対して、Ｆ（ｃ＄ｂａｓｅ，ｃ＄ｎｏｎｂａｓｅ）＝０となる点ｃ＄ｂａｓｅ∈ＣＩ＄ｂａｓｅが唯一存在するかどうか」を判定し、唯一存在すると判定された場合には、後述する方法により領域（ＣＩ＄ｂａｓｅ，ＣＩ＄ｎｏｎｂａｓｅ）を絞り込んでもよい。
【００６３】
‖Ｍ‖＜１、かつ、Ｎ（ｃ♯＄，ＣＩ＄）⊂領域ＣＩ＄ｂａｓｅであれば、任意の点ｃ＄ｎｏｎｂａｓｅ∈ＣＩ＄ｎｏｎｂａｓｅに対して、Ｆ（ｃ＄ｂａｓｅ，Ｃ＄ｎｏｎｂａｓｅ）＝０となる点ｃ＄ｂａｓｅ∈ＣＩ＄ｂａｓｅが唯一存在することが上記参考文献３等により知られているため、上記の判定は、‖Ｍ‖＜１、かつ、Ｎ（ｃ♯＄，ＣＩ＄）⊂領域ＣＩ＄ｂａｓｅであるかを判定することにより行う。
【００６４】
[装置構成]
擬因子判定装置、方法の一実施形態を、図１から図８を参照して説明をする。
入力部１１（図１）から入力された、実区間多項式Ｐ（Ｘ）を特定するための情報、及び、実区間多項式Ｆ（Ｘ）を特定するための情報は、記憶部２０に格納される。
【００６５】
剰余演算部３０は、記憶部２０から、実区間多項式Ｐ（Ｘ）を特定するための情報、及び、実区間多項式Ｆ（Ｘ）を特定するための情報を読み込んで、実区間多項式Ｐ（Ｘ）を実区間多項式Ｆ（Ｘ）で割った剰余を求め、剰余を特定するための情報を制約多項式生成部４０に出力する（ステップＳ１）。剰余演算部３０は、例えば上記ステップＡ１から上記ステップＡ３の処理を行うことにより、剰余を求める。
【００６６】
制約多項式生成部４０は、上記剰余の同類項をまとめた場合に上記剰余はｍ（ｍは１以上の整数）個の項から構成されるとして、上記ｍ個の項のそれぞれの係数から成る、実区間多項式Ｐ（Ｘ）及び実区間多項式Ｐ（Ｘ）の区間数の内のｎ（ｎは１以上の整数）個の区間数Ｃｉ（ｉ＝１，…，ｎ、ｌｉとｈｉをｌｉ≦ｈｉの関係を満たす有理数としてＣｉ＝［ｌｉ，ｈｉ］）を変数とするｍ個の制約多項式Ｆ（Ｃ）（Ｆ（Ｃ）＝（ｆ１（Ｃ），…，ｆｍ（Ｃ））、Ｃ＝（Ｃｉ，…，Ｃｎ））を生成する（ステップＳ２）。制約多項式Ｆ（Ｃ）の数ｍ及び変数の数ｎは、大小関係判定部５０に送られる。制約多項式Ｆ（Ｃ）を特定するための情報、及び、ｎ個の区間数Ｃｉの取り得る範囲についての情報ｌｉ，ｈｉは、判定部８５、線形判定部８０、領域縮小部６０等に送られる。
【００６７】
判定部８５は、制約多項式Ｆ（Ｃ）の中に常に非零となる制約多項式があるかどうかを判定して、常に非零となる制約多項式がある場合には、実区間多項式Ｐ（Ｘ）は実区間多項式Ｆ（Ｘ）を擬因子として持たないと判定する（ステップＳ２１）。常に非零となるかどうかは、例えば制約多項式Ｆ（Ｃ）の中に、実区間多項式Ｐ（Ｘ）及び実区間多項式Ｆ（Ｘ）の区間数の何れも含まない制約多項式があるかどうかを判定すればよい。制約多項式Ｆ（Ｃ）の中に常に非零となる制約多項式がある場合には、実区間多項式Ｐ（Ｘ）を実区間多項式Ｆ（Ｘ）で割った剰余が任意のＸに対して０になるとは限らない。したがって、実区間多項式Ｐ（Ｘ）は実区間多項式Ｆ（Ｘ）を擬因子として持たないと判定することができるのである。
【００６８】
制約多項式Ｆ（Ｃ）の中に常に非零となる制約多項式がない場合には、線形判定部８０は、制約多項式Ｆ（Ｃ）がｎ個の変数が線形であるかどうかを判定する（ステップＳ３）。線形である場合には、非特許文献１に記載された方法により判定を行う。
【００６９】
線形でない場合には、大小関係判定部５０は、制約多項式Ｆ（Ｃ）の数ｍと変数の数ｎとの大小関係を判定する（ステップＳ４）。ｍ≧ｎであれば、その旨の情報が領域縮小部６０に送られる。ｍ＜ｎであれば、その旨の情報が制約多項式増加部１２０に送られる。ｍ＜ｎの場合に、その旨の情報が領域縮小部１３０に送られてもよい。
【００７０】
ｍ＜ｎである旨の情報を受け取ると、領域縮小部６０の制御部６１は、領域の集合Ｌ＝｛Ｃｌ｝として記憶部６２にＬを格納する（ステップＢ１、図６）。
【００７１】
領域縮小部６０の制御部６１（図２）は、領域の集合Ｌのすべての要素について以下に述べる領域の縮小化の処理を行ったかどうかを判断する（ステップＢ２）。領域の集合Ｌのすべての要素について処理を行った場合には、擬因子判定処理を終える。
【００７２】
領域の集合Ｌのすべての要素について同処理を行っていない場合には、制御部６１は、記憶部６２に格納されたｋをｋ＝０とする（ステップＢ３）。
【００７３】
制御部６１は、領域の集合Ｌから処理を行っていない要素をひとつ取り出して、領域ＣＩ（ｋ）とする（ステップＢ４）。領域ＣＩ（ｋ）についての情報は、点決定部６４、区間ヤコビ行列計算部６５及び区間ガウス消去法演算部６３に送られる。
【００７４】
領域縮小部６０の区間ガウス消去法演算部６３は、ｎ個の区間数が作るｎ次元の領域ＣＩに含まれるｎ次元の領域ＣＩ（ｋ）に含まれる任意の一点ｃ＊（ｋ）の位置を基準として上記ｍ個の制約多項式Ｆ（Ｃ）を上記ｍ個の制約多項式Ｆ（Ｃ）についての各要素が区間数となる区間ヤコビ行列Ｊ（ｃ＊（ｋ），ＣＩ（ｋ））を用いて一次近似した式
Ｆ（ｃ＊（ｋ））＋Ｊ（ｃ＊（ｋ），ＣＩ（ｋ））・（Ｎ（ｃ＊（ｋ），ＣＩ（ｋ））−ｃ＊（ｋ））
を０とするｎ次元の領域Ｎ（ｃ＊（ｋ），ｑＩ（ｋ））を含む領域Ｎ’（ｃ＊（ｋ），ｑＩ（ｋ））を区間ガウスの消去法を用いて求め、求まった領域Ｎ’（ｃ＊（ｋ），ｑＩ（ｋ））と上記領域ＣＩ（ｋ）との共通部分である領域ＣＩ（ｋ＋１）を求める。領域Ｎ’（ｃ＊（ｋ），ｑＩ（ｋ））についての情報は、包含関係判定部７０（図１）に送られる。また、領域ＣＩ（ｋ＋１）についての情報は、空集合判定部９０（図１）及び同一領域判定部１００に送られる。
【００７５】
点決定部６４が、領域ＣＩ（ｋ）についての情報を基にして点ｃ＊（ｋ）∈ＣＩ（ｋ）を定めて、区間ヤコビ行列計算部６５に送る。例えば点ｃ＊（ｋ）は領域ＣＩ（ｋ）の中点とする。区間ヤコビ行列計算部６５が、点ｃ＊（ｋ）及び領域ＣＩ（ｋ）についての情報を基にして区間ヤコビ行列Ｊ（ｃ＊（ｋ），ＣＩ（ｋ））を計算して、区間ガウス消去法演算部６３に送る。
【００７６】
なお、区間ガウス消去法演算部６３は、式Ｆ（ｃ＊（ｋ））＋Ｊ（ｃ＊（ｋ），ＣＩ（ｋ））・（Ｎ（ｃ＊（ｋ），ＣＩ（ｋ））−ｃ＊（ｋ））＝０ではなく、この式を正規化した式
ＢＦ（ｃ＊（ｋ））＋ＢＪ（ｃ＊（ｋ），ＣＩ（ｋ））・（Ｎ（ｃ＊（ｋ），ＣＩ（ｋ））−ｃ＊（ｋ））＝０  
を満たす領域Ｎ（ｃ＊（ｋ），ＣＩ（ｋ））を含む領域Ｎ’（ｃ＊（ｋ），ＣＩ（ｋ））を求めてもよい。線形変形行列の計算及び上記式の正規化は正規化部６３１により行われる。
【００７７】
空集合判定部９０（図１）は、領域ＣＩ（ｋ＋１）が空集合φであるかどうかを判定する（ステップＢ６）。領域ＣＩ（ｋ＋１）が空集合φである場合には、定理２より、領域ＣＩ（ｋ）に零点はないと判断することができる。領域ＣＩ（ｋ）が領域ＣＩである場合には、実区間多項式Ｐ（Ｘ）は実区間多項式Ｆ（Ｘ）を擬因子として持たないと判断できる。この場合、その後ステップＢ２に進む。領域ＣＩ（ｋ＋１）が空集合φでない場合には、ステップＢ７に進む。
【００７８】
同一領域判定部１００（図１）は、領域ＣＩ（ｋ＋１）＝領域ＣＩ（ｋ）であるかどうかを判定する（ステップＢ７）。領域ＣＩ（ｋ＋１）＝領域ＣＩ（ｋ）であると判定された場合には、制御部６１は領域ＣＩ（ｋ）を任意に分割した各領域を領域の集合Ｌに加える。そして、その後ステップＢ２に進む。これにより、領域縮小部６０は、領域ＣＩ（ｋ＋１）＝領域ＣＩ（ｋ）である場合には、領域ＣＩ（ｋ）を分割した領域を新たなｎ次元の領域ＣＩ（ｋ）として、新たな領域ＣＩ（ｋ＋１）を求めることになる。
【００７９】
包含関係判定部７０（図１）は、領域Ｎ’（ｃ＊（ｋ），ｑＩ（ｋ））⊆領域ＣＩ（ｋ）であるかどうかを判定する（ステップＢ９）。領域Ｎ’（ｃ＊（ｋ），ｑＩ（ｋ））⊆領域ＣＩ（ｋ）であれば、定理３より、制約多項式Ｆ（Ｃ）の零点は領域Ｎ’（ｃ＊（ｋ），ｑＩ（ｋ））に含まれると判断することができる。すなわち、実区間多項式Ｐ（Ｘ）は実区間多項式Ｆ（Ｘ）を擬因子として持つと判断することができる。この場合、必要に応じて、ステップＢ１１以降の処理を行う。領域Ｎ’（ｃ＊（ｋ），ｑＩ（ｋ））⊆領域ＣＩ（ｋ）でないと判定された場合には、制御部６１はｋを１だけインクリメントして（ステップ１０）、そのステップＢ４に進む。
【００８０】
Ｒ判定部６６（図２）は、‖ＲＩ（ｋ）‖を計算して、‖ＲＩ（ｋ）‖＜１であるかどうかを判定する（ステップＢ１１）。‖ＲＩ（ｋ）‖＜１であれば、定理４より、制約多項式Ｆ（Ｃ）は領域ＣＩ（ｋ＋１）の中に唯一の零点を持ち、零点が含まれる領域ＣＩ（ｋ）の大きさを線形以上の速さで減少させることができる。この場合、ステップＢ１２に進む。‖ＲＩ（ｋ）‖＜１でない場合には、ステップＢ１０に進む。
【００８１】
領域限定部１１０（図１）は、区間ガウスの消去法を用いて、領域ＣＩ（ｋ＋１）を新たな領域ＣＩ（ｋ）として、上記と同様に領域ＣＩ（ｋ）から領域ＣＩ（ｋ＋１）を求める処理を、求まった領域ＣＩ（ｋ＋１）が予め定められた領域よりも小さくなるまで繰り返えす（ステップＢ１２）。予め定められた領域よりも領域ＣＩ（ｋ＋１）が小さくなった場合には、領域限定部１１０は、その領域を出力する。
【００８２】
大小関係判定部５０においてｍ＜ｎと判定された場合には、制約多項式増加部１２０（図１）は、ｎ個の区間数が作るｎ次元の領域のある点Ｃのその領域の中点からの距離を目的関数ｇ（Ｃ）として、その目的関数ｇ（Ｃ）を極小にするための、上記ｎ個の区間数及びそのｎ個の区間数以外のｍ＋１個の区間数を変数とするｎ＋１個の制約多項式を生成する（ステップＳ５、図１）。生成された制約多項式についての情報は、領域縮小部６０に送られる。
【００８３】
その後、領域縮小部６０、包含関係判定部７０、空集合判定部９０、同一領域判定部１００及び領域限定部１１０は、ｎ個の変数についてのｍ個の制約多項式Ｆ（Ｃ）に代えて、ｎ個の変数に上記のｍ＋１個の変数を加えたｍ＋ｎ＋１個の変数についてｍ＋ｎ＋１個の制約多項式を新たな制約多項式Ｆ（Ｃ）として、ステップＢ１からステップＢ１２の処理をｍ≧ｎの場合と同様に行う。
【００８４】
大小関係判定部５０においてｍ＜ｎと判定された場合には、制約多項式増加部１２０、領域縮小部６０、包含関係判定部７０、空集合判定部９０、同一領域判定部１００及び領域限定部１１０によるステップＳ５，ステップＢ１からステップＢ１２の処理に代えて、領域縮小部１３０（図１）、包含関係判定部１４０及び領域限定部１５０が、図７，図８に例示したステップＣ１からＣ９，Ｄ１からＤ１１までの処理を行ってもよい。
【００８５】
ｍ＜ｎである旨の情報を受け取ると、領域縮小部１３０の制御部１３１は、領域の集合Ｌ＝｛Ｃｌ｝として記憶部１３２にＬを格納する（ステップＣ１、図７）。
【００８６】
制御部１３１（図３）は、領域の集合Ｌのすべての要素について以下に述べる領域の縮小化の処理を行ったかどうかを判断する（ステップＣ２）。領域の集合Ｌのすべての要素について処理を行った場合には、擬因子判定処理を終える。
【００８７】
領域の集合Ｌのすべての要素について同処理を行っていない場合には、制御部１３１は、処理を行っていない領域の集合Ｌの要素をひとつ取り出してＣＩ＄とする（ステップＣ３）。
【００８８】
制御部１３３は、ｎ個の変数ｖａｒ（Ｃ）＝｛Ｃ１，…，Ｃｎ｝のうちｍ個を基底変数ｖａｒ（Ｃｂａｓｅ）として選択する（ステップＣ４）。
【００８９】
領域計算部１３４は、上記式（４）及び式（５）で定義されるＭ及びＮ（ｃ♯＄，ＣＩ＄）を計算する（ステップＣ５）。
【００９０】
包含関係判定部１４０（図１）は、領域Ｎ（ｃ♯＄，ＣＩ＄）と領域ＣＩ＄ｂａｓｅとの包含関係を判定する（ステップＣ６）。Ｎ（ｃ♯＄，ＣＩ＄）⊂ＣＩ＄ｂａｓｅであれば、実区間多項式Ｐ（Ｘ）は実区間多項式Ｆ（Ｘ）を擬因子として持つと判定することができる。Ｎ（ｃ♯＄，ＣＩ＄）⊂ＣＩ＄ｂａｓｅでなければ、制御部１３１は領域ＣＩ＄ｂａｓｅを任意に分割した各領域をＬに加える（ステップＣ７）。その後、ステップＣ２に進む。
【００９１】
Ｎ（ｃ♯＄，ＣＩ＄）⊂ＣＩ＄ｂａｓｅである場合には、必要に応じて、以下のステップＣ８，Ｃ９，Ｄ１からＤ１１の処理を行って、解が存在する領域の限定、絞り込みを行ってもよい。
制御部１３１は、‖Ｍ‖＜１であるかを判定する（ステップＣ８）。
【００９２】
‖Ｍ‖＜１である場合には、任意の点ｃ＄ｎｏｎｂａｓｅ∈ＣＩ＄ｎｏｎｂａｓｅに対して、Ｆ（ｃ＄ｂａｓｅ，ｃ＄ｎｏｎｂａｓｅ）＝０となる点ｃ＄ｂａｓｅ∈ＣＩ＄ｂａｓｅが唯一存在すると判断することができる。この場合、制御部１３１は、領域の集合Ｓに、領域（ＣＩ＄ｂａｓｅ，ＣＩ＄ｎｏｎｂａｓｅ）を入れる（ステップＣ９）。その後、図８のステップＤ１に進む。‖Ｍ‖＜１でない場合には、制御部１３１は領域ＣＩ＄ｂａｓｅを任意に分割した各領域をＬに加える（ステップＣ７）。その後、ステップＣ２に進む。
【００９３】
領域限定部１５０（図１）の制御部１５１（図４）は、領域の集合Ｓのすべての要素についてステップＤ２以降の処理を行ったかどうかを判定する。領域の集合Ｓのすべての要素について処理を行った場合には、ステップＣ２に進むか、擬因子判定処理を終える。
【００９４】
領域の集合Ｓのすべての要素について同処理を行っていない場合には、制御部６１は、領域の集合Ｓから処理を行っていない要素をひとつ取り出して、領域ＣＩ＄とする（ステップＤ２）。
【００９５】
決定部１５３は、領域ＣＩ＄は、‖κ＋｜Ｍ｜‖＜１を満たす、有理数を要素に持つ行列κを決定する（ステップＤ３）。ただし、｜Ｍ｜は区間行列Ｍの各要素である区間の絶対値を要素に持つ非区間非負行列である。
【００９６】
また、決定部１５３は、ｍ次元有理数ベクトルｐ，ｑをｐ＋ｑ≦κ・ｒａｄ（ＣＩ＄ｂａｓｅ）を満たすように決定する（ステップＤ５）。
区間行列計算部１５４は、Ｒ＝Ｂｆ（εＣＩ＄ｂａｓｅ，ＣＩ＄ｎｏｎｂａｓｅ）を計算する。
【００９７】
判定部１５５は、ｒａｄ（Ｒ）≧ｐであるかを判定する（ステップＤ６）。ｒａｄ（Ｒ）≧ｐであれば、制御部１５１は、領域ＣＩ＄ｎｏｎｂａｓｅを任意に分割した各領域を、領域の集合Ｓに加える（ステップＤ７）。ｒａｄ（Ｒ）≧ｐでない場合には、ステップＤ８に進む。
【００９８】
限定部１５６は、領域ＣＩ＄＊ｂａｓｅ＝ｃｃｂａｓｅ−Ｒ＋Ｍ（ＣＩ＄ｂａｓｅ−ｃｃｂａｓｅ）を丸め誤差なしで計算する（ステップＤ８）。
【００９９】
判定部１５７は、δを予め定められた値として、‖ｒａｄ（ＣＩ＄＊ｂａｓｅ）‖＜δであるかどうかを判定する（ステップＤ９）。‖ｒａｄ（ＣＩ＄＊ｂａｓｅ）‖＜δであれば、領域ＣＩ＄＊ｂａｓｅを解が存在する領域として出力する（ステップＤ１０）。その後、ステップＤ１に進む。
【０１００】
‖ｒａｄ（ＣＩ＄＊ｂａｓｅ）‖＜δでない場合には、制御部１５１は、領域ＣＩ＄＊ｂａｓｅを誤差ｑ以内で外側に丸めて、領域ＣＩ＄との共通部分を取り、その共通部分である領域を領域の集合Ｓに加える（ステップＤ１１）。その後、ステップＤ１に進む。
【０１０１】
［実施例］
以下の例は一変数の区間多項式によるものであるが、多変数区間多項式についても項順序＞を定めることにおり、上述の方法で解を求めることができる。
実区間多項式がＰ（Ｘ）＝ｘ３＋［ｌ０，ｈ０］ｘ２＋１／２，Ｆ（Ｘ）＝ｘ２−［ｌ１，ｈ１］ｘ−［ｌ２，ｈ２］，区間の範囲が、［ｌ０，ｈ０］＝［ｌ１，ｈ１］＝［ｌ２，ｈ２］＝［−１，１］で与えられるとする。
このとき、Ｐ（Ｘ）をＦ（Ｘ）で割った剰余は、（［ｌ１，ｈ１］２＋［ｌ０，ｈ０］［ｌ１，ｈ１］＋［ｌ２，ｈ２］）・ｘ＋［ｌ１，ｈ１］［ｌ２，ｈ２］＋［ｌ０，ｈ０］［ｌ２，ｈ２］＋１／２となり、制約多項式Ｆ（Ｃ）＝０は以下のようになる。
Ｃ１２＋Ｃ０Ｃ１＋Ｃ２＝０
Ｃ１Ｃ２＋Ｃ０Ｃ２＋１／２＝０
−１≦Ｃ０，Ｃ１，Ｃ２≦１
この連立区間多項式における解は（−０．２９３，１，−０．７０７）から（１，０．２９７，−０．３８５）へ通り抜ける曲線全体となり、無数に存在する。
【０１０２】
これに対して、上記［ｍ＜ｎの場合の第２の方法］を適用した結果、非基底変数をＣ０として任意のＣ０∈［０．８７５，１］に対し、基底変数（Ｃ１，Ｃ２）の解が（［０．２５，０．５］，［−０．５，０］）内に唯一存在することがわかる。さらに、（ｃ１，ｃ２）の範囲を狭めることにより、（ｃ１，ｃ２）の解は（［０．２６７，０．３６４］，［−０．４３０，−０．３５４］）内に存在することがわかる。
【０１０３】
つづいて、上記［ｍ＜ｎの場合の第２の方法］を適用して、区間の中心［０，０，０］からのユークリッド距離（ｌ２−ノルム）が最小となる解を求めることを考える。目的関数をＣ０２＋Ｃ１２＋Ｃ２２とすると、この問題のＪｏｈｎ条件は、
ｕ＋Ｅ１ｖ１＋Ｅ２ｖ２＝０
２ｕＣ０＋Ｃ１ｖ１＋Ｃ２ｖ２＝０
２ｕＣ１＋（Ｃ０＋２Ｃ１）ｖ１＋Ｃ２ｖ２＝０
２ｕＣ２＋ｖ１＋（Ｃ０＋Ｃ１）ｖ２＝０
Ｃ１２＋Ｃ０Ｃ１＋Ｃ２＝０
Ｃ１Ｃ２＋Ｃ０Ｃ２＋１／２＝０
Ｅ１，Ｅ２＝［１，１＋ε］，ｕ≧０
で与えられる。これの変数の個数と制約の個数は等しいため、［ｍ≧ｎの場合］の方法を適用することができる。これにより、最適解（Ｃ０，Ｃ１，Ｃ２）＝（０．４２，０．５４，−０．５２）を含む領域（［０．４１６，０．４２４］，［０．５３７，０．５４７］，［−０．５２６，−５１５］）が得られる。
【０１０４】
［変形例等］
上記アルゴリズムは、分割された区間の境界上に解が存在する場は解の存在条件を満たさないため、有限ステップでは終了しない可能性がある。このため、以下の参考文献４に倣い、区間ＣＩについて、中心のニュートン写像による修正量（［ｍ≧ｎの場合］のアルゴリズムにおいては‖ＢＦ（εＣＩ（ｋ））‖、［ｍ＜ｎの場合の第２の方法］のアルゴリズムにおいては‖ＢＦ（εＣＩ＄ｂａｓｅ，ＣＩ＄ｎｏｎｂａｓｅ）‖）の修正量のρ倍（ρ＞１）と、元の区間の半径とを比べて、大きい方を区間の半径としてもよい。
〔参考文献４〕柏木雅英，大石進一，「区間解析と有理数演算による非線形方程式の近似解の精度保証」，電子情報通信学会論文誌，Ｖｏｌ．Ｊ７７−Ａ，Ｎｏ．１０，ｐｐ．１３７２−１３８２，１９９４
以上の説明では、説明を簡単にするために区間数の端点及び多項式の係数は有理数としたが、アルゴリズムの実行のためには四則演算及び等号判定が実行できれば十分なので、例えば実代数的数（整数係数一次代数方程式の根となる実数）としてもそのまま通用する。
【０１０５】
各部が処理を行うために必要な情報は、その情報が記憶された記憶部から読み込み、処理を行った後の計算結果、及び、必要に応じて計算途中の値が上記記憶部と同一又は異なる記憶部に格納される。記憶部を介さずに、各部間で直接必要な情報のやり取りが行われてもよい。
【０１０６】
擬因子判定装置をコンピュータによって実現する場合、擬因子判定装置が有する各部の処理内容はプログラムによって記述される。そして、このプログラムを図９に例示するコンピュータで実行することにより、各部の処理機能がコンピュータ上で実現される。
【０１０７】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよいが、具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（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）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０１１０】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、各装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【０１１１】
また、上述の各種の処理は、記載にしたがって時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【産業上の利用可能性】
【０１１２】
本発明は、係数に誤差のある実多項式、すなわち区間多項式についての演算を行うディジタル信号処理、システム制御等の分野において用いられる。
【図面の簡単な説明】
【０１１３】
【図１】擬因子判定装置の例を示す機能ブロック図。
【図２】領域縮小部６０の例を示す機能ブロック図。
【図３】領域縮小部１３０の例を示す機能ブロック図。
【図４】領域限定部１５０の例を示す機能ブロック図。
【図５】擬因子判定方法の例を示す第一のフローチャート。
【図６】擬因子判定方法の例を示す第二のフローチャート。
【図７】擬因子判定方法の例を示す第三のフローチャート。
【図８】擬因子判定方法の例を示す第四のフローチャート。
【図９】コンピュータを擬因子判定装置として機能させる場合のコンピュータの機能ブロク図。
【符号の説明】
【０１１４】
３０   剰余演算部
４０   制約多項式生成部
５０   大小関係判定部
６０   領域縮小部（第一領域縮小部）
７０   包含関係判定部（第一包含関係判定部）
８０   線形判定部
８５   判定部
１００ 同一領域判定部
１２０ 制約多項式増加部
１３０ 領域縮小部（第二領域縮小部）
１４０ 包含関係判定部（第二領域縮小部）
【図１】
2010122905.tif 000005
【図２】
2010122905.tif 000006
【図３】
2010122905.tif 000007
【図４】
2010122905.tif 000008
【図５】
2010122905.tif 000009
【図６】
2010122905.tif 000010
【図７】
2010122905.tif 000011
【図８】
2010122905.tif 000012
【図９】
2010122905.tif 000013