ヴァンサンの定理

数学において、アレクサンドル・ジョゼフ・イドゥルフ・ヴァンサン（フランス語版）^{[訳注 1]}（フランス語: Alexandre Joseph Hidulphe Vincent）にちなんで名付けられたヴァンサンの定理（ヴァンサンのていり、ヴィンセントの定理、英語: Vincent's theorem）は、有理係数を持つ多項式の実根を分離する定理である。

ヴァンサンの定理は、多項式の実根を分離する最速の方式の基礎であるにもかかわらず、スツルムの定理の影に隠れ、ほぼ完全に忘れ去られていた。その結果、Uspensky（英語版）の著書を除いて、方程式論に関する20世紀の古典的な書籍には登場しない。この定理の2つの変種と、それらから導かれるいくつかの実根分離法（連分数法と二分法）が提示される。

符号変化

c₀, c₁, c₂, ... を有限または無限の実数列とする。l < r であり、以下の条件が成り立つものとする。

1. r = l+1 の場合、数 c_l と c_r は符号が逆になる。
2. r ≥ l+2 の場合、数 c_l+1, ..., c_r−1 はすべてゼロとなり、数 c_l と c_r は符号が逆になる。

これは、数 c_l と c_r の間の符号変化（sign variation または sign change）と呼ばれる。

一変数多項式 p(x) を扱う場合、p(x) の符号変化の数を、その係数の数列内の符号変化の数として定義する。

この定理には2つのバージョンがある。ヴァンサンによる連分数版^[1][2][3] と、AlesinaとGaluzziによる二分法版^[4][5] である。

ヴァンサンの定理：連分数版（1834および1836年）

有理係数を持ち、多重根を持たない多項式方程式において、次の形式の変換を連続的に行うとする。

