距離算出装置、多項式算出装置、距離算出方法、多項式算出方法、および記録媒体
【課題】本発明は、解く必要のある方程式の数がｅｊ（ｘ）の数の多項式オーダで収まる方法を提供することを目的とする。
【解決手段】本発明の距離算出装置は、記録部、多項式判定部、第１計算部、第２計算部 を備える。第１計算部は、集合Δと集合Δ〜と集合Ｚ〜と集合Ｚを求めるΔ、Δ〜、Ｚ〜、Ｚ計算手段、集合Δ＼Ｚ〜と集合Ｊ＼Ｚを求めるΔ＼Ｚ〜、Ｊ＼Ｚ計算手段、φｊ（σ）計算手段、Φ（σ）計算手段、実閉区間確認手段、ｍ計算手段、ｍ決定手段を有する。
【解決手段】本発明の距離算出装置は、記録部、多項式判定部、第１計算部、第２計算部 を備える。第１計算部は、集合Δと集合Δ〜と集合Ｚ〜と集合Ｚを求めるΔ、Δ〜、Ｚ〜、Ｚ計算手段、集合Δ＼Ｚ〜と集合Ｊ＼Ｚを求めるΔ＼Ｚ〜、Ｊ＼Ｚ計算手段、φｊ（σ）計算手段、Φ（σ）計算手段、実閉区間確認手段、ｍ計算手段、ｍ決定手段を有する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、実数全体の集合内の指定された区間に実重複零点を持つ一変数実多項式のうち、上記区間に実重複零点を持たない或る一変数実多項式ｆに最も近い一変数実多項式ｆ~について、一変数実多項式ｆと一変数実多項式ｆ~との距離を求める技術、および一変数実多項式ｆ~を求める技術に関する。
【背景技術】
【０００２】
デジタル信号処理やシステム制御の分野において、実一変数多項式の零点の位置は、デジタルフィルタの周波数特性やシステムの性能に密接に関係する。デジタルフィルタの周波数特性やシステムの性能を設計する上で、ある実区間Ｉに所望の個数（ゼロ個の場合も含む）の実零点を持つように多項式の係数を設定したい場合を考える。多項式の係数は有限精度でしか指定できないので、必ず誤差を持つ。また、多項式の実重複零点は、どんなに小さな係数の変化に対しても、複数の複素零点あるいは実の近接零点となるので、実重複零点を持つ多項式が係数の誤差範囲に存在すれば、実区間Ｉの実零点の個数を制御できないことになる。したがって、設計によって求めた実一変数多項式が、実重複零点を持つ実一変数多項式とどの程度離れているのかは、デジタルフィルタの周波数特性やシステムの性能を設計する上で重要な問題である。なお、実閉区間Ｉは、Ｒ上の閉区間であって、ａ，ｂ∈Ｒとして、［ａ，ｂ］,（−∞,a］,［b，＋∞）,（−∞，＋∞）のいずれかで表現される。
【０００３】
ｆ（ｘ），ｅ１（ｘ），ｅ２（ｘ），…，ｅｎ（ｘ）は、それぞれあらかじめ与えられた一変数実多項式（係数が実数の一変数多項式）であるとする。ただし、実数全体の集合をＲと表記し、ｅ１（ｘ），ｅ２（ｘ），…，ｅｎ（ｘ）はＲ上一次独立とする。つまり、実数ｃ１，ｃ２，…，ｃｎに対して、ｃ１ｅ１（ｘ）＋ｃ２ｅ２（ｘ）＋・・・＋ｃｎｅｎ（ｘ）が恒等的に０となるのは、ｃ１＝ｃ２＝・・・＝ｃｎ＝０の場合に限られるとする。また、ａ１，ａ２，…，ａｎもあらかじめ与えられた実数とする。
【０００４】
２つの多項式間の距離を測る代表的な方法には、ｌ∞−ノルムとｌ２−ノルムとがある。ｌ∞−ノルムでの距離は、以下のように定義される。２つの一変数実多項式ｆ（ｘ）、ｇ（ｘ）を
【０００５】
【数２５】
とすると、距離ｄ（ｇ，ｈ）は、ｍａｘ｛｜ａ１−ｂ１｜，｜ａ２−ｂ２｜，…，｜ａｎ−ｂｎ｜｝で与えられる。
ｌ２−ノルムでの距離は、以下のように定義される。２つの一変数実多項式ｆ（ｘ）、ｇ（ｘ）を
【０００６】
【数２６】
とすると、距離ｄ（ｆ，ｇ）は、
【０００７】
【数２７】
で与えられる。
【０００８】
ある実区間Ｉに重複零点を持たないように多項式の係数を設定したい場合に、係数に誤差が含まれたとしても間違いなく実区間Ｉに重複零点を持たないようにできるかという問題を解決する必要がある。これと類似の問題を扱っている文献として、非特許文献１がある。非特許文献１では、ｌ２−ノルムを最小とする多項式を求める問題を、ある二次形式の最小化の問題に帰着して解決している。これは、本発明で扱う問題を似ているが、係数およびその誤差を複素数の範囲とする点、重複零点を実とは限らない点、多項式間の距離をｌ∞−ノルムではなくｌ２−ノルムで測っている点が異なり、本発明と似て非なるものである。
【０００９】
また、２つの多項式ｆ（ｘ）、ｇ（ｘ）の距離をｌ∞−ノルムで定義した文献としては、非特許文献２がある。
【非特許文献１】L. Zhi and W. Wu, "Nearest Singular Polynomials," Journal of Symbolic Computation, Vol.26, No.6, pp.667-675, 1998.
【非特許文献２】H.Sekigawa, "The Nearest Real Polynomial with a Real Multiple Zero in a Given Real Interval," Proc. Asian Symposium on Computer Mathematics (ASCM2007), 2007.
【発明の開示】
【発明が解決しようとする課題】
【００１０】
まず、非特許文献２の内容について説明する。実閉区間Ｉに重複零点を持ち、かつ、一変数実多項式f（ｘ）にｌ∞−ノルムで計算して最も近い一変数実多項式
【００１１】
【数２８】
について、以下の性質が成り立つ。
【００１２】
性質１
高々１つの例外の係数を除き、｜ｔｊ｜＝ｄ（ｆ，ｆ〜）が成り立つ。よって、以下の２つの場合に分けて問題を扱う。
（ｉ）すべてのｊに対して｜ｔｊ｜＝ｄ（ｆ，ｆ〜）が成り立つ場合
（ｉｉ）｜ｔμ｜＜｜ｔ１｜＝・・・＝｜ｔμ−１｜＝｜ｔμ＋１｜＝・・・＝｜ｔｎ｜となるμが存在する場合
（ｉ）の場合、ｘとｔｊに関する連立方程式
【００１３】
【数２９】
をｘ∈Ｉかつｔ１，…，ｔｎ∈Ｒという条件の下で解き、解の中で｜ｔ１｜＝・・・＝｜ｔｎ｜が最小となるものが最小距離であり、それに対応する多項式が｜ｆ（ｘ）−ｆ〜（ｘ）｜が最小となる多項式である。条件を満たす解がないとき、（ｉ）の場合には、Ｉに実重複零点を持つ多項式は存在しない。方程式（１）がｘ∈Ｉかつｔ１，…，ｔｎ∈Ｒという解を持つことは、以下のうち少なくとも一組の連立方程式がｘ∈Ｉかつｔ∈Ｒという解を持つことと同値である。
【００１４】
【数３０】
ここで、±は、＋と−のすべての組合せがあるので、組合せは２ｎ−１通りである。すなわち、最悪の場合、２ｎ−１の方程式を解く必要がある。（ｉｉ）の場合、｜ｔμ｜＝ｄ（ｆ，ｆ〜）であるから、
【００１５】
【数３１】
をｘ∈Ｉかつｔ１，…，ｔｎ∈Ｒという条件の下で解き、解の中で｜ｔ１｜＝・・・＝｜ｔμ−１｜＝｜ｔμ＋１｜＝・・・＝｜ｔｎ｜が最小となるものが最小距離、それに対応する多項式が｜ｆ（ｘ）−ｆ〜（ｘ）｜が最小となる多項式である。条件を満たす解がないとき、（ｉｉ）の場合には、Ｉに重複零点を持つ多項式が存在しない。方程式（２）がｘ∈Ｉかつｔ１，…，ｔｎ∈Ｒという解を持つということは、以下のうち少なくとも一組の連立方程式がｘ∈Ｉ，ｔμ，ｔ∈Ｒかつ｜ｔμ｜＜｜ｔ｜という解を持つことと同値である。
【００１６】
【数３２】
ここで、±は、＋と−のすべての組合せがあるので、組合せは２ｎ−２通りである。また、μの選び方がｎ通りある。すなわち、最悪の場合、２ｎ−２・ｎの方程式を解く必要がある。
【００１７】
このように、非特許文献２の方法では、最悪の場合、解く必要のある連立方程式の組の数がｅｊ（ｘ）の数の指数になる。したがって、ｅｊ（ｘ）の数が多い場合には現実的な方法ではない。
【００１８】
本発明の目的は、解く必要のある方程式の数がｅｊ（ｘ）の数の多項式オーダで収まる実閉区間Ｉに実重複零点を持ち、かつ、一変数実多項式f（ｘ）にｌ∞−ノルムで計算して最も近い一変数実多項式までの距離を求める方法を提供すること、および最も近い一変数実多項式を求める方法を提供することである。
【課題を解決するための手段】
【００１９】
本発明の距離算出装置は、実数全体の集合をＲとし、ａ１，ａ２，…，ａｎをそれぞれあらかじめ与えられた実数とし、ｅ１（ｘ），…，ｅｎ（ｘ）をそれぞれあらかじめ与えられた一変数実多項式とし、一変数実多項式ｆ（ｘ）が実閉区間Ｉに実重複零点を持たないとして、一変数実多項式の集合
【００２０】
【数３３】
のうち、実閉区間Ｉに実重複零点を持ち、かつ、一変数実多項式f（ｘ）にｌ∞−ノルムで計算して最も近い一変数実多項式ｆ〜（ｘ）について、一変数実多項式ｆ（ｘ）と一変数実多項式ｆ〜（ｘ）との距離を算出する距離算出装置であって、記録部、多項式判定部、第１計算部、第２計算部を備える。
【００２１】
記録部は、ａ１，ａ２，…，ａｎと、ｆ（ｘ），ｅ１（ｘ），…，ｅｎ（ｘ）と、実閉区間Ｉとを記録する。多項式判定部は、ｎ＝１かｎ＞１かを判定する。第１計算部は、ｎ＞１のときに一変数実多項式ｆ（ｘ）と一変数実多項式ｆ〜（ｘ）との距離を算出する。第２計算部は、ｎ＝１のときに一変数実多項式ｆ（ｘ）と一変数実多項式ｆ〜（ｘ）との距離を算出する。
【００２２】
第１計算部は、Δ、Δ〜、Ｚ〜、Ｚ計算手段、Δ＼Ｚ〜、Ｊ＼Ｚ計算手段、φｊ（σ）計算手段、Φ（σ）計算手段、実閉区間確認手段、ｍ計算手段、ｍ決定手段を有する。Δ、Δ〜、Ｚ〜、Ｚ計算手段は、
【００２３】
【数３４】
を求める。Δ＼Ｚ〜、Ｊ＼Ｚ計算手段は、集合Δ＼Ｚ〜と集合Ｊ＼Ｚを求める。φｊ（σ）計算手段は、
【００２４】
【数３５】
ただし、σ∈Ｉ＼Δ、ｊ＝１，…，ｎ
を求める。Φ（σ）計算手段は、
【００２５】
【数３６】
を求める。実閉区間確認手段は、実閉区間Ｉが一点かを確認する。ｍ計算手段は、実閉区間Ｉが一点でない場合に、
【００２６】
【数３７】
を計算する。ｍ決定手段は、実閉区間Ｉが一点でない場合にはｍ＝ｍｉｎ｛ｍ１，…，ｍ４｝とし、実閉区間Ｉが一点の場合にはｍ＝Φ（σ）のように距離ｍを決定する。
【００２７】
第２計算部は、連立方程式生成手段、恒等性確認手段、多項式生成手段、距離計算手段、距離選定手段、ゼロ多項式用距離計算手段を有する。連立方程式生成手段は、
【００２８】
【数３８】
を生成する。恒等性確認手段は、ｆ(ｘ)ｅ’１（ｘ）−ｆ’（ｘ）ｅ１（ｘ）が恒等的に０かを確認する。多項式生成手段は、ｆ(ｘ)ｅ’１（ｘ）−ｆ’（ｘ）ｅ１（ｘ）が恒等的に０ではない場合に、ｆ(ｘ)ｅ’１（ｘ）−ｆ’（ｘ）ｅ１（ｘ）＝０を満たす有限個のｔ１を求め、すべてのｔ１に対する多項式ｆ(ｘ)＋ｔ１ｅ１（ｘ）を生成する。距離計算手段は、ｆ(ｘ)ｅ’１（ｘ）−ｆ’（ｘ）ｅ１（ｘ）が恒等的に０ではない場合に、ｌ∞−ノルムによって多項式生成手段が生成した各多項式と多項式ｆ（ｘ）との距離を計算する。距離選定手段は、ｆ(ｘ)ｅ’１（ｘ）−ｆ’（ｘ）ｅ１（ｘ）が恒等的に０ではない場合に、距離計算手段が計算した距離の中で最小の距離を選定する。ゼロ多項式用距離計算手段は、ｆ(ｘ)ｅ’１（ｘ）−ｆ’（ｘ）ｅ１（ｘ）が恒等的に０の場合に、ｌ∞−ノルムによってゼロ多項式と多項式ｆ（ｘ）との距離を計算する。
【００２９】
本発明の多項式算出装置は、第１計算部にさらに多項式算出手段を有し、第２計算部は距離選定手段とゼロ多項式用距離計算手段の代わりに多項式選定手段を有する。多項式算出手段は、多項式
【００３０】
【数３９】
の中の１つまたは複数の情報を求める。多項式選定手段は、ｆ(ｘ)ｅ’１（ｘ）−ｆ’（ｘ）ｅ１（ｘ）が恒等的に０ではない場合には、距離計算手段が計算した距離が最小となる多項式を選定し、ｆ(ｘ)ｅ’１（ｘ）−ｆ’（ｘ）ｅ１（ｘ）が恒等的に０の場合には、ゼロ多項式を選定する。
【発明の効果】
【００３１】
本発明の距離算出装置および多項式算出装置はこのような構成なので、実閉区間Ｉに属する点σを零点とする多項式のうち、ｆ（ｘ）に最も近いものまでの距離を表す式Φ（σ）を導入し、その後にσをＩ上で動かしたときの距離の最小値を求めている。したがって、解く必要のある方程式の数、その次数をｎ、ｄ＝ｍａｘ｛ｄｅｇ（ｆ(ｘ)），ｄｅｇ（ｅ１（ｘ）），…，ｄｅｇ（ｅｎ（ｘ））｝の多項式オーダにできる。
【発明を実施するための最良の形態】
【００３２】
［理論的説明］
本発明では、実数全体の集合をＲ、ａ１，ａ２，…，ａｎをそれぞれあらかじめ与えられた実数、ｆ（ｘ），ｅ１（ｘ），…，ｅｎ（ｘ）をそれぞれあらかじめ与えられた一変数実多項式とし、ｅ１（ｘ），…，ｅｎ（ｘ）はＲ上一時独立とする。また、集合Ｆを
【００３３】
【数４０】
とする。Ｉはあらかじめ与えられた実閉区間とし、ｆ（ｘ）はＩに重複零点を持たないものとする。実閉区間Ｉが有界でないときには、集合Ｆに属する多項式の次数はｔｊによらず一定と仮定する。なお、重み付きのｌ∞−ノルムｍａｘｊ｛ｗｊ｜ａｊ｜｝（ただし、０＜ｗｊ）を用いる場合は、｛ｅ１（ｘ），…，ｅｎ（ｘ）｝の代わりに、｛ｅ１（ｘ）／ｗ１，…，ｅｎ（ｘ）／ｗｎ｝を用いればよい。
【００３４】
次の定理は、非特許文献２に示されている定理１（THEOREM1）である。
定理１
一変数実多項式ｆ（ｘ）と集合Ｆは上記の通り、距離ｄ（ｆ，ｇ）はｌ∞−ノルムでの距離、Ｉは実閉区間とする。もし、Ｉに重複零点を持つ多項式ｇ（ｘ）∈Ｆが存在するならば、Ｉに重複零点を持ち、かつ‖ｆ−ｆ〜‖∞が最小となるようなｆ〜（ｘ）∈Ｆが存在する。
【００３５】
次の定理は、定理１の「Ｉに重複零点を持つ多項式ｇ（ｘ）∈Ｆが存在」という条件が、ある場合は自動的に満たされることを示すものである。
定理２
一変数実多項式ｆ（ｘ）、ｅ１（ｘ），…，ｅｎ（ｘ）は上記の通りとし、Ｉは一点ではないとする。ｎ≧２のとき、集合Ｆに属する多項式でＩに重複零点を持つものが存在する。
証明
ｎ＝２の場合に証明すれば十分である。ｆ（ｘ）＋ｔ１ｅ１（ｘ）＋ｔ２ｅ２（ｘ）がｘ＝ｃにおいて重複零点を持つ必要十分条件は、連立方程式
【００３６】
【数４１】
がｘ＝ｃを解とすることである。ただし、ｆ’（ｘ）は、ｆ（ｘ）をｘで１回微分した多項式である。上記連立方程式をｔ１とｔ２に関する連立方程式（ｘはパラメータ）と見る。ｅ１（ｘ）とｅ２（ｘ）はＲ上一次独立だから、（ｅ１（ｘ），ｅ’１（ｘ））と（ｅ２（ｘ），ｅ’２（ｘ））もＲ上一次独立である。
【００３７】
よって、行列式ｅ１（ｘ）ｅ’２（ｘ）−ｅ’１（ｘ）ｅ２（ｘ）は多項式として０ではなく、これが０となるようなｘは有限個である。なぜならば、ｅ１（ｘ）ｅ’２（ｘ）−ｅ’１（ｘ）ｅ２（ｘ）が多項式として０と仮定すると、（後述するｎ＝１の場合と同じ議論で、）ある実数ａがあって、ｅ２（ｘ）＝ａｅ１（ｘ）と書けることになるが、これはｅ１（ｘ）とｅ２（ｘ）がＲ上一次独立であることに矛盾するからである。
【００３８】
よって、適当にｃを選べば、ｅ１（ｃ）ｅ’２（ｃ）−ｅ’１（ｃ）ｅ２（ｃ）≠０とできる。そのｃに対して上記連立方程式は解けて、ｔ１，ｔ２∈Ｒの値が決まる。
（証明終）
【００３９】
なお、Ｉが一点の場合は、後述の補題１により、最近多項式が存在するか否か判定できることに注意されたい。ｎ＝１の場合、ｆ（ｘ）＋ｔ１ｅ１（ｘ）（ｔ１∈Ｒ）がｘ＝ｃにおいて重複零点を持つ必要十分条件は、連立方程式
【００４０】
【数４２】
がｘ＝ｃを解とすることである。よって、行列式ｆ（ｃ）ｅ’１（ｃ）−ｆ’（ｃ）ｅ１（ｃ）は０となる。これは、ｓ０とｓ１についての連立方程式
【００４１】
【数４３】
が（ｓ０，ｓ１）＝（１，ｔ１）という（０，０）ではない解を持つことからいえる。
【００４２】
したがって、ｆ（ｘ）ｅ’１（ｘ）−ｆ’（ｘ）ｅ１（ｘ）が多項式として０でないときには、ｆ（ｘ）ｅ’１（ｘ）−ｆ’（ｘ）ｅ１（ｘ）＝０を解いて（根は有限個）、それらについて連立方程式（３）を満たすｔ１を求めればよい。なお、このときには、解がない場合もある。例えば、ｆ（ｘ）＝１、ｅ１（ｘ）＝ｘ２などである。また、解がある場合でも、この段階で候補が有限個となるので、直接一番近い多項式を求めることができる。
【００４３】
次に、ｆ（ｘ）ｅ’１（ｘ）−ｆ’（ｘ）ｅ１（ｘ）が多項式として０のときには、ｆ（ｘ）／ｅ１（ｘ）＝ｆ’（ｘ）／ｅ’１（ｘ）＝ｐ（ｘ）とおくことができ、
ｆ（ｘ）＝ｐ（ｘ）ｅ１（ｘ）
ｆ’（ｘ）＝ｐ（ｘ）ｅ’１（ｘ）
が成り立つ。一方、ｆ（ｘ）＝ｐ（ｘ）ｅ１（ｘ）の両辺を微分すると、
ｆ’（ｘ）＝ｐ’（ｘ）ｅ１（ｘ）＋ｐ（ｘ）ｅ’１（ｘ）
である。よって、有理関数として、ｐ’（ｘ）ｅ１（ｘ）＝０となるが、ｅ１（ｘ）は多項式として０ではないから、ｐ’（ｘ）が０となる。つまり、ｐ（ｘ）は定数となるので、ａとおくと、ｆ（ｘ）＝ａ・ｅ１（ｘ）と書ける。よって、連立方程式（３）は、
【００４４】
【数４４】
となる。解がｔ１＝−ａの場合、ｆ（ｘ）−ａ・ｅ１（ｘ）はゼロ多項式である。なお、解がｔ１≠−ａとすると、ｅ１（ｘ）＝ｅ’１（ｘ）＝０となる。このときｅ１（ｘ）がＩに実重複零点を持つことになり、ｆ（ｘ）＝ａ・ｅ１（ｘ）も実重複零点を持つことになってしまう。これは、ｆ（ｘ）がＩに実重複零点を持たないことに矛盾する。つまり、ｆ（ｘ）ｅ’１（ｘ）−ｆ’（ｘ）ｅ１（ｘ）が多項式として０のときには、ゼロ多項式が最近多項式である。
【００４５】
次の補題は、最小距離を算出する上で重要な役割を果たすものである。
補題１
ｆ（ｘ），ｅｊ（ｘ）はあらかじめ与えられた実係数一変数多項式とし、
【００４６】
【数４５】
とする。このとき、αを零点とするf〜∈Ｆεが存在する必要十分条件は以下のとおりである。
【００４７】
【数４６】
なお、本明細書中ではＦ^は、ベクトルを表現しており、Ｆは集合を表現していることに注意されたい。
証明
αを重複零点とするｇ∈Ｆεが存在する必要十分条件は、(0,0)が集合
{(h(α),h’(α))|h(x)∈Ｆε｝ (4)
に属することである。
【００４８】
【数４７】
とすると、上記の集合は以下のように書ける。
【００４９】
【数４８】
集合Ｖε（α）は凸多角形となる。これは文献（H.Sekigawa and K.Shirayanagi, "Locating Real Multiple Zeros of a Real Interval Polynomial Proc.," International Symposium on Symbolic and Algebraic Computation（ISSAC2006），pp.310-317, 2006.）のTHEOREM4に示されている。凸多角形の頂点は以下のように求めることができる。
【００５０】
【数４９】
よって、凸多角形
【００５１】
【数５０】
【００５２】
【数５１】
【００５３】
【数５２】
【００５４】
【数５３】
【００５５】
【数５４】
凸多角形が線分に退化した場合、すなわち、ｊ＝１，…，ｎに対して式（８）の右辺が０となる場合、不等式（９）が必要である。
【００５６】
（０，０）が集合（４）に属する必要十分条件は、−Ｆ＾（α）が凸多角形（６）に属することである。
【００５７】
【数５５】
以下の等式が成り立つことに注意されたい。
【００５８】
【数５６】
したがって、以下が成り立つ。
【００５９】
【数５７】
よって、以下の不等式が成り立つ。
【００６０】
【数５８】
最後に、以下の点に注意すれば証明が終わる。
【００６１】
【数５９】
（証明終）
【００６２】
以下の定理は補題１からしたがう。根号を避けるため、補題１で退化の場合の式を変形する。
定理３
【００６３】
【数６０】
ｆ（ｘ），ｅｊ（ｘ）はあらかじめ与えられた実係数一変数多項式とし、αはｆ（ｘ）の実重複零点ではないものとする。
【００６４】
１．１≦ｊ＜ｋ≦ｎに対して、A(E^j(α),E^j(α))=0が成立するとき、最近多項式が存在する必要十分条件は、A(E^j(α),F^(α))=0が、ｊ＝１，…，ｎにたいして成り立ち、さらに、E^j(α)≠(0,0)となるｊが存在することである。このときの距離は、
【００６５】
【数６１】
である。
【００６６】
２．あるｊ＜ｋに対して、A(E^j(α),E^j(α))≠0が成立するとき、最近多項式は存在する。最小距離は、
【００６７】
【数６２】
である。ただし、分母が０となるものは除く。
証明
２は、補題１からただちに従うので、１のみを証明する。(0,0)，E^1(α)，…，E^n(α)が一直線上にあり、最近多項式が存在する条件が満たされているとき、ｊ＝１，…，ｎに対し、E^j(α)＝αjF(α)（αj∈R）と書ける。このとき、補題１の条件
【００６８】
【数６３】
である。したがって、１が証明された。
（証明終）
【００６９】
次に、最短距離が求められたときの多項式の算出方法を示す。εを最小距離とする。このとき、（−ｆ（α），−ｆ’（α））Ｔは、凸多角形のある辺上にある。この辺の端点をεＷ＾ｉとεＷ＾ｉ＋１とすると、
【００７０】
【数６４】
であり、（−ｆ（α），−ｆ’（α））ＴはεＷ＾ｉとεＷ＾ｉ＋１とを結ぶ辺上にあるから、ｔ（ただし、０≦ｔ≦１）が存在して、
【００７１】
【数６５】
と書ける。ν（ｋ）＝ｉとなるｋをとると、式（１０）のＬ（ｊ），Ｒ（ｊ）の作り方より、
【００７２】
【数６６】
どちらの符号を取るかは、式（５）で決まる。
次に、ｊ∈Ｐ（ｉ）になるｊについて考察する。
【００７３】
【数６７】
なお、μは、１つだけ符号が異なる番号ｊである。μ以外のｊについてはａ〜ｊ＝±εとし、番号μについては、
【００７４】
【数６８】
は、αを実重複零点として持ち、しかも、μとは異なるｊについてはｅ〜ｊの係数がεあるいは−εである。なお、符号は式（５）から決定できる。さらに、−１≦ｓ≦１であることに注意すれば、ｇ＾は条件を満たす多項式であることが分かる。
【００７５】
次に、凸多角形が線分に退化している場合について説明する。この場合は、補題１より、
【００７６】
【数６９】
が成立する。ただし、±の符号は、補題１で等号が成立するものを取る。このように取った符号に対して、
【００７７】
【数７０】
とすれば、多項式ｇ（ｘ）が求められる。
【実施例１】
【００７８】
本発明の距離算出装置の機能構成例を図１に示す。距離算出装置１０は、実数全体の集合をＲ、ａ１，ａ２，…，ａｎをそれぞれあらかじめ与えられた実数、ｅ１（ｘ），…，ｅｎ（ｘ）をそれぞれあらかじめ与えられた一変数実多項式、一変数実多項式ｆ（ｘ）が実閉区間Ｉに実重複零点を持たないとして、一変数実多項式の集合
【００７９】
【数７１】
のうち、実閉区間Ｉに実重複零点を持ち、かつ、一変数実多項式f（ｘ）にｌ∞−ノルムで計算して最も近い一変数実多項式ｆ〜（ｘ）について、一変数実多項式ｆ（ｘ）と一変数実多項式ｆ〜（ｘ）との距離を算出する。距離算出装置１０は、少なくとも、記録部１９０、多項式判定部１５０、第１計算部２００、第２計算部３００を備える。入力部１００は記録部１９０に情報を入力するための構成部であるが、距離算出装置１０の外部であらかじめ記録された情報を記録部１９０が有する場合には不要である。出力部４００は、第１計算部２００や第２計算部３００の計算結果を出力する構成部であるが、第１計算部２００や第２計算部３００の計算結果を記録部１９０に記録させ、距離算出装置１０の外部に取り出す場合には不要である。
【００８０】
図２に第１計算部の機能構成例、図３に第２計算部の機能構成例を示す。また、図４に距離算出装置１０の処理フロー、図５に第１計算部の処理フロー、図６に第２計算部の処理フローを示す。
【００８１】
記録部１９０は、入力部１００などを介して、ａ１，ａ２，…，ａｎと、ｆ（ｘ），ｅ１（ｘ），…，ｅｎ（ｘ）と、実閉区間Ｉとを記録する（Ｓ１００）。多項式判定部１５０は、ｎ＝１かｎ＞１かを判定する（Ｓ１５０）。第１計算部２００は、ｎ＞１のときに一変数実多項式ｆ（ｘ）と一変数実多項式ｆ〜（ｘ）との距離を算出する（Ｓ２００）。第２計算部３００は、ｎ＝１のときに一変数実多項式ｆ（ｘ）と一変数実多項式ｆ〜（ｘ）との距離を算出する（Ｓ３００）。出力部４００は、算出された距離を出力する（Ｓ４００）。
【００８２】
第１計算部２００の詳細な構成と処理フローは以下のとおりである。第１計算部２００は、Δ、Δ〜、Ｚ〜、Ｚ計算手段２１０、Δ＼Ｚ〜、Ｊ＼Ｚ計算手段２２０、φｊ（σ）計算手段２３０、Φ（σ）計算手段２４０、実閉区間確認手段２５０、ｍ計算手段２６０、ｍ決定手段２７０を有する。Δ、Δ〜、Ｚ〜、Ｚ計算手段２１０は、
【００８３】
【数７２】
を求める（Ｓ２１０）。なお、集合Ｚを求めるときの和集合をとる際には、
【００８４】
【数７３】
が恒等的に０になる集合は除く。
【００８５】
Δ＼Ｚ〜、Ｊ＼Ｚ計算手段２２０は、集合Δ＼Ｚ〜と集合Ｊ＼Ｚを求める（Ｓ２２０）。φｊ（σ）計算手段２３０は、
【００８６】
【数７４】
ただし、σ∈Ｉ＼Δ、ｊ＝１，…，ｎ
を求める（Ｓ２３０）。
Φ（σ）計算手段２４０は、
【００８７】
【数７５】
を求める（Ｓ２４０）。なお、
【００８８】
【数７６】
の符号が集合Ｊ＼Ｚの各区間で不変なので、φｊ（σ）はσの有理関数である。また、集合Ｚは有限集合だから、集合Ｊ＼Ｚは有限個の区間の和集合である。したがって、例えば、集合Ｊ＼Ｚを有限個の区間Ｊｊの和集合で書き、以下のアルゴリズムを｛φ１（σ），…，φｎ（σ）｝と各Ｊｊに適用すると、Φ（σ）を集合Ｊ＼Ｚ上の区分的な有理関数として得ることができる。
【００８９】
アルゴリズム１（ｍａｘ｛φ１（σ），…，φｎ（σ）｝の計算）
入力を有理関数の集合Ｓ＝｛φ１（σ），…，φｎ（σ）｝と実区間Ｉ（ただし、φｊ（σ）の極はＩには存在しない）とする。
（ｉ）Ｓ＝｛φ１（σ）｝のとき、｛（Ｉ，φ１（σ））｝を出力して終了する。Ｓ≠｛φ１（σ）｝の場合は、ＳをＴ個に分割し、ｍａｘＳｔ（ただし、ｔ＝１，…，Ｔ）を
【００９０】
【数７７】
の形で得る。ただし、ｑｔはｍａｘＳｔを表現するために実区間Ｉを分割した数である。分割は、ｍａｘＳｔが容易に得られるところまで行えばよい。例えば、Ｔ＝ｎとすれば必ずｍａｘＳｔが得られる。
（ｉｉ）実区間Ｉでφ〜１＋２（σ）＝ｍａｘ｛φ〜１（σ），φ〜２（σ）｝を次のように計算して、
【００９１】
【数７８】
を得る。ただし、ｐ１，ｐ２はｍａｘＳ１，ｍａｘＳ２を表現するために実区間Ｉを分割した数、ｐ１＋２はｍａｘ｛Ｓ１，Ｓ２｝を表現するために実区間Ｉを分割した数である。まず、Ｉ１，ｊ∩Ｉ２，ｋ≠０となる区間の対を取る。このような対は高々ｐ１＋ｐ２−１存在するので、ｍａｘ｛φ〜１（σ），φ〜２（σ）｝を各対の共通部分で計算する。空でない区間Ｉ１，ｊ∩Ｉ２，ｋ≠０の下限をａ、上限をｂとする。なお、ａは−∞、ｂは∞となることもある。区間（ａ，ｂ）内にあるφθ１（ｊ）（σ）＝φθ２（ｊ）（σ）の解σ１＜…＜σＱを求める。そして、
ａ＜τ１＜σ１＜τ２＜…＜τＱ＜σＱ＜τＱ＋１＜ｂ
となるτ１，…，τＱ＋１を求め、φθ１（ｊ）（τｑ）とφθ２（ｊ）（τｑ）の大小関係を求め、
【００９２】
【数７９】
を求める。
（ｉｉｉ）（ｉｉ）の処理をＴ−１回繰り返すことで、（ｉ）でＴ個に分割された集合Ｓｔを統合することができ、ｍａｘ｛φ１（σ），…，φｎ（σ）｝を
【００９３】
【数８０】
の形で得ることができる。ただし、ｐはｍａｘＳを表現するために実区間Ｉを分割した数である。
【００９４】
実閉区間確認手段２５０は、実閉区間Ｉが一点かを確認する（Ｓ２５０）。実閉区間Ｉが一点でない場合には、ｍ計算手段２６０は、
【００９５】
【数８１】
を計算する（Ｓ２６０）。そして、ｍ決定手段２７０は、距離ｍ＝ｍｉｎ｛ｍ１，…，ｍ４｝とする（Ｓ２７０）。実閉区間Ｉが一点の場合には、ｍ決定手段２７０が、距離ｍ＝Φ（σ）とする。
【００９６】
第２計算部３００の詳細な構成と処理フローは以下のとおりである。第２計算部３００は、連立方程式生成手段３１０、恒等性確認手段３２０、多項式生成手段３３０、距離計算手段３４０、距離選定手段３５０、ゼロ多項式用距離計算手段３４５を有する。連立方程式生成手段３１０は、
【００９７】
【数８２】
を生成する（Ｓ３１０）。恒等性確認手段３２０は、ｆ(ｘ)ｅ’１（ｘ）−ｆ’（ｘ）ｅ１（ｘ）が恒等的に０かを確認する（Ｓ３２０）。ｆ(ｘ)ｅ’１（ｘ）−ｆ’（ｘ）ｅ１（ｘ）が恒等的に０ではない場合には、多項式生成手段３３０は、ｆ(ｘ)ｅ’１（ｘ）−ｆ’（ｘ）ｅ１（ｘ）＝０を満たす有限個のｔ１を求め、すべてのｔ１に対する多項式ｆ(ｘ)＋ｔ１ｅ１（ｘ）を生成する（Ｓ３３０）。そして、距離計算手段３４０は、ｌ∞−ノルムによって多項式生成手段３３０が生成した各多項式と多項式ｆ（ｘ）との距離を計算する（Ｓ３４０）。距離選定手段３５０は、距離計算手段３４０が計算した距離の中で最小の距離を選定する（Ｓ３５０）。ｆ(ｘ)ｅ’１（ｘ）−ｆ’（ｘ）ｅ１（ｘ）が恒等的に０の場合には、ゼロ多項式用距離計算手段３４５は、ｌ∞−ノルムによってゼロ多項式と多項式ｆ（ｘ）との距離を計算する（Ｓ３４５）。
［計算量の解析］
まず、アルゴリズム１の計算量を解析する。この解析に必要な定義を次に示す。
定義１（Davenport-Schinzel列）
Σｎ＝｛ａ１，ａ２，…，ａｎ｝とし、Ｌｎ，ｓをアルファベットΣｎ上の文字列の集合で、ａｉａｉおよびξｓｉｊ（ただし、ｉ≠ｊ）を部分列として含まないのもとする。ここで、ξｓｉｊは以下で定義される長さｓ＋２の文字列である。
【００９８】
ξ１ｉｊ＝ａｉａｊａｉ， ξ２ｐｉｊ＝ξ２ｐ−１ｉｊａｊ， ξ２ｐ＋１ｉｊ＝ξ２ｐｉｊａｉ （１≦ｐ）
λ（ｎ，ｓ）をｍａｘ｛｜σ｜｜σ∈Ｌｎ，ｓ｝で定義し、Ｌｎ，ｓに属する列を（ｎ，ｓ）Davenport-Schinzel列という。
【００９９】
次の補題は、文献（M. J. Atallah, “Some dynamic computational geometry problems,” Computers and Mathematics with Applications, Vol.11, No.12, pp.1171-1181, 1985.）のLemma 2.4と本質的に同じものであり、アルゴリズム１とDavenport-Schinzel列との関係を示すものである。
補題２
ｆ１（ｔ），…，ｆｎ（ｔ）を実変数を取るｔ∈Ｉ⊂Ｒの関数かつ、連続なものとする。異なる２つのｆｉ（ｔ）とｆｊ（ｔ）を任意に取ったとき、ｆｉ（ｔ）とｆｊ（ｔ）が高々ｓ回しか交わらないとすると、
ｈ（ｔ）＝ｍａｘ｛ｆ１（ｔ），…，ｆｎ（ｔ）｝
は、Ｉを高々λ（ｎ，ｓ）個の区間に細分することにより、各細分上でｆ１（ｔ），…，ｆｎ（ｔ）のいずれかと等しいようにできる。ここで、λ（ｎ，ｓ）という値はこれ以上小さくはできない。
【０１００】
δを、アルゴリズム１において、φ１（σ），…，φｎ（σ）の分母分子の次数の最大値とする。すると、φｊ（σ）とφｋ（σ）（ただし、ｊ≠ｋ）は、Ｉにおいて高々２δ回しか交わらない。よって、ｍａｘ｛φ〜１（σ），φ〜２（σ）｝を計算するために、（ｉｉ）においてφｊ（σ）＝φｋ（σ）という方程式を解く回数は、高々
【０１０１】
【数８３】
である。よって、ｍａｘ｛φ１（σ），…，φｎ（σ）｝を計算するためにφｊ（σ）＝φｋ（σ）という方程式を解く回数は、高々
【０１０２】
【数８４】
となる。式（１３）の値を評価するために次の補題を用いる。
補題３
任意の正の自然数ｍに対し、ｍλ（ｎ，ｓ）≦λ（ｍｎ，ｓ）が成立する。
証明
σ１，…，σｍを、アルファベットΣｎ，Σ２ｎ＼Σｎ，…，Σｍｎ＼Σ（ｍ−１）ｎ上の（ｎ，ｓ）Davenport-Schinzel列とする。このときσ１，…，σｍは、Σｍｎ上の（ｍｎ，ｓ）Davenport-Schinzel列で長さがｍλ（ｎ，ｓ）であるから、補題の不等式は成り立つ。
（証明終）
【０１０３】
補題３より、
【数８５】
となる。λ（ｎ，ｓ）はｎとｓについて、多項式オーダである。例えば、
λ（ｎ，ｓ）≦ｓｎ（ｎ−１）＋１
という評価が、文献（H. Davenportand A. Schinzel, “A combinatorial problem concerned with differential equations,” American Journal of Mathematics, Vol.87, No.3, pp.684-694, 1965.）で与えられている。
【０１０４】
次に、図５に示した第１計算部２００の処理フロー（Ｓ２００）の計算量を解析する。ｄ＝ｍａｘ｛ｄｅｇ（ｆ），ｄｅｇ（ｅ１），…，ｄｅｇ（ｅｎ）｝とすると、
【０１０５】
【数８６】
の次数は高々２ｄである。解く必要のある方程式の数は以下の通りである。
【０１０６】
Δ、Δ〜、Ｚ〜、Ｚ計算手段２１０が、Δ、Δ〜、Ｚ〜、Ｚを計算するためには、それぞれ１つの方程式を解けばよい。Δ、Δ〜、Ｚ〜、Ｚに対する方程式の次数は高々、
２ｄ， ２ｄ， ２ｄ， ｎ（ｎ＋１）ｄ
である。
Ｊ＼Ｚ上でΦ（σ）を計算するために必要な解くべき方程式の数と次数は、高々、
【０１０７】
【数８７】
である。Ｊ＼Ｚは、高々ｎ（ｎ＋１）ｄ＋２ｄ＋１個の区間の和集合として書けることに注意されたい。Φ（σ）を計算するために、各区間上で解く必要のある方程式の数は、
【０１０８】
【数８８】
である。
【０１０９】
ｍ１，ｍ２を計算するために比較が必要な値は、高々、
２ｄ， ｎ（ｎ＋１）ｄ
である。
【０１１０】
Δ〜＼Ｚ〜は、高々２ｄ個の区間（一点に退化したものを含む）の和として書ける。ｍ３を、Δ〜＼Ｚ〜の一点に退化していない区間上で計算するためには、Φ’（σ）＝０を解く必要がある。Φ（σ）の分母分子の次数は高々２ｄだから、Φ’（σ）の分子の次数は、高々、
４ｄ−１
である。
【０１１１】
ｍ４を計算するためには、Φ’（σ）＝０を、Ｊ＼Ｚの各区間上で解く必要がある。Φ（σ）の分母分子の次数は高々２ｄだから、Φ’（σ）の分子の次数は、高々、
４ｄ−１
である。
以上より、解く必要のある方程式の数、その次数は、ｎ、ｄの多項式オーダであることが分かる。
【０１１２】
したがって、本発明の距離算出装置によれば、解く必要のある方程式の数、その次数をｎ、ｄ＝ｍａｘ｛ｄｅｇ（ｆ(ｘ)），ｄｅｇ（ｅ１（ｘ）），…，ｄｅｇ（ｅｎ（ｘ））｝の多項式オーダにできる。
［具体例］
以下に、ｆ(ｘ)＝ｘ３＋１とし、Ｉ＝Ｒに重複零点を持ちｆ（ｘ）に一番近い多項式
ｆ〜（ｘ）＝ｆ(ｘ)＋ａ〜１ｅ１（ｘ）＋ａ〜２ｅ２（ｘ）＋ａ〜３ｅ３（ｘ）
ただし、ａ〜１，ａ〜２，ａ〜３∈Ｒ、ｅ１（ｘ）＝ｘ３、ｅ２（ｘ）＝ｘ２、ｅ３（ｘ）＝ｘ
を距離算出装置１０を用いて求める場合を示す。
【０１１３】
ｆ(ｘ)＝ｘ３＋１、ｅ１（ｘ）＝ｘ３、ｅ２（ｘ）＝ｘ２、ｅ３（ｘ）＝ｘと実閉区間Ｉが記録部１９０に記録される（Ｓ１００）。多項式判定部１５０は、ｎ＝３であるから、ｎ＞１と判定する（Ｓ１５０）。したがって、第１計算部２００が、一変数実多項式ｆ（ｘ）と一変数実多項式ｆ〜（ｘ）との距離を算出する（Ｓ２００）。
第１計算部２００では、Δ、Δ〜、Ｚ〜、Ｚ計算手段２１０が、
【０１１４】
【数８９】
を計算し、
【０１１５】
【数９０】
を求める（Ｓ２１０）。
【０１１６】
Δ＼Ｚ〜、Ｊ＼Ｚ計算手段２２０は、Ｊ＝Ｉ＼Δ＝（−∞，０）∪（０，∞）を求め、
【０１１７】
【数９１】
を求める（Ｓ２２０）。
φｊ（σ）計算手段２３０は、
【０１１８】
【数９２】
を求める（Ｓ２３０）。
【０１１９】
Φ（σ）計算手段２４０は、次のような手順でΦ（σ）を求める。まず、集合ＺでのΦ（σ）を求めると、
【０１２０】
【数９３】
となる。次に、集合Ｊ＼ＺでのΦ（σ）を、アルゴリズム１を用いて計算する。
【０１２１】
Ｓ＝｛φ１（σ），φ２（σ），φ３（σ）｝であるから、３個に分割し、Ｓ１＝｛φ１（σ）｝、Ｓ２＝｛φ２（σ）｝、Ｓ３＝｛φ３（σ）｝とする。このとき、ｍａｘＳ１＝φ１（σ）（σ∈Ｉ）、ｍａｘＳ２＝φ２（σ）（σ∈Ｉ）、ｍａｘＳ３＝φ３（σ）（σ∈Ｉ）である（アルゴリズム１の（ｉ）に相当）。
【０１２２】
集合Ｊ＼Ｚについて、アルゴリズム１の（ｉｉ）（ｉｉｉ）を行うと次のようになる。
（−∞，０）においては、
【０１２３】
【数９４】
である。φ２（σ）−φ１（σ）の分子σ４−２σ３−３σ２−２σ＋１は、負の実零点を持たないから、φ１（σ）＜φ２（σ）が常に成り立つ。なお、多項式の大小関係は、アルゴリズム１の（ｉｉ）に示したように範囲内から適宜τ１を選び、φ１（τ１）とφ２（τ１）を比較すればよい。例えば、（−∞，０）の範囲である−１を選ぶと、φ２（−１）−φ１（−１）＝３＞０となる。したがって、φ１（σ）＜φ２（σ）であることが分かる。多項式間の大小関係の比較はどれも同じようにすればよいので、以下の多項式間の大小関係の比較ではこの説明は省略する。このようにして、
ｍａｘ｛Ｓ１，Ｓ２｝＝φ２（σ）（σ∈（−∞，０））
が求められる。
【０１２４】
φ３（σ）−φ２（σ）の分子σ４＋２σ３＋３σ２−２σ−１の負の実零点は１つあり、α１＝−０．３５０９１・・・である。したがって、（−∞，α１）ではφ２（σ）＜φ３（σ）、α１ではφ２（σ）＝φ３（σ）、（α１，０）ではφ２（σ）＞φ３（σ）が成り立つ。
【０１２５】
このようにして、ｍａｘ｛ｍａｘ｛Ｓ１，Ｓ２｝，Ｓ３｝、つまりｍａｘＳを求めることができ、
【０１２６】
【数９５】
となる（範囲（−∞，０）に対するアルゴリズム１の（ｉｉ）（ｉｉｉ）に相当）。
【０１２７】
【数９６】
である。φ２（σ）−φ１（σ）の分子−σ４−２σ３−３σ２＋２σ＋１は、この区間に１つの実零点α２＝０．７００５９・・・を持つ。そして、（０，α２）ではφ１（σ）＜φ２（σ）、α２ではφ１（σ）＝φ２（σ）、（α２，（１／２）１／３）ではφ１（σ）＞φ２（σ）が成り立つ。
【０１２８】
φ３（σ）−φ２（σ）の分子σ４−２σ３−３σ２−２σ＋１の（０，α２］の範囲にある零点は、α３＝０．３１９４８・・・のみである。そして、（０，α３）ではφ２（σ）＜φ３（σ）、α３ではφ２（σ）＝φ３（σ）、（α３，α２］ではφ２（σ）＞φ３（σ）が成り立つ。
【０１２９】
また、φ３（σ）−φ１（σ）の分子−２σ４−４σ３−６σ２−２σ＋２は、（α２，（１／２）１／３）の範囲では零点を持たず、この範囲全体でφ１（σ）＞φ３（σ）が成り立つ。よって、
【０１３０】
【数９７】
である（範囲（０，（１／２）１／３）に対するアルゴリズム１の（ｉｉ）（ｉｉｉ）に相当）。
【０１３１】
【数９８】
である。φ２（σ）−φ１（σ）の分子−σ４−２σ３−３σ２＋２σ＋１は、（（１／２）１／３，２１／３）の範囲に実零点を持たず、φ１（σ）＞φ２（σ）が成り立つ。
【０１３２】
φ３（σ）−φ１（σ）の分子２σ４＋４σ３−６σ２−４σ−２は、（（１／２）１／３，２１／３）の範囲に実零点を持たず、φ１（σ）＞φ３（σ）が成り立つ。よって、
【０１３３】
【数９９】
である（範囲（（１／２）１／３，２１／３）に対するアルゴリズム１の（ｉｉ）（ｉｉｉ）に相当）。
【０１３４】
【数１００】
である。φ２（σ）−φ１（σ）の分子σ４＋２σ３−３σ２−２σ−７は、（２１／３，∞）の範囲に実零点α４＝１．７３４７６・・・を持つ。そして、（２１／３，α４）ではφ１（σ）＞φ２（σ）、α４ではφ１（σ）＝φ２（σ）、（α４，∞）ではφ１（σ）＜φ２（σ）が成り立つ。
【０１３５】
φ３（σ）−φ１（σ）の分子２σ４＋４σ３−６σ２−４σ−２は、（２１／３，α４］の範囲に実零点α５＝１．４２７３５・・・を持つ。そして、（２１／３，α５）ではφ１（σ）＞φ３（σ）、α５ではφ１（σ）＝φ３（σ）、（α５，α４］ではφ１（σ）＜φ３（σ）が成り立つ。
【０１３６】
φ３（σ）−φ２（σ）の分子−σ４＋２σ３＋３σ２＋２σ−１の（α４，∞）の範囲にある零点は、α６＝３．１３０００・・・である。そして、（α４，α６）ではφ２（σ）＜φ３（σ）、α６ではφ２（σ）＝φ３（σ）、（α３，∞）ではφ２（σ）＞φ３（σ）が成り立つ。よって、
【０１３７】
【数１０１】
である（範囲（（２１／３，∞）に対するアルゴリズム１の（ｉｉ）（ｉｉｉ）に相当）。
以上をまとめると、集合Ｊ＼ＺでのΦ（σ）は、
【０１３８】
【数１０２】
となる（Ｓ２４０）。
【０１３９】
実閉区間確認手段２５０は、実閉区間Ｉが一点かを確認する（Ｓ２５０）。この例では実閉区間Ｉは一点ではないので、ｍ計算手段２６０は、ｍ１，…，ｍ４を次のように計算する（Ｓ２６０）。
【０１４０】
【数１０３】
である。ｍ４は次のように求める。Φ（σ）を微分すると
【０１４１】
【数１０４】
となる。
（−∞，α１］において、φ３’（σ）の分母は常に負である。φ３’（σ）の分子−２σ３＋６σ−２はβ＝−１．８７９３８・・・においてのみ零点を持ち、（−∞，β）において正、（β，α１）において負である。したがって、Φ（σ）は、（−∞，β）において単調減少、（β，α１）において単調増加である。また、（α１，０）においては、φ２’（σ）の分母は常に正である。φ２’（σ）の分子２σ３＋６σ２＋２は零点を持たず常に正である。したがって、Φ（σ）は、（α１，０）において単調増加である。同様にΦ（σ）を調べていくと、Φ（σ）は（０，（１／２）１／３）∪（（１／２）１／３，２１／３）∪（２１／３，α５）で単調減少、［α５，∞）で単調増加である。したがって、集合Ｊ＼ＺにおけるΦ（σ）の最小値ｍ４は
ｍ４＝ｍｉｎ｛Φ（β），Φ（α５）｝
＝ｍｉｎ｛０．８４９３５・・・，０．６１３２４・・・｝
＝０．６１３２４・・・
である。
【０１４２】
ｍ決定手段２７０は、
ｍ＝ｍｉｎ｛ｍ１，…，ｍ４｝＝ｍ４＝０．６１３２４・・・
を計算して、最小距離０．６１３２４・・・を求める（Ｓ２７０）。
【０１４３】
出力部４００は、第１計算部２００の計算結果である最小距離０．６１３２４・・・を出力する（Ｓ４００）。
【０１４４】
なお、上述の説明では、説明を簡単にするために区間Ｉの端点、多項式の係数は有理数としたが、実施例に示した計算では四則演算と等号判定が実行できれば十分なので、例えば実代数的数（整数係数一次代数方程式の根となる実数）としてもよい。
【実施例２】
【０１４５】
実施例１では距離算出装置と距離算出方法を示したが、同様の技術で多項式算出装置や多項式算出方法も提供できる。実施例２では、多項式算出装置と多項式算出方法について説明する。本発明の多項式算出装置の機能構成例も図１に示す。また、図２に第１計算部の機能構成例、図３に第２計算部の機能構成例を示す。また、図４に多項式算出装置２０の処理フロー、図５に第１計算部の処理フロー、図６に第２計算部の処理フローを示す。実線で示した構成部や処理ステップが距離算出装置１０と多項式算出装置２０に共通な構成部や処理ステップ、点線で示した構成部や処理ステップが多項式算出装置２０にのみ必要な構成部や処理ステップ、一点鎖線で示した構成部や処理ステップは距離算出装置１０にのみ必要な構成部や処理ステップである。
【０１４６】
多項式算出装置２０は、第１計算部と第２計算部とが、距離算出装置１０と異なる。多項式算出装置２０は、第１計算部２００’に、さらに多項式算出手段２８０を有し、第２計算部３００’は距離選定手段３５０とゼロ多項式用距離計算手段３４５の代わりに多項式選定手段３６０を有する。その他の構成は、第１計算部２００、第２計算部３００と同じである。多項式算出手段２８０は、ｍ決定手段２７０が求めた最短距離ｍを用いて、多項式
【０１４７】
【数１０５】
の中の１つまたは複数の情報を求める（Ｓ２８０）。なお、ｍ’の値、±の符号については、理論的説明で示した式（１１）（１２）（５）などにより定めることができる。多項式選定手段３６０は、ｆ(ｘ)ｅ’１（ｘ）−ｆ’（ｘ）ｅ１（ｘ）が恒等的に０ではない場合には、距離計算手段が計算した距離が最小となる多項式を選定し（Ｓ３６５）、ｆ(ｘ)ｅ’１（ｘ）−ｆ’（ｘ）ｅ１（ｘ）が恒等的に０の場合には、ゼロ多項式を選定する（Ｓ３６０）。そして、出力部４００は、算出された多項式の情報を出力する（Ｓ４００）。
【０１４８】
多項式算出装置２０は、このように距離算出装置１０と同じ技術によって多項式を算出するので、解く必要のある方程式の数、その次数をｎ、ｄ＝ｍａｘ｛ｄｅｇ（ｆ(ｘ)），ｄｅｇ（ｅ１（ｘ）），…，ｄｅｇ（ｅｎ（ｘ））｝の多項式オーダにできる。
【０１４９】
図７にコンピュータの機能構成例を示す。上述の実施例は、図７に示すコンピュータの記録部２０２０に、上記装置としてコンピュータを実行させるプログラムを読み込ませ、制御部２０１０、入力部２０３０、出力部２０４０などに動作させることで実施できる。また、コンピュータに読み込ませる方法としては、プログラムをコンピュータ読み取り可能な記録媒体に記録しておき、記録媒体からコンピュータに読み込ませる方法、サーバ等に記録されたプログラムを、電気通信回線等を通じてコンピュータに読み込ませる方法などがある。
【産業上の利用可能性】
【０１５０】
デジタル信号処理やシステム制御の分野において、実一変数多項式の零点の位置は、デジタルフィルタの周波数特性やシステムの性能に密接に関係する。デジタルフィルタの周波数特性やシステムの性能を設計する上で、ある実区間Ｉに所望の個数（ゼロ個の場合も含む）の実零点を持つように多項式の係数を設定したい場合を考える。多項式の係数は有限精度でしか指定できないので、必ず誤差を持つ。また、多項式の実重複零点は、どんなに小さな係数の変化に対しても、複数の複素零点あるいは実の近接零点となるので、実重複零点を持つ多項式が係数の誤差範囲に存在すれば、実区間Ｉの実零点の個数を制御できないことになる。したがって、設計によって求めた実一変数多項式が、実重複零点を持つ実一変数多項式とどの程度離れているのかは、デジタルフィルタの周波数特性やシステムの性能を設計する上で重要な問題である。
【０１５１】
本発明は、例えば、実閉区間Ｉに実重複零点を持たないように多項式の係数を設定したい場合に、係数設定に誤差を伴うことを前提として、誤差範囲内のどのような多項式であっても間違いなく実閉区間に実重複零点を持たないようにするときに、その誤差限界の確定などとして用いることができる。このような場合の一例として、デジタル信号処理におけるデジタルフィルタ（例えば、ＩＩＲ〔Infinite Impulse Response〕フィルタ）の設計などに有用である。
【図面の簡単な説明】
【０１５２】
【図１】本発明の距離算出装置および多項式算出装置の機能構成例を示す図。
【図２】第１計算部の機能構成例を示す図。
【図３】第２計算部の機能構成例を示す図。
【図４】本発明の距離算出装置および多項式算出装置の処理フローを示す図。
【図５】第１計算部の処理フローを示す図。
【図６】第２計算部の処理フローを示す図。
【図７】コンピュータの機能構成例を示す図。
【符号の説明】
【０１５３】
１０ 距離算出装置 ２０ 多項式算出装置
１００ 入力部 １５０ 多項式判定部
１９０ 記録部 ２００、２００’ 第１計算部
２１０ Δ、Δ〜、Ｚ〜、Ｚ計算手段 ２２０ Δ＼Ｚ〜、Ｊ＼Ｚ計算手段
２３０ φｊ（σ）計算手段 ２４０ Φ（σ）計算手段
２５０ 実閉区間確認手段 ２６０ ｍ計算手段
２７０ ｍ決定手段 ２８０ 多項式算出手段
３００、３００’ 第２計算部 ３１０ 連立方程式生成手段
３２０ 恒等性確認手段 ３３０ 多項式生成手段
３４０ 距離計算手段 ３４５ ゼロ多項式用距離計算手段
３５０ 距離選定手段 ３６０ 多項式選定手段
４００ 出力部
【技術分野】
【０００１】
本発明は、実数全体の集合内の指定された区間に実重複零点を持つ一変数実多項式のうち、上記区間に実重複零点を持たない或る一変数実多項式ｆに最も近い一変数実多項式ｆ~について、一変数実多項式ｆと一変数実多項式ｆ~との距離を求める技術、および一変数実多項式ｆ~を求める技術に関する。
【背景技術】
【０００２】
デジタル信号処理やシステム制御の分野において、実一変数多項式の零点の位置は、デジタルフィルタの周波数特性やシステムの性能に密接に関係する。デジタルフィルタの周波数特性やシステムの性能を設計する上で、ある実区間Ｉに所望の個数（ゼロ個の場合も含む）の実零点を持つように多項式の係数を設定したい場合を考える。多項式の係数は有限精度でしか指定できないので、必ず誤差を持つ。また、多項式の実重複零点は、どんなに小さな係数の変化に対しても、複数の複素零点あるいは実の近接零点となるので、実重複零点を持つ多項式が係数の誤差範囲に存在すれば、実区間Ｉの実零点の個数を制御できないことになる。したがって、設計によって求めた実一変数多項式が、実重複零点を持つ実一変数多項式とどの程度離れているのかは、デジタルフィルタの周波数特性やシステムの性能を設計する上で重要な問題である。なお、実閉区間Ｉは、Ｒ上の閉区間であって、ａ，ｂ∈Ｒとして、［ａ，ｂ］,（−∞,a］,［b，＋∞）,（−∞，＋∞）のいずれかで表現される。
【０００３】
ｆ（ｘ），ｅ１（ｘ），ｅ２（ｘ），…，ｅｎ（ｘ）は、それぞれあらかじめ与えられた一変数実多項式（係数が実数の一変数多項式）であるとする。ただし、実数全体の集合をＲと表記し、ｅ１（ｘ），ｅ２（ｘ），…，ｅｎ（ｘ）はＲ上一次独立とする。つまり、実数ｃ１，ｃ２，…，ｃｎに対して、ｃ１ｅ１（ｘ）＋ｃ２ｅ２（ｘ）＋・・・＋ｃｎｅｎ（ｘ）が恒等的に０となるのは、ｃ１＝ｃ２＝・・・＝ｃｎ＝０の場合に限られるとする。また、ａ１，ａ２，…，ａｎもあらかじめ与えられた実数とする。
【０００４】
２つの多項式間の距離を測る代表的な方法には、ｌ∞−ノルムとｌ２−ノルムとがある。ｌ∞−ノルムでの距離は、以下のように定義される。２つの一変数実多項式ｆ（ｘ）、ｇ（ｘ）を
【０００５】
【数２５】
とすると、距離ｄ（ｇ，ｈ）は、ｍａｘ｛｜ａ１−ｂ１｜，｜ａ２−ｂ２｜，…，｜ａｎ−ｂｎ｜｝で与えられる。
ｌ２−ノルムでの距離は、以下のように定義される。２つの一変数実多項式ｆ（ｘ）、ｇ（ｘ）を
【０００６】
【数２６】
とすると、距離ｄ（ｆ，ｇ）は、
【０００７】
【数２７】
で与えられる。
【０００８】
ある実区間Ｉに重複零点を持たないように多項式の係数を設定したい場合に、係数に誤差が含まれたとしても間違いなく実区間Ｉに重複零点を持たないようにできるかという問題を解決する必要がある。これと類似の問題を扱っている文献として、非特許文献１がある。非特許文献１では、ｌ２−ノルムを最小とする多項式を求める問題を、ある二次形式の最小化の問題に帰着して解決している。これは、本発明で扱う問題を似ているが、係数およびその誤差を複素数の範囲とする点、重複零点を実とは限らない点、多項式間の距離をｌ∞−ノルムではなくｌ２−ノルムで測っている点が異なり、本発明と似て非なるものである。
【０００９】
また、２つの多項式ｆ（ｘ）、ｇ（ｘ）の距離をｌ∞−ノルムで定義した文献としては、非特許文献２がある。
【非特許文献１】L. Zhi and W. Wu, "Nearest Singular Polynomials," Journal of Symbolic Computation, Vol.26, No.6, pp.667-675, 1998.
【非特許文献２】H.Sekigawa, "The Nearest Real Polynomial with a Real Multiple Zero in a Given Real Interval," Proc. Asian Symposium on Computer Mathematics (ASCM2007), 2007.
【発明の開示】
【発明が解決しようとする課題】
【００１０】
まず、非特許文献２の内容について説明する。実閉区間Ｉに重複零点を持ち、かつ、一変数実多項式f（ｘ）にｌ∞−ノルムで計算して最も近い一変数実多項式
【００１１】
【数２８】
について、以下の性質が成り立つ。
【００１２】
性質１
高々１つの例外の係数を除き、｜ｔｊ｜＝ｄ（ｆ，ｆ〜）が成り立つ。よって、以下の２つの場合に分けて問題を扱う。
（ｉ）すべてのｊに対して｜ｔｊ｜＝ｄ（ｆ，ｆ〜）が成り立つ場合
（ｉｉ）｜ｔμ｜＜｜ｔ１｜＝・・・＝｜ｔμ−１｜＝｜ｔμ＋１｜＝・・・＝｜ｔｎ｜となるμが存在する場合
（ｉ）の場合、ｘとｔｊに関する連立方程式
【００１３】
【数２９】
をｘ∈Ｉかつｔ１，…，ｔｎ∈Ｒという条件の下で解き、解の中で｜ｔ１｜＝・・・＝｜ｔｎ｜が最小となるものが最小距離であり、それに対応する多項式が｜ｆ（ｘ）−ｆ〜（ｘ）｜が最小となる多項式である。条件を満たす解がないとき、（ｉ）の場合には、Ｉに実重複零点を持つ多項式は存在しない。方程式（１）がｘ∈Ｉかつｔ１，…，ｔｎ∈Ｒという解を持つことは、以下のうち少なくとも一組の連立方程式がｘ∈Ｉかつｔ∈Ｒという解を持つことと同値である。
【００１４】
【数３０】
ここで、±は、＋と−のすべての組合せがあるので、組合せは２ｎ−１通りである。すなわち、最悪の場合、２ｎ−１の方程式を解く必要がある。（ｉｉ）の場合、｜ｔμ｜＝ｄ（ｆ，ｆ〜）であるから、
【００１５】
【数３１】
をｘ∈Ｉかつｔ１，…，ｔｎ∈Ｒという条件の下で解き、解の中で｜ｔ１｜＝・・・＝｜ｔμ−１｜＝｜ｔμ＋１｜＝・・・＝｜ｔｎ｜が最小となるものが最小距離、それに対応する多項式が｜ｆ（ｘ）−ｆ〜（ｘ）｜が最小となる多項式である。条件を満たす解がないとき、（ｉｉ）の場合には、Ｉに重複零点を持つ多項式が存在しない。方程式（２）がｘ∈Ｉかつｔ１，…，ｔｎ∈Ｒという解を持つということは、以下のうち少なくとも一組の連立方程式がｘ∈Ｉ，ｔμ，ｔ∈Ｒかつ｜ｔμ｜＜｜ｔ｜という解を持つことと同値である。
【００１６】
【数３２】
ここで、±は、＋と−のすべての組合せがあるので、組合せは２ｎ−２通りである。また、μの選び方がｎ通りある。すなわち、最悪の場合、２ｎ−２・ｎの方程式を解く必要がある。
【００１７】
このように、非特許文献２の方法では、最悪の場合、解く必要のある連立方程式の組の数がｅｊ（ｘ）の数の指数になる。したがって、ｅｊ（ｘ）の数が多い場合には現実的な方法ではない。
【００１８】
本発明の目的は、解く必要のある方程式の数がｅｊ（ｘ）の数の多項式オーダで収まる実閉区間Ｉに実重複零点を持ち、かつ、一変数実多項式f（ｘ）にｌ∞−ノルムで計算して最も近い一変数実多項式までの距離を求める方法を提供すること、および最も近い一変数実多項式を求める方法を提供することである。
【課題を解決するための手段】
【００１９】
本発明の距離算出装置は、実数全体の集合をＲとし、ａ１，ａ２，…，ａｎをそれぞれあらかじめ与えられた実数とし、ｅ１（ｘ），…，ｅｎ（ｘ）をそれぞれあらかじめ与えられた一変数実多項式とし、一変数実多項式ｆ（ｘ）が実閉区間Ｉに実重複零点を持たないとして、一変数実多項式の集合
【００２０】
【数３３】
のうち、実閉区間Ｉに実重複零点を持ち、かつ、一変数実多項式f（ｘ）にｌ∞−ノルムで計算して最も近い一変数実多項式ｆ〜（ｘ）について、一変数実多項式ｆ（ｘ）と一変数実多項式ｆ〜（ｘ）との距離を算出する距離算出装置であって、記録部、多項式判定部、第１計算部、第２計算部を備える。
【００２１】
記録部は、ａ１，ａ２，…，ａｎと、ｆ（ｘ），ｅ１（ｘ），…，ｅｎ（ｘ）と、実閉区間Ｉとを記録する。多項式判定部は、ｎ＝１かｎ＞１かを判定する。第１計算部は、ｎ＞１のときに一変数実多項式ｆ（ｘ）と一変数実多項式ｆ〜（ｘ）との距離を算出する。第２計算部は、ｎ＝１のときに一変数実多項式ｆ（ｘ）と一変数実多項式ｆ〜（ｘ）との距離を算出する。
【００２２】
第１計算部は、Δ、Δ〜、Ｚ〜、Ｚ計算手段、Δ＼Ｚ〜、Ｊ＼Ｚ計算手段、φｊ（σ）計算手段、Φ（σ）計算手段、実閉区間確認手段、ｍ計算手段、ｍ決定手段を有する。Δ、Δ〜、Ｚ〜、Ｚ計算手段は、
【００２３】
【数３４】
を求める。Δ＼Ｚ〜、Ｊ＼Ｚ計算手段は、集合Δ＼Ｚ〜と集合Ｊ＼Ｚを求める。φｊ（σ）計算手段は、
【００２４】
【数３５】
ただし、σ∈Ｉ＼Δ、ｊ＝１，…，ｎ
を求める。Φ（σ）計算手段は、
【００２５】
【数３６】
を求める。実閉区間確認手段は、実閉区間Ｉが一点かを確認する。ｍ計算手段は、実閉区間Ｉが一点でない場合に、
【００２６】
【数３７】
を計算する。ｍ決定手段は、実閉区間Ｉが一点でない場合にはｍ＝ｍｉｎ｛ｍ１，…，ｍ４｝とし、実閉区間Ｉが一点の場合にはｍ＝Φ（σ）のように距離ｍを決定する。
【００２７】
第２計算部は、連立方程式生成手段、恒等性確認手段、多項式生成手段、距離計算手段、距離選定手段、ゼロ多項式用距離計算手段を有する。連立方程式生成手段は、
【００２８】
【数３８】
を生成する。恒等性確認手段は、ｆ(ｘ)ｅ’１（ｘ）−ｆ’（ｘ）ｅ１（ｘ）が恒等的に０かを確認する。多項式生成手段は、ｆ(ｘ)ｅ’１（ｘ）−ｆ’（ｘ）ｅ１（ｘ）が恒等的に０ではない場合に、ｆ(ｘ)ｅ’１（ｘ）−ｆ’（ｘ）ｅ１（ｘ）＝０を満たす有限個のｔ１を求め、すべてのｔ１に対する多項式ｆ(ｘ)＋ｔ１ｅ１（ｘ）を生成する。距離計算手段は、ｆ(ｘ)ｅ’１（ｘ）−ｆ’（ｘ）ｅ１（ｘ）が恒等的に０ではない場合に、ｌ∞−ノルムによって多項式生成手段が生成した各多項式と多項式ｆ（ｘ）との距離を計算する。距離選定手段は、ｆ(ｘ)ｅ’１（ｘ）−ｆ’（ｘ）ｅ１（ｘ）が恒等的に０ではない場合に、距離計算手段が計算した距離の中で最小の距離を選定する。ゼロ多項式用距離計算手段は、ｆ(ｘ)ｅ’１（ｘ）−ｆ’（ｘ）ｅ１（ｘ）が恒等的に０の場合に、ｌ∞−ノルムによってゼロ多項式と多項式ｆ（ｘ）との距離を計算する。
【００２９】
本発明の多項式算出装置は、第１計算部にさらに多項式算出手段を有し、第２計算部は距離選定手段とゼロ多項式用距離計算手段の代わりに多項式選定手段を有する。多項式算出手段は、多項式
【００３０】
【数３９】
の中の１つまたは複数の情報を求める。多項式選定手段は、ｆ(ｘ)ｅ’１（ｘ）−ｆ’（ｘ）ｅ１（ｘ）が恒等的に０ではない場合には、距離計算手段が計算した距離が最小となる多項式を選定し、ｆ(ｘ)ｅ’１（ｘ）−ｆ’（ｘ）ｅ１（ｘ）が恒等的に０の場合には、ゼロ多項式を選定する。
【発明の効果】
【００３１】
本発明の距離算出装置および多項式算出装置はこのような構成なので、実閉区間Ｉに属する点σを零点とする多項式のうち、ｆ（ｘ）に最も近いものまでの距離を表す式Φ（σ）を導入し、その後にσをＩ上で動かしたときの距離の最小値を求めている。したがって、解く必要のある方程式の数、その次数をｎ、ｄ＝ｍａｘ｛ｄｅｇ（ｆ(ｘ)），ｄｅｇ（ｅ１（ｘ）），…，ｄｅｇ（ｅｎ（ｘ））｝の多項式オーダにできる。
【発明を実施するための最良の形態】
【００３２】
［理論的説明］
本発明では、実数全体の集合をＲ、ａ１，ａ２，…，ａｎをそれぞれあらかじめ与えられた実数、ｆ（ｘ），ｅ１（ｘ），…，ｅｎ（ｘ）をそれぞれあらかじめ与えられた一変数実多項式とし、ｅ１（ｘ），…，ｅｎ（ｘ）はＲ上一時独立とする。また、集合Ｆを
【００３３】
【数４０】
とする。Ｉはあらかじめ与えられた実閉区間とし、ｆ（ｘ）はＩに重複零点を持たないものとする。実閉区間Ｉが有界でないときには、集合Ｆに属する多項式の次数はｔｊによらず一定と仮定する。なお、重み付きのｌ∞−ノルムｍａｘｊ｛ｗｊ｜ａｊ｜｝（ただし、０＜ｗｊ）を用いる場合は、｛ｅ１（ｘ），…，ｅｎ（ｘ）｝の代わりに、｛ｅ１（ｘ）／ｗ１，…，ｅｎ（ｘ）／ｗｎ｝を用いればよい。
【００３４】
次の定理は、非特許文献２に示されている定理１（THEOREM1）である。
定理１
一変数実多項式ｆ（ｘ）と集合Ｆは上記の通り、距離ｄ（ｆ，ｇ）はｌ∞−ノルムでの距離、Ｉは実閉区間とする。もし、Ｉに重複零点を持つ多項式ｇ（ｘ）∈Ｆが存在するならば、Ｉに重複零点を持ち、かつ‖ｆ−ｆ〜‖∞が最小となるようなｆ〜（ｘ）∈Ｆが存在する。
【００３５】
次の定理は、定理１の「Ｉに重複零点を持つ多項式ｇ（ｘ）∈Ｆが存在」という条件が、ある場合は自動的に満たされることを示すものである。
定理２
一変数実多項式ｆ（ｘ）、ｅ１（ｘ），…，ｅｎ（ｘ）は上記の通りとし、Ｉは一点ではないとする。ｎ≧２のとき、集合Ｆに属する多項式でＩに重複零点を持つものが存在する。
証明
ｎ＝２の場合に証明すれば十分である。ｆ（ｘ）＋ｔ１ｅ１（ｘ）＋ｔ２ｅ２（ｘ）がｘ＝ｃにおいて重複零点を持つ必要十分条件は、連立方程式
【００３６】
【数４１】
がｘ＝ｃを解とすることである。ただし、ｆ’（ｘ）は、ｆ（ｘ）をｘで１回微分した多項式である。上記連立方程式をｔ１とｔ２に関する連立方程式（ｘはパラメータ）と見る。ｅ１（ｘ）とｅ２（ｘ）はＲ上一次独立だから、（ｅ１（ｘ），ｅ’１（ｘ））と（ｅ２（ｘ），ｅ’２（ｘ））もＲ上一次独立である。
【００３７】
よって、行列式ｅ１（ｘ）ｅ’２（ｘ）−ｅ’１（ｘ）ｅ２（ｘ）は多項式として０ではなく、これが０となるようなｘは有限個である。なぜならば、ｅ１（ｘ）ｅ’２（ｘ）−ｅ’１（ｘ）ｅ２（ｘ）が多項式として０と仮定すると、（後述するｎ＝１の場合と同じ議論で、）ある実数ａがあって、ｅ２（ｘ）＝ａｅ１（ｘ）と書けることになるが、これはｅ１（ｘ）とｅ２（ｘ）がＲ上一次独立であることに矛盾するからである。
【００３８】
よって、適当にｃを選べば、ｅ１（ｃ）ｅ’２（ｃ）−ｅ’１（ｃ）ｅ２（ｃ）≠０とできる。そのｃに対して上記連立方程式は解けて、ｔ１，ｔ２∈Ｒの値が決まる。
（証明終）
【００３９】
なお、Ｉが一点の場合は、後述の補題１により、最近多項式が存在するか否か判定できることに注意されたい。ｎ＝１の場合、ｆ（ｘ）＋ｔ１ｅ１（ｘ）（ｔ１∈Ｒ）がｘ＝ｃにおいて重複零点を持つ必要十分条件は、連立方程式
【００４０】
【数４２】
がｘ＝ｃを解とすることである。よって、行列式ｆ（ｃ）ｅ’１（ｃ）−ｆ’（ｃ）ｅ１（ｃ）は０となる。これは、ｓ０とｓ１についての連立方程式
【００４１】
【数４３】
が（ｓ０，ｓ１）＝（１，ｔ１）という（０，０）ではない解を持つことからいえる。
【００４２】
したがって、ｆ（ｘ）ｅ’１（ｘ）−ｆ’（ｘ）ｅ１（ｘ）が多項式として０でないときには、ｆ（ｘ）ｅ’１（ｘ）−ｆ’（ｘ）ｅ１（ｘ）＝０を解いて（根は有限個）、それらについて連立方程式（３）を満たすｔ１を求めればよい。なお、このときには、解がない場合もある。例えば、ｆ（ｘ）＝１、ｅ１（ｘ）＝ｘ２などである。また、解がある場合でも、この段階で候補が有限個となるので、直接一番近い多項式を求めることができる。
【００４３】
次に、ｆ（ｘ）ｅ’１（ｘ）−ｆ’（ｘ）ｅ１（ｘ）が多項式として０のときには、ｆ（ｘ）／ｅ１（ｘ）＝ｆ’（ｘ）／ｅ’１（ｘ）＝ｐ（ｘ）とおくことができ、
ｆ（ｘ）＝ｐ（ｘ）ｅ１（ｘ）
ｆ’（ｘ）＝ｐ（ｘ）ｅ’１（ｘ）
が成り立つ。一方、ｆ（ｘ）＝ｐ（ｘ）ｅ１（ｘ）の両辺を微分すると、
ｆ’（ｘ）＝ｐ’（ｘ）ｅ１（ｘ）＋ｐ（ｘ）ｅ’１（ｘ）
である。よって、有理関数として、ｐ’（ｘ）ｅ１（ｘ）＝０となるが、ｅ１（ｘ）は多項式として０ではないから、ｐ’（ｘ）が０となる。つまり、ｐ（ｘ）は定数となるので、ａとおくと、ｆ（ｘ）＝ａ・ｅ１（ｘ）と書ける。よって、連立方程式（３）は、
【００４４】
【数４４】
となる。解がｔ１＝−ａの場合、ｆ（ｘ）−ａ・ｅ１（ｘ）はゼロ多項式である。なお、解がｔ１≠−ａとすると、ｅ１（ｘ）＝ｅ’１（ｘ）＝０となる。このときｅ１（ｘ）がＩに実重複零点を持つことになり、ｆ（ｘ）＝ａ・ｅ１（ｘ）も実重複零点を持つことになってしまう。これは、ｆ（ｘ）がＩに実重複零点を持たないことに矛盾する。つまり、ｆ（ｘ）ｅ’１（ｘ）−ｆ’（ｘ）ｅ１（ｘ）が多項式として０のときには、ゼロ多項式が最近多項式である。
【００４５】
次の補題は、最小距離を算出する上で重要な役割を果たすものである。
補題１
ｆ（ｘ），ｅｊ（ｘ）はあらかじめ与えられた実係数一変数多項式とし、
【００４６】
【数４５】
とする。このとき、αを零点とするf〜∈Ｆεが存在する必要十分条件は以下のとおりである。
【００４７】
【数４６】
なお、本明細書中ではＦ^は、ベクトルを表現しており、Ｆは集合を表現していることに注意されたい。
証明
αを重複零点とするｇ∈Ｆεが存在する必要十分条件は、(0,0)が集合
{(h(α),h’(α))|h(x)∈Ｆε｝ (4)
に属することである。
【００４８】
【数４７】
とすると、上記の集合は以下のように書ける。
【００４９】
【数４８】
集合Ｖε（α）は凸多角形となる。これは文献（H.Sekigawa and K.Shirayanagi, "Locating Real Multiple Zeros of a Real Interval Polynomial Proc.," International Symposium on Symbolic and Algebraic Computation（ISSAC2006），pp.310-317, 2006.）のTHEOREM4に示されている。凸多角形の頂点は以下のように求めることができる。
【００５０】
【数４９】
よって、凸多角形
【００５１】
【数５０】
【００５２】
【数５１】
【００５３】
【数５２】
【００５４】
【数５３】
【００５５】
【数５４】
凸多角形が線分に退化した場合、すなわち、ｊ＝１，…，ｎに対して式（８）の右辺が０となる場合、不等式（９）が必要である。
【００５６】
（０，０）が集合（４）に属する必要十分条件は、−Ｆ＾（α）が凸多角形（６）に属することである。
【００５７】
【数５５】
以下の等式が成り立つことに注意されたい。
【００５８】
【数５６】
したがって、以下が成り立つ。
【００５９】
【数５７】
よって、以下の不等式が成り立つ。
【００６０】
【数５８】
最後に、以下の点に注意すれば証明が終わる。
【００６１】
【数５９】
（証明終）
【００６２】
以下の定理は補題１からしたがう。根号を避けるため、補題１で退化の場合の式を変形する。
定理３
【００６３】
【数６０】
ｆ（ｘ），ｅｊ（ｘ）はあらかじめ与えられた実係数一変数多項式とし、αはｆ（ｘ）の実重複零点ではないものとする。
【００６４】
１．１≦ｊ＜ｋ≦ｎに対して、A(E^j(α),E^j(α))=0が成立するとき、最近多項式が存在する必要十分条件は、A(E^j(α),F^(α))=0が、ｊ＝１，…，ｎにたいして成り立ち、さらに、E^j(α)≠(0,0)となるｊが存在することである。このときの距離は、
【００６５】
【数６１】
である。
【００６６】
２．あるｊ＜ｋに対して、A(E^j(α),E^j(α))≠0が成立するとき、最近多項式は存在する。最小距離は、
【００６７】
【数６２】
である。ただし、分母が０となるものは除く。
証明
２は、補題１からただちに従うので、１のみを証明する。(0,0)，E^1(α)，…，E^n(α)が一直線上にあり、最近多項式が存在する条件が満たされているとき、ｊ＝１，…，ｎに対し、E^j(α)＝αjF(α)（αj∈R）と書ける。このとき、補題１の条件
【００６８】
【数６３】
である。したがって、１が証明された。
（証明終）
【００６９】
次に、最短距離が求められたときの多項式の算出方法を示す。εを最小距離とする。このとき、（−ｆ（α），−ｆ’（α））Ｔは、凸多角形のある辺上にある。この辺の端点をεＷ＾ｉとεＷ＾ｉ＋１とすると、
【００７０】
【数６４】
であり、（−ｆ（α），−ｆ’（α））ＴはεＷ＾ｉとεＷ＾ｉ＋１とを結ぶ辺上にあるから、ｔ（ただし、０≦ｔ≦１）が存在して、
【００７１】
【数６５】
と書ける。ν（ｋ）＝ｉとなるｋをとると、式（１０）のＬ（ｊ），Ｒ（ｊ）の作り方より、
【００７２】
【数６６】
どちらの符号を取るかは、式（５）で決まる。
次に、ｊ∈Ｐ（ｉ）になるｊについて考察する。
【００７３】
【数６７】
なお、μは、１つだけ符号が異なる番号ｊである。μ以外のｊについてはａ〜ｊ＝±εとし、番号μについては、
【００７４】
【数６８】
は、αを実重複零点として持ち、しかも、μとは異なるｊについてはｅ〜ｊの係数がεあるいは−εである。なお、符号は式（５）から決定できる。さらに、−１≦ｓ≦１であることに注意すれば、ｇ＾は条件を満たす多項式であることが分かる。
【００７５】
次に、凸多角形が線分に退化している場合について説明する。この場合は、補題１より、
【００７６】
【数６９】
が成立する。ただし、±の符号は、補題１で等号が成立するものを取る。このように取った符号に対して、
【００７７】
【数７０】
とすれば、多項式ｇ（ｘ）が求められる。
【実施例１】
【００７８】
本発明の距離算出装置の機能構成例を図１に示す。距離算出装置１０は、実数全体の集合をＲ、ａ１，ａ２，…，ａｎをそれぞれあらかじめ与えられた実数、ｅ１（ｘ），…，ｅｎ（ｘ）をそれぞれあらかじめ与えられた一変数実多項式、一変数実多項式ｆ（ｘ）が実閉区間Ｉに実重複零点を持たないとして、一変数実多項式の集合
【００７９】
【数７１】
のうち、実閉区間Ｉに実重複零点を持ち、かつ、一変数実多項式f（ｘ）にｌ∞−ノルムで計算して最も近い一変数実多項式ｆ〜（ｘ）について、一変数実多項式ｆ（ｘ）と一変数実多項式ｆ〜（ｘ）との距離を算出する。距離算出装置１０は、少なくとも、記録部１９０、多項式判定部１５０、第１計算部２００、第２計算部３００を備える。入力部１００は記録部１９０に情報を入力するための構成部であるが、距離算出装置１０の外部であらかじめ記録された情報を記録部１９０が有する場合には不要である。出力部４００は、第１計算部２００や第２計算部３００の計算結果を出力する構成部であるが、第１計算部２００や第２計算部３００の計算結果を記録部１９０に記録させ、距離算出装置１０の外部に取り出す場合には不要である。
【００８０】
図２に第１計算部の機能構成例、図３に第２計算部の機能構成例を示す。また、図４に距離算出装置１０の処理フロー、図５に第１計算部の処理フロー、図６に第２計算部の処理フローを示す。
【００８１】
記録部１９０は、入力部１００などを介して、ａ１，ａ２，…，ａｎと、ｆ（ｘ），ｅ１（ｘ），…，ｅｎ（ｘ）と、実閉区間Ｉとを記録する（Ｓ１００）。多項式判定部１５０は、ｎ＝１かｎ＞１かを判定する（Ｓ１５０）。第１計算部２００は、ｎ＞１のときに一変数実多項式ｆ（ｘ）と一変数実多項式ｆ〜（ｘ）との距離を算出する（Ｓ２００）。第２計算部３００は、ｎ＝１のときに一変数実多項式ｆ（ｘ）と一変数実多項式ｆ〜（ｘ）との距離を算出する（Ｓ３００）。出力部４００は、算出された距離を出力する（Ｓ４００）。
【００８２】
第１計算部２００の詳細な構成と処理フローは以下のとおりである。第１計算部２００は、Δ、Δ〜、Ｚ〜、Ｚ計算手段２１０、Δ＼Ｚ〜、Ｊ＼Ｚ計算手段２２０、φｊ（σ）計算手段２３０、Φ（σ）計算手段２４０、実閉区間確認手段２５０、ｍ計算手段２６０、ｍ決定手段２７０を有する。Δ、Δ〜、Ｚ〜、Ｚ計算手段２１０は、
【００８３】
【数７２】
を求める（Ｓ２１０）。なお、集合Ｚを求めるときの和集合をとる際には、
【００８４】
【数７３】
が恒等的に０になる集合は除く。
【００８５】
Δ＼Ｚ〜、Ｊ＼Ｚ計算手段２２０は、集合Δ＼Ｚ〜と集合Ｊ＼Ｚを求める（Ｓ２２０）。φｊ（σ）計算手段２３０は、
【００８６】
【数７４】
ただし、σ∈Ｉ＼Δ、ｊ＝１，…，ｎ
を求める（Ｓ２３０）。
Φ（σ）計算手段２４０は、
【００８７】
【数７５】
を求める（Ｓ２４０）。なお、
【００８８】
【数７６】
の符号が集合Ｊ＼Ｚの各区間で不変なので、φｊ（σ）はσの有理関数である。また、集合Ｚは有限集合だから、集合Ｊ＼Ｚは有限個の区間の和集合である。したがって、例えば、集合Ｊ＼Ｚを有限個の区間Ｊｊの和集合で書き、以下のアルゴリズムを｛φ１（σ），…，φｎ（σ）｝と各Ｊｊに適用すると、Φ（σ）を集合Ｊ＼Ｚ上の区分的な有理関数として得ることができる。
【００８９】
アルゴリズム１（ｍａｘ｛φ１（σ），…，φｎ（σ）｝の計算）
入力を有理関数の集合Ｓ＝｛φ１（σ），…，φｎ（σ）｝と実区間Ｉ（ただし、φｊ（σ）の極はＩには存在しない）とする。
（ｉ）Ｓ＝｛φ１（σ）｝のとき、｛（Ｉ，φ１（σ））｝を出力して終了する。Ｓ≠｛φ１（σ）｝の場合は、ＳをＴ個に分割し、ｍａｘＳｔ（ただし、ｔ＝１，…，Ｔ）を
【００９０】
【数７７】
の形で得る。ただし、ｑｔはｍａｘＳｔを表現するために実区間Ｉを分割した数である。分割は、ｍａｘＳｔが容易に得られるところまで行えばよい。例えば、Ｔ＝ｎとすれば必ずｍａｘＳｔが得られる。
（ｉｉ）実区間Ｉでφ〜１＋２（σ）＝ｍａｘ｛φ〜１（σ），φ〜２（σ）｝を次のように計算して、
【００９１】
【数７８】
を得る。ただし、ｐ１，ｐ２はｍａｘＳ１，ｍａｘＳ２を表現するために実区間Ｉを分割した数、ｐ１＋２はｍａｘ｛Ｓ１，Ｓ２｝を表現するために実区間Ｉを分割した数である。まず、Ｉ１，ｊ∩Ｉ２，ｋ≠０となる区間の対を取る。このような対は高々ｐ１＋ｐ２−１存在するので、ｍａｘ｛φ〜１（σ），φ〜２（σ）｝を各対の共通部分で計算する。空でない区間Ｉ１，ｊ∩Ｉ２，ｋ≠０の下限をａ、上限をｂとする。なお、ａは−∞、ｂは∞となることもある。区間（ａ，ｂ）内にあるφθ１（ｊ）（σ）＝φθ２（ｊ）（σ）の解σ１＜…＜σＱを求める。そして、
ａ＜τ１＜σ１＜τ２＜…＜τＱ＜σＱ＜τＱ＋１＜ｂ
となるτ１，…，τＱ＋１を求め、φθ１（ｊ）（τｑ）とφθ２（ｊ）（τｑ）の大小関係を求め、
【００９２】
【数７９】
を求める。
（ｉｉｉ）（ｉｉ）の処理をＴ−１回繰り返すことで、（ｉ）でＴ個に分割された集合Ｓｔを統合することができ、ｍａｘ｛φ１（σ），…，φｎ（σ）｝を
【００９３】
【数８０】
の形で得ることができる。ただし、ｐはｍａｘＳを表現するために実区間Ｉを分割した数である。
【００９４】
実閉区間確認手段２５０は、実閉区間Ｉが一点かを確認する（Ｓ２５０）。実閉区間Ｉが一点でない場合には、ｍ計算手段２６０は、
【００９５】
【数８１】
を計算する（Ｓ２６０）。そして、ｍ決定手段２７０は、距離ｍ＝ｍｉｎ｛ｍ１，…，ｍ４｝とする（Ｓ２７０）。実閉区間Ｉが一点の場合には、ｍ決定手段２７０が、距離ｍ＝Φ（σ）とする。
【００９６】
第２計算部３００の詳細な構成と処理フローは以下のとおりである。第２計算部３００は、連立方程式生成手段３１０、恒等性確認手段３２０、多項式生成手段３３０、距離計算手段３４０、距離選定手段３５０、ゼロ多項式用距離計算手段３４５を有する。連立方程式生成手段３１０は、
【００９７】
【数８２】
を生成する（Ｓ３１０）。恒等性確認手段３２０は、ｆ(ｘ)ｅ’１（ｘ）−ｆ’（ｘ）ｅ１（ｘ）が恒等的に０かを確認する（Ｓ３２０）。ｆ(ｘ)ｅ’１（ｘ）−ｆ’（ｘ）ｅ１（ｘ）が恒等的に０ではない場合には、多項式生成手段３３０は、ｆ(ｘ)ｅ’１（ｘ）−ｆ’（ｘ）ｅ１（ｘ）＝０を満たす有限個のｔ１を求め、すべてのｔ１に対する多項式ｆ(ｘ)＋ｔ１ｅ１（ｘ）を生成する（Ｓ３３０）。そして、距離計算手段３４０は、ｌ∞−ノルムによって多項式生成手段３３０が生成した各多項式と多項式ｆ（ｘ）との距離を計算する（Ｓ３４０）。距離選定手段３５０は、距離計算手段３４０が計算した距離の中で最小の距離を選定する（Ｓ３５０）。ｆ(ｘ)ｅ’１（ｘ）−ｆ’（ｘ）ｅ１（ｘ）が恒等的に０の場合には、ゼロ多項式用距離計算手段３４５は、ｌ∞−ノルムによってゼロ多項式と多項式ｆ（ｘ）との距離を計算する（Ｓ３４５）。
［計算量の解析］
まず、アルゴリズム１の計算量を解析する。この解析に必要な定義を次に示す。
定義１（Davenport-Schinzel列）
Σｎ＝｛ａ１，ａ２，…，ａｎ｝とし、Ｌｎ，ｓをアルファベットΣｎ上の文字列の集合で、ａｉａｉおよびξｓｉｊ（ただし、ｉ≠ｊ）を部分列として含まないのもとする。ここで、ξｓｉｊは以下で定義される長さｓ＋２の文字列である。
【００９８】
ξ１ｉｊ＝ａｉａｊａｉ， ξ２ｐｉｊ＝ξ２ｐ−１ｉｊａｊ， ξ２ｐ＋１ｉｊ＝ξ２ｐｉｊａｉ （１≦ｐ）
λ（ｎ，ｓ）をｍａｘ｛｜σ｜｜σ∈Ｌｎ，ｓ｝で定義し、Ｌｎ，ｓに属する列を（ｎ，ｓ）Davenport-Schinzel列という。
【００９９】
次の補題は、文献（M. J. Atallah, “Some dynamic computational geometry problems,” Computers and Mathematics with Applications, Vol.11, No.12, pp.1171-1181, 1985.）のLemma 2.4と本質的に同じものであり、アルゴリズム１とDavenport-Schinzel列との関係を示すものである。
補題２
ｆ１（ｔ），…，ｆｎ（ｔ）を実変数を取るｔ∈Ｉ⊂Ｒの関数かつ、連続なものとする。異なる２つのｆｉ（ｔ）とｆｊ（ｔ）を任意に取ったとき、ｆｉ（ｔ）とｆｊ（ｔ）が高々ｓ回しか交わらないとすると、
ｈ（ｔ）＝ｍａｘ｛ｆ１（ｔ），…，ｆｎ（ｔ）｝
は、Ｉを高々λ（ｎ，ｓ）個の区間に細分することにより、各細分上でｆ１（ｔ），…，ｆｎ（ｔ）のいずれかと等しいようにできる。ここで、λ（ｎ，ｓ）という値はこれ以上小さくはできない。
【０１００】
δを、アルゴリズム１において、φ１（σ），…，φｎ（σ）の分母分子の次数の最大値とする。すると、φｊ（σ）とφｋ（σ）（ただし、ｊ≠ｋ）は、Ｉにおいて高々２δ回しか交わらない。よって、ｍａｘ｛φ〜１（σ），φ〜２（σ）｝を計算するために、（ｉｉ）においてφｊ（σ）＝φｋ（σ）という方程式を解く回数は、高々
【０１０１】
【数８３】
である。よって、ｍａｘ｛φ１（σ），…，φｎ（σ）｝を計算するためにφｊ（σ）＝φｋ（σ）という方程式を解く回数は、高々
【０１０２】
【数８４】
となる。式（１３）の値を評価するために次の補題を用いる。
補題３
任意の正の自然数ｍに対し、ｍλ（ｎ，ｓ）≦λ（ｍｎ，ｓ）が成立する。
証明
σ１，…，σｍを、アルファベットΣｎ，Σ２ｎ＼Σｎ，…，Σｍｎ＼Σ（ｍ−１）ｎ上の（ｎ，ｓ）Davenport-Schinzel列とする。このときσ１，…，σｍは、Σｍｎ上の（ｍｎ，ｓ）Davenport-Schinzel列で長さがｍλ（ｎ，ｓ）であるから、補題の不等式は成り立つ。
（証明終）
【０１０３】
補題３より、
【数８５】
となる。λ（ｎ，ｓ）はｎとｓについて、多項式オーダである。例えば、
λ（ｎ，ｓ）≦ｓｎ（ｎ−１）＋１
という評価が、文献（H. Davenportand A. Schinzel, “A combinatorial problem concerned with differential equations,” American Journal of Mathematics, Vol.87, No.3, pp.684-694, 1965.）で与えられている。
【０１０４】
次に、図５に示した第１計算部２００の処理フロー（Ｓ２００）の計算量を解析する。ｄ＝ｍａｘ｛ｄｅｇ（ｆ），ｄｅｇ（ｅ１），…，ｄｅｇ（ｅｎ）｝とすると、
【０１０５】
【数８６】
の次数は高々２ｄである。解く必要のある方程式の数は以下の通りである。
【０１０６】
Δ、Δ〜、Ｚ〜、Ｚ計算手段２１０が、Δ、Δ〜、Ｚ〜、Ｚを計算するためには、それぞれ１つの方程式を解けばよい。Δ、Δ〜、Ｚ〜、Ｚに対する方程式の次数は高々、
２ｄ， ２ｄ， ２ｄ， ｎ（ｎ＋１）ｄ
である。
Ｊ＼Ｚ上でΦ（σ）を計算するために必要な解くべき方程式の数と次数は、高々、
【０１０７】
【数８７】
である。Ｊ＼Ｚは、高々ｎ（ｎ＋１）ｄ＋２ｄ＋１個の区間の和集合として書けることに注意されたい。Φ（σ）を計算するために、各区間上で解く必要のある方程式の数は、
【０１０８】
【数８８】
である。
【０１０９】
ｍ１，ｍ２を計算するために比較が必要な値は、高々、
２ｄ， ｎ（ｎ＋１）ｄ
である。
【０１１０】
Δ〜＼Ｚ〜は、高々２ｄ個の区間（一点に退化したものを含む）の和として書ける。ｍ３を、Δ〜＼Ｚ〜の一点に退化していない区間上で計算するためには、Φ’（σ）＝０を解く必要がある。Φ（σ）の分母分子の次数は高々２ｄだから、Φ’（σ）の分子の次数は、高々、
４ｄ−１
である。
【０１１１】
ｍ４を計算するためには、Φ’（σ）＝０を、Ｊ＼Ｚの各区間上で解く必要がある。Φ（σ）の分母分子の次数は高々２ｄだから、Φ’（σ）の分子の次数は、高々、
４ｄ−１
である。
以上より、解く必要のある方程式の数、その次数は、ｎ、ｄの多項式オーダであることが分かる。
【０１１２】
したがって、本発明の距離算出装置によれば、解く必要のある方程式の数、その次数をｎ、ｄ＝ｍａｘ｛ｄｅｇ（ｆ(ｘ)），ｄｅｇ（ｅ１（ｘ）），…，ｄｅｇ（ｅｎ（ｘ））｝の多項式オーダにできる。
［具体例］
以下に、ｆ(ｘ)＝ｘ３＋１とし、Ｉ＝Ｒに重複零点を持ちｆ（ｘ）に一番近い多項式
ｆ〜（ｘ）＝ｆ(ｘ)＋ａ〜１ｅ１（ｘ）＋ａ〜２ｅ２（ｘ）＋ａ〜３ｅ３（ｘ）
ただし、ａ〜１，ａ〜２，ａ〜３∈Ｒ、ｅ１（ｘ）＝ｘ３、ｅ２（ｘ）＝ｘ２、ｅ３（ｘ）＝ｘ
を距離算出装置１０を用いて求める場合を示す。
【０１１３】
ｆ(ｘ)＝ｘ３＋１、ｅ１（ｘ）＝ｘ３、ｅ２（ｘ）＝ｘ２、ｅ３（ｘ）＝ｘと実閉区間Ｉが記録部１９０に記録される（Ｓ１００）。多項式判定部１５０は、ｎ＝３であるから、ｎ＞１と判定する（Ｓ１５０）。したがって、第１計算部２００が、一変数実多項式ｆ（ｘ）と一変数実多項式ｆ〜（ｘ）との距離を算出する（Ｓ２００）。
第１計算部２００では、Δ、Δ〜、Ｚ〜、Ｚ計算手段２１０が、
【０１１４】
【数８９】
を計算し、
【０１１５】
【数９０】
を求める（Ｓ２１０）。
【０１１６】
Δ＼Ｚ〜、Ｊ＼Ｚ計算手段２２０は、Ｊ＝Ｉ＼Δ＝（−∞，０）∪（０，∞）を求め、
【０１１７】
【数９１】
を求める（Ｓ２２０）。
φｊ（σ）計算手段２３０は、
【０１１８】
【数９２】
を求める（Ｓ２３０）。
【０１１９】
Φ（σ）計算手段２４０は、次のような手順でΦ（σ）を求める。まず、集合ＺでのΦ（σ）を求めると、
【０１２０】
【数９３】
となる。次に、集合Ｊ＼ＺでのΦ（σ）を、アルゴリズム１を用いて計算する。
【０１２１】
Ｓ＝｛φ１（σ），φ２（σ），φ３（σ）｝であるから、３個に分割し、Ｓ１＝｛φ１（σ）｝、Ｓ２＝｛φ２（σ）｝、Ｓ３＝｛φ３（σ）｝とする。このとき、ｍａｘＳ１＝φ１（σ）（σ∈Ｉ）、ｍａｘＳ２＝φ２（σ）（σ∈Ｉ）、ｍａｘＳ３＝φ３（σ）（σ∈Ｉ）である（アルゴリズム１の（ｉ）に相当）。
【０１２２】
集合Ｊ＼Ｚについて、アルゴリズム１の（ｉｉ）（ｉｉｉ）を行うと次のようになる。
（−∞，０）においては、
【０１２３】
【数９４】
である。φ２（σ）−φ１（σ）の分子σ４−２σ３−３σ２−２σ＋１は、負の実零点を持たないから、φ１（σ）＜φ２（σ）が常に成り立つ。なお、多項式の大小関係は、アルゴリズム１の（ｉｉ）に示したように範囲内から適宜τ１を選び、φ１（τ１）とφ２（τ１）を比較すればよい。例えば、（−∞，０）の範囲である−１を選ぶと、φ２（−１）−φ１（−１）＝３＞０となる。したがって、φ１（σ）＜φ２（σ）であることが分かる。多項式間の大小関係の比較はどれも同じようにすればよいので、以下の多項式間の大小関係の比較ではこの説明は省略する。このようにして、
ｍａｘ｛Ｓ１，Ｓ２｝＝φ２（σ）（σ∈（−∞，０））
が求められる。
【０１２４】
φ３（σ）−φ２（σ）の分子σ４＋２σ３＋３σ２−２σ−１の負の実零点は１つあり、α１＝−０．３５０９１・・・である。したがって、（−∞，α１）ではφ２（σ）＜φ３（σ）、α１ではφ２（σ）＝φ３（σ）、（α１，０）ではφ２（σ）＞φ３（σ）が成り立つ。
【０１２５】
このようにして、ｍａｘ｛ｍａｘ｛Ｓ１，Ｓ２｝，Ｓ３｝、つまりｍａｘＳを求めることができ、
【０１２６】
【数９５】
となる（範囲（−∞，０）に対するアルゴリズム１の（ｉｉ）（ｉｉｉ）に相当）。
【０１２７】
【数９６】
である。φ２（σ）−φ１（σ）の分子−σ４−２σ３−３σ２＋２σ＋１は、この区間に１つの実零点α２＝０．７００５９・・・を持つ。そして、（０，α２）ではφ１（σ）＜φ２（σ）、α２ではφ１（σ）＝φ２（σ）、（α２，（１／２）１／３）ではφ１（σ）＞φ２（σ）が成り立つ。
【０１２８】
φ３（σ）−φ２（σ）の分子σ４−２σ３−３σ２−２σ＋１の（０，α２］の範囲にある零点は、α３＝０．３１９４８・・・のみである。そして、（０，α３）ではφ２（σ）＜φ３（σ）、α３ではφ２（σ）＝φ３（σ）、（α３，α２］ではφ２（σ）＞φ３（σ）が成り立つ。
【０１２９】
また、φ３（σ）−φ１（σ）の分子−２σ４−４σ３−６σ２−２σ＋２は、（α２，（１／２）１／３）の範囲では零点を持たず、この範囲全体でφ１（σ）＞φ３（σ）が成り立つ。よって、
【０１３０】
【数９７】
である（範囲（０，（１／２）１／３）に対するアルゴリズム１の（ｉｉ）（ｉｉｉ）に相当）。
【０１３１】
【数９８】
である。φ２（σ）−φ１（σ）の分子−σ４−２σ３−３σ２＋２σ＋１は、（（１／２）１／３，２１／３）の範囲に実零点を持たず、φ１（σ）＞φ２（σ）が成り立つ。
【０１３２】
φ３（σ）−φ１（σ）の分子２σ４＋４σ３−６σ２−４σ−２は、（（１／２）１／３，２１／３）の範囲に実零点を持たず、φ１（σ）＞φ３（σ）が成り立つ。よって、
【０１３３】
【数９９】
である（範囲（（１／２）１／３，２１／３）に対するアルゴリズム１の（ｉｉ）（ｉｉｉ）に相当）。
【０１３４】
【数１００】
である。φ２（σ）−φ１（σ）の分子σ４＋２σ３−３σ２−２σ−７は、（２１／３，∞）の範囲に実零点α４＝１．７３４７６・・・を持つ。そして、（２１／３，α４）ではφ１（σ）＞φ２（σ）、α４ではφ１（σ）＝φ２（σ）、（α４，∞）ではφ１（σ）＜φ２（σ）が成り立つ。
【０１３５】
φ３（σ）−φ１（σ）の分子２σ４＋４σ３−６σ２−４σ−２は、（２１／３，α４］の範囲に実零点α５＝１．４２７３５・・・を持つ。そして、（２１／３，α５）ではφ１（σ）＞φ３（σ）、α５ではφ１（σ）＝φ３（σ）、（α５，α４］ではφ１（σ）＜φ３（σ）が成り立つ。
【０１３６】
φ３（σ）−φ２（σ）の分子−σ４＋２σ３＋３σ２＋２σ−１の（α４，∞）の範囲にある零点は、α６＝３．１３０００・・・である。そして、（α４，α６）ではφ２（σ）＜φ３（σ）、α６ではφ２（σ）＝φ３（σ）、（α３，∞）ではφ２（σ）＞φ３（σ）が成り立つ。よって、
【０１３７】
【数１０１】
である（範囲（（２１／３，∞）に対するアルゴリズム１の（ｉｉ）（ｉｉｉ）に相当）。
以上をまとめると、集合Ｊ＼ＺでのΦ（σ）は、
【０１３８】
【数１０２】
となる（Ｓ２４０）。
【０１３９】
実閉区間確認手段２５０は、実閉区間Ｉが一点かを確認する（Ｓ２５０）。この例では実閉区間Ｉは一点ではないので、ｍ計算手段２６０は、ｍ１，…，ｍ４を次のように計算する（Ｓ２６０）。
【０１４０】
【数１０３】
である。ｍ４は次のように求める。Φ（σ）を微分すると
【０１４１】
【数１０４】
となる。
（−∞，α１］において、φ３’（σ）の分母は常に負である。φ３’（σ）の分子−２σ３＋６σ−２はβ＝−１．８７９３８・・・においてのみ零点を持ち、（−∞，β）において正、（β，α１）において負である。したがって、Φ（σ）は、（−∞，β）において単調減少、（β，α１）において単調増加である。また、（α１，０）においては、φ２’（σ）の分母は常に正である。φ２’（σ）の分子２σ３＋６σ２＋２は零点を持たず常に正である。したがって、Φ（σ）は、（α１，０）において単調増加である。同様にΦ（σ）を調べていくと、Φ（σ）は（０，（１／２）１／３）∪（（１／２）１／３，２１／３）∪（２１／３，α５）で単調減少、［α５，∞）で単調増加である。したがって、集合Ｊ＼ＺにおけるΦ（σ）の最小値ｍ４は
ｍ４＝ｍｉｎ｛Φ（β），Φ（α５）｝
＝ｍｉｎ｛０．８４９３５・・・，０．６１３２４・・・｝
＝０．６１３２４・・・
である。
【０１４２】
ｍ決定手段２７０は、
ｍ＝ｍｉｎ｛ｍ１，…，ｍ４｝＝ｍ４＝０．６１３２４・・・
を計算して、最小距離０．６１３２４・・・を求める（Ｓ２７０）。
【０１４３】
出力部４００は、第１計算部２００の計算結果である最小距離０．６１３２４・・・を出力する（Ｓ４００）。
【０１４４】
なお、上述の説明では、説明を簡単にするために区間Ｉの端点、多項式の係数は有理数としたが、実施例に示した計算では四則演算と等号判定が実行できれば十分なので、例えば実代数的数（整数係数一次代数方程式の根となる実数）としてもよい。
【実施例２】
【０１４５】
実施例１では距離算出装置と距離算出方法を示したが、同様の技術で多項式算出装置や多項式算出方法も提供できる。実施例２では、多項式算出装置と多項式算出方法について説明する。本発明の多項式算出装置の機能構成例も図１に示す。また、図２に第１計算部の機能構成例、図３に第２計算部の機能構成例を示す。また、図４に多項式算出装置２０の処理フロー、図５に第１計算部の処理フロー、図６に第２計算部の処理フローを示す。実線で示した構成部や処理ステップが距離算出装置１０と多項式算出装置２０に共通な構成部や処理ステップ、点線で示した構成部や処理ステップが多項式算出装置２０にのみ必要な構成部や処理ステップ、一点鎖線で示した構成部や処理ステップは距離算出装置１０にのみ必要な構成部や処理ステップである。
【０１４６】
多項式算出装置２０は、第１計算部と第２計算部とが、距離算出装置１０と異なる。多項式算出装置２０は、第１計算部２００’に、さらに多項式算出手段２８０を有し、第２計算部３００’は距離選定手段３５０とゼロ多項式用距離計算手段３４５の代わりに多項式選定手段３６０を有する。その他の構成は、第１計算部２００、第２計算部３００と同じである。多項式算出手段２８０は、ｍ決定手段２７０が求めた最短距離ｍを用いて、多項式
【０１４７】
【数１０５】
の中の１つまたは複数の情報を求める（Ｓ２８０）。なお、ｍ’の値、±の符号については、理論的説明で示した式（１１）（１２）（５）などにより定めることができる。多項式選定手段３６０は、ｆ(ｘ)ｅ’１（ｘ）−ｆ’（ｘ）ｅ１（ｘ）が恒等的に０ではない場合には、距離計算手段が計算した距離が最小となる多項式を選定し（Ｓ３６５）、ｆ(ｘ)ｅ’１（ｘ）−ｆ’（ｘ）ｅ１（ｘ）が恒等的に０の場合には、ゼロ多項式を選定する（Ｓ３６０）。そして、出力部４００は、算出された多項式の情報を出力する（Ｓ４００）。
【０１４８】
多項式算出装置２０は、このように距離算出装置１０と同じ技術によって多項式を算出するので、解く必要のある方程式の数、その次数をｎ、ｄ＝ｍａｘ｛ｄｅｇ（ｆ(ｘ)），ｄｅｇ（ｅ１（ｘ）），…，ｄｅｇ（ｅｎ（ｘ））｝の多項式オーダにできる。
【０１４９】
図７にコンピュータの機能構成例を示す。上述の実施例は、図７に示すコンピュータの記録部２０２０に、上記装置としてコンピュータを実行させるプログラムを読み込ませ、制御部２０１０、入力部２０３０、出力部２０４０などに動作させることで実施できる。また、コンピュータに読み込ませる方法としては、プログラムをコンピュータ読み取り可能な記録媒体に記録しておき、記録媒体からコンピュータに読み込ませる方法、サーバ等に記録されたプログラムを、電気通信回線等を通じてコンピュータに読み込ませる方法などがある。
【産業上の利用可能性】
【０１５０】
デジタル信号処理やシステム制御の分野において、実一変数多項式の零点の位置は、デジタルフィルタの周波数特性やシステムの性能に密接に関係する。デジタルフィルタの周波数特性やシステムの性能を設計する上で、ある実区間Ｉに所望の個数（ゼロ個の場合も含む）の実零点を持つように多項式の係数を設定したい場合を考える。多項式の係数は有限精度でしか指定できないので、必ず誤差を持つ。また、多項式の実重複零点は、どんなに小さな係数の変化に対しても、複数の複素零点あるいは実の近接零点となるので、実重複零点を持つ多項式が係数の誤差範囲に存在すれば、実区間Ｉの実零点の個数を制御できないことになる。したがって、設計によって求めた実一変数多項式が、実重複零点を持つ実一変数多項式とどの程度離れているのかは、デジタルフィルタの周波数特性やシステムの性能を設計する上で重要な問題である。
【０１５１】
本発明は、例えば、実閉区間Ｉに実重複零点を持たないように多項式の係数を設定したい場合に、係数設定に誤差を伴うことを前提として、誤差範囲内のどのような多項式であっても間違いなく実閉区間に実重複零点を持たないようにするときに、その誤差限界の確定などとして用いることができる。このような場合の一例として、デジタル信号処理におけるデジタルフィルタ（例えば、ＩＩＲ〔Infinite Impulse Response〕フィルタ）の設計などに有用である。
【図面の簡単な説明】
【０１５２】
【図１】本発明の距離算出装置および多項式算出装置の機能構成例を示す図。
【図２】第１計算部の機能構成例を示す図。
【図３】第２計算部の機能構成例を示す図。
【図４】本発明の距離算出装置および多項式算出装置の処理フローを示す図。
【図５】第１計算部の処理フローを示す図。
【図６】第２計算部の処理フローを示す図。
【図７】コンピュータの機能構成例を示す図。
【符号の説明】
【０１５３】
１０ 距離算出装置 ２０ 多項式算出装置
１００ 入力部 １５０ 多項式判定部
１９０ 記録部 ２００、２００’ 第１計算部
２１０ Δ、Δ〜、Ｚ〜、Ｚ計算手段 ２２０ Δ＼Ｚ〜、Ｊ＼Ｚ計算手段
２３０ φｊ（σ）計算手段 ２４０ Φ（σ）計算手段
２５０ 実閉区間確認手段 ２６０ ｍ計算手段
２７０ ｍ決定手段 ２８０ 多項式算出手段
３００、３００’ 第２計算部 ３１０ 連立方程式生成手段
３２０ 恒等性確認手段 ３３０ 多項式生成手段
３４０ 距離計算手段 ３４５ ゼロ多項式用距離計算手段
３５０ 距離選定手段 ３６０ 多項式選定手段
４００ 出力部
【特許請求の範囲】
【請求項１】
実数全体の集合をＲとし、ａ１，ａ２，…，ａｎをそれぞれあらかじめ与えられた実数とし、ｅ１（ｘ），…，ｅｎ（ｘ）をそれぞれあらかじめ与えられた一変数実多項式とし、一変数実多項式ｆ（ｘ）が実閉区間Ｉに実重複零点を持たないとして、一変数実多項式の集合
【数１】
のうち、前記実閉区間Ｉに実重複零点を持ち、かつ、前記一変数実多項式f（ｘ）にｌ∞−ノルムで計算して最も近い一変数実多項式ｆ〜（ｘ）について、前記一変数実多項式ｆ（ｘ）と前記一変数実多項式ｆ〜（ｘ）との距離を算出する距離算出装置であって、
前記ａ１，ａ２，…，ａｎと、前記ｆ（ｘ），ｅ１（ｘ），…，ｅｎ（ｘ）と、前記実閉区間Ｉとを記録する記録部と、
ｎ＝１かｎ＞１かを判定する多項式判定部と、
ｎ＞１のときに前記一変数実多項式ｆ（ｘ）と前記一変数実多項式ｆ〜（ｘ）との距離を算出する第１計算部と、
ｎ＝１のときに前記一変数実多項式ｆ（ｘ）と前記一変数実多項式ｆ〜（ｘ）との距離を算出する第２計算部と、
を備え、
前記第１計算部は、
【数２】
を求めるΔ、Δ〜、Ｚ〜、Ｚ計算手段と、
集合Δ＼Ｚ〜と集合Ｊ＼Ｚを求めるΔ＼Ｚ〜、Ｊ＼Ｚ計算手段と、
【数３】
ただし、σ∈Ｉ＼Δ、ｊ＝１，…，ｎ
を求めるφｊ（σ）計算手段と、
【数４】
を求めるΦ（σ）計算手段と、
実閉区間Ｉが一点かを確認する実閉区間確認手段と、
実閉区間Ｉが一点でない場合に、
【数５】
を計算するｍ計算手段と、
実閉区間Ｉが一点でない場合にはｍ＝ｍｉｎ｛ｍ１，…，ｍ４｝とし、実閉区間Ｉが一点の場合にはｍ＝Φ（σ）のように距離ｍを決定するｍ決定手段と、
を有する距離算出装置。
【請求項２】
請求項１記載の距離算出装置であって、
前記第２計算部は、
【数６】
を生成する連立方程式生成手段と、
ｆ(ｘ)ｅ’１（ｘ）−ｆ’（ｘ）ｅ１（ｘ）が恒等的に０かを確認する恒等性確認手段と、
ｆ(ｘ)ｅ’１（ｘ）−ｆ’（ｘ）ｅ１（ｘ）が恒等的に０ではない場合には、ｆ(ｘ)ｅ’１（ｘ）−ｆ’（ｘ）ｅ１（ｘ）＝０を満たす有限個のｔ１を求め、すべてのｔ１に対する多項式ｆ(ｘ)＋ｔ１ｅ１（ｘ）を生成する多項式生成手段と、
ｆ(ｘ)ｅ’１（ｘ）−ｆ’（ｘ）ｅ１（ｘ）が恒等的に０ではない場合には、ｌ∞−ノルムによって前記多項式生成手段が生成した各多項式と多項式ｆ（ｘ）との距離を計算する距離計算手段と、
ｆ(ｘ)ｅ’１（ｘ）−ｆ’（ｘ）ｅ１（ｘ）が恒等的に０ではない場合には、前記距離計算手段が計算した距離の中で最小の距離を選定する距離選定手段と、
ｆ(ｘ)ｅ’１（ｘ）−ｆ’（ｘ）ｅ１（ｘ）が恒等的に０の場合には、ｌ∞−ノルムによってゼロ多項式と多項式ｆ（ｘ）との距離を計算するゼロ多項式用距離計算手段と、
を有する距離算出装置。
【請求項３】
実数全体の集合をＲとし、ａ１，ａ２，…，ａｎをそれぞれあらかじめ与えられた実数とし、ｅ１（ｘ），…，ｅｎ（ｘ）をそれぞれあらかじめ与えられた一変数実多項式とし、一変数実多項式ｆ（ｘ）が実閉区間Ｉに実重複零点を持たないとして、一変数実多項式の集合
【数７】
のうち、前記実閉区間Ｉに実重複零点を持ち、かつ、前記一変数実多項式f（ｘ）にｌ∞−ノルムで計算して最も近い一変数実多項式ｆ〜（ｘ）を求める多項式算出装置であって、
前記ａ１，ａ２，…，ａｎと、前記ｆ（ｘ），ｅ１（ｘ），…，ｅｎ（ｘ）と、前記実閉区間Ｉとを記録する記録部と、
ｎ＝１かｎ＞１かを判定する多項式判定部と、
ｎ＞１のときに前記一変数実多項式ｆ（ｘ）と前記一変数実多項式ｆ〜（ｘ）との距離を算出する第１計算部と、
ｎ＝１のときに前記一変数実多項式ｆ（ｘ）と前記一変数実多項式ｆ〜（ｘ）との距離を算出する第２計算部と、
を備え、
前記第１計算部は、
【数８】
を求めるΔ、Δ〜、Ｚ〜、Ｚ計算手段と、
集合Δ＼Ｚ〜と集合Ｊ＼Ｚを求めるΔ＼Ｚ〜、Ｊ＼Ｚ計算手段と、
【数９】
ただし、σ∈Ｉ＼Δ、ｊ＝１，…，ｎ
を求めるφｊ（σ）計算手段と、
【数１０】
を求めるΦ（σ）計算手段と、
実閉区間Ｉが一点かを確認する実閉区間確認手段と、
実閉区間Ｉが一点でない場合に、
【数１１】
を計算するｍ計算手段と、
実閉区間Ｉが一点でない場合にはｍ＝ｍｉｎ｛ｍ１，…，ｍ４｝とし、実閉区間Ｉが一点の場合にはｍ＝Φ（σ）のように距離ｍを決定するｍ決定手段と、
多項式
【数１２】
の中の１つまたは複数の情報を求める多項式算出手段と
を備える多項式算出装置。
【請求項４】
請求項３記載の多項式算出装置であって、
前記第２計算部は、
【数１３】
を生成する連立方程式生成手段と、
ｆ(ｘ)ｅ’１（ｘ）−ｆ’（ｘ）ｅ１（ｘ）が恒等的に０かを確認する恒等性確認手段と、
ｆ(ｘ)ｅ’１（ｘ）−ｆ’（ｘ）ｅ１（ｘ）が恒等的に０ではない場合には、ｆ(ｘ)ｅ’１（ｘ）−ｆ’（ｘ）ｅ１（ｘ）＝０を満たす有限個のｔ１を求め、すべてのｔ１に対する多項式ｆ(ｘ)＋ｔ１ｅ１（ｘ）を生成しする多項式生成手段と、
ｆ(ｘ)ｅ’１（ｘ）−ｆ’（ｘ）ｅ１（ｘ）が恒等的に０ではない場合には、ｌ∞−ノルムによって前記多項式生成手段が生成した各多項式と多項式ｆ（ｘ）との距離を計算する距離計算手段と、
ｆ(ｘ)ｅ’１（ｘ）−ｆ’（ｘ）ｅ１（ｘ）が恒等的に０ではない場合には、前記距離計算手段が計算した距離が最小となる多項式を選定し、ｆ(ｘ)ｅ’１（ｘ）−ｆ’（ｘ）ｅ１（ｘ）が恒等的に０の場合には、ゼロ多項式を選定する多項式選定手段と、
を有する多項式算出装置。
【請求項５】
実数全体の集合をＲとし、ａ１，ａ２，…，ａｎをそれぞれあらかじめ与えられた実数とし、ｅ１（ｘ），…，ｅｎ（ｘ）をそれぞれあらかじめ与えられた一変数実多項式とし、一変数実多項式ｆ（ｘ）が実閉区間Ｉに実重複零点を持たないとして、一変数実多項式の集合
【数１４】
のうち、前記実閉区間Ｉに実重複零点を持ち、かつ、前記一変数実多項式f（ｘ）にｌ∞−ノルムで計算して最も近い一変数実多項式ｆ〜（ｘ）について、前記一変数実多項式ｆ（ｘ）と前記一変数実多項式ｆ〜（ｘ）との距離を算出する距離算出方法であって、
記録部に、あらかじめ前記ａ１，ａ２，…，ａｎと、前記ｆ（ｘ），ｅ１（ｘ），…，ｅｎ（ｘ）と、前記実閉区間Ｉとを記録しておき、
多項式判定部が、ｎ＝１かｎ＞１かを判定する多項式判定ステップと、
第１計算部が、ｎ＞１のときに前記一変数実多項式ｆ（ｘ）と前記一変数実多項式ｆ〜（ｘ）との距離を算出する第１計算ステップと、
第２計算部が、ｎ＝１のときに前記一変数実多項式ｆ（ｘ）と前記一変数実多項式ｆ〜（ｘ）との距離を算出する第２計算ステップ
を有し、
前記第１計算ステップは、
【数１５】
を求めるΔ、Δ〜、Ｚ〜、Ｚ計算サブステップと、
集合Δ＼Ｚ〜と集合Ｊ＼Ｚを求めるΔ＼Ｚ〜、Ｊ＼Ｚ計算サブステップと、
【数１６】
ただし、σ∈Ｉ＼Δ、ｊ＝１，…，ｎ
を求めるφｊ（σ）計算サブステップと、
【数１７】
を求めるΦ（σ）計算サブステップと、
実閉区間Ｉが一点かを確認する実閉区間確認サブステップと、
実閉区間Ｉが一点でない場合に、
【数１８】
を計算するｍ計算サブステップと、
実閉区間Ｉが一点でない場合にはｍ＝ｍｉｎ｛ｍ１，…，ｍ４｝とし、実閉区間Ｉが一点の場合にはｍ＝Φ（σ）のように距離ｍを決定するｍ決定サブステップと、
を有する距離算出方法。
【請求項６】
実数全体の集合をＲとし、ａ１，ａ２，…，ａｎをそれぞれあらかじめ与えられた実数とし、ｅ１（ｘ），…，ｅｎ（ｘ）をそれぞれあらかじめ与えられた一変数実多項式とし、一変数実多項式ｆ（ｘ）が実閉区間Ｉに実重複零点を持たないとして、一変数実多項式の集合
【数１９】
のうち、前記実閉区間Ｉに実重複零点を持ち、かつ、前記一変数実多項式f（ｘ）にｌ∞−ノルムで計算して最も近い一変数実多項式ｆ〜（ｘ）を求める多項式算出方法であって、
記録部に、あらかじめ前記ａ１，ａ２，…，ａｎと、前記ｆ（ｘ），ｅ１（ｘ），…，ｅｎ（ｘ）と、前記実閉区間Ｉとを記録しておき、
多項式判定部が、ｎ＝１かｎ＞１かを判定する多項式判定ステップと、
第１計算部が、ｎ＞１のときに前記一変数実多項式ｆ（ｘ）と前記一変数実多項式ｆ〜（ｘ）との距離を算出する第１計算ステップと、
第２計算部が、ｎ＝１のときに前記一変数実多項式ｆ（ｘ）と前記一変数実多項式ｆ〜（ｘ）との距離を算出する第２計算ステップと、
を備え、
前記第１計算ステップは、
【数２０】
を求めるΔ、Δ〜、Ｚ〜、Ｚ計算サブステップと、
集合Δ＼Ｚ〜と集合Ｊ＼Ｚを求めるΔ＼Ｚ〜、Ｊ＼Ｚ計算サブステップと、
【数２１】
ただし、σ∈Ｉ＼Δ、ｊ＝１，…，ｎ
を求めるφｊ（σ）計算サブステップと、
【数２２】
を求めるΦ（σ）計算サブステップと、
実閉区間Ｉが一点かを確認する実閉区間確認サブステップと、
実閉区間Ｉが一点でない場合に、
【数２３】
を計算するｍ計算サブステップと、
実閉区間Ｉが一点でない場合にはｍ＝ｍｉｎ｛ｍ１，…，ｍ４｝とし、実閉区間Ｉが一点の場合にはｍ＝Φ（σ）のように距離ｍを決定するｍ決定サブステップと、
多項式
【数２４】
の中の１つまたは複数の情報を求める多項式算出サブステップと
を有する多項式算出方法。
【請求項７】
請求項５または６記載の方法の各ステップをコンピュータに実行させるプログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項１】
実数全体の集合をＲとし、ａ１，ａ２，…，ａｎをそれぞれあらかじめ与えられた実数とし、ｅ１（ｘ），…，ｅｎ（ｘ）をそれぞれあらかじめ与えられた一変数実多項式とし、一変数実多項式ｆ（ｘ）が実閉区間Ｉに実重複零点を持たないとして、一変数実多項式の集合
【数１】
のうち、前記実閉区間Ｉに実重複零点を持ち、かつ、前記一変数実多項式f（ｘ）にｌ∞−ノルムで計算して最も近い一変数実多項式ｆ〜（ｘ）について、前記一変数実多項式ｆ（ｘ）と前記一変数実多項式ｆ〜（ｘ）との距離を算出する距離算出装置であって、
前記ａ１，ａ２，…，ａｎと、前記ｆ（ｘ），ｅ１（ｘ），…，ｅｎ（ｘ）と、前記実閉区間Ｉとを記録する記録部と、
ｎ＝１かｎ＞１かを判定する多項式判定部と、
ｎ＞１のときに前記一変数実多項式ｆ（ｘ）と前記一変数実多項式ｆ〜（ｘ）との距離を算出する第１計算部と、
ｎ＝１のときに前記一変数実多項式ｆ（ｘ）と前記一変数実多項式ｆ〜（ｘ）との距離を算出する第２計算部と、
を備え、
前記第１計算部は、
【数２】
を求めるΔ、Δ〜、Ｚ〜、Ｚ計算手段と、
集合Δ＼Ｚ〜と集合Ｊ＼Ｚを求めるΔ＼Ｚ〜、Ｊ＼Ｚ計算手段と、
【数３】
ただし、σ∈Ｉ＼Δ、ｊ＝１，…，ｎ
を求めるφｊ（σ）計算手段と、
【数４】
を求めるΦ（σ）計算手段と、
実閉区間Ｉが一点かを確認する実閉区間確認手段と、
実閉区間Ｉが一点でない場合に、
【数５】
を計算するｍ計算手段と、
実閉区間Ｉが一点でない場合にはｍ＝ｍｉｎ｛ｍ１，…，ｍ４｝とし、実閉区間Ｉが一点の場合にはｍ＝Φ（σ）のように距離ｍを決定するｍ決定手段と、
を有する距離算出装置。
【請求項２】
請求項１記載の距離算出装置であって、
前記第２計算部は、
【数６】
を生成する連立方程式生成手段と、
ｆ(ｘ)ｅ’１（ｘ）−ｆ’（ｘ）ｅ１（ｘ）が恒等的に０かを確認する恒等性確認手段と、
ｆ(ｘ)ｅ’１（ｘ）−ｆ’（ｘ）ｅ１（ｘ）が恒等的に０ではない場合には、ｆ(ｘ)ｅ’１（ｘ）−ｆ’（ｘ）ｅ１（ｘ）＝０を満たす有限個のｔ１を求め、すべてのｔ１に対する多項式ｆ(ｘ)＋ｔ１ｅ１（ｘ）を生成する多項式生成手段と、
ｆ(ｘ)ｅ’１（ｘ）−ｆ’（ｘ）ｅ１（ｘ）が恒等的に０ではない場合には、ｌ∞−ノルムによって前記多項式生成手段が生成した各多項式と多項式ｆ（ｘ）との距離を計算する距離計算手段と、
ｆ(ｘ)ｅ’１（ｘ）−ｆ’（ｘ）ｅ１（ｘ）が恒等的に０ではない場合には、前記距離計算手段が計算した距離の中で最小の距離を選定する距離選定手段と、
ｆ(ｘ)ｅ’１（ｘ）−ｆ’（ｘ）ｅ１（ｘ）が恒等的に０の場合には、ｌ∞−ノルムによってゼロ多項式と多項式ｆ（ｘ）との距離を計算するゼロ多項式用距離計算手段と、
を有する距離算出装置。
【請求項３】
実数全体の集合をＲとし、ａ１，ａ２，…，ａｎをそれぞれあらかじめ与えられた実数とし、ｅ１（ｘ），…，ｅｎ（ｘ）をそれぞれあらかじめ与えられた一変数実多項式とし、一変数実多項式ｆ（ｘ）が実閉区間Ｉに実重複零点を持たないとして、一変数実多項式の集合
【数７】
のうち、前記実閉区間Ｉに実重複零点を持ち、かつ、前記一変数実多項式f（ｘ）にｌ∞−ノルムで計算して最も近い一変数実多項式ｆ〜（ｘ）を求める多項式算出装置であって、
前記ａ１，ａ２，…，ａｎと、前記ｆ（ｘ），ｅ１（ｘ），…，ｅｎ（ｘ）と、前記実閉区間Ｉとを記録する記録部と、
ｎ＝１かｎ＞１かを判定する多項式判定部と、
ｎ＞１のときに前記一変数実多項式ｆ（ｘ）と前記一変数実多項式ｆ〜（ｘ）との距離を算出する第１計算部と、
ｎ＝１のときに前記一変数実多項式ｆ（ｘ）と前記一変数実多項式ｆ〜（ｘ）との距離を算出する第２計算部と、
を備え、
前記第１計算部は、
【数８】
を求めるΔ、Δ〜、Ｚ〜、Ｚ計算手段と、
集合Δ＼Ｚ〜と集合Ｊ＼Ｚを求めるΔ＼Ｚ〜、Ｊ＼Ｚ計算手段と、
【数９】
ただし、σ∈Ｉ＼Δ、ｊ＝１，…，ｎ
を求めるφｊ（σ）計算手段と、
【数１０】
を求めるΦ（σ）計算手段と、
実閉区間Ｉが一点かを確認する実閉区間確認手段と、
実閉区間Ｉが一点でない場合に、
【数１１】
を計算するｍ計算手段と、
実閉区間Ｉが一点でない場合にはｍ＝ｍｉｎ｛ｍ１，…，ｍ４｝とし、実閉区間Ｉが一点の場合にはｍ＝Φ（σ）のように距離ｍを決定するｍ決定手段と、
多項式
【数１２】
の中の１つまたは複数の情報を求める多項式算出手段と
を備える多項式算出装置。
【請求項４】
請求項３記載の多項式算出装置であって、
前記第２計算部は、
【数１３】
を生成する連立方程式生成手段と、
ｆ(ｘ)ｅ’１（ｘ）−ｆ’（ｘ）ｅ１（ｘ）が恒等的に０かを確認する恒等性確認手段と、
ｆ(ｘ)ｅ’１（ｘ）−ｆ’（ｘ）ｅ１（ｘ）が恒等的に０ではない場合には、ｆ(ｘ)ｅ’１（ｘ）−ｆ’（ｘ）ｅ１（ｘ）＝０を満たす有限個のｔ１を求め、すべてのｔ１に対する多項式ｆ(ｘ)＋ｔ１ｅ１（ｘ）を生成しする多項式生成手段と、
ｆ(ｘ)ｅ’１（ｘ）−ｆ’（ｘ）ｅ１（ｘ）が恒等的に０ではない場合には、ｌ∞−ノルムによって前記多項式生成手段が生成した各多項式と多項式ｆ（ｘ）との距離を計算する距離計算手段と、
ｆ(ｘ)ｅ’１（ｘ）−ｆ’（ｘ）ｅ１（ｘ）が恒等的に０ではない場合には、前記距離計算手段が計算した距離が最小となる多項式を選定し、ｆ(ｘ)ｅ’１（ｘ）−ｆ’（ｘ）ｅ１（ｘ）が恒等的に０の場合には、ゼロ多項式を選定する多項式選定手段と、
を有する多項式算出装置。
【請求項５】
実数全体の集合をＲとし、ａ１，ａ２，…，ａｎをそれぞれあらかじめ与えられた実数とし、ｅ１（ｘ），…，ｅｎ（ｘ）をそれぞれあらかじめ与えられた一変数実多項式とし、一変数実多項式ｆ（ｘ）が実閉区間Ｉに実重複零点を持たないとして、一変数実多項式の集合
【数１４】
のうち、前記実閉区間Ｉに実重複零点を持ち、かつ、前記一変数実多項式f（ｘ）にｌ∞−ノルムで計算して最も近い一変数実多項式ｆ〜（ｘ）について、前記一変数実多項式ｆ（ｘ）と前記一変数実多項式ｆ〜（ｘ）との距離を算出する距離算出方法であって、
記録部に、あらかじめ前記ａ１，ａ２，…，ａｎと、前記ｆ（ｘ），ｅ１（ｘ），…，ｅｎ（ｘ）と、前記実閉区間Ｉとを記録しておき、
多項式判定部が、ｎ＝１かｎ＞１かを判定する多項式判定ステップと、
第１計算部が、ｎ＞１のときに前記一変数実多項式ｆ（ｘ）と前記一変数実多項式ｆ〜（ｘ）との距離を算出する第１計算ステップと、
第２計算部が、ｎ＝１のときに前記一変数実多項式ｆ（ｘ）と前記一変数実多項式ｆ〜（ｘ）との距離を算出する第２計算ステップ
を有し、
前記第１計算ステップは、
【数１５】
を求めるΔ、Δ〜、Ｚ〜、Ｚ計算サブステップと、
集合Δ＼Ｚ〜と集合Ｊ＼Ｚを求めるΔ＼Ｚ〜、Ｊ＼Ｚ計算サブステップと、
【数１６】
ただし、σ∈Ｉ＼Δ、ｊ＝１，…，ｎ
を求めるφｊ（σ）計算サブステップと、
【数１７】
を求めるΦ（σ）計算サブステップと、
実閉区間Ｉが一点かを確認する実閉区間確認サブステップと、
実閉区間Ｉが一点でない場合に、
【数１８】
を計算するｍ計算サブステップと、
実閉区間Ｉが一点でない場合にはｍ＝ｍｉｎ｛ｍ１，…，ｍ４｝とし、実閉区間Ｉが一点の場合にはｍ＝Φ（σ）のように距離ｍを決定するｍ決定サブステップと、
を有する距離算出方法。
【請求項６】
実数全体の集合をＲとし、ａ１，ａ２，…，ａｎをそれぞれあらかじめ与えられた実数とし、ｅ１（ｘ），…，ｅｎ（ｘ）をそれぞれあらかじめ与えられた一変数実多項式とし、一変数実多項式ｆ（ｘ）が実閉区間Ｉに実重複零点を持たないとして、一変数実多項式の集合
【数１９】
のうち、前記実閉区間Ｉに実重複零点を持ち、かつ、前記一変数実多項式f（ｘ）にｌ∞−ノルムで計算して最も近い一変数実多項式ｆ〜（ｘ）を求める多項式算出方法であって、
記録部に、あらかじめ前記ａ１，ａ２，…，ａｎと、前記ｆ（ｘ），ｅ１（ｘ），…，ｅｎ（ｘ）と、前記実閉区間Ｉとを記録しておき、
多項式判定部が、ｎ＝１かｎ＞１かを判定する多項式判定ステップと、
第１計算部が、ｎ＞１のときに前記一変数実多項式ｆ（ｘ）と前記一変数実多項式ｆ〜（ｘ）との距離を算出する第１計算ステップと、
第２計算部が、ｎ＝１のときに前記一変数実多項式ｆ（ｘ）と前記一変数実多項式ｆ〜（ｘ）との距離を算出する第２計算ステップと、
を備え、
前記第１計算ステップは、
【数２０】
を求めるΔ、Δ〜、Ｚ〜、Ｚ計算サブステップと、
集合Δ＼Ｚ〜と集合Ｊ＼Ｚを求めるΔ＼Ｚ〜、Ｊ＼Ｚ計算サブステップと、
【数２１】
ただし、σ∈Ｉ＼Δ、ｊ＝１，…，ｎ
を求めるφｊ（σ）計算サブステップと、
【数２２】
を求めるΦ（σ）計算サブステップと、
実閉区間Ｉが一点かを確認する実閉区間確認サブステップと、
実閉区間Ｉが一点でない場合に、
【数２３】
を計算するｍ計算サブステップと、
実閉区間Ｉが一点でない場合にはｍ＝ｍｉｎ｛ｍ１，…，ｍ４｝とし、実閉区間Ｉが一点の場合にはｍ＝Φ（σ）のように距離ｍを決定するｍ決定サブステップと、
多項式
【数２４】
の中の１つまたは複数の情報を求める多項式算出サブステップと
を有する多項式算出方法。
【請求項７】
請求項５または６記載の方法の各ステップをコンピュータに実行させるプログラムを記録したコンピュータ読み取り可能な記録媒体。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【公開番号】特開２００９−２７６８４１（Ｐ２００９−２７６８４１Ａ）
【公開日】平成２１年１１月２６日（２００９．１１．２６）
【国際特許分類】
【出願番号】特願２００８−１２４９４３（Ｐ２００８−１２４９４３）
【出願日】平成２０年５月１２日（２００８．５．１２）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２１年１１月２６日（２００９．１１．２６）
【国際特許分類】
【出願日】平成２０年５月１２日（２００８．５．１２）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]