実根分離とは？わかりやすく解説

数学、特に数値解析とコンピュータ代数において、多項式の実根分離（じつこんぶんり、英語: Real-root isolation）とは、実数直線の互いに素な区間を生成することであり、これらの区間は多項式の実根をそれぞれ1つだけ含み、また全体としては多項式のすべての実根を含む。

実根分離が有用なのは、多項式の実根を計算する通常の求根アルゴリズムは、いくつかの実根（の探索結果）を生成することはあっても、一般にすべての実根が探索されたことを証明できないためである。特に、そのようなアルゴリズムで根が探索されない場合、それが実根が存在しないからなのかどうかは分からない。いくつかのアルゴリズムはすべての複素根を計算するが、一般に実根は複素根よりもはるかに少ないため、計算時間の大部分は非実根の計算に費やされる（平均して、次数 $n$ の多項式には $n$ 個の複素根があり、実根は $log n$ 個しかない。多項式の根の性質の『実根』（英語版）を参照）。さらに、虚部が小さい非実根と実根を区別することが困難な場合がある（次のセクションのウィルキンソンの多項式（英語版）の例を参照）。

最初の完全な実根分離アルゴリズムはスツルムの定理（1829年）から得られた。しかし、実根分離アルゴリズムがコンピュータに実装され始めたとき、スツルムの定理から導かれたアルゴリズムはデカルトの符号法則（1637年）から導かれたアルゴリズムよりも効率が悪いことがわかった。20世紀初頭以来、デカルトの符号法則から導かれるアルゴリズムの改良と、きわめて効率的な実装の実現、そしてそれらの計算複雑度（英語版）の決定に関する研究が盛んに行われてきた。最良の実装は、1,000次を超える多項式の実根を問題なく分離することができる。^[1]^[2]

仕様と一般的な戦略

多項式の実根を求める一般的な戦略は、実数直線（または根を求める区間）を、各区間に根が最大で1つになるまで互いに素な区間に分割することである。このような手順は根分離と呼ばれ、結果として得られる区間にちょうど1つの根が含まれる場合、その根の分離区間となる。

ウィルキンソンの多項式（英語版）は、多項式の1つの係数をわずかに変更するだけで、根の値だけでなく、根の性質（実数か複素数か）も劇的に変化する可能性があることを示している。また、良好な近似値を用いても、近似根で多項式を評価すると、結果がゼロに非常に近くなる場合がある。例えば、20次（ウィルキンソン多項式の次数）の多項式の根が10に近い場合、その根における多項式の導関数は $10^{20}$

Obreschkoff–Ostrowski の定理：青と黄色は、0または1の符号変化を持つべき複素平面上の根が存在しない領域。左側は

p

の根が除外される領域、右側は変換された多項式

q

の根が除外される領域。青色で示されているのは、符号変化が1回であるため除外されている領域で、符号変化が0回の場合を許容している。

定理 (Obreschkoff–Ostrowski) ― ヴァンサンの補助定理の結論は、多項式 $p (x)$ が

\left(\alpha -{\frac {a}{c}}\right)\left(\alpha -{\frac {b}{d}}\right)+\beta ^{2}\leq {\frac {1}{\sqrt {3}}}\left|\beta \left({\frac {a}{c}}-{\frac {b}{d}}\right)\right|

となる根 $α + iβ$ を最大で1つ持つ場合に成立する。特に、この結論は

\left|{\frac {a}{c}}-{\frac {b}{d}}\right|<{\frac {\operatorname {sep} (p)}{2{\sqrt {3}}}}

の場合に成立する。ここで $sep(p)$ は $p$ の2つの根間の最小距離である。

整数係数を持つ多項式の場合、最小距離 $sep(p)$ は、多項式の次数とその係数の絶対値の最大値によって下限が定められる（多項式の根の性質の『根の分離』（英語版）を参照）。これにより、ヴァンサンの定理に基づくアルゴリズムの最悪ケースの複雑度（英語版）を解析できる。しかし、Obreschkoff–Ostrowski の定理によれば、これらのアルゴリズムの反復回数は、動作区間の近傍における根間の距離に依存するため、同じ多項式でも異なる根に対して反復回数は大きく異なる可能性がある。

