説明

多項式間距離算出装置、方法および記録媒体、一変数最近実多項式算出装置、方法および記録媒体

【課題】複素領域Dに零点を持つ一変数実多項式のうち、領域Dに零点を持たない一変数実多項式fに最も近い一変数実多項式f~と、一変数実多項式fとのl-ノルムで定義された距離を、最悪の場合であっても多項式時間の計算量で求める。
【解決手段】領域Dの境界Λ上の点αに対して、この点αを零点とする一変数実多項式のうち一変数実多項式f(x)に最も近い一変数実多項式g(x)と一変数実多項式f(x)との距離を与える関数Φ(α)を用いて、区分境界Λ12,…,ΛKごとに関数Φ(α)の最小値を求め(距離候補探索:S50、S51、S6、S71〜75、S81〜85)、この距離候補探索で得られた値のうち最小のものを求める(最小距離算出:S52)。

【発明の詳細な説明】
【技術分野】
【0001】
本発明は、複素数全体の集合内の指定された領域に零点を持つ一変数実多項式のうち、上記領域に零点を持たない或る一変数実多項式fに最も近い一変数実多項式f~について、一変数実多項式fと一変数実多項式f~との距離を求める技術に関する。
【背景技術】
【0002】
f(x),e1(x),e2(x),…,en(x)は、それぞれ予め与えられた一変数実多項式〔係数が実数の一変数多項式〕であるとする。但し、実数全体の集合をRと表記すると、e1(x),e2(x),…,en(x)はR上一次独立とする。つまり、実数c1,c2,…,cnに対して、c1e1(x)+c2e2(x)+…+cnen(x)が恒等的に0となるのは、c1=c2=…=cn=0の場合に限られるとする。また、複素数全体の集合をCと表記する。
【0003】
このとき、次の問題☆を考える。なお、この明細書中において記号~は直前の文字の頭上に附されるものとする。
[問題☆]
一変数実多項式f(x)がC内の予め与えられた領域Dに零点を持たないとする。このとき、式(1)で表される一変数実多項式の集合Fのうち、領域Dに零点を持ち、かつ、一変数実多項式f(x)に最も近い一変数実多項式f~(x)について、一変数実多項式f(x)と一変数実多項式f~(x)との距離を求めよ。また、このような一変数実多項式f~(x)を一つ求めよ。
【数20】

【0004】
但し、二つの一変数実多項式g,hの距離d(g,h)は、g-hの係数のl-ノルム〔最大値ノルム〕で定義する。即ち、式(2)で表される二つの一変数実多項式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の係数のl-ノルムを‖g-h‖とも表記する場合がある。
【数21】

【0005】
なお、多項式の表記に際して変数xを明記したい場合にはf(x),g(x)の如く表すこととし、それ以外の場合には、単にf,gの如く表すこととする。また、特に断りの無い限り、「一変数実多項式」を「多項式」と略記する。
【0006】
上記問題☆を考えることには、実用上の利益がある。例えばディジタル信号処理やシステム制御のような伝達関数による制御などにおいて、所望の特性を得るために、領域Dに零点を持たないように多項式の係数を設定したい場合がある。しかし、係数は有限の精度でしか指定できないため、その設定には一般的に誤差を伴う。そこで、所望の領域Dに零点を確実に持たないように多項式の係数を設定するには、係数設定に誤差を伴うことを前提として、誤差範囲内のどのような多項式であっても間違いなく領域Dに零点を持たないようにすることが望まれる。そこで、上記問題☆を解決する必要がある。視点を変えて説明すると、このことは、領域Dに零点を持たないことが既知である多項式fの「領域Dに零点を持たない」という性質を保ったまま多項式fの係数を動かすときのその限界を求めることであり、このような限界は、多項式fとこれに最も近い多項式f~との距離〔l-ノルム〕として与えられる。
【0007】
上記問題☆に関連して、非特許文献1が挙げられる。この非特許文献1では、与えられた複素数γを零点とする複素係数多項式に対して、上記問題☆に類似する問題を扱っている。なお、非特許文献1は複素係数多項式を取り上げているが、非特許文献1中に示唆されているように、実係数多項式(実多項式)の場合にも適用できるように体系化できる。
上記問題☆と非特許文献1が取り上げている問題との違いは、上記問題☆が与えられた領域に零点を持つ多項式を対象としていることに対して、非特許文献1が取り上げている問題は与えられた一点を零点とする多項式を対象として距離最小のものを求める点にある。
【0008】
零点の存在場所が一点ではなく領域となっている問題を扱った研究として、非特許文献2が挙げられる。
この非特許文献2では、距離を上記の如くl-ノルムとして問題を解く場合には、領域ではなく一点に零点を持つ場合に限定している。また、零点の存在場所が領域の場合について問題を解く場合には、二つの多項式f(x)とg(x)との間の距離をl-ノルム、即ち、f(x)-g(x)の係数から決まるベクトルのl-ノルム ((a1-b1)2+…+(an-bn)2)1/2で定義した場合にのみ解決している。
【0009】
二つの多項式f(x)とg(x)間の距離をl-ノルムで定義して上記問題☆を扱った研究として非特許文献3が挙げられる。以下、非特許文献3の内容について概説する。
【0010】
まず、以下の条件を仮定する。
〈1〉領域Dは閉集合である複素領域である。
〈2〉領域Dの境界Λは長さが有限な単純閉曲線であり、一つ以上の有限個の区分境界Λkの和集合として表現される。即ち、境界Λは、Λ=∪μ=1KΛμ=Λ1∪Λ2∪・・・∪ΛK(整数Kは1≦K<∞を満たす。)且つ、Λj∩Λk=φ(j≠k)と表現される。但し、φは空集合を表す。また、各区分境界Λμは、単射のγμによって、
γμ: Iμ → Λμ
と表示される。ここでγμは有理式であって、分母・分子の多項式の係数は実代数的数a,bおよび虚数単位iを用いてa+biと表現されるものに限る。Iμ⊂Rは、α,βを実代数的数として[α,β]、[α,∞)、(−∞,β]、(−∞,∞)のいずれかであるとする。
【0011】
このとき距離最小の多項式f~=f+Σj=1について、以下の性質が成り立つ。
[性質1] 少なくとも一つの零点は領域Dの境界Λ上に存在する。より詳細には、多項式f~がゼロ多項式の場合を除くと、多項式f~の領域D上の全ての零点は領域Dの境界Λ上に在る。
[性質2] 高々一つの例外の係数を除き、|tj|=d(f,f~)が成り立つ。
【0012】
よって、以下の二つの場合に分けて上記問題☆を扱う。
≪第一の場合≫全てのjに対して、|tj|=d(f,f~)が成り立つ場合。
≪第二の場合≫|tμ|<d(f,f~)となるμが存在する場合。
【0013】
≪第一の場合≫では、xとtに関する連立方程式(3)をx∈Λかつt,…,t∈Rという条件の下で解き、解の中で|t1|=…=|tn|が最小となるものが最小距離であり、それに対応する多項式が、‖f-f~が最小となる多項式f~である。上記条件を満たす解が無い場合は、式(1)で表される集合Fに属する多項式であって≪第一の場合≫の条件を満たし且つ領域Dに零点を持つ多項式は存在しない。
【数22】

【0014】
≪第二の場合≫では、μと異なる番号jについては|tj|=d(f,f~)であるから、連立方程式(4)をx∈Λかつt,…,t∈Rという条件の下で解き、解の中で|t1|=…=|tμ-1|=|tμ+1|=|tn|が最小となるものが最小距離であり、それに対応する多項式が、‖f-f~が最小となる多項式f~である。上記条件を満す解が無い場合は、式(1)で表される集合Fに属する多項式であって≪第二の場合≫の条件を満たし且つ領域Dに零点を持つ多項式は存在しない。
【数23】

【非特許文献1】H. J. Stetter, "The Nearest Polynomial with a Given Zero, and Similar Problems," ACM SIGSAM Bulletin, Vol.33, No.4, pp.2-4, 1999.
【非特許文献2】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.
【非特許文献3】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.
【発明の開示】
【発明が解決しようとする課題】
【0015】
上記非特許文献1の手法によれば、与えられた多項式に最も近い、与えられた一点を零点とする多項式を求めることはできる。しかし、与えられた「一点」を「領域」とした上記問題☆に上記非特許文献1の手法を適用できない。
【0016】
また、上記非特許文献2の手法では、l-ノルムで距離をはかる場合、過剰決定の連立一次方程式の近似解を求める手法を利用している。これを零点の存在場所が領域の場合に拡張することは、非特許文献2に述べられているとおり、困難である。また、l-ノルムで距離をはかる場合には、零点の存在場所が領域の場合も扱えるが、l-ノルムに特化した手法であるため、l-ノルムで距離をはかる場合には上記非特許文献2の手法を用いることができない。つまり、上記非特許文献2の手法では、上記問題☆に回答を与えることができない。
【0017】
上記非特許文献3の手法では、最悪の場合、解く必要のある方程式の数が、eの個数nを指数とする指数関数で表現されるオーダーの個数となる。
【0018】
上記≪第一の場合≫では、連立方程式(3)がx∈Λかつt,…,t∈Rという解を持つことは、方程式(5)のうち少なくとも一つの方程式がx∈Λかつt∈Rという解を持つことと同値である。ここで、±は、+と−の全ての組み合わせを取るので、組み合わせは全部で2n−1通りである。即ち、最悪の場合、2n−1本の方程式を解く必要がある。
f(x)+t(e1(x)±e2(x)±…±en(x))=0 (5)
【0019】
また、上記≪第二の場合≫では、連立方程式(4)がx∈Λかつt,…,t∈Rという解を持つことは、方程式(6)のうちの少なくとも一つの方程式がx∈Λ,tμ,t∈R,|tμ|<|t|という解を持つことと同値である。ここで、±は、+と−の全ての組み合わせを取るので、組み合わせは全部で2n−2通りである。μの選び方がn通りあるので、最悪の場合、2n−2・n本の方程式を解く必要がある。
f(x)+tμeμ(x)+t(e1(x)±…±eμ-1(x)±eμ+1(x)±…±en(x))=0 (6)
【0020】
従って、eの個数nが多い場合に、非特許文献3の手法が現実的であるとは言い難い。
【0021】
そこで本発明は、複素数全体の集合内の指定された領域Dに零点を持つ一変数実多項式のうち、領域Dに零点を持たない或る一変数実多項式fに最も近い一変数実多項式f~と、一変数実多項式fとのl-ノルムで定義された距離を、最悪の場合であっても多項式時間の計算量で求める、多項式間距離算出装置、方法および記録媒体、さらに、一変数実多項式f~を求める、一変数最近実多項式算出装置、方法および記録媒体、提供することを目的とする。
【課題を解決するための手段】
【0022】
上記課題を解決するために、本発明では、Rを実数全体の集合とし、f(x),e1(x),…,en(x)をそれぞれ予め与えられた一変数実多項式とし、二つの一変数実多項式の距離をl-ノルムで定義し、一変数実多項式f(x)が複素数全体の集合内の閉な領域Dに零点を持たないとして、一変数実多項式の集合
【数24】

に属する一変数実多項式であって、領域Dに零点を持ち、かつ、一変数実多項式f(x)に最も近い一変数実多項式f~(x)について、一変数実多項式f(x)と一変数実多項式f~(x)との距離を以下のとおり算出する。
一変数実多項式f(x),e1(x),…,en(x)と、領域Dの境界Λを構成する有限個の区分境界Λ12,…,ΛKとが記憶手段に記憶されており、境界Λ上の点αに対して、集合Fに属しこの点αを零点とする一変数実多項式のうち一変数実多項式f(x)に最も近い一変数実多項式g(x)と一変数実多項式f(x)との距離を与える関数Φ(α)を用いて、区分境界Λ12,…,ΛKごとに関数Φ(α)の最小値を求め(距離候補探索)、この距離候補探索で得られた値のうち最小のものを求める(最小距離算出)。
詳細な理論は後述するが、一変数実多項式f~(x)の領域D上の零点は領域Dの境界Λ上にのみ存在するので、点αを境界Λ上で動かしたときの関数Φ(α)の最小値が最小距離となる。
【0023】
ここで関数Φ(α)を次のとおりとすればよい。複素数の実部と虚部をそれぞれRe,Imで表すとして、複素数u,vに対する行列式
【数25】

を定義し、iを虚数単位とし、
[1]1≦j<k≦nなる全てのj,kに対してA(ej(α),ek(α))=0が成立し、かつ、A(ej(α),f(α))=0がj=1,…,nに対して成立ち、かつ、e(α)≠0となるjが存在する場合に、関数Φ(α)は、
【数26】

であり、
[2]或るj,k(1≦j<k≦n)に対してA(ej(α),ek(α))≠0が成立する場合に、関数Φ(α)は、
【数27】

(但し、分母が0となるものは除く。)であるとする。
【0024】
上記距離候補探索では、各区分境界Λμ(但しμ=1,2,…,K)が点であるか否かを判定する区分境界点判定を行うことができる。この場合、距離候補探索では、区分境界Λμが点であると判定されなかった場合に、上記[1]の場合を、少なくとも一つのjについてA(ej(α),if(α))=0が成立する場合S1とそれ以外の場合S2に分け、上記[2]の場合を、少なくとも一つのjについてA(ej(α),f(α))=0または1≦j<k≦nなるj,kに対してA(ej(α),ek(α))=0が成立する場合S3とそれ以外の場合S4に分け、当該区分境界Λμでの関数Φ(α)の最小値を、各場合S1〜S4の関数Φ(α)の各最小値のうち最小のものとする。この理論的な詳細は後述する。
【0025】
また、各区分境界Λμ(但しμ=1,2,…,K)が、実数上の集合Iμに対する有理式で表される単射γμ(s) (但しs∈Iμ)で与えられるとし、集合Δμ
【数28】

とし、集合Δ~μ⊂Δμ
【数29】

とし、集合Z~μ⊂Δ~μ
【数30】


とし、集合Zμ⊂Δμ
【数31】

とし、区分境界Λμに対応する関数Φ(α)を
【数32】

で表すとして、上記距離候補探索では、上記区分境界点判定で点であると判定された区分境界Λμについて、実数上の集合Iμ(={δ})が集合Iμ\Δμに属する場合に、当該区分境界Λμでの関数Φμ(s)の最小値を、
【数33】

で求め、実数上の集合Iμ(={δ})が上記集合Δ~μに属する場合に、当該区分境界Λμでの関数Φμ(s)の最小値を、
【数34】

で求める第一距離候補探索と、上記区分境界点判定で点であると判定されなかった区分境界Λμについて、上記S1の場合に上記集合Z~μの有限個の元σについて、mμ,1
【数35】

で求め、上記S2の場合に有限個の区間の和集合で表される集合Δ~μ\Z~μに属する元σについて,mμ,3
【数36】

で求め、上記S3の場合に上記集合Zμの有限個の元σについて、mμ,2
【数37】

で求め、上記S4の場合に有限個の区間の和集合で表される集合(Iμ\Δμ)\Zμに属する元σについて,mμ,4
【数38】

で求め、当該区分境界Λμでの関数Φμ(s)の最小値をmin{mμ,1,mμ,2,mμ,3,mμ,4}で求める第二距離候補探索とを含むことができる。この理論的な詳細は後述する。
【0026】
また、本発明では、領域Dが非有界の場合には、集合Fの次数が一定であることが要求される。そこで、領域Dが有界であるか否かを判定する領域有界判定と、領域Dが有界でない場合に、集合Fの次数が一定であるか否かを判定する次数判定とを行うようにしてもよい。
【0027】
また、多項式
【数39】

