一変数実区間多項式の実重複擬零点の位置判定装置、位置判定方法、位置判定プログラムおよび記録媒体
【課題】一変数実区間多項式Fに対して、その実重複擬零点全体の集合MZR(F)を決定する。
【解決手段】実数の閉区間で表される区間数を係数とする一変数実区間多項式〔実区間多項式F〕に対して、集合Z決定手段が、実区間多項式Fのエッジ多項式について、その実重複擬零点〔エッジ多項式に属する多項式の実重複零点〕全体の集合Zを求める。そして、集合MZR(F)決定手段が、実数全体の集合に対する集合Zの補集合における全ての実区間Jごとに、各実区間J上で任意に1点γを選択して、この点γを実重複零点とする多項式が実区間多項式Fに存在するか否かを判定し、これが存在する場合の点γを含む実区間Jと集合Zとの和集合をとったものを、実区間多項式Fの実重複擬零点〔実区間多項式Fに属する多項式の実重複零点〕全体の集合MZR(F)とする。
【解決手段】実数の閉区間で表される区間数を係数とする一変数実区間多項式〔実区間多項式F〕に対して、集合Z決定手段が、実区間多項式Fのエッジ多項式について、その実重複擬零点〔エッジ多項式に属する多項式の実重複零点〕全体の集合Zを求める。そして、集合MZR(F)決定手段が、実数全体の集合に対する集合Zの補集合における全ての実区間Jごとに、各実区間J上で任意に1点γを選択して、この点γを実重複零点とする多項式が実区間多項式Fに存在するか否かを判定し、これが存在する場合の点γを含む実区間Jと集合Zとの和集合をとったものを、実区間多項式Fの実重複擬零点〔実区間多項式Fに属する多項式の実重複零点〕全体の集合MZR(F)とする。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は、実区間多項式の零点の位置判定装置、位置判定方法、位置判定プログラムおよび記録媒体に関する。より詳細には、一変数実区間多項式の実重複擬零点の位置判定装置、位置判定方法、位置判定プログラムおよび記録媒体に関する。
【背景技術】
【0002】
係数に誤差のある一変数実多項式は、例えばディジタル信号処理やシステム制御の分野に現れ、その零点の位置はディジタルフィルタの周波数特性やシステムの性能に密接に関係する。
【0003】
そして、多項式の実の重複零点〔重複度が2以上の零点〕は、どんなに小さな係数の変化に対しても、複数の複素零点あるいは実の近接零点となる。従って、実の零点が存在するか否か、あるいは、いくつ存在するのかを知る必要があるとき、実の重複零点の存在が重大な関心事となる。
【0004】
式(1)で表される実係数一変数多項式が与えられたとする。
【数1】
【0005】
各実係数ai(ここではi=0,1,・・・,dである。)は、観測や測定によって得られたもので真の値とは異なるかもしれない、と仮定する。但し、誤差の範囲は分かっており、各実係数aiの真の値は実の閉区間[ui,hi]内にあるものとする。『各実係数aiがこの誤差範囲内にある多項式で、実の重複零点を有するものがあるか否か判定せよ』という問題を考える。
【0006】
これに関連して、非特許文献1には、式(1)で表される多項式の各係数aiが複素数のとき、重複零点を有する複素数係数の多項式g(x)〔式(2)参照。〕の中で、式(3)で表される量、つまりf(x)−g(x)のl2−ノルム〔文字「l」はアルファベットの「エル」の小文字である。〕を最小とするものを求める問題を、適当なある二次形式の最小化の問題に帰着して解決する方法が示されている。
【数2】
【0007】
この方法は、下記の点で、後に詳述する本発明と似て非なるものである。
・係数およびその誤差を複素数の範囲とする点
・重複零点を実とは限らない点
・誤差の範囲指定が係数ごとではなく、多項式のl2−ノルムとしている点
・重複零点の有無についての判定問題は扱えるが、重複零点となる数の集合の決定、即ち、係数誤差範囲内で多項式を動かしたときに、その重複零点となる数すべての集合を決定する問題は扱えない点
【0008】
一変数多項式は、各係数も変数と見なした上で元の変数に値を代入すると、それぞれの係数に対応する変数について一次式と見ることができる。この性質を利用すれば、『多項式の各係数を誤差範囲内で動かして、与えられた実数αを零点として持つようにできるか』という問題は、誤差範囲が実数のとき、誤差範囲の端点を正確に計算する区間演算で判定可能である。具体的には、各係数aiがui≦ai≦hiなる範囲にあるとして、式(4)を、端点を正確に計算する区間演算を用いて求め、その結果の区間に0が入るか否かを調べればよい。
【数3】
【0009】
誤差範囲が複素数のときには、非特許文献2に記述のあるとおり、適当なある不等式の成立、不成立の判定に帰着できる。
f(x)がx=αにおいて重複零点を持つ必要十分条件は、f(x)=f′(x)=0がx=αなる解を持つこと、すなわち、連立方程式(5)がx=αなる解を持つことである。なお、ここで記号「′」はxに関する微分を表す。
【数4】
【0010】
連立方程式(5)を書き改めると、連立方程式(6)がx=αなる解を持つことである。
【数5】
【0011】
『xに値を代入して係数をある範囲で動かしたとき、連立方程式(6)が成り立つようにできるか』という問題に関連して、非特許文献2〔非特許文献2のCorollary 9参照。〕は、連立方程式(7)にxi=αiを代入したとき、bijを、uij≦bij≦hijの範囲で動かして連立方程式(7)を成立させることができるか否かの判定が、適当なある不等式が成立するか否の判定に帰着できることを述べている。
【数6】
【0012】
そうすると、非特許文献2が提示する解法を連立方程式(6)のaiに誤差がある場合にも適用できるように思える。しかし、連立方程式(7)では、行列(bij)の全ての成分が独立に動かせるものと仮定しての結果である。連立方程式(6)においては、ai,・・・,adが2ヵ所ずつに現れるので、非特許文献2のCorollary 9を用いた解法は適用できない。
【非特許文献1】L. Zhi and W. Wu, "Nearest Singular Polynomials", Journal of Symbolic Computation, Vol.26, No.6, pp.667-675, 1998.
【非特許文献2】H. J. Stetter, "The nearest polynomial with a given zero,and similar problems", ACM SIGSAM Bulletin, Vol.33, No.4, pp.2-4, 1999.
【発明の開示】
【発明が解決しようとする課題】
【0013】
さて、『一変数多項式の各係数および係数毎の誤差をそれぞれ実数で与えるとして、各係数が係数毎の誤差範囲内に在る多項式が或る与えられた実の区間で重複零点を有するか否かを判定せよ、さらに、係数誤差範囲内で多項式を動かしたとき、その重複零点となる実数すべての集合を具体的に表示せよ』・・・(☆)という問題を考える。
【0014】
非特許文献1に提示される解法は、l2−ノルムで誤差をはかり、二次形式の最小化を用いるものであるから、係数毎に誤差範囲を指定した問題(☆)を扱うことができない〔なお、上記4点の差異も参照のこと。〕。また、非特許文献2に提示される解法は、1点を与えたときに、それを「零点」とするような多項式が係数誤差範囲内に存在するか否かの判定は可能だが、「重複零点」とする場合の問題(☆)には適用できない。また、いずれも、重複零点となりうる点の集合の決定はできない。
【0015】
そこで、本発明は、問題(☆)に解答を与えることを目的とする。
この目的を、より端的に説明する。
これに先立ち、この明細書における記号および用語の説明をする。
但し、記号については、説明の便宜等からそれまでの意味とは異なる意味で同じ記号を用いる場合があることに留意しておくこと。
【0016】
係数が確定していない(例えば、係数に誤差がある場合などである。)多項式を表す手法として、区間多項式がある。区間多項式F(x)とは、数の集合である区間数Ai(1≦i≦d、但しiは整数。)を各項の係数として式(8)のように表記されるものである。つまり、区間多項式F(x)は、係数がai∈Aiである多項式f(x)〔式(9)参照。〕全体の集合を表す。なお、この明細書における区間多項式は、特に断りのない限り、一変数区間多項式であるとする。
【数7】
【0017】
ここでは、区間数を実数の範囲で考える。この場合、区間数Aiとして閉区間[ui,hi]を用いる。このような区間多項式であることを明確にするため、以下では、実区間多項式と云うことにする〔正確には、「一変数実区間多項式」と云うべきであるが、「実区間多項式」と略記する。〕。
また、ei(x)は、実数である係数が確定した多項式であり、恒等的に0ではないとする。
なお、多項式について、例えば実区間多項式F(x)を実区間多項式Fなどのように変数を略記して表すことがある。
【0018】
実区間多項式Fに対し、実区間多項式Fに属する多項式fが存在して、多項式fがa∈R〔記号∈は、或る要素が集合に「属する」ことを意味する。Rは、実数全体の集合を表す。〕で重複零点を有するとき、実区間多項式Fは実重複擬零点aを有する、と云うことにする。実区間多項式Fに対し、その実重複擬零点全体の集合をMZR(F)と表記する。
【0019】
このとき、問題(☆)を次のように表現できる。
《問題1》 与えられた実区間多項式Fおよび実の区間Iに対し、実区間I内に実区間多項式Fの実重複擬零点が存在するか否かを判定せよ。
《問題2》 与えられた実区間多項式Fに対し、MZR(F)を決定せよ。
【0020】
つまり、本発明は、与えられた実区間多項式Fおよび実の区間Iに対し、実区間I内に実区間多項式Fの実重複擬零点が存在するか否かを判定し、あるいは、与えられた実区間多項式Fに対してMZR(F)を決定する一変数実区間多項式の実重複擬零点の位置判定装置、位置判定方法、位置判定プログラムおよび記録媒体を提供することを目的とする。
【課題を解決するための手段】
【0021】
上記課題を解決するために、本発明は、実数の閉区間で表される区間数を係数とする一変数実区間多項式〔実区間多項式F〕および実区間Iについて、選択点多項式判定手段が、実区間I上で任意に1点〔選択点〕を選択し、この選択点を実重複零点とする多項式が実区間多項式Fに存在するか否かを判定して、エッジ多項式判定手段が、実区間I上に実重複零点を有し且つエッジ多項式〔実区間多項式Fの1つの係数を除いた係数が区間数の端点となっている実区間多項式の集合〕に属する多項式が存在するか否かを判定する。
このような構成は数学的な保証に基づくものであり、この詳細は後述する。
【0022】
また、上記課題を解決するために、本発明は、実数の閉区間で表される区間数を係数とする一変数実区間多項式〔実区間多項式F〕に対して、集合Z決定手段が、実区間多項式Fのエッジ多項式について、その実重複擬零点〔エッジ多項式に属する多項式の実重複零点〕全体の集合Zを求める。そして、集合MZR(F)決定手段が、実数全体の集合に対する集合Zの補集合における全ての実区間Jごとに、各実区間J上で任意に1点γを選択して、この点γを実重複零点とする多項式が実区間多項式Fに存在するか否かを判定し、これが存在する場合の点γを含む実区間Jと集合Zとの和集合をとったものを、実区間多項式Fの実重複擬零点〔実区間多項式Fに属する多項式の実重複零点〕全体の集合MZR(F)とする。
このような構成は数学的な保証に基づくものであり、この詳細は後述する。
【発明の効果】
【0023】
本発明によれば、数学的保証の下に、実区間Iの1点について、これを実重複零点とする多項式が実区間多項式Fに存在するか否かを判定し、実区間I上に実重複零点を有し且つエッジ多項式に属する多項式が存在するか否かを判定することで、有限ステップで完全にかつ効率良く、実区間I内に実区間多項式Fの実重複擬零点が存在するか否かを判定することができる。
【0024】
本発明によれば、数学的保証の下に、まず、実区間多項式Fのエッジ多項式について、その実重複擬零点全体の集合Zを求めてから、実数全体の集合に対する集合Zの補集合における全ての実区間Jごとに、各実区間J上で任意に1点γを選択して、この点γを実重複零点とする多項式が実区間多項式Fに存在するか否かを判定し、これが存在する場合の点γを含む実区間Jと集合Zとの和集合をとったものを、実区間多項式Fの実重複擬零点全体の集合MZR(F)とすることで、有限ステップで完全にかつ効率良く、実区間多項式Fの実重複擬零点全体の集合MZR(F)を決定することができる。
【発明を実施するための最良の形態】
【0025】
[理論]
これから、本発明における実区間多項式の実重複擬零点の位置判定の理論およびアルゴリズムを、図面を参照しながら説明する。なお、予め説明しておくと、本発明における「実区間多項式の実重複擬零点の位置判定」とは、実区間多項式の実重複擬零点の位置(座標)を特定することではなく、所定の領域に実区間多項式の実重複擬零点が存在するか否かに係わる判定および実区間多項式に対してMZR(F)を決定することである。換言すれば、実区間多項式の実重複擬零点が所定の領域に存在するか否か、および、MZR(F)の決定の意味において、実区間多項式の実重複擬零点の位置判定をすることになる。
【0026】
式(8)および式(9)において、区間数の端点ui、hiおよび多項式ei(x)の係数は、理論上は実数としてよいが、コンピュータなどによる演算の上では四則演算および等号判定を有限ステップのアルゴリズムで実行できることが必要かつ十分であり、そのために例えば実代数的数(整数係数一変数代数方程式の根となる実数)とし、具体例として有理数であるとする。
以下では、説明の便宜から、ei(x)を有理数係数多項式の場合を例示して説明する。また、実代数的数として有理数を例にとって説明する。つまり、端点ui、hiを有理数としている。
【0027】
まず、《問題1》について。
問題1は、既述のとおり『与えられた実区間多項式Fおよび実の区間Iに対し、実区間I内に実区間多項式Fの実重複擬零点が存在するか否かを判定せよ』である。
【0028】
この問題1に対する解答の要旨は、次のとおりである。
<1>実区間I内で任意に選択した1点cについて、この点cが実区間多項式Fの実重複擬零点か否かを判定する。つまり、c∈Iを実重複零点とする多項式が実区間多項式Fに存在するか否かを判定する。点cが実重複擬零点ならば、問題1に対して「存在する」を解答として与える。点cが実重複擬零点でなければ、次の処理<2>を行う。
<2>実区間多項式Fのエッジ多項式に属する多項式であって、実区間I内に実重複零点を有する多項式が存在するか否かを判定する。このような多項式が存在すれば、問題1に対して「存在する」を解答として与える。このような多項式が存在しなければ、問題1に対して「存在しない」を解答として与える。
【0029】
ここでエッジ多項式とは、「実区間多項式Fの1つの係数を除いた係数が区間数の端点となっている実区間多項式の集合」である。より詳細には、実区間多項式Fに対し、そのエッジ多項式とは、ある一つの番号j(1≦j≦d、但しjは整数。)を除いては、係数aiがuiもしくはhi(但し、i≠jである。)に等しい実区間多項式の集合のことであり、式(10)で表される。
【数8】
【0030】
ここで、留意しなければならないのは、定義あるいは式(10)から明らかなとおり、エッジ多項式は実区間多項式Fの部分集合である。例えばj番目の係数を除いて係数が区間数の端点に固定されているエッジ多項式と云うとき、このエッジ多項式には最多2d−1個のものが考えられる。なぜなら、j番目の係数以外の各係数がそれぞれの区間数で端点を取る組み合わせが考えられ、式(10)の整数jが1≦j≦dであるとき、この組み合わせは最多2d−1個だからである。つまり、式(10)の第2項は最多2d−1本の多項式が考えられるので、「j番目の係数を除いて係数が区間数の端点に固定されているエッジ多項式」は最多2d−1個のエッジ多項式を云うことになる。そうすると、実区間多項式F(x)では、最多d×2d−1個のエッジ多項式が存在する。ここで、エッジ多項式に属する多項式〔単に多項式と言えば、係数が確定している多項式を云う。〕を、「要素エッジ多項式」と云うことにする。
数学的表現を用いるならば、実区間多項式F、エッジ多項式E、要素エッジ多項式gとしたとき、これらはE⊂F、g∈Eなる関係にある。
【0031】
以下、問題1に対する解答の要旨が上記のとおりに与えられる理由を説明する。
まず、実区間I上で任意に選択した1点cについて、この点cを実重複零点とする多項式が実区間多項式F(x)に存在するならば(図1のステップS100参照。)、「実区間Iに実重複零点を有する多項式f(x)∈F(x)が存在する」ことが判明したことになり、「実区間I内に実区間多項式Fの実重複擬零点が存在する」ことが言えたことと同じである(図1のステップS103参照。)。つまり、問題1に解答を与えたことになる。
なお、『実区間I上で任意に選択した1点cについて、この点cを実重複零点とする多項式が実区間多項式F(x)に存在するか否か』の判定方法は後述の《凸包判定》で説明する。
【0032】
次に、『実区間I上で任意に選択された1点cについて、この点cを実重複零点とする多項式が実区間多項式F(x)に存在しない場合、もし、実区間I上に実重複零点を有する多項式が存在するならば、その中で、エッジ多項式に属するものが存在する』ことが言える。
この証明を以下に説明する。
【0033】
今、「実区間I上の点d(但し、点cを除く。)を実重複零点とする多項式f(x)∈F(x)が存在するとして、多項式f(x)がエッジ多項式に属さない」と仮定する。このとき、区間数の端点に固定されていない係数(2つ以上あるとする。)を2つ選択し、これをpおよびqとする。
ここで記号αを実区間I上の点を表すパラメータとして、f(α)およびf′(α)を式(11)の如く表記することにする。なお、上記では記号αを実重複零点としたが、ここでの説明では異なる定義であることに留意すること。
【数9】
【0034】
点αにおいてf(α)=f′(α)=0になることは、pおよびqの2変数連立一次方程式(12)が成立することである。
【数10】
【0035】
点dは実重複零点であるから、α=dでは、所定の範囲(区間数内)に収まっている連立方程式(12)の解p、qが存在する(このp、qは、点dを実重複零点とする多項式f(x)の係数pおよびqに対応する。)。
ここでα=dにおいて行列式(13)が0とすると、連立方程式の解が不定であるならば、pおよびqを解としたまま、少なくともその1つを区間数の端点となるまで動かすことができる。また、連立方程式の解が存在しないのであるならば、パラメータαが行列式(13)を0にする値に近付くとき、p、qのうち少なくとも一方は∞あるいは−∞に発散するから、その前に区間数の端点に達することとなる。これは、上記仮定:「実区間I上の点dを実重複零点とする多項式f(x)∈F(x)が存在するとして、多項式f(x)がエッジ多項式に属さない」と矛盾する。なお記号≡は「定義」を表す。
【数11】
【0036】
従って、行列式(13)はα=dにおいて0ではないとする。点αを実区間I上において点dから動かしていくと、点αが点cに到達する前に、次のいずれかが起こる。もし、いずれも起こらずに点cに到達したとすると、「点cを実重複零点とする多項式が実区間多項式F(x)に存在しない」とする前提と矛盾する。なお、α0は点dおよび点cの間にある実区間I上の点である。
(i)pが区間数の端点に到達する。
(ii)qが区間数の端点に到達する。
(iii)行列式(13)が、α=α0において0になる。
【0037】
(i)および(ii)の場合は、多項式f(x)の係数のうち区間数の端点とならないものの個数が多項式f(x)の場合よりも1つ小さい多項式であって、実区間I上に実重複零点を有する多項式g(x)∈F(x)が存在することを示している。
【0038】
(iii)の場合は、後述の《補足説明》で説明するように、行列式(13)が0となる点において、連立方程式(12)は不定となるので、pおよびqを解としたまま、少なくともその1つを区間数の端点となるまで動かすことができる。つまり、多項式f(x)の係数のうち区間数の端点とならないものの個数が多項式f(x)の場合よりも1つ小さい多項式であって、実区間I上に実重複零点を有する多項式g(x)∈F(x)が存在することを示している。
【0039】
結局、以上から、点cを実重複零点とする多項式が実区間多項式F(x)に存在しない場合、実区間I上に実重複零点を有する多項式が存在するとしたとき、実区間I上の点dを実重複零点とするエッジ多項式に属さない多項式f(x)∈F(x)に対して、多項式f(x)の係数のうち区間数の端点とならないものの個数が多項式f(x)の場合よりも1つ小さい多項式であって、実区間I上に実重複零点を有する多項式g(x)∈F(x)が存在することが言えた。以上のような操作を(区間数の端点に固定されていない係数が3つ以上ある場合に)必要に応じて繰り返せば、エッジ多項式に属する多項式g(x)∈F(x)で、実区間I上に実重複零点を有するものが存在することが言える。
【0040】
従って、点cを実重複零点とする多項式が実区間多項式F(x)に存在しない場合には、『エッジ多項式に属する多項式g(x)∈F(x)であって、その実重複零点が実区間I上にあるものが存在するか否か』の判定をすればよい(図1のステップS101参照。)。このような多項式が存在すれば、問題1に対する解答は「存在する」となる(図1のステップS103参照。)。このような多項式が存在しなければ、問題1に対する解答は「存在しない」となる(図1のステップS102参照。)。
なお、『エッジ多項式に属する多項式g(x)∈F(x)であって、その実重複零点が実区間I上にあるものが存在するか否か』の判定方法は後述の《エッジ多項式判定》で説明する。
【0041】
《補足説明》
補足説明では、行列式(13)が0となる点において、連立方程式(12)が不定となることを説明する。
ここで、np(α)、nq(α)を式(14)によって定義する。ここでのp、qは、上記と同様、2つ選択された区間数の端点に固定されていない係数を意味する。
【数12】
【0042】
連立方程式(12)の解p、qは、αの関数として、式(15)によって表される。
【数13】
【0043】
αがα0に近づくとき、D(α)は0に収束するから、np(α)、nq(α)も0に収束する。収束することは、全ての係数がαの連続関数として表すことができることから保証されており、もし収束値が0以外ならば、αがα0に到達する前まで連立方程式(12)の解が有界であることに矛盾する。np(α)、nq(α)はαについて連続であるから、結局、式(16)が成り立つ。
【数14】
【0044】
さらに、aj(α0)=bj(α0)=0ならば〔但し、ここでのjは、j=1,2とする。〕、cj(α0)=0が成り立つ。なぜなら、ある正数Mがあって、αが実区間I上において点α0に近づくとき、常に不等式|p(α)|≦M、|q(α)|≦Mが成立するので、三角不等式から式(17)が成立する。
【数15】
【0045】
αが実区間I上において点α0に近づくとき、(|aj(α)|+|bj(α)|)Mは0に収束するから、cj(α)も0に収束する。そして、cj(α)は連続であることからcj(α0)=0が成り立つ。
【0046】
この準備の下、次の3通りに分けて証明する。
(i)a1(α0)=a2(α0)=0の場合について。もしb1(α0)≠0ならば、行列式(13)から、連立方程式(12)の第2式は第1式のb2(α0)/b1(α0)倍となる。ここでb1(α0)≠0から、連立方程式(12)が不定であることがわかる。もしb1(α0)=0ならば、上記の準備からc1(α0)=0となり、連立方程式(12)は第2式のみとなる。このとき、b2(α0)=0ならば、やはり上記準備からc2(α0)=0となり、第2式もなくなる。b2(α0)≠0ならば第2式は残るが、解は不定である。
【0047】
(ii)a1(α0)およびa2(α0)のうち、一方が0であり、他方が0ではない場合について。この場合、a1(α0)=0、a2(α0)≠0の場合について示せば十分である。上記のD(α0)=0から、b1(α0)=0となる。従って、上記準備からc1(α0)=0となる。つまり、連立方程式(12)は第2式のみに退化し、a2(α0)≠0から解は不定であることがわかる。
【0048】
(iii)a1(α0)およびa2(α0)が共に0ではない場合について。この場合、上記のD(α0)=0および行列式(13)から、連立方程式(12)において、第2式は第1式のa2(α0)/a1(α0)倍となる。従って、a1(α0)≠0から解は不定であることがわかる。
以上で《補足説明》は終わりである。
【0049】
《凸包判定》
実区間I上の任意の1点cを選択して、この点cを実重複零点とする多項式が実区間多項式F(x)に存在するか否かを調べる方法について説明する。以下では、アルゴリズムを簡単かつ効率良くするため、エッジ多項式に限らない範囲で調べるとする。
【0050】
ここでは、上記点cを説明の便宜からαに記号の置き換えをする。
式(8)で与えられる実区間多項式の区間数Ajを閉区間[uj,hj]で表したことに留意すると、閉区間[uj,hj]は、パラメータtj(0≦tj≦1なる実数)を用いて{(hj−uj)tj+uj}と表記することができる。パラメータtjは、閉区間の両端点uj、hjの内分比を表す。このとき、式(8)の実区間多項式F(x)は、上記区間数{(hj−uj)tj+uj}を各項の係数として式(18)のように表現され、各j(1≦j≦d、但しjは整数。)に対して係数がaj∈{(hj−uj)tj+uj}である多項式f(x)〔式(19)参照〕の全体の集合を表す。
【数16】
【0051】
このとき、「点αを実重複零点とする多項式が実区間多項式F(x)に存在するか否か」は、「連立方程式(20)を満足するtjの組み合わせが存在するか否か」と同値である。また、連立方程式(20)を書き改めると、連立方程式(21)と表せる。
【数17】
【0052】
つまり、連立方程式(21)を満足するtjの組み合わせが存在するならば、それは、この点αを実重複零点とする多項式が実区間多項式F(x)に存在することを意味する。ここで留意しなければならないのは、tjの組み合わせを特定することではなく、「連立方程式(21)を満足するtjの組み合わせが存在するか否か」である。ここで説明の便宜から、(ej(α) e′j(α))TをBjと表記する〔但し、Tは転置を表す。〕。そうすると、Bjは、デカルト直交座標系において、原点を始点、(x,y)=(ej(α),e′j(α))を終点とする位置ベクトルとみることができる。このような視点から、以下の説明でx座標、y座標と云えば、デカルト直交座標系〔以下、「平面」という。〕において位置ベクトルの終点を指すものする。
【0053】
そうすると、式(21)左辺について(hj−uj)tjBjを、「Bjを(hj−uj)倍した位置ベクトル(hj−uj)Bjを、tjによってスカラー倍したものである」と見れば、0≦tj≦1によって式(21)の左辺が取り得る平面上の範囲に、式(21)の右辺の点が存在するか否かを調べればよい。つまり、凸包に或る1点が存在するか否かの判定に持ち込むことを考えればよい。そこで、このような凸包を用いた判定を効率良く行うために、前処理を行う。
【0054】
まず、式(21)の左辺の各項(j=1,…,d)を順番に見ていき、各項について次のような判定と書き換えを行う。まず、(hj−uj)Bjのx座標〔つまり、(hj−uj)ej(α)である。〕が負であるかを判定する。負である場合には、(hj−uj)tjBjを(hj−uj)(1−tj)Bjに書き換える。次に、(hj−uj)Bjのx座標が負でない場合は、(hj−uj)Bjのx座標が0かつy座標〔つまり、(hj−uj)e′j(α)である。〕が負であるか否かを判定する。x座標が0かつy座標が負である場合には、(hj−uj)tjBjを(hj−uj)(1−tj)Bjに書き換える。
なお、この操作は式(20)において、(hj−uj)Bjのx座標が負である場合に{(hj−uj)tj+uj}Bjを{(hj−uj)(1−tj)+uj}Bjと書き換え、(hj−uj)Bjのx座標が0かつy座標が負である場合に{(hj−uj)tj+uj}Bjを{(hj−uj)(1−tj)+uj}Bjと書き換えることと同じである。
【0055】
以上の操作は、例えば、x座標が負である位置ベクトル(hj−uj)Bjをtjスカラー倍(0≦tj≦1)することは、平面原点対象に移動した位置ベクトル(hj−uj)×(−1)×Bjをkjスカラー倍(−1≦kj≦0)することと同じであるから、tjの範囲が0≦tj≦1であることに留意してkj=tj−1とおくと、(hj−uj)×(−1)×kj×Bjは、(hj−uj)×(1−tj)×Bjとなることに基づく。このような操作を行うことで、式(21)の左辺の点(hj−uj)Bjは、見かけ上、全て平面の右半平面(x座標が0以上の領域全体、但し、x座標が0かつy座標が負の部分は除く。)に集められるとともに、平面のy軸の負の部分には点が乗らないものとなる。換言すれば、この操作の結果得られた点集合は、平面原点を頂点とする凸包を平面の右半平面で構成する(但し、平面のy軸の負の部分に凸包の頂点はない。)。
【0056】
なお、このような操作は、後述の凸包を求めるための便宜としての前処理であるから、上記に限定されるものではない。例えば、(hj−uj)Bjのx座標が正であるかを判定し、正である場合には、(hj−uj)tjBjを(hj−uj)(1−tj)Bjに書き換え、(hj−uj)Bjのx座標が正でない場合は、(hj−uj)Bjのx座標が0かつy座標が負であるか否かを判定する。そして、x座標が0かつy座標が負である場合には、(hj−uj)tjBjを(hj−uj)(1−tj)Bjに書き換える(つまり、平面原点を頂点とする凸包を平面左側で構成する。)、といった操作などに適宜に変更できる。
【0057】
以上の操作を行ない、その結果に対して適切な式変形および記号の置き換え(ajおよびb)をすると、当該結果は式(22)のように表すことができる。但し、式(22)において、ajおよびbは上記Bjと同様にaj=(aj1 aj2)T、b=(b1 b2)Tと表される。つまり、ajおよびbは平面上の原点を始点とする位置ベクトルとみることができる。
【数18】
【0058】
結局、式(22)を満たすようなtj(0≦tj≦1)の組み合わせが存在するか否かの判定となるが、これは、εj=0あるいはεj=1とした場合に、式(23)の全体、即ち平面上で高々2d+1個の点の凸包に式(22)の右辺bの終点座標が入るか否かの判定と同じである〔下記参考文献1参照。〕。なお、式(22)を得る際の上記操作から、式(23)の全体のなす凸包は、平面の右半平面(但し、x座標が0かつy座標が負の部分は除く。)に存在することがわかる。従って、式(22)の右辺bのx座標が負の場合、あるいは、bのx座標が0かつy座標が負の場合、凸包を下記説明のように具体的に構成しなくてもbが式(23)の全体のなす凸包に入らないことがわかることに留意するべきである。
(参考文献1) 関川浩、白柳潔著、「区間多項式の零点の所在について」、社団法人電子情報通信学会、電子情報通信学会論文誌A、Vol.J89-A、No.3、pp.199-216
【数19】
【0059】
そこで、まず、式(23)で表される点の全体の凸包を求める。これは、効率的に求めることができる。
具体的にはまず、平面のy軸の負の部分を除く平面の右半平面の領域〔−π/2<arg≦π/2、argは角度を表す。〕において、aj≠0を傾き〔arg(aj)=aj2/aj1、但し、aj1=0ならばaj1/aj2は∞とみなす。〕でソート(sort)する。つまり、位置ベクトルaj≠0がx軸となす角度arg(aj)を、−π/2<arg≦π/2で、小さい方から大きい方へと昇順に並び替える。但し、同じ傾きのものがあるときには、それらを全部足したものに置き換えたものを1つとしてソートする。例えば、ajおよびakの傾きが同じときには、aj,akの代わりに、aj+akを対象としてソートする。なぜなら、傾きが同じ位置ベクトルajおよび位置ベクトルakの各終点は平面上において凸包の頂点となりえないからである(凸包の頂点の可能性があるのは、同じ傾きのものを全てベクトル加算した点である。)。このソートの結果を位置ベクトルp1,・・・,pmとする。なお、mはd+1より小さいことがあることに留意すること。
【0060】
このとき、求める平面上の凸包の頂点は、平面原点(0と表記する。)から始めて反時計回りに、0,p1,p1+p2,…,p1+…+pn,p2+p3+…pm,p3+…+pm,…,pm−1+pm,pmの全部で2m個となる。
つまり、式(23)の全体のなす凸包の平面における頂点座標は、反時計回りに式(24)で与えられる位置ベクトルvi(0≦i≦2m−1)の終点として表される〔複素平面の場合について参考文献1参照。〕。
【数20】
【0061】
この位置ベクトルvi(0≦i≦2m−1)の終点〔以下、「頂点vi」という。〕で構成される凸包に式(22)の右辺bの終点が入るか否かを判定する。この判定は、例えば次のようにして行うことができる。まず、arg(b)に対して、arg(vk)≦arg(b)<arg(vk+1)なる凸包の頂点vk、vk+1をとる。このとき、式(22)の右辺bの終点が凸包に入るか否かは、頂点vk、vk+1を結んだ線分に対して原点側(線分上を含む。)あるいは原点とは反対側の何れの側にbの終点が存在するかと同値である。そこで、位置ベクトルz1=(z1x,z1y)、z2=(z2x,z2y)に対してd(z1,z2)なる演算を式(25)の如く定義する。このとき、d(b−vk,vk+1−b)が正ならばbの終点が凸包に含まれず、d(b−vk,vk+1−b)が0以下ならばbの終点が凸包に含まれる。
【数21】
【0062】
bの終点が凸包に入る場合には、点cを実重複零点とする多項式が実区間多項式F(x)に存在すると判定でき、bの終点が凸包に入らない場合には、点cを実重複零点とする多項式が実区間多項式F(x)に存在しないと判定できる。
【0063】
以上のアルゴリズムに基づく凸包判定の処理フローを一例として図2に示す。
【0064】
まず、実区間I上の任意の1点αを選択する(ステップS400)。
【0065】
次に、選択した点αをx=αとして実区間多項式F(x)および実区間多項式F(x)を1階微分したものに代入する(ステップS401)。
【0066】
パラメータjを1に設定する(ステップS402)。
【0067】
このパラメータjに対応する(hj−uj)ej(α)が負であるかを判定する(ステップS403)。
【0068】
(hj−uj)ej(α)負である場合には、{(hj−uj)tj+uj}Bjを{(hj−uj)(1−tj)+uj}Bjと書き換える(ステップS405)。
【0069】
もし(hj−uj)ej(α)が負でない場合は、(hj−uj)ej(α)が0かつ(hj−uj)e′j(α)が負であるか否かを判定する(ステップS404)。
【0070】
(hj−uj)ej(α)が0かつ(hj−uj)e′j(α)が負である場合には、{(hj−uj)tj+uj}Bjを{(hj−uj)(1−tj)+uj}Bjと書き換える(ステップS405)。
【0071】
そしてパラメータjがdと等しいか否かを判定する(ステップS406)。
【0072】
j≠dであれば、jに1加えたものを新たなjとして(ステップS407)、ステップS403〜S406の処理を行う。j=dであれば、ステップS403〜S406の処理で得られた実区間多項式を式(22)の如く式変形する(ステップS408)。
【0073】
次に、ステップS408の処理で得られた式(22)の右辺で表される位置ベクトルbのx座標が負であるか否かを判定する(ステップS408x)。
【0074】
位置ベクトルbのx座標が負であれば、位置ベクトルbがステップS408の処理で得られた式(22)の左辺で表される点全体の凸包に入ることはないので、任意に選択された点αを実重複零点とする多項式が実区間多項式F(x)に存在しないといえる(ステップS411)。
【0075】
位置ベクトルbのx座標が負でなければ、ステップS408yの処理を行う。即ち、ステップS408の処理で得られた式(22)の右辺で表される位置ベクトルbのx座標が0かつy座標が負であるか否かを判定する(ステップS408y)。
【0076】
位置ベクトルbのx座標が0かつy座標が負であれば、位置ベクトルbがステップS408の処理で得られた式(22)の左辺で表される点全体の凸包に入ることはないので、任意に選択された点αを実重複零点とする多項式が実区間多項式F(x)に存在しないといえる(ステップS411)。
【0077】
位置ベクトルbのx座標が0かつy座標が負でなければ、ステップS409の処理を行う。即ち、ステップS408の処理で得られた式(22)の左辺で表される点全体の凸包を上記のアルゴリズムに従って構成する(ステップS409)。
【0078】
次に、ステップS408の処理で得られた式(22)の右辺で表される点が、ステップS409で構成された凸包に入るか否かを判定する(ステップS410)。
【0079】
凸包に入れば、任意に選択された点αを実重複零点とする多項式が実区間多項式F(x)に存在するといえる(ステップS412)。凸包に入らなければ、任意に選択された点αを実重複零点とする多項式が実区間多項式F(x)に存在しないといえる(ステップS411)。
以上で《凸包判定》の説明は終わりである。
【0080】
《エッジ多項式判定》
エッジ多項式に属する多項式g(x)∈F(x)であって、その実重複零点が実区間I上にあるものが存在するか否かを調べる方法について説明する。
ここでは説明の便宜から、j番目の係数を除いて係数が区間数の端点に固定されているエッジ多項式EをAjej(x)+r(x)と表現する〔式(10)参照。但し、既述のとおり、j番目の係数を除いて係数が区間数の端点に固定されているエッジ多項式Eにおいてr(x)には最多2d−1本の多項式が考えられることに留意すること。〕。さらに表現を簡略なものとするため、j番目の係数を除いて係数が区間数の端点に固定されていないことを前提としてインデックスjを明記しないことにする。但し、区間数A=[u,h](=Aj)である。
【0081】
エッジ多項式Eに属する要素エッジ多項式g(x)で実区間Iに実重複零点を有するものが存在するか否かという問題を考える。この問題は、連立方程式(26)がu≦t≦h、x∈Iなる解を持つか否かという問題と同じである。
【数22】
【0082】
連立方程式(26)を、xをパラメータとし、tを変数とする方程式と見る。また、P(x)=e(x)r′(x)−e′(x)r(x)、Q(x)/R(x)=−r(x)/e(x)とおく。ただし、Q(x),R(x)∈Q[x]かつgcd(Q,R)=1とする。なお、Q[x]は、有理係数1変数多項式全体の集合〔変数はx〕を表し、gcd(・)は最大公約多項式を表す。
【0083】
このとき、以下のことが云える。
〈1〉
x=c∈Iでe(c)=e′(c)=0の場合に、連立方程式(26)が解を持つ必要十分条件は、r(c)=r′(c)=0である。連立方程式(26)が解を持つとき、任意の実数tが解となる。換言すると、w(x)=gcd(e(x),r(x),e′(x),r′(x))としたとき、w(x)が実区間Iに零点ρを有するならば、必ずu≦t≦hが成立する。つまり、w(x)が実区間Iに零点ρを有するならば、「要素エッジ多項式g(x)∈Eであって、その実重複零点が実区間I上にあるものが存在する」と云える。w(x)が実区間Iに零点を有するか否かはSturmの定理に基づくアルゴリズムなどで判定可能である。Sturmの定理については、参考文献2を参照のこと。
(参考文献2) 高木貞治著、「代数学講義(改訂新版)」、共立出版、1965.
【0084】
〈2〉
tが区間数の端点uまたはhに固定されている場合。ηをuまたはhとすると、t=ηとした連立方程式(26)の解xがx∈Iであるかを判定すればよい。換言すると、上記〈1〉においてw(x)が実区間Iに零点を有しないとき、式(27)で表される多項式wη(x)が実区間Iに零点ξηを有するか否かをSturmの定理に基づくアルゴリズムなどで判定すればよい。なお、式(27)においてw(x)を除数としているのは、上記〈1〉を経たことに拠る計算効率化のためである。多項式wη(x)が実区間Iに零点を有するならば、「要素エッジ多項式g(x)∈Eであって、その実重複零点が実区間I上にあるものが存在する」と云える。
【数23】
【0085】
〈3〉
x=c∈Iでe(c)≠0かつe′(c)≠0の場合に、連立方程式(26)が解を持つ必要十分条件は、P(c)=0である。連立方程式(26)が解を持つとき、解はちょうど一つでt=Q(c)/R(c)である。
つまるところ、上記〈2〉において多項式wu(x)および多項式wh(x)が実区間Iに零点を有しないとき、式(28)で表されるP1(x)が実区間Iに零点ζを有するか否かをSturmの定理に基づくアルゴリズムなどで判定し、さらにu<Q(ζ)/R(ζ)<hの成立を判定すればよい。Q(ζ)/R(ζ)については上記〈2〉を経ることでQ(ζ)/R(ζ)=ηとなることがないから、u<Q(ζ)/R(ζ)<hの成立を判定すればよく、これは十分に精度を上げた誤差解析付の近似計算、例えば、区間計算で判定可能である。
なお、式(28)において多項式wu(x)、多項式wh(x)、gcd(e(x),e′(x))を除数としているのは、上記〈1〉および〈2〉を経たことに拠る計算効率化のためである。P1(x)が実区間Iに零点ζを有し、かつ、u<Q(ζ)/R(ζ)<hが成立するならば、「要素エッジ多項式g(x)∈Eであって、その実重複零点が実区間I上にあるものが存在する」と云える。P1(x)が実区間Iに零点ζを有さず、あるいは、u<Q(ζ)/R(ζ)<hが成立しないならば、「少なくとも、いま与えられているエッジ多項式について、その実重複擬零点が実区間I上に存在しない」ことが云える。
【数24】
【0086】
なお、P(x)が恒等的に0になる場合、連立方程式(26)は一本の方程式に退化するから、R(β)≠0を満たす1点β∈Iを任意に選択し、この1点βについてu<Q(β)/R(β)<hを判定すればよい。u<Q(β)/R(β)<hが成立するならば、「要素エッジ多項式g(x)∈Eであって、その実重複零点が実区間I上にあるものが存在する」と云える。u<Q(β)/R(β)<hが成立しないならば、「少なくとも、いま与えられているエッジ多項式について、その実重複擬零点が実区間I上に存在しない」と云える。
【0087】
以上の処理〈1〉〜〈3〉を順次に行っていくことで、要素エッジ多項式g(x)∈Eであって、その実重複零点が実区間I上にあるものが存在するか否かが判定できる。このエッジ多項式判定は、エッジ多項式が有限個であるから有限ステップで終了できる。なお、「要素エッジ多項式g(x)∈Eであって、その実重複零点が実区間I上にあるものが存在する」ことが云えた時点でエッジ多項式判定を終了できる。
【0088】
ここで、留意しなければならないのは、既述のとおりg(x)∈E⊂Fであるところ、実区間多項式Fには最多d×2d−1個のエッジ多項式が存在するということである。
【0089】
従ってより詳細には、(a)パラメータjを定める、(b)j番目の係数を除いて係数が区間数の端点に固定されている、最多2d−1本のエッジ多項式について上記処理〈1〉〜〈3〉を行う、(c)1≦j≦dについて(a)および(b)の処理を実施する、というアルゴリズムになる(但し、「要素エッジ多項式g(x)であって、その実重複零点が実区間I上にあるものが存在する」ことが言えた時点でエッジ多項式判定を終了できる。)。
【0090】
以上のアルゴリズムに基づくエッジ多項式判定の処理フローを一例として図3に示す。
【0091】
まず、パラメータjを1に設定する(ステップS500)。
【0092】
次に、j番目の係数を除いて係数が区間数の端点に固定されている、最大で2d−1個のエッジ多項式Eにおいて、未調査(ここで未調査とは、後述のステップS502〜S514の処理が行われていないことを云う。)のエッジ多項式を1個選択する(ステップS501)。この選択されたエッジ多項式が上記Ajej(x)+r(x)において多項式r(x)を1本に固定したものに対応する。また、区間数Aj=[u,h]とする。
【0093】
次に、w(x)=gcd(e(x),r(x),e′(x),r′(x))を求める(ステップS502)。
【0094】
次に、w(x)が実区間Iに零点ρを有するか否かを判定する(ステップS503)。
【0095】
w(x)が実区間Iに零点ρを有する場合、「要素エッジ多項式g(x)∈E⊂F(x)であって、その実重複零点が実区間I上にあるものが存在する」ことが云える(ステップS517)。
【0096】
w(x)が実区間Iに零点ρを有さない場合、式(29)の多項式wu(x)を求める(ステップS504)。
【数25】
【0097】
次に、多項式wu(x)が実区間Iに零点ξuを有するか否かを判定する(ステップS505)。
【0098】
多項式wu(x)が実区間Iに零点ξuを有する場合、「要素エッジ多項式g(x)∈E⊂F(x)であって、その実重複零点が実区間I上にあるものが存在する」ことが云える(ステップS517)。
【0099】
多項式wu(x)が実区間Iに零点ξuを有さない場合、式(30)の多項式wh(x)を求める(ステップS506)。
【数26】
【0100】
次に、多項式wh(x)が実区間Iに零点ξhを有するか否かを判定する(ステップS507)。
【0101】
多項式wh(x)が実区間Iに零点ξhを有する場合、「要素エッジ多項式g(x)∈E⊂F(x)であって、その実重複零点が実区間I上にあるものが存在する」ことが云える(ステップS517)。
【0102】
多項式wh(x)が実区間Iに零点ξhを有さない場合、P(x)=e(x)r′(x)−e′(x)r(x)、Q(x)/R(x)=−r(x)/e(x)を求める。ただし、Q(x),R(x)∈Q[x]かつgcd(Q,R)=1とする(ステップS508)。
【0103】
次に、常等的にP(x)=0が成立するか否かを判定する(ステップS509)。
【0104】
常等的にP(x)=0が成立する場合、R(β)≠0を満たす1点である参照点β∈Iを任意に選択する(ステップS512)。
【0105】
続いて、選択された参照点β∈Iについて、u<Q(β)/R(β)<hが成立するか否かを判定する(ステップS513)。
【0106】
u<Q(β)/R(β)<hが成立する場合、「要素エッジ多項式g(x)∈E⊂F(x)であって、その実重複零点が実区間I上にあるものが存在する」ことが云える(ステップS517)。
【0107】
u<Q(β)/R(β)<hが成立しない場合、「いま与えられているエッジ多項式について、その実重複擬零点が実区間I上に存在しない」ことが云えるので、他のエッジ多項式について処理を進めるべくステップS514への処理に移行する。
【0108】
ステップS509の処理において、常等的にP(x)=0ではない場合、式(31)で表されるP1(x)を求める(ステップS510)。
【数27】
【0109】
続いて、P1(x)が実区間Iに零点ζを有し、かつ、u<Q(ζ)/R(ζ)<hが成立するか否かを判定する(ステップS511)。なお、図面において記号∧は論理積を表す。
【0110】
P1(x)が実区間Iに零点ζを有し、かつ、u<Q(ζ)/R(ζ)<hが成立するならば、「要素エッジ多項式g(x)∈E⊂F(x)であって、その実重複零点が実区間I上にあるものが存在する」と云える(ステップS517)。
【0111】
P1(x)が実区間Iに零点ζを有さず、あるいは、実区間Iに零点ζを有してもu<Q(ζ)/R(ζ)<hが成立しないならば、「いま与えられているエッジ多項式について、その実重複擬零点が実区間I上に存在しない」ことが云えるので、他のエッジ多項式について処理を進めるべくステップS514への処理に移行する。
【0112】
ステップS511またはステップS513の判定が偽であれば、未調査のエッジ多項式があるか否かを判定する(ステップS514)。
【0113】
未調査のエッジ多項式が存在すれば、ステップS501〜S513の処理を行う。未調査のエッジ多項式が存在しなければ、j=dであるか否かを判定する(ステップS515)。
【0114】
j≠dであれば、jに1加えたものを新たなjとして(ステップS516)、ステップS501〜S515の処理を行う。j=dであれば、「要素エッジ多項式g(x)∈F(x)であって、その実重複零点が実区間I上にあるものが存在しない」と云える(ステップS518)。
以上で《エッジ多項式判定》の説明は終わりである。
【0115】
次に、《問題2》について。
問題2は、既述のとおり『与えられた実区間多項式Fに対し、その実重複擬零点全体の集合MZR(F)を決定せよ』である。
【0116】
この問題2に対する解答およびアルゴリズムを説明する。
まず、エッジ多項式判定における処理〈1〉〜〈3〉で説明したことから、下記のことが云える。
【0117】
(ア)
点cがエッジ多項式Eに属する任意の要素エッジ多項式の実重複零点となる必要十分条件は、多項式w(c)=0となることである。但し、w(x)=gcd(ej(x),r(x),e′j(x),r′(x))である。
【0118】
(イ)
点cがエッジ多項式Eに属する要素エッジ多項式ujej(x)+r(x)に対してのみ実重複零点となる必要十分条件は、多項式wu(c)=0となることである〔式(29)参照。〕。
【0119】
(ウ)
点cがエッジ多項式Eに属する要素エッジ多項式hjej(x)+r(x)に対してのみ実重複零点となる必要十分条件は、多項式wh(c)=0となることである〔式(30)参照。〕。
【0120】
(エ)
点cがちょうど一本の要素エッジ多項式φej(x)+r(x)∈E〔但し、φは開区間(uj,hj)に属する。〕の実重複零点となる必要十分条件は、P1(c)=0かつQ(c)/R(c)∈(uj,hj)が成り立つことである〔式(31)参照。〕。
なお、P(x)=ej(x)r′(x)−e′j(x)r(x)が恒等的に0ではないのならば、エッジ多項式の実重複擬零点は有限個の点となることに留意すること〔∵P(c)=0となることが必要条件なので。〕。
【0121】
次に、問題1の解答およびアルゴリズムの説明で明らかになったとおり、『実区間多項式Fおよび実区間Iについて、実区間Iに属する点αで、実区間多項式Fの実重複擬零点ではない点が存在するとき、実区間多項式Fが実区間I内に実重複擬零点を有することと、実区間多項式Fのエッジ多項式の中に、実区間I内に実重複擬零点を有するものが存在することとは同値である』・・・(定理1)ことが云える。
【0122】
また、『実区間多項式Fのj番目の係数を除いて係数が区間数の端点に固定されているエッジ多項式E=Ajej(x)+r(x)〔式(10)参照。但し、Aj=[uj,hj]〕について、その実重複擬零点全体の集合MZR(E)は有限個の閉区間の和集合となる。もし、P(x)=ej(x)r′(x)−e′j(x)r(x)≠0ならば、MZR(E)は有限集合である』・・・(定理2)ことが云える。
【0123】
《定理2の証明》
§1.
まず、最後の「もし、ej(x)r′(x)−e′j(x)r(x)≠0ならば、MZR(E)は有限集合である。」については、次のとおりである。
上記(エ)で、尚書きで説明したとおり、P(x)=ej(x)r′(x)−e′j(x)r(x)が恒等的に0ではないならば、実数cがMZR(E)に入る必要条件はP(c)=0となることであるところ、P(c)=0を満たすcは有限個しかない。従って、MZR(E)は有限集合である。
【0124】
§2.
次に、「MZR(E)は有限個の閉区間の和集合となる。」について。「P(x)が恒等的に0」ではない場合は、1.で証明済みなので、以下、「P(x)は恒等的に0」と仮定する。
上記(ア)〜(ウ)を経ることで、多項式w(x)、多項式wu(x)、多項式wu(x)の全実零点を求め、この集合をSZと表記する。なお、既述のとおりej(x)を恒等的に0ではないとしたことから、多項式w(x)は恒等的に0にならないが、多項式wu(x)、多項式wu(x)は恒等的に0になる場合がありえる〔例えば、r(x)=0かつu=0の場合などである。〕。この場合は実数全体の集合RがMZR(E)となるから、ここではこのような場合を除くとする。多項式w(x)、多項式wu(x)、多項式wu(x)の全実零点は、Sturmの定理に基づくアルゴリズムなどによって求めることができる。
集合SZにおいては、エッジ多項式Eは実重複擬零点を有し、それ以外の点で、もしエッジ多項式Eが実重複擬零点を有する場合、式(26)のtはただ1つに決まり、しかもujともhjとも異なる。
以下、集合SZの要素をα1<α2<・・・<αmと表記する。
開区間(αi,αi+1)の点は、すべてMZR(E)に属する、あるいは、1つもMZR(E)に属さない、のいずれかになる。換言すれば、開区間(αi,αi+1)はMZR(E)の部分集合となる、あるいは、MZR(E)とはまったく共通部分を持たない、のいずれかである。
この事実を、叙述して示す。なお、以下では添え字jを略する。
【0125】
§2.1
『e(c)=e′(c)=0かつc∈(αi,αi+1)ならばR(c)=0』を云う。
もし、e(c)=e′(c)=0となる点cが開区間(αi,αi+1)内にあれば、上記(ア)を経たことから、このような点は集合SZに含まれているから、r(c)≠0またはr′(c)≠0である。
r(c)≠0の場合、r(x)はx−cでは割り切れず、一方、e(c)=0からe(x)はx−cで割り切れるから、R(x)はx−cで割り切れる。つまり、R(c)=0である。
r(c)=0かつr′(c)≠0の場合、r(x)はx−cで割り切れるが、(x−c)2では割り切れない。一方、e(c)=e′(c)=0であるから、e(x)は(x−c)2で割り切れるから、R(x)はx−cで割り切れる。つまり、この場合もR(c)=0である。
【0126】
§2.2
『開区間(αi,αi+1)内の1点cに対してu<Q(c)/R(c)<hならば、開区間(αi,αi+1)内の任意の1点dに対してもu<Q(d)/R(d)<hが成立する』を云う。
開区間(αi,αi+1)内の1点cに対してR(c)≠0ならば、§2.1で説明したことから、(e(c),e′(c))≠(0,0)である。このcに対して、u<Q(c)/R(c)<hならば、任意の点d∈(αi,αi+1)に対して、(e(d),e′(d))≠(0,0)である。しかも、R(d)≠0かつu<Q(d)/R(d)<hとなる。
このことを背理法で示す。
まず、R(x)の零点が開区間(αi,αi+1)内にある場合、そのうち、cに一番近いものをdとする。R(c)≠0より「R(x)は恒等的に0」ではないから、区間(c,d)〔あるいは、区間(d,c)〕において、Q(x)/R(x)はxの連続関数である。しかも、Q(x)およびR(x)は互いに素に取ってあるから、Q(d)≠0である。よって、xがdに近づくとき、Q(x)/R(x)の絶対値はいくらでも大きくなる。従って、中間値の定理から、Q(x)/R(x)がuまたはhに等しくなる点が区間(c,d)〔あるいは、区間(d,c)〕に、即ち、開区間(αi,αi+1)の中に存在することになる。これは、開区間(αi,αi+1)の取り方に矛盾する〔このような点は、すでに上記(ア)〜(ウ)の処理で集合SZに取り込み済みで、開区間(αi,αi+1)の中には存在しない。)。
次に、R(x)の零点が開区間(αi,αi+1)内に無い場合は、Q(x)/R(x)がu以下あるいはh以上となる点dが開区間(αi,αi+1)内に存在したと仮定する。まず、開区間(αi,αi+1)の取り方から、Q(x)/R(x)がuあるいはhとなる点は開区間(αi,αi+1)内には存在しないから、Q(d)/R(d)がuより小さいかあるいはhよりも大きいかのどちらかである。よって、区間(c,d)〔あるいは、区間(d,c)〕に中間値の定理を適用すれば、Q(x)/R(x)がuまたはhに等しくなる点が区間(c,d)〔あるいは、区間(d,c)〕に、即ち、開区間(αi,αi+1)の中に存在することになり、開区間(αi,αi+1)の取り方に矛盾する。
【0127】
§2.3
『開区間(αi,αi+1)内の1点cに対してQ(c)/R(c)<uあるいはh<Q(c)/R(c)ならば、開区間(αi,αi+1)内にはu≦Q(d)/R(d)≦hとなる点は存在しない』を云う。
u≦Q(d)/R(d)≦hとなる点dが開区間(αi,αi+1)内に存在したと仮定する。もし、開区間(αi,αi+1)内にR(x)の零点が存在しないならば、§2.2と同様な議論で、Q(x)/R(x)がuまたはhに等しくなる点は、開区間(αi,αi+1)内には存在しないから、Q(d)/R(d)がuより小さいかあるいはhよりも大きいかのどちらかである。区間(c,d)〔あるいは、区間(d,c)〕に中間値の定理を適用すれば、Q(x)/R(x)がuまたはhに等しくなる点が区間(c,d)〔あるいは、区間(d,c)〕に、即ち、開区間(αi,αi+1)の中に存在することになり、開区間(αi,αi+1)の取り方に矛盾する。
もし、開区間(αi,αi+1)内にR(x)の零点が存在したならば、そのうちdに一番近いものd′を取れば、§2.2と同じ議論によって、やはりQ(x)/R(x)がuまたはhに等しくなる点が区間(c,d)〔あるいは、区間(d,c)〕に、即ち、開区間(αi,αi+1)の中に存在することになり、開区間(αi,αi+1)の取り方に矛盾する。
【0128】
§2.4
以上から、開区間(αi,αi+1)はMZR(E)の部分集合となる、あるいは、MZR(E)とはまったく共通部分を持たない、のいずれかが示せた。
なお、開区間(αi,αi+1)で任意に選択された1点βについて、u<Q(β)/R(β)<hの成立を調べることで、上記いずれが成立しているかを判定できる。
以上で《定理2の証明》は終わりである。
【0129】
さて、定理1および定理2から、次のことが云える。
即ち、『実区間多項式Fと、実区間Jに対し、実区間多項式Fの全てのエッジ多項式は実区間J内に実重複擬零点を有さないと仮定する。このとき、実区間Jの閉包の全ての点が実区間多項式Fの実重複擬零点であるか、あるいは、実区間Jのどの点も実区間多項式Fの実重複擬零点ではないか、のどちらかが成り立つ。』・・・(定理3)ことが云える。
【0130】
《定理3の証明》
実区間Jに属する2点α、βについて,αは実区間多項式Fの実重複擬零点だが、βは実重複擬零点でないと仮定する。すると、定理1から、実区間多項式Fのエッジ多項式Eの中に、MZR(E)∩Jは空集合ではないものが存在する。これは、「実区間多項式Fの全てのエッジ多項式は実区間J内に実重複擬零点を持たない」という仮定に矛盾する。つまり、(1)実区間JはMZR(F)の部分集合である、(2)実区間JとMZR(F)の共通部分は空集合である、のいずれかとなる、(2)の場合および(1)で実区間Jが閉区間のときにはこれで証明できたことになる。
従って、(1)で実区間Jが閉区間ではないとき、つまり、a<bであって、J=(a,b)、[a,b)、(a,b]の場合を考える。どれでも証明は同じなので、端点aが実区間Jに含まれない場合を示す。このとき、K={a}∪J、つまり、J=(a,b)のときK=[a,b)、J=(a,b]のときK=[a,b]とする。定理1をKに対して適用する。もし端点aが実区間多項式Fの実重複擬零点ではないとすると、実区間多項式Fのエッジ多項式Eであって、Kに実重複擬零点を持つものが存在することになる。ところが、端点aは実区間多項式Fの実重複擬零点ではないので、当然、エッジ多項式の実重複擬零点でもない。よって、実区間Jに実重複擬零点を持つものが存在することになる。これは上記仮定に矛盾する。
以上で《定理3の証明》は終わりである。
【0131】
そうすると、問題2に対する大まかな解答は、次のようになる。
まず、実区間多項式Fの全てのエッジ多項式について、その実重複擬零点全体の集合Zを求める〔集合Z決定処理〕(図4のステップS200参照。)。集合Zは、有限個の閉区間の和集合MZR(E)の和集合をとったものとして求めることができる。即ちZ=∪MZR(E)〔エッジ多項式Eは、実区間多項式Fの全てのエッジ多項式を渡る。〕である〔記号∪は和集合を表す。〕。
次いで、集合Zの補集合〔但し、全体集合は実数全体の集合Rとする。〕の各実区間について〔集合Zの補集合は、有限個の開区間の和集合となるから、各開区間をJとする。〕、実区間J上の任意の1点γを選択し、この点γを実重複零点とする多項式が実区間多項式Fに存在するか否かを判定する〔この判定は既述の凸包判定を用いて可能である。〕。これが存在する場合には、点γを含む実区間Jと集合Zとの和集合をとったものを新たな集合Zに置き換える〔MZR(F)決定処理〕(図4のステップS201参照。)。なお、集合Zが実数全体の集合Rの場合には、集合Rが集合MZR(F)となる。
この結果、得られた集合ZがMZR(F)である。
【0132】
《集合Z決定処理》
ここでは、以上の定理等に基づく集合Z=∪MZR(E)を求めるの処理フローを一例として図5および図6に示す。なお、図3および図3に係わる説明も参照のこと。
なお、集合Zの初期値および集合MZR(E)の各初期値は空集合とする。
【0133】
まず、パラメータjを1に設定する(ステップS600)。
【0134】
次に、j番目の係数を除いて係数が区間数の端点に固定されている、最大で2d−1個のエッジ多項式Eにおいて、未調査(ここで未調査とは、後述のステップS602〜S631の処理が行われていないことを云う。)のエッジ多項式を1個選択する(ステップS601)。この選択されたエッジ多項式が上記Ajej(x)+r(x)において多項式r(x)を1本に固定したものに対応する。また、区間数Aj=[uj,hj]とする。
【0135】
次に、多項式w(x)=gcd(ej(x),rj(x),e′j(x),r′j(x))を求める(ステップS602)。
【0136】
次に、w(x)の実零点全体の集合SZを求める(ステップS603)。
【0137】
続いて、式(32)の多項式wu(x)を求める(ステップS604)。
【数28】
【0138】
次に、常等的にwu(x)=0が成立するか否かを判定する(ステップS605)。
【0139】
常等的にwu(x)=0が成立する場合、集合Z=R(実数全体の集合)として集合Z決定処理を終了する(ステップS608)。
【0140】
常等的にwu(x)=0が成立しない場合、式(33)の多項式wh(x)を求める(ステップS606)。
【数29】
【0141】
次に、常等的にwh(x)=0が成立するか否かを判定する(ステップS607)。
【0142】
常等的にwh(x)=0が成立する場合、集合Z=R(実数全体の集合)として集合Z決定処理を終了する(ステップS608)。
【0143】
常等的にwh(x)=0が成立しない場合、多項式wu(x)および多項式wh(x)それぞれの全実零点の集合ZR(wu)および集合ZR(wh)を求める(ステップS609)。
【0144】
続いて、集合SZ、集合ZR(wu)および集合ZR(wh)の和集合をとり、この和集合を新たな集合SZとして置き換える。そして、この集合SZの要素をα1<α2<・・・<αmとする(ステップS610)。
【0145】
続いて、P(x)=ej(x)r′(x)−e′j(x)r(x)、Q(x)/R(x)=−r(x)/ej(x)を求める。ただし、Q(x),R(x)∈Q[x]かつgcd(Q,R)=1とする(ステップS611)。
【0146】
次に、常等的にP(x)=0が成立するか否かを判定する(ステップS612)。
【0147】
常等的にP(x)=0が成立する場合、参照点βiを、R(βi)≠0かつβ1<α1<β2<α2<…<αm<βm+1を満たすように選択する(ステップS618)。但し、パラメータi=1,2,・・・,m+1とする。m=0の場合は、参照点β1は任意に選択できる。
【0148】
続いて、i=1かつm=0かつuj<Q(βi)/R(βi)<hjの成立を判定する(ステップS619)。
【0149】
i=1かつm=0かつuj<Q(βi)/R(βi)<hjが成立するならば、集合Z=R(実数全体の集合)として集合Z決定処理を終了する(ステップS620)。
【0150】
i=1かつm=0かつuj<Q(βi)/R(βi)<hjが成立しない場合、i=1かつm≧1かつuj<Q(βi)/R(βi)<hjの成立を判定する(ステップS621)。
【0151】
i=1かつm≧1かつuj<Q(βi)/R(βi)<hjが成立する場合、集合SZおよび(−∞,α1]の和集合をとり、この和集合を新たな集合SZとして置き換えて(ステップS622)、続いてステップS623の処理を行う。
また、i=1かつm≧1かつuj<Q(βi)/R(βi)<hjが成立しない場合は、続いてステップS623の処理を行う。
【0152】
続いて、パラメータiを2に設定する(ステップS623)。
【0153】
次に、uj<Q(βi)/R(βi)<hjの成立を判定する(ステップS624)。
【0154】
uj<Q(βi)/R(βi)<hjが成立する場合、集合SZおよび閉区間[αi−1,αi]の和集合をとり、この和集合を新たな集合SZとして置き換えて(ステップS625)、続いてステップS626の処理を行う。uj<Q(βi)/R(βi)<hjが成立しない場合、ステップS627の処理を行う。
【0155】
ステップS625の処理に続いて、i=m+1の成立を判定する(ステップS626)。i=m+1が成立する場合、続いてステップS628の処理を行う。i=m+1が成立しない場合、続いてステップS627の処理を行う。
【0156】
ステップS624の処理でuj<Q(βi)/R(βi)<hjが成立しない場合、あるいは、ステップS626の処理でi=m+1が成立しない場合、iに1加えたものを新たなiとして(ステップS627)、ステップS624〜S626の処理を行う。
【0157】
ステップS626の処理でi=m+1が成立した場合、i=m+1かつuj<Q(βi)/R(βi)<hjの成立を判定する(ステップS628)。
【0158】
i=m+1かつuj<Q(βi)/R(βi)<hjが成立した場合、集合SZおよび閉区間[αm,∞)の和集合をとり、この和集合を新たな集合SZとして置き換えて(ステップS629)、続いてステップS630の処理を行う。i=m+1かつuj<Q(βi)/R(βi)<hjが成立しない場合、ステップS630の処理を行う。
【0159】
ステップS612の処理で、常等的にP(x)=0が成立しない場合、式(34)で表されるP1(x)を求め、このP1(x)の全実零点集合{ζ}を求める(ステップS613)。
【数30】
【0160】
続いて、集合{ζ}の中から、未選択(ここで未選択とは、後述のステップS615〜S617の処理が行われていないことを云う。)の零点を1つ選択する(ステップS614)。この選択された零点をζSと表記する。
【0161】
選択された零点ζSについて、uj<Q(ζS)/R(ζS)<hjの成立を判定する(ステップS615)。
【0162】
uj<Q(ζS)/R(ζS)<hjが成立する場合、集合SZおよび{ζS}との和集合をとり、この和集合を新たな集合SZとして置き換えて(ステップS616)、続いてステップS617の処理を行う。uj<Q(ζS)/R(ζS)<hjが成立しない場合、ステップS617の処理を行う。
【0163】
未選択の零点ζSが存在すれば、ステップS614〜S616の処理を行う。未選択の零点ζSが存在しなければ、ステップS630の処理を行う(ステップS617)。
【0164】
ステップS617、ステップS628、ステップS629の処理に続いて、この段階で得られている集合SZおよび集合MZR(E)との和集合をとり、この和集合を新たな集合MZR(E)に置き換える(ステップS630)。
【0165】
続いて、未調査のエッジ多項式があるか否かを判定する(ステップS631)。未調査のエッジ多項式が存在すれば、ステップS601〜S630の処理を行う。
【0166】
未調査のエッジ多項式が存在しなければ、集合Zおよび集合MZR(E)との和集合をとり、この和集合を新たな集合Zとして置き換える(ステップS632)。
【0167】
続いて、j=dであるか否かを判定する(ステップS633)。
【0168】
j≠dであれば、jに1加えたものを新たなjとして(ステップS634)、ステップS601〜S633の処理を行う。j=dであれば、集合Z決定処理を終了する。この段階で得られた集合Zが所望の集合である。
以上で《集合Z決定処理》の説明は終わりである。
【0169】
《MZR(F)決定処理》
続いて、以上のアルゴリズムに基づく集合MZR(F)を求めるの処理フローを一例として図7に示す。
なお、集合Zの初期値は集合Z決定処理で得られた集合であることに留意すること。
【0170】
まず、集合Zが実数全体の集合Rに等しいか否かを判定する(ステップS700)。
【0171】
集合Zが実数全体の集合Rに等しい場合、MZR(F)決定処理を終了する。集合MZR(F)は、この段階で得られた集合Z、つまり集合Rとなる。
【0172】
集合Zが実数全体の集合Rに等しくない場合、集合Zを式(35)のように表現する(ステップS701)。これは集合Z決定処理で得られた集合Zを区間ごとの和集合として書き表したものである。但し、(β0<)α1≦β1<α2≦・・・≦βm(<αm+1)とする。また、式(35)のmは、上記で用いた記号mの意味とは異なることに留意すること。
【数31】
【0173】
次に、(β0<)γ1<α1≦β1<γ2<α2≦・・・≦βm<γm+1(<αm+1)を満たすm+1個の参照点γi∈R〔i=1,2,・・・,m+1〕をとる(ステップS702)。但し、m=0のときは、γ1をどこにとってもよい。
【0174】
続いて、パラメータiを1に設定する(ステップS703)。
【0175】
続いて、i=1かつm=0かつ『γiが実区間多項式Fの実重複擬零点である』の成立を判定する(ステップS704)。『γiが実区間多項式Fの実重複擬零点である』か否かは既述の凸包判定で可能である〔以下同様。〕。
【0176】
i=1かつm=0かつ『γiが実区間多項式Fの実重複擬零点である』が成立するならば、集合Z=R(実数全体の集合)としてMZR(F)決定処理を終了する(ステップS705)。集合MZR(F)は、この段階で得られた集合Z、つまり集合Rとなる。
【0177】
i=1かつm=0かつ『γiが実区間多項式Fの実重複擬零点である』が成立しない場合、i=1かつm≧1かつ『γiが実区間多項式Fの実重複擬零点である』の成立を判定する(ステップS706)。
【0178】
i=1かつm≧1かつ『γiが実区間多項式Fの実重複擬零点である』が成立する場合、集合Zおよび(−∞,β1]の和集合をとり、この和集合を新たな集合Zとして置き換えて(ステップS707)、続いてステップS708の処理を行う。
また、i=1かつm≧1かつ『γiが実区間多項式Fの実重複擬零点である』が成立しない場合は、続いてステップS708の処理を行う。
【0179】
続いて、パラメータiを2に設定する(ステップS708)。
【0180】
次に、『γiが実区間多項式Fの実重複擬零点である』の成立を判定する(ステップS709)。
【0181】
『γiが実区間多項式Fの実重複擬零点である』が成立する場合、集合Zおよび閉区間[βi−1,αi]の和集合をとり、この和集合を新たな集合Zとして置き換えて(ステップS710)、続いてステップS711の処理を行う。『γiが実区間多項式Fの実重複擬零点である』が成立しない場合、ステップS712の処理を行う。
【0182】
ステップS710の処理に続いて、i=m+1の成立を判定する(ステップS711)。i=m+1が成立する場合、続いてステップS713の処理を行う。i=m+1が成立しない場合、続いてステップS712の処理を行う。
【0183】
ステップS709の処理で『γiが実区間多項式Fの実重複擬零点である』が成立しない場合、あるいは、ステップS711の処理でi=m+1が成立しない場合、iに1加えたものを新たなiとして(ステップS712)、ステップS709〜S711の処理を行う。
【0184】
ステップS711の処理でi=m+1が成立した場合、i=m+1かつ『γiが実区間多項式Fの実重複擬零点である』の成立を判定する(ステップS713)。
【0185】
i=m+1かつ『γiが実区間多項式Fの実重複擬零点である』が成立した場合、集合Zおよび閉区間[βm,∞)の和集合をとり、この和集合を新たな集合Zとして置き換えて(ステップS714)、MZR(F)決定処理を終了する。集合MZR(F)は、この段階で得られた集合Zである。i=m+1かつ『γiが実区間多項式Fの実重複擬零点である』が成立しない場合、MZR(F)決定処理を終了する。集合MZR(F)は、この段階で得られた集合Zである。
以上で《MZR(F)決定処理》の説明は終わりである。
【0186】
《Sturmの定理に基づくアルゴリズム》
Sturmの定理に基づくアルゴリズムの適用について概説する。
係数が確定した実係数多項式H(s)について、多項式の列H0(s)、H1(s)、H2(s)、・・・、Hr(s)を生成する。但し、これらの多項式の列は、次の規則に従って生成する。H0(s)=H(s)、H1(s)=dH(s)/ds〔sに関する1階微分である。ライプニッツ記法〕、Hk−1(s)をHk(s)で割った剰余多項式を(符号を変えて)−Hk+1(s)とする。つまり、商の多項式をQk(s)と表すと、Hk−1(s)=Hk(s)Qk(s)−Hk+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)の零点ではないとする(零点であれば、個数を表す式が少し変わるが、本発明においては本質的な部分ではないので略する。)。w(a)−w(b)=0であれば零点が存在しないことが判明し、w(a)−w(b)≠0であれば零点が存在することが判明する。区間S=[a,b]を十分に狭くとることで実零点の所在を決定できる。
以上で《Sturmの定理に基づくアルゴリズム》の概説は終わりである。
【0187】
[第1実施形態]
以下に、本発明の第1実施形態を説明する。第1実施形態は、実区間多項式Fの実重複擬零点が実区間Iに存在するか否かに係わる。
図8は、本実施形態に係わる実重複擬零点位置判定装置(1)のハードウェア構成を例示した構成ブロック図である。
【0188】
図8に例示するように、実重複擬零点位置判定装置(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などの記憶媒体を読み書きできる装置(ドライブ)などを設けるとしてもよい。このようなハードウェア資源を備えた物理的実体としては、汎用コンピュータなどがある。
【0189】
実重複擬零点位置判定装置(1)の外部記憶装置(17)には、実区間多項式の実重複擬零点の位置判定をするのに必要となるプログラムおよびこのプログラムの処理において必要となるデータなどが保存記憶されている。また、これらのプログラムの処理によって得られるデータなどは、RAMや外部記憶装置などに適宜に保存記憶される。以下、演算結果やその格納領域のアドレスなどを記憶するRAM(15)やレジスタなどの装置を単に「メモリ」と呼ぶことにする。
【0190】
より具体的には、実重複擬零点位置判定装置(1)の外部記憶装置(17)〔あるいはROMなど〕には、実区間I上で任意に1点αを選択し、この点αを実重複零点とする多項式が実区間多項式Fに存在するか否かを判定するための選択点多項式判定プログラム、実区間I上に実重複零点を有する要素エッジ多項式が実区間多項式Fに存在するか否かを判定するためのエッジ多項式判定プログラムおよびこれらのプログラムの処理において必要となるデータなどが保存記憶されている。その他、これらのプログラムに基づく処理を制御するための制御プログラムも適宜に保存記憶しておく。
【0191】
実重複擬零点位置判定装置(1)では、外部記憶装置(17)〔あるいはROMなど〕に記憶された各プログラムとこの各プログラムの処理に必要なデータが必要に応じてメモリ(20)に読み込まれて、適宜にCPU(14)で解釈実行・処理される。その結果、CPU(14)が所定の機能(選択点多項式判定部、エッジ多項式判定部、制御部)を実現する。
【0192】
図1、図2、図3、図8、図9を参照して、本実施形態における実区間多項式の実重複擬零点の位置判定処理について説明する。
【0193】
実重複擬零点位置判定装置(1)の外部記憶装置(17)には、予め、実区間多項式F(x)、実区間Iなどが予め保存記憶されているとする。
【0194】
この実施形態では、説明の便宜からより具体的に、実区間多項式F(x)の各項の区間数Aj=[uj,hj]≡{(hj−uj)tj+uj}〔但し、0≦tj≦1、j=0,1,2,・・・,dとする。〕、実区間I=[a,b]がデータとして、予め、実重複擬零点位置判定装置(1)の外部記憶装置(17)に保存記憶されているとする。なお、実区間Iは閉区間、左閉右開区間、左開右閉区間、開区間のいずれでもよい。
【0195】
これらの情報などは、予め実重複擬零点位置判定装置(1)の外部記憶装置(17)に保存記憶しておくのではなく、例えば、入力部(11)から入力されるとしてもよいし、あるいは、これらの情報などを格納した記録媒体からドライブを駆動して読み込むようにしてもよく、適宜に変更可能である。
【0196】
また、これらの情報などに限定する趣旨のものではない。例えば、実区間多項式F(x)の区間数ではなく実区間多項式F(x)そのものを実重複擬零点位置判定装置(1)の外部記憶装置(17)に保存記憶しておくとしてもよい(実区間多項式に属する多項式それぞれを記憶するのではないことに留意する。)。
【0197】
なお、本発明の細部においては、数値計算処理のみならず有理式や区間多項式などの数式処理も必要となるが、数値計算処理および数式処理自体は、公知技術と同様にして達成されるので、その演算処理方法などの詳細な説明は省略する(この点の技術水準を示す数式処理が可能なソフトウェアとしては、例えば、Risa/Asir、Maple(登録商標)、MATHEMATICA(登録商標第2312968号)、Gnuplotなどが挙げられる。Risa/Asirについては、例えばインターネット〈URL:http://hpc.cs.ehime-u.ac.jp/risa/〉[平成18年4月25日検索]を参照のこと。Mapleについては、例えばインターネット〈URL:http://www.cybernet.co.jp/maple/〉[平成18年4月25日検索]を参照のこと。Gnuplotについては、例えばインターネット〈URL: http://www.gnuplot.info/〉[平成18年4月25日検索]を参照のこと。)。
【0198】
まず、実重複擬零点位置判定装置(1)の制御部(190)は、外部記憶装置(17)から全ての区間数Aj={(hj−uj)tj+uj}、実区間I=[a,b]を読み込み、それぞれをメモリ(20)の所定の格納領域に格納しておく。以後、「メモリから○○を読み込む」旨の説明をした場合は、「メモリにおいて○○が格納されている所定の格納領域から○○を読み込む」ことを意味するとする。
【0199】
選択点多項式判定部(141)は、メモリ(20)から、全ての区間数Aj={(hj−uj)tj+uj}、実区間I=[a,b]を読み込み、《凸包判定》で説明したアルゴリズムに従って、実区間I上で任意に選択された1点αについて、この点αを実重複擬零点とする多項式が実区間多項式F(x)に存在するか否かを判定する(図1のステップS100)。
概略を示すと、選択点多項式判定部(141)は、メモリ(20)と協働しながら、次のような動作をする。つまり、実区間I上で任意に1点αを選択し、この点αを実区間多項式F(x)および実区間多項式F(x)を1階微分したものに代入して式(22)の如く式変形を行う。式(22)の左辺で表される点全体の凸包に式(22)の右辺の点が入るかを判定し、その判定結果を得る。判定結果は、「点αを実重複零点とする多項式が実区間多項式F(x)に存在する」あるいは「点αを実重複零点とする多項式が実区間多項式F(x)に存在しない」を表す情報Θである。
【0200】
制御部(190)は、この判定結果情報Θが、点αを実重複零点とする多項式が実区間多項式F(x)に存在するというものである場合には(図2のステップS412参照。)、「実区間I内に実区間多項式Fの実重複擬零点が存在する」ことを表す情報θ(例えばこの場合は、θ=1とする。)をメモリ(20)の所定の格納領域に格納する(図1のステップS103)。なぜなら、この場合、この点αを実重複零点とする実区間多項式F(x)に属する多項式が存在することは、まさに実区間多項式F(x)が実区間I上に実重複擬零点を有することと同じであるからである。
【0201】
制御部(190)は、判定結果情報Θが、点αを実重複零点とする多項式が実区間多項式F(x)に存在しないというものである場合には(図2のステップS411参照。)、ステップS101の処理を実行するように制御する。
【0202】
次に、エッジ多項式判定部(142)は、メモリ(20)から、全ての区間数Aj={(hj−uj)tj+uj}、実区間I=[a,b]を読み込み、《エッジ多項式判定》で説明したアルゴリズムに従って、実区間I上に実重複零点を有する要素エッジ多項式が実区間多項式F(x)に存在するか否かを判定する(図1のステップS101)。
概略を示すと、エッジ多項式判定部(142)は、メモリ(20)と協働しながら、区間数Ajに対するエッジ多項式について次のような動作をする。つまり、多項式w(x)、多項式wu(x)、多項式wu(x)について各実零点が、実区間Iに属するか否かを判定し、その判定結果を得る。判定結果は、「実区間I上に実重複零点を有する要素エッジ多項式が存在する」あるいは「実区間I上に実重複零点を有する要素エッジ多項式が存在しない」を表す情報Γである。判定結果情報Γが「実区間I上に実重複零点を有する要素エッジ多項式が存在する」場合には、エッジ多項式判定部(142)はエッジ多項式判定処理を終了してよい。判定結果情報Γが「実区間I上に実重複零点を有する要素エッジ多項式が存在しない」場合には、多項式P、既約有理式Q/Rを求め、多項式Pが恒等的に0か否かを判定する。多項式Pが恒等的に0であるならばβ∈IについてQ(β)/R(β)∈IE〔IEは、エッジ多項式において端点に固定されていない係数の区間数(但し、端点を除く。)を表す。上記説明では、開区間(u,h)に対応する。〕の成否を判定し、これが成立するならば「実区間I上に実重複零点を有する要素エッジ多項式が存在する」を表す情報Γを得る。多項式Pが恒等的に0でないならば多項式P1を求め、多項式P1の実零点ζについて、ζ∈IかつQ(ζ)/R(ζ)∈IEの成否を判定し、これが成立するならば「実区間I上に実重複零点を有する要素エッジ多項式が存在する」を表す情報Γを得る。いずれのエッジ多項式について上記所定の判定を満足しなかった場合は、「実区間I上に実重複零点を有する要素エッジ多項式が存在しない」を表す情報Γを得る。
【0203】
制御部(190)は、この判定結果情報Γが、実区間I上に実重複零点を有する要素エッジ多項式が存在しないというものである場合には(図3のステップS518参照。)、「実区間I内に実区間多項式Fの実重複擬零点が存在しない」ことを表す情報θ(例えばこの場合は、θ=0とする。)をメモリ(20)の所定の格納領域に格納する(図1のステップS102)。なぜなら、上記理論から明らかなとおり、実区間多項式F(x)に属するいかなる要素エッジ多項式も実区間I上に実重複零点を有しないことは、結局、実区間I内に実区間多項式Fの実重複擬零点が存在しないことと同じであるからである。
【0204】
制御部(190)は、判定結果情報Γが、実区間I上に実重複零点を有する要素エッジ多項式が存在するというものである場合には(図3のステップS517参照。)、「実区間I内に実区間多項式Fの実重複擬零点が存在する」ことを表す情報θ(例えばこの場合は、θ=1とする。)をメモリ(20)の所定の格納領域に格納する(図1のステップS103)。なぜなら、この場合、実区間I上に実重複零点を有する要素エッジ多項式が存在することは、まさに実区間I内に実区間多項式Fの実重複擬零点が存在することと同じであるからである。
【0205】
[第2実施形態]
以下に、本発明の第2実施形態を説明する。第2実施形態は、実区間多項式Fの実重複擬零点全体の集合MZR(F)の決定に係わる。なお、第1実施形態と第2実施形態は両立するから、コンピュータに両者を実装することができる。ここでは説明の便宜から、実区間多項式Fの実重複擬零点全体の集合MZR(F)の決定を第2実施形態としている。
第2実施形態に係わる実重複擬零点位置判定装置(1)〔以下、単に実重複擬零点位置判定装置(1)ということにする。〕のハードウェア構成等は第1実施形態と同様であるから、第2実施形態の本質部分について説明を加える。
【0206】
第2実施形態に係わる実重複擬零点位置判定装置(1)の外部記憶装置(17)〔あるいはROMなど〕には、実区間多項式Fの全てのエッジ多項式について、その実重複擬零点全体の集合Zを求めるための集合Z決定プログラム、集合Zの補集合における全ての実区間Jについて、各実区間J上で任意に1点γを選択し、この点γを実重複零点とする多項式が実区間多項式Fに存在するか否かを判定し、これが存在する場合には点γを含む実区間Jと集合Zとの和集合を求めることで集合MZR(F)を得る集合MZR(F)決定プログラムおよびこれらのプログラムの処理において必要となるデータなどが保存記憶されている。その他、これらのプログラムに基づく処理を制御するための制御プログラムも適宜に保存記憶しておく。
【0207】
実重複擬零点位置判定装置(1)では、外部記憶装置(17)〔あるいはROMなど〕に記憶された各プログラムとこの各プログラムの処理に必要なデータが必要に応じてメモリ(20)に読み込まれて、適宜にCPU(14)で解釈実行・処理される。その結果、CPU(14)が所定の機能(集合Z決定部、集合MZR(F)決定部、制御部)を実現する。
【0208】
図4、図5、図6、図7、図10を参照して、第2実施形態における実区間多項式の実重複擬零点の位置判定処理について説明する。
【0209】
実重複擬零点位置判定装置(1)の外部記憶装置(17)には、予め、実区間多項式F(x)、実区間Iなどが予め保存記憶されているとする。
【0210】
第2実施形態では、説明の便宜からより具体的に、実区間多項式F(x)の各項の区間数Aj=[uj,hj]≡{(hj−uj)tj+uj}〔但し、0≦tj≦1、j=0,1,2,・・・,dとする。〕が、予め、実重複擬零点位置判定装置(1)の外部記憶装置(17)に保存記憶されているとする。
【0211】
まず、実重複擬零点位置判定装置(1)の制御部(190)は、外部記憶装置(17)から全ての区間数Aj={(hj−uj)tj+uj}を読み込み、それぞれをメモリ(20)の所定の格納領域に格納しておく。以後、「メモリから○○を読み込む」旨の説明をした場合は、「メモリにおいて○○が格納されている所定の格納領域から○○を読み込む」ことを意味するとする。
【0212】
集合Z決定部(145)は、メモリ(20)から、全ての区間数Aj={(hj−uj)tj+uj}を読み込み、《集合Z決定処理》で説明したアルゴリズムに従って、実区間多項式Fの全てのエッジ多項式について、その実重複擬零点全体の集合である集合Zを求める(図4のステップS200)。
概略を示すと、集合Z決定部(145)は、メモリ(20)と協働しながら、区間数Ajに対するエッジ多項式について次のような動作をする。つまり、多項式w(x)、多項式wu(x)、多項式wu(x)について全実零点集合の和集合SZを求める。なお、多項式wu(x)、多項式wu(x)についていずれかが恒等的に0ならば集合Zは実数全体の集合Rとして集合Z決定処理を終了してよい。多項式P、既約有理式Q/Rを求め、多項式Pが恒等的に0か否かを判定する。多項式Pが恒等的に0ならば、集合SZの各要素を挟むようにとった各点βについて、Q(β)/R(β)∈IE〔IEは、エッジ多項式において端点に固定されていない係数の区間数(但し、端点を除く。)を表す。上記説明では、開区間(u,h)に対応する。〕の成否を判定し、これが成立するならば、点βに応じた区間を集合SZに加える〔以下、集合と集合との和集合をとることを「加える」と表現する。〕。なお、集合SZの要素が1つも無い場合には、1点βについてQ(β)/R(β)∈IEの成否を判定し、これが成立するならば、集合Zは実数全体の集合Rとして集合Z決定処理を終了してよい。多項式Pが恒等的に0でないならば、多項式P1を求め、多項式P1の全実零点ζSについて、ζS∈IかつQ(ζ)/R(ζ)∈IEの成否を判定し、これが成立するならば、{ζS}を集合SZに加える。エッジ多項式ごとに得られた集合SZの和集合を集合MZR(E)とし、エッジ多項式ごとに得られた集合MZR(E)の和集合を集合Zとする。
【0213】
制御部(190)は、集合Zが得られたら、ステップS201の処理を実行するように制御する。
【0214】
次に、集合MZR(F)決定部(146)は、メモリ(20)から、集合Zを読み込み〔必要に応じて、全ての区間数Aj={(hj−uj)tj+uj}および実区間Jが読み込まれる。〕、《集合MZR(F)決定処理》で説明したアルゴリズムに従って、集合MZR(F)を得る(図4のステップS201)。
概略を示すと、集合MZR(F)決定部(146)は、メモリ(20)と協働しながら、次のような動作をする。つまり、まず、集合Zが実数全体の集合Rであるならば、集合MZR(F)は集合Rであるとして集合MZR(F)決定処理を終了してよい。集合Zが実数全体の集合Rでないならば、集合Zを区間の和集合として書き表し、集合Zの補集合における全ての実区間Jについて、各実区間J上で任意に1点γを選択する。点γを実重複零点とする多項式が実区間多項式Fに存在するか否かを判定し〔凸包判定を用いればよい。〕、これが存在する場合には点γを含む実区間Jを集合Zに加えることで集合MZR(F)を得る。
【0215】
本発明である実区間多項式の実重複擬零点の位置装置、位置判定方法は上述の実施形態に限定されるものではなく、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。また、上記実施形態において説明した処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されるとしてもよい。
【0216】
また、上記実施形態において説明した実重複擬零点位置判定装置における処理機能をコンピュータによって実現する場合、実重複擬零点位置判定装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記実重複擬零点位置判定装置における処理機能がコンピュータ上で実現される。
【0217】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、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)等を用いることができる。
【0218】
また、このプログラムの流通は、例えば、そのプログラムを記録したDVD、CD−ROM等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【0219】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるASP(Application Service Provider)型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの(コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等)を含むものとする。
【0220】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、実重複擬零点位置判定装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【実施例1】
【0221】
以下、本発明である実区間多項式の実重複擬零点の位置判定方法の実施例を、具体例を示して簡単に説明する。以下では、ある桁から先の値を省略する意味の『…』が付されていない小数は、正確な値を表すものとする。
【0222】
この実施例では、多項式e1(x)=Πi=120(x−i),e2(x)=x19,e3(x)=x18として、実区間多項式F(x)を式(36)で与える。式(36)の実区間多項式Fに対し、第2実施形態を適用して集合MZR(F)を決定する。
【数32】
【0223】
実区間多項式Fの全てのエッジ多項式は以下のとおりである。
E1=e1(x)+[−2-23,0]e2(x)
E2=e1(x)+[−2-23,0]e2(x)+2-16e3(x)
E3=e1(x)−2-23e2(x)+[0,2-16]e3(x)
E4=e1(x)+[0,2-16]e3(x)
【0224】
エッジ多項式E1は5個の実重複擬零点を持つ。それをα11,・・・,α15と表すことにする。
α11=10.328…,α12=12.388…,α13=14.451…,
α14=16.524…,α15=18.619…
【0225】
エッジ多項式E2は実重複擬零点を持たない。
【0226】
エッジ多項式E3は3個の実重複擬零点を持つ。
α31=9.313…,α32=10.292…,α33=19.811…
【0227】
エッジ多項式E4は6個の実重複擬零点を持つ。
α41=9.307…,α42=11.365…,α43=13.426…,
α44=15.493…,α45=17.573…,α46=19.694…
【0228】
従って、実区間多項式Fのエッジ多項式は、全部で14個の実重複擬零点を持ち、集合Zは式(37)のとおりとなる。
【数33】
【0229】
なお、αijを大きさの順に並べると以下のとおりである。
α41<α31<α32<α11<α42<α12<α43<α13<α44<α14<α45<α15<α46<α33
【0230】
参照点γ1,γ2,…,γ15を以下のとおりに採る。
γ1=0,γ2=9.31,γ3=10,γ4=10.3,γ5=11,
γ6=12,γ7=13, γ8=14,γ9=15, γ10=16,
γ11=17,γ12=18, γ13=19,γ14=19.8,γ15=20
【0231】
各参照点γiに対し、これらが実区間多項式F(x)の実重複擬零点となるか否かを判定することによって、集合Zは以下のとおりとなる。
Z=[α41,α31]∪[α32,α11]∪[α42,α12]∪[α43,α13]∪[α44,α14]∪[α45,α15]∪[α46,α33]
【0232】
ここで得られた集合Zが集合MZR(F)である。
【実施例2】
【0233】
この実施例では、式(38)の実区間多項式Gに対し、第2実施形態を適用して集合MZR(G)を求める。
【数34】
【0234】
エッジ多項式は全部で12本あり、それらが持つ実重複擬零点は合わせて5個である。小さい方から並べると、以下のとおりである。
α1=−1.00012…, α2=−1.00006…,
α3=−0.99993741…,α4=−0.999937407…,
α5=−0.9998…
【0235】
従って、集合Zは次のとおり与えられる。
Z=[α1,α1]∪[α2,α2]∪[α3,α3]∪[α4,α4]∪[α5,α5]
【0236】
なお、各αiは、以下の要素エッジ多項式Eiの実重複擬零点となっている。
E1=144e1(x)+εe2(x)+[−ε,ε]e3(x)−εe4(x)
E2=144e1(x)+εe2(x)+εe3(x)+[−ε,ε]e4(x)
E3=144e1(x)−εe2(x)−εe3(x)+[−ε,ε]e4(x)
E4=144e1(x)+[−ε,ε]e2(x)+εe3(x)+εe4(x)
E5=144e1(x)−εe2(x)+[−ε,ε]e3(x)+εe4(x)
【0237】
参照点を以下のとおりに採る。
γ1=−2,γ2=−1.0001,γ3=−1,γ4=−0.9999374,γ5=−0.9999,γ6=0
【0238】
各参照点γiに対し、これらが実区間多項式F(x)の実重複擬零点となるか否かを判定することによって、Z=[α1,α5]を得る。
【0239】
ここで得られた集合Zが集合MZR(G)である。
【産業上の利用可能性】
【0240】
本発明は、例えば、多項式の係数に誤差を含むため一意に多項式を決定できない場合において、当該多項式の実重複零点が所定の領域に存在するかを判定したい場合や実区間多項式の実重複擬零点全体の集合を求めたい場合などに用いられ、そのような場合の一例として、ディジタル信号処理におけるディジタルフィルタの周波数特性の解析などに有用である。
【図面の簡単な説明】
【0241】
【図1】実区間I内に実区間多項式Fの実重複擬零点が存在するか否かを判定する実重複擬零点位置判定処理のフローチャート。
【図2】実区間I上で任意に選択された1点を実重複零点とする多項式が実区間多項式Fに存在するか否かを判定する凸包判定処理のフローチャート。
【図3】実区間I上に実重複零点を有する要素エッジ多項式が実区間多項式Fに存在するか否かを判定するエッジ多項式判定処理のフローチャート。
【図4】実区間多項式Fの実重複擬零点全体の集合MZR(F)を決定する実重複擬零点位置判定処理のフローチャート。
【図5】実区間多項式Fの全てのエッジ多項式について、その実重複擬零点全体の集合Zを決定する集合Z決定処理のフローチャート(その1)。
【図6】実区間多項式Fの全てのエッジ多項式について、その実重複擬零点全体の集合Zを決定する集合Z決定処理のフローチャート(その2)。
【図7】集合Zから集合MZR(F)を決定する集合MZR(F)決定処理のフローチャート。
【図8】実重複擬零点位置判定装置(1)のハードウェア構成を例示した構成ブロック図。
【図9】実区間I内に実区間多項式Fの実重複擬零点が存在するか否かを判定する実重複擬零点位置判定処理の処理機能を示す機能ブロック図。
【図10】実区間多項式Fの実重複擬零点全体の集合MZR(F)を決定する実重複擬零点位置判定処理の処理機能を示す機能ブロック図。
【符号の説明】
【0242】
1 実重複擬零点位置判定装置
141 選択点多項式判定部
142 エッジ多項式判定部
145 集合Z決定部
146 集合MZR(F)決定部
190 制御部
【技術分野】
【0001】
本発明は、実区間多項式の零点の位置判定装置、位置判定方法、位置判定プログラムおよび記録媒体に関する。より詳細には、一変数実区間多項式の実重複擬零点の位置判定装置、位置判定方法、位置判定プログラムおよび記録媒体に関する。
【背景技術】
【0002】
係数に誤差のある一変数実多項式は、例えばディジタル信号処理やシステム制御の分野に現れ、その零点の位置はディジタルフィルタの周波数特性やシステムの性能に密接に関係する。
【0003】
そして、多項式の実の重複零点〔重複度が2以上の零点〕は、どんなに小さな係数の変化に対しても、複数の複素零点あるいは実の近接零点となる。従って、実の零点が存在するか否か、あるいは、いくつ存在するのかを知る必要があるとき、実の重複零点の存在が重大な関心事となる。
【0004】
式(1)で表される実係数一変数多項式が与えられたとする。
【数1】
【0005】
各実係数ai(ここではi=0,1,・・・,dである。)は、観測や測定によって得られたもので真の値とは異なるかもしれない、と仮定する。但し、誤差の範囲は分かっており、各実係数aiの真の値は実の閉区間[ui,hi]内にあるものとする。『各実係数aiがこの誤差範囲内にある多項式で、実の重複零点を有するものがあるか否か判定せよ』という問題を考える。
【0006】
これに関連して、非特許文献1には、式(1)で表される多項式の各係数aiが複素数のとき、重複零点を有する複素数係数の多項式g(x)〔式(2)参照。〕の中で、式(3)で表される量、つまりf(x)−g(x)のl2−ノルム〔文字「l」はアルファベットの「エル」の小文字である。〕を最小とするものを求める問題を、適当なある二次形式の最小化の問題に帰着して解決する方法が示されている。
【数2】
【0007】
この方法は、下記の点で、後に詳述する本発明と似て非なるものである。
・係数およびその誤差を複素数の範囲とする点
・重複零点を実とは限らない点
・誤差の範囲指定が係数ごとではなく、多項式のl2−ノルムとしている点
・重複零点の有無についての判定問題は扱えるが、重複零点となる数の集合の決定、即ち、係数誤差範囲内で多項式を動かしたときに、その重複零点となる数すべての集合を決定する問題は扱えない点
【0008】
一変数多項式は、各係数も変数と見なした上で元の変数に値を代入すると、それぞれの係数に対応する変数について一次式と見ることができる。この性質を利用すれば、『多項式の各係数を誤差範囲内で動かして、与えられた実数αを零点として持つようにできるか』という問題は、誤差範囲が実数のとき、誤差範囲の端点を正確に計算する区間演算で判定可能である。具体的には、各係数aiがui≦ai≦hiなる範囲にあるとして、式(4)を、端点を正確に計算する区間演算を用いて求め、その結果の区間に0が入るか否かを調べればよい。
【数3】
【0009】
誤差範囲が複素数のときには、非特許文献2に記述のあるとおり、適当なある不等式の成立、不成立の判定に帰着できる。
f(x)がx=αにおいて重複零点を持つ必要十分条件は、f(x)=f′(x)=0がx=αなる解を持つこと、すなわち、連立方程式(5)がx=αなる解を持つことである。なお、ここで記号「′」はxに関する微分を表す。
【数4】
【0010】
連立方程式(5)を書き改めると、連立方程式(6)がx=αなる解を持つことである。
【数5】
【0011】
『xに値を代入して係数をある範囲で動かしたとき、連立方程式(6)が成り立つようにできるか』という問題に関連して、非特許文献2〔非特許文献2のCorollary 9参照。〕は、連立方程式(7)にxi=αiを代入したとき、bijを、uij≦bij≦hijの範囲で動かして連立方程式(7)を成立させることができるか否かの判定が、適当なある不等式が成立するか否の判定に帰着できることを述べている。
【数6】
【0012】
そうすると、非特許文献2が提示する解法を連立方程式(6)のaiに誤差がある場合にも適用できるように思える。しかし、連立方程式(7)では、行列(bij)の全ての成分が独立に動かせるものと仮定しての結果である。連立方程式(6)においては、ai,・・・,adが2ヵ所ずつに現れるので、非特許文献2のCorollary 9を用いた解法は適用できない。
【非特許文献1】L. Zhi and W. Wu, "Nearest Singular Polynomials", Journal of Symbolic Computation, Vol.26, No.6, pp.667-675, 1998.
【非特許文献2】H. J. Stetter, "The nearest polynomial with a given zero,and similar problems", ACM SIGSAM Bulletin, Vol.33, No.4, pp.2-4, 1999.
【発明の開示】
【発明が解決しようとする課題】
【0013】
さて、『一変数多項式の各係数および係数毎の誤差をそれぞれ実数で与えるとして、各係数が係数毎の誤差範囲内に在る多項式が或る与えられた実の区間で重複零点を有するか否かを判定せよ、さらに、係数誤差範囲内で多項式を動かしたとき、その重複零点となる実数すべての集合を具体的に表示せよ』・・・(☆)という問題を考える。
【0014】
非特許文献1に提示される解法は、l2−ノルムで誤差をはかり、二次形式の最小化を用いるものであるから、係数毎に誤差範囲を指定した問題(☆)を扱うことができない〔なお、上記4点の差異も参照のこと。〕。また、非特許文献2に提示される解法は、1点を与えたときに、それを「零点」とするような多項式が係数誤差範囲内に存在するか否かの判定は可能だが、「重複零点」とする場合の問題(☆)には適用できない。また、いずれも、重複零点となりうる点の集合の決定はできない。
【0015】
そこで、本発明は、問題(☆)に解答を与えることを目的とする。
この目的を、より端的に説明する。
これに先立ち、この明細書における記号および用語の説明をする。
但し、記号については、説明の便宜等からそれまでの意味とは異なる意味で同じ記号を用いる場合があることに留意しておくこと。
【0016】
係数が確定していない(例えば、係数に誤差がある場合などである。)多項式を表す手法として、区間多項式がある。区間多項式F(x)とは、数の集合である区間数Ai(1≦i≦d、但しiは整数。)を各項の係数として式(8)のように表記されるものである。つまり、区間多項式F(x)は、係数がai∈Aiである多項式f(x)〔式(9)参照。〕全体の集合を表す。なお、この明細書における区間多項式は、特に断りのない限り、一変数区間多項式であるとする。
【数7】
【0017】
ここでは、区間数を実数の範囲で考える。この場合、区間数Aiとして閉区間[ui,hi]を用いる。このような区間多項式であることを明確にするため、以下では、実区間多項式と云うことにする〔正確には、「一変数実区間多項式」と云うべきであるが、「実区間多項式」と略記する。〕。
また、ei(x)は、実数である係数が確定した多項式であり、恒等的に0ではないとする。
なお、多項式について、例えば実区間多項式F(x)を実区間多項式Fなどのように変数を略記して表すことがある。
【0018】
実区間多項式Fに対し、実区間多項式Fに属する多項式fが存在して、多項式fがa∈R〔記号∈は、或る要素が集合に「属する」ことを意味する。Rは、実数全体の集合を表す。〕で重複零点を有するとき、実区間多項式Fは実重複擬零点aを有する、と云うことにする。実区間多項式Fに対し、その実重複擬零点全体の集合をMZR(F)と表記する。
【0019】
このとき、問題(☆)を次のように表現できる。
《問題1》 与えられた実区間多項式Fおよび実の区間Iに対し、実区間I内に実区間多項式Fの実重複擬零点が存在するか否かを判定せよ。
《問題2》 与えられた実区間多項式Fに対し、MZR(F)を決定せよ。
【0020】
つまり、本発明は、与えられた実区間多項式Fおよび実の区間Iに対し、実区間I内に実区間多項式Fの実重複擬零点が存在するか否かを判定し、あるいは、与えられた実区間多項式Fに対してMZR(F)を決定する一変数実区間多項式の実重複擬零点の位置判定装置、位置判定方法、位置判定プログラムおよび記録媒体を提供することを目的とする。
【課題を解決するための手段】
【0021】
上記課題を解決するために、本発明は、実数の閉区間で表される区間数を係数とする一変数実区間多項式〔実区間多項式F〕および実区間Iについて、選択点多項式判定手段が、実区間I上で任意に1点〔選択点〕を選択し、この選択点を実重複零点とする多項式が実区間多項式Fに存在するか否かを判定して、エッジ多項式判定手段が、実区間I上に実重複零点を有し且つエッジ多項式〔実区間多項式Fの1つの係数を除いた係数が区間数の端点となっている実区間多項式の集合〕に属する多項式が存在するか否かを判定する。
このような構成は数学的な保証に基づくものであり、この詳細は後述する。
【0022】
また、上記課題を解決するために、本発明は、実数の閉区間で表される区間数を係数とする一変数実区間多項式〔実区間多項式F〕に対して、集合Z決定手段が、実区間多項式Fのエッジ多項式について、その実重複擬零点〔エッジ多項式に属する多項式の実重複零点〕全体の集合Zを求める。そして、集合MZR(F)決定手段が、実数全体の集合に対する集合Zの補集合における全ての実区間Jごとに、各実区間J上で任意に1点γを選択して、この点γを実重複零点とする多項式が実区間多項式Fに存在するか否かを判定し、これが存在する場合の点γを含む実区間Jと集合Zとの和集合をとったものを、実区間多項式Fの実重複擬零点〔実区間多項式Fに属する多項式の実重複零点〕全体の集合MZR(F)とする。
このような構成は数学的な保証に基づくものであり、この詳細は後述する。
【発明の効果】
【0023】
本発明によれば、数学的保証の下に、実区間Iの1点について、これを実重複零点とする多項式が実区間多項式Fに存在するか否かを判定し、実区間I上に実重複零点を有し且つエッジ多項式に属する多項式が存在するか否かを判定することで、有限ステップで完全にかつ効率良く、実区間I内に実区間多項式Fの実重複擬零点が存在するか否かを判定することができる。
【0024】
本発明によれば、数学的保証の下に、まず、実区間多項式Fのエッジ多項式について、その実重複擬零点全体の集合Zを求めてから、実数全体の集合に対する集合Zの補集合における全ての実区間Jごとに、各実区間J上で任意に1点γを選択して、この点γを実重複零点とする多項式が実区間多項式Fに存在するか否かを判定し、これが存在する場合の点γを含む実区間Jと集合Zとの和集合をとったものを、実区間多項式Fの実重複擬零点全体の集合MZR(F)とすることで、有限ステップで完全にかつ効率良く、実区間多項式Fの実重複擬零点全体の集合MZR(F)を決定することができる。
【発明を実施するための最良の形態】
【0025】
[理論]
これから、本発明における実区間多項式の実重複擬零点の位置判定の理論およびアルゴリズムを、図面を参照しながら説明する。なお、予め説明しておくと、本発明における「実区間多項式の実重複擬零点の位置判定」とは、実区間多項式の実重複擬零点の位置(座標)を特定することではなく、所定の領域に実区間多項式の実重複擬零点が存在するか否かに係わる判定および実区間多項式に対してMZR(F)を決定することである。換言すれば、実区間多項式の実重複擬零点が所定の領域に存在するか否か、および、MZR(F)の決定の意味において、実区間多項式の実重複擬零点の位置判定をすることになる。
【0026】
式(8)および式(9)において、区間数の端点ui、hiおよび多項式ei(x)の係数は、理論上は実数としてよいが、コンピュータなどによる演算の上では四則演算および等号判定を有限ステップのアルゴリズムで実行できることが必要かつ十分であり、そのために例えば実代数的数(整数係数一変数代数方程式の根となる実数)とし、具体例として有理数であるとする。
以下では、説明の便宜から、ei(x)を有理数係数多項式の場合を例示して説明する。また、実代数的数として有理数を例にとって説明する。つまり、端点ui、hiを有理数としている。
【0027】
まず、《問題1》について。
問題1は、既述のとおり『与えられた実区間多項式Fおよび実の区間Iに対し、実区間I内に実区間多項式Fの実重複擬零点が存在するか否かを判定せよ』である。
【0028】
この問題1に対する解答の要旨は、次のとおりである。
<1>実区間I内で任意に選択した1点cについて、この点cが実区間多項式Fの実重複擬零点か否かを判定する。つまり、c∈Iを実重複零点とする多項式が実区間多項式Fに存在するか否かを判定する。点cが実重複擬零点ならば、問題1に対して「存在する」を解答として与える。点cが実重複擬零点でなければ、次の処理<2>を行う。
<2>実区間多項式Fのエッジ多項式に属する多項式であって、実区間I内に実重複零点を有する多項式が存在するか否かを判定する。このような多項式が存在すれば、問題1に対して「存在する」を解答として与える。このような多項式が存在しなければ、問題1に対して「存在しない」を解答として与える。
【0029】
ここでエッジ多項式とは、「実区間多項式Fの1つの係数を除いた係数が区間数の端点となっている実区間多項式の集合」である。より詳細には、実区間多項式Fに対し、そのエッジ多項式とは、ある一つの番号j(1≦j≦d、但しjは整数。)を除いては、係数aiがuiもしくはhi(但し、i≠jである。)に等しい実区間多項式の集合のことであり、式(10)で表される。
【数8】
【0030】
ここで、留意しなければならないのは、定義あるいは式(10)から明らかなとおり、エッジ多項式は実区間多項式Fの部分集合である。例えばj番目の係数を除いて係数が区間数の端点に固定されているエッジ多項式と云うとき、このエッジ多項式には最多2d−1個のものが考えられる。なぜなら、j番目の係数以外の各係数がそれぞれの区間数で端点を取る組み合わせが考えられ、式(10)の整数jが1≦j≦dであるとき、この組み合わせは最多2d−1個だからである。つまり、式(10)の第2項は最多2d−1本の多項式が考えられるので、「j番目の係数を除いて係数が区間数の端点に固定されているエッジ多項式」は最多2d−1個のエッジ多項式を云うことになる。そうすると、実区間多項式F(x)では、最多d×2d−1個のエッジ多項式が存在する。ここで、エッジ多項式に属する多項式〔単に多項式と言えば、係数が確定している多項式を云う。〕を、「要素エッジ多項式」と云うことにする。
数学的表現を用いるならば、実区間多項式F、エッジ多項式E、要素エッジ多項式gとしたとき、これらはE⊂F、g∈Eなる関係にある。
【0031】
以下、問題1に対する解答の要旨が上記のとおりに与えられる理由を説明する。
まず、実区間I上で任意に選択した1点cについて、この点cを実重複零点とする多項式が実区間多項式F(x)に存在するならば(図1のステップS100参照。)、「実区間Iに実重複零点を有する多項式f(x)∈F(x)が存在する」ことが判明したことになり、「実区間I内に実区間多項式Fの実重複擬零点が存在する」ことが言えたことと同じである(図1のステップS103参照。)。つまり、問題1に解答を与えたことになる。
なお、『実区間I上で任意に選択した1点cについて、この点cを実重複零点とする多項式が実区間多項式F(x)に存在するか否か』の判定方法は後述の《凸包判定》で説明する。
【0032】
次に、『実区間I上で任意に選択された1点cについて、この点cを実重複零点とする多項式が実区間多項式F(x)に存在しない場合、もし、実区間I上に実重複零点を有する多項式が存在するならば、その中で、エッジ多項式に属するものが存在する』ことが言える。
この証明を以下に説明する。
【0033】
今、「実区間I上の点d(但し、点cを除く。)を実重複零点とする多項式f(x)∈F(x)が存在するとして、多項式f(x)がエッジ多項式に属さない」と仮定する。このとき、区間数の端点に固定されていない係数(2つ以上あるとする。)を2つ選択し、これをpおよびqとする。
ここで記号αを実区間I上の点を表すパラメータとして、f(α)およびf′(α)を式(11)の如く表記することにする。なお、上記では記号αを実重複零点としたが、ここでの説明では異なる定義であることに留意すること。
【数9】
【0034】
点αにおいてf(α)=f′(α)=0になることは、pおよびqの2変数連立一次方程式(12)が成立することである。
【数10】
【0035】
点dは実重複零点であるから、α=dでは、所定の範囲(区間数内)に収まっている連立方程式(12)の解p、qが存在する(このp、qは、点dを実重複零点とする多項式f(x)の係数pおよびqに対応する。)。
ここでα=dにおいて行列式(13)が0とすると、連立方程式の解が不定であるならば、pおよびqを解としたまま、少なくともその1つを区間数の端点となるまで動かすことができる。また、連立方程式の解が存在しないのであるならば、パラメータαが行列式(13)を0にする値に近付くとき、p、qのうち少なくとも一方は∞あるいは−∞に発散するから、その前に区間数の端点に達することとなる。これは、上記仮定:「実区間I上の点dを実重複零点とする多項式f(x)∈F(x)が存在するとして、多項式f(x)がエッジ多項式に属さない」と矛盾する。なお記号≡は「定義」を表す。
【数11】
【0036】
従って、行列式(13)はα=dにおいて0ではないとする。点αを実区間I上において点dから動かしていくと、点αが点cに到達する前に、次のいずれかが起こる。もし、いずれも起こらずに点cに到達したとすると、「点cを実重複零点とする多項式が実区間多項式F(x)に存在しない」とする前提と矛盾する。なお、α0は点dおよび点cの間にある実区間I上の点である。
(i)pが区間数の端点に到達する。
(ii)qが区間数の端点に到達する。
(iii)行列式(13)が、α=α0において0になる。
【0037】
(i)および(ii)の場合は、多項式f(x)の係数のうち区間数の端点とならないものの個数が多項式f(x)の場合よりも1つ小さい多項式であって、実区間I上に実重複零点を有する多項式g(x)∈F(x)が存在することを示している。
【0038】
(iii)の場合は、後述の《補足説明》で説明するように、行列式(13)が0となる点において、連立方程式(12)は不定となるので、pおよびqを解としたまま、少なくともその1つを区間数の端点となるまで動かすことができる。つまり、多項式f(x)の係数のうち区間数の端点とならないものの個数が多項式f(x)の場合よりも1つ小さい多項式であって、実区間I上に実重複零点を有する多項式g(x)∈F(x)が存在することを示している。
【0039】
結局、以上から、点cを実重複零点とする多項式が実区間多項式F(x)に存在しない場合、実区間I上に実重複零点を有する多項式が存在するとしたとき、実区間I上の点dを実重複零点とするエッジ多項式に属さない多項式f(x)∈F(x)に対して、多項式f(x)の係数のうち区間数の端点とならないものの個数が多項式f(x)の場合よりも1つ小さい多項式であって、実区間I上に実重複零点を有する多項式g(x)∈F(x)が存在することが言えた。以上のような操作を(区間数の端点に固定されていない係数が3つ以上ある場合に)必要に応じて繰り返せば、エッジ多項式に属する多項式g(x)∈F(x)で、実区間I上に実重複零点を有するものが存在することが言える。
【0040】
従って、点cを実重複零点とする多項式が実区間多項式F(x)に存在しない場合には、『エッジ多項式に属する多項式g(x)∈F(x)であって、その実重複零点が実区間I上にあるものが存在するか否か』の判定をすればよい(図1のステップS101参照。)。このような多項式が存在すれば、問題1に対する解答は「存在する」となる(図1のステップS103参照。)。このような多項式が存在しなければ、問題1に対する解答は「存在しない」となる(図1のステップS102参照。)。
なお、『エッジ多項式に属する多項式g(x)∈F(x)であって、その実重複零点が実区間I上にあるものが存在するか否か』の判定方法は後述の《エッジ多項式判定》で説明する。
【0041】
《補足説明》
補足説明では、行列式(13)が0となる点において、連立方程式(12)が不定となることを説明する。
ここで、np(α)、nq(α)を式(14)によって定義する。ここでのp、qは、上記と同様、2つ選択された区間数の端点に固定されていない係数を意味する。
【数12】
【0042】
連立方程式(12)の解p、qは、αの関数として、式(15)によって表される。
【数13】
【0043】
αがα0に近づくとき、D(α)は0に収束するから、np(α)、nq(α)も0に収束する。収束することは、全ての係数がαの連続関数として表すことができることから保証されており、もし収束値が0以外ならば、αがα0に到達する前まで連立方程式(12)の解が有界であることに矛盾する。np(α)、nq(α)はαについて連続であるから、結局、式(16)が成り立つ。
【数14】
【0044】
さらに、aj(α0)=bj(α0)=0ならば〔但し、ここでのjは、j=1,2とする。〕、cj(α0)=0が成り立つ。なぜなら、ある正数Mがあって、αが実区間I上において点α0に近づくとき、常に不等式|p(α)|≦M、|q(α)|≦Mが成立するので、三角不等式から式(17)が成立する。
【数15】
【0045】
αが実区間I上において点α0に近づくとき、(|aj(α)|+|bj(α)|)Mは0に収束するから、cj(α)も0に収束する。そして、cj(α)は連続であることからcj(α0)=0が成り立つ。
【0046】
この準備の下、次の3通りに分けて証明する。
(i)a1(α0)=a2(α0)=0の場合について。もしb1(α0)≠0ならば、行列式(13)から、連立方程式(12)の第2式は第1式のb2(α0)/b1(α0)倍となる。ここでb1(α0)≠0から、連立方程式(12)が不定であることがわかる。もしb1(α0)=0ならば、上記の準備からc1(α0)=0となり、連立方程式(12)は第2式のみとなる。このとき、b2(α0)=0ならば、やはり上記準備からc2(α0)=0となり、第2式もなくなる。b2(α0)≠0ならば第2式は残るが、解は不定である。
【0047】
(ii)a1(α0)およびa2(α0)のうち、一方が0であり、他方が0ではない場合について。この場合、a1(α0)=0、a2(α0)≠0の場合について示せば十分である。上記のD(α0)=0から、b1(α0)=0となる。従って、上記準備からc1(α0)=0となる。つまり、連立方程式(12)は第2式のみに退化し、a2(α0)≠0から解は不定であることがわかる。
【0048】
(iii)a1(α0)およびa2(α0)が共に0ではない場合について。この場合、上記のD(α0)=0および行列式(13)から、連立方程式(12)において、第2式は第1式のa2(α0)/a1(α0)倍となる。従って、a1(α0)≠0から解は不定であることがわかる。
以上で《補足説明》は終わりである。
【0049】
《凸包判定》
実区間I上の任意の1点cを選択して、この点cを実重複零点とする多項式が実区間多項式F(x)に存在するか否かを調べる方法について説明する。以下では、アルゴリズムを簡単かつ効率良くするため、エッジ多項式に限らない範囲で調べるとする。
【0050】
ここでは、上記点cを説明の便宜からαに記号の置き換えをする。
式(8)で与えられる実区間多項式の区間数Ajを閉区間[uj,hj]で表したことに留意すると、閉区間[uj,hj]は、パラメータtj(0≦tj≦1なる実数)を用いて{(hj−uj)tj+uj}と表記することができる。パラメータtjは、閉区間の両端点uj、hjの内分比を表す。このとき、式(8)の実区間多項式F(x)は、上記区間数{(hj−uj)tj+uj}を各項の係数として式(18)のように表現され、各j(1≦j≦d、但しjは整数。)に対して係数がaj∈{(hj−uj)tj+uj}である多項式f(x)〔式(19)参照〕の全体の集合を表す。
【数16】
【0051】
このとき、「点αを実重複零点とする多項式が実区間多項式F(x)に存在するか否か」は、「連立方程式(20)を満足するtjの組み合わせが存在するか否か」と同値である。また、連立方程式(20)を書き改めると、連立方程式(21)と表せる。
【数17】
【0052】
つまり、連立方程式(21)を満足するtjの組み合わせが存在するならば、それは、この点αを実重複零点とする多項式が実区間多項式F(x)に存在することを意味する。ここで留意しなければならないのは、tjの組み合わせを特定することではなく、「連立方程式(21)を満足するtjの組み合わせが存在するか否か」である。ここで説明の便宜から、(ej(α) e′j(α))TをBjと表記する〔但し、Tは転置を表す。〕。そうすると、Bjは、デカルト直交座標系において、原点を始点、(x,y)=(ej(α),e′j(α))を終点とする位置ベクトルとみることができる。このような視点から、以下の説明でx座標、y座標と云えば、デカルト直交座標系〔以下、「平面」という。〕において位置ベクトルの終点を指すものする。
【0053】
そうすると、式(21)左辺について(hj−uj)tjBjを、「Bjを(hj−uj)倍した位置ベクトル(hj−uj)Bjを、tjによってスカラー倍したものである」と見れば、0≦tj≦1によって式(21)の左辺が取り得る平面上の範囲に、式(21)の右辺の点が存在するか否かを調べればよい。つまり、凸包に或る1点が存在するか否かの判定に持ち込むことを考えればよい。そこで、このような凸包を用いた判定を効率良く行うために、前処理を行う。
【0054】
まず、式(21)の左辺の各項(j=1,…,d)を順番に見ていき、各項について次のような判定と書き換えを行う。まず、(hj−uj)Bjのx座標〔つまり、(hj−uj)ej(α)である。〕が負であるかを判定する。負である場合には、(hj−uj)tjBjを(hj−uj)(1−tj)Bjに書き換える。次に、(hj−uj)Bjのx座標が負でない場合は、(hj−uj)Bjのx座標が0かつy座標〔つまり、(hj−uj)e′j(α)である。〕が負であるか否かを判定する。x座標が0かつy座標が負である場合には、(hj−uj)tjBjを(hj−uj)(1−tj)Bjに書き換える。
なお、この操作は式(20)において、(hj−uj)Bjのx座標が負である場合に{(hj−uj)tj+uj}Bjを{(hj−uj)(1−tj)+uj}Bjと書き換え、(hj−uj)Bjのx座標が0かつy座標が負である場合に{(hj−uj)tj+uj}Bjを{(hj−uj)(1−tj)+uj}Bjと書き換えることと同じである。
【0055】
以上の操作は、例えば、x座標が負である位置ベクトル(hj−uj)Bjをtjスカラー倍(0≦tj≦1)することは、平面原点対象に移動した位置ベクトル(hj−uj)×(−1)×Bjをkjスカラー倍(−1≦kj≦0)することと同じであるから、tjの範囲が0≦tj≦1であることに留意してkj=tj−1とおくと、(hj−uj)×(−1)×kj×Bjは、(hj−uj)×(1−tj)×Bjとなることに基づく。このような操作を行うことで、式(21)の左辺の点(hj−uj)Bjは、見かけ上、全て平面の右半平面(x座標が0以上の領域全体、但し、x座標が0かつy座標が負の部分は除く。)に集められるとともに、平面のy軸の負の部分には点が乗らないものとなる。換言すれば、この操作の結果得られた点集合は、平面原点を頂点とする凸包を平面の右半平面で構成する(但し、平面のy軸の負の部分に凸包の頂点はない。)。
【0056】
なお、このような操作は、後述の凸包を求めるための便宜としての前処理であるから、上記に限定されるものではない。例えば、(hj−uj)Bjのx座標が正であるかを判定し、正である場合には、(hj−uj)tjBjを(hj−uj)(1−tj)Bjに書き換え、(hj−uj)Bjのx座標が正でない場合は、(hj−uj)Bjのx座標が0かつy座標が負であるか否かを判定する。そして、x座標が0かつy座標が負である場合には、(hj−uj)tjBjを(hj−uj)(1−tj)Bjに書き換える(つまり、平面原点を頂点とする凸包を平面左側で構成する。)、といった操作などに適宜に変更できる。
【0057】
以上の操作を行ない、その結果に対して適切な式変形および記号の置き換え(ajおよびb)をすると、当該結果は式(22)のように表すことができる。但し、式(22)において、ajおよびbは上記Bjと同様にaj=(aj1 aj2)T、b=(b1 b2)Tと表される。つまり、ajおよびbは平面上の原点を始点とする位置ベクトルとみることができる。
【数18】
【0058】
結局、式(22)を満たすようなtj(0≦tj≦1)の組み合わせが存在するか否かの判定となるが、これは、εj=0あるいはεj=1とした場合に、式(23)の全体、即ち平面上で高々2d+1個の点の凸包に式(22)の右辺bの終点座標が入るか否かの判定と同じである〔下記参考文献1参照。〕。なお、式(22)を得る際の上記操作から、式(23)の全体のなす凸包は、平面の右半平面(但し、x座標が0かつy座標が負の部分は除く。)に存在することがわかる。従って、式(22)の右辺bのx座標が負の場合、あるいは、bのx座標が0かつy座標が負の場合、凸包を下記説明のように具体的に構成しなくてもbが式(23)の全体のなす凸包に入らないことがわかることに留意するべきである。
(参考文献1) 関川浩、白柳潔著、「区間多項式の零点の所在について」、社団法人電子情報通信学会、電子情報通信学会論文誌A、Vol.J89-A、No.3、pp.199-216
【数19】
【0059】
そこで、まず、式(23)で表される点の全体の凸包を求める。これは、効率的に求めることができる。
具体的にはまず、平面のy軸の負の部分を除く平面の右半平面の領域〔−π/2<arg≦π/2、argは角度を表す。〕において、aj≠0を傾き〔arg(aj)=aj2/aj1、但し、aj1=0ならばaj1/aj2は∞とみなす。〕でソート(sort)する。つまり、位置ベクトルaj≠0がx軸となす角度arg(aj)を、−π/2<arg≦π/2で、小さい方から大きい方へと昇順に並び替える。但し、同じ傾きのものがあるときには、それらを全部足したものに置き換えたものを1つとしてソートする。例えば、ajおよびakの傾きが同じときには、aj,akの代わりに、aj+akを対象としてソートする。なぜなら、傾きが同じ位置ベクトルajおよび位置ベクトルakの各終点は平面上において凸包の頂点となりえないからである(凸包の頂点の可能性があるのは、同じ傾きのものを全てベクトル加算した点である。)。このソートの結果を位置ベクトルp1,・・・,pmとする。なお、mはd+1より小さいことがあることに留意すること。
【0060】
このとき、求める平面上の凸包の頂点は、平面原点(0と表記する。)から始めて反時計回りに、0,p1,p1+p2,…,p1+…+pn,p2+p3+…pm,p3+…+pm,…,pm−1+pm,pmの全部で2m個となる。
つまり、式(23)の全体のなす凸包の平面における頂点座標は、反時計回りに式(24)で与えられる位置ベクトルvi(0≦i≦2m−1)の終点として表される〔複素平面の場合について参考文献1参照。〕。
【数20】
【0061】
この位置ベクトルvi(0≦i≦2m−1)の終点〔以下、「頂点vi」という。〕で構成される凸包に式(22)の右辺bの終点が入るか否かを判定する。この判定は、例えば次のようにして行うことができる。まず、arg(b)に対して、arg(vk)≦arg(b)<arg(vk+1)なる凸包の頂点vk、vk+1をとる。このとき、式(22)の右辺bの終点が凸包に入るか否かは、頂点vk、vk+1を結んだ線分に対して原点側(線分上を含む。)あるいは原点とは反対側の何れの側にbの終点が存在するかと同値である。そこで、位置ベクトルz1=(z1x,z1y)、z2=(z2x,z2y)に対してd(z1,z2)なる演算を式(25)の如く定義する。このとき、d(b−vk,vk+1−b)が正ならばbの終点が凸包に含まれず、d(b−vk,vk+1−b)が0以下ならばbの終点が凸包に含まれる。
【数21】
【0062】
bの終点が凸包に入る場合には、点cを実重複零点とする多項式が実区間多項式F(x)に存在すると判定でき、bの終点が凸包に入らない場合には、点cを実重複零点とする多項式が実区間多項式F(x)に存在しないと判定できる。
【0063】
以上のアルゴリズムに基づく凸包判定の処理フローを一例として図2に示す。
【0064】
まず、実区間I上の任意の1点αを選択する(ステップS400)。
【0065】
次に、選択した点αをx=αとして実区間多項式F(x)および実区間多項式F(x)を1階微分したものに代入する(ステップS401)。
【0066】
パラメータjを1に設定する(ステップS402)。
【0067】
このパラメータjに対応する(hj−uj)ej(α)が負であるかを判定する(ステップS403)。
【0068】
(hj−uj)ej(α)負である場合には、{(hj−uj)tj+uj}Bjを{(hj−uj)(1−tj)+uj}Bjと書き換える(ステップS405)。
【0069】
もし(hj−uj)ej(α)が負でない場合は、(hj−uj)ej(α)が0かつ(hj−uj)e′j(α)が負であるか否かを判定する(ステップS404)。
【0070】
(hj−uj)ej(α)が0かつ(hj−uj)e′j(α)が負である場合には、{(hj−uj)tj+uj}Bjを{(hj−uj)(1−tj)+uj}Bjと書き換える(ステップS405)。
【0071】
そしてパラメータjがdと等しいか否かを判定する(ステップS406)。
【0072】
j≠dであれば、jに1加えたものを新たなjとして(ステップS407)、ステップS403〜S406の処理を行う。j=dであれば、ステップS403〜S406の処理で得られた実区間多項式を式(22)の如く式変形する(ステップS408)。
【0073】
次に、ステップS408の処理で得られた式(22)の右辺で表される位置ベクトルbのx座標が負であるか否かを判定する(ステップS408x)。
【0074】
位置ベクトルbのx座標が負であれば、位置ベクトルbがステップS408の処理で得られた式(22)の左辺で表される点全体の凸包に入ることはないので、任意に選択された点αを実重複零点とする多項式が実区間多項式F(x)に存在しないといえる(ステップS411)。
【0075】
位置ベクトルbのx座標が負でなければ、ステップS408yの処理を行う。即ち、ステップS408の処理で得られた式(22)の右辺で表される位置ベクトルbのx座標が0かつy座標が負であるか否かを判定する(ステップS408y)。
【0076】
位置ベクトルbのx座標が0かつy座標が負であれば、位置ベクトルbがステップS408の処理で得られた式(22)の左辺で表される点全体の凸包に入ることはないので、任意に選択された点αを実重複零点とする多項式が実区間多項式F(x)に存在しないといえる(ステップS411)。
【0077】
位置ベクトルbのx座標が0かつy座標が負でなければ、ステップS409の処理を行う。即ち、ステップS408の処理で得られた式(22)の左辺で表される点全体の凸包を上記のアルゴリズムに従って構成する(ステップS409)。
【0078】
次に、ステップS408の処理で得られた式(22)の右辺で表される点が、ステップS409で構成された凸包に入るか否かを判定する(ステップS410)。
【0079】
凸包に入れば、任意に選択された点αを実重複零点とする多項式が実区間多項式F(x)に存在するといえる(ステップS412)。凸包に入らなければ、任意に選択された点αを実重複零点とする多項式が実区間多項式F(x)に存在しないといえる(ステップS411)。
以上で《凸包判定》の説明は終わりである。
【0080】
《エッジ多項式判定》
エッジ多項式に属する多項式g(x)∈F(x)であって、その実重複零点が実区間I上にあるものが存在するか否かを調べる方法について説明する。
ここでは説明の便宜から、j番目の係数を除いて係数が区間数の端点に固定されているエッジ多項式EをAjej(x)+r(x)と表現する〔式(10)参照。但し、既述のとおり、j番目の係数を除いて係数が区間数の端点に固定されているエッジ多項式Eにおいてr(x)には最多2d−1本の多項式が考えられることに留意すること。〕。さらに表現を簡略なものとするため、j番目の係数を除いて係数が区間数の端点に固定されていないことを前提としてインデックスjを明記しないことにする。但し、区間数A=[u,h](=Aj)である。
【0081】
エッジ多項式Eに属する要素エッジ多項式g(x)で実区間Iに実重複零点を有するものが存在するか否かという問題を考える。この問題は、連立方程式(26)がu≦t≦h、x∈Iなる解を持つか否かという問題と同じである。
【数22】
【0082】
連立方程式(26)を、xをパラメータとし、tを変数とする方程式と見る。また、P(x)=e(x)r′(x)−e′(x)r(x)、Q(x)/R(x)=−r(x)/e(x)とおく。ただし、Q(x),R(x)∈Q[x]かつgcd(Q,R)=1とする。なお、Q[x]は、有理係数1変数多項式全体の集合〔変数はx〕を表し、gcd(・)は最大公約多項式を表す。
【0083】
このとき、以下のことが云える。
〈1〉
x=c∈Iでe(c)=e′(c)=0の場合に、連立方程式(26)が解を持つ必要十分条件は、r(c)=r′(c)=0である。連立方程式(26)が解を持つとき、任意の実数tが解となる。換言すると、w(x)=gcd(e(x),r(x),e′(x),r′(x))としたとき、w(x)が実区間Iに零点ρを有するならば、必ずu≦t≦hが成立する。つまり、w(x)が実区間Iに零点ρを有するならば、「要素エッジ多項式g(x)∈Eであって、その実重複零点が実区間I上にあるものが存在する」と云える。w(x)が実区間Iに零点を有するか否かはSturmの定理に基づくアルゴリズムなどで判定可能である。Sturmの定理については、参考文献2を参照のこと。
(参考文献2) 高木貞治著、「代数学講義(改訂新版)」、共立出版、1965.
【0084】
〈2〉
tが区間数の端点uまたはhに固定されている場合。ηをuまたはhとすると、t=ηとした連立方程式(26)の解xがx∈Iであるかを判定すればよい。換言すると、上記〈1〉においてw(x)が実区間Iに零点を有しないとき、式(27)で表される多項式wη(x)が実区間Iに零点ξηを有するか否かをSturmの定理に基づくアルゴリズムなどで判定すればよい。なお、式(27)においてw(x)を除数としているのは、上記〈1〉を経たことに拠る計算効率化のためである。多項式wη(x)が実区間Iに零点を有するならば、「要素エッジ多項式g(x)∈Eであって、その実重複零点が実区間I上にあるものが存在する」と云える。
【数23】
【0085】
〈3〉
x=c∈Iでe(c)≠0かつe′(c)≠0の場合に、連立方程式(26)が解を持つ必要十分条件は、P(c)=0である。連立方程式(26)が解を持つとき、解はちょうど一つでt=Q(c)/R(c)である。
つまるところ、上記〈2〉において多項式wu(x)および多項式wh(x)が実区間Iに零点を有しないとき、式(28)で表されるP1(x)が実区間Iに零点ζを有するか否かをSturmの定理に基づくアルゴリズムなどで判定し、さらにu<Q(ζ)/R(ζ)<hの成立を判定すればよい。Q(ζ)/R(ζ)については上記〈2〉を経ることでQ(ζ)/R(ζ)=ηとなることがないから、u<Q(ζ)/R(ζ)<hの成立を判定すればよく、これは十分に精度を上げた誤差解析付の近似計算、例えば、区間計算で判定可能である。
なお、式(28)において多項式wu(x)、多項式wh(x)、gcd(e(x),e′(x))を除数としているのは、上記〈1〉および〈2〉を経たことに拠る計算効率化のためである。P1(x)が実区間Iに零点ζを有し、かつ、u<Q(ζ)/R(ζ)<hが成立するならば、「要素エッジ多項式g(x)∈Eであって、その実重複零点が実区間I上にあるものが存在する」と云える。P1(x)が実区間Iに零点ζを有さず、あるいは、u<Q(ζ)/R(ζ)<hが成立しないならば、「少なくとも、いま与えられているエッジ多項式について、その実重複擬零点が実区間I上に存在しない」ことが云える。
【数24】
【0086】
なお、P(x)が恒等的に0になる場合、連立方程式(26)は一本の方程式に退化するから、R(β)≠0を満たす1点β∈Iを任意に選択し、この1点βについてu<Q(β)/R(β)<hを判定すればよい。u<Q(β)/R(β)<hが成立するならば、「要素エッジ多項式g(x)∈Eであって、その実重複零点が実区間I上にあるものが存在する」と云える。u<Q(β)/R(β)<hが成立しないならば、「少なくとも、いま与えられているエッジ多項式について、その実重複擬零点が実区間I上に存在しない」と云える。
【0087】
以上の処理〈1〉〜〈3〉を順次に行っていくことで、要素エッジ多項式g(x)∈Eであって、その実重複零点が実区間I上にあるものが存在するか否かが判定できる。このエッジ多項式判定は、エッジ多項式が有限個であるから有限ステップで終了できる。なお、「要素エッジ多項式g(x)∈Eであって、その実重複零点が実区間I上にあるものが存在する」ことが云えた時点でエッジ多項式判定を終了できる。
【0088】
ここで、留意しなければならないのは、既述のとおりg(x)∈E⊂Fであるところ、実区間多項式Fには最多d×2d−1個のエッジ多項式が存在するということである。
【0089】
従ってより詳細には、(a)パラメータjを定める、(b)j番目の係数を除いて係数が区間数の端点に固定されている、最多2d−1本のエッジ多項式について上記処理〈1〉〜〈3〉を行う、(c)1≦j≦dについて(a)および(b)の処理を実施する、というアルゴリズムになる(但し、「要素エッジ多項式g(x)であって、その実重複零点が実区間I上にあるものが存在する」ことが言えた時点でエッジ多項式判定を終了できる。)。
【0090】
以上のアルゴリズムに基づくエッジ多項式判定の処理フローを一例として図3に示す。
【0091】
まず、パラメータjを1に設定する(ステップS500)。
【0092】
次に、j番目の係数を除いて係数が区間数の端点に固定されている、最大で2d−1個のエッジ多項式Eにおいて、未調査(ここで未調査とは、後述のステップS502〜S514の処理が行われていないことを云う。)のエッジ多項式を1個選択する(ステップS501)。この選択されたエッジ多項式が上記Ajej(x)+r(x)において多項式r(x)を1本に固定したものに対応する。また、区間数Aj=[u,h]とする。
【0093】
次に、w(x)=gcd(e(x),r(x),e′(x),r′(x))を求める(ステップS502)。
【0094】
次に、w(x)が実区間Iに零点ρを有するか否かを判定する(ステップS503)。
【0095】
w(x)が実区間Iに零点ρを有する場合、「要素エッジ多項式g(x)∈E⊂F(x)であって、その実重複零点が実区間I上にあるものが存在する」ことが云える(ステップS517)。
【0096】
w(x)が実区間Iに零点ρを有さない場合、式(29)の多項式wu(x)を求める(ステップS504)。
【数25】
【0097】
次に、多項式wu(x)が実区間Iに零点ξuを有するか否かを判定する(ステップS505)。
【0098】
多項式wu(x)が実区間Iに零点ξuを有する場合、「要素エッジ多項式g(x)∈E⊂F(x)であって、その実重複零点が実区間I上にあるものが存在する」ことが云える(ステップS517)。
【0099】
多項式wu(x)が実区間Iに零点ξuを有さない場合、式(30)の多項式wh(x)を求める(ステップS506)。
【数26】
【0100】
次に、多項式wh(x)が実区間Iに零点ξhを有するか否かを判定する(ステップS507)。
【0101】
多項式wh(x)が実区間Iに零点ξhを有する場合、「要素エッジ多項式g(x)∈E⊂F(x)であって、その実重複零点が実区間I上にあるものが存在する」ことが云える(ステップS517)。
【0102】
多項式wh(x)が実区間Iに零点ξhを有さない場合、P(x)=e(x)r′(x)−e′(x)r(x)、Q(x)/R(x)=−r(x)/e(x)を求める。ただし、Q(x),R(x)∈Q[x]かつgcd(Q,R)=1とする(ステップS508)。
【0103】
次に、常等的にP(x)=0が成立するか否かを判定する(ステップS509)。
【0104】
常等的にP(x)=0が成立する場合、R(β)≠0を満たす1点である参照点β∈Iを任意に選択する(ステップS512)。
【0105】
続いて、選択された参照点β∈Iについて、u<Q(β)/R(β)<hが成立するか否かを判定する(ステップS513)。
【0106】
u<Q(β)/R(β)<hが成立する場合、「要素エッジ多項式g(x)∈E⊂F(x)であって、その実重複零点が実区間I上にあるものが存在する」ことが云える(ステップS517)。
【0107】
u<Q(β)/R(β)<hが成立しない場合、「いま与えられているエッジ多項式について、その実重複擬零点が実区間I上に存在しない」ことが云えるので、他のエッジ多項式について処理を進めるべくステップS514への処理に移行する。
【0108】
ステップS509の処理において、常等的にP(x)=0ではない場合、式(31)で表されるP1(x)を求める(ステップS510)。
【数27】
【0109】
続いて、P1(x)が実区間Iに零点ζを有し、かつ、u<Q(ζ)/R(ζ)<hが成立するか否かを判定する(ステップS511)。なお、図面において記号∧は論理積を表す。
【0110】
P1(x)が実区間Iに零点ζを有し、かつ、u<Q(ζ)/R(ζ)<hが成立するならば、「要素エッジ多項式g(x)∈E⊂F(x)であって、その実重複零点が実区間I上にあるものが存在する」と云える(ステップS517)。
【0111】
P1(x)が実区間Iに零点ζを有さず、あるいは、実区間Iに零点ζを有してもu<Q(ζ)/R(ζ)<hが成立しないならば、「いま与えられているエッジ多項式について、その実重複擬零点が実区間I上に存在しない」ことが云えるので、他のエッジ多項式について処理を進めるべくステップS514への処理に移行する。
【0112】
ステップS511またはステップS513の判定が偽であれば、未調査のエッジ多項式があるか否かを判定する(ステップS514)。
【0113】
未調査のエッジ多項式が存在すれば、ステップS501〜S513の処理を行う。未調査のエッジ多項式が存在しなければ、j=dであるか否かを判定する(ステップS515)。
【0114】
j≠dであれば、jに1加えたものを新たなjとして(ステップS516)、ステップS501〜S515の処理を行う。j=dであれば、「要素エッジ多項式g(x)∈F(x)であって、その実重複零点が実区間I上にあるものが存在しない」と云える(ステップS518)。
以上で《エッジ多項式判定》の説明は終わりである。
【0115】
次に、《問題2》について。
問題2は、既述のとおり『与えられた実区間多項式Fに対し、その実重複擬零点全体の集合MZR(F)を決定せよ』である。
【0116】
この問題2に対する解答およびアルゴリズムを説明する。
まず、エッジ多項式判定における処理〈1〉〜〈3〉で説明したことから、下記のことが云える。
【0117】
(ア)
点cがエッジ多項式Eに属する任意の要素エッジ多項式の実重複零点となる必要十分条件は、多項式w(c)=0となることである。但し、w(x)=gcd(ej(x),r(x),e′j(x),r′(x))である。
【0118】
(イ)
点cがエッジ多項式Eに属する要素エッジ多項式ujej(x)+r(x)に対してのみ実重複零点となる必要十分条件は、多項式wu(c)=0となることである〔式(29)参照。〕。
【0119】
(ウ)
点cがエッジ多項式Eに属する要素エッジ多項式hjej(x)+r(x)に対してのみ実重複零点となる必要十分条件は、多項式wh(c)=0となることである〔式(30)参照。〕。
【0120】
(エ)
点cがちょうど一本の要素エッジ多項式φej(x)+r(x)∈E〔但し、φは開区間(uj,hj)に属する。〕の実重複零点となる必要十分条件は、P1(c)=0かつQ(c)/R(c)∈(uj,hj)が成り立つことである〔式(31)参照。〕。
なお、P(x)=ej(x)r′(x)−e′j(x)r(x)が恒等的に0ではないのならば、エッジ多項式の実重複擬零点は有限個の点となることに留意すること〔∵P(c)=0となることが必要条件なので。〕。
【0121】
次に、問題1の解答およびアルゴリズムの説明で明らかになったとおり、『実区間多項式Fおよび実区間Iについて、実区間Iに属する点αで、実区間多項式Fの実重複擬零点ではない点が存在するとき、実区間多項式Fが実区間I内に実重複擬零点を有することと、実区間多項式Fのエッジ多項式の中に、実区間I内に実重複擬零点を有するものが存在することとは同値である』・・・(定理1)ことが云える。
【0122】
また、『実区間多項式Fのj番目の係数を除いて係数が区間数の端点に固定されているエッジ多項式E=Ajej(x)+r(x)〔式(10)参照。但し、Aj=[uj,hj]〕について、その実重複擬零点全体の集合MZR(E)は有限個の閉区間の和集合となる。もし、P(x)=ej(x)r′(x)−e′j(x)r(x)≠0ならば、MZR(E)は有限集合である』・・・(定理2)ことが云える。
【0123】
《定理2の証明》
§1.
まず、最後の「もし、ej(x)r′(x)−e′j(x)r(x)≠0ならば、MZR(E)は有限集合である。」については、次のとおりである。
上記(エ)で、尚書きで説明したとおり、P(x)=ej(x)r′(x)−e′j(x)r(x)が恒等的に0ではないならば、実数cがMZR(E)に入る必要条件はP(c)=0となることであるところ、P(c)=0を満たすcは有限個しかない。従って、MZR(E)は有限集合である。
【0124】
§2.
次に、「MZR(E)は有限個の閉区間の和集合となる。」について。「P(x)が恒等的に0」ではない場合は、1.で証明済みなので、以下、「P(x)は恒等的に0」と仮定する。
上記(ア)〜(ウ)を経ることで、多項式w(x)、多項式wu(x)、多項式wu(x)の全実零点を求め、この集合をSZと表記する。なお、既述のとおりej(x)を恒等的に0ではないとしたことから、多項式w(x)は恒等的に0にならないが、多項式wu(x)、多項式wu(x)は恒等的に0になる場合がありえる〔例えば、r(x)=0かつu=0の場合などである。〕。この場合は実数全体の集合RがMZR(E)となるから、ここではこのような場合を除くとする。多項式w(x)、多項式wu(x)、多項式wu(x)の全実零点は、Sturmの定理に基づくアルゴリズムなどによって求めることができる。
集合SZにおいては、エッジ多項式Eは実重複擬零点を有し、それ以外の点で、もしエッジ多項式Eが実重複擬零点を有する場合、式(26)のtはただ1つに決まり、しかもujともhjとも異なる。
以下、集合SZの要素をα1<α2<・・・<αmと表記する。
開区間(αi,αi+1)の点は、すべてMZR(E)に属する、あるいは、1つもMZR(E)に属さない、のいずれかになる。換言すれば、開区間(αi,αi+1)はMZR(E)の部分集合となる、あるいは、MZR(E)とはまったく共通部分を持たない、のいずれかである。
この事実を、叙述して示す。なお、以下では添え字jを略する。
【0125】
§2.1
『e(c)=e′(c)=0かつc∈(αi,αi+1)ならばR(c)=0』を云う。
もし、e(c)=e′(c)=0となる点cが開区間(αi,αi+1)内にあれば、上記(ア)を経たことから、このような点は集合SZに含まれているから、r(c)≠0またはr′(c)≠0である。
r(c)≠0の場合、r(x)はx−cでは割り切れず、一方、e(c)=0からe(x)はx−cで割り切れるから、R(x)はx−cで割り切れる。つまり、R(c)=0である。
r(c)=0かつr′(c)≠0の場合、r(x)はx−cで割り切れるが、(x−c)2では割り切れない。一方、e(c)=e′(c)=0であるから、e(x)は(x−c)2で割り切れるから、R(x)はx−cで割り切れる。つまり、この場合もR(c)=0である。
【0126】
§2.2
『開区間(αi,αi+1)内の1点cに対してu<Q(c)/R(c)<hならば、開区間(αi,αi+1)内の任意の1点dに対してもu<Q(d)/R(d)<hが成立する』を云う。
開区間(αi,αi+1)内の1点cに対してR(c)≠0ならば、§2.1で説明したことから、(e(c),e′(c))≠(0,0)である。このcに対して、u<Q(c)/R(c)<hならば、任意の点d∈(αi,αi+1)に対して、(e(d),e′(d))≠(0,0)である。しかも、R(d)≠0かつu<Q(d)/R(d)<hとなる。
このことを背理法で示す。
まず、R(x)の零点が開区間(αi,αi+1)内にある場合、そのうち、cに一番近いものをdとする。R(c)≠0より「R(x)は恒等的に0」ではないから、区間(c,d)〔あるいは、区間(d,c)〕において、Q(x)/R(x)はxの連続関数である。しかも、Q(x)およびR(x)は互いに素に取ってあるから、Q(d)≠0である。よって、xがdに近づくとき、Q(x)/R(x)の絶対値はいくらでも大きくなる。従って、中間値の定理から、Q(x)/R(x)がuまたはhに等しくなる点が区間(c,d)〔あるいは、区間(d,c)〕に、即ち、開区間(αi,αi+1)の中に存在することになる。これは、開区間(αi,αi+1)の取り方に矛盾する〔このような点は、すでに上記(ア)〜(ウ)の処理で集合SZに取り込み済みで、開区間(αi,αi+1)の中には存在しない。)。
次に、R(x)の零点が開区間(αi,αi+1)内に無い場合は、Q(x)/R(x)がu以下あるいはh以上となる点dが開区間(αi,αi+1)内に存在したと仮定する。まず、開区間(αi,αi+1)の取り方から、Q(x)/R(x)がuあるいはhとなる点は開区間(αi,αi+1)内には存在しないから、Q(d)/R(d)がuより小さいかあるいはhよりも大きいかのどちらかである。よって、区間(c,d)〔あるいは、区間(d,c)〕に中間値の定理を適用すれば、Q(x)/R(x)がuまたはhに等しくなる点が区間(c,d)〔あるいは、区間(d,c)〕に、即ち、開区間(αi,αi+1)の中に存在することになり、開区間(αi,αi+1)の取り方に矛盾する。
【0127】
§2.3
『開区間(αi,αi+1)内の1点cに対してQ(c)/R(c)<uあるいはh<Q(c)/R(c)ならば、開区間(αi,αi+1)内にはu≦Q(d)/R(d)≦hとなる点は存在しない』を云う。
u≦Q(d)/R(d)≦hとなる点dが開区間(αi,αi+1)内に存在したと仮定する。もし、開区間(αi,αi+1)内にR(x)の零点が存在しないならば、§2.2と同様な議論で、Q(x)/R(x)がuまたはhに等しくなる点は、開区間(αi,αi+1)内には存在しないから、Q(d)/R(d)がuより小さいかあるいはhよりも大きいかのどちらかである。区間(c,d)〔あるいは、区間(d,c)〕に中間値の定理を適用すれば、Q(x)/R(x)がuまたはhに等しくなる点が区間(c,d)〔あるいは、区間(d,c)〕に、即ち、開区間(αi,αi+1)の中に存在することになり、開区間(αi,αi+1)の取り方に矛盾する。
もし、開区間(αi,αi+1)内にR(x)の零点が存在したならば、そのうちdに一番近いものd′を取れば、§2.2と同じ議論によって、やはりQ(x)/R(x)がuまたはhに等しくなる点が区間(c,d)〔あるいは、区間(d,c)〕に、即ち、開区間(αi,αi+1)の中に存在することになり、開区間(αi,αi+1)の取り方に矛盾する。
【0128】
§2.4
以上から、開区間(αi,αi+1)はMZR(E)の部分集合となる、あるいは、MZR(E)とはまったく共通部分を持たない、のいずれかが示せた。
なお、開区間(αi,αi+1)で任意に選択された1点βについて、u<Q(β)/R(β)<hの成立を調べることで、上記いずれが成立しているかを判定できる。
以上で《定理2の証明》は終わりである。
【0129】
さて、定理1および定理2から、次のことが云える。
即ち、『実区間多項式Fと、実区間Jに対し、実区間多項式Fの全てのエッジ多項式は実区間J内に実重複擬零点を有さないと仮定する。このとき、実区間Jの閉包の全ての点が実区間多項式Fの実重複擬零点であるか、あるいは、実区間Jのどの点も実区間多項式Fの実重複擬零点ではないか、のどちらかが成り立つ。』・・・(定理3)ことが云える。
【0130】
《定理3の証明》
実区間Jに属する2点α、βについて,αは実区間多項式Fの実重複擬零点だが、βは実重複擬零点でないと仮定する。すると、定理1から、実区間多項式Fのエッジ多項式Eの中に、MZR(E)∩Jは空集合ではないものが存在する。これは、「実区間多項式Fの全てのエッジ多項式は実区間J内に実重複擬零点を持たない」という仮定に矛盾する。つまり、(1)実区間JはMZR(F)の部分集合である、(2)実区間JとMZR(F)の共通部分は空集合である、のいずれかとなる、(2)の場合および(1)で実区間Jが閉区間のときにはこれで証明できたことになる。
従って、(1)で実区間Jが閉区間ではないとき、つまり、a<bであって、J=(a,b)、[a,b)、(a,b]の場合を考える。どれでも証明は同じなので、端点aが実区間Jに含まれない場合を示す。このとき、K={a}∪J、つまり、J=(a,b)のときK=[a,b)、J=(a,b]のときK=[a,b]とする。定理1をKに対して適用する。もし端点aが実区間多項式Fの実重複擬零点ではないとすると、実区間多項式Fのエッジ多項式Eであって、Kに実重複擬零点を持つものが存在することになる。ところが、端点aは実区間多項式Fの実重複擬零点ではないので、当然、エッジ多項式の実重複擬零点でもない。よって、実区間Jに実重複擬零点を持つものが存在することになる。これは上記仮定に矛盾する。
以上で《定理3の証明》は終わりである。
【0131】
そうすると、問題2に対する大まかな解答は、次のようになる。
まず、実区間多項式Fの全てのエッジ多項式について、その実重複擬零点全体の集合Zを求める〔集合Z決定処理〕(図4のステップS200参照。)。集合Zは、有限個の閉区間の和集合MZR(E)の和集合をとったものとして求めることができる。即ちZ=∪MZR(E)〔エッジ多項式Eは、実区間多項式Fの全てのエッジ多項式を渡る。〕である〔記号∪は和集合を表す。〕。
次いで、集合Zの補集合〔但し、全体集合は実数全体の集合Rとする。〕の各実区間について〔集合Zの補集合は、有限個の開区間の和集合となるから、各開区間をJとする。〕、実区間J上の任意の1点γを選択し、この点γを実重複零点とする多項式が実区間多項式Fに存在するか否かを判定する〔この判定は既述の凸包判定を用いて可能である。〕。これが存在する場合には、点γを含む実区間Jと集合Zとの和集合をとったものを新たな集合Zに置き換える〔MZR(F)決定処理〕(図4のステップS201参照。)。なお、集合Zが実数全体の集合Rの場合には、集合Rが集合MZR(F)となる。
この結果、得られた集合ZがMZR(F)である。
【0132】
《集合Z決定処理》
ここでは、以上の定理等に基づく集合Z=∪MZR(E)を求めるの処理フローを一例として図5および図6に示す。なお、図3および図3に係わる説明も参照のこと。
なお、集合Zの初期値および集合MZR(E)の各初期値は空集合とする。
【0133】
まず、パラメータjを1に設定する(ステップS600)。
【0134】
次に、j番目の係数を除いて係数が区間数の端点に固定されている、最大で2d−1個のエッジ多項式Eにおいて、未調査(ここで未調査とは、後述のステップS602〜S631の処理が行われていないことを云う。)のエッジ多項式を1個選択する(ステップS601)。この選択されたエッジ多項式が上記Ajej(x)+r(x)において多項式r(x)を1本に固定したものに対応する。また、区間数Aj=[uj,hj]とする。
【0135】
次に、多項式w(x)=gcd(ej(x),rj(x),e′j(x),r′j(x))を求める(ステップS602)。
【0136】
次に、w(x)の実零点全体の集合SZを求める(ステップS603)。
【0137】
続いて、式(32)の多項式wu(x)を求める(ステップS604)。
【数28】
【0138】
次に、常等的にwu(x)=0が成立するか否かを判定する(ステップS605)。
【0139】
常等的にwu(x)=0が成立する場合、集合Z=R(実数全体の集合)として集合Z決定処理を終了する(ステップS608)。
【0140】
常等的にwu(x)=0が成立しない場合、式(33)の多項式wh(x)を求める(ステップS606)。
【数29】
【0141】
次に、常等的にwh(x)=0が成立するか否かを判定する(ステップS607)。
【0142】
常等的にwh(x)=0が成立する場合、集合Z=R(実数全体の集合)として集合Z決定処理を終了する(ステップS608)。
【0143】
常等的にwh(x)=0が成立しない場合、多項式wu(x)および多項式wh(x)それぞれの全実零点の集合ZR(wu)および集合ZR(wh)を求める(ステップS609)。
【0144】
続いて、集合SZ、集合ZR(wu)および集合ZR(wh)の和集合をとり、この和集合を新たな集合SZとして置き換える。そして、この集合SZの要素をα1<α2<・・・<αmとする(ステップS610)。
【0145】
続いて、P(x)=ej(x)r′(x)−e′j(x)r(x)、Q(x)/R(x)=−r(x)/ej(x)を求める。ただし、Q(x),R(x)∈Q[x]かつgcd(Q,R)=1とする(ステップS611)。
【0146】
次に、常等的にP(x)=0が成立するか否かを判定する(ステップS612)。
【0147】
常等的にP(x)=0が成立する場合、参照点βiを、R(βi)≠0かつβ1<α1<β2<α2<…<αm<βm+1を満たすように選択する(ステップS618)。但し、パラメータi=1,2,・・・,m+1とする。m=0の場合は、参照点β1は任意に選択できる。
【0148】
続いて、i=1かつm=0かつuj<Q(βi)/R(βi)<hjの成立を判定する(ステップS619)。
【0149】
i=1かつm=0かつuj<Q(βi)/R(βi)<hjが成立するならば、集合Z=R(実数全体の集合)として集合Z決定処理を終了する(ステップS620)。
【0150】
i=1かつm=0かつuj<Q(βi)/R(βi)<hjが成立しない場合、i=1かつm≧1かつuj<Q(βi)/R(βi)<hjの成立を判定する(ステップS621)。
【0151】
i=1かつm≧1かつuj<Q(βi)/R(βi)<hjが成立する場合、集合SZおよび(−∞,α1]の和集合をとり、この和集合を新たな集合SZとして置き換えて(ステップS622)、続いてステップS623の処理を行う。
また、i=1かつm≧1かつuj<Q(βi)/R(βi)<hjが成立しない場合は、続いてステップS623の処理を行う。
【0152】
続いて、パラメータiを2に設定する(ステップS623)。
【0153】
次に、uj<Q(βi)/R(βi)<hjの成立を判定する(ステップS624)。
【0154】
uj<Q(βi)/R(βi)<hjが成立する場合、集合SZおよび閉区間[αi−1,αi]の和集合をとり、この和集合を新たな集合SZとして置き換えて(ステップS625)、続いてステップS626の処理を行う。uj<Q(βi)/R(βi)<hjが成立しない場合、ステップS627の処理を行う。
【0155】
ステップS625の処理に続いて、i=m+1の成立を判定する(ステップS626)。i=m+1が成立する場合、続いてステップS628の処理を行う。i=m+1が成立しない場合、続いてステップS627の処理を行う。
【0156】
ステップS624の処理でuj<Q(βi)/R(βi)<hjが成立しない場合、あるいは、ステップS626の処理でi=m+1が成立しない場合、iに1加えたものを新たなiとして(ステップS627)、ステップS624〜S626の処理を行う。
【0157】
ステップS626の処理でi=m+1が成立した場合、i=m+1かつuj<Q(βi)/R(βi)<hjの成立を判定する(ステップS628)。
【0158】
i=m+1かつuj<Q(βi)/R(βi)<hjが成立した場合、集合SZおよび閉区間[αm,∞)の和集合をとり、この和集合を新たな集合SZとして置き換えて(ステップS629)、続いてステップS630の処理を行う。i=m+1かつuj<Q(βi)/R(βi)<hjが成立しない場合、ステップS630の処理を行う。
【0159】
ステップS612の処理で、常等的にP(x)=0が成立しない場合、式(34)で表されるP1(x)を求め、このP1(x)の全実零点集合{ζ}を求める(ステップS613)。
【数30】
【0160】
続いて、集合{ζ}の中から、未選択(ここで未選択とは、後述のステップS615〜S617の処理が行われていないことを云う。)の零点を1つ選択する(ステップS614)。この選択された零点をζSと表記する。
【0161】
選択された零点ζSについて、uj<Q(ζS)/R(ζS)<hjの成立を判定する(ステップS615)。
【0162】
uj<Q(ζS)/R(ζS)<hjが成立する場合、集合SZおよび{ζS}との和集合をとり、この和集合を新たな集合SZとして置き換えて(ステップS616)、続いてステップS617の処理を行う。uj<Q(ζS)/R(ζS)<hjが成立しない場合、ステップS617の処理を行う。
【0163】
未選択の零点ζSが存在すれば、ステップS614〜S616の処理を行う。未選択の零点ζSが存在しなければ、ステップS630の処理を行う(ステップS617)。
【0164】
ステップS617、ステップS628、ステップS629の処理に続いて、この段階で得られている集合SZおよび集合MZR(E)との和集合をとり、この和集合を新たな集合MZR(E)に置き換える(ステップS630)。
【0165】
続いて、未調査のエッジ多項式があるか否かを判定する(ステップS631)。未調査のエッジ多項式が存在すれば、ステップS601〜S630の処理を行う。
【0166】
未調査のエッジ多項式が存在しなければ、集合Zおよび集合MZR(E)との和集合をとり、この和集合を新たな集合Zとして置き換える(ステップS632)。
【0167】
続いて、j=dであるか否かを判定する(ステップS633)。
【0168】
j≠dであれば、jに1加えたものを新たなjとして(ステップS634)、ステップS601〜S633の処理を行う。j=dであれば、集合Z決定処理を終了する。この段階で得られた集合Zが所望の集合である。
以上で《集合Z決定処理》の説明は終わりである。
【0169】
《MZR(F)決定処理》
続いて、以上のアルゴリズムに基づく集合MZR(F)を求めるの処理フローを一例として図7に示す。
なお、集合Zの初期値は集合Z決定処理で得られた集合であることに留意すること。
【0170】
まず、集合Zが実数全体の集合Rに等しいか否かを判定する(ステップS700)。
【0171】
集合Zが実数全体の集合Rに等しい場合、MZR(F)決定処理を終了する。集合MZR(F)は、この段階で得られた集合Z、つまり集合Rとなる。
【0172】
集合Zが実数全体の集合Rに等しくない場合、集合Zを式(35)のように表現する(ステップS701)。これは集合Z決定処理で得られた集合Zを区間ごとの和集合として書き表したものである。但し、(β0<)α1≦β1<α2≦・・・≦βm(<αm+1)とする。また、式(35)のmは、上記で用いた記号mの意味とは異なることに留意すること。
【数31】
【0173】
次に、(β0<)γ1<α1≦β1<γ2<α2≦・・・≦βm<γm+1(<αm+1)を満たすm+1個の参照点γi∈R〔i=1,2,・・・,m+1〕をとる(ステップS702)。但し、m=0のときは、γ1をどこにとってもよい。
【0174】
続いて、パラメータiを1に設定する(ステップS703)。
【0175】
続いて、i=1かつm=0かつ『γiが実区間多項式Fの実重複擬零点である』の成立を判定する(ステップS704)。『γiが実区間多項式Fの実重複擬零点である』か否かは既述の凸包判定で可能である〔以下同様。〕。
【0176】
i=1かつm=0かつ『γiが実区間多項式Fの実重複擬零点である』が成立するならば、集合Z=R(実数全体の集合)としてMZR(F)決定処理を終了する(ステップS705)。集合MZR(F)は、この段階で得られた集合Z、つまり集合Rとなる。
【0177】
i=1かつm=0かつ『γiが実区間多項式Fの実重複擬零点である』が成立しない場合、i=1かつm≧1かつ『γiが実区間多項式Fの実重複擬零点である』の成立を判定する(ステップS706)。
【0178】
i=1かつm≧1かつ『γiが実区間多項式Fの実重複擬零点である』が成立する場合、集合Zおよび(−∞,β1]の和集合をとり、この和集合を新たな集合Zとして置き換えて(ステップS707)、続いてステップS708の処理を行う。
また、i=1かつm≧1かつ『γiが実区間多項式Fの実重複擬零点である』が成立しない場合は、続いてステップS708の処理を行う。
【0179】
続いて、パラメータiを2に設定する(ステップS708)。
【0180】
次に、『γiが実区間多項式Fの実重複擬零点である』の成立を判定する(ステップS709)。
【0181】
『γiが実区間多項式Fの実重複擬零点である』が成立する場合、集合Zおよび閉区間[βi−1,αi]の和集合をとり、この和集合を新たな集合Zとして置き換えて(ステップS710)、続いてステップS711の処理を行う。『γiが実区間多項式Fの実重複擬零点である』が成立しない場合、ステップS712の処理を行う。
【0182】
ステップS710の処理に続いて、i=m+1の成立を判定する(ステップS711)。i=m+1が成立する場合、続いてステップS713の処理を行う。i=m+1が成立しない場合、続いてステップS712の処理を行う。
【0183】
ステップS709の処理で『γiが実区間多項式Fの実重複擬零点である』が成立しない場合、あるいは、ステップS711の処理でi=m+1が成立しない場合、iに1加えたものを新たなiとして(ステップS712)、ステップS709〜S711の処理を行う。
【0184】
ステップS711の処理でi=m+1が成立した場合、i=m+1かつ『γiが実区間多項式Fの実重複擬零点である』の成立を判定する(ステップS713)。
【0185】
i=m+1かつ『γiが実区間多項式Fの実重複擬零点である』が成立した場合、集合Zおよび閉区間[βm,∞)の和集合をとり、この和集合を新たな集合Zとして置き換えて(ステップS714)、MZR(F)決定処理を終了する。集合MZR(F)は、この段階で得られた集合Zである。i=m+1かつ『γiが実区間多項式Fの実重複擬零点である』が成立しない場合、MZR(F)決定処理を終了する。集合MZR(F)は、この段階で得られた集合Zである。
以上で《MZR(F)決定処理》の説明は終わりである。
【0186】
《Sturmの定理に基づくアルゴリズム》
Sturmの定理に基づくアルゴリズムの適用について概説する。
係数が確定した実係数多項式H(s)について、多項式の列H0(s)、H1(s)、H2(s)、・・・、Hr(s)を生成する。但し、これらの多項式の列は、次の規則に従って生成する。H0(s)=H(s)、H1(s)=dH(s)/ds〔sに関する1階微分である。ライプニッツ記法〕、Hk−1(s)をHk(s)で割った剰余多項式を(符号を変えて)−Hk+1(s)とする。つまり、商の多項式をQk(s)と表すと、Hk−1(s)=Hk(s)Qk(s)−Hk+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)の零点ではないとする(零点であれば、個数を表す式が少し変わるが、本発明においては本質的な部分ではないので略する。)。w(a)−w(b)=0であれば零点が存在しないことが判明し、w(a)−w(b)≠0であれば零点が存在することが判明する。区間S=[a,b]を十分に狭くとることで実零点の所在を決定できる。
以上で《Sturmの定理に基づくアルゴリズム》の概説は終わりである。
【0187】
[第1実施形態]
以下に、本発明の第1実施形態を説明する。第1実施形態は、実区間多項式Fの実重複擬零点が実区間Iに存在するか否かに係わる。
図8は、本実施形態に係わる実重複擬零点位置判定装置(1)のハードウェア構成を例示した構成ブロック図である。
【0188】
図8に例示するように、実重複擬零点位置判定装置(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などの記憶媒体を読み書きできる装置(ドライブ)などを設けるとしてもよい。このようなハードウェア資源を備えた物理的実体としては、汎用コンピュータなどがある。
【0189】
実重複擬零点位置判定装置(1)の外部記憶装置(17)には、実区間多項式の実重複擬零点の位置判定をするのに必要となるプログラムおよびこのプログラムの処理において必要となるデータなどが保存記憶されている。また、これらのプログラムの処理によって得られるデータなどは、RAMや外部記憶装置などに適宜に保存記憶される。以下、演算結果やその格納領域のアドレスなどを記憶するRAM(15)やレジスタなどの装置を単に「メモリ」と呼ぶことにする。
【0190】
より具体的には、実重複擬零点位置判定装置(1)の外部記憶装置(17)〔あるいはROMなど〕には、実区間I上で任意に1点αを選択し、この点αを実重複零点とする多項式が実区間多項式Fに存在するか否かを判定するための選択点多項式判定プログラム、実区間I上に実重複零点を有する要素エッジ多項式が実区間多項式Fに存在するか否かを判定するためのエッジ多項式判定プログラムおよびこれらのプログラムの処理において必要となるデータなどが保存記憶されている。その他、これらのプログラムに基づく処理を制御するための制御プログラムも適宜に保存記憶しておく。
【0191】
実重複擬零点位置判定装置(1)では、外部記憶装置(17)〔あるいはROMなど〕に記憶された各プログラムとこの各プログラムの処理に必要なデータが必要に応じてメモリ(20)に読み込まれて、適宜にCPU(14)で解釈実行・処理される。その結果、CPU(14)が所定の機能(選択点多項式判定部、エッジ多項式判定部、制御部)を実現する。
【0192】
図1、図2、図3、図8、図9を参照して、本実施形態における実区間多項式の実重複擬零点の位置判定処理について説明する。
【0193】
実重複擬零点位置判定装置(1)の外部記憶装置(17)には、予め、実区間多項式F(x)、実区間Iなどが予め保存記憶されているとする。
【0194】
この実施形態では、説明の便宜からより具体的に、実区間多項式F(x)の各項の区間数Aj=[uj,hj]≡{(hj−uj)tj+uj}〔但し、0≦tj≦1、j=0,1,2,・・・,dとする。〕、実区間I=[a,b]がデータとして、予め、実重複擬零点位置判定装置(1)の外部記憶装置(17)に保存記憶されているとする。なお、実区間Iは閉区間、左閉右開区間、左開右閉区間、開区間のいずれでもよい。
【0195】
これらの情報などは、予め実重複擬零点位置判定装置(1)の外部記憶装置(17)に保存記憶しておくのではなく、例えば、入力部(11)から入力されるとしてもよいし、あるいは、これらの情報などを格納した記録媒体からドライブを駆動して読み込むようにしてもよく、適宜に変更可能である。
【0196】
また、これらの情報などに限定する趣旨のものではない。例えば、実区間多項式F(x)の区間数ではなく実区間多項式F(x)そのものを実重複擬零点位置判定装置(1)の外部記憶装置(17)に保存記憶しておくとしてもよい(実区間多項式に属する多項式それぞれを記憶するのではないことに留意する。)。
【0197】
なお、本発明の細部においては、数値計算処理のみならず有理式や区間多項式などの数式処理も必要となるが、数値計算処理および数式処理自体は、公知技術と同様にして達成されるので、その演算処理方法などの詳細な説明は省略する(この点の技術水準を示す数式処理が可能なソフトウェアとしては、例えば、Risa/Asir、Maple(登録商標)、MATHEMATICA(登録商標第2312968号)、Gnuplotなどが挙げられる。Risa/Asirについては、例えばインターネット〈URL:http://hpc.cs.ehime-u.ac.jp/risa/〉[平成18年4月25日検索]を参照のこと。Mapleについては、例えばインターネット〈URL:http://www.cybernet.co.jp/maple/〉[平成18年4月25日検索]を参照のこと。Gnuplotについては、例えばインターネット〈URL: http://www.gnuplot.info/〉[平成18年4月25日検索]を参照のこと。)。
【0198】
まず、実重複擬零点位置判定装置(1)の制御部(190)は、外部記憶装置(17)から全ての区間数Aj={(hj−uj)tj+uj}、実区間I=[a,b]を読み込み、それぞれをメモリ(20)の所定の格納領域に格納しておく。以後、「メモリから○○を読み込む」旨の説明をした場合は、「メモリにおいて○○が格納されている所定の格納領域から○○を読み込む」ことを意味するとする。
【0199】
選択点多項式判定部(141)は、メモリ(20)から、全ての区間数Aj={(hj−uj)tj+uj}、実区間I=[a,b]を読み込み、《凸包判定》で説明したアルゴリズムに従って、実区間I上で任意に選択された1点αについて、この点αを実重複擬零点とする多項式が実区間多項式F(x)に存在するか否かを判定する(図1のステップS100)。
概略を示すと、選択点多項式判定部(141)は、メモリ(20)と協働しながら、次のような動作をする。つまり、実区間I上で任意に1点αを選択し、この点αを実区間多項式F(x)および実区間多項式F(x)を1階微分したものに代入して式(22)の如く式変形を行う。式(22)の左辺で表される点全体の凸包に式(22)の右辺の点が入るかを判定し、その判定結果を得る。判定結果は、「点αを実重複零点とする多項式が実区間多項式F(x)に存在する」あるいは「点αを実重複零点とする多項式が実区間多項式F(x)に存在しない」を表す情報Θである。
【0200】
制御部(190)は、この判定結果情報Θが、点αを実重複零点とする多項式が実区間多項式F(x)に存在するというものである場合には(図2のステップS412参照。)、「実区間I内に実区間多項式Fの実重複擬零点が存在する」ことを表す情報θ(例えばこの場合は、θ=1とする。)をメモリ(20)の所定の格納領域に格納する(図1のステップS103)。なぜなら、この場合、この点αを実重複零点とする実区間多項式F(x)に属する多項式が存在することは、まさに実区間多項式F(x)が実区間I上に実重複擬零点を有することと同じであるからである。
【0201】
制御部(190)は、判定結果情報Θが、点αを実重複零点とする多項式が実区間多項式F(x)に存在しないというものである場合には(図2のステップS411参照。)、ステップS101の処理を実行するように制御する。
【0202】
次に、エッジ多項式判定部(142)は、メモリ(20)から、全ての区間数Aj={(hj−uj)tj+uj}、実区間I=[a,b]を読み込み、《エッジ多項式判定》で説明したアルゴリズムに従って、実区間I上に実重複零点を有する要素エッジ多項式が実区間多項式F(x)に存在するか否かを判定する(図1のステップS101)。
概略を示すと、エッジ多項式判定部(142)は、メモリ(20)と協働しながら、区間数Ajに対するエッジ多項式について次のような動作をする。つまり、多項式w(x)、多項式wu(x)、多項式wu(x)について各実零点が、実区間Iに属するか否かを判定し、その判定結果を得る。判定結果は、「実区間I上に実重複零点を有する要素エッジ多項式が存在する」あるいは「実区間I上に実重複零点を有する要素エッジ多項式が存在しない」を表す情報Γである。判定結果情報Γが「実区間I上に実重複零点を有する要素エッジ多項式が存在する」場合には、エッジ多項式判定部(142)はエッジ多項式判定処理を終了してよい。判定結果情報Γが「実区間I上に実重複零点を有する要素エッジ多項式が存在しない」場合には、多項式P、既約有理式Q/Rを求め、多項式Pが恒等的に0か否かを判定する。多項式Pが恒等的に0であるならばβ∈IについてQ(β)/R(β)∈IE〔IEは、エッジ多項式において端点に固定されていない係数の区間数(但し、端点を除く。)を表す。上記説明では、開区間(u,h)に対応する。〕の成否を判定し、これが成立するならば「実区間I上に実重複零点を有する要素エッジ多項式が存在する」を表す情報Γを得る。多項式Pが恒等的に0でないならば多項式P1を求め、多項式P1の実零点ζについて、ζ∈IかつQ(ζ)/R(ζ)∈IEの成否を判定し、これが成立するならば「実区間I上に実重複零点を有する要素エッジ多項式が存在する」を表す情報Γを得る。いずれのエッジ多項式について上記所定の判定を満足しなかった場合は、「実区間I上に実重複零点を有する要素エッジ多項式が存在しない」を表す情報Γを得る。
【0203】
制御部(190)は、この判定結果情報Γが、実区間I上に実重複零点を有する要素エッジ多項式が存在しないというものである場合には(図3のステップS518参照。)、「実区間I内に実区間多項式Fの実重複擬零点が存在しない」ことを表す情報θ(例えばこの場合は、θ=0とする。)をメモリ(20)の所定の格納領域に格納する(図1のステップS102)。なぜなら、上記理論から明らかなとおり、実区間多項式F(x)に属するいかなる要素エッジ多項式も実区間I上に実重複零点を有しないことは、結局、実区間I内に実区間多項式Fの実重複擬零点が存在しないことと同じであるからである。
【0204】
制御部(190)は、判定結果情報Γが、実区間I上に実重複零点を有する要素エッジ多項式が存在するというものである場合には(図3のステップS517参照。)、「実区間I内に実区間多項式Fの実重複擬零点が存在する」ことを表す情報θ(例えばこの場合は、θ=1とする。)をメモリ(20)の所定の格納領域に格納する(図1のステップS103)。なぜなら、この場合、実区間I上に実重複零点を有する要素エッジ多項式が存在することは、まさに実区間I内に実区間多項式Fの実重複擬零点が存在することと同じであるからである。
【0205】
[第2実施形態]
以下に、本発明の第2実施形態を説明する。第2実施形態は、実区間多項式Fの実重複擬零点全体の集合MZR(F)の決定に係わる。なお、第1実施形態と第2実施形態は両立するから、コンピュータに両者を実装することができる。ここでは説明の便宜から、実区間多項式Fの実重複擬零点全体の集合MZR(F)の決定を第2実施形態としている。
第2実施形態に係わる実重複擬零点位置判定装置(1)〔以下、単に実重複擬零点位置判定装置(1)ということにする。〕のハードウェア構成等は第1実施形態と同様であるから、第2実施形態の本質部分について説明を加える。
【0206】
第2実施形態に係わる実重複擬零点位置判定装置(1)の外部記憶装置(17)〔あるいはROMなど〕には、実区間多項式Fの全てのエッジ多項式について、その実重複擬零点全体の集合Zを求めるための集合Z決定プログラム、集合Zの補集合における全ての実区間Jについて、各実区間J上で任意に1点γを選択し、この点γを実重複零点とする多項式が実区間多項式Fに存在するか否かを判定し、これが存在する場合には点γを含む実区間Jと集合Zとの和集合を求めることで集合MZR(F)を得る集合MZR(F)決定プログラムおよびこれらのプログラムの処理において必要となるデータなどが保存記憶されている。その他、これらのプログラムに基づく処理を制御するための制御プログラムも適宜に保存記憶しておく。
【0207】
実重複擬零点位置判定装置(1)では、外部記憶装置(17)〔あるいはROMなど〕に記憶された各プログラムとこの各プログラムの処理に必要なデータが必要に応じてメモリ(20)に読み込まれて、適宜にCPU(14)で解釈実行・処理される。その結果、CPU(14)が所定の機能(集合Z決定部、集合MZR(F)決定部、制御部)を実現する。
【0208】
図4、図5、図6、図7、図10を参照して、第2実施形態における実区間多項式の実重複擬零点の位置判定処理について説明する。
【0209】
実重複擬零点位置判定装置(1)の外部記憶装置(17)には、予め、実区間多項式F(x)、実区間Iなどが予め保存記憶されているとする。
【0210】
第2実施形態では、説明の便宜からより具体的に、実区間多項式F(x)の各項の区間数Aj=[uj,hj]≡{(hj−uj)tj+uj}〔但し、0≦tj≦1、j=0,1,2,・・・,dとする。〕が、予め、実重複擬零点位置判定装置(1)の外部記憶装置(17)に保存記憶されているとする。
【0211】
まず、実重複擬零点位置判定装置(1)の制御部(190)は、外部記憶装置(17)から全ての区間数Aj={(hj−uj)tj+uj}を読み込み、それぞれをメモリ(20)の所定の格納領域に格納しておく。以後、「メモリから○○を読み込む」旨の説明をした場合は、「メモリにおいて○○が格納されている所定の格納領域から○○を読み込む」ことを意味するとする。
【0212】
集合Z決定部(145)は、メモリ(20)から、全ての区間数Aj={(hj−uj)tj+uj}を読み込み、《集合Z決定処理》で説明したアルゴリズムに従って、実区間多項式Fの全てのエッジ多項式について、その実重複擬零点全体の集合である集合Zを求める(図4のステップS200)。
概略を示すと、集合Z決定部(145)は、メモリ(20)と協働しながら、区間数Ajに対するエッジ多項式について次のような動作をする。つまり、多項式w(x)、多項式wu(x)、多項式wu(x)について全実零点集合の和集合SZを求める。なお、多項式wu(x)、多項式wu(x)についていずれかが恒等的に0ならば集合Zは実数全体の集合Rとして集合Z決定処理を終了してよい。多項式P、既約有理式Q/Rを求め、多項式Pが恒等的に0か否かを判定する。多項式Pが恒等的に0ならば、集合SZの各要素を挟むようにとった各点βについて、Q(β)/R(β)∈IE〔IEは、エッジ多項式において端点に固定されていない係数の区間数(但し、端点を除く。)を表す。上記説明では、開区間(u,h)に対応する。〕の成否を判定し、これが成立するならば、点βに応じた区間を集合SZに加える〔以下、集合と集合との和集合をとることを「加える」と表現する。〕。なお、集合SZの要素が1つも無い場合には、1点βについてQ(β)/R(β)∈IEの成否を判定し、これが成立するならば、集合Zは実数全体の集合Rとして集合Z決定処理を終了してよい。多項式Pが恒等的に0でないならば、多項式P1を求め、多項式P1の全実零点ζSについて、ζS∈IかつQ(ζ)/R(ζ)∈IEの成否を判定し、これが成立するならば、{ζS}を集合SZに加える。エッジ多項式ごとに得られた集合SZの和集合を集合MZR(E)とし、エッジ多項式ごとに得られた集合MZR(E)の和集合を集合Zとする。
【0213】
制御部(190)は、集合Zが得られたら、ステップS201の処理を実行するように制御する。
【0214】
次に、集合MZR(F)決定部(146)は、メモリ(20)から、集合Zを読み込み〔必要に応じて、全ての区間数Aj={(hj−uj)tj+uj}および実区間Jが読み込まれる。〕、《集合MZR(F)決定処理》で説明したアルゴリズムに従って、集合MZR(F)を得る(図4のステップS201)。
概略を示すと、集合MZR(F)決定部(146)は、メモリ(20)と協働しながら、次のような動作をする。つまり、まず、集合Zが実数全体の集合Rであるならば、集合MZR(F)は集合Rであるとして集合MZR(F)決定処理を終了してよい。集合Zが実数全体の集合Rでないならば、集合Zを区間の和集合として書き表し、集合Zの補集合における全ての実区間Jについて、各実区間J上で任意に1点γを選択する。点γを実重複零点とする多項式が実区間多項式Fに存在するか否かを判定し〔凸包判定を用いればよい。〕、これが存在する場合には点γを含む実区間Jを集合Zに加えることで集合MZR(F)を得る。
【0215】
本発明である実区間多項式の実重複擬零点の位置装置、位置判定方法は上述の実施形態に限定されるものではなく、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。また、上記実施形態において説明した処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されるとしてもよい。
【0216】
また、上記実施形態において説明した実重複擬零点位置判定装置における処理機能をコンピュータによって実現する場合、実重複擬零点位置判定装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記実重複擬零点位置判定装置における処理機能がコンピュータ上で実現される。
【0217】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、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)等を用いることができる。
【0218】
また、このプログラムの流通は、例えば、そのプログラムを記録したDVD、CD−ROM等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【0219】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるASP(Application Service Provider)型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの(コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等)を含むものとする。
【0220】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、実重複擬零点位置判定装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【実施例1】
【0221】
以下、本発明である実区間多項式の実重複擬零点の位置判定方法の実施例を、具体例を示して簡単に説明する。以下では、ある桁から先の値を省略する意味の『…』が付されていない小数は、正確な値を表すものとする。
【0222】
この実施例では、多項式e1(x)=Πi=120(x−i),e2(x)=x19,e3(x)=x18として、実区間多項式F(x)を式(36)で与える。式(36)の実区間多項式Fに対し、第2実施形態を適用して集合MZR(F)を決定する。
【数32】
【0223】
実区間多項式Fの全てのエッジ多項式は以下のとおりである。
E1=e1(x)+[−2-23,0]e2(x)
E2=e1(x)+[−2-23,0]e2(x)+2-16e3(x)
E3=e1(x)−2-23e2(x)+[0,2-16]e3(x)
E4=e1(x)+[0,2-16]e3(x)
【0224】
エッジ多項式E1は5個の実重複擬零点を持つ。それをα11,・・・,α15と表すことにする。
α11=10.328…,α12=12.388…,α13=14.451…,
α14=16.524…,α15=18.619…
【0225】
エッジ多項式E2は実重複擬零点を持たない。
【0226】
エッジ多項式E3は3個の実重複擬零点を持つ。
α31=9.313…,α32=10.292…,α33=19.811…
【0227】
エッジ多項式E4は6個の実重複擬零点を持つ。
α41=9.307…,α42=11.365…,α43=13.426…,
α44=15.493…,α45=17.573…,α46=19.694…
【0228】
従って、実区間多項式Fのエッジ多項式は、全部で14個の実重複擬零点を持ち、集合Zは式(37)のとおりとなる。
【数33】
【0229】
なお、αijを大きさの順に並べると以下のとおりである。
α41<α31<α32<α11<α42<α12<α43<α13<α44<α14<α45<α15<α46<α33
【0230】
参照点γ1,γ2,…,γ15を以下のとおりに採る。
γ1=0,γ2=9.31,γ3=10,γ4=10.3,γ5=11,
γ6=12,γ7=13, γ8=14,γ9=15, γ10=16,
γ11=17,γ12=18, γ13=19,γ14=19.8,γ15=20
【0231】
各参照点γiに対し、これらが実区間多項式F(x)の実重複擬零点となるか否かを判定することによって、集合Zは以下のとおりとなる。
Z=[α41,α31]∪[α32,α11]∪[α42,α12]∪[α43,α13]∪[α44,α14]∪[α45,α15]∪[α46,α33]
【0232】
ここで得られた集合Zが集合MZR(F)である。
【実施例2】
【0233】
この実施例では、式(38)の実区間多項式Gに対し、第2実施形態を適用して集合MZR(G)を求める。
【数34】
【0234】
エッジ多項式は全部で12本あり、それらが持つ実重複擬零点は合わせて5個である。小さい方から並べると、以下のとおりである。
α1=−1.00012…, α2=−1.00006…,
α3=−0.99993741…,α4=−0.999937407…,
α5=−0.9998…
【0235】
従って、集合Zは次のとおり与えられる。
Z=[α1,α1]∪[α2,α2]∪[α3,α3]∪[α4,α4]∪[α5,α5]
【0236】
なお、各αiは、以下の要素エッジ多項式Eiの実重複擬零点となっている。
E1=144e1(x)+εe2(x)+[−ε,ε]e3(x)−εe4(x)
E2=144e1(x)+εe2(x)+εe3(x)+[−ε,ε]e4(x)
E3=144e1(x)−εe2(x)−εe3(x)+[−ε,ε]e4(x)
E4=144e1(x)+[−ε,ε]e2(x)+εe3(x)+εe4(x)
E5=144e1(x)−εe2(x)+[−ε,ε]e3(x)+εe4(x)
【0237】
参照点を以下のとおりに採る。
γ1=−2,γ2=−1.0001,γ3=−1,γ4=−0.9999374,γ5=−0.9999,γ6=0
【0238】
各参照点γiに対し、これらが実区間多項式F(x)の実重複擬零点となるか否かを判定することによって、Z=[α1,α5]を得る。
【0239】
ここで得られた集合Zが集合MZR(G)である。
【産業上の利用可能性】
【0240】
本発明は、例えば、多項式の係数に誤差を含むため一意に多項式を決定できない場合において、当該多項式の実重複零点が所定の領域に存在するかを判定したい場合や実区間多項式の実重複擬零点全体の集合を求めたい場合などに用いられ、そのような場合の一例として、ディジタル信号処理におけるディジタルフィルタの周波数特性の解析などに有用である。
【図面の簡単な説明】
【0241】
【図1】実区間I内に実区間多項式Fの実重複擬零点が存在するか否かを判定する実重複擬零点位置判定処理のフローチャート。
【図2】実区間I上で任意に選択された1点を実重複零点とする多項式が実区間多項式Fに存在するか否かを判定する凸包判定処理のフローチャート。
【図3】実区間I上に実重複零点を有する要素エッジ多項式が実区間多項式Fに存在するか否かを判定するエッジ多項式判定処理のフローチャート。
【図4】実区間多項式Fの実重複擬零点全体の集合MZR(F)を決定する実重複擬零点位置判定処理のフローチャート。
【図5】実区間多項式Fの全てのエッジ多項式について、その実重複擬零点全体の集合Zを決定する集合Z決定処理のフローチャート(その1)。
【図6】実区間多項式Fの全てのエッジ多項式について、その実重複擬零点全体の集合Zを決定する集合Z決定処理のフローチャート(その2)。
【図7】集合Zから集合MZR(F)を決定する集合MZR(F)決定処理のフローチャート。
【図8】実重複擬零点位置判定装置(1)のハードウェア構成を例示した構成ブロック図。
【図9】実区間I内に実区間多項式Fの実重複擬零点が存在するか否かを判定する実重複擬零点位置判定処理の処理機能を示す機能ブロック図。
【図10】実区間多項式Fの実重複擬零点全体の集合MZR(F)を決定する実重複擬零点位置判定処理の処理機能を示す機能ブロック図。
【符号の説明】
【0242】
1 実重複擬零点位置判定装置
141 選択点多項式判定部
142 エッジ多項式判定部
145 集合Z決定部
146 集合MZR(F)決定部
190 制御部
【特許請求の範囲】
【請求項1】
実数の閉区間で表される区間数を係数とする一変数実区間多項式〔以下、「実区間多項式F」という。〕および実区間Iを記憶する記憶手段と、
記憶手段に記憶される実区間I上で任意に1点〔以下、「選択点」という。〕を選択し、この選択点を実重複零点とする多項式が実区間多項式Fに存在するか否かを判定する選択点多項式判定手段と、
記憶手段に記憶される実区間I上に実重複零点を有し且つエッジ多項式〔実区間多項式Fの1つの係数を除いた係数が区間数の端点となっている実区間多項式の集合〕に属する多項式が存在するか否かを判定するエッジ多項式判定手段と
を備えた一変数実区間多項式の実重複擬零点の位置判定装置。
【請求項2】
実数の閉区間で表される区間数を係数とする一変数実区間多項式〔以下、「実区間多項式F」という。〕を記憶する記憶手段と、
実区間多項式Fのエッジ多項式〔実区間多項式Fの1つの係数を除いた係数が区間数の端点となっている実区間多項式の集合〕について、その実重複擬零点〔エッジ多項式に属する多項式の実重複零点〕全体の集合Zを求める集合Z決定手段と、
実数全体の集合に対する集合Zの補集合における全ての実区間Jごとに、各実区間J上で任意に1点γを選択して、この点γを実重複零点とする多項式が実区間多項式Fに存在するか否かを判定し、これが存在する場合の点γを含む実区間Jと集合Zとの和集合をとったものを、実区間多項式Fの実重複擬零点〔実区間多項式Fに属する多項式の実重複零点〕全体の集合MZR(F)とする集合MZR(F)決定手段と
を備えた一変数実区間多項式の実重複擬零点の位置判定装置。
【請求項3】
記憶手段には、実数の閉区間で表される区間数を係数とする一変数実区間多項式〔以下、「実区間多項式F」という。〕および実区間Iが記憶され、
選択点多項式判定手段が、記憶手段に記憶される実区間I上で任意に1点〔以下、「選択点」という。〕を選択し、この選択点を実重複零点とする多項式が実区間多項式Fに存在するか否かを判定する選択点多項式判定ステップと、
エッジ多項式判定手段が、選択点多項式判定ステップにおいて選択点を実重複零点とする多項式が実区間多項式Fに存在しないと判定された場合に、記憶手段に記憶される実区間I上に実重複零点を有し且つエッジ多項式〔実区間多項式Fの1つの係数を除いた係数が区間数の端点となっている実区間多項式の集合〕に属する多項式が存在するか否かを判定するエッジ多項式判定ステップと
を有する一変数実区間多項式の実重複擬零点の位置判定方法。
【請求項4】
実区間多項式Fの各区間数をそれぞれの両端点および内分比で表すとして、
上記選択点多項式判定ステップは、
選択点を実区間多項式Fおよび実区間多項式Fを変数で1階微分したものに代入した連立方程式について、内分比に関する連立方程式の解を位置ベクトルの終点〔以下、「点」という。〕と見立てて、各区間数ごとに内分比を含む項(内分比項)と含まない項(非内分比項)に分け、内分比項の和で定まる点全体の凸包に、非内分比項の和で定まる点が入るか否かの判定をすることによって、選択点を実重複零点に有する多項式が実区間多項式Fに存在するか否かを判定するものである
請求項3に記載の一変数実区間多項式の実重複擬零点の位置判定方法。
【請求項5】
上記エッジ多項式判定ステップは、
実区間多項式Fおよび実区間多項式Fを変数で1階微分したものの連立方程式について、その解の存在条件に基づいて得られる多項式の零点が実区間Iに属するか否かを判定するステップを含む
請求項3または請求項4に記載の一変数実区間多項式の実重複擬零点の位置判定方法。
【請求項6】
上記エッジ多項式判定ステップは、
実区間多項式Fおよび実区間多項式Fを変数で1階微分したものの連立方程式について、その解の存在条件に基づいて得られる多項式の零点において、当該解がエッジ多項式において端点に固定されていない係数である区間数に属するか否かを判定するステップを含む
請求項5に記載の一変数実区間多項式の実重複擬零点の位置判定方法。
【請求項7】
記憶手段には、実数の閉区間で表される区間数を係数とする一変数実区間多項式〔以下、「実区間多項式F」という。〕が記憶され、
集合Z決定手段が、実区間多項式Fのエッジ多項式〔実区間多項式Fの1つの係数を除いた係数が区間数の端点となっている実区間多項式の集合〕について、その実重複擬零点〔エッジ多項式に属する多項式の実重複零点〕全体の集合Zを求める集合Z決定ステップと、
集合MZR(F)決定手段が、実数全体の集合に対する集合Zの補集合における全ての実区間Jごとに、各実区間J上で任意に1点γを選択して、この点γを実重複零点とする多項式が実区間多項式Fに存在するか否かを判定し、これが存在する場合の点γを含む実区間Jと集合Zとの和集合をとったものを、実区間多項式Fの実重複擬零点〔実区間多項式Fに属する多項式の実重複零点〕全体の集合MZR(F)とする集合MZR(F)決定ステップと
を有する一変数実区間多項式の実重複擬零点の位置判定方法。
【請求項8】
上記集合Z決定ステップは、
実区間多項式Fおよび実区間多項式Fを変数で1階微分したものの連立方程式について、その解の存在条件に基づいて得られる多項式の零点の集合SZを求めるステップを含む
請求項7に記載の一変数実区間多項式の実重複擬零点の位置判定方法。
【請求項9】
上記集合Z決定ステップは、
実区間多項式Fおよび実区間多項式Fを変数で1階微分したものの連立方程式について、その解の存在条件に基づいて得られる多項式の零点において、当該解がエッジ多項式において端点に固定されていない係数である区間数に属する場合に、当該零点あるいは当該零点を含む実区間を集合SZに加えるステップを含む
請求項8に記載の一変数実区間多項式の実重複擬零点の位置判定方法。
【請求項10】
上記集合MZR(F)決定ステップにおいて、点γを実重複零点とする多項式が実区間多項式Fに存在するか否かを判定は、
実区間多項式Fの各区間数をそれぞれの両端点および内分比で表すとして、点γを実区間多項式Fおよび実区間多項式Fを変数で1階微分したものに代入した連立方程式について、内分比に関する連立方程式の解を位置ベクトルの終点〔以下、「点」という。〕と見立てて、各区間数ごとに内分比を含む項(内分比項)と含まない項(非内分比項)に分け、内分比項の和で定まる点全体の凸包に、非内分比項の和で定まる点が入るか否かの判定をすることによって、点γを実重複零点に有する多項式が実区間多項式Fに存在するか否かを判定するものである
請求項7から請求項9のいずれかに記載の一変数実区間多項式の実重複擬零点の位置判定方法。
【請求項11】
コンピュータに請求項3から請求項10のいずれかに記載の一変数実区間多項式の実重複擬零点の位置判定方法を実行させるための、一変数実区間多項式の実重複擬零点の位置判定プログラム。
【請求項12】
請求項11に記載の、一変数実区間多項式の実重複擬零点の位置判定プログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項1】
実数の閉区間で表される区間数を係数とする一変数実区間多項式〔以下、「実区間多項式F」という。〕および実区間Iを記憶する記憶手段と、
記憶手段に記憶される実区間I上で任意に1点〔以下、「選択点」という。〕を選択し、この選択点を実重複零点とする多項式が実区間多項式Fに存在するか否かを判定する選択点多項式判定手段と、
記憶手段に記憶される実区間I上に実重複零点を有し且つエッジ多項式〔実区間多項式Fの1つの係数を除いた係数が区間数の端点となっている実区間多項式の集合〕に属する多項式が存在するか否かを判定するエッジ多項式判定手段と
を備えた一変数実区間多項式の実重複擬零点の位置判定装置。
【請求項2】
実数の閉区間で表される区間数を係数とする一変数実区間多項式〔以下、「実区間多項式F」という。〕を記憶する記憶手段と、
実区間多項式Fのエッジ多項式〔実区間多項式Fの1つの係数を除いた係数が区間数の端点となっている実区間多項式の集合〕について、その実重複擬零点〔エッジ多項式に属する多項式の実重複零点〕全体の集合Zを求める集合Z決定手段と、
実数全体の集合に対する集合Zの補集合における全ての実区間Jごとに、各実区間J上で任意に1点γを選択して、この点γを実重複零点とする多項式が実区間多項式Fに存在するか否かを判定し、これが存在する場合の点γを含む実区間Jと集合Zとの和集合をとったものを、実区間多項式Fの実重複擬零点〔実区間多項式Fに属する多項式の実重複零点〕全体の集合MZR(F)とする集合MZR(F)決定手段と
を備えた一変数実区間多項式の実重複擬零点の位置判定装置。
【請求項3】
記憶手段には、実数の閉区間で表される区間数を係数とする一変数実区間多項式〔以下、「実区間多項式F」という。〕および実区間Iが記憶され、
選択点多項式判定手段が、記憶手段に記憶される実区間I上で任意に1点〔以下、「選択点」という。〕を選択し、この選択点を実重複零点とする多項式が実区間多項式Fに存在するか否かを判定する選択点多項式判定ステップと、
エッジ多項式判定手段が、選択点多項式判定ステップにおいて選択点を実重複零点とする多項式が実区間多項式Fに存在しないと判定された場合に、記憶手段に記憶される実区間I上に実重複零点を有し且つエッジ多項式〔実区間多項式Fの1つの係数を除いた係数が区間数の端点となっている実区間多項式の集合〕に属する多項式が存在するか否かを判定するエッジ多項式判定ステップと
を有する一変数実区間多項式の実重複擬零点の位置判定方法。
【請求項4】
実区間多項式Fの各区間数をそれぞれの両端点および内分比で表すとして、
上記選択点多項式判定ステップは、
選択点を実区間多項式Fおよび実区間多項式Fを変数で1階微分したものに代入した連立方程式について、内分比に関する連立方程式の解を位置ベクトルの終点〔以下、「点」という。〕と見立てて、各区間数ごとに内分比を含む項(内分比項)と含まない項(非内分比項)に分け、内分比項の和で定まる点全体の凸包に、非内分比項の和で定まる点が入るか否かの判定をすることによって、選択点を実重複零点に有する多項式が実区間多項式Fに存在するか否かを判定するものである
請求項3に記載の一変数実区間多項式の実重複擬零点の位置判定方法。
【請求項5】
上記エッジ多項式判定ステップは、
実区間多項式Fおよび実区間多項式Fを変数で1階微分したものの連立方程式について、その解の存在条件に基づいて得られる多項式の零点が実区間Iに属するか否かを判定するステップを含む
請求項3または請求項4に記載の一変数実区間多項式の実重複擬零点の位置判定方法。
【請求項6】
上記エッジ多項式判定ステップは、
実区間多項式Fおよび実区間多項式Fを変数で1階微分したものの連立方程式について、その解の存在条件に基づいて得られる多項式の零点において、当該解がエッジ多項式において端点に固定されていない係数である区間数に属するか否かを判定するステップを含む
請求項5に記載の一変数実区間多項式の実重複擬零点の位置判定方法。
【請求項7】
記憶手段には、実数の閉区間で表される区間数を係数とする一変数実区間多項式〔以下、「実区間多項式F」という。〕が記憶され、
集合Z決定手段が、実区間多項式Fのエッジ多項式〔実区間多項式Fの1つの係数を除いた係数が区間数の端点となっている実区間多項式の集合〕について、その実重複擬零点〔エッジ多項式に属する多項式の実重複零点〕全体の集合Zを求める集合Z決定ステップと、
集合MZR(F)決定手段が、実数全体の集合に対する集合Zの補集合における全ての実区間Jごとに、各実区間J上で任意に1点γを選択して、この点γを実重複零点とする多項式が実区間多項式Fに存在するか否かを判定し、これが存在する場合の点γを含む実区間Jと集合Zとの和集合をとったものを、実区間多項式Fの実重複擬零点〔実区間多項式Fに属する多項式の実重複零点〕全体の集合MZR(F)とする集合MZR(F)決定ステップと
を有する一変数実区間多項式の実重複擬零点の位置判定方法。
【請求項8】
上記集合Z決定ステップは、
実区間多項式Fおよび実区間多項式Fを変数で1階微分したものの連立方程式について、その解の存在条件に基づいて得られる多項式の零点の集合SZを求めるステップを含む
請求項7に記載の一変数実区間多項式の実重複擬零点の位置判定方法。
【請求項9】
上記集合Z決定ステップは、
実区間多項式Fおよび実区間多項式Fを変数で1階微分したものの連立方程式について、その解の存在条件に基づいて得られる多項式の零点において、当該解がエッジ多項式において端点に固定されていない係数である区間数に属する場合に、当該零点あるいは当該零点を含む実区間を集合SZに加えるステップを含む
請求項8に記載の一変数実区間多項式の実重複擬零点の位置判定方法。
【請求項10】
上記集合MZR(F)決定ステップにおいて、点γを実重複零点とする多項式が実区間多項式Fに存在するか否かを判定は、
実区間多項式Fの各区間数をそれぞれの両端点および内分比で表すとして、点γを実区間多項式Fおよび実区間多項式Fを変数で1階微分したものに代入した連立方程式について、内分比に関する連立方程式の解を位置ベクトルの終点〔以下、「点」という。〕と見立てて、各区間数ごとに内分比を含む項(内分比項)と含まない項(非内分比項)に分け、内分比項の和で定まる点全体の凸包に、非内分比項の和で定まる点が入るか否かの判定をすることによって、点γを実重複零点に有する多項式が実区間多項式Fに存在するか否かを判定するものである
請求項7から請求項9のいずれかに記載の一変数実区間多項式の実重複擬零点の位置判定方法。
【請求項11】
コンピュータに請求項3から請求項10のいずれかに記載の一変数実区間多項式の実重複擬零点の位置判定方法を実行させるための、一変数実区間多項式の実重複擬零点の位置判定プログラム。
【請求項12】
請求項11に記載の、一変数実区間多項式の実重複擬零点の位置判定プログラムを記録したコンピュータ読み取り可能な記録媒体。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【公開番号】特開2007−299264(P2007−299264A)
【公開日】平成19年11月15日(2007.11.15)
【国際特許分類】
【出願番号】特願2006−127588(P2006−127588)
【出願日】平成18年5月1日(2006.5.1)
【出願人】(000004226)日本電信電話株式会社 (13,992)
【Fターム(参考)】
【公開日】平成19年11月15日(2007.11.15)
【国際特許分類】
【出願日】平成18年5月1日(2006.5.1)
【出願人】(000004226)日本電信電話株式会社 (13,992)
【Fターム(参考)】
[ Back to top ]