(57)【要約】【課題】区分境界Ｃｋの数の大小に関わらず、効率の良い複素区間多項式の零点の位置を判定する技術を提供する。【解決手段】複素区間多項式Ｆ（ｘ）中に、領域Ｄに零点を持たない多項式が存在する場合に、領域Ｄの境界Ｃ上の一点ｃ（代表点ｃ）を選択して、この代表点ｃを零点とする多項式が複素区間多項式Ｆ（ｘ）の中に存在するか否かを調べる（ステップＳ４）。代表点ｃを零点とする多項式が存在しないと判定された場合に、所定の等式を成立させる複素数が、区分境界線上にあるか否かを区分境界線ごとに判定して（ステップＳ５５）、その判定結果を上記複素区間多項式が零点を有するか否かを表す情報として出力する。【選択図】図３
2008269047.tif 000002
【特許請求の範囲】
【請求項１】
複素区間多項式の零点の位置を判定する方法において、
記憶手段には、区間数が複素平面上の円領域で表される複素区間多項式と、有理関数で表される有限個の区分境界線から構成される複素領域の境界線と、その境界線によって分けられた複素平面上の領域がそれぞれ記憶され、
代表多項式選択手段が、記憶手段に記憶される複素区間多項式に属する多項式を１つ選択する代表多項式選択ステップと、
代表多項式零点判定手段が、上記選択された代表多項式が、記憶手段に記憶された複素平面上の領域に零点を有するか否かを判定する代表多項式零点判定ステップと、
代表点選択手段が、記憶手段に記憶された境界線上の任意の一点（以下、代表点とする。）を選択する代表点選択ステップと、
多項式判定手段が、上記代表点を零点とする多項式が、記憶手段に記憶された複素区間多項式の中に存在するか否かを判定する多項式判定ステップと、
等式判定手段が、多項式判定ステップにおいて、上記代表点を零点とする多項式が存在しないと判定された場合に、所定の等式を成立させる複素数が、区分境界線上にあるか否かを区分境界線ごとに判定して、その判定結果を上記複素区間多項式が零点を有するか否かを表す情報として出力する等式判定ステップと、
を有する複素区間多項式の零点の位置判定方法。
【請求項２】
請求項１に記載の複素区間多項式の零点の位置判定方法において、
上記複素区間多項式は、複素数係数の多項式（以下、多項式とする。）と、その多項式ごとの区間数との積の和で表されており、
上記所定の等式は、上記多項式とその多項式ごとの区間数の中心点との積の和の絶対値は、上記多項式の絶対値とその多項式ごとの区間数の複素平面上の円領域の半径との積の和と等しいとする式である、
ことを特徴とする複素区間多項式の零点の位置判定方法。
【請求項３】
請求項１又は２に記載の複素区間多項式の零点の位置判定方法において、
上記代表多項式零点判定ステップは、
境界上零点判定手段が、上記選択された代表多項式が、記憶手段に記憶された複素領域の境界線上に零点を有するか否かを判定する境界上零点判定ステップと、
領域内部零点判定手段が、境界上零点判定ステップにおいて、上記境界線上に零点を有しないと判定された場合に、上記選択された代表多項式が、記憶手段に記憶された複素平面上の領域の内部に零点を有するか否かを判定する領域内部零点判定ステップと、
を含む、
ことを特徴とする複素区間多項式の零点の位置判定方法。
【請求項４】
複素区間多項式の零点の位置を判定する装置において、
区間数が複素平面上の円領域で表される複素区間多項式と、有理関数で表される有限個の区分境界線から構成される複素領域の境界線と、その境界線によって分けられた複素平面上の領域がそれぞれ記憶された記憶手段と、
記憶手段に記憶される複素区間多項式に属する多項式を１つ選択する代表多項式選択手段と、
上記選択された代表多項式が、記憶手段に記憶された複素平面上の領域に零点を有するか否かを判定する代表多項式零点判定手段と、
記憶手段に記憶された境界線上の任意の一点（以下、代表点とする。）を選択する代表点選択手段と、
上記代表点を零点とする多項式が、記憶手段に記憶された複素区間多項式の中に存在するか否かを判定する多項式判定手段と、
多項式判定手段において、上記代表点を零点とする多項式が存在しないと判定された場合に、所定の等式を成立させる複素数が、区分境界線上にあるか否かを区分境界線ごとに判定して、その判定結果を上記複素区間多項式が零点を有するか否かを表す情報として出力する等式判定手段と、
を有する複素区間多項式の零点の位置判定装置。
【請求項５】
請求項１に記載の複素区間多項式の零点の位置判定装置において、
上記複素区間多項式は、複素数係数の多項式（以下、多項式とする。）と、その多項式ごとの区間数との積の和で表されており、
上記所定の等式は、上記多項式とその多項式ごとの区間数の中心点との積の和の絶対値は、上記多項式の絶対値とその多項式ごとの区間数の複素平面上の円領域の半径との積の和と等しいとする式である、
ことを特徴とする複素区間多項式の零点の位置判定装置。
【請求項６】
請求項４又は５に記載の複素区間多項式の零点の位置判定装置において、
上記代表多項式零点判定手段は、
上記選択された代表多項式が、記憶手段に記憶された複素領域の境界線上に零点を有するか否かを判定する境界上零点判定手段と、
境界上零点判定ステップにおいて、上記境界線上に零点を有しないと判定された場合に、上記選択された代表多項式が、記憶手段に記憶された複素平面上の領域の内部に零点を有するか否かを判定する領域内部零点判定手段と、
を含む、
ことを特徴とする複素区間多項式の零点の位置判定装置。
【請求項７】
請求項１から請求項３の何れかに記載の複素区間多項式の零点の位置判定方法をコンピュータに実行させるための複素区間多項式の零点の位置判定プログラム。
【請求項８】
請求項７に記載の複素区間多項式の零点の位置判定プログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複素区間多項式の零点の位置判定方法、装置、プログラム及びその記録媒体に関する。より詳細には、一変数複素区間多項式の零点の位置判定方法、装置、プログラム及びその記録媒体に関する。
【背景技術】
【０００２】
係数が確定していない（例えば、係数に誤差がある場合などである。）多項式を表す手法として、区間多項式がある。区間多項式Ｆ（ｘ）とは、数の集合である区間数Ａｊ（０≦ｊ≦ｄ）を各項の係数として式（１）のように表記されるものである。つまり、区間多項式Ｆ（ｘ）は、係数がａｊ∈Ａｊである多項式ｆ（ｘ）〔式（２）参照。〕全体の集合を表す。なお、この明細書における区間多項式は、特に断りのない限り、一変数区間多項式であるとする。
【数１】
2008269047.tif 000003
【０００３】
区間数を実数の範囲で考える場合は、区間数として閉区間［ａ，ｂ］（ａ≦ｃ≦ｂを満す実数ｃの集合）を用いる。区間数を複素数の範囲で考える場合は、区間数として、円領域のもの（中心と半径を指定する。）、あるいは、長方形の領域のもの（実部および虚部それぞれの上限および下限を指定する。）を用いる。
【０００４】
係数が円領域の区間数で表された一変数複素区間多項式について、それに属する多項式であって、指定した一つの複素数を零点とするものが存在するか否かの判定法については既に知られている（例えば、非特許文献１参照。）。
【０００５】
また、区間数を長方形の領域とした複素区間多項式に対し、「当該複素区間多項式に属する全ての零点が複素左半平面（実部が負である領域）に存在する」という命題が成立するか否かの判定については、Kharitonovの定理によって判定可能である（例えば、非特許文献２参照。）。
【０００６】
係数が円領域の区間数で表された一変数複素区間多項式Ｆ（ｘ）が与えられたとき、当該複素区間多項式Ｆ（ｘ）に属する多項式であって、与えられた複素領域Ｄ内に零点を持つものが存在するか否かを判定する方法として、以下に述べる方法がある（例えば、特許文献１参照）。
【０００７】
複素平面上の領域をＤとする。領域は、その境界Ｃを含むものとする。境界Ｃは、単純な曲線であって、１つ以上の有限個の区分境界Ｃｋ（ｋ＝１，…，Ｋ）の和集合として表現される。すなわち、Ｃ＝Ｃ１∪…∪ＣＫである。各区分境界Ｃｋは、パラメータｓによって、φｋ（ｓ）＋ｉ・ψｋ（ｓ）と表示される。ここで、ｉは、虚数単位を表す。ここで、φｋ（ｓ）、ψｋ（ｓ）は有理数係数の有理式であるとし、ｓの動く範囲Ｓｋは、［ａ，ｂ］、（−∞，ｂ］、［ａ，∞）、（−∞，∞）のいずれかであるとする。[・，・]は閉区間、（・，・］は左開右閉区間、［・，・）は左閉右開区間、（・，・）は開区間を表す。また、パラメータｓと区分境界Ｃｋとの間は単射であるとする。すなわち、式（３）で表される関係があるとする。
【数２】
2008269047.tif 000004
このとき、以下のようにして、複素区間多項式Ｆ（ｘ）内に、所定の複素領域Ｄ内に零点を持つ多項式があるか否かを判定する。
【０００８】
＜ステップ１＞
まず、複素区間多項式Ｆ（ｘ）に属する、各係数の実部、虚部が有理数である多項式を一つ選択する。これを代表多項式と呼びｆ’（ｘ）で表す。
【０００９】
＜ステップ２＞
領域Ｄ内に代表多項式ｆ’（ｘ）の零点が存在するか否かを判定する。この判定は、公知の手法によって達成される。
【００１０】
まず、領域Ｄの境界Ｃ上において零点が存在するか否かの判定を行う。例えば、領域Ｄの境界Ｃの表示φ（ｓ）＋ｉ・ψ（ｓ）を代表多項式ｆ’（ｘ）に代入した後、Sturmの定理に基づくアルゴリズムにしたがって零点の有無を判定する。
【００１１】
Strumの定理に基づくアルゴリズムの適用について説明する。
【００１２】
領域Ｄの境界Ｃの表示φ（ｓ）＋ｉ・ψ（ｓ）が代入された代表多項式ｆ（φ（ｓ）＋ｉ・ψ（ｓ））は、有理数係数有理式α（ｓ）およびβ（ｓ）によってｆ（φ（ｓ）＋ｉ・ψ（ｓ））＝α（ｓ）＋ｉ・β（ｓ）と表示できる。ここで「代表多項式ｆ’（ｘ）が、φ（ｓ）＋ｉ・ψ（ｓ）において０となる」ことと、「α（ｓ）およびβ（ｓ）がｓ＝ｓ０で同時に０となる」ことは同値である。また、「α（ｓ）およびβ（ｓ）がｓ＝ｓ０で同時に０となる」ことと、「α（ｓ）＝α１（ｓ）／α２（ｓ），β（ｓ）＝β１（ｓ）／β２（ｓ）、ただし、α１（ｓ）とα２（ｓ）は互いに素，β１（ｓ）とβ２（ｓ）は互いに素、と書いたとき、α１（ｓ）およびβ１（ｓ）のＧＣＤ（最大公約多項式）がｓ０において０になる」ことは同値である。したがって、有理数係数有理式であるα１（ｓ）およびβ１（ｓ）のＧＣＤに対し、Strumの定理に基づくアルゴリズムを適用する。説明の便宜からα１（ｓ）およびβ１（ｓ）のＧＣＤをＨ（ｓ）とする。このＨ（ｓ）について、多項式の列Ｈ０（ｓ）、Ｈ１（ｓ）、Ｈ２（ｓ）、・・・、Ｈｒ（ｓ）を生成する。ただし、これらの多項式の列は、次の規則にしたがって生成する。Ｈ０（ｓ）＝Ｈ（ｓ）、Ｈ１（ｓ）＝ｄＨ（ｓ）／ｄｓ〔ｓに関する１階微分である。ライプニッツ記法〕、Ｈｋ−１（ｓ）をＨｋ（ｓ）で割った剰余多項式を（符号を変えて）−Ｈｋ＋１（ｓ）とする。つまり、商の多項式をＱｋ（ｓ）と表すと、Ｈｋ−１（ｓ）＝Ｈｋ（ｓ）Ｑｋ（ｓ）−Ｈｋ＋１（ｓ）の関係が成立する。また、Ｈｒ−１（ｓ）は、Ｈｒ（ｓ）で割り切れる。つまり、商の多項式をＱｒ（ｓ）と表すと、Ｈｒ−１（ｓ）＝Ｈｒ（ｓ）Ｑｒ（ｓ）の関係が成立する。
このときＳ＝[ａ，ｂ]において、Ｈ０（ａ）、Ｈ１（ａ）、Ｈ２（ａ）、…、Ｈｒ（ａ）における正負の符号変化の回数をｗ（ａ）、Ｈ０（ｂ）、Ｈ１（ｂ）、Ｈ２（ｂ）、…、Ｈｒ（ｂ）における正負の符号変化の回数をｗ（ｂ）で表すとすると、区間Ｓ＝[ａ，ｂ]におけるＨ（ｓ）の零点の個数は、ｗ（ａ）−ｗ（ｂ）である。なお、ここでは、区間Ｓ＝[ａ，ｂ]のａ、ｂは共にＨ（ｓ）の零点ではないとする（零点であれば、個数を表す式が少し変わるが、本発明においては本質的な部分ではないので略する。）。ｗ（ａ）−ｗ（ｂ）＝０であれば零点が存在しないことが判明し、ｗ（ａ）−ｗ（ｂ）≠０であれば零点が存在することが判明する。
【００１３】
なお、Sturmの定理については、参考文献１を参照のこと。
（参考文献１）  高木貞治、代数学講義（改訂新版）、共立出版、１９６５．
もし、この段階で零点の存在が確認されれば、複素区間多項式Ｆ（ｘ）は領域Ｄにおいて零点を有する多項式を持つといえるので、零点位置判定処理を終了してよい。
【００１４】
もし、この段階で零点が存在しなければ、領域Ｄの内部において零点が存在するか否かの判定を行う。この判定には偏角の原理を用いることで達成される。なお、偏角の原理に基づく判定においては、領域Ｄの境界Ｃ上に代表多項式ｆ’（ｘ）の零点がないことが前提となるから、まず、境界Ｃ上での零点の有無を判定しておくのである。
【００１５】
偏角の原理に基づくアルゴリズムの適用について説明する。
【００１６】
区分境界Ｃｋの表示φｋ（ｓ）＋ｉ・ψｋ（ｓ）を代表多項式ｆ’（ｘ）に代入する。このとき、ｆ’（ｘ）＝ｆ’（φｋ（ｓ）＋ｉ・ψｋ（ｓ））＝ｕ（φｋ（ｓ），ψｋ（ｓ））＋ｉ・ｖ（φｋ（ｓ），ψｋ（ｓ））と表される。そこで、実部ｕ（φｋ（ｓ），ψｋ（ｓ））と虚部ｖ（φｋ（ｓ），ψｋ（ｓ））それぞれの実根を、ｓ∈Ｓにおいて求める。同様にして全ての区分境界について根を求め、これらの根を現れる順に並べたリストＳ１を作る。また、境界Ｃに囲まれた領域における根の計数用のリストＳ２を用意する（初期状態では、リストＳ２は空である。）。リストＳ１の先頭から順次に根を読み出すこととし、まず、先頭要素（根）Ａを取り出し、リストＳ２が空のリストであればそれをＳ２に書き込む。リストＳ２が空でないときは先頭要素（根）ＡとリストＳ２の先頭の要素（根）がともに実部の解であるかともに虚部の解であるかを判定し、この判定が真であればリストＳ２から先頭の要素（根）を取り除く。当該判定が偽であるときは先頭要素（根）ＡをリストＳ２の先頭に書き足す。この処理操作をリストＳ１の先頭から順次に根を読み出すことで行う。この結果、リストＳ２における要素（根）の個数の１／４が境界Ｃの内部に含まれる代表多項式ｆ’（ｘ）の根の数になる。この数が０であれば、代表多項式ｆ’（ｘ）の零点が領域Ｄ内部に存在しないことが判明し、この数が０でなければ、代表多項式ｆ’（ｘ）の零点が領域Ｄ内部に存在することが判明する。
【００１７】
なお、偏角の原理を用いた零点の存在判定については、参考文献２を参照のこと。
（参考文献２）  平野照比古、「偏角の原理を用いた多項式の根の数え上げ」、数式処理、Vol.9, No.4, pp.34-35, 2003.
もし、この段階で零点の存在が確認されれば、複素区間多項式Ｆ（ｘ）は領域Ｄにおいて零点を有する多項式を持つといえるので、零点位置判定処理を終了してよい。
【００１８】
ステップ２において、代表多項式ｆ’（ｘ）が領域Ｄの内部および境界Ｃ上において零点を有しないことが判明した場合、続いてステップ３の処理を行う。ステップ３以降の処理では、領域Ｄの境界Ｃ上において零点が存在するか否かを判定する。領域Ｄに零点を有しない多項式（代表多項式ｆ’（ｘ））の存在が確認された後は、複素区間多項式Ｆ（ｘ）が領域Ｄに零点を有する多項式を持つことと、複素区間多項式Ｆ（ｘ）が領域Ｄの境界Ｃに零点を有する多項式を持つこととは同値になるためである（特許文献１参照。）
＜ステップ３＞
領域Ｄの境界Ｃにおける区分境界を１つ選択する。つまり、境界Ｃを構成する区分境界Ｃ１，Ｃ２，・・・，ＣＫから１つ選択する。
【００１９】
＜ステップ４＞
後記《ステップ４の詳細》において説明する不等式が成立するか否かを判定する。不等式が成立する場合には、複素区間多項式Ｆ（ｘ）は領域Ｄにおいて零点を有する多項式を持つといえるので、零点位置判定処理を終了してよい。不等式が成立しない場合には、ステップ５の処理を行う。
【００２０】
＜ステップ５＞
未選択の区分境界が存在する場合には、その未選択の区分境界から１つの区分境界を選択し、ステップ４における不等式が成立するか否かの判定を行う。
【００２１】
未選択の区分境界が存在しない場合には、複素区間多項式Ｆ（ｘ）は領域Ｄにおいて零点を有する多項式を持たないことになり、零点位置判定処理を終了する。
【００２２】
《ステップ４の詳細》
以下に、上記ステップ４における不等式の判定について詳しく述べる。
【００２３】
複素数ｃに対して、「複素区間多項式Ｆ（ｘ）に属するある多項式ｆ（ｘ）について、ｆ（ｃ）＝０となる〔ｃは零点である。〕」ことと、「不等式（４）がｘ＝ｃで成立する」ことは同値である（非特許文献１参照。）。ただし、不等式（４）のｆ０（ｘ）は、式（５）で与えられる。
【００２４】
なお、ｒｊ，ｃｊについては、後述の［発明を実施するための最良の形態］の記載中の記号説明を参照のこと。
【数３】
2008269047.tif 000005
【００２５】
すなわち、「複素区間多項式Ｆ（ｘ）に属するある多項式ｆ（ｘ）の零点が領域Ｄの境界Ｃ上に存在する」ことと、「不等式（４）を満たす点が領域Ｄの境界Ｃ上に存在する」ことは同値となる。
【００２６】
不等式（４）に領域Ｄの境界Ｃの区分境界Ｃｋの表示φｋ（ｓ）＋ｉ・ψｋ（ｓ）（ｓ∈Ｓ）を代入すると、不等式（６）で表される。なお、右辺については、オイラーの公式を適用した（｜ｘｊ｜＝｜ｘ｜ｊ）。
【数４】
2008269047.tif 000006
【００２７】
不等式（６）は、両辺ともに０以上なので、両辺を平方した不等式（７）と同値である。
【数５】
2008269047.tif 000007
【００２８】
不等式（７）の左辺は、式（８）に等しい。
【数６】
2008269047.tif 000008
【００２９】
式（８）を展開すると、変数ｓに関する有理数係数の有理式となるので、式（８）をｋ（ｓ）と表すことにする。ただし、複素数ｃに対し、ｃ−（記号−は、ｃの上に−を付すことを表す。）はｃの複素共役（虚部の符号を変えた数）を表す。
【００３０】
不等式（７）の右辺は、式（９）に等しい。
【数７】
2008269047.tif 000009
【００３１】
ここで、ｈ１（ｓ）、ｈ２（ｓ）は変数ｓに関する有理数係数の有理式として表される。したがって、不等式（７）は不等式（１０）と同値である。
【数８】
2008269047.tif 000010
【００３２】
ｈ２（ｓ）は、整数ｒｊおよびφｋ（ｓ）＋ｉ・ψｋ（ｓ）の絶対値の偶数冪乗の和算・乗算から構成されるから０≦ｈ２（ｓ）となる。したがって、不等式（１０）の右辺は常に０以上であることに留意する。
【００３３】
以上から、不等式（１０）は以下の条件式（１１）と同値である。
【数９】
2008269047.tif 000011
【００３４】
条件式（１１）は、φｋ（ｓ）＋ｉ・ψｋ（ｓ）の絶対値（すなわち根号）を含まないため、有理式の範囲内で不等号判定が可能である。有理式によって表現される不等式の演算（不等号判定）は、絶対値や根号を含んだ不等式の演算に比して、演算効率が格段に良く、またアルゴリズムも簡単なものになるという利点がある。
【００３５】
条件式（１１）を満すｓが範囲Ｓｋに存在するか否かは既知の方法で判定できる。
ここで、Ｐ（ｓ）を、Ｐ（ｓ）＝ｋ（ｓ）−ｈ１（ｓ）、またはＰ（ｓ）＝（ｋ（ｓ）−ｈ１（ｓ））２−ｈ２（ｓ）２（φ（ｓ）２＋ψ（ｓ）２）とする。Ｐ（ｓ）は有理式である。この有理式Ｐ（ｓ）に対し、Ｐ（ｓ）≦０となるｓが範囲Ｓｋに存在するか否かの判定は、次に説明するとおりに行われる。なお、有理式Ｐ（ｓ）を既約な有理式で書いたときの分子をＱ（ｓ）とする。
【００３６】
（ａ）  Ｓｋ＝［ａ，ｂ］の場合、Ｐ（ａ）≦０あるいはＰ（ｂ）≦０ならば、「範囲Ｓｋに条件式（１１）を満たすｓが存在する」。そうでないならば、「Ｐ（ｓ）≦０を満すｓ∈［ａ，ｂ］が存在する」ことと、「Ｑ（ｓ）の零点が（ａ，ｂ）に存在する」ことは同値である。
【００３７】
（ｂ）  Ｓｋ＝（−∞，ｂ］の場合、Ｐ（ｂ）≦０ならば、「範囲Ｓｋに条件式（１３）を満たすｓが存在する」。そうでないならば、「Ｐ（ｓ）≦０を満すｓ∈（−∞，ｂ］が存在する」ことと、「（−∞，ｂ）の範囲にＱ（ｓ）の零点が存在する」ことは同値である。
【００３８】
（ｃ）  Ｓｋ＝［ａ，∞）の場合、Ｐ（ａ）≦０ならば、「範囲Ｓｋに条件式（１３）を満たすｓが存在する」。そうでないならば、「Ｐ（ｓ）≦０を満すｓ∈［ａ，∞）が存在する」ことと、「（ａ，∞）の範囲にＱ（ｓ）の零点が存在する」ことは同値である。
【００３９】
（ｄ）  Ｓｋ＝（−∞，∞）の場合、Ｐ（０）≦０ならば、「範囲Ｓｋに条件式（１３）を満たすｓが存在する」。そうでないならば、「Ｐ（ｓ）≦０を満すｓ∈（−∞，∞）が存在する」ことと、「（−∞，∞）の範囲にＱ（ｓ）の零点が存在する」ことは同値である。
【００４０】
上記の（ａ）〜（ｄ）において、与えられた範囲ＳｋにＱ（ｓ）の零点が存在するか否かは、例えば上述したSturmの定理に基づくアルゴリズムで判定可能である。
【００４１】
以上では「複素区間多項式Ｆ（ｘ）に属するある多項式ｆ（ｘ）の零点が領域Ｄの境界Ｃ上に存在する」ことと「不等式（４）を満たす点が領域Ｄの境界Ｃ上に存在する」ことは同値であるから、不等式（４）に領域Ｄの境界Ｃの区分境界Ｃｋの表示φｋ（ｓ）＋ｉ・ψｋ（ｓ）（ｓ∈Ｓ）を代入するとした。
【非特許文献１】H.J.Stetter,"The nearest polynomial with a given zero, and similar problems", ACM SIGSAM Bulletin, Vo1.33, No.4, pp.2-4, 1999.
【非特許文献２】山本哲朗、「区間多項式のロバスト安定性に関するKharitonovの定理をめぐって」、電子情報通信学会誌、Ｖｏ１．８１、Ｎｏ．２、ｐｐ．１７４−１８２、１９９８.
【非特許文献３】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.
【特許文献１】特開２００７−３４９９０号公報
【発明の開示】
【発明が解決しようとする課題】
【００４２】
従来技術においては、ステップＳ４の処理において、各区分境界Ｃｋごとに、その区分境界Ｃｋ上の一点について、その点を零点とする多項式が複素区間多項式Ｆ（ｘ）内に存在するかどうかを確認していた（ステップＳ４の（ａ）〜（ｂ）参照。）。そして、その点を零点とする多項式が複素区間多項式Ｆ（ｘ）内に存在しない場合には、条件式（１１）の左辺に現れる有理式の零点が指定に区間内に存在するか否かを判定していた。したがって、区分境界Ｃｋの数が多い場合には、効率が悪い。
【００４３】
本発明の課題は、多数の点について不等式の成立判定をすることを回避した効率の良い複素区間多項式の零点の位置判定方法、装置、プログラム及びその記録媒体に関する技術を提供することである。
【課題を解決するための手段】
【００４４】
本発明によれば、複素区間多項式の零点の位置を判定する方法において、記憶手段には、区間数が複素平面上の円領域で表される複素区間多項式と、有理関数で表される有限個の区分境界線から構成される複素領域の境界線と、その境界線によって分けられた複素平面上の領域がそれぞれ記憶される。代表多項式選択手段が、記憶手段に記憶される複素区間多項式に属する多項式を１つ選択する。代表多項式零点判定手段が、上記選択された代表多項式が、記憶手段に記憶された複素平面上の領域に零点を有するか否かを判定する。代表点選択手段が、記憶手段に記憶された境界線上の任意の一点（以下、代表点とする。）を選択する。多項式判定手段が、上記代表点を零点とする多項式が、記憶手段に記憶された複素区間多項式の中に存在するか否かを判定する。等式判定手段が、多項式判定ステップにおいて、上記代表点を零点とする多項式が存在しないと判定された場合に、所定の等式を成立させる複素数が、区分境界線上にあるか否かを区分境界線ごとに判定して、その判定結果を上記複素区間多項式が零点を有するか否かを表す情報として出力する。
【発明の効果】
【００４５】
本発明によれば、区分境界Ｃｋの数に関わらず、境界Ｃ上の一点について、その点を零点に持つ多項式が複素区間多項式Ｆ（ｘ）内にあるかどうかを調べれば良い。このため、計算効率が良い。
【発明を実施するための最良の形態】
【００４６】
[理論]
本発明の実施形態の説明に先立ち、本発明の理論について説明する。なお、ステップＳ１，Ｓ２の処理は従来技術と同様である。ステップＳ３〜Ｓ５の処理が従来技術とは異なる。図２と図３に、零点位置判定方法のフローチャートを例示する。図２の六角形で囲まれたＡと図３の六角形で囲まれたＡは、いわゆる他ページ結合子を意味し、図２のステップＳ２２においてｎｏと判定された場合、次に図３のステップＳ３を行うことを意味する。
【００４７】
はじめに、この明細書における記号および用語の説明をする。
【００４８】
複素数ｃおよび非負の実数ｒに対し、区間数｛ｃ；ｒ｝を、｜ｘ−ｃ｜≦ｒを満たす複素数ｘ全体の集合とする。すなわち、区間数は複素平面上の円領域として表現される。このとき、複素区間多項式Ｆ（ｘ）は、上記区間数｛ｃ；ｒ｝を各項の係数として式（１２）のように表記されるものであり、各ｊ（１≦ｊ≦ｄ、ただしｊは整数。）に対して係数がａｊ∈｛ｃｊ；ｒｊ｝である多項式ｆ（ｘ）〔式（４）参照〕の全体の集合を表す。ただし、ｃｊの実部と虚部、および、ｒｊは代数的数（整数係数一次代数方程式の根となる数）とし、例えば有理数である。また、ｅｊ（ｘ）は複素係数の多項式とする。
【数１０】
2008269047.tif 000012
【００４９】
有界な複素領域Ｄ（以下、単に「領域Ｄ」という。）の境界Ｃは、長さが有限な単純閉曲線（Jordan閉曲線）であるものとし、境界Ｃは、１つ以上の有限個の区分境界Ｃｋの和集合として表現されているものとする。すなわち、Ｃ＝Ｃ１∪Ｃ２∪・・・∪ＣＫ（Ｋは１以上の整数とする。）である。ただし、各区分境界Ｃｋは、パラメータｓによってΦｋ（ｓ）＝φｋ（ｓ）＋ｉ・ψｋ（ｓ）と表示されるとする〔ｋ＝１，２，・・・，Ｋ〕。ｉは、虚数単位を表す。ここで、φｋ（ｓ）、ψｋ（ｓ）は有理数係数の有理式であるとし、ｓの動く範囲Ｓｋは、［ａ，ｂ］、（−∞，ｂ］、［ａ，∞）、（−∞，∞）のいずれかであるとする。[・，・]は閉区間、（・，・］は左開右閉区間、［・，・）は左閉右開区間、（・，・）は開区間を表す。また、パラメータｓと区分境界Ｃｋとの間は単射であるとする。すなわち、式（１４）で表される関係があるとする。
【数１１】
2008269047.tif 000013
【００５０】
領域Ｄが有界ではないとき、すなわち、０を中心とするどんなに半径が大きい円をとってもその内部に領域Ｄ全部が含まれないときは、複素区間多項式Ｆ（ｘ）に属する多項式ｆ（ｘ）の次数が一定であるとする。
このとき、以下のようにして、複素区間多項式Ｆ（ｘ）内に、所定の複素領域Ｄ内に零点を持つ多項式があるか否かを判定する。
【００５１】
＜ステップ１＞
まず、複素区間多項式Ｆ（ｘ）に属する多項式を一つ選択する。これを代表多項式と呼びｆ’（ｘ）で表す。
【００５２】
＜ステップ２＞
領域Ｄ内に代表多項式ｆ’（ｘ）の零点が存在するか否かを判定する。この判定は、公知の手法によって達成される。
【００５３】
まず、領域Ｄの境界Ｃ上において零点が存在するか否かの判定を行う。例えば、領域Ｄの境界Ｃの表示φ（ｓ）＋ｉ・ψ（ｓ）を代表多項式ｆ’（ｘ）に代入した後、Sturmの定理に基づくアルゴリズムに従って零点の有無を判定する。Sturmの定理に基づくアルゴリズムについては、背景技術の記載及び特許文献１の記載を参照のこと。
【００５４】
もし、この段階で零点の存在が確認されれば、複素区間多項式Ｆ（ｘ）は領域Ｄにおいて零点を有するといえるので、零点位置判定処理を終了してよい。
【００５５】
もし、この段階で零点が存在しなければ、領域Ｄの内部において零点が存在するか否かの判定を行う。この判定には偏角の原理を用いることで達成される。なお、偏角の原理に基づく判定においては、領域Ｄの境界Ｃ上に代表多項式ｆ’（ｘ）の零点がないことが前提となるから、まず、境界Ｃ上での零点の有無を判定しておくのである。偏角の原理を用いた零点の存在判定については、背景技術の記載及び特許文献１の記載を参照のこと。
【００５６】
もし、この段階で零点の存在が確認されれば、複素区間多項式Ｆ（ｘ）は領域Ｄにおいて零点を有するといえるので、零点位置判定処理を終了してよい。
【００５７】
ステップ２において、代表多項式ｆ’（ｘ）が領域Ｄの内部および境界Ｃ上において零点を有しないことが判明した場合、続いてステップ３の処理を行う。ステップ３以降の処理では、領域Ｄの境界Ｃ上において零点が存在するか否かを判定することに留意する。なぜなら、領域Ｄに零点を持たない多項式ｆ’（ｘ）∈Ｆ（ｘ）が存在することがわかっている場合には、領域Ｄに零点を持つ多項式が複素区間多項式Ｆ（ｘ）に属することと、領域Ｄの境界Ｃ上に零点を持つ多項式が複素区間多項式Ｆ（ｘ）に存在することとが同値となるためである。その証明については、特許文献１を参照のこと。
【００５８】
＜ステップＳ３＞
領域Ｄの境界Ｃ上の一点を取り、代表点ｃとする。
【００５９】
＜ステップＳ４＞
代表点ｃを零点とする多項式が、複素区間多項式Ｆ（ｘ）の中に存在するか否かを判定する。存在すれば、代表点ｃを返して終了する。存在しなければ、ステップＳ５の処理を行う。
【００６０】
＜ステップＳ５＞
区分境界Ｃｋごとに、後述する所定の等式を成立させる点が、Ｃｋ上に存在するかどうかを判定する。存在すれば、Ｃｋを返して終了する。所定の等式とは、例えば、後述する式（Ａ）を等号で結んだ式であり、後述する式（Ｃ）である。
【００６１】
以上が、本発明による複素区間多項式の零点の位置判定方法の流れの概要である。
【００６２】
≪ステップＳ３，Ｓ４の詳細について≫
ステップＳ３，Ｓ４において、領域Ｄの境界Ｃ上の任意の一点である代表点ｃを零点とする多項式が複素区間多項式Ｆ（ｘ）に存在するかどうかを調べておけば、ステップＳ５において、不等式ではなく、等式を成立させる点の存在のみを調べれば十分である理由は以下の通りである。
【００６３】
《理由》
非特許文献１及び背景技術の記載より、複素数αを零点とする多項式が複素区間多項式Ｆ（ｘ）に存在する必要十分条件は、以下の不等式（Ａ）が成立することである。
【数１２】
2008269047.tif 000014
領域Ｄの境界Ｃ上の一点αが、式（Ａ）を満たすならば、複素区間多項式Ｆ（ｘ）に属する多項式でα∈Ｃ⊂Ｄに零点を持つものが存在する。以下、領域Ｄの境界Ｃ上のある一点αで、式（Ａ）が成立しないとする。すなわち、αにおいて、式（Ａ）の不等号＞が成り立っているとする。
【００６４】
ステップＳ２において、領域Ｄに零点を持たない多項式ｆ’（ｘ）∈Ｆ（ｘ）が存在することがわかっているため、「領域Ｄに零点を持つ多項式が複素区間多項式Ｆ（ｘ）に属することと、領域Ｄの境界Ｃ上に零点を持つ多項式が複素区間多項式Ｆ（ｘ）に存在することが同値」となることは、特許文献１の記載の通りである。
【００６５】
もし、境界Ｃ上のある点βにおいて、式（Ａ）の等号が成立するならば、明らかに複素区間多項式Ｆ（ｘ）に属する多項式でβ∈Ｃ⊂Ｄを零点とするものが存在する。
【００６６】
逆に、領域Ｄに零点を持つ多項式が複素区間多項式Ｆ（ｘ）に存在するならば、上記したように領域Ｄの境界Ｃ上に零点を持つ多項式が存在する。以下、その境界Ｃ上の零点をβとする。もし、βにおいて式（Ａ）の等号が成り立つならば証明終わり。そうでない場合、不等号＜が成り立っている。境界Ｃ上の点ｚを、βからαに向かって境界Ｃ上を動かして行くと、式（Ａ）の左辺から右辺を引いたものはｚについての連続関数であり、ｚ＝αにおいては＋であり、ｚ＝βにおいては−であり、異符号である。よって、どこか中間の点ｚ＝γにおいて、式（Ａ）の左辺から右辺を引いたものは０となる。すなわち、このγにおいて、式（Ａ）の等号が成り立つ。このように、領域Ｄに零点を持つ多項式が複素区間多項式Ｆ（ｘ）に存在するならば、式（Ａ）の等号を成立させる点が境界Ｃ上に必ず存在する。
【００６７】
以上より、  ステップＳ３，Ｓ４において、領域Ｄの境界Ｃ上の任意の一点である代表点ｃを零点とする多項式が複素区間多項式Ｆ（ｘ）に存在するかどうかを調べておけば、ステップＳ５において、不等式ではなく、等式を成立させる点の存在のみを調べれば十分であることが示された。
【００６８】
なお、境界Ｃは、少なくともひとつの区分境界Ｃｋから構成されるため、この区分境界Ｃｋごとに、この区分境界Ｃｋ上の零点であって、式（Ａ）の等号を成立させるものがあるか否かを調べる点に留意する。
【００６９】
以下、ステップＳ４の具体的な計算方法について説明する。
【００７０】
ｅｊ（ｘ）が、ｘの単項式である場合には、１つの区分境界Ｃｋと、１つのσ∈Ｓｋを取り、背景技術に記載した式（１１）がｓ＝σで成立するか否かを従来技術と同様の方法で調べる。どのσ∈Ｓｋでもよいので、特に有理数であるσを取れば、正確演算により式（１１）が、ｓ＝σで成立するか否かを容易に判定することができる。
【００７１】
ｅｊ（ｘ）が一般の場合は以下の通り。上記の通り、複素数αを零点とする多項式が複素区間多項式Ｆ（ｘ）に存在する必要十分条件は、式（Ａ）が成立することである。境界Ｃについての条件より、複素数αとして実部、虚部ともに有理数である点を取ることができるので、そのようなαに対して、式（Ａ）はｑ及びｑｊを非負の有理数として以下の形となる。
【数１３】
2008269047.tif 000015
式（１５）が成立するか否かは、まず等号が成立するか否かを正確演算で判定する。等号が成立しないときに不等号が成立するか否かの判定は、例えば誤差解析付きの近似計算（区分演算など）により、十分に近似精度を上げれば可能である。
【００７２】
≪ステップＳ５の詳細について≫
式（Ａ）の等号を成立させるα∈Ｃｋが存在するか否かの判断は、例えばコンピュータ上で以下のように行う。その処理の流れを例示するフローチャートを図３に示す。
【００７３】
αの与え方によっては、式（Ａ）のままでもコンピュータで処理することができる。しかし、一般に、式（Ａ）のままでは、式（Ａ）の右辺を計算機で処理することができない場合がある。また、等号を厳密に判断することができない場合がある。このために、式（Ａ）の右辺を零点として持つ多項式Ｑを導入し、この多項式Ｑの情報を用いて、式（Ａ）を成立させるα∈Ｃｋが存在するか否かを判断する。
【００７４】
以下の手順により、多項式Ｐ０，…，Ｐｎ，Ｑを構成する（ステップＳ５１）。ここで、Ｑ（ｘ２）は、多項式Ｑ（ｘ）のｘに、ｘ２を代入した式のことである。
【数１４】
2008269047.tif 000016
【００７５】
このようにすると、以下の事実が成り立つ。
《事実》
１．Ｐｊ（ｊ＝１，…，ｎ）は、ｘ２の多項式である。
２．Ｐｎの次数は２ｎであり、その零点は、
【数１５】
2008269047.tif 000017
である。ただし、すべての＋，−の組合せを取る。すなわち、Ｐｎの零点は、２ｎ個存在する。例えばｎ＝２の場合、Ｐｎの零点は、下の４（＝２２）つである。
【数１６】
2008269047.tif 000018
３．Ｑ（ｘ）の次数は２ｎ−１であり、その零点は、下式の通りである。ただし、すべての＋，−の組合せを取る。すなわち、Ｑ（ｘ）の零点は、重複も含めて２ｎ−１個存在する。
【数１７】
2008269047.tif 000019
ここで、Ｑ（ｘ）の零点は、式（Ａ）の右辺の平方であるｒ１｜ｅ１（α）｜＋…＋ｒｎ｜ｅｎ（α）｜を含む。すなわち、式（Ａ）の右辺の平方は、Ｑの零点（の１つ）である。
【００７６】
上記の事実を用いると、以下のようにして、式（Ａ）の等号を成立させるα∈Ｃｋが存在するか否かを判定することができ、また、式（Ａ）の等号を成立させるαを求めることができる。以下では、α＝Φｋ（ｓ）と表示する。
【００７７】
多項式Ｑ（ｘ）のｘに、式（Ａ）の左辺の平方である
【数１８】
2008269047.tif 000020
を代入して、ｓの有理式（Ｂ）を生成する（ステップＳ５３）。
【数１９】
2008269047.tif 000021
ここで、［・］−は、すなわち・の上にバーを付けたものは、・の複素共役を意味する。また、関数ｆ−（・）、すなわち、有理関数ｆの上にバーを付けたものは、有理関数ｆの各係数について複素共役を取ることを意味する。
【００７８】
式（Ｂ）のｘについての零点（Ｑ＝０をｘについて解いたもの）は、上記事実の「３．」より、
【数２０】
2008269047.tif 000022
である。これらの零点はそれぞれ、式（Ａ）の左辺の平方と等しい。なぜなら、式（Ｂ）においてＱ（ｘ）のｘに代入したのは、式（Ａ）の左辺の平方であるからである。このため、式（Ｂ）の零点の中に、式（Ａ）の両辺を二乗した式である、
【数２１】
2008269047.tif 000023
を成り立たせるもの、すなわち式（Ａ）の等号を成り立たせるものがある。
【００７９】
式（Ｂ）＝０をｓ∈Ｓｋについて解き、換言すると、区間Ｓｋに入るＱの実零点を求め、式（Ａ）の等号を成立させるｓの候補を求める（ステップＳ５４）。そして、求まったｓの候補について、実際に式（Ａ）の等号が成立させるかどうか、すなわち、下式（Ｃ）を満たすかどうかを調べる（ステップＳ５５）。
【数２２】
2008269047.tif 000024
【００８０】
一般に、ｓ及びαは無限に存在するため、式（Ｃ）を満たすかどうかをコンピュータですべて調べることはできない。しかし、このように、多項式Ｑ（ｘ）を導入し、そこから得られる情報を元にして、式（Ｃ）を満たすｓの候補を有限個（重複も含めて２ｎ−１個）に絞ることにより、コンピュータで調べることが可能となる。
【００８１】
式（Ｃ）を満たす、Ｓｋに属する式（Ｂ）の零点が存在する必要十分条件は、Ｆ（ｘ）の中に、区分境界Ｃｋ上に零点を持つ多項式が存在することである。すなわち、ｓの候補である式（Ｂ）の零点が式（Ｃ）を満たせば、Ｆ（ｘ）の中に、区分境界Ｃｋ上に零点を持つ多項式が存在する（ステップＳ５６）。一方、ｓの候補である式（Ｂ）の零点が式（Ｃ）を満たさない場合には、Ｆ（ｘ）の中に、区分境界Ｃｋ上に零点を持つ多項式が存在しない（ステップＳ５７）。
【００８２】
式（Ｂ）の各零点が、式（Ｃ）を満たすか否かは、誤差解析付きの近似計算、例えば区間演算により調べることが可能である。なぜなら、式（Ｂ）のどの零点がｅｊ（Φｋ（ｓ））の零点であるかは、例えばＧＣＤ計算とＳｔｕｒｍのアルゴリズムにより確認が可能であり、式（Ｂ）の各零点σについて、ｓ＝σとした式（Ｃ）の左辺
【数２３】
2008269047.tif 000025
は、事実の「２．」より以下のどれかと等しいからである。
【数２４】
2008269047.tif 000026
この確認を近似計算で実行可能なように、上記の通り、予め式（Ｂ）とｅｊ（Φｋ（ｓ））との共通零点を調べておく。
【００８３】
［実施形態］
図１〜３を参照して、複素区間多項式の零点の位置判定装置（以下、零点位置判定装置１とする。）について説明をする。図１は、零点位置判定装置１の機能構成を例示する図である。図２,３は、零点位置判定方法のフローチャートを例示する図である。
【００８４】
零点位置判定装置１は、図１に例示するように、代表多項式選択部２、記憶部３、代表多項式零点判定部４、代表点選択部５、多項式判定部６、等式判定部７、取得部８を備える。代表多項式零点判定部４は、例えば境界上零点判定部４１、領域内部零点判定部４２を備える。等式判定部７は、第一Ｑ式生成部７１、第二Ｑ式生成部７２、零点演算部７３、検証部７４、バッファ７５を備える。
【００８５】
記憶部３は、零点位置判定装置１の各部とデータの読み書きが可能なように接続されている。本発明の処理に先立って、記憶部３には、区間数が複素平面上の円領域で表される複素区間多項式Ｆ（ｘ）に関する情報（すなわちｊ＝１,…,ｎとして、各項ｅｊ（ｘ）、各項の区間数の中心点ｃｊと半径ｒｊ等）、有理関数で表された区分境界Ｃｋに関する情報（例えば、Ｃｋのｓによるパラメータ表示φ（ｓ）と、ｓの動く範囲Ｓｋ等）、区分境界Ｃｋの集合である境界Ｃによって分けられた複素平面上の領域（領域Ｄの内部についての情報）等のデータが、取得部８から入力され、格納される。
【００８６】
＜ステップＳ１＞
代表多項式選択部２は、記憶部３に記憶される複素区間多項式Ｆ（ｘ）に属する任意の多項式を１つ選択し、それを代表多項式ｆ’（ｘ）とする（ステップＳ１）。選択された代表多項式ｆ’（ｘ）は、代表多項式零点判定部４に出力される。
【００８７】
＜ステップＳ２＞
代表多項式零点判定部４は、領域Ｄに、代表多項式ｆ’（ｘ）が零点を有するか否かを判定する。ステップＳ２は、図２に例示するように、例えば、ステップＳ２１〜ステップＳ２２の処理から構成される。代表多項式ｆ’（ｘ）が領域Ｄに零点を有しないと判定された場合には、その旨を表す信号が代表点選択部５に出力される。
【００８８】
≪ステップＳ２１≫
まず、代表多項式零点判定部４の境界上零点判定部４１が、領域Ｄの境界Ｃ上に代表多項式ｆ’（ｘ）が零点を有するか否かを判定する（ステップＳ２１）。例えば、領域Ｄの境界の表示φ（ｓ）＋ｉ・ψ（ｓ）を代表多項式ｆ’（ｘ）に代入した後、Ｓｔｕｒｍの定理に基づくアルゴリズムに従って零点の有無を判定する。この際、境界上零点判定部４１は、境界Ｃについての情報を記憶部３から読み出す。
【００８９】
もし、この段階で零点の存在が確認されれば、複素区間多項式Ｆ（ｘ）は領域Ｄにおいて零点を有する多項式を有するといえるので、零点位置判定処理を終了しても良い（ステップＳ２３）。
【００９０】
≪ステップＳ２２≫
この段階で零点が存在しなければ、領域内部零点判定部４２は、代表多項式ｆ’（ｘ）が領域Ｄの内部において零点を有するか否かの判定を行う（ステップＳ２２）。この際、領域内部零点判定部４２は、領域Ｄの内部についての情報を記憶部３から読み込む。この判定には偏角の原理を用いることで達成される。なお、偏角の原理に基づく判定においては、領域Ｄの境界Ｃ上に代表多項式ｆ’（ｘ）の零点がないことが前提となるから、まず、ステップＳ２１において境界Ｃ上での零点の有無を判定している。
【００９１】
もし、この段階で零点の存在が確認されれば、複素区間多項式Ｆ（ｘ）は領域Ｄにおいて零点を有する多項式を有するといえるので、零点位置判定処理を終了しても良い（ステップＳ２４）。
【００９２】
＜ステップＳ３（図３）＞
代表多項式ｆ’（ｘ）が領域Ｄに零点を有しない旨を表す信号を受けた代表点選択部５は、記憶部３に記憶された境界線Ｃ上の任意の一点を選択して、その選択された点を代表点ｃとする（ステップＳ３）。その際、代表点選択部５は、境界Ｃに関する情報を記憶部３から読み込む。代表点選択部５は、選択された代表点ｃは、多項式判定部６に出力する。
【００９３】
＜ステップＳ４＞
多項式判定部６は、代表点ｃを零点とする多項式が、記憶部３に記憶された複素区間多項式Ｆ（ｘ）の中に存在するか否かを判定する（ステップＳ４）。存在すれば、複素区間多項式Ｆ（ｘ）は、領域Ｄに零点を有する多項式を持つため処理を終了する（ステップＳ４１）。存在しない場合には、その旨の信号を等式判定部７に出力する。
【００９４】
具体的には、多項式判定部６は、記憶部３から読み込んだｅｊ（ｘ）が、ｘの単項式である場合には、記憶部３から読み込んだ１つの区分境界Ｃｋと、記憶部３から読み込んだＳｋから１つのσ∈Ｓｋを取り、背景技術に記載した式（１１）がｓ＝σで成立するか否かを従来技術と同様の方法で調べる。
【００９５】
ｅｊ（ｘ）が一般の場合には、上記式（１５）が成立するか否かを、まず等号が成立するか否かを正確演算で判定する。等号が成立しないときに不等号が成立するか否かの判定を、例えば誤差解析付きの近似計算（区間演算など）により行う。
【００９６】
＜ステップＳ５＞
代表点ｃを零点とする多項式が複素区間多項式Ｆ（ｘ）の中に存在しない旨を表す信号を受けた等式判定部７は、所定の等式を成立させる複素数が、区分境界線Ｃｋ上にあるか否かを区分境界線Ｃｋごとに判定して、その判定結果を出力する（ステップＳ５）。所定の等式とは、例えば、上記式（Ｃ）である。ステップＳ５の処理は、図３に例示する、ステップＳ５１〜ステップＳ５１０の各処理から構成される。
【００９７】
等式判定部７の第一Ｑ式生成部７１は、記憶部３から読み込んだｒｊ、ｅｊ（ｘ）を用いて、多項式Ｐ０（ｘ），…，Ｐｊ（ｘ），…，Ｐｎ（ｘ）を生成して、これらの生成された多項式Ｐ０（ｘ），…，Ｐｊ（ｘ），…，Ｐｎ（ｘ）から、Ｑ（ｘ）を生成する（ステップＳ５１）。生成されたＱ（ｘ）は、等式判定部７の第二Ｑ式生成部７２に出力される。
【００９８】
等式判定部７は、バッファ７５に記憶されたｋを、ｋ＝１とする（ステップＳ５２）。
【００９９】
第二Ｑ式生成部７２は、上記生成されたＱ（ｘ）と、記憶部３から読み込んだΦｋ（ｓ）とを用いて、ｓの有理式である式（Ｂ）を生成する（ステップＳ５３）。生成された式（Ｂ）は、零点演算部７３に送られる。すなわち、ｋごとに異なるｓ有理式Ｑｋ（ｓ）を生成して、零点演算部７３に送る。
【０１００】
零点演算部７３は、上記生成された式（Ｂ）と、記憶部３から読み込んだＳｋを用いて、式（Ｂ）の実零点を求めて、検証部７４に送る（ステップＳ５４）。
【０１０１】
検証部７４は、上記求まった実零点と、記憶部３から読み込んだｃｊ，ｅｊ,φｋ（ｓ）とを用いて、上記求まった実零点が、上記式（Ｃ）を満たすか否かを検証する（ステップＳ５５）。検証部７４は、例えば誤差解析付きの近似計算、例えば区間演算により調べる。ステップＳ５４において求まった実零点が複数存在する場合には、複数の実零点のそれぞれについて、式（Ｃ）を満たすか否かを検証する。検証結果として、例えば、式（Ｃ）を満たす場合には、そのときの区分境界Ｃｋ及び／又はその零点を出力する。また、式（Ｃ）を満たさない場合には、その旨の信号を出力する。
【０１０２】
式（Ｃ）を満たせば、領域Ｄの境界Ｃ上に零点を持つ多項式が複素区間多項式Ｆ（ｘ）に存在すると判断することができる。すなわち、複素区間多項式Ｆ（ｘ）は、領域Ｄに零点に持つ多項式を有すると判断することができる（ステップＳ５６）。
【０１０３】
式（Ｃ）を満たさない場合には、領域Ｄの境界Ｃ上に零点を持つ多項式が複素区間多項式Ｆ（ｘ）に存在しないと判断することができる。すなわち、複素区間多項式Ｆ（ｘ）は、領域Ｄに零点に持つ多項式を有しないと判断することができる（ステップＳ５７）。
【０１０４】
式（Ｃ）を満たさない場合には、バッファ７５に格納されたｋが記憶部３から読み込んだＫ以上であるか否かを判定する（ステップＳ５８）。
【０１０５】
ｋ＜Ｋである場合（ｋ≧Ｋでない場合）には、バッファ７５に格納されたｋをインクリメントして（ステップＳ５９）、ステップＳ５３の処理に戻る。このようにして、すべての区分境界Ｃｋ（ｋ＝１,…,Ｋ）について、その区分境界Ｃｋ上に式（Ｃ）を満たす複素数が存在するか否かを調べる。ｋ≧Ｋである場合には、処理を終了する。
【０１０６】
なお、図３に破線で記載したように、ステップＳ５６の後に、ｋ≧Ｋであるか否か、すなわちバッファ７５に格納されたｋが記憶部３から読み込んだＫ以上であるか否かを判定するステップＳ５１０を設けても良い。これにより、すべての区分境界Ｃｋ上にある零点を漏れなく見つけることができる。
【０１０７】
なお、上記ではｋ＝１から初めてｋが小さい方から順番に区分境界Ｃｋが式（Ｃ）を満たすか否かを判定した。しかし、この順番は任意であり、任意のｋから区分境界Ｃｋが式（Ｃ）を満たすか否かを判定してもよい。
【０１０８】
以上では説明を簡単にするために、現れる数について、実の場合は有理数、複素の場合は実部、虚部ともに有理数としたが、アルゴリズムの実行のためには四則演算および等号判定が実行できれば十分なので、例えば実代数的数（整数係数一次代数方程式の根となる実数）としてもそのまま通用する。
【０１０９】
また、区間多項式に属する多項式の次数が一定のときは、領域Ｄの境界Ｃが閉曲線でなくてもよい。例えば、Ｄが半平面の場合などである。
【０１１０】
零点位置判定装置１をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムを図４に例示するコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【０１１１】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよいが、具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（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）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０１１４】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、各装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【０１１５】
また、上述の各種の処理は、記載にしたがって時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【０１１６】
［具体例］
≪例１≫
複素区間多項式Ｆ（ｘ）を、
【０１１７】
【数２５】
2008269047.tif 000027
領域Ｄを、頂点が、
【０１１８】
【数２６】
2008269047.tif 000028
である長方形の周及び内部とする。長方形の周のパラメータ表示は、
【０１１９】
【数２７】
2008269047.tif 000029
とする。このとき、複素区間多項式Ｆ（ｘ）に属する多項式ｆ（ｘ）であって、領域Ｄに零点を持つものは存在するか否かを判定する。
【０１２０】
１．代表多項式ｆ’（ｘ）として、各区間数の中心を係数とする多項式を取る。すなわち、ｆ０（ｘ）＝ｘ２−０．６５ｘ＋１とする。
【０１２１】
２．代表多項式ｆ’（ｘ）の零点は０．３２５±ｉ・０．９４５７１…で、領域Ｄに属さないので、判定結果は「存在しない」となる。なお、この例では、代表多項式ｆ’（ｘ）が２次式なので直接零点を求めることができたが、一般には前述の通り、境界Ｃ上に零点が存在するか否かの判定と、領域Ｄの内部に零点が存在するか否かの判定を行う。
【０１２２】
３．境界Ｃ上の代表点として、０．３＋０．８ｉを取る。
【０１２３】
４．このとき調べるべき条件は、
【０１２４】
【数２８】
2008269047.tif 000030
が成立するか否か、すなわち、
【０１２５】
【数２９】
2008269047.tif 000031
が成立するか否かである。この例では、ｅｊ（ｘ）がｘの単項式なので、特許文献１に記載された方法により判定可能であるが、以下では、ｅｊ（ｘ）が一般の場合（すなわち、単項式ではない場合）の方法で説明をする。仮定から、小数はすべて正確としてよい。
【０１２６】
【数３０】
2008269047.tif 000032
２６６５を素因数分解すると、５・１３・４１、一方、７３は素数だから、上記式（ａ）において等号は成立しないことが分かる。
【０１２７】
よって、近似計算により不等号が成立するか否かを調べる。
【０１２８】
【数３１】
2008269047.tif 000033
これにより、式（ａ）は不成立と分かる。
【０１２９】
５．まだ、調べていない境界区分Ｃｋが存在するので、そのうちの１つＣ１を取る。
【０１３０】
６．代表多項式ｆ’（ｘ）＝ｘ２−０．６５ｘ＋１なので、式（７）の左辺ｇ（ｓ）は以下の通り。
【０１３１】
【数３２】
2008269047.tif 000034
式（７）の右辺は以下の通り。
【０１３２】
【数３３】
2008269047.tif 000035
よって、式（８）は以下の通り。
【０１３３】
【数３４】
2008269047.tif 000036
これは以下と同値である。
【０１３４】
【数３５】
2008269047.tif 000037
あるいは
【０１３５】
【数３６】
2008269047.tif 000038
Ｓｔｕｒｍの定理に基づくアルゴリズムにより、このいずれの左辺の多項式も（０．３,０．３２]に零点を持たないことがわかる。すなわち、等号を成立させる点は、Ｃ１上には存在しない。よって、ステップ５．に戻る
５．まだ、調べていない境界区分Ｃｋが存在するので、そのうちの１つＣ２を取る。
【０１３６】
６．式（７）の左辺ｇ（ｓ）は以下の通り。
【０１３７】
【数３７】
2008269047.tif 000039
また、式（７）の右辺は以下の通り。
【０１３８】
【数３８】
2008269047.tif 000040
よって、式（８）は以下の通り。
【０１３９】
【数３９】
2008269047.tif 000041
これは、以下と同値である。
【０１４０】
【数４０】
2008269047.tif 000042
あるいは、
【０１４１】
【数４１】
2008269047.tif 000043
この最初の不等式について調べる。Ｓｔｕｒｍのアルゴリズムにより、左辺の多項式は、（０．８,１．２]に２つの零点を持つことがわかり、すなわち等号を成立させる点が２点存在することがわかり、境界の区分Ｃ２を返して判定は終了する。
【０１４２】
≪例２≫
以下の複素区間多項式Ｆ（ｘ）と、複素領域Ｅ（ｒ）に対して、Ｆ（ｘ）に属する多項式で、複素領域Ｅ（ｒ）に零点を持つものが存在するか否かを調べる。
【０１４３】
【数４２】
2008269047.tif 000044
ただし、
【０１４４】
【数４３】
2008269047.tif 000045
である。複素領域Ｅ（ｒ）は、中心が原点、半径がｒの開円板の外側とする。その境界Ｃ（ｒ）は、
【０１４５】
【数４４】
2008269047.tif 000046
ただし、Ｃ１（ｒ）はＣ（ｒ）から１点ｒを除いた集合とし、
【０１４６】
【数４５】
2008269047.tif 000047
と表されているものとする。
【０１４７】
複素領域Ｅ（ｒ）は非有界であるが、複素区間多項式Ｆ（ｘ）に属する多項式の次数はすべて等しいので、本発明を適用することが可能である。
【０１４８】
以下、Ｅ（１．０７）及びＥ（１．０６）内に、複素区間多項式Ｆ（ｘ）に属する多項式の零点となり得る点が存在するか否かを判定する。共通となる部分も多いので、以下の説明では、Ｅ（１．０７）及びＥ（１．０６）に対する処理を並行して記述する。
【０１４９】
１．まず、ｆ’（ｘ）＝ｘ３−１を代表多項式として採用する。
【０１５０】
２．代表多項式ｆ’（ｘ）が、１＜ｒのとき、複素領域Ｅ（ｒ）に零点を持たないことは明らかである。代表多項式の零点は、すべて絶対値が１であるからである。
【０１５１】
３．ｒ＝１．０７（Ｅ（１．０７の場合））としても、１．０６（Ｅ（１．０６）の場合）としても、境界Ｃ（ｒ）乗の代表点ｒを零点として持つ多項式は複素区間多項式Ｆ（ｘ）の中に存在しない。
【０１５２】
４．まず、Ｃ（１．０７）に対しては以下の通り、式（Ｂ）
【０１５３】
【数４６】
2008269047.tif 000048
の分子は、４８次式であり、調べると実零点を持たないことが分かる。よって、複素区間多項式Ｆ（ｘ）に属する多項式でＥ（１．０７）に零点を持つものは存在しない。
【０１５４】
次に、Ｃ（１．０６）については以下の通り。式（Ｂ）
【０１５５】
【数４７】
2008269047.tif 000049
の分子は、４８次式であり、０．５７１５８２５１…,０．５８１４５９５４…の２つの実零点を持つ。何れの零点も、式（Ｃ）を満たす。よって、複素区間多項式Ｆ（ｘ）に属する多項式で、Ｅ（１．０６）の部分集合であるＣ（１．０６）に零点を持つものが存在する。
【０１５６】
≪例３≫
複素区間多項式Ｆ（ｘ）を例２と同じ複素区間多項式とし、領域Ｄ（ｒ）を中心が原点、半径がｒの開円板とする。領域Ｄ（ｒ）の境界である円周の境界Ｃ（ｒ）を、例２と同じく、Ｃ１（ｒ）と｛ｒ｝の和集合として表す。
【０１５７】
以下で、Ｄ（０．９４）及びＤ（０．９５）内に、複素区間多項式Ｆ（ｘ）に属する多項式の零点となり得る点が存在するか否かを判定する。共通する部分も多いため、以下の説明では、Ｄ（０．９４）及びＤ（０．９５）に対する処理を並列して記述する。
【０１５８】
１．例２と同じく、代表多項式としてｆ’（ｘ）＝ｘ３−１を取る。
【０１５９】
２．代表多項式ｆ’（ｘ）が、領域Ｄ（ｒ）（ｒ＜１）に零点を持たないことは明らかである。
【０１６０】
３．ｒ＝０．９４（Ｄ（０．９４）の場合）としても、０．９５（Ｄ（０．９５）の場合）としても、境界Ｃ（ｒ）上の点ｒを零点として持つ多項式は複素区間多項式Ｆ（ｘ）に存在しない。
【０１６１】
４．まず、Ｃ（０．９４）については以下の通り。式（Ｂ）
【０１６２】
【数４８】
2008269047.tif 000050
の分子は４８次式であり、調べると実零点を持たないことが分かる。よって、複素区間多項式Ｆ（ｘ）に属する多項式で、Ｄ（０．９４）に零点を持つものは存在しない。
【０１６３】
次に、Ｃ（０．９５）については以下の通り。式（Ｂ）
【０１６４】
【数４９】
2008269047.tif 000051
の分子は４８式であり、−０．５８８９０４２９…，−０．５６３９３８３８…，０．５５７６８３６１…，０．５９５６４６１６…の４つの実零点を持つ。
【０１６５】
【数５０】
2008269047.tif 000052
これらはすべて式（Ｃ）を満たす。よって、複素区間多項式Ｆ（ｘ）属する多項式で、Ｄ（０．９５）の部分集合であるＣ（０．９５）に零点を持つものが存在する。
【０１６６】
例２と例３とを合わせると、複素区間多項式Ｆ（ｘ）に属する多項式の零点となり得る点はすべて集合
【０１６７】
【数５１】
2008269047.tif 000053
に属すること、また、０．９４を０．９５に、あるいは、１．０７を１．０６に置き換えるのは不可能であることがわかる。
【産業上の利用可能性】
【０１６８】
本発明は、例えば、多項式の係数に誤差を含むため一意に多項式を決定できない場合において、当該多項式の零点が所定の領域に存在するかを判定したい場合などに用いられ、そのような場合の一例として、ディジタル信号処理におけるディジタルフィルタ（例えば、ＩＩＲ〔Infinite Impulse Response〕フィルタ）の周波数特性の解析などに有用である。
【図面の簡単な説明】
【０１６９】
【図１】複素区間多項式の零点の位置判定装置（零点位置判定装置１）の機能構成を例示する図。
【図２】複素区間多項式の零点の位置判定方法のフローチャートを例示する図（その１）。
【図３】複素区間多項式の零点の位置判定方法のフローチャートを例示する図（その２）。
【図４】零点位置判定装置１をコンピュータで実現する場合の機能構成を例示する図。
【符号の説明】
【０１７０】
１     零点位置判定装置
２     代表多項式選択部
３     記憶部
４     代表多項式零点判定部
５     代表点選択部
６     多項式判定部
７     等式判定部
８     取得部
４１   境界上零点判定部
４２   領域内部零点判定部
４３   合成音声生成部
７１   第一Ｑ式生成部
７２   第二Ｑ式生成部
７３   零点演算部
７４   検証部
７５   バッファ
【図１】
2008269047.tif 000054
【図２】
2008269047.tif 000055
【図３】
2008269047.tif 000056
【図４】
2008269047.tif 000057