(57)【要約】【課題】  複素空間が与えられた場合に、特殊な制約条件が同時に付与されている場合以外は、零点を判定する方法がない。【解決手段】  本発明は、判定問題を場合分けし、単純閉曲線Ｃ上または、Ｃ内部に零点を有する区間多項式が存在するか、Ｃの区分Ｃｋの端点に零点を有する多項式が存在するか、また、Ｃの区分Ｃｋ上に零点を有し、高々1個の係数を除く他の係数が区間の端点である多項式が存在するかの判定を行う。【選択図】  図１
2005235121.tif 000002
【特許請求の範囲】
【請求項１】
実区間多項式の零点の位置を判定する方法において、
入力手段から、区間の端点が有理数である一変数実区間多項式と、有限個に区分され各区分が一変数有理式で表される複素平面上の単純閉曲線とを入力し、該一変数実区間多項式と該単純閉曲線とを記憶手段に記憶する入力ステップと、
多項式抽出手段において、前記記憶手段から前記一変数実区間多項式Ｆに属する一つの多項式ｆ０を読み出す多項式抽出ステップと、
多項式判定手段において、読み出された前記多項式ｆ０について、前記記憶手段から前記単純閉曲線Cを読み出して、該単純閉曲線Ｃ上または、該Ｃ内部にｆ０が零点を有するかを判定する多項式判定ステップと、
区分境界点判定手段において、前記単純閉曲線Ｃの区分Ｃｋの端点に零点を有する多項式ｇ∈Ｆが存在するかを判定する区分境界点判定ステップと、
区分内点判定手段において、前記単純閉曲線Ｃの区分Ｃｋ上に零点を有し、高々1個の係数を除く他の係数が区間の端点である多項式ｇ∈Ｆが存在するかを判定する区分内点判定ステップと、からなることを特徴とする実区間多項式の零点の位置判定方法。
【請求項２】
前記多項式判定ステップにおいて、
抽出された前記多項式ｆ０が前記単純閉曲線Ｃ上に零点を有するか判定し、有していないと判定された場合には、該多項式ｆ０が前記Ｃの内部に零点を有するかを判定する請求項1記載の実区間多項式の零点の位置判定方法。
【請求項３】
前記区分境界点判定ステップにおいて、
ある端点αを取り、前記区間多項式Ｆを
【数１】
2005235121.tif 000043
と書き直し、（ｕｊ−ｍｊ）αｊの実部が負となるｊが存在するかを判定し、存在する場合には、｛（ｕｊ−ｍｊ）ｔｊ＋ｍｊ｝αｊを｛（ｕｊ−ｍｊ）（１−ｔｊ）＋ｍｊ｝αｊと書き換え、
（ｕｊ−ｍｊ）αｊの実部が０、かつ、虚部が負となるｊが存在するか判定し、存在する場合には、｛（ｕｊ−ｍｊ）ｔｊ＋ｍｊ｝αｊを｛（ｕｊ−ｍｊ）（１−ｔｊ）＋ｍｊ｝αｊと書き換え、
最終的なΣ…を０に等しいとおいた上で、
【数２】
2005235121.tif 000044
と書き換え、ａ０，ａ１，…，ａｄの凸包を求め、
前記ｂが前記凸包に属していれば、前記区間多項式は前記Ｃ上あるいは該Ｃ内部に零点を有すると判定する請求項1記載の実区間多項式の零点の位置判定方法。
【請求項４】
前記区分内点判定ステップにおいて、
エッジ多項式を取得し、エッジに対応する、ただ一つ残っているパラメータをｔとし、
前記エッジ多項式に対し、まだ調べていない前記単純閉曲線Ｃの区分Ｃｋを取得し、
前記Ｃｋの有理係数有理式の表記φ（ｓ）＋ｉψ（ｓ）（ｓ∈Ｓ）を前記エッジ多項式に代入し、実部をｕ（ｓ，ｔ）、虚部をｖ（ｓ，ｔ）とし、ｕ＝ｖ＝０をｔについて解き、ｕ＝０から解いたものをｔ＝ｈ１（ｓ），ｖ＝０から解いたものをｔ＝ｈ２（ｓ）とし、
ｈ１（ｓ）−ｈ２（ｓ）の分母を払った多項式をＰ（ｓ）とし、
ｈ１（ｓ）、ｈ２（ｓ）のどちらかを選びＨ（ｓ）とし、
Ｈ（ｓ）−ｍの分母を払った多項式とＰ（ｓ）の最大公約多項式Ｇｍ（ｓ）及び、Ｈ（ｓ）−ｕの分母を払った多項式とＰ（ｓ）の最大公約多項式Ｇｕ（ｓ）を計算し、
Ｇｍ（ｓ）＝０の実根βで、β∈Ｓを満たすものがあるかを判定し、ある場合には、前記Ｃ上あるいはＣ内部に零点を有すると判定し、
ない場合には、Ｇｕ（ｓ）＝０の実根βで、β∈Ｓを満たすものがあるかを判定し、ある場合には、前記Ｃ上あるいは該Ｃ内部に零点を有すると判定し、
ない場合には、Ｐ（ｓ）／（Ｇｍ（ｓ）Ｇｕ（ｓ））＝０の実根βで、β∈Ｓかつｍ＜Ｈ（β）＜ｕを満たすものがあるかを判定し、ある場合には、前記Ｃ上あるいは該Ｃ内部に零点を有すると判定する請求項1記載の実区間多項式の零点の位置判定方法。
【請求項５】
実区間多項式の零点の位置を判定させるためのプログラムであって、
コンピュータに、
入力手段から入力された、区間の端点が有理数である一変数実区間多項式と、有限個に区分され各区分が一変数有理式で表される複素平面上の単純閉曲線とを記憶手段に格納する入力ステップと、
前記記憶手段から前記一変数実区間多項式Ｆに属する一つの多項式ｆ０を読み出す多項式抽出ステップと、
読み出された前記多項式ｆ０について、前記記憶手段から前記単純閉曲線を読み出して、該単純閉曲線Ｃ上または、該Ｃ内部にｆ０が零点を有するかを判定する多項式判定ステップと、
前記単純閉曲線Ｃの区分Ｃｋの端点に零点を有する多項式ｇ∈Ｆが存在するかを判定する区分境界点判定ステップと、
前記単純閉曲線Ｃの区分Ｃｋ上に零点を有し、高々1個の係数を除く他の係数が区間の端点である多項式ｇ∈Ｆが存在するかを判定する区分内点判定ステップと、を実行させることを特徴とする実区間多項式の零点の位置判定プログラム。
【請求項６】
前記多項式判定ステップにおいて、
抽出された前記多項式ｆ０が前記単純閉曲線Ｃ上に零点を有するか判定し、有していないと判定された場合には、該多項式ｆ０が該Ｃの内部に零点を有するかを判定するステップを実行させる請求項５記載の実区間多項式の零点の位置判定プログラム。
【請求項７】
前記区分境界点判定ステップにおいて、
ある端点αが設定されると、前記区間多項式Ｆを
【数３】
2005235121.tif 000045
と設定し直すステップと、
（ｕｊ−ｍｊ）αｊの実部が負となるｊが存在するかを判定し、存在する場合には、｛（ｕｊ−ｍｊ）ｔｊ＋ｍｊ｝αｊを｛（ｕｊ−ｍｊ）（１−ｔｊ）＋ｍｊ｝αｊと書き換えるステップと、
（ｕｊ−ｍｊ）αｊの実部が０、かつ、虚部が負となるｊが存在するか判定し、存在する場合には、｛（ｕｊ−ｍｊ）ｔｊ＋ｍｊ｝αｊを｛（ｕｊ−ｍｊ）（１−ｔｊ）＋ｍｊ｝αｊと書き換えるステップと、
最終的なΣ…を０に等しいとおいた上で、
【数４】
2005235121.tif 000046
と書き換え、ａ０，ａ１，…，ａｄの凸包を求めるステップと、
前記ｂが前記凸包に属していれば、前記区間多項式は前記Ｃ上あるいは該Ｃ内部に零点を有すると判定するステップと、を実行させる請求項５記載の実区間多項式の零点の位置判定プログラム。
【請求項８】
前記区分内点判定ステップにおいて、
エッジ多項式を取得し、エッジに対応するただ一つ残っているパラメータをｔとするステップと、
前記エッジ多項式に対し、まだ調べていない前記単純閉曲線Ｃの区分Ｃｋを取得するステップと、
前記Ｃｋの有理係数有理式の表記φ（ｓ）＋ｉψ（ｓ）（ｓ∈Ｓ）を前記エッジ多項式に代入し、実部をｕ（ｓ，ｔ）、虚部をｖ（ｓ，ｔ）とし、ｕ＝ｖ＝０をｔについて解き、ｕ＝０から解いたものをｔ＝ｈ１（ｓ），ｖ＝０から解いたものをｔ＝ｈ２（ｓ）とするステップと、
ｈ１（ｓ）−ｈ２（ｓ）の分母を払った多項式をＰ（ｓ）とするステップと、
ｈ１（ｓ）、ｈ２（ｓ）のどちらかを選びＨ（ｓ）とするステップと、
Ｈ（ｓ）−ｍの分母を払った多項式とＰ（ｓ）の最大公約多項式Ｇｍ（ｓ）及び、Ｈ（ｓ）−ｕの分母を払った多項式とＰ（ｓ）の最大公約多項式Ｇｕ（ｓ）を計算するステップと、
Ｇｍ（ｓ）＝０の実根βで、β∈Ｓを満たすものがあるかを判定し、ある場合には、前記Ｃ上あるいは該Ｃの内部に零点を有すると判定するステップと、
ない場合には、Ｇｕ（ｓ）＝０の実根βで、β∈Ｓを満たすものがあるかを判定し、ある場合には、前記Ｃ上あるいは該Ｃの内部に零点を有すると判定するステップと、
ない場合には、Ｐ（ｓ）／（Ｇｍ（ｓ）Ｇｕ（ｓ））＝０の実根βで、β∈Ｓかつｍ＜Ｈ（β）＜ｕを満たすものがあるかを判定し、ある場合には、前記Ｃ上あるいは該Ｃの内部に零点を有すると判定するステップと、を実行させる請求項５記載の実区間多項式の零点の位置判定プログラム。
【請求項９】
実区間多項式の零点の位置を判定するプログラムを格納した記憶媒体であって、
コンピュータに、
入力手段から入力された、区間の端点が有理数である一変数実区間多項式と、有限個に区分され各区分が一変数有理式で表される複素平面上の単純閉曲線とを記憶手段に格納する入力ステップと、
前記記憶手段から前記一変数実区間多項式Ｆに属する一つの多項式ｆ０を読み出す多項式抽出ステップと、
読み出された前記多項式ｆ０について、前記記憶手段から前記単純閉曲線を読み出して、該単純閉曲線Ｃ上または、該Ｃ内部にｆ０が零点を有するかを判定する多項式判定ステップと、
前記単純閉曲線Ｃの区分Ｃｋの端点に零点を有する多項式ｇ∈Ｆが存在するかを判定する区分境界点判定ステップと、
前記単純閉曲線Ｃの区分Ｃｋ上に零点を有し、高々1個の係数を除く他の係数が区間の端点である多項式ｇ∈Ｆが存在するかを判定する区分内点判定ステップと、を実行させるプログラムを格納したことを特徴とする実区間多項式の零点の位置判定プログラムを格納した記憶媒体。
【請求項１０】
前記多項式判定ステップにおいて、
抽出された前記多項式ｆ０が前記単純閉曲線Ｃ上に零点を有するか判定し、有していないと判定された場合には、該多項式ｆ０が該Ｃの内部に零点を有するかを判定するステップを実行させる請求項９記載の実区間多項式の零点の位置判定プログラムを格納した記憶媒体。
【請求項１１】
前記区分境界点判定ステップにおいて、
ある端点αが設定されると、前記区間多項式Ｆを
【数５】
2005235121.tif 000047
と設定し直すステップと、
（ｕｊ−ｍｊ）αｊの実部が負となるｊが存在するかを判定し、存在する場合には、｛（ｕｊ−ｍｊ）ｔｊ＋ｍｊ｝αｊを｛（ｕｊ−ｍｊ）（１−ｔｊ）＋ｍｊ｝αｊと書き換えるステップと、
（ｕｊ−ｍｊ）αｊの実部が０、かつ、虚部が負となるｊが存在するか判定し、存在する場合には、｛（ｕｊ−ｍｊ）ｔｊ＋ｍｊ｝αｊを｛（ｕｊ−ｍｊ）（１−ｔｊ）＋ｍｊ｝αｊと書き換えるステップと、
最終的なΣ…を０に等しいとおいた上で、
【数６】
2005235121.tif 000048
と書き換え、ａ０，ａ１，…，ａｄの凸包を求めるステップと、
前記ｂが前記凸包に属していれば、前記区間多項式は前記Ｃ上あるいは該Ｃ内部に零点を有すると判定するステップと、を実行させる請求項９記載の実区間多項式の零点の位置判定プログラムを格納した記憶媒体。
【請求項１２】
前記区分内点判定ステップにおいて、
エッジ多項式を取得し、エッジに対応するただ一つ残っているパラメータをｔとするステップと、
前記エッジ多項式に対し、まだ調べていない前記単純閉曲線Ｃの区分Ｃｋを取得するステップと、
前記Ｃｋの有理係数有理式の表記φ（ｓ）＋ｉψ（ｓ）（ｓ∈Ｓ）を前記エッジ多項式に代入し、実部をｕ（ｓ，ｔ）、虚部をｖ（ｓ，ｔ）とし、ｕ＝ｖ＝０をｔについて解き、ｕ＝０から解いたものをｔ＝ｈ１（ｓ），ｖ＝０から解いたものをｔ＝ｈ２（ｓ）とするステップと、
ｈ１（ｓ）−ｈ２（ｓ）の分母を払った多項式をＰ（ｓ）とするステップと、
ｈ１（ｓ）、ｈ２（ｓ）のどちらかを選びＨ（ｓ）とするステップと、
Ｈ（ｓ）−ｍの分母を払った多項式とＰ（ｓ）の最大公約多項式Ｇｍ（ｓ）及び、Ｈ（ｓ）−ｕの分母を払った多項式とＰ（ｓ）の最大公約多項式Ｇｕ（ｓ）を計算するステップと、
Ｇｍ（ｓ）＝０の実根βで、β∈Ｓを満たすものがあるかを判定し、ある場合には、前記Ｃ上あるいは、該Ｃの内部に零点を有すると判定するステップと、
ない場合には、Ｇｕ（ｓ）＝０の実根βで、β∈Ｓを満たすものがあるかを判定し、ある場合には、前記Ｃ上あるいは該Ｃの内部に零点を有すると判定するステップと、
ない場合には、Ｐ（ｓ）／（Ｇｍ（ｓ）Ｇｕ（ｓ））＝０の実根βで、β∈Ｓかつｍ＜Ｈ（β）＜ｕを満たすものがあるかを判定し、ある場合には、前記Ｃ上あるいは該Ｃの内部に零点を有すると判定するステップと、を実行させる請求項９記載の実区間多項式の零点の位置判定プログラムを格納した記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、実区間多項式の零点の位置判定方法及び位置判定プログラム及び位置判定プログラムを格納した記憶媒体に係り、特に、係数に誤差のある一変数実多項式の零点の位置判定を行うための実区間多項式の零点の位置判定方法及び位置判定プログラム及び位置判定プログラムを格納した記憶媒体に関する。
【背景技術】
【０００２】
係数が確定している一変数多項式の零点、即ち、その多項式が０に等しいとおいた一変数代数方程式の根が、与えられた領域に少なくとも一つ存在するかどうかの判定は、古典的な「Sturmのアルゴリズム」などを用いれば可能である(例えば、非特許文献１参照)。しかしながら、実際の応用上現れる多項式においては、係数を測定によって得たり、あるいは、測定値より計算したものであることが多い。即ち、係数の正確な値は分からない場合が多い。
【０００３】
一変数代数方程式の根は、次数が変化しないときには係数に関して連続だが、係数の変動に対して非常に敏感であって、係数をわずかに変えただけで激しく動く。ここでは、Wilkinsonによる例を取り上げて説明する。１から２０までの連続する２０個の整数を根として持つ２０次の代数方程式
Ｐ（ｘ）＝（ｘ−１）（ｘ−２）…(ｘ−２０)＝ｘ２０−２１０ｘ１９＋…＋２０！＝０
をとり、
Ｑ（ｘ）＝Ｐ（ｘ）−２−２３ｘ１９
と置く。Ｐ（ｘ）とＱ（ｘ）の違いは、ｘ１９の係数が前者は-210、後者は-210.00000011…
である点だけである。Ｐ（ｘ）とＱ（ｘ）をすべて書き下ろしたものを、以下に示す。
【０００４】
【数７】
2005235121.tif 000003
上記のＰ（ｘ）＝０の根はすべて実で２０個（１から２０までの連続する整数）あるが、Ｑ（ｘ）＝０の実根は１０個になってしまう（残りの１０個は５組の共役な虚根となる）。Ｑ（ｘ）＝０の最大の実根は、20.08…、二番目に大きい実根は8.9…である。
【０００５】
したがって、係数が正確にはわからない方程式の根の位置判定は、慎重に行う必要がある。
【０００６】
以下、方程式の係数は実数で誤差があるものとし、その範囲を区間数で表す。区間数［ｍ，ｕ］とは、ｍ≦ｃ≦ｕとなる実数ｃの全体の集合のことである。ｍとｕを区間数［ｍ，ｕ］の端点と呼ぶ。区間多項式とは、
【０００７】
【数８】
2005235121.tif 000004
のように表記されるもので、全てのｊ（０≦ｊ≦ｄ）に対してｃｊ∈［ｍｊ，ｕｊ］となる多項式
【０００８】
【数９】
2005235121.tif 000005
全体の集合を表すものである。ここでは、全ての区間数の端点は有理数であるものとし、与えられた領域に零点をもつような多項式ｆ（ｘ）（∈Ｆ(ｘ)）が存在するか否かを判定する問題を考える。
【０００９】
もし、与えられた領域が実の場合、即ち、ある実の区間［ａ，ｂ］であれば、以下の方法をとればよい。
【００１０】
場合１：区間［ａ，ｂ］が０以上の領域に入る場合、すなわち、０≦ａの場合、
【００１１】
【数１０】
2005235121.tif 000006
と置く。このとき、ｆｍ，ｆｕ∈Ｆ（ｘ）かつ、区間［ａ，ｂ］において、つねに、ｆｍ（ｘ）≦ｆｕ（ｘ）が成り立つことに注意する。
【００１２】
まず、区間の端点ａ，ｂにおいて、ｆｍ，ｆｕの値を調べる。
【００１３】
・ｆｍ（ａ），ｆｍ（ｂ），ｆｕ（ａ），ｆｕ（ｂ）の中に０のものがあれば、零点が存在することがわかり、判定終了。
【００１４】
・ｆｍ（ａ），ｆｍ（ｂ），ｆｕ（ａ），ｆｕ（ｂ）の中に異符号のものがあれば、さらに場合分けする。ｆｍ（ａ）とｆｍ（ｂ）が異符号の場合は、あるｃ（ａ＜ｃ＜ｂ）があって、ｆｍ（ｃ）＝０であることがわかり、判定終了。ｆｕ（ａ）とｆｕ（ｂ）が異符号の場合も、あるｃ（ａ＜ｃ＜ｂ）があってｆｕ（ｃ）＝０であることがわかり、判定終了。残るは、ｆｍ(ａ)とｆｍ（ｂ）が同符号、ｆｕ（ａ）とｆｕ（ｂ）が同符号の場合である。この場合の状況を図２０に示す。ｆｍ（ａ）≦ｆｕ（ａ）だから、ｆｍ（ａ）＜０＜ｆｕ（ａ）である（ｆｍ(ａ)とｆｕ（ａ）が同符号ならば、ｆｍ（ａ），ｆｍ（ｂ），ｆｕ（ａ），ｆｕ（ｂ）の全てが同符号になってしまう）。ｇ(ｔ，ｘ)＝(１−ｔ)ｆｍ(ｘ)＋ｔｆｕ（ｘ）とおくと、任意の０≦ｔ≦１に対し、ｇ（ｔ，ｘ）は区間多項式Ｆに属す。ｆｕ（ａ）−ｆｍ（ａ）＞０であり、ｔ０＝−ｆｍ（ａ）／（ｆｕ（ａ）−ｆｍ（ａ））とおくと、ｇ（ｔ０，ａ）＝０かつ０＜−ｆｍ(ａ)／（ｆｕ（ａ）−ｆｍ（ａ））＜１。すなわち、多項式ｇ（ｔ０，ｘ）は、区間多項式Ｆに属し、しかも、ａを零点とすることがわかり、判定終了。
【００１５】
ｆｍ(ａ)，ｆｍ（ｂ），ｆｕ（ａ），ｆｕ（ｂ）の全てが同符号の場合、それが正ならばｆｍが［ａ，ｂ］に零点を持つか否か調べればよい。図２１、図２２は、それぞれ、ｆｍが零点を持つ場合、持たない場合を示す図である。同様に、ｆｍ（ａ），ｆｍ（ｂ），ｆｕ（ａ），ｆｕ（ｂ）のすべてが負ならば、ｆｕが［ａ，ｂ］に零点を持つか否か調べればよい。いずれの場合も、既に知られている『Sturmのアルゴリズム』その他を用いれば判定できる。
【００１６】
場合２：  区間［ａ，ｂ］が０以下の領域に入る場合、即ち、ｂ≦０の場合、この場合は、ｘ＝−ｙと変数変換することにより、ケース１に帰着する。
【００１７】
場合３：  区間［ａ，ｂ］の内部に０が含まれる場合、すなわち、ａ＜０＜ｂの場合。この場合は、区間［ａ，ｂ］を［ａ，０］と［０，ｂ］に分ければ、それぞれ、ケース１、ケース２に帰着する。
【００１８】
複素平面上にある領域を対象とするとき、特別な場合には「Rouche」（ルーシェ）の定理（ｆ(ｚ)とｇ(ｚ)とは閉曲線Ｃの内部及びＣ上で正則とし、Ｃ上では｜ｆ（ｚ）｜＞｜ｇ(ｚ)｜であるとする。このとき、ｆ(ｚ)とｆ（ｚ）＋ｇ（ｚ）とはＣ内部に重複度を含めて、同数個の零点をもつ）を用いて判定可能である（例えば、非特許文献２参照）。有限個に区分された各区分が一変数有理係数有理式で表される複素平面上の単純閉曲線（Jordan曲線）Ｃが与えられたとき、Ｆに属するある多項式ｆについて、ｆは、Ｃの周上に零点を持たず(この判定はSturmのアルゴリズムなどで可能)、任意のｇ∈Ｆに対し、｜ｇ−ｆ｜＜｜ｆ｜がＣ上でつねに成り立つことがいえるならば、ｆのみをRoucheの定理を用いて調べればよい。この場合、任意のｇ∈Ｆに対し、Ｃ上にはｇの零点はなく、Ｃで囲まれた領域内のｇの零点の数は、ｆのそれに等しいからである。但し、上記の逆はいえないので、｜ｇ−ｆ｜≧｜ｆ｜となるｇが存在する場合には、上記の手法は適用できない。
【００１９】
また、『少なくとも一つの零点が存在』ではなく、『すべての零点が存在』という形なら、エッジ定理（例えば、非特許文献３参照）が適用可能である。すなわち、Ｆに属する全てのエッジ多項式、つまり、高々一つの係数を除く、係数が区間数の端点となっている多項式のみ調べればよい。但し、今考えている領域をＤとしたとき、領域Ｄに「Ｄの補集合の任意の点が無限遠に向かう適当な経路上にある」という制限がつく。従って、『領域Ｄに少なくとも一つの零点がある』の否定と同値な「領域Ｄの補集合に全ての零点があり、かつ、Ｄの境界上に零点がない」を示すのにエッジ定理を常に使えるわけではない。
【００２０】
上記のように、対象とする領域が実をはみ出し複素平面上にあるとき、いかなる集合であっても有限ステップで厳密に判定が可能な手法は存在していない
【非特許文献１】高木貞治、代数学講義(改訂新版)、第３章、共立出版、１９６５
【非特許文献２】吉田洋一、函数論(第２版)、VII章、留数、§４８、１９６５
【非特許文献３】A. C. Bartlett, L.Huang and C. V. Hollot, Root location of an entire polytope of polynomials: it suffices to check the edges, Mathematics of Controls, Signals and Systems, Vol.1, pp.61-71, 1988
【発明の開示】
【発明が解決しようとする課題】
【００２１】
上記のように、従来は、対象とする領域が実をはみ出し複素平面上にある場合は、特殊な制約条件が同時に付与されている場合以外は、零点を判断する方法がなかった。
【００２２】
本発明は、上記の点に鑑みなされたもので、各係数の誤差範囲が区間で指定された区間多項式に属する多項式であって、与えられた複素平面上の単純閉曲線で囲まれた境界も含む領域内に零点を持つものが存在するか否かを有限ステップで厳密に判定することが可能な実区間多項式の零点の位置判定方法及び位置判定プログラム及び位置判定プログラムを格納した記憶媒体を提供することを目的とする。
【課題を解決するための手段】
【００２３】
図１は、本発明の原理を説明するための図である。
【００２４】
本発明は、実区間多項式の零点の位置を判定する方法において、
入力手段から、区間の端点が有理数である一変数実区間多項式と、有限個に区分され各区分が一変数有理式で表される複素平面上の単純閉曲線とを入力し、該一変数実区間多項式と該単純閉曲線とを記憶手段に記憶する入力ステップ（ステップ１）と、
多項式抽出手段において、記憶手段から一変数実区間多項式Ｆに属する一つの多項式ｆ０を読み出す多項式抽出ステップ（ステップ２）と、
多項式判定手段において、読み出された多項式ｆ０について、記憶手段から単純閉曲線を読み出して、該単純閉曲線Ｃ上または、該Ｃ内部にｆ０が零点を有するかを判定する多項式判定ステップ（ステップ３）と、
区分境界点判定手段において、単純閉曲線Ｃの区分Ｃｋの端点に零点を有する多項式ｇ∈Ｆが存在するかを判定する区分境界点判定ステップ（ステップ４）と、
区分内点判定手段において、単純閉曲線Ｃの区分Ｃｋ上に零点を有し、高々1個の係数を除く他の係数が区間の端点である多項式ｇ∈Ｆが存在するかを判定する区分内点判定ステップ（ステップ５）と、からなる。
【００２５】
また、本発明は、多項式判定ステップにおいて、
抽出された多項式ｆ０が単純閉曲線Ｃ上に零点を有するか判定し、有していないと判定された場合には、該多項式ｆ０がＣの内部に零点を有するかを判定する。
【００２６】
また、本発明は、区分境界点判定ステップにおいて、
ある端点αを取り、区間多項式Ｆを
【００２７】
【数１１】
2005235121.tif 000007
と書き直し、（ｕｊ−ｍｊ）αｊの実部が負となるｊが存在するかを判定し、存在する場合には、｛（ｕｊ−ｍｊ）ｔｊ＋ｍｊ｝αｊを｛（ｕｊ−ｍｊ）（１−ｔｊ）＋ｍｊ｝αｊと書き換え、
（ｕｊ−ｍｊ）αｊの実部が０、かつ、虚部が負となるｊが存在するか判定し、存在する場合には、｛（ｕｊ−ｍｊ）ｔｊ＋ｍｊ｝αｊを｛（ｕｊ−ｍｊ）（１−ｔｊ）＋ｍｊ｝αｊと書き換え、
最終的なΣ…を０に等しいとおいた上で、
【００２８】
【数１２】
2005235121.tif 000008
と書き換え、ａ０，ａ１，…，ａｄの凸包を求め、
ｂが凸包に属していれば、区間多項式はＣ上あるいはＣ内部に零点を有すると判定する。
【００２９】
また、本発明は、区分内点判定ステップにおいて、
エッジ多項式を取得し、エッジに対応するただ一つ残っているパラメータをｔとし、
エッジ多項式に対し、まだ調べていない単純閉曲線Ｃの区分Ｃｋを取得し、
Ｃｋの有理係数有理式の表記φ（ｓ）＋ｉψ（ｓ）（ｓ∈Ｓ）をエッジ多項式に代入し、実部をｕ（ｓ，ｔ）、虚部をｖ（ｓ，ｔ）とし、ｕ＝ｖ＝０をｔについて解き、ｕ＝０から解いたものをｔ＝ｈ１（ｓ），ｖ＝０から解いたものをｔ＝ｈ２（ｓ）とし、
ｈ１（ｓ）−ｈ２（ｓ）の分母を払った多項式をＰ（ｓ）とし、
ｈ１（ｓ）、ｈ２（ｓ）のどちらかを選びＨ（ｓ）とし、
Ｈ（ｓ）−ｍの分母を払った多項式とＰ（ｓ）の最大公約多項式Ｇｍ（ｓ）及び、Ｈ（ｓ）−ｕの分母を払った多項式とＰ（ｓ）の最大公約多項式Ｇｕ（ｓ）を計算し、
Ｇｍ（ｓ）＝０の実根βで、β∈Ｓを満たすものがあるかを判定し、ある場合には、Ｃ上あるいは内部に零点を有すると判定し、
ない場合には、Ｇｕ（ｓ）＝０の実根βで、β∈Ｓを満たすものがあるかを判定し、ある場合には、Ｃ上あるいは内部に零点を有すると判定し、
ない場合には、Ｐ（ｓ）／（Ｇｍ（ｓ）Ｇｕ（ｓ））＝０の実根βで、β∈Ｓかつｍ＜Ｈ（β）＜ｕを満たすものがあるかを判定し、ある場合には、Ｃ上あるいはＣ内部に零点を有すると判定する。
【００３０】
本発明は、実区間多項式の零点の位置を判定させるプログラムであって、
コンピュータに、
入力手段から入力された、区間の端点が有理数である一変数実区間多項式と、有限個に区分され各区分が一変数有理式で表される複素平面上の単純閉曲線とを記憶手段に格納する入力ステップと、
記憶手段から一変数実区間多項式Ｆに属する一つの多項式ｆ０を読み出す多項式抽出ステップと、
読み出された多項式ｆ０について、記憶手段から単純閉曲線を読み出して、該単純閉曲線Ｃ上または、該Ｃ内部にｆ０が零点を有するかを判定する多項式判定ステップと、
単純閉曲線Ｃの区分Ｃｋの端点に零点を有する多項式ｇ∈Ｆが存在するかを判定する区分境界点判定ステップと、
単純閉曲線Ｃの区分Ｃｋ上に零点を有し、高々1個の係数を除く他の係数が区間の端点である多項式ｇ∈Ｆが存在するかを判定する区分内点判定ステップと、を実行させる。
【００３１】
また、本発明は、多項式判定ステップにおいて、
抽出された多項式ｆ０が単純閉曲線Ｃ上に零点を有するか判定し、有していないと判定された場合には、該多項式ｆ０がＣの内部に零点を有するかを判定するステップを実行させる。
【００３２】
また、本発明は、区分境界点判定ステップにおいて、
ある端点αが設定されると、多項式Ｆを
【００３３】
【数１３】
2005235121.tif 000009
と設定し直すステップと、
（ｕｊ−ｍｊ）αｊの実部が負となるｊが存在するかを判定し、存在する場合には、｛（ｕｊ−ｍｊ）ｔｊ＋ｍｊ｝αｊを｛（ｕｊ−ｍｊ）（１−ｔｊ）＋ｍｊ｝αｊと書き換えるステップと、
（ｕｊ−ｍｊ）αｊの実部が０、かつ、虚部が負となるｊが存在するか判定し、存在する場合には、｛（ｕｊ−ｍｊ）ｔｊ＋ｍｊ｝αｊを｛（ｕｊ−ｍｊ）（１−ｔｊ）＋ｍｊ｝αｊと書き換えるステップと、
最終的なΣ…を０に等しいとおいた上で、
【００３４】
【数１４】
2005235121.tif 000010
と書き換え、ａ０，ａ１，…，ａｄの凸包を求めるステップと、
ｂが凸包に属していれば、区間多項式はＣ上あるいはＣ内部に零点を有すると判定するステップと、を実行させる。
【００３５】
また、本発明は、区分内点判定ステップにおいて、
エッジ多項式を取得し、エッジに対応するただ一つ残っているパラメータをｔとするステップと、
エッジ多項式に対し、まだ調べていない単純閉曲線Ｃの区分Ｃｋを取得するステップと、
Ｃｋの有理係数有理式の表記φ（ｓ）＋ｉψ（ｓ）（ｓ∈Ｓ）をエッジ多項式に代入し、実部をｕ（ｓ，ｔ）、虚部をｖ（ｓ，ｔ）とし、ｕ＝ｖ＝０をｔについて解き、ｕ＝０から解いたものをｔ＝ｈ１（ｓ），ｖ＝０から解いたものをｔ＝ｈ２（ｓ）とするステップと、
ｈ１（ｓ）−ｈ２（ｓ）の分母を払った多項式をＰ（ｓ）とするステップと、
ｈ１（ｓ）、ｈ２（ｓ）のどちらかを選びＨ（ｓ）とするステップと、
Ｈ（ｓ）−ｍの分母を払った多項式とＰ（ｓ）の最大公約多項式Ｇｍ（ｓ）及び、Ｈ（ｓ）−ｕの分母を払った多項式とＰ（ｓ）の最大公約多項式Ｇｕ（ｓ）を計算するステップと、
Ｇｍ（ｓ）＝０の実根βで、β∈Ｓを満たすものがあるかを判定し、ある場合には、Ｃ上あるいはＣ内部に零点を有すると判定するステップと、
ない場合には、Ｇｕ（ｓ）＝０の実根βで、β∈Ｓを満たすものがあるかを判定し、ある場合には、Ｃ上あるいはＣ内部に零点を有すると判定するステップと、
ない場合には、Ｐ（ｓ）／（Ｇｍ（ｓ）Ｇｕ（ｓ））＝０の実根βで、β∈Ｓかつｍ＜Ｈ（β）＜ｕを満たすものがあるかを判定し、ある場合には、Ｃ上あるいはＣ内部に零点を有すると判定するステップと、を実行させる。
【００３６】
本発明は、実区間多項式の零点の位置を判定させるプログラムを格納した記憶媒体であって、
コンピュータに、
入力手段から入力された、区間の端点が有理数である一変数実区間多項式と、有限個に区分され各区分が一変数有理式で表される複素平面上の単純閉曲線とを記憶手段に格納する入力ステップと、
記憶手段から一変数実区間多項式Ｆに属する一つの多項式ｆ０を読み出す多項式抽出ステップと、
読み出された多項式ｆ０について、記憶手段から単純閉曲線を読み出して、該単純閉曲線Ｃまたは、該Ｃ内部にｆ０が零点を有するかを判定する多項式判定ステップと、
単純閉曲線Ｃの区分Ｃｋの端点に零点を有する多項式ｇ∈Ｆが存在するかを判定する区分境界点判定ステップと、
単純閉曲線Ｃの区分Ｃｋ上に零点を有し、高々1個の係数を除く他の係数が区間の端点である多項式ｇ∈Ｆが存在するかを判定する区分内点判定ステップと、を実行させるプログラムを格納した記憶媒体である。
【００３７】
また、本発明は、多項式判定ステップにおいて、
抽出された多項式ｆ０が単純閉曲線Ｃ上に零点を有するか判定し、有していないと判定された場合には、該多項式ｆ０がＣの内部に零点を有するかを判定するステップを実行させるプログラムを格納した記憶媒体である。
【００３８】
また、本発明は、区分境界点判定ステップにおいて、
ある端点αが設定されると、多項式Ｆを
【００３９】
【数１５】
2005235121.tif 000011
と設定し直すステップと、
（ｕｊ−ｍｊ）αｊの実部が負となるｊが存在するかを判定し、存在する場合には、｛（ｕｊ−ｍｊ）ｔｊ＋ｍｊ｝αｊを｛（ｕｊ−ｍｊ）（１−ｔｊ）＋ｍｊ｝αｊと書き換えるステップと、
（ｕｊ−ｍｊ）αｊの実部が０、かつ、虚部が負となるｊが存在するか判定し、存在する場合には、｛（ｕｊ−ｍｊ）ｔｊ＋ｍｊ｝αｊを｛（ｕｊ−ｍｊ）（１−ｔｊ）＋ｍｊ｝αｊと書き換えるステップと、
最終的なΣ…を０に等しいとおいた上で、
【００４０】
【数１６】
2005235121.tif 000012
と書き換え、ａ０，ａ１，…，ａｄの凸包を求めるステップと、
ｂが凸包に属していれば、区間多項式はＣ上あるいはＣ内部に零点を有すると判定するステップと、を実行させるプログラムを格納した記憶媒体である。
【００４１】
また、本発明は、区分内点判定ステップにおいて、
エッジ多項式を取得し、残りのパラメータとするステップと、
エッジ多項式に対し、まだ調べていない単純閉曲線Ｃの区分Ｃｋを取得するステップと、
Ｃｋの有理係数有理式の表記φ（ｓ）＋ｉψ（ｓ）（ｓ∈Ｓ）をエッジ多項式に代入し、実部をｕ（ｓ，ｔ）、虚部をｖ（ｓ，ｔ）とし、ｕ＝ｖ＝０をｔについて解き、ｕ＝０から解いたものをｔ＝ｈ１（ｓ），ｖ＝０から解いたものをｔ＝ｈ２（ｓ）とするステップと、
ｈ１（ｓ）−ｈ２（ｓ）の分母を払った多項式をＰ（ｓ）とするステップと、
ｈ１（ｓ）、ｈ２（ｓ）のどちらかを選びＨ（ｓ）とするステップと、
Ｈ（ｓ）−ｍの分母を払った多項式とＰ（ｓ）の最大公約多項式Ｇｍ（ｓ）及び、Ｈ（ｓ）−ｕの分母を払った多項式とＰ（ｓ）の最大公約多項式Ｇｕ（ｓ）を計算するステップと、
Ｇｍ（ｓ）＝０の実根βで、β∈Ｓを満たすものがあるかを判定し、ある場合には、Ｃ上あるいはＣ内部に零点を有すると判定するステップと、
ない場合には、Ｇｕ（ｓ）＝０の実根βで、β∈Ｓを満たすものがあるかを判定し、ある場合には、Ｃ上あるいはＣ内部に零点を有すると判定するステップと、
ない場合には、Ｐ（ｓ）／（Ｇｍ（ｓ）Ｇｕ（ｓ））＝０の実根βで、β∈Ｓかつｍ＜Ｈ（β）＜ｕを満たすものがあるかを判定し、ある場合には、Ｃ上に零点を有すると判定するステップと、を実行させるプログラムを格納した記憶媒体である。
【発明の効果】
【００４２】
上記のように、本発明によれば、区間係数多項式に対して、与えられた複素平面上の領域に根が存在するような多項式の存在の有無を判定することが可能である。
【発明を実施するための最良の形態】
【００４３】
以下、図面と共に本発明の実施の形態を説明する。
【００４４】
図２は、本発明の一実施の形態における位置判定装置の構成を示す。
【００４５】
同図に示す実区間多項式の零点の位置判定装置は、入力部１０、代表多項式抽出部２０、代表多項式判定部３０、区分境界判定部４０、区分内点判定部５０及び、出力部６０から構成される。
【００４６】
入力部１０は、区間の端点が有理数である一変数実区間多項式と、有限個に区分された各区分が一変数有理係数有理式で表される複素平面上の単純閉曲線とを入力し、一変数実区間多項式と単純閉曲線を記憶手段（図示せず）に格納する。
【００４７】
代表多項式抽出部２０は、記憶手段に格納されている一変数実区間多項式に属する一つの多項式を読み出す。
【００４８】
代表多項式判定部３０は、代表多項式抽出部２０で抽出された一つの多項式が入力された単純閉曲線Ｃ上、または、単純閉曲線Ｃで囲まれた領域に零点を持つか否かを判定する。
【００４９】
区分境界点判定部４０は、記憶手段から一変数実区間多項式Ｆを読出し、単純閉曲線Ｃの各区分Ｃｋの端点を零点とする多項式が存在するか否かを判定する。即ち、Ｃの区分Ｃｋの端点を零点とする多項式ｇ∈Ｆの存在の有無を判定する。
【００５０】
区分内点判定部５０は、区分境界点判定部４０において、Ｃｋの端点に零点を有する多項式が存在しない場合に、区間多項式に属する全てのエッジ多項式に対して単純閉曲線Ｃ上の各区分の内点において少なくとも一つの零点を持つか否かを判定する。即ち、Ｃｋに零点を有し、高々1個の係数を除く他の係数が区間の端点である多項式ｇ∈Ｆの存在の有無を判定する。
【００５１】
出力部６０は、各判定結果を出力する。
【００５２】
図３は、本発明の一実施の形態における判定処理のフローチャートである。
【００５３】
区間多項式
【００５４】
【数１７】
2005235121.tif 000013
及び、単純閉曲線Ｃが与えられているものとし、Ｃ上あるいは、Ｃ内部に零点を持つような多項式ｆ∈Ｆが存在するか否かを判断する問題を考える。但し、Ｃは有限個に区分され、各区分が一変数有理係数有理式で表されているものとする。
【００５５】
まず、代表多項式抽出部２０は、記憶手段（図示せず）から区間多項式Ｆに属する多項式ｆ０を一つ読み出し（ステップ１１０）、代表多項式判定部３０において、それがＣ上あるいはＣの内部に零点を持つか否かを調べる（判定Ａ：ステップ１２０）。これは、「Sturmのアルゴリズム」などで判断できる。図４は、本発明の一実施の形態における判定Ａの動作のフローチャートである。
【００５６】
【数１８】
2005235121.tif 000014
は、中心（ｃｊ＝（ｍｊ＋ｕｊ）／２），端（ｃｊ＝ｍｊあるいはｕｊ）、その他計算しやすいものでよい。この段階で、もし、零点をもつことがわかれば判定は終了する（ステップ１２１）。
【００５７】
以下、Ｃ上にはｆ０の零点がないものとする。ｆ０の零点がＣで囲まれた領域内にあるかどうかは、複素領域に対する「Sturmのアルゴリズム」や、偏角の原理により判定可能である。この段階でもし、零点をもつことがわかれば判定は終了する（判定Ａ：ステップ１２２）。
【００５８】
ｆ０の零点がＣ上にも、Ｃで囲まれた領域の内部にもない場合（ステップ１２０、Ｎｏ）、もし、区間多項式Ｆに属するｇで、Ｃ上あるいはＣで囲まれた領域に零点を持つものがあれば、Ｃ上で零点を持つｈ∈Ｆが存在する。なぜなら、ｇ自身がＣ上に零点を持つ場合はｈとしてｇをとればよいし、ｇがＣ上に零点を持たない場合は、もし、任意のｔ（０≦ｔ≦１）に対し、ｆ０＋ｔ（ｇ−ｆ０）がＣ上に零点を持たないとすると、Ｃで囲まれた領域の内部にあるｆ０の零点とｆ０＋（ｇ−ｆ０）＝ｆ０の零点の数は等しくなる（Roucheの定理の特別な場合）。これは矛盾するからあるｔ０（０≦ｔ０≦１）があって、ｈ＝ｆ０＋ｔ０（ｇ−ｆ０）の零点はＣ上にある。作り方から、任意の（０≦ｔ≦１）に対し、ｆ０＋ｔ（ｇ−ｆ０）はＦに属するから、ｈ∈Ｆである。よって、以下Ｃ上に零点を持つ多項式ｇ∈Ｆが存在するか否かを判定すれば十分である。
【００５９】
次に、任意のｆ∈Ｆ及び、ｆの任意の零点αに対し、ｇ∈Ｆであってｇ(α)＝０となる多項式
【００６０】
【数１９】
2005235121.tif 000015
で、高々二つのｊを除き、ｃｊ＝ｍｊあるいはｕｊとなるものが存在することを説明する。
【００６１】
αを根とする次数が高々ｄの一変数実多項式ｇ（ｘ）（Ｆ（ｘ）に入らないものも含める）の係数の集合をＶとする。ｇ(α)＝０を実部と虚部に分けて、その連立方程式と見ることにより、Ｖは、Ｒｄ＋１の中でｄ次元（αが実数の場合）、あるいは、ｄ−１次元（αが虚数の場合）のベクトル空間となることがわかる。ベクトル空間Ｖと、Ｆの係数からなる超直方体Ｂとは交わる（ｆは両者に入る）ので、特に、ベクトル空間Ｖは、Ｂの面と共通点があることがわかる。すなわち、高々２つを除くと、係数が区間の端点となる多項式ｇ（ｘ）∈Ｆ（ｘ）であって、ｇ(α)＝０となるものが存在することがわかる。
【００６２】
以上より、ｆ０がＣ上及びＣで囲まれた内部に零点を持たない場合（ステップ１２０、Ｎｏ）、Ｃ上あるいは、Ｃで囲まれた内部に零点を持つ多項式ｇ∈Ｆが存在することと、高々二個の係数を除き係数が区間の端点となっている多項式ｇ∈Ｆであって、その零点がＣ上にあるものが存在することが同値であることがわかる。
【００６３】
以下、高々二個の係数を除き係数が区間の端点となっている多項式ｇ∈Ｆであって、その零点がＣ上にあるものが存在するか否かを問題にする。
【００６４】
高々二個の係数を除き、係数が区間の端点となっている多項式ｇ∈ＦがＣ上に根αを持つとする。
【００６５】
αがＣの区分Ｃｋにあるとし、Ｃｋの表記をｘ＝φ(ｓ)＋ｉψ（ｓ）とする。但し、φ(ｓ)、ψ（ｓ）は、ｓの有理係数有理式とする。ｇ（φ(ｓ)＋ｉψ（ｓ））の実部をｕ（ｓ）、虚部をｖ（ｓ）とおくと、ｕ（ｓ）＝ｖ（ｓ）＝０という連立方程式となる。
【００６６】
今、ｇの係数のうち、区間の端点となっていないもの（高々二つ）をｔ１、ｔ２と書くことにする。ｕ（ｓ）＝ｖ（ｓ）＝０を、ｓをパラメータとするｔ１，ｔ２の連立方程式とみれば、ｓを動かしたとき、行列式が０でない限りは、必ず解が存在し、しかも、ｓについて連続である。よって、αに対応するｓをｓ０と書けば、ｓをｓ０から動かしていったとき、
（１）行列式が０になるか、
（２）行列式が０とならず、ｔ１あるいはｔ２が区間の端点に達するか、
（３）行列式が０とならず、ｓがパラメータの動く範囲の端点に達するか、
のいずれかが起こる。
【００６７】
（２）はエッジ多項式となる。（３）は、パラメータが端点のところで、対応する根が区分Ｃｋの端点となる。
【００６８】
（１）の場合は、そのとき連立方程式の解が不定なら、式が一本の場合と同じ状況になるので、ｓを止めたままで、ｔ１、ｔ２を連立方程式を満たすよう動かすことができる。そして、ｔ１，ｔ２のうちの少なくとも一つが区間の端点に達するまで動かせる。すなわち、上記(２)の場合になる。不能の場合、パラメータｓが行列式を０にする値に近付くとき、ｔ１，ｔ２のうち少なくとも一方は∞あるいは−∞に発散するから、そのまえに区間の端点に達する。すなわち、上記（２）の場合に含まれる。以上より、（１）の場合は、（２）に含まれることがわかる。
【００６９】
以上を整理すれば、
（ａ）高々一個の係数を除き係数が区間の端点となっている多項式(エッジ多項式)ｇ∈Ｆであって、その零点がＣｋ上にあるものが存在する、
（ｂ）高々二個の係数を除き係数が区間の端点となっている多項式ｇ∈Ｆであって、Ｃｋの端点の根とするものが存在する、
としたとき、（ａ）あるいは（ｂ）が成り立つことと、高々二個の係数を除き係数が区間の端点となっている多項式ｇ∈Ｆであって、その零点がＣｋ上にあるものが存在することは同値である。
【００７０】
よって、以下、(ａ)，（ｂ）をいかに調べるか、について記述する。
【００７１】
最初に、（ｂ）の場合について述べる。まず、区間多項式を
【００７２】
【数２０】
2005235121.tif 000016
と書き直す。以下、アルゴリズムを簡単かつ、効率よくするため、エッジ多項式と限らない範囲で調べる（判定Ｂ：ステップ１３０）。
【００７３】
図５は、本発明の一実施の形態における判定Ｂの動作のフローチャートである。区分境界判定部４０は、まず、まだ調べていない端点αを取る（ステップ１３１）。ｘにαを代入し、Ｆを
【００７４】
【数２１】
2005235121.tif 000017
と書き直す（ステップ１３２）。（ｕｊ−ｍｊ）αｊの実部が負となるｊが存在するかを判定し（ステップ１３３）、存在する場合には、｛（ｕｊ−ｍｊ）ｔｊ＋ｍｊ｝αｊを｛（ｕｊ−ｍｊ）（１−ｔｊ）＋ｍｊ｝αｊと書き換え（ステップ１３５）、（ｕｊ−ｍｊ）αｊの実部が０かつ虚部が負となるｊが存在するか判定し（ステップ１３４）、存在する場合には、｛（ｕｊ−ｍｊ）ｔｊ＋ｍｊ｝αｊを｛（ｕｊ−ｍｊ）（１−ｔｊ）＋ｍｊ｝αｊと書き換え（ステップ１３５）、その結果を、
【００７５】
【数２２】
2005235121.tif 000018
とする（ステップ１３６）。これを満たすような０≦ｔｊ≦１が存在するか否かの判定となるが、これは、
【００７６】
【数２３】
2005235121.tif 000019
但し、ｅｊ＝０あるいは１、の全体、高々２ｄ＋１個の点の凸包にｂが入るか否かの判定である。よって、まず、
【００７７】
【数２４】
2005235121.tif 000020
の全体の凸包を求める。これは、効率的に計算できる。まず、ａｊを傾きでソートする。但し、傾きは−π／２とπ／２の間、とする。ソートの結果をｖ１，…，ｖｎとする。但し、同じ傾きのものがあるときには、それらを全部足したもの一つに置き換える(例えば、ａｊとａｋの傾きが同じときには、ｖ１，…，ｖｎの中には、ａｊ，ａｋの代わりに、ａｊ＋ａｋを入れる。よって、ｎは、ｄ＋１より小さいことがある)。このとき、求める凸包の頂点は、０から始めて反時計回りに、０，ｖ１，ｖ１＋ｖ２，…，ｖ１＋…＋ｖｎ，ｖ２＋ｖ３＋…ｖｎ，ｖ３＋…＋ｖｎ，ｖｎ−１＋ｖｎ，ｖｎの全部で２ｎ個となる（ステップ１３７）。この凸包にｂが属するかを判定し（ステップ１３８）、属する場合には（ステップ１３８、Ｙｅｓ）ＦはＣ上あるいはＣの内部に零点を有すると判定する。属さない場合は（ステップ１３８、Ｎｏ）、まだ調べていない端点があるかを判断し、ある場合にはステップ１３１に移行し、ない場合には判定Ｃ（ステップ１４０）に移行する。
【００７８】
次に、（ａ）の場合を説明する（判定Ｃ：ステップ１４０）。ただ一つ残ったパラメータをｔとし、ｕ（ｓ）＝ｖ（ｓ）＝０を、パラメータも明記して、ｕ（ｓ，ｔ）＝ｖ（ｓ，ｔ）＝０と書く。この方程式は、ｔについては一次であるから、ｕ（ｓ，ｔ）＝０，ｖ（ｓ，ｔ）＝０それぞれからｔを解いて、ｔ＝ｈ１（ｓ）＝ｈ２（ｓ）と書ける。但し、ｈ１、ｈ２ともにｓの有理係数有理式である。ｈ１（ｓ）−ｈ２（ｓ）の分母を払った多項式をＰ（ｘ）とし、ｓの動く範囲をＳとする。Ｓは、有限の閉空間［ａ，ｂ］か、片方が無限となる［ａ，∞）あるいは、（∞，ｂ］、両方が無限のＲ全体、のいずれかである。
【００７９】
解くべき問題は、『有理係数方程式Ｐ（ｓ）＝０のＳに入る実根α、有理係数有理式Ｈ（ｓ），（ｈ１，ｈ２のどちらでも同じなので、計算が簡単な方を選んでよい）、有理数ｍ，ｕに対してｍ≦Ｈ（α）≦ｕかどうかを判定せよ』である。
【００８０】
これを解くために、Ｈ（ｓ）−ｍの分母を払った多項式とＰ（ｓ）との最大多項式Ｇｍ（ｓ）、及び、Ｈ（ｓ）−ｕの分母を払った多項式とＰ（ｓ）の最大公約多項式Ｇｕ（ｓ）を計算する。ＧｍとＧｕは互いに素であるから（Ｇｍの根αに対しＨ（α）＝ｍとなり、Ｇｕの根βに対しＨ（β）＝ｕとなるから）、Ｐの根は、Ｇｍの根、Ｇｕの根、Ｐ／（ＧｍＧｕ）の根の、三種類に分かれる。ＧｍあるいはＧｕの根αについては、α∈Ｓの判定のみ行えば十分であり、これは、「Sturmのアルゴリズム」などで可能である。Ｐ／（ＧｍＧｕ）の根βについては、β∈Ｓ及びｍ≦Ｈ（β）≦ｕの判定となるが、前者は、「Sturmのアルゴリズム」で、後者は、等号が成り立つことはなく、ｍ＜Ｈ（β）＜ｕの判定であるから、十分に精度を上げた誤差解析付の近似計算、例えば、区間計算で判定可能である。
【００８１】
以上を、各エッジ多項式について行っていき、どこかで零点があることが分かれば判定終了である。エッジ多項式は有限個であるから、全てについて零点がないことがわかれば区間多項式Ｆに属する多項式で、与えられた領域に零点をもつものがないことがわかり、判定が終了する。
【００８２】
図６は、本発明の一実施の形態における判定Ｃの動作のフローチャートである。
【００８３】
まず、区分内点判定部５０は、まだ調べていないエッジ多項式を記憶手段から読み出し、残っているパラメータをｔとする（ステップ１４１）。取得したエッジ多項式に対し、まだ調べていないＣの区分Ｃｋを取得する（ステップ１４２）。Ｃｋの有理係数有理式の表記φ（ｓ）＋ｉψ（ｓ）（ｓ∈Ｓ）をエッジ多項式に代入し、実部をｕ（ｓ，ｔ）、虚部をｖ（ｓ，ｔ）と書く（ステップ１４３）。
【００８４】
次に、ｕ＝ｖ＝０をｔについて解く。ｕ＝０から解いたものをｔ＝ｈ１（ｓ），ｖ＝０から解いたものをｔ＝ｈ２（ｓ）とする（ステップ１４４）。ｈ１（ｓ）−ｈ２（ｓ）の分母を払った多項式をＰ（ｓ）と書く（ステップ１４５）。ｈ１（ｓ），ｈ２（ｓ）のどちらかを選びＨ（ｓ）と書く（ステップ１４６）。Ｈ（ｓ）−ｍの分母を払った多項式とＰ（ｓ）の最大公約数多項式Ｇｍ（ｓ）及びＨ（ｓ）−ｕの分母を払った多項式Ｐ（ｓ）の最大公約多項式Ｇｕ（ｓ）を計算する（ステップ１４６）。
【００８５】
Ｇｍ（ｓ）＝０の実根βで、β∈Ｓを満たすものがあるかを判断し（ステップ１４８）、ある場合には、ＣあるいはＣの内部に零点を有すると判断する。ない場合には、Ｇｕ（ｓ）＝０の実根βで、β∈Ｓを満たすものがあるかを判断する（ステップ１４９）。ある場合には、ＣあるいはＣの内部に零点を有すると判断する。ない場合には、Ｐ（ｓ）／（Ｇｍ（ｓ）Ｇｕ（ｓ））＝０の実根βで、β∈Ｓかつｍ＜Ｈ（β）＜ｕを満たすものがあるかを判断する（ステップ１５０）。ある場合は、ＣあるいはＣの内部に零点を有すると判断する。ない場合には、取得したエッジ多項式に対し、まだ調べていないＣの区分が存在するかを判定し、存在する場合にはステップ１４２に移行する（ステップ１５１）。存在しない場合には、まだ調べていない多項式が存在するかを判断し、存在する場合にはステップ１４１に移行し、存在しない場合には、多項式Ｆは、Ｃ及び内部に零点を有しないと判断し、処理を終了する（ステップ１５２）。
【実施例】
【００８６】
以下、図面と共に本発明の実施例を説明する。
【００８７】
以下では、実際に区間多項式と領域を与えて説明する。なお、以下では、ある桁から先の値を省略する意味の『…』がない小数は、正確な値を表すものとする。
【００８８】
［第１の実施例］
図７は、本発明の第１の実施例の動作のフローチャートである。
【００８９】
本実施例では、Ｆを二次の区間多項式
［0.9995,1.0005］x2+[-0.6185,-0.6175]x+[0.995,1.0005]
とし、単純閉曲線Ｃとして、中心がｃ＝0．3096＋i・0.9526、半径がｒ＝0.0004の円周をとり、Ｃ及びその内部をＤとしたとき、Ｄに少なくとも一つの根を持つようなＦに属する多項式が存在するか否かを判定することを考える。
【００９０】
図８は、本発明の第１の実施例の円周Ｃを示す。なお、Ｃの有理関数による表示は以下の通り与えられているものとする。
【００９１】
Ｃ＝Ｃ１∪Ｃ２、但し、Ｃ１は、一点ｃ−ｒ（＝0.3092+i・0.9526）のみからなり、Ｃ２は、Ｃから一点ｃ−ｒを除いたものである。前者の表記は、ｘ＝ｃ−ｒであり、後者の表記は、ｘ＝ｃ＋ｒ（１−ｓ２）／（１＋ｓ２）＋ｉ・２ｒｓ／（１＋ｓ２）、但し、−∞＜ｓ＜∞である。
【００９２】
まず、Ｆに属する多項式ｆ０を一つとる（ステップ２０１）。ここでは、各区間係数の中点を係数とする多項式をｆ０とする。すなわち、f0(x)=x2-0.618+1である。f0(x)=0の二根は、0.309±i・√0.904519=0.309±i・0.951062,…であって、実部を見れば、Ｄの外にあることがわかる（ステップ２０２）。この状況を図９に示す。
【００９３】
次に、Ｃ上に根を持つようなｆ∈Ｆが存在するか否かの判定になる。
【００９４】
まず、「Ｃ１，Ｃ２の端点を根として持つｆが存在するか」（ステップ２０３）、であるが、今の場合、Ｃ１には端点がなく、Ｃ２の端点は、ｃ−ｒただ一点である。すなわち、「ｃ−ｒ（＝0.3092+i・0.9526）を根とするｆが存在するか」、である。
【００９５】
Ｆ=｛（0.9995+0.001t2）x2-(0.6185+0.001t1)x+(0.9995+0.001t0)｜0≦t0,t1,t2≦１｝
と書けることから、
(0.9995+0.001t2)x2-(0.6185+0.001t1)x+(0.9995+0.001t0)=0
を解くことになる。これに、ｘ＝ｃ−ｒを代入し、整理したものが以下のようになる。
【００９６】
【数２５】
2005235121.tif 000021
ｔ２の係数の実部が負なので、ｔ２を１−ｔ２で置き換えると、以下のようになる。
【００９７】
【数２６】
2005235121.tif 000022
係数をソートすると、
v1=0.00081184212-i・0.00058908784,
v2=0.001,
v3=0.0003092+i・0.0009526
となる。よって、凸包の頂点リスト及びその座標は、以下のようになる。
【００９８】
【数２７】
2005235121.tif 000023
この凸包に、
【００９９】
【数２８】
2005235121.tif 000024
の右辺の値v=0.00398824106-i・0.00019928392は入らないことがわかる。この状況を図１０に示す。
【０１００】
次に、Ｃ１上に零点があるかの判定を行なう（ステップ２０５）。これは、以下に示す１２本のエッジ多項式から決まる方程式が対象となる。
【０１０１】
【数２９】
2005235121.tif 000025
以下、上記の最初の式をｆ１とし、それについて説明する。
f1(x)=tx2-(6185/10000)x+9995/10000=0(9995/10000≦ｔ≦10005/10000)である。
【０１０２】
まず、x=c+r(1-s2)/(1+s2)+i・2rs/(1+s2)(-∞<s<∞)を代入して整理すると、その実部、虚部は、以下の通りとなる。
【０１０３】
【数３０】
2005235121.tif 000026
上記の実部、虚部それぞれにおいて、ｔを解くと以下のようになる。
【０１０４】
【数３１】
2005235121.tif 000027
上記の等式を整理すると、以下のようになる。
【０１０５】
【数３２】
2005235121.tif 000028
「Sturmのアルゴリズム」を使えば、上記の方程式に実根がないことがわかる。よって、全ての
t(9995/10000≦t≦10005/10000)
に対して
f1(x)=tx2-(6185/10000)x+9995/10000=0
の根はＤの外であることがわかる。
【０１０６】
他の11本の多項式についても同じように確認することにより（ステップ２０６）、Ｆの中にはＤに根を持つ多項式がないことがわかる（ステップ２０７）。
【０１０７】
［第2の実施例］
本実施例では、区間多項式Ｆは、上記の第1の実施例と同じものとする。
【０１０８】
単純閉曲線Ｃとして、４つの頂点が、
R1=0.3092+i・0.95
R2=0.31+i・0.95
R3=0.31+i・0.953
R4=0.3092+i・0.953
である長方形をとる。図１１にその長方形Ｃを示す。なお、同図において、点線で示してある円周は、前述の第1の実施例のものである。なお、Ｃの有理関数による表示は、以下の通り与えられているものとする。
【０１０９】
Ｃ＝Ｃ１∪Ｃ２∪Ｃ３∪Ｃ４但し、Ｃ１，Ｃ２，Ｃ３，Ｃ４の表示は、以下に示すとおりである。
【０１１０】
【数３３】
2005235121.tif 000029
図１２は、本発明の第２の実施例の動作のフローチャート（その１）である。
【０１１１】
Ｆに属する多項式として、第1の実施例と同じf0(x)=x2-0.618x+1をとる（ステップ３０１）。ｆ0(x)=0の二根は、0.309±i・√0.904519=0.309±i・0.951062…であって、実部を見ればいずれもＤの外にあることがわかる。この状況を図１３に示す。
【０１１２】
次に、Ｃ上に零点を持つようなｆ∈Ｆが存在するか否かの判定を行う（ステップ３０２）。
【０１１３】
まず、「Ｃ１，Ｃ２，Ｃ３，Ｃ４の端点、すなわち、4点Ｒ１，Ｒ２，Ｒ３，Ｒ４を零点として持つｆが存在するか」、を判定する。第1の実施例と同じく、
(0.9995+0.001t2)x2-(0.6185+0.001t1)x+(0.9995+0.001t0)=0
のｘに、Ｒ１，Ｒ２，Ｒ３，Ｒ４の座標を入れて整理し（ステップ３０３）、必要ならｔｊを1−ｔｊで置き換えて、凸包を作って調べることになる（ステップ３０４）。Ｒ１，Ｒ２，Ｒ３，Ｒ４それぞれに対応する凸包及びその頂点を、図１４、図１５、図１６、図１７に示す、いずれにしてもＣの区分の端点を零点とする多項式ｆ∈Ｆは存在しないことがわかる（ステップ３０６）。
【０１１４】
図１８は、本発明の第２の実施例の動作のフローチャート（その２）である。
【０１１５】
次に、端点を除く、Ｃ１，Ｃ２，Ｃ３，Ｃ４上に零点があるかの判定を行う。これは、第1の実施例と同じ、以下の１２本のエッジ多項式から決まる方程式が対象となる。
【０１１６】
【数３４】
2005235121.tif 000030
但し、それぞれの方程式について、Ｃ１，Ｃ２，Ｃ３，Ｃ４上を調べることになるので、全部で48回の判定となる。以下、上記の最初の式をｆ１とし（ステップ４０１）、それについて説明する。
【０１１７】
ｆ１(x)=tx2-(6185/10000)x+9995/10000=0(9995/10000≦t≦10005/10000)
である。
【０１１８】
まず、長方形の上の辺Ｃ３について調べる。
【０１１９】
ｘ=s+i・953/1000(3092/10000≦s≦31/100)
を代入して整理すると（ステップ４０２）、その実部、虚部は、以下のようになる。
【０１２０】
【数３５】
2005235121.tif 000031
上記の実部、虚部それぞれにおいてｔを解くと（ステップ４０３）、以下のようになる。
【０１２１】
【数３６】
2005235121.tif 000032
上記の第二項と第三項が等しいという方程式を整理すると、以下のようになる。
【０１２２】
【数３７】
2005235121.tif 000033
上記の方程式は、3092/10000≦ｓ≦31/100の範囲に根を持たない。実際、これの一根は、0.028…、もう一根は32.3…である（ステップ４０４）。
【０１２３】
次に、長方形の左の辺Ｃ４について調べる。
【０１２４】
x=3092/10000+i・s(95/100≦ｓ≦953/1000)
を代入して整理すると（ステップ４０５）、その実部、虚部は、以下のようになる。
【０１２５】
【数３８】
2005235121.tif 000034
上記の実部、虚部それぞれにおいて、ｔを解くと（ステップ４０６）、以下のようになる。
【０１２６】
【数３９】
2005235121.tif 000035
上記の第二項と第三項が等しいという式を整理すると、以下のようになる。
【０１２７】
【数４０】
2005235121.tif 000036
上記の方程式は、95/100≦ｓ≦953/1000の範囲に一つの根s=0.950649…を持つ（ステップ４０７）。そのとき、t=6185/6184=1.0001617…で、9995/10000≦t≦10005/10000、すなわち、0.9995≦t≦1.0005の範囲内に収まっている（ステップ４０８）。
【０１２８】
以上より、Ｆに属する多項式
tx2-0.6185x+0.9995=0(t=6185/6184)が、0.3092+si(s=0.950649…)
というＤ内（より詳しくは、長方形の左の辺Ｃ４上）に根を持つことがわかる（ステップ３０４）。この状況を図１９に示す。
【０１２９】
ここまでは、説明を簡単にするため、区間の端点や曲線を表す式の係数は有理数としてきたが、有理数に限らず、計算機上で四則演算及び等号判定が厳密に実行可能な数ならよい。例えば、実代数的数（一変数整数係数代数方程式の根となる実数）としてもよい。
【０１３０】
また、区間多項式は、単項式ｘｊに区間係数［ｍｊ，ｕｊ］を掛けたものの和の形のみであったが、より一般的に、係数が正確に分かっている多項式ｅｊ（ｘ）に区間係数［ｍｊ，ｕｊ］を掛けたものの和の形としてもよい。すなわち、
【０１３１】
【数４１】
2005235121.tif 000037
の形でもよい。
【０１３２】
なお、区間演算を用いて、
【０１３３】
【数４２】
2005235121.tif 000038
を、
【０１３４】
【数４３】
2005235121.tif 000039
と整理すると、（Ａｊは区間）、Ｆ（ｘ）⊂Ｇ（ｘ）は常に成立するが、一般にはＦ（ｘ）≠Ｇ（ｘ）である。よって、整理する前の形のまま扱う必要がある。
【０１３５】
このような形は、応用上、例えば、いつくかの点における値によって定められた多項式として現れる。具体的には、相異なるｎ＋１個の点ａ０，ａ１，…，ａｎでの値がｂ０，ｂ１，…，ｂｎである高々ｎ次の多項式ｆ（ｘ）は一意に決まり、
【０１３６】
【数４４】
2005235121.tif 000040
として、
【０１３７】
【数４５】
2005235121.tif 000041
と書ける。従って、ｂｊの値に誤差があるときは、
【０１３８】
【数４６】
2005235121.tif 000042
の形となる。
【０１３９】
なお、上記の実施の形態及び実施例における動作をプログラムとして構築し、コンピュータのＣＰＵにインストールし実行させる、または、ネットワークを介して流通させることが可能である。
【０１４０】
また、構築されたプログラムをコンピュータに接続されるハードディスク装置や、フレキシブルディスクやＣＤ−ＲＯＭ等の可搬記憶媒体に格納しておき、コンピュータに読み込ませ、実行させることも可能である。
【０１４１】
なお、本発明は、上記の実施の形態及び実施例に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。
【産業上の利用可能性】
【０１４２】
本発明は、与えられた領域（単純閉曲線やその内部）が複素空間である場合に適用可能である。
【図面の簡単な説明】
【０１４３】
【図１】本発明の原理を説明するための図である。
【図２】本発明の一実施の形態における位置判定装置の構成図である。
【図３】本発明の一実施の形態における判定処理のフローチャートである。
【図４】本発明の一実施の形態における判定Ａの動作のフローチャートである。
【図５】本発明の一実施の形態における判定Ｂの動作のフローチャートである。
【図６】本発明の一実施の形態における判定Ｃの動作のフローチャートである。
【図７】本発明の第1の実施例の動作のフローチャートである。
【図８】本発明の第1の実施例の円周Ｃを示す図である。
【図９】本発明の第1の実施例の各区間係数の中点を係数とする多項式を説明するための図である。
【図１０】本発明の第1の実施例の動作を説明するための図である。
【図１１】本発明の第２の実施例の与えられた単純閉曲線である長方形Ｃを示す図である。
【図１２】本発明の第２の実施例の動作のフローチャート（その１）である。
【図１３】本発明の第２の実施例の一つ取り出した多項式の零点と与えられた領域の位置関係を示す図である。
【図１４】本発明の第２の実施例の長方形の頂点Ｒ１を根とするＦに属する多項式が存在するか否かを判定するための凸包及びその頂点座標を示す図である。
【図１５】本発明の第２の実施例の長方形の頂点Ｒ２を根とするＦに属する多項式が存在するか否かを判定するための凸包及びその頂点座標を示す図である。
【図１６】本発明の第２の実施例の長方形の頂点Ｒ３を根とするＦに属する多項式が存在するか否かを判定するための凸包及びその頂点座標を示す図である。
【図１７】本発明の第２の実施例の長方形の頂点Ｒ４を根とするＦに属する多項式が存在するか否かを判定するための凸包及びその頂点座標を示す図である。
【図１８】本発明の第２の実施例の動作のフローチャート（その２）である。
【図１９】本発明の第２の実施例の与えられた長方形の左辺上にあるＦに属する多項式の零点を示す図である。
【図２０】ｆｍ（ａ）とｆｍ（ｂ）が同符号、ｆｕ（ａ）とｆｕ（ｂ）が同符号の場合を示す図である。
【図２１】ｆｍが区間［ａ，ｂ］に根を持つ例を示す図である。
【図２２】ｆｍが区間［ａ，ｂ］に根を持たない例を示す図である。
【符号の説明】
【０１４４】
１０  入力部
２０  代表多項式抽出部
３０  代表多項式判定部
４０  区分境界点判定部
５０  区分内点判定部
６０  出力部
【図１】
2005235121.tif 000049
【図２】
2005235121.tif 000050
【図３】
2005235121.tif 000051
【図４】
2005235121.tif 000052
【図５】
2005235121.tif 000053
【図６】
2005235121.tif 000054
【図７】
2005235121.tif 000055
【図８】
2005235121.tif 000056
【図９】
2005235121.tif 000057
【図１０】
2005235121.tif 000058
【図１１】
2005235121.tif 000059
【図１２】
2005235121.tif 000060
【図１３】
2005235121.tif 000061
【図１４】
2005235121.tif 000062
【図１５】
2005235121.tif 000063
【図１６】
2005235121.tif 000064
【図１７】
2005235121.tif 000065
【図１８】
2005235121.tif 000066
【図１９】
2005235121.tif 000067
【図２０】
2005235121.tif 000068
【図２１】
2005235121.tif 000069
【図２２】
2005235121.tif 000070