が恒等的に0となる実数a1,a2,…,anが存在するか否かを判定し、存在する場合には一変数実多項式f(x)と恒等的に0の多項式との距離を求める恒等式調査を行う場合には、上記最小距離算出に代えて、距離候補探索で得られた値および恒等式調査で得られた距離のうち最小のものを求める第二最小距離算出を行うようにすることができる。
これにより、恒等的に0の多項式との距離についても考慮を要求する場合の最小距離を求めることができる。この理論的な詳細は後述する。
【0028】
また、詳しい理論は後述するが、後述する命題、補題、定理などに基づき、最小距離が求められると一変数実多項式f~も求められる。
【0029】
また、本発明の多項式間距離算出装置としてコンピュータを機能させる多項式間距離算出プログラムによって、コンピュータを多項式間距離算出装置として作動処理させることができるところ、このようなプログラムを記録した、コンピュータによって読み取り可能なプログラム記録媒体によって、他のコンピュータを多項式間距離算出装置として機能させることや、プログラムを流通させることなどが可能になる。
【0030】
同様に、本発明の一変数最近実多項式算出装置としてコンピュータを機能させる一変数最近実多項式算出プログラムによって、コンピュータを一変数最近実多項式算出装置として作動処理させることができるところ、このようなプログラムを記録した、コンピュータによって読み取り可能なプログラム記録媒体によって、他のコンピュータを一変数最近実多項式算出装置として機能させることや、プログラムを流通させることなどが可能になる。
【0031】
なお、一つの記録媒体に、これらのプログラムを記録することができる。
【発明の効果】
【0032】
上記非特許文献3の手法では、多項式間距離を変数として、最小距離が満たす代数方程式を導出することで、最小の多項式間距離を算出するため、最悪の場合に、解く必要のある方程式の数が、eの個数nを指数とする指数関数で表現されるオーダーの個数となる。これに対して本発明によれば、境界Λ上の点αに対して、集合Fに属しこの点αを零点とする一変数実多項式のうち一変数実多項式f(x)に最も近い一変数実多項式g(x)と一変数実多項式f(x)との距離を与える関数Φ(α)を用いて、区分境界Λ12,…,ΛKごとに関数Φ(α)の最小値を求めることで、最悪の場合であっても多項式時間の計算量で最小距離を求めることが可能になっている。事実、詳細は後述するが、解く必要のある方程式の数が一変数実多項式eの個数nの多項式のオーダーで収まる演算で求めるアルゴリズムが存在する。また、最小距離が求まると、後述の補題等により一変数実多項式f~も求めることができる。
【発明を実施するための最良の形態】
【0033】
[理論]
本発明の実施形態の説明に先立ち、本発明の理論について説明する。
まず、本発明では、複素数全体の集合C内の予め与えられた領域Dを閉な複素領域とし、領域Dの境界Λは一定の条件が課された有限の長さの単純閉曲線とする。
即ち、本発明の解決すべき問題は、次のとおりである。
===================================
≪問題≫
[条件]
〈1〉 f(x),e1(x),e2(x),…,en(x)は、それぞれ予め与えられた一変数実多項式であるとする。但し、実数全体の集合Rについて、e1(x),e2(x),…,en(x)はR上一次独立とする。
〈2〉 一変数実多項式f(x)が複素数全体の集合C内の予め与えられた領域Dに零点を持たないとする。但し、領域Dは閉な複素領域であり、領域Dの境界Λは有限の長さの単純閉曲線とする。
〈3〉 境界Λは、一つ以上の有限個の区分境界Λμの和集合として表現される。即ち、境界Λは、Λ=∪μ=1KΛμ=Λ1∪Λ2∪・・・∪ΛK(整数Kは1≦K<∞を満たす。)且つ、Λj∩Λk=φ(j≠k)と表現される。但し、φは空集合を表す。また、各区分境界Λμは、単射のγμによって、
γμ: Iμ → Λμ
と表示される。ここでγμは有理式であって、分母・分子の多項式の係数は実代数的数a,bおよび虚数単位iを用いてa+biと表現されるものに限る。Iμ⊂Rは、α,βを実代数的数として[α,β]、[α,∞)、(−∞,β]、(−∞,∞)のいずれかであるとする。
〈4〉 二つの一変数実多項式g,hの距離d(g,h)は、g-hの係数のl-ノルムで定義する。
〈5〉 領域Dが非有界の場合、式(7)で表される一変数実多項式の集合Fの次数は、ajに拠らず一定である。
〈6〉 nを1以上の正整数とする。但し、nを正の無限大であるとはしない。即ち、一変数実多項式e1(x),e2(x),…,en(x)の個数(n個)を有限とする。
上記条件の下、式(7)で表される一変数実多項式の集合Fに属する一変数実多項式のうち、領域Dに零点を持ち、かつ、一変数実多項式f(x)に最も近い一変数実多項式f~(x)について、一変数実多項式f(x)と一変数実多項式f~(x)との距離d(f,f~)を求めよ。また、このような一変数実多項式f~(x)を一つ求めよ。
【数40】

===================================
【0034】
なお、従前同様に、多項式の表記に際して変数xを明記したい場合にはf(x),g(x)の如く表すこととし、それ以外の場合には、単にf,gの如く表すこととする。また、特に断りの無い限り、「一変数実多項式」を「多項式」と略記する。
【0035】
また、多項式の係数は、理論上は実数としてよいが、コンピュータなどによる演算の上では四則演算および等号判定を有限ステップのアルゴリズムで実行できることが必要かつ十分であり、そのために例えば実代数的数(整数係数一変数代数方程式の根となる実数)とする。以降の説明では、説明の便宜から、多項式の係数は有理数であるとする。
【0036】
条件〈2〉本文から、多項式f(x)は領域Dに零点を持たない。
もし、多項式f(x)が領域Dに零点を持たないことを確認する必要がある場合には、次のような処理を行えばよい。
【0037】
〔多項式f(x)が領域Dに零点を持たないことの確認処理〕
領域D(境界Λ上およびその内部)に多項式f(x)の零点が存在するか否かの判定は、公知の手法によって達成される。
まず、領域Dの境界Λ上において多項式f(x)の零点が存在するか否かの判定を行う。例えば、領域Dの境界Λの表示を多項式f(x)に代入した後、Sturmの定理に基づくアルゴリズムに従って零点の有無を判定する。
【0038】
ここでは説明の便宜から一例として、各区分境界Λkが、パラメータsおよびパラメータsを一変数とする有理式φk(s)、ψk(s)によってφk(s)+i・ψk(s)と表示されるとする〔k=1,2,…,K〕。iは、虚数単位を表す。ここで、有理式φk(s)、ψk(s)における係数は、上記同様に、理論上は実数としてよいが、コンピュータなどによる演算の上では四則演算および等号判定を有限ステップのアルゴリズムで実行できることが必要かつ十分であり、そのために例えば実代数的数(整数係数一変数代数方程式の根となる実数)とし、具体例として有理数であるとする。以下では、有理式φk(s)、ψk(s)を、有理数係数の有理式であるとして例示説明する。パラメータsの動く範囲Skは、条件〈3〉に対応して[α,β]、[α,∞)、(−∞,β]、(−∞,∞)のいずれかであるとする。[・,・]は閉区間、(・,・]は左開右閉区間、[・,・)は左閉右開区間、(・,・)は開区間を表す。また、パラメータsと区分境界Λkとの間は単射である。
【0039】
Strumの定理に基づくアルゴリズムの適用について説明する。各区分境界Λkについて同様の処理となるから、敢えて沿え字kを省略して説明する。
【0040】
領域Dの区分境界Λの表示φ(s)+i・ψ(s)が代入された多項式f(φ(s)+i・ψ(s))は、有理数係数有理式ω(s)およびτ(s)によってf(φ(s)+i・ψ(s))=ω(s)+i・τ(s)と表示できる。ここで「多項式f(x)が、φ(s0)+i・ψ(s0)において0となる」ことと、「ω(s)およびτ(s)がs=s0で同時に0となる」ことは同値である。また、「ω(s)およびτ(s)がs=s0で同時に0となる」ことと、「ω(s)およびτ(s)をそれぞれ既約な有理数係数有理式として表したときの分子のGCD(最大公約多項式)がs0において0になる」ことは同値である。
【0041】
従って、ω(s)およびτ(s)をそれぞれ既約な有理数係数有理式として表したときの分子のGCDに対し、Strumの定理に基づくアルゴリズムを適用する。説明の便宜からω(s)およびτ(s)をそれぞれ既約な有理数係数有理式として表したときの分子のGCDをH(s)とする。
【0042】
このH(s)について、多項式の列H0(s),H1(s),H2(s),…,Hr(s)を生成する。但し、これらの多項式の列は、次の規則に従って生成する。H0(s)=H(s),H1(s)=dH(s)/ds〔sに関する1階微分である。ライプニッツ記法〕、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)の関係が成立する。このとき、区間S=[a,b]において、H0(a),H1(a),H2(a),…,Hr(a)における正負の符号変化の回数をw(a)で表し、H0(b),H1(b),H2(b),…,Hr(b)における正負の符号変化の回数をw(b)で表すとすると、区間S=[a,b]におけるH(s)の零点の個数は、w(a)-w(b)である。なお、ここでは、区間S=[a,b]のa、bは共にH(s)の零点ではないとした(零点であれば、個数を表す式が少し変わるが、本発明においては本質的な部分ではないので略する。)。
【0043】
w(a)-w(b)=0であればH(s)の零点が存在しないことが判明し、区分境界上で多項式f(x)の零点は存在しない。w(a)-w(b)≠0であればH(s)の零点が存在することが判明し、区分境界上で多項式f(x)の零点は存在する。全ての区分境界上でH(s)の零点の不存在を確認することで、領域Dの境界Λ上において多項式f(x)の零点が存在しないことが確認される。
【0044】
なお、この判定ではSturmの定理によって、厳密には、区間(a,b]に多項式f(x)の零点が存在するか否かを判定している。そこで、s=aがH(s)の零点であるか否かについては、f(s)=0の成立を判定すればよい。区間Sの端点が∞又は-∞で与えられる場合であっても、係数が確定している多項式f(x)は上記端点に近づいては零点を持たないから符号変化の回数が変わらず、上記アルゴリズムに従って判定することができる。
【0045】
なお、Sturmの定理については、参考文献1を参照のこと。
(参考文献1) 高木貞治著、「代数学講義(改訂新版)」、共立出版、1965.
【0046】
以上では、領域Dの境界Λ上において多項式f(x)の零点が存在するか否かの判定を、領域Dの境界Λの表示を多項式f(x)に代入した後、Sturmの定理に基づくアルゴリズムによって行うものとして説明した。しかし、Sturmの定理に基づくアルゴリズムに限定する趣旨ではない。要は、一変数実係数の代数方程式が或る実の区間に根を持つか否かの判定ができればよく、例えば参考文献2に示されるsign variation methodによってこれを判定するとしてもよい。
(参考文献2) 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.
【0047】
もし、境界Λ上に多項式f(x)の零点が存在しなければ、領域Dの内部において多項式f(x)の零点が存在するか否かの判定を行う。この判定には偏角の原理を用いることで達成される。なお、偏角の原理に基づく判定においては、領域Dの境界Λ上に多項式f(x)の零点がないことが前提となるから、まず、境界Λ上での零点の有無を判定しておいたのである。
【0048】
偏角の原理に基づくアルゴリズムの適用について説明する。
区分境界Λ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))それぞれの実根をs∈Sにおいて求める。同様にして全ての区分境界について根を求め、これらの根を現れる順に並べたリストS1を作る。また、境界Λに囲まれた領域における根の計数用のリストS2を用意する(初期状態では、リストS2は空である。)。リストS1の先頭から順次に根を読み出すこととし、まず、先頭要素(根)Aを取り出し、リストS2が空のリストであればそれをS2に書き込む。リストS2が空でないときは先頭要素(根)AとリストS2の先頭の要素(根)が共に実部の解であるか共に虚部の解であるかを判定し、この判定が真であればリストS2から先頭の要素(根)を取り除く。当該判定が偽であるときは先頭要素(根)AをリストS2の先頭に書き足す。この処理操作をリストS1の先頭から順次に根を読み出すことで行う。この結果、リストS2における要素(根)の個数の1/4が境界Λの内部に含まれる多項式f(x)の根の数になる。この数が0であれば、多項式f(x)の零点が領域Dの内部に存在しないことが判明し、この数が0でなければ、多項式f(x)の零点が領域Dの内部に存在することが判明する。
【0049】
なお、偏角の原理を用いた多項式の零点の数え上げについては、参考文献3を参照のこと。
(参考文献3) 平野照比古著、「偏角の原理を用いた多項式の根の数え上げ」、数式処理、Vol.9, No.4, pp.34-35, 2003.
【0050】
以上では、領域Dの内部において多項式f(x)の零点が存在するか否かの判定を偏角の原理に基づくアルゴリズムによって行うものとして説明した。しかし、要は、多項式f(x)が領域Dの内部に根を持つか否かの判定ができればよく、偏角の原理に基づくアルゴリズムに限定する趣旨ではない。
以上で〔多項式f(x)が領域Dに零点を持たないことの確認処理〕の説明は終わりである。
【0051】
さて、条件〈6〉から、上記≪問題≫を《n=1の場合》と《n≧2の場合》に分けて解答する。
【0052】
《n=1の場合》
この場合、多項式f(x)+t1e1(x) (t1∈R)がx=c∈Dにおいて零点を持つ必要十分条件は、連立方程式(8)が点cを解とすることである。
【数41】

【0053】
よって、行列式Re f(c) Im e1(c)−Im f(c) Re e1(c)は0である。これは、s0とs1を変数と見た連立方程式(9)が(s0,s1)=(1,t1)という(0,0)ではない解を持つことから云える。
【数42】

【0054】
上記[性質1]または下記[命題]から、境界Λ上に距離最小の多項式の零点が存在する。よって、各μ(μ=1,2,…,K)に対して、区分境界の表示γμ(s)をxに代入し、Re f(γμ(s)) Im e1μ(s))−Im f(γμ(s)) Re e1μ(s))が恒等的に0ではない場合には、Re f(γμ(s)) Im e1μ(s))−Im f(γμ(s)) Re e1μ(s))=0を解いて(根は有限個である。)、これらの有限個の根のうちσi(i=1,2,…)∈Iμについて連立方程式(8)を満たす実数解t1を求めればよい。実数解は、t1(i)=-f(γμi))/e1μi))である。
【0055】
このとき、実数解t1が存在しない場合がある。例えば、f(x)=1,e1(x)=xで領域DがRと共通部分を持たない場合である。このような場合、求めるべき多項式f~は存在しない。
【0056】
実数解t1が存在する場合、この段階で候補が有限個であるから、領域Dに零点を持たない多項式fに最も近い多項式f~を求めることができる。求めるべき最小距離は|t1(i)| (i=1,2,…)のうち最小のものである。この最小距離をmini{|t1(i)|}と表記すると、求めるべき多項式f~の一例は、f(x)±mini{|t1(i)|}e1(x)のうちいずれかである。
【0057】
次に、Re f(x) Im e1(x)−Im f(x) Re e1(x)が恒等的に0である場合について考える。
ここで、Re e1(x)が恒等的に0とすると、e1(x)は定数となる(※1)。e1(x)は実多項式であるから、定数ならば実数であり、その実部が0ということはe1(x)がゼロ多項式であることを意味し、e1(x)が条件〈1〉の一次独立であることに矛盾する(ただ一つの元が一次独立であることは、それが0ではないことと同値である。)。故に、Re e1(x)は恒等的に0ではない。
【0058】
Im e1(x)が恒等的に0である場合、e1(x)は定数となる(※1)。さらに、「Re f(x) Im e1(x)−Im f(x) Re e1(x)が恒等的に0である」から、Im f(x) Re e1(x)は恒等的に0となる。よって、Im f(x)は恒等的に0となる(※2)。よってf(x)は定数となる(※1)。このとき、実多項式f(x),e1(x)がともに定数なので、それぞれ実数となり、a∈Rによってf/e1=aと書ける(上述のとおり多項式e1(x)は0ではない。)。つまり、f=a e1である。
【0059】
Im e1(x)が恒等的に0ではない場合、「Re f(x) Im e1(x)−Im f(x) Re e1(x)が恒等的に0である」から、Re f(x)/Re e1(x)=Im f(x)/Im e1(x)となる。これをp(x)とおくと、p(x)は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)はxの値に拠らず実であるから、Im (f(x)/e1(x))は恒等的に0となる。よって、f(x)/e1(x)は定数となる(※1)。f(x)/e1(x)は実係数有理式であるから定数ならば実数である。故に、a∈Rによってf(x)/e1(x)=aと書ける。つまり、f(x)=a e1(x)である。
【0060】
(※1)
h(x) (x∈C)が正則関数のとき(多項式や有理式は正則関数である。)、h(x)の一次微分h'(x)は微分する方向に拠らない。もし、Re h(x)が常に0であるなら、つまりh(x)が常に純虚数なら、h'(x)=limc→0{h(x+c)-h(x)}/cにおいて、cを実数の範囲で0に近づけることによってh'(x)はxによらず純虚数となる。他方、h'(x)=limc→0{h(x+ic)-h(x)}/(ic)でもあるから、cを実数の範囲で0に近づけることによってh'(x)はxによらず実数となる。よって、h'(x)は常に純虚数かつ実数、つまり0である。故に、h(x)は定数となる。Im h(x)が常に0である、つまりh(x)が常に実数としても同様である。
以上で(※1)の説明を終わる。
【0061】
(※2)
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)は恒等的に0」は、「r1(u,v)・q2(u,v)が恒等的に0」を意味する。上述のとおりq2(u,v)はゼロ多項式ではないからr1(u,v)がゼロ多項式、つまりIm f(x)は恒等的に0となる。
以上で(※2)の説明を終わる。
【0062】
以上のことから、Re f(x) Im e1(x)−Im f(x) Re e1(x)が恒等的に0である場合、或るa∈Rによってf(x)=a e1(x)と書ける。よって、連立方程式(8)は、連立方程式(10)と書ける。
【数43】

