(57)【要約】【課題】各区分境界の端点を零点とする多項式が一変数実区間多項式に存在するか否かを判定することなく、一変数実区間多項式が、境界が有理関数で記述されているような複素領域において零点を有するか否かを判定する。【解決手段】代表多項式選択手段が、一変数実区間多項式に属する多項式を１つ選択する。そして、代表多項式零点判定手段が、前記選択された代表多項式が、複素領域に零点を有するか否かを判定する。次に、対象点多項式判定手段が、複素領域の境界上の任意の１点を零点に有する多項式が一変数実区間多項式に存在するか否かを判定する。さらに、エッジ多項式判定手段が、いずれかの区分境界上に零点を有する、高々１つの係数を除き係数が区間数の端点となっている多項式（エッジ多項式）が一変数実区間多項式に存在するか否かを判定する。【選択図】図１
2007148815.tif 000002
【特許請求の範囲】
【請求項１】
区間数が実数の閉区間で表される一変数実区間多項式と、複素領域の境界を構成する有理関数で表される有限個の区分境界と、複素領域を指定する点座標とを記憶する記憶手段と、
記憶手段に記憶される一変数実区間多項式に属する多項式を１つ選択する代表多項式選択手段と、
代表多項式選択手段によって選択された代表多項式が、記憶手段に記憶された点座標によって指定される複素領域に零点を有するか否かを判定する代表多項式零点判定手段と、
記憶手段に記憶された点座標によって指定される複素領域の境界上の任意の１点を零点に有する多項式が一変数実区間多項式に存在するか否かを判定する対象点多項式判定手段と、
いずれかの区分境界上に零点を有する、高々１つの係数を除き係数が区間数の端点となっている多項式（エッジ多項式）が一変数実区間多項式に存在するか否かを判定するエッジ多項式判定手段と
を備えたことを特徴とする一変数実区間多項式の零点の位置判定装置。
【請求項２】
上記複素領域が非有界の場合に、一変数実区間多項式に属する多項式の次数が一定であるか否かを判定する次数判定手段も備えた
ことを特徴とする請求項１に記載の一変数実区間多項式の零点の位置判定装置。
【請求項３】
一変数実区間多項式の零点の位置を判定する方法であって、
記憶手段には、区間数が実数の閉区間で表される一変数実区間多項式と、複素領域の境界を構成する有理関数で表される有限個の区分境界と、複素領域を指定する点座標とが記憶され、
代表多項式選択手段が、記憶手段に記憶される一変数実区間多項式に属する多項式を１つ選択する代表多項式選択ステップと、
代表多項式零点判定手段が、代表多項式選択ステップにおいて選択された代表多項式が、記憶手段に記憶された点座標によって指定される複素領域に零点を有するか否かを判定する代表多項式零点判定ステップと、
対象点多項式判定手段が、記憶手段に記憶された点座標によって指定される複素領域の境界上の任意の１点を零点に有する多項式が一変数実区間多項式に存在するか否かを判定する対象点多項式判定ステップと、
エッジ多項式判定手段が、いずれかの区分境界上に零点を有する、高々１つの係数を除き係数が区間数の端点となっている多項式（エッジ多項式）が一変数実区間多項式に存在するか否かを判定するエッジ多項式判定ステップと
を有することを特徴とする一変数実区間多項式の零点の位置判定方法。
【請求項４】
上記代表多項式零点判定ステップは、
代表多項式零点判定手段が、
まず、代表多項式選択ステップにおいて選択された代表多項式が、記憶手段に記憶された点座標によって指定される複素領域の境界上に零点を有するか否かを判定し、次に、当該境界上に零点を有しないと判定された場合に、代表多項式選択ステップにおいて選択された代表多項式が、当該複素領域の内部に零点を有するか否かを判定するものである
ことを特徴とする請求項３に記載の一変数実区間多項式の零点の位置判定方法。
【請求項５】
一変数実区間多項式の各区間数をそれぞれの両端点および内分比で表すとして、
上記対象点多項式判定ステップは、
対象点多項式判定が、記憶手段に記憶された点座標によって指定される複素領域の境界上の任意の１点（対象点）を一変数実区間多項式に代入した多項式について、各区間数ごとに内分比を含む項（内分比項）と含まない項（非内分比項）に分け、内分比項の和で定まる点全体の凸包に、非内分比項の和で定まる点が入るか否かの判定をすることによって、対象点を零点に有する多項式が一変数実区間多項式に存在するか否かを判定するものである
ことを特徴とする請求項３または請求項４に記載の一変数実区間多項式の零点の位置判定方法。
【請求項６】
各区分境界がそれぞれ一変数（区分境界変数）の有理関数およびその区分境界変数の取りえる範囲（変数範囲）によって表されるとして、
上記エッジ多項式判定ステップは、
エッジ多項式判定手段が、区分境界をエッジ多項式に代入し、この代入されたエッジ多項式を、区間数の端点に固定されていない係数を変数とする多項式とみて、この根を一意に与えるときの区分境界変数が区分境界変数の変数範囲に存在するか否かを判定することによって、いずれかの区分境界上に零点を有するエッジ多項式が一変数実区間多項式に存在するか否かを判定するものである
ことを特徴とする請求項３から請求項５のいずれかに記載の一変数実区間多項式の零点の位置判定方法。
【請求項７】
次数判定手段が、上記複素領域が非有界の場合に、一変数実区間多項式に属する多項式の次数が一定であるか否かを判定する次数判定ステップをも有する
ことを特徴とする請求項３から請求項６のいずれかに記載の一変数実区間多項式の零点の位置判定方法。
【請求項８】
コンピュータに請求項３から請求項７のいずれかに記載の一変数実区間多項式の零点の位置判定方法を実行させるための、一変数実区間多項式の零点の位置判定プログラム。
【請求項９】
請求項８に記載の一変数実区間多項式の零点の位置判定プログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、実区間多項式の零点の位置判定装置、位置判定方法、位置判定プログラムおよび記録媒体に関する。より詳細には、一変数実区間多項式の零点の位置判定装置、位置判定方法、位置判定プログラムおよび記録媒体に関する。
【背景技術】
【０００２】
係数が確定していない（例えば、係数に誤差がある場合などである。）多項式を表す手法として、区間多項式がある。区間多項式Ｆ（ｘ）とは、数の集合である区間数Ａｊ（０≦ｊ≦ｄ）を各項の係数として式（１）のように表記されるものである。つまり、区間多項式Ｆ（ｘ）は、係数がａｊ∈Ａｊである多項式ｆ（ｘ）〔式（２）参照。〕全体の集合を表す。なお、この明細書における区間多項式は、特に断りのない限り、一変数区間多項式であるとする。なお、ｅｊ（ｘ）は多項式とする。
【数１】
2007148815.tif 000003
【０００３】
以下では、区間数を実数の範囲で考える。この場合、区間数Ａｊとして閉区間［ｍｊ，ｕｊ］を用いる。このような区間多項式であることを明確にするため、以下では、実区間多項式と云うことにする。
実区間多項式Ｆ（ｘ）に属する多項式が与えられた複素領域Ｄ（この境界Ｃを含む。）に零点を持つか否かを判定する方法として、特許文献１に開示される方法がある。
【０００４】
なお、複素領域Ｄ（以下、単に「領域Ｄ」という。）の境界Ｃは、長さが有限な単純閉曲線（Jordan閉曲線）であって、境界Ｃは、１つ以上の有限個の区分境界Ｃｐの和集合として表現されるとする。即ち、Ｃ＝Ｃ１∪Ｃ２∪・・・∪Ｃｎ（ｎは１以上の整数とする。）である。但し、各区分境界Ｃｐは、パラメータｓによってφｐ（ｓ）＋ｉ・ψｐ（ｓ）と表示されるとする〔ｐ＝１，２，・・・，ｎ〕。ｉは、虚数単位を表す。ここで、φｐ（ｓ）、ψｐ（ｓ）は有理数係数の有理式であるとし、ｓの動く範囲Ｓｐは、［ａ，ｂ］、（−∞，ｂ］、［ａ，∞）、（−∞，∞）のいずれかであるとする。[・，・]は閉区間、（・，・］は左開右閉区間、［・，・）は左閉右開区間、（・，・）は開区間を表す。また、パラメータｓと区分境界Ｃｐとの間は単射であるとする。即ち、式（３）で表される関係は単射であるとする。
【数２】
2007148815.tif 000004
【０００５】
このとき、特許文献１に開示される方法は、「領域Ｄ（境界Ｃを含む。）に少なくとも１つ零点を持つ多項式ｆ（ｘ）∈Ｆ（ｘ）が存在するか否か」・・・（☆）を厳密に判定可能である。なお、記号∈は、或る要素が集合に「属する」ことを意味する。
【０００６】
特許文献１に開示される方法（零点位置判定処理）のアルゴリズムは、図２３を参照して説明すると、以下のとおりである。
○ステップ１：代表多項式ｆ０（ｘ）∈Ｆ（ｘ）を選択する（Ｓ９００）。
○ステップ２：領域Ｄ（境界Ｃ上およびその内部）に、代表多項式ｆ０（ｘ）の零点が存在するか否かを判定する（Ｓ９０１）。もし、零点が存在すれば、（☆）について「存在する」と云えて零点位置判定処理を終了する（Ｓ９０８）。もし、零点が存在しなければ、パラメータｐ＝１として（Ｓ９０２）、次のステップを処理する。
○ステップ３：区分境界Ｃｐの端点を零点とする多項式が実区間多項式Ｆ（ｘ）に存在するか否かを判定する（Ｓ９０３）。もし、このような多項式が存在すれば、（☆）について「存在する」と云えて零点位置判定処理を終了する（Ｓ９０８）。もし、このような多項式が存在しなければ、次のステップを処理する。
○ステップ４：区分境界Ｃｐ上に零点を持ち、係数のうち高々１つだけが端点ではない多項式（エッジ多項式）が実区間多項式Ｆ（ｘ）に存在するか否かを判定する（Ｓ９０４）。もし、このような多項式が存在すれば、（☆）について「存在する」と云えて零点位置判定処理を終了する（Ｓ９０８）。もし、このような多項式が存在しなければ、次のステップを処理する。
○ステップ５：ｐ＜ｎならば（Ｓ９０５）、ｐに１を加えたものをｐに置き換え（Ｓ９０６）、ステップ３の処理以降を行う。ｐ＝ｎならば（Ｓ９０５）、（☆）について「存在しない」が云えることとなり零点位置判定処理を終了する（Ｓ９０７）。
【０００７】
なお、区間数が実数の区間多項式について、当該区間多項式に属する全ての多項式の全ての零点が、与えられた複素領域（但し、適当な条件を満すものに限られる。）に属するか否かについては、エッジ定理により判定可能である（例えば、非特許文献１参照。）。そこで、（☆）が「少なくとも１つ零点を持つ」ではなく、「全ての零点を持つ」という問題ならば、エッジ定理が適用可能である。すなわち、実区間多項式Ｆ（ｘ）に属する全てのエッジ多項式、つまり、高々１つの係数を除く係数が区間数の端点となっている多項式のみを調べればよい。但し、領域Ｄについて「領域Ｄの補集合の任意の点が無限遠に向かう適当な経路上にある」という制限がつく。従って、「領域Ｄ（境界Ｃを含む。）に少なくとも１つ零点を持つ」の否定と同値な「領域Ｄの補集合に全ての零点がある」を示すのに、エッジ定理を常に使えるわけではない。
【特許文献１】特開２００５−２３５１２１号公報
【非特許文献１】A.C.Bartlett, C.V.Hollot and L.Huang,"Root location of an entire po1ytope of polynomials: it suffices to check the edges", Mathematics of Controls, Signals and Systems, Vol.1, pp.61-71, 1988.
【発明の開示】
【発明が解決しようとする課題】
【０００８】
特許文献１に開示される方法では、上記○ステップ３において、各区分境界の端点を対象として、その点を零点とする多項式であって、与えられた実区間多項式Ｆ（ｘ）に属するものが存在するか否かを判定しなければならなかった。そのため、区分境界の数が多い場合には判定効率が悪くなるという問題があった。
【０００９】
そこで、本発明は、各区分境界の端点を零点とする多項式が一変数実区間多項式Ｆ（ｘ）に存在するか否かを判定することなく、一変数実区間多項式Ｆ（ｘ）が、境界が有理関数で記述されているような複素領域において零点を有するか否かを判定する一変数実区間多項式の零点の位置判定装置、位置判定方法、位置判定プログラムおよび記録媒体を提供することを目的とする。
【課題を解決するための手段】
【００１０】
上記課題を解決するために、本発明では、区間数が実数の閉区間で表される一変数実区間多項式と、複素領域の境界を構成する有理関数で表される有限個の区分境界と、複素領域を指定する点座標とを記憶手段に記憶しておき、まず、代表多項式選択手段が、記憶手段に記憶される一変数実区間多項式に属する多項式を１つ選択する。そして、代表多項式零点判定手段が、前記選択された代表多項式が、記憶手段に記憶された点座標によって指定される複素領域に零点を有するか否かを判定する。次に、対象点多項式判定手段が、記憶手段に記憶された点座標によって指定される複素領域の境界上の任意の１点を零点に有する多項式が一変数実区間多項式に存在するか否かを判定する。さらに、エッジ多項式判定手段が、いずれかの区分境界上に零点を有する、高々１つの係数を除き係数が区間数の端点となっている多項式（エッジ多項式）が一変数実区間多項式に存在するか否かを判定する。
このように、各区分境界の端点を零点とする多項式が一変数実区間多項式Ｆ（ｘ）に存在するか否かを判定するのではなく、複素領域の境界上の任意の１点を零点に有する多項式が一変数実区間多項式に存在するか否かを判定する。
【００１１】
また、代表多項式零点判定手段が、まず、上記選択された代表多項式が、記憶手段に記憶された点座標によって指定される複素領域の境界上に零点を有するか否かを判定し、次に、この境界上に零点を有しないと判定された場合に、代表多項式が、前記複素領域の内部に零点を有するか否かを判定するものであるとしてもよい。
このように、代表多項式が複素領域の境界上に零点を有するか否かを判定し、零点を有しないことを確認してから（もし、この段階で零点を有することがわかれば、一変数実区間多項式は複素領域に零点を有するといえる。）、代表多項式が複素領域の内部に零点を有するかを判定する。これは、前者の判定にStrumの定理に基づくアルゴリズムなどを適用し、後者の判定に偏角の原理に基づくアルゴリズムなどを適用することを可能にする。
【００１２】
また、一変数実区間多項式の各区間数をそれぞれの両端点および内分比で表すとして、対象点多項式判定が、記憶手段に記憶された点座標によって指定される複素領域の境界上の任意の１点（対象点）を一変数実区間多項式に代入した多項式について、各区間数ごとに内分比を含む項（内分比項）と含まない項（非内分比項）に分け、内分比項の和で定まる点全体の凸包に、非内分比項の和で定まる点が入るか否かの判定をすることによって、対象点を零点に有する多項式が一変数実区間多項式に存在するか否かを判定するとしてもよい。
このようにすることで、凸包を用いた効率的な判定が行える。
【００１３】
また、各区分境界がそれぞれ一変数（区分境界変数）の有理関数およびその区分境界変数の取りえる範囲（変数範囲）によって表されるとして、エッジ多項式判定手段が、区分境界をエッジ多項式に代入し、この代入されたエッジ多項式を、区間数の端点に固定されていない係数を変数とする多項式とみて、この根を一意に与えるときの区分境界変数が区分境界変数の変数範囲に存在するか否かを判定することによって、いずれかの区分境界上に零点を有するエッジ多項式が一変数実区間多項式に存在するか否かを判定するものであるとしてもよい。
このようにすることで、区間数の端点に固定されていない係数についての一次の方程式の解を求める方法を利用した簡易な判定が行える。
【００１４】
また、次数判定手段が、上記複素領域が非有界の場合に、一変数実区間多項式に属する多項式の次数が一定であるか否かを判定するとしてもよい。
このようにすることで、複素領域が非有界の場合にも、一変数実区間多項式の零点位置判定が行える。
【００１５】
また、本発明の一変数実区間多項式の零点の位置判定方法をコンピュータによって実行させる一変数実区間多項式の零点の位置判定プログラムによって、コンピュータを零点位置判定装置として作動処理させることができる。そして、この位置判定プログラムを記録した、コンピュータによって読み取り可能なプログラム記録媒体によって、他のコンピュータを位置判定装置として機能させることや、位置判定プログラムを流通させることなどが可能になる。
【発明の効果】
【００１６】
本発明によれば、各区分境界の端点を零点とする多項式が一変数実区間多項式Ｆ（ｘ）に存在するか否かを判定する従来の方法に対して、複素領域の境界上の任意の１点を零点に有する多項式が一変数実区間多項式に存在するか否かを判定するだけなので、区分境界が複数ある場合に効率良く、一変数実区間多項式の零点位置判定を行うことができる。
【発明を実施するための最良の形態】
【００１７】
[理論]
本発明の実施形態の説明に先立ち、本発明の理論について説明する。
はじめに、この明細書における記号および用語の説明をする。但し、記号については、説明の便宜等からそれまでとは異なる意味で同じ記号を用いる場合がある。
実数の範囲の区間数である或る閉区間［ｍｊ，ｕｊ］を、便宜上、パラメータｔｊ（０≦ｔｊ≦１）を用いて、｛（ｕｊ−ｍｊ）ｔｊ＋ｍｊ｝と表記する。ｔｊは、閉区間の両端点ｍｊ、ｕｊの内分比を表す。このとき、一変数実区間多項式Ｆ（ｘ）〔以下、「一変数」という文言を略する。〕は、上記区間数｛（ｕｊ−ｍｊ）ｔｊ＋ｍｊ｝を各項の係数として式（４）のように表記されるものであり、各ｊ（０≦ｊ≦ｄ、但しｊは整数。）に対して係数がａｊ∈｛（ｕｊ−ｍｊ）ｔｊ＋ｍｊ｝である多項式ｆ（ｘ）〔式（５）参照〕の全体の集合を表す。また、ｅｊ（ｘ）は実数である係数が確定した多項式とする。なお、区間数の端点ｍｊ、ｕｊおよび多項式ｅｊ（ｘ）の係数は、理論上は実数としてよいが、コンピュータなどによる演算の上では四則演算および等号判定を有限ステップのアルゴリズムで実行できることが必要かつ十分であり、そのために例えば実代数的数（整数係数一変数代数方程式の根となる実数）とし、具体例として有理数であるとする。
【数３】
2007148815.tif 000005
【００１８】
以下では、説明の便宜から、ｅｊ（ｘ）＝ｘｊの場合を例示して説明する。また、実代数的数として有理数を例にとって説明する。
【００１９】
実区間多項式Ｆ（ｘ）の零点が存在するか否かの対象となる複素領域は、有界の場合と非有界の場合を考えることができる。
境界の長さが有限である有界な複素領域Ｄ（以下、単に「領域Ｄ」という。）の境界Ｃは、長さが有限な単純閉曲線（Jordan閉曲線）であって、境界Ｃは、１つ以上の有限個の区分境界Ｃｐの和集合として表現される。即ち、Ｃ＝Ｃ１∪Ｃ２∪・・・∪Ｃｎ（ｎは１以上の整数とする。）である。但し、各区分境界Ｃｐは、パラメータｓおよびパラメータｓを一変数とする有理式φｐ（ｓ）、ψｐ（ｓ）によってφｐ（ｓ）＋ｉ・ψｐ（ｓ）と表示されるとする〔ｐ＝１，２，・・・，ｎ〕。ｉは、虚数単位を表す。ここで、有理式φｐ（ｓ）、ψｐ（ｓ）における係数は、理論上は実数としてよいが、コンピュータなどによる演算の上では四則演算および等号判定を有限ステップのアルゴリズムで実行できることが必要かつ十分であり、そのために例えば実代数的数（整数係数一変数代数方程式の根となる実数）とし、具体例として有理数であるとする。以下では、有理式φｐ（ｓ）、ψｐ（ｓ）を、有理数係数の有理式であるとして例示説明する。パラメータｓの動く範囲Ｓｐは、［ａ，ｂ］、（−∞，ｂ］、［ａ，∞）、（−∞，∞）のいずれかであるとする。[・，・]は閉区間、（・，・］は左開右閉区間、［・，・）は左閉右開区間、（・，・）は開区間を表す。また、パラメータｓと区分境界Ｃｐとの間は単射であるとする。即ち、式（６）で表される関係は単射とする。
【数４】
2007148815.tif 000006
【００２０】
領域Ｄが有界ではないとき、即ち、０を中心とするどんなに半径が大きい円をとってもその内部に領域Ｄ全部が含まれないとき、この領域Ｄの境界は、上記の境界の長さが有限である有界な領域Ｄと同様にして境界を表すことができる場合と、閉曲線ではない境界として表される場合がある。後者の場合の境界Ｃは、Ｃ＝Ｃ１∪Ｃ２∪・・・∪Ｃｎ（ｎは１以上の整数とする。）であり、且つ、両端の区分境界Ｃ１およびＣｎのみが長さ有限ではないことになる。なお、領域Ｄが有界ではないときは、実区間多項式Ｆ（ｘ）に属する多項式ｆ（ｘ）の次数が一定であるとする。この点については、後述の《補遺》において説明を加える。
【００２１】
次に、本発明における実区間多項式の零点の位置判定のアルゴリズムを、図１を参照しながら説明する。なお、予め説明しておくと、本発明における「実区間多項式の零点の位置判定」とは、実区間多項式の零点の位置（座標）を特定することではなく、所定の領域に実区間多項式の零点が存在するか否かに係わる判定のことである。換言すれば、実区間多項式の零点が所定の領域に存在するか否かの意味において、実区間多項式の零点の位置判定をすることになる。
【００２２】
＜ステップ１＞
まず、実区間多項式Ｆ（ｘ）に属する多項式を一つ選択する。これを代表多項式と呼びｆ（ｘ）で表す（Ｓ８００）。
【００２３】
＜ステップ２＞
領域Ｄ（境界Ｃ上およびその内部）に代表多項式ｆ（ｘ）の零点が存在するか否かを判定する（Ｓ８０１）。この判定は、公知の手法によって達成される。
まず、領域Ｄの境界Ｃ上において代表多項式ｆ（ｘ）の零点が存在するか否かの判定を行う。例えば、領域Ｄの境界Ｃの表示φ（ｓ）＋ｉ・ψ（ｓ）を代表多項式ｆ（ｘ）に代入した後、Sturmの定理に基づくアルゴリズムに従って零点の有無を判定する。
【００２４】
Strumの定理に基づくアルゴリズムの適用について説明する。
領域Ｄの境界Ｃの表示φ（ｓ）＋ｉ・ψ（ｓ）が代入された代表多項式ｆ（φ（ｓ）＋ｉ・ψ（ｓ））は、有理数係数有理式α（ｓ）およびβ（ｓ）によってｆ（φ（ｓ）＋ｉ・ψ（ｓ））＝α（ｓ）＋ｉ・β（ｓ）と表示できる。ここで「代表多項式ｆ（ｘ）が、φ（ｓ０）＋ｉ・ψ（ｓ０）において０となる」ことと、「α（ｓ）およびβ（ｓ）がｓ＝ｓ０で同時に０となる」ことは同値である。また、「α（ｓ）およびβ（ｓ）がｓ＝ｓ０で同時に０となる」ことと、「α（ｓ）およびβ（ｓ）をそれぞれ既約な有理数係数有理式として表したときの分子のＧＣＤ（最大公約多項式）がｓ０において０になる」ことは同値である。従って、α（ｓ）およびβ（ｓ）をそれぞれ既約な有理数係数有理式として表したときの分子のＧＣＤに対し、Strumの定理に基づくアルゴリズムを適用する。説明の便宜からα（ｓ）およびβ（ｓ）をそれぞれ既約な有理数係数有理式として表したときの分子のＧＣＤをＨ（ｓ）とする。このＨ（ｓ）について、多項式の列Ｈ０（ｓ）、Ｈ１（ｓ）、Ｈ２（ｓ）、・・・、Ｈｒ（ｓ）を生成する。但し、これらの多項式の列は、次の規則に従って生成する。Ｈ０（ｓ）＝Ｈ（ｓ）、Ｈ１（ｓ）＝ｄＨ（ｓ）／ｄｓ〔ｓに関する１階微分である。ライプニッツ記法〕、Ｈｋ−１（ｓ）をＨｋ（ｓ）で割った剰余多項式を（符号を変えて）−Ｈｋ＋１（ｓ）とする。つまり、商の多項式をＱｋ（ｓ）と表すと、Ｈｋ−１（ｓ）＝Ｈｋ（ｓ）Ｑｋ（ｓ）−Ｈｋ＋１（ｓ）の関係が成立する。また、Ｈｒ−１（ｓ）は、Ｈｒ（ｓ）で割り切れる。つまり、商の多項式をＱｒ（ｓ）と表すと、Ｈｒ−１（ｓ）＝Ｈｒ（ｓ）Ｑｒ（ｓ）の関係が成立する。このとき、Ｓ＝[ａ，ｂ]において、Ｈ０（ａ）、Ｈ１（ａ）、Ｈ２（ａ）、・・・、Ｈｒ（ａ）における正負の符号変化の回数をｗ（ａ）で表し、Ｈ０（ｂ）、Ｈ１（ｂ）、Ｈ２（ｂ）、・・・、Ｈｒ（ｂ）における正負の符号変化の回数をｗ（ｂ）で表すとすると、区間Ｓ＝[ａ，ｂ]におけるＨ（ｓ）の零点の個数は、ｗ（ａ）−ｗ（ｂ）である。なお、ここでは、区間Ｓ＝[ａ，ｂ]のａ、ｂは共にＨ（ｓ）の零点ではないとする（零点であれば、個数を表す式が少し変わるが、本発明においては本質的な部分ではないので略する。）。ｗ（ａ）−ｗ（ｂ）＝０であれば零点が存在しないことが判明し、ｗ（ａ）−ｗ（ｂ）≠０であれば零点が存在することが判明する。
【００２５】
なお、Sturmの定理については、参考文献１を参照のこと。
（参考文献１）  高木貞治著、「代数学講義（改訂新版）」、共立出版、１９６５．
【００２６】
以上では、領域Ｄの境界Ｃ上において代表多項式ｆ（ｘ）の零点が存在するか否かの判定を、領域Ｄの境界Ｃの表示φ（ｓ）＋ｉ・ψ（ｓ）を代表多項式ｆ（ｘ）に代入した後、Sturmの定理に基づくアルゴリズムによって行うものとして説明した。しかし、Sturmの定理に基づくアルゴリズムに限定する趣旨ではない。要は、一変数実係数の代数方程式がある実の区間に根を持つか否かの判定ができればよく、例えば参考文献２に示されるsign variation methodによってこれを判定するとしてもよい。
（参考文献２）  G. E. Collins and R. Loos, "Real zeros of polynomials", Computer Algebra, Symbolic and Algebraic Computation, (B. Buchberger, G. E. Collins and R. Loos(編)), pp.83-94, Springer-Verlag,1983.
【００２７】
もし、この段階で零点の存在が確認されれば、実区間多項式Ｆ（ｘ）は領域Ｄにおいて零点を有するといえるので、零点位置判定処理を終了してよい（Ｓ８０８）。
【００２８】
もし、この段階で零点が存在しなければ、領域Ｄの内部において代表多項式ｆ（ｘ）の零点が存在するか否かの判定を行う。この判定には偏角の原理を用いることで達成される。なお、偏角の原理に基づく判定においては、領域Ｄの境界Ｃ上に代表多項式ｆ（ｘ）の零点がないことが前提となるから、まず、境界Ｃ上での零点の有無を判定しておく。
【００２９】
偏角の原理に基づくアルゴリズムの適用について説明する。
区分境界Ｃｐの表示φｐ（ｓ）＋ｉ・ψｐ（ｓ）を代表多項式ｆ（ｘ）に代入する。このとき、ｆ（ｘ）＝ｆ（φｐ（ｓ）＋ｉ・ψｐ（ｓ））＝ｕ（φｐ（ｓ），ψｐ（ｓ））＋ｉ・ｖ（φｐ（ｓ），ψｐ（ｓ））と表される。そこで、実部ｕ（φ（ｓ），ψ（ｓ））と虚部ｖ（φ（ｓ），ψ（ｓ））それぞれの実根をｓ∈Ｓにおいて求める。同様にして全ての区分境界について根を求め、これらの根を現れる順に並べたリストＳ１を作る。また、境界Ｃに囲まれた領域における根の計数用のリストＳ２を用意する（初期状態では、リストＳ２は空である。）。リストＳ１の先頭から順次に根を読み出すこととし、まず、先頭要素（根）Ａを取り出し、リストＳ２が空のリストであればそれをＳ２に書き込む。リストＳ２が空でないときは先頭要素（根）ＡとリストＳ２の先頭の要素（根）がともに実部の解であるかともに虚部の解であるかを判定し、この判定が真であればリストＳ２から先頭の要素（根）を取り除く。当該判定が偽であるときは先頭要素（根）ＡをリストＳ２の先頭に書き足す。この処理操作をリストＳ１の先頭から順次に根を読み出すことで行う。この結果、リストＳ２における要素（根）の個数の１／４が境界Ｃの内部に含まれる代表多項式ｆ（ｘ）の根の数になる。この数が０であれば、代表多項式ｆ（ｘ）の零点が領域Ｄの内部に存在しないことが判明し、この数が０でなければ、代表多項式ｆ（ｘ）の零点が領域Ｄの内部に存在することが判明する。
【００３０】
なお、偏角の原理については、参考文献３を参照のこと。
（参考文献３）  平野照比古著、「偏角の原理を用いた多項式の根の数え上げ」、数式処理、Vol.9, No.4, pp.34-35, 2003.
【００３１】
以上では、領域Ｄの内部において代表多項式ｆ（ｘ）の零点が存在するか否かの判定を偏角の原理に基づくアルゴリズムによって行うものとして説明した。しかし、要は、代表多項式ｆ（ｘ）〔より一般的には「多項式など」である。〕が領域Ｄの内部に根を持つか否かの判定ができればよく、偏角の原理に基づくアルゴリズムに限定する趣旨ではない。
【００３２】
もし、この段階で零点の存在が確認されれば、実区間多項式Ｆ（ｘ）は領域Ｄにおいて零点を有するといえるので、零点位置判定処理を終了してよい（Ｓ８０８）。
この＜ステップ２＞において、代表多項式ｆ（ｘ）が領域Ｄ（境界Ｃ上およびその内部）において零点を持たないことが判明した場合、続いて＜ステップ３＞の処理を行う。＜ステップ３＞以降の処理では、領域Ｄの境界Ｃ上において零点が存在するか否かを判定することに留意する。この点については、後述の《補遺》で説明する。
【００３３】
＜ステップ３＞
領域Ｄの境界Ｃ上の任意の１点ｃを選択し、この点ｃを零点とする多項式が実区間多項式Ｆ（ｘ）に存在するか否かを判定する（Ｓ８０２、後述の《ステップ３の詳細》を参照。）。このような多項式が存在すれば、実区間多項式Ｆ（ｘ）は領域Ｄにおいて零点を有するといえるので、零点位置判定処理を終了してよい（Ｓ８０８）。このような多項式が存在しなければ、区分境界Ｃｐを１つ選択して（Ｓ８０３、ここではパラメータｐ＝１に設定する。）、＜ステップ４＞の処理を行う。
【００３４】
＜ステップ４＞
区分境界Ｃｐ上に零点を有するエッジ多項式が実区間多項式Ｆ（ｘ）に存在するか否かを判定する（Ｓ８０４、後述の《ステップ４の詳細》を参照。）。このようなエッジ多項式が存在すれば、実区間多項式Ｆ（ｘ）は領域Ｄにおいて零点を有するといえるので、零点位置判定処理を終了してよい（Ｓ８０８）。このようなエッジ多項式が存在しなければ、＜ステップ５＞の処理を行う。
【００３５】
＜ステップ５＞
未選択の区分境界Ｃｐが存在する場合には（Ｓ８０５、ｐ＜ｎの場合）、その未選択の区分境界から１つの区分境界を選択し（Ｓ８０６、ここではｐに１を加えたものをｐに置き換える。）、上記＜ステップ４＞における判定処理を行う。
未選択の区分境界が存在しない場合には（Ｓ８０５、ｐ＝ｎの場合）、実区間多項式Ｆ（ｘ）は領域Ｄにおいて零点を有しないことになり、零点位置判定処理を終了する（Ｓ８０７）。
【００３６】
なお、＜ステップ３＞〜＜ステップ５＞は、その処理手順を入れ替えることが可能である。図２を参照して説明する。
＜ステップ１＞（Ｓ８００）および＜ステップ２＞（Ｓ８０１）の処理を実行した後、区分境界Ｃｐを１つ選択して（Ｓ８０２ａ、ここではパラメータｐ＝１に設定する。）、＜ステップ４＞の処理を行う。即ち、区分境界Ｃｐ上に零点を有するエッジ多項式が実区間多項式Ｆ（ｘ）に存在するか否かを判定する（Ｓ８０３ａ）。このようなエッジ多項式が存在すれば、実区間多項式Ｆ（ｘ）は領域Ｄにおいて零点を有するといえるので、零点位置判定処理を終了してよい（Ｓ８０８）。このようなエッジ多項式が存在しなければ、＜ステップ５＞の処理を行う。即ち、未選択の区分境界が存在する場合には（Ｓ８０４ａ、ｐ＜ｎの場合）、その未選択の区分境界から１つの区分境界を選択し（Ｓ８０５ａ、ｐに１を加えたものをｐに置き換える。）、上記＜ステップ４＞における処理を行う。未選択の区分境界が存在しない場合には（Ｓ８０４ａ、ｐ＝ｎの場合）、上記＜ステップ３＞の処理を行う。即ち、領域Ｄの境界Ｃ上の任意の１点ｃを選択し、この点ｃを零点とする多項式が実区間多項式Ｆ（ｘ）に存在するか否かを判定する（Ｓ８０６ａ）。このような多項式が存在すれば、実区間多項式Ｆ（ｘ）は領域Ｄにおいて零点を有するとして零点位置判定処理を終了する（Ｓ８０８）。このような多項式が存在しなければ、実区間多項式Ｆ（ｘ）は領域Ｄにおいて零点を有しないとして零点位置判定処理を終了する（Ｓ８０７）。
このように、＜ステップ３＞〜＜ステップ５＞の処理手順を入れ替えることが可能な理由は、後述の《ステップ３とステップ４の前後関係》で説明する。
【００３７】
《補遺》
上記＜ステップ２＞において、代表多項式ｆ（ｘ）が領域Ｄ（境界Ｃ上およびその内部）に零点を有しないと判明した場合、上記＜ステップ３＞以降の処理では、境界Ｃ上に零点が存在するか否かを判定すれば十分である。このことは、次の理由による。
【００３８】
ここでの説明においては、ｆ（ｘ）を、上記の代表多項式ではなく、実区間多項式Ｆ（ｘ）に属する（任意の）多項式を表すものとする。
実区間多項式Ｆ（ｘ）に属する２つの（任意の）多項式ｆ（ｘ）、ｇ（ｘ）について、ｆ（ｘ）＋ｔ（ｇ（ｘ）−ｆ（ｘ））（０≦ｔ≦１）は、常に実区間多項式Ｆ（ｘ）に属する。なぜならば、区間数が実数閉区間で与えられるからである。
【００３９】
（１）まず、領域Ｄが有界の場合について説明する。
実区間多項式Ｆ（ｘ）に属する多項式ｆ（ｘ）が、領域Ｄ（有限長の単純閉曲線である境界Ｃで閉じた有界領域である。境界Ｃを含む。）の内部に零点を持たないと仮定する。この場合、実区間多項式Ｆ（ｘ）に属する多項式ｇ（ｘ）で、領域Ｄに零点を持つものが存在するならば、あるｔ（０≦ｔ≦１）が存在して、ｆ（ｘ）＋ｔ（ｇ（ｘ）−ｆ（ｘ））の零点が領域Ｄの境界Ｃ上に存在する。なぜならば、いかなるｔ（０≦ｔ≦１）に対してもｆ（ｘ）＋ｔ（ｇ（ｘ）−ｆ（ｘ））の零点が境界Ｃ上に存在しないと仮定すると、Roucheの定理から、境界Ｃの内部（つまり、領域Ｄの内部に一致する。）に存在する多項式ｆ（ｘ）の零点の数（０個）と多項式ｇ（ｘ）の零点の数（１個以上）とが等しいこととなり矛盾してしまうからである。
【００４０】
なお、Roucheの定理については参考文献４などを参照のこと。
（参考文献４）  吉田洋一著、「函数論（第２版）」、岩波書店、１９６５．
【００４１】
（２）次に、領域Ｄが非有界の場合について説明する。
（２-１）  境界Ｃが単純閉曲線の場合。
実区間多項式Ｆ（ｘ）に属する多項式ｆ（ｘ）が、領域Ｄの内部（有限長の単純閉曲線である境界Ｃで閉じた有界領域の外側領域である。但し、境界Ｃを含む。）に零点を持たないと仮定する。この場合、実区間多項式Ｆ（ｘ）に属する多項式ｇ（ｘ）で、領域Ｄの内部に零点を持つものが存在するならば、「実区間多項式Ｆ（ｘ）に属する多項式の次数が一定である」という仮定の下、上記（１）で説明したことと同じ結論が成り立つ。領域Ｄの境界Ｃの長さが有限であるから、領域Ｄの外部（つまり、有限長の単純閉曲線である境界Ｃで閉じた有界領域である。但し、境界Ｃを含まない。）は有界なので、いかなるｔ（０≦ｔ≦１）に対してもｆ（ｘ）＋ｔ（ｇ（ｘ）−ｆ（ｘ））の零点が境界Ｃ上に存在しないと仮定すると、（１）と同様の議論が成り立ち、領域Ｄの外部に存在する多項式ｆ（ｘ）の零点の数と多項式ｇ（ｘ）の零点の数とが等しいと云える（Roucheの定理）。ここで、「実区間多項式Ｆ（ｘ）に属する多項式の次数が一定」という条件を導入すると、重複度まで込めて数えれば複素平面全体での零点の数が同じになるので、領域Ｄの内部に存在する多項式ｆ（ｘ）の零点の数（０個）と多項式ｇ（ｘ）の零点の数（１個以上）とが等しいこととなり矛盾となる。従って、実区間多項式Ｆ（ｘ）に属する多項式ｇ（ｘ）で、領域Ｄの内部に零点を持つものが存在するならば、「実区間多項式Ｆ（ｘ）に属する多項式の次数が一定である」という仮定の下、あるｔ（０≦ｔ≦１）が存在して、ｆ（ｘ）＋ｔ（ｇ（ｘ）−ｆ（ｘ））の零点が領域Ｄの境界Ｃ上に存在する。
【００４２】
（２-２）  境界Ｃが閉曲線でない場合。
上記において、「実区間多項式Ｆ（ｘ）に属する多項式の次数が一定」という条件を設けたが、この場合、実区間多項式Ｆ（ｘ）に属する多項式の零点の存在範囲は有界となる。具体的には、実区間多項式Ｆ（ｘ）に属する多項式がすべてｄ次であったとして、ｘｄの係数の絶対値の最小値をｍとし（仮定からｍは正である。）、ｘｊ（０≦ｊ＜ｄ）の係数の絶対値の最大値をＭとすると、実区間多項式Ｆ（ｘ）に属する任意の多項式の全ての零点は、複素平面原点中心の半径１＋Ｍ／ｍの円内に存在する（参考文献１参照。より具体的には複素係数ａｎ−１，ａｎ−２，・・・，ａ０の方程式ｘｎ＋ａｎ−１ｘｎ−１＋・・・＋ａ０＝０の全ての根は、その絶対値が、方程式、ｒｎ−｜ａｎ−１｜ｒｎ−１−｜ａｎ−２｜ｒｎ−２−・・・−｜ａ０｜＝０の唯一の正根ｒ０を超えない、という根の限界に関する定理から導出される。）。従って、実区間多項式Ｆ（ｘ）に属する多項式の次数が一定の場合、例えば領域Ｄが左半平面（実部が０以下である複素数）とすると境界Ｃは複素平面の虚軸であって閉じていない（Jordan閉曲線ではない。）が、非有界領域Ｄの代わりに、非有界領域Ｄと複素平面原点中心の半径１＋Ｍ／ｍの円との共通部分を考えればよく、この領域は有界となるから、上記（１）の場合に帰着する。なお、この場合は、元の領域Ｄ（左半平面）の境界Ｃは、Ｃ＝Ｃ１∪Ｃ２∪・・・∪Ｃｎ（ｎは１以上の整数とする。）であり、且つ、両端の区分境界Ｃ１およびＣｎのみが長さ有限ではないことになる。
【００４３】
なお、閉曲線でない境界Ｃによる非有界領域Ｄと複素平面原点中心の半径１＋Ｍ／ｍの円との共通部分が存在しない場合は、当該領域Ｄにおいて零点は存在しないから、この場合は、予め共通部分の有無を判定することで領域Ｄに零点が存在するか否かを判定できることに留意しなければならない。
【００４４】
結局、ここでの説明における多項式ｆ（ｘ）を上記＜ステップ１＞で選択した代表多項式ｆ（ｘ）と同視すれば、上記＜ステップ２＞において、代表多項式ｆ（ｘ）が領域Ｄ（境界Ｃ上およびその内部）において零点を有しないことが判明した場合、「領域Ｄに零点を持つ多項式が実区間多項式Ｆ（ｘ）の中に存在すること」と「境界Ｃ上に零点を持つ多項式が実区間多項式Ｆ（ｘ）の中に存在すること」とは同値である。従って、上記＜ステップ３＞以降の処理では、領域Ｄの境界Ｃ上において零点が存在するか否かを判定すればよいことになる。この場合、領域Ｄの境界Ｃ上において零点が存在しないならば、実区間多項式Ｆ（ｘ）に属するいかなる多項式も、領域Ｄに零点を有しないことが判明するのである。
以上で《補遺》の説明は終わりである。
【００４５】
次に、《ステップ３の詳細》および《ステップ４の詳細》について説明する。
これに先立ち、実区間多項式Ｆ（ｘ）に属する任意の多項式ｆ（ｘ）の任意の零点αに対して、高々２つの係数を除き係数が区間数の端点となっている、実区間多項式Ｆ（ｘ）に属する多項式であって、前記零点αを零点に有する多項式ｇ（ｘ）が存在することを説明する。換言すれば、式（７）の多項式ｇ（ｘ）において、ｇ（α）＝０であり、高々２つのｊを除きγｊ＝ｍｊあるいはｕｊとなるものが存在することを説明する。
【数５】
2007148815.tif 000007
【００４６】
αを根とする次数が高々ｄの一変数実多項式ｇ（ｘ）〔ここでは、実区間多項式Ｆ（ｘ）に属さないものも含める。〕の係数の集合をＶとする。このとき、ｇ(α)＝０を実部と虚部に分けて、その連立方程式と見ることによって、Ｖは、ｄ＋１次元の実ベクトル空間Ｒｄ＋１の中でｄ次元（但し、αが実数の場合である。この場合、ｇ（α）＝０の実部における線形関係によって次元が１つ減る。）、あるいはｄ−１次元（但し、αが実数でない場合である。この場合、ｇ（α）＝０の実部および虚部における線形関係によって次元が２つ減る。）のベクトル空間となる。ベクトル空間Ｖと、実区間多項式Ｆ（ｘ）の係数からなるｄ＋１次元の超直方体Ｂとは交わる（なぜなら、ｆ（ｘ）∈Ｆ（ｘ）の係数の集合はベクトル空間Ｖに含まれる。）ので、特に、ベクトル空間Ｖは、超直方体Ｂの面と共通点があることがわかる。即ち、高々２つの係数を除き係数が区間数の端点となる多項式ｇ（ｘ）∈Ｆ（ｘ）であって、ｇ(α)＝０となるものが存在することがわかる。
【００４７】
このことを別の観点から説明する。ｇ（α）＝０を満たす式（７）の多項式ｇ（ｘ）において、γｊが区間数の端点に固定されていないパラメータｊが３つ以上あるとして、そのうちの３つを選択してこれをλ、μ、νとする。複素平面を実ベクトル空間と見たときの次元は２であるから、αλ、αμ、ανは一次従属となり、例えばαλは、αμとανの実係数の一次結合で表現できる。このとき、γλを動かしても、γμ、γνを適当に変えることによって、式（７）の右辺の値を変えないようにすることができる。このとき係数γλを大きくしていくと、係数γλがその区間数の上端に達するか、あるいは、この前にγμ（あるいはγν）がその区間数の端点に達するかが起こる。即ち、実区間多項式Ｆ（ｘ）に属する式（８）の多項式ｈ（ｘ）において、ｈ（α）＝０を満たし、係数γ’ｊが区間数の端点に固定されていないものの数が多項式ｇ（ｘ）の場合よりも少なくとも１つ少ないものが存在する。この操作を繰り返すことで、高々２つの係数を除き係数が区間数の端点となる多項式ｇ（ｘ）∈Ｆ（ｘ）であって、ｇ(α)＝０となるものが存在することが言える。
【数６】
2007148815.tif 000008
【００４８】
以上から、上記＜ステップ２＞において代表多項式ｆ（ｘ）が領域Ｄ（境界Ｃ上および境界Ｃで囲まれた内部）に零点を持たないことが判明した場合、「領域Ｄに零点を持つ多項式ｇ（ｘ）∈Ｆ（ｘ）が存在する」ことと、「高々２つの係数を除き係数が区間数の端点となっている多項式ｇ（ｘ）∈Ｆ（ｘ）であって、その零点が領域Ｄの境界Ｃ上にあるものが存在する」ことが同値であることがわかる。
【００４９】
そこで、「高々２つの係数を除き係数が区間数の端点となっている多項式ｇ（ｘ）∈Ｆ（ｘ）であって、その零点が領域Ｄの境界Ｃ上にあるものが存在するか否か」について説明を行う。
【００５０】
高々２つの係数を除き係数が区間数の端点となっている多項式ｇ（ｘ）∈Ｆ（ｘ）が領域Ｄの境界Ｃ上に零点αを持つとする。ここで、零点αが境界Ｃの区分境界Ｃｐ上にあるとし、区分境界Ｃｐの表記をＣｐ：φｐ(ｓ)＋ｉ・ψｐ（ｓ）とする。但し、φｐ(ｓ)、ψｐ（ｓ）は、ｓの有理数係数有理式である。このとき、零点αは、ｇ（φｐ(ｓ)＋ｉ・ψｐ（ｓ））の実部をｕ（ｓ）、虚部をｖ（ｓ）とおくと、ｕ（ｓ）＝ｖ（ｓ）＝０という連立方程式の解として与えられる。
【００５１】
ここで、多項式ｇ（ｘ）の係数のうち、区間数の端点に固定されていないものを（高々２つなので）ｑ１、ｑ２と表すことにする。そうすると、連立方程式ｕ（ｓ）＝ｖ（ｓ）＝０を、ｓをパラメータとするｑ１、ｑ２の連立方程式とみれば、それは連立一次方程式であって、パラメータｓを動かしたとき、当該連立方程式の係数に係わる行列式が０でない限りは、必ず解が存在し、しかも、パラメータｓについて連続である。従って、零点αに対応するｓをｓ０と表すと、ｓをｓ０から動かしていったとき、次のいずれかが起こる。
（ｉ）行列式が０になる。
（ｉｉ）行列式が０とならず、ｑ１あるいはｑ２が区間の端点に達する。
（ｉｉｉ）行列式が０とならず、ｓがパラメータの動く範囲の端点に達する。
【００５２】
（ｉｉ）の場合は、エッジ多項式となる。（ｉｉｉ）の場合は、パラメータｓがその可動範囲の端点のところで、このパラメータｓに対応する点が区分境界Ｃｐの端点となる。
【００５３】
（ｉ）の場合は、このとき連立方程式の解が不定であるならば、連立方程式が１本の場合（実質的に方程式が１本になるので、正確にはもはや「連立」方程式ではない。）と同じ状況になるので、パラメータｓを止めたままで、ｑ１、ｑ２を連立方程式を満たすよう動かすことができる。そして、ｑ１、ｑ２のうちの少なくとも一つを区間数の端点に達するまで動かすことができる。即ち、上記(ｉｉ)の場合と同様になる。また連立方程式の解が存在しないのであるならば、パラメータｓが行列式を０にする値に近付くとき、ｑ１、ｑ２のうち少なくとも一方は∞あるいは−∞に発散するから、その前に区間数の端点に達することとなる。即ち、上記（ｉｉ）の場合と同様になる。従って、（ｉ）の場合は、（ｉｉ）の場合に帰着される。
【００５４】
以上を整理すると、
[ａ]高々１つの係数を除き係数が区間数の端点となっている多項式(エッジ多項式)ｇ（ｘ）∈Ｆ（ｘ）であって、その零点が区分境界Ｃｐ上にあるものが存在する、
[ｂ]高々２つの係数を除き係数が区間数の端点となっている多項式ｇ（ｘ）∈Ｆ（ｘ）であって、区分境界Ｃｐの端点を零点とするものが存在する、
としたとき、「［ａ］あるいは［ｂ］が成り立つ」ことと、「高々２つの係数を除き係数が区間数の端点となっている多項式ｇ（ｘ）∈Ｆ（ｘ）であって、その零点が区分境界Ｃｐ上にあるものが存在すること」とは同値である。
【００５５】
従って、各区分境界について［ａ］あるいは［ｂ］が成立するか否かを調べればよい〔正確には、全ての区分境界について調べるのではなく、区分境界を順番に調べていって、ある区分境界について［ａ］または［ｂ］が成立すると判明した時点で、「領域Ｄに零点を持つ多項式ｇ（ｘ）∈Ｆ（ｘ）が存在する」ことが判明したことになるので、零点位置判定処理を終了できる。〕。
【００５６】
ここで本発明は、従来技術（特許文献１）と異なり、上記［ｂ］については各区分境界について調べることなく、領域Ｄの境界Ｃ上の任意の１点を選択して、この１点を零点とする多項式が実区間多項式Ｆ（ｘ）に存在するか否かを調べればよいことを特徴とする。そこで、このことについて説明を行う。
【００５７】
《ステップ３の詳細》
まず、領域Ｄの境界Ｃ上の任意の１点ｃを選択する。もし点ｃを零点とする多項式が実区間多項式Ｆ（ｘ）に存在するならば、「領域Ｄに零点を持つ多項式ｇ（ｘ）∈Ｆ（ｘ）が存在する」ことが判明したのと同じなので、零点位置判定処理を終了できる。
【００５８】
点ｃを零点とする多項式が実区間多項式Ｆ（ｘ）に存在しない場合、もし、境界Ｃ上に零点を持つ多項式が存在するならば、その中で、
「高々１つの係数を除き係数が区間数の端点となっている多項式(エッジ多項式)」・・・（＊）
が存在することが言える。この理由を以下に説明する。
【００５９】
今、境界Ｃ上の点ｄ（但し、点ｃを除く。）を零点とする多項式ｆ（ｘ）∈Ｆ（ｘ）が存在するとして、多項式ｆ（ｘ）が条件（＊）を満たさないと仮定する。このとき、区間数の端点に固定されていない係数（２つ以上あるとする。）を２つ選択し、これをｐおよびｑとする。
ここで記号αを境界Ｃ上の点を表すパラメータとして、ｆ（α）の実部および虚部を式（９）の如く表記することにする。なお、上記では記号αを零点、ｐを区分境界の指標、ｑを係数としたが、ここでの説明では異なる定義であることに留意すること。
【数７】
2007148815.tif 000009
【００６０】
点αにおいて多項式ｆ（α）が０になることは、ｐおよびｑの２変数連立一次方程式（１０）が成立することである。
【数８】
2007148815.tif 000010
【００６１】
点ｄは零点であるから、α＝ｄでは、所定の範囲（区間数内）に収まっている連立方程式（１０）の解ｐ、ｑが存在する（このｐ、ｑは、点ｄを零点とする多項式ｆ（ｘ）の係数ｐおよびｑに対応する。）。
ここでα＝ｄにおいて行列式（１１）が０とすると、連立方程式の解が不定であるならば、ｐおよびｑを解としたまま、少なくともその１つを区間数の端点となるまで動かすことができる。また、連立方程式の解が存在しないのであるならば、パラメータαが行列式（１１）を０にする値に近付くとき、ｐ、ｑのうち少なくとも一方は∞あるいは−∞に発散するから、その前に区間数の端点に達することとなる。これは、上記仮定：「境界Ｃ上の点ｄを零点とする多項式ｆ（ｘ）∈Ｆ（ｘ）が存在するとして、多項式ｆ（ｘ）が条件（＊）を満たさない」と矛盾する。なお記号≡は「定義」を表す。
【数９】
2007148815.tif 000011
【００６２】
従って、行列式（１１）はα＝ｄにおいて０ではないとする。点αを境界Ｃ上において点ｄから動かしていくと、点αが点ｃに到達する前に、次のいずれかが起こる。もし、いずれも起こらずに点ｃに到達したとすると、「点ｃを零点とする多項式が実区間多項式Ｆ（ｘ）に存在しない」とする前提と矛盾する。なお、α０は点ｄおよび点ｃの間にある境界Ｃ上の点である。
（ｉ）ｐが区間数の端点に到達する。
（ｉｉ）ｑが区間数の端点に到達する。
（ｉｉｉ）行列式（１１）が、α＝α０において０になる。
【００６３】
（ｉ）（ｉｉ）の場合は、多項式ｆ（ｘ）の係数のうち区間数の端点とならないものの個数が多項式ｆ（ｘ）の場合よりも１つ小さい多項式であって、領域Ｄの境界Ｃ上に零点を持つ多項式ｇ（ｘ）∈Ｆ（ｘ）が存在することを示している。
【００６４】
（ｉｉｉ）の場合は、後述の《補足説明》で説明するように、行列式（１１）が０となる点において、連立方程式（１０）は不定となるので、ｐおよびｑを解としたまま、少なくともその１つを区間数の端点となるまで動かすことができる。つまり、多項式ｆ（ｘ）の係数のうち区間数の端点とならないものの個数が多項式ｆ（ｘ）の場合よりも１つ小さい多項式であって、領域Ｄの境界Ｃ上に零点を持つ多項式ｇ（ｘ）∈Ｆ（ｘ）が存在することを示している。
【００６５】
結局、以上から、点ｃを零点とする多項式が実区間多項式Ｆ（ｘ）に存在しない場合、境界Ｃ上に零点を持つ多項式が存在するとしたとき、境界Ｃ上の点ｄを零点とする条件（＊）を満たさない多項式ｆ（ｘ）∈Ｆ（ｘ）に対して、多項式ｆ（ｘ）の係数のうち区間数の端点とならないものの個数が多項式ｆ（ｘ）の場合よりも１つ小さい多項式であって、領域Ｄの境界Ｃ上に零点を持つ多項式ｇ（ｘ）∈Ｆ（ｘ）が存在することが言えた。以上のような操作を（区間数の端点に固定されていない係数が３つ以上ある場合に）必要に応じて繰り返せば、条件（＊）を満たす多項式ｇ（ｘ）∈Ｆ（ｘ）で、領域Ｄの境界Ｃ上に零点を持つものが存在することが言える。つまり、点ｃを零点とする多項式が実区間多項式Ｆ（ｘ）に存在しない場合には、[ａ]が成立するか否かの判定に帰着できる。
【００６６】
《補足説明》
補足説明では、行列式（１１）が０となる点において、連立方程式（１０）が不定となることを説明する。
ここで、ｎｐ（α）、ｎｑ（α）を式（１２）によって定義する。ここでのｐ、ｑは、上記と同様、２つ選択された区間数の端点に固定されていない係数を意味する。
【数１０】
2007148815.tif 000012
【００６７】
連立方程式（１０）の解ｐ、ｑは、αの関数として、式（１３）によって表される。
【数１１】
2007148815.tif 000013
【００６８】
αがα０に近づくとき、Ｄ（α）は０に収束するから、ｎｐ（α）、ｎｑ（α）も０に収束する。収束することは、全ての係数がαの連続関数として表すことができることから保証されており、もし収束値が０以外ならば、αがα０に到達する前まで連立方程式（１０）の解が有界であることに矛盾する。ｎｐ（α）、ｎｑ（α）はαについて連続であるから、結局、式（１４）が成り立つ。
【数１２】
2007148815.tif 000014
【００６９】
さらに、ａｊ（α０）＝ｂｊ（α０）＝０ならば〔但し、ここでのｊは、ｊ＝１，２とする。〕、ｃｊ（α０）＝０が成り立つ。なぜなら、ある正数Ｍがあって、αが境界Ｃ上において点α０に近づくとき、常に不等式｜ｐ（α）｜≦Ｍ、｜ｑ（α）｜≦Ｍが成立するので、三角不等式から式（１５）が成立する。
【数１３】
2007148815.tif 000015
【００７０】
αが境界Ｃ上において点α０に近づくとき、（｜ａｊ（α）｜＋｜ｂｊ（α）｜）Ｍは０に収束するから、ｃｊ（α）も０に収束する。そして、ｃｊ（α）は連続であることからｃｊ（α０）＝０が成り立つ。
【００７１】
この準備の下、次の３通りに分けて証明する。
（ｉ）ａ１（α０）＝ａ２（α０）＝０の場合について。もしｂ１（α０）≠０ならば、行列式（１１）から、連立方程式（１０）の第２式は第１式のｂ２（α０）／ｂ１（α０）倍となる。ここでｂ１（α０）≠０から、連立方程式（１０）が不定であることがわかる。もしｂ１（α０）＝０ならば、上記の準備からｃ１（α０）＝０となり、連立方程式（１０）は第２式のみとなる。このとき、ｂ２（α０）＝０ならば、やはり上記準備からｃ２（α０）＝０となり、第２式もなくなる。ｂ２（α０）≠０ならば第２式は残るが、解は不定である。
【００７２】
（ｉｉ）ａ１（α０）およびａ２（α０）のうち、一方が０であり、他方が０ではない場合について。この場合、ａ１（α０）＝０、ａ２（α０）≠０の場合について示せば十分である。上記のＤ（α０）＝０から、ｂ１（α０）＝０となる。従って、上記準備からｃ１（α０）＝０となる。つまり、連立方程式（１０）は第２式のみに退化し、ａ２（α０）≠０から解は不定であることがわかる。
【００７３】
（ｉｉｉ）ａ１（α０）およびａ２（α０）が共に０ではない場合について。この場合、上記のＤ（α０）＝０および行列式（１１）から、連立方程式（１０）において、第２式は第１式のａ２（α０）／ａ１（α０）倍となる。従って、ａ１（α０）≠０から解は不定であることがわかる。
以上で《補足説明》は終わりである。
【００７４】
さて、以上から、上記［ｂ］については各区分境界について調べることなく、領域Ｄの境界Ｃ上の任意の１点（上記点ｃに相当する。）を選択して、この１点を零点とする多項式が実区間多項式Ｆ（ｘ）に存在するか否かを調べればよい。
そこで、この方法について具体的に説明する。以下では、アルゴリズムを簡単かつ効率良くするため、エッジ多項式と限らない範囲で調べるとする。また、上記点ｃを便宜からαに記号の置き換えをする。
【００７５】
今、多項式ｅｊ（ｘ）＝ｘｊとして例示説明しているので、式（４）の実区間多項式Ｆ（ｘ）は、式（１６）と表せる（右辺のみを表記する。）。
【数１４】
2007148815.tif 000016
【００７６】
変数ｘを点αとして、これを式（１６）に代入する。このとき式（１６）は式（１７）と表せる。また、式（１７）を式変形すると、式（１８）と表せる。
【数１５】
2007148815.tif 000017
【００７７】
式（１８）を満足するｔｊの組み合わせが存在するならば、それは、この点αを零点とする多項式が実区間多項式Ｆ（ｘ）に存在することを意味する。ここで留意しなければならないのは、ｔｊの組み合わせを特定することではなく、「式（１８）を満足するｔｊの組み合わせが存在するか否か」である。そうすると、（ｕｊ−ｍｊ）αｊｔｊを、「（ｕｊ−ｍｊ）αｊを、複素平面原点を始点、点（ｕｊ−ｍｊ）αｊを終点とするベクトルとみなし、このベクトルをｔｊによってスカラー倍したものである」−つまり当該ベクトルをｔｊスカラー倍したベクトルの終点が（ｕｊ−ｍｊ）αｊｔｊである−と見れば、０≦ｔｊ≦１によって式（１８）の左辺が取り得る複素平面上の範囲に、式（１８）の右辺の点が存在するか否かを調べればよい。つまり、凸包に或る１点が存在するか否かの判定に持ち込むことを考えればよい。そこで、このような凸包を用いた判定を効率良く行うために、前処理を行う。
【００７８】
まず、式（１８）の左辺の各項（ｊ＝０，１，…，ｄ）を順番に見ていき、各項について次のような判定と書き換えを行う。まず、（ｕｊ−ｍｊ）αｊの実部が負であるかを判定する。負である場合には、（ｕｊ−ｍｊ）αｊｔｊを（ｕｊ−ｍｊ）αｊ（１−ｔｊ）に書き換える。次に、（ｕｊ−ｍｊ）αｊの実部が負でない場合は、（ｕｊ−ｍｊ）αｊの実部が０かつ虚部が負であるか否かを判定する。実部が０かつ虚部が負である場合には、（ｕｊ−ｍｊ）αｊｔｊを（ｕｊ−ｍｊ）αｊ（１−ｔｊ）に書き換える。
なお、この操作は式（１７）において、（ｕｊ−ｍｊ）αｊの実部が負である場合に｛（ｕｊ−ｍｊ）ｔｊ＋ｍｊ｝αｊを｛（ｕｊ−ｍｊ）（１−ｔｊ）＋ｍｊ｝αｊと書き換え、（ｕｊ−ｍｊ）αｊの実部が０かつ虚部が負である場合に｛（ｕｊ−ｍｊ）ｔｊ＋ｍｊ｝αｊを｛（ｕｊ−ｍｊ）（１−ｔｊ）＋ｍｊ｝αｊと書き換えることと同じである。
【００７９】
以上の操作は、例えば、実部が負であるベクトル（ｕｊ−ｍｊ）αｊをｔｊスカラー倍（０≦ｔｊ≦１）することは、複素平面原点対象に移動したベクトル（ｕｊ−ｍｊ）αｊ×（−１）をｈｊスカラー倍（−１≦ｈｊ≦０）することと同じであるから、ｔｊの範囲が０≦ｔｊ≦１であることに留意してｈｊ＝ｔｊ−１とおくと、（ｕｊ−ｍｊ）αｊ×（−１）×ｈｊは、（ｕｊ−ｍｊ）αｊ×（１−ｔｊ）となることに基づく。このような操作を行うことで、式（１８）の左辺の点（ｕｊ−ｍｊ）αｊは、見かけ上、全て複素平面の右半平面（実部が０以上の領域全体、但し、実部が０かつ虚部が負の部分は除く。）に集められるとともに、複素平面の虚軸の負の部分には点が乗らないものとなる。換言すれば、この操作の結果得られた点集合は、複素平面原点を頂点とする凸包を複素平面の右半平面で構成する（但し、複素平面の虚軸の負の部分に凸包の頂点はない。）。
【００８０】
なお、このような操作は、後述の凸包を求めるための便宜としての前処理であるから、上記に限定されるものではない。例えば、（ｕｊ−ｍｊ）αｊの実部が正であるかを判定し、正である場合には、（ｕｊ−ｍｊ）αｊｔｊを（ｕｊ−ｍｊ）αｊ（１−ｔｊ）に書き換え、（ｕｊ−ｍｊ）αｊの実部が正でない場合は、（ｕｊ−ｍｊ）αｊの実部が０かつ虚部が負であるか否かを判定する。そして、実部が０かつ虚部が負である場合には、（ｕｊ−ｍｊ）αｊｔｊを（ｕｊ−ｍｊ）αｊ（１−ｔｊ）に書き換える（つまり、複素平面原点を頂点とする凸包を複素平面左側で構成する。）、といった操作などに適宜に変更できる。
【００８１】
以上の操作の結果を式変形して式（１９）を得る。
【数１６】
2007148815.tif 000018
【００８２】
結局、式（１９）を満たすようなｔｊの組み合わせが存在するか否かの判定となるが、これは、εｊ＝０あるいはεｊ＝１とした場合に、式（２０）の全体、即ち複素平面上で高々２ｄ＋１個の点の凸包にｂが入るか否かの判定と同じである。なお、式（１９）を得る際の上記操作から、式（２０）の全体のなす凸包は、複素平面の右半平面（但し、実部が０かつ虚部が負の部分は除く。）に存在することがわかる。従って、式（１９）の右辺のｂの実部が負の場合、あるいは、ｂの実部が０かつ虚部が負の場合、凸包を具体的に構成しなくてもｂが式（２０）の全体のなす凸包に入らないことがわかることに留意するべきである。
【数１７】
2007148815.tif 000019
【００８３】
そこで、まず、式（２０）で表される点の全体の凸包を求める。これは、効率的に求めることができる。
具体的にはまず、複素平面の虚軸の負の部分を除く複素平面の右半平面の領域（−π／２＜ａｒｇ≦π／２、ａｒｇは角度を表す。）において、ａｊを傾き（複素平面上の偏角）でソートする。つまり、ベクトルａｊの複素平面上の偏角を、−π／２＜θ≦π／２で、小さい方から大きい方へと順番に並び替える。但し、同じ傾きのものがあるときには、それらを全部足したものに置き換えたものを１つとしてソートする。例えば、ａｊおよびａｋの傾きが同じときには、ａｊ，ａｋの代わりに、ａｊ＋ａｋを対象としてソートする。なぜなら、傾きが同じ点ａｊおよび点ａｋは複素平面上において凸包の頂点となりえないからである（凸包の頂点の可能性があるのは、同じ傾きのものを全てベクトル加算した点である。）。このソートの結果をｖ１，…，ｖｎとする。なお、ｎはｄ＋１より小さいことがあることに留意すること。
【００８４】
このとき、求める複素平面上の凸包の頂点は、複素平面原点（０と表記する。）から始めて反時計回りに、０，ｖ１，ｖ１＋ｖ２，…，ｖ１＋…＋ｖｎ，ｖ２＋ｖ３＋…ｖｎ，ｖ３＋…＋ｖｎ，…，ｖｎ−１＋ｖｎ，ｖｎの全部で２ｎ個となる。この凸包に式（１９）の右辺ｂが入るか否かを判定する。この判定は公知のアルゴリズムによって達成するから説明を省略する（参考文献５参照。）。点ｂが凸包に入る場合には、実区間多項式Ｆ（ｘ）は領域Ｄ（境界Ｃ上あるいは境界Ｃの内部）に零点を有すると判定できる。
（参考文献５）  Franco P. Preparata（原著）、Michael Ian Shamos（原著）、浅野孝夫（翻訳）、浅野哲夫（翻訳）、「計算幾何学入門」、総研出版、１９９２．
【００８５】
以上のアルゴリズムに基づく上記＜ステップ３＞の処理フローを一例として図３に示す。
まず、境界Ｃ上の任意の１点αを選択する（ステップＳ４００）。次に、選択した点αをｘ＝αとして実区間多項式Ｆ（ｘ）に代入する（ステップＳ４０１）。パラメータｊを０に設定する（ステップＳ４０２）。このパラメータｊに対応する（ｕｊ−ｍｊ）αｊの実部が負であるかを判定する（ステップＳ４０３）。負である場合には、（ｕｊ−ｍｊ）αｊｔｊを（ｕｊ−ｍｊ）αｊ（１−ｔｊ）に書き換える（ステップＳ４０５）。もし（ｕｊ−ｍｊ）αｊの実部が負でない場合は、（ｕｊ−ｍｊ）αｊの実部が０かつ虚部が負であるか否かを判定する（ステップＳ４０４）。実部が０かつ虚部が負である場合には、（ｕｊ−ｍｊ）αｊｔｊを（ｕｊ−ｍｊ）αｊ（１−ｔｊ）に書き換える（ステップＳ４０５）。そしてパラメータｊがｄと等しいか否かを判定する（ステップＳ４０６）。ｊ≠ｄであれば、ｊに１加えたものを新たなｊとして（ステップＳ４０７）、ステップＳ４０３〜Ｓ４０６の処理を行う。ｊ＝ｄであれば、ステップＳ４０３〜Ｓ４０６の処理で得られた実区間多項式を式（１９）の如く式変形する（ステップＳ４０８）。次に、ステップＳ４０８の処理で得られた式（１９）の右辺で表される点ｂの実部が負であるか否かを判定する（ステップＳ４０８ｘ）。点ｂの実部が負であれば、点ｂがステップＳ４０８の処理で得られた式（１９）の左辺で表される点全体の凸包に入ることはないので、任意に選択された点αを零点とする多項式が実区間多項式Ｆ（ｘ）に存在しないといえる（ステップＳ４１１）。点ｂの実部が負でなければ、ステップＳ４０８ｙの処理を行う。即ち、ステップＳ４０８の処理で得られた式（１９）の右辺で表される点ｂの実部が０かつ虚部が負であるか否かを判定する（ステップＳ４０８ｙ）。点ｂの実部が０かつ虚部が負であれば、点ｂがステップＳ４０８の処理で得られた式（１９）の左辺で表される点全体の凸包に入ることはないので、任意に選択された点αを零点とする多項式が実区間多項式Ｆ（ｘ）に存在しないといえる（ステップＳ４１１）。点ｂの実部が０かつ虚部が負でなければ、ステップＳ４０９の処理を行う。即ち、ステップＳ４０８の処理で得られた式（１９）の左辺で表される点全体の凸包を上記のアルゴリズムに従って求める（ステップＳ４０９）。次に、ステップＳ４０８の処理で得られた式（１９）の右辺で表される点が、ステップＳ４０９で求められた凸包に入るか否かを判定する（ステップＳ４１０）。凸包に入れば、任意に選択された点αを零点とする多項式が実区間多項式Ｆ（ｘ）に存在するといえる（ステップＳ４１２）。凸包に入らなければ、任意に選択された点αを零点とする多項式が実区間多項式Ｆ（ｘ）に存在しないといえる（ステップＳ４１１）。
以上で《ステップ３の詳細》の説明は終わりである。
【００８６】
《ステップ４の詳細》
上記点ｂが凸包に入らない場合は、境界Ｃの各区分境界について上記［ａ］、即ち「高々１つの係数を除き係数が区間数の端点となっている多項式(エッジ多項式)ｇ（ｘ）∈Ｆ（ｘ）であって、その零点が区分境界Ｃｐ上にあるものが存在する」が成立するか否かを調べることとなる。そこで、この方法を説明する。
【００８７】
エッジ多項式において区間数の端点に固定されていない係数をｔとして、連立方程式ｕ（ｓ）＝ｖ（ｓ）＝０を、係数ｔも明記してｕ（ｓ，ｔ）＝ｖ（ｓ，ｔ）＝０と表すことにする。この連立方程式は、係数ｔについては一次であるから、ｕ（ｓ，ｔ）＝０，ｖ（ｓ，ｔ）＝０それぞれからｔについて解いて、ｔ＝ｈ１（ｓ）＝ｈ２（ｓ）と表すことができる。但し、ｈ１、ｈ２ともにパラメータｓの有理数係数有理式である。ここで、ｈ１（ｓ）−ｈ２（ｓ）を既約な有理式として表したときの分子である多項式をＰ（ｓ）とし、パラメータｓの動く範囲をＳとする。Ｓは、閉区間［ａ，ｂ］、左閉右開区間［ａ，∞）、右閉左開区間（−∞，ｂ］、開区間（−∞，∞）のいずれかである。
なお、上記係数ｔが、実区間多項式Ｆ（ｘ）における定数項〔即ち、式（１６）で言えばｊ＝０の項〕の区間数の端点に固定されていない係数である場合、虚部に係わる方程式ｖ（ｓ，ｔ）＝０は、パラメータｓのみの方程式となるから係数ｔについて解くことができない。そこで、このような場合には、ｖ（ｓ）を既約な有理式で表したときの分子をＰ（ｓ）とする。
【００８８】
そうすると、解くべき問題は、「有理数係数一変数代数方程式Ｐ（ｓ）＝０のＳに入る実根をαとしたとき、有理数係数有理式Ｈ（ｓ）〔ｈ１（ｓ），ｈ２（ｓ）のどちらでも同じなので、いずれか一方とする。〕について、係数ｔが属する区間数の端点ｍ，ｕに対してｍ≦Ｈ（α）≦ｕが成立するか否かを判定せよ」となる。
但し、上記のように係数ｔが、実区間多項式Ｆ（ｘ）における定数項〔式（１６）で言えばｊ＝０の項〕の区間数の端点に固定されていない係数である場合、解くべき問題は、「有理数係数一変数代数方程式Ｐ（ｓ）＝０のＳに入る実根をαとしたとき、有理数係数有理式Ｈ（ｓ）〔上記方程式ｕ（ｓ，ｔ）＝０をｔについて解いた有理数係数有理式である。〕について、係数ｔが属する区間数の端点ｍ０，ｕ０に対してｍ０≦Ｈ（α）≦ｕ０が成立するか否かを判定せよ」となる。
【００８９】
これを解くために、Ｈ（ｓ）−ｍを既約な有理式として表したときの分子である多項式と多項式Ｐ（ｓ）との最大公約多項式Ｇｍ（ｓ）および、Ｈ（ｓ）−ｕを既約な有理式として表したときの分子である多項式と多項式Ｐ（ｓ）の最大公約多項式Ｇｕ（ｓ）を求める。Ｇｍ（ｓ）とＧｕ（ｓ）は互いに素であるから〔Ｇｍ（ｓ）の根ηに対してＨ（η）＝ｍとなり、Ｇｕ（ｓ）の根τに対してＨ（τ）＝ｕとなるから。〕、多項式Ｐ（ｓ）の根は、Ｇｍの根、Ｇｕの根、Ｐ（ｓ）／（Ｇｍ（ｓ）Ｇｕ（ｓ））の根の３種類に分かれる。
【００９０】
Ｇｍ（ｓ）あるいはＧｕ（ｓ）の根については、この根がＳに属するか否かの判定のみを行えば十分であり、これは、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/〉［平成１７年１１月１５日検索］を参照のこと。）。
【０１１４】
まず、零点位置判定装置（１）の制御部（１９０）は、外部記憶装置（１７）から全ての区間数Ａｊ＝｛（ｕｊ−ｍｊ）ｔｊ＋ｍｊ｝、各区分境界Ｃｐ〔但し、ｐ＝１，２，・・・，ｎ〕を表現する有理数係数有理式φｐ（ｓ）、ψｐ（ｓ）、パラメータｓの取り得る範囲Ｓｐ、実区間多項式Ｆ（ｘ）の最高次数ｄ、領域Ｄに含まれる１点の複素平面上の座標λ、境界Ｃが閉曲線であるか否かを表す情報ξを読み込み、それぞれをＲＡＭ（１５）の所定の格納領域に格納しておく。以後、「ＲＡＭから○○を読み込む」旨の説明をした場合は、「ＲＡＭにおいて○○が格納されている所定の格納領域から○○を読み込む」ことを意味するとする。
【０１１５】
境界種判定制御部（１４０）は、ＲＡＭ（１５）から、境界Ｃが閉曲線であるか否かを表す情報ξを読み込み、情報ξに応じてステップＳ２０の処理またはステップＳ２２の処理のいずれかを実行するように制御する（ステップＳ１）。例えば、予め、境界Ｃが閉曲線である場合にはξ＝１を入力し、境界Ｃが閉曲線でない場合にはξ＝０を入力すると規約しておく。境界種判定制御部（１４０）は、当該既約の下に入力された情報ξがξ＝１の場合には、ステップＳ２０の処理を実行し、情報ξがξ＝０の場合には、ステップＳ２２の処理を実行するように制御する。
【０１１６】
第１反復制御部（１９１）は、ＲＡＭ（１５）からｄを読み込み、パラメータσの値をｄに設定し、このσをＲＡＭ（１５）の所定の格納領域に格納する（ステップＳ２２）。
【０１１７】
第１次数判定制御部（１４１）は、ＲＡＭ（１５）から、実区間多項式Ｆ（ｘ）の全ての区間数Ａｊ＝｛（ｕｊ−ｍｊ）ｔｊ＋ｍｊ｝およびσを読み込み、このσで特定される区間数Ａσが複素平面上の原点を含むか否かを判定し、この判定結果に基づき、ステップＳ３１の処理またはステップＳ２４の処理のいずれかを実行するように制御する（ステップＳ２３）。
【０１１８】
（（原点を含む場合−ステップＳ２４））
第１反復制御部（１９１）は、ＲＡＭ（１５）からσを読み込み、σ＝０が成立するか否かを判定する（ステップＳ２４）。そして、第１反復制御部（１９１）は、この判定結果が、σ＝０が成立するというものである場合には、「実区間多項式Ｆ（ｘ）に属する多項式は領域Ｄに零点を有する」ことを表す情報θ（例えばこの場合は、θ＝１とする。）をＲＡＭ（１５）の所定の格納領域に格納する（ステップＳ２５）。なぜなら、この場合、実区間多項式Ｆ（ｘ）は単項式Ｆ（ｘ）＝Ａ０であるといえ、さらにステップＳ２３において区間数Ａ０が原点を含むと判定されているので、実区間多項式Ｆ（ｘ）に属する多項式が領域Ｄに零点を有するといえるからである。なお、図１５において、[・]は、場合によって返り値があることを示している。
第１反復制御部（１９１）は、判定結果が、σ＝０が成立しないというものである場合には、ステップＳ２６の処理を実行するように制御する。
【０１１９】
第２次数判定制御部（１４１８）は、ＲＡＭ（１５）から、実区間多項式Ｆ（ｘ）の全ての区間数Ａｊ＝｛（ｕｊ−ｍｊ）ｔｊ＋ｍｊ｝およびσを読み込み、このσで特定される区間数Ａσが複素平面上の原点と等しいか否か（つまり、Ａσ＝[０，０]が成立するか否か）を判定し、この判定結果に基づき、ステップＳ２７の処理またはステップＳ２８の処理のいずれかを実行するように制御する（ステップＳ２６）。
【０１２０】
（（原点と等しい場合−ステップＳ２７））
第１反復制御部（１９１）は、ＲＡＭ（１５）からσを読み込み、σの値から１を引いて、このσをＲＡＭ（１５）の所定の格納領域に格納する（ステップＳ２７）。続いて、第１反復制御部（１９１）は、ステップＳ２３以降の処理を実行するように制御する。
【０１２１】
ステップＳ２２、Ｓ２３、Ｓ２４、Ｓ２６、Ｓ２７の一連の処理は、見かけだけの最高次数を排除し（つまり、最高次数の区間数が[０，０]として与えられている項を排除する。）、実質的に真の最高次数を決定するために行うものである。
【０１２２】
（（原点に等しくない場合−ステップＳ２８））
恒等式判定制御部（１４１７）は、ＲＡＭ（１５）から、全ての区間数Ａｊ＝｛（ｕｊ−ｍｊ）ｔｊ＋ｍｊ｝を読み込み、各区間数がそれぞれ複素平面上の原点を含むか否かを判定する（ステップＳ２８）。そして、恒等式判定制御部（１４１７）は、この判定結果が、各区間数がそれぞれ複素平面上の原点を含むというものである場合には、「実区間多項式Ｆ（ｘ）に属する多項式は領域Ｄに零点を有する」ことを表す情報θ（例えばこの場合は、θ＝１とする。）をＲＡＭ（１５）の所定の格納領域に格納する（ステップＳ２９）。なぜなら、この場合、実区間多項式Ｆ（ｘ）が恒等的に０となる場合があるので、実区間多項式Ｆ（ｘ）に属する多項式が領域Ｄに零点を有するといえるからである。
恒等式判定制御部（１４１７）は、判定結果が、各区間数がそれぞれ複素平面上の原点を含むとはいえない（つまり、複素平面上原点を含まない区間数が存在するということ。）というものである場合には、零点位置判定処理を終了するように制御する（ステップＳ２８ａ）。なぜなら、上記理論において説明したように、境界Ｃが閉曲線でない場合には、実区間多項式Ｆ（ｘ）に属する多項式の次数が一定である必要があるところ、この条件を満たさないからである（ステップＳ２３で区間数が原点を含むと判定されていることに留意すること。）。
【０１２３】
（（原点を含まない場合−ステップＳ３１））
交点判定部（１４２）は、ＲＡＭ（１５）から、全ての区間数Ａｊ＝｛（ｕｊ−ｍｊ）ｔｊ＋ｍｊ｝、各区分境界Ｃｐ〔但し、ｐ＝１，２，・・・，ｎ〕を表現する有理数係数有理式φｐ（ｓ）、ψｐ（ｓ）、パラメータｓの取り得る範囲Ｓｐ、σを読み込む。そして、交点判定部（１４２）は、実区間多項式Ｆ（ｘ）の最高次数〔ステップＳ２３におけるσで定まる。〕の項の区間数の絶対値の最小値ｍ、実区間多項式Ｆ（ｘ）の最高次数の項以外の項〔つまり、ｊ＝０，１，・・・σ−１で定まる項である。〕の区間数の絶対値の最大値Ｍをそれぞれ求め、原点中心の半径１＋Ｍ／ｍの円と境界Ｃとが交点を有するか否かを判定する。つまり、複素平面上において、原点中心の半径１＋Ｍ／ｍの円と、各区分境界Ｃｐ〔但し、ｐ＝１，２，・・・，ｎ〕であるφｐ（ｓ）＋ｉ・ψｐ（ｓ）とがｓ∈Ｓｐにおいて交点を有するか否かを判定する。交点を有する場合には、交点を有することを表す判定結果ν（例えばこの場合は、ν＝１とする。）およびその交点の複素平面上における座標μ（当然、交点は１つ以上である。）をＲＡＭ（１５）の所定の格納領域に格納する。交点を有しない場合には、交点を有しないことを表す判定結果ν（例えばこの場合は、ν＝０とする。）をＲＡＭ（１５）の所定の格納領域に格納する（ステップＳ３１）。なお、上記ｍおよびＭもＲＡＭ（１５）の所定の格納領域に格納する。
【０１２４】
制御部（１９０）は、ＲＡＭ（１５）からステップＳ３１において格納された判定結果νを読み込み、この判定結果が、交点を有しないというものである場合には、ステップＳ３２の処理を実行するように制御する。
制御部（１９０）は、判定結果νが交点を有するというものである場合には、ステップＳ３１ａの処理を実行するように制御する。
【０１２５】
ステップＳ３２の処理は次のとおりである。
即ち、共通領域判定部（１４３）は、ＲＡＭ（１５）から、各区分境界Ｃｐ〔但し、ｐ＝１，２，・・・，ｎ〕を表現する有理数係数有理式φｐ（ｓ）、ψｐ（ｓ）、パラメータｓの取り得る範囲Ｓｐ、領域Ｄに含まれる１点の複素平面上の座標λを読み込み、領域Ｄが複素平面上の原点を含むか否かを判定する（ステップＳ３２）。そして、共通領域判定部（１４３）は、この判定結果が、領域Ｄが複素平面上の原点を含まないというものである場合には、「実区間多項式Ｆ（ｘ）に属する多項式は領域Ｄに零点を有しない」ことを表す情報θ（例えばこの場合は、θ＝０とする。）をＲＡＭ（１５）の所定の格納領域に格納する（ステップＳ３３）。なぜなら、この場合、上記理論において説明したとおり、実区間多項式Ｆ（ｘ）に属する多項式が領域Ｄに零点を有しないことは明らかだからである。
共通領域判定部（１４３）は、判定結果が、領域Ｄが複素平面上の原点を含むというものである場合には、「実区間多項式Ｆ（ｘ）に属する多項式は領域Ｄに零点を有する」ことを表す情報θ（例えばこの場合は、θ＝１とする。）をＲＡＭ（１５）の所定の格納領域に格納する（ステップＳ３４）。なぜなら、この場合、上記理論において説明したとおり、実区間多項式Ｆ（ｘ）に属する多項式が領域Ｄに零点を有することは明らかだからである。
【０１２６】
ステップＳ３１ａの処理は次のとおりである。
交点数判定制御部（１４１４）は、ＲＡＭ（１５）から、ステップＳ３１で得られた交点の座標μを読み込み、その交点の個数が１個であるか複数であるかを判定し、この判定結果に基づき、ステップＳ３１ｂの処理またはステップＳ３７の処理のいずれかを実行するように制御する（ステップＳ３１ａ）。
【０１２７】
（（交点が１個の場合−ステップＳ３１ｂ））
共通領域判定制御部（１４１５）は、ＲＡＭ（１５）から、各区分境界Ｃｐ〔但し、ｐ＝１，２，・・・，ｎ〕を表現する有理数係数有理式φｐ（ｓ）、ψｐ（ｓ）、パラメータｓの取り得る範囲Ｓｐ、領域Ｄに含まれる１点の複素平面上の座標λを読み込み、領域Ｄが複素平面上の原点を含むか否かを判定する（ステップＳ３１ｂ）。そして、共通領域判定制御部（１４１５）は、この判定結果が、領域Ｄが複素平面上の原点を含むというものである場合には、「実区間多項式Ｆ（ｘ）に属する多項式は領域Ｄに零点を有する」ことを表す情報θ（例えばこの場合は、θ＝１とする。）をＲＡＭ（１５）の所定の格納領域に格納する（ステップＳ３１ｃ）。なぜなら、この場合、上記理論において説明したとおり、実区間多項式Ｆ（ｘ）に属する多項式が領域Ｄに零点を有することは明らかだからである。
共通領域判定制御部（１４１５）は、判定結果が、領域Ｄが複素平面上の原点を含まないというものである場合には、ステップＳ３１ｄの処理を実行するように制御する。
【０１２８】
対象点多項式第１判定部（１４１６）は、ＲＡＭ（１５）から、全ての区間数Ａｊ＝｛（ｕｊ−ｍｊ）ｔｊ＋ｍｊ｝、ステップＳ３１で得られた交点の座標μを読み込み、《ステップ３の詳細》で説明したアルゴリズムに従って、この交点を零点とする多項式が実区間多項式Ｆ（ｘ）に存在するか否かを判定する（ステップＳ３１ｄ）。なお、この判定処理では、図３に示した処理フローにおいてステップＳ４００の１点αを交点の座標μに置き換えたアルゴリズムとなる。この判定結果が、交点を零点とする多項式が実区間多項式Ｆ（ｘ）に存在しないというものである場合には（図３のステップＳ４１１参照。）、「実区間多項式Ｆ（ｘ）に属する多項式は領域Ｄに零点を有しない」ことを表す情報θ（例えばこの場合は、θ＝０とする。）をＲＡＭ（１５）の所定の格納領域に格納する（ステップＳ３１ｅ）。なぜなら、実区間多項式Ｆ（ｘ）に属するいかなる多項式もこの交点を零点としないことは、結局、実区間多項式Ｆ（ｘ）に属する多項式は領域Ｄに零点を有しないことと同じであるからである。
対象点多項式第１判定部（１４１６）は、判定結果が、交点を零点とする多項式が実区間多項式Ｆ（ｘ）に存在するというものである場合には（図３のステップＳ４１２参照。）、「実区間多項式Ｆ（ｘ）に属する多項式は領域Ｄに零点を有する」ことを表す情報θ（例えばこの場合は、θ＝１とする。）をＲＡＭ（１５）の所定の格納領域に格納する（ステップＳ３１ｆ）。なぜなら、この場合、この交点を零点とする実区間多項式Ｆ（ｘ）に属する多項式が存在することは、まさに実区間多項式Ｆ（ｘ）に属する多項式が領域Ｄに零点を有することと同じであるからである。
【０１２９】
（（交点が複数の場合−ステップＳ３７））
ステップＳ３７の処理は次のとおりである。
境界設定部（１４１０）は、ＲＡＭ（１５）から、各区分境界Ｃｐ〔但し、ｐ＝１，２，・・・，ｎ〕を表現する有理数係数有理式φｐ（ｓ）、ψｐ（ｓ）、パラメータｓの取り得る範囲Ｓｐ、ステップＳ３１において求められたＭおよびｍ、領域Ｄに含まれる１点の複素平面上の座標λを読み込み、新たに有界な領域Ｅの境界を設定する。ここで、新しい有界な領域Ｅとは、原点中心の半径１＋Ｍ／ｍの円の内部（円周を含む。）と領域Ｄとの共通部分を含み、且つ、領域Ｄの部分集合である有界な領域のことである。有界な領域Ｅの境界の設定について、図１６（ａ）および図１６（ｂ）を参照して具体的に説明する。図１６（ａ）は、半径１＋Ｍ／ｍの円と境界Ｃとが６個の交点（●で図示している。以下、同じ。）を有する場合を示している。図１６（ａ）における斜線部は、原点中心の半径１＋Ｍ／ｍの円の内部（円周を含む。）と領域Ｄとの共通部分を示している。図１６（ｂ）は、境界Ｃ、２個の交点を有する原点中心の半径Ｒの円などの関係を示している。図１６（ｂ）における斜線部は、領域Ｅを示している。なお、図１６（ａ）および図１６（ｂ）における境界Ｃは、各区分境界Ｃｐから構成されるものの、図示の便宜から明示していないことに留意すること。
まず、半径Ｒが１＋Ｍ／ｍ以上の円と境界Ｃとの交点が２個になるような半径Ｒの円を設定する。このような円の半径Ｒは、初期半径を１＋Ｍ／ｍとして境界Ｃとの交点が２個であるか否かを判定し、２個でない場合には、この半径を２倍（半径を拡大できるなら何倍でもよいが、一例として２倍にしている。）にして境界Ｃとの交点が２個であるか否かを判定することを繰り返すことで得られる。仮に、このような繰り返し処理によって交点が２個未満になった場合は、そもそも境界Ｃ（より正確には、境界Ｃを表現する区分境界Ｃｐ）が適正なものでなかったことになるから、零点位置判定処理を終了するなど適宜に制御すればよい。交点が２個になった場合の交点座標をそれぞれη１、η２とする。次に、境界Ｃにおける交点η１、η２の間の部分と、半径Ｒの円周における交点η１、η２の間の部分（円弧）とを、交点η１、η２において接続する。この結果得られた有界領域が領域Ｅである。なお、半径Ｒの円周は複素平面上において式（２１）の２つ区分境界Ｃcircle1、Ｃcircle2によって表される。
【数１８】
2007148815.tif 000020
【０１３０】
交点η１、η２は、半径Ｒの円周を２個の円弧に分割するところ、いずれか一方の円弧を、領域Ｅの境界を構成する円弧として決定しなければならない。この決定は、次のようにして行えばよい。まず、半径Ｒの円周上で任意の１点η３を選択する。但し、点η３は、交点η１、η２とは異なるとする。次に、領域Ｄに含まれる１点の複素平面上の座標λと点η３とを結んだ線分と、境界Ｃとの交点を求める。この交点が存在しない場合は、点η３がある円弧を、領域Ｅの境界を構成する円弧として決定する。もし、交点が存在する場合には、重複度を含めてその交点の個数を計数する（あるいは、点η３を選択し直して、全ての交点の重複度を１としてから交点の個数を計数するとしてもよい。）。この計数された個数が偶数の場合は、点η３がある円弧を、領域Ｅの境界を構成する円弧として決定する。この計数された個数が奇数の場合は、点η３がない円弧を、領域Ｅの境界を構成する円弧として決定する。図１６（ｂ）では、参考として、点η３および点η３’を選択した場合における、領域Ｄに含まれる１点の複素平面上の座標λと点η３ないし点η３’とを結んだ線分と境界Ｃとの交点の個数を示している。
境界設定部（１４１０）は、領域Ｅの境界を表現する区分境界Ｃｐを表現する有理数係数有理式φｐ（ｓ）、ψｐ（ｓ）、パラメータｓの取り得る範囲ＳｐをＲＡＭ（１５）の所定の格納領域に格納する〔説明の便宜上、領域Ｄに対する境界Ｃを表現する記号Ｃｐ、φｐ（ｓ）、ψｐ（ｓ）、Ｓｐを流用していることに留意すること。〕（ステップＳ３７）。
仮に実区間多項式Ｆ（ｘ）の零点が存在するとすれば、それは半径１＋Ｍ／ｍの円の境界およびその内部であるから、この円と領域Ｄとの共通部分を内包する有界な領域Ｅにおいて零点の有無を調べることは、領域Ｄにおいて零点の有無を調べることと同値であることにも留意する。
【０１３１】
制御部（１９０）は、ステップＳ３７に続き、ステップＳ３７１以降の処理を実行するように制御する。
【０１３２】
代表多項式選択部（１４５）は、ＲＡＭ（１５）から、全ての区間数Ａｊ＝｛（ｕｊ−ｍｊ）ｔｊ＋ｍｊ｝を読み込み、各区間数から１つずつ任意に値ａｊ∈Ａｊを選択し、これらの値ａｊをＲＡＭ（１５）の所定の格納領域に格納する（ステップＳ３７１）。以下、これらの値ａｊを各項の係数に有する多項式を代表多項式ｆ（ｘ）と呼ぶ。
【０１３３】
境界上零点判定制御部（１４６）は、ＲＡＭ（１５）から、ステップＳ３７１において選択された値ａｊ、各区分境界Ｃｐ〔但し、ｐ＝１，２，・・・，ｎ〕を表現する有理数係数有理式φｐ（ｓ）、ψｐ（ｓ）、パラメータｓの取り得る範囲Ｓｐ（領域Ｅの境界Ｃを表すことに留意。）を読み込み、Sturmの定理に基づくアルゴリズムに従って、代表多項式ｆ（ｘ）が、各区分境界Ｃｐからなる境界Ｃ上に零点を有するか否かを判定する（ステップＳ３７２）。そして、境界上零点判定制御部（１４６）は、この判定結果が、境界Ｃ上に零点が存在するというものである場合には、「実区間多項式Ｆ（ｘ）に属する多項式は領域Ｄに零点を有する」ことを表す情報θ（例えばこの場合は、θ＝１とする。）をＲＡＭ（１５）の所定の格納領域に格納する（ステップＳ３７３）。なぜなら、この場合、実区間多項式Ｆ（ｘ）に属する代表多項式が領域Ｅの境界Ｃ上に零点を有するので、結局、領域Ｄに零点を有することになるからである。
境界上零点判定制御部（１４６）は、判定結果が、境界Ｃ上に零点が存在しないというものである場合には、ステップＳ３７４の処理を実行するように制御する。
【０１３４】
領域内部零点判定制御部（１４７）は、ＲＡＭ（１５）から、ステップＳ３７１において選択された値ａｊ、各区分境界Ｃｐ〔但し、ｐ＝１，２，・・・，ｎ〕を表現する有理数係数有理式φｐ（ｓ）、ψｐ（ｓ）、パラメータｓの取り得る範囲Ｓｐ（領域Ｅの境界Ｃを表すことに留意。）を読み込み、偏角の原理に基づくアルゴリズムに従って、代表多項式ｆ（ｘ）が、各区分境界Ｃｐからなる境界Ｃで与えられる領域Ｅの内部に零点を有するか否かを判定する（ステップＳ３７４）。そして、領域内部零点判定制御部（１４７）は、この判定結果が、領域Ｅ内部に零点が存在するというものである場合には、「実区間多項式Ｆ（ｘ）に属する多項式は領域Ｄに零点を有する」ことを表す情報θ（例えばこの場合は、θ＝１とする。）をＲＡＭ（１５）の所定の格納領域に格納する（ステップＳ３７５）。なぜなら、この場合、実区間多項式Ｆ（ｘ）に属する代表多項式が領域Ｅ内部に零点を有することは、領域Ｄにおいて零点を有することになるからである。
領域内部零点判定制御部（１４７）は、判定結果が、領域Ｅ内部に零点が存在しないというものである場合には、ステップＳ３７６の処理を実行するように制御する。
【０１３５】
対象点多項式第２判定制御部（１４８）は、ＲＡＭ（１５）から、全ての区間数Ａｊ＝｛（ｕｊ−ｍｊ）ｔｊ＋ｍｊ｝、区分境界Ｃ１を表現する有理数係数有理式φ１（ｓ）、ψ１（ｓ）、パラメータｓの取り得る範囲Ｓ１（領域Ｅの境界Ｃの一部を表すことに留意。）を読み込み、《ステップ３の詳細》で説明したアルゴリズムに従って、範囲Ｓ１の端点のパラメータｓ１に対応する点α〔φ１（ｓ１）＋ｉ・ψ１（ｓ１）〕を零点とする多項式が実区間多項式Ｆ（ｘ）に存在するか否かを判定する（ステップＳ３７６）。なお、この判定処理では、図３に示した処理フローのステップＳ４００における任意の１点αを、区分境界Ｃ１を表現する有理数係数有理式φ１（ｓ）、ψ１（ｓ）について範囲Ｓ１の端点のパラメータｓ１に対応する点として与えるとした。勿論、各区分境界Ｃｐ〔但し、ｐ＝１，２，・・・，ｎ〕を表現する有理数係数有理式φｐ（ｓ）、ψｐ（ｓ）、パラメータｓの取り得る範囲Ｓｐ（領域Ｅの境界Ｃを表すことに留意。）をＲＡＭ（１５）から読み込み、各区分境界Ｃｐからなる境界Ｃ上の任意の１点αを選択するようにしてもよい。
対象点多項式第２判定制御部（１４８）は、この判定結果が、点αを零点とする多項式が実区間多項式Ｆ（ｘ）に存在するというものである場合には（図３のステップＳ４１２参照。）、「実区間多項式Ｆ（ｘ）に属する多項式は領域Ｄに零点を有する」ことを表す情報θ（例えばこの場合は、θ＝１とする。）をＲＡＭ（１５）の所定の格納領域に格納する（ステップＳ３７７）。なぜなら、この場合、この点αを零点とする実区間多項式Ｆ（ｘ）に属する多項式が存在することは、まさに実区間多項式Ｆ（ｘ）に属する多項式が領域Ｄに零点を有することと同じであるからである。
対象点多項式第２判定制御部（１４８）は、判定結果が、点αを零点とする多項式が実区間多項式Ｆ（ｘ）に存在しないというものである場合には（図３のステップＳ４１１参照。）、ステップＳ３７８の処理を実行するように制御する。
【０１３６】
次に、エッジ多項式判定部（１４９）は、ＲＡＭ（１５）から、全ての区間数Ａｊ＝｛（ｕｊ−ｍｊ）ｔｊ＋ｍｊ｝、各区分境界Ｃｐ〔但し、ｐ＝１，２，・・・，ｎ〕を表現する有理数係数有理式φｐ（ｓ）、ψｐ（ｓ）、パラメータｓの取り得る範囲Ｓｐ（領域Ｅの境界Ｃを表すことに留意。）を読み込み、《ステップ４の詳細》で説明したアルゴリズムに従って、境界Ｃ上に零点を有するエッジ多項式が実区間多項式Ｆ（ｘ）に存在するか否かを判定する（ステップＳ３７８）。
エッジ多項式判定部（１４９）は、この判定結果が、境界Ｃ上に零点を有するエッジ多項式が実区間多項式Ｆ（ｘ）に存在しないというものである場合には（図４のステップＳ５１４参照。）、「実区間多項式Ｆ（ｘ）に属する多項式は領域Ｄに零点を有しない」ことを表す情報θ（例えばこの場合は、θ＝０とする。）をＲＡＭ（１５）の所定の格納領域に格納する（ステップＳ３７１０）。なぜなら、上記理論から明らかなとおり、実区間多項式Ｆ（ｘ）に属するいかなるエッジ多項式も境界Ｃ上に零点を有しないことは、結局、実区間多項式Ｆ（ｘ）に属する多項式は領域Ｄに零点を有しないことと同じであるからである。
エッジ多項式判定部（１４９）は、判定結果が、境界Ｃ上に零点を有するエッジ多項式が実区間多項式Ｆ（ｘ）に存在するというものである場合には（図４のステップＳ５１５参照。）、「実区間多項式Ｆ（ｘ）に属する多項式は領域Ｄに零点を有する」ことを表す情報θ（例えばこの場合は、θ＝１とする。）をＲＡＭ（１５）の所定の格納領域に格納する（ステップＳ３７９）。なぜなら、この場合、境界Ｃ上に零点を有する実区間多項式Ｆ（ｘ）に属するエッジ多項式が存在することは、まさに実区間多項式Ｆ（ｘ）に属する多項式が領域Ｄに零点を有することと同じであるからである。
【０１３７】
（（ξ＝１の場合））
ステップＳ２０の処理は次のとおりである。
有界性判定制御部（１４４）は、ＲＡＭ（１５）から、各区分境界Ｃｐ〔但し、ｐ＝１，２，・・・，ｎ〕を表現する有理数係数有理式φｐ（ｓ）、ψｐ（ｓ）、パラメータｓの取り得る範囲Ｓｐ、領域Ｄに含まれる１点の複素平面上の座標λを読み込み、領域Ｄが有界であるか否かを判定する（ステップＳ２０）。そして、有界性判定制御部（１４４）は、この判定結果が、領域Ｄが有界であるというものである場合には、ステップＳ２３０以降の処理を実行するように制御する。
有界性判定制御部（１４４）は、判定結果が、領域Ｄが非有界であるというものである場合には、ステップＳ２１ａの処理を実行するように制御する。
【０１３８】
（（領域Ｄが有界の場合−ステップＳ２３０））
ステップＳ２３０以降の処理は次のとおりである。
代表多項式選択部（１４５）は、ＲＡＭ（１５）から、全ての区間数Ａｊ＝｛（ｕｊ−ｍｊ）ｔｊ＋ｍｊ｝を読み込み、各区間数から１つずつ任意に値ａｊ∈Ａｊを選択し、これらの値ａｊをＲＡＭ（１５）の所定の格納領域に格納する（ステップＳ２３０）。以下、これらの値ａｊを各項の係数に有する多項式を代表多項式ｆ（ｘ）と呼ぶ。
【０１３９】
境界上零点判定制御部（１４６）は、ＲＡＭ（１５）から、ステップＳ２３０において選択された値ａｊ、各区分境界Ｃｐ〔但し、ｐ＝１，２，・・・，ｎ〕を表現する有理数係数有理式φｐ（ｓ）、ψｐ（ｓ）、パラメータｓの取り得る範囲Ｓｐを読み込み、Sturmの定理に基づくアルゴリズムに従って、代表多項式ｆ（ｘ）が、各区分境界Ｃｐからなる境界C上に零点を有するか否かを判定する（ステップＳ２３１）。そして、境界上零点判定制御部（１４６）は、この判定結果が、境界Ｃ上に零点が存在するというものである場合には、「実区間多項式Ｆ（ｘ）に属する多項式は領域Ｄに零点を有する」ことを表す情報θ（例えばこの場合は、θ＝１とする。）をＲＡＭ（１５）の所定の格納領域に格納する（ステップＳ２３２）。なぜなら、この場合、実区間多項式Ｆ（ｘ）に属する代表多項式が領域Ｄの境界Ｃ上に零点を有することが明らかだからである。
境界上零点判定制御部（１４６）は、この判定結果が、境界Ｃ上に零点が存在しないというものである場合には、ステップＳ２３３の処理を実行するように制御する。
【０１４０】
領域内部零点判定制御部（１４７）は、ＲＡＭ（１５）から、ステップＳ２３０において選択された値ａｊ、各区分境界Ｃｐ〔但し、ｐ＝１，２，・・・，ｎ〕を表現する有理数係数有理式φｐ（ｓ）、ψｐ（ｓ）、パラメータｓの取り得る範囲Ｓｐを読み込み、偏角の原理に基づくアルゴリズムに従って、代表多項式ｆ（ｘ）が、各区分境界Ｃｐからなる境界Ｃで与えられる領域Ｄの内部に零点を有するか否かを判定する（ステップＳ２３３）。そして、領域内部零点判定制御部（１４７）は、この判定結果が、領域Ｄ内部に零点が存在するというものである場合には、「実区間多項式Ｆ（ｘ）に属する多項式は領域Ｄに零点を有する」ことを表す情報θ（例えばこの場合は、θ＝１とする。）をＲＡＭ（１５）の所定の格納領域に格納する（ステップＳ２３４）。なぜなら、この場合、実区間多項式Ｆ（ｘ）に属する代表多項式が領域Ｄ内部に零点を有することが明らかだからである。
領域内部零点判定制御部（１４７）は、判定結果が、領域Ｄ内部に零点が存在しないというものである場合には、ステップＳ２３５の処理を実行するように制御する。
【０１４１】
対象点多項式第２判定制御部（１４８）は、ＲＡＭ（１５）から、全ての区間数Ａｊ＝｛（ｕｊ−ｍｊ）ｔｊ＋ｍｊ｝、区分境界Ｃ１を表現する有理数係数有理式φ１（ｓ）、ψ１（ｓ）、パラメータｓの取り得る範囲Ｓ１を読み込み、《ステップ３の詳細》で説明したアルゴリズムに従って、範囲Ｓ１の端点のパラメータｓ１に対応する点α〔φ１（ｓ１）＋ｉ・ψ１（ｓ１）〕を零点とする多項式が実区間多項式Ｆ（ｘ）に存在するか否かを判定する（ステップＳ２３５）。なお、この判定処理では、図３に示した処理フローのステップＳ４００における任意の１点αを、区分境界Ｃ１を表現する有理数係数有理式φ１（ｓ）、ψ１（ｓ）について範囲Ｓ１の端点のパラメータｓ１に対応する点として与えるとした。勿論、各区分境界Ｃｐ〔但し、ｐ＝１，２，・・・，ｎ〕を表現する有理数係数有理式φｐ（ｓ）、ψｐ（ｓ）、パラメータｓの取り得る範囲ＳｐをＲＡＭ（１５）から読み込み、各区分境界Ｃｐからなる境界Ｃ上の任意の１点αを選択するようにしてもよい。
対象点多項式第２判定制御部（１４８）は、この判定結果が、点αを零点とする多項式が実区間多項式Ｆ（ｘ）に存在するというものである場合には（図３のステップＳ４１２参照。）、「実区間多項式Ｆ（ｘ）に属する多項式は領域Ｄに零点を有する」ことを表す情報θ（例えばこの場合は、θ＝１とする。）をＲＡＭ（１５）の所定の格納領域に格納する（ステップＳ２３６）。なぜなら、この場合、この点αを零点とする実区間多項式Ｆ（ｘ）に属する多項式が存在することは、まさに実区間多項式Ｆ（ｘ）に属する多項式が領域Ｄに零点を有することと同じであるからである。
対象点多項式第２判定制御部（１４８）は、判定結果が、点αを零点とする多項式が実区間多項式Ｆ（ｘ）に存在しないというものである場合には（図３のステップＳ４１１参照。）、ステップＳ２３７の処理を実行するように制御する。
【０１４２】
次に、エッジ多項式判定部（１４９）は、ＲＡＭ（１５）から、全ての区間数Ａｊ＝｛（ｕｊ−ｍｊ）ｔｊ＋ｍｊ｝、各区分境界Ｃｐ〔但し、ｐ＝１，２，・・・，ｎ〕を表現する有理数係数有理式φｐ（ｓ）、ψｐ（ｓ）、パラメータｓの取り得る範囲Ｓｐを読み込み、《ステップ４の詳細》で説明したアルゴリズムに従って、境界Ｃ上に零点を有するエッジ多項式が実区間多項式Ｆ（ｘ）に存在するか否かを判定する（ステップＳ２３７）。
エッジ多項式判定部（１４９）は、この判定結果が、境界Ｃ上に零点を有するエッジ多項式が実区間多項式Ｆ（ｘ）に存在しないというものである場合には（図４のステップＳ５１４参照。）、「実区間多項式Ｆ（ｘ）に属する多項式は領域Ｄに零点を有しない」ことを表す情報θ（例えばこの場合は、θ＝０とする。）をＲＡＭ（１５）の所定の格納領域に格納する（ステップＳ２３９）。なぜなら、上記理論から明らかなとおり、実区間多項式Ｆ（ｘ）に属するいかなるエッジ多項式も境界Ｃ上に零点を有しないことは、結局、実区間多項式Ｆ（ｘ）に属する多項式は領域Ｄに零点を有しないことと同じであるからである。
エッジ多項式判定部（１４９）は、判定結果が、境界Ｃ上に零点を有するエッジ多項式が実区間多項式Ｆ（ｘ）に存在するというものである場合には（図４のステップＳ５１５参照。）、「実区間多項式Ｆ（ｘ）に属する多項式は領域Ｄに零点を有する」ことを表す情報θ（例えばこの場合は、θ＝１とする。）をＲＡＭ（１５）の所定の格納領域に格納する（ステップＳ２３８）。なぜなら、この場合、境界Ｃ上に零点を有する実区間多項式Ｆ（ｘ）に属するエッジ多項式が存在することは、まさに実区間多項式Ｆ（ｘ）に属する多項式が領域Ｄに零点を有することと同じであるからである。
【０１４３】
（（領域Ｄが有界でない場合−ステップＳ２１ａ））
ステップＳ２１ａの処理は次のとおりである。
第１反復制御部（１９１）は、ＲＡＭ（１５）からｄを読み込み、パラメータσの値をｄに設定し、このσをＲＡＭ（１５）の所定の格納領域に格納する（ステップＳ２１ａ）。
【０１４４】
第１次数判定制御部（１４１）は、ＲＡＭ（１５）から、実区間多項式Ｆ（ｘ）の全ての区間数Ａｊ＝｛（ｕｊ−ｍｊ）ｔｊ＋ｍｊ｝およびσを読み込み、このσで特定される区間数Ａσが複素平面上の原点を含むか否かを判定し、この判定結果に基づき、ステップＳ２２０の処理またはステップＳ２１ｃの処理のいずれかを実行するように制御する（ステップＳ２１ｂ）。
【０１４５】
（（原点を含む場合−ステップＳ２１ｃ））
第１反復制御部（１９１）は、ＲＡＭ（１５）からσを読み込み、σ＝０が成立するか否かを判定する（ステップＳ２１ｃ）。そして、第１反復制御部（１９１）は、この判定結果が、σ＝０が成立するというものである場合には、「実区間多項式Ｆ（ｘ）に属する多項式は領域Ｄに零点を有する」ことを表す情報θ（例えばこの場合は、θ＝１とする。）をＲＡＭ（１５）の所定の格納領域に格納する（ステップＳ２１ｄ）。なぜなら、この場合、実区間多項式Ｆ（ｘ）は単項式Ｆ（ｘ）＝Ａ０であるといえ、さらにステップＳ２１ｂにおいて区間数Ａ０が原点を含むと判定されているので、実区間多項式Ｆ（ｘ）に属する多項式が領域Ｄに零点を有するといえるからである。
第１反復制御部（１９１）は、判定結果が、σ＝０が成立しないというものである場合には、ステップＳ２１ｅの処理を実行するように制御する。
【０１４６】
第２次数判定制御部（１４１８）は、ＲＡＭ（１５）から、実区間多項式Ｆ（ｘ）の全ての区間数Ａｊ＝｛（ｕｊ−ｍｊ）ｔｊ＋ｍｊ｝およびσを読み込み、このσで特定される区間数Ａσが複素平面上の原点と等しいか否か（つまり、Ａσ＝[０，０]が成立するか否か）を判定し、この判定結果に基づき、ステップＳ２１ｆの処理またはステップＳ２１ｇの処理のいずれかを実行するように制御する（ステップＳ２１ｅ）。
【０１４７】
（（原点と等しい場合−ステップＳ２１ｆ））
第１反復制御部（１９１）は、ＲＡＭ（１５）からσを読み込み、σの値から１を引いて、このσをＲＡＭ（１５）の所定の格納領域に格納する（ステップＳ２１ｆ）。続いて、第１反復制御部（１９１）は、ステップＳ２１ｂ以降の処理を実行するように制御する。
【０１４８】
ステップＳ２１ａ、Ｓ２１ｂ、Ｓ２１ｃ、Ｓ２１ｅ、Ｓ２１ｆの一連の処理は、見かけだけの最高次数を排除し（つまり、最高次数の区間数が[０，０]として与えられている項を排除する。）、実質的に真の最高次数を決定するために行うものである。
【０１４９】
（（原点に等しくない場合−ステップＳ２１ｇ））
恒等式判定制御部（１４１７）は、ＲＡＭ（１５）から、全ての区間数Ａｊ＝｛（ｕｊ−ｍｊ）ｔｊ＋ｍｊ｝を読み込み、各区間数がそれぞれ複素平面上の原点を含むか否かを判定する（ステップＳ２１ｇ）。そして、恒等式判定制御部（１４１７）は、この判定結果が、各区間数がそれぞれ複素平面上の原点を含むというものである場合には、「実区間多項式Ｆ（ｘ）に属する多項式は領域Ｄに零点を有する」ことを表す情報θ（例えばこの場合は、θ＝１とする。）をＲＡＭ（１５）の所定の格納領域に格納する（ステップＳ２１ｋ）。なぜなら、この場合、実区間多項式Ｆ（ｘ）が恒等的に０となる場合があるので、実区間多項式Ｆ（ｘ）に属する多項式が領域Ｄに零点を有するといえるからである。
恒等式判定制御部（１４１７）は、判定結果が、各区間数がそれぞれ複素平面上の原点を含むとはいえない（つまり、複素平面上原点を含まない区間数が存在するということ。）というものである場合には、零点位置判定処理を終了するように制御する（ステップＳ２１ｈ）。なぜなら、上記理論において説明したように、境界Ｃが閉曲線でない場合には、実区間多項式Ｆ（ｘ）に属する多項式の次数が一定である必要があるところ、この条件を充たさないからである（ステップＳ２１ｂで区間数が原点を含むと判定されていることに留意すること。）。
【０１５０】
（（原点を含まない場合−ステップＳ２２０））
ステップＳ２２０以降の処理は次のとおりである。
代表多項式選択部（１４５）は、ＲＡＭ（１５）から、全ての区間数Ａｊ＝｛（ｕｊ−ｍｊ）ｔｊ＋ｍｊ｝を読み込み、各区間数から１つずつ任意に値ａｊ∈Ａｊを選択し、これらの値ａｊをＲＡＭ（１５）の所定の格納領域に格納する（ステップＳ２２０）。以下、これらの値ａｊを各項の係数に有する多項式を代表多項式ｆ（ｘ）と呼ぶ。
【０１５１】
境界上零点判定制御部（１４６）は、ＲＡＭ（１５）から、ステップＳ２２０において選択された値ａｊ、各区分境界Ｃｐ〔但し、ｐ＝１，２，・・・，ｎ〕を表現する有理数係数有理式φｐ（ｓ）、ψｐ（ｓ）、パラメータｓの取り得る範囲Ｓｐを読み込み、Sturmの定理に基づくアルゴリズムに従って、代表多項式ｆ（ｘ）が、各区分境界Ｃｐからなる境界C上に零点を有するか否かを判定する（ステップＳ２２１）。そして、境界上零点判定制御部（１４６）は、この判定結果が、境界Ｃ上に零点が存在するというものである場合には、「実区間多項式Ｆ（ｘ）に属する多項式は領域Ｄに零点を有する」ことを表す情報θ（例えばこの場合は、θ＝１とする。）をＲＡＭ（１５）の所定の格納領域に格納する（ステップＳ２２２）。なぜなら、この場合、実区間多項式Ｆ（ｘ）に属する代表多項式が領域Ｄの境界Ｃ上に零点を有することが明らかだからである。
境界上零点判定制御部（１４６）は、判定結果が、境界Ｃ上に零点が存在しないというものである場合には、ステップＳ２２３の処理を実行するように制御する。
【０１５２】
領域内部零点判定制御部（１４７）は、ＲＡＭ（１５）から、ステップＳ２２０において選択された値ａｊ、各区分境界Ｃｐ〔但し、ｐ＝１，２，・・・，ｎ〕を表現する有理数係数有理式φｐ（ｓ）、ψｐ（ｓ）、パラメータｓの取り得る範囲Ｓｐを読み込み、偏角の原理に基づくアルゴリズムに従って、各区分境界Ｃｐからなる境界Ｃで与えられる領域Ｄの外部（但し、ここでの外部とは、領域Ｄに含まれる１点の複素平面上の座標λで指定される側ではない領域、即ち有界領域の側を指していることに留意する。）に存在する代表多項式ｆ（ｘ）の零点の個数（重複する零点はその数だけ数える。）を計数する。そして、領域内部零点判定制御部（１４７）は、代表多項式の次数から上記の計数した零点の個数を引いて領域Ｄの内部に存在する代表多項式ｆ（ｘ）の零点の個数を求めることで〔領域Ｄ内部に存在する零点の個数＝代表多項式の次数−領域Ｄ外部に存在する零点の個数〕、代表多項式ｆ（ｘ）が領域Ｄの内部に零点を有するか否かを判定する（ステップＳ２２３）。そして、領域内部零点判定制御部（１４７）は、この判定結果が、領域Ｄ内部に零点が存在するというものである場合には、「実区間多項式Ｆ（ｘ）に属する多項式は領域Ｄに零点を有する」ことを表す情報θ（例えばこの場合は、θ＝１とする。）をＲＡＭ（１５）の所定の格納領域に格納する（ステップＳ２２４）。なぜなら、この場合、実区間多項式Ｆ（ｘ）に属する代表多項式が領域Ｄ内部に零点を有することが明らかだからである。
領域内部零点判定制御部（１４７）は、判定結果が、領域Ｄ内部に零点が存在しないというものである場合には、ステップＳ２２５の処理を実行するように制御する。
【０１５３】
対象点多項式第２判定制御部（１４８）は、ＲＡＭ（１５）から、全ての区間数Ａｊ＝｛（ｕｊ−ｍｊ）ｔｊ＋ｍｊ｝、区分境界Ｃ１を表現する有理数係数有理式φ１（ｓ）、ψ１（ｓ）、パラメータｓの取り得る範囲Ｓ１を読み込み、《ステップ３の詳細》で説明したアルゴリズムに従って、範囲Ｓ１の端点のパラメータｓ１に対応する点α〔φ１（ｓ１）＋ｉ・ψ１（ｓ１）〕を零点とする多項式が実区間多項式Ｆ（ｘ）に存在するか否かを判定する（ステップＳ２２５）。なお、この判定処理では、図３に示した処理フローのステップＳ４００における任意の１点αを、区分境界Ｃ１を表現する有理数係数有理式φ１（ｓ）、ψ１（ｓ）について範囲Ｓ１の端点のパラメータｓ１に対応する点として与えるとした。勿論、各区分境界Ｃｐ〔但し、ｐ＝１，２，・・・，ｎ〕を表現する有理数係数有理式φｐ（ｓ）、ψｐ（ｓ）、パラメータｓの取り得る範囲ＳｐをＲＡＭ（１５）から読み込み、各区分境界Ｃｐからなる境界Ｃ上の任意の１点αを選択するようにしてもよい。
対象点多項式第２判定制御部（１４８）は、この判定結果が、点αを零点とする多項式が実区間多項式Ｆ（ｘ）に存在するというものである場合には（図３のステップＳ４１２参照。）、「実区間多項式Ｆ（ｘ）に属する多項式は領域Ｄに零点を有する」ことを表す情報θ（例えばこの場合は、θ＝１とする。）をＲＡＭ（１５）の所定の格納領域に格納する（ステップＳ２２６）。なぜなら、この場合、この点αを零点とする実区間多項式Ｆ（ｘ）に属する多項式が存在することは、まさに実区間多項式Ｆ（ｘ）に属する多項式が領域Ｄに零点を有することと同じであるからである。
対象点多項式第２判定制御部（１４８）は、判定結果が、点αを零点とする多項式が実区間多項式Ｆ（ｘ）に存在しないというものである場合には（図３のステップＳ４１１参照。）、ステップＳ２２７の処理を実行するように制御する。
【０１５４】
次に、エッジ多項式判定部（１４９）は、ＲＡＭ（１５）から、全ての区間数Ａｊ＝｛（ｕｊ−ｍｊ）ｔｊ＋ｍｊ｝、各区分境界Ｃｐ〔但し、ｐ＝１，２，・・・，ｎ〕を表現する有理数係数有理式φｐ（ｓ）、ψｐ（ｓ）、パラメータｓの取り得る範囲Ｓｐを読み込み、《ステップ４の詳細》で説明したアルゴリズムに従って、境界Ｃ上に零点を有するエッジ多項式が実区間多項式Ｆ（ｘ）に存在するか否かを判定する（ステップＳ２２７）。
エッジ多項式判定部（１４９）は、この判定結果が、境界Ｃ上に零点を有するエッジ多項式が実区間多項式Ｆ（ｘ）に存在しないというものである場合には（図４のステップＳ５１４参照。）、「実区間多項式Ｆ（ｘ）に属する多項式は領域Ｄに零点を有しない」ことを表す情報θ（例えばこの場合は、θ＝０とする。）をＲＡＭ（１５）の所定の格納領域に格納する（ステップＳ２２９）。なぜなら、上記理論から明らかなとおり、実区間多項式Ｆ（ｘ）に属するいかなるエッジ多項式も境界Ｃ上に零点を有しないことは、結局、実区間多項式Ｆ（ｘ）に属する多項式は領域Ｄに零点を有しないことと同じであるからである。
エッジ多項式判定部（１４９）は、判定結果が、境界Ｃ上に零点を有するエッジ多項式が実区間多項式Ｆ（ｘ）に存在するというものである場合には（図４のステップＳ５１５参照。）、「実区間多項式Ｆ（ｘ）に属する多項式は領域Ｄに零点を有する」ことを表す情報θ（例えばこの場合は、θ＝１とする。）をＲＡＭ（１５）の所定の格納領域に格納する（ステップＳ２２８）。なぜなら、この場合、境界Ｃ上に零点を有する実区間多項式Ｆ（ｘ）に属するエッジ多項式が存在することは、まさに実区間多項式Ｆ（ｘ）に属する多項式が領域Ｄに零点を有することと同じであるからである。
【０１５５】
本発明である実区間多項式の零点の位置装置、位置判定方法は上述の実施形態に限定されるものではなく、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。また、上記実施形態において説明した処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されるとしてもよい。
【０１５６】
また、上記実施形態において説明した零点位置判定装置における処理機能をコンピュータによって実現する場合、零点位置判定装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記零点位置判定装置における処理機能がコンピュータ上で実現される。
【０１５７】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（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）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０１６０】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、零点位置判定装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【実施例】
【０１６１】
以下、本発明である実区間多項式の零点の位置判定方法の実施例を、図１７、図１８、図１９を参照しながら、具体例を示して説明する。以下では、ある桁から先の値を省略する意味の『…』が付されていない小数は、正確な値を表すものとする。ここで、用いる処理フロー（図１７、図１８、図１９）は図６、図３、図５に示した処理フローである。図１７、図１８、図１９では、これらの処理フロー（図６、図３、図５）に対応することを示すため、この具体例で経過した処理ステップの符号には添え字Ｒを当てている。
【０１６２】
この実施例では、実区間多項式Ｆ（ｘ）を式（２２）で与えられる２次の実区間多項式とする。
【数１９】
2007148815.tif 000021
【０１６３】
領域Ｄを、頂点が、Ｒ１=0.3092+i・0.95、Ｒ２=0.31+i・0.95、Ｒ３=0.31+i・0.953、Ｒ４=0.3092+i・0.953である長方形の周および内部とする。長方形の周（境界Ｃ）のパラメータ表示は、式（２３）で与えられる。そして、Ｃ＝Ｃ１∪Ｃ２∪Ｃ３∪Ｃ４である。
【数２０】
2007148815.tif 000022
【０１６４】
実区間多項式Ｆ（ｘ）に属する多項式として、ｆ０（ｘ）=x2-0.618x+1を選択する（ステップＳ８００Ｒ）。ｆ０（ｘ）＝０の方程式の根は、0.309±i・√0.904519=0.309±i・0.951062…であって、実部を見ればいずれも領域Ｄの外にあることがわかる。この様子を図２０に示す（但し、縮尺などは必ずしも正確ではない。）。従って判定結果は、「領域Ｄ内部および境界Ｃ上に零点は存在しない」となる（ステップＳ８０１Ｒ）。なお、この例では代表多項式ｆ０（ｘ）が２次式なので直接零点を求めることができたが、一般的には既述のとおり、境界Ｃ上に零点が存在するか否かの判定と、内部に零点が存在するか否かの判定を行う。
【０１６５】
次に、境界Ｃ上の１点を零点とする多項式が実区間多項式Ｆ（ｘ）に存在するか否かを行う（ステップＳ８０２Ｒ）。
ここでは、境界Ｃ上の１点として上記のＲ１を選択する（ステップＳ４００Ｒ）。この点Ｒ１を零点とする多項式が実区間多項式Ｆ（ｘ）に存在するか否かの判定は、式（２２）から方程式(0.9995+0.001t2)x2+(-0.6185+0.001t1)x+(0.9995+0.001t0)=0の変数ｘにＲ１の座標を代入し（ステップＳ４０１Ｒ）、必要ならｔｊを1−ｔｊで置き換えて（ステップＳ４０２Ｒ〜Ｓ４０７Ｒ）、式（１９）に相当する式変形を行う（ステップＳ４０８Ｒ）。次に、ステップＳ４０８Ｒの処理で得られた式（１９）の右辺に相当する点ｂ（以下、「判定点」という。）の実部が負であるか否かを判定する（ステップＳ４０８ｘＲ）。判定点ｂの実部が負であれば、判定点ｂがステップＳ４０８Ｒの処理で得られた式（１９）の左辺に相当する点全体の凸包（以下、「判定凸包」という。）に入ることはないので、点Ｒ１を零点とする多項式が実区間多項式Ｆ（ｘ）に存在しないといえる（ステップＳ４１１Ｒ）。判定点ｂの実部が負でなければ、ステップＳ４０８ｙの処理を行う。即ち、判定点ｂの実部が０かつ虚部が負であるか否かを判定する（ステップＳ４０８ｙ）。ここで、判定点ｂの実部が０かつ虚部が負であれば、判定点ｂが判定凸包に入ることはないので、点Ｒ１を零点とする多項式が実区間多項式Ｆ（ｘ）に存在しないといえる。他方、判定点ｂの実部が０かつ虚部が負でなければ、ステップＳ４０９の処理を行う。即ち、判定凸包を作って（ステップＳ４０９）、判定点ｂが凸包に入るか否かを判定する（ステップＳ４１０）。結果だけを示すと、判定凸包の頂点の座標は、0、0.00080689536-i・0.00058748、0.00180689536-i・0.00058748、0.00211609536+i・0.00036252、0.0013092+i・0.00095、0.0003092+i・0.00095であり、判定点ｂの点座標は、-0.00096099232-i・0.00019874となる。この場合の判定凸包およびその頂点を図２１に示す（但し、縮尺などは必ずしも正確ではない。）。図２１および判定点ｂの座標から明らかなように、判定点ｂの実部が負であるから、ステップＳ４０８ｘＲの段階で点Ｒ１を零点とする多項式ｆ（ｘ）∈Ｆ（ｘ）は存在しないことがわかる（ステップＳ４１１Ｒ）。
【０１６６】
次に、境界Ｃ上、即ち各区分境界Ｃ１，Ｃ２，Ｃ３，Ｃ４上に零点を有するエッジ多項式が実区間多項式Ｆ（ｘ）に存在するか否かの判定を行う（ステップＳ８０４Ｒ）。これは、式群（２４）に示す１２本のエッジ多項式から決まる方程式が対象となる。
【数２１】
2007148815.tif 000023
【０１６７】
但し、各方程式について、各区分境界Ｃ１，Ｃ２，Ｃ３，Ｃ４上に零点を有するエッジ多項式の有無を調べることになるので、全部で４８回の判定となることに留意しなければならない。以下、式群（２４）の最初の式をｆ１（ｘ）=tx2-(6185/10000)x+9995/10000=0(9995/10000≦t≦10005/10000)として、このｆ１（ｘ）について説明する（ステップＳ５００Ｒ、Ｓ５０１Ｒ。但し、この具体例では、ステップＳ５００Ｒにおいてｊ＝０と設定するのではなく、或るｊ（ｊ≠０）を１つ選択するとした。従って、既述のステップＳ５０１ａ、Ｓ５０４ａ、Ｓ５０５ａを図１９には示していない。）。
【０１６８】
まず、長方形の領域Ｄの区分境界Ｃ３上について判定を行う（ステップＳ５０２Ｒ）。区分境界Ｃ３の有理数係数有理式の表現ｘ=s+i・953/1000(3092/10000≦s≦31/100)をｆ１（ｘ）に代入すると、その実部および虚部は式（２５）のようになる。
【数２２】
2007148815.tif 000024
【０１６９】
式（２５）の実部、虚部それぞれにおいてｔについて解くと、式（２６）を得る（ステップＳ５０３Ｒ）。
【数２３】
2007148815.tif 000025
【０１７０】
式（２６）の第２項と第３項が等しいという方程式を整理すると、式（２７）を得る（ステップＳ５０４Ｒ）。式（２７）の方程式は、3092/10000≦ｓ≦31/100の範囲に根を持たない（ステップＳ５２０Ｒ）。実際、式（２７）の一根は0.028…、もう一根は32.3…である。なお、この例では代表多項式Ｐ（ｓ）が２次式なので直接ｓについて解くことができたが〔ステップＳ５２０Ｒに相当する。〕、一般的には既述のとおり、ステップＳ５０５〜Ｓ５０９の処理を行う。
【数２４】
2007148815.tif 000026
【０１７１】
次に、長方形の領域Ｄの区分境界Ｃ４上について判定を行う（ステップＳ５１０Ｒ、Ｓ５０２Ｒ）。区分境界Ｃ４の有理数係数有理式の表現x=3092/10000+i・s(95/100≦ｓ≦953/1000)をｆ１（ｘ）に代入すると、その実部および虚部は式（２８）のようになる。
【数２５】
2007148815.tif 000027
【０１７２】
式（２８）の実部、虚部それぞれにおいてｔについて解くと、式（２９）を得る（ステップＳ５０３Ｒ）。
【数２６】
2007148815.tif 000028
【０１７３】
式（２９）の第２項と第３項が等しいという方程式を整理すると、式（３０）を得る（ステップＳ５０４Ｒ）。式（３０）の方程式は、95/100≦ｓ≦953/1000の範囲に１つの根s=0.950649…を持つ（ステップＳ５２０Ｒ）。そのとき、t=6185/6184=1.0001617…で、9995/10000≦t≦10005/10000、即ち、0.9995≦t≦1.0005の範囲内に収まっている。
【数２７】
2007148815.tif 000029
【０１７４】
以上から、実区間多項式Ｆ（ｘ）に属する多項式tx2-0.6185x+0.9995=0(t=6185/6184)が、領域Ｄという（より詳しくは、領域Ｄの区分境界Ｃ４上の点0.3092+i・s(s=0.950649…)である。）に零点を持つことがわかる（ステップＳ８０８Ｒ）。この様子を図２２に示す（但し、縮尺などは必ずしも正確ではない。）。
結局、本実施例では、「実区間多項式Ｆ（ｘ）は領域Ｄに零点を有する」、即ち、「領域Ｄに零点を有する多項式が実区間多項式Ｆ（ｘ）に存在する」と判定できたことになる。
【０１７５】
なお、以上の具体例では説明を簡単にするためにいくつかの制限（用いた数値が実数の場合は有理数、複素数の場合は実部、虚部ともに有理数であること、多項式ｅｊ（ｘ）は、ｅｊ（ｘ）＝ｘｊであること、境界は閉曲線であって領域Ｄは有界であること。）を設けているが、既述のとおり、これらの制限はいずれも必須のものではないことに留意しなければならない。
【０１７６】
また、上記の具体例では、境界Ｃは４つの区分境界によって構成された。しかしながら、境界Ｃは必ず複数の区分境界によって構成されなければならないものではなく、境界Ｃを１つの区分境界（この場合、「区分」境界という言葉は正確ではないが、対比を容易にするために敢えて使用している。）で構成することでもよい。その一例としては、境界Ｃをパラメータｓによってφ（ｓ）＋ｉ・ψ（ｓ）と表すとすると、有理数係数有理式φ（ｓ）、ψ（ｓ）を式（３１）で表すものが挙げられる。
【数２８】
2007148815.tif 000030
【産業上の利用可能性】
【０１７７】
本発明は、例えば、多項式の係数に誤差を含むため一意に多項式を決定できない場合において、当該多項式の零点が所定の領域に存在するかを判定したい場合などに用いられ、そのような場合の一例として、ディジタル信号処理におけるディジタルフィルタ（例えば、ＩＩＲ〔Infinite Impulse Response〕フィルタ）の周波数特性の解析などに有用である。
【図面の簡単な説明】
【０１７８】
【図１】本発明の零点位置判定処理のフローチャート。
【図２】本発明の零点位置判定処理の変形例のフローチャート。
【図３】境界Ｃ上の任意の１点を零点とする多項式が実区間多項式Ｆ（ｘ）に存在するか否かを判定するための処理フロー。
【図４−１】境界Ｃ上に零点を有するエッジ多項式が実区間多項式Ｆ（ｘ）に存在するか否かを判定するための処理フロー（その１）。
【図４−２】境界Ｃ上に零点を有するエッジ多項式が実区間多項式Ｆ（ｘ）に存在するか否かを判定するための処理フロー（その２）。
【図５−１】境界Ｃ上に零点を有するエッジ多項式が実区間多項式Ｆ（ｘ）に存在するか否かを判定するための処理フローの変形例（その１）。
【図５−２】境界Ｃ上に零点を有するエッジ多項式が実区間多項式Ｆ（ｘ）に存在するか否かを判定するための処理フローの変形例（その２）。
【図６】図５−１および図５−２に示した処理フローに対応した本発明の零点位置判定処理のフローチャート。
【図７】零点位置判定装置（１）のハードウェア構成を例示した構成ブロック図。
【図８】零点位置判定の処理フロー（その１）。
【図９】零点位置判定の処理フロー（その２）。
【図１０】零点位置判定の処理フロー（その３）。
【図１１】零点位置判定の処理フロー（その４）。
【図１２】零点位置判定の処理フロー（その５）。
【図１３】零点位置判定の処理フロー（その６）。
【図１４】零点位置判定の処理フロー（その７）。
【図１５】零点位置判定装置（１）における処理機能を示す機能ブロック図。
【図１６】（ａ）原点中心の半径１＋Ｍ／ｍの円、境界Ｃおよび領域Ｄの関係を示す図。（ｂ）原点中心の半径１＋Ｍ／ｍの円、原点中心の半径Ｒの円、境界Ｃ、領域Ｄおよび領域Ｅの関係を示す図。
【図１７】実施例における、零点位置判定処理のフローチャート。
【図１８】実施例における、境界Ｃ上の任意の１点を零点とする多項式が実区間多項式Ｆ（ｘ）に存在するか否かを判定するための処理フロー。
【図１９】実施例における、境界Ｃ上に零点を有するエッジ多項式が実区間多項式Ｆ（ｘ）に存在するか否かを判定するための処理フロー（変形例）。
【図２０】実施例における、領域Ｄと代表多項式の根との位置関係を示す図。
【図２１】実施例における、凸包と判定点との位置関係を示す図。
【図２２】実施例における、領域Ｄと実区間多項式Ｆ（ｘ）に属する多項式で領域Ｄに零点を有するものの零点との位置関係を示す図。
【図２３】従来における零点位置判定処理のフローチャート。
【符号の説明】
【０１７９】
１        零点位置判定装置
１４０    境界種判定制御部
１４１    第１次数判定制御部
１４２    交点判定部
１４３    共通領域判定部
１４４    有界性判定制御部
１４５    代表多項式選択部
１４６    境界上零点判定制御部
１４７    領域内部零点判定制御部
１４８    対象点多項式第２判定制御部
１４９    エッジ多項式判定部
１４１０  境界設定部
１４１４  交点数判定制御部
１４１５  共通領域判定制御部
１４１６  対象点多項式第１判定部
１４１７  恒等式判定制御部
１４１８  第２次数判定制御部
１９０    制御部
１９１    第１反復制御部
【図１】
2007148815.tif 000031
【図２】
2007148815.tif 000032
【図３】
2007148815.tif 000033
【図４−１】
2007148815.tif 000034
【図４−２】
2007148815.tif 000035
【図５−１】
2007148815.tif 000036
【図５−２】
2007148815.tif 000037
【図６】
2007148815.tif 000038
【図７】
2007148815.tif 000039
【図８】
2007148815.tif 000040
【図９】
2007148815.tif 000041
【図１０】
2007148815.tif 000042
【図１１】
2007148815.tif 000043
【図１２】
2007148815.tif 000044
【図１３】
2007148815.tif 000045
【図１４】
2007148815.tif 000046
【図１５】
2007148815.tif 000047
【図１６】
2007148815.tif 000048
【図１７】
2007148815.tif 000049
【図１８】
2007148815.tif 000050
【図１９】
2007148815.tif 000051
【図２０】
2007148815.tif 000052
【図２１】
2007148815.tif 000053
【図２２】
2007148815.tif 000054
【図２３】
2007148815.tif 000055