James V. Uspensky（英語版）は、連分数（ヴァンサンの定理における整数 $k$ ）の長さについて、符号変化が0または1となる上限を与えた^[1]^[7]。

定理 (Uspensky) ― $p (x)$ を $n$ 次の多項式とし、 $sep(p)$ を $p$ の2つの根の間の最小距離とする。

\varepsilon =\left(n+{\frac {1}{n}}\right)^{\frac {1}{n-1}}-1

とすると、ヴァンサンの定理で存在するとされている整数 $k$ は、

F_{h-1}\operatorname {sep} (p)>2\quad {\text{and}}\quad F_{h-1}F_{k}\operatorname {sep} (p)>{\frac {1}{\varepsilon }}

となる最小の整数 $h$ より大きくない。ここで $F_{h}$ は $h$ 番目のフィボナッチ数である。

連分数法

実根分離における連分数の使用はヴァンサンによって導入されたが、彼はジョゼフ＝ルイ・ラグランジュの成果を引用しながらも、出典を示していない^[4]。ヴァンサンの定理のアルゴリズムを作成するには、彼の定理に現れる $a_{i}$ を選択するための基準を与える必要がある。ヴァンサン自身もいくつかの選択肢を提示している（下記参照）。他にも選択肢があり得るが、アルゴリズムの効率はこれらの選択肢に大きく依存する可能性がある。以下に、これらの選択肢が後述する補助関数によって決定されるアルゴリズムを示す。

このアルゴリズムを実行するには、特定のデータ構造で表される区間のリストを使用する必要がある。このアルゴリズムは、区間を選択し、リストから削除し、0、1、または2つのより小さな区間をリストに追加し、場合によっては分離区間を出力するという動作をする。

次数 $n$ の多項式 $p (x)$ の実根を分離するために、各区間は $(A(x),M(x))$ のペアで表される。ここで、 $A (x)$ は次数 $n$ の多項式であり、 $M(x)={\frac {px+r}{qx+s}}$ は整数係数のメビウス変換である。ひとつは

A(x)=p(M(x)),

で、このデータ構造で表される区間は、 $M(\infty )={\frac {p}{q}}$ と $M(0)={\frac {r}{s}}$ を端点とする区間である。メビウス変換は、この区間における $p$ の根を、 $(0, +\infty)$ における $A$ の根に写像する。

このアルゴリズムは、区間のリストを用いて動作する。リストには、最初に、実数を正と負の数に分割する2つの区間 $(A(x)=p(x),M(x)=x)$ と $(A(x)=p(-x),M(x)=-x)$ が含まれる（ゼロは根ではないと仮定することもできる。もしゼロが根であるならば、このアルゴリズムを $p (x)/ x$ に適用すれば良い）。次に、リスト内の各区間 $(A (x), M (x))$ について、アルゴリズムはそれをリストから削除する。 $A$ の係数の符号変化の数が 0 の場合、区間に根は存在せず、次の区間に進む。符号変化の数が 1 の場合、 $M(0)$ と $M(\infty )$ によって定義される区間は分離区間である。それ以外の場合は、正の実数 $b$ を使用して区間 $(0, +\infty)$ を $(0, b)$ と $(b, +\infty)$ に分割し、各部分区間について、区間を $(0, +\infty)$ にマッピングするメビウス変換を使用して $M$ を合成し、リストに追加する2つの新しい区間を取得する。擬似コードは次のようになる。ここで、 $var(A)$ は多項式 $A$ の係数の符号変化の数を示す。