【0063】
この連立方程式(10)の実数解t1として、t1=-aの場合が考えられる。このとき、最小距離は|t1|であり、多項式f(x)+t1e1(x)は恒等的に0になる。つまり、求めるべき多項式f~は、0〔ゼロ多項式〕である。
【0064】
また、連立方程式(10)の実数解t1として、t1≠-a且つRe e1(x)=Im e1(x)=0の場合が考えられる。これは多項式e1(x)が領域Dに零点を持つことを意味し、このとき、多項式f(x)=a e1(x)が実重複零点を持つことになり、条件に反する。よって、このような場合、求めるべき多項式f~は存在しない。
以上で、《n=1の場合》の説明は終わりである。
【0065】
《n≧2の場合》
まず、下記の命題を証明する。これは上記[性質1]に相当し、多項式fに最も近い、即ち距離最小の多項式f~が存在するならば、多項式f~の零点は領域Dの境界Λ上にのみ存在することを保証する。
===================================
[命題]距離最小の多項式f~が恒等的に0ではない場合、その領域D上の零点は、領域Dの境界Λ上にのみ存在する。
===================================
【0066】
(証明)
中心をz∈C、半径をrとする開円板をB(z;r)={w|w∈C,|z-w|<r}と書き、X⊂Cの内点の集合、すなわち、{z∈X|あるr>0が存在してB(z;r)⊂X}をX°と表記する。
【0067】
まず、次のことを示す。
『多項式f(x)が領域Dに零点を持たず、恒等的に0ではない多項式g(x)=f(x)+Σj=1nbjej(x) (bj∈R)が領域Dの内部D°に零点を持つとする。このとき、D°に零点を持ち、d(f,g~)<d(f,g)を満たす恒等的に0ではない多項式g~(x)=f(x)+Σj=1nb~jej(x) (b~j∈R)が存在する。』・・・(★)
【0068】
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)は式(7)で表される集合Fに属する。つまり、p(t,x)∈Fである。
【0069】
ζをD°に在る多項式gの零点とする。すると、条件「B(ζ;ε)⊂Dかつ、任意のξ∈B(ζ;ε),ξ≠ζに対して、g(ξ)≠0」を満たすε>0が存在する。仮にこのようなεが存在しないとすると、多項式gが恒等的に0ではないことに矛盾する。
【0070】
今、任意のt(0≦t≦1)に対して、p(t,x)がB(ζ;ε/2)の境界に零点を持たないと仮定する。すると、Roucheの定理により、B(ζ;ε/2)内に在るp(0,x) (=f(x))の零点の個数(0個)とp(1,x) (=g(x))の零点の個数(1個以上)が等しくなり矛盾する。従って、或る0<τ<1が存在してp(τ,x)はB(ζ;ε/2)の境界に零点を持つので、g~(x)としてp(τ,x)を採ればd(f,g~)=τd(f,g)<d(f,g)が成り立つ。
よって、題意★が示せた。
【0071】
このとき、距離最小の多項式f~の零点がD°に存在するとすると、D°に零点を持ち、d(f,g~)<d(f,f~)を満たす多項式g~(x)=f(x)+Σj=1nb~jej(x) (b~j∈R)が存在することになり、多項式f~が距離最小のときの多項式であることに矛盾する。よって、距離最小の多項式f~の領域D上の零点は、領域Dの境界Λ上にのみ存在する。
以上により[命題]の証明は終了である。
(証明終)
【0072】
次に、定理1を証明する。これは、式(7)に表される集合Fに属する多項式で領域Dに零点を持つものがあれば、その中で多項式fに最も近い多項式f~が存在することを保証する。
===================================
[定理1]記号F,f,d,Dは上記の通りとする。もし、領域Dに零点を持つ多項式g∈Fが存在するならば、領域Dに零点を持ち、かつ‖f-f~‖が最小となるようなf~∈Fが存在する。
===================================
【0073】
(証明)
[領域Dが有界の場合]
G(z,t1,…,tn)を式(11)で定義されるC×RからCへの関数とする。
【数44】

【0074】
すると、G-1(0)は、閉集合(一点0)の連続関数による逆像だから閉集合である。
【0075】
以下、(t1,…,tn)∈Rとf(x)+Σj=1ntjej(x)∈Fを同一視する。また、集合Aを次式(12)のとおり定義する。ここで記号×は直積集合を表す。
【数45】

【0076】
すると、集合Aは、閉集合G-1(0)と有界な閉集合D×{h∈F|d(f,h)≦d(f,g)}との積集合だから、有界かつ閉であり、コンパクトとなる。
【0077】
よって、集合Aから実数集合Rへの連続関数(13)は最小値を持つ。
【数46】

【0078】
この最小値を(ζ,τ,…,τ)∈Aでとると仮定する。f~をf~= f(x)+Σj=1nτjej(x)で定義すると、f~∈F、f~はζ∈Dを零点とし、d(f,f~)は最小となる。
【0079】
[領域Dが非有界の場合]
集合Fに属する多項式の次数が等しいという条件〈5〉から、集合Fに属する多項式の最高次の係数は等しい。多項式f~を探すには、‖f-h‖≦‖f-g‖を満たす多項式hのみを調べれば十分である。これら全ての多項式hの全ての零点を含むような、中心が0、半径がrの閉円板を取ることができる。よって、有界な閉集合D∩{z∈C||z|≦r}を考えることで上記[領域Dが有界の場合]に帰着される。
以上により[定理1]の証明は終了である。
(証明終)
【0080】
さて、次の定理2は、上記の定理1の「領域Dに零点を持つ多項式g∈Fが存在する」という条件が、或る場合は自動的に満たされることを示すものである。
===================================
[定理2]記号f,e(j=1,…,n),D,Fは上記の通りとする。n≧2のとき、集合Fに属する多項式で領域Dに零点を持つものが存在する。
===================================
【0081】
(証明)
n=2の場合に証明すれば十分である。
条件〈1〉から多項式eと多項式eの両方が定数であることはない。そこで必要であれば添字を付け換えて、多項式eが定数でないとする。e1(z)=0となるzは有限個である。よって、a∈D°でe1(a)≠0となるものが存在する。ここで多項式eは連続であるから、点aを含む十分に小さい開集合U⊂Dであって、0∈/e(U)となるものが存在する(つまり、∃U⊂D,∀p∈U°,e1(p)≠0)。ここで記号「∈/」は、「集合に属さない」を意味する。
【0082】
e2/e1による開集合Uの像は複素平面上の空ではない開集合であり(正則関数の性質)、複素平面上でRの部分集合となる開集合は空集合のみであるから、e2(α)/e1(α)∈/Rとなるα∈Uが存在する。
【0083】
よって、e1(α)とe2(α)はR上一次独立となる。従って、-f(α)=c1e1(α)+c2e2(α)となるc,c∈Rが存在する。即ち、f(α)+c1e1(α)+c2e2(α)=0である。
以上により[定理2]の証明は終了である。
(証明終)
【0084】
続いて、下記の補題1は、最小距離を算出する上で重要な役割を果たすものである。
===================================
[補題1]記号f,eは上記の通りとする。また、一変数実多項式の集合Fεを式(14)で与える。但し、0≦εとする。
【数47】

このとき、点α∈Cを零点とする多項式g∈Fεが存在する必要十分条件は以下の通りである。
[1]0,e1(α),…,en(α)が一直線上にあるとき、必要十分条件は、f(α)がその直線上にあり、かつ、不等式(15)が成立することである。
【数48】

[2]0,e1(α),…,en(α)が一直線上にはないとき、必要十分条件は、i=1,…,nに対して不等式(16)が成立することである。
【数49】

===================================
【0085】
(証明)
集合Fεに属する多項式gが存在して点α∈Cが多項式gの零点となる必要十分条件は、0が式(17)で与えられる集合に属することである。
【数50】

【0086】
ここで、式(18)を定義する。
【数51】

【0087】
このとき、式(17)で与えられる集合は、式(19)による表現に書き改められる。
【数52】

【0088】
〔式(19)の解説〕
式(14)から、係数biは閉区間[−ε,ε]で表される区間数であり、閉区間[−ε,ε]は、パラメータt(0≦t≦1)を用いて{2εt−ε}と表記することができる。パラメータtは、閉区間の両端点−ε、εの内分比を表す。このとき、集合Fεは、上記区間数{2εt−ε}を各項の係数として式(20)のように表現される。
【数53】

【0089】
このとき、「点αを零点とする多項式が集合Fεに存在するか否か」は、「連立方程式(21)を満足するt(i=1,2,…,n)の組み合わせが存在するか否か」と同値である。また、連立方程式(21)を書き改めると、連立方程式(22)と表せる。
【数54】

【0090】
つまり、連立方程式(22)を満足するtの組み合わせが存在するならば、それは、この点αを零点とする多項式が集合Fεに存在することを意味する。ここで留意しなければならないのは、tの組み合わせを特定することではなく、「連立方程式(22)を満足するtの組み合わせが存在するか否か」である。ここで説明の便宜から、(Reei(α) Imei(α))をBと表記する。そうすると、Bは、複素平面において、原点を始点、(Reei(α),Imei(α))を終点とする位置ベクトルとみることができる。
【0091】
そうすると、式(22)左辺について2εtを、「Bを2ε倍した位置ベクトル2εBを、tによってスカラー倍したものである」と見れば、0≦t≦1によって式(22)の左辺が取り得る平面上の範囲に、式(22)の右辺の点が存在するか否かを調べればよい。つまり、凸多角形に或る1点が存在するか否かの判定に持ち込むことを考えればよい。そこで、このような凸多角形を用いた判定を効率良く行うために、前処理を行う。
【0092】
まず、式(22)の左辺の各項(i=1,…,n)を順番に見ていき、各項について次のような判定と書き換えを行う。まず、2εBの実部〔つまり、2εRee(α)である。〕が負であるかを判定する。負である場合には、2εtを2ε(1−t)Bに書き換える。次に、2εBの実部が負でない場合は、2εBの実部が0かつ虚部〔つまり、2εIme(α)である。〕が負であるか否かを判定する。実部が0かつ虚部が負である場合には、2εtを2ε(1−t)Bに書き換える。
なお、この操作は式(21)において、2εBの実部が負である場合に{2εt−ε}Bを{2ε(1−t)−ε}B、即ち{2εt−ε}(−B)と書き換え、2εBの実部が0かつ虚部が負である場合に{2εt−ε}Bを{2ε(1−t)−ε}B、即ち{2εt−ε}(−B)と書き換えることと同じである。式(21)でこの書換え処理を施したものの左辺を、実部と虚部に分けずに表現したものが式(19)である。
【0093】
以上の操作は、例えば、実部が負である位置ベクトル2εBをtスカラー倍(0≦t≦1)することは、平面原点対象に移動した位置ベクトル2ε×(−1)×Bをkスカラー倍(−1≦k≦0)することと同じであるから、tの範囲が0≦t≦1であることに留意してk=t−1とおくと、2ε×(−1)×k×Bは、2ε×(1−t)×Bとなることに基づく。このような操作を行うことで、式(22)の左辺の点2εBは、見かけ上、全て平面の右半平面(実部が0以上の領域全体、但し、実部が0かつ虚部が負の部分は除く。)に集められるとともに、平面の虚軸の負の部分には点が乗らないものとなる。換言すれば、この操作の結果得られた点集合は、平面原点を頂点とする凸多角形を平面の右半平面で構成する(但し、平面の虚軸の負の部分に凸多角形の頂点はない。)。
【0094】
なお、このような操作は、凸多角形を求めるための便宜としての前処理であるから、上記処理に限定されるものではない。例えば、2εBの実部が正であるかを判定し、正である場合には、2εtを2ε(1−t)Bに書き換え、2εBの実部が正でない場合は、2εBの実部が0かつ虚部が負であるか否かを判定する。そして、実部が0かつ虚部が負である場合には、2εtを2ε(1−t)Bに書き換える(つまり、平面原点を頂点とする凸多角形を平面左側で構成する。)、といった操作などに適宜に変更できる。
以上で〔式(19)の解説〕の説明は終わりである。
【0095】
さて、式(19)の第3項で表現される集合、即ち式(23)で表現される集合は、平面上で高々2個の点の凸包となる凸多角形となる〔参考文献4参照〕。
(参考文献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.
【数55】

【0096】
そこで、この凸多角形の頂点を求める。これは、効率的に求めることができる。
具体的にはまず、平面の虚軸の負の部分を除く平面の右半平面の領域〔−π/2<arg≦π/2、argは偏角を表す。〕において、e^(α)≠0を偏角〔arg(e^i(α))=arctan(Ime^i(α)/Ree^i(α))、但し、Ree^i(α)=0ならばarctan(Ime^i(α)/Ree^i(α))はπ/2とみなす。〕でソート(sort)する。つまり、位置ベクトルe^(α)≠0が実軸となす角度arg(e^i(α))を、−π/2<arg≦π/2で、小さい方から大きい方へと昇順に並び替える。但し、同じ傾きのものがあるときには、それらを全部足したものに置き換えたものを1つとしてソートする。例えば、e^(α)およびe^(α)の傾きが同じときには、e^(α),e^(α)の代わりに、e^(α)+e^(α)を対象としてソートする。なぜなら、傾きが同じ位置ベクトルe^(α)および位置ベクトルe^(α)の各終点は平面上において凸包の頂点となりえないからである(凸包の頂点の可能性があるのは、同じ傾きのものを全てベクトル加算した点である。)。このソートの結果を位置ベクトルp,・・・,pとする。なお、mはnより小さいことがあることに留意すること。
【0097】
このとき、求める平面上の凸包の頂点は、平面原点(0と表記する。)から始めて反時計回りに、0,p,p+p,…,p+…+p,p+p+…p,p+…+p,…,pm−1+p,pの全部で2m個となる。
つまり、凸多角形の平面における頂点は、反時計回りに式(24)で与えられる位置ベクトルv(0≦i≦2m−1)の終点として表される〔上記参考文献4参照。〕。
【数56】

【0098】
従って、式(25)で表現される凸多角形は、反時計回りに頂点εw,εw,・・・,εw2m−1を持つ。但し、w(0≦i≦2m−1)は式(26)で与えられる〔∵Σi=1ne^i(α)=Σj=1mpj〕。
【数57】

【0099】
式(25)で表現される凸多角形では、全てのe^(α)≠0について、e^(α)と平行な辺が丁度二つ存在し、全ての辺について、辺に平行なe^(α)を少なくとも一つ存在する。そこで、e^(α)≠0について、e^(α)と平行な両端点をεw,εwj+1とする辺を考える。但し、jは最小のものを選択する。頂点を識別するjはe^(α)を識別するiに依存するから、j=ν(i)と書く。さらに、u=(Re u Im u)およびv=(Re v Im v)に対する行列式(27)をA(u,v)と表記することにする。
【数58】

【0100】
さて、e^(α)と平行な二つの辺を含む直線は、式(28)で表される。但し、z=(Re z Im z)である。
【数59】

【0101】
式(28)は、式(29)に等価である。
【数60】

【0102】
原点は式(25)で表現される凸多角形に属するから、この凸多角形は、全てのi=1,2,・・・,nに対して不等式(30)を満たす位置ベクトルzの終点集合と云うことができる。但し、凸多角形が線分に退化している場合、即ちi=1,2,・・・,nに対して不等式(30)の右辺が0となる場合には、この凸多角形は、不等式(30)に加えて不等式(31)を満たす位置ベクトルzの終点集合と云うことができる。
【数61】

【0103】
さて、原点が式(19)で与えられる集合に属することの必要十分条件は、(-Ref(α) -Imf(α))が式(25)で与えられる凸多角形に属することである。|A(e^i(α),-f(α))|=|A(e^i(α),f(α))|および|-f(α))|=|f(α))|が成立することに注意すれば、点α∈Cを零点とする多項式g∈Fεが存在することの必要十分条件は、式(32)、式(33)で表される。
【数62】

【0104】
ここで、式(34)が成立する。
【数63】

【0105】
よって、式(35)が成立する。ここでj∈/L(i)∪R(i)に対してA(e^i(α),e^j(α))=0が成り立つことに留意すること。
【数64】

【0106】
よって、不等式(36)が成り立つ。
【数65】

【0107】
ここで式(37)、式(38)が云える。
【数66】

【0108】
よって、点α∈Cを零点とする多項式g∈Fεが存在する必要十分条件は以下の通りである。
[1]0,e1(α),…,en(α)が一直線上にあるとき(凸多角形が線分に退化している場合)、必要十分条件は、f(α)がその直線上にあり、かつ、不等式(39)が成立することである。
【数67】

[2]0,e1(α),…,en(α)が一直線上にはないとき、必要十分条件は、i=1,…,nに対して不等式(40)が成立することである。
【数68】

以上により[補題1]の証明は終了である。
(証明終)
【0109】
この補題1から下記の定理3が得られる。なお、補題1の記号iをjに、jをkに置き換えてある。
===================================
[定理3]記号f,e,F,A(・,・),αは上記の通りとする。また、f(α)≠0とする。
[1]1≦j<k≦nなるj,kに対してA(ej(α),ek(α))=0が成立するとき、点αを零点とする距離最小の多項式f~が存在する必要十分条件は、A(ej(α),f(α))=0がj=1,…,nに対して成立ち、さらに、e(α)≠0となるjが存在することである。このとき最小距離は式(41)で与えられる。式(41)で記号iは虚数単位を表す。
【数69】

[2]或るj,k(1≦j<k≦n)に対してA(ej(α),ek(α))≠0が成立するとき、点αを零点とする距離最小の多項式f~は存在する。このとき最小距離は式(42)で与えられる。但し、分母が0となるものは除く。
【数70】

===================================
【0110】
(証明)
まず、定理3の[2]は、補題1の[2]から従う。補題1の[2]に拠ると、0,e1(α),…,en(α)が一直線上にはないとき、つまり或るj,k(1≦j<k≦n)に対してA(ej(α),ek(α))≠0が成立するとき、点α∈Cを零点とする多項式g∈Fεが存在する必要十分条件は、j=1,…,nの全てに対して不等式(43)が成立することである。
【数71】

