(57)【特許請求の範囲】
【請求項１】
実数全体の集合をＲとし、a1,a2,…,anをそれぞれ予め与えられた有限の精度で表現される実数とし、e0(x),e1(x),…,en(x)をそれぞれ予め与えられた一変数実多項式とし、一変数実多項式
【数１】
0004778486.tif 000041
が複素数全体の集合内の有界で閉な領域Ｄに零点を持たないとして、一変数実多項式の集合
【数２】
0004778486.tif 000042
のうち、上記領域Ｄに零点を持ち、かつ、上記一変数実多項式f(x)との距離d(f(x), f~(x))が最小となる一変数実多項式f~(x)について、その最小距離Tを算出する多項式間距離算出装置であり、
上記一変数多項式f(x)とf~(x)との上記距離d(f(x), f~(x))は、
d(f(x), f~(x))＝max｛|a1-b1|, |a2-b2|,…,|an-bn|｝
であり、
上記a1,a2,…,anと、上記e0(x),e1(x),…,en(x)と、上記領域Ｄの境界を構成する有理式で表される有限個の区分境界Ｃ1,Ｃ2,…,ＣKの有理式による表示γｋ（ただし、γｋは予め定めた実数の範囲SkからCkへの単射である）とを記憶する記憶手段と、
上記記憶手段から多項式e0(x),e1(x),…,en(x)を読み込み、
【数３】
0004778486.tif 000043
を
【数５６】
0004778486.tif 000044
と表現したときの各係数ｗｉを０とした連立一次方程式の解が存在するか否かを判定し、存在する場合には上記最小距離T=d(f,0)とし、Tの値を上記記憶手段に格納する恒等式調査手段と、
各上記区分境界の有理式による表示γk〔但し、ｋ=1,2,…,K〕と集合｛Σj=1n±ej(x)｝（ただし、±は＋と−の全ての組み合わせを表す）に属する多項式q(x)との組み合わせ毎に、
【数４】
0004778486.tif 000045
（ただし、Reは複素数の実部、Imは複素数の虚部を表す）の解ｓを求め、求めたｓを第一方程式f(x)+tq(x)=0の零点の候補ｓとして上記記憶手段に格納する第一候補探索手段と、
上記第一候補探索手段によって得られた各上記第一方程式の零点の候補ｓに対応する
【数５７】
0004778486.tif 000046
または
【数５８】
0004778486.tif 000047
の絶対値を計算し、それらの中で最小の値|t0|を求め、|t0|が上記記憶手段に格納されたTの値よりも小さい場合には、当該最小の値|t0|で上記記憶手段に格納された最小距離Tの値を書き換える第一距離候補決定手段と、
各上記区分境界の有理式による表示γkと集合｛1,2,…,n｝に属する整数μと集合{Σ1≦j≦n,j≠μ±ej(x)}に属する多項式pμ(x)との組み合わせ毎に、
【数５０】
0004778486.tif 000048
が定数ｃであるか否かを判定し、定数ｃの場合は上記式（３６）の分母が０となる点以外の任意のｓ∈Ｓｋで、かつ、｜ｔμ（γｋ（ｓ））｜＜｜ｃ｜を満たすものを第二方程式f(x)+tμeμ(x)+τpμ(x)=0の零点の候補とし、この零点の候補を記憶手段に格納する第二候補探索手段と、
上記第二候補探索手段によって得られた各上記第二方程式の零点の候補に対応するγｋ（ｓ）を
【数３１】
0004778486.tif 000049
のｘに代入して得られる二元連立一次方程式のｔ及びｔμの解t<solution>及びtμ<solution>を計算し、計算したt<solution>のうち最小のものを求め、その値が上記記憶手段に格納されたTの値よりも小さい場合には、当該最小の値t<solution>で上記記憶手段に格納された最小距離Tの値を書き換える第二距離候補決定手段と、
を備えた多項式間距離算出装置。
【請求項２】
実数全体の集合をＲとし、a1,a2,…,anをそれぞれ予め与えられた有限の精度で表現される実数とし、e0(x),e1(x),…,en(x)をそれぞれ予め与えられた一変数実多項式とし、一変数実多項式
【数１】
0004778486.tif 000050
が複素数全体の集合内の有界で閉な領域Ｄに零点を持たないとして、一変数実多項式の集合
【数２】
0004778486.tif 000051
のうち、上記領域Ｄに零点を持ち、かつ、上記一変数実多項式f(x)との距離d(f(x), f~(x))が最小となる一変数実多項式f~(x)について、その最小距離Tを算出する多項式間距離算出方法であり、
上記一変数多項式f(x)とf~(x)との上記距離d(f(x), f~(x))は、
d(f(x), f~(x))＝max｛|a1-b1|, |a2-b2|,…,|an-bn|｝
であり、
記憶手段手段には、上記a1,a2,…,anと、上記e0(x),e1(x),…,en(x)と、上記領域Ｄの境界を構成する有理式で表される有限個の区分境界Ｃ1,Ｃ2,…,ＣKの有理式による表示γｋ（ただし、γｋは予め定めた実数の範囲SkからCkへの単射である）とを記憶され、
恒等式調査手段が、上記記憶手段から多項式e0(x),e1(x),…,en(x)を読み込み、
【数３】
0004778486.tif 000052
を
【数５６】
0004778486.tif 000053
と表現したときの各係数ｗｉを０とした連立一次方程式の解が存在するか否かを判定し、存在する場合には上記最小距離T=d(f,0)とし、Tの値を上記記憶手段に格納する恒等式調査ステップと、
第一候補探索手段が、各上記区分境界の有理式による表示γk〔但し、ｋ=1,2,…,K〕と集合｛Σj=1n±ej(x)｝（ただし、±は＋と−の全ての組み合わせを表す）に属する多項式q(x)との組み合わせ毎に、
【数４】
0004778486.tif 000054
（ただし、Reは複素数の実部、Imは複素数の虚部を表す）の解ｓを求め、求めたｓを第一方程式f(x)+tq(x)=0の零点の候補ｓとして上記記憶手段に格納する第一候補探索ステップと、
第一距離候補決定手段が、上記第一候補探索手段によって得られた各上記第一方程式の零点の候補ｓに対応する
【数５７】
0004778486.tif 000055
または
【数５８】
0004778486.tif 000056
の絶対値を計算し、それらの中で最小の値|t0|を求め、|t0|が上記記憶手段に格納されたTの値よりも小さい場合には、当該最小の値|t0|で上記記憶手段に格納された最小距離Tの値を書き換える第一距離候補決定ステップと、
第二候補探索手段が、各上記区分境界の有理式による表示γkと集合｛1,2,…,n｝に属する整数μと集合{Σ1≦j≦n,j≠μ±ej(x)}に属する多項式pμ(x)との組み合わせ毎に、
【数５０】
0004778486.tif 000057
が定数ｃであるか否かを判定し、定数ｃの場合は上記式（３６）の分母が０となる点以外の任意のｓ∈Ｓｋで、かつ、｜ｔμ（γｋ（ｓ））｜＜｜ｃ｜を満たすものを第二方程式f(x)+tμeμ(x)+τpμ(x)=0の零点の候補とし、この零点の候補を記憶手段に格納する第二候補探索ステップと、
第二距離候補決定手段が、上記第二候補探索手段によって得られた各上記第二方程式の零点の候補に対応するγｋ（ｓ）を
【数３１】
0004778486.tif 000058
のｘに代入して得られる二元連立一次方程式のｔ及びｔμの解t<solution>及びtμ<solution>を計算し、計算したt<solution>のうち最小のものを求め、その値が上記記憶手段に格納されたTの値よりも小さい場合には、当該最小の値t<solution>で上記記憶手段に格納された最小距離Tの値を書き換える第二距離候補決定ステップと、
を有する多項式間距離算出方法。
【請求項３】
実数全体の集合をＲとし、a1,a2,…,anをそれぞれ予め与えられた有限の精度で表現される実数とし、e0(x),e1(x),…,en(x)をそれぞれ予め与えられた一変数実多項式とし、一変数実多項式
【数１】
0004778486.tif 000059
が複素数全体の集合内の有界で閉な領域Ｄに零点を持たないとして、一変数実多項式の集合
【数２】
0004778486.tif 000060
のうち、上記領域Ｄに零点を持ち、かつ、上記一変数実多項式f(x)との距離d(f(x), f~(x))が最小となる一変数実多項式f~(x)を算出する一変数最近実多項式算出装置であり、
上記一変数多項式f(x)とf~(x)との上記距離d(f(x), f~(x))は、
d(f(x), f~(x))＝max｛|a1-b1|, |a2-b2|,…,|an-bn|｝
であり、
上記a1,a2,…,anと、上記e0(x),e1(x),…,en(x)と、上記領域Ｄの境界を構成する有理式で表される有限個の区分境界Ｃ1,Ｃ2,…,ＣKの有理式による表示γｋ（ただし、γｋは予め定めた実数の範囲SkからCkへの単射である）とを記憶する記憶手段と、
上記記憶手段から多項式e0(x),e1(x),…,en(x)を読み込み、
【数３】
0004778486.tif 000061
を
【数５６】
0004778486.tif 000062
と表現したときの各係数ｗｉを０とした連立一次方程式の解が存在するか否かを判定し、存在する場合には上記最小距離T=d(f,0)とし、Tの値を上記記憶手段に格納する恒等式調査部と、
各上記区分境界の有理式による表示γk〔但し、ｋ=1,2,…,K〕と集合｛Σj=1n±ej(x)｝（ただし、±は＋と−の全ての組み合わせを表す）に属する多項式q(x)との組み合わせ毎に、
【数４】
0004778486.tif 000063
（ただし、Reは複素数の実部、Imは複素数の虚部を表す）の解ｓを求め（旧請求項５）、求めたｓを第一方程式f(x)+tq(x)=0の零点の候補ｓとして上記記憶手段に格納する第一候補探索手段と、
上記第一候補探索手段によって得られた各上記第一方程式の零点の候補ｓに対応する
【数５７】
0004778486.tif 000064
または
【数５８】
0004778486.tif 000065
の絶対値を計算し、それらの中で最小の値|t0|求め、|t0|が上記記憶手段に格納されたTの値よりも小さい場合には、当該最小の値|t0|で上記記憶手段に格納された最小距離Tの値を書き換え、上記記憶手段に格納された最小距離Tの値を上記|t0|で書き変えた場合に、当該最小の値|t0|を与えたときの上記q(x)を用いて、
【数４９】
0004778486.tif 000066
により上記最小距離Tを与える一変数実多項式f~(x)を求め、これを記憶手段に格納する第一多項式候補決定手段と、
各上記区分境界の有理式による表示γkと集合｛1,2,…,n｝に属する整数μと集合{Σ1≦j≦n,j≠μ±ej(x)}に属する多項式pμ(x)との組み合わせ毎に、
【数５０】
0004778486.tif 000067
が定数ｃであるか否かを判定し、定数ｃの場合は上記式（３６）の分母が０となる点以外の任意のｓ∈Ｓｋで、かつ、｜ｔμ（γｋ（ｓ））｜＜｜ｃ｜を満たすものを第二方程式f(x)+tμeμ(x)+τpμ(x)=0の零点の候補とし、この零点の候補を記憶手段に格納する第二候補探索手段と、
上記第二候補探索手段によって得られた各上記第二方程式の零点の候補に対応するγｋ（ｓ）を
【数３１】
0004778486.tif 000068
のｘに代入して得られる二元連立一次方程式のｔ及びｔμの解t<solution>及びtμ<solution>を計算し、計算したt<solution>のうち最小のものを求め、その値が上記記憶手段に格納されたTの値よりも小さい場合には、当該最小の値t<solution>で上記記憶手段に格納された最小距離Tの値を書き換え、上記記憶手段に格納された最小距離Tの値を上記最小の値t<solution>により書き換えた場合に、当該最小の値t<solution>を与えたときの解tμ<solution>(以下、tμ<solution>,0とする）及びpμ(x)（以下、pμ,0(x)とする）を用いて、
【数５２】
0004778486.tif 000069
により上記最小距離Tを与える一変数実多項式f~(x)を求め、これを記憶手段に格納する第二多項式候補決定手段と、
を備えた一変数最近多項式算出装置。
【請求項４】
実数全体の集合をＲとし、a1,a2,…,anをそれぞれ予め与えられた有限の精度で表現される実数とし、e0(x),e1(x),…,en(x)をそれぞれ予め与えられた一変数実多項式とし、一変数実多項式
【数１】
0004778486.tif 000070
が複素数全体の集合内の有界で閉な領域Ｄに零点を持たないとして、一変数実多項式の集合
【数２】
0004778486.tif 000071
のうち、上記領域Ｄに零点を持ち、かつ、上記一変数実多項式f(x)との距離d(f(x), f~(x))が最小となる一変数実多項式f~(x)を算出する一変数最近実多項式算出方法であり、
上記一変数多項式f(x)とf~(x)との上記距離d(f(x), f~(x))は、
d(f(x), f~(x))＝max｛|a1-b1|, |a2-b2|,…,|an-bn|｝
であり、
記憶手段には上記a1,a2,…,anと、上記e0(x),e1(x),…,en(x)と、上記領域Ｄの境界を構成する有理式で表される有限個の区分境界Ｃ1,Ｃ2,…,ＣKの有理式による表示γｋ（ただし、γｋは予め定めた実数の範囲SkからCkへの単射である）とを記憶され、
恒等式調査部が、上記記憶手段から多項式e0(x),e1(x),…,en(x)を読み込み、
【数３】
0004778486.tif 000072
を
【数５６】
0004778486.tif 000073
と表現したときの各係数ｗｉを０とした連立一次方程式の解が存在するか否かを判定し、存在する場合には上記最小距離T=d(f,0)とし、Tの値を上記記憶手段に格納する恒等式調査ステップと、
第一候補探索手段が、各上記区分境界の有理式による表示γk〔但し、ｋ=1,2,…,K〕と集合｛Σj=1n±ej(x)｝（ただし、±は＋と−の全ての組み合わせを表す）に属する多項式q(x)との組み合わせ毎に、
【数４】
0004778486.tif 000074
（ただし、Reは複素数の実部、Imは複素数の虚部を表す）の解ｓを求め（旧請求項５）、求めたｓを第一方程式f(x)+tq(x)=0の零点の候補ｓとして上記記憶手段に格納する第一候補探索ステップと、
第一多項式候補決定手段が、上記第一候補探索手段によって得られた各上記第一方程式の零点の候補ｓに対応する
【数５７】
0004778486.tif 000075
または
【数５８】
0004778486.tif 000076
の絶対値を計算し、それらの中で最小の値|t0|求め、|t0|が上記記憶手段に格納されたTの値よりも小さい場合には、当該最小の値|t0|で上記記憶手段に格納された最小距離Tの値を書き換え、上記記憶手段に格納された最小距離Tの値を上記|t0|で書き変えた場合に、当該最小の値|t0|を与えたときの上記q(x)を用いて、
【数４９】
0004778486.tif 000077
により上記最小距離Tを与える一変数実多項式f~(x)を求め、これを記憶手段に格納する第一多項式候補決定ステップと、
第二候補探索手段が、各上記区分境界の有理式による表示γkと集合｛1,2,…,n｝に属する整数μと集合{Σ1≦j≦n,j≠μ±ej(x)}に属する多項式pμ(x)との組み合わせ毎に、
【数５０】
0004778486.tif 000078
が定数ｃであるか否かを判定し、定数ｃの場合は上記式（３６）の分母が０となる点以外の任意のｓ∈Ｓｋで、かつ、｜ｔμ（γｋ（ｓ））｜＜｜ｃ｜を満たすものを第二方程式f(x)+tμeμ(x)+τpμ(x)=0の零点の候補とし、この零点の候補を記憶手段に格納する第二候補探索ステップと、
第二多項式候補決定手段が、上記第二候補探索手段によって得られた各上記第二方程式の零点の候補に対応するγｋ（ｓ）を
【数３１】
0004778486.tif 000079
のｘに代入して得られる二元連立一次方程式のｔ及びｔμの解t<solution>及びtμ<solution>を計算し、計算したt<solution>のうち最小のものを求め、その値が上記記憶手段に格納されたTの値よりも小さい場合には、当該最小の値t<solution>で上記記憶手段に格納された最小距離Tの値を書き換え、上記記憶手段に格納された最小距離Tの値を上記最小の値t<solution>により書き換えた場合に、当該最小の値t<solution>を与えたときの解tμ<solution>(以下、tμ<solution>,0とする）及びpμ(x)（以下、pμ,0(x)とする）を用いて、
【数５２】
0004778486.tif 000080
により上記最小距離Tを与える一変数実多項式f~(x)を求め、これを記憶手段に格納する第二多項式候補決定ステップと、
を備えた一変数最近多項式算出方法。
【請求項５】
請求項１に記載された多項式間距離算出装置としてコンピュータを機能させるための多項式間距離算出プログラム。
【請求項６】
請求項５に記載の多項式間距離算出プログラムを記録した、コンピュータに読み取り可能な記録媒体。
【請求項７】
請求項３に記載された一変数最近実多項式算出装置としてコンピュータを機能させるための一変数最近実多項式算出プログラム。
【請求項８】
請求項７に記載の一変数最近実多項式算出プログラムを記録した、コンピュータに読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複素数全体の集合内の指定された領域に零点を持つ一変数実多項式のうち、上記領域に零点を持たない或る一変数実多項式ｆに最も近い一変数実多項式ｆ~について、一変数実多項式ｆと一変数実多項式ｆ~との距離を求める技術に関する。
【背景技術】
【０００２】
e0(x),e1(x),e2(x),…,en(x)は、それぞれ予め与えられた一変数実多項式〔係数が実数の一変数多項式〕であるとする。但し、実数全体の集合をＲと表記すると、e1(x),e2(x),…,en(x)はＲ上一次独立とする。つまり、実数c1,c2,…,cnに対して、c1e1(x)+c2e2(x)+…+cnen(x)が恒等的に０となるのは、c1=c2=…=cn=0の場合に限られるとする。
【０００３】
a1,a2,…,anをそれぞれ予め与えられた実数とする。また、複素数全体の集合をＣｇと表記する。このとき、次の問題☆を考える。なお、この明細書中において記号~は直前の文字の頭上に附されるものとする。
［問題☆］
式（１）で表される一変数実多項式f(x)がＣｇ内の予め与えられた領域Ｄに零点を持たないとする。このとき、式（２）で表される一変数実多項式の集合のうち、領域Ｄに零点を持ち、かつ、一変数実多項式f(x)に最も近い一変数実多項式f~(x)について、一変数実多項式f(x)と一変数実多項式f~(x)との距離を求めよ。また、このような一変数実多項式f~(x)を一つ求めよ。
【数１７】
0004778486.tif 000002
【０００４】
但し、二つの一変数実多項式f,gの距離d(f,g)は、f-gの係数のｌ∞-ノルム〔最大値ノルム〕で定義する。即ち、式（３）で表される二つの一変数実多項式f,gの距離d(f,g)は、max{|a1-b1|,|a2-b2|,…,|an-bn|}で与えられる。max{|a1-b1|,|a2-b2|,…,|an-bn|}は、集合|a1-b1|,|a2-b2|,…,|an-bn|のうち最大の元を表す。
【数１８】
0004778486.tif 000003
【０００５】
なお、多項式の表記に際して変数ｘを明記したい場合にはf(x),g(x)の如く表すこととし、それ以外の場合には、単にf,gの如く表すこととする。また、特に断りの無い限り、「一変数実多項式」を「多項式」と略記する。
【０００６】
上記問題☆を考えることには、実用上の利益がある。例えばディジタル信号処理のような伝達関数による制御などにおいて、所望の特性を得るために、領域Ｄに零点を持たないように多項式の係数を設定したい場合がある。しかし、係数は有限の精度でしか指定できないため、その設定には一般的に誤差を伴う。このような誤差を伴うことを前提として、誤差付きで設定される多項式が間違いなく領域Ｄに零点を持たないようにできるか否か、という判定には、上記問題☆を解決する必要がある。視点を変えて説明すると、前記判定は、領域Ｄに零点を持たないことが既知である多項式ｆの「領域Ｄに零点を持たない」という性質を保ったまま多項式ｆの係数を動かすときのその限界を求めることであり、このような限界は、多項式ｆとこれに最も近い多項式ｆ~との距離〔ｌ∞-ノルム〕として与えられる。
【０００７】
上記問題☆に関連して、非特許文献１が挙げられる。この非特許文献１では、与えられた複素数γを零点とする複素係数多項式に対して、上記問題☆に類似する問題を扱っている。なお、非特許文献１は複素係数多項式を取り上げているが、非特許文献１中に示唆されているように、実係数多項式（実多項式）の場合にも適用できるように体系化できる。
上記問題☆と非特許文献１が取り上げている問題との違いは、上記問題☆が与えられた領域に零点を持つ多項式を対象としていることに対して、非特許文献１が取り上げている問題は与えられた一点を零点とする多項式を対象として距離最小のものを求める点にある。
【０００８】
零点の存在場所が一点ではなく領域となっている問題を扱った研究として、非特許文献２が挙げられる。
この非特許文献２では、距離を上記の如くｌ∞-ノルムとして問題を解く場合には、領域ではなく一点に零点を持つ場合に限定している。また、零点の存在場所が領域の場合について問題を解く場合には、二つの多項式f(x)とg(x)との間の距離をｌ２-ノルム、即ち、f(x)-g(x)の係数から決まるベクトルのｌ２-ノルム ((a1-b1)2+…+(an-bn)2)1/2で定義した場合にのみ解決している。
【０００９】
また、領域Ｄに零点を持たない多項式ｆに対してεを正の実数としたとき、d(f,g)≦εを満たす多項式ｇであって、指定された係数誤差範囲内において条件「領域Ｄに零点を持つ」を満すものが存在するか否かの判定法として、非特許文献３および特許文献１が挙げられる。
非特許文献３および特許文献１に示される判定法を用いれば、或る実数ｒ＞０に対し、d(f,g)≦ｒを満す多項式ｇで上記条件を満すものが存在するか否かの判定を行うことができるので、この有無を判断基底としてｒについて二分法を適用すれば、上記条件を満たす多項式であって多項式ｆに最も近いものと多項式ｆとの距離ｍの近似値を求めることができる。つまり、d(f,g)≦ｒを満す多項式ｇが存在するようなｒをHの初期値、０をLの初期値として、d(f,g)≦(H+L)/2を満たす多項式が存在すればHを(H+L)/2で置き換え、存在しなければLを(H+L)/2で置き換える処理を繰り返せばよい。このような処理を繰り返すことで、Hは上限ｍに上から近づく。従って、上記条件を満たす多項式で多項式ｆに最も近いものと多項式ｆとの距離ｍの近似値を求めることができる。
【非特許文献１】H. J. Stetter, "The Nearest Polynomial with a Given Zero, and Similar Problems," ACM SIGSAM Bulletin, Vol.33, No.4, pp.2-4, 1999.
【非特許文献２】M. A. Hitz and E. Kaltofen, "Efficient algorithms for computing the nearest polynomial with constrained roots," Proc. 1998 International Symposium on Symbolic and Algebraic Computation (ISSAC98), pp.236-243, 1998.
【非特許文献３】関川浩、白柳潔、「区間多項式の零点の所在について」、電子情報通信学会論文誌分冊Ａ、Vol.J89-A、No.3、pp.199-216、2006.
【特許文献１】特開２００５−２３５１２１号公報
【発明の開示】
【発明が解決しようとする課題】
【００１０】
上記非特許文献１の手法によれば、与えられた多項式に最も近い、与えられた一点を零点とする多項式を求めることはできる。しかし、与えられた「一点」を「領域」とした上記問題☆に上記非特許文献１の手法を適用できない。
【００１１】
また、上記非特許文献２の手法では、ｌ∞-ノルムで距離をはかる場合、過剰決定の連立一次方程式の近似解を求める手法を利用している。これを零点の存在場所が領域の場合に拡張することは、非特許文献２に述べられているとおり、困難である。また、ｌ２-ノルムで距離をはかる場合には、零点の存在場所が領域の場合も扱えるが、ｌ２-ノルムに特化した手法であるため、ｌ∞-ノルムで距離をはかる場合には上記非特許文献２の手法を用いることができない。つまり、上記非特許文献２の手法では、上記問題☆に回答を与えることができない。
【００１２】
上記非特許文献３あるいは上記特許文献１の判定法に二分法を適用する手法では、上記条件「領域Ｄに零点を持つ」を満す多項式ｇが存在する場合、当該条件を満たす多項式であって多項式ｆに最も近いものと多項式ｆとの距離の近似値を求めることはできるが、正確な距離や最も近い多項式そのものを求めることはできない。そもそも、二分法を利用するものであるところ、上記条件を満たす多項式の存在、つまりd(f,g)≦ｒを満す多項式ｇが存在するようなｒが分かっていることが必要であるから、何らかの方法でこのようなｒの存在を確認しないと、非特許文献３あるいは特許文献１の判定法を用いることができない。従って、上記非特許文献３あるいは上記特許文献１の判定法に二分法を適用する手法では、上記問題☆に回答を与えることができない。
【００１３】
そこで本発明は、上記問題☆に回答を与えること、つまり、複素数全体の集合内の指定された領域Ｄに零点を持つ一変数実多項式のうち、領域Ｄに零点を持たない或る一変数実多項式ｆに最も近い一変数実多項式ｆ~と、一変数実多項式ｆとのｌ∞-ノルムで定義された距離を求める、多項式間距離算出装置、方法、プログラムおよび記録媒体、さらに、一変数実多項式ｆ~を求める、一変数最近実多項式算出装置、方法、プログラムおよび記録媒体、提供することを目的とする。
【課題を解決するための手段】
【００１４】
上記課題を解決するために、本発明では、実数a1,a2,…,anと、一変数実多項式e0(x),e1(x),…,en(x)と、複素数全体の集合内の有界で閉な複素領域Ｄの境界を構成する有理式で表される有限個の区分境界Ｃ1,Ｃ2,…,ＣKとを記憶手段に記憶して、各区分境界Ｃk〔ｋ=1,2,…,K〕と集合｛Σj=1n±ej(x)｝に属する多項式q(x)との組み合わせ毎に得られる第一方程式f(x)+tq(x)=0の零点ｘの候補を求め（第一候補探索）、第一候補探索で得られた各候補に対応して得られる第一方程式のtの絶対値|t|のうち最小のものを求める（第一距離候補決定）。また、各区分境界Ｃkと集合｛1,2,…,n｝に属する整数μと集合{Σ1≦j≦n,j≠μ±ej(x)}に属する多項式pμ(x)との組み合わせ毎に得られる第二方程式f(x)+tμeμ(x)+τpμ(x)=0の零点ｘの候補を求め（第二候補探索）、第二候補探索で得られた各候補に対応して得られる第二方程式のτの絶対値|τ|のうち最小のものを求める（第二距離候補決定）。そして、第一距離候補決定と第二距離候補決定で得られた値のうち最小のものを出力して（最小距離出力）、これを最小距離とする。
【００１５】
また、多項式
【数１９】
0004778486.tif 000004
が恒等的に０となる実数c1,c2,…,cnが存在するか否かを判定し、存在する場合には一変数実多項式f(x)と恒等的に０の多項式との距離を求め（恒等式調査）、上記の最小距離出力に代えて、第一距離候補決定と第二距離候補決定によって得られた値および恒等式調査によって得られた距離のうち最小のものを求めるとしてもよい。
恒等的に０の多項式との距離についても考慮を要求する場合の最小距離を求めることができる。
【００１６】
また、集合｛Σj=1n±ej(x)｝の部分集合ＸΩを、集合｛Σj=1n±ej(x)｝に属する任意の二つの多項式M1，M2につきM1=-M2なる関係があるときいずれか一方を元とする集合として、第一候補探索では、上記の組み合わせを、各区分境界Ｃkと部分集合ＸΩに属する多項式q(x)との組み合わせとしてもよい。また、集合{Σ1≦j≦n,j≠μ±ej(x)}の部分集合Ｘμを、集合{Σ1≦j≦n,j≠μ±ej(x)}に属する任意の二つの多項式P1，P2につきP1=-P2なる関係があるときいずれか一方を元とする集合として、第二候補探索では、上記の組み合わせを、各区分境界Ｃkと、集合｛1,2,…,n｝に属する整数μと、部分集合Ｘμに属する多項式pμ(x)との組み合わせとしてもよい。
この場合、それぞれの処理に係る演算コストを半分にすることができる。
【００１７】
また、各区分境界Ｃkが、実数上の集合Ｓkに対する単射γk(s)〔但しｓ∈Ｓk〕で与えられ、複素数の実部と虚部をそれぞれＲｅ、Ｉｍで表すとして、上記の第一候補探索は、第一方程式f(x)+tq(x)=0の区分境界Ｃk上の零点ｘの候補を、
【数２０】
0004778486.tif 000005
の解ｓとして得るとすることができる。
この理論的な詳細は後述する。
【００１８】
また、上記の第二候補探索は、第二方程式f(x)+tμeμ(x)+τpμ(x)=0の区分境界Ｃk上の零点ｘの候補を、
【数２１】
0004778486.tif 000006
が最小となる条件を満足するｓとして得るとすることができる。
この理論的な詳細は後述する。
【００１９】
また、詳しい理論は後述するが、後述する命題、定理１、定理２に基づき、最小距離が求められると一変数実多項式ｆ~も求められるから、最小距離に対応する一変数実多項式ｆ~を出力すればよい。
【００２０】
また、本発明の多項式間距離算出装置としてコンピュータを機能させる多項式間距離算出プログラムによって、コンピュータを多項式間距離算出装置として作動処理させることができる。同様に、本発明の一変数最近実多項式算出装置としてコンピュータを機能させる一変数最近実多項式算出プログラムによって、コンピュータを一変数最近実多項式算出装置として作動処理させることができる。
そして、このようなプログラムを記録した、コンピュータによって読み取り可能なプログラム記録媒体によって、他のコンピュータを多項式間距離算出装置、一変数最近実多項式算出装置として機能させることや、プログラムを流通させることなどが可能になる。
【発明の効果】
【００２１】
本発明によれば、後述する命題、定理１、定理２に基づき、多項式間距離を変数として、最小距離が満たす代数方程式を導出することで、最小の多項式間距離を算出する。このことにより、複素数全体の集合内の指定された領域Ｄに零点を持つ一変数実多項式のうち、領域Ｄに零点を持たない或る一変数実多項式ｆに最も近い一変数実多項式ｆ~と、一変数実多項式ｆとのｌ∞-ノルムで定義された距離を求めることができる。また、最小距離が求まると、上記定理等により一変数実多項式ｆ~も求めることができる。
【発明を実施するための最良の形態】
【００２２】
[理論]
本発明の実施形態の説明に先立ち、本発明の理論について説明する。
まず、本発明では、複素数全体の集合Ｃｇ内の予め与えられた領域Ｄを有界で閉な複素領域とし、その境界Ｃは一定の条件が課された有限の長さの単純閉曲線とする。
即ち、本発明の解決すべき問題は、次のとおりである。
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
≪問題≫
[条件]
〈１〉 e0(x),e1(x),e2(x),…,en(x)は、それぞれ予め与えられた一変数実多項式であるとする。但し、実数全体の集合Ｒについて、e1(x),e2(x),…,en(x)はＲ上一次独立とする。
〈２〉 a1,a2,…,anをそれぞれ予め与えられた実数とする。
〈３〉 式（４）で表される一変数実多項式f(x)が複素数全体の集合Ｃｇ内の予め与えられた領域Ｄに零点を持たないとする。但し、領域Ｄは有界で閉な複素領域であり、領域Ｄの境界Ｃは有限の長さの単純閉曲線とする。
〈４〉境界Ｃは、一つ以上の有限個の区分境界Ｃkの和集合として表現される。即ち、境界Ｃは、Ｃ＝∪k=1KＣk＝Ｃ1∪Ｃ2∪・・・∪ＣK（整数Kは１≦K＜∞を満たす。）且つ、Ｃj∩Ｃk＝φ（j≠k）と表現される。但し、φは空集合を表す。また、各区分境界Ｃkは、単射のγkによって、
γk ： Ｓk  →  Ｃk
と表示される。ここでγkは有理式であって、分母・分子の多項式の係数は実代数的数a,bおよび虚数単位iを用いてa+biと表現されるものに限る。Ｓk⊂Ｒは、α,βを実代数的数として［α，β］、［α，∞）、（−∞，β］、（−∞，∞）のいずれかであるとする。
〈５〉 二つの一変数実多項式f,gの距離d(f,g)は、f-gの係数のｌ∞-ノルムで定義する。
上記条件の下、式（５）で表される一変数実多項式の集合のうち、領域Ｄに零点を持ち、かつ、一変数実多項式f(x)に最も近い一変数実多項式f~(x)について、一変数実多項式f(x)と一変数実多項式f~(x)との距離を求めよ。また、このような一変数実多項式f~(x)を一つ求めよ。
【数２２】
0004778486.tif 000007
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
【００２３】
なお、従前同様に、多項式の表記に際して変数ｘを明記したい場合にはf(x),g(x)の如く表すこととし、それ以外の場合には、単にf,gの如く表すこととする。また、特に断りの無い限り、「一変数実多項式」を「多項式」と略記する。
【００２４】
また、多項式の係数は、理論上は実数としてよいが、コンピュータなどによる演算の上では四則演算および等号判定を有限ステップのアルゴリズムで実行できることが必要かつ十分であり、そのために例えば実代数的数（整数係数一変数代数方程式の根となる実数）とする。以降の説明では、説明の便宜から、多項式の係数は有理数であるとする。
【００２５】
条件〈３〉本文から、式（４）で表される多項式f(x)は領域Ｄに零点を持たない。
もし、任意にa1,a2,…,anを選択して得られる多項式f(x)が領域Ｄに零点を持たないことを確認する必要がある場合には、次のような処理を行えばよい。
【００２６】
〔多項式f(x)が領域Ｄに零点を持たないことの確認処理〕
領域Ｄ（境界Ｃ上およびその内部）に多項式f(x)の零点が存在するか否かの判定は、公知の手法によって達成される。
まず、領域Ｄの境界Ｃ上において多項式f(x)の零点が存在するか否かの判定を行う。例えば、領域Ｄの境界Ｃの表示を多項式f(x)に代入した後、Sturmの定理に基づくアルゴリズムに従って零点の有無を判定する。
ここでは説明の便宜から一例として、各区分境界Ｃkが、パラメータsおよびパラメータsを一変数とする有理式φk(s)、ψk(s)によってφk(s)+i・ψk(s)と表示されるとする〔k=1,2,…,K〕。ｉは、虚数単位を表す。ここで、有理式φk(s)、ψk(s)における係数は、上記同様に、理論上は実数としてよいが、コンピュータなどによる演算の上では四則演算および等号判定を有限ステップのアルゴリズムで実行できることが必要かつ十分であり、そのために例えば実代数的数（整数係数一変数代数方程式の根となる実数）とし、具体例として有理数であるとする。以下では、有理式φk(s)、ψk(s)を、有理数係数の有理式であるとして例示説明する。パラメータsの動く範囲Ｓkは、条件〈４〉に対応して［α，β］、［α，∞）、（−∞，β］、（−∞，∞）のいずれかであるとする。[・，・]は閉区間、（・，・］は左開右閉区間、［・，・）は左閉右開区間、（・，・）は開区間を表す。また、パラメータsと区分境界Ｃkとの間は単射である。
【００２７】
Strumの定理に基づくアルゴリズムの適用について説明する。各区分境界Ｃkについて同様の処理となるから、敢えて沿え字kを省略して説明する。
領域Ｄの区分境界Ｃの表示φ(s)+i・ψ(s)が代入された多項式f(φ(s)+i・ψ(s))は、有理数係数有理式ω(s)およびτ(s)によってf(φ(s)+i・ψ(s))=ω(s)+i・τ(s)と表示できる。ここで「多項式f(x)が、φ(s0)+i・ψ(s0)において０となる」ことと、「ω(s)およびτ(s)がs=s0で同時に０となる」ことは同値である。また、「ω(s)およびτ(s)がs=s0で同時に０となる」ことと、「ω(s)およびτ(s)をそれぞれ既約な有理数係数有理式として表したときの分子のＧＣＤ（最大公約多項式）がs0において０になる」ことは同値である。従って、ω(s)およびτ(s)をそれぞれ既約な有理数係数有理式として表したときの分子のＧＣＤに対し、Strumの定理に基づくアルゴリズムを適用する。説明の便宜からω(s)およびτ(s)をそれぞれ既約な有理数係数有理式として表したときの分子のＧＣＤをH(s)とする。このH(s)について、多項式の列H0(s),H1(s),H2(s),…,Hr(s)を生成する。但し、これらの多項式の列は、次の規則に従って生成する。H0(s)=H(s),H1(s)=dH(s)/ds〔ｓに関する１階微分である。ライプニッツ記法〕、Hj-1(s)をHj(s)で割った剰余多項式を（符号を変えて）-Hj+1(s)とする。つまり、商の多項式をQj(s)と表すと、Hj-1(s)=Hj(s)Qj(s)-Hj+1(s)の関係が成立する。また、Hr-1(s)は、Hr(s)で割り切れる。つまり、商の多項式をQr(s)と表すと、Hr-1(s)=Hr(s)Qr(s)の関係が成立する。このとき、区間Ｓ＝[ａ，ｂ]において、H0(a),H1(a),H2(a),…,Hr(a)における正負の符号変化の回数をw(a)で表し、H0(b),H1(b),H2(b),…,Hr(b)における正負の符号変化の回数をw(b)で表すとすると、区間Ｓ＝[ａ，ｂ]におけるH(s)の零点の個数は、w(a)-w(b)である。なお、ここでは、区間Ｓ＝[ａ，ｂ]のａ、ｂは共にH(s)の零点ではないとする（零点であれば、個数を表す式が少し変わるが、本発明においては本質的な部分ではないので略する。）。w(a)-w(b)=0であれば零点が存在しないことが判明し、w(a)-w(b)≠0であれば零点が存在することが判明する。
【００２８】
なお、Sturmの定理については、参考文献１を参照のこと。
（参考文献１）  高木貞治著、「代数学講義（改訂新版）」、共立出版、１９６５．
【００２９】
以上では、領域Ｄの境界Ｃ上において多項式f(x)の零点が存在するか否かの判定を、領域Ｄの境界Ｃの表示を多項式f(x)に代入した後、Sturmの定理に基づくアルゴリズムによって行うものとして説明した。しかし、Sturmの定理に基づくアルゴリズムに限定する趣旨ではない。要は、一変数実係数の代数方程式が或る実の区間に根を持つか否かの判定ができればよく、例えば参考文献２に示されるsign variation methodによってこれを判定するとしてもよい。
（参考文献２）  G. E. Collins and R. Loos, "Real zeros of polynomials", Computer Algebra, Symbolic and Algebraic Computation, (B. Buchberger, G. E. Collins and R. Loos(編)), pp.83-94, Springer-Verlag,1983.
【００３０】
もし、境界Ｃ上に多項式f(x)の零点が存在しなければ、領域Ｄの内部において多項式f(x)の零点が存在するか否かの判定を行う。この判定には偏角の原理を用いることで達成される。なお、偏角の原理に基づく判定においては、領域Ｄの境界Ｃ上に多項式f(x)の零点がないことが前提となるから、まず、境界Ｃ上での零点の有無を判定しておいたのである。
【００３１】
偏角の原理に基づくアルゴリズムの適用について説明する。
区分境界Ｃkの表示φk（ｓ）＋ｉ・ψk（ｓ）を多項式ｆ（ｘ）に代入する。このとき、ｆ（ｘ）＝ｆ（φk（ｓ）＋ｉ・ψk（ｓ））＝ｕ（φk（ｓ），ψk（ｓ））＋ｉ・ｖ（φk（ｓ），ψk（ｓ））と表される。そこで、実部ｕ（φ（ｓ），ψ（ｓ））と虚部ｖ（φ（ｓ），ψ（ｓ））それぞれの実根をｓ∈Ｓにおいて求める。同様にして全ての区分境界について根を求め、これらの根を現れる順に並べたリストＳ１を作る。また、境界Ｃに囲まれた領域における根の計数用のリストＳ２を用意する（初期状態では、リストＳ２は空である。）。リストＳ１の先頭から順次に根を読み出すこととし、まず、先頭要素（根）Ａを取り出し、リストＳ２が空のリストであればそれをＳ２に書き込む。リストＳ２が空でないときは先頭要素（根）ＡとリストＳ２の先頭の要素（根）が共に実部の解であるか共に虚部の解であるかを判定し、この判定が真であればリストＳ２から先頭の要素（根）を取り除く。当該判定が偽であるときは先頭要素（根）ＡをリストＳ２の先頭に書き足す。この処理操作をリストＳ１の先頭から順次に根を読み出すことで行う。この結果、リストＳ２における要素（根）の個数の１／４が境界Ｃの内部に含まれる多項式f(x)の根の数になる。この数が０であれば、多項式f(x)の零点が領域Ｄの内部に存在しないことが判明し、この数が０でなければ、多項式f(x)の零点が領域Ｄの内部に存在することが判明する。
【００３２】
なお、偏角の原理を用いた多項式の零点の数え上げについては、参考文献３を参照のこと。
（参考文献３）  平野照比古著、「偏角の原理を用いた多項式の根の数え上げ」、数式処理、Vol.9, No.4, pp.34-35, 2003.
【００３３】
以上では、領域Ｄの内部において多項式f(x)の零点が存在するか否かの判定を偏角の原理に基づくアルゴリズムによって行うものとして説明した。しかし、要は、多項式f(x)が領域Ｄの内部に根を持つか否かの判定ができればよく、偏角の原理に基づくアルゴリズムに限定する趣旨ではない。
以上で〔多項式f(x)が領域Ｄに零点を持たないことの確認処理〕の説明は終わりである。
【００３４】
次に、恒等的に０ではない多項式であって多項式ｆに最も近い多項式ｆ~の領域Ｄにおける零点は全て境界Ｃ上に存在すること、および、多項式ｆ~の零点と成り得る点のうち有限個のみ調べれば十分であることを示す。
このことにより多項式ｆ~の候補が有限個となるので、d(f,f~)の最小値およびそのときの多項式ｆ~を求めることが可能となる。このような候補が一つも無い場合、もし式（５）で表される多項式の集合の中に恒等的に０となる多項式があれば、この多項式が最も近い多項式ｆ~となる。もし式（５）で表される多項式の集合の中に恒等的に０となる多項式がなければ、領域Ｄに零点を持つ多項式であって式（５）で表される多項式の集合に属する多項式は存在しないと結論付けられる。
【００３５】
まず、上記非特許文献３、上記特許文献１およびそれと類似の議論によって、
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
[命題]距離最小の多項式ｆ~が恒等的に０ではない場合、その零点は、領域Ｄの境界Ｃ上にのみ存在する。
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
[定理１]距離最小のときの多項式ｆ~は、恒等的に０であるか、あるいは、高々一つの例外の係数を除き、|aj-a~j|=d(f,f~)を満す。
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
ことがわかる。
【００３６】
[命題]を証明する。
まず、次のことを示す。
『多項式f(x)=e0(x)+Σj=1najej(x) (aj∈Ｒ)が領域Ｄに零点を持たず、恒等的に０ではない多項式g(x)=e0(x)+Σj=1nbjej(x) (bj∈Ｒ)が領域Ｄの内部に零点を持つとする。このとき、領域Ｄの内部に零点を持ち、d(f,g~)＜d(f,g)を満たす多項式g~(x)=e0(x)+Σj=1nb~jej(x) (b~j∈Ｒ)が存在する。』・・・（★）
【００３７】
複素数ｚを中心とする半径ｒの開円板（境界は含まない。）をB(z;r)と表すことにする。つまり、B(z;r)={w|w∈Ｃg,|z-w|<r}である。p(t,x)=f(x)+t(g(x)-f(x))とおく。このとき、p(0,x)=f(x),p(1,x)=g(x)であり、任意のt(0≦t≦1)に対して、p(t,x)は、e0(x)+Σj=1ncjej(x) (cj∈Ｒ)と表現できる。
ζを領域Ｄの内部に在る多項式ｇの零点とする。すると、条件「B(ζ;ε)⊂Ｄかつ、任意のξ∈B(ζ;ε),ξ≠ζに対して、g(ξ)≠0」を満たすε＞０が存在する。仮にこのようなεが存在しないとすると、多項式ｇが恒等的に０ではないことに矛盾する。
今、任意のt(0≦t≦1)に対して、p(t,x)がB(ζ;ε/2)の境界に零点を持たないと仮定する。すると、Roucheの定理により、B(ζ;ε/2)内に在るp(0,x)(=f(x))の零点の個数（０個）とp(1,x)(=g(x))の零点の個数（１個以上）が等しくなり矛盾する。従って、或る０＜τ＜１が存在してp(τ,x)はB(ζ;ε/2)の境界に零点を持つので、g~(x)としてp(τ,x)を採ればd(f,g~)=τd(f,g)<d(f,g)が成り立つ。
よって、題意★が示せた。
【００３８】
このとき、距離最小のときの多項式ｆ~の零点が領域Ｄの内部に存在するとすると、領域Ｄの内部に零点を持ち、d(f,g~)＜d(f,f~)を満たす多項式g~(x)=e0(x)+Σj=1nb~jej(x) (b~j∈Ｒ)が存在することになり、多項式ｆ~が距離最小のときの多項式であることに矛盾する。よって、距離最小のときの多項式ｆ~の零点は、領域Ｄの境界Ｃ上にのみ存在する。以上により[命題]の証明は終了である。
【００３９】
次に[定理１]を証明する。
恒等的に０ではない多項式f~(x)=e0(x)+Σj=1na~jej(x) (a~j∈Ｒ)が多項式ｆに一番近い多項式とする。すると、上記[命題]のとおり、多項式ｆ~は領域Ｄの境界Ｃ上にのみ零点ζを持つ。
【００４０】
|aj-a~j|＜d(f,f~)となるｊが２個以上あるとせよ。このｊから２個選択して、これをμとηとする。つまり、二つの添字μとηがあって、|aμ-a~μ|および|aη-a~η|がd(f,f~)よりも小さい、とする(このようなμ、ηが存在しなければ証明終わり。)。
この仮定から矛盾が生じるか、あるいは、「条件[1]，[2]，[3]を満たす、式（６）で表される多項式ｇが存在する」ことを云えばよい。
【数２３】
0004778486.tif 000008
[1] d(f,g)=d(f,f~)
[2] |aμ-bμ|=d(f,f~)あるいは|aη-bη|=d(f,f~)
[3] 多項式ｇは、領域Ｄの境界Ｃ上に零点を持つ。
【００４１】
以下、bμ, bνをそれぞれ、tμ+aμ, tν+aνと書く。すると、式（７）が云える。
【数２４】
0004778486.tif 000009
【００４２】
よって、方程式g(x)=0は連立方程式（８）と等価である。但し、uj(x)=Re ej(x), vj(x)=Im ej(x)とする。Ｒｅは実数部分、Ｉｍは虚数部分を表す。
【数２５】
0004778486.tif 000010
【００４３】
連立方程式（８）を、ｘをパラメータとするtμ, tνの連立方程式とみる。また、上記[命題]から境界Ｃ上にある多項式ｆ~の零点ζをとる。このとき、行列式（９）がｘ＝ζにおいて０であったとすると、ζが多項式ｇの零点のまま、|tμ|=d(f,f~)あるいは|tν|=d(f,f~)が成り立つまでtμとtνを動かすことができる。
【数２６】
0004778486.tif 000011
【００４４】
つまり、式（６）で表される多項式ｇであって、[1] d(f,g)=d(f,f~)、[2] |aμ-bμ|=d(f,f~)あるいは|aη-bη|=d(f,f~)、[3] 境界Ｃ上に零点を持つ、という各条件を満たす多項式ｇが存在することになる。
【００４５】
もし多項式ｇが恒等的に０であるならこれで証明は終わるが、多項式ｇが恒等的に０でない場合で、|aj-a~j|＜d(f,f~)となるｊが依然として２個以上あれば、上記の証明を繰り返せばよい。
【００４６】
もし、行列式（９）がｘ＝ζにおいて０でないならば、連立方程式（８）の解tμ, tνは一意に決まり、行列式（９）が０でない限り、パラメータｘについて連続である。よって、tμ, tνはそれぞれｘの連続関数になるので、tμ(x), tν(x)と書く。すると、|tμ(x)|＜d(f,f~)および|tν(x)|＜d(f,f~)が全てのｘ∈B(ζ;ε)に対して成立するような正数εが存在する。
【００４７】
そこで、ξを領域Ｄの内部と開円板B(ζ;ε)の共通部分から取る。このとき、bμ=tμ(ξ)+aμ, bν=tν(ξ)+aνに対して、式（１０）で表される多項式ｇは、領域Ｄの内部に在る点ξを零点とする。
【数２７】
0004778486.tif 000012
【００４８】
よって、上記[命題]を多項式（１０）に適用すれば、式（１１）で表される多項式ｇ~であって、d(f,g~)＜d(f,g)=d(f,f~)が成り立つものが存在する。これは、多項式ｆ~が多項式ｆに最も近い、という仮定に矛盾する。
よって、[定理１]が示せた。以上により[定理１]の証明は終了である。
【数２８】
0004778486.tif 000013
【００４９】
さて、[定理１]から、或る番号μがあって、多項式ｆとの距離の最小値を実現する多項式ｆ~のeμ(x)の係数a~μについて|aμ-a~μ|＜d(f,f~)である場合、μと異なる番号ｊについては|aj-a~j|=d(f,f~)であるから、σj=１または−１として、式（１２）のように多項式ｆ~を表現できる。
【数２９】
0004778486.tif 000014
【００５０】
ここで、ｔμおよびｔを変数、ｘをパラメータと見た、式（１２）の右辺を一般化した方程式（１３）を考える。但し、pμ(x)は集合{Σ1≦j≦n,j≠μ±ej(x)}に属する多項式とする。なお、t=d(f,f~)かつtμ=a~μ-aμのとき、方程式（１３）の左辺は多項式f~(x)と同じであることに注意する。また、ｔおよびｔμは正負の値を取りえることにも注意する。
【数３０】
0004778486.tif 000015
【００５１】
方程式（１３）は、連立方程式（１４）と等価である。
【数３１】
0004778486.tif 000016
【００５２】
ここで、多項式f~(x)の境界Ｃ上の零点ζを取る。もし、行列式（１５）がｘ＝ζにおいて０ならば、|t|を|tμ|≦|t|かつ方程式（１３）を満足するまま小さくすることができる。これは、多項式ｆ~が多項式ｆとの距離の最小値を実現する多項式であることに矛盾する。
【数３２】
0004778486.tif 000017
【００５３】
よって、ｘ＝ζにおいて行列式（１５）は０ではなく、また、ζの廻りの近傍Ｕにおいても行列式（１５）は０ではなく〔∵複素関数の連続性〕、連立方程式（１４）の解ｔは、式（１６）の如く表せる。
【数３３】
0004778486.tif 000018
【００５４】
式（１６）の右辺はパラメータｘについて連続であるから、ｘの関数としてt(x)と書く。すると、|t(x)|はｘ＝ζにおいてＵ∩Ｃ内の最小値をとる。もしそうでなければ、領域Ｄに属する点であるξを零点とするg(x)=e0(x)+Σj=1nbjej(x) (bj∈Ｒ)であって、しかもd(f,g)＜d(f,f~)となるものが存在することになり、多項式ｆ~が多項式ｆとの距離の最小値を実現する多項式であることに矛盾する。
【００５５】
以上の議論から、[定理２]が云える。
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
[定理２]多項式f~(x)=e0(x)+Σj=1na~jej(x) (a~j∈Ｒ)は、恒等的に０ではない多項式であって、領域Ｄに零点を持ち、d(f,f~)が最小なものとする。さらに、或る番号μがあって、|aμ-a~μ|＜d(f,f~)とする。このとき、方程式（１３）を考える。ζが多項式f~(x)の境界Ｃ上の零点であり、Ｕはζの近傍であって、Ｕにて行列式（１５）が０にならないとする。このとき、式（１６）の右辺の絶対値はｘ＝ζにおいてＵ∩Ｃ内の最小値となる。
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
【００５６】
上記定理から、多項式ｆ~の零点と成り得る点のうち有限個のみ調べれば十分であることが導かれる。このことを、具体的な計算方法を示して説明する。
【００５７】
〔上記定理に基づく計算方法〕
以下、上記定理に基づく計算方法を、二つの場合に分けて説明する。第一の場合は、|aj-a~j|=d(f,f~)が全てのｊについて成り立つ場合、第二の場合は、或る番号μがあって|aμ-a~μ|＜d(f,f~)となる場合である。
【００５８】
≪第一の場合≫
bj=tj+ajとおく。このとき、多項式g(x)=e0(x)+Σj=1nbjej(x) (bj∈Ｒ)は、式（１７）のように表現できる。
【数３４】
0004778486.tif 000019
【００５９】
よって、連立一次方程式（１８）を、ｘ∈Ｃかつt1,…,tn∈Ｒという条件の下で解き、解の中で|t1|=…=|tn|が最小となるものが最小距離となる。条件を満たす解が無い場合は、多項式の集合｛e0(x)+Σj=1nbjej(x)｜bj∈Ｒ｝に属する多項式で|a1-b1|=|a2-b2|=…=|an-bn|かつ領域Ｄに零点を持つものは存在しない。
【数３５】
0004778486.tif 000020
【００６０】
連立一次方程式（１８）は、方程式（１９）と等価である。
なお、厳密には連立一次方程式（１８）は、方程式f(x)+t(±e1(x)±e2(x)±…±en(x))=0と等価である。しかし、ｔは正負の値を取る変数であるから、方程式としては実質的にf(x)+t(e1(x)±e2(x)±…±en(x))=0、つまり方程式（１９）を解けばよい。但し、この意味では連立一次方程式（１８）は方程式（１９）のみに等価ということではない。集合｛Σj=1n±ej(x)｝=｛±e1(x)±e2(x)±…±en(x)｝の部分集合ＸΩを、集合｛Σj=1n±ej(x)｝に属する任意の二つの多項式M1，M2につきM1=-M2なる関係があるときいずれか一方を元とする集合としたとき、部分集合ＸΩから選択した多項式q(x)についてf(x)+tq(x)=0とした方程式に等価である。そのうちの一本が方程式（１９）である。以下、方程式（１９）について議論を進めるが、一般性を失うものではない。
【数３６】
0004778486.tif 000021
【００６１】
ここで、±は、＋と−の全ての組み合わせを取るので、組み合わせは全部で２ｎ−１通りであり、各方程式は式（２０）のような表現となる。但し、ここでの多項式q(x)は、e1(x)±e2(x)±…±en(x)の中の一つである〔一般的には、多項式q(x)は部分集合ＸΩから選択され得る。〕。
f(x)+tq(x)=0     （２０）
【００６２】
以下、方程式（２０）それぞれについて区分境界Ｃk上で調べる。区分境界Ｃkの表示を用いると、方程式（２０）がｘ∈Ｃかつｔ∈Ｒなる解を持つ必要十分条件は、方程式（２１）がｓ∈Ｓkかつｔ∈Ｒなる解を持つことである。
f(γk(s))+tq(γk(s))=0     （２１）
【００６３】
方程式（２１）は連立方程式（２２）と等価である。
【数３７】
0004778486.tif 000022
【００６４】
複素係数多項式g(x)∈Ｃg[x]に対して、各係数をその複素共役で置き換えた多項式をg^(x)の如く表記する。また、複素係数有理式h(x)=h1(x)/h2(x) (h1(x),h2(x)∈Ｃg[x])に対し、複素係数有理式h^1(x)/h^2(x)をh^(x)と書く。なお、この明細書中において記号^は直前の文字の頭上に附されるものとする。
このとき実係数有理式Ｊ〔Ｊ(x)＝f(x)、q(x)〕に対して、式（２３）が成り立つ。
【数３８】
0004778486.tif 000023
【００６５】
よって、連立方程式（２２）をｔの方程式と見たとき、係数は有理数係数有理式である。
【００６６】
Re q(γk(s))≠０のとき、ｔは式（２４）で表される。
【数３９】
0004778486.tif 000024
【００６７】
連立方程式（２２）の第二式のｔに式（２４）の右辺を代入すると、式（２５）を得る。
【数４０】
0004778486.tif 000025
【００６８】
即ち、式（２６）かつRe q(γk(s))≠０である。
【数４１】
0004778486.tif 000026
【００６９】
Re q(γk(s))＝０のとき、連立方程式（２２）からRe f(γk(s))＝０である。このとき、もしIm q(γk(s))＝０ならば連立方程式（２２）からIm f(γk(s))＝０かつｔは任意である。これは、多項式ｆが領域Ｄに零点を持たないという仮定に矛盾する。よって、Re q(γk(s))＝０のときIm q(γk(s))≠０であり、式（２７）が成り立つ。
【数４２】
0004778486.tif 000027
【００７０】
連立方程式（２２）の第一式のｔに式（２７）の右辺を代入すると、式（２８）を得る。
【数４３】
0004778486.tif 000028
【００７１】
即ち、式（２９）かつIm q(γk(s))≠０である。
【数４４】
0004778486.tif 000029
【００７２】
以上をまとまると、Re q(γk(s))とIm q(γk(s))が同時に０となることはないので、単に方程式（３０）を解けばよい。
【数４５】
0004778486.tif 000030
【００７３】
方程式（３０）の左辺が定数ではないとき、解の候補であるｓ∈Ｓkは有限個である。方程式（３０）の左辺が恒等的に０のとき、解の候補ｓは、式（２４）、式（２７）から、式（３１）の絶対値または式（３２）の絶対値がＳk上で最小、という条件を満たす。
【数４６】
0004778486.tif 000031
【００７４】
従って、式（３１）の絶対値が定数でないときには、式（３３）の零点およびＳkの端点が解の候補であり、式（３１）の絶対値が定数のときには、Ｓkに属するどの一点を解の候補としてもよい。
【数４７】
0004778486.tif 000032
【００７５】
式（３２）についても同様で、式（３２）の絶対値が定数でないときには、式（３４）の零点およびＳkの端点が解の候補であり、式（３２）の絶対値が定数のときには、Ｓkに属するどの一点を解の候補としてもよい。
【数４８】
0004778486.tif 000033
【００７６】
以上より、有限個のｓ∈Ｓkについて、式（３１）の絶対値あるいは式（３２）の絶対値を計算し、それらの中の最小値を≪第一の場合≫における最小距離として採用すればよい。
また、この最小値を与えた式（３１）あるいは式（３２）の値をt0とすると、≪第一の場合≫における、多項式ｆとの最小距離|t0|を実現する多項式ｆ~のうち一つは、値t0を与えたときのq(x)を用いて、式（３５）で得られる〔式（２０）参照〕。
【数４９】
0004778486.tif 000034
【００７７】
≪第二の場合≫
式（１３）に立ち返って説明する。
或る区分境界Ｃkにつき、或るμを選択するとともにpμ(x)を一本選択する。
既述のとおり、多項式ｆ~の境界Ｃ上の零点ｘ＝ζに対応する点ｓ∈Ｓkについては、行列式（１５）のｘに区分境界Ｃkの表示γk(s)を代入したものが０ではない。このことに注意して、式（１６）に区分境界Ｃkの表示γk(s)を代入して式（３６）を得る。
【数５０】
0004778486.tif 000035
【００７８】
t(γk(s))が定数ｃのとき、多項式ｆ~の候補となる多項式は|tμ(γk(s))|＜|c|を満たす。そこで、|tμ(γk(s))|＜|c|を満たすｓ∈Ｓkを一つ取り、これを選択したμ、pμ(x)におけるパラメータｓの候補とすればよい。
具体的には、t(γk(s))が定数ｃのとき、ｓ∈Ｓkを任意に一つ取り、このｓが|tμ(γk(s))|＜|c|を満たすならば、このｓをパラメータｓの候補とすればよい。もし、任意に選択したｓが|tμ(γk(s))|≧|c|を満たすならば、他の区分境界とpμ(x)との組み合わせについて候補の存在を調べる。理由は次のとおりである。もし、全てのｓ′∈Ｓkが|tμ(γk(s′))|≧|c|を満たすならば、選択しているpμ(x)と区分境界Ｃk〔つまりＳk〕の組み合わせにおいて、≪問題≫について候補となるべきパラメータｓは存在しない。もし、|tμ(γk(s))|＜|c|を満たすｓ1∈Ｓkが存在するならば、|tμ(γk(s2))|=|c|を満たすｓ2∈Ｓkが存在する〔中間値の定理〕。従って、この場合は≪第一の場合≫の対象となるから、多項式ｆ~を一つ求めればよいことを考慮すればｓ1を候補とする必要がない。
【００７９】
t(γk(s))が定数ではなく|t(γk(s))|がｓ＝δにおいて最小値を取るときには、δは式（３７）の零点であるかＳkの端点である。式（３７）は有理式であるから、これのＳkに属する零点は有限個である。即ち、パラメータｓの候補は有限個となる。なお、いずれにしても、式（３６）の分母が０となる点は除くことに留意しなければならない。
【数５１】
0004778486.tif 000036
【００８０】
候補となったｓに対応して、連立方程式（１４）のｘにγk(s)を代入することで、連立方程式（１４）はｔおよびｔμに関する二元連立一次方程式として確定する〔∵パラメータｘはｓに対応して決まっている。〕。従って、この二元連立一次方程式を解くことで、ｔおよびｔμの解ｔ<solution>およびｔμ<solution>が決まる。このとき、候補となったｓに対応して得られるｔ<solution>のうちその絶対値が最小となるものの値をt0すると、|t0|を≪第二の場合≫における最小距離として採用すればよい。
また、≪第二の場合≫における、多項式ｆとの最小距離|t0|を実現する多項式ｆ~のうち一つは、値t0を与えたときのｔμ<solution>〔ｔμ<solution>,0とする。〕およびpμ(x)〔pμ,0(x)とする。〕を用いて、式（３８）で得られる〔式（１３）参照〕。
【数５２】
0004778486.tif 000037
【００８１】
≪第一の場合≫と≪第二の場合≫は理論的な先後関係に無いから、何れを先行して行うとしてもよい。従って、≪第一の場合≫で得られた最小距離|t0|と≪第二の場合≫で得られた最小距離|t0|とを比較して小さい方を最小距離として選択すればよい〔両者が等しい場合には、いずれか一方を選択すれば足りる。〕。さらに、多項式ｆ~が恒等的に０となる場合を考慮しないときには、各区分境界で≪第一の場合≫と≪第二の場合≫の処理を行って、区分境界ごとに得られた最小距離のうち最も小さい距離を≪問題≫の解答としての最小距離とすればよい。但し、多項式ｆ~が恒等的に０となる場合も考慮するときは、区分境界ごとに得られた最小距離のうち最も小さい距離と、恒等的に０である多項式ｆ~＝０と多項式ｆとの距離d(f,0)とを比較して小さい方を≪問題≫の解答としての最小距離とすればよい〔両者が等しい場合には、いずれか一方を選択すれば足りる。〕。
【００８２】
ｓとｘが単射の関係にあることに注意して以上の説明をまとめれば、多項式ｆ~が恒等的に０となる場合を考慮しないときには、要するに、≪問題≫の解答としての最小距離は、区分境界Ｃkとq(x)の組み合わせ毎に得られる方程式（２０）の零点の候補、および、区分境界Ｃkとμとpμ(x)の組み合わせ毎に得られる方程式（１３）の零点の候補、の各候補について対応して得られるｔの絶対値のうちの最小値として与えられる。また、多項式ｆ~が恒等的に０となる場合も考慮するときは、要するに、前記最小値とd(f,0)とを比較した小さい方として与えられる。従って、コンピュータ等で実行する場合の最小距離を求めるアルゴリズムは、このような網羅的な探索を行うものであればよく、その詳細について格別の限定は無い。
【００８３】
また、≪問題≫の解答としての多項式ｆ~は、≪問題≫の解答としての最小距離に対応する多項式とすればよい〔最小距離が複数ある場合には、いずれか一つを選択すれば足りる。〕。
以上で、[理論]の説明は終わりである。
【００８４】
[アルゴリズム]
上述の[理論]に基づき、最小距離d(f,f~)を求めるアルゴリズムの一例を説明する〔図１−１および図１−２参照〕。
例示するアルゴリズムでは、
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
入力：多項式e0(x),e1(x),e2(x),…,en(x)、
有理数a1,a2,…,an、
多項式f(x)=e0(x)+Σj=1najej(x)の零点が存在しない複素領域Ｄの境界Ｃ＝∪k=1KＣkにつき、各区分境界Ｃkの有理式による表示
但し、各区分境界Ｃkは、単射γk ： Ｓk  →  Ｃkと表示される。
出力：最小距離d(f,f~)
但し、多項式ｆ~が存在しない場合は、出力は−１である。
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
とする。なお、ここで有理数は実代数的数の具体例に過ぎない。
【００８５】
〈アルゴリズムの具体例〉
◎ステップＳ１
e0(x)+Σj=1ncjej(x)=0を満たす実数c1,c2,…,cnが存在する場合、Ｔ＝d(f,0)とする。このような実数c1,c2,…,cnが存在しない場合、Ｔ＝−１とする。
＜解説＞
ステップＳ１は、多項式ｆ~が恒等的に０である場合を排除しないための処理である。実数c1,c2,…,cnが存在することの判定は、e0(x)+Σj=1ncjej(x)をΣi=0Nwixiのように表現したときの各係数wiを０とした連立方程式を解けばよい〔但し、実際に解を求める必要はなく、連立方程式の解の存在判定（公知）を行うだけでよい。〕。多項式ｆ~が恒等的に０である場合を考慮しないときは、初期値設定Ｔ＝−１のみを行う。
【００８６】
◎ステップＳ２
ステップＳ２の処理の詳細は次のとおりである。
未選択の区分境界が存在するか否かを判定する（○ステップＳ２０）。
未選択の区分境界が存在すれば、その中の一つＣkを選択する（○ステップＳ２１）。
未選択の区分境界が存在しなければ、Ｔの値をd(f,f~)として出力して終了（○ステップＳ２２）。
＜解説＞
ステップＳ２は、全ての区分境界について以降のステップＳ３およびステップＳ４の各処理を行うための処理である。全ての区分境界についてステップＳ３およびステップＳ４の各処理を実行した場合は、終了である。
【００８７】
◎ステップＳ３
《第一の場合》で説明した処理を行う。ステップＳ３の処理の詳細は次のとおりである。
【００８８】
○ステップＳ３０１
未選択のq(x)が存在するか否かを判定する。
【００８９】
○ステップＳ３０２
未選択のq(x)が存在すれば、その中の一つを選択する。
ステップＳ３０４の処理の以降では、ステップＳ３０２の処理で選択されたq(x)について、方程式（３０）を解く。
【００９０】
○ステップＳ３０３
未選択のq(x)が存在しなければ、全ての候補ｓに対応する、式（３１）の絶対値あるいは式（３２）の絶対値を計算し、それらの中の最小値|t0|を求める。Ｔ＝−１またはＴ＞|t0|の場合、Ｔ＝|t0|とする。つまり、Ｔの値を書き換える。
ステップＳ３０３の処理の後、ステップＳ４の処理を行う。
【００９１】
○ステップＳ３０４
方程式（３０）の左辺が恒等的に０か否かを判定する。方程式（３０）の左辺が恒等的に０ではないときはステップＳ３０５の処理へ、方程式（３０）の左辺が恒等的に０のときはステップＳ３０４ｃの処理へ、進む。
【００９２】
○ステップＳ３０４ｃ
Re q(γk(s))が恒等的に０か否かを判定する。Re q(γk(s))が恒等的に０ならばステップＳ３０９の処理へ、Re q(γk(s))が恒等的に０でないならばステップＳ３０６の処理へ、進む。
【００９３】
○ステップＳ３０５
方程式（３０）の左辺が恒等的に０ではないとき、方程式（３０）の解ｓを候補とする。
ステップＳ３０５の処理の後、ステップＳ３０１の処理を行う。
【００９４】
○ステップＳ３０６
式（３１）が定数か否か判定する。定数ではないときはステップＳ３０７の処理へ、定数のときはステップＳ３０８の処理へ、進む。
【００９５】
○ステップＳ３０７
式（３３）の零点およびＳkの端点を候補とする。続いて、ステップＳ３０１の処理に戻る。
【００９６】
○ステップＳ３０８
Ｓkに属する任意の一点を候補とする。続いて、ステップＳ３０１の処理に戻る。
【００９７】
○ステップＳ３０９
式（３２）が定数か否か判定する。定数ではないときはステップＳ３１０の処理へ、定数のときはステップＳ３１１の処理へ、進む。
【００９８】
○ステップＳ３１０
式（３４）の零点およびＳkの端点を候補とする。
ステップＳ３１０の処理の後、ステップＳ３０１へ戻る。
【００９９】
○ステップＳ３１１
Ｓkに属する任意の一点を候補とする。
ステップＳ３１１の処理の後、ステップＳ３０１へ戻る。
【０１００】
＜ステップＳ３についての概説＞
ステップＳ３０４ｃの処理にて、Re q(γk(s))が恒等的に０である場合、式（２６）に関して既述したとおり、Im q(γk(s))は０とならないことが分かるので、Im q(γk(s))が恒等的に０か否かの判定は不要であり、ステップＳ３０９の処理を行う。
【０１０１】
ステップＳ３０４ｃの処理にて、Re q(γk(s))が恒等的に０ではない場合、ステップＳ３０９〜Ｓ３１１の処理を行うことなく、ステップＳ３０１の処理に戻ることができる。以下、その理由を説明する。
【０１０２】
ステップＳ３０６の処理結果がyesの場合、ステップＳ３０４の処理結果がyesでありRe q(γk(s))は多項式として０ではないので、Im q(γk(s))が恒等的に０となる場合を除き、有理式として式（３９）のように表現できる。
【数５３】
0004778486.tif 000038
【０１０３】
従って、式（３９）の右辺も定数である。ところで、式（３９）の両辺の分母Re q(γk(s))、Im q(γk(s))が０となる点ｓについて、議論の端緒である連立方程式（２２）に立ち返ると、Re q(γk(s))=0のときRe f(γk(s))=0で連立方程式（２２）は第二式〔下の式〕のみとなり、しかもこのときIm q(γk(s))≠0なので、結局、Ｓkに属するどの点を候補としても問題ない。逆に、Im q(γk(s))=0の場合も同様である。もし、Im q(γk(s))が恒等的に０であるならば、Re q(γk(s))の零点はＳk内に無いので、この場合もＳkに属するどの点を候補としても問題ない。
本論において求めるべきはｔの絶対値であり、式（４０）のとおり定数である。従って、ステップＳ３０８の処理でＳkに属する一つの点を選択すれば十分である。
【数５４】
0004778486.tif 000039
【０１０４】
ステップＳ３０６の処理結果がnoの場合、ステップＳ３０７の処理を行いステップＳ３０１の処理に戻ればよい。
Re q(γk(s))が多項式として０ではない場合、式（３９）の左辺について分母分子の共通因子があれば、それで除して既約にしておけば、Ｓk内に分母の零点は無いことになる。
仮に、分母の零点s0∈Ｓkがあったとすると、Re q(γk(s))=0であるから、Im q(γk(s))が恒等的に０ということはない。ここでステップＳ３０４の処理結果がyesなので、有理式として式（３９）のように表現される。従って、Im q(γk(s))=0となり、「Re q(γk(s))とIm q(γk(s))が同時に０となることはない」ことと矛盾する。
【０１０５】
なお、ステップＳ３０４ｃの処理では、Re q(γk(s))が恒等的に０か否かを判定するようにしたが、以上の説明から明らかなように、Im q(γk(s))が恒等的に０か否かを判定するようにしてもよい。この場合、この判定がnoならばステップＳ３０９〜Ｓ３１１の処理を行うようにしてステップＳ３０１に戻るとし、前記判定がyesならばステップＳ３０６〜Ｓ３０８の処理を行うようにしてステップＳ３０１に戻るとすればよい。
以上で＜ステップＳ３についての概説＞は終わりである。
【０１０６】
◎ステップＳ４
《第二の場合》で説明した処理を行う。ステップＳ４の処理の詳細は次のとおりである。
【０１０７】
○ステップＳ４０１
未選択のμが存在するか否かを判定する。
【０１０８】
○ステップＳ４０２
未選択のμが存在しなければ、全ての候補ｓに対応して、連立方程式（１４）のｘにγk(s)を代入して得られる二元連立一次方程式を解いて、ｔおよびｔμの解ｔ<solution>およびｔμ<solution>を得る。このとき、候補となったｓに対応して得られるｔ<solution>のうちその絶対値が最小となるものの値をt0する。Ｔ＝−１またはＴ＞|t0|の場合、Ｔ＝|t0|とする。つまり、Ｔの値を書き換える。
ステップＳ４０２の処理の後、ステップＳ２０の処理を行う。
【０１０９】
○ステップＳ４０３
未選択のμが存在すれば、その中の一つを選択する。
【０１１０】
○ステップＳ４０４
未選択のpμ(x)が存在するか否かを判定する。未選択のpμ(x)が存在しなければ、ステップＳ４０１の処理へ、存在するときはステップＳ４０５の処理へ、進む。
【０１１１】
○ステップＳ４０５
未選択のpμ(x)の中から、先頭のσjが１のものを一つ選択する。
＜解説＞
「先頭のσjが１のもの」とは、μ＝１の場合、σ2＝１であり、μ≠１の場合、σ1＝１である。ここで「先頭のσjが−１のもの」を選択しない理由は、次のとおりである。μ＝１の場合、pμ(x)=σ2e2(x)+…+σnen(x)=±e2(x)±…±en(x)であるから、式（１３）の左辺は、f(x)+tμeμ(x)+t・pμ(x)=f(x)+tμeμ(x)+t(±e2(x)±…±en(x))となる。ここでｔは正負の値を取る変数であるから、方程式としては実質的にf(x)+tμeμ(x)+t(e2(x)±…±en(x))=0を解けばよい。また、μ≠１の場合も同様で、方程式としては実質的にf(x)+tμeμ(x)+t(e1(x)±…±en(x))=0を解けばよい。従って、「先頭のσjが１のもの」を選択すれば十分である。この観点からすれば、「先頭のσjが１のもの」に限定されず、「先頭のσjが−１のもの」を選択するようにしてもよい。さらに云えば、集合{Σ1≦j≦n,j≠μ±ej(x)}の部分集合Ｙμを、集合{Σ1≦j≦n,j≠μ±ej(x)}に属する任意の二つの多項式P1，P2につきP1=-P2なる関係があるときいずれか一方を元とする集合として、多項式pμ(x)を部分集合Ｙμの中から選択するようにすることができる。この具体例を説明する。各μに対応して決められた二つの整数α、β〔但し、α、βは集合{1,2,…,n}に属し、互いに異なる。〕に対して、μ≠αの場合には、多項式pμ(x)を集合{Σ1≦j≦n,j≠μσjej(x)|σα=1,σj≠α=±1}から選択するようにし、μ＝αの場合には、多項式pμ(x)を集合{Σ1≦j≦n,j≠μσjej(x)|σβ=1,σj≠β=±1}から選択するようにすればよい。勿論、μ≠αの場合に、多項式pμ(x)を集合{Σ1≦j≦n,j≠μσjej(x)|σα=-1,σj≠α=±1}から選択するようにしてもよいし、μ＝αの場合に、多項式pμ(x)を集合{Σ1≦j≦n,j≠μσjej(x)|σβ=-1,σj≠β=±1}から選択するようにしてもよい。
【０１１２】
○ステップＳ４０６
式（３６）が定数ｃか否か判定する。定数ｃのときはステップＳ４０７の処理へ、定数でないときはステップＳ４１０の処理へ、進む。
【０１１３】
○ステップＳ４０７
ｓ∈Ｓkを任意に一つ取る。但し、式（３６）の分母が０となる点は除く。
【０１１４】
○ステップＳ４０８
ステップＳ４０７の処理で選択したｓが|tμ(γk(s))|＜|c|を満たすか否か判定する。ｓが|tμ(γk(s))|＜|c|を満たさない場合、このｓを候補とすることなくステップＳ４０４の処理へ進む。
【０１１５】
○ステップＳ４０９
ｓが|tμ(γk(s))|＜|c|を満たす場合、このｓを候補とする。続いて、ステップＳ４０４の処理へ進む。
【０１１６】
○ステップＳ４１０
式（３７）の零点およびＳkの端点を候補とする。但し、式（３６）の分母が０となる点は除く。
ステップＳ４１０の処理の後、ステップＳ４０４へ戻る。
【０１１７】
上記のアルゴリズムは一例に過ぎず、論理的な先後関係を逸脱しない限り、処理の順番を入れ替えたり変更したりすることができる。
例えば、３００番台の処理と４００番台の処理とを総じて入れ替えたアルゴリズムに変更することができる〔図２−１および図２−２参照〕。また、ステップＳ１の処理内容は全ての処理に先立ち行われることに限定されるものではない。例えば、次のようにも変更できる。ステップＳ１では単にＴ＝−１に設定するだけにする。そして、ステップＳ２２の処理の後、終了することなく、多項式ｆ~が恒等的に０となる場合の実数c1,c2,…,cnの存在を判定し、存在すればＴ1＝d(f,0)とする。さらに、Ｔ1とステップＳ２２の処理の段階でのＴとを比較してこの最小値を距離の最小値とする。また、上記のアルゴリズムでは、区分境界ごとに３００番台の処理と４００番台の処理を行うようにしたが、３００番台の処理を選択したq(x)につき区分境界ごとに行うようにしてもよいし、４００番台の処理を選択したμ、pμ(x)につき区分境界ごとに行うようにしてもよい。
【０１１８】
さらに、上記のアルゴリズムでは、有理数〔実代数的数〕a1,a2,…,anにて複素領域Ｄに多項式f(x)=e0(x)+Σj=1najej(x)の零点が存在しないことが予め既知のものとしたが、Sturmの定理と偏角の原理を用いて、複素領域Ｄに零点が存在しないことを確認する処理を前置で行うようにしてもよい。この場合、各区分境界Ｃkの有理式による表示だけでなく、各区分境界Ｃkからなる単純閉曲線である境界Ｃで囲まれた有界領域が複素領域Ｄであることを示すための指標、例えば複素領域Ｄの内部に属する一点も入力とする。
【０１１９】
また、上記のアルゴリズムは、多項式ｆと多項式ｆ~との距離の最小値を求めるものであったが、多項式ｆ~を出力するようにしてもよい。
この場合、一例として、上記アルゴリズムを次のように変更すればよい〔図３−１および図３−２参照〕。
・ステップＳ１を次のように変更する。
e0(x)+Σj=1ncjej(x)=0を満たす実数c1,c2,…,cnが存在する場合、Ｔ＝d(f,0)とする。このような実数c1,c2,…,cnが存在しない場合、Ｔ＝−１とする。また、Ｔ＝d(f,0)とき多項式Ｐを０とする。Ｔ＝−１とき多項式Ｐを−１とする。多項式Ｐ＝−１は、「領域Ｄに零点を持つ多項式であって式（５）で表される多項式の集合に属する多項式は存在しない」ということである。
・ステップＳ２２を次のように変更する。
未選択の区分境界が存在しなければ、Ｔの値をd(f,f~)として出力し、多項式Ｐを多項式ｆ~として出力して終了。
・ステップＳ３０３を次のように変更する。
未選択のq(x)が存在しなければ、全ての候補ｓに対応する、式（３１）の絶対値あるいは式（３２）の絶対値を計算し、それらの中の最小値|t0|を求める。Ｔ＝−１またはＴ＞|t0|の場合、Ｔ＝|t0|とする。つまり、Ｔの値を書き換える。また、Ｔの値を書き換えた場合、値t0を与えたときのq(x)を用いて式（３５）により求めた多項式を多項式Ｐとする。つまり、多項式Ｐを書き換える。もし、Ｔの値を書き換えなければ、多項式Ｐを書き換えない。
・ステップＳ４０２を次のように変更する。
未選択のμが存在しなければ、全ての候補ｓに対応して、連立方程式（１４）のｘにγk(s)を代入して得られる二元連立一次方程式を解いて、ｔおよびｔμの解ｔ<solution>およびｔμ<solution>を得る。このとき、候補となったｓに対応して得られるｔ<solution>のうちその絶対値が最小となるものの値をt0する。Ｔ＝−１またはＴ＞|t0|の場合、Ｔ＝|t0|とする。つまり、Ｔの値を書き換える。また、Ｔの値を書き換えた場合、値t0を与えたときのｔμ<solution>,0およびpμ,0(x)を用いて式（３８）により求めた多項式を多項式Ｐとする。つまり、多項式Ｐを書き換える。もし、Ｔの値を書き換えなければ、多項式Ｐを書き換えない。
【０１２０】
なお、最小距離Ｔに併せて多項式Ｐを出力することに限定するものではなく、多項式Ｐのみを出力するようにしてもよい。
【０１２１】
[第１実施形態]
以下に、本発明の第１実施形態を上記アルゴリズム例〔図１−１、図１−２参照〕に則して説明する。第１実施形態は、多項式f(x)=e0(x)+Σj=1najej(x) (aj∈Ｒ)と多項式f~(x)=e0(x)+Σj=1na~jej(x) (a~j∈Ｒ)との最小距離の算出〔多項式間距離算出〕に係わる。
図４は、本実施形態に係わる多項式間距離算出装置（１）のハードウェア構成を例示した構成ブロック図である。
【０１２２】
図４に例示するように、多項式間距離算出装置（１）は、キーボードなどが接続可能な入力部（１１）、液晶ディスプレイなどが接続可能な出力部（１２）、多項式間距離算出装置（１）外部に通信可能な通信装置（例えば通信ケーブル）が接続可能な通信部（１３）、ＣＰＵ（Central Processing Unit）（１４）〔キャッシュメモリやレジスタなどを備えていてもよい。〕、メモリであるＲＡＭ（１５）、ＲＯＭ（１６）やハードディスクである外部記憶装置（１７）並びにこれらの入力部（１１）、出力部（１２）、通信部（１３）、ＣＰＵ（１４）、ＲＡＭ（１５）、ＲＯＭ（１６）、外部記憶装置（１７）間のデータのやり取りが可能なように接続するバス（１８）を有している。また必要に応じて、多項式間距離算出装置（１）に、ＣＤ−ＲＯＭなどの記憶媒体を読み書きできる装置（ドライブ）などを設けるとしてもよい。このようなハードウェア資源を備えた物理的実体としては、汎用コンピュータなどがある。
【０１２３】
多項式間距離算出装置（１）の外部記憶装置（１７）には、多項式ｆと多項式ｆ~との最小距離の算出に必要となるプログラムおよびこのプログラムの処理において必要となるデータなどが記憶されている。また、これらのプログラムの処理によって得られるデータなどは、ＲＡＭや外部記憶装置などに適宜に記憶される。以下、演算結果やその格納領域のアドレスなどを記憶するＲＡＭ（１５）やレジスタなどの装置を単に「メモリ」と呼ぶことにする。
【０１２４】
より具体的には、多項式間距離算出装置（１）の外部記憶装置（１７）〔あるいはＲＯＭなど〕には、多項式ｆ~が恒等的に０となる場合について調査するための恒等式調査プログラム、多項式ｆ~について|aj-a~j|=d(f,f~)が全てのｊに対して成り立つ場合として区分境界Ｃkとq(x)の組み合わせ毎に得られる方程式（２０）の零点の候補を求めるための第一候補探索プログラム、第一候補探索プログラムによる処理で得られた各候補について対応して得られるｔ〔式（３１）、式（３２）参照〕の絶対値|t|で最小のものを決定するための第一距離候補決定プログラム、多項式ｆ~について或る番号μでは|aμ-a~μ|＜d(f,f~)でありｊ≠μでは|aj-a~j|=d(f,f~)が成り立つ場合として区分境界Ｃkとμとpμ(x)の組み合わせ毎に得られる方程式（１３）の零点の候補を求めるための第二候補探索プログラム、第二候補探索プログラムによる処理で得られた各候補について対応して得られるｔ〔式（１３）、式（１４）参照〕の絶対値|t|で最小のものを決定するための第二距離候補決定プログラム、第一候補探索プログラムと第一距離候補決定プログラムと第二候補探索プログラムと第二距離候補決定プログラムを区分境界毎に実行せしめて最小距離を出力するための探索制御プログラム、およびこれらのプログラムの処理において必要となるデータなどが記憶されている。その他、これらのプログラムに基づく処理などを制御するための制御プログラムも適宜に保存記憶しておく。
【０１２５】
多項式間距離算出装置（１）では、外部記憶装置（１７）〔あるいはＲＯＭなど〕に記憶された各プログラムとこの各プログラムの処理に必要なデータが必要に応じてメモリ（２０）に読み込まれて、適宜にＣＰＵ（１４）で解釈実行・処理される。その結果、ＣＰＵ（１４）が所定の機能（恒等式調査部、第一候補探索部、第一距離候補決定部、第二候補探索部、第二距離候補決定部、探索制御部、制御部）を実現する。
【０１２６】
図１−１、図１−２を参照して、本実施形態における多項式間距離算出処理について説明する。
【０１２７】
多項式間距離算出装置（１）の外部記憶装置（１７）には、予め、多項式e0(x),e1(x),e2(x),…,en(x)、有理数〔実代数的数〕a1,a2,…,an、多項式f(x)=e0(x)+Σj=1najej(x)の零点が存在しない複素領域Ｄの境界Ｃ＝∪k=1KＣkにつき、各区分境界Ｃkの有理式による表示〔各区分境界Ｃkは、単射γk ： Ｓk  →  Ｃkで表示される。〕がデータとして予め記憶されているとする。
【０１２８】
なお、これらの情報などは、予め多項式間距離算出装置（１）の外部記憶装置（１７）に記憶しておくのではなく、例えば、入力部（１１）から入力されるとしてもよいし、あるいは、これらの情報などを格納した記録媒体からドライブを駆動して読み込むようにしてもよく、適宜に変更可能である。
【０１２９】
また、データとして予め記憶される情報が、これらの情報などに限定される趣旨ではない。例えば、多項式e0(x),e1(x),e2(x),…,en(x)について、多項式そのものを記憶するのではなく、各次数のｘの項についてその係数を記憶しておくようにしてもよい。また、例えば、境界Ｃを表す式自体を入力部（１１）から入力するとし、境界Ｃを区分境界に適宜に分割するためのプログラムを解釈・実行するＣＰＵ（１４）が、メモリ（２０）に格納された境界Ｃをメモリ（２０）から読み込んで、区分境界を出力するようにしてもよい。
【０１３０】
なお、本発明の細部においては、数値計算処理のみならず有理式や多項式などの数式処理も必要となるが、数値計算処理および数式処理自体は、公知技術と同様にして達成されるので、その演算処理方法などの詳細な説明は省略する（この点の技術水準を示す数式処理が可能なソフトウェアとしては、例えば、Risa/Asir、Maple（登録商標）、MATHEMATICA（登録商標第2312968号）、Gnuplotなどが挙げられる。Risa/Asirについては、例えばインターネット〈URL:http://hpc.cs.ehime-u.ac.jp/risa/〉［平成19年7月2日検索］を参照のこと。Mapleについては、例えばインターネット〈URL:http://www.cybernet.co.jp/maple/〉［平成19年7月2日検索］を参照のこと。Gnuplotについては、例えばインターネット〈URL: http://www.gnuplot.info/〉［平成19年7月2日検索］を参照のこと。）。
【０１３１】
まず、多項式間距離算出装置（１）の制御部（１９０）は、外部記憶装置（１７）から多項式e0(x),e1(x),e2(x),…,en(x)、有理数〔実代数的数〕a1,a2,…,an、各区分境界Ｃkの有理式による表示γkを読み込み、それぞれをメモリ（２０）の所定の格納領域に格納しておく。以後、「メモリから○○を読み込む」旨の説明をした場合は、「メモリにおいて○○が格納されている所定の格納領域から○○を読み込む」ことを意味するとする。
【０１３２】
多項式間距離算出装置（１）の恒等式調査部（１１０）は、メモリ（２０）から多項式e0(x),e1(x),e2(x),…,en(x)を読み込み、e0(x)+Σj=1ncjej(x)=0を満たす実数c1,c2,…,cnの存在を判定する。恒等式調査部（１１０）は、そのような実数c1,c2,…,cnが存在すればＴ＝d(f,0)に設定してＴをメモリ（２０）の所定の格納領域に格納し、このような実数c1,c2,…,cnが存在しない場合は、Ｔ＝−１に設定してＴをメモリ（２０）の所定の格納領域に格納する〔図１−１のステップＳ１〕。
【０１３３】
次いで、多項式間距離算出装置（１）の探索制御部（１２０）は、未選択の区分境界の有無を判定する〔図１−１のステップＳ２０〕。未選択区分境界が存在しなければメモリ（２０）に記憶されているＴを液晶ディスプレイなどに表示する出力処理を行って多項式間距離算出処理を終了する〔図１−１のステップＳ２２〕。未選択区分境界が存在すれば未選択区分境界から一つ選択して、その情報をメモリ（２０）の所定の格納領域に格納する〔図１−１のステップＳ２１〕。
具体例として、探索制御部（１２０）は、区分境界Ｃk（k=1,2,…,K）について、k=1からインクリメントしてk=Kまで各処理を行うとすればよい。
また、探索制御部（１２０）は、ステップＳ２０の処理で未選択区分境界が存在しないと判定されるまで、後述の第一候補探索部（１３０）、第一距離候補決定部（１４０）、第二候補探索部（１５０）、第二距離候補決定部（１６０）の各動作を制御する。
【０１３４】
次いで、多項式間距離算出装置（１）の第一候補探索部（１３０）は、メモリ（２０）と協働して、多項式ｆ~について|aj-a~j|=d(f,f~)が全てのｊに対して成り立つ場合としてステップＳ２１で選択された区分境界Ｃkとq(x)の組み合わせ毎に得られる方程式（２０）の零点の候補を求め、これら候補をメモリ（２０）の所定の格納領域に格納する〔図１−１のステップＳ３０１〜Ｓ３１１。但し、ステップＳ３０３を除く。〕。なお、上記アルゴリズムに則する場合では、メモリ（２０）に格納される零点の候補は、ステップＳ２１で選択された区分境界Ｃkに対応するＳkに属するｓで与えられる。
【０１３５】
次いで、多項式間距離算出装置（１）の第一距離候補決定部（１４０）は、メモリ（２０）と協働して、第一候補探索部（１３０）による一連の処理で得られた各候補について対応して得られるｔ〔式（３１）、式（３２）参照〕の絶対値|t|で最小のもの|t0|を決定し、現段階でメモリ（２０）に記憶されているＴの値がＴ＝−１またはＴ＞|t0|の場合、メモリ（２０）に格納されているＴの値を|t0|に書き換えて格納する。ただし、Ｔ＝−１またはＴ＞|t0|が成立しない場合は、現段階でメモリ（２０）に記憶されているＴの値が維持される〔図１−１のステップＳ３０３〕。
【０１３６】
次いで、多項式間距離算出装置（１）の第二候補探索部（１５０）は、メモリ（２０）と協働して、多項式ｆ~について或る番号μでは|aμ-a~μ|＜d(f,f~)でありｊ≠μでは|aj-a~j|=d(f,f~)が成り立つ場合としてステップＳ２１で選択された区分境界Ｃkとμとpμ(x)の組み合わせ毎に得られる方程式（１３）の零点の候補を求め、これら候補をメモリ（２０）の所定の格納領域に格納する〔図１−２のステップＳ４０１〜Ｓ４０９。但し、ステップＳ４０２を除く。〕。なお、上記アルゴリズムに則する場合では、メモリ（２０）に格納される零点の候補は、ステップＳ２１で選択された区分境界Ｃkに対応するＳkに属するｓで与えられる。
【０１３７】
次いで、多項式間距離算出装置（１）の第二距離候補決定部（１６０）は、メモリ（２０）と協働して、第二候補探索部（１５０）による一連の処理で得られた各候補について対応して得られるｔ〔式（１３）、式（１４）参照〕の絶対値|t|で最小のもの|t0|を決定し、現段階でメモリ（２０）に記憶されているＴの値がＴ＝−１またはＴ＞|t0|の場合、メモリ（２０）に格納されているＴの値を|t0|に書き換えて格納する。ただし、Ｔ＝−１またはＴ＞|t0|が成立しない場合は、現段階でメモリ（２０）に記憶されているＴの値が維持される〔図１−２のステップＳ４０２〕。
【０１３８】
[第２実施形態]
以下に、本発明の第２実施形態を上記アルゴリズム例〔図３−１、図３−２参照〕に則して説明する。第２実施形態は、多項式f(x)=e0(x)+Σj=1najej(x) (aj∈Ｒ)と多項式f~(x)=e0(x)+Σj=1na~jej(x) (a~j∈Ｒ)との最小距離を与える多項式f~(x)の算出〔一変数最近実多項式算出〕に係わる。ここでは説明の便宜から、第１実施形態の最小距離の算出に加えて、多項式f~(x)も算出するものとして説明する。
【０１３９】
第２実施形態に係わる多項式間距離算出兼一変数最近実多項式算出装置のハードウェア構成は、図４に示した多項式間距離算出装置（１）のハードウェア構成と同様であるから、説明を略する。そこで、第２実施形態では、第１実施形態の多項式間距離算出装置（１）を、多項式間距離算出兼一変数最近実多項式算出装置（１）と呼称変更する。
【０１４０】
多項式間距離算出兼一変数最近実多項式算出装置（１）の外部記憶装置（１７）〔あるいはＲＯＭなど〕には、多項式ｆ~が恒等的に０となる場合について調査するための恒等式調査プログラム、多項式ｆ~について|aj-a~j|=d(f,f~)が全てのｊに対して成り立つ場合として区分境界Ｃkとq(x)の組み合わせ毎に得られる方程式（２０）の零点の候補を求めるための第一候補探索プログラム、第一候補探索プログラムによる処理で得られた各候補について対応して得られるｔ〔式（３１）、式（３２）参照〕の絶対値|t|で最小のものを決定すると共にこの最小値に対応する多項式を算出するための第一距離・多項式候補決定プログラム、多項式ｆ~について或る番号μでは|aμ-a~μ|＜d(f,f~)でありｊ≠μでは|aj-a~j|=d(f,f~)が成り立つ場合として区分境界Ｃkとμとpμ(x)の組み合わせ毎に得られる方程式（１３）の零点の候補を求めるための第二候補探索プログラム、第二候補探索プログラムによる処理で得られた各候補について対応して得られるｔ〔式（１３）、式（１４）参照〕の絶対値|t|で最小のものを決定すると共にこの最小値に対応する多項式を算出するための第二距離・多項式候補決定プログラム、第一候補探索プログラムと第一距離・多項式候補決定プログラムと第二候補探索プログラムと第二距離・多項式候補決定プログラムを区分境界毎に実行せしめて最小距離および多項式ｆ~を出力するための探索制御プログラム、およびこれらのプログラムの処理において必要となるデータなどが記憶されている。その他、これらのプログラムに基づく処理などを制御するための制御プログラムも適宜に保存記憶しておく。
【０１４１】
多項式間距離算出兼一変数最近実多項式算出装置（１）では、外部記憶装置（１７）〔あるいはＲＯＭなど〕に記憶された各プログラムとこの各プログラムの処理に必要なデータが必要に応じてメモリ（２０）に読み込まれて、適宜にＣＰＵ（１４）で解釈実行・処理される。その結果、ＣＰＵ（１４）が所定の機能（恒等式調査部、第一候補探索部、第一距離・多項式候補決定部、第二候補探索部、第二距離・多項式候補決定部、探索制御部、制御部）を実現する。
【０１４２】
図３−１、図３−２を参照して、本実施形態における多項式間距離算出兼一変数最近実多項式算出処理について説明する。
【０１４３】
多項式間距離算出兼一変数最近実多項式算出装置（１）の外部記憶装置（１７）には、予め、多項式e0(x),e1(x),e2(x),…,en(x)、有理数〔実代数的数〕a1,a2,…,an、多項式f(x)=e0(x)+Σj=1najej(x)の零点が存在しない複素領域Ｄの境界Ｃ＝∪k=1KＣkにつき、各区分境界Ｃkの有理式による表示〔各区分境界Ｃkは、単射γk ： Ｓk  →  Ｃkで表示される。〕がデータとして予め記憶されているとする。この点については第１実施形態と同様であり、例えば、これらの情報が入力部（１１）から入力されるとしてもよいし、多項式e0(x),e1(x),e2(x),…,en(x)について、多項式そのものを記憶するのではなく、各次数のｘの項についてその係数を記憶しておくようにしてもよい。また、数値計算処理および数式処理が、公知技術と同様にして達成されることも既述のとおりである。
【０１４４】
まず、多項式間距離算出兼一変数最近実多項式算出装置（１）の制御部（２９０）は、外部記憶装置（１７）から多項式e0(x),e1(x),e2(x),…,en(x)、有理数〔実代数的数〕a1,a2,…,an、各区分境界Ｃkの有理式による表示γkを読み込み、それぞれをメモリ（２０）の所定の格納領域に格納しておく。
【０１４５】
多項式間距離算出兼一変数最近実多項式算出装置（１）の恒等式調査部（２１０）は、メモリ（２０）から多項式e0(x),e1(x),e2(x),…,en(x)を読み込み、e0(x)+Σj=1ncjej(x)=0を満たす実数c1,c2,…,cnの存在を判定する。恒等式調査部（２１０）は、そのような実数c1,c2,…,cnが存在すればＴ＝d(f,0)、Ｐ＝０に設定してＴおよびＰをメモリ（２０）の所定の格納領域に格納し、このような実数c1,c2,…,cnが存在しない場合は、Ｔ＝−１、Ｐ＝−１に設定してＴおよびＰをメモリ（２０）の所定の格納領域に格納する〔図３−１のステップＳ１ａ〕。
【０１４６】
次いで、多項式間距離算出兼一変数最近実多項式算出装置（１）の探索制御部（２２０）は、未選択の区分境界の有無を判定する〔図３−１のステップＳ２０〕。未選択区分境界が存在しなければメモリ（２０）に記憶されているＴおよびＰを液晶ディスプレイなどに表示する出力処理を行って多項式間距離算出処理を終了する〔図３−１のステップＳ２２ａ〕。未選択区分境界が存在すれば未選択区分境界から一つ選択して、その情報をメモリ（２０）の所定の格納領域に格納する〔図３−１のステップＳ２１〕。
具体例としては、第１実施形態の場合と同様に、探索制御部（２２０）は、区分境界Ｃk（k=1,2,…,K）について、k=1からインクリメントしてk=Kまで各処理を行うとすればよい。
また、探索制御部（２２０）は、ステップＳ２０の処理で未選択区分境界が存在しないと判定されるまで、後述の第一候補探索部（２３０）、第一距離・多項式候補決定部（２４０）、第二候補探索部（２５０）、第二距離・多項式候補決定部（２６０）の各動作を制御する。
【０１４７】
次いで、多項式間距離算出兼一変数最近実多項式算出装置（１）の第一候補探索部（２３０）は、メモリ（２０）と協働して、多項式ｆ~について|aj-a~j|=d(f,f~)が全てのｊに対して成り立つ場合としてステップＳ２１で選択された区分境界Ｃkとq(x)の組み合わせ毎に得られる方程式（２０）の零点の候補を求め、これら候補をメモリ（２０）の所定の格納領域に格納する〔図３−１のステップＳ３０１〜Ｓ３１１。但し、ステップＳ３０３ａを除く。〕。なお、上記アルゴリズムに則する場合では、メモリ（２０）に格納される零点の候補は、ステップＳ２１で選択された区分境界Ｃkに対応するＳkに属するｓで与えられる。
【０１４８】
次いで、多項式間距離算出兼一変数最近実多項式算出装置（１）の第一距離・多項式候補決定部（２４０）は、メモリ（２０）と協働して、第一候補探索部（２３０）による一連の処理で得られた各候補について対応して得られるｔ〔式（３１）、式（３２）参照〕の絶対値|t|で最小のもの|t0|を決定し、現段階でメモリ（２０）に記憶されているＴの値がＴ＝−１またはＴ＞|t0|の場合、メモリ（２０）に格納されているＴの値を|t0|に書き換えて格納する。ただし、Ｔ＝−１またはＴ＞|t0|が成立しない場合は、現段階でメモリ（２０）に記憶されているＴの値が維持される。また、第一距離・多項式候補決定部（２４０）は、Ｔの値を書き換えた場合、値t0を与えたときのq(x)を用いて式（３５）により求めた多項式を多項式Ｐとして求め、メモリ（２０）に格納されている多項式をここで求められた多項式Ｐに書き換えて格納する。ただし、Ｔ＝−１またはＴ＞|t0|が成立しない場合は、現段階でメモリ（２０）に記憶されている多項式Ｐが維持される〔図３−１のステップＳ３０３ａ〕。
【０１４９】
次いで、多項式間距離算出兼一変数最近実多項式算出装置（１）の第二候補探索部（２５０）は、メモリ（２０）と協働して、多項式ｆ~について或る番号μでは|aμ-a~μ|＜d(f,f~)でありｊ≠μでは|aj-a~j|=d(f,f~)が成り立つ場合としてステップＳ２１で選択された区分境界Ｃkとμとpμ(x)の組み合わせ毎に得られる方程式（１３）の零点の候補を求め、これら候補をメモリ（２０）の所定の格納領域に格納する〔図３−２のステップＳ４０１〜Ｓ４０９。但し、ステップＳ４０２ａを除く。〕。なお、上記アルゴリズムに則する場合では、メモリ（２０）に格納される零点の候補は、ステップＳ２１で選択された区分境界Ｃkに対応するＳkに属するｓで与えられる。
【０１５０】
次いで、多項式間距離算出兼一変数最近実多項式算出装置（１）の第二距離・多項式候補決定部（２６０）は、メモリ（２０）と協働して、第二候補探索部（１５０）による一連の処理で得られた各候補について対応して得られるｔ〔式（１３）、式（１４）参照〕の絶対値|t|で最小のもの|t0|を決定し、現段階でメモリ（２０）に記憶されているＴの値がＴ＝−１またはＴ＞|t0|の場合、メモリ（２０）に格納されているＴの値を|t0|に書き換えて格納する。ただし、Ｔ＝−１またはＴ＞|t0|が成立しない場合は、現段階でメモリ（２０）に記憶されているＴの値が維持される。また、第二距離候補決定部（２６０）は、Ｔの値を書き換えた場合、値t0を与えたときのｔμ<solution>,0およびpμ,0(x)を用いて式（３８）により求めた多項式を多項式Ｐとして求め、メモリ（２０）に格納されている多項式をここで求められた多項式Ｐに書き換えて格納する。ただし、Ｔ＝−１またはＴ＞|t0|が成立しない場合は、現段階でメモリ（２０）に記憶されている多項式Ｐが維持される〔図３−２のステップＳ４０２ａ〕。
【０１５１】
第２実施形態では、最小距離と多項式ｆ~を出力するものとしたが、多項式ｆ~のみを出力するようにすれば、多項式間距離算出兼一変数最近実多項式算出装置（１）は一変数最近実多項式算出装置として動作することになる。
【０１５２】
本発明である多項式間距離算出装置、多項式間距離算出方法、一変数最近実多項式算出装置、一変数最近実多項式算出方法は上述の実施形態に限定されるものではなく、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。また、上記実施形態において説明した処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されるとしてもよい。
【０１５３】
また、上記実施形態において説明した多項式間距離算出装置、一変数最近実多項式算出装置における処理機能をコンピュータによって実現する場合、多項式間距離算出装置、一変数最近実多項式算出装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記多項式間距離算出装置、一変数最近実多項式算出装置における処理機能がコンピュータ上で実現される。
【０１５４】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ（Random Access Memory）、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）等を、光磁気記録媒体として、ＭＯ（Magneto-Optical disc）等を、半導体メモリとしてＥＥＰ−ＲＯＭ（Electronically Erasable and Programmable-Read Only Memory）等を用いることができる。
【０１５５】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【０１５６】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０１５７】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、多項式間距離算出装置、一変数最近実多項式算出装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【実施例】
【０１５８】
図１−１および図１−２に示したアルゴリズムに則った最小距離算出の具体的な実施例を説明する。
【０１５９】
f(x)=x2+2とし、j=0,1,2に対して、ej(x)=x2-jとする。領域Ｄをガウス平面上の単位円の周および内部からなる領域とする。領域Ｄの境界Ｃ、つまり単位円の周Ｃは、Ｃ1={1}とＣ2の和集合とする。但し、Ｃ1とＣ2は式（４１）のように表される。
【数５５】
0004778486.tif 000040
【０１６０】
このとき、領域Ｄに零点を持ち多項式ｆに最も近い多項式f~(x)=e0(x)+a~1e1(x)+a~2e2(x) (a~1,a~2∈Ｒ)を求める場合のアルゴリズムの挙動をしめす。
【０１６１】
・ステップＳ１
e0(x)+c1e1(x)+c2e2(x)=0となる実数c1,c2は存在しないので、Ｔ＝−１とする。
【０１６２】
・ステップＳ２０
未選択区分境界が存在する。ステップＳ２１へ進む。
【０１６３】
・ステップＳ２１
区分境界Ｃ1を選択する。
【０１６４】
・ステップＳ３０１〜ステップＳ３１１
q(x)はx+1とx-1の二通りである。
q(x)=x+1の場合、式（３０）は恒等的に成立する。また、条件Re q(γ1(s))≠０は２≠０であるから常に成立する。一方、Im q(γ1(s))≠０は０≠０であるから常に不成立である。式（３１）は定数３／２である。式（３２）は分母が０となるから考慮しない。従って、ｓの候補はただ一点、１である。このとき|t|=3/2である。
q(x)=x-1の場合、式（３０）は恒等的に成立する。また、条件Re q(γ1(s))≠０は０≠０であるから常に不成立である。一方、Im q(γ1(s))≠０も０≠０であるから常に不成立である。よって、この場合、候補となるｓは存在しない。
以上から、全ての候補ｓに対する|t|の最小値は３／２であり、Ｔ＝３／２となる。
【０１６５】
・ステップＳ４０１〜ステップＳ４０９
μ＝１のとき、pμ(x)=1のみである。
μ＝２のとき、pμ(x)=xのみである。
いずれの場合も、式（３６）の分母が恒等的に０となるから候補はなく、Ｔの置換は生じない。
【０１６６】
・ステップＳ２０
未選択区分境界が存在する。ステップＳ２１へ進む。
【０１６７】
・ステップＳ２１
区分境界Ｃ2を選択する。
【０１６８】
・ステップＳ３０１〜ステップＳ３１１
q(x)はx+1とx-1の二通りである。
q(x)=x+1の場合、式（３０）は(2s3-6s)/(s2+1)2=0であり、これを条件「2s2/(s2+1)≠0あるいは-2s/(s2+1)≠0」の下で解く。これは、s2-3=0を解くことと同値である。それゆえ、ｓの候補は、±√３である。このときs=±√３に対して|t|=1である。
q(x)=x-1の場合、式（３０）は(-2s3+6s)/(s2+1)2=0であり、これを条件「-2/(s2+1)≠0あるいは-2s/(s2+1)≠0」の下で解く。これは、s2-3=0を解くことと同値である。それゆえ、ｓの候補は、±√３である。このときs=±√３に対して|t|=1である。
以上から、全ての候補ｓに対する|t|の最小値は１であり、Ｔの値は３／２から１に置き換わる。
【０１６９】
・ステップＳ４０１〜ステップＳ４０９
μ＝１のとき、pμ(x)=1について調べる。このとき式（３６）は１（定数）となり、t1=(-2s2+2)/(s2+1)である。|t1|<１となるｓの値が候補となるが、これはｓ２＜３あるいは３ｓ２＞１であるから空集合ではなく|t|=1（定数）である。
μ＝２のとき、pμ(x)=xについて調べる。このとき式（３６）は(2s2-2)/(s2+1)である。これは定数ではないから、t(γ2(s))をsで微分して8s/(s4+2s2+1)を得る。従って、ｓの候補は０のみであり、このとき|t|=2となる。
以上から、この場合の|t|の最小値は１である。現段階で保存されているＴの値は１であるから、Ｔの置き換えは生じない。
【０１７０】
・ステップＳ２０
未選択区分境界は存在しない。ステップＳ２２へ進む。
【０１７１】
・ステップＳ２２
Ｔの値、つまり１を出力して終了する。
【産業上の利用可能性】
【０１７２】
本発明は、例えば、複素領域Ｄに零点を持たないように多項式の係数を設定したい場合に、係数設定に誤差を伴うことを前提として、誤差付きで設定される多項式が間違いなく複素領域Ｄに零点を持たないようにするときに、その誤差限界の確定などとして用いることができる。このような場合の一例として、ディジタル信号処理におけるディジタルフィルタ（例えば、ＩＩＲ〔Infinite Impulse Response〕フィルタ）の設計などに有用である。
【図面の簡単な説明】
【０１７３】
【図１−１】第１実施形態の多項式間距離算出処理のフローチャート（其の壱）。
【図１−２】第１実施形態の多項式間距離算出処理のフローチャート（其の弐）。
【図２−１】第１実施形態の多項式間距離算出処理の変形例のフローチャート（其の壱）。
【図２−２】第１実施形態の多項式間距離算出処理の変形例のフローチャート（其の弐）。
【図３−１】第２実施形態の多項式間距離算出兼一変数最近実多項式算出処理のフローチャート（其の壱）。
【図３−２】第２実施形態の多項式間距離算出兼一変数最近実多項式算出処理のフローチャート（其の弐）。
【図４】多項式間距離算出装置（１）のハードウェア構成を例示した構成ブロック図。
【図５】多項式間距離算出処理の処理機能を示す機能ブロック図。
【図６】多項式間距離算出兼一変数最近実多項式算出処理の処理機能を示す機能ブロック図。
【符号の説明】
【０１７４】
１        多項式間距離算出装置
１１０    常等式調査部
１２０    探索制御部
１３０    第１候補探索部
１４０    第１距離候補決定部
１５０    第２候補探索部
１６０    第２距離候補決定部
２１０    常等式調査部
２２０    探索制御部
２３０    第１候補探索部
２４０    第１距離・多項式候補決定部
２５０    第２候補探索部
２６０    第２距離・多項式候補決定部
【図１−１】
0004778486.tif 000081
【図１−２】
0004778486.tif 000082
【図２−１】
0004778486.tif 000083
【図２−２】
0004778486.tif 000084
【図３−１】
0004778486.tif 000085
【図３−２】
0004778486.tif 000086
【図４】
0004778486.tif 000087
【図５】
0004778486.tif 000088
【図６】
0004778486.tif 000089