(57)【要約】【課題】一変数実区間多項式Ｆに対して、その実重複擬零点全体の集合ＭＺＲ(Ｆ)を決定する。【解決手段】実数の閉区間で表される区間数を係数とする一変数実区間多項式〔実区間多項式Ｆ〕に対して、集合Ｚ決定手段が、実区間多項式Ｆのエッジ多項式について、その実重複擬零点〔エッジ多項式に属する多項式の実重複零点〕全体の集合Ｚを求める。そして、集合ＭＺＲ(Ｆ)決定手段が、実数全体の集合に対する集合Ｚの補集合における全ての実区間Ｊごとに、各実区間Ｊ上で任意に１点γを選択して、この点γを実重複零点とする多項式が実区間多項式Ｆに存在するか否かを判定し、これが存在する場合の点γを含む実区間Ｊと集合Ｚとの和集合をとったものを、実区間多項式Ｆの実重複擬零点〔実区間多項式Ｆに属する多項式の実重複零点〕全体の集合ＭＺＲ(Ｆ)とする。【選択図】図４
2007299264.tif 000002
【特許請求の範囲】
【請求項１】
実数の閉区間で表される区間数を係数とする一変数実区間多項式〔以下、「実区間多項式Ｆ」という。〕および実区間Ｉを記憶する記憶手段と、
記憶手段に記憶される実区間Ｉ上で任意に１点〔以下、「選択点」という。〕を選択し、この選択点を実重複零点とする多項式が実区間多項式Ｆに存在するか否かを判定する選択点多項式判定手段と、
記憶手段に記憶される実区間Ｉ上に実重複零点を有し且つエッジ多項式〔実区間多項式Ｆの１つの係数を除いた係数が区間数の端点となっている実区間多項式の集合〕に属する多項式が存在するか否かを判定するエッジ多項式判定手段と
を備えた一変数実区間多項式の実重複擬零点の位置判定装置。
【請求項２】
実数の閉区間で表される区間数を係数とする一変数実区間多項式〔以下、「実区間多項式Ｆ」という。〕を記憶する記憶手段と、
実区間多項式Ｆのエッジ多項式〔実区間多項式Ｆの１つの係数を除いた係数が区間数の端点となっている実区間多項式の集合〕について、その実重複擬零点〔エッジ多項式に属する多項式の実重複零点〕全体の集合Ｚを求める集合Ｚ決定手段と、
実数全体の集合に対する集合Ｚの補集合における全ての実区間Ｊごとに、各実区間Ｊ上で任意に１点γを選択して、この点γを実重複零点とする多項式が実区間多項式Ｆに存在するか否かを判定し、これが存在する場合の点γを含む実区間Ｊと集合Ｚとの和集合をとったものを、実区間多項式Ｆの実重複擬零点〔実区間多項式Ｆに属する多項式の実重複零点〕全体の集合ＭＺＲ(Ｆ)とする集合ＭＺＲ(Ｆ)決定手段と
を備えた一変数実区間多項式の実重複擬零点の位置判定装置。
【請求項３】
記憶手段には、実数の閉区間で表される区間数を係数とする一変数実区間多項式〔以下、「実区間多項式Ｆ」という。〕および実区間Ｉが記憶され、
選択点多項式判定手段が、記憶手段に記憶される実区間Ｉ上で任意に１点〔以下、「選択点」という。〕を選択し、この選択点を実重複零点とする多項式が実区間多項式Ｆに存在するか否かを判定する選択点多項式判定ステップと、
エッジ多項式判定手段が、選択点多項式判定ステップにおいて選択点を実重複零点とする多項式が実区間多項式Ｆに存在しないと判定された場合に、記憶手段に記憶される実区間Ｉ上に実重複零点を有し且つエッジ多項式〔実区間多項式Ｆの１つの係数を除いた係数が区間数の端点となっている実区間多項式の集合〕に属する多項式が存在するか否かを判定するエッジ多項式判定ステップと
を有する一変数実区間多項式の実重複擬零点の位置判定方法。
【請求項４】
実区間多項式Ｆの各区間数をそれぞれの両端点および内分比で表すとして、
上記選択点多項式判定ステップは、
選択点を実区間多項式Ｆおよび実区間多項式Ｆを変数で１階微分したものに代入した連立方程式について、内分比に関する連立方程式の解を位置ベクトルの終点〔以下、「点」という。〕と見立てて、各区間数ごとに内分比を含む項（内分比項）と含まない項（非内分比項）に分け、内分比項の和で定まる点全体の凸包に、非内分比項の和で定まる点が入るか否かの判定をすることによって、選択点を実重複零点に有する多項式が実区間多項式Ｆに存在するか否かを判定するものである
請求項３に記載の一変数実区間多項式の実重複擬零点の位置判定方法。
【請求項５】
上記エッジ多項式判定ステップは、
実区間多項式Ｆおよび実区間多項式Ｆを変数で１階微分したものの連立方程式について、その解の存在条件に基づいて得られる多項式の零点が実区間Ｉに属するか否かを判定するステップを含む
請求項３または請求項４に記載の一変数実区間多項式の実重複擬零点の位置判定方法。
【請求項６】
上記エッジ多項式判定ステップは、
実区間多項式Ｆおよび実区間多項式Ｆを変数で１階微分したものの連立方程式について、その解の存在条件に基づいて得られる多項式の零点において、当該解がエッジ多項式において端点に固定されていない係数である区間数に属するか否かを判定するステップを含む
請求項５に記載の一変数実区間多項式の実重複擬零点の位置判定方法。
【請求項７】
記憶手段には、実数の閉区間で表される区間数を係数とする一変数実区間多項式〔以下、「実区間多項式Ｆ」という。〕が記憶され、
集合Ｚ決定手段が、実区間多項式Ｆのエッジ多項式〔実区間多項式Ｆの１つの係数を除いた係数が区間数の端点となっている実区間多項式の集合〕について、その実重複擬零点〔エッジ多項式に属する多項式の実重複零点〕全体の集合Ｚを求める集合Ｚ決定ステップと、
集合ＭＺＲ(Ｆ)決定手段が、実数全体の集合に対する集合Ｚの補集合における全ての実区間Ｊごとに、各実区間Ｊ上で任意に１点γを選択して、この点γを実重複零点とする多項式が実区間多項式Ｆに存在するか否かを判定し、これが存在する場合の点γを含む実区間Ｊと集合Ｚとの和集合をとったものを、実区間多項式Ｆの実重複擬零点〔実区間多項式Ｆに属する多項式の実重複零点〕全体の集合ＭＺＲ(Ｆ)とする集合ＭＺＲ(Ｆ)決定ステップと
を有する一変数実区間多項式の実重複擬零点の位置判定方法。
【請求項８】
上記集合Ｚ決定ステップは、
実区間多項式Ｆおよび実区間多項式Ｆを変数で１階微分したものの連立方程式について、その解の存在条件に基づいて得られる多項式の零点の集合ＳＺを求めるステップを含む
請求項７に記載の一変数実区間多項式の実重複擬零点の位置判定方法。
【請求項９】
上記集合Ｚ決定ステップは、
実区間多項式Ｆおよび実区間多項式Ｆを変数で１階微分したものの連立方程式について、その解の存在条件に基づいて得られる多項式の零点において、当該解がエッジ多項式において端点に固定されていない係数である区間数に属する場合に、当該零点あるいは当該零点を含む実区間を集合ＳＺに加えるステップを含む
請求項８に記載の一変数実区間多項式の実重複擬零点の位置判定方法。
【請求項１０】
上記集合ＭＺＲ(Ｆ)決定ステップにおいて、点γを実重複零点とする多項式が実区間多項式Ｆに存在するか否かを判定は、
実区間多項式Ｆの各区間数をそれぞれの両端点および内分比で表すとして、点γを実区間多項式Ｆおよび実区間多項式Ｆを変数で１階微分したものに代入した連立方程式について、内分比に関する連立方程式の解を位置ベクトルの終点〔以下、「点」という。〕と見立てて、各区間数ごとに内分比を含む項（内分比項）と含まない項（非内分比項）に分け、内分比項の和で定まる点全体の凸包に、非内分比項の和で定まる点が入るか否かの判定をすることによって、点γを実重複零点に有する多項式が実区間多項式Ｆに存在するか否かを判定するものである
請求項７から請求項９のいずれかに記載の一変数実区間多項式の実重複擬零点の位置判定方法。
【請求項１１】
コンピュータに請求項３から請求項１０のいずれかに記載の一変数実区間多項式の実重複擬零点の位置判定方法を実行させるための、一変数実区間多項式の実重複擬零点の位置判定プログラム。
【請求項１２】
請求項１１に記載の、一変数実区間多項式の実重複擬零点の位置判定プログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、実区間多項式の零点の位置判定装置、位置判定方法、位置判定プログラムおよび記録媒体に関する。より詳細には、一変数実区間多項式の実重複擬零点の位置判定装置、位置判定方法、位置判定プログラムおよび記録媒体に関する。
【背景技術】
【０００２】
係数に誤差のある一変数実多項式は、例えばディジタル信号処理やシステム制御の分野に現れ、その零点の位置はディジタルフィルタの周波数特性やシステムの性能に密接に関係する。
【０００３】
そして、多項式の実の重複零点〔重複度が２以上の零点〕は、どんなに小さな係数の変化に対しても、複数の複素零点あるいは実の近接零点となる。従って、実の零点が存在するか否か、あるいは、いくつ存在するのかを知る必要があるとき、実の重複零点の存在が重大な関心事となる。
【０００４】
式（１）で表される実係数一変数多項式が与えられたとする。
【数１】
2007299264.tif 000003
【０００５】
各実係数ａｉ（ここではｉ＝０，１，・・・，ｄである。）は、観測や測定によって得られたもので真の値とは異なるかもしれない、と仮定する。但し、誤差の範囲は分かっており、各実係数ａｉの真の値は実の閉区間［ｕｉ，ｈｉ］内にあるものとする。『各実係数ａｉがこの誤差範囲内にある多項式で、実の重複零点を有するものがあるか否か判定せよ』という問題を考える。
【０００６】
これに関連して、非特許文献１には、式（１）で表される多項式の各係数ａｉが複素数のとき、重複零点を有する複素数係数の多項式ｇ(ｘ)〔式（２）参照。〕の中で、式（３）で表される量、つまりｆ(ｘ)−ｇ(ｘ)のｌ２−ノルム〔文字「ｌ」はアルファベットの「エル」の小文字である。〕を最小とするものを求める問題を、適当なある二次形式の最小化の問題に帰着して解決する方法が示されている。
【数２】
2007299264.tif 000004
【０００７】
この方法は、下記の点で、後に詳述する本発明と似て非なるものである。
・係数およびその誤差を複素数の範囲とする点
・重複零点を実とは限らない点
・誤差の範囲指定が係数ごとではなく、多項式のｌ２−ノルムとしている点
・重複零点の有無についての判定問題は扱えるが、重複零点となる数の集合の決定、即ち、係数誤差範囲内で多項式を動かしたときに、その重複零点となる数すべての集合を決定する問題は扱えない点
【０００８】
一変数多項式は、各係数も変数と見なした上で元の変数に値を代入すると、それぞれの係数に対応する変数について一次式と見ることができる。この性質を利用すれば、『多項式の各係数を誤差範囲内で動かして、与えられた実数αを零点として持つようにできるか』という問題は、誤差範囲が実数のとき、誤差範囲の端点を正確に計算する区間演算で判定可能である。具体的には、各係数ａｉがｕｉ≦ａｉ≦ｈｉなる範囲にあるとして、式（４）を、端点を正確に計算する区間演算を用いて求め、その結果の区間に０が入るか否かを調べればよい。
【数３】
2007299264.tif 000005
【０００９】
誤差範囲が複素数のときには、非特許文献２に記述のあるとおり、適当なある不等式の成立、不成立の判定に帰着できる。
ｆ(ｘ)がｘ＝αにおいて重複零点を持つ必要十分条件は、ｆ(ｘ)＝ｆ′(ｘ)＝０がｘ＝αなる解を持つこと、すなわち、連立方程式（５）がｘ＝αなる解を持つことである。なお、ここで記号「′」はｘに関する微分を表す。
【数４】
2007299264.tif 000006
【００１０】
連立方程式（５）を書き改めると、連立方程式（６）がｘ＝αなる解を持つことである。
【数５】
2007299264.tif 000007
【００１１】
『ｘに値を代入して係数をある範囲で動かしたとき、連立方程式（６）が成り立つようにできるか』という問題に関連して、非特許文献２〔非特許文献２のCorollary ９参照。〕は、連立方程式（７）にｘｉ＝αｉを代入したとき、ｂijを、ｕij≦ｂij≦ｈijの範囲で動かして連立方程式（７）を成立させることができるか否かの判定が、適当なある不等式が成立するか否の判定に帰着できることを述べている。
【数６】
2007299264.tif 000008
【００１２】
そうすると、非特許文献２が提示する解法を連立方程式（６）のａｉに誤差がある場合にも適用できるように思える。しかし、連立方程式（７）では、行列（ｂij）の全ての成分が独立に動かせるものと仮定しての結果である。連立方程式（６）においては、ａｉ，・・・，ａｄが２ヵ所ずつに現れるので、非特許文献２のCorollary ９を用いた解法は適用できない。
【非特許文献１】L. Zhi and W. Wu, "Nearest Singular Polynomials", Journal of Symbolic Computation, Vol.26, No.6, pp.667-675, 1998.
【非特許文献２】H. J. Stetter, "The nearest polynomial with a given zero,and similar problems", ACM SIGSAM Bulletin, Vol.33, No.4, pp.2-4, 1999.
【発明の開示】
【発明が解決しようとする課題】
【００１３】
さて、『一変数多項式の各係数および係数毎の誤差をそれぞれ実数で与えるとして、各係数が係数毎の誤差範囲内に在る多項式が或る与えられた実の区間で重複零点を有するか否かを判定せよ、さらに、係数誤差範囲内で多項式を動かしたとき、その重複零点となる実数すべての集合を具体的に表示せよ』・・・（☆）という問題を考える。
【００１４】
非特許文献１に提示される解法は、ｌ２−ノルムで誤差をはかり、二次形式の最小化を用いるものであるから、係数毎に誤差範囲を指定した問題（☆）を扱うことができない〔なお、上記４点の差異も参照のこと。〕。また、非特許文献２に提示される解法は、１点を与えたときに、それを「零点」とするような多項式が係数誤差範囲内に存在するか否かの判定は可能だが、「重複零点」とする場合の問題（☆）には適用できない。また、いずれも、重複零点となりうる点の集合の決定はできない。
【００１５】
そこで、本発明は、問題（☆）に解答を与えることを目的とする。
この目的を、より端的に説明する。
これに先立ち、この明細書における記号および用語の説明をする。
但し、記号については、説明の便宜等からそれまでの意味とは異なる意味で同じ記号を用いる場合があることに留意しておくこと。
【００１６】
係数が確定していない（例えば、係数に誤差がある場合などである。）多項式を表す手法として、区間多項式がある。区間多項式Ｆ(ｘ)とは、数の集合である区間数Ａｉ（１≦ｉ≦ｄ、但しｉは整数。）を各項の係数として式（８）のように表記されるものである。つまり、区間多項式Ｆ(ｘ)は、係数がａｉ∈Ａｉである多項式ｆ(ｘ)〔式（９）参照。〕全体の集合を表す。なお、この明細書における区間多項式は、特に断りのない限り、一変数区間多項式であるとする。
【数７】
2007299264.tif 000009
【００１７】
ここでは、区間数を実数の範囲で考える。この場合、区間数Ａｉとして閉区間［ｕｉ，ｈｉ］を用いる。このような区間多項式であることを明確にするため、以下では、実区間多項式と云うことにする〔正確には、「一変数実区間多項式」と云うべきであるが、「実区間多項式」と略記する。〕。
また、ｅｉ(ｘ)は、実数である係数が確定した多項式であり、恒等的に０ではないとする。
なお、多項式について、例えば実区間多項式Ｆ(ｘ)を実区間多項式Ｆなどのように変数を略記して表すことがある。
【００１８】
実区間多項式Ｆに対し、実区間多項式Ｆに属する多項式ｆが存在して、多項式ｆがａ∈Ｒ〔記号∈は、或る要素が集合に「属する」ことを意味する。Ｒは、実数全体の集合を表す。〕で重複零点を有するとき、実区間多項式Ｆは実重複擬零点ａを有する、と云うことにする。実区間多項式Ｆに対し、その実重複擬零点全体の集合をＭＺＲ(Ｆ)と表記する。
【００１９】
このとき、問題（☆）を次のように表現できる。
《問題１》  与えられた実区間多項式Ｆおよび実の区間Ｉに対し、実区間Ｉ内に実区間多項式Ｆの実重複擬零点が存在するか否かを判定せよ。
《問題２》  与えられた実区間多項式Ｆに対し、ＭＺＲ(Ｆ)を決定せよ。
【００２０】
つまり、本発明は、与えられた実区間多項式Ｆおよび実の区間Ｉに対し、実区間Ｉ内に実区間多項式Ｆの実重複擬零点が存在するか否かを判定し、あるいは、与えられた実区間多項式Ｆに対してＭＺＲ(Ｆ)を決定する一変数実区間多項式の実重複擬零点の位置判定装置、位置判定方法、位置判定プログラムおよび記録媒体を提供することを目的とする。
【課題を解決するための手段】
【００２１】
上記課題を解決するために、本発明は、実数の閉区間で表される区間数を係数とする一変数実区間多項式〔実区間多項式Ｆ〕および実区間Ｉについて、選択点多項式判定手段が、実区間Ｉ上で任意に１点〔選択点〕を選択し、この選択点を実重複零点とする多項式が実区間多項式Ｆに存在するか否かを判定して、エッジ多項式判定手段が、実区間Ｉ上に実重複零点を有し且つエッジ多項式〔実区間多項式Ｆの１つの係数を除いた係数が区間数の端点となっている実区間多項式の集合〕に属する多項式が存在するか否かを判定する。
このような構成は数学的な保証に基づくものであり、この詳細は後述する。
【００２２】
また、上記課題を解決するために、本発明は、実数の閉区間で表される区間数を係数とする一変数実区間多項式〔実区間多項式Ｆ〕に対して、集合Ｚ決定手段が、実区間多項式Ｆのエッジ多項式について、その実重複擬零点〔エッジ多項式に属する多項式の実重複零点〕全体の集合Ｚを求める。そして、集合ＭＺＲ(Ｆ)決定手段が、実数全体の集合に対する集合Ｚの補集合における全ての実区間Ｊごとに、各実区間Ｊ上で任意に１点γを選択して、この点γを実重複零点とする多項式が実区間多項式Ｆに存在するか否かを判定し、これが存在する場合の点γを含む実区間Ｊと集合Ｚとの和集合をとったものを、実区間多項式Ｆの実重複擬零点〔実区間多項式Ｆに属する多項式の実重複零点〕全体の集合ＭＺＲ(Ｆ)とする。
このような構成は数学的な保証に基づくものであり、この詳細は後述する。
【発明の効果】
【００２３】
本発明によれば、数学的保証の下に、実区間Ｉの１点について、これを実重複零点とする多項式が実区間多項式Ｆに存在するか否かを判定し、実区間Ｉ上に実重複零点を有し且つエッジ多項式に属する多項式が存在するか否かを判定することで、有限ステップで完全にかつ効率良く、実区間Ｉ内に実区間多項式Ｆの実重複擬零点が存在するか否かを判定することができる。
【００２４】
本発明によれば、数学的保証の下に、まず、実区間多項式Ｆのエッジ多項式について、その実重複擬零点全体の集合Ｚを求めてから、実数全体の集合に対する集合Ｚの補集合における全ての実区間Ｊごとに、各実区間Ｊ上で任意に１点γを選択して、この点γを実重複零点とする多項式が実区間多項式Ｆに存在するか否かを判定し、これが存在する場合の点γを含む実区間Ｊと集合Ｚとの和集合をとったものを、実区間多項式Ｆの実重複擬零点全体の集合ＭＺＲ(Ｆ)とすることで、有限ステップで完全にかつ効率良く、実区間多項式Ｆの実重複擬零点全体の集合ＭＺＲ(Ｆ)を決定することができる。
【発明を実施するための最良の形態】
【００２５】
[理論]
これから、本発明における実区間多項式の実重複擬零点の位置判定の理論およびアルゴリズムを、図面を参照しながら説明する。なお、予め説明しておくと、本発明における「実区間多項式の実重複擬零点の位置判定」とは、実区間多項式の実重複擬零点の位置（座標）を特定することではなく、所定の領域に実区間多項式の実重複擬零点が存在するか否かに係わる判定および実区間多項式に対してＭＺＲ(Ｆ)を決定することである。換言すれば、実区間多項式の実重複擬零点が所定の領域に存在するか否か、および、ＭＺＲ(Ｆ)の決定の意味において、実区間多項式の実重複擬零点の位置判定をすることになる。
【００２６】
式（８）および式（９）において、区間数の端点ｕｉ、ｈｉおよび多項式ｅｉ(ｘ)の係数は、理論上は実数としてよいが、コンピュータなどによる演算の上では四則演算および等号判定を有限ステップのアルゴリズムで実行できることが必要かつ十分であり、そのために例えば実代数的数（整数係数一変数代数方程式の根となる実数）とし、具体例として有理数であるとする。
以下では、説明の便宜から、ｅｉ(ｘ)を有理数係数多項式の場合を例示して説明する。また、実代数的数として有理数を例にとって説明する。つまり、端点ｕｉ、ｈｉを有理数としている。
【００２７】
まず、《問題１》について。
問題１は、既述のとおり『与えられた実区間多項式Ｆおよび実の区間Ｉに対し、実区間Ｉ内に実区間多項式Ｆの実重複擬零点が存在するか否かを判定せよ』である。
【００２８】
この問題１に対する解答の要旨は、次のとおりである。
＜１＞実区間Ｉ内で任意に選択した１点ｃについて、この点ｃが実区間多項式Ｆの実重複擬零点か否かを判定する。つまり、ｃ∈Ｉを実重複零点とする多項式が実区間多項式Ｆに存在するか否かを判定する。点ｃが実重複擬零点ならば、問題１に対して「存在する」を解答として与える。点ｃが実重複擬零点でなければ、次の処理＜２＞を行う。
＜２＞実区間多項式Ｆのエッジ多項式に属する多項式であって、実区間Ｉ内に実重複零点を有する多項式が存在するか否かを判定する。このような多項式が存在すれば、問題１に対して「存在する」を解答として与える。このような多項式が存在しなければ、問題１に対して「存在しない」を解答として与える。
【００２９】
ここでエッジ多項式とは、「実区間多項式Ｆの１つの係数を除いた係数が区間数の端点となっている実区間多項式の集合」である。より詳細には、実区間多項式Ｆに対し、そのエッジ多項式とは、ある一つの番号ｊ（１≦ｊ≦ｄ、但しｊは整数。）を除いては、係数ａｉがｕｉもしくはｈｉ（但し、ｉ≠ｊである。）に等しい実区間多項式の集合のことであり、式（１０）で表される。
【数８】
2007299264.tif 000010
【００３０】
ここで、留意しなければならないのは、定義あるいは式（１０）から明らかなとおり、エッジ多項式は実区間多項式Ｆの部分集合である。例えばｊ番目の係数を除いて係数が区間数の端点に固定されているエッジ多項式と云うとき、このエッジ多項式には最多２ｄ−１個のものが考えられる。なぜなら、ｊ番目の係数以外の各係数がそれぞれの区間数で端点を取る組み合わせが考えられ、式（１０）の整数ｊが１≦ｊ≦ｄであるとき、この組み合わせは最多２ｄ−１個だからである。つまり、式（１０）の第２項は最多２ｄ−１本の多項式が考えられるので、「ｊ番目の係数を除いて係数が区間数の端点に固定されているエッジ多項式」は最多２ｄ−１個のエッジ多項式を云うことになる。そうすると、実区間多項式Ｆ(ｘ)では、最多ｄ×２ｄ−１個のエッジ多項式が存在する。ここで、エッジ多項式に属する多項式〔単に多項式と言えば、係数が確定している多項式を云う。〕を、「要素エッジ多項式」と云うことにする。
数学的表現を用いるならば、実区間多項式Ｆ、エッジ多項式Ｅ、要素エッジ多項式ｇとしたとき、これらはＥ⊂Ｆ、ｇ∈Ｅなる関係にある。
【００３１】
以下、問題１に対する解答の要旨が上記のとおりに与えられる理由を説明する。
まず、実区間Ｉ上で任意に選択した１点ｃについて、この点ｃを実重複零点とする多項式が実区間多項式Ｆ(ｘ)に存在するならば（図１のステップＳ１００参照。）、「実区間Ｉに実重複零点を有する多項式ｆ(ｘ)∈Ｆ(ｘ)が存在する」ことが判明したことになり、「実区間Ｉ内に実区間多項式Ｆの実重複擬零点が存在する」ことが言えたことと同じである（図１のステップＳ１０３参照。）。つまり、問題１に解答を与えたことになる。
なお、『実区間Ｉ上で任意に選択した１点ｃについて、この点ｃを実重複零点とする多項式が実区間多項式Ｆ(ｘ)に存在するか否か』の判定方法は後述の《凸包判定》で説明する。
【００３２】
次に、『実区間Ｉ上で任意に選択された１点ｃについて、この点ｃを実重複零点とする多項式が実区間多項式Ｆ(ｘ)に存在しない場合、もし、実区間Ｉ上に実重複零点を有する多項式が存在するならば、その中で、エッジ多項式に属するものが存在する』ことが言える。
この証明を以下に説明する。
【００３３】
今、「実区間Ｉ上の点ｄ（但し、点ｃを除く。）を実重複零点とする多項式ｆ(ｘ)∈Ｆ(ｘ)が存在するとして、多項式ｆ(ｘ)がエッジ多項式に属さない」と仮定する。このとき、区間数の端点に固定されていない係数（２つ以上あるとする。）を２つ選択し、これをｐおよびｑとする。
ここで記号αを実区間Ｉ上の点を表すパラメータとして、ｆ(α)およびｆ′(α)を式（１１）の如く表記することにする。なお、上記では記号αを実重複零点としたが、ここでの説明では異なる定義であることに留意すること。
【数９】
2007299264.tif 000011
【００３４】
点αにおいてｆ(α)＝ｆ′(α)＝０になることは、ｐおよびｑの２変数連立一次方程式（１２）が成立することである。
【数１０】
2007299264.tif 000012
【００３５】
点ｄは実重複零点であるから、α＝ｄでは、所定の範囲（区間数内）に収まっている連立方程式（１２）の解ｐ、ｑが存在する（このｐ、ｑは、点ｄを実重複零点とする多項式ｆ(ｘ)の係数ｐおよびｑに対応する。）。
ここでα＝ｄにおいて行列式（１３）が０とすると、連立方程式の解が不定であるならば、ｐおよびｑを解としたまま、少なくともその１つを区間数の端点となるまで動かすことができる。また、連立方程式の解が存在しないのであるならば、パラメータαが行列式（１３）を０にする値に近付くとき、ｐ、ｑのうち少なくとも一方は∞あるいは−∞に発散するから、その前に区間数の端点に達することとなる。これは、上記仮定：「実区間Ｉ上の点ｄを実重複零点とする多項式ｆ(ｘ)∈Ｆ(ｘ)が存在するとして、多項式ｆ(ｘ)がエッジ多項式に属さない」と矛盾する。なお記号≡は「定義」を表す。
【数１１】
2007299264.tif 000013
【００３６】
従って、行列式（１３）はα＝ｄにおいて０ではないとする。点αを実区間Ｉ上において点ｄから動かしていくと、点αが点ｃに到達する前に、次のいずれかが起こる。もし、いずれも起こらずに点ｃに到達したとすると、「点ｃを実重複零点とする多項式が実区間多項式Ｆ(ｘ)に存在しない」とする前提と矛盾する。なお、α０は点ｄおよび点ｃの間にある実区間Ｉ上の点である。
（ｉ）ｐが区間数の端点に到達する。
（ｉｉ）ｑが区間数の端点に到達する。
（ｉｉｉ）行列式（１３）が、α＝α０において０になる。
【００３７】
（ｉ）および（ｉｉ）の場合は、多項式ｆ(ｘ)の係数のうち区間数の端点とならないものの個数が多項式ｆ(ｘ)の場合よりも１つ小さい多項式であって、実区間Ｉ上に実重複零点を有する多項式ｇ(ｘ)∈Ｆ(ｘ)が存在することを示している。
【００３８】
（ｉｉｉ）の場合は、後述の《補足説明》で説明するように、行列式（１３）が０となる点において、連立方程式（１２）は不定となるので、ｐおよびｑを解としたまま、少なくともその１つを区間数の端点となるまで動かすことができる。つまり、多項式ｆ(ｘ)の係数のうち区間数の端点とならないものの個数が多項式ｆ(ｘ)の場合よりも１つ小さい多項式であって、実区間Ｉ上に実重複零点を有する多項式ｇ(ｘ)∈Ｆ(ｘ)が存在することを示している。
【００３９】
結局、以上から、点ｃを実重複零点とする多項式が実区間多項式Ｆ(ｘ)に存在しない場合、実区間Ｉ上に実重複零点を有する多項式が存在するとしたとき、実区間Ｉ上の点ｄを実重複零点とするエッジ多項式に属さない多項式ｆ(ｘ)∈Ｆ(ｘ)に対して、多項式ｆ(ｘ)の係数のうち区間数の端点とならないものの個数が多項式ｆ(ｘ)の場合よりも１つ小さい多項式であって、実区間Ｉ上に実重複零点を有する多項式ｇ(ｘ)∈Ｆ(ｘ)が存在することが言えた。以上のような操作を（区間数の端点に固定されていない係数が３つ以上ある場合に）必要に応じて繰り返せば、エッジ多項式に属する多項式ｇ(ｘ)∈Ｆ(ｘ)で、実区間Ｉ上に実重複零点を有するものが存在することが言える。
【００４０】
従って、点ｃを実重複零点とする多項式が実区間多項式Ｆ(ｘ)に存在しない場合には、『エッジ多項式に属する多項式ｇ(ｘ)∈Ｆ(ｘ)であって、その実重複零点が実区間Ｉ上にあるものが存在するか否か』の判定をすればよい（図１のステップＳ１０１参照。）。このような多項式が存在すれば、問題１に対する解答は「存在する」となる（図１のステップＳ１０３参照。）。このような多項式が存在しなければ、問題１に対する解答は「存在しない」となる（図１のステップＳ１０２参照。）。
なお、『エッジ多項式に属する多項式ｇ(ｘ)∈Ｆ(ｘ)であって、その実重複零点が実区間Ｉ上にあるものが存在するか否か』の判定方法は後述の《エッジ多項式判定》で説明する。
【００４１】
《補足説明》
補足説明では、行列式（１３）が０となる点において、連立方程式（１２）が不定となることを説明する。
ここで、ｎｐ(α)、ｎｑ(α)を式（１４）によって定義する。ここでのｐ、ｑは、上記と同様、２つ選択された区間数の端点に固定されていない係数を意味する。
【数１２】
2007299264.tif 000014
【００４２】
連立方程式（１２）の解ｐ、ｑは、αの関数として、式（１５）によって表される。
【数１３】
2007299264.tif 000015
【００４３】
αがα０に近づくとき、Ｄ(α)は０に収束するから、ｎｐ(α)、ｎｑ(α)も０に収束する。収束することは、全ての係数がαの連続関数として表すことができることから保証されており、もし収束値が０以外ならば、αがα０に到達する前まで連立方程式（１２）の解が有界であることに矛盾する。ｎｐ(α)、ｎｑ(α)はαについて連続であるから、結局、式（１６）が成り立つ。
【数１４】
2007299264.tif 000016
【００４４】
さらに、ａｊ(α０)＝ｂｊ(α０)＝０ならば〔但し、ここでのｊは、ｊ＝１，２とする。〕、ｃｊ(α０)＝０が成り立つ。なぜなら、ある正数Ｍがあって、αが実区間Ｉ上において点α０に近づくとき、常に不等式｜ｐ(α)｜≦Ｍ、｜ｑ(α)｜≦Ｍが成立するので、三角不等式から式（１７）が成立する。
【数１５】
2007299264.tif 000017
【００４５】
αが実区間Ｉ上において点α０に近づくとき、(｜ａｊ(α)｜＋｜ｂｊ(α)｜)Ｍは０に収束するから、ｃｊ(α)も０に収束する。そして、ｃｊ(α)は連続であることからｃｊ(α０)＝０が成り立つ。
【００４６】
この準備の下、次の３通りに分けて証明する。
（ｉ）ａ１(α０)＝ａ２(α０)＝０の場合について。もしｂ１(α０)≠０ならば、行列式（１３）から、連立方程式（１２）の第２式は第１式のｂ２(α０)／ｂ１(α０)倍となる。ここでｂ１(α０)≠０から、連立方程式（１２）が不定であることがわかる。もしｂ１(α０)＝０ならば、上記の準備からｃ１(α０)＝０となり、連立方程式（１２）は第２式のみとなる。このとき、ｂ２(α０)＝０ならば、やはり上記準備からｃ２(α０)＝０となり、第２式もなくなる。ｂ２(α０)≠０ならば第２式は残るが、解は不定である。
【００４７】
（ｉｉ）ａ１(α０)およびａ２(α０)のうち、一方が０であり、他方が０ではない場合について。この場合、ａ１(α０)＝０、ａ２(α０)≠０の場合について示せば十分である。上記のＤ(α０)＝０から、ｂ１(α０)＝０となる。従って、上記準備からｃ１(α０)＝０となる。つまり、連立方程式（１２）は第２式のみに退化し、ａ２(α０)≠０から解は不定であることがわかる。
【００４８】
（ｉｉｉ）ａ１(α０)およびａ２(α０)が共に０ではない場合について。この場合、上記のＤ(α０)＝０および行列式（１３）から、連立方程式（１２）において、第２式は第１式のａ２(α０)／ａ１(α０)倍となる。従って、ａ１(α０)≠０から解は不定であることがわかる。
以上で《補足説明》は終わりである。
【００４９】
《凸包判定》
実区間Ｉ上の任意の１点ｃを選択して、この点ｃを実重複零点とする多項式が実区間多項式Ｆ(ｘ)に存在するか否かを調べる方法について説明する。以下では、アルゴリズムを簡単かつ効率良くするため、エッジ多項式に限らない範囲で調べるとする。
【００５０】
ここでは、上記点ｃを説明の便宜からαに記号の置き換えをする。
式（８）で与えられる実区間多項式の区間数Ａｊを閉区間［ｕｊ，ｈｊ］で表したことに留意すると、閉区間［ｕｊ，ｈｊ］は、パラメータｔｊ（０≦ｔｊ≦１なる実数）を用いて｛（ｈｊ−ｕｊ）ｔｊ＋ｕｊ｝と表記することができる。パラメータｔｊは、閉区間の両端点ｕｊ、ｈｊの内分比を表す。このとき、式（８）の実区間多項式Ｆ(ｘ)は、上記区間数｛（ｈｊ−ｕｊ）ｔｊ＋ｕｊ｝を各項の係数として式（１８）のように表現され、各ｊ（１≦ｊ≦ｄ、但しｊは整数。）に対して係数がａｊ∈｛（ｈｊ−ｕｊ）ｔｊ＋ｕｊ｝である多項式ｆ(ｘ)〔式（１９）参照〕の全体の集合を表す。
【数１６】
2007299264.tif 000018
【００５１】
このとき、「点αを実重複零点とする多項式が実区間多項式Ｆ(ｘ)に存在するか否か」は、「連立方程式（２０）を満足するｔｊの組み合わせが存在するか否か」と同値である。また、連立方程式（２０）を書き改めると、連立方程式（２１）と表せる。
【数１７】
2007299264.tif 000019
【００５２】
つまり、連立方程式（２１）を満足するｔｊの組み合わせが存在するならば、それは、この点αを実重複零点とする多項式が実区間多項式Ｆ(ｘ)に存在することを意味する。ここで留意しなければならないのは、ｔｊの組み合わせを特定することではなく、「連立方程式（２１）を満足するｔｊの組み合わせが存在するか否か」である。ここで説明の便宜から、（ｅｊ(α)  ｅ′ｊ(α)）ＴをＢｊと表記する〔但し、Ｔは転置を表す。〕。そうすると、Ｂｊは、デカルト直交座標系において、原点を始点、（ｘ，ｙ）＝（ｅｊ(α)，ｅ′ｊ(α)）を終点とする位置ベクトルとみることができる。このような視点から、以下の説明でｘ座標、ｙ座標と云えば、デカルト直交座標系〔以下、「平面」という。〕において位置ベクトルの終点を指すものする。
【００５３】
そうすると、式（２１）左辺について（ｈｊ−ｕｊ）ｔｊＢｊを、「Ｂｊを（ｈｊ−ｕｊ）倍した位置ベクトル（ｈｊ−ｕｊ）Ｂｊを、ｔｊによってスカラー倍したものである」と見れば、０≦ｔｊ≦１によって式（２１）の左辺が取り得る平面上の範囲に、式（２１）の右辺の点が存在するか否かを調べればよい。つまり、凸包に或る１点が存在するか否かの判定に持ち込むことを考えればよい。そこで、このような凸包を用いた判定を効率良く行うために、前処理を行う。
【００５４】
まず、式（２１）の左辺の各項（ｊ＝１，…，ｄ）を順番に見ていき、各項について次のような判定と書き換えを行う。まず、（ｈｊ−ｕｊ）Ｂｊのｘ座標〔つまり、（ｈｊ−ｕｊ）ｅｊ(α)である。〕が負であるかを判定する。負である場合には、（ｈｊ−ｕｊ）ｔｊＢｊを（ｈｊ−ｕｊ）（１−ｔｊ）Ｂｊに書き換える。次に、（ｈｊ−ｕｊ）Ｂｊのｘ座標が負でない場合は、（ｈｊ−ｕｊ）Ｂｊのｘ座標が０かつｙ座標〔つまり、（ｈｊ−ｕｊ）ｅ′ｊ(α)である。〕が負であるか否かを判定する。ｘ座標が０かつｙ座標が負である場合には、（ｈｊ−ｕｊ）ｔｊＢｊを（ｈｊ−ｕｊ）（１−ｔｊ）Ｂｊに書き換える。
なお、この操作は式（２０）において、（ｈｊ−ｕｊ）Ｂｊのｘ座標が負である場合に｛（ｈｊ−ｕｊ）ｔｊ＋ｕｊ｝Ｂｊを｛（ｈｊ−ｕｊ）（１−ｔｊ）＋ｕｊ｝Ｂｊと書き換え、（ｈｊ−ｕｊ）Ｂｊのｘ座標が０かつｙ座標が負である場合に｛（ｈｊ−ｕｊ）ｔｊ＋ｕｊ｝Ｂｊを｛（ｈｊ−ｕｊ）（１−ｔｊ）＋ｕｊ｝Ｂｊと書き換えることと同じである。
【００５５】
以上の操作は、例えば、ｘ座標が負である位置ベクトル（ｈｊ−ｕｊ）Ｂｊをｔｊスカラー倍（０≦ｔｊ≦１）することは、平面原点対象に移動した位置ベクトル（ｈｊ−ｕｊ）×（−１）×Ｂｊをｋｊスカラー倍（−１≦ｋｊ≦０）することと同じであるから、ｔｊの範囲が０≦ｔｊ≦１であることに留意してｋｊ＝ｔｊ−１とおくと、（ｈｊ−ｕｊ）×（−１）×ｋｊ×Ｂｊは、（ｈｊ−ｕｊ）×（１−ｔｊ）×Ｂｊとなることに基づく。このような操作を行うことで、式（２１）の左辺の点（ｈｊ−ｕｊ）Ｂｊは、見かけ上、全て平面の右半平面（ｘ座標が０以上の領域全体、但し、ｘ座標が０かつｙ座標が負の部分は除く。）に集められるとともに、平面のｙ軸の負の部分には点が乗らないものとなる。換言すれば、この操作の結果得られた点集合は、平面原点を頂点とする凸包を平面の右半平面で構成する（但し、平面のｙ軸の負の部分に凸包の頂点はない。）。
【００５６】
なお、このような操作は、後述の凸包を求めるための便宜としての前処理であるから、上記に限定されるものではない。例えば、（ｈｊ−ｕｊ）Ｂｊのｘ座標が正であるかを判定し、正である場合には、（ｈｊ−ｕｊ）ｔｊＢｊを（ｈｊ−ｕｊ）（１−ｔｊ）Ｂｊに書き換え、（ｈｊ−ｕｊ）Ｂｊのｘ座標が正でない場合は、（ｈｊ−ｕｊ）Ｂｊのｘ座標が０かつｙ座標が負であるか否かを判定する。そして、ｘ座標が０かつｙ座標が負である場合には、（ｈｊ−ｕｊ）ｔｊＢｊを（ｈｊ−ｕｊ）（１−ｔｊ）Ｂｊに書き換える（つまり、平面原点を頂点とする凸包を平面左側で構成する。）、といった操作などに適宜に変更できる。
【００５７】
以上の操作を行ない、その結果に対して適切な式変形および記号の置き換え（ａｊおよびｂ）をすると、当該結果は式（２２）のように表すことができる。但し、式（２２）において、ａｊおよびｂは上記Ｂｊと同様にａｊ＝（ａｊ１  ａｊ２）Ｔ、ｂ＝（ｂ１  ｂ２）Ｔと表される。つまり、ａｊおよびｂは平面上の原点を始点とする位置ベクトルとみることができる。
【数１８】
2007299264.tif 000020
【００５８】
結局、式（２２）を満たすようなｔｊ（０≦ｔｊ≦１）の組み合わせが存在するか否かの判定となるが、これは、εｊ＝０あるいはεｊ＝１とした場合に、式（２３）の全体、即ち平面上で高々２ｄ＋１個の点の凸包に式（２２）の右辺ｂの終点座標が入るか否かの判定と同じである〔下記参考文献１参照。〕。なお、式（２２）を得る際の上記操作から、式（２３）の全体のなす凸包は、平面の右半平面（但し、ｘ座標が０かつｙ座標が負の部分は除く。）に存在することがわかる。従って、式（２２）の右辺ｂのｘ座標が負の場合、あるいは、ｂのｘ座標が０かつｙ座標が負の場合、凸包を下記説明のように具体的に構成しなくてもｂが式（２３）の全体のなす凸包に入らないことがわかることに留意するべきである。
（参考文献１）  関川浩、白柳潔著、「区間多項式の零点の所在について」、社団法人電子情報通信学会、電子情報通信学会論文誌Ａ、Vol.J89-A、No.3、pp.199-216
【数１９】
2007299264.tif 000021
【００５９】
そこで、まず、式（２３）で表される点の全体の凸包を求める。これは、効率的に求めることができる。
具体的にはまず、平面のｙ軸の負の部分を除く平面の右半平面の領域〔−π／２＜ａｒｇ≦π／２、ａｒｇは角度を表す。〕において、ａｊ≠０を傾き〔ａｒｇ(ａｊ)＝ａｊ２／ａｊ１、但し、ａｊ１＝０ならばａｊ１／ａｊ２は∞とみなす。〕でソート（sort）する。つまり、位置ベクトルａｊ≠０がｘ軸となす角度ａｒｇ(ａｊ)を、−π／２＜ａｒｇ≦π／２で、小さい方から大きい方へと昇順に並び替える。但し、同じ傾きのものがあるときには、それらを全部足したものに置き換えたものを１つとしてソートする。例えば、ａｊおよびａｋの傾きが同じときには、ａｊ，ａｋの代わりに、ａｊ＋ａｋを対象としてソートする。なぜなら、傾きが同じ位置ベクトルａｊおよび位置ベクトルａｋの各終点は平面上において凸包の頂点となりえないからである（凸包の頂点の可能性があるのは、同じ傾きのものを全てベクトル加算した点である。）。このソートの結果を位置ベクトルｐ１，・・・，ｐｍとする。なお、ｍはｄ＋１より小さいことがあることに留意すること。
【００６０】
このとき、求める平面上の凸包の頂点は、平面原点（０と表記する。）から始めて反時計回りに、０，ｐ１，ｐ１＋ｐ２，…，ｐ１＋…＋ｐｎ，ｐ２＋ｐ３＋…ｐｍ，ｐ３＋…＋ｐｍ，…，ｐｍ−１＋ｐｍ，ｐｍの全部で２ｍ個となる。
つまり、式（２３）の全体のなす凸包の平面における頂点座標は、反時計回りに式（２４）で与えられる位置ベクトルｖｉ（０≦ｉ≦２ｍ−１）の終点として表される〔複素平面の場合について参考文献１参照。〕。
【数２０】
2007299264.tif 000022
【００６１】
この位置ベクトルｖｉ（０≦ｉ≦２ｍ−１）の終点〔以下、「頂点ｖｉ」という。〕で構成される凸包に式（２２）の右辺ｂの終点が入るか否かを判定する。この判定は、例えば次のようにして行うことができる。まず、ａｒｇ(ｂ)に対して、ａｒｇ(ｖｋ)≦ａｒｇ(ｂ)＜ａｒｇ(ｖｋ＋１)なる凸包の頂点ｖｋ、ｖｋ＋１をとる。このとき、式（２２）の右辺ｂの終点が凸包に入るか否かは、頂点ｖｋ、ｖｋ＋１を結んだ線分に対して原点側（線分上を含む。）あるいは原点とは反対側の何れの側にｂの終点が存在するかと同値である。そこで、位置ベクトルｚ１＝（ｚ１ｘ，ｚ１ｙ）、ｚ２＝（ｚ２ｘ，ｚ２ｙ）に対してｄ（ｚ１，ｚ２）なる演算を式（２５）の如く定義する。このとき、ｄ(ｂ−ｖｋ，ｖｋ＋１−ｂ)が正ならばｂの終点が凸包に含まれず、ｄ(ｂ−ｖｋ，ｖｋ＋１−ｂ)が０以下ならばｂの終点が凸包に含まれる。
【数２１】
2007299264.tif 000023
【００６２】
ｂの終点が凸包に入る場合には、点ｃを実重複零点とする多項式が実区間多項式Ｆ(ｘ)に存在すると判定でき、ｂの終点が凸包に入らない場合には、点ｃを実重複零点とする多項式が実区間多項式Ｆ(ｘ)に存在しないと判定できる。
【００６３】
以上のアルゴリズムに基づく凸包判定の処理フローを一例として図２に示す。
【００６４】
まず、実区間Ｉ上の任意の１点αを選択する（ステップＳ４００）。
【００６５】
次に、選択した点αをｘ＝αとして実区間多項式Ｆ(ｘ)および実区間多項式Ｆ(ｘ)を１階微分したものに代入する（ステップＳ４０１）。
【００６６】
パラメータｊを１に設定する（ステップＳ４０２）。
【００６７】
このパラメータｊに対応する（ｈｊ−ｕｊ）ｅｊ(α)が負であるかを判定する（ステップＳ４０３）。
【００６８】
（ｈｊ−ｕｊ）ｅｊ(α)負である場合には、｛（ｈｊ−ｕｊ）ｔｊ＋ｕｊ｝Ｂｊを｛（ｈｊ−ｕｊ）（１−ｔｊ）＋ｕｊ｝Ｂｊと書き換える（ステップＳ４０５）。
【００６９】
もし（ｈｊ−ｕｊ）ｅｊ(α)が負でない場合は、（ｈｊ−ｕｊ）ｅｊ(α)が０かつ（ｈｊ−ｕｊ）ｅ′ｊ(α)が負であるか否かを判定する（ステップＳ４０４）。
【００７０】
（ｈｊ−ｕｊ）ｅｊ(α)が０かつ（ｈｊ−ｕｊ）ｅ′ｊ(α)が負である場合には、｛（ｈｊ−ｕｊ）ｔｊ＋ｕｊ｝Ｂｊを｛（ｈｊ−ｕｊ）（１−ｔｊ）＋ｕｊ｝Ｂｊと書き換える（ステップＳ４０５）。
【００７１】
そしてパラメータｊがｄと等しいか否かを判定する（ステップＳ４０６）。
【００７２】
ｊ≠ｄであれば、ｊに１加えたものを新たなｊとして（ステップＳ４０７）、ステップＳ４０３〜Ｓ４０６の処理を行う。ｊ＝ｄであれば、ステップＳ４０３〜Ｓ４０６の処理で得られた実区間多項式を式（２２）の如く式変形する（ステップＳ４０８）。
【００７３】
次に、ステップＳ４０８の処理で得られた式（２２）の右辺で表される位置ベクトルｂのｘ座標が負であるか否かを判定する（ステップＳ４０８ｘ）。
【００７４】
位置ベクトルｂのｘ座標が負であれば、位置ベクトルｂがステップＳ４０８の処理で得られた式（２２）の左辺で表される点全体の凸包に入ることはないので、任意に選択された点αを実重複零点とする多項式が実区間多項式Ｆ(ｘ)に存在しないといえる（ステップＳ４１１）。
【００７５】
位置ベクトルｂのｘ座標が負でなければ、ステップＳ４０８ｙの処理を行う。即ち、ステップＳ４０８の処理で得られた式（２２）の右辺で表される位置ベクトルｂのｘ座標が０かつｙ座標が負であるか否かを判定する（ステップＳ４０８ｙ）。
【００７６】
位置ベクトルｂのｘ座標が０かつｙ座標が負であれば、位置ベクトルｂがステップＳ４０８の処理で得られた式（２２）の左辺で表される点全体の凸包に入ることはないので、任意に選択された点αを実重複零点とする多項式が実区間多項式Ｆ(ｘ)に存在しないといえる（ステップＳ４１１）。
【００７７】
位置ベクトルｂのｘ座標が０かつｙ座標が負でなければ、ステップＳ４０９の処理を行う。即ち、ステップＳ４０８の処理で得られた式（２２）の左辺で表される点全体の凸包を上記のアルゴリズムに従って構成する（ステップＳ４０９）。
【００７８】
次に、ステップＳ４０８の処理で得られた式（２２）の右辺で表される点が、ステップＳ４０９で構成された凸包に入るか否かを判定する（ステップＳ４１０）。
【００７９】
凸包に入れば、任意に選択された点αを実重複零点とする多項式が実区間多項式Ｆ(ｘ)に存在するといえる（ステップＳ４１２）。凸包に入らなければ、任意に選択された点αを実重複零点とする多項式が実区間多項式Ｆ(ｘ)に存在しないといえる（ステップＳ４１１）。
以上で《凸包判定》の説明は終わりである。
【００８０】
《エッジ多項式判定》
エッジ多項式に属する多項式ｇ(ｘ)∈Ｆ(ｘ)であって、その実重複零点が実区間Ｉ上にあるものが存在するか否かを調べる方法について説明する。
ここでは説明の便宜から、ｊ番目の係数を除いて係数が区間数の端点に固定されているエッジ多項式ＥをＡｊｅj(ｘ)＋ｒ(ｘ)と表現する〔式（１０）参照。但し、既述のとおり、ｊ番目の係数を除いて係数が区間数の端点に固定されているエッジ多項式Ｅにおいてｒ(ｘ)には最多２ｄ−１本の多項式が考えられることに留意すること。〕。さらに表現を簡略なものとするため、ｊ番目の係数を除いて係数が区間数の端点に固定されていないことを前提としてインデックスｊを明記しないことにする。但し、区間数Ａ＝[ｕ，ｈ]（＝Ａｊ）である。
【００８１】
エッジ多項式Ｅに属する要素エッジ多項式ｇ(ｘ)で実区間Ｉに実重複零点を有するものが存在するか否かという問題を考える。この問題は、連立方程式（２６）がｕ≦ｔ≦ｈ、ｘ∈Ｉなる解を持つか否かという問題と同じである。
【数２２】
2007299264.tif 000024
【００８２】
連立方程式（２６）を、ｘをパラメータとし、ｔを変数とする方程式と見る。また、Ｐ(ｘ)＝ｅ(ｘ)ｒ′(ｘ)−ｅ′(ｘ)ｒ(ｘ)、Ｑ(ｘ)／Ｒ(ｘ)＝−ｒ(ｘ)／ｅ(ｘ)とおく。ただし、Ｑ(ｘ)，Ｒ(ｘ)∈Ｑ[ｘ]かつｇｃｄ(Ｑ，Ｒ)＝１とする。なお、Ｑ[ｘ]は、有理係数１変数多項式全体の集合〔変数はｘ〕を表し、ｇｃｄ(・)は最大公約多項式を表す。
【００８３】
このとき、以下のことが云える。
〈１〉
ｘ＝ｃ∈Ｉでｅ(ｃ)＝ｅ′(ｃ)＝０の場合に、連立方程式（２６）が解を持つ必要十分条件は、ｒ(ｃ)＝ｒ′(ｃ)＝０である。連立方程式（２６）が解を持つとき、任意の実数ｔが解となる。換言すると、ｗ(ｘ)＝ｇｃｄ(ｅ(ｘ)，ｒ(ｘ)，ｅ′(ｘ)，ｒ′(ｘ))としたとき、ｗ(ｘ)が実区間Ｉに零点ρを有するならば、必ずｕ≦ｔ≦ｈが成立する。つまり、ｗ(ｘ)が実区間Ｉに零点ρを有するならば、「要素エッジ多項式ｇ(ｘ)∈Ｅであって、その実重複零点が実区間Ｉ上にあるものが存在する」と云える。ｗ(ｘ)が実区間Ｉに零点を有するか否かはSturmの定理に基づくアルゴリズムなどで判定可能である。Sturmの定理については、参考文献２を参照のこと。
（参考文献２）  高木貞治著、「代数学講義（改訂新版）」、共立出版、１９６５．
【００８４】
〈２〉
ｔが区間数の端点ｕまたはｈに固定されている場合。ηをｕまたはｈとすると、ｔ＝ηとした連立方程式（２６）の解ｘがｘ∈Ｉであるかを判定すればよい。換言すると、上記〈１〉においてｗ(ｘ)が実区間Ｉに零点を有しないとき、式（２７）で表される多項式ｗη(ｘ)が実区間Ｉに零点ξηを有するか否かをSturmの定理に基づくアルゴリズムなどで判定すればよい。なお、式（２７）においてｗ(ｘ)を除数としているのは、上記〈１〉を経たことに拠る計算効率化のためである。多項式ｗη(ｘ)が実区間Ｉに零点を有するならば、「要素エッジ多項式ｇ(ｘ)∈Ｅであって、その実重複零点が実区間Ｉ上にあるものが存在する」と云える。
【数２３】
2007299264.tif 000025
【００８５】
〈３〉
ｘ＝ｃ∈Ｉでｅ(ｃ)≠０かつｅ′(ｃ)≠０の場合に、連立方程式（２６）が解を持つ必要十分条件は、Ｐ(ｃ)＝０である。連立方程式（２６）が解を持つとき、解はちょうど一つでｔ＝Ｑ(ｃ)／Ｒ(ｃ)である。
つまるところ、上記〈２〉において多項式ｗｕ(ｘ)および多項式ｗｈ(ｘ)が実区間Ｉに零点を有しないとき、式（２８）で表されるＰ１(ｘ)が実区間Ｉに零点ζを有するか否かをSturmの定理に基づくアルゴリズムなどで判定し、さらにｕ＜Ｑ(ζ)／Ｒ(ζ)＜ｈの成立を判定すればよい。Ｑ(ζ)／Ｒ(ζ)については上記〈２〉を経ることでＱ(ζ)／Ｒ(ζ)＝ηとなることがないから、ｕ＜Ｑ(ζ)／Ｒ(ζ)＜ｈの成立を判定すればよく、これは十分に精度を上げた誤差解析付の近似計算、例えば、区間計算で判定可能である。
なお、式（２８）において多項式ｗｕ(ｘ)、多項式ｗｈ(ｘ)、ｇｃｄ(ｅ(ｘ)，ｅ′(ｘ))を除数としているのは、上記〈１〉および〈２〉を経たことに拠る計算効率化のためである。Ｐ１(ｘ)が実区間Ｉに零点ζを有し、かつ、ｕ＜Ｑ(ζ)／Ｒ(ζ)＜ｈが成立するならば、「要素エッジ多項式ｇ(ｘ)∈Ｅであって、その実重複零点が実区間Ｉ上にあるものが存在する」と云える。Ｐ１(ｘ)が実区間Ｉに零点ζを有さず、あるいは、ｕ＜Ｑ(ζ)／Ｒ(ζ)＜ｈが成立しないならば、「少なくとも、いま与えられているエッジ多項式について、その実重複擬零点が実区間Ｉ上に存在しない」ことが云える。
【数２４】
2007299264.tif 000026
【００８６】
なお、Ｐ(ｘ)が恒等的に０になる場合、連立方程式（２６）は一本の方程式に退化するから、Ｒ(β)≠０を満たす１点β∈Ｉを任意に選択し、この１点βについてｕ＜Ｑ(β)／Ｒ(β)＜ｈを判定すればよい。ｕ＜Ｑ(β)／Ｒ(β)＜ｈが成立するならば、「要素エッジ多項式ｇ(ｘ)∈Ｅであって、その実重複零点が実区間Ｉ上にあるものが存在する」と云える。ｕ＜Ｑ(β)／Ｒ(β)＜ｈが成立しないならば、「少なくとも、いま与えられているエッジ多項式について、その実重複擬零点が実区間Ｉ上に存在しない」と云える。
【００８７】
以上の処理〈１〉〜〈３〉を順次に行っていくことで、要素エッジ多項式ｇ(ｘ)∈Ｅであって、その実重複零点が実区間Ｉ上にあるものが存在するか否かが判定できる。このエッジ多項式判定は、エッジ多項式が有限個であるから有限ステップで終了できる。なお、「要素エッジ多項式ｇ(ｘ)∈Ｅであって、その実重複零点が実区間Ｉ上にあるものが存在する」ことが云えた時点でエッジ多項式判定を終了できる。
【００８８】
ここで、留意しなければならないのは、既述のとおりｇ(ｘ)∈Ｅ⊂Ｆであるところ、実区間多項式Ｆには最多ｄ×２ｄ−１個のエッジ多項式が存在するということである。
【００８９】
従ってより詳細には、（ａ）パラメータｊを定める、（ｂ）ｊ番目の係数を除いて係数が区間数の端点に固定されている、最多２ｄ−１本のエッジ多項式について上記処理〈１〉〜〈３〉を行う、（ｃ）１≦ｊ≦ｄについて（ａ）および（ｂ）の処理を実施する、というアルゴリズムになる（但し、「要素エッジ多項式ｇ(ｘ)であって、その実重複零点が実区間Ｉ上にあるものが存在する」ことが言えた時点でエッジ多項式判定を終了できる。）。
【００９０】
以上のアルゴリズムに基づくエッジ多項式判定の処理フローを一例として図３に示す。
【００９１】
まず、パラメータｊを１に設定する（ステップＳ５００）。
【００９２】
次に、ｊ番目の係数を除いて係数が区間数の端点に固定されている、最大で２ｄ−１個のエッジ多項式Ｅにおいて、未調査（ここで未調査とは、後述のステップＳ５０２〜Ｓ５１４の処理が行われていないことを云う。）のエッジ多項式を１個選択する（ステップＳ５０１）。この選択されたエッジ多項式が上記Ａｊｅｊ(ｘ)＋ｒ(ｘ)において多項式ｒ(ｘ)を１本に固定したものに対応する。また、区間数Ａｊ＝[ｕ，ｈ]とする。
【００９３】
次に、ｗ(ｘ)＝ｇｃｄ(ｅ(ｘ)，ｒ(ｘ)，ｅ′(ｘ)，ｒ′(ｘ))を求める（ステップＳ５０２）。
【００９４】
次に、ｗ(ｘ)が実区間Ｉに零点ρを有するか否かを判定する（ステップＳ５０３）。
【００９５】
ｗ(ｘ)が実区間Ｉに零点ρを有する場合、「要素エッジ多項式ｇ(ｘ)∈Ｅ⊂Ｆ(ｘ)であって、その実重複零点が実区間Ｉ上にあるものが存在する」ことが云える（ステップＳ５１７）。
【００９６】
ｗ(ｘ)が実区間Ｉに零点ρを有さない場合、式（２９）の多項式ｗｕ(ｘ)を求める（ステップＳ５０４）。
【数２５】
2007299264.tif 000027
【００９７】
次に、多項式ｗｕ(ｘ)が実区間Ｉに零点ξｕを有するか否かを判定する（ステップＳ５０５）。
【００９８】
多項式ｗｕ(ｘ)が実区間Ｉに零点ξｕを有する場合、「要素エッジ多項式ｇ(ｘ)∈Ｅ⊂Ｆ(ｘ)であって、その実重複零点が実区間Ｉ上にあるものが存在する」ことが云える（ステップＳ５１７）。
【００９９】
多項式ｗｕ(ｘ)が実区間Ｉに零点ξｕを有さない場合、式（３０）の多項式ｗｈ(ｘ)を求める（ステップＳ５０６）。
【数２６】
2007299264.tif 000028
【０１００】
次に、多項式ｗｈ(ｘ)が実区間Ｉに零点ξｈを有するか否かを判定する（ステップＳ５０７）。
【０１０１】
多項式ｗｈ(ｘ)が実区間Ｉに零点ξｈを有する場合、「要素エッジ多項式ｇ(ｘ)∈Ｅ⊂Ｆ(ｘ)であって、その実重複零点が実区間Ｉ上にあるものが存在する」ことが云える（ステップＳ５１７）。
【０１０２】
多項式ｗｈ(ｘ)が実区間Ｉに零点ξｈを有さない場合、Ｐ(ｘ)＝ｅ(ｘ)ｒ′(ｘ)−ｅ′(ｘ)ｒ(ｘ)、Ｑ(ｘ)／Ｒ(ｘ)＝−ｒ(ｘ)／ｅ(ｘ)を求める。ただし、Ｑ(ｘ)，Ｒ(ｘ)∈Ｑ[ｘ]かつｇｃｄ(Ｑ，Ｒ)＝１とする（ステップＳ５０８）。
【０１０３】
次に、常等的にＰ(ｘ)＝０が成立するか否かを判定する（ステップＳ５０９）。
【０１０４】
常等的にＰ(ｘ)＝０が成立する場合、Ｒ(β)≠０を満たす１点である参照点β∈Ｉを任意に選択する（ステップＳ５１２）。
【０１０５】
続いて、選択された参照点β∈Ｉについて、ｕ＜Ｑ(β)／Ｒ(β)＜ｈが成立するか否かを判定する（ステップＳ５１３）。
【０１０６】
ｕ＜Ｑ(β)／Ｒ(β)＜ｈが成立する場合、「要素エッジ多項式ｇ(ｘ)∈Ｅ⊂Ｆ(ｘ)であって、その実重複零点が実区間Ｉ上にあるものが存在する」ことが云える（ステップＳ５１７）。
【０１０７】
ｕ＜Ｑ(β)／Ｒ(β)＜ｈが成立しない場合、「いま与えられているエッジ多項式について、その実重複擬零点が実区間Ｉ上に存在しない」ことが云えるので、他のエッジ多項式について処理を進めるべくステップＳ５１４への処理に移行する。
【０１０８】
ステップＳ５０９の処理において、常等的にＰ(ｘ)＝０ではない場合、式（３１）で表されるＰ１(ｘ)を求める（ステップＳ５１０）。
【数２７】
2007299264.tif 000029
【０１０９】
続いて、Ｐ１(ｘ)が実区間Ｉに零点ζを有し、かつ、ｕ＜Ｑ(ζ)／Ｒ(ζ)＜ｈが成立するか否かを判定する（ステップＳ５１１）。なお、図面において記号∧は論理積を表す。
【０１１０】
Ｐ１(ｘ)が実区間Ｉに零点ζを有し、かつ、ｕ＜Ｑ(ζ)／Ｒ(ζ)＜ｈが成立するならば、「要素エッジ多項式ｇ(ｘ)∈Ｅ⊂Ｆ(ｘ)であって、その実重複零点が実区間Ｉ上にあるものが存在する」と云える（ステップＳ５１７）。
【０１１１】
Ｐ１(ｘ)が実区間Ｉに零点ζを有さず、あるいは、実区間Ｉに零点ζを有してもｕ＜Ｑ(ζ)／Ｒ(ζ)＜ｈが成立しないならば、「いま与えられているエッジ多項式について、その実重複擬零点が実区間Ｉ上に存在しない」ことが云えるので、他のエッジ多項式について処理を進めるべくステップＳ５１４への処理に移行する。
【０１１２】
ステップＳ５１１またはステップＳ５１３の判定が偽であれば、未調査のエッジ多項式があるか否かを判定する（ステップＳ５１４）。
【０１１３】
未調査のエッジ多項式が存在すれば、ステップＳ５０１〜Ｓ５１３の処理を行う。未調査のエッジ多項式が存在しなければ、ｊ＝ｄであるか否かを判定する（ステップＳ５１５）。
【０１１４】
ｊ≠ｄであれば、ｊに１加えたものを新たなｊとして（ステップＳ５１６）、ステップＳ５０１〜Ｓ５１５の処理を行う。ｊ＝ｄであれば、「要素エッジ多項式ｇ(ｘ)∈Ｆ(ｘ)であって、その実重複零点が実区間Ｉ上にあるものが存在しない」と云える（ステップＳ５１８）。
以上で《エッジ多項式判定》の説明は終わりである。
【０１１５】
次に、《問題２》について。
問題２は、既述のとおり『与えられた実区間多項式Ｆに対し、その実重複擬零点全体の集合ＭＺＲ(Ｆ)を決定せよ』である。
【０１１６】
この問題２に対する解答およびアルゴリズムを説明する。
まず、エッジ多項式判定における処理〈１〉〜〈３〉で説明したことから、下記のことが云える。
【０１１７】
（ア）
点ｃがエッジ多項式Ｅに属する任意の要素エッジ多項式の実重複零点となる必要十分条件は、多項式ｗ(ｃ)＝０となることである。但し、ｗ(ｘ)＝ｇｃｄ(ｅｊ(ｘ)，ｒ(ｘ)，ｅ′ｊ(ｘ)，ｒ′(ｘ))である。
【０１１８】
（イ）
点ｃがエッジ多項式Ｅに属する要素エッジ多項式ｕｊｅｊ(ｘ)＋ｒ(ｘ)に対してのみ実重複零点となる必要十分条件は、多項式ｗｕ(ｃ)＝０となることである〔式（２９）参照。〕。
【０１１９】
（ウ）
点ｃがエッジ多項式Ｅに属する要素エッジ多項式ｈｊｅｊ(ｘ)＋ｒ(ｘ)に対してのみ実重複零点となる必要十分条件は、多項式ｗｈ(ｃ)＝０となることである〔式（３０）参照。〕。
【０１２０】
（エ）
点ｃがちょうど一本の要素エッジ多項式φｅｊ(ｘ)＋ｒ(ｘ)∈Ｅ〔但し、φは開区間(ｕｊ，ｈｊ)に属する。〕の実重複零点となる必要十分条件は、Ｐ1(ｃ)＝０かつＱ(ｃ)／Ｒ(ｃ)∈(ｕｊ，ｈｊ)が成り立つことである〔式（３１）参照。〕。
なお、Ｐ(ｘ)＝ｅj(ｘ)ｒ′(ｘ)−ｅ′j(ｘ)ｒ(ｘ)が恒等的に０ではないのならば、エッジ多項式の実重複擬零点は有限個の点となることに留意すること〔∵Ｐ(ｃ)＝０となることが必要条件なので。〕。
【０１２１】
次に、問題１の解答およびアルゴリズムの説明で明らかになったとおり、『実区間多項式Ｆおよび実区間Ｉについて、実区間Ｉに属する点αで、実区間多項式Ｆの実重複擬零点ではない点が存在するとき、実区間多項式Ｆが実区間Ｉ内に実重複擬零点を有することと、実区間多項式Ｆのエッジ多項式の中に、実区間Ｉ内に実重複擬零点を有するものが存在することとは同値である』・・・（定理１）ことが云える。
【０１２２】
また、『実区間多項式Ｆのｊ番目の係数を除いて係数が区間数の端点に固定されているエッジ多項式Ｅ＝Ａｊｅｊ(ｘ)＋ｒ(ｘ)〔式（１０）参照。但し、Ａｊ＝[ｕｊ，ｈｊ]〕について、その実重複擬零点全体の集合ＭＺＲ(Ｅ)は有限個の閉区間の和集合となる。もし、Ｐ(ｘ)＝ｅj(ｘ)ｒ′(ｘ)−ｅ′j(ｘ)ｒ(ｘ)≠０ならば、ＭＺＲ(Ｅ)は有限集合である』・・・（定理２）ことが云える。
【０１２３】
《定理２の証明》
§１.
まず、最後の「もし、ｅj(ｘ)ｒ′(ｘ)−ｅ′j(ｘ)ｒ(ｘ)≠０ならば、ＭＺＲ(Ｅ)は有限集合である。」については、次のとおりである。
上記（エ）で、尚書きで説明したとおり、Ｐ(ｘ)＝ｅj(ｘ)ｒ′(ｘ)−ｅ′j(ｘ)ｒ(ｘ)が恒等的に０ではないならば、実数ｃがＭＺＲ(Ｅ)に入る必要条件はＰ(ｃ)＝０となることであるところ、Ｐ(ｃ)＝０を満たすｃは有限個しかない。従って、ＭＺＲ(Ｅ)は有限集合である。
【０１２４】
§２．
次に、「ＭＺＲ(Ｅ)は有限個の閉区間の和集合となる。」について。「Ｐ(ｘ)が恒等的に０」ではない場合は、１．で証明済みなので、以下、「Ｐ(ｘ)は恒等的に０」と仮定する。
上記（ア）〜（ウ）を経ることで、多項式ｗ(ｘ)、多項式ｗｕ(ｘ)、多項式ｗｕ(ｘ)の全実零点を求め、この集合をＳＺと表記する。なお、既述のとおりｅｊ(ｘ)を恒等的に０ではないとしたことから、多項式ｗ(ｘ)は恒等的に０にならないが、多項式ｗｕ(ｘ)、多項式ｗｕ(ｘ)は恒等的に０になる場合がありえる〔例えば、ｒ(ｘ)＝０かつｕ＝０の場合などである。〕。この場合は実数全体の集合ＲがＭＺＲ(Ｅ)となるから、ここではこのような場合を除くとする。多項式ｗ(ｘ)、多項式ｗｕ(ｘ)、多項式ｗｕ(ｘ)の全実零点は、Sturmの定理に基づくアルゴリズムなどによって求めることができる。
集合ＳＺにおいては、エッジ多項式Ｅは実重複擬零点を有し、それ以外の点で、もしエッジ多項式Ｅが実重複擬零点を有する場合、式（２６）のｔはただ１つに決まり、しかもｕｊともｈｊとも異なる。
以下、集合ＳＺの要素をα１＜α２＜・・・＜αｍと表記する。
開区間（αｉ，αｉ＋１）の点は、すべてＭＺＲ(Ｅ)に属する、あるいは、１つもＭＺＲ(Ｅ)に属さない、のいずれかになる。換言すれば、開区間（αｉ，αｉ＋１）はＭＺＲ(Ｅ)の部分集合となる、あるいは、ＭＺＲ(Ｅ)とはまったく共通部分を持たない、のいずれかである。
この事実を、叙述して示す。なお、以下では添え字ｊを略する。
【０１２５】
§２．１
『ｅ(ｃ)＝ｅ′(ｃ)＝０かつｃ∈（αｉ，αｉ＋１）ならばＲ(ｃ)＝０』を云う。
もし、ｅ(ｃ)＝ｅ′(ｃ)＝０となる点ｃが開区間（αｉ，αｉ＋１）内にあれば、上記（ア）を経たことから、このような点は集合ＳＺに含まれているから、ｒ(ｃ)≠０またはｒ′(ｃ)≠０である。
ｒ(ｃ)≠０の場合、ｒ(ｘ)はｘ−ｃでは割り切れず、一方、ｅ(ｃ)＝０からｅ(ｘ)はｘ−ｃで割り切れるから、Ｒ(ｘ)はｘ−ｃで割り切れる。つまり、Ｒ(ｃ)＝０である。
ｒ(ｃ)＝０かつｒ′(ｃ)≠０の場合、ｒ(ｘ)はｘ−ｃで割り切れるが、(ｘ−ｃ)２では割り切れない。一方、ｅ(ｃ)＝ｅ′(ｃ)＝０であるから、ｅ(ｘ)は(ｘ−ｃ)２で割り切れるから、Ｒ(ｘ)はｘ−ｃで割り切れる。つまり、この場合もＲ(ｃ)＝０である。
【０１２６】
§２．２
『開区間（αｉ，αｉ＋１）内の１点ｃに対してｕ＜Ｑ(ｃ)／Ｒ(ｃ)＜ｈならば、開区間（αｉ，αｉ＋１）内の任意の１点ｄに対してもｕ＜Ｑ(ｄ)／Ｒ(ｄ)＜ｈが成立する』を云う。
開区間（αｉ，αｉ＋１）内の１点ｃに対してＲ(ｃ)≠０ならば、§２．１で説明したことから、（ｅ(ｃ)，ｅ′(ｃ)）≠（０，０）である。このｃに対して、ｕ＜Ｑ(ｃ)／Ｒ(ｃ)＜ｈならば、任意の点ｄ∈（αｉ，αｉ＋１）に対して、（ｅ(ｄ)，ｅ′(ｄ)）≠（０，０）である。しかも、Ｒ(ｄ)≠０かつｕ＜Ｑ(ｄ)／Ｒ(ｄ)＜ｈとなる。
このことを背理法で示す。
まず、Ｒ(ｘ)の零点が開区間（αｉ，αｉ＋１）内にある場合、そのうち、ｃに一番近いものをｄとする。Ｒ(ｃ)≠０より「Ｒ(ｘ)は恒等的に０」ではないから、区間（ｃ，ｄ）〔あるいは、区間（ｄ，ｃ）〕において、Ｑ(ｘ)／Ｒ(ｘ)はｘの連続関数である。しかも、Ｑ(ｘ)およびＲ(ｘ)は互いに素に取ってあるから、Ｑ(ｄ)≠０である。よって、ｘがｄに近づくとき、Ｑ(ｘ)／Ｒ(ｘ)の絶対値はいくらでも大きくなる。従って、中間値の定理から、Ｑ(ｘ)／Ｒ(ｘ)がｕまたはｈに等しくなる点が区間（ｃ，ｄ）〔あるいは、区間（ｄ，ｃ）〕に、即ち、開区間（αｉ，αｉ＋１）の中に存在することになる。これは、開区間（αｉ，αｉ＋１）の取り方に矛盾する〔このような点は、すでに上記（ア）〜（ウ）の処理で集合ＳＺに取り込み済みで、開区間（αｉ，αｉ＋１）の中には存在しない。）。
次に、Ｒ(ｘ)の零点が開区間（αｉ，αｉ＋１）内に無い場合は、Ｑ(ｘ)／Ｒ(ｘ)がｕ以下あるいはｈ以上となる点ｄが開区間（αｉ，αｉ＋１）内に存在したと仮定する。まず、開区間（αｉ，αｉ＋１）の取り方から、Ｑ(ｘ)／Ｒ(ｘ)がｕあるいはｈとなる点は開区間（αｉ，αｉ＋１）内には存在しないから、Ｑ(ｄ)／Ｒ(ｄ)がｕより小さいかあるいはｈよりも大きいかのどちらかである。よって、区間（ｃ，ｄ）〔あるいは、区間（ｄ，ｃ）〕に中間値の定理を適用すれば、Ｑ(ｘ)／Ｒ(ｘ)がｕまたはｈに等しくなる点が区間（ｃ，ｄ）〔あるいは、区間（ｄ，ｃ）〕に、即ち、開区間（αｉ，αｉ＋１）の中に存在することになり、開区間（αｉ，αｉ＋１）の取り方に矛盾する。
【０１２７】
§２．３
『開区間（αｉ，αｉ＋１）内の１点ｃに対してＱ(ｃ)／Ｒ(ｃ)＜ｕあるいはｈ＜Ｑ(ｃ)／Ｒ(ｃ)ならば、開区間（αｉ，αｉ＋１）内にはｕ≦Ｑ(ｄ)／Ｒ(ｄ)≦ｈとなる点は存在しない』を云う。
ｕ≦Ｑ(ｄ)／Ｒ(ｄ)≦ｈとなる点ｄが開区間（αｉ，αｉ＋１）内に存在したと仮定する。もし、開区間（αｉ，αｉ＋１）内にＲ(ｘ)の零点が存在しないならば、§２．２と同様な議論で、Ｑ(ｘ)／Ｒ(ｘ)がｕまたはｈに等しくなる点は、開区間（αｉ，αｉ＋１）内には存在しないから、Ｑ(ｄ)／Ｒ(ｄ)がｕより小さいかあるいはｈよりも大きいかのどちらかである。区間（ｃ，ｄ）〔あるいは、区間（ｄ，ｃ）〕に中間値の定理を適用すれば、Ｑ(ｘ)／Ｒ(ｘ)がｕまたはｈに等しくなる点が区間（ｃ，ｄ）〔あるいは、区間（ｄ，ｃ）〕に、即ち、開区間（αｉ，αｉ＋１）の中に存在することになり、開区間（αｉ，αｉ＋１）の取り方に矛盾する。
もし、開区間（αｉ，αｉ＋１）内にＲ(ｘ)の零点が存在したならば、そのうちｄに一番近いものｄ′を取れば、§２．２と同じ議論によって、やはりＱ(ｘ)／Ｒ(ｘ)がｕまたはｈに等しくなる点が区間（ｃ，ｄ）〔あるいは、区間（ｄ，ｃ）〕に、即ち、開区間（αｉ，αｉ＋１）の中に存在することになり、開区間（αｉ，αｉ＋１）の取り方に矛盾する。
【０１２８】
§２．４
以上から、開区間（αｉ，αｉ＋１）はＭＺＲ(Ｅ)の部分集合となる、あるいは、ＭＺＲ(Ｅ)とはまったく共通部分を持たない、のいずれかが示せた。
なお、開区間（αｉ，αｉ＋１）で任意に選択された１点βについて、ｕ＜Ｑ(β)／Ｒ(β)＜ｈの成立を調べることで、上記いずれが成立しているかを判定できる。
以上で《定理２の証明》は終わりである。
【０１２９】
さて、定理１および定理２から、次のことが云える。
即ち、『実区間多項式Ｆと、実区間Ｊに対し、実区間多項式Ｆの全てのエッジ多項式は実区間Ｊ内に実重複擬零点を有さないと仮定する。このとき、実区間Ｊの閉包の全ての点が実区間多項式Ｆの実重複擬零点であるか、あるいは、実区間Ｊのどの点も実区間多項式Ｆの実重複擬零点ではないか、のどちらかが成り立つ。』・・・（定理３）ことが云える。
【０１３０】
《定理３の証明》
実区間Ｊに属する２点α、βについて，αは実区間多項式Ｆの実重複擬零点だが、βは実重複擬零点でないと仮定する。すると、定理１から、実区間多項式Ｆのエッジ多項式Ｅの中に、ＭＺＲ(Ｅ)∩Ｊは空集合ではないものが存在する。これは、「実区間多項式Ｆの全てのエッジ多項式は実区間Ｊ内に実重複擬零点を持たない」という仮定に矛盾する。つまり、（１）実区間ＪはＭＺＲ(Ｆ)の部分集合である、（２）実区間ＪとＭＺＲ(Ｆ)の共通部分は空集合である、のいずれかとなる、（２）の場合および（１）で実区間Ｊが閉区間のときにはこれで証明できたことになる。
従って、（１）で実区間Ｊが閉区間ではないとき、つまり、ａ＜ｂであって、Ｊ＝（ａ，ｂ）、［ａ，ｂ）、（ａ，ｂ]の場合を考える。どれでも証明は同じなので、端点ａが実区間Ｊに含まれない場合を示す。このとき、Ｋ＝｛ａ｝∪Ｊ、つまり、Ｊ＝（ａ，ｂ）のときＫ＝［ａ，ｂ）、Ｊ＝（ａ，ｂ]のときＫ＝［ａ，ｂ]とする。定理１をＫに対して適用する。もし端点ａが実区間多項式Ｆの実重複擬零点ではないとすると、実区間多項式Ｆのエッジ多項式Ｅであって、Ｋに実重複擬零点を持つものが存在することになる。ところが、端点ａは実区間多項式Ｆの実重複擬零点ではないので、当然、エッジ多項式の実重複擬零点でもない。よって、実区間Ｊに実重複擬零点を持つものが存在することになる。これは上記仮定に矛盾する。
以上で《定理３の証明》は終わりである。
【０１３１】
そうすると、問題２に対する大まかな解答は、次のようになる。
まず、実区間多項式Ｆの全てのエッジ多項式について、その実重複擬零点全体の集合Ｚを求める〔集合Ｚ決定処理〕（図４のステップＳ２００参照。）。集合Ｚは、有限個の閉区間の和集合ＭＺＲ(Ｅ)の和集合をとったものとして求めることができる。即ちＺ＝∪ＭＺＲ(Ｅ)〔エッジ多項式Ｅは、実区間多項式Ｆの全てのエッジ多項式を渡る。〕である〔記号∪は和集合を表す。〕。
次いで、集合Ｚの補集合〔但し、全体集合は実数全体の集合Ｒとする。〕の各実区間について〔集合Ｚの補集合は、有限個の開区間の和集合となるから、各開区間をＪとする。〕、実区間Ｊ上の任意の１点γを選択し、この点γを実重複零点とする多項式が実区間多項式Ｆに存在するか否かを判定する〔この判定は既述の凸包判定を用いて可能である。〕。これが存在する場合には、点γを含む実区間Ｊと集合Ｚとの和集合をとったものを新たな集合Ｚに置き換える〔ＭＺＲ(Ｆ)決定処理〕（図４のステップＳ２０１参照。）。なお、集合Ｚが実数全体の集合Ｒの場合には、集合Ｒが集合ＭＺＲ(Ｆ)となる。
この結果、得られた集合ＺがＭＺＲ(Ｆ)である。
【０１３２】
《集合Ｚ決定処理》
ここでは、以上の定理等に基づく集合Ｚ＝∪ＭＺＲ(Ｅ)を求めるの処理フローを一例として図５および図６に示す。なお、図３および図３に係わる説明も参照のこと。
なお、集合Ｚの初期値および集合ＭＺＲ(Ｅ)の各初期値は空集合とする。
【０１３３】
まず、パラメータｊを１に設定する（ステップＳ６００）。
【０１３４】
次に、ｊ番目の係数を除いて係数が区間数の端点に固定されている、最大で２ｄ−１個のエッジ多項式Ｅにおいて、未調査（ここで未調査とは、後述のステップＳ６０２〜Ｓ６３１の処理が行われていないことを云う。）のエッジ多項式を１個選択する（ステップＳ６０１）。この選択されたエッジ多項式が上記Ａｊｅｊ(ｘ)＋ｒ(ｘ)において多項式ｒ(ｘ)を１本に固定したものに対応する。また、区間数Ａｊ＝[ｕｊ，ｈｊ]とする。
【０１３５】
次に、多項式ｗ(ｘ)＝ｇｃｄ(ｅｊ(ｘ)，ｒｊ(ｘ)，ｅ′ｊ(ｘ)，ｒ′ｊ(ｘ))を求める（ステップＳ６０２）。
【０１３６】
次に、ｗ(ｘ)の実零点全体の集合ＳＺを求める（ステップＳ６０３）。
【０１３７】
続いて、式（３２）の多項式ｗｕ(ｘ)を求める（ステップＳ６０４）。
【数２８】
2007299264.tif 000030
【０１３８】
次に、常等的にｗｕ(ｘ)＝０が成立するか否かを判定する（ステップＳ６０５）。
【０１３９】
常等的にｗｕ(ｘ)＝０が成立する場合、集合Ｚ＝Ｒ（実数全体の集合）として集合Ｚ決定処理を終了する（ステップＳ６０８）。
【０１４０】
常等的にｗｕ(ｘ)＝０が成立しない場合、式（３３）の多項式ｗｈ(ｘ)を求める（ステップＳ６０６）。
【数２９】
2007299264.tif 000031
【０１４１】
次に、常等的にｗｈ(ｘ)＝０が成立するか否かを判定する（ステップＳ６０７）。
【０１４２】
常等的にｗｈ(ｘ)＝０が成立する場合、集合Ｚ＝Ｒ（実数全体の集合）として集合Ｚ決定処理を終了する（ステップＳ６０８）。
【０１４３】
常等的にｗｈ(ｘ)＝０が成立しない場合、多項式ｗｕ(ｘ)および多項式ｗｈ(ｘ)それぞれの全実零点の集合ＺＲ(ｗｕ)および集合ＺＲ(ｗｈ)を求める（ステップＳ６０９）。
【０１４４】
続いて、集合ＳＺ、集合ＺＲ(ｗｕ)および集合ＺＲ(ｗｈ)の和集合をとり、この和集合を新たな集合ＳＺとして置き換える。そして、この集合ＳＺの要素をα１＜α２＜・・・＜αｍとする（ステップＳ６１０）。
【０１４５】
続いて、Ｐ(ｘ)＝ｅｊ(ｘ)ｒ′(ｘ)−ｅ′ｊ(ｘ)ｒ(ｘ)、Ｑ(ｘ)／Ｒ(ｘ)＝−ｒ(ｘ)／ｅｊ(ｘ)を求める。ただし、Ｑ(ｘ)，Ｒ(ｘ)∈Ｑ[ｘ]かつｇｃｄ(Ｑ，Ｒ)＝１とする（ステップＳ６１１）。
【０１４６】
次に、常等的にＰ(ｘ)＝０が成立するか否かを判定する（ステップＳ６１２）。
【０１４７】
常等的にＰ(ｘ)＝０が成立する場合、参照点βｉを、Ｒ(βｉ)≠０かつβ１＜α１＜β２＜α２＜…＜αｍ＜βｍ＋１を満たすように選択する（ステップＳ６１８）。但し、パラメータｉ＝１，２，・・・，ｍ＋１とする。ｍ＝０の場合は、参照点β１は任意に選択できる。
【０１４８】
続いて、ｉ＝１かつｍ＝０かつｕｊ＜Ｑ(βｉ)／Ｒ(βｉ)＜ｈｊの成立を判定する（ステップＳ６１９）。
【０１４９】
ｉ＝１かつｍ＝０かつｕｊ＜Ｑ(βｉ)／Ｒ(βｉ)＜ｈｊが成立するならば、集合Ｚ＝Ｒ（実数全体の集合）として集合Ｚ決定処理を終了する（ステップＳ６２０）。
【０１５０】
ｉ＝１かつｍ＝０かつｕｊ＜Ｑ(βｉ)／Ｒ(βｉ)＜ｈｊが成立しない場合、ｉ＝１かつｍ≧１かつｕｊ＜Ｑ(βｉ)／Ｒ(βｉ)＜ｈｊの成立を判定する（ステップＳ６２１）。
【０１５１】
ｉ＝１かつｍ≧１かつｕｊ＜Ｑ(βｉ)／Ｒ(βｉ)＜ｈｊが成立する場合、集合ＳＺおよび（−∞，α１]の和集合をとり、この和集合を新たな集合ＳＺとして置き換えて（ステップＳ６２２）、続いてステップＳ６２３の処理を行う。
また、ｉ＝１かつｍ≧１かつｕｊ＜Ｑ(βｉ)／Ｒ(βｉ)＜ｈｊが成立しない場合は、続いてステップＳ６２３の処理を行う。
【０１５２】
続いて、パラメータｉを２に設定する（ステップＳ６２３）。
【０１５３】
次に、ｕｊ＜Ｑ(βｉ)／Ｒ(βｉ)＜ｈｊの成立を判定する（ステップＳ６２４）。
【０１５４】
ｕｊ＜Ｑ(βｉ)／Ｒ(βｉ)＜ｈｊが成立する場合、集合ＳＺおよび閉区間[αｉ−１，αｉ]の和集合をとり、この和集合を新たな集合ＳＺとして置き換えて（ステップＳ６２５）、続いてステップＳ６２６の処理を行う。ｕｊ＜Ｑ(βｉ)／Ｒ(βｉ)＜ｈｊが成立しない場合、ステップＳ６２７の処理を行う。
【０１５５】
ステップＳ６２５の処理に続いて、ｉ＝ｍ＋１の成立を判定する（ステップＳ６２６）。ｉ＝ｍ＋１が成立する場合、続いてステップＳ６２８の処理を行う。ｉ＝ｍ＋１が成立しない場合、続いてステップＳ６２７の処理を行う。
【０１５６】
ステップＳ６２４の処理でｕｊ＜Ｑ(βｉ)／Ｒ(βｉ)＜ｈｊが成立しない場合、あるいは、ステップＳ６２６の処理でｉ＝ｍ＋１が成立しない場合、ｉに１加えたものを新たなｉとして（ステップＳ６２７）、ステップＳ６２４〜Ｓ６２６の処理を行う。
【０１５７】
ステップＳ６２６の処理でｉ＝ｍ＋１が成立した場合、ｉ＝ｍ＋１かつｕｊ＜Ｑ(βｉ)／Ｒ(βｉ)＜ｈｊの成立を判定する（ステップＳ６２８）。
【０１５８】
ｉ＝ｍ＋１かつｕｊ＜Ｑ(βｉ)／Ｒ(βｉ)＜ｈｊが成立した場合、集合ＳＺおよび閉区間[αｍ，∞）の和集合をとり、この和集合を新たな集合ＳＺとして置き換えて（ステップＳ６２９）、続いてステップＳ６３０の処理を行う。ｉ＝ｍ＋１かつｕｊ＜Ｑ(βｉ)／Ｒ(βｉ)＜ｈｊが成立しない場合、ステップＳ６３０の処理を行う。
【０１５９】
ステップＳ６１２の処理で、常等的にＰ(ｘ)＝０が成立しない場合、式（３４）で表されるＰ１(ｘ)を求め、このＰ１(ｘ)の全実零点集合｛ζ｝を求める（ステップＳ６１３）。
【数３０】
2007299264.tif 000032
【０１６０】
続いて、集合｛ζ｝の中から、未選択（ここで未選択とは、後述のステップＳ６１５〜Ｓ６１７の処理が行われていないことを云う。）の零点を１つ選択する（ステップＳ６１４）。この選択された零点をζＳと表記する。
【０１６１】
選択された零点ζＳについて、ｕｊ＜Ｑ(ζＳ)／Ｒ(ζＳ)＜ｈｊの成立を判定する（ステップＳ６１５）。
【０１６２】
ｕｊ＜Ｑ(ζＳ)／Ｒ(ζＳ)＜ｈｊが成立する場合、集合ＳＺおよび｛ζＳ｝との和集合をとり、この和集合を新たな集合ＳＺとして置き換えて（ステップＳ６１６）、続いてステップＳ６１７の処理を行う。ｕｊ＜Ｑ(ζＳ)／Ｒ(ζＳ)＜ｈｊが成立しない場合、ステップＳ６１７の処理を行う。
【０１６３】
未選択の零点ζＳが存在すれば、ステップＳ６１４〜Ｓ６１６の処理を行う。未選択の零点ζＳが存在しなければ、ステップＳ６３０の処理を行う（ステップＳ６１７）。
【０１６４】
ステップＳ６１７、ステップＳ６２８、ステップＳ６２９の処理に続いて、この段階で得られている集合ＳＺおよび集合ＭＺＲ(Ｅ)との和集合をとり、この和集合を新たな集合ＭＺＲ(Ｅ)に置き換える（ステップＳ６３０）。
【０１６５】
続いて、未調査のエッジ多項式があるか否かを判定する（ステップＳ６３１）。未調査のエッジ多項式が存在すれば、ステップＳ６０１〜Ｓ６３０の処理を行う。
【０１６６】
未調査のエッジ多項式が存在しなければ、集合Ｚおよび集合ＭＺＲ(Ｅ)との和集合をとり、この和集合を新たな集合Ｚとして置き換える（ステップＳ６３２）。
【０１６７】
続いて、ｊ＝ｄであるか否かを判定する（ステップＳ６３３）。
【０１６８】
ｊ≠ｄであれば、ｊに１加えたものを新たなｊとして（ステップＳ６３４）、ステップＳ６０１〜Ｓ６３３の処理を行う。ｊ＝ｄであれば、集合Ｚ決定処理を終了する。この段階で得られた集合Ｚが所望の集合である。
以上で《集合Ｚ決定処理》の説明は終わりである。
【０１６９】
《ＭＺＲ(Ｆ)決定処理》
続いて、以上のアルゴリズムに基づく集合ＭＺＲ(Ｆ)を求めるの処理フローを一例として図７に示す。
なお、集合Ｚの初期値は集合Ｚ決定処理で得られた集合であることに留意すること。
【０１７０】
まず、集合Ｚが実数全体の集合Ｒに等しいか否かを判定する（ステップＳ７００）。
【０１７１】
集合Ｚが実数全体の集合Ｒに等しい場合、ＭＺＲ(Ｆ)決定処理を終了する。集合ＭＺＲ(Ｆ)は、この段階で得られた集合Ｚ、つまり集合Ｒとなる。
【０１７２】
集合Ｚが実数全体の集合Ｒに等しくない場合、集合Ｚを式（３５）のように表現する（ステップＳ７０１）。これは集合Ｚ決定処理で得られた集合Ｚを区間ごとの和集合として書き表したものである。但し、（β０＜）α１≦β１＜α２≦・・・≦βｍ（＜αｍ＋１）とする。また、式（３５）のｍは、上記で用いた記号ｍの意味とは異なることに留意すること。
【数３１】
2007299264.tif 000033
【０１７３】
次に、（β０＜）γ１＜α１≦β１＜γ２＜α２≦・・・≦βｍ＜γm+1（＜αm+1）を満たすｍ＋１個の参照点γｉ∈Ｒ〔ｉ＝１，２，・・・，ｍ＋１〕をとる（ステップＳ７０２）。但し、ｍ＝０のときは、γ１をどこにとってもよい。
【０１７４】
続いて、パラメータｉを１に設定する（ステップＳ７０３）。
【０１７５】
続いて、ｉ＝１かつｍ＝０かつ『γｉが実区間多項式Ｆの実重複擬零点である』の成立を判定する（ステップＳ７０４）。『γｉが実区間多項式Ｆの実重複擬零点である』か否かは既述の凸包判定で可能である〔以下同様。〕。
【０１７６】
ｉ＝１かつｍ＝０かつ『γｉが実区間多項式Ｆの実重複擬零点である』が成立するならば、集合Ｚ＝Ｒ（実数全体の集合）としてＭＺＲ(Ｆ)決定処理を終了する（ステップＳ７０５）。集合ＭＺＲ(Ｆ)は、この段階で得られた集合Ｚ、つまり集合Ｒとなる。
【０１７７】
ｉ＝１かつｍ＝０かつ『γｉが実区間多項式Ｆの実重複擬零点である』が成立しない場合、ｉ＝１かつｍ≧１かつ『γｉが実区間多項式Ｆの実重複擬零点である』の成立を判定する（ステップＳ７０６）。
【０１７８】
ｉ＝１かつｍ≧１かつ『γｉが実区間多項式Ｆの実重複擬零点である』が成立する場合、集合Ｚおよび（−∞，β１]の和集合をとり、この和集合を新たな集合Ｚとして置き換えて（ステップＳ７０７）、続いてステップＳ７０８の処理を行う。
また、ｉ＝１かつｍ≧１かつ『γｉが実区間多項式Ｆの実重複擬零点である』が成立しない場合は、続いてステップＳ７０８の処理を行う。
【０１７９】
続いて、パラメータｉを２に設定する（ステップＳ７０８）。
【０１８０】
次に、『γｉが実区間多項式Ｆの実重複擬零点である』の成立を判定する（ステップＳ７０９）。
【０１８１】
『γｉが実区間多項式Ｆの実重複擬零点である』が成立する場合、集合Ｚおよび閉区間[βｉ−１，αｉ]の和集合をとり、この和集合を新たな集合Ｚとして置き換えて（ステップＳ７１０）、続いてステップＳ７１１の処理を行う。『γｉが実区間多項式Ｆの実重複擬零点である』が成立しない場合、ステップＳ７１２の処理を行う。
【０１８２】
ステップＳ７１０の処理に続いて、ｉ＝ｍ＋１の成立を判定する（ステップＳ７１１）。ｉ＝ｍ＋１が成立する場合、続いてステップＳ７１３の処理を行う。ｉ＝ｍ＋１が成立しない場合、続いてステップＳ７１２の処理を行う。
【０１８３】
ステップＳ７０９の処理で『γｉが実区間多項式Ｆの実重複擬零点である』が成立しない場合、あるいは、ステップＳ７１１の処理でｉ＝ｍ＋１が成立しない場合、ｉに１加えたものを新たなｉとして（ステップＳ７１２）、ステップＳ７０９〜Ｓ７１１の処理を行う。
【０１８４】
ステップＳ７１１の処理でｉ＝ｍ＋１が成立した場合、ｉ＝ｍ＋１かつ『γｉが実区間多項式Ｆの実重複擬零点である』の成立を判定する（ステップＳ７１３）。
【０１８５】
ｉ＝ｍ＋１かつ『γｉが実区間多項式Ｆの実重複擬零点である』が成立した場合、集合Ｚおよび閉区間[βｍ，∞）の和集合をとり、この和集合を新たな集合Ｚとして置き換えて（ステップＳ７１４）、ＭＺＲ(Ｆ)決定処理を終了する。集合ＭＺＲ(Ｆ)は、この段階で得られた集合Ｚである。ｉ＝ｍ＋１かつ『γｉが実区間多項式Ｆの実重複擬零点である』が成立しない場合、ＭＺＲ(Ｆ)決定処理を終了する。集合ＭＺＲ(Ｆ)は、この段階で得られた集合Ｚである。
以上で《ＭＺＲ(Ｆ)決定処理》の説明は終わりである。
【０１８６】
《Sturmの定理に基づくアルゴリズム》
Sturmの定理に基づくアルゴリズムの適用について概説する。
係数が確定した実係数多項式Ｈ(ｓ)について、多項式の列Ｈ０(ｓ)、Ｈ１(ｓ)、Ｈ２(ｓ)、・・・、Ｈｒ(ｓ)を生成する。但し、これらの多項式の列は、次の規則に従って生成する。Ｈ０(ｓ)＝Ｈ(ｓ)、Ｈ１(ｓ)＝ｄＨ(ｓ)／ｄｓ〔ｓに関する１階微分である。ライプニッツ記法〕、Ｈｋ−１(ｓ)をＨｋ(ｓ)で割った剰余多項式を（符号を変えて）−Ｈｋ＋１(ｓ)とする。つまり、商の多項式をＱｋ(ｓ)と表すと、Ｈｋ−１(ｓ)＝Ｈｋ(ｓ)Ｑｋ(ｓ)−Ｈｋ＋１(ｓ)の関係が成立する。また、Ｈｒ−１(ｓ)は、Ｈｒ(ｓ)で割り切れる。つまり、商の多項式をＱｒ(ｓ)と表すと、Ｈｒ−１(ｓ)＝Ｈｒ(ｓ)Ｑｒ(ｓ)の関係が成立する。このとき、Ｓ＝[ａ，ｂ]において、Ｈ０(ａ)、Ｈ１(ａ)、Ｈ２(ａ)、・・・、Ｈｒ(ａ)における正負の符号変化の回数をｗ(ａ)で表し、Ｈ０(ｂ)、Ｈ１(ｂ)、Ｈ２(ｂ)、・・・、Ｈｒ(ｂ)における正負の符号変化の回数をｗ(ｂ)で表すとすると、区間Ｓ＝[ａ，ｂ]におけるＨ(ｓ)の零点の個数は、ｗ(ａ)−ｗ(ｂ)である。なお、ここでは、区間Ｓ＝[ａ，ｂ]のａ、ｂは共にＨ(ｓ)の零点ではないとする（零点であれば、個数を表す式が少し変わるが、本発明においては本質的な部分ではないので略する。）。ｗ(ａ)−ｗ(ｂ)＝０であれば零点が存在しないことが判明し、ｗ(ａ)−ｗ(ｂ)≠０であれば零点が存在することが判明する。区間Ｓ＝[ａ，ｂ]を十分に狭くとることで実零点の所在を決定できる。
以上で《Sturmの定理に基づくアルゴリズム》の概説は終わりである。
【０１８７】
[第１実施形態]
以下に、本発明の第１実施形態を説明する。第１実施形態は、実区間多項式Ｆの実重複擬零点が実区間Ｉに存在するか否かに係わる。
図８は、本実施形態に係わる実重複擬零点位置判定装置（１）のハードウェア構成を例示した構成ブロック図である。
【０１８８】
図８に例示するように、実重複擬零点位置判定装置（１）は、キーボードなどが接続可能な入力部（１１）、液晶ディスプレイなどが接続可能な出力部（１２）、実重複擬零点位置判定装置（１）外部に通信可能な通信装置（例えば通信ケーブル）が接続可能な通信部（１３）、ＣＰＵ（Central Processing Unit）（１４）〔キャッシュメモリやレジスタなどを備えていてもよい。〕、メモリであるＲＡＭ（１５）、ＲＯＭ（１６）やハードディスクである外部記憶装置（１７）並びにこれらの入力部（１１）、出力部（１２）、通信部（１３）、ＣＰＵ（１４）、ＲＡＭ（１５）、ＲＯＭ（１６）、外部記憶装置（１７）間のデータのやり取りが可能なように接続するバス（１８）を有している。また必要に応じて、実重複擬零点位置判定装置（１）に、ＣＤ−ＲＯＭなどの記憶媒体を読み書きできる装置（ドライブ）などを設けるとしてもよい。このようなハードウェア資源を備えた物理的実体としては、汎用コンピュータなどがある。
【０１８９】
実重複擬零点位置判定装置（１）の外部記憶装置（１７）には、実区間多項式の実重複擬零点の位置判定をするのに必要となるプログラムおよびこのプログラムの処理において必要となるデータなどが保存記憶されている。また、これらのプログラムの処理によって得られるデータなどは、ＲＡＭや外部記憶装置などに適宜に保存記憶される。以下、演算結果やその格納領域のアドレスなどを記憶するＲＡＭ（１５）やレジスタなどの装置を単に「メモリ」と呼ぶことにする。
【０１９０】
より具体的には、実重複擬零点位置判定装置（１）の外部記憶装置（１７）〔あるいはＲＯＭなど〕には、実区間Ｉ上で任意に１点αを選択し、この点αを実重複零点とする多項式が実区間多項式Ｆに存在するか否かを判定するための選択点多項式判定プログラム、実区間Ｉ上に実重複零点を有する要素エッジ多項式が実区間多項式Ｆに存在するか否かを判定するためのエッジ多項式判定プログラムおよびこれらのプログラムの処理において必要となるデータなどが保存記憶されている。その他、これらのプログラムに基づく処理を制御するための制御プログラムも適宜に保存記憶しておく。
【０１９１】
実重複擬零点位置判定装置（１）では、外部記憶装置（１７）〔あるいはＲＯＭなど〕に記憶された各プログラムとこの各プログラムの処理に必要なデータが必要に応じてメモリ（２０）に読み込まれて、適宜にＣＰＵ（１４）で解釈実行・処理される。その結果、ＣＰＵ（１４）が所定の機能（選択点多項式判定部、エッジ多項式判定部、制御部）を実現する。
【０１９２】
図１、図２、図３、図８、図９を参照して、本実施形態における実区間多項式の実重複擬零点の位置判定処理について説明する。
【０１９３】
実重複擬零点位置判定装置（１）の外部記憶装置（１７）には、予め、実区間多項式Ｆ(ｘ)、実区間Ｉなどが予め保存記憶されているとする。
【０１９４】
この実施形態では、説明の便宜からより具体的に、実区間多項式Ｆ(ｘ)の各項の区間数Ａｊ＝［ｕｊ，ｈｊ］≡｛（ｈｊ−ｕｊ）ｔｊ＋ｕｊ｝〔但し、０≦ｔｊ≦１、ｊ＝０，１，２，・・・，ｄとする。〕、実区間Ｉ＝［ａ，ｂ］がデータとして、予め、実重複擬零点位置判定装置（１）の外部記憶装置（１７）に保存記憶されているとする。なお、実区間Ｉは閉区間、左閉右開区間、左開右閉区間、開区間のいずれでもよい。
【０１９５】
これらの情報などは、予め実重複擬零点位置判定装置（１）の外部記憶装置（１７）に保存記憶しておくのではなく、例えば、入力部（１１）から入力されるとしてもよいし、あるいは、これらの情報などを格納した記録媒体からドライブを駆動して読み込むようにしてもよく、適宜に変更可能である。
【０１９６】
また、これらの情報などに限定する趣旨のものではない。例えば、実区間多項式Ｆ(ｘ)の区間数ではなく実区間多項式Ｆ(ｘ)そのものを実重複擬零点位置判定装置（１）の外部記憶装置（１７）に保存記憶しておくとしてもよい（実区間多項式に属する多項式それぞれを記憶するのではないことに留意する。）。
【０１９７】
なお、本発明の細部においては、数値計算処理のみならず有理式や区間多項式などの数式処理も必要となるが、数値計算処理および数式処理自体は、公知技術と同様にして達成されるので、その演算処理方法などの詳細な説明は省略する（この点の技術水準を示す数式処理が可能なソフトウェアとしては、例えば、Risa/Asir、Maple（登録商標）、MATHEMATICA（登録商標第2312968号）、Gnuplotなどが挙げられる。Risa/Asirについては、例えばインターネット〈URL:http://hpc.cs.ehime-u.ac.jp/risa/〉［平成１８年４月２５日検索］を参照のこと。Mapleについては、例えばインターネット〈URL:http://www.cybernet.co.jp/maple/〉［平成１８年４月２５日検索］を参照のこと。Gnuplotについては、例えばインターネット〈URL: http://www.gnuplot.info/〉［平成１８年４月２５日検索］を参照のこと。）。
【０１９８】
まず、実重複擬零点位置判定装置（１）の制御部（１９０）は、外部記憶装置（１７）から全ての区間数Ａｊ＝｛（ｈｊ−ｕｊ）ｔｊ＋ｕｊ｝、実区間Ｉ＝［ａ，ｂ］を読み込み、それぞれをメモリ（２０）の所定の格納領域に格納しておく。以後、「メモリから○○を読み込む」旨の説明をした場合は、「メモリにおいて○○が格納されている所定の格納領域から○○を読み込む」ことを意味するとする。
【０１９９】
選択点多項式判定部（１４１）は、メモリ（２０）から、全ての区間数Ａｊ＝｛（ｈｊ−ｕｊ）ｔｊ＋ｕｊ｝、実区間Ｉ＝［ａ，ｂ］を読み込み、《凸包判定》で説明したアルゴリズムに従って、実区間Ｉ上で任意に選択された１点αについて、この点αを実重複擬零点とする多項式が実区間多項式Ｆ(ｘ)に存在するか否かを判定する（図１のステップＳ１００）。
概略を示すと、選択点多項式判定部（１４１）は、メモリ（２０）と協働しながら、次のような動作をする。つまり、実区間Ｉ上で任意に１点αを選択し、この点αを実区間多項式Ｆ(ｘ)および実区間多項式Ｆ(ｘ)を１階微分したものに代入して式（２２）の如く式変形を行う。式（２２）の左辺で表される点全体の凸包に式（２２）の右辺の点が入るかを判定し、その判定結果を得る。判定結果は、「点αを実重複零点とする多項式が実区間多項式Ｆ(ｘ)に存在する」あるいは「点αを実重複零点とする多項式が実区間多項式Ｆ(ｘ)に存在しない」を表す情報Θである。
【０２００】
制御部（１９０）は、この判定結果情報Θが、点αを実重複零点とする多項式が実区間多項式Ｆ(ｘ)に存在するというものである場合には（図２のステップＳ４１２参照。）、「実区間Ｉ内に実区間多項式Ｆの実重複擬零点が存在する」ことを表す情報θ（例えばこの場合は、θ＝１とする。）をメモリ（２０）の所定の格納領域に格納する（図１のステップＳ１０３）。なぜなら、この場合、この点αを実重複零点とする実区間多項式Ｆ(ｘ)に属する多項式が存在することは、まさに実区間多項式Ｆ(ｘ)が実区間Ｉ上に実重複擬零点を有することと同じであるからである。
【０２０１】
制御部（１９０）は、判定結果情報Θが、点αを実重複零点とする多項式が実区間多項式Ｆ(ｘ)に存在しないというものである場合には（図２のステップＳ４１１参照。）、ステップＳ１０１の処理を実行するように制御する。
【０２０２】
次に、エッジ多項式判定部（１４２）は、メモリ（２０）から、全ての区間数Ａｊ＝｛（ｈｊ−ｕｊ）ｔｊ＋ｕｊ｝、実区間Ｉ＝［ａ，ｂ］を読み込み、《エッジ多項式判定》で説明したアルゴリズムに従って、実区間Ｉ上に実重複零点を有する要素エッジ多項式が実区間多項式Ｆ(ｘ)に存在するか否かを判定する（図１のステップＳ１０１）。
概略を示すと、エッジ多項式判定部（１４２）は、メモリ（２０）と協働しながら、区間数Ａｊに対するエッジ多項式について次のような動作をする。つまり、多項式ｗ(ｘ)、多項式ｗｕ(ｘ)、多項式ｗｕ(ｘ)について各実零点が、実区間Ｉに属するか否かを判定し、その判定結果を得る。判定結果は、「実区間Ｉ上に実重複零点を有する要素エッジ多項式が存在する」あるいは「実区間Ｉ上に実重複零点を有する要素エッジ多項式が存在しない」を表す情報Γである。判定結果情報Γが「実区間Ｉ上に実重複零点を有する要素エッジ多項式が存在する」場合には、エッジ多項式判定部（１４２）はエッジ多項式判定処理を終了してよい。判定結果情報Γが「実区間Ｉ上に実重複零点を有する要素エッジ多項式が存在しない」場合には、多項式Ｐ、既約有理式Ｑ／Ｒを求め、多項式Ｐが恒等的に０か否かを判定する。多項式Ｐが恒等的に０であるならばβ∈ＩについてＱ(β)／Ｒ(β)∈ＩＥ〔ＩＥは、エッジ多項式において端点に固定されていない係数の区間数（但し、端点を除く。）を表す。上記説明では、開区間（ｕ，ｈ）に対応する。〕の成否を判定し、これが成立するならば「実区間Ｉ上に実重複零点を有する要素エッジ多項式が存在する」を表す情報Γを得る。多項式Ｐが恒等的に０でないならば多項式Ｐ１を求め、多項式Ｐ１の実零点ζについて、ζ∈ＩかつＱ(ζ)／Ｒ(ζ)∈ＩＥの成否を判定し、これが成立するならば「実区間Ｉ上に実重複零点を有する要素エッジ多項式が存在する」を表す情報Γを得る。いずれのエッジ多項式について上記所定の判定を満足しなかった場合は、「実区間Ｉ上に実重複零点を有する要素エッジ多項式が存在しない」を表す情報Γを得る。
【０２０３】
制御部（１９０）は、この判定結果情報Γが、実区間Ｉ上に実重複零点を有する要素エッジ多項式が存在しないというものである場合には（図３のステップＳ５１８参照。）、「実区間Ｉ内に実区間多項式Ｆの実重複擬零点が存在しない」ことを表す情報θ（例えばこの場合は、θ＝０とする。）をメモリ（２０）の所定の格納領域に格納する（図１のステップＳ１０２）。なぜなら、上記理論から明らかなとおり、実区間多項式Ｆ(ｘ)に属するいかなる要素エッジ多項式も実区間Ｉ上に実重複零点を有しないことは、結局、実区間Ｉ内に実区間多項式Ｆの実重複擬零点が存在しないことと同じであるからである。
【０２０４】
制御部（１９０）は、判定結果情報Γが、実区間Ｉ上に実重複零点を有する要素エッジ多項式が存在するというものである場合には（図３のステップＳ５１７参照。）、「実区間Ｉ内に実区間多項式Ｆの実重複擬零点が存在する」ことを表す情報θ（例えばこの場合は、θ＝１とする。）をメモリ（２０）の所定の格納領域に格納する（図１のステップＳ１０３）。なぜなら、この場合、実区間Ｉ上に実重複零点を有する要素エッジ多項式が存在することは、まさに実区間Ｉ内に実区間多項式Ｆの実重複擬零点が存在することと同じであるからである。
【０２０５】
[第２実施形態]
以下に、本発明の第２実施形態を説明する。第２実施形態は、実区間多項式Ｆの実重複擬零点全体の集合ＭＺＲ(Ｆ)の決定に係わる。なお、第１実施形態と第２実施形態は両立するから、コンピュータに両者を実装することができる。ここでは説明の便宜から、実区間多項式Ｆの実重複擬零点全体の集合ＭＺＲ(Ｆ)の決定を第２実施形態としている。
第２実施形態に係わる実重複擬零点位置判定装置（１）〔以下、単に実重複擬零点位置判定装置（１）ということにする。〕のハードウェア構成等は第１実施形態と同様であるから、第２実施形態の本質部分について説明を加える。
【０２０６】
第２実施形態に係わる実重複擬零点位置判定装置（１）の外部記憶装置（１７）〔あるいはＲＯＭなど〕には、実区間多項式Ｆの全てのエッジ多項式について、その実重複擬零点全体の集合Ｚを求めるための集合Ｚ決定プログラム、集合Ｚの補集合における全ての実区間Ｊについて、各実区間Ｊ上で任意に１点γを選択し、この点γを実重複零点とする多項式が実区間多項式Ｆに存在するか否かを判定し、これが存在する場合には点γを含む実区間Ｊと集合Ｚとの和集合を求めることで集合ＭＺＲ(Ｆ)を得る集合ＭＺＲ(Ｆ)決定プログラムおよびこれらのプログラムの処理において必要となるデータなどが保存記憶されている。その他、これらのプログラムに基づく処理を制御するための制御プログラムも適宜に保存記憶しておく。
【０２０７】
実重複擬零点位置判定装置（１）では、外部記憶装置（１７）〔あるいはＲＯＭなど〕に記憶された各プログラムとこの各プログラムの処理に必要なデータが必要に応じてメモリ（２０）に読み込まれて、適宜にＣＰＵ（１４）で解釈実行・処理される。その結果、ＣＰＵ（１４）が所定の機能（集合Ｚ決定部、集合ＭＺＲ(Ｆ)決定部、制御部）を実現する。
【０２０８】
図４、図５、図６、図７、図１０を参照して、第２実施形態における実区間多項式の実重複擬零点の位置判定処理について説明する。
【０２０９】
実重複擬零点位置判定装置（１）の外部記憶装置（１７）には、予め、実区間多項式Ｆ(ｘ)、実区間Ｉなどが予め保存記憶されているとする。
【０２１０】
第２実施形態では、説明の便宜からより具体的に、実区間多項式Ｆ(ｘ)の各項の区間数Ａｊ＝［ｕｊ，ｈｊ］≡｛（ｈｊ−ｕｊ）ｔｊ＋ｕｊ｝〔但し、０≦ｔｊ≦１、ｊ＝０，１，２，・・・，ｄとする。〕が、予め、実重複擬零点位置判定装置（１）の外部記憶装置（１７）に保存記憶されているとする。
【０２１１】
まず、実重複擬零点位置判定装置（１）の制御部（１９０）は、外部記憶装置（１７）から全ての区間数Ａｊ＝｛（ｈｊ−ｕｊ）ｔｊ＋ｕｊ｝を読み込み、それぞれをメモリ（２０）の所定の格納領域に格納しておく。以後、「メモリから○○を読み込む」旨の説明をした場合は、「メモリにおいて○○が格納されている所定の格納領域から○○を読み込む」ことを意味するとする。
【０２１２】
集合Ｚ決定部（１４５）は、メモリ（２０）から、全ての区間数Ａｊ＝｛（ｈｊ−ｕｊ）ｔｊ＋ｕｊ｝を読み込み、《集合Ｚ決定処理》で説明したアルゴリズムに従って、実区間多項式Ｆの全てのエッジ多項式について、その実重複擬零点全体の集合である集合Ｚを求める（図４のステップＳ２００）。
概略を示すと、集合Ｚ決定部（１４５）は、メモリ（２０）と協働しながら、区間数Ａｊに対するエッジ多項式について次のような動作をする。つまり、多項式ｗ(ｘ)、多項式ｗｕ(ｘ)、多項式ｗｕ(ｘ)について全実零点集合の和集合ＳＺを求める。なお、多項式ｗｕ(ｘ)、多項式ｗｕ(ｘ)についていずれかが恒等的に０ならば集合Ｚは実数全体の集合Ｒとして集合Ｚ決定処理を終了してよい。多項式Ｐ、既約有理式Ｑ／Ｒを求め、多項式Ｐが恒等的に０か否かを判定する。多項式Ｐが恒等的に０ならば、集合ＳＺの各要素を挟むようにとった各点βについて、Ｑ(β)／Ｒ(β)∈ＩＥ〔ＩＥは、エッジ多項式において端点に固定されていない係数の区間数（但し、端点を除く。）を表す。上記説明では、開区間（ｕ，ｈ）に対応する。〕の成否を判定し、これが成立するならば、点βに応じた区間を集合ＳＺに加える〔以下、集合と集合との和集合をとることを「加える」と表現する。〕。なお、集合ＳＺの要素が１つも無い場合には、１点βについてＱ(β)／Ｒ(β)∈ＩＥの成否を判定し、これが成立するならば、集合Ｚは実数全体の集合Ｒとして集合Ｚ決定処理を終了してよい。多項式Ｐが恒等的に０でないならば、多項式Ｐ１を求め、多項式Ｐ１の全実零点ζＳについて、ζＳ∈ＩかつＱ(ζ)／Ｒ(ζ)∈ＩＥの成否を判定し、これが成立するならば、｛ζＳ｝を集合ＳＺに加える。エッジ多項式ごとに得られた集合ＳＺの和集合を集合ＭＺＲ(Ｅ)とし、エッジ多項式ごとに得られた集合ＭＺＲ(Ｅ)の和集合を集合Ｚとする。
【０２１３】
制御部（１９０）は、集合Ｚが得られたら、ステップＳ２０１の処理を実行するように制御する。
【０２１４】
次に、集合ＭＺＲ(Ｆ)決定部（１４６）は、メモリ（２０）から、集合Ｚを読み込み〔必要に応じて、全ての区間数Ａｊ＝｛（ｈｊ−ｕｊ）ｔｊ＋ｕｊ｝および実区間Ｊが読み込まれる。〕、《集合ＭＺＲ(Ｆ)決定処理》で説明したアルゴリズムに従って、集合ＭＺＲ(Ｆ)を得る（図４のステップＳ２０１）。
概略を示すと、集合ＭＺＲ(Ｆ)決定部（１４６）は、メモリ（２０）と協働しながら、次のような動作をする。つまり、まず、集合Ｚが実数全体の集合Ｒであるならば、集合ＭＺＲ(Ｆ)は集合Ｒであるとして集合ＭＺＲ(Ｆ)決定処理を終了してよい。集合Ｚが実数全体の集合Ｒでないならば、集合Ｚを区間の和集合として書き表し、集合Ｚの補集合における全ての実区間Ｊについて、各実区間Ｊ上で任意に１点γを選択する。点γを実重複零点とする多項式が実区間多項式Ｆに存在するか否かを判定し〔凸包判定を用いればよい。〕、これが存在する場合には点γを含む実区間Ｊを集合Ｚに加えることで集合ＭＺＲ(Ｆ)を得る。
【０２１５】
本発明である実区間多項式の実重複擬零点の位置装置、位置判定方法は上述の実施形態に限定されるものではなく、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。また、上記実施形態において説明した処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されるとしてもよい。
【０２１６】
また、上記実施形態において説明した実重複擬零点位置判定装置における処理機能をコンピュータによって実現する場合、実重複擬零点位置判定装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記実重複擬零点位置判定装置における処理機能がコンピュータ上で実現される。
【０２１７】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（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）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０２２０】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、実重複擬零点位置判定装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【実施例１】
【０２２１】
以下、本発明である実区間多項式の実重複擬零点の位置判定方法の実施例を、具体例を示して簡単に説明する。以下では、ある桁から先の値を省略する意味の『…』が付されていない小数は、正確な値を表すものとする。
【０２２２】
この実施例では、多項式ｅ1(ｘ)＝Πｉ＝１20(ｘ−ｉ)，ｅ2(ｘ)＝ｘ19，ｅ3(ｘ)＝ｘ18として、実区間多項式Ｆ(ｘ)を式（３６）で与える。式（３６）の実区間多項式Ｆに対し、第２実施形態を適用して集合ＭＺＲ(Ｆ)を決定する。
【数３２】
2007299264.tif 000034
【０２２３】
実区間多項式Ｆの全てのエッジ多項式は以下のとおりである。
Ｅ１＝e1(ｘ)＋［−２-23，０］e2(ｘ)
Ｅ２＝e1(ｘ)＋［−２-23，０］e2(ｘ)＋２-16e3(ｘ)
Ｅ３＝e1(ｘ)−２-23e2(ｘ)＋［０，２-16］e3(ｘ)
Ｅ４＝e1(ｘ)＋［０，２-16］e3(ｘ)
【０２２４】
エッジ多項式Ｅ１は５個の実重複擬零点を持つ。それをα11，・・・，α15と表すことにする。
α11＝10.328…，α12＝12.388…，α13＝14.451…，
α14＝16.524…，α15＝18.619…
【０２２５】
エッジ多項式Ｅ２は実重複擬零点を持たない。
【０２２６】
エッジ多項式Ｅ３は３個の実重複擬零点を持つ。
α31＝9.313…，α32＝10.292…，α33＝19.811…
【０２２７】
エッジ多項式Ｅ４は６個の実重複擬零点を持つ。
α41＝9.307…，α42＝11.365…，α43＝13.426…，
α44＝15.493…，α45＝17.573…，α46＝19.694…
【０２２８】
従って、実区間多項式Ｆのエッジ多項式は、全部で１４個の実重複擬零点を持ち、集合Ｚは式（３７）のとおりとなる。
【数３３】
2007299264.tif 000035
【０２２９】
なお、αijを大きさの順に並べると以下のとおりである。
α41＜α31＜α32＜α11＜α42＜α12＜α43＜α13＜α44＜α14＜α45＜α15＜α46＜α33
【０２３０】
参照点γ１，γ２，…，γ15を以下のとおりに採る。
γ１＝０，γ２＝9.31，γ３＝10，γ４＝10.3，γ５＝11，
γ６＝12，γ７＝13，  γ８＝14，γ９＝15，  γ10＝16，
γ11＝17，γ12＝18，  γ13＝19，γ14＝19.8，γ15＝20
【０２３１】
各参照点γｉに対し、これらが実区間多項式Ｆ(ｘ)の実重複擬零点となるか否かを判定することによって、集合Ｚは以下のとおりとなる。
Ｚ=[α41,α31]∪[α32,α11]∪[α42,α12]∪[α43,α13]∪[α44,α14]∪[α45,α15]∪[α46,α33]
【０２３２】
ここで得られた集合Ｚが集合ＭＺＲ(Ｆ)である。
【実施例２】
【０２３３】
この実施例では、式（３８）の実区間多項式Ｇに対し、第２実施形態を適用して集合ＭＺＲ(Ｇ)を求める。
【数３４】
2007299264.tif 000036
【０２３４】
エッジ多項式は全部で１２本あり、それらが持つ実重複擬零点は合わせて５個である。小さい方から並べると、以下のとおりである。
α１＝−1.00012…，   α２＝−1.00006…，
α３＝−0.99993741…，α４＝−0.999937407…，
α５＝−0.9998…
【０２３５】
従って、集合Ｚは次のとおり与えられる。
Ｚ＝[α１,α１]∪[α２,α２]∪[α３,α３]∪[α４,α４]∪[α５,α５]
【０２３６】
なお、各αｉは、以下の要素エッジ多項式Ｅｉの実重複擬零点となっている。
Ｅ１＝144ｅ1(ｘ)＋εｅ2(ｘ)＋[−ε，ε]ｅ3(ｘ)−εｅ4(ｘ)
Ｅ２＝144ｅ1(ｘ)＋εｅ2(ｘ)＋εｅ3(ｘ)＋[−ε，ε]ｅ4(ｘ)
Ｅ３＝144ｅ1(ｘ)−εｅ2(ｘ)−εｅ3(ｘ)＋[−ε，ε]ｅ4(ｘ)
Ｅ４＝144ｅ1(ｘ)＋[−ε，ε]ｅ2(ｘ)＋εｅ3(ｘ)＋εｅ4(ｘ)
Ｅ５＝144ｅ1(ｘ)−εｅ2(ｘ)＋[−ε，ε]ｅ3(ｘ)＋εｅ4(ｘ)
【０２３７】
参照点を以下のとおりに採る。
γ１＝−2，γ２＝−1.0001，γ３＝−1，γ４＝−0.9999374，γ５＝−0.9999，γ６＝0
【０２３８】
各参照点γｉに対し、これらが実区間多項式Ｆ(ｘ)の実重複擬零点となるか否かを判定することによって、Ｚ＝［α１，α５］を得る。
【０２３９】
ここで得られた集合Ｚが集合ＭＺＲ(Ｇ)である。
【産業上の利用可能性】
【０２４０】
本発明は、例えば、多項式の係数に誤差を含むため一意に多項式を決定できない場合において、当該多項式の実重複零点が所定の領域に存在するかを判定したい場合や実区間多項式の実重複擬零点全体の集合を求めたい場合などに用いられ、そのような場合の一例として、ディジタル信号処理におけるディジタルフィルタの周波数特性の解析などに有用である。
【図面の簡単な説明】
【０２４１】
【図１】実区間Ｉ内に実区間多項式Ｆの実重複擬零点が存在するか否かを判定する実重複擬零点位置判定処理のフローチャート。
【図２】実区間Ｉ上で任意に選択された１点を実重複零点とする多項式が実区間多項式Ｆに存在するか否かを判定する凸包判定処理のフローチャート。
【図３】実区間Ｉ上に実重複零点を有する要素エッジ多項式が実区間多項式Ｆに存在するか否かを判定するエッジ多項式判定処理のフローチャート。
【図４】実区間多項式Ｆの実重複擬零点全体の集合ＭＺＲ(Ｆ)を決定する実重複擬零点位置判定処理のフローチャート。
【図５】実区間多項式Ｆの全てのエッジ多項式について、その実重複擬零点全体の集合Ｚを決定する集合Ｚ決定処理のフローチャート（その１）。
【図６】実区間多項式Ｆの全てのエッジ多項式について、その実重複擬零点全体の集合Ｚを決定する集合Ｚ決定処理のフローチャート（その２）。
【図７】集合Ｚから集合ＭＺＲ(Ｆ)を決定する集合ＭＺＲ(Ｆ)決定処理のフローチャート。
【図８】実重複擬零点位置判定装置（１）のハードウェア構成を例示した構成ブロック図。
【図９】実区間Ｉ内に実区間多項式Ｆの実重複擬零点が存在するか否かを判定する実重複擬零点位置判定処理の処理機能を示す機能ブロック図。
【図１０】実区間多項式Ｆの実重複擬零点全体の集合ＭＺＲ(Ｆ)を決定する実重複擬零点位置判定処理の処理機能を示す機能ブロック図。
【符号の説明】
【０２４２】
１        実重複擬零点位置判定装置
１４１    選択点多項式判定部
１４２    エッジ多項式判定部
１４５    集合Ｚ決定部
１４６    集合ＭＺＲ(Ｆ)決定部
１９０    制御部
【図１】
2007299264.tif 000037
【図２】
2007299264.tif 000038
【図３】
2007299264.tif 000039
【図４】
2007299264.tif 000040
【図５】
2007299264.tif 000041
【図６】
2007299264.tif 000042
【図７】
2007299264.tif 000043
【図８】
2007299264.tif 000044
【図９】
2007299264.tif 000045
【図１０】
2007299264.tif 000046