【0111】
これを点α∈C(但し、≪問題≫に対しては上記[命題]からα∈Λでよい。)を零点とする距離最小の多項式f~について適用する。或るj,k(1≦j<k≦n)に対してA(ej(α),ek(α))≠0が成立するとき、j=1,…,nのそれぞれに対して不等式(43)の等号が成立するときのεのうち最大のもの(εmax)が存在するので、距離最小の多項式f~は必ず存在する。最小距離はεmaxであり、式(44)で与えられる(但し、分母が0となるものは除く。)。
【数72】

【0112】
次に、定理3の[1]は、補題1の[1]から従う。補題1の[1]に拠ると、0,e1(α),…,en(α)が一直線上にあるとき、点α∈Cを零点とする多項式g∈Fεが存在する必要十分条件は、f(α)がその直線上にあり、かつ、不等式(45)が成立することである。
【数73】

【0113】
これを点α∈C(但し、≪問題≫に対しては上記[命題]からα∈Λでよい。)を零点とする距離最小の多項式f~について適用する。f(α)が0,e1(α),…,en(α)が乗る一直線上に乗るために、j=1,…,nに対してA(ej(α),f(α))=0が成立しなければならない。また、j=1,…,nに対してe(α)=0が成立すると、f(α)=0となる。しかし≪問題≫では多項式fは領域Dに零点を持たないので、f(α)≠0である。従って、e(α)≠0となるjが存在することも条件となる。
【0114】
0,e1(α),…,en(α)が一直線上にあり、多項式f~が存在する必要十分条件が満たされているとき、j=1,…,nに対して、ej(α)=ajf(α) (aj∈R)と書ける。このとき、不等式(45)は不等式(46)に書き換えることができる。
【数74】

【0115】
f(α)≠0が成り立つから、最小距離は不等式(46)を満たす最小のεであり1/Σj=1n|aj|である。
一方、A(ej(α),if(α))=A(ajf(α),if(α))=ajA(f(α),if(α))が成り立つ。ここでA(f(α),if(α))=|f(α)|2>0に注意すると、式(47)が成立する。なお、この式によれば根号の処理を避けることができる。
【数75】

以上により[定理3]の証明は終了である。
(証明終)
【0116】
定理3から最小距離が求まるので、求めるべき多項式f~を示す。ここでは[補題1]の記法を踏襲する。
【0117】
まず、凸多角形が線分に退化していない場合について説明する。
式(25)で表現される凸多角形は、反時計回りに頂点εw,εw,・・・,εw2m−1を持つ。最小距離をd(f,g~)と表示すると、0≦ε<d(f,g~)ならば、多項式gの零点α∈Dが与える点(-Ref(α),-Imf(α))は式(25)で表現される凸多角形に属さない。一方、ε=d(f,g~)のとき、点(-Ref(α),-Imf(α))は式(25)で表現される凸多角形に属する。換言すれば、複素平面上にd(f,g~)w,d(f,g~)w,・・・,d(f,g~)w2m−1を頂点に持つ凸多角形Zの或る辺の上に点(-Ref(α),-Imf(α))が乗っている。
【0118】
そこでεを最小距離d(f,g~)に固定し、点(-Ref(α),-Imf(α))が乗っている凸多角形の辺の端点をεw,εwi+1とする。但し、w,wi+1は式(47a)のとおりである。なお、i=2m−1のときは、i+1を0に読み替えるものとする。
【数76】

【0119】
点(-Ref(α),-Imf(α))は端点εwと端点εwi+1とを結ぶ辺上に存在するから、或るt(0≦t≦1)が存在して、式(47b)の如く表すことができる。式(47b)は、式(47a)において0≦i≦m−1の場合の計算であるが、m≦i≦2m−1の場合は、wi=-wi-mに注意すれば、式(47b)の最後の式を−1倍したものが成立する。
【数77】

【0120】
今、ν(k)=i+1となるkをとると、式(47b)は、式(34)から式(47c)に変形できる。式(47c)は、式(47a)において0≦i≦m−1の場合の計算であるが、m≦i≦2m−1の場合は、上述のとおり、式(47c)の最後の式を−1倍したものが成立する。
【数78】

【0121】
よって、集合P(i)を式(47d)で与えると、式(47e)で表される多項式gは点αを零点として持ち、しかもe^j(x)が位置ベクトルpiと平行でないような識別子jについては、ej(x)の係数がε或いは−εであることが分かる。どちらの符号を取るかは式(18)で分かる。式(47e)は、式(47a)において0≦i≦m−1の場合の計算であるが、m≦i≦2m−1の場合は、上述のとおり、式(47e)の最後の項を−1倍したものが成立する。
【数79】

【0122】
以下、j∈P(k)なる識別子jについて考察する。
このとき、式(47e)の右辺第四項について不等式(47f)が成立する。式(47f)は、式(47a)において0≦i≦m−1の場合の計算であるが、m≦i≦2m−1の場合は、上述のとおり、式(47f)の各辺を−1倍したものが成立する。
【数80】

【0123】
今、例えば集合P(k)に属するjを若い方から順番にj1、j2、j3、・・・、jMと表記するとして、不等式(47f)の第一辺を集合P(k)に属するjを若い方から順にεの符号をプラスに書き換えていくと、あるm(1≦m≦M)があって式(47f)の第二辺について不等式(47g)が成立する。なお、不等式(47g)はεの符号に意識した表記としてある。式(47g)は、式(47a)において0≦i≦m−1の場合の計算であるが、m≦i≦2m−1の場合は、上述のとおり、式(47g)の各辺を−1倍したものが成立する。
【数81】

【0124】
よって、jm以外の識別子jiについては、a~ji=+ε (1≦i≦m-1), a~ji=-ε (m+1≦i≦M)と置くことととし、識別子jmについては、式(47h)で表されるsを用いて、a~jm=sεと置くこととする。このとき、−1≦s≦1が成り立つことに注意する。式(47h)は、式(47a)において0≦i≦m−1の場合の計算であるが、m≦i≦2m−1の場合は、上述のとおり、式(47h)の右辺を−1倍したものが成立する。
【数82】

【0125】
すると、式(47e)および式(47g)から、式(47i)で表される多項式g^は、点αを零点として持ち、しかも識別子jmの多項式ejm(x)とは異なる多項式の係数がε或いは−εであることが分かる。ji∈P(k),i≠mの場合の符号も上記の操作および式(18)で分かる。さらに−1≦s≦1に留意すれば、多項式g^は≪問題≫の解答となる多項式f~であることが分かる。式(47i)は、式(47a)において0≦i≦m−1の場合の計算であるが、m≦i≦2m−1の場合は、上述のとおり、式(47i)の右辺第4項〜第6項を−1倍したものが成立する。
【数83】

【0126】
要するに、凸多角形が線分に退化していない場合の求めるべき多項式f~は、式(7)で表される一変数実多項式の集合のうち、多項式ejm(x)の係数の絶対値を最小距離d(f,g~)以下とし、多項式ejm(x)以外の多項式の係数の絶対値を最小距離d(f,g~)としたものとして表すことができる。
多項式ejm(x)の特定は、式(40)で等号が成立するi〔複数あるときには若い番号を採用する。〕を取り、二つあるeiと平行な辺のうちから式(47b)の一番上の等式を満たすt(0≦t≦1)が存在するものを選んだ上で、ji∈P(k)なる識別子jiについて式(47g)から多項式ejm(x)の特定することができる。
【0127】
次に、凸多角形が線分に退化している場合について説明する。
この場合は、凸多角形が線分に退化していない場合と同様の議論によって、εを最小距離d(f,g~)に固定すると式(39)の等号が成立するから、式(47j)が成立する。但し、式(47j)が成立するときの符号±は、[1]Ref(α)<0の場合、Reei(α)<0となる識別子iについては+εとし、Reei(α)>0となる識別子iについては−εとする、[2]Ref(α)>0の場合、Reei(α)<0となる識別子iについては−εとし、Reei(α)>0となる識別子iについては+εとする、のいずれかである。なお、Reei(α)=0の場合は−ε、+εのどちらをとってもよい。
【数84】

【0128】
よって、式(47k)で表される多項式g^が≪問題≫の解答となる多項式f~であることが分かる。但し、式(47k)中の符号±は、上述のとおり決めればよい。
【数85】

【0129】
要するに、凸多角形が線分に退化している場合の求めるべき多項式f~は、式(7)で表される一変数実多項式の集合のうち、多項式e1(x),e2(x),…,en(x)の係数の絶対値を最小距離d(f,g~)としたものとして表すことができる。
以上で《n≧2の場合》の説明は終わりである。
以上で、[理論]の説明は終わりである。
【0130】
上述の[理論]に基づくと、要するに、≪問題≫に対しては次のとおり解答を与える。即ち、領域Dの境界Λ上の点αに対して、式(7)で表される集合Fに属しこの点αを零点とする多項式のうち多項式f(x)に最も近い多項式g(x)と多項式f(x)との距離を与える関数Φ(α)を用いて、区分境界Λ12,…,ΛKごとに関数Φ(α)の最小値を求め(距離候補探索)、この距離候補探索で得られた値のうち最小のものを求める(最小距離算出)。
【0131】
関数Φ(α)は、[1]1≦j<k≦nなる全てのj,kに対してA(ej(α),ek(α))=0が成立し、かつ、A(ej(α),f(α))=0がj=1,…,nに対して成立ち、かつ、e(α)≠0となるjが存在する場合に式(47m)で与えられ、[2]或るj,k(1≦j<k≦n)に対してA(ej(α),ek(α))≠0が成立する場合に、式(47n)で与えられる。
【数86】

【0132】
多項式f~は、距離の最小値を与える点αの所在に応じて、式(47i)または式(47k)に従う。
【0133】
n=1の場合とn≧2の場合に分けて解答した理由は、n=1の場合には、n≧2の場合で説明した解法よりも簡便な解法がある為であり、n=1の場合に於いてn≧2の場合で説明した解法を用いて解くことを妨げるものではない。
【0134】
《記号の導入》
複素係数多項式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]に対し、式(48)を定義する。
【数87】

【0135】
すると、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))と書くことにする。
以上で、《記号の導入》の説明は終わりである。
【0136】
《アルゴリズム》
上述の[理論]に基づき、最小距離d(f,f~)を求めるアルゴリズムを説明する。
上記命題より、領域Dの境界Λ上の零点のみを考えれば十分である。
【0137】
条件〈3〉から、区分境界Λμ(μ∈{1,…,K})上の点γμ(s) (s∈Iμ)を零点として持つ、最大値ノルムではかって多項式fに最も近い多項式f~までの距離をΦ(s)とする。
【0138】
Φ(s)を計算するためにIμの部分集合をいくつか定義する。
まず、集合Δμ⊂Iμを以下で定義する。
【0139】
n≧2のとき、Δμを式(49)のとおり定義する。
【数88】

【0140】
次に集合Δ~μ⊂Δμを式(50)で定義する。
【数89】

【0141】
Φμ(s)はs∈Δμ\Δ~μに対しては定義されない。なぜなら、定理3の[1]よりs∈Δμ\Δ~μに対して多項式f~は存在しないからである。記号\は、差集合を表す。
【0142】
上記各集合を用いると、Φμ(s)は式(51)の通りに書ける。式(51)の第二式で、最大値は点ごとに取る。
【数90】

【0143】
[式(51)の第一式について]
s∈Δ~μに対してΦμ(s)を具体的に計算するために(つまり、Φμ(s)の第一式に現れる絶対値の記号を外した形式で計算するために)、Δ~μの部分集合Z~μを式(52)の通り定義する。
【数91】

【0144】
Z~μは有限集合であり、Δ~μ\Z~μは有限個の区間の和集合で書ける。但し、区間は点に退化している場合もある。このとき、A(ejμ(s)),if(γμ(s)))≠0がΔ~μ\Z~μの各区間で成り立つ。これは、s∈Δμのとき、A(ejμ(s)),if(γμ(s)))=0が成り立つのは、ejμ(s))=0であることと同値だからである。よって、Φμ(s)はΔ~μ\Z~μの各区間で有理関数となる。なお、各区間では式(51)の第一式に表れる絶対値の中身の符号は確定しており、それは、各区間から代表点を一つずつとって符号を調べればよい。
【0145】
[式(51)の第二式について]
μ\ΔμをJμと書く。s∈Jμに対してΦμ(s)を具体的に計算するために(つまり、Φμ(s)の第二式に現れる絶対値の記号を外した形式で計算するために)、Jμの部分集合Zμを導入する。ここで、式(53)で表される和集合をとるときに、A(ejμ(s)),ekμ(s))), A(ejμ(s)),f(γμ(s)))が恒等的に0となる集合は除く。
【数92】

【0146】
μは有限集合であり、Jμ\Zμは有限個の区間の和集合である。但し、区間は点に退化している場合もある。また、Jμ\Zμにおいてφμ,j(s)はsの有理関数となる。これは、A(ejμ(s),ekμ(s))), A(ejμ(s),f(γμ(s)))の符号がJμ\Zμの各区間で不変だからである。このように、各区間では式(51)の第一式に表れる絶対値の中身の符号は確定しており、それは、各区間から代表点を一つずつとって符号を調べればよい。
【0147】
μ\Zμを有限個の区間Jμ,h(h=1,2,…)の和集合で書き、下記のアルゴリズム1を{φμ,1,…,φμ,n}と各Jμ,hに適用する。すると、Φμ(s)をJμ\Zμ上の区分的な有理関数として得ることができる。
【0148】
[アルゴリズム1]
このアルゴリズムは、入力された実区間Iにおいて、入力された一つ以上の関数f,…,fのうち或る関数fξが残りの関数よりも大となる区間Iξ⊂Iと関数fξとの組合せを出力するものである。つまり、
===================================
入力:有理関数の集合S={f1,…,ft}と実区間I
但し、fj(j=1,…,t)の極(分母の零点)は実区間Iには存在しないとする。
出力:maxS
但し{(Ij,fθ(j))|1≦j≦p}の形式で、I=∪j=1pIj, Ij∩Ik=0(j≠k)かつ、IjにおいてmaxS=fθ(j)である。
===================================
とするアルゴリズムである。
【0149】
●ステップ1
t=1のとき、{(I,f1)}を出力して終了する。
t≧2のとき、集合Sを二つの部分集合S,Sに分ける。但し、S=S∪SかつS∩S=φ(空集合)とする。例えば式(54)に示す集合S,Sとする。
【数93】

