(57)【要約】【課題】複素領域Ｄに零点を持つ一変数実多項式のうち、領域Ｄに零点を持たない一変数実多項式ｆに最も近い一変数実多項式ｆ~と、一変数実多項式ｆとのｌ∞-ノルムで定義された距離を、最悪の場合であっても多項式時間の計算量で求める。【解決手段】領域Ｄの境界Λ上の点αに対して、この点αを零点とする一変数実多項式のうち一変数実多項式f(x)に最も近い一変数実多項式g(x)と一変数実多項式f(x)との距離を与える関数Φ(α)を用いて、区分境界Λ1,Λ2,…,ΛKごとに関数Φ(α)の最小値を求め（距離候補探索：Ｓ５０、Ｓ５１、Ｓ６、Ｓ７１〜７５、Ｓ８１〜８５）、この距離候補探索で得られた値のうち最小のものを求める（最小距離算出：Ｓ５２）。【選択図】図１−２
2009271888.tif 000002
【特許請求の範囲】
【請求項１】
Ｒを実数全体の集合とし、f(x),e1(x),…,en(x)をそれぞれ予め与えられた一変数実多項式とし、二つの一変数実多項式の距離をｌ∞-ノルムで定義し、一変数実多項式f(x)が複素数全体の集合内の閉な領域Ｄに零点を持たないとして、
一変数実多項式の集合
【数１】
2009271888.tif 000090
に属する一変数実多項式であって、上記領域Ｄに零点を持ち、かつ、上記一変数実多項式f(x)に最も近い一変数実多項式f~(x)について、上記一変数実多項式f(x)と上記一変数実多項式f~(x)との距離を算出する多項式間距離算出装置であり、
上記f(x),e1(x),…,en(x)と、上記領域Ｄの境界Λを構成する有限個の区分境界Λ1,Λ2,…,ΛKとを記憶する記憶手段と、
上記境界Λ上の点αに対して、上記集合Ｆに属しこの点αを零点とする一変数実多項式のうち上記一変数実多項式f(x)に最も近い一変数実多項式g(x)と上記一変数実多項式f(x)との距離を与える関数Φ(α)を用いて、上記区分境界Λ1,Λ2,…,ΛKごとに前記関数Φ(α)の最小値を求める距離候補探索手段と、
上記距離候補探索手段によって得られた値のうち最小のものを求める最小距離算出手段と
を備えた多項式間距離算出装置。
【請求項２】
複素数の実部と虚部をそれぞれＲｅ，Ｉｍで表すとして、複素数ｕ，ｖに対する行列式
【数２】
2009271888.tif 000091
を定義し、ｉを虚数単位とし、
［１］１≦ｊ＜ｋ≦ｎなる全てのｊ，ｋに対してA(ej(α),ek(α))=0が成立し、かつ、A(ej(α),f(α))=0がｊ＝１，…，ｎに対して成立ち、かつ、ｅｊ(α)≠０となるｊが存在する場合に、上記関数Φ(α)は、
【数３】
2009271888.tif 000092
であり、
［２］或るｊ，ｋ（１≦ｊ＜ｋ≦ｎ）に対してA(ej(α),ek(α))≠0が成立する場合に、上記関数Φ(α)は、
【数４】
2009271888.tif 000093
（但し、分母が０となるものは除く。）である
ことを特徴とする請求項１に記載の多項式間距離算出装置。
【請求項３】
上記距離候補探索手段は、
各上記区分境界Λμ（但しμ=1,2,…,K）が点であるか否かを判定する区分境界点判定手段を含み、
区分境界Λμが点であると判定されなかった場合に、
上記［１］の場合を、少なくとも一つのｊについてA(ej(α),if(α))=0が成立する場合Ｓ１とそれ以外の場合Ｓ２に分け、
上記［２］の場合を、少なくとも一つのｊについてA(ej(α),f(α))=0または１≦ｊ＜ｋ≦ｎなるｊ，ｋに対してA(ej(α),ek(α))=0が成立する場合Ｓ３とそれ以外の場合Ｓ４に分け、
当該区分境界Λμでの上記関数Φ(α)の最小値を、各上記場合Ｓ１〜Ｓ４の上記関数Φ(α)の各最小値のうち最小のものとする
ことを特徴とする請求項２に記載の多項式間距離算出装置。
【請求項４】
各上記区分境界Λμ（但しμ=1,2,…,K）が、実数上の集合Ｉμに対する有理式で表される単射γμ(s) （但しｓ∈Ｉμ）で与えられるとし、
集合Δμを
【数５】
2009271888.tif 000094
とし、
集合Δ~μ⊂Δμを
【数６】
2009271888.tif 000095
とし、
集合Ｚ~μ⊂Δ~μを
【数７】
2009271888.tif 000096
とし、
集合Ｚμ⊂Δμを
【数８】
2009271888.tif 000097
とし、
区分境界Λμに対応する上記関数Φ(α)を
【数９】
2009271888.tif 000098
で表すとし、
上記距離候補探索手段は、
上記区分境界点判定手段によって点であると判定された区分境界Λμについて、実数上の集合Ｉμ（＝｛δ｝）が集合Ｉμ＼Δμに属する場合に、当該区分境界Λμでの上記関数Φμ(s)の最小値を、
【数１０】
2009271888.tif 000099
で求め、実数上の集合Ｉμ（＝｛δ｝）が上記集合Δ~μに属する場合に、当該区分境界Λμでの上記関数Φμ(s)の最小値を、
【数１１】
2009271888.tif 000100
で求める第一距離候補探索手段と、
上記区分境界点判定手段によって点であると判定されなかった区分境界Λμについて、上記Ｓ１の場合に上記集合Ｚ~μの有限個の元σについて、ｍμ，１を
【数１２】
2009271888.tif 000101
で求め、上記Ｓ２の場合に有限個の区間の和集合で表される集合Δ~μ＼Ｚ~μに属する元σについて，ｍμ，３を
【数１３】
2009271888.tif 000102
で求め、上記Ｓ３の場合に上記集合Ｚμの有限個の元σについて、ｍμ，２を
【数１４】
2009271888.tif 000103
で求め、上記Ｓ４の場合に有限個の区間の和集合で表される集合（Ｉμ＼Δμ）＼Ｚμに属する元σについて，ｍμ，４を
【数１５】
2009271888.tif 000104
で求め、当該区分境界Λμでの上記関数Φμ(s)の最小値をmin{mμ,1,mμ,2,mμ,3,mμ,4}で求める第二距離候補探索手段とを含む
ことを特徴とする請求項３に記載の多項式間距離算出装置。
【請求項５】
上記領域Ｄが有界であるか否かを判定する領域有界判定手段と、
上記領域Ｄが有界でない場合に、上記集合Ｆの次数が一定であるか否かを判定する次数判定手段とを備える
ことを特徴とする請求項１から請求項４のいずれかに記載の多項式間距離算出装置。
【請求項６】
多項式
【数１６】
2009271888.tif 000105
が恒等的に０となる実数a1,a2,…,anが存在するか否かを判定し、存在する場合には上記一変数実多項式f(x)と恒等的に０の多項式との距離を求める恒等式調査手段を備え、
上記最小距離算出手段に代えて、
上記距離候補探索手段によって得られた値および上記恒等式調査手段によって得られた距離のうち最小のものを求める第二最小距離算出手段を備える
ことを特徴とする請求項１から請求項５のいずれかに記載の多項式間距離算出装置。
【請求項７】
Ｒを実数全体の集合とし、f(x),e1(x),…,en(x)をそれぞれ予め与えられた一変数実多項式とし、二つの一変数実多項式の距離をｌ∞-ノルムで定義し、一変数実多項式f(x)が複素数全体の集合内の閉な領域Ｄに零点を持たないとして、
一変数実多項式の集合
【数１７】
2009271888.tif 000106
に属する一変数実多項式であって、上記領域Ｄに零点を持ち、かつ、上記一変数実多項式f(x)に最も近い一変数実多項式f~(x)について、上記一変数実多項式f(x)と上記一変数実多項式f~(x)との距離を算出する多項式間距離算出方法であり、
記憶手段には、上記f(x),e1(x),…,en(x)と、上記領域Ｄの境界Λを構成する有限個の区分境界Λ1,Λ2,…,ΛKとが記憶されており、
距離候補探索手段が、上記境界Λ上の点αに対して、上記集合Ｆに属しこの点αを零点とする一変数実多項式のうち上記一変数実多項式f(x)に最も近い一変数実多項式g(x)と上記一変数実多項式f(x)との距離を与える関数Φ(α)を用いて、上記区分境界Λ1,Λ2,…,ΛKごとに前記関数Φ(α)の最小値を求める距離候補探索ステップと、
最小距離算出手段が、上記距離候補探索ステップにおいて得られた値のうち最小のものを求める最小距離算出ステップと
を有する多項式間距離算出方法。
【請求項８】
Ｒを実数全体の集合とし、f(x),e1(x),…,en(x)をそれぞれ予め与えられた一変数実多項式とし、二つの一変数実多項式の距離をｌ∞-ノルムで定義し、一変数実多項式f(x)が複素数全体の集合内の閉な領域Ｄに零点を持たないとして、
一変数実多項式の集合
【数１８】
2009271888.tif 000107
に属する一変数実多項式であって、上記領域Ｄに零点を持ち、かつ、上記一変数実多項式f(x)に最も近い一変数実多項式f~(x)を算出する一変数最近実多項式算出装置であり、
上記f(x),e1(x),…,en(x)と、上記領域Ｄの境界Λを構成する有限個の区分境界Λ1,Λ2,…,ΛKとを記憶する記憶手段と、
上記境界Λ上の点αに対して、上記集合Ｆに属しこの点αを零点とする一変数実多項式のうち上記一変数実多項式f(x)に最も近い一変数実多項式g(x)と上記一変数実多項式f(x)との距離を与える関数Φ(α)を用いて、上記区分境界Λ1,Λ2,…,ΛKごとに前記関数Φ(α)の最小値を求める距離候補探索手段と、
上記距離候補探索手段によって得られた値のうち最小のものに対応する多項式を求める多項式算出手段と
を備えた一変数最近実多項式算出装置。
【請求項９】
Ｒを実数全体の集合とし、f(x),e1(x),…,en(x)をそれぞれ予め与えられた一変数実多項式とし、二つの一変数実多項式の距離をｌ∞-ノルムで定義し、一変数実多項式f(x)が複素数全体の集合内の閉な領域Ｄに零点を持たないとして、
一変数実多項式の集合
【数１９】
2009271888.tif 000108
に属する一変数実多項式であって、上記領域Ｄに零点を持ち、かつ、上記一変数実多項式f(x)に最も近い一変数実多項式f~(x)を算出する一変数最近実多項式算出方法であり、
記憶手段には、上記f(x),e1(x),…,en(x)と、上記領域Ｄの境界Λを構成する有限個の区分境界Λ1,Λ2,…,ΛKとが記憶されており、
距離候補探索手段が、上記境界Λ上の点αに対して、上記集合Ｆに属しこの点αを零点とする一変数実多項式のうち上記一変数実多項式f(x)に最も近い一変数実多項式g(x)と上記一変数実多項式f(x)との距離を与える関数Φ(α)を用いて、上記区分境界Λ1,Λ2,…,ΛKごとに前記関数Φ(α)の最小値を求める距離候補探索ステップと、
多項式算出手段が、上記距離候補探索ステップにおいて得られた値のうち最小のものに対応する多項式を求める多項式算出ステップと
を有する一変数最近実多項式算出方法。
【請求項１０】
コンピュータに請求項７に記載された多項式間距離算出方法の各処理を実行させるためのプログラム、または／および、コンピュータに請求項９に記載された一変数最近実多項式算出方法の各処理を実行させるためのプログラムを記録した、コンピュータに読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複素数全体の集合内の指定された領域に零点を持つ一変数実多項式のうち、上記領域に零点を持たない或る一変数実多項式ｆに最も近い一変数実多項式ｆ~について、一変数実多項式ｆと一変数実多項式ｆ~との距離を求める技術に関する。
【背景技術】
【０００２】
f(x),e1(x),e2(x),…,en(x)は、それぞれ予め与えられた一変数実多項式〔係数が実数の一変数多項式〕であるとする。但し、実数全体の集合をＲと表記すると、e1(x),e2(x),…,en(x)はＲ上一次独立とする。つまり、実数c1,c2,…,cnに対して、c1e1(x)+c2e2(x)+…+cnen(x)が恒等的に０となるのは、c1=c2=…=cn=0の場合に限られるとする。また、複素数全体の集合をＣと表記する。
【０００３】
このとき、次の問題☆を考える。なお、この明細書中において記号~は直前の文字の頭上に附されるものとする。
［問題☆］
一変数実多項式f(x)がＣ内の予め与えられた領域Ｄに零点を持たないとする。このとき、式（１）で表される一変数実多項式の集合Ｆのうち、領域Ｄに零点を持ち、かつ、一変数実多項式f(x)に最も近い一変数実多項式f~(x)について、一変数実多項式f(x)と一変数実多項式f~(x)との距離を求めよ。また、このような一変数実多項式f~(x)を一つ求めよ。
【数２０】
2009271888.tif 000003
【０００４】
但し、二つの一変数実多項式g,hの距離d(g,h)は、g-hの係数のｌ∞-ノルム〔最大値ノルム〕で定義する。即ち、式（２）で表される二つの一変数実多項式g,hの距離d(g,h)は、max{|a1-b1|,|a2-b2|,…,|an-bn|}で与えられる。max{|a1-b1|,|a2-b2|,…,|an-bn|}は、集合｛|a1-b1|,|a2-b2|,…,|an-bn|｝の元のうち最大の元を表す。また、この明細書では、g-hの係数のｌ∞-ノルムを‖g-h‖∞とも表記する場合がある。
【数２１】
2009271888.tif 000004
【０００５】
なお、多項式の表記に際して変数ｘを明記したい場合にはf(x),g(x)の如く表すこととし、それ以外の場合には、単にf,gの如く表すこととする。また、特に断りの無い限り、「一変数実多項式」を「多項式」と略記する。
【０００６】
上記問題☆を考えることには、実用上の利益がある。例えばディジタル信号処理やシステム制御のような伝達関数による制御などにおいて、所望の特性を得るために、領域Ｄに零点を持たないように多項式の係数を設定したい場合がある。しかし、係数は有限の精度でしか指定できないため、その設定には一般的に誤差を伴う。そこで、所望の領域Ｄに零点を確実に持たないように多項式の係数を設定するには、係数設定に誤差を伴うことを前提として、誤差範囲内のどのような多項式であっても間違いなく領域Ｄに零点を持たないようにすることが望まれる。そこで、上記問題☆を解決する必要がある。視点を変えて説明すると、このことは、領域Ｄに零点を持たないことが既知である多項式ｆの「領域Ｄに零点を持たない」という性質を保ったまま多項式ｆの係数を動かすときのその限界を求めることであり、このような限界は、多項式ｆとこれに最も近い多項式ｆ~との距離〔ｌ∞-ノルム〕として与えられる。
【０００７】
上記問題☆に関連して、非特許文献１が挙げられる。この非特許文献１では、与えられた複素数γを零点とする複素係数多項式に対して、上記問題☆に類似する問題を扱っている。なお、非特許文献１は複素係数多項式を取り上げているが、非特許文献１中に示唆されているように、実係数多項式（実多項式）の場合にも適用できるように体系化できる。
上記問題☆と非特許文献１が取り上げている問題との違いは、上記問題☆が与えられた領域に零点を持つ多項式を対象としていることに対して、非特許文献１が取り上げている問題は与えられた一点を零点とする多項式を対象として距離最小のものを求める点にある。
【０００８】
零点の存在場所が一点ではなく領域となっている問題を扱った研究として、非特許文献２が挙げられる。
この非特許文献２では、距離を上記の如くｌ∞-ノルムとして問題を解く場合には、領域ではなく一点に零点を持つ場合に限定している。また、零点の存在場所が領域の場合について問題を解く場合には、二つの多項式f(x)とg(x)との間の距離をｌ２-ノルム、即ち、f(x)-g(x)の係数から決まるベクトルのｌ２-ノルム ((a1-b1)2+…+(an-bn)2)1/2で定義した場合にのみ解決している。
【０００９】
二つの多項式f(x)とg(x)間の距離をｌ∞-ノルムで定義して上記問題☆を扱った研究として非特許文献３が挙げられる。以下、非特許文献３の内容について概説する。
【００１０】
まず、以下の条件を仮定する。
〈１〉領域Ｄは閉集合である複素領域である。
〈２〉領域Ｄの境界Λは長さが有限な単純閉曲線であり、一つ以上の有限個の区分境界Λkの和集合として表現される。即ち、境界Λは、Λ＝∪μ=1KΛμ＝Λ1∪Λ2∪・・・∪ΛK（整数Kは１≦K＜∞を満たす。）且つ、Λj∩Λk＝φ（j≠k）と表現される。但し、φは空集合を表す。また、各区分境界Λμは、単射のγμによって、
γμ： Ｉμ  →  Λμ
と表示される。ここでγμは有理式であって、分母・分子の多項式の係数は実代数的数a,bおよび虚数単位iを用いてa+biと表現されるものに限る。Ｉμ⊂Ｒは、α,βを実代数的数として［α，β］、［α，∞）、（−∞，β］、（−∞，∞）のいずれかであるとする。
【００１１】
このとき距離最小の多項式ｆ~＝ｆ＋Σj=1ｎｔｊｅｊについて、以下の性質が成り立つ。
[性質１]  少なくとも一つの零点は領域Ｄの境界Λ上に存在する。より詳細には、多項式ｆ~がゼロ多項式の場合を除くと、多項式ｆ~の領域Ｄ上の全ての零点は領域Ｄの境界Λ上に在る。
[性質２]  高々一つの例外の係数を除き、|tj|=d(f,f~)が成り立つ。
【００１２】
よって、以下の二つの場合に分けて上記問題☆を扱う。
≪第一の場合≫全てのｊに対して、|tj|=d(f,f~)が成り立つ場合。
≪第二の場合≫|tμ|<d(f,f~)となるμが存在する場合。
【００１３】
≪第一の場合≫では、ｘとｔｊに関する連立方程式（３）をｘ∈Λかつｔ１，…，ｔｎ∈Ｒという条件の下で解き、解の中で|t1|=…=|tn|が最小となるものが最小距離であり、それに対応する多項式が、‖f-f~‖∞が最小となる多項式ｆ~である。上記条件を満たす解が無い場合は、式（１）で表される集合Ｆに属する多項式であって≪第一の場合≫の条件を満たし且つ領域Ｄに零点を持つ多項式は存在しない。
【数２２】
2009271888.tif 000005
【００１４】
≪第二の場合≫では、μと異なる番号ｊについては|tj|=d(f,f~)であるから、連立方程式（４）をｘ∈Λかつｔ１，…，ｔｎ∈Ｒという条件の下で解き、解の中で|t1|=…=|tμ-1|=|tμ+1|=|tn|が最小となるものが最小距離であり、それに対応する多項式が、‖f-f~‖∞が最小となる多項式ｆ~である。上記条件を満す解が無い場合は、式（１）で表される集合Ｆに属する多項式であって≪第二の場合≫の条件を満たし且つ領域Ｄに零点を持つ多項式は存在しない。
【数２３】
2009271888.tif 000006
【非特許文献１】H. J. Stetter, "The Nearest Polynomial with a Given Zero, and Similar Problems," ACM SIGSAM Bulletin, Vol.33, No.4, pp.2-4, 1999.
【非特許文献２】M. A. Hitz and E. Kaltofen, "Efficient algorithms for computing the nearest polynomial with constrained roots," Proc. 1998 International Symposium on Symbolic and Algebraic Computation (ISSAC98), pp.236-243, 1998.
【非特許文献３】H.Sekigawa, "The Nearest Polynomial with a Zero in a Given Domain," Proc. International Workshop on Symbolic Numeric Computation 2007（SNC2007), pp.190-196, 2007.
【発明の開示】
【発明が解決しようとする課題】
【００１５】
上記非特許文献１の手法によれば、与えられた多項式に最も近い、与えられた一点を零点とする多項式を求めることはできる。しかし、与えられた「一点」を「領域」とした上記問題☆に上記非特許文献１の手法を適用できない。
【００１６】
また、上記非特許文献２の手法では、ｌ∞-ノルムで距離をはかる場合、過剰決定の連立一次方程式の近似解を求める手法を利用している。これを零点の存在場所が領域の場合に拡張することは、非特許文献２に述べられているとおり、困難である。また、ｌ２-ノルムで距離をはかる場合には、零点の存在場所が領域の場合も扱えるが、ｌ２-ノルムに特化した手法であるため、ｌ∞-ノルムで距離をはかる場合には上記非特許文献２の手法を用いることができない。つまり、上記非特許文献２の手法では、上記問題☆に回答を与えることができない。
【００１７】
上記非特許文献３の手法では、最悪の場合、解く必要のある方程式の数が、ｅｊの個数ｎを指数とする指数関数で表現されるオーダーの個数となる。
【００１８】
上記≪第一の場合≫では、連立方程式（３）がｘ∈Λかつｔ１，…，ｔｎ∈Ｒという解を持つことは、方程式（５）のうち少なくとも一つの方程式がｘ∈Λかつｔ∈Ｒという解を持つことと同値である。ここで、±は、＋と−の全ての組み合わせを取るので、組み合わせは全部で２ｎ−１通りである。即ち、最悪の場合、２ｎ−１本の方程式を解く必要がある。
f(x)+t(e1(x)±e2(x)±…±en(x))=0      （５）
【００１９】
また、上記≪第二の場合≫では、連立方程式（４）がｘ∈Λかつｔ１，…，ｔｎ∈Ｒという解を持つことは、方程式（６）のうちの少なくとも一つの方程式がｘ∈Λ，ｔμ，ｔ∈Ｒ，|tμ|<|t|という解を持つことと同値である。ここで、±は、＋と−の全ての組み合わせを取るので、組み合わせは全部で２ｎ−２通りである。μの選び方がｎ通りあるので、最悪の場合、２ｎ−２・ｎ本の方程式を解く必要がある。
f(x)+tμeμ(x)+t(e1(x)±…±eμ-1(x)±eμ+1(x)±…±en(x))=0      （６）
【００２０】
従って、ｅｊの個数ｎが多い場合に、非特許文献３の手法が現実的であるとは言い難い。
【００２１】
そこで本発明は、複素数全体の集合内の指定された領域Ｄに零点を持つ一変数実多項式のうち、領域Ｄに零点を持たない或る一変数実多項式ｆに最も近い一変数実多項式ｆ~と、一変数実多項式ｆとのｌ∞-ノルムで定義された距離を、最悪の場合であっても多項式時間の計算量で求める、多項式間距離算出装置、方法および記録媒体、さらに、一変数実多項式ｆ~を求める、一変数最近実多項式算出装置、方法および記録媒体、提供することを目的とする。
【課題を解決するための手段】
【００２２】
上記課題を解決するために、本発明では、Ｒを実数全体の集合とし、f(x),e1(x),…,en(x)をそれぞれ予め与えられた一変数実多項式とし、二つの一変数実多項式の距離をｌ∞-ノルムで定義し、一変数実多項式f(x)が複素数全体の集合内の閉な領域Ｄに零点を持たないとして、一変数実多項式の集合
【数２４】
2009271888.tif 000007
に属する一変数実多項式であって、領域Ｄに零点を持ち、かつ、一変数実多項式f(x)に最も近い一変数実多項式f~(x)について、一変数実多項式f(x)と一変数実多項式f~(x)との距離を以下のとおり算出する。
一変数実多項式f(x),e1(x),…,en(x)と、領域Ｄの境界Λを構成する有限個の区分境界Λ1,Λ2,…,ΛKとが記憶手段に記憶されており、境界Λ上の点αに対して、集合Ｆに属しこの点αを零点とする一変数実多項式のうち一変数実多項式f(x)に最も近い一変数実多項式g(x)と一変数実多項式f(x)との距離を与える関数Φ(α)を用いて、区分境界Λ1,Λ2,…,ΛKごとに関数Φ(α)の最小値を求め（距離候補探索）、この距離候補探索で得られた値のうち最小のものを求める（最小距離算出）。
詳細な理論は後述するが、一変数実多項式f~(x)の領域Ｄ上の零点は領域Ｄの境界Λ上にのみ存在するので、点αを境界Λ上で動かしたときの関数Φ(α)の最小値が最小距離となる。
【００２３】
ここで関数Φ(α)を次のとおりとすればよい。複素数の実部と虚部をそれぞれＲｅ，Ｉｍで表すとして、複素数ｕ，ｖに対する行列式
【数２５】
2009271888.tif 000008
を定義し、ｉを虚数単位とし、
［１］１≦ｊ＜ｋ≦ｎなる全てのｊ，ｋに対してA(ej(α),ek(α))=0が成立し、かつ、A(ej(α),f(α))=0がｊ＝１，…，ｎに対して成立ち、かつ、ｅｊ(α)≠０となるｊが存在する場合に、関数Φ(α)は、
【数２６】
2009271888.tif 000009
であり、
［２］或るｊ，ｋ（１≦ｊ＜ｋ≦ｎ）に対してA(ej(α),ek(α))≠0が成立する場合に、関数Φ(α)は、
【数２７】
2009271888.tif 000010
（但し、分母が０となるものは除く。）であるとする。
【００２４】
上記距離候補探索では、各区分境界Λμ（但しμ=1,2,…,K）が点であるか否かを判定する区分境界点判定を行うことができる。この場合、距離候補探索では、区分境界Λμが点であると判定されなかった場合に、上記［１］の場合を、少なくとも一つのｊについてA(ej(α),if(α))=0が成立する場合Ｓ１とそれ以外の場合Ｓ２に分け、上記［２］の場合を、少なくとも一つのｊについてA(ej(α),f(α))=0または１≦ｊ＜ｋ≦ｎなるｊ，ｋに対してA(ej(α),ek(α))=0が成立する場合Ｓ３とそれ以外の場合Ｓ４に分け、当該区分境界Λμでの関数Φ(α)の最小値を、各場合Ｓ１〜Ｓ４の関数Φ(α)の各最小値のうち最小のものとする。この理論的な詳細は後述する。
【００２５】
また、各区分境界Λμ（但しμ=1,2,…,K）が、実数上の集合Ｉμに対する有理式で表される単射γμ(s) （但しｓ∈Ｉμ）で与えられるとし、集合Δμを
【数２８】
2009271888.tif 000011
とし、集合Δ~μ⊂Δμを
【数２９】
2009271888.tif 000012
とし、集合Ｚ~μ⊂Δ~μを
【数３０】
2009271888.tif 000013
とし、集合Ｚμ⊂Δμを
【数３１】
2009271888.tif 000014
とし、区分境界Λμに対応する関数Φ(α)を
【数３２】
2009271888.tif 000015
で表すとして、上記距離候補探索では、上記区分境界点判定で点であると判定された区分境界Λμについて、実数上の集合Ｉμ（＝｛δ｝）が集合Ｉμ＼Δμに属する場合に、当該区分境界Λμでの関数Φμ(s)の最小値を、
【数３３】
2009271888.tif 000016
で求め、実数上の集合Ｉμ（＝｛δ｝）が上記集合Δ~μに属する場合に、当該区分境界Λμでの関数Φμ(s)の最小値を、
【数３４】
2009271888.tif 000017
で求める第一距離候補探索と、上記区分境界点判定で点であると判定されなかった区分境界Λμについて、上記Ｓ１の場合に上記集合Ｚ~μの有限個の元σについて、ｍμ，１を
【数３５】
2009271888.tif 000018
で求め、上記Ｓ２の場合に有限個の区間の和集合で表される集合Δ~μ＼Ｚ~μに属する元σについて，ｍμ，３を
【数３６】
2009271888.tif 000019
で求め、上記Ｓ３の場合に上記集合Ｚμの有限個の元σについて、ｍμ，２を
【数３７】
2009271888.tif 000020
で求め、上記Ｓ４の場合に有限個の区間の和集合で表される集合（Ｉμ＼Δμ）＼Ｚμに属する元σについて，ｍμ，４を
【数３８】
2009271888.tif 000021
で求め、当該区分境界Λμでの関数Φμ(s)の最小値をmin{mμ,1,mμ,2,mμ,3,mμ,4}で求める第二距離候補探索とを含むことができる。この理論的な詳細は後述する。
【００２６】
また、本発明では、領域Ｄが非有界の場合には、集合Ｆの次数が一定であることが要求される。そこで、領域Ｄが有界であるか否かを判定する領域有界判定と、領域Ｄが有界でない場合に、集合Ｆの次数が一定であるか否かを判定する次数判定とを行うようにしてもよい。
【００２７】
また、多項式
【数３９】
2009271888.tif 000022
が恒等的に０となる実数a1,a2,…,anが存在するか否かを判定し、存在する場合には一変数実多項式f(x)と恒等的に０の多項式との距離を求める恒等式調査を行う場合には、上記最小距離算出に代えて、距離候補探索で得られた値および恒等式調査で得られた距離のうち最小のものを求める第二最小距離算出を行うようにすることができる。
これにより、恒等的に０の多項式との距離についても考慮を要求する場合の最小距離を求めることができる。この理論的な詳細は後述する。
【００２８】
また、詳しい理論は後述するが、後述する命題、補題、定理などに基づき、最小距離が求められると一変数実多項式ｆ~も求められる。
【００２９】
また、本発明の多項式間距離算出装置としてコンピュータを機能させる多項式間距離算出プログラムによって、コンピュータを多項式間距離算出装置として作動処理させることができるところ、このようなプログラムを記録した、コンピュータによって読み取り可能なプログラム記録媒体によって、他のコンピュータを多項式間距離算出装置として機能させることや、プログラムを流通させることなどが可能になる。
【００３０】
同様に、本発明の一変数最近実多項式算出装置としてコンピュータを機能させる一変数最近実多項式算出プログラムによって、コンピュータを一変数最近実多項式算出装置として作動処理させることができるところ、このようなプログラムを記録した、コンピュータによって読み取り可能なプログラム記録媒体によって、他のコンピュータを一変数最近実多項式算出装置として機能させることや、プログラムを流通させることなどが可能になる。
【００３１】
なお、一つの記録媒体に、これらのプログラムを記録することができる。
【発明の効果】
【００３２】
上記非特許文献３の手法では、多項式間距離を変数として、最小距離が満たす代数方程式を導出することで、最小の多項式間距離を算出するため、最悪の場合に、解く必要のある方程式の数が、ｅｊの個数ｎを指数とする指数関数で表現されるオーダーの個数となる。これに対して本発明によれば、境界Λ上の点αに対して、集合Ｆに属しこの点αを零点とする一変数実多項式のうち一変数実多項式f(x)に最も近い一変数実多項式g(x)と一変数実多項式f(x)との距離を与える関数Φ(α)を用いて、区分境界Λ1,Λ2,…,ΛKごとに関数Φ(α)の最小値を求めることで、最悪の場合であっても多項式時間の計算量で最小距離を求めることが可能になっている。事実、詳細は後述するが、解く必要のある方程式の数が一変数実多項式ｅｊの個数ｎの多項式のオーダーで収まる演算で求めるアルゴリズムが存在する。また、最小距離が求まると、後述の補題等により一変数実多項式ｆ~も求めることができる。
【発明を実施するための最良の形態】
【００３３】
[理論]
本発明の実施形態の説明に先立ち、本発明の理論について説明する。
まず、本発明では、複素数全体の集合Ｃ内の予め与えられた領域Ｄを閉な複素領域とし、領域Ｄの境界Λは一定の条件が課された有限の長さの単純閉曲線とする。
即ち、本発明の解決すべき問題は、次のとおりである。
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
≪問題≫
[条件]
〈１〉 f(x),e1(x),e2(x),…,en(x)は、それぞれ予め与えられた一変数実多項式であるとする。但し、実数全体の集合Ｒについて、e1(x),e2(x),…,en(x)はＲ上一次独立とする。
〈２〉 一変数実多項式f(x)が複素数全体の集合Ｃ内の予め与えられた領域Ｄに零点を持たないとする。但し、領域Ｄは閉な複素領域であり、領域Ｄの境界Λは有限の長さの単純閉曲線とする。
〈３〉 境界Λは、一つ以上の有限個の区分境界Λμの和集合として表現される。即ち、境界Λは、Λ＝∪μ=1KΛμ＝Λ1∪Λ2∪・・・∪ΛK（整数Kは１≦K＜∞を満たす。）且つ、Λj∩Λk＝φ（j≠k）と表現される。但し、φは空集合を表す。また、各区分境界Λμは、単射のγμによって、
γμ： Iμ  →  Λμ
と表示される。ここでγμは有理式であって、分母・分子の多項式の係数は実代数的数a,bおよび虚数単位iを用いてa+biと表現されるものに限る。Iμ⊂Ｒは、α,βを実代数的数として［α，β］、［α，∞）、（−∞，β］、（−∞，∞）のいずれかであるとする。
〈４〉 二つの一変数実多項式g,hの距離d(g,h)は、g-hの係数のｌ∞-ノルムで定義する。
〈５〉 領域Ｄが非有界の場合、式（７）で表される一変数実多項式の集合Ｆの次数は、ajに拠らず一定である。
〈６〉 ｎを１以上の正整数とする。但し、ｎを正の無限大であるとはしない。即ち、一変数実多項式e1(x),e2(x),…,en(x)の個数（ｎ個）を有限とする。
上記条件の下、式（７）で表される一変数実多項式の集合Ｆに属する一変数実多項式のうち、領域Ｄに零点を持ち、かつ、一変数実多項式f(x)に最も近い一変数実多項式f~(x)について、一変数実多項式f(x)と一変数実多項式f~(x)との距離d(f,f~)を求めよ。また、このような一変数実多項式f~(x)を一つ求めよ。
【数４０】
2009271888.tif 000023
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
【００３４】
なお、従前同様に、多項式の表記に際して変数ｘを明記したい場合にはf(x),g(x)の如く表すこととし、それ以外の場合には、単にf,gの如く表すこととする。また、特に断りの無い限り、「一変数実多項式」を「多項式」と略記する。
【００３５】
また、多項式の係数は、理論上は実数としてよいが、コンピュータなどによる演算の上では四則演算および等号判定を有限ステップのアルゴリズムで実行できることが必要かつ十分であり、そのために例えば実代数的数（整数係数一変数代数方程式の根となる実数）とする。以降の説明では、説明の便宜から、多項式の係数は有理数であるとする。
【００３６】
条件〈２〉本文から、多項式f(x)は領域Ｄに零点を持たない。
もし、多項式f(x)が領域Ｄに零点を持たないことを確認する必要がある場合には、次のような処理を行えばよい。
【００３７】
〔多項式f(x)が領域Ｄに零点を持たないことの確認処理〕
領域Ｄ（境界Λ上およびその内部）に多項式f(x)の零点が存在するか否かの判定は、公知の手法によって達成される。
まず、領域Ｄの境界Λ上において多項式f(x)の零点が存在するか否かの判定を行う。例えば、領域Ｄの境界Λの表示を多項式f(x)に代入した後、Sturmの定理に基づくアルゴリズムに従って零点の有無を判定する。
【００３８】
ここでは説明の便宜から一例として、各区分境界Λkが、パラメータsおよびパラメータsを一変数とする有理式φk(s)、ψk(s)によってφk(s)+i・ψk(s)と表示されるとする〔k=1,2,…,K〕。ｉは、虚数単位を表す。ここで、有理式φk(s)、ψk(s)における係数は、上記同様に、理論上は実数としてよいが、コンピュータなどによる演算の上では四則演算および等号判定を有限ステップのアルゴリズムで実行できることが必要かつ十分であり、そのために例えば実代数的数（整数係数一変数代数方程式の根となる実数）とし、具体例として有理数であるとする。以下では、有理式φk(s)、ψk(s)を、有理数係数の有理式であるとして例示説明する。パラメータsの動く範囲Ｓkは、条件〈３〉に対応して［α，β］、［α，∞）、（−∞，β］、（−∞，∞）のいずれかであるとする。[・，・]は閉区間、（・，・］は左開右閉区間、［・，・）は左閉右開区間、（・，・）は開区間を表す。また、パラメータsと区分境界Λkとの間は単射である。
【００３９】
Strumの定理に基づくアルゴリズムの適用について説明する。各区分境界Λkについて同様の処理となるから、敢えて沿え字kを省略して説明する。
【００４０】
領域Ｄの区分境界Λの表示φ(s)+i・ψ(s)が代入された多項式f(φ(s)+i・ψ(s))は、有理数係数有理式ω(s)およびτ(s)によってf(φ(s)+i・ψ(s))=ω(s)+i・τ(s)と表示できる。ここで「多項式f(x)が、φ(s0)+i・ψ(s0)において０となる」ことと、「ω(s)およびτ(s)がs=s0で同時に０となる」ことは同値である。また、「ω(s)およびτ(s)がs=s0で同時に０となる」ことと、「ω(s)およびτ(s)をそれぞれ既約な有理数係数有理式として表したときの分子のＧＣＤ（最大公約多項式）がs0において０になる」ことは同値である。
【００４１】
従って、ω(s)およびτ(s)をそれぞれ既約な有理数係数有理式として表したときの分子のＧＣＤに対し、Strumの定理に基づくアルゴリズムを適用する。説明の便宜からω(s)およびτ(s)をそれぞれ既約な有理数係数有理式として表したときの分子のＧＣＤをH(s)とする。
【００４２】
このH(s)について、多項式の列H0(s),H1(s),H2(s),…,Hr(s)を生成する。但し、これらの多項式の列は、次の規則に従って生成する。H0(s)=H(s),H1(s)=dH(s)/ds〔ｓに関する１階微分である。ライプニッツ記法〕、Hj-1(s)をHj(s)で割った剰余多項式を（符号を変えて）-Hj+1(s)とする。つまり、商の多項式をQj(s)と表すと、Hj-1(s)=Hj(s)Qj(s)-Hj+1(s)の関係が成立する。また、Hr-1(s)は、Hr(s)で割り切れる。つまり、商の多項式をQr(s)と表すと、Hr-1(s)=Hr(s)Qr(s)の関係が成立する。このとき、区間Ｓ＝[ａ，ｂ]において、H0(a),H1(a),H2(a),…,Hr(a)における正負の符号変化の回数をw(a)で表し、H0(b),H1(b),H2(b),…,Hr(b)における正負の符号変化の回数をw(b)で表すとすると、区間Ｓ＝[ａ，ｂ]におけるH(s)の零点の個数は、w(a)-w(b)である。なお、ここでは、区間Ｓ＝[ａ，ｂ]のａ、ｂは共にH(s)の零点ではないとした（零点であれば、個数を表す式が少し変わるが、本発明においては本質的な部分ではないので略する。）。
【００４３】
w(a)-w(b)=0であればH(s)の零点が存在しないことが判明し、区分境界上で多項式f(x)の零点は存在しない。w(a)-w(b)≠0であればH(s)の零点が存在することが判明し、区分境界上で多項式f(x)の零点は存在する。全ての区分境界上でH(s)の零点の不存在を確認することで、領域Ｄの境界Λ上において多項式f(x)の零点が存在しないことが確認される。
【００４４】
なお、この判定ではSturmの定理によって、厳密には、区間（ａ，ｂ]に多項式f(x)の零点が存在するか否かを判定している。そこで、s＝ａがH(s)の零点であるか否かについては、f(s)=0の成立を判定すればよい。区間Ｓの端点が∞又は-∞で与えられる場合であっても、係数が確定している多項式f(x)は上記端点に近づいては零点を持たないから符号変化の回数が変わらず、上記アルゴリズムに従って判定することができる。
【００４５】
なお、Sturmの定理については、参考文献１を参照のこと。
（参考文献１）  高木貞治著、「代数学講義（改訂新版）」、共立出版、１９６５．
【００４６】
以上では、領域Ｄの境界Λ上において多項式f(x)の零点が存在するか否かの判定を、領域Ｄの境界Λの表示を多項式f(x)に代入した後、Sturmの定理に基づくアルゴリズムによって行うものとして説明した。しかし、Sturmの定理に基づくアルゴリズムに限定する趣旨ではない。要は、一変数実係数の代数方程式が或る実の区間に根を持つか否かの判定ができればよく、例えば参考文献２に示されるsign variation methodによってこれを判定するとしてもよい。
（参考文献２）  G. E. Collins and R. Loos, "Real zeros of polynomials", Computer Algebra, Symbolic and Algebraic Computation, (B. Buchberger, G. E. Collins and R. Loos(編)), pp.83-94, Springer-Verlag,1983.
【００４７】
もし、境界Λ上に多項式f(x)の零点が存在しなければ、領域Ｄの内部において多項式f(x)の零点が存在するか否かの判定を行う。この判定には偏角の原理を用いることで達成される。なお、偏角の原理に基づく判定においては、領域Ｄの境界Λ上に多項式f(x)の零点がないことが前提となるから、まず、境界Λ上での零点の有無を判定しておいたのである。
【００４８】
偏角の原理に基づくアルゴリズムの適用について説明する。
区分境界Λkの表示φk(s)+i・ψk(s)を多項式f(x)に代入する。このとき、f(x)=f(φk(s)+i・ψk(s))=u(φk(s),ψk(s))+i・v(φk(s),ψk(s))と表される。そこで、実部u(φ(s),ψ(s))と虚部v(φ(s),ψ(s))それぞれの実根をｓ∈Ｓにおいて求める。同様にして全ての区分境界について根を求め、これらの根を現れる順に並べたリストＳ１を作る。また、境界Λに囲まれた領域における根の計数用のリストＳ２を用意する（初期状態では、リストＳ２は空である。）。リストＳ１の先頭から順次に根を読み出すこととし、まず、先頭要素（根）Ａを取り出し、リストＳ２が空のリストであればそれをＳ２に書き込む。リストＳ２が空でないときは先頭要素（根）ＡとリストＳ２の先頭の要素（根）が共に実部の解であるか共に虚部の解であるかを判定し、この判定が真であればリストＳ２から先頭の要素（根）を取り除く。当該判定が偽であるときは先頭要素（根）ＡをリストＳ２の先頭に書き足す。この処理操作をリストＳ１の先頭から順次に根を読み出すことで行う。この結果、リストＳ２における要素（根）の個数の１／４が境界Λの内部に含まれる多項式f(x)の根の数になる。この数が０であれば、多項式f(x)の零点が領域Ｄの内部に存在しないことが判明し、この数が０でなければ、多項式f(x)の零点が領域Ｄの内部に存在することが判明する。
【００４９】
なお、偏角の原理を用いた多項式の零点の数え上げについては、参考文献３を参照のこと。
（参考文献３）  平野照比古著、「偏角の原理を用いた多項式の根の数え上げ」、数式処理、Vol.9, No.4, pp.34-35, 2003.
【００５０】
以上では、領域Ｄの内部において多項式f(x)の零点が存在するか否かの判定を偏角の原理に基づくアルゴリズムによって行うものとして説明した。しかし、要は、多項式f(x)が領域Ｄの内部に根を持つか否かの判定ができればよく、偏角の原理に基づくアルゴリズムに限定する趣旨ではない。
以上で〔多項式f(x)が領域Ｄに零点を持たないことの確認処理〕の説明は終わりである。
【００５１】
さて、条件〈６〉から、上記≪問題≫を《ｎ＝１の場合》と《ｎ≧２の場合》に分けて解答する。
【００５２】
《ｎ＝１の場合》
この場合、多項式f(x)+t1e1(x) (t1∈Ｒ)がｘ＝ｃ∈Ｄにおいて零点を持つ必要十分条件は、連立方程式（８）が点ｃを解とすることである。
【数４１】
2009271888.tif 000024
【００５３】
よって、行列式Re f(c) Im e1(c)−Im f(c) Re e1(c)は０である。これは、s0とs1を変数と見た連立方程式（９）が(s0,s1)=(1,t1)という(0,0)ではない解を持つことから云える。
【数４２】
2009271888.tif 000025
【００５４】
上記[性質１]または下記[命題]から、境界Λ上に距離最小の多項式の零点が存在する。よって、各μ（μ=1,2,…,K）に対して、区分境界の表示γμ(s)をｘに代入し、Re f(γμ(s)) Im e1(γμ(s))−Im f(γμ(s)) Re e1(γμ(s))が恒等的に０ではない場合には、Re f(γμ(s)) Im e1(γμ(s))−Im f(γμ(s)) Re e1(γμ(s))=0を解いて（根は有限個である。）、これらの有限個の根のうちσi(i=1,2,…)∈Iμについて連立方程式（８）を満たす実数解t1を求めればよい。実数解は、t1(i)=-f(γμ(σi))/e1(γμ(σi))である。
【００５５】
このとき、実数解t1が存在しない場合がある。例えば、f(x)=1,e1(x)=xで領域ＤがＲと共通部分を持たない場合である。このような場合、求めるべき多項式ｆ~は存在しない。
【００５６】
実数解t1が存在する場合、この段階で候補が有限個であるから、領域Ｄに零点を持たない多項式ｆに最も近い多項式ｆ~を求めることができる。求めるべき最小距離は|t1(i)| (i=1,2,…)のうち最小のものである。この最小距離をmini{|t1(i)|}と表記すると、求めるべき多項式ｆ~の一例は、f(x)±mini{|t1(i)|}e1(x)のうちいずれかである。
【００５７】
次に、Re f(x) Im e1(x)−Im f(x) Re e1(x)が恒等的に０である場合について考える。
ここで、Re e1(x)が恒等的に０とすると、e1(x)は定数となる（※１）。e1(x)は実多項式であるから、定数ならば実数であり、その実部が０ということはe1(x)がゼロ多項式であることを意味し、e1(x)が条件〈１〉の一次独立であることに矛盾する（ただ一つの元が一次独立であることは、それが０ではないことと同値である。）。故に、Re e1(x)は恒等的に０ではない。
【００５８】
Im e1(x)が恒等的に０である場合、e1(x)は定数となる（※１）。さらに、「Re f(x) Im e1(x)−Im f(x) Re e1(x)が恒等的に０である」から、Im f(x) Re e1(x)は恒等的に０となる。よって、Im f(x)は恒等的に０となる（※２）。よってf(x)は定数となる（※１）。このとき、実多項式f(x)，e1(x)がともに定数なので、それぞれ実数となり、ａ∈Ｒによってf/e1=aと書ける（上述のとおり多項式e1(x)は０ではない。）。つまり、f=a e1である。
【００５９】
Im e1(x)が恒等的に０ではない場合、「Re f(x) Im e1(x)−Im f(x) Re e1(x)が恒等的に０である」から、Re f(x)/Re e1(x)=Im f(x)/Im e1(x)となる。これをp(x)とおくと、p(x)はｘの値に拠らず実となる。また、Re f(x)=p(x)・Re e1(x)，Im f(x)=p(x)・Im e1(x)が成立する。ここで、f(x)=Re f(x)+i Im f(x)，e1(x)=Re e1(x)+i Im e1(x)であることに注意すると、p(x)=f(x)/e1(x)である。さて、p(x)はｘの値に拠らず実であるから、Im (f(x)/e1(x))は恒等的に０となる。よって、f(x)/e1(x)は定数となる（※１）。f(x)/e1(x)は実係数有理式であるから定数ならば実数である。故に、ａ∈Ｒによってf(x)/e1(x)=aと書ける。つまり、f(x)=a e1(x)である。
【００６０】
（※１）
h(x) （ｘ∈Ｃ）が正則関数のとき（多項式や有理式は正則関数である。）、h(x)の一次微分h'(x)は微分する方向に拠らない。もし、Re h(x)が常に０であるなら、つまりh(x)が常に純虚数なら、h'(x)=limc→0{h(x+c)-h(x)}/cにおいて、ｃを実数の範囲で０に近づけることによってh'(x)はxによらず純虚数となる。他方、h'(x)=limc→0{h(x+ic)-h(x)}/(ic)でもあるから、ｃを実数の範囲で０に近づけることによってh'(x)はxによらず実数となる。よって、h'(x)は常に純虚数かつ実数、つまり０である。故に、h(x)は定数となる。Im h(x)が常に０である、つまりh(x)が常に実数としても同様である。
以上で（※１）の説明を終わる。
【００６１】
（※２）
f(x)，e1(x)にx=u+ivを代入して展開すると、f(u+iv)=q1(u,v)+ir1(u,v)，e1(u+iv)=q2(u,v)+ir2(u,v)と書ける（q1，r1，q2，r2は実係数の多項式である。）。このとき、「Im f(x) Re e1(x)は恒等的に０」は、「r1(u,v)・q2(u,v)が恒等的に０」を意味する。上述のとおりq2(u,v)はゼロ多項式ではないからr1(u,v)がゼロ多項式、つまりIm f(x)は恒等的に０となる。
以上で（※２）の説明を終わる。
【００６２】
以上のことから、Re f(x) Im e1(x)−Im f(x) Re e1(x)が恒等的に０である場合、或るa∈Ｒによってf(x)=a e1(x)と書ける。よって、連立方程式（８）は、連立方程式（１０）と書ける。
【数４３】
2009271888.tif 000026
【００６３】
この連立方程式（１０）の実数解t1として、t1=-aの場合が考えられる。このとき、最小距離は|t1|であり、多項式f(x)+t1e1(x)は恒等的に０になる。つまり、求めるべき多項式ｆ~は、０〔ゼロ多項式〕である。
【００６４】
また、連立方程式（１０）の実数解t1として、t1≠-a且つRe e1(x)=Im e1(x)=0の場合が考えられる。これは多項式e1(x)が領域Ｄに零点を持つことを意味し、このとき、多項式f(x)=a e1(x)が実重複零点を持つことになり、条件に反する。よって、このような場合、求めるべき多項式ｆ~は存在しない。
以上で、《ｎ＝１の場合》の説明は終わりである。
【００６５】
《ｎ≧２の場合》
まず、下記の命題を証明する。これは上記[性質１]に相当し、多項式ｆに最も近い、即ち距離最小の多項式ｆ~が存在するならば、多項式ｆ~の零点は領域Ｄの境界Λ上にのみ存在することを保証する。
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
[命題]距離最小の多項式ｆ~が恒等的に０ではない場合、その領域Ｄ上の零点は、領域Ｄの境界Λ上にのみ存在する。
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
【００６６】
（証明）
中心をｚ∈Ｃ、半径をｒとする開円板をB(z;r)={w|w∈Ｃ,|z-w|<r}と書き、Ｘ⊂Ｃの内点の集合、すなわち、｛ｚ∈Ｘ｜あるｒ＞０が存在してＢ（ｚ；ｒ）⊂Ｘ｝をＸ°と表記する。
【００６７】
まず、次のことを示す。
『多項式f(x)が領域Ｄに零点を持たず、恒等的に０ではない多項式g(x)=f(x)+Σj=1nbjej(x) (bj∈Ｒ)が領域Ｄの内部Ｄ°に零点を持つとする。このとき、Ｄ°に零点を持ち、d(f,g~)＜d(f,g)を満たす恒等的に０ではない多項式g~(x)=f(x)+Σj=1nb~jej(x) (b~j∈Ｒ)が存在する。』・・・（★）
【００６８】
p(t,x)=f(x)+t(g(x)-f(x))とおく。このとき、p(0,x)=f(x),p(1,x)=g(x)であり、任意のt(0≦t≦1)に対して、p(t,x)は式（７）で表される集合Ｆに属する。つまり、p(t,x)∈Ｆである。
【００６９】
ζをＤ°に在る多項式ｇの零点とする。すると、条件「B(ζ;ε)⊂Ｄかつ、任意のξ∈B(ζ;ε),ξ≠ζに対して、g(ξ)≠0」を満たすε＞０が存在する。仮にこのようなεが存在しないとすると、多項式ｇが恒等的に０ではないことに矛盾する。
【００７０】
今、任意のt(0≦t≦1)に対して、p(t,x)がB(ζ;ε/2)の境界に零点を持たないと仮定する。すると、Roucheの定理により、B(ζ;ε/2)内に在るp(0,x) (=f(x))の零点の個数（０個）とp(1,x) (=g(x))の零点の個数（１個以上）が等しくなり矛盾する。従って、或る０＜τ＜１が存在してp(τ,x)はB(ζ;ε/2)の境界に零点を持つので、g~(x)としてp(τ,x)を採ればd(f,g~)=τd(f,g)<d(f,g)が成り立つ。
よって、題意★が示せた。
【００７１】
このとき、距離最小の多項式ｆ~の零点がＤ°に存在するとすると、Ｄ°に零点を持ち、d(f,g~)＜d(f,f~)を満たす多項式g~(x)=f(x)+Σj=1nb~jej(x) (b~j∈Ｒ)が存在することになり、多項式ｆ~が距離最小のときの多項式であることに矛盾する。よって、距離最小の多項式ｆ~の領域Ｄ上の零点は、領域Ｄの境界Λ上にのみ存在する。
以上により[命題]の証明は終了である。
（証明終）
【００７２】
次に、定理１を証明する。これは、式（７）に表される集合Ｆに属する多項式で領域Ｄに零点を持つものがあれば、その中で多項式ｆに最も近い多項式ｆ~が存在することを保証する。
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
[定理１]記号Ｆ，ｆ，ｄ，Ｄは上記の通りとする。もし、領域Ｄに零点を持つ多項式ｇ∈Ｆが存在するならば、領域Ｄに零点を持ち、かつ‖f-f~‖∞が最小となるようなｆ~∈Ｆが存在する。
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
【００７３】
（証明）
［領域Ｄが有界の場合］
G(z,t1,…,tn)を式（１１）で定義されるＣ×ＲｎからＣへの関数とする。
【数４４】
2009271888.tif 000027
【００７４】
すると、G-1(0)は、閉集合（一点０）の連続関数による逆像だから閉集合である。
【００７５】
以下、(t1,…,tn)∈Ｒｎとf(x)+Σj=1ntjej(x)∈Fを同一視する。また、集合Ａを次式（１２）のとおり定義する。ここで記号×は直積集合を表す。
【数４５】
2009271888.tif 000028
【００７６】
すると、集合Ａは、閉集合G-1(0)と有界な閉集合D×{h∈F|d(f,h)≦d(f,g)}との積集合だから、有界かつ閉であり、コンパクトとなる。
【００７７】
よって、集合Ａから実数集合Ｒへの連続関数（１３）は最小値を持つ。
【数４６】
2009271888.tif 000029
【００７８】
この最小値を（ζ，τ１，…，τｎ）∈Ａでとると仮定する。ｆ~をｆ~= f(x)+Σj=1nτjej(x)で定義すると、ｆ~∈Ｆ、ｆ~はζ∈Ｄを零点とし、d(f,f~)は最小となる。
【００７９】
［領域Ｄが非有界の場合］
集合Ｆに属する多項式の次数が等しいという条件〈５〉から、集合Ｆに属する多項式の最高次の係数は等しい。多項式ｆ~を探すには、‖f-h‖∞≦‖f-g‖∞を満たす多項式ｈのみを調べれば十分である。これら全ての多項式ｈの全ての零点を含むような、中心が０、半径がｒの閉円板を取ることができる。よって、有界な閉集合Ｄ∩｛ｚ∈Ｃ｜|z|≦ｒ｝を考えることで上記［領域Ｄが有界の場合］に帰着される。
以上により[定理１]の証明は終了である。
（証明終）
【００８０】
さて、次の定理２は、上記の定理１の「領域Ｄに零点を持つ多項式ｇ∈Ｆが存在する」という条件が、或る場合は自動的に満たされることを示すものである。
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
[定理２]記号ｆ，ｅｊ(ｊ＝１，…，ｎ），Ｄ，Ｆは上記の通りとする。ｎ≧２のとき、集合Ｆに属する多項式で領域Ｄに零点を持つものが存在する。
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
【００８１】
（証明）
ｎ＝２の場合に証明すれば十分である。
条件〈１〉から多項式ｅ１と多項式ｅ２の両方が定数であることはない。そこで必要であれば添字を付け換えて、多項式ｅ１が定数でないとする。e1(z)=0となるｚは有限個である。よって、ａ∈Ｄ°でe1(a)≠0となるものが存在する。ここで多項式ｅ１は連続であるから、点ａを含む十分に小さい開集合Ｕ⊂Ｄであって、０∈/ｅ１(Ｕ）となるものが存在する（つまり、∃Ｕ⊂Ｄ，∀p∈Ｕ°，e1(p)≠0）。ここで記号「∈/」は、「集合に属さない」を意味する。
【００８２】
e2/e1による開集合Ｕの像は複素平面上の空ではない開集合であり（正則関数の性質）、複素平面上でＲの部分集合となる開集合は空集合のみであるから、e2(α)/e1(α)∈/Ｒとなるα∈Ｕが存在する。
【００８３】
よって、e1(α)とe2(α)はＲ上一次独立となる。従って、-f(α)=c1e1(α)+c2e2(α)となるｃ１，ｃ２∈Ｒが存在する。即ち、f(α)+c1e1(α)+c2e2(α)=0である。
以上により[定理２]の証明は終了である。
（証明終）
【００８４】
続いて、下記の補題１は、最小距離を算出する上で重要な役割を果たすものである。
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
[補題１]記号ｆ，ｅｉは上記の通りとする。また、一変数実多項式の集合Ｆεを式（１４）で与える。但し、０≦εとする。
【数４７】
2009271888.tif 000030
このとき、点α∈Ｃを零点とする多項式ｇ∈Ｆεが存在する必要十分条件は以下の通りである。
［１］0，e1(α)，…，en(α)が一直線上にあるとき、必要十分条件は、f(α)がその直線上にあり、かつ、不等式（１５）が成立することである。
【数４８】
2009271888.tif 000031
［２］0，e1(α)，…，en(α)が一直線上にはないとき、必要十分条件は、ｉ＝１，…，ｎに対して不等式（１６）が成立することである。
【数４９】
2009271888.tif 000032
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
【００８５】
（証明）
集合Ｆεに属する多項式ｇが存在して点α∈Ｃが多項式ｇの零点となる必要十分条件は、０が式（１７）で与えられる集合に属することである。
【数５０】
2009271888.tif 000033
【００８６】
ここで、式（１８）を定義する。
【数５１】
2009271888.tif 000034
【００８７】
このとき、式（１７）で与えられる集合は、式（１９）による表現に書き改められる。
【数５２】
2009271888.tif 000035
【００８８】
〔式（１９）の解説〕
式（１４）から、係数biは閉区間［−ε，ε］で表される区間数であり、閉区間［−ε，ε］は、パラメータｔｉ（０≦ｔｉ≦１）を用いて｛２εｔｉ−ε｝と表記することができる。パラメータｔｉは、閉区間の両端点−ε、εの内分比を表す。このとき、集合Ｆεは、上記区間数｛２εｔｉ−ε｝を各項の係数として式（２０）のように表現される。
【数５３】
2009271888.tif 000036
【００８９】
このとき、「点αを零点とする多項式が集合Ｆεに存在するか否か」は、「連立方程式（２１）を満足するｔｉ（i=1,2,…,n）の組み合わせが存在するか否か」と同値である。また、連立方程式（２１）を書き改めると、連立方程式（２２）と表せる。
【数５４】
2009271888.tif 000037
【００９０】
つまり、連立方程式（２２）を満足するｔｉの組み合わせが存在するならば、それは、この点αを零点とする多項式が集合Ｆεに存在することを意味する。ここで留意しなければならないのは、ｔｉの組み合わせを特定することではなく、「連立方程式（２２）を満足するｔｉの組み合わせが存在するか否か」である。ここで説明の便宜から、（Reei(α) Imei(α)）ＴをＢｉと表記する。そうすると、Ｂｉは、複素平面において、原点を始点、（Reei(α),Imei(α)）を終点とする位置ベクトルとみることができる。
【００９１】
そうすると、式（２２）左辺について２εｔｉＢｉを、「Ｂｉを２ε倍した位置ベクトル２εＢｉを、ｔｉによってスカラー倍したものである」と見れば、０≦ｔｉ≦１によって式（２２）の左辺が取り得る平面上の範囲に、式（２２）の右辺の点が存在するか否かを調べればよい。つまり、凸多角形に或る１点が存在するか否かの判定に持ち込むことを考えればよい。そこで、このような凸多角形を用いた判定を効率良く行うために、前処理を行う。
【００９２】
まず、式（２２）の左辺の各項（ｉ＝１，…，ｎ）を順番に見ていき、各項について次のような判定と書き換えを行う。まず、２εＢｉの実部〔つまり、２εＲｅｅｉ(α)である。〕が負であるかを判定する。負である場合には、２εｔｉＢｉを２ε（１−ｔｉ）Ｂｉに書き換える。次に、２εＢｉの実部が負でない場合は、２εＢｉの実部が０かつ虚部〔つまり、２εＩｍｅｉ(α)である。〕が負であるか否かを判定する。実部が０かつ虚部が負である場合には、２εｔｉＢｉを２ε（１−ｔｉ）Ｂｉに書き換える。
なお、この操作は式（２１）において、２εＢｉの実部が負である場合に｛２εｔｉ−ε｝Ｂｉを｛２ε（１−ｔｉ）−ε｝Ｂｉ、即ち｛２εｔｉ−ε｝（−Ｂｉ）と書き換え、２εＢｉの実部が０かつ虚部が負である場合に｛２εｔｉ−ε｝Ｂｉを｛２ε（１−ｔｉ）−ε｝Ｂｉ、即ち｛２εｔｉ−ε｝（−Ｂｉ）と書き換えることと同じである。式（２１）でこの書換え処理を施したものの左辺を、実部と虚部に分けずに表現したものが式（１９）である。
【００９３】
以上の操作は、例えば、実部が負である位置ベクトル２εＢｉをｔｉスカラー倍（０≦ｔｉ≦１）することは、平面原点対象に移動した位置ベクトル２ε×（−１）×Ｂｉをｋｉスカラー倍（−１≦ｋｉ≦０）することと同じであるから、ｔｉの範囲が０≦ｔｉ≦１であることに留意してｋｉ＝ｔｉ−１とおくと、２ε×（−１）×ｋｉ×Ｂｉは、２ε×（１−ｔｉ）×Ｂｉとなることに基づく。このような操作を行うことで、式（２２）の左辺の点２εＢｉは、見かけ上、全て平面の右半平面（実部が０以上の領域全体、但し、実部が０かつ虚部が負の部分は除く。）に集められるとともに、平面の虚軸の負の部分には点が乗らないものとなる。換言すれば、この操作の結果得られた点集合は、平面原点を頂点とする凸多角形を平面の右半平面で構成する（但し、平面の虚軸の負の部分に凸多角形の頂点はない。）。
【００９４】
なお、このような操作は、凸多角形を求めるための便宜としての前処理であるから、上記処理に限定されるものではない。例えば、２εＢｉの実部が正であるかを判定し、正である場合には、２εｔｉＢｉを２ε（１−ｔｉ）Ｂｉに書き換え、２εＢｉの実部が正でない場合は、２εＢｉの実部が０かつ虚部が負であるか否かを判定する。そして、実部が０かつ虚部が負である場合には、２εｔｉＢｉを２ε（１−ｔｉ）Ｂｉに書き換える（つまり、平面原点を頂点とする凸多角形を平面左側で構成する。）、といった操作などに適宜に変更できる。
以上で〔式（１９）の解説〕の説明は終わりである。
【００９５】
さて、式（１９）の第３項で表現される集合、即ち式（２３）で表現される集合は、平面上で高々２ｎ個の点の凸包となる凸多角形となる〔参考文献４参照〕。
（参考文献４）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.
【数５５】
2009271888.tif 000038
【００９６】
そこで、この凸多角形の頂点を求める。これは、効率的に求めることができる。
具体的にはまず、平面の虚軸の負の部分を除く平面の右半平面の領域〔−π／２＜ａｒｇ≦π／２、ａｒｇは偏角を表す。〕において、ｅ＾ｉ(α)≠０を偏角〔ａｒｇ(e^i(α))＝arctan(Ime^i(α)/Ree^i(α))、但し、Ree^i(α)=0ならばarctan(Ime^i(α)/Ree^i(α))はπ／２とみなす。〕でソート（sort）する。つまり、位置ベクトルｅ＾ｉ(α)≠０が実軸となす角度ａｒｇ(e^i(α))を、−π／２＜ａｒｇ≦π／２で、小さい方から大きい方へと昇順に並び替える。但し、同じ傾きのものがあるときには、それらを全部足したものに置き換えたものを１つとしてソートする。例えば、ｅ＾ｊ(α)およびｅ＾ｋ(α)の傾きが同じときには、ｅ＾ｊ(α)，ｅ＾ｋ(α)の代わりに、ｅ＾ｊ(α)＋ｅ＾ｋ(α)を対象としてソートする。なぜなら、傾きが同じ位置ベクトルｅ＾ｊ(α)および位置ベクトルｅ＾ｋ(α)の各終点は平面上において凸包の頂点となりえないからである（凸包の頂点の可能性があるのは、同じ傾きのものを全てベクトル加算した点である。）。このソートの結果を位置ベクトルｐ１，・・・，ｐｍとする。なお、ｍはｎより小さいことがあることに留意すること。
【００９７】
このとき、求める平面上の凸包の頂点は、平面原点（０と表記する。）から始めて反時計回りに、０，ｐ１，ｐ１＋ｐ２，…，ｐ１＋…＋ｐｍ，ｐ２＋ｐ３＋…ｐｍ，ｐ３＋…＋ｐｍ，…，ｐｍ−１＋ｐｍ，ｐｍの全部で２ｍ個となる。
つまり、凸多角形の平面における頂点は、反時計回りに式（２４）で与えられる位置ベクトルｖｉ（０≦ｉ≦２ｍ−１）の終点として表される〔上記参考文献４参照。〕。
【数５６】
2009271888.tif 000039
【００９８】
従って、式（２５）で表現される凸多角形は、反時計回りに頂点εｗ０，εｗ１，・・・，εｗ２ｍ−１を持つ。但し、ｗｉ（０≦ｉ≦２ｍ−１）は式（２６）で与えられる〔∵Σi=1ne^i(α)=Σj=1mpj〕。
【数５７】
2009271888.tif 000040
【００９９】
式（２５）で表現される凸多角形では、全てのｅ＾ｉ(α)≠０について、ｅ＾ｉ(α)と平行な辺が丁度二つ存在し、全ての辺について、辺に平行なｅ＾ｉ(α)を少なくとも一つ存在する。そこで、ｅ＾ｉ(α)≠０について、ｅ＾ｉ(α)と平行な両端点をεｗｊ，εｗｊ＋１とする辺を考える。但し、ｊは最小のものを選択する。頂点を識別するｊはｅ＾ｉ(α)を識別するｉに依存するから、ｊ＝ν(ｉ)と書く。さらに、u=(Re u Im u)Ｔおよびv=(Re v Im v)Ｔに対する行列式（２７）をA(u,v)と表記することにする。
【数５８】
2009271888.tif 000041
【０１００】
さて、ｅ＾ｉ(α)と平行な二つの辺を含む直線は、式（２８）で表される。但し、z=(Re z Im z)Ｔである。
【数５９】
2009271888.tif 000042
【０１０１】
式（２８）は、式（２９）に等価である。
【数６０】
2009271888.tif 000043
【０１０２】
原点は式（２５）で表現される凸多角形に属するから、この凸多角形は、全てのｉ＝１，２，・・・，ｎに対して不等式（３０）を満たす位置ベクトルｚの終点集合と云うことができる。但し、凸多角形が線分に退化している場合、即ちｉ＝１，２，・・・，ｎに対して不等式（３０）の右辺が０となる場合には、この凸多角形は、不等式（３０）に加えて不等式（３１）を満たす位置ベクトルｚの終点集合と云うことができる。
【数６１】
2009271888.tif 000044
【０１０３】
さて、原点が式（１９）で与えられる集合に属することの必要十分条件は、（-Ref(α) -Imf(α)）Ｔが式（２５）で与えられる凸多角形に属することである。|A(e^i(α),-f(α))|=|A(e^i(α),f(α))|および|-f(α))|=|f(α))|が成立することに注意すれば、点α∈Ｃを零点とする多項式ｇ∈Ｆεが存在することの必要十分条件は、式（３２）、式（３３）で表される。
【数６２】
2009271888.tif 000045
【０１０４】
ここで、式（３４）が成立する。
【数６３】
2009271888.tif 000046
【０１０５】
よって、式（３５）が成立する。ここでj∈/L(i)∪R(i)に対してA(e^i(α),e^j(α))=0が成り立つことに留意すること。
【数６４】
2009271888.tif 000047
【０１０６】
よって、不等式（３６）が成り立つ。
【数６５】
2009271888.tif 000048
【０１０７】
ここで式（３７）、式（３８）が云える。
【数６６】
2009271888.tif 000049
【０１０８】
よって、点α∈Ｃを零点とする多項式ｇ∈Ｆεが存在する必要十分条件は以下の通りである。
［１］0，e1(α)，…，en(α)が一直線上にあるとき（凸多角形が線分に退化している場合）、必要十分条件は、f(α)がその直線上にあり、かつ、不等式（３９）が成立することである。
【数６７】
2009271888.tif 000050
［２］0，e1(α)，…，en(α)が一直線上にはないとき、必要十分条件は、ｉ＝１，…，ｎに対して不等式（４０）が成立することである。
【数６８】
2009271888.tif 000051
以上により[補題１]の証明は終了である。
（証明終）
【０１０９】
この補題１から下記の定理３が得られる。なお、補題１の記号ｉをｊに、ｊをｋに置き換えてある。
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
[定理３]記号ｆ，ｅｊ，Ｆ，Ａ（・，・），αは上記の通りとする。また、f(α)≠0とする。
［１］１≦ｊ＜ｋ≦ｎなるｊ，ｋに対してA(ej(α),ek(α))=0が成立するとき、点αを零点とする距離最小の多項式ｆ~が存在する必要十分条件は、A(ej(α),f(α))=0がｊ＝１，…，ｎに対して成立ち、さらに、ｅｊ(α)≠０となるｊが存在することである。このとき最小距離は式（４１）で与えられる。式（４１）で記号ｉは虚数単位を表す。
【数６９】
2009271888.tif 000052
［２］或るｊ，ｋ（１≦ｊ＜ｋ≦ｎ）に対してA(ej(α),ek(α))≠0が成立するとき、点αを零点とする距離最小の多項式ｆ~は存在する。このとき最小距離は式（４２）で与えられる。但し、分母が０となるものは除く。
【数７０】
2009271888.tif 000053
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
【０１１０】
（証明）
まず、定理３の［２］は、補題１の［２］から従う。補題１の［２］に拠ると、0，e1(α)，…，en(α)が一直線上にはないとき、つまり或るｊ，ｋ（１≦ｊ＜ｋ≦ｎ）に対してA(ej(α),ek(α))≠0が成立するとき、点α∈Ｃを零点とする多項式ｇ∈Ｆεが存在する必要十分条件は、ｊ＝１，…，ｎの全てに対して不等式（４３）が成立することである。
【数７１】
2009271888.tif 000054
【０１１１】
これを点α∈Ｃ（但し、≪問題≫に対しては上記[命題]からα∈Λでよい。）を零点とする距離最小の多項式ｆ~について適用する。或るｊ，ｋ（１≦ｊ＜ｋ≦ｎ）に対してA(ej(α),ek(α))≠0が成立するとき、ｊ＝１，…，ｎのそれぞれに対して不等式（４３）の等号が成立するときのεのうち最大のもの（εｍａｘ）が存在するので、距離最小の多項式ｆ~は必ず存在する。最小距離はεｍａｘであり、式（４４）で与えられる（但し、分母が０となるものは除く。）。
【数７２】
2009271888.tif 000055
【０１１２】
次に、定理３の［１］は、補題１の［１］から従う。補題１の［１］に拠ると、0，e1(α)，…，en(α)が一直線上にあるとき、点α∈Ｃを零点とする多項式ｇ∈Ｆεが存在する必要十分条件は、f(α)がその直線上にあり、かつ、不等式（４５）が成立することである。
【数７３】
2009271888.tif 000056
【０１１３】
これを点α∈Ｃ（但し、≪問題≫に対しては上記[命題]からα∈Λでよい。）を零点とする距離最小の多項式ｆ~について適用する。f(α)が0，e1(α)，…，en(α)が乗る一直線上に乗るために、ｊ＝１，…，ｎに対してA(ej(α),f(α))=0が成立しなければならない。また、ｊ＝１，…，ｎに対してｅｊ(α)＝０が成立すると、f(α)=0となる。しかし≪問題≫では多項式ｆは領域Ｄに零点を持たないので、f(α)≠0である。従って、ｅｊ(α)≠０となるｊが存在することも条件となる。
【０１１４】
0，e1(α)，…，en(α)が一直線上にあり、多項式ｆ~が存在する必要十分条件が満たされているとき、ｊ＝１，…，ｎに対して、ej(α)=ajf(α) (aj∈R)と書ける。このとき、不等式（４５）は不等式（４６）に書き換えることができる。
【数７４】
2009271888.tif 000057
【０１１５】
f(α)≠0が成り立つから、最小距離は不等式（４６）を満たす最小のεであり1/Σj=1n|aj|である。
一方、A(ej(α),if(α))=A(ajf(α),if(α))=ajA(f(α),if(α))が成り立つ。ここでA(f(α),if(α))=|f(α)|2>0に注意すると、式（４７）が成立する。なお、この式によれば根号の処理を避けることができる。
【数７５】
2009271888.tif 000058
以上により[定理３]の証明は終了である。
（証明終）
【０１１６】
定理３から最小距離が求まるので、求めるべき多項式ｆ~を示す。ここでは[補題１]の記法を踏襲する。
【０１１７】
まず、凸多角形が線分に退化していない場合について説明する。
式（２５）で表現される凸多角形は、反時計回りに頂点εｗ０，εｗ１，・・・，εｗ２ｍ−１を持つ。最小距離をd(f,g~)と表示すると、０≦ε＜d(f,g~)ならば、多項式ｇの零点α∈Ｄが与える点（-Ref(α),-Imf(α)）は式（２５）で表現される凸多角形に属さない。一方、ε＝d(f,g~)のとき、点（-Ref(α),-Imf(α)）は式（２５）で表現される凸多角形に属する。換言すれば、複素平面上にd(f,g~)ｗ０，d(f,g~)ｗ１，・・・，d(f,g~)ｗ２ｍ−１を頂点に持つ凸多角形Ｚの或る辺の上に点（-Ref(α),-Imf(α)）が乗っている。
【０１１８】
そこでεを最小距離d(f,g~)に固定し、点（-Ref(α),-Imf(α)）が乗っている凸多角形の辺の端点をεｗｉ，εｗｉ＋１とする。但し、ｗｉ，ｗｉ＋１は式（４７ａ）のとおりである。なお、ｉ＝２ｍ−１のときは、ｉ＋１を０に読み替えるものとする。
【数７６】
2009271888.tif 000059
【０１１９】
点（-Ref(α),-Imf(α)）は端点εｗｉと端点εｗｉ＋１とを結ぶ辺上に存在するから、或るｔ（０≦ｔ≦１）が存在して、式（４７ｂ）の如く表すことができる。式（４７ｂ）は、式（４７ａ）において０≦ｉ≦ｍ−１の場合の計算であるが、ｍ≦ｉ≦２ｍ−１の場合は、wi=-wi-mに注意すれば、式（４７ｂ）の最後の式を−１倍したものが成立する。
【数７７】
2009271888.tif 000060
【０１２０】
今、ν(k)=i+1となるｋをとると、式（４７ｂ）は、式（３４）から式（４７ｃ）に変形できる。式（４７ｃ）は、式（４７ａ）において０≦ｉ≦ｍ−１の場合の計算であるが、ｍ≦ｉ≦２ｍ−１の場合は、上述のとおり、式（４７ｃ）の最後の式を−１倍したものが成立する。
【数７８】
2009271888.tif 000061
【０１２１】
よって、集合P(i)を式（４７ｄ）で与えると、式（４７ｅ）で表される多項式ｇは点αを零点として持ち、しかもｅ＾j(x)が位置ベクトルpiと平行でないような識別子ｊについては、ej(x)の係数がε或いは−εであることが分かる。どちらの符号を取るかは式（１８）で分かる。式（４７ｅ）は、式（４７ａ）において０≦ｉ≦ｍ−１の場合の計算であるが、ｍ≦ｉ≦２ｍ−１の場合は、上述のとおり、式（４７ｅ）の最後の項を−１倍したものが成立する。
【数７９】
2009271888.tif 000062
【０１２２】
以下、j∈P(k)なる識別子ｊについて考察する。
このとき、式（４７ｅ）の右辺第四項について不等式（４７ｆ）が成立する。式（４７ｆ）は、式（４７ａ）において０≦ｉ≦ｍ−１の場合の計算であるが、ｍ≦ｉ≦２ｍ−１の場合は、上述のとおり、式（４７ｆ）の各辺を−１倍したものが成立する。
【数８０】
2009271888.tif 000063
【０１２３】
今、例えば集合P(k)に属するｊを若い方から順番にｊ１、ｊ２、ｊ３、・・・、ｊＭと表記するとして、不等式（４７ｆ）の第一辺を集合P(k)に属するｊを若い方から順にεの符号をプラスに書き換えていくと、あるｍ（１≦ｍ≦Ｍ）があって式（４７ｆ）の第二辺について不等式（４７ｇ）が成立する。なお、不等式（４７ｇ）はεの符号に意識した表記としてある。式（４７ｇ）は、式（４７ａ）において０≦ｉ≦ｍ−１の場合の計算であるが、ｍ≦ｉ≦２ｍ−１の場合は、上述のとおり、式（４７ｇ）の各辺を−１倍したものが成立する。
【数８１】
2009271888.tif 000064
【０１２４】
よって、ｊｍ以外の識別子ｊｉについては、a~ji=+ε (1≦i≦m-1), a~ji=-ε (m+1≦i≦M)と置くことととし、識別子ｊｍについては、式（４７ｈ）で表されるｓを用いて、a~jm=sεと置くこととする。このとき、−１≦ｓ≦１が成り立つことに注意する。式（４７ｈ）は、式（４７ａ）において０≦ｉ≦ｍ−１の場合の計算であるが、ｍ≦ｉ≦２ｍ−１の場合は、上述のとおり、式（４７ｈ）の右辺を−１倍したものが成立する。
【数８２】
2009271888.tif 000065
【０１２５】
すると、式（４７ｅ）および式（４７ｇ）から、式（４７ｉ）で表される多項式ｇ＾は、点αを零点として持ち、しかも識別子ｊｍの多項式ejm(x)とは異なる多項式の係数がε或いは−εであることが分かる。ji∈P(k),i≠mの場合の符号も上記の操作および式（１８）で分かる。さらに−１≦ｓ≦１に留意すれば、多項式ｇ＾は≪問題≫の解答となる多項式ｆ~であることが分かる。式（４７ｉ）は、式（４７ａ）において０≦ｉ≦ｍ−１の場合の計算であるが、ｍ≦ｉ≦２ｍ−１の場合は、上述のとおり、式（４７ｉ）の右辺第４項〜第６項を−１倍したものが成立する。
【数８３】
2009271888.tif 000066
【０１２６】
要するに、凸多角形が線分に退化していない場合の求めるべき多項式ｆ~は、式（７）で表される一変数実多項式の集合のうち、多項式ejm(x)の係数の絶対値を最小距離d(f,g~)以下とし、多項式ejm(x)以外の多項式の係数の絶対値を最小距離d(f,g~)としたものとして表すことができる。
多項式ejm(x)の特定は、式（４０）で等号が成立するｉ〔複数あるときには若い番号を採用する。〕を取り、二つあるeiと平行な辺のうちから式（４７ｂ）の一番上の等式を満たすｔ（０≦ｔ≦１）が存在するものを選んだ上で、ji∈P(k)なる識別子ｊｉについて式（４７ｇ）から多項式ejm(x)の特定することができる。
【０１２７】
次に、凸多角形が線分に退化している場合について説明する。
この場合は、凸多角形が線分に退化していない場合と同様の議論によって、εを最小距離d(f,g~)に固定すると式（３９）の等号が成立するから、式（４７ｊ）が成立する。但し、式（４７ｊ）が成立するときの符号±は、［１］Ref(α)＜0の場合、Reei(α)＜0となる識別子ｉについては＋εとし、Reei(α)＞0となる識別子ｉについては−εとする、［２］Ref(α)＞0の場合、Reei(α)＜0となる識別子ｉについては−εとし、Reei(α)＞0となる識別子ｉについては＋εとする、のいずれかである。なお、Reei(α)=0の場合は−ε、＋εのどちらをとってもよい。
【数８４】
2009271888.tif 000067
【０１２８】
よって、式（４７ｋ）で表される多項式ｇ＾が≪問題≫の解答となる多項式ｆ~であることが分かる。但し、式（４７ｋ）中の符号±は、上述のとおり決めればよい。
【数８５】
2009271888.tif 000068
【０１２９】
要するに、凸多角形が線分に退化している場合の求めるべき多項式ｆ~は、式（７）で表される一変数実多項式の集合のうち、多項式e1(x),e2(x),…,en(x)の係数の絶対値を最小距離d(f,g~)としたものとして表すことができる。
以上で《ｎ≧２の場合》の説明は終わりである。
以上で、[理論]の説明は終わりである。
【０１３０】
上述の[理論]に基づくと、要するに、≪問題≫に対しては次のとおり解答を与える。即ち、領域Ｄの境界Λ上の点αに対して、式（７）で表される集合Ｆに属しこの点αを零点とする多項式のうち多項式f(x)に最も近い多項式g(x)と多項式f(x)との距離を与える関数Φ(α)を用いて、区分境界Λ1,Λ2,…,ΛKごとに関数Φ(α)の最小値を求め（距離候補探索）、この距離候補探索で得られた値のうち最小のものを求める（最小距離算出）。
【０１３１】
関数Φ(α)は、［１］１≦ｊ＜ｋ≦ｎなる全てのｊ，ｋに対してA(ej(α),ek(α))=0が成立し、かつ、A(ej(α),f(α))=0がｊ＝１，…，ｎに対して成立ち、かつ、ｅｊ(α)≠０となるｊが存在する場合に式（４７ｍ）で与えられ、［２］或るｊ，ｋ（１≦ｊ＜ｋ≦ｎ）に対してA(ej(α),ek(α))≠0が成立する場合に、式（４７ｎ）で与えられる。
【数８６】
2009271888.tif 000069
【０１３２】
多項式ｆ~は、距離の最小値を与える点αの所在に応じて、式（４７ｉ）または式（４７ｋ）に従う。
【０１３３】
ｎ＝１の場合とｎ≧２の場合に分けて解答した理由は、ｎ＝１の場合には、ｎ≧２の場合で説明した解法よりも簡便な解法がある為であり、ｎ＝１の場合に於いてｎ≧２の場合で説明した解法を用いて解くことを妨げるものではない。
【０１３４】
《記号の導入》
複素係数多項式g(x)∈C[x]に対して、各係数をその複素共役で置き換えた多項式をg-(x)と書く。複素係数有理関数h(x)=h1(x)/h2(x) （h1(x),h2(x)∈C[x]）に対して、複素係数有理関数h-1(x)/h-2(x)をh-(x)と書く。実多項式g(x)∈R[x]に対し、式（４８）を定義する。
【数８７】
2009271888.tif 000070
【０１３５】
すると、gμ,r(s),gμ,i(s)∈R(s)，a∈Rに対してgμ,r(a)=Re g(γμ(a))，gμ,i(a)=Im g(γμ(a))が成り立つ。よって、以下、gμ,r(s)，gμ,i(s)を、Re g(γμ(s))，Im g(γμ(s))と書くことにする。
以上で、《記号の導入》の説明は終わりである。
【０１３６】
《アルゴリズム》
上述の[理論]に基づき、最小距離d(f,f~)を求めるアルゴリズムを説明する。
上記命題より、領域Ｄの境界Λ上の零点のみを考えれば十分である。
【０１３７】
条件〈３〉から、区分境界Λμ（μ∈{1,…,K}）上の点γμ(s) （s∈Iμ）を零点として持つ、最大値ノルムではかって多項式ｆに最も近い多項式ｆ~までの距離をΦ(s)とする。
【０１３８】
Φ(s)を計算するためにＩμの部分集合をいくつか定義する。
まず、集合Δμ⊂Iμを以下で定義する。
【０１３９】
ｎ≧２のとき、Δμを式（４９）のとおり定義する。
【数８８】
2009271888.tif 000071
【０１４０】
次に集合Δ~μ⊂Δμを式（５０）で定義する。
【数８９】
2009271888.tif 000072
【０１４１】
Φμ(s)はｓ∈Δμ＼Δ~μに対しては定義されない。なぜなら、定理３の［１］よりｓ∈Δμ＼Δ~μに対して多項式ｆ~は存在しないからである。記号＼は、差集合を表す。
【０１４２】
上記各集合を用いると、Φμ(s)は式（５１）の通りに書ける。式（５１）の第二式で、最大値は点ごとに取る。
【数９０】
2009271888.tif 000073
【０１４３】
［式（５１）の第一式について］
ｓ∈Δ~μに対してΦμ(s)を具体的に計算するために（つまり、Φμ(s)の第一式に現れる絶対値の記号を外した形式で計算するために）、Δ~μの部分集合Ｚ~μを式（５２）の通り定義する。
【数９１】
2009271888.tif 000074
【０１４４】
Ｚ~μは有限集合であり、Δ~μ＼Ｚ~μは有限個の区間の和集合で書ける。但し、区間は点に退化している場合もある。このとき、A(ej(γμ(s)),if(γμ(s)))≠0がΔ~μ＼Ｚ~μの各区間で成り立つ。これは、ｓ∈Δμのとき、A(ej(γμ(s)),if(γμ(s)))=0が成り立つのは、ej(γμ(s))=0であることと同値だからである。よって、Φμ(s)はΔ~μ＼Ｚ~μの各区間で有理関数となる。なお、各区間では式（５１）の第一式に表れる絶対値の中身の符号は確定しており、それは、各区間から代表点を一つずつとって符号を調べればよい。
【０１４５】
［式（５１）の第二式について］
Ｉμ＼ΔμをＪμと書く。ｓ∈Ｊμに対してΦμ(s)を具体的に計算するために（つまり、Φμ(s)の第二式に現れる絶対値の記号を外した形式で計算するために）、Ｊμの部分集合Ｚμを導入する。ここで、式（５３）で表される和集合をとるときに、A(ej(γμ(s)),ek(γμ(s))), A(ej(γμ(s)),f(γμ(s)))が恒等的に０となる集合は除く。
【数９２】
2009271888.tif 000075
【０１４６】
Ｚμは有限集合であり、Ｊμ＼Ｚμは有限個の区間の和集合である。但し、区間は点に退化している場合もある。また、Ｊμ＼Ｚμにおいてφμ,j(s)はｓの有理関数となる。これは、A(ej(γμ(s),ek(γμ(s))), A(ej(γμ(s),f(γμ(s)))の符号がＪμ＼Ｚμの各区間で不変だからである。このように、各区間では式（５１）の第一式に表れる絶対値の中身の符号は確定しており、それは、各区間から代表点を一つずつとって符号を調べればよい。
【０１４７】
Ｊμ＼Ｚμを有限個の区間Jμ,h（h=1,2,…）の和集合で書き、下記のアルゴリズム１を｛φμ,1,…,φμ,n｝と各Jμ,hに適用する。すると、Φμ(s)をＪμ＼Ｚμ上の区分的な有理関数として得ることができる。
【０１４８】
［アルゴリズム１］
このアルゴリズムは、入力された実区間Iにおいて、入力された一つ以上の関数ｆ１，…，ｆｔのうち或る関数ｆξが残りの関数よりも大となる区間Iξ⊂Iと関数ｆξとの組合せを出力するものである。つまり、
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
入力：有理関数の集合Ｓ＝｛f1,…,ft｝と実区間Ｉ
但し、fj（j=1,…,t）の極（分母の零点）は実区間Ｉには存在しないとする。
出力：maxＳ
但し｛(Ij,fθ(j))|1≦j≦p｝の形式で、I=∪j=1pIj, Ij∩Ik=0(j≠k)かつ、IjにおいてmaxＳ＝fθ(j)である。
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
とするアルゴリズムである。
【０１４９】
●ステップ１
ｔ＝１のとき、｛(I,f1)｝を出力して終了する。
ｔ≧２のとき、集合Ｓを二つの部分集合Ｓ１，Ｓ２に分ける。但し、Ｓ＝Ｓ１∪Ｓ２かつＳ１∩Ｓ２＝φ（空集合）とする。例えば式（５４）に示す集合Ｓ１，Ｓ２とする。
【数９３】
2009271888.tif 000076
【０１５０】
●ステップ２
maxＳ１を｛(I1,j,fθ1(j))|1≦j≦q｝の形式で、maxＳ２を｛(I2,j,fθ2(j))|1≦j≦r｝の形式で得る。maxＳ１とmaxＳ２は、（Ｓ１，Ｉ），（Ｓ２，Ｉ）を入力として、このアルゴリズム１を用いて得ることができる。つまり、アルゴリズム１は、自身をサブルーチンとして持つ再帰的アルゴリズムである。
【０１５１】
●ステップ３
max｛maxＳ１，maxＳ２｝を計算し、｛(Ij,fθ(j))|1≦j≦p｝を得る。そして、｛(Ij,fθ(j))|1≦j≦p｝を出力して終了する。
【０１５２】
以下、●ステップ３について説明する。
まず、I1,j∩I2,k≠φ（空集合）となる区間の対を取る。このような対は高々ｑ＋ｒ−１個存在し、max｛f1,…,ft｝を得るためにはmax｛maxＳ１，maxＳ２｝を各対の共通部分で計算する。空ではない区間I1,j∩I2,kの下限をａ、上限をｂとする（ａは−∞、ｂは∞となることがある。）。また、σ１＜…＜σζを、区間（ａ，ｂ）内にあるfθ1(j)(s)=fθ2(k)(s)の解とする。空ではない区間I1,j∩I2,kは、最多でも、σ１,…,σζで分割される。
【０１５３】
すると、I1,j∩I2,kにおけるmax｛maxＳ１，maxＳ２｝を求めるためには、fθ1(j)(τw)およびfθ2(k)(τw)の値をｗ＝１，…，ζ＋１に対して求めて、その大小関係を判定すればよい。ここで、τw（ｗ＝１，…，ζ＋１）は、ａ＜τ１＜σ１＜τ２＜…＜τζ＜σ１＜τζ＋１＜ｂを満足する任意の値である。
以上で●ステップ３の説明を終わる。
【０１５４】
図６−１および図６−２に示す具体例をもってアルゴリズム１の挙動を示す。
この具体例では、図６−１（ａ）に示すように、入力を有理関数の集合Ｓ＝｛f1,f2,f3,f4｝と実区間Ｉとしている。
【０１５５】
このとき、集合Ｓを二つの部分集合Ｓ１＝｛f1,f2｝，Ｓ２＝｛f3,f4｝に分け（●ステップ１-Ａ）、maxＳ１を｛(I1,j,fθ1(j))|1≦j≦q｝の形式で、maxＳ２を｛(I2,j,fθ2(j))|1≦j≦r｝の形式で得る（●ステップ２-Ａ）。但し、この段階で直截的にmaxＳ１とmaxＳ２を得られるわけではなく、再帰的にアルゴリズム１の呼び出しが行われる。
【０１５６】
部分集合Ｓ１＝｛f1,f2｝について、（Ｓ１，Ｉ）を入力として、アルゴリズム１を適用すると、｛(I,f1)｝、｛(I,f2)｝が出力される（●ステップ１-Ｂ）。この出力が●ステップ２-Ａに返される。そこで、実区間Ｉでmax｛f1,f2｝を求める（●ステップ３-Ａ）。部分集合Ｓ１に対する●ステップ３-Ａの挙動を図６−１（ｂ）に示す。
【０１５７】
この段階では単一の実区間Ｉのみなので、I1,j∩I2,k≠φ（空集合）となる区間の対は実区間Ｉである。よって、実区間Iの下限をａ、上限をｂとし、σ１を区間（ａ，ｂ）内にあるf1=f2の解とする（θ1(j)=1,θ2(k)=2）。実区間Iは、σ１で分割され、I1,1とI1,2となる。
【０１５８】
すると、実区間Iにおけるmax｛f１,f２｝を求めるためには、f1(τw)およびf2(τw)の値をｗ＝１，２に対して求めて、その大小関係を判定すればよい。ここで、ａ＜τ１＜σ１＜τ２＜ｂである。よって、maxＳ１を｛(I1,1,f1),(I1,2,f2)｝の形式で得る。
【０１５９】
同様に、部分集合Ｓ２＝｛f3,f4｝について、（Ｓ２，Ｉ）を入力として、アルゴリズム１を適用すると、｛(I,f3)｝、｛(I,f4)｝が出力される（●ステップ１-Ｃ）。この出力が●ステップ２-Ａに返される。そこで、実区間Ｉでmax｛f3,f4｝を求める（●ステップ３-Ａ）。部分集合Ｓ２に対する●ステップ３-Ａの挙動を図６−１（ｃ）に示す。
【０１６０】
この段階では単一の実区間Ｉのみなので、I1,j∩I2,k≠φ（空集合）となる区間の対は実区間Ｉである。よって、実区間Iの下限をａ、上限をｂとし、σ１,σ２を区間（ａ，ｂ）内にあるf3=f4の解とする（θ1(j)=3,θ2(k)=4）。実区間Iは、σ１,σ２で分割され、I2,1，I2,2，I2,3となる。
【０１６１】
すると、実区間Iにおけるmax｛f3,f4｝を求めるためには、f3(τw)およびf4(τw)の値をｗ＝１，２，３に対して求めて、その大小関係を判定すればよい。ここで、ａ＜τ１＜σ１＜τ２＜σ２＜τ３＜ｂである。よって、maxＳ２を｛(I2,1,f4),(I2,2,f3),(I2,3,f4)｝の形式で得る。
【０１６２】
続いて、max｛maxＳ１，maxＳ２｝を計算する。集合Ｓに対する●ステップ３-Ａの挙動を図６−２（ｄ）〜（ｆ）に示す。
maxＳ１は｛(I1,1,f1),(I1,2,f2)｝であり、maxＳ２は｛(I2,1,f4),(I2,2,f3),(I2,3,f4)｝である。よって、I1,j∩I2,k≠φ（空集合）となる区間の対はI1,1∩I2,1，I1,1∩I2,2，I1,2∩I2,2，I1,2∩I2,3である（図６−２（ｄ））。
【０１６３】
区間I1,1∩I2,1の下限をａ、上限をｂとする。この区間でmax｛f1,f4｝を求めるが、区間（ａ，ｂ）内にあるf1=f4の解は存在しない。よって、I1,1∩I2,1の分割は生じない。
【０１６４】
区間I1,1∩I2,1におけるmax｛f1,f4｝を求めるためには、f1(τw)およびf4(τw)の値をｗ＝１に対して求めて、その大小関係を判定すればよい。ここで、ａ＜τ１＜ｂである。よって、区間I1,1∩I2,1のmax｛f1,f4｝は(I1,1∩I2,1,f1)である。
【０１６５】
同様にして、区間I1,1∩I2,2のmax｛f1,f3｝は(I1,1∩I2,2,f1)であり、区間I1,2∩I2,2のmax｛f2,f3｝は(I1,2∩I2,2,f2)である。
【０１６６】
次に、区間I1,2∩I2,3の下限をａ、上限をｂとする。この区間でmax｛f2,f4｝を求める。区間I1,2∩I2,3でf2=f4の解は一つ存在し、この解σ１で区間I1,2∩I2,3は、ILとIRに分割される（図６−２（ｅ））。
【０１６７】
そこで、区間I1,2∩I2,3におけるmax｛f2,f4｝を求めるためには、f1(τw)およびf2(τw)の値をｗ＝１，２に対して求めて、その大小関係を判定すればよい。ここで、ａ＜τ１＜σ１＜τ２＜ｂである。よって、区間I1,2∩I2,3のmax｛f2,f4｝は(IL,f2)と(IR,f4)である。
【０１６８】
よって、(I1,1∩I2,1,f1)，(I1,1∩I2,2,f1)，(I1,2∩I2,2,f2)，(IL,f2)，(IR,f4)を得る。ここで、I1,1∩I2,1とI1,1∩I2,2を連結してI1とし、I1,2∩I2,2とILを連結してI2とすることに注意すると、最終的にmaxＳとして(I1,f1)，(I2,f2)，(I3,f4)が出力される（図６−２（ｆ））。なお、I=∪j=13Ij, Ij∩Ik=0(j≠k)である。
【０１６９】
なお、ここではアルゴリズム１を再帰的アルゴリズムとして例示したが、同等の結果を得ることができるならば、非再帰的アルゴリズムに変更するなど、適宜に変更可能である。
【０１７０】
さて、上述の[理論]などに基づき、≪問題≫の最小距離d(f,f~)を求めるアルゴリズムの一例であるアルゴリズム２を説明する〔図１−１および図１−２参照〕。
【０１７１】
［アルゴリズム２］
例示するアルゴリズム２では、
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
入力：多項式f(x),e1(x),e2(x),…,en(x)
多項式f(x)の零点が存在しない複素領域Ｄの境界Λ＝∪μ=1KΛμにつき、各区分境界Λμの有理式による表示｛γ1,…,γK｝，｛I1,…,IK｝
但し、各区分境界Λμは、単射γμ： Ｉμ  →  Λμと表示される。
領域Ｄに含まれる一点Ｑ
出力：多項式ｆから多項式ｆ~までの最小距離d(f,f~)
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
とする。ここでは、Ｘが空集合のときには、mins∈X｛Φ(s)｝=∞と約束し、Φ(s)がｓ＝σで定義されていないときには、Φ(σ)=∞と約束する。
【０１７２】
〈アルゴリズムの具体例〉
◎ステップＳ１
f(x)+Σj=1najej(x)=0を満たす実数a1,a2,…,anが存在する場合、Ｔ＝d(f,0)とする。このような実数a1,a2,…,anが存在しない場合、Ｔ＝∞とする。
＜解説＞
ステップＳ１は、多項式ｆ~が恒等的に０である場合を排除しないための処理である。実数a1,a2,…,anが存在することの判定は、f(x)+Σj=1najej(x)をΣi=0Nwixiのように表現したときの各係数wiを０とした連立方程式を解けばよい〔但し、実際に解を求める必要はなく、連立方程式の解の存在判定（公知）を行うだけでよい。〕。このような実数a1,a2,…,anが存在する場合、最小距離はd(f,0)である。
多項式ｆ~が恒等的に０である場合を考慮しないときは、初期値設定Ｔ＝∞のみを行う。
【０１７３】
◎ステップＳ２
入力された多項式f(x),e1(x),e2(x),…,en(x)についてｎ≧２であるか否かを判定する。
ｎ≧２である場合は、ステップＳ４の処理を行う。
ｎ≧２ではない場合、つまりｎ＝１の場合は、ステップＳ３の処理を行う。
【０１７４】
◎ステップＳ３
《ｎ＝１の場合》で説明した処理を行う。ステップＳ３の処理の詳細は次のとおりである。
【０１７５】
○ステップＳ３０１
Re f(x) Im e1(x)−Im f(x) Re e1(x)が恒等的に０であるか否かを判定する。
【０１７６】
○ステップＳ３０２
Re f(x) Im e1(x)−Im f(x) Re e1(x)が恒等的に０である場合、f(x)/e1(x)は定数である。この時点で記憶されているＴの値がＴ＞|f(x)/e1(x)|ならば、Ｔ＝|f(x)/e1(x)|とし、このＴをd(f,f~)として出力して処理を終了する。この時点で記憶されているＴの値がＴ≦|f(x)/e1(x)|ならば、この時点でのＴの値をd(f,f~)として出力して処理を終了する。
【０１７７】
○ステップＳ３０３
Re f(x) Im e1(x)−Im f(x) Re e1(x)が恒等的に０ではない場合、各μ（μ=1,2,…,K）に対して以下の処理を行う。区分境界の表示γμ(s)をｘに代入し、Re f(γμ(s)) Im e1(γμ(s))−Im f(γμ(s)) Re e1(γμ(s))=0を解いて（根は有限個である。）、これらの有限個の根のうちσi(i=1,2,…)∈Iμについて連立方程式（１２）を満たす実数解t1を求める。
【０１７８】
○ステップＳ３０４
実数解t1が存在するか否か判定する。
【０１７９】
○ステップＳ３０５
実数解t1が一つ以上存在する場合〔これをt1(i)とする。〕、この時点で記憶されているＴの値がＴ＞mini{|t1(i)|}ならば、Ｔ＝mini{|t1(i)|}とし、このＴをd(f,f~)として出力して処理を終了する。この時点で記憶されているＴの値がＴ≦mini{|t1(i)|}ならば、この時点でのＴの値をd(f,f~)として出力して処理を終了する。
【０１８０】
○ステップＳ３０６
実数解t1が存在しない場合、≪問題≫の解答としての多項式ｆ~は存在しない。よって、最小距離が存在しない旨を出力して処理を終了する。
【０１８１】
◎ステップＳ４
《ｎ≧２の場合》で説明した処理を行う。ステップＳ４の処理の詳細は次のとおりである。
【０１８２】
○ステップＳ４０１
入力された区分境界表示と一点Ｑから特定される領域Ｄが有界であるか否かを判定する。
＜解説＞
この判定処理は、定理１に基づくものであり、次のとおり行うことができる。
（☆ステップ１）
Λ⊂｛z∈C|Re z < a｝となる実数ａを求める。境界Λは長さが有限の単純閉曲線であり、その区分境界表示が具体的に特定されているので、このような実数ａを求めることができる。また、このような実数ａは複素平面上で実軸上の一点で表示される。
（☆ステップ２）
点ａと点Ｑとを結んだ線分が境界Λと交点を持ち、それが全て区分境界Λμの端点でなければ、重複度も込めて交点の数を数える。交点の数が奇数ならば領域Ｄは有界、偶数（０の場合も含む。）ならば非有界である。
（☆ステップ３）
もし、点ａと点Ｑとを結んだ線分が境界Λと交点を持ち、そのうちの少なくとも一つが或る区分境界Λμの端点であるならば点ａを取り直す。具体的には、点ａと点Ｑとを結んだ線分が実軸と平行でないならば、ａをａ＋１で置き替えて☆ステップ２を行う。また、点ａと点Ｑとを結んだ線分が実軸と平行であるならば、ａをａ＋ｉで置き替えて☆ステップ２を行う。
境界Λ上の点で区分境界の端点となっているものの数は有限である。上記の手続で得られる点ａと点Ｑとを結んだ線分の傾きに同じものはないので、有限回の点ａの取り直しで必ず区分境界の端点ではない点を交点とするように点ａを取ることができる。
【０１８３】
○ステップＳ４０２
領域Ｄが有界ではない場合、全てのｉ（ｉ＝１，・・・，ｎ）について多項式ei(x)の次数ｋｉが多項式ｆの次数ｍ未満であるか否かを判定する。
【０１８４】
○ステップＳ４０３
全てのｉ（ｉ＝１，・・・，ｎ）について多項式ei(x)の次数ｋｉが多項式ｆの次数ｍ未満ではない場合、条件〈５〉に反するから、処理対象外である旨を出力して処理を終了する。
【０１８５】
領域Ｄが有界である場合、あるいは、全てのｉ（ｉ＝１，・・・，ｎ）について多項式ei(x)の次数ｋｉが多項式ｆの次数ｍ未満である場合、ステップＳ５の処理を行う。
【０１８６】
◎ステップＳ５
未選択の区分境界が存在するか否かを判定する（○ステップＳ５０）。
未選択の区分境界が存在すれば、その中の一つΛμを選択する（○ステップＳ５１）。
未選択の区分境界が存在しない場合、この時点で記憶されているＴの値がＴ＞min｛m1,…,mμ,…,mK｝ならば、Ｔ＝min｛m1,…,mμ,…,mK｝とし、このＴをd(f,f~)として出力して処理を終了する。この時点で記憶されているＴの値がＴ≦min｛m1,…,mμ,…,mK｝ならば、この時点でのＴの値をd(f,f~)として出力して処理を終了する。（○ステップＳ５２）。
＜解説＞
ステップＳ５は、全ての区分境界について以降のステップＳ６〜ステップＳ８の各処理を行うための処理である。全ての区分境界についてステップＳ６〜ステップＳ８の各処理を実行した場合は、終了である。出力Ｔが∞のときは、集合Ｆに属する多項式で領域Ｄに零点を持つ多項式は存在しない。
【０１８７】
◎ステップＳ６
ステップＳ５１の処理で選択された区分境界Λμに対応する実区間Iμ⊂Ｒが一点であるか否かを判定する。これは、実区間Iμ=[α,β]と表されている場合にα＝βの成立を判定すればよい。
実区間Iμが一点δ、つまりIμ=[δ,δ]の場合にはステップＳ７の処理へ、実区間Iμが一点ではない場合にはステップＳ８の処理へ、進む。
【０１８８】
◎ステップＳ７
ステップＳ７は実区間Iμが一点である場合にΦμ(δ）を求める処理である。但し、δが集合Δ~μに属する場合、Φμ(δ）は式（５１）の第一式で求め、δが集合Ｉμ＼Δμに属する場合、Φμ(δ）は式（５１）の第二式で求める。
ステップＳ７の処理の詳細は次のとおりである。
【０１８９】
○ステップＳ７１
実区間Iμ、つまりδが集合Ｉμ＼Δμに属するか否か判定する。Δμは式（４９）のとおりである。なお、実区間Iμが一点δであるから、１≦ｊ＜ｋ≦ｎの全てのｊ、ｋについて、A(ej(γμ(δ)),ek(γμ(δ)))=0が成立するならば、δ∈Δμであることがわかる。
【０１９０】
○ステップＳ７２
実区間Iμ、つまりδが集合Ｉμ＼Δμに属する場合、Φμ(δ）を式（５１）の第二式で求める。このΦμ(δ）をｍμとする。この後、ステップＳ５０の処理に進む。
【０１９１】
○ステップＳ７３
実区間Iμ、つまりδが集合Ｉμ＼Δμに属さない場合、δが集合Δ~μに属するか否か判定する。Δ~μは式（５０）のとおりである。
【０１９２】
○ステップＳ７４
δが集合Δ~μに属する場合、Φμ(δ）を式（５１）の第一式で求める。このΦμ(δ）をｍμとする。この後、ステップＳ５０の処理に進む。
【０１９３】
○ステップＳ７５
δが集合Δ~μに属さない場合、実区間Iμである点δを零点とする最近実多項式ｆ~は存在しない（定理３）。そこでｍμを∞とする。この後、ステップＳ５０の処理に進む。
【０１９４】
◎ステップＳ８
ステップＳ８は実区間Iμが一点ではない場合にΦμ(ｓ）を求める処理である。
但し、ｓが集合Δ~μに属する場合において、
［其の壱］ｓが集合Δ~μ＼Ｚ~μに属するならばΦμ(ｓ）は式（５１）の第一式で表される有理関数としてその最小値を求めることができ、
［其の弐］ｓが集合Ｚ~μに属するならば有限個のｓ∈Ｚ~μをそれぞれ式（５１）の第一式で表されるΦμ(ｓ）に入力することでその最小値を求めることができる。
また、ｓが集合Ｉμ＼Δμ（＝Ｊμ）に属する場合において、
［其の参］ｓが集合Ｊμ＼Ｚμに属するならば、Ｊμ＼Ｚμを有限個の区間Jμ,h（h=1,2,…）の和集合で書き、上記アルゴリズム１を｛φμ,1,…,φμ,n｝と各Jμ,hに適用することで、Φμ（ｓ）をＪμ＼Ｚμ上の区分的な有理関数として得ることができるから、その最小値を求めることができ、
［其の四］ｓが集合Ｚμに属するならば有限個のｓ∈Ｚμをそれぞれ式（５１）の第二式で表されるΦμ(ｓ）に入力することでその最小値を求めることができる。
ステップＳ８の処理の詳細は次のとおりである。
【０１９５】
○ステップＳ８１
［其の弐］の場合の処理である。式（５５）に従いｍμ，１を求める。Ｚ~μは式（５２）のとおりである。Φμ(ｓ）は式（５１）の第一式である。式（５５）ではＺ~μの有限個の元σ１,…,σｒの個数をｒとしている。
【数９４】
2009271888.tif 000077
【０１９６】
○ステップＳ８２
［其の四］の場合の処理である。式（５６）に従いｍμ，２を求める。Ｚμは式（５３）のとおりである。Φμ(ｓ）は式（５１）の第二式である。式（５６）ではＺμの有限個の元σ１,…,σｒの個数をｒとしている（記号ｒは説明の便宜で用いており、Ｚ~μの元の個数と常に同じという趣旨ではない。）。
【数９５】
2009271888.tif 000078
【０１９７】
○ステップＳ８３
［其の壱］の場合の処理である。式（５７）に従いｍμ，３を求める。Δ~μは式（５０）のとおりである。Ｚ~μは式（５２）のとおりである。Φμ(ｓ）は式（５１）の第一式である。Ｚ~μは有限集合であり、Δ~μ＼Ｚ~μは有限個の区間Lμ,h（h=1,2,…,r）の和集合で表される。ここでは有限個の区間の個数をｒとした（記号ｒは説明の便宜で用いており、Ｚ~μやＺμの元の個数と常に同じという趣旨ではない。）。但し、区間は点に退化している場合もある。
区間Lμ,hでΦμ(ｓ）の最小値はΦμ(ｓ）を微分して０となるときの根Ｘを入力したΦμ(Ｘ）の中に存在する可能性がある。また、区間Lμ,hが端点ｓ＝Ｙを持つときはΦμ(Ｙ）も最小値の可能性がある。これらの可能性のある値のうち最小値を求めればよい。区間Lμ,hが点ｓ＝Ｗに退化しているときはΦμ(Ｗ）を求めればよい。各区間Lμ,hで求まる最小値うち最小のものがｍμ，３である。なお、式（５７）の分母の記号±はｊごとに区間Lμ,h（h=1,2,…,r）に対していずれか一方に一意に定まることに留意すること。
【数９６】
2009271888.tif 000079
【０１９８】
○ステップＳ８４
［其の参］の場合の処理である。式（５８）に従いｍμ，４を求める。Ｊμ＝Ｉμ＼Δμとする。Δμは式（４９）のとおりである。Ｚμは式（５３）のとおりである。Ｊμ＼Ｚμを有限個の区間Jμ,h（h=1,2,…,r）の和集合で表し（ここでは有限個の区間の個数をｒとした。記号ｒは説明の便宜で用いており、Δ~μ＼Ｚ~μの有限個の区間の個数と常に同じという趣旨ではない。）、上記アルゴリズム１を｛φμ,1,…,φμ,n｝と各Jμ,hに適用することで、Φμ（ｓ）をＪμ＼Ｚμ上の区分的な有理関数として得る。つまり、或るJμ,hにつき、Φμ（ｓ）は、アルゴリズム１によってΦμ,h(s)=｛(Jμ,h,j,φμ,θ(j)(s))|1≦j≦ph｝として得られる。但し、θ(j)∈｛1,…,n｝， Jμ,h,j⊂Jμ,hである。なお、アルゴリズム１の適用において、式（５１）で表現される｛φμ,1,…,φμ,n｝の分母分子の絶対値は外れて±のいずれか一方に一意に定まることに留意すること。
区間Jμ,hでΦμ，ｈ(ｓ）の最小値は、Φμ，ｈ(ｓ）を微分して０となるときの根Ｘを入力したΦμ，ｈ(Ｘ）の中に存在する可能性がある（実際は区分Jμ,h,jごとにφμ,θ(j)(s)を微分して０となるときの根Ｘを入力したφμ,θ(j)(Ｘ）の中に存在する可能性がある。また、区分Jμ,h,jの端点ｓ＝Ｖを入力とするφμ,θ(j)(Ｖ）も最小値の可能性がある。）。また、区間Jμ,hが端点ｓ＝Ｙを持つときはΦμ，ｈ(Ｙ）も最小値の可能性がある。これらの可能性のある値のうち最小値を求めればよい。区間Jμ,hが点ｓ＝Ｗに退化しているときはΦμ，ｈ(Ｗ）を求めればよい。各区間Jμ,hで求まる最小値うち最小のものがｍμ，４である。
【数９７】
2009271888.tif 000080
【０１９９】
○ステップＳ８５
mμ=min{mμ,1,mμ,2,mμ,3,mμ,4}を求める。この後、ステップＳ５０の処理に進む。
【０２００】
［アルゴリズムの計算量の解析］
まず、アルゴリズム１の計算量を解析する。この解析のために、Davenport-Schinzel列を定義する。
【０２０１】
定義１（Davenport-Schinzel列）
Σn={a1,a2,…,an}とし、Ln,sをアルファべットΣｎ上の文字列の集合で、aiaiおよびξijs（ｉ≠ｊ）を部分文字列として含まないものとする。ここで、ξijsは式（５９）で定義される長さｓ＋２の文字列である。λ(n,s)をmax{|σ||σ∈Ln,s}で定義し、Ln,sに属する列を(n,s)Davenport-Schinzel列という。
【数９８】
2009271888.tif 000081
【０２０２】
下記の補題２は、アルゴリズム１とDavenport-Schinzel列の関係を示すもので、参考文献５に記載されたLemma2.4と本質的に同じものである。
（参考文献５）M.J.Atallah, Some dynamic computational geometry problems, Computers and Mathematics with Applications, Vol.11, No.12, pp.1171-1181, 1985.
【０２０３】
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
[補題２]ｆ１，…，ｆｎを、実数値を取るｔ∈Ｉ⊂Ｒの関数かつ連続なものとする。異なる二つのｆｉとｆｊを任意に取ったとき、ｆｉとｆｊが高々ｓ回しか交わらないとすると、
h(t)=max{f1(t),…,fn(t)}
は、Ｉを高々λ(n,s)個の区間に細分することにより、各細分上でｆ１，…，ｆｎのいずれかと等しいようにできる。ここで、λ(n,s)という値はこれ以上小さくはできない。
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
【０２０４】
δを、アルゴリズム１において、ｆ１，…，ｆｎの分母分子の次数の最大値とする。すると、ｆｊとｆｋ（ｊ≠ｋ）は、Ｉにおいて高々２δ回しか交わらない。よって、max{f~1,f~2}を計算するために、●ステップ３において、fj=fkという方程式を解く回数は、高々、式（６０）で表されるとおりである。
【数９９】
2009271888.tif 000082
【０２０５】
よって、max{f1,…,fn}を計算するためにfj=fkという方程式を解く回数は、高々、式（６１）で表されるとおりとなる。
【数１００】
2009271888.tif 000083
【０２０６】
式（６１）の値を評価するために、下記の補題３を用いる。
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
[補題３]任意の正の自然数ｍに対し、mλ(n,s)≦λ(mn,s)が成立する。
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
（証明）
σ１，…，σｍを、アルファベットΣｎ，Σ２ｎ＼Σｎ，…，Σｍｎ＼Σ（ｍ−１）ｎ上の(n,s)Davenport-Schinzel列とする。このとき、σ１，…，σｍは、Σｍｎ上の(mn,s)Davenport-Schinzel列で長さがmλ(n,s)であるから、補題３の不等式は成り立つ。
（証明終）
【０２０７】
補題３から、式（６２）が得られる。
【数１０１】
2009271888.tif 000084
【０２０８】
λ(n,s)はｎとｓについて、多項式オーダーである。例えば、
λ(n,s)≦sn(n-1)+1
という評価が、参考文献６で与えられている。
（参考文献６）H.Davenport and A.Schinzel, A combinatorial problem concerned with differential equations, American Journal of Mathematics, Vol.87, No.3, pp.684-694, 1965.
【０２０９】
次に、アルゴリズム２の計算量を解析する。特に、ステップＳ７０番台、Ｓ８０番台の計算量について解析する。
【０２１０】
ｄ次の多項式p(x)∈R[x]と、分母分子の次数が高々ｍの有理関数r(x)∈R[x]に対して、p(r(x))の分母分子の次数は高々ｍｄである。よって、Rep(r(x)),Imp(r(x))の分母分子の次数は高々２ｍｄとなる。
【０２１１】
d=max{deg(f),deg(e1),…,deg(en)}とし、γ1(s),…,γK(s)の分母分子のうちの最高次数をｍとする。すると、f(γμ(s)),ej(γμ(s))の分母分子のうちの最高次数は高々ｍｄであり、
A(ej(γμ(s)),ek(γμ(s))),    A(ej(γμ(s)),f(γμ(s))),
A(f(γμ(s)),if(γμ(s)))
の分母分子の最高次数は高々８ｍｄである。
【０２１２】
各μ（μ＝１，…，Ｋ）に対し、解く必要のある方程式の数は下記の通りである。
【０２１３】
・Δμ，Δ~μ，Ｚ~μ，Ｚμを構成するためには、それぞれ一つの方程式を解けばよい。
Δμ，Δ~μ，Ｚ~μ，Ｚμに対する方程式の次数は高々、
8md,  8md,  min{8md,mnd},  4mn(n+1)d
である。
【０２１４】
・Ｊμ＼Ｚμ上でΦμを構成するために必要な解くべき方程式の数と次数は、高々、式（６３）で与えられるものである。Ｊμ＼Ｚμは、高々4mn(n+1)d+8md+1個の区間の和集合として書けることに注意すること。Φμを構成するために、各区間上で解く必要のある方程式の数は、高々、式（６４）で与えられるものである。
【数１０２】
2009271888.tif 000085
【０２１５】
・ｍμ，１，ｍμ，２を計算するのに比較が必要な値は、高々、
min{8md,mnd},    4mn(n+1)d
である。
【０２１６】
・Δ~μ＼Ｚ~μは、高々８ｍｄ個の区間（一点に退化したものも含む。）の和として書ける。
ｍμ，３を、Δ~μ＼Ｚ~μの一点に退化していない区間上で計算するためには、Φ'μ(ｓ）＝０を解く必要がある。Φμ(ｓ）の分母分子の次数は高々８ｍ（ｎ＋１）ｄだから、Φ'μ(ｓ）の分子の次数は、高々、
16m(n+1)d-1
である。
【０２１７】
・ｍμ，４を計算するために、Φ'μ(ｓ）＝０を、Ｊμ＼Ｚμの各区間上で解く必要がある。Φμ(ｓ）の分母分子の次数は高々８ｍ（ｎ＋１）ｄだから、Φ'μ(ｓ）の分子の次数は、高々、
16m(n+1)d-1
である。
【０２１８】
以上より、解く必要のある方程式の数、その次数は、ｍ，ｎ，ｄ，Ｍの多項式オーダーであることが分かる。
以上で［アルゴリズムの計算量の解析］の説明は終わりである。
【０２１９】
上記のアルゴリズムは一例に過ぎず、論理的な先後関係を逸脱しない限り、処理の順番を入れ替えたり変更したりすることができる。
例えば、ステップＳ８１、Ｓ８２、Ｓ８３、Ｓ８４の各処理に論理的な先後関係はないので適宜に処理手順を変更することができる。また、ステップＳ１の処理内容は全ての処理に先立ち行われることに限定されるものではない。例えば、次のようにも変更できる。ステップＳ１では単にＴ＝∞に設定するだけにする。そして、ステップＳ５２の処理の後、終了することなく、多項式ｆ~が恒等的に０となる場合の実数a1,a2,…,anの存在を判定し、存在すればＴ1＝d(f,0)とする。さらに、Ｔ1とステップＳ５２の処理の段階でのＴとを比較してこの最小値を距離の最小値とする。
【０２２０】
さらに、上記のアルゴリズムでは、複素領域Ｄに多項式f(x)の零点が存在しないことが予め既知のものとしたが、Sturmの定理と偏角の原理を用いて、複素領域Ｄに零点が存在しないことを確認する処理を前置で行うようにしてもよい。
【０２２１】
また、上記のアルゴリズムは、多項式ｆと多項式ｆ~との距離の最小値を求めるものであったが、多項式ｆ~を出力するようにしてもよい。
この場合、一例として、上記アルゴリズムを次のように変更すればよい〔図２−１および図２−２参照〕。
【０２２２】
・ステップＳ１を次のように変更する（ステップＳ１ａ）。
f(x)+Σj=1ncjej(x)=0を満たす実数a1,a2,…,anが存在する場合、Ｔ＝d(f,0)とする。このような実数a1,a2,…,anが存在しない場合、Ｔ＝∞とする。また、Ｔ＝d(f,0)とき多項式Ｐを０とする。Ｔ＝∞のとき多項式Ｐを−１とする。多項式Ｐ＝−１は、「領域Ｄに零点を持つ多項式であって式（７）で表される多項式の集合に属する多項式は存在しない」ということである。
【０２２３】
・ステップＳ３０２を次のように変更する（ステップＳ３０２ａ）。
f(x)/e1(x)が定数である場合、この時点で記憶されているＴの値がＴ＞|f(x)/e1(x)|ならば、Ｔ＝|f(x)/e1(x)|，Ｐ＝０〔ゼロ多項式〕とし、このＴとＰを出力して処理を終了する。この時点で記憶されているＴの値がＴ≦|f(x)/e1(x)|ならば、この時点でのＴとＰを出力して処理を終了する。
【０２２４】
・ステップＳ３０５を次のように変更する（ステップＳ３０５ａ）。
実数解t1が一つ以上存在する場合〔これをt1(i)とする。〕、この時点で記憶されているＴの値がＴ＞mini{|t1(i)|}ならば、Ｔ＝mini{|t1(i)|}，P=f(x)+mini{|t1(i)|}e1(x)とし、このＴとＰを出力して処理を終了する。この多項式Ｐは、f(x)±mini{|t1(i)|}e1(x)のうちの一つである。本発明では一つの多項式ｆ~を提示すれば十分である。また、この時点で記憶されているＴの値がＴ≦mini{|t1(i)|}ならば、この時点でのＴとＰを出力して処理を終了する。
【０２２５】
・ステップＳ５２を次のように変更する（ステップＳ５２ａ）。
未選択の区分境界が存在しなければ、この時点で記憶されているＴの値がＴ＞min｛m1,…,mμ,…,mK｝ならば、Ｔ＝min｛m1,…,mμ,…,mK｝とし，このＴを与えたmｘ（x∈{1,…,K}）がステップＳ７２、Ｓ８２、Ｓ８４のいずれかで得られたものである場合には多項式Ｐを式（４７ｉ）で求め、このＴを与えたmｘ（x∈{1,…,K}）がステップＳ７４、Ｓ８１、Ｓ８３のいずれかで得られたものである場合には多項式Ｐを式（４７ｋ）で求め、このＴとＰを出力して処理を終了する。
また、この時点で記憶されているＴの値がＴ≦min｛m1,…,mμ,…,mK｝ならば、この時点でのＴとＰを出力して処理を終了する。
【０２２６】
なお、最小距離Ｔに併せて多項式Ｐを出力することに限定するものではなく、多項式Ｐのみを出力するようにしてもよい。
【０２２７】
また、上述のアルゴリズムでは下記のように変更できる。
ｎ≧２であることが既知である場合には、ステップＳ２、ステップＳ３００番台の各処理を省略できる。
領域Ｄが有界であることが既知である場合には、ステップＳ４００番台の各処理を省略できる。
ｎ≧２および領域Ｄが有界であることが既知である場合には、ステップＳ２、ステップＳ３００番台、ステップＳ４００番台の各処理を省略できる。
多項式ｆ~が恒等的に０である場合を除くときには、ステップＳ１の処理を省略できる。但し、この場合は初期値設定を適宜に行う。
【０２２８】
[第１実施形態]
以下に、本発明の第１実施形態を上記アルゴリズム例〔図１−１、図１−２参照〕に則して説明する。第１実施形態は、多項式f(x)と多項式f~(x)=f(x)+Σj=1na~jej(x) (a~j∈Ｒ)との最小距離の算出〔多項式間距離算出〕に係わる。
図３は、本実施形態に係わる多項式間距離算出装置（１）のハードウェア構成を例示した構成ブロック図である。
【０２２９】
図３に例示するように、多項式間距離算出装置（１）は、キーボードなどが接続可能な入力部（１１）、液晶ディスプレイなどが接続可能な出力部（１２）、多項式間距離算出装置（１）外部に通信可能な通信装置（例えば通信ケーブル）が接続可能な通信部（１３）、ＣＰＵ（Central Processing Unit）（１４）〔キャッシュメモリやレジスタなどを備えていてもよい。〕、メモリであるＲＡＭ（１５）やＲＯＭ（１６）、ハードディスクである外部記憶装置（１７）並びにこれらの入力部（１１）、出力部（１２）、通信部（１３）、ＣＰＵ（１４）、ＲＡＭ（１５）、ＲＯＭ（１６）、外部記憶装置（１７）間のデータのやり取りが可能なように接続するバス（１８）を有している。また必要に応じて、多項式間距離算出装置（１）に、ＣＤ−ＲＯＭなどの記憶媒体を読み書きできる装置（ドライブ）などを設けるとしてもよい。このようなハードウェア資源を備えた物理的実体としては、汎用コンピュータなどがある。
【０２３０】
多項式間距離算出装置（１）の外部記憶装置（１７）には、多項式ｆと多項式ｆ~との最小距離の算出に必要となるプログラムおよびこのプログラムの処理において必要となるデータなどが記憶されている（外部記憶装置に限らず、例えばプログラムを読み出し専用記憶装置であるＲＯＭに記憶させておくなどでもよい。）。また、これらのプログラムの処理によって得られるデータなどは、ＲＡＭや外部記憶装置などに適宜に記憶される。以下、演算結果やその格納領域のアドレスなどを記憶するＲＡＭ（１５）やレジスタなどの記憶装置を単に「メモリ」と呼ぶことにする。
【０２３１】
より具体的には、多項式間距離算出装置（１）の外部記憶装置（１７）〔あるいはＲＯＭなど〕には、
多項式ｆ~が恒等的に０となる場合について調査するための恒等式調査プログラム、
入力された多項式f(x),e1(x),e2(x),…,en(x)の個数についてｎ≧２であるか否かを判定するための多項式数条件判定プログラム、
ｎ＝１の場合に最小距離を算出するための第一最小距離算出プログラム、
ｎ≧２の場合に領域Ｄが有界であるか否かを判定するための領域有界判定プログラム、
多項式ei(x) （i=1,・・・,n）の次数ｋｉが多項式ｆの次数ｍ未満であるか否かを判定するための次数判定プログラム、
未選択の区分境界の有無を調べ、未選択の区分境界がある場合にはその中から一つの区分境界を選択するための探索制御プログラム、
選択された区分境界が点であるか否かを判定するための区分境界点判定プログラム、
選択された区分境界が点（区分境界に対応する実区間Ｉμが点δ）である場合に、点δが集合Ｉμ＼Δμに属する場合は式（５１）の第二式で距離候補ｍμを求め、点δが集合Δ~μに属する場合は式（５１）の第一式で距離候補ｍμ求めるための第一距離候補探索プログラム、
選択された区分境界が点でない場合に、式（５５）〜式（５８）でmμ,1,mμ,2,mμ,3,mμ,4を求めてから、距離候補mμ=min{mμ,1,mμ,2,mμ,3,mμ,4}を求めるための第二距離候補探索プログラム、
第一距離候補探索プログラムと第二距離候補探索プログラムの実行で得られた値のうちから最小のもの（最小距離）を算出するための第二最小距離算出プログラム、
およびこれらのプログラムの処理において必要となるデータなどが記憶されている。その他、これらのプログラムに基づく処理などを制御するための制御プログラムも適宜に記憶しておく。
【０２３２】
多項式間距離算出装置（１）では、外部記憶装置（１７）〔あるいはＲＯＭなど〕に記憶された各プログラムとこの各プログラムの処理に必要なデータが必要に応じてメモリ（２０）に読み込まれて、適宜にＣＰＵ（１４）で解釈実行・処理される。その結果、ＣＰＵ（１４）が所定の機能（恒等式調査部、多項式数条件判定部、第一最小距離算出部、領域有界判定部、次数判定部、探索制御部、区分境界点判定部、第一距離候補探索部、第二距離候補探索部、第二最小距離算出部、制御部）を実現する。
【０２３３】
図１−１、図１−２を参照して、本実施形態における多項式間距離算出処理について説明する。
【０２３４】
多項式間距離算出装置（１）の外部記憶装置（１７）には、予め、多項式f(x),e1(x),e2(x),…,en(x)、多項式f(x)の零点が存在しない複素領域Ｄの境界Λ＝∪μ=1KΛμにつき、各区分境界Λμの有理式による表示（｛γ1,…,γK｝，｛I1,…,IK｝）〔各区分境界Λμは、単射γμ： Ｉμ  →  Λμで表示される。〕、領域Ｄを指定する一点Ｑがデータとして予め記憶されているとする。
【０２３５】
なお、これらの情報などは、予め多項式間距離算出装置（１）の外部記憶装置（１７）に記憶しておくのではなく、例えば、入力部（１１）から入力されるとしてもよいし、あるいは、これらの情報などを格納した記録媒体からドライブを駆動して読み込むようにしてもよく、適宜に変更可能である。
【０２３６】
また、データとして予め記憶される情報が、これらの情報などに限定される趣旨ではない。例えば、多項式f(x),e1(x),e2(x),…,en(x)について、多項式そのものを記憶するのではなく、各次数のｘの項についてその係数を記憶しておくようにしてもよい。また、例えば、境界Λを表す式自体を入力部（１１）から入力するとし、境界Λを区分境界に適宜に分割するためのプログラムを解釈・実行するＣＰＵ（１４）が、メモリ（２０）に格納された境界Λをメモリ（２０）から読み込んで、区分境界を出力するようにしてもよい。
【０２３７】
なお、本発明の細部においては、数値計算処理のみならず有理式や多項式などの数式処理も必要となるが、数値計算処理および数式処理自体は、公知技術と同様にして達成されるので、その演算処理方法などの詳細な説明は省略する（この点の技術水準を示す数式処理が可能なソフトウェアとしては、例えば、Risa/Asir、Maple（登録商標）、MATHEMATICA（登録商標第2312968号）、Gnuplotなどが挙げられる。Risa/Asirについては、例えばインターネット〈URL:http://www.math.kobe-u.ac.jp/Asir/asir-ja.html〉［平成20年5月2日検索］を参照のこと。Mapleについては、例えばインターネット〈URL:http://www.cybernet.co.jp/maple/〉［平成20年5月2日検索］を参照のこと。Gnuplotについては、例えばインターネット〈URL: http://www.gnuplot.info/〉［平成20年5月2日検索］を参照のこと。）。
【０２３８】
まず、多項式間距離算出装置（１）の制御部（１９９）は、外部記憶装置（１７）から多項式f(x),e1(x),e2(x),…,en(x)、各区分境界Λμの有理式による表示（｛γ1,…,γK｝，｛I1,…,IK｝）、領域Ｄを指定する一点Ｑを読み込み、それぞれをメモリ（２０）の所定の格納領域に格納しておく。以後、「メモリから○○を読み込む」旨の説明をした場合は、「メモリにおいて○○が格納されている所定の格納領域から○○を読み込む」ことを意味するとする。
【０２３９】
多項式間距離算出装置（１）の恒等式調査部（１００）は、メモリ（２０）から多項式f(x),e1(x),e2(x),…,en(x)を読み込み、f(x)+Σj=1najej(x)=0を満たす実数a1,a2,…,anの存在を判定する。恒等式調査部（１００）は、そのような実数a1,a2,…,anが存在すればＴ＝d(f,0)に設定してＴをメモリ（２０）の所定の格納領域に格納し、このような実数a1,a2,…,anが存在しない場合は、Ｔ＝∞に設定してＴをメモリ（２０）の所定の格納領域に格納する〔ステップＳ１〕。
【０２４０】
多項式間距離算出装置（１）の多項式数条件判定部（１１０）は、メモリ（２０）から多項式e1(x),e2(x),…,en(x)を読み込み、ｎ≧２であるか否かを判定する〔ステップＳ２〕。制御部（１９９）は、ｎ≧２が成立の場合、ステップＳ４０１の処理を実行するように制御を行い、ｎ＝１が成立の場合、ステップＳ３０１の処理を実行するように制御を行う。
【０２４１】
多項式間距離算出装置（１）の第一最小距離算出部（１２０）は、メモリ（２０）から多項式f(x),e1(x),e2(x),…,en(x)〔但し、実際にはf(x),e1(x)である。〕を読み込み、メモリ（２０）と協働して、ｎ＝１の場合の距離候補（既述の記法に従えば｜f(x)/e1(x)｜あるいはmini{t1(i)}）を算出し、この距離候補とメモリ（２０）に記憶されているＴのいずれか最小のものを新たなＴ（ｎ＝１の場合の最小距離Ｔ）としてメモリ（２０）の所定の格納領域に格納する〔ステップＳ３０１〜Ｓ３０５〕。そして、制御部（１９９）がメモリ（２０）に記憶されているＴを液晶ディスプレイなどに表示する出力処理を行って多項式間距離算出処理を終了する。もし、ステップＳ３０４の処理で条件を満たさない場合には、制御部（１９９）の制御により、多項式ｆ~が存在しない旨を通知するなどして多項式間距離算出処理を終了する〔ステップＳ３０６〕。
【０２４２】
多項式間距離算出装置（１）の領域有界判定部（１３０）は、メモリ（２０）から各区分境界Λμの有理式による表示（｛γ1,…,γK｝，｛I1,…,IK｝）、領域Ｄを指定する一点Ｑを読み込み、領域Ｄが有界であるか否かを判定する〔ステップＳ４０１〕。制御部（１９９）は、領域Ｄが有界であると判定された場合、ステップＳ５０の処理を実行するように制御を行い、領域Ｄが有界ではないと判定された場合、ステップＳ４０２の処理を実行するように制御を行う。
【０２４３】
多項式間距離算出装置（１）の次数判定部（１４０）は、メモリ（２０）から多項式f(x),e1(x),e2(x),…,en(x)を読み込み、全てのｉ（i=1,・・・,n）について多項式ei(x)の次数ｋｉが多項式ｆの次数ｍ未満であるか否かを判定する〔ステップＳ４０２〕。この判定に合格した場合、制御部（１９９）は、ステップＳ５０の処理を実行するように制御を行う。もし、ステップＳ４０２の処理で条件を満たさない場合には、制御部（１９９）の制御により、処理対象外である旨を通知するなどして多項式間距離算出処理を終了する〔ステップＳ４０３〕。
【０２４４】
次いで、多項式間距離算出装置（１）の探索制御部（１５０）は、未選択の区分境界の有無を判定する〔ステップＳ５０〕。未選択区分境界が存在しないと判定されると、制御部（１９９）が、ステップＳ５２の処理を実行するように制御を行う。未選択区分境界が存在すると判定されると、探索制御部（１５０）は、未選択区分境界から一つ選択して、その情報をメモリ（２０）の所定の格納領域に格納する〔ステップＳ５１〕。具体例として、探索制御部（１５０）は、区分境界Λμ（μ=1,2,…,K）について、μ=1からインクリメントしてμ=Kまで各処理を行うとすればよい。
【０２４５】
多項式間距離算出装置（１）の第二最小距離算出部（１９０）は、メモリ（２０）から、Ｔと区分境界毎に得られた距離候補m1,…,mμ,…,mKを読み込み、Ｔとmin｛m1,…,mμ,…,mK｝のいずれか最小のものを新たなＴ（ｎ≧２の場合の最小距離Ｔ）としてメモリ（２０）の所定の格納領域に格納する〔ステップＳ５２〕。そして、制御部（１９９）がメモリ（２０）に記憶されているＴを液晶ディスプレイなどに表示する出力処理を行って多項式間距離算出処理を終了する。
【０２４６】
多項式間距離算出装置（１）の区分境界点判定部（１６０）は、メモリ（２０）から、ステップＳ５１の処理で選択された区分境界に対応する実区間Ｉμを読み込み、実区間Ｉμが点であるか否かを判定する〔ステップＳ６〕。制御部（１９９）は、実区間Ｉμが点であると判定された場合、ステップＳ７１の処理を実行するように制御を行い、実区間Ｉμが点ではないと判定された場合、ステップＳ８１の処理を実行するように制御を行う。
【０２４７】
多項式間距離算出装置（１）の第一距離候補探索部（１７０）は、メモリ（２０）から、ステップＳ５１の処理で選択された区分境界の有理式による表示（γμ、Ｉμ：但し、実区間Ｉμの内実は点δである。）、多項式f(x),e1(x),e2(x),…,en(x)を読み込み、メモリ（２０）と協働して、点δが集合Ｉμ＼Δμに属する場合はｍμ＝Φμ(δ）を式（５１）の第二式で求め、点δが集合Δ~μに属する場合はｍμ＝Φμ(δ）を式（５１）の第一式で求め、点δがいずれの集合にも属さない場合にはｍμ＝∞として、距離候補ｍμをメモリ（２０）の所定の格納領域に格納する〔ステップＳ７１〜Ｓ７５〕。
【０２４８】
多項式間距離算出装置（１）の第二距離候補探索部（１８０）は、メモリ（２０）から、ステップＳ５１の処理で選択された区分境界の有理式による表示（γμ、Ｉμ）、多項式f(x),e1(x),e2(x),…,en(x)を読み込み、メモリ（２０）と協働して、式（５５）〜式（５８）でmμ,1,mμ,2,mμ,3,mμ,4を求めてから、mμ=min{mμ,1,mμ,2,mμ,3,mμ,4}を求め、距離候補ｍμをメモリ（２０）の所定の格納領域に格納する〔ステップＳ８１〜Ｓ８５〕。
【０２４９】
制御部（１９９）は、ステップＳ７２、Ｓ７４、Ｓ７５、Ｓ８５の各処理の後、ステップＳ５０の処理を実行するように制御を行う。
【０２５０】
[第２実施形態]
以下に、本発明の第２実施形態を上記アルゴリズム例〔図２−１、図２−２参照〕に則して説明する。第２実施形態は、多項式f(x)と多項式f~(x)=f(x)+Σj=1na~jej(x) (a~j∈Ｒ)との最小距離を与える多項式f~(x)の算出〔一変数最近実多項式算出〕に係わる。ここでは説明の便宜から、第１実施形態の最小距離の算出に加えて、多項式f~(x)も算出するものとして説明する。
【０２５１】
第２実施形態に係わる多項式間距離算出兼一変数最近実多項式算出装置のハードウェア構成は、図３に示した多項式間距離算出装置（１）のハードウェア構成と同様であるから、説明を略する。そこで、第２実施形態では、第１実施形態の多項式間距離算出装置（１）を、多項式間距離算出兼一変数最近実多項式算出装置（２）と呼称変更する。
【０２５２】
多項式間距離算出兼一変数最近実多項式算出装置（２）の外部記憶装置（１７）〔あるいはＲＯＭなど〕には、
多項式ｆ~が恒等的に０となる場合について調査するための恒等式調査プログラム、
入力された多項式f(x),e1(x),e2(x),…,en(x)の個数についてｎ≧２であるか否かを判定するための多項式数条件判定プログラム、
ｎ＝１の場合に最小距離を算出すると共にこの最小距離に対応する多項式ｆ~を算出するための第一最小距離算出プログラム、
ｎ≧２の場合に領域Ｄが有界であるか否かを判定するための領域有界判定プログラム、
多項式ei(x) （i=1,・・・,n）の次数ｋｉが多項式ｆの次数ｍ未満であるか否かを判定するための次数判定プログラム、
未選択の区分境界の有無を調べ、未選択の区分境界がある場合にはその中から一つの区分境界を選択するための探索制御プログラム、
選択された区分境界が点であるか否かを判定するための区分境界点判定プログラム、
選択された区分境界が点（区分境界に対応する実区間Ｉμが点δ）である場合に、点δが集合Ｉμ＼Δμに属する場合は式（５１）の第二式で距離候補ｍμを求め、点δが集合Δ~μに属する場合は式（５１）の第一式で距離候補ｍμ求めるための第一距離候補探索プログラム、
選択された区分境界が点でない場合に、式（５５）〜式（５８）でmμ,1,mμ,2,mμ,3,mμ,4を求めてから、距離候補mμ=min{mμ,1,mμ,2,mμ,3,mμ,4}を求めるための第二距離候補探索プログラム、
第一距離候補探索プログラムと第二距離候補探索プログラムの実行で得られた値のうちから最小のもの（最小距離）を算出すると共にこの最小距離に対応する多項式ｆ~を算出するための第二最小距離・多項式算出プログラム、
およびこれらのプログラムの処理において必要となるデータなどが記憶されている。その他、これらのプログラムに基づく処理などを制御するための制御プログラムも適宜に記憶しておく。
【０２５３】
多項式間距離算出兼一変数最近実多項式算出装置（２）では、外部記憶装置（１７）〔あるいはＲＯＭなど〕に記憶された各プログラムとこの各プログラムの処理に必要なデータが必要に応じてメモリ（２０）に読み込まれて、適宜にＣＰＵ（１４）で解釈実行・処理される。その結果、ＣＰＵ（１４）が所定の機能（恒等式調査部、多項式数条件判定部、第一最小距離・多項式算出部、領域有界判定部、次数判定部、探索制御部、区分境界点判定部、第一距離候補探索部、第二距離候補探索部、第二最小距離・多項式算出部、制御部）を実現する。
【０２５４】
図２−１、図２−２を参照して、本実施形態における多項式間距離算出処理について説明する。
【０２５５】
第２実施形態では、多項式間距離算出兼一変数最近実多項式算出装置（２）の外部記憶装置（１７）に、予め、多項式f(x),e1(x),e2(x),…,en(x)、多項式f(x)の零点が存在しない複素領域Ｄの境界Λ＝∪μ=1KΛμにつき、各区分境界Λμの有理式による表示（｛γ1,…,γK｝，｛I1,…,IK｝）〔各区分境界Λμは、単射γμ： Ｉμ  →  Λμで表示される。〕、領域Ｄを指定する一点Ｑがデータとして予め記憶されているとする。この点については第１実施形態と同様であり、例えば、これらの情報が入力部（１１）から入力されるとしてもよいし、多項式f(x),e1(x),e2(x),…,en(x)について、多項式そのものを記憶するのではなく、各次数のｘの項についてその係数を記憶しておくようにしてもよい。また、数値計算処理および数式処理が、公知技術と同様にして達成されることも既述のとおりである。
【０２５６】
まず、多項式間距離算出兼一変数最近実多項式算出装置（２）の制御部（２９９）は、外部記憶装置（１７）から多項式f(x),e1(x),e2(x),…,en(x)、各区分境界Λμの有理式による表示（｛γ1,…,γK｝，｛I1,…,IK｝）、領域Ｄを指定する一点Ｑを読み込み、それぞれをメモリ（２０）の所定の格納領域に格納しておく。
【０２５７】
多項式間距離算出兼一変数最近実多項式算出装置（２）の恒等式調査部（２００）は、メモリ（２０）から多項式f(x),e1(x),e2(x),…,en(x)を読み込み、f(x)+Σj=1najej(x)=0を満たす実数a1,a2,…,anの存在を判定する。恒等式調査部（２００）は、そのような実数a1,a2,…,anが存在すればＴ＝d(f,0)、Ｐ＝０に設定してＴおよびＰをメモリ（２０）の所定の格納領域に格納し、このような実数a1,a2,…,anが存在しない場合は、Ｔ＝∞、Ｐ＝−１に設定してＴおよびＰをメモリ（２０）の所定の格納領域に格納する〔ステップＳ１ａ〕。
【０２５８】
多項式間距離算出兼一変数最近実多項式算出装置（２）の多項式数条件判定部（２１０）は、メモリ（２０）から多項式e1(x),e2(x),…,en(x)を読み込み、ｎ≧２であるか否かを判定する〔ステップＳ２〕。制御部（２９９）は、ｎ≧２が成立の場合、ステップＳ４０１の処理を実行するように制御を行い、ｎ＝１が成立の場合、ステップＳ３０１の処理を実行するように制御を行う。
【０２５９】
多項式間距離算出兼一変数最近実多項式算出装置（２）の第一最小距離・多項式算出部（２２０）は、メモリ（２０）から多項式f(x),e1(x),e2(x),…,en(x)〔但し、実際にはf(x),e1(x)である。〕を読み込み、メモリ（２０）と協働して、ｎ＝１の場合の距離候補（既述の記法に従えば｜f(x)/e1(x)｜あるいはmini{t1(i)}）および多項式候補（既述の記法に従えば０あるいはf(x)+mini{|t1(i)|}e1(x)）を算出し、この距離候補とメモリ（２０）に記憶されているＴのいずれか最小のものを新たなＴ（ｎ＝１の場合の最小距離Ｔ）としてメモリ（２０）の所定の格納領域に格納する〔ステップＳ３０１〜Ｓ３０５ａ〕。ここでＴの書き換えが行われた場合は、メモリ（２０）に記憶されているＰを多項式候補で書き換えるが、Ｔの書き換えが行われなかった場合は、メモリ（２０）に記憶されているＰの書き換えを行わない。そして、制御部（２９９）がメモリ（２０）に記憶されているＴおよびＰを液晶ディスプレイなどに表示する出力処理を行って多項式間距離算出処理を終了する。もし、ステップＳ３０４の処理で条件を満たさない場合には、制御部（２９９）の制御により、多項式ｆ~が存在しない旨を通知するなどして多項式間距離算出処理を終了する〔ステップＳ３０６〕。
【０２６０】
多項式間距離算出兼一変数最近実多項式算出装置（２）の領域有界判定部（２３０）は、メモリ（２０）から各区分境界Λμの有理式による表示（｛γ1,…,γK｝，｛I1,…,IK｝）、領域Ｄを指定する一点Ｑを読み込み、領域Ｄが有界であるか否かを判定する〔ステップＳ４０１〕。制御部（２９９）は、領域Ｄが有界であると判定された場合、ステップＳ５０の処理を実行するように制御を行い、領域Ｄが有界ではないと判定された場合、ステップＳ４０２の処理を実行するように制御を行う。
【０２６１】
多項式間距離算出兼一変数最近実多項式算出装置（２）の次数判定部（２４０）は、メモリ（２０）から多項式f(x),e1(x),e2(x),…,en(x)を読み込み、全てのｉ（i=1,・・・,n）について多項式ei(x)の次数ｋｉが多項式ｆの次数ｍ未満であるか否かを判定する〔ステップＳ４０２〕。この判定に合格した場合、制御部（２９９）は、ステップＳ５０の処理を実行するように制御を行う。もし、ステップＳ４０２の処理で条件を満たさない場合には、制御部（２９９）の制御により、処理対象外である旨を通知するなどして多項式間距離算出処理を終了する〔ステップＳ４０３〕。
【０２６２】
次いで、多項式間距離算出兼一変数最近実多項式算出装置（２）の探索制御部（２５０）は、未選択の区分境界の有無を判定する〔ステップＳ５０〕。未選択区分境界が存在しないと判定されると、制御部（２９９）が、ステップＳ５２の処理を実行するように制御を行う。未選択区分境界が存在すると判定されると、探索制御部（２５０）は、未選択区分境界から一つ選択して、その情報をメモリ（２０）の所定の格納領域に格納する〔ステップＳ５１〕。具体例として、探索制御部（２５０）は、区分境界Λμ（μ=1,2,…,K）について、μ=1からインクリメントしてμ=Kまで各処理を行うとすればよい。
【０２６３】
多項式間距離算出兼一変数最近実多項式算出装置（２）の第二最小距離・多項式算出部（２９０）は、メモリ（２０）から、Ｔと区分境界毎に得られた距離候補m1,…,mμ,…,mKを読み込み、Ｔとmin｛m1,…,mμ,…,mK｝のいずれか最小のものを新たなＴ（ｎ≧２の場合の最小距離Ｔ）としてメモリ（２０）の所定の格納領域に格納する〔ステップＳ５２ａ〕。また、第二最小距離算出部（２９０）は、Ｔの書き換えが行われた場合は、このＴを与えたmｘ（x∈{1,…,K}）がステップＳ７２、Ｓ８２、Ｓ８４のいずれかで得られたものである場合には多項式Ｐを式（４７ｉ）で求め、このＴを与えたmｘ（x∈{1,…,K}）がステップＳ７４、Ｓ８１、Ｓ８３のいずれかで得られたものである場合には多項式Ｐを式（４７ｋ）で求め、この多項式Ｐでメモリ（２０）に記憶されているＰを書き換える。但し、Ｔの書き換えが行われなかった場合は、メモリ（２０）に記憶されているＰの書き換えを行わない。そして、制御部（２９９）がメモリ（２０）に記憶されているＴを液晶ディスプレイなどに表示する出力処理を行って多項式間距離算出処理を終了する。
【０２６４】
多項式間距離算出兼一変数最近実多項式算出装置（２）の区分境界点判定部（２６０）は、メモリ（２０）から、ステップＳ５１の処理で選択された区分境界に対応する実区間Ｉμを読み込み、実区間Ｉμが点であるか否かを判定する〔ステップＳ６〕。制御部（２９９）は、実区間Ｉμが点であると判定された場合、ステップＳ７１の処理を実行するように制御を行い、実区間Ｉμが点ではないと判定された場合、ステップＳ８１の処理を実行するように制御を行う。
【０２６５】
多項式間距離算出兼一変数最近実多項式算出装置（２）の第一距離候補探索部（２７０）は、メモリ（２０）から、ステップＳ５１の処理で選択された区分境界の有理式による表示（γμ、Ｉμ：但し、実区間Ｉμの内実は点δである。）、多項式f(x),e1(x),e2(x),…,en(x)を読み込み、メモリ（２０）と協働して、点δが集合Ｉμ＼Δμに属する場合はｍμ＝Φμ(δ）を式（５１）の第二式で求め、点δが集合Δ~μに属する場合はｍμ＝Φμ(δ）を式（５１）の第一式で求め、点δがいずれの集合にも属さない場合にはｍμ＝∞として、距離候補ｍμをメモリ（２０）の所定の格納領域に格納する〔ステップＳ７１〜Ｓ７５〕。
【０２６６】
多項式間距離算出兼一変数最近実多項式算出装置（２）の第二距離候補探索部（２８０）は、メモリ（２０）から、ステップＳ５１の処理で選択された区分境界の有理式による表示（γμ、Ｉμ）、多項式f(x),e1(x),e2(x),…,en(x)を読み込み、メモリ（２０）と協働して、式（５５）〜式（５８）でmμ,1,mμ,2,mμ,3,mμ,4を求めてから、mμ=min{mμ,1,mμ,2,mμ,3,mμ,4}を求め、距離候補ｍμをメモリ（２０）の所定の格納領域に格納する〔ステップＳ８１〜Ｓ８５〕。
【０２６７】
制御部（２９９）は、ステップＳ７２、Ｓ７４、Ｓ７５、Ｓ８５の各処理の後、ステップＳ５０の処理を実行するように制御を行う。
【０２６８】
第２実施形態では、最小距離と多項式ｆ~を出力するものとしたが、多項式ｆ~のみを出力するようにすれば、多項式間距離算出兼一変数最近実多項式算出装置（２）は一変数最近実多項式算出装置として動作することになる。
【０２６９】
本発明である多項式間距離算出装置、多項式間距離算出方法、一変数最近実多項式算出装置、一変数最近実多項式算出方法は上述の実施形態に限定されるものではなく、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。例えば、重みつきのｌ∞-ノルム maxj{wj|aj|} (0<wj)を用いる場合は、{e1(x),…,en(x)}の代わりに{e1(x)/w1,…,en(x)/wn}を用いればよい。また、上記実施形態において説明した処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されるとしてもよい。
【０２７０】
また、上記実施形態において説明した多項式間距離算出装置、一変数最近実多項式算出装置における処理機能をコンピュータによって実現する場合、多項式間距離算出装置、一変数最近実多項式算出装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記多項式間距離算出装置、一変数最近実多項式算出装置における処理機能がコンピュータ上で実現される。
【０２７１】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（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）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０２７４】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、多項式間距離算出装置、一変数最近実多項式算出装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【実施例】
【０２７５】
図１−１および図１−２に示したアルゴリズムに則った最小距離算出の具体的な実施例を説明する。
【０２７６】
ｆ(ｘ）＝ｘ２＋２とし、領域Ｄを単位円の周および内部からなる有界閉領域とし、境界Λは、Λ１＝｛１｝とΛ２＝Λ＼Λ１の和集合とする。ただし、Λ１，Λ２は式（６５）の通り表されているものとする。ただし、Ｉ１＝｛１｝，Ｉ２＝Ｒである（Ｒは実数全体の集合）。
【数１０３】
2009271888.tif 000086
【０２７７】
このとき、領域Ｄに零点を持ち多項式ｆに一番近い多項式
f~(x)=f(x)+a~1e1(x)+a~2e2(x)+a~3e3(x) (a~1,a~2,a~3∈R)
を求める場合にアルゴリズム２の挙動を示す。ただし、ｅ１(ｘ)＝ｘ２，ｅ２(ｘ)＝ｘ，ｅ３(ｘ)＝１とする。ここでは、上記設定からステップＳ５０番台、ステップＳ６、ステップＳ７０番台、ステップＳ８０番台の処理を中心に説明する。
【０２７８】
・ステップＳ１
Ｔ＝∞とおく。
【０２７９】
・ステップＳ５０、Ｓ５１、Ｓ６、Ｓ７１〜７５
まず、μ＝１とする。ｆ(１）＝３であり、ｅ１(１）＝ｅ２(１）＝ｅ３(１）＝１は一直線上（実軸上）にあり、しかも、ｅ１(１）≠０だから、１を零点とする最近多項式ｆ~＝−ｘ＋１が存在する。距離候補ｍ１は１である。
【０２８０】
・ステップＳ５０、Ｓ５１、Ｓ６、Ｓ８１〜８５
次にμ＝２とする。このとき、式（６６）が得られる。
【数１０４】
2009271888.tif 000087
【０２８１】
よって、式（６７）が得られる。
【数１０５】
2009271888.tif 000088
【０２８２】
従って、
Δ２＝Δ~２＝｛０｝，  Ｚ~２＝φ，  Ｚ２＝｛−１，１｝
となるから、
Δ２＼Δ~２＝φ
であり、また、Ｊ２＝（−∞，０）∪（０，∞）から、
Ｊ２＼Ｚ２＝（−∞，−１）∪（−１，０）∪（０，１）∪（１，∞）
である。
【０２８３】
Δ~２およびＺ２においては、
Φ２(０）＝１，  Φ２(−１）＝Φ２(１）＝１／２
が得られる。
【０２８４】
Ｊ２＼Ｚ２においては、式（６８）が得られる。
【数１０６】
2009271888.tif 000089
【０２８５】
これらから以下を得る。
ｍ２，１＝∞，ｍ２，２＝ｍ２，４＝１／２，ｍ２，３＝１
したがって、
ｍ２＝min｛m2,1,m2,2,m2,3,m2,4｝＝１／２
【０２８６】
・ステップＳ５２
２．ｍ１＝１，ｍ２＝１／２より、
min｛m1,m2｝＝１／２
となる。ステップＳ１でＴ＝∞であるから、最小距離は１／２である。
上記例の場合、最近多項式ｆ~は±ｉに零点を持つ（３ｘ２＋３）／２となる。
【産業上の利用可能性】
【０２８７】
本発明は、例えば、複素領域Ｄに零点を持たないように多項式の係数を設定したい場合に、係数設定に誤差を伴うことを前提として、誤差付きで設定される多項式が間違いなく複素領域Ｄに零点を持たないようにするときに、その誤差限界の確定などとして用いることができる。このような場合の一例として、ディジタル信号処理におけるディジタルフィルタ（例えば、ＩＩＲ〔Infinite Impulse Response〕フィルタ）の設計などに有用である。
【図面の簡単な説明】
【０２８８】
【図１−１】第１実施形態の多項式間距離算出処理のフローチャート（其の壱）。
【図１−２】第１実施形態の多項式間距離算出処理のフローチャート（其の弐）。
【図２−１】第２実施形態の多項式間距離算出兼一変数最近実多項式算出処理のフローチャート（其の壱）。
【図２−２】第２実施形態の多項式間距離算出兼一変数最近実多項式算出処理のフローチャート（其の弐）。
【図３】多項式間距離算出装置（１）のハードウェア構成を例示した構成ブロック図。
【図４】多項式間距離算出処理の処理機能を示す機能ブロック図。
【図５】多項式間距離算出兼一変数最近実多項式算出処理の処理機能を示す機能ブロック図。
【図６−１】アルゴリズム１の挙動を説明するための具体例。（ａ）４つの関数f1,f2,f3,f4と実区間Ｉを入力とする。（ｂ）２つの関数f1,f2と実区間Ｉを入力としたアルゴリズム１の結果。（ｃ）２つの関数f3,f4と実区間Ｉを入力としたアルゴリズム１の結果。
【図６−２】アルゴリズム１の挙動を説明するための具体例。（ｄ）２つの関数f1,f2と実区間Ｉを入力としたアルゴリズム１の結果と、２つの関数f3,f4と実区間Ｉを入力としたアルゴリズム１の結果とから得られるI1,j∩I2,k≠φ（空集合）となる区間の対を示す図。（ｅ）区間I1,j∩I2,k≠φごとのアルゴリズム１の結果。（ｆ）４つの関数f1,f2,f3,f4と実区間Ｉを入力されたアルゴリズム１の結果。
【符号の説明】
【０２８９】
１        多項式間距離算出装置
１００    恒等式調査部
１１０    多項式数条件判定部
１２０    第一最小距離算出部
１３０    領域有界判定部
１４０    次数判定部
１５０    探索制御部
１６０    区分境界点判定部
１７０    第一距離候補探索部
１８０    第二距離候補探索部
１９０    第二最小距離算出部
２        多項式間距離算出兼一変数最近実多項式算出装置
２００    恒等式調査部
２１０    多項式数条件判定部
２２０    第一最小距離・多項式算出部
２３０    領域有界判定部
２４０    次数判定部
２５０    探索制御部
２６０    区分境界点判定部
２７０    第一距離候補探索部
２８０    第二距離候補探索部
２９０    第二最小距離・多項式算出部
【図１−１】
2009271888.tif 000109
【図１−２】
2009271888.tif 000110
【図２−１】
2009271888.tif 000111
【図２−２】
2009271888.tif 000112
【図３】
2009271888.tif 000113
【図４】
2009271888.tif 000114
【図５】
2009271888.tif 000115
【図６−１】
2009271888.tif 000116
【図６−２】
2009271888.tif 000117