function continued fraction is
    input: P(x) 平方無縁多項式（英語版）
    output: 分離区間を定義する有理数のペアのリスト
    /* 初期化 */
        L := [(P(x), x), (P(–x), –x)]                /* 2つの開始区間 */
        Isol := [ ]
    /* 計算 */
    while L  $\neq$  [ ] do
        Choose (A(x), M(x)) in L, and remove it from L
        v := var(A)
        if v = 0 then exit                /* 区間内に根がない */
        if v = 1 then                     /* 分離区間が見つかった */
            add (M(0), M(∞)) to Isol
            exit
        b := some positive integer
        B(x) = A(x + b)
        w := v – var(B)
        if B(0) = 0 then                         /* 有理根が見つかった */
            add (M(b), M(b)) to Isol
            B(x) := B(x)/x
        add (B(x),  M(b + x)) to L           /* (M(b), M(+∞)) の根 */
        if w = 0 then exit                  /* ブダンの定理 */ 
        if w = 1 then                       /* 再度ブダンの定理 */ 
            add (M(0), M(b)) to Isol
        if w > 1 then
            add ( A(b/(1 + x)),  M(b/(1 + x)) )to L      /* (M(0), M(b)) の根 */

アルゴリズムの様々なバリエーションは、基本的に $b$ の選択に依存する。ヴァンサンの論文とUspenskyの著書では、常に $b = 1$ としているが、Uspenskyは $(0, b)$ に関連付けられた区間の更なる二分を避けるため、ブダンの定理を用いていない、という違いがある。

常に $b = 1$ を選択することの欠点は、 $x \to 1 + x$ という形式の変数変換を何度も連続して行わなければならないことである。これは単一の変数変換 $x \to n + x$ で置き換えることもできるが、それでもブダンの定理を適用するためには、中間の変数変換を行う必要がある。

アルゴリズムの効率を改善する方法は、 $b$ に対して、多項式の係数から計算された正の実根の下限値を取ることである（このような下限値については多項式の根の性質（英語版）を参照）。^[8]^[1]

二分法

大まかに言うと、二分法は多項式のすべての実根を含む区間から出発し、それを再帰的に2つの部分に分割し、最終的に0個または1個の根を含む区間を得るというものである。開始区間は $(- B, B)$ という形式を取ることができる。ここで、 $B$ は根の絶対値の上限であり、例えば「多項式の根の性質の『（複素）多項式の根の境界』（英語版）」で与えられる。技術的な理由（変数変換の単純化、複雑度解析の単純化、コンピュータの2元解析を活用できる可能性など）により、アルゴリズムは一般的に区間 $[0, 1]$ から開始するものとして提示される。変数 $x = By$ と $x = - By$ の変換により、それぞれ区間 $[0, 1]$ 内の正の根と負の根が移動するため、一般性が失われることはない。(変数 $x = (2 By - B)$ の変換も使用できる)

この方法では、区間に0個、1個、あるいは複数の根が存在するかどうかをテストするアルゴリズムが必要である。また、終了を保証するために、このテストアルゴリズムは「複数の根が存在する可能性」が無限回出力される可能性を排除する必要がある。スツルムの定理とヴァンサンの補助定理は、このような便利なテストを提供する。デカルトの符号法則とヴァンサンの補助定理の使用は、スツルムの定理の使用よりもはるかに計算効率が高いため、このセクションでは前者についてのみ説明する。

デカルトの符号法則とヴァンサンの補助定理に基づく二分法は、1976年にAkritasとCollins（英語版）によって「修正Uspenskyアルゴリズム」^[3]という名称で導入され、「Uspenskyアルゴリズム」、「Vincent–Akritas–Collins アルゴリズム」、あるいは「デカルト法」とも呼ばれてきたが、デカルト、ヴァンサン、Uspenskyが実際にこの方式を記述したことはない。