【0150】
●ステップ2
maxSを{(I1,j,fθ1(j))|1≦j≦q}の形式で、maxSを{(I2,j,fθ2(j))|1≦j≦r}の形式で得る。maxSとmaxSは、(S,I),(S,I)を入力として、このアルゴリズム1を用いて得ることができる。つまり、アルゴリズム1は、自身をサブルーチンとして持つ再帰的アルゴリズムである。
【0151】
●ステップ3
max{maxS,maxS}を計算し、{(Ij,fθ(j))|1≦j≦p}を得る。そして、{(Ij,fθ(j))|1≦j≦p}を出力して終了する。
【0152】
以下、●ステップ3について説明する。
まず、I1,j∩I2,k≠φ(空集合)となる区間の対を取る。このような対は高々q+r−1個存在し、max{f1,…,ft}を得るためにはmax{maxS,maxS}を各対の共通部分で計算する。空ではない区間I1,j∩I2,kの下限をa、上限をbとする(aは−∞、bは∞となることがある。)。また、σ<…<σζを、区間(a,b)内にあるfθ1(j)(s)=fθ2(k)(s)の解とする。空ではない区間I1,j∩I2,kは、最多でも、σ,…,σζで分割される。
【0153】
すると、I1,j∩I2,kにおけるmax{maxS,maxS}を求めるためには、fθ1(j)w)およびfθ2(k)w)の値をw=1,…,ζ+1に対して求めて、その大小関係を判定すればよい。ここで、τw(w=1,…,ζ+1)は、a<τ<σ<τ<…<τζ<σ<τζ+1<bを満足する任意の値である。
以上で●ステップ3の説明を終わる。
【0154】
図6−1および図6−2に示す具体例をもってアルゴリズム1の挙動を示す。
この具体例では、図6−1(a)に示すように、入力を有理関数の集合S={f1,f2,f3,f4}と実区間Iとしている。
【0155】
このとき、集合Sを二つの部分集合S={f1,f2},S={f3,f4}に分け(●ステップ1-A)、maxSを{(I1,j,fθ1(j))|1≦j≦q}の形式で、maxSを{(I2,j,fθ2(j))|1≦j≦r}の形式で得る(●ステップ2-A)。但し、この段階で直截的にmaxSとmaxSを得られるわけではなく、再帰的にアルゴリズム1の呼び出しが行われる。
【0156】
部分集合S={f1,f2}について、(S,I)を入力として、アルゴリズム1を適用すると、{(I,f1)}、{(I,f2)}が出力される(●ステップ1-B)。この出力が●ステップ2-Aに返される。そこで、実区間Iでmax{f1,f2}を求める(●ステップ3-A)。部分集合Sに対する●ステップ3-Aの挙動を図6−1(b)に示す。
【0157】
この段階では単一の実区間Iのみなので、I1,j∩I2,k≠φ(空集合)となる区間の対は実区間Iである。よって、実区間Iの下限をa、上限をbとし、σを区間(a,b)内にあるf1=f2の解とする(θ1(j)=1,θ2(k)=2)。実区間Iは、σで分割され、I1,1とI1,2となる。
【0158】
すると、実区間Iにおけるmax{f,f}を求めるためには、f1w)およびf2w)の値をw=1,2に対して求めて、その大小関係を判定すればよい。ここで、a<τ<σ<τ<bである。よって、maxSを{(I1,1,f1),(I1,2,f2)}の形式で得る。
【0159】
同様に、部分集合S={f3,f4}について、(S,I)を入力として、アルゴリズム1を適用すると、{(I,f3)}、{(I,f4)}が出力される(●ステップ1-C)。この出力が●ステップ2-Aに返される。そこで、実区間Iでmax{f3,f4}を求める(●ステップ3-A)。部分集合Sに対する●ステップ3-Aの挙動を図6−1(c)に示す。
【0160】
この段階では単一の実区間Iのみなので、I1,j∩I2,k≠φ(空集合)となる区間の対は実区間Iである。よって、実区間Iの下限をa、上限をbとし、σを区間(a,b)内にあるf3=f4の解とする(θ1(j)=3,θ2(k)=4)。実区間Iは、σで分割され、I2,1,I2,2,I2,3となる。
【0161】
すると、実区間Iにおけるmax{f3,f4}を求めるためには、f3w)およびf4w)の値をw=1,2,3に対して求めて、その大小関係を判定すればよい。ここで、a<τ<σ<τ<σ<τ<bである。よって、maxSを{(I2,1,f4),(I2,2,f3),(I2,3,f4)}の形式で得る。
【0162】
続いて、max{maxS,maxS}を計算する。集合Sに対する●ステップ3-Aの挙動を図6−2(d)〜(f)に示す。
maxSは{(I1,1,f1),(I1,2,f2)}であり、maxSは{(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である(図6−2(d))。
【0163】
区間I1,1∩I2,1の下限をa、上限をbとする。この区間でmax{f1,f4}を求めるが、区間(a,b)内にあるf1=f4の解は存在しない。よって、I1,1∩I2,1の分割は生じない。
【0164】
区間I1,1∩I2,1におけるmax{f1,f4}を求めるためには、f1w)およびf4w)の値をw=1に対して求めて、その大小関係を判定すればよい。ここで、a<τ<bである。よって、区間I1,1∩I2,1のmax{f1,f4}は(I1,1∩I2,1,f1)である。
【0165】
同様にして、区間I1,1∩I2,2のmax{f1,f3}は(I1,1∩I2,2,f1)であり、区間I1,2∩I2,2のmax{f2,f3}は(I1,2∩I2,2,f2)である。
【0166】
次に、区間I1,2∩I2,3の下限をa、上限をbとする。この区間でmax{f2,f4}を求める。区間I1,2∩I2,3でf2=f4の解は一つ存在し、この解σで区間I1,2∩I2,3は、ILとIRに分割される(図6−2(e))。
【0167】
そこで、区間I1,2∩I2,3におけるmax{f2,f4}を求めるためには、f1w)およびf2w)の値をw=1,2に対して求めて、その大小関係を判定すればよい。ここで、a<τ<σ<τ<bである。よって、区間I1,2∩I2,3のmax{f2,f4}は(IL,f2)と(IR,f4)である。
【0168】
よって、(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とすることに注意すると、最終的にmaxSとして(I1,f1),(I2,f2),(I3,f4)が出力される(図6−2(f))。なお、I=∪j=13Ij, Ij∩Ik=0(j≠k)である。
【0169】
なお、ここではアルゴリズム1を再帰的アルゴリズムとして例示したが、同等の結果を得ることができるならば、非再帰的アルゴリズムに変更するなど、適宜に変更可能である。
【0170】
さて、上述の[理論]などに基づき、≪問題≫の最小距離d(f,f~)を求めるアルゴリズムの一例であるアルゴリズム2を説明する〔図1−1および図1−2参照〕。
【0171】
[アルゴリズム2]
例示するアルゴリズム2では、
===================================
入力:多項式f(x),e1(x),e2(x),…,en(x)
多項式f(x)の零点が存在しない複素領域Dの境界Λ=∪μ=1KΛμにつき、各区分境界Λμの有理式による表示{γ1,…,γK},{I1,…,IK
但し、各区分境界Λμは、単射γμ: Iμ → Λμと表示される。
領域Dに含まれる一点Q
出力:多項式fから多項式f~までの最小距離d(f,f~)
===================================
とする。ここでは、Xが空集合のときには、mins∈X{Φ(s)}=∞と約束し、Φ(s)がs=σで定義されていないときには、Φ(σ)=∞と約束する。
【0172】
〈アルゴリズムの具体例〉
◎ステップS1
f(x)+Σj=1najej(x)=0を満たす実数a1,a2,…,anが存在する場合、T=d(f,0)とする。このような実数a1,a2,…,anが存在しない場合、T=∞とする。
<解説>
ステップS1は、多項式f~が恒等的に0である場合を排除しないための処理である。実数a1,a2,…,anが存在することの判定は、f(x)+Σj=1najej(x)をΣi=0Nwixiのように表現したときの各係数wiを0とした連立方程式を解けばよい〔但し、実際に解を求める必要はなく、連立方程式の解の存在判定(公知)を行うだけでよい。〕。このような実数a1,a2,…,anが存在する場合、最小距離はd(f,0)である。
多項式f~が恒等的に0である場合を考慮しないときは、初期値設定T=∞のみを行う。
【0173】
◎ステップS2
入力された多項式f(x),e1(x),e2(x),…,en(x)についてn≧2であるか否かを判定する。
n≧2である場合は、ステップS4の処理を行う。
n≧2ではない場合、つまりn=1の場合は、ステップS3の処理を行う。
【0174】
◎ステップS3
《n=1の場合》で説明した処理を行う。ステップS3の処理の詳細は次のとおりである。
【0175】
○ステップS301
Re f(x) Im e1(x)−Im f(x) Re e1(x)が恒等的に0であるか否かを判定する。
【0176】
○ステップS302
Re f(x) Im e1(x)−Im f(x) Re e1(x)が恒等的に0である場合、f(x)/e1(x)は定数である。この時点で記憶されているTの値がT>|f(x)/e1(x)|ならば、T=|f(x)/e1(x)|とし、このTをd(f,f~)として出力して処理を終了する。この時点で記憶されているTの値がT≦|f(x)/e1(x)|ならば、この時点でのTの値をd(f,f~)として出力して処理を終了する。
【0177】
○ステップS303
Re f(x) Im e1(x)−Im f(x) Re e1(x)が恒等的に0ではない場合、各μ(μ=1,2,…,K)に対して以下の処理を行う。区分境界の表示γμ(s)をxに代入し、Re f(γμ(s)) Im e1μ(s))−Im f(γμ(s)) Re e1μ(s))=0を解いて(根は有限個である。)、これらの有限個の根のうちσi(i=1,2,…)∈Iμについて連立方程式(12)を満たす実数解t1を求める。
【0178】
○ステップS304
実数解t1が存在するか否か判定する。
【0179】
○ステップS305
実数解t1が一つ以上存在する場合〔これをt1(i)とする。〕、この時点で記憶されているTの値がT>mini{|t1(i)|}ならば、T=mini{|t1(i)|}とし、このTをd(f,f~)として出力して処理を終了する。この時点で記憶されているTの値がT≦mini{|t1(i)|}ならば、この時点でのTの値をd(f,f~)として出力して処理を終了する。
【0180】
○ステップS306
実数解t1が存在しない場合、≪問題≫の解答としての多項式f~は存在しない。よって、最小距離が存在しない旨を出力して処理を終了する。
【0181】
◎ステップS4
《n≧2の場合》で説明した処理を行う。ステップS4の処理の詳細は次のとおりである。
【0182】
○ステップS401
入力された区分境界表示と一点Qから特定される領域Dが有界であるか否かを判定する。
<解説>
この判定処理は、定理1に基づくものであり、次のとおり行うことができる。
(☆ステップ1)
Λ⊂{z∈C|Re z < a}となる実数aを求める。境界Λは長さが有限の単純閉曲線であり、その区分境界表示が具体的に特定されているので、このような実数aを求めることができる。また、このような実数aは複素平面上で実軸上の一点で表示される。
(☆ステップ2)
点aと点Qとを結んだ線分が境界Λと交点を持ち、それが全て区分境界Λμの端点でなければ、重複度も込めて交点の数を数える。交点の数が奇数ならば領域Dは有界、偶数(0の場合も含む。)ならば非有界である。
(☆ステップ3)
もし、点aと点Qとを結んだ線分が境界Λと交点を持ち、そのうちの少なくとも一つが或る区分境界Λμの端点であるならば点aを取り直す。具体的には、点aと点Qとを結んだ線分が実軸と平行でないならば、aをa+1で置き替えて☆ステップ2を行う。また、点aと点Qとを結んだ線分が実軸と平行であるならば、aをa+iで置き替えて☆ステップ2を行う。
境界Λ上の点で区分境界の端点となっているものの数は有限である。上記の手続で得られる点aと点Qとを結んだ線分の傾きに同じものはないので、有限回の点aの取り直しで必ず区分境界の端点ではない点を交点とするように点aを取ることができる。
【0183】
○ステップS402
領域Dが有界ではない場合、全てのi(i=1,・・・,n)について多項式ei(x)の次数kが多項式fの次数m未満であるか否かを判定する。
【0184】
○ステップS403
全てのi(i=1,・・・,n)について多項式ei(x)の次数kが多項式fの次数m未満ではない場合、条件〈5〉に反するから、処理対象外である旨を出力して処理を終了する。
【0185】
領域Dが有界である場合、あるいは、全てのi(i=1,・・・,n)について多項式ei(x)の次数kが多項式fの次数m未満である場合、ステップS5の処理を行う。
【0186】
◎ステップS5
未選択の区分境界が存在するか否かを判定する(○ステップS50)。
未選択の区分境界が存在すれば、その中の一つΛμを選択する(○ステップS51)。
未選択の区分境界が存在しない場合、この時点で記憶されているTの値がT>min{m1,…,mμ,…,mK}ならば、T=min{m1,…,mμ,…,mK}とし、このTをd(f,f~)として出力して処理を終了する。この時点で記憶されているTの値がT≦min{m1,…,mμ,…,mK}ならば、この時点でのTの値をd(f,f~)として出力して処理を終了する。(○ステップS52)。
<解説>
ステップS5は、全ての区分境界について以降のステップS6〜ステップS8の各処理を行うための処理である。全ての区分境界についてステップS6〜ステップS8の各処理を実行した場合は、終了である。出力Tが∞のときは、集合Fに属する多項式で領域Dに零点を持つ多項式は存在しない。
【0187】
◎ステップS6
ステップS51の処理で選択された区分境界Λμに対応する実区間Iμ⊂Rが一点であるか否かを判定する。これは、実区間Iμ=[α,β]と表されている場合にα=βの成立を判定すればよい。
実区間Iμが一点δ、つまりIμ=[δ,δ]の場合にはステップS7の処理へ、実区間Iμが一点ではない場合にはステップS8の処理へ、進む。
【0188】
◎ステップS7
ステップS7は実区間Iμが一点である場合にΦμ(δ)を求める処理である。但し、δが集合Δ~μに属する場合、Φμ(δ)は式(51)の第一式で求め、δが集合Iμ\Δμに属する場合、Φμ(δ)は式(51)の第二式で求める。
ステップS7の処理の詳細は次のとおりである。
【0189】
○ステップS71
実区間Iμ、つまりδが集合Iμ\Δμに属するか否か判定する。Δμは式(49)のとおりである。なお、実区間Iμが一点δであるから、1≦j<k≦nの全てのj、kについて、A(ejμ(δ)),ekμ(δ)))=0が成立するならば、δ∈Δμであることがわかる。
【0190】
○ステップS72
実区間Iμ、つまりδが集合Iμ\Δμに属する場合、Φμ(δ)を式(51)の第二式で求める。このΦμ(δ)をmμとする。この後、ステップS50の処理に進む。
【0191】
○ステップS73
実区間Iμ、つまりδが集合Iμ\Δμに属さない場合、δが集合Δ~μに属するか否か判定する。Δ~μは式(50)のとおりである。
【0192】
○ステップS74
δが集合Δ~μに属する場合、Φμ(δ)を式(51)の第一式で求める。このΦμ(δ)をmμとする。この後、ステップS50の処理に進む。
【0193】
○ステップS75
δが集合Δ~μに属さない場合、実区間Iμである点δを零点とする最近実多項式f~は存在しない(定理3)。そこでmμを∞とする。この後、ステップS50の処理に進む。
【0194】
◎ステップS8
ステップS8は実区間Iμが一点ではない場合にΦμ(s)を求める処理である。
但し、sが集合Δ~μに属する場合において、
[其の壱]sが集合Δ~μ\Z~μに属するならばΦμ(s)は式(51)の第一式で表される有理関数としてその最小値を求めることができ、
[其の弐]sが集合Z~μに属するならば有限個のs∈Z~μをそれぞれ式(51)の第一式で表されるΦμ(s)に入力することでその最小値を求めることができる。
また、sが集合Iμ\Δμ(=Jμ)に属する場合において、
[其の参]sが集合Jμ\Zμに属するならば、Jμ\Zμを有限個の区間Jμ,h(h=1,2,…)の和集合で書き、上記アルゴリズム1を{φμ,1,…,φμ,n}と各Jμ,hに適用することで、Φμ(s)をJμ\Zμ上の区分的な有理関数として得ることができるから、その最小値を求めることができ、
[其の四]sが集合Zμに属するならば有限個のs∈Zμをそれぞれ式(51)の第二式で表されるΦμ(s)に入力することでその最小値を求めることができる。
ステップS8の処理の詳細は次のとおりである。
【0195】
○ステップS81
[其の弐]の場合の処理である。式(55)に従いmμ,1を求める。Z~μは式(52)のとおりである。Φμ(s)は式(51)の第一式である。式(55)ではZ~μの有限個の元σ,…,σの個数をrとしている。
【数94】

【0196】
○ステップS82
[其の四]の場合の処理である。式(56)に従いmμ,2を求める。Zμは式(53)のとおりである。Φμ(s)は式(51)の第二式である。式(56)ではZμの有限個の元σ,…,σの個数をrとしている(記号rは説明の便宜で用いており、Z~μの元の個数と常に同じという趣旨ではない。)。
【数95】

【0197】
○ステップS83
[其の壱]の場合の処理である。式(57)に従いmμ,3を求める。Δ~μは式(50)のとおりである。Z~μは式(52)のとおりである。Φμ(s)は式(51)の第一式である。Z~μは有限集合であり、Δ~μ\Z~μは有限個の区間Lμ,h(h=1,2,…,r)の和集合で表される。ここでは有限個の区間の個数をrとした(記号rは説明の便宜で用いており、Z~μやZμの元の個数と常に同じという趣旨ではない。)。但し、区間は点に退化している場合もある。
区間Lμ,hでΦμ(s)の最小値はΦμ(s)を微分して0となるときの根Xを入力したΦμ(X)の中に存在する可能性がある。また、区間Lμ,hが端点s=Yを持つときはΦμ(Y)も最小値の可能性がある。これらの可能性のある値のうち最小値を求めればよい。区間Lμ,hが点s=Wに退化しているときはΦμ(W)を求めればよい。各区間Lμ,hで求まる最小値うち最小のものがmμ,3である。なお、式(57)の分母の記号±はjごとに区間Lμ,h(h=1,2,…,r)に対していずれか一方に一意に定まることに留意すること。
【数96】

【0198】
○ステップS84
[其の参]の場合の処理である。式(58)に従いmμ,4を求める。Jμ=Iμ\Δμとする。Δμは式(49)のとおりである。Zμは式(53)のとおりである。Jμ\Zμを有限個の区間Jμ,h(h=1,2,…,r)の和集合で表し(ここでは有限個の区間の個数をrとした。記号rは説明の便宜で用いており、Δ~μ\Z~μの有限個の区間の個数と常に同じという趣旨ではない。)、上記アルゴリズム1を{φμ,1,…,φμ,n}と各Jμ,hに適用することで、Φμ(s)をJμ\Zμ上の区分的な有理関数として得る。つまり、或るJμ,hにつき、Φμ(s)は、アルゴリズム1によってΦμ,h(s)={(Jμ,h,jμ,θ(j)(s))|1≦j≦ph}として得られる。但し、θ(j)∈{1,…,n}, Jμ,h,j⊂Jμ,hである。なお、アルゴリズム1の適用において、式(51)で表現される{φμ,1,…,φμ,n}の分母分子の絶対値は外れて±のいずれか一方に一意に定まることに留意すること。
区間Jμ,hでΦμ,h(s)の最小値は、Φμ,h(s)を微分して0となるときの根Xを入力したΦμ,h(X)の中に存在する可能性がある(実際は区分Jμ,h,jごとにφμ,θ(j)(s)を微分して0となるときの根Xを入力したφμ,θ(j)(X)の中に存在する可能性がある。また、区分Jμ,h,jの端点s=Vを入力とするφμ,θ(j)(V)も最小値の可能性がある。)。また、区間Jμ,hが端点s=Yを持つときはΦμ,h(Y)も最小値の可能性がある。これらの可能性のある値のうち最小値を求めればよい。区間Jμ,hが点s=Wに退化しているときはΦμ,h(W)を求めればよい。各区間Jμ,hで求まる最小値うち最小のものがmμ,4である。
【数97】