${\displaystyle x=a_{1}+{\frac {1}{x'}},\quad x'=a_{2}+{\frac {1}{x''}},\quad x''=a_{3}+{\frac {1}{x'''}},\ldots }$

ここで ${\displaystyle a_{1},a_{2},a_{3},\ldots }$ は1以上の任意の正数である。このような変換を複数回行った後、結果として得られる変換された方程式は符号変化が0個か、1個の符号変化を持つかのいずれかになる。前者の場合、根は存在しないが、後者の場合、正の実根が1個存在する。さらに、提案された方程式の対応する根は有限連分数で近似される。^[1][2][3]

${\displaystyle a_{1}+{\cfrac {1}{a_{2}+{\cfrac {1}{a_{3}+{\cfrac {1}{\ddots }}}}}}}$

さらに、この性質を満たす無限の数 ${\displaystyle a_{1},a_{2},a_{3},\ldots }$ が見つかる場合、根は（無限の）対応する連分数で表される。

上記の記述は、ヴァンサンの原論文^[1][2][3]に見られる定理の正確な翻訳である。ただし、より明確な理解のために以下の説明が必要である。

• ${\displaystyle f_{n}(x)}$ が n 回の置換（および分母の除去）後に得られる多項式を表す場合、すべての ${\displaystyle n\geq N}$ に対して ${\displaystyle f_{n}(x)}$ が符号変化を持たないか、1つの符号変化を持つような N が存在する。後者の場合、${\displaystyle f_{n}(x)}$ はすべての ${\displaystyle n\geq N}$ に対して1つの正の実根を持つ。
• 連分数は元の方程式の正根を表し、元の方程式は複数の正根を持つ場合がある。さらに、${\displaystyle a_{1}\geq 1}$ と仮定すると、元の方程式の根は1より大きいものしか得られない。任意の正根を得るには、${\displaystyle a_{1}\geq 0}$ と仮定する必要がある。
• 負根は x を -x に置き換えることによって得られる。この場合、負根は正になる。

ヴァンサンの定理：二分法版（AlesinaとGaluzzi 2000年）

p(x) を、単根のみを持つ次数 deg(p) の実多項式とする。 ${\displaystyle |b-a|<\delta }$ を満たす任意の正の実数 a、b のペアに対して、形式

${\displaystyle f(x)=(1+x)^{\deg(p)}p\left({\frac {a+bx}{1+x}}\right)}$

(1)

の変換された多項式が正確に0または1個の符号変化を持つような正の値 δ を定めることができる。2番目のケースは、p(x) が (a, b) 内に単一の根を持つ場合にのみ可能である。

Alesina–Galuzziの「a_b根検定」

式 (1) から、多項式が区間 (a, b) 内に根を持つかどうかを判定するための以下の基準が得られる。

p(x) に次の置換を実行する。

${\displaystyle x\leftarrow {\frac {a+bx}{1+x}}}$

そして、変換された多項式の係数列における符号変化の数を数える。この数は、開区間 (a, b) 内における p(x) の実根の数の「上限」を与える。より正確には、次数 deg(p) の R[x] における多項式 p(x) の開区間 (a, b) における実根の数（重複度も数えられる）ρ_ab(p) は、符号変化 var_ab(p) の数によって上限が定められる。ここで

${\displaystyle \operatorname {var} _{ab}(p)=\operatorname {var} \left((1+x)^{\deg(p)}p\left({\frac {a+bx}{1+x}}\right)\right)}$

${\displaystyle \operatorname {var} _{ab}(p)=\operatorname {var} _{ba}(p)\geq \rho _{ab}(p)}$

デカルトの符号法則の場合と同様に、var_ab(p) = 0 であれば ρ_ab(p) = 0 となり、var_ab(p) = 1 であれば ρ_ab(p) = 1 となる。

Alesina–Galuzziの「a_b根検定」の特殊なケースは、ブダンの「0_1根検定」である。

証明の概要

ヴァンサンの定理、その拡張、関連する変換の幾何学的解釈、そして3つの異なる証明についての詳細な議論は、AlesinaとGaluzziの著作^[4][5]に見ることができる。4つ目の証明はOstrowski（英語版）によるもの^[6]で、彼はObreschkoff（英語版）が1920～1923年に述べた定理^[7]（p. 81）の特殊なケースを再発見した。

ヴァンサンの定理（両方のバージョン）を証明するために、AlesinaとGaluzziは、定理に記載されている一連の変換の後、1つの正根を持つ多項式は最終的に1つの符号変化を持つことを示す。これを示すために、彼らは前述の1920～1923年のObreschkoff（英語版）の定理に対する次の系を用いている。すなわち、次の系は、1つの正根を持つ多項式がその係数の列においてちょうど1つの符号変化を持つための必要条件を与える。対応する図も参照のこと。

系（Obreschkoff（英語版）の円錐定理または扇形定理 1920–1923^[7] p. 81）：実多項式が1つの単純根 x₀ を持ち、他のすべての根（重複を許容）が扇形内にある場合、

${\displaystyle S_{\sqrt {3}}=\left\{x=-\alpha +i\beta \$ :\ |\beta |\leq {\sqrt {3}}|\alpha |,\alpha >0\right\}}

その係数列はちょうど1つの符号変化を持つ。

Obreschkoff（英語版）の ${\displaystyle S_{\sqrt {3}}}$ セクターと彼の有名な8の字型図形（円）

ここで、メビウス変換

${\displaystyle M(x)={\frac {ax+b}{cx+d}},\qquad a,b,c,d\in \mathbb {Z} _{>0}}$

と、対応する図に示されている3つの円について考える。 a/c < b/d と仮定する。

• 円（黄色）

${\displaystyle \left|x-{\tfrac {1}{2}}\left({\tfrac {a}{c}}+{\tfrac {b}{d}}\right)\right|={\tfrac {1}{2}}\left({\tfrac {b}{d}}-{\tfrac {a}{c}}\right)}$

は、直径が実軸上にあり、端点が a/c と b/d である。逆メビウス変換

${\displaystyle M^{-1}(x)={\frac {dx-b}{-cx+a}}}$

によって虚軸に写像される。例えば、点

${\displaystyle {\tfrac {1}{2}}\left({\tfrac {a}{c}}+{\tfrac {b}{d}}\right)+{\tfrac {i}{2}}\left({\tfrac {b}{d}}-{\tfrac {a}{c}}\right)}$

は、点 −i d/c に写像される。外点は Re(x) < 0 を持つ半平面に写像される。

• 2つの円（青い三日月形のみが見えている）

は、中心が

${\displaystyle {\tfrac {1}{2}}\left({\tfrac {a}{c}}+{\tfrac {b}{d}}\right)\pm {\tfrac {i}{2{\sqrt {3}}}}\left({\tfrac {b}{d}}-{\tfrac {a}{c}}\right)}$

半径が

${\displaystyle {\tfrac {1}{\sqrt {3}}}\left({\tfrac {b}{d}}-{\tfrac {a}{c}}\right)}$

である。逆メビウス変換

${\displaystyle M^{-1}(x)={\frac {dx-b}{-cx+a}}}$

によって直線 Im(x) = ±√3 Re(x) に写像される。例えば、点

${\displaystyle {\tfrac {1}{2}}\left({\tfrac {a}{c}}+{\tfrac {b}{d}}\right)-{\tfrac {3i}{2{\sqrt {3}}}}\left({\tfrac {b}{d}}-{\tfrac {a}{c}}\right)}$

は、点

${\displaystyle {\tfrac {-d}{2c}}\left(1-i{\sqrt {3}}\right)}$

に写像される。外側の点（8の字型の外側にある点）は ${\displaystyle S_{\sqrt {3}}}$ セクターに写像される。

上記から、多項式が8の字型の図形の内側に正根を1つ持ち、他のすべての根がその外側にある場合、その係数の列に1つの符号変化が生じることが明らかである。これにより、処理の終了も保証される。

歴史的背景

ヴァンサンの定理の初期の応用

ヴァンサンは基礎論文^[1][2][3]の中で、連分数を含む多項式の実根を分離するために彼の定理をどのように用いるかを正確に示す例を示した。しかし、この手法の計算時間は指数関数的であった。これは当時の数学者たちが認識していたに違いなく、1世紀後のUspensky（英語版）もこの事実に気づいた。^[8] p. 136

ヴァンサンによる根の探索（ブダンの定理を適用）

ヴァンサンのアルゴリズムが指数関数的な性質を持つのは、部分商「a_i」（ヴァンサンの定理において）を計算する方式による。つまり、各部分商 a_i を計算する（根が x 軸上のどこに位置するかを特定する）ために、ヴァンサンはブダンの定理を「無根検定」として用いる。言い換えれば、根の整数部を求めるために、ヴァンサンは x ← x+1 という形式の逐次置換を実行し、多項式 p(x) と p(x+1) の係数列における符号変化の数が変化する（つまり、p(x+1) の符号変化の数が減少する）場合にのみ停止する。

対応する図では、根が区間 (5, 6) に位置する。根が原点から遠く離れている場合、この方式では整数部を求めるのに非常に時間がかかることが容易に推測できる。これが、ヴァンサンの方式が指数関数的な性質を持つ理由である。以下で、この欠点がどのように克服されるかを説明する。

ヴァンサンの定理の消滅

ヴァンサンは、19世紀において多項式の実根の分離に自身の定理を用いた最後の著者であった。

その理由は、1827年にスツルムの定理が登場したことである。この定理は、多項式が実開区間 (a, b) において持つ実根の正確な個数を定義することで、実根の分離問題を多項式時間で解決した。この定理によって得られた多項式の実根を計算する（Sturmの）方式は、それ以来広く知られ、使用された唯一の方式であったが、1980年頃までに（ほぼすべてのコンピュータ代数システムにおいて）ヴァンサンの定理から導かれた方式に置き換えられた。その中で最も高速な方式は、Vincent–Akritas–Strzeboński法（VAS）であった^[9]。

Serretは代数学の著書^[10] の363～368ページに、ヴァンサンの定理とその証明を掲載し、興味のある読者には、定理の用例についてはヴァンサンの論文を参照するよう指示した。Serretは19世紀にヴァンサンの定理に言及した最後の著者であった。

ヴァンサンの定理の復活

20世紀において、ヴァンサンの定理は方程式論のどの書籍にも見当たらない。唯一の例外はUspensky（英語版）の著書^[8]とObreschkoff（英語版）の著書^[7]で、後者には定理の記述のみが記されている。

AkritasはUspensky（英語版）の著書^[8]でヴァンサンの定理を発見し、1978年に米国ノースカロライナ州立大学で博士論文「代数的操作におけるヴァンサンの定理」のテーマとした。当時の大きな成果は、ヴァンサンの1836年の原論文を入手したことだったが、Uspensky（英語版）はそれを理解できず、大きな誤解を招いた。ヴァンサンによる1836年の原論文は、米国ウィスコンシン大学マディソン校図書館の司書の素晴らしい努力（図書館間貸借）により、Akritasに提供された。

ヴァンサンの定理から導かれる実根分離法

多項式の実根分離とは、各区間にちょうど1つの実根が含まれ、かつすべての実根が何らかの区間に含まれるような、互いに素な開区間を求める処理である。19世紀のフランス数学派によれば、これは実根を計算する最初のステップであり、次に任意の精度で実根を近似することとなる。さらに、多項式 p(x) の負根を分離するには、x を −x (x ← −x) に置き換え、この処理を繰り返す必要があるため、正根に焦点が当てられる。

ヴァンサンの定理の連分数版は、次数 deg(p) の与えられた多項式 p(x) の正根を分離するために使用できる。これを理解するには、メビウス変換

${\displaystyle M(x)={\frac {ax+b}{cx+d}},\qquad a,b,c,d\in \mathbb {N} }$

を用いて、係数列に1つの符号変化を持つ変換多項式

${\displaystyle f(x)=(cx+d)^{\deg(p)}p\left({\frac {ax+b}{cx+d}}\right)}$

(2)

に至る連分数を表す。すると、f(x) の唯一の正根（区間 (0, ∞) 内）は、端点 ${\displaystyle {\frac {b}{d}}}$ と ${\displaystyle {\frac {a}{c}}}$ を持つ開区間にある p(x) の『その』正根に対応する。これらの端点は順序付けされておらず、それぞれ M(0) と M(∞) に対応する。

したがって、多項式の正根を分離するために必要なことは、各根に対して、係数の列に1つの符号変化を持つ方程式 (2) のような、変換された多項式に対応する メビウス変換

${\displaystyle M(x)={\frac {ax+b}{cx+d}}}$

の変数 a、b、c、d を計算することだけである。

重要な考察： 係数の列に1つの符号変化を持つ、方程式 (2) のような変換された多項式を導く（ヴァンサンの定理における）メビウス変換

${\displaystyle M(x)={\frac {ax+b}{cx+d}}}$

の変数 a, b, c, d は、次のいずれかにより計算できる：

• 連分数法：Vincent–Akritas–Strzebonski (VAS)の連分数法^[9]
• 二分法：Vincent–Collins–Akritas (VCA)の二分法^[11]など

この極めて重要な考察の「二分法部分」は、Alesina と Galuzzi の論文^[4][5]において特別な定理として登場した。

以下に述べるすべての手法（歴史的背景についてはブダンの定理の記事を参照）は、対象とする多項式の正根の値の上限値 ub を（いちど）計算する必要がある。例外はVAS法で、この方式ではメインループのほぼすべてのサイクルで下限値 lb を追加計算する必要がある。多項式 p(x) の下限値 lb を計算するには、多項式 ${\displaystyle x^{\deg(p)}p\left({\frac {1}{x}}\right)}$ の上限値 ub を計算し、${\displaystyle lb={\frac {1}{ub}}}$ と設定する。

多項式の正根の値に対する優れた（上限および下限）境界は、Doru Stefanescu の先行研究に基づき Akritas、Strzeboński および Vigklas によって開発された。これらは P. S. Vigklas の博士論文^[12]およびその他の文献^[13] に記載されている。これらの境界は既にコンピュータ代数システムのMathematica、SageMath、SymPy、Xcas（英語版）などに実装されている。

以下に説明する3つの手法はすべて、François Boulier の優れた発表^[14](p. 24) に従っている。

連分数法

ヴァンサンの定理から派生した連分数法は1つだけである。上記で述べたように、この方式は1830年代にヴァンサンが論文^[1][2][3]の中で、彼の定理を用いて連分数を含む多項式の実根分離法を示すいくつかの例を示したことに始まる。しかし、結果として得られた方式は指数関数的な計算時間を要した。以下では、この方式がどのように発展してきたかを説明する。

Vincent–Akritas–Strzeboński（VAS、2005年）

これは、ヴァンサン法の指数関数的な挙動に対処するために開発された2番目の方式（VCAに次ぐ）である。

VAS連分数法は、ヴァンサンの定理を「直接的に」実装したものである。この定理は、1834年から1838年にかけて^{[訳注 2]}ヴァンサンによって論文^[1][2][3]の中で指数形式で初めて提示された。つまり、ヴァンサンは各部分商 a_i を、一連の「単位」増分 a_i ← a_i + 1 によって計算した。これは、形式 x ← x + 1 の置換と同等である。

ヴァンサンの方式は、Akritas によって多項式複雑度の形式に変換された。Akritas は1978年の博士論文（Vincent's theorem in algebraic manipulation, North Carolina State University, USA）において、各部分商 a_i を多項式の正根の値の下限値 lb として計算した。これは「理想的な」正根の下限と呼ばれ、最小の正根の整数部を計算する（対応する図を参照）。つまり、a_i ← lb と設定するか、あるいは等価的に、置換 x ← x + lb を実行する。これは、置換 x ← x + 1 とほぼ同じ時間がかかる。

VAS による根の探索：理想的な下限は5なので、x ← x + 5 である。

最後に、理想的な正根の下限は存在しないため、Strzeboński は 2005 年に、${\displaystyle lb_{computed}>16}$ のときは常に、置換 ${\displaystyle x\leftarrow lb_{computed}*x}$ を導入した^[15]。一般に ${\displaystyle lb>lb_{computed}}$ であり、値16は実験的に決定された。さらに、VAS法（連分数法）はVCA法（二分法）の最速実装よりも高速であることが示されており^[16]、この事実は独立して確認されている^[17]。より正確には、高次Mignotte多項式の場合、VASはVCAの最速実装よりも約50,000倍高速である。

2007年、Sharmaは理想的な正の下限値の仮説を覆し、VASが依然として時間に関して多項式的であることを証明した^[18]。

VASは、Mathematica、SageMath、SymPy、Xcas（英語版）における根分離のデフォルトアルゴリズムである。

スツルム法とVASの比較には、Xcas（英語版）の関数 realroot(poly) と time(realroot(poly)) を使用する。realroot(poly) の実根分離では、デフォルトでVAS法を使用し、スツルム法を使用する場合は realroot(sturm, poly) と記述する。A. Berkakisによる同じ機能を持つAndroidデバイス用アプリケーションについては、外部リンクを参照のこと。

VAS(p, M) の動作を以下に示す。ここでは、簡潔にするために Strzeboński の寄与は考慮していない。

• p(x) を、p(0) ≠ 0 となる次数 deg(p) の多項式とする。その正根を分離するには、p(x) にメビウス変換 M(x) = x を関連付け、処理対象のペア {p(x), M(x)} がある間、以下の手順を繰り返す。
• p(x) に デカルトの符号法則 を適用し、可能であれば（係数の数列の符号変化の数 var を使用して）、区間 (0, ∞) 内の根の数を計算する。根が存在しない場合は空集合 ∅ を返す。一方、根が1つ存在する場合は区間 (a, b) を返す。ここで、a = min(M(0), M(∞))、かつ b = max(M(0), M(∞)) です。b = ∞ の場合は、b = ub と設定する。ここで、ub は p(x) の正の根の値の上限である^[12][13]。
• 2 つ以上の符号変化がある場合、デカルトの符号法則 によれば、区間 (0, ∞) 内には0個、1個、または複数の実根が存在する可能性がある。この場合、区間 (0, 1) 内にある p(x) の根と、区間 (1, ∞) 内にある根を別々に考慮する。1については特別な検定を行う必要がある。
  • 区間 (0, 1) 内に根が存在することを保証するために、理想的な下限値 lb が使用される。つまり、最小の正根の整数部は、p(x) の正根の値に対する下限値 ${\displaystyle lb_{computed}}$ を用いて計算される^[12][13]。${\displaystyle lb_{computed}>1}$ の場合、p(x) と M(x) に対して置換 ${\displaystyle x\leftarrow x+lb_{computed}}$ が実行される。一方、${\displaystyle lb_{computed}\leq 1}$ の場合、置換 x ← x+1 を使用して根の整数部を求める。
  • 区間 (0, 1) 内の根を計算するには、${\displaystyle x\leftarrow {\frac {1}{1+x}}}$ を p(x) と M(x) に代入し、ペア {p(1 + x)、M(1 + x)} を処理する。

${\displaystyle \left\{(1+x)^{\deg(p)}p\left({\tfrac {1}{1+x}}\right),M({\tfrac {1}{1+x}})\right\}}$

一方、区間 (1, ∞) 内の根を計算するには、p(x) と M(x) に x ← x + 1 を代入し、ペア {p(1 + x), M(1 + x)} を処理する。 1が p(x) の根となる可能性は十分にあり、その場合 M(1) は元の多項式の根となり、分離区間は点に縮約される。

以下は、VAS(p, M) の再帰的表現である。

VAS(p, M):

入力: 単変数、平方無縁で次数 deg(p) の多項式 ${\displaystyle p(x)\in \mathbb {Z} [x],p(0)\neq 0}$ と メビウス変換

${\displaystyle M(x)={\frac {ax+b}{cx+d}}=x,\qquad a,b,c,d\in \mathbb {N} .}$

出力: p(x) の正根の分離区間のリスト

1 var ← p(x) の符号変化の数 // デカルトの符号法則;
2 if var = 0 then RETURN ∅;
3 if var = 1 then RETURN {(a, b)} // a = min(M(0), M(∞)), b = max(M(0), M(∞)), but if b = ∞ set b = ub, ただし ub は p(x) の正根の値の上限;
4 lb ← the ideal lower bound on the positive roots of p(x);
5 if lb ≥ 1 then p ← p(x + lb), M ← M(x + lb);
6 p01 ← (x + 1)deg(p) p(1/x + 1), M01 ← M(1/x + 1) // Look for real roots in (0, 1);
7 m ← M(1) // Is 1 a root?
8 p1∞ ← p(x + 1), M1∞ ← M(x + 1) // Look for real roots in (1, ∞);
9 if p(1) ≠ 0  then
10 RETURN VAS(p01, M01) ∪ VAS(p1∞, M1∞)
11 else
12 RETURN VAS(p01, M01) ∪ {[m, m]} ∪ VAS(p1∞, M1∞)
13 end

注釈

• 簡潔にするため、Strzeboński の寄与は考慮されていない。
• 上記のアルゴリズムでは、各多項式に メビウス変換 M(x) が関連付けられている。
• 1行目でデカルトの符号法則が適用される。
• VAS(p, M) から4行目と5行目を削除すると、結果として得られるアルゴリズムはヴァンサンの指数アルゴリズムになる。
• 多項式 p(x) に対して実行されるすべての置換は、関連するメビウス変換 M(x) に対しても実行される（5行目、6行目、8行目）。
• 分離区間は、7行目（および12行目）で計算される整数根を除き、3行目のメビウス変換から計算される。

VAS(p, M) の例

VAS法を p(x) = x³ − 7x + 7 に適用する（注：M(x) = x）。

反復1

VAS(x3 − 7x + 7, x)
1 var ← 2 // p(x) = x3 − 7x + 7 の係数の数列の符号変化の数
4 lb ← 1 // the ideal lower bound—found using lbcomputed and substitution(s) x ← x + 1
5 p ← x3 + 3x2 − 4x + 1, M ← x + 1
6 p01 ← x3 − x2 − 2x + 1, M01 ← x + 2/x + 1
7 m ← 1
8 p1∞ ← x3 + 6x2 + 5x + 1, M1∞ ← x + 2
10          RETURN VAS(x3 − x2 − 2x + 1, x + 2/x + 1) ∪ VAS(x3 + 6x2 + 5x + 1, x + 2)

分離間隔のリスト：{ }

処理対象ペアのリスト {p, M} ：

${\displaystyle \left\{\left\{x^{3}-x^{2}-2x+1,{\tfrac {x+2}{x+1}}\right\},\{x^{3}+6x^{2}+5x+1,x+2\}\right\}.}$

リストの先頭の要素を取り出し、それに対して処理を行う。

反復2

VAS(x3 − x2 − 2x + 1, x + 2/x + 1)
1 var ← 2 // p(x) = x3 − x2 − 2x + 1 の係数の数列の符号変化の数
4 lb ← 0 // the ideal lower bound—found using lbcomputed and substitution(s) x ← x + 1
6 p01 ← x3 + x2 − 2x − 1, M01 ← 2x + 3/x + 1
7 m ← 3/2
8 p1∞ ← x3 + 2x2 − x − 1, M1∞ ← x + 3/x + 2
10          RETURN VAS(x3 + x2 − 2x − 1, 2x + 3/x + 2) ∪ VAS(x3 + 2x2 − x − 1, x + 3/x + 2)

分離間隔のリスト：{ }

処理対象ペアのリスト {p, M} ：

${\displaystyle \left\{\left\{x^{3}+x^{2}-2x-1,{\tfrac {2x+3}{x+2}}\right\},\left\{x^{3}+2x^{2}-x-1,{\tfrac {x+3}{x+2}}\right\},\{x^{3}+6x^{2}+5x+1,x+2\}\right\}.}$

リストの先頭の要素を取り出し、それに対して処理を行う。

反復3

VAS(x3 + x2 − 2x − 1, 2x + 3/x + 2)
1 var ← 1 // p(x) = x3 + x2 − 2x − 1 の係数の数列の符号変化の数
3          RETURN {(3/2, 2)}

分離間隔のリスト：{(3/2, 2)}

処理対象ペアのリスト {p, M} ：

${\displaystyle \left\{\left\{x^{3}+2x^{2}-x-1,{\tfrac {x+3}{x+2}}\right\},\{x^{3}+6x^{2}+5x+1,x+2\}\right\}.}$

リストの先頭の要素を取り出し、それに対して処理を行う。

反復4

VAS(x3 + 2x2 − x − 1, x + 3/x + 2)
1 var ← 1 // p(x) = x3 + 2x2 − x − 1 の係数の数列の符号変化の数
3          RETURN {(1, 3/2)}

分離間隔のリスト：{(1, 3/2), (3/2, 2)}

処理対象ペアのリスト {p, M} ：

${\displaystyle \left\{\left\{x^{3}+6x^{2}+5x+1,x+2\right\}\right\}.}$

リストの先頭の要素を取り出し、それに対して処理を行う。

反復5

VAS(x3 + 6x2 + 5x + 1, x + 2)
1 var ← 0 // p(x) = x3 + 6x2 + 5x + 1 の係数の数列の符号変化の数
2          RETURN ∅ の係数の数列の符号変化の数

分離間隔のリスト：{(1, 3/2), (3/2, 2)}

処理対象ペアのリスト {p, M} ：∅.

終了。

結論

したがって、多項式 p(x) = x³ − 7x + 7 の2つの正の根は、分離区間 (1, 3/2) と (3/2, 2) 内にある。それぞれの根は（例えば）端点の差が 10⁻⁶ より小さくなるまで、それが含まれる分離区間を二等分することで近似できる。この方式に従うと、根は ρ₁ = 1.3569 と ρ₂ = 1.69202 になる。

二分法

ヴァンサンの定理から派生した二分法には様々な方式があり、それらはすべて他の文献で紹介され比較されている^[19]。ここでは、その中で最も重要な2つの方式、すなわちVincent–Collins–Akritas（VCA）法とVincent–Alesina–Galuzzi（VAG）法について説明する。

Vincent–Alesina–Galuzzi（VAG）法は、ヴァンサンの定理から派生した方式の中で最も単純だが、多項式が対象区間に根を持つかどうかを判定するテスト（1行目）に最も時間がかかる。そのため、この記事で紹介する方式の中で最も低速である。

対照的に、Vincent–Collins–Akritas（VCA）法はVAG法よりも複雑だが、より単純なテスト（1行目）を使用する。これといくつかの改良^[16]により、VCAは最速の二分法となった。

Vincent–Collins–Akritas（VCA、1976年）

これは、Vincentの元のアプローチの指数関数的性質を克服するために開発された最初の手法であり、その名称に関しては非常に興味深い歴史がある。デカルトの符号法則とヴァンサンの定理を用いて実根を分離するこの手法は、当初、発明者のCollinsとAkritasによって「修正Uspenskyアルゴリズム」と呼ばれていた^[11]。「Collins–Akritas法」や「デカルト法」（フーリエの論文^[20]を考えると混乱を招く）といった名称を経て、最終的にLille大学の François Boulier が「Uspensky法」が存在しないこと^[21]と「デカルト法」が存在しない^[22]という事実に基づき、「Vincent–Collins–Akritas法」（VCA）と名付けた^[14](p.24)。この手法の最も優れた実装はRouillierとZimmermanによるもの^[16]で、現在までに最速の二分法である。最悪のケースではスツルムのアルゴリズムと同じ計算量であるが、ほとんどの場合、はるかに高速である。MapleのRootFindingパッケージに実装されている。

VCA(p, (a, b)) の動作は以下の通り。

• 次数 deg(p) の多項式 p_orig(x) が与えられ、その正根は孤立している必要があり、p_orig(0) ≠ 0 とする。まず、これらの正根の値の上限 ub を計算し^[12][13]、p(x) = p_orig(ub * x) かつ (a, b) = (0, ub) とする。 p(x) の正根はすべて区間 (0, 1) 内にあり、それらと p_orig(x) の根（すべて区間 (a, b) = (0, ub) 内に存在する）との間には全単射が存在する（対応する図を参照）。この全単射は α_{(a, b)} = a +α_{(0, 1)}(b − a) で表される。同様に、区間 (0, 1) と (0, ub) の間にも全単射が存在する。

p_orig(x) と p(x) の根の間の全単射。

• 処理対象ペアのリスト {p(x), (a, b)} がある間、以下の手順を繰り返す。
• ブダンの「0_1根検定」を p(x) に適用し、区間 (0, 1) 内に存在する根の数を計算する（係数列における符号変化の数 var を使用する）。根がない場合は空集合 ∅ を返し、根が1つある場合は区間 (a, b) を返す。
• 2つ以上の符号変化がある場合、ブダンの「0_1根検定」は、区間 (0, 1) 内に 0、1、2、またはそれ以上の実根が存在する可能性があることを意味する。この場合、区間を半分に分割し、区間 (0, 1/2) 内の p(x) の根（区間 (a, 1/2(a + b)）内の p_orig(x) の根に対応するものと、区間 (1/2, 1) 内にあり、区間 (1/2(a + b), b) 内の p_orig(x) の根に対応するものを別々に考える。つまり、それぞれ次のペアを処理する。

${\displaystyle \left\{2^{\deg(p)}p({\tfrac {x}{2}}),(a,{\tfrac {1}{2}}(a+b))\right\},\quad \left\{2^{\deg(p)}p({\tfrac {1}{2}}(x+1)),({\tfrac {1}{2}}(a+b),b)\right\}}$

(対応する図を参照)。1/2 が p(x) の根となる場合もあり、その場合、1/2(a + b) は p_orig(x) の根となり、分離区間は点に縮約される。

p(x) の根と、p(x/2) および p(x + 1/2) の根との間の全単射。

以下は、元のアルゴリズム VCA(p, (a, b)) の再帰的表現である。

VCA(p, (a, b))

入力：一変数、平方無縁で次数 deg(p) の多項式 p(ub * x) ∈ Z[x], p(0) ≠ 0、開区間 (a, b) = (0, ub)、ここで ub は p(x) の正根の値の上限である。（p(ub * x) の正根はすべて開区間 (0, 1) 内にある）
の係数の数列の符号変化の数 出力：p(x) の正根の分離区間のリスト

1 var ← (x + 1)deg(p)p(1/x + 1) の符号変化の数 // ブダンの「0_1根検定」;
2 if var = 0 then RETURN ∅;
3 if var = 1 then RETURN {(a, b)};
4 p01/2 ← 2deg(p)p(x/2) // Look for real roots in (0, 1/2);
5 m ← 1/2(a + b) // Is 1/2 a root?
6 p1/21 ← 2deg(p)p(x + 1/2) // Look for real roots in (1/2, 1);
7 if p(1/2) ≠ 0 then
8         RETURN VCA (p01/2, (a, m)) ∪ VCA (p1/21, (m, b))
9 else
10        RETURN VCA (p01/2, (a, m)) ∪ {[m, m]} ∪ VCA (p1/21, (m, b))
11 end

注釈

• 上記のアルゴリズムでは、各多項式に区間（a、b）が関連付けられている。^[22] p. 11で示されているように、各多項式にメビウス変換を関連付けることもできる。その場合、VCAはVASに似たものになる。
• 1行目では、ブダンの「0_1根検定」が適用される。

VCA（p, (a,b)）の例

多項式 p_orig(x) = x³ − 7x + 7 が与えられ、正根の値の上限 ^[12][13] として ub = 4 を考慮すると、VCA 法の引数は p(x) = 64x³ − 28x + 7 と (a, b) = (0, 4) である。

反復1

1 var ← 2 // (x + 1)3p(1/x + 1) = 7x3 − 7x2 − 35x + 43 の係数の数列の符号変化の数
4 p01/2 ← 64x3 − 112x + 56
5 m ← 2
6 p1/21 ← 64x3 + 192x2 + 80x + 8
7 p(1/2) = 1
8          RETURN VCA(64x3 − 112x + 56, (0, 2)) ∪ VCA(64x3 + 192x2 + 80x + 8, (2, 4))

分離間隔のリスト：{ }

処理対象ペアのリスト {p, I} ：

${\displaystyle \left\{\left\{64x^{3}-112x+56,(0,2)\right\},\left\{64x^{3}+192x^{2}+80x+8,(2,4)\right\}\right\}.}$

リストの先頭の要素を取り出し、それに対して処理を行う。

反復2

VCA(64x3 − 112x + 56, (0, 2))
1 var ← 2 // (x + 1)3p(1/x + 1) = 56x3 + 56x2 − 56x + 8 の係数の数列の符号変化の数
4 p01/2 ← 64x3 − 448x + 448
5 m ← 1
6 p1/21 ← 64x3 + 192x2 − 256x + 64
7 p(1/2) = 8
8          RETURN VCA(64x3 − 448x + 448, (0, 1)) ∪ VCA(64x3 + 192x2 − 256x + 64, (1, 2))

分離間隔のリスト：{ }

処理対象ペアのリスト {p, I} ：

${\displaystyle \left\{\left\{64x^{3}-448x+448,(0,1)\right\},\left\{64x^{3}+192x^{2}-256x+64,(1,2)\right\},\left\{64x^{3}+192x^{2}+80x+8,(2,4)\right\}\right\}.}$

リストの先頭の要素を取り出し、それに対して処理を行う。

反復3

VCA(64x3 − 448x + 448, (0, 1))
1 var ← 0 // (x + 1)3p(1/x + 1) = 448x3 + 896x2 + 448x + 64 の係数の数列の符号変化の数
2          RETURN ∅

分離間隔のリスト：{ }

処理対象ペアのリスト {p, I} ：

${\displaystyle \left\{\left\{64x^{3}+192x^{2}-256x+64,(1,2)\right\},\left\{64x^{3}+192x^{2}+80x+8,(2,4)\right\}\right\}.}$

リストの先頭の要素を取り出し、それに対して処理を行う。

反復4

VCA(64x3 + 192x2 − 256x + 64, (1, 2))
1 var ← 2 // (x + 1)3p(1/x + 1) = 64x3 − 64x2 − 128x + 64 の係数の数列の符号変化の数
4 p01/2 ← 64x3 + 384x2 − 1024x + 512
5 m ← 3/2
6 p1/21 ← 64x3 + 576x2 − 64x + 64
7 p(1/2) = −8
8 RETURN VCA(64x3 + 384x2 − 1024x + 512, (1, 3/2)) ∪ VCA(64x3 + 576x2 − 64x − 64, (3/2, 2))

分離間隔のリスト：{ }

処理対象ペアのリスト {p, I} ：

${\displaystyle \left\{\left\{64x^{3}+384x^{2}-1024x+512,\left(1,{\tfrac {3}{2}}\right)\right\},\left\{64x^{3}+576x^{2}-64x-64,\left({\tfrac {3}{2}},2\right)\right\},\left\{64x^{3}+192x^{2}+80x+8,(2,4)\right\}\right\}.}$

リストの先頭の要素を取り出し、それに対して処理を行う。

反復5

VCA(64x3 + 384x2 − 1024x + 512, (1, 3/2))
1 var ← 1 // (x + 1)3p(1/x + 1) = 512x3 + 512x2 − 128x − 64 の係数の数列の符号変化の数
3 RETURN {(1, 3/2)}

分離間隔のリスト：{(1, 3/2)}

処理対象ペアのリスト {p, I} ：

${\displaystyle \left\{\left\{64x^{3}+576x^{2}-64x-64,\left({\tfrac {3}{2}},2\right)\right\},\left\{64x^{3}+192x^{2}+80x+8,(2,4)\right\}\right\}.}$

リストの先頭の要素を取り出し、それに対して処理を行う。

反復6

VCA(64x³ + 576x² − 64x − 64, (3/2, 2))

1 var ← 1 // (x + 1)3p(1/x + 1) = −64x3 − 256x2 + 256x + 512 の係数の数列の符号変化の数
3 RETURN {(3/2, 2)}

分離間隔のリスト：{(1, 3/2), (3/2, 2)}

処理対象ペアのリスト {p, I} ：

${\displaystyle \left\{\left\{64x^{3}+192x^{2}+80x+8,(2,4)\right\}\right\}.}$

リストの先頭の要素を取り出し、それに対して処理を行う。

反復7

VCA(64x3 + 192x2 + 80x + 8, (2, 4))
1 var ← 0 // (x + 1)3p(1/x + 1) = 8x3 + 104x2 + 376x + 344 の係数の数列の符号変化の数
2 RETURN ∅

分離間隔のリスト：{(1, 3/2), (3/2, 2)}

処理対象ペアのリスト {p, I} ：∅.

終了。

結論

したがって、多項式 p(x) = x³ − 7x + 7 の2つの正根は、分離区間 (1, 3/2) と (3/2, 2) 内にある。それぞれの根は（例えば）端点の差が 10⁻⁶ より小さくなるまで、それが含まれる分離区間を二等分することで近似できる。この方式に従うと、根は ρ₁ = 1.3569 と ρ₂ = 1.69202 になる。

Vincent–Alesina–Galuzzi（VAG、2000年）

これは最後に開発されたもので、ヴァンサンの定理から導かれる最も単純な実根分離法である。

VAG(p, (a, b))の動作は以下の通り。

• 次数 deg(p) の多項式 p(x) が与えられ、その正根は分離されていなければならない。まず、これらの正根の値の上限 ub を計算し^[12][13]、(a, b) = (0, ub) とする。p(x) の正根は、すべて区間 (a, b) 内にある。
• 処理対象の区間 (a, b) がある限り、以下の手順を繰り返す。この場合、多項式 p(x) は変化しない。
• p(x) に対して Alesina–Galuzziの「a_b根検定」を用いて、区間 (a, b) 内の根の数を計算する（係数列における符号変化の数 var を使用）。根がない場合は空集合 ∅ を返し、根が1つある場合は区間 (a, b) を返す。
• 符号変化が2つ以上ある場合、Alesina–Galuzziの「a_b根検定」は、区間 (a, b) 内に 0、1、2、またはそれ以上の実根が存在する可能性があることを意味する。この場合、区間を半分に分割し、区間 (a, 1/2(a + b)) 内の p(x) の根と、区間 (1/2(a + b), b) 内の根を別々に考える。つまり、それぞれ区間 (a, 1/2(a + b)) と (1/2(a + b), b) を処理する。1/2(a + b) が p(x) の根であることが判明する可能性があり、その場合、分離区間は点に縮約される。

以下は、VAG(p, (a, b)) の再帰的表現である。

VAG(p, (a, b))
入力: 一変数、平方無縁で次数 deg(p) の多項式 p(x) ∈ Z[x], p(0) ≠ 0、開区間 (a, b) = (0, ub)、ここで、ub は p(x) の正根の値の上限。
出力: p(x) の正根の分離区間のリスト。

1 var ← (x + 1)deg(p) p(a + bx/1 + x) の符号変化の数 // Alesina–Galuzziの「a_b根検定」;
2 if var = 0 then RETURN ∅;
3 if var = 1 then RETURN {(a, b)};
4 m ← 1/2(a + b) // Subdivide the interval (a, b) in two equal parts;
5 if p(m) ≠ 0 then
6        RETURN VAG(p, (a, m)) ∪ VAG(p, (m, b))
7 else
8        RETURN VAG(p, (a, m)) ∪  {[m, m]} ∪ VAG(p, (m, b))
9 end

備考

• VCAと比較すると、上記のアルゴリズムは非常に単純である。一方、VAG は時間のかかる「a_b根検定」を使用するため、VCAよりもはるかに遅くなる^[19]。
• AlesinaとGaluzziが指摘しているように、このアルゴリズムの Donato Saeli による変種がある^[5] p. 189。Saeliは、端点の中点 1/2(a + b) の代わりに、端点のmediant（英語版）を使用することを提案した。しかし、端点のmediant（英語版）を使用すると、一般的に「中点」バージョンよりもはるかに遅くなることが示されている^[19]。

VAG（p, (a,b)）の例

多項式 p(x) = x³ − 7x + 7 が与えられ、正根の値の上限^[12][13]として ub = 4 を考慮すると、VAGの引数は p(x) = x³ − 7x + 7 と (a, b) = (0, 4) である。

反復1

1 var ← 2 // (x + 1)3p(4x/x + 1) = 43x3 − 35x2 − 7x + 7 の係数の数列の符号変化の数
4 m ← 1/2(0 + 4) = 2
5 p(m) = 1
8          RETURN VAG(x3 − 7x + 7, (0, 2)) ∪ VAG(x3 − 7x + 7, (2, 4)

分離間隔のリスト：{}

処理対象の間隔のリスト：{(0, 2), (2, 4)}

リストの先頭の要素を取り出し、それに対して処理を行う。

反復2

VAG(x3 − 7x + 7, (0, 2))
1 var ← 2 // (x + 1)3p(2x/x + 1) = x3 − 7x2 + 7x + 7 の係数の数列の符号変化の数
4 m ← 1/2(0 + 2) = 1
5 p(m) = 1
8          RETURN VAG(x3 − 7x + 7, (0, 1)) ∪ VAG(x3 − 7x + 7, (1, 2)

分離間隔のリスト：{}

処理対象の間隔のリスト：{(0, 1), (1, 2), (2, 4)}

リストの先頭の要素を取り出し、それに対して処理を行う。

反復3

VAG(x3 − 7x + 7, (0, 1))
1 var ← 0 // (x + 1)3p(x/x + 1) = x3 + 7x2 + 14x + 7 の係数の数列の符号変化の数
2          RETURN ∅

分離間隔のリスト：{}

処理対象の間隔のリスト：{(1, 2), (2, 4)}

リストの先頭の要素を取り出し、それに対して処理を行う。

反復4

VAG(x3 − 7x + 7, (1, 2))
1 var ← 2 // (x + 1)3p(2x + 1/x + 1) = x3 − 2x2 − x + 1 の係数の数列の符号変化の数
4 m ← 1/2(1 + 2) = 3/2
5 p(m) = −1/8
8          RETURN VAG(x3 − 7x + 7, (1, 3/2)) ∪ VAG(x3 − 7x + 7, (3/2, 2))

分離間隔のリスト：{}

処理対象の間隔のリスト：{(1, 3/2), (3/2, 2), (2, 4)}

リストの先頭の要素を取り出し、それに対して処理を行う。

反復5

VAG(x3 − 7x + 7, (1, 3/2))
1 var ← 1 // 23(x + 1)3p(3/2x + 1/x + 1) = x3 + 2x2 − 8x − 8 の係数の数列の符号変化の数
3          RETURN (1, 3/2)

分離間隔のリスト：{(1, 3/2)}

処理対象の間隔のリスト：{(3/2, 2), (2, 4)}

リストの先頭の要素を取り出し、それに対して処理を行う。

反復6

VAG(x3 − 7x + 7, (3/2, 2))
1 var ← 1 // 23(x + 1)3p(2x + 3/2/x + 1) = 8x3 + 4x2 − 4x − 1 の係数の数列の符号変化の数
3          RETURN (3/2, 2)

分離間隔のリスト：{(1, 3/2), (3/2, 2)}

処理対象の間隔のリスト：{(2, 4)}

リストの先頭の要素を取り出し、それに対して処理を行う。

反復7

VAG(x3 − 7x + 7, (2, 4))
1 var ← 0 // (x + 1)3p(4x + 2/x + 1) = 344x3 + 376x2 + 104x + 8 の係数の数列の符号変化の数
2          RETURN ∅

分離間隔のリスト：{(1, 3/2), (3/2, 2)}

処理対象の間隔のリスト：∅

終了。

結論

したがって、多項式 p(x) = x³ − 7x + 7 の2つの正根は、分離区間 (1, 3/2) と (3/2, 2) 内にある。それぞれの根は（例えば）端点の差が 10⁻⁶ より小さくなるまで、それが含まれる分離区間を二等分することで近似できる。この方式に従うと、根は ρ₁ = 1.3569 と ρ₂ = 1.69202 になる。

関連項目

• 多項式の根
• 求根アルゴリズム
• 根と係数の関係（ビエタの公式）
• ニュートン法
• スツルムの定理
• ブダンの定理
• 実根分離