この方式は以下のように機能する。ある区間における根を求めるには、まずその区間を $[0, 1]$ に写像するため変数を変換し、新しい多項式 $q (x)$ を生成する。 $[0, 1]$ における $q$ の根を求めるには、変数変換 $x\to {\frac {1}{x+1}}$ によって区間 $[0, 1]$ を $[0, +\infty])$ ^{[訳注 1]} に写像して、多項式 $r (x)$ を得る。多項式 $r$ にデカルトの符号法則を適用すると、区間 $[0, 1]$ における $q$ の実根の個数が示され、したがって、 $[0, 1]$ に写像された区間における初期多項式の根の個数が示される。 $r$ の係数のシーケンスに符号変化がない場合、考慮されている区間に実根は存在しない。符号変化が1つある場合は、孤立区間となる。それ以外の場合、区間 $[0, 1]$ を $[0, 1/2]$ と $[1/2, 1]$ に分割し、変数変換 $x = y /2$ と $x = (y + 1)/2$ によって、これらを $[0, 1]$ に写像する。ヴァンサンの補助定理により、この手順は確実に終了する。

初期化を除けば、これらの変数変換はすべて、最大で2つの非常に単純な変数変換、すなわち2倍のスケーリング $x \to x /2$ 、平行移動 $x \to x + 1$ 、および逆数 $x \to 1/ x$ の組み合わせで構成される。逆数は、多項式の係数の順序を単純に反転するだけである。計算時間のほとんどは変数の変換に費やされるため、すべての区間を $[0, 1]$ にマッピングする方法は、優れた効率を確保するための基本となる。

擬似コード

以下の擬似コードでは、次の表記法が使用されている。

$p (x)$ は、区間 $[0, 1]$ 内の実根が孤立している必要がある多項式である。
$var(q (x))$ は、多項式 $q$ の係数列における符号変化の数を表す。
作業リストの要素は (c, k, q(x)) の形式を持つ。
- $c$ と $k$ は、 $c < 2 k$ を満たす 2 つの非負整数で、区間 $\left[{\frac {c}{2^{k}}},{\frac {c+1}{2^{k}}}\right]$ を表す。
- $q(x)=2^{kn}p\left({\frac {x+c}{2^{k}}}\right)$ 、ただし $n$ は $p$ の次数。（多項式 $q$ は $p$ , $c$ および $k$ から直接計算できるが、アルゴリズム内で行われるよう逐次的に計算する方がコストが低くなる。 $p$ に整数係数がある場合、 $q$ についても同様）