【0199】
○ステップS85
mμ=min{mμ,1,mμ,2,mμ,3,mμ,4}を求める。この後、ステップS50の処理に進む。
【0200】
[アルゴリズムの計算量の解析]
まず、アルゴリズム1の計算量を解析する。この解析のために、Davenport-Schinzel列を定義する。
【0201】
定義1(Davenport-Schinzel列)
Σn={a1,a2,…,an}とし、Ln,sをアルファべットΣ上の文字列の集合で、aiaiおよびξijs(i≠j)を部分文字列として含まないものとする。ここで、ξijsは式(59)で定義される長さs+2の文字列である。λ(n,s)をmax{|σ||σ∈Ln,s}で定義し、Ln,sに属する列を(n,s)Davenport-Schinzel列という。
【数98】

【0202】
下記の補題2は、アルゴリズム1とDavenport-Schinzel列の関係を示すもので、参考文献5に記載されたLemma2.4と本質的に同じものである。
(参考文献5)M.J.Atallah, Some dynamic computational geometry problems, Computers and Mathematics with Applications, Vol.11, No.12, pp.1171-1181, 1985.
【0203】
===================================
[補題2]f,…,fを、実数値を取るt∈I⊂Rの関数かつ連続なものとする。異なる二つのfとfを任意に取ったとき、fとfが高々s回しか交わらないとすると、
h(t)=max{f1(t),…,fn(t)}
は、Iを高々λ(n,s)個の区間に細分することにより、各細分上でf,…,fのいずれかと等しいようにできる。ここで、λ(n,s)という値はこれ以上小さくはできない。
===================================
【0204】
δを、アルゴリズム1において、f,…,fの分母分子の次数の最大値とする。すると、fとf(j≠k)は、Iにおいて高々2δ回しか交わらない。よって、max{f~1,f~2}を計算するために、●ステップ3において、fj=fkという方程式を解く回数は、高々、式(60)で表されるとおりである。
【数99】

【0205】
よって、max{f1,…,fn}を計算するためにfj=fkという方程式を解く回数は、高々、式(61)で表されるとおりとなる。
【数100】

【0206】
式(61)の値を評価するために、下記の補題3を用いる。
===================================
[補題3]任意の正の自然数mに対し、mλ(n,s)≦λ(mn,s)が成立する。
===================================
(証明)
σ,…,σを、アルファベットΣ,Σ2n\Σ,…,Σmn\Σ(m−1)n上の(n,s)Davenport-Schinzel列とする。このとき、σ,…,σは、Σmn上の(mn,s)Davenport-Schinzel列で長さがmλ(n,s)であるから、補題3の不等式は成り立つ。
(証明終)
【0207】
補題3から、式(62)が得られる。
【数101】

【0208】
λ(n,s)はnとsについて、多項式オーダーである。例えば、
λ(n,s)≦sn(n-1)+1
という評価が、参考文献6で与えられている。
(参考文献6)H.Davenport and A.Schinzel, A combinatorial problem concerned with differential equations, American Journal of Mathematics, Vol.87, No.3, pp.684-694, 1965.
【0209】
次に、アルゴリズム2の計算量を解析する。特に、ステップS70番台、S80番台の計算量について解析する。
【0210】
d次の多項式p(x)∈R[x]と、分母分子の次数が高々mの有理関数r(x)∈R[x]に対して、p(r(x))の分母分子の次数は高々mdである。よって、Rep(r(x)),Imp(r(x))の分母分子の次数は高々2mdとなる。
【0211】
d=max{deg(f),deg(e1),…,deg(en)}とし、γ1(s),…,γK(s)の分母分子のうちの最高次数をmとする。すると、f(γμ(s)),ejμ(s))の分母分子のうちの最高次数は高々mdであり、
A(ejμ(s)),ekμ(s))), A(ejμ(s)),f(γμ(s))),
A(f(γμ(s)),if(γμ(s)))
の分母分子の最高次数は高々8mdである。
【0212】
各μ(μ=1,…,K)に対し、解く必要のある方程式の数は下記の通りである。
【0213】
・Δμ,Δ~μ,Z~μ,Zμを構成するためには、それぞれ一つの方程式を解けばよい。
Δμ,Δ~μ,Z~μ,Zμに対する方程式の次数は高々、
8md, 8md, min{8md,mnd}, 4mn(n+1)d
である。
【0214】
・Jμ\Zμ上でΦμを構成するために必要な解くべき方程式の数と次数は、高々、式(63)で与えられるものである。Jμ\Zμは、高々4mn(n+1)d+8md+1個の区間の和集合として書けることに注意すること。Φμを構成するために、各区間上で解く必要のある方程式の数は、高々、式(64)で与えられるものである。
【数102】

【0215】
・mμ,1,mμ,2を計算するのに比較が必要な値は、高々、
min{8md,mnd}, 4mn(n+1)d
である。
【0216】
・Δ~μ\Z~μは、高々8md個の区間(一点に退化したものも含む。)の和として書ける。
μ,3を、Δ~μ\Z~μの一点に退化していない区間上で計算するためには、Φ'μ(s)=0を解く必要がある。Φμ(s)の分母分子の次数は高々8m(n+1)dだから、Φ'μ(s)の分子の次数は、高々、
16m(n+1)d-1
である。
【0217】
・mμ,4を計算するために、Φ'μ(s)=0を、Jμ\Zμの各区間上で解く必要がある。Φμ(s)の分母分子の次数は高々8m(n+1)dだから、Φ'μ(s)の分子の次数は、高々、
16m(n+1)d-1
である。
【0218】
以上より、解く必要のある方程式の数、その次数は、m,n,d,Mの多項式オーダーであることが分かる。
以上で[アルゴリズムの計算量の解析]の説明は終わりである。
【0219】
上記のアルゴリズムは一例に過ぎず、論理的な先後関係を逸脱しない限り、処理の順番を入れ替えたり変更したりすることができる。
例えば、ステップS81、S82、S83、S84の各処理に論理的な先後関係はないので適宜に処理手順を変更することができる。また、ステップS1の処理内容は全ての処理に先立ち行われることに限定されるものではない。例えば、次のようにも変更できる。ステップS1では単にT=∞に設定するだけにする。そして、ステップS52の処理の後、終了することなく、多項式f~が恒等的に0となる場合の実数a1,a2,…,anの存在を判定し、存在すればT1=d(f,0)とする。さらに、T1とステップS52の処理の段階でのTとを比較してこの最小値を距離の最小値とする。
【0220】
さらに、上記のアルゴリズムでは、複素領域Dに多項式f(x)の零点が存在しないことが予め既知のものとしたが、Sturmの定理と偏角の原理を用いて、複素領域Dに零点が存在しないことを確認する処理を前置で行うようにしてもよい。
【0221】
また、上記のアルゴリズムは、多項式fと多項式f~との距離の最小値を求めるものであったが、多項式f~を出力するようにしてもよい。
この場合、一例として、上記アルゴリズムを次のように変更すればよい〔図2−1および図2−2参照〕。
【0222】
・ステップS1を次のように変更する(ステップS1a)。
f(x)+Σj=1ncjej(x)=0を満たす実数a1,a2,…,anが存在する場合、T=d(f,0)とする。このような実数a1,a2,…,anが存在しない場合、T=∞とする。また、T=d(f,0)とき多項式Pを0とする。T=∞のとき多項式Pを−1とする。多項式P=−1は、「領域Dに零点を持つ多項式であって式(7)で表される多項式の集合に属する多項式は存在しない」ということである。
【0223】
・ステップS302を次のように変更する(ステップS302a)。
f(x)/e1(x)が定数である場合、この時点で記憶されているTの値がT>|f(x)/e1(x)|ならば、T=|f(x)/e1(x)|,P=0〔ゼロ多項式〕とし、このTとPを出力して処理を終了する。この時点で記憶されているTの値がT≦|f(x)/e1(x)|ならば、この時点でのTとPを出力して処理を終了する。
【0224】
・ステップS305を次のように変更する(ステップS305a)。
実数解t1が一つ以上存在する場合〔これをt1(i)とする。〕、この時点で記憶されているTの値がT>mini{|t1(i)|}ならば、T=mini{|t1(i)|},P=f(x)+mini{|t1(i)|}e1(x)とし、このTとPを出力して処理を終了する。この多項式Pは、f(x)±mini{|t1(i)|}e1(x)のうちの一つである。本発明では一つの多項式f~を提示すれば十分である。また、この時点で記憶されているTの値がT≦mini{|t1(i)|}ならば、この時点でのTとPを出力して処理を終了する。
【0225】
・ステップS52を次のように変更する(ステップS52a)。
未選択の区分境界が存在しなければ、この時点で記憶されているTの値がT>min{m1,…,mμ,…,mK}ならば、T=min{m1,…,mμ,…,mK}とし,このTを与えたm(x∈{1,…,K})がステップS72、S82、S84のいずれかで得られたものである場合には多項式Pを式(47i)で求め、このTを与えたm(x∈{1,…,K})がステップS74、S81、S83のいずれかで得られたものである場合には多項式Pを式(47k)で求め、このTとPを出力して処理を終了する。
また、この時点で記憶されているTの値がT≦min{m1,…,mμ,…,mK}ならば、この時点でのTとPを出力して処理を終了する。
【0226】
なお、最小距離Tに併せて多項式Pを出力することに限定するものではなく、多項式Pのみを出力するようにしてもよい。
【0227】
また、上述のアルゴリズムでは下記のように変更できる。
n≧2であることが既知である場合には、ステップS2、ステップS300番台の各処理を省略できる。
領域Dが有界であることが既知である場合には、ステップS400番台の各処理を省略できる。
n≧2および領域Dが有界であることが既知である場合には、ステップS2、ステップS300番台、ステップS400番台の各処理を省略できる。
多項式f~が恒等的に0である場合を除くときには、ステップS1の処理を省略できる。但し、この場合は初期値設定を適宜に行う。
【0228】
[第1実施形態]
以下に、本発明の第1実施形態を上記アルゴリズム例〔図1−1、図1−2参照〕に則して説明する。第1実施形態は、多項式f(x)と多項式f~(x)=f(x)+Σj=1na~jej(x) (a~j∈R)との最小距離の算出〔多項式間距離算出〕に係わる。
図3は、本実施形態に係わる多項式間距離算出装置(1)のハードウェア構成を例示した構成ブロック図である。
【0229】
図3に例示するように、多項式間距離算出装置(1)は、キーボードなどが接続可能な入力部(11)、液晶ディスプレイなどが接続可能な出力部(12)、多項式間距離算出装置(1)外部に通信可能な通信装置(例えば通信ケーブル)が接続可能な通信部(13)、CPU(Central Processing Unit)(14)〔キャッシュメモリやレジスタなどを備えていてもよい。〕、メモリであるRAM(15)やROM(16)、ハードディスクである外部記憶装置(17)並びにこれらの入力部(11)、出力部(12)、通信部(13)、CPU(14)、RAM(15)、ROM(16)、外部記憶装置(17)間のデータのやり取りが可能なように接続するバス(18)を有している。また必要に応じて、多項式間距離算出装置(1)に、CD−ROMなどの記憶媒体を読み書きできる装置(ドライブ)などを設けるとしてもよい。このようなハードウェア資源を備えた物理的実体としては、汎用コンピュータなどがある。
【0230】
多項式間距離算出装置(1)の外部記憶装置(17)には、多項式fと多項式f~との最小距離の算出に必要となるプログラムおよびこのプログラムの処理において必要となるデータなどが記憶されている(外部記憶装置に限らず、例えばプログラムを読み出し専用記憶装置であるROMに記憶させておくなどでもよい。)。また、これらのプログラムの処理によって得られるデータなどは、RAMや外部記憶装置などに適宜に記憶される。以下、演算結果やその格納領域のアドレスなどを記憶するRAM(15)やレジスタなどの記憶装置を単に「メモリ」と呼ぶことにする。
【0231】
より具体的には、多項式間距離算出装置(1)の外部記憶装置(17)〔あるいはROMなど〕には、
多項式f~が恒等的に0となる場合について調査するための恒等式調査プログラム、
入力された多項式f(x),e1(x),e2(x),…,en(x)の個数についてn≧2であるか否かを判定するための多項式数条件判定プログラム、
n=1の場合に最小距離を算出するための第一最小距離算出プログラム、
n≧2の場合に領域Dが有界であるか否かを判定するための領域有界判定プログラム、
多項式ei(x) (i=1,・・・,n)の次数kが多項式fの次数m未満であるか否かを判定するための次数判定プログラム、
未選択の区分境界の有無を調べ、未選択の区分境界がある場合にはその中から一つの区分境界を選択するための探索制御プログラム、
選択された区分境界が点であるか否かを判定するための区分境界点判定プログラム、
選択された区分境界が点(区分境界に対応する実区間Iμが点δ)である場合に、点δが集合Iμ\Δμに属する場合は式(51)の第二式で距離候補mμを求め、点δが集合Δ~μに属する場合は式(51)の第一式で距離候補mμ求めるための第一距離候補探索プログラム、
選択された区分境界が点でない場合に、式(55)〜式(58)でmμ,1,mμ,2,mμ,3,mμ,4を求めてから、距離候補mμ=min{mμ,1,mμ,2,mμ,3,mμ,4}を求めるための第二距離候補探索プログラム、
第一距離候補探索プログラムと第二距離候補探索プログラムの実行で得られた値のうちから最小のもの(最小距離)を算出するための第二最小距離算出プログラム、
およびこれらのプログラムの処理において必要となるデータなどが記憶されている。その他、これらのプログラムに基づく処理などを制御するための制御プログラムも適宜に記憶しておく。
【0232】
多項式間距離算出装置(1)では、外部記憶装置(17)〔あるいはROMなど〕に記憶された各プログラムとこの各プログラムの処理に必要なデータが必要に応じてメモリ(20)に読み込まれて、適宜にCPU(14)で解釈実行・処理される。その結果、CPU(14)が所定の機能(恒等式調査部、多項式数条件判定部、第一最小距離算出部、領域有界判定部、次数判定部、探索制御部、区分境界点判定部、第一距離候補探索部、第二距離候補探索部、第二最小距離算出部、制御部)を実現する。
【0233】
図1−1、図1−2を参照して、本実施形態における多項式間距離算出処理について説明する。
【0234】
多項式間距離算出装置(1)の外部記憶装置(17)には、予め、多項式f(x),e1(x),e2(x),…,en(x)、多項式f(x)の零点が存在しない複素領域Dの境界Λ=∪μ=1KΛμにつき、各区分境界Λμの有理式による表示({γ1,…,γK},{I1,…,IK})〔各区分境界Λμは、単射γμ: Iμ → Λμで表示される。〕、領域Dを指定する一点Qがデータとして予め記憶されているとする。
【0235】
なお、これらの情報などは、予め多項式間距離算出装置(1)の外部記憶装置(17)に記憶しておくのではなく、例えば、入力部(11)から入力されるとしてもよいし、あるいは、これらの情報などを格納した記録媒体からドライブを駆動して読み込むようにしてもよく、適宜に変更可能である。
【0236】
また、データとして予め記憶される情報が、これらの情報などに限定される趣旨ではない。例えば、多項式f(x),e1(x),e2(x),…,en(x)について、多項式そのものを記憶するのではなく、各次数のxの項についてその係数を記憶しておくようにしてもよい。また、例えば、境界Λを表す式自体を入力部(11)から入力するとし、境界Λを区分境界に適宜に分割するためのプログラムを解釈・実行するCPU(14)が、メモリ(20)に格納された境界Λをメモリ(20)から読み込んで、区分境界を出力するようにしてもよい。
【0237】
なお、本発明の細部においては、数値計算処理のみならず有理式や多項式などの数式処理も必要となるが、数値計算処理および数式処理自体は、公知技術と同様にして達成されるので、その演算処理方法などの詳細な説明は省略する(この点の技術水準を示す数式処理が可能なソフトウェアとしては、例えば、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日検索]を参照のこと。)。
【0238】
まず、多項式間距離算出装置(1)の制御部(199)は、外部記憶装置(17)から多項式f(x),e1(x),e2(x),…,en(x)、各区分境界Λμの有理式による表示({γ1,…,γK},{I1,…,IK})、領域Dを指定する一点Qを読み込み、それぞれをメモリ(20)の所定の格納領域に格納しておく。以後、「メモリから○○を読み込む」旨の説明をした場合は、「メモリにおいて○○が格納されている所定の格納領域から○○を読み込む」ことを意味するとする。
【0239】
多項式間距離算出装置(1)の恒等式調査部(100)は、メモリ(20)から多項式f(x),e1(x),e2(x),…,en(x)を読み込み、f(x)+Σj=1najej(x)=0を満たす実数a1,a2,…,anの存在を判定する。恒等式調査部(100)は、そのような実数a1,a2,…,anが存在すればT=d(f,0)に設定してTをメモリ(20)の所定の格納領域に格納し、このような実数a1,a2,…,anが存在しない場合は、T=∞に設定してTをメモリ(20)の所定の格納領域に格納する〔ステップS1〕。
【0240】
多項式間距離算出装置(1)の多項式数条件判定部(110)は、メモリ(20)から多項式e1(x),e2(x),…,en(x)を読み込み、n≧2であるか否かを判定する〔ステップS2〕。制御部(199)は、n≧2が成立の場合、ステップS401の処理を実行するように制御を行い、n=1が成立の場合、ステップS301の処理を実行するように制御を行う。
【0241】
多項式間距離算出装置(1)の第一最小距離算出部(120)は、メモリ(20)から多項式f(x),e1(x),e2(x),…,en(x)〔但し、実際にはf(x),e1(x)である。〕を読み込み、メモリ(20)と協働して、n=1の場合の距離候補(既述の記法に従えば|f(x)/e1(x)|あるいはmini{t1(i)})を算出し、この距離候補とメモリ(20)に記憶されているTのいずれか最小のものを新たなT(n=1の場合の最小距離T)としてメモリ(20)の所定の格納領域に格納する〔ステップS301〜S305〕。そして、制御部(199)がメモリ(20)に記憶されているTを液晶ディスプレイなどに表示する出力処理を行って多項式間距離算出処理を終了する。もし、ステップS304の処理で条件を満たさない場合には、制御部(199)の制御により、多項式f~が存在しない旨を通知するなどして多項式間距離算出処理を終了する〔ステップS306〕。
【0242】
多項式間距離算出装置(1)の領域有界判定部(130)は、メモリ(20)から各区分境界Λμの有理式による表示({γ1,…,γK},{I1,…,IK})、領域Dを指定する一点Qを読み込み、領域Dが有界であるか否かを判定する〔ステップS401〕。制御部(199)は、領域Dが有界であると判定された場合、ステップS50の処理を実行するように制御を行い、領域Dが有界ではないと判定された場合、ステップS402の処理を実行するように制御を行う。
【0243】
多項式間距離算出装置(1)の次数判定部(140)は、メモリ(20)から多項式f(x),e1(x),e2(x),…,en(x)を読み込み、全てのi(i=1,・・・,n)について多項式ei(x)の次数kが多項式fの次数m未満であるか否かを判定する〔ステップS402〕。この判定に合格した場合、制御部(199)は、ステップS50の処理を実行するように制御を行う。もし、ステップS402の処理で条件を満たさない場合には、制御部(199)の制御により、処理対象外である旨を通知するなどして多項式間距離算出処理を終了する〔ステップS403〕。
【0244】
次いで、多項式間距離算出装置(1)の探索制御部(150)は、未選択の区分境界の有無を判定する〔ステップS50〕。未選択区分境界が存在しないと判定されると、制御部(199)が、ステップS52の処理を実行するように制御を行う。未選択区分境界が存在すると判定されると、探索制御部(150)は、未選択区分境界から一つ選択して、その情報をメモリ(20)の所定の格納領域に格納する〔ステップS51〕。具体例として、探索制御部(150)は、区分境界Λμ(μ=1,2,…,K)について、μ=1からインクリメントしてμ=Kまで各処理を行うとすればよい。
【0245】
多項式間距離算出装置(1)の第二最小距離算出部(190)は、メモリ(20)から、Tと区分境界毎に得られた距離候補m1,…,mμ,…,mKを読み込み、Tとmin{m1,…,mμ,…,mK}のいずれか最小のものを新たなT(n≧2の場合の最小距離T)としてメモリ(20)の所定の格納領域に格納する〔ステップS52〕。そして、制御部(199)がメモリ(20)に記憶されているTを液晶ディスプレイなどに表示する出力処理を行って多項式間距離算出処理を終了する。
【0246】
多項式間距離算出装置(1)の区分境界点判定部(160)は、メモリ(20)から、ステップS51の処理で選択された区分境界に対応する実区間Iμを読み込み、実区間Iμが点であるか否かを判定する〔ステップS6〕。制御部(199)は、実区間Iμが点であると判定された場合、ステップS71の処理を実行するように制御を行い、実区間Iμが点ではないと判定された場合、ステップS81の処理を実行するように制御を行う。
【0247】
多項式間距離算出装置(1)の第一距離候補探索部(170)は、メモリ(20)から、ステップS51の処理で選択された区分境界の有理式による表示(γμ、Iμ:但し、実区間Iμの内実は点δである。)、多項式f(x),e1(x),e2(x),…,en(x)を読み込み、メモリ(20)と協働して、点δが集合Iμ\Δμに属する場合はmμ=Φμ(δ)を式(51)の第二式で求め、点δが集合Δ~μに属する場合はmμ=Φμ(δ)を式(51)の第一式で求め、点δがいずれの集合にも属さない場合にはmμ=∞として、距離候補mμをメモリ(20)の所定の格納領域に格納する〔ステップS71〜S75〕。
【0248】
多項式間距離算出装置(1)の第二距離候補探索部(180)は、メモリ(20)から、ステップS51の処理で選択された区分境界の有理式による表示(γμ、Iμ)、多項式f(x),e1(x),e2(x),…,en(x)を読み込み、メモリ(20)と協働して、式(55)〜式(58)でmμ,1,mμ,2,mμ,3,mμ,4を求めてから、mμ=min{mμ,1,mμ,2,mμ,3,mμ,4}を求め、距離候補mμをメモリ(20)の所定の格納領域に格納する〔ステップS81〜S85〕。
【0249】
制御部(199)は、ステップS72、S74、S75、S85の各処理の後、ステップS50の処理を実行するように制御を行う。
【0250】
[第2実施形態]
以下に、本発明の第2実施形態を上記アルゴリズム例〔図2−1、図2−2参照〕に則して説明する。第2実施形態は、多項式f(x)と多項式f~(x)=f(x)+Σj=1na~jej(x) (a~j∈R)との最小距離を与える多項式f~(x)の算出〔一変数最近実多項式算出〕に係わる。ここでは説明の便宜から、第1実施形態の最小距離の算出に加えて、多項式f~(x)も算出するものとして説明する。
【0251】
第2実施形態に係わる多項式間距離算出兼一変数最近実多項式算出装置のハードウェア構成は、図3に示した多項式間距離算出装置(1)のハードウェア構成と同様であるから、説明を略する。そこで、第2実施形態では、第1実施形態の多項式間距離算出装置(1)を、多項式間距離算出兼一変数最近実多項式算出装置(2)と呼称変更する。
【0252】
多項式間距離算出兼一変数最近実多項式算出装置(2)の外部記憶装置(17)〔あるいはROMなど〕には、
多項式f~が恒等的に0となる場合について調査するための恒等式調査プログラム、
入力された多項式f(x),e1(x),e2(x),…,en(x)の個数についてn≧2であるか否かを判定するための多項式数条件判定プログラム、
n=1の場合に最小距離を算出すると共にこの最小距離に対応する多項式f~を算出するための第一最小距離算出プログラム、
n≧2の場合に領域Dが有界であるか否かを判定するための領域有界判定プログラム、
多項式ei(x) (i=1,・・・,n)の次数kが多項式fの次数m未満であるか否かを判定するための次数判定プログラム、
未選択の区分境界の有無を調べ、未選択の区分境界がある場合にはその中から一つの区分境界を選択するための探索制御プログラム、
選択された区分境界が点であるか否かを判定するための区分境界点判定プログラム、
選択された区分境界が点(区分境界に対応する実区間Iμが点δ)である場合に、点δが集合Iμ\Δμに属する場合は式(51)の第二式で距離候補mμを求め、点δが集合Δ~μに属する場合は式(51)の第一式で距離候補mμ求めるための第一距離候補探索プログラム、
選択された区分境界が点でない場合に、式(55)〜式(58)でmμ,1,mμ,2,mμ,3,mμ,4を求めてから、距離候補mμ=min{mμ,1,mμ,2,mμ,3,mμ,4}を求めるための第二距離候補探索プログラム、
第一距離候補探索プログラムと第二距離候補探索プログラムの実行で得られた値のうちから最小のもの(最小距離)を算出すると共にこの最小距離に対応する多項式f~を算出するための第二最小距離・多項式算出プログラム、
およびこれらのプログラムの処理において必要となるデータなどが記憶されている。その他、これらのプログラムに基づく処理などを制御するための制御プログラムも適宜に記憶しておく。
【0253】
多項式間距離算出兼一変数最近実多項式算出装置(2)では、外部記憶装置(17)〔あるいはROMなど〕に記憶された各プログラムとこの各プログラムの処理に必要なデータが必要に応じてメモリ(20)に読み込まれて、適宜にCPU(14)で解釈実行・処理される。その結果、CPU(14)が所定の機能(恒等式調査部、多項式数条件判定部、第一最小距離・多項式算出部、領域有界判定部、次数判定部、探索制御部、区分境界点判定部、第一距離候補探索部、第二距離候補探索部、第二最小距離・多項式算出部、制御部)を実現する。
【0254】
図2−1、図2−2を参照して、本実施形態における多項式間距離算出処理について説明する。
【0255】
第2実施形態では、多項式間距離算出兼一変数最近実多項式算出装置(2)の外部記憶装置(17)に、予め、多項式f(x),e1(x),e2(x),…,en(x)、多項式f(x)の零点が存在しない複素領域Dの境界Λ=∪μ=1KΛμにつき、各区分境界Λμの有理式による表示({γ1,…,γK},{I1,…,IK})〔各区分境界Λμは、単射γμ: Iμ → Λμで表示される。〕、領域Dを指定する一点Qがデータとして予め記憶されているとする。この点については第1実施形態と同様であり、例えば、これらの情報が入力部(11)から入力されるとしてもよいし、多項式f(x),e1(x),e2(x),…,en(x)について、多項式そのものを記憶するのではなく、各次数のxの項についてその係数を記憶しておくようにしてもよい。また、数値計算処理および数式処理が、公知技術と同様にして達成されることも既述のとおりである。
【0256】
まず、多項式間距離算出兼一変数最近実多項式算出装置(2)の制御部(299)は、外部記憶装置(17)から多項式f(x),e1(x),e2(x),…,en(x)、各区分境界Λμの有理式による表示({γ1,…,γK},{I1,…,IK})、領域Dを指定する一点Qを読み込み、それぞれをメモリ(20)の所定の格納領域に格納しておく。
【0257】
多項式間距離算出兼一変数最近実多項式算出装置(2)の恒等式調査部(200)は、メモリ(20)から多項式f(x),e1(x),e2(x),…,en(x)を読み込み、f(x)+Σj=1najej(x)=0を満たす実数a1,a2,…,anの存在を判定する。恒等式調査部(200)は、そのような実数a1,a2,…,anが存在すればT=d(f,0)、P=0に設定してTおよびPをメモリ(20)の所定の格納領域に格納し、このような実数a1,a2,…,anが存在しない場合は、T=∞、P=−1に設定してTおよびPをメモリ(20)の所定の格納領域に格納する〔ステップS1a〕。
【0258】
多項式間距離算出兼一変数最近実多項式算出装置(2)の多項式数条件判定部(210)は、メモリ(20)から多項式e1(x),e2(x),…,en(x)を読み込み、n≧2であるか否かを判定する〔ステップS2〕。制御部(299)は、n≧2が成立の場合、ステップS401の処理を実行するように制御を行い、n=1が成立の場合、ステップS301の処理を実行するように制御を行う。
【0259】
多項式間距離算出兼一変数最近実多項式算出装置(2)の第一最小距離・多項式算出部(220)は、メモリ(20)から多項式f(x),e1(x),e2(x),…,en(x)〔但し、実際にはf(x),e1(x)である。〕を読み込み、メモリ(20)と協働して、n=1の場合の距離候補(既述の記法に従えば|f(x)/e1(x)|あるいはmini{t1(i)})および多項式候補(既述の記法に従えば0あるいはf(x)+mini{|t1(i)|}e1(x))を算出し、この距離候補とメモリ(20)に記憶されているTのいずれか最小のものを新たなT(n=1の場合の最小距離T)としてメモリ(20)の所定の格納領域に格納する〔ステップS301〜S305a〕。ここでTの書き換えが行われた場合は、メモリ(20)に記憶されているPを多項式候補で書き換えるが、Tの書き換えが行われなかった場合は、メモリ(20)に記憶されているPの書き換えを行わない。そして、制御部(299)がメモリ(20)に記憶されているTおよびPを液晶ディスプレイなどに表示する出力処理を行って多項式間距離算出処理を終了する。もし、ステップS304の処理で条件を満たさない場合には、制御部(299)の制御により、多項式f~が存在しない旨を通知するなどして多項式間距離算出処理を終了する〔ステップS306〕。
【0260】
多項式間距離算出兼一変数最近実多項式算出装置(2)の領域有界判定部(230)は、メモリ(20)から各区分境界Λμの有理式による表示({γ1,…,γK},{I1,…,IK})、領域Dを指定する一点Qを読み込み、領域Dが有界であるか否かを判定する〔ステップS401〕。制御部(299)は、領域Dが有界であると判定された場合、ステップS50の処理を実行するように制御を行い、領域Dが有界ではないと判定された場合、ステップS402の処理を実行するように制御を行う。
【0261】
多項式間距離算出兼一変数最近実多項式算出装置(2)の次数判定部(240)は、メモリ(20)から多項式f(x),e1(x),e2(x),…,en(x)を読み込み、全てのi(i=1,・・・,n)について多項式ei(x)の次数kが多項式fの次数m未満であるか否かを判定する〔ステップS402〕。この判定に合格した場合、制御部(299)は、ステップS50の処理を実行するように制御を行う。もし、ステップS402の処理で条件を満たさない場合には、制御部(299)の制御により、処理対象外である旨を通知するなどして多項式間距離算出処理を終了する〔ステップS403〕。
【0262】
次いで、多項式間距離算出兼一変数最近実多項式算出装置(2)の探索制御部(250)は、未選択の区分境界の有無を判定する〔ステップS50〕。未選択区分境界が存在しないと判定されると、制御部(299)が、ステップS52の処理を実行するように制御を行う。未選択区分境界が存在すると判定されると、探索制御部(250)は、未選択区分境界から一つ選択して、その情報をメモリ(20)の所定の格納領域に格納する〔ステップS51〕。具体例として、探索制御部(250)は、区分境界Λμ(μ=1,2,…,K)について、μ=1からインクリメントしてμ=Kまで各処理を行うとすればよい。
【0263】
多項式間距離算出兼一変数最近実多項式算出装置(2)の第二最小距離・多項式算出部(290)は、メモリ(20)から、Tと区分境界毎に得られた距離候補m1,…,mμ,…,mKを読み込み、Tとmin{m1,…,mμ,…,mK}のいずれか最小のものを新たなT(n≧2の場合の最小距離T)としてメモリ(20)の所定の格納領域に格納する〔ステップS52a〕。また、第二最小距離算出部(290)は、Tの書き換えが行われた場合は、このTを与えたm(x∈{1,…,K})がステップS72、S82、S84のいずれかで得られたものである場合には多項式Pを式(47i)で求め、このTを与えたm(x∈{1,…,K})がステップS74、S81、S83のいずれかで得られたものである場合には多項式Pを式(47k)で求め、この多項式Pでメモリ(20)に記憶されているPを書き換える。但し、Tの書き換えが行われなかった場合は、メモリ(20)に記憶されているPの書き換えを行わない。そして、制御部(299)がメモリ(20)に記憶されているTを液晶ディスプレイなどに表示する出力処理を行って多項式間距離算出処理を終了する。
【0264】
多項式間距離算出兼一変数最近実多項式算出装置(2)の区分境界点判定部(260)は、メモリ(20)から、ステップS51の処理で選択された区分境界に対応する実区間Iμを読み込み、実区間Iμが点であるか否かを判定する〔ステップS6〕。制御部(299)は、実区間Iμが点であると判定された場合、ステップS71の処理を実行するように制御を行い、実区間Iμが点ではないと判定された場合、ステップS81の処理を実行するように制御を行う。
【0265】
多項式間距離算出兼一変数最近実多項式算出装置(2)の第一距離候補探索部(270)は、メモリ(20)から、ステップS51の処理で選択された区分境界の有理式による表示(γμ、Iμ:但し、実区間Iμの内実は点δである。)、多項式f(x),e1(x),e2(x),…,en(x)を読み込み、メモリ(20)と協働して、点δが集合Iμ\Δμに属する場合はmμ=Φμ(δ)を式(51)の第二式で求め、点δが集合Δ~μに属する場合はmμ=Φμ(δ)を式(51)の第一式で求め、点δがいずれの集合にも属さない場合にはmμ=∞として、距離候補mμをメモリ(20)の所定の格納領域に格納する〔ステップS71〜S75〕。
【0266】
多項式間距離算出兼一変数最近実多項式算出装置(2)の第二距離候補探索部(280)は、メモリ(20)から、ステップS51の処理で選択された区分境界の有理式による表示(γμ、Iμ)、多項式f(x),e1(x),e2(x),…,en(x)を読み込み、メモリ(20)と協働して、式(55)〜式(58)でmμ,1,mμ,2,mμ,3,mμ,4を求めてから、mμ=min{mμ,1,mμ,2,mμ,3,mμ,4}を求め、距離候補mμをメモリ(20)の所定の格納領域に格納する〔ステップS81〜S85〕。
【0267】
制御部(299)は、ステップS72、S74、S75、S85の各処理の後、ステップS50の処理を実行するように制御を行う。
【0268】
第2実施形態では、最小距離と多項式f~を出力するものとしたが、多項式f~のみを出力するようにすれば、多項式間距離算出兼一変数最近実多項式算出装置(2)は一変数最近実多項式算出装置として動作することになる。
【0269】
本発明である多項式間距離算出装置、多項式間距離算出方法、一変数最近実多項式算出装置、一変数最近実多項式算出方法は上述の実施形態に限定されるものではなく、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。例えば、重みつきのl-ノルム maxj{wj|aj|} (0<wj)を用いる場合は、{e1(x),…,en(x)}の代わりに{e1(x)/w1,…,en(x)/wn}を用いればよい。また、上記実施形態において説明した処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されるとしてもよい。
【0270】
また、上記実施形態において説明した多項式間距離算出装置、一変数最近実多項式算出装置における処理機能をコンピュータによって実現する場合、多項式間距離算出装置、一変数最近実多項式算出装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記多項式間距離算出装置、一変数最近実多項式算出装置における処理機能がコンピュータ上で実現される。
【0271】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、DVD(Digital Versatile Disc)、DVD−RAM(Random Access Memory)、CD−ROM(Compact Disc Read Only Memory)、CD−R(Recordable)/RW(ReWritable)等を、光磁気記録媒体として、MO(Magneto-Optical disc)等を、半導体メモリとしてEEP−ROM(Electronically Erasable and Programmable-Read Only Memory)等を用いることができる。
【0272】
また、このプログラムの流通は、例えば、そのプログラムを記録したDVD、CD−ROM等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【0273】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるASP(Application Service Provider)型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの(コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等)を含むものとする。
【0274】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、多項式間距離算出装置、一変数最近実多項式算出装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【実施例】
【0275】
図1−1および図1−2に示したアルゴリズムに則った最小距離算出の具体的な実施例を説明する。
【0276】
f(x)=x+2とし、領域Dを単位円の周および内部からなる有界閉領域とし、境界Λは、Λ={1}とΛ=Λ\Λの和集合とする。ただし、Λ,Λは式(65)の通り表されているものとする。ただし、I={1},I=Rである(Rは実数全体の集合)。
【数103】

【0277】
このとき、領域Dに零点を持ち多項式fに一番近い多項式
f~(x)=f(x)+a~1e1(x)+a~2e2(x)+a~3e3(x) (a~1,a~2,a~3∈R)
を求める場合にアルゴリズム2の挙動を示す。ただし、e(x)=x,e(x)=x,e(x)=1とする。ここでは、上記設定からステップS50番台、ステップS6、ステップS70番台、ステップS80番台の処理を中心に説明する。
【0278】
・ステップS1
T=∞とおく。
【0279】
・ステップS50、S51、S6、S71〜75
まず、μ=1とする。f(1)=3であり、e(1)=e(1)=e(1)=1は一直線上(実軸上)にあり、しかも、e(1)≠0だから、1を零点とする最近多項式f~=−x+1が存在する。距離候補mは1である。
【0280】
・ステップS50、S51、S6、S81〜85
次にμ=2とする。このとき、式(66)が得られる。
【数104】

【0281】
よって、式(67)が得られる。
【数105】

【0282】
従って、
Δ=Δ~={0}, Z~=φ, Z={−1,1}
となるから、
Δ\Δ~=φ
であり、また、J=(−∞,0)∪(0,∞)から、
\Z=(−∞,−1)∪(−1,0)∪(0,1)∪(1,∞)
である。
【0283】
Δ~およびZにおいては、
Φ(0)=1, Φ(−1)=Φ(1)=1/2
が得られる。
【0284】
\Zにおいては、式(68)が得られる。
【数106】

【0285】
これらから以下を得る。
2,1=∞,m2,2=m2,4=1/2,m2,3=1
したがって、
=min{m2,1,m2,2,m2,3,m2,4}=1/2
【0286】
・ステップS52
2.m=1,m=1/2より、
min{m1,m2}=1/2
となる。ステップS1でT=∞であるから、最小距離は1/2である。
上記例の場合、最近多項式f~は±iに零点を持つ(3x+3)/2となる。
【産業上の利用可能性】
【0287】
本発明は、例えば、複素領域Dに零点を持たないように多項式の係数を設定したい場合に、係数設定に誤差を伴うことを前提として、誤差付きで設定される多項式が間違いなく複素領域Dに零点を持たないようにするときに、その誤差限界の確定などとして用いることができる。このような場合の一例として、ディジタル信号処理におけるディジタルフィルタ(例えば、IIR〔Infinite Impulse Response〕フィルタ)の設計などに有用である。
【図面の簡単な説明】
【0288】
【図1−1】第1実施形態の多項式間距離算出処理のフローチャート(其の壱)。
【図1−2】第1実施形態の多項式間距離算出処理のフローチャート(其の弐)。
【図2−1】第2実施形態の多項式間距離算出兼一変数最近実多項式算出処理のフローチャート(其の壱)。
【図2−2】第2実施形態の多項式間距離算出兼一変数最近実多項式算出処理のフローチャート(其の弐)。
【図3】多項式間距離算出装置(1)のハードウェア構成を例示した構成ブロック図。
【図4】多項式間距離算出処理の処理機能を示す機能ブロック図。
【図5】多項式間距離算出兼一変数最近実多項式算出処理の処理機能を示す機能ブロック図。
【図6−1】アルゴリズム1の挙動を説明するための具体例。(a)4つの関数f1,f2,f3,f4と実区間Iを入力とする。(b)2つの関数f1,f2と実区間Iを入力としたアルゴリズム1の結果。(c)2つの関数f3,f4と実区間Iを入力としたアルゴリズム1の結果。
【図6−2】アルゴリズム1の挙動を説明するための具体例。(d)2つの関数f1,f2と実区間Iを入力としたアルゴリズム1の結果と、2つの関数f3,f4と実区間Iを入力としたアルゴリズム1の結果とから得られるI1,j∩I2,k≠φ(空集合)となる区間の対を示す図。(e)区間I1,j∩I2,k≠φごとのアルゴリズム1の結果。(f)4つの関数f1,f2,f3,f4と実区間Iを入力されたアルゴリズム1の結果。
【符号の説明】
【0289】
1 多項式間距離算出装置
100 恒等式調査部
110 多項式数条件判定部
120 第一最小距離算出部
130 領域有界判定部
140 次数判定部
150 探索制御部
160 区分境界点判定部
170 第一距離候補探索部
180 第二距離候補探索部
190 第二最小距離算出部
2 多項式間距離算出兼一変数最近実多項式算出装置
200 恒等式調査部
210 多項式数条件判定部
220 第一最小距離・多項式算出部
230 領域有界判定部
240 次数判定部
250 探索制御部
260 区分境界点判定部
270 第一距離候補探索部
280 第二距離候補探索部
290 第二最小距離・多項式算出部

【特許請求の範囲】
【請求項1】
Rを実数全体の集合とし、f(x),e1(x),…,en(x)をそれぞれ予め与えられた一変数実多項式とし、二つの一変数実多項式の距離をl-ノルムで定義し、一変数実多項式f(x)が複素数全体の集合内の閉な領域Dに零点を持たないとして、
一変数実多項式の集合
【数1】

に属する一変数実多項式であって、上記領域Dに零点を持ち、かつ、上記一変数実多項式f(x)に最も近い一変数実多項式f~(x)について、上記一変数実多項式f(x)と上記一変数実多項式f~(x)との距離を算出する多項式間距離算出装置であり、
上記f(x),e1(x),…,en(x)と、上記領域Dの境界Λを構成する有限個の区分境界Λ12,…,ΛKとを記憶する記憶手段と、
上記境界Λ上の点αに対して、上記集合Fに属しこの点αを零点とする一変数実多項式のうち上記一変数実多項式f(x)に最も近い一変数実多項式g(x)と上記一変数実多項式f(x)との距離を与える関数Φ(α)を用いて、上記区分境界Λ12,…,ΛKごとに前記関数Φ(α)の最小値を求める距離候補探索手段と、
上記距離候補探索手段によって得られた値のうち最小のものを求める最小距離算出手段と
を備えた多項式間距離算出装置。
【請求項2】
複素数の実部と虚部をそれぞれRe,Imで表すとして、複素数u,vに対する行列式
【数2】

を定義し、iを虚数単位とし、
[1]1≦j<k≦nなる全てのj,kに対してA(ej(α),ek(α))=0が成立し、かつ、A(ej(α),f(α))=0がj=1,…,nに対して成立ち、かつ、e(α)≠0となるjが存在する場合に、上記関数Φ(α)は、
【数3】

であり、
[2]或るj,k(1≦j<k≦n)に対してA(ej(α),ek(α))≠0が成立する場合に、上記関数Φ(α)は、
【数4】

(但し、分母が0となるものは除く。)である
ことを特徴とする請求項1に記載の多項式間距離算出装置。
【請求項3】
上記距離候補探索手段は、
各上記区分境界Λμ(但しμ=1,2,…,K)が点であるか否かを判定する区分境界点判定手段を含み、
区分境界Λμが点であると判定されなかった場合に、
上記[1]の場合を、少なくとも一つのjについてA(ej(α),if(α))=0が成立する場合S1とそれ以外の場合S2に分け、
上記[2]の場合を、少なくとも一つのjについてA(ej(α),f(α))=0または1≦j<k≦nなるj,kに対してA(ej(α),ek(α))=0が成立する場合S3とそれ以外の場合S4に分け、
当該区分境界Λμでの上記関数Φ(α)の最小値を、各上記場合S1〜S4の上記関数Φ(α)の各最小値のうち最小のものとする
ことを特徴とする請求項2に記載の多項式間距離算出装置。
【請求項4】
各上記区分境界Λμ(但しμ=1,2,…,K)が、実数上の集合Iμに対する有理式で表される単射γμ(s) (但しs∈Iμ)で与えられるとし、
集合Δμ
【数5】

とし、
集合Δ~μ⊂Δμ
【数6】

とし、
集合Z~μ⊂Δ~μ
【数7】

とし、
集合Zμ⊂Δμ
【数8】

とし、
区分境界Λμに対応する上記関数Φ(α)を
【数9】

で表すとし、
上記距離候補探索手段は、
上記区分境界点判定手段によって点であると判定された区分境界Λμについて、実数上の集合Iμ(={δ})が集合Iμ\Δμに属する場合に、当該区分境界Λμでの上記関数Φμ(s)の最小値を、
【数10】

で求め、実数上の集合Iμ(={δ})が上記集合Δ~μに属する場合に、当該区分境界Λμでの上記関数Φμ(s)の最小値を、
【数11】

で求める第一距離候補探索手段と、
上記区分境界点判定手段によって点であると判定されなかった区分境界Λμについて、上記S1の場合に上記集合Z~μの有限個の元σについて、mμ,1
【数12】

で求め、上記S2の場合に有限個の区間の和集合で表される集合Δ~μ\Z~μに属する元σについて,mμ,3
【数13】

で求め、上記S3の場合に上記集合Zμの有限個の元σについて、mμ,2
【数14】

で求め、上記S4の場合に有限個の区間の和集合で表される集合(Iμ\Δμ)\Zμに属する元σについて,mμ,4
【数15】

で求め、当該区分境界Λμでの上記関数Φμ(s)の最小値をmin{mμ,1,mμ,2,mμ,3,mμ,4}で求める第二距離候補探索手段とを含む
ことを特徴とする請求項3に記載の多項式間距離算出装置。
【請求項5】
上記領域Dが有界であるか否かを判定する領域有界判定手段と、
上記領域Dが有界でない場合に、上記集合Fの次数が一定であるか否かを判定する次数判定手段とを備える
ことを特徴とする請求項1から請求項4のいずれかに記載の多項式間距離算出装置。
【請求項6】
多項式
【数16】

が恒等的に0となる実数a1,a2,…,anが存在するか否かを判定し、存在する場合には上記一変数実多項式f(x)と恒等的に0の多項式との距離を求める恒等式調査手段を備え、
上記最小距離算出手段に代えて、
上記距離候補探索手段によって得られた値および上記恒等式調査手段によって得られた距離のうち最小のものを求める第二最小距離算出手段を備える
ことを特徴とする請求項1から請求項5のいずれかに記載の多項式間距離算出装置。
【請求項7】
Rを実数全体の集合とし、f(x),e1(x),…,en(x)をそれぞれ予め与えられた一変数実多項式とし、二つの一変数実多項式の距離をl-ノルムで定義し、一変数実多項式f(x)が複素数全体の集合内の閉な領域Dに零点を持たないとして、
一変数実多項式の集合
【数17】

に属する一変数実多項式であって、上記領域Dに零点を持ち、かつ、上記一変数実多項式f(x)に最も近い一変数実多項式f~(x)について、上記一変数実多項式f(x)と上記一変数実多項式f~(x)との距離を算出する多項式間距離算出方法であり、
記憶手段には、上記f(x),e1(x),…,en(x)と、上記領域Dの境界Λを構成する有限個の区分境界Λ12,…,ΛKとが記憶されており、
距離候補探索手段が、上記境界Λ上の点αに対して、上記集合Fに属しこの点αを零点とする一変数実多項式のうち上記一変数実多項式f(x)に最も近い一変数実多項式g(x)と上記一変数実多項式f(x)との距離を与える関数Φ(α)を用いて、上記区分境界Λ12,…,ΛKごとに前記関数Φ(α)の最小値を求める距離候補探索ステップと、
最小距離算出手段が、上記距離候補探索ステップにおいて得られた値のうち最小のものを求める最小距離算出ステップと
を有する多項式間距離算出方法。
【請求項8】
Rを実数全体の集合とし、f(x),e1(x),…,en(x)をそれぞれ予め与えられた一変数実多項式とし、二つの一変数実多項式の距離をl-ノルムで定義し、一変数実多項式f(x)が複素数全体の集合内の閉な領域Dに零点を持たないとして、
一変数実多項式の集合
【数18】

に属する一変数実多項式であって、上記領域Dに零点を持ち、かつ、上記一変数実多項式f(x)に最も近い一変数実多項式f~(x)を算出する一変数最近実多項式算出装置であり、
上記f(x),e1(x),…,en(x)と、上記領域Dの境界Λを構成する有限個の区分境界Λ12,…,ΛKとを記憶する記憶手段と、
上記境界Λ上の点αに対して、上記集合Fに属しこの点αを零点とする一変数実多項式のうち上記一変数実多項式f(x)に最も近い一変数実多項式g(x)と上記一変数実多項式f(x)との距離を与える関数Φ(α)を用いて、上記区分境界Λ12,…,ΛKごとに前記関数Φ(α)の最小値を求める距離候補探索手段と、
上記距離候補探索手段によって得られた値のうち最小のものに対応する多項式を求める多項式算出手段と
を備えた一変数最近実多項式算出装置。
【請求項9】
Rを実数全体の集合とし、f(x),e1(x),…,en(x)をそれぞれ予め与えられた一変数実多項式とし、二つの一変数実多項式の距離をl-ノルムで定義し、一変数実多項式f(x)が複素数全体の集合内の閉な領域Dに零点を持たないとして、
一変数実多項式の集合
【数19】

に属する一変数実多項式であって、上記領域Dに零点を持ち、かつ、上記一変数実多項式f(x)に最も近い一変数実多項式f~(x)を算出する一変数最近実多項式算出方法であり、
記憶手段には、上記f(x),e1(x),…,en(x)と、上記領域Dの境界Λを構成する有限個の区分境界Λ12,…,ΛKとが記憶されており、
距離候補探索手段が、上記境界Λ上の点αに対して、上記集合Fに属しこの点αを零点とする一変数実多項式のうち上記一変数実多項式f(x)に最も近い一変数実多項式g(x)と上記一変数実多項式f(x)との距離を与える関数Φ(α)を用いて、上記区分境界Λ12,…,ΛKごとに前記関数Φ(α)の最小値を求める距離候補探索ステップと、
多項式算出手段が、上記距離候補探索ステップにおいて得られた値のうち最小のものに対応する多項式を求める多項式算出ステップと
を有する一変数最近実多項式算出方法。
【請求項10】
コンピュータに請求項7に記載された多項式間距離算出方法の各処理を実行させるためのプログラム、または/および、コンピュータに請求項9に記載された一変数最近実多項式算出方法の各処理を実行させるためのプログラムを記録した、コンピュータに読み取り可能な記録媒体。

【図1−1】
image rotate

【図1−2】
image rotate

【図2−1】
image rotate

【図2−2】
image rotate

【図3】
image rotate

【図4】
image rotate

【図5】
image rotate

【図6−1】
image rotate

【図6−2】
image rotate


【公開番号】特開2009−271888(P2009−271888A)
【公開日】平成21年11月19日(2009.11.19)
【国際特許分類】
【出願番号】特願2008−124355(P2008−124355)
【出願日】平成20年5月12日(2008.5.12)
【出願人】(000004226)日本電信電話株式会社 (13,992)
【Fターム(参考)】