function bisection is
    input:  $p (x)$   $p (0) p (1) \neq 0$  を満たす平方無縁多項式（英語版）、
                      区間  $[0, 1]$  内の根が探索される
    output: 3つの数の組  $(c, k, h)$  のリスト、
                      形式  $\left[{\frac {c}{2^{k}}},{\frac {c+h}{2^{k}}}\right]$  の分離区間を表す
    /* 初期化 */
    L := [(0, 0, p(x))] /* 作業リスト L 内の単一要素 */
    Isol := [ ]
    n := degree(p)
    /* 計算 */
    while L  $\neq$  [ ] do
        Choose (c, k,  $q (x))$  in L, and remove it from L
        if  $q (0) = 0$  then
             $q (x) := q (x)/ x$ 
            n := n – 1                /* 有理根が見つかった */
            add (c, k, 0) to Isol
        v :=  $\operatorname {var} ((x+1)^{n}q(1/(x+1)))$ 
        if v = 1 then                /* 分離区間が見つかった */
            add (c, k, 1) to Isol
        if v > 1 then                /* 二分する */
            add (2c, k + 1,  $2^{n}q(x/2)$   to L
            add (2c + 1, k + 1,  $2^{n}q((x+1)/2)$   to L
    end

この手順は、CollinsとAkritasによって記述されたものと本質的に同じである^[3]。実行時間は主に、考慮しなければならない区間の数と変数の変化に依存する。効率を向上させる方法はいくつかあり、アルゴリズムの発表以来、特に21世紀初頭から活発に研究されてきた。

脚注

訳注

^ $[0, +\infty])$ は原文の通り。

出典

参考文献

Alesina, Alberto; Massimo Galuzzi (1998). “A new proof of Vincent's theorem”. L'Enseignement Mathématique 44 (3–4): 219–256. オリジナルの2014-07-14時点におけるアーカイブ。 2018年12月16日閲覧。.
Akritas, Alkiviadis G. (1986). There's no "Uspensky's Method". Proceedings of the fifth ACM Symposium on Symbolic and Algebraic Computation (SYMSAC '86). Waterloo, Ontario, Canada. pp. 88–90.
Akritas, Alkiviadis G.; Strzeboński, A. W.; Vigklas, P. S. (2008). “Improving the performance of the continued fractions method using new bounds of positive roots”. Nonlinear Analysis: Modelling and Control 13 (3): 265–279. doi:10.15388/NA.2008.13.3.14557.
Akritas, Alkiviadis G.; Strzeboński, Adam W. (2005). “A Comparative Study of Two Real Root Isolation Methods”. Nonlinear Analysis: Modelling and Control 10 (4): 297–304. doi:10.15388/NA.2005.10.4.15110.
Collins, George E.; Akritas, Alkiviadis G. (1976). Polynomial Real Root Isolation Using Descartes' Rule of Signs. SYMSAC '76, Proceedings of the third ACM symposium on Symbolic and algebraic computation. Yorktown Heights, NY, USA: ACM. pp. 272–275. doi:10.1145/800205.806346.
Kobel, Alexander; Rouillier, Fabrice; Sagraloff, Michael (2016). “Computing real roots of real polynomials ... and now for real!”. ISSAC '16, Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation. Waterloo, Canada. arXiv:1605.00410. doi:10.1145/2930889.2930937.
Obreschkoff, Nikola (1963) (ドイツ語). Verteilung und Berechnung der Nullstellen reeller Polynome. Berlin: VEB Deutscher Verlag der Wissenschaften. p. 81
Ostrowski, A. M. (1950). “Note on Vincent's theorem”. Annals of Mathematics. Second Series 52 (3): 702–707. doi:10.2307/1969443. JSTOR 1969443.
Rouillier, F.; Zimmerman, P. (2004). “Efficient isolation of polynomial's real roots”. Journal of Computational and Applied Mathematics 162 (1): 33–50. Bibcode: 2004JCoAM.162...33R. doi:10.1016/j.cam.2003.08.015.
Sagraloff, M.; Mehlhorn, K. (2016). “Computing real roots of real polynomials”. Journal of Symbolic Computation 73: 46–86. arXiv:1308.4088. doi:10.1016/j.jsc.2015.03.004.
Tsigaridas, Elias P.; Emiris, Ioannis Z. (2006). “Univariate Polynomial Real Root Isolation: Continued Fractions Revisited”. In Azar, Yossi; Erlebach, Thomas (eds.). Algorithms - ESA 2006, 14th Annual European Symposium, Zurich, Switzerland, September 11-13, 2006, Proceedings. Lecture Notes in Computer Science. Vol. 4168. Springer. pp. 817–828. arXiv:cs/0604066. doi:10.1007/11841036_72. ISBN 978-3-540-38875-3.
Uspensky, James Victor (1948). Theory of Equations. New York: McGraw–Hill Book Company
Vincent, Alexandre Joseph Hidulphe (1834). “Mémoire sur la résolution des équations numériques” (フランス語). Mémoires de la Société Royale des Sciences, de L' Agriculture et des Arts, de Lille: 1–34.
Vincent, Alexandre Joseph Hidulphe (1836). “Note sur la résolution des équations numériques”. Journal de Mathématiques Pures et Appliquées 1: 341–372.
Vincent, Alexandre Joseph Hidulphe (1838). “Addition à une précédente note relative à la résolution des équations numériques”. Journal de Mathématiques Pures et Appliquées 3: 235–243. オリジナルの2013-10-29時点におけるアーカイブ。 2018年12月16日閲覧。.

実根分離とは？わかりやすく解説

実根分離

仕様と一般的な戦略

連分数法

二分法

擬似コード

最近の改良

脚注

訳注

出典

参考文献

関連項目

実根分離とは？ わかりやすく解説

実根分離

仕様と一般的な戦略

連分数法

二分法

擬似コード

最近の改良

脚注

訳注

出典

参考文献

関連項目

急上昇のことば

実根分離とは？わかりやすく解説