ヴィンセント定理

数学において、アレクサンドル・ジョゼフ・イドゥルフ・ヴィンセントにちなんで名付けられたヴィンセント定理は、有理係数を持つ多項式の実根を分離する定理です。

ヴィンセント定理は多項式の実根を分離する最速の方法の基礎であるにもかかわらず、シュトゥルムの定理に隠れてほとんど忘れ去られていました。その結果、ウスペンスキーの本を除いて、方程式の理論に関する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間の符号変化または符号変更と呼ばれます。

1変数の多項式p ( x )を扱う場合、 p ( x )の符号変化の数をその係数のシーケンス内の符号変化の数として定義します。

この定理には2つのバージョンが提示されている。ヴィンセントによる連分数^{バージョン[1] [2] [3]} とアレシナとガルッツィによる二分^{バージョン[4] [5] である。}

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

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

ここで は1 以上の任意の正数であり、このような変換を何回か行った後、結果として得られる変換された方程式は符号変化がゼロか、または 1 つの符号変化を持つ。最初のケースでは根はないが、2 番目のケースでは 1 つの正の実根がある。さらに、提案された方程式の対応する根は有限連分数で近似される: ^{[1] [2] [3]}${\displaystyle a_{1},a_{2},a_{3},\ldots }$

${\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]}に記載されている定理の正確な翻訳である。しかし、より明確な理解のためには、以下の注釈が必要である。

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

p ( x ) を、単純な根のみを持つ次数 deg( p ) の実多項式とします。 となる正の実数a、b の任意のペアに対して、次の形式の変換された多項式が 成り立つように、正の量 δ を決定することが可能です。${\displaystyle |b-a|<\delta }$

符号の変化は0または1つだけあります。2番目のケースは、 p ( x )が( 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 根検定」の特殊なケースは、Budan の「0_1 根検定」です。

ヴィンセント定理、その拡張、関連する変換の幾何学的解釈、および3つの異なる証明についての詳細な議論は、アレシナとガルッツィの著作で見ることができる。^{[4] [5]} 4番目の証明は、1920年から1923年にかけてオブレシュコフ^[7]の81ページ で述べられた定理の特殊なケースを再発見したオストロフスキー^{[6]によるものである。}

ヴィンセント定理（両方のバージョン）を証明するために、アレシナとガルッツィは、定理で述べられている一連の変換の後、1 つの正の根を持つ多項式は最終的に 1 つの符号変化を持つことを示しています。これを示すために、彼らは前述の 1920 年から 1923 年のオブレシュコフの定理の次の系を使用します。つまり、次の系は、1 つの正の根を持つ多項式がその係数のシーケンスで正確に 1 つの符号変化を持つために必要な条件を与えます。対応する図も参照してください。

系（オブレシュコフの円錐または扇形定理、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 つの符号変化があります。

メビウス変換を考えてみましょう

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

対応する図に示されている3つの円について、次のように仮定する。 1つの/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)}$

その直径は実軸上にあり、端点は⁠1つの/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世紀後に ウスペンスキー^[8] p. 136によって認識された。

ヴィンセントのアルゴリズムの指数関数的な性質は、部分商 a _i (ヴィンセントの定理) の計算方法によるものです。つまり、各部分商 a _{i を}計算するために(つまり、根がx軸上のどこにあるかを見つけるために)、ヴィンセントはブダンの定理を「根なしテスト」として使用します。言い換えると、根の整数部分を見つけるために、ヴィンセントはx ← x +1 の形式の連続的な置換を実行し、多項式p ( x ) とp ( x +1) の係数のシーケンスの符号の変化の数が異なる場合 (つまり、 p ( x +1)の符号の変化の数が減少した場合) のみ停止します。

対応する図を見てください。この図では、根は区間 (5, 6) にあります。根が原点から遠く離れている場合、この方法では整数部分を見つけるのに多くの時間がかかることが容易に推測できます。これが、 Vincent 法の指数関数的な性質です。以下では、この欠点を克服する方法について説明します。

ヴィンセントは、多項式の実根の分離に彼の定理を使用した 19 世紀最後の著者でした。

その理由は、 1827年にシュトゥルムの定理が登場したためである。この定理は、実開区間 ( a、b ) における多項式の実根の正確な個数を定義することで、実根孤立問題を多項式時間で解決した。多項式の実根を計算する結果として得られた (シュトゥルムの) 方法は、それ以来広く知られ、使用されている唯一の方法であったが、1980年頃に (ほぼすべてのコンピュータ代数システムで) ヴィンセントの定理から派生した方法に置き換えられた。最も高速な方法は、ヴィンセント・アクリタス・ストレボニスキ (VAS) 法であった。^[9]

セレットは、その著書『代数学』^[10] 363-368ページにヴィンセント定理とその証明を掲載し、興味のある読者に、定理の使用例についてはヴィンセントの論文を参照するよう勧めた。セレットは19世紀にヴィンセント定理について言及した最後の著者であった。

20世紀には、ヴィンセント定理は方程式理論のどの本にも見当たりません。唯一の例外はウスペンスキー^[8]とオブレシュコフ^[7]の本で、後者には定理の記述だけがあります。

アクリタスはウスペンスキーの本^[8]でヴィンセントの定理を発見し、それを博士論文「代数操作におけるヴィンセントの定理」（米国ノースカロライナ州立大学、 1978年）のテーマとした。当時の大きな成果は、ウスペンスキーが入手できなかったヴィンセントの1836年の原論文を入手したことであり、その結果大きな誤解を招いた。ヴィンセントの1836年の原論文は、米国ウィスコンシン大学マディソン校図書館の司書の称賛に値する努力（図書館間貸借）によりアクリタスが入手できた。

多項式の実根の分離とは、それぞれが正確に 1 つの実根を含み、すべての実根が何らかの区間に含まれるような、互いに素な開区間を見つけるプロセスです。19 世紀のフランスの数学学派によれば、これが実根を計算する最初のステップであり、2 番目のステップは実根を任意の精度で近似することです。さらに、多項式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つの符号の変化があります。すると、f ( x ) の単一の正の根 (区間 (0,∞) 内) は、端点がおよびである開区間にある p (x) の正の根に対応します。これらの端点は順序付けられておらず、それぞれM (0) とM (∞)に対応します。 ${\displaystyle {\frac {b}{d}}}$${\displaystyle {\frac {a}{c}}}$

したがって、多項式の正の根を分離するには、各根について、対応するメビウス変換の変数a、b、c、dを計算するだけでよい。

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

これは式( 2 )のように係数の順序に1つの符号変化を持つ 変換された多項式につながる。

重要な観察:メビウス変換の変数a、b、c、d

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

（ヴィンセント定理において）係数の順序に1つの符号変化を持つ変換多項式（式（2））を導く計算は次の通りである。

• 連分数法では、ヴィンセント・アクリタス・ストレボンスキー（VAS）連分数法が用いられる。 ^[9]
• あるいは二分法によって、（他の方法の中でも）ヴィンセント・コリンズ・アクリタス（VCA）二分法につながる。^[11]

この非常に重要な観察の「二分部分」は、アレシナとガルッツィの論文の中で特別な定理として登場しました。^{[4] [5]}

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

多項式の正の根の値に対する優れた（上限と下限の）境界は、Doru Stefanescu の以前の研究に基づいて、Akritas、Strzeboński、および Vigklas によって開発されました。これらは、PS Vigklas の博士論文^[12]やその他の文献で説明されています。^{[13]これらの境界は、} Mathematica、SageMath、SymPy、Xcasなどの コンピュータ代数システム にすでに実装されています。

^{以下に説明する3つの方法はすべて、フランソワ・ブーリエ[14]}の24ページ の優れた説明に従っています。

ヴィンセントの定理から派生した連分数法は1 つだけです。前述のように、この方法は 1830 年代にヴィンセントが論文^{[1] [2] [3]で、}連分数を含む多項式の実根を分離するために定理を使用する方法を示すいくつかの例を示したときに始まりました。ただし、結果として得られた方法の計算時間は指数関数的でした。以下では、この方法がどのように進化したかを説明します。

これは、Vincent 法の 指数関数的動作を処理するために開発された 2 番目の方法 (VCA に続く) です。

VAS連分数法は、ヴィンセント定理を直接実装したものです。この定理は、もともと1834年から1938年にかけてヴィンセントが論文^{[1] [2] [3]}で指数形式で発表しました。つまり、ヴィンセントは、各部分商 a _{i を、}一連の単位増分a i ← a i + 1で計算しまし_た。これ_は、 x ← x + 1の形式の置換と同等です。

ヴィンセントの方法は、1978 年の博士論文 (ヴィンセントの代数的操作における定理、ノースカロライナ州立大学、米国 ) で、各部分商a _{i を}多項式の正の根の値の下限lbとして計算した Akritas によって多項式の複雑性形式に変換されました。これは、最小の正の根の整数部分を計算する理想的な正の根の下限と呼ばれます(対応する図を参照)。つまり、ここでa _i ← lbに設定するか、または同等に、置換x ← x + lbを実行します。これには、置換x ← x + 1 とほぼ同じ時間がかかります。

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

2007年にシャルマ^[18]は理想的な正の下限の仮説を取り除き、VASが依然として時間に関して多項式であることを証明した。

VAS は、 Mathematica、SageMath、SymPy、Xcasにおけるルート分離のデフォルト アルゴリズムです。

Sturm 法と VAS を比較するには、 Xcasの関数 realroot(poly) と time(realroot(poly)) を使用します。デフォルトでは、poly の実根を分離するために realroot は VAS 法を使用します。Sturm 法を使用するには、realroot(sturm, poly) と記述します。同じことを実行する Android デバイス用の A. Berkakis によるアプリケーションについては、外部リンクも参照してください。

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 )の正の根の値に対する下限^{[12] [13]} の助けを借りて計算されます。 の場合、 p ( x ) とM ( x ) に置換が行われますが、 の場合は、根の整数部を見つけるために置換x ← x +1を使用します。${\displaystyle lb_{computed}}$${\displaystyle lb_{computed}>1}$${\displaystyle x\leftarrow x+lb_{computed}}$${\displaystyle lb_{computed}\leq 1}$
  • 区間(0, 1)内の根を計算するには、 p ( x )とM ( x )に代入し、次のペアを処理する。${\displaystyle x\leftarrow {\frac {1}{1+x}}}$

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

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

以下はVAS( p , M )の再帰的な表現です。

VAS（p、M）：

入力:次数deg( p )の1変数の平方自由多項式とメビウス変換${\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 var = 0の場合は RETURN ∅;
3 var = 1 の場合、  RETURN {( a , b )} // a = min( M (0), M (∞)), b = max( M (0), M (∞)), ただし、 b = ∞の場合は、b = ubに設定します。ここで、ubはp ( x )の正の根の値の上限です。
4 lb ← p ( x )の正の根の理想的な下限値。
5 lb ≥ 1の場合 、p ← p ( x + lb )、M ← M ( x + lb )。 
6 p 01 ← ( x + 1)度( p )  p ( ⁠1/x + 1⁠ ), M 01 ← M ( ⁠1/x + 1⁠ ) // (0, 1) 内の実根を探します。
7 m ← M (1) // 1はルートですか？
8 p 1∞ ← p ( x + 1), M 1∞ ← M ( x + 1) // (1, ∞) 内の実根を探す。
9 p (1) ≠ 0  ならば10  
VAS ( p 01 , M 01 ) ∪ VAS( p 1∞ , M 1∞ )を返す
11そうでない場合12 
VAS ( p 01 , M 01 ) ∪ {[ m , m ]} ∪ VAS( p 1∞ , M 1∞ )を返す
13終わり

備考

• 簡潔にするために、Strzeboński の貢献は含まれていません。
• 上記のアルゴリズムでは、各多項式にメビウス変換 M ( x )が関連付けられています。
• 1行目にはデカルトの記号規則が適用されます。
• VAS( p , M )から4行目と5行目を削除すると、結果として得られるアルゴリズムはVincentの指数アルゴリズムになります。
• 多項式p ( x )に対して実行される置換は、関連するメビウス変換 M ( x )に対しても実行されます(5行目、6行目、8行目)。
• 分離区間は、 7 行目 (12 行目も) で計算される整数根を除き、3 行目のメビウス変換から計算されます。

VAS法を^p(x)=x3−7x + 7に適用する（M(x ) = xであることに注意）。

VAS( x 3 − 7 x + 7, x )
1 var ← 2 // p ( x ) = x 3 − 7 x + 7の係数列における符号変化の数
4 lb ← 1 // 理想的な下限値 - lb を計算して代入するとx ← x + 1になる
5 p ← x 3 + 3 x 2 − 4 x + 1, M ← x + 1
6 p 01 ← x 3 − x 2 − 2 x + 1, M 01 ← ⁠バツ+ 2/x + 1⁠ 
7 m ← 1
8 p 1∞ ← x 3 + 6 x 2 + 5 x + 1、M 1∞ ← x + 2
10          戻り値 VAS( x 3 − x 2 − 2 x + 1, ⁠バツ+ 2/x + 1⁠ ) ∪ VAS( x 3 + 6 x 2 + 5 x + 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\}.}$

最初に削除して処理します。

VAS( x 3 − x 2 − 2 x + 1, ⁠バツ+ 2/x + 1⁠ )
1 var ← 2 // p ( x ) = x 3 − x 2 − 2 x + 1の係数列における符号変化の数
4 lb ← 0 // 理想的な下限値（lbを計算して代入することで得られる）x ← x + 1
6 p 01 ← x 3 + x 2 − 2 x − 1, M 01 ← ⁠2 × +3/x + 1⁠ 
7 m ← ⁠3/2⁠ 
8 p 1∞ ← x 3 + 2 x 2 − x − 1, M 1∞ ← ⁠バツ+ 3/バツ+ 2⁠ 
10          戻り値VAS( x 3 + x 2 − 2 x − 1, ⁠2 × +3/バツ+ 2⁠ ) ∪ VAS( x 3 + 2 x 2 − x − 1, ⁠バツ+ 3/バツ+ 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\}.}$

最初に削除して処理します。

VAS( x 3 + x 2 − 2 x − 1, ⁠2 × +3/バツ+ 2⁠ )
1 var ← 1 // p ( x ) = x 3 + x 2 − 2 x − 1の係数列における符号変化の数
3          戻り値{( ⁠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\}.}$

最初に削除して処理します。

VAS( x 3 + 2 x 2 − x − 1, ⁠バツ+ 3/バツ+ 2⁠ )
1 var ← 1 // p ( x ) = x 3 + 2 x 2 − x − 1の係数列における符号変化の数
3          戻り値{(1, ⁠3/2⁠ )}

隔離間隔のリスト: {(1, ⁠3/2⁠）、（⁠3/2⁠、2)}。

処理する ペア{ p , M }のリスト:

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

最初に削除して処理します。

VAS( × 3 +6 × 2 +5 × +1、x +2)
1 var ← 0 // p ( x ) = x 3 + 6 x 2 + 5 x + 1の係数列における符号変化の数
2          戻る∅

隔離間隔のリスト: {(1, ⁠3/2⁠）、（⁠3/2⁠、2)}。

処理対象となるペア{ p , M }のリスト: ∅。

終了した。

したがって、多項式p ( x ) = x ³ − 7 x + 7の2つの正の根は、孤立区間（1、⁠3/2⁠ )と( ⁠3/2⁠ , 2) }。各根は、（例えば）その根が含まれる孤立区間を、端点の差が10 ^{−6未満になるまで二等分することによって近似することができます。この方法に従うと、根は}ρ ₁ = 1.3569およびρ ₂ = 1.69202になります。

ヴィンセント定理から派生した様々な二分法があり、それらはすべて他の場所で紹介され比較されています。^[19]ここでは、その中で最も重要な2つの方法、すなわち、ヴィンセント–コリンズ–アクリタス（VCA）法とヴィンセント–アレシナ–ガルッツィ（VAG）法について説明します。

Vincent–Alesina–Galuzzi (VAG) 法は、Vincent の定理から派生したすべての方法の中で最も単純ですが、多項式が対象区間内に根を持つかどうかを判断するためのテスト (1 行目) に最も時間がかかります。そのため、この記事で紹介する方法の中で最も低速です。

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

これは、ヴィンセントの元のアプローチの指数的性質を克服するために開発された最初の方法であり、その名前に関する限り、非常に興味深い歴史を持っています。デカルトの符号規則とヴィンセントの定理を使用して実根を分離するこの方法は、発明者のコリンズとアクリタスによって、当初は修正ウスペンスキーのアルゴリズムと呼ばれていました。 ^{[11] 「コリンズ-アクリタス法」や「デカルト法」（フーリエの論文[20]}を考慮すると混乱しすぎる）などの名前を経て、最終的にリール大学のフランソワ・ブーリエが、 「ウスペンスキー法」は存在しない^{[21]という事実と「デカルト法」の両方が存在しないという事実に基づいて、この方法を}ヴィンセント-コリンズ-アクリタス（VCA）法と名付けました^[14] p. 24。^[22]この方法の最良の実装はRouillierとZimmermanによるもので、^[16]現在までに最速の二分法です。これはSturmのアルゴリズムと同じ最悪のケースの複雑さを持ちますが、ほとんどの場合はるかに高速です。これはMapleのRootFindingパッケージ に実装されています。

VCA( p , ( a , b )) の動作は次のとおりです。

• deg( p )次多項式p _orig ( x )でp _orig (0) ≠ 0であって、その正の根が孤立している必要がある場合、まずこれらの正の根の値の上限^{[12] [13]} ub を計算し、 p ( x ) = p _orig ( ub * x )かつ( a , b ) = (0, ub )と設定する。p ( x )の正の根はすべて区間(0, 1)内にあり、それらとp _orig ( x )の根の間には一対一の関係があり、p orig ( x )の根はすべて区間( a , b ) = (0, ub )内にある(対応する図を参照)。この一対一の関係はα _{( a , b )} = a + α _(0,1) ( b − a )と表現される。同様に、区間(0, 1)と(0, ub )の間にも一対一の関係がある。

• 処理するペア{ p ( x ),( a , b )}がある間、次の手順を繰り返します。
• p ( x )に対してBudan の「0_1 根検定」を使用して、区間 (0, 1) 内の根の数を計算します (係数のシーケンス内の符号変化の数varを使用)。根がない場合は空集合 ∅ を返し、根が 1 つある場合は区間 ( a , b ) を返します。
• 2つ以上の符号変化がある場合、ブダンの「0_1根テスト」は、区間(0, 1)内に0、1、2、またはそれ以上の実根が存在する可能性があることを意味します。この場合、それを半分にカットし、区間( 0、⁠1/2⁠ ) であり、区間 ( a、⁠ )内のp _orig ( x )の根に対応する。1/2⁠ ( a + b )) を区間 ( ⁠1/2⁠ , 1 )であり_、区間( ⁠1/2⁠ ( a + b ), b ); つまり、それぞれペアを処理する

${\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 )の根であり、分離区間は点に減少します。

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

VCA ( p、 ( a、b ))

入力: 一変量、平方自由多項式p ( ub * x ) ∈ Z [ x ]、次数 deg( p ) の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⁠ ) // Budan の「0_1 根テスト」 ;
2 var = 0の場合 は RETURN ∅;
3 var = 1 の場合 、RETURN {( a , b )};
4 p 0 ⁠1/2⁠ ← 2 度( p ) p ( ⁠x/2⁠ ) // (0, ⁠の実根を探す1/2⁠ );
5m ← ⁠​1/2⁠ ( a + b ) // ⁠1/2⁠ルート？
6ページ​1/2⁠ 1 ← 2 度( p ) p ( ⁠x + 1/2⁠ ) // ( ⁠内の実根を探す1/2⁠、1);
7もし p ( ⁠1/2⁠ ) ≠ 0 の場合は
8          RETURN VCA ( p 0 ⁠1/2⁠ , ( a , m )) ∪ VCA ( p ⁠1/2⁠ 1、 ( m、 b ))
9そうでない場合
10         RETURN VCA ( p 0 ⁠1/2⁠ , ( a , m )) ∪ {[ m , m ]} ∪ VCA ( p ⁠1/2⁠ 1、 ( m、 b ))
11終わり

述べる

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

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

1 var ← 2 // ( x + 1)の係数列における符号変化の数3 p ( ⁠1/x + 1⁠） = 7 x 3 − 7 x 2 − 35 x + 43
4 p 0 ⁠1/2← 64 x 3 − 112 x + 56
5メートル← 2
6ページ​1/2⁠ 1 ← 64 x 3 + 192 x 2 + 80 x + 8
7ページ( ⁠1/2⁠） = 1
8          戻り値VCA(64 x 3 − 112 x + 56, (0, 2)) ∪ VCA(64 x 3 + 192 x 2 + 80 x + 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\}.}$

最初に削除して処理します。

VCA(64 x 3 − 112 x + 56, (0, 2))
1 var ← 2 // ( x + 1)の係数列における符号変化の数3 p ( ⁠1/x + 1⁠） = 56 x 3 + 56 x 2 − 56 x + 8
4 p 0 ⁠1/2← 64 x 3 − 448 x + 448
5メートル← 1
6ページ​1/2⁠ 1 ← 64 x 3 + 192 x 2 − 256 x + 64
7ページ( ⁠1/2⁠） = 8
8          戻り値VCA(64 x 3 − 448 x + 448, (0, 1)) ∪ VCA(64 x 3 + 192 x 2 − 256 x + 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\}.}$

最初に削除して処理します。

VCA(64 x 3 − 448 x + 448, (0, 1))
1 var ← 0 // ( x + 1) 3 p ( ⁠の係数のシーケンスにおける符号の変化の数1/x + 1⁠） = 448 x 3 + 896 x 2 + 448 x + 64
2          戻る∅

分離間隔のリスト: { }。

処理する ペア{ 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\}.}$

最初に削除して処理します。

VCA(64 x 3 + 192 x 2 − 256 x + 64, (1, 2))
1 var ← 2 // ( x + 1)の係数列における符号変化の数3 p ( ⁠1/x + 1⁠） = 64 x 3 − 64 x 2 − 128 x + 64
4 p 0 ⁠1/2⁠ ← 64 x 3 + 384 x 2 − 1024 x + 512
5m ← ⁠​3/2⁠ 
6ページ⁠1/2⁠ 1 ← 64 x 3 + 576 x 2 − 64 x + 64
7ページ( ⁠1/2⁠ ) = −8
8リターンVCA(64 x 3 + 384 x 2 − 1024 x + 512, (1, ⁠3/2⁠ )) ∪ VCA(64 x 3 + 576 x 2 − 64 x − 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\}.}$

最初に削除して処理します。

VCA(64 x 3 + 384 x 2 − 1024 x + 512, (1, ⁠3/2⁠ ))
1 var ← 1 // ( x + 1) 3 p ( ⁠の係数のシーケンスにおける符号の変化の数1/x + 1⁠） = 512 x 3 + 512 x 2 − 128 x − 64
3戻り値{(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\}.}$

最初に削除して処理します。

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

1 var ← 1 // ( x + 1) 3 p ( ⁠の係数のシーケンスにおける符号の変化の数1/x + 1⁠） = −64 x 3 − 256 x 2 + 256 x + 512
3戻り値{( ⁠3/2⁠、2)}

隔離間隔のリスト: {(1, ⁠3/2⁠）、（⁠3/2⁠、2)}。

処理する ペア{ p , I }のリスト:

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

最初に削除して処理します。

VCA(64 x 3 + 192 x 2 + 80 x + 8, (2, 4))
1 var ← 0 // ( x + 1) 3 p ( ⁠の係数のシーケンスにおける符号の変化の数1/x + 1⁠） = 8 x 3 + 104 x 2 + 376 x + 344
2戻る∅

隔離間隔のリスト: {(1, ⁠3/2⁠）、（⁠3/2⁠、2)}。

処理対象となるペア{ p , I }のリスト: ∅。

終了した。

したがって、多項式p ( x ) = x ³ − 7 x + 7の2つの正の根は、孤立区間（1、⁠3/2⁠ )と( ⁠3/2⁠ , 2) }。各根は、（例えば）その根が含まれる孤立区間を、端点の差が10 ^{−6未満になるまで二等分することによって近似することができます。この方法に従うと、根は}ρ ₁ = 1.3569およびρ ₂ = 1.69202になります。

これは最後に開発されたもので、ヴィンセント定理から導かれた最も単純な実根分離法です。

VAG( p , ( a , b )) の動作は 次のとおりです。

• p (0) ≠ 0となる次数deg( p )の多項式p ( x )が与えられ、その正の根は孤立していなければならない場合、まずこれらの正の根の値の上限[12] [13] ubを計算し、(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つ以上の符号変化がある場合、アレシナ・ガルッツィの「a_b根テスト」は、区間（a、b ）内に0、1、2、またはそれ以上の実根が存在する可能性があることを意味します。この場合、区間を半分に分割し、区間（a、⁠）内のp（x ）の根を個別に検討します。1/2⁠ ( a + b )) を区間 ( ⁠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 ))
入力: 一変量、平方自由多項式p ( x ) ∈ Z [ x ]、p (0) ≠ 0、次数 deg( p )、開区間 ( 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 var = 0の場合 は RETURN ∅;
3 var = 1 の場合 、RETURN {( a , b )};
4 m ← ⁠1/2⁠ ( a + b ) // 区間 ( a、b ) を 2 つの等しい部分に分割します。
5 p ( m ) ≠ 0の場合6  
RETURN         VAG ( p , ( a , m )) ∪ VAG( p , ( m , b ))
7そうでない場合
8         RETURN VAG( p , ( a , m )) ∪ {[ m , m ]} ∪ VAG( p , ( m , b ))
9終わり

備考

• VCAと比較すると、上記のアルゴリズムは非常に単純です。対照的に、VAGは時間のかかる「a_bルートテスト」を使用するため、VCAよりもはるかに遅くなります。^[19]
• アレシナとガルッツィが指摘しているように、^[5] p. 189、ドナート・サエリによるこのアルゴリズムのバリエーションがあります。サエリは、端点の中点の代わりに端点の中央値を使用することを提案しました。1/2⁠ ( a + b ) 。しかし、エンドポイントの中央値を使用すると、一般に「中間点」バージョンよりもはるかに遅くなることが示されています^{[19] 。}

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

1 var ← 2 // ( x + 1)の係数列における符号変化の数3 p ( ⁠4倍/x + 1⁠） = 43 x 3 − 35 x 2 − 7 x + 7
4 m ← ⁠1/2⁠ (0 + 4) = 2
5 p ( m ) = 1
8          戻り値VAG( x 3 − 7 x + 7, (0, 2)) ∪ VAG( x 3 − 7 x + 7, (2, 4)

分離間隔のリスト: {}。

処理する間隔のリスト: {(0, 2), (2, 4)}。

最初に削除して処理します。

VAG( x 3 − 7 x + 7, (0, 2))
1 var ← 2 // ( x + 1)の係数列における符号変化の数3 p ( ⁠2倍/x + 1⁠） = x 3 − 7 x 2 + 7 x + 7
4 m ← ⁠1/2⁠ (0 + 2) = 1
5 p ( m ) = 1
8          戻り値VAG( x 3 − 7 x + 7, (0, 1)) ∪ VAG( x 3 − 7 x + 7, (1, 2)

分離間隔のリスト: {}。

処理する間隔のリスト: {(0, 1), (1, 2), (2, 4)}。

最初に削除して処理します。

VAG( x 3 − 7 x + 7, (0, 1))
1 var ← 0 // ( x + 1) 3 p ( ⁠の係数のシーケンスにおける符号の変化の数x/x + 1⁠） = x 3 + 7 x 2 + 14 x + 7
2          戻る∅

分離間隔のリスト: {}。

処理する間隔のリスト: {(1, 2), (2, 4)}。

最初に削除して処理します。

VAG( x 3 − 7 x + 7, (1, 2))
1 var ← 2 // ( x + 1)の係数列における符号変化の数3 p ( ⁠2倍+1/x + 1⁠） = x 3 − 2 x 2 − x + 1
4 m ← ⁠1/2⁠ (1 + 2) = ⁠3/2⁠ 
5 p ( m ) = − ⁠1/8⁠ 
8          戻り値VAG( x 3 − 7 x + 7, (1, ⁠3/2⁠ )) ∪ VAG( x 3 − 7 x + 7, ( ⁠3/2⁠、2))

分離間隔のリスト: {}。

処理する区間のリスト: {(1, ⁠3/2⁠）、（⁠3/2⁠ , 2), (2, 4)}.

最初に削除して処理します。

VAG( x 3 − 7 x + 7, (1, ⁠3/2⁠ ))
1 var ← 1 // 2 3 ( x + 1) 3 p ( ⁠の係数のシーケンスにおける符号の変化の数⁠3/2⁠ x + 1/x + 1⁠） = x 3 + 2 x 2 − 8 x − 8
3          リターン(1, ⁠3/2⁠ )

隔離間隔のリスト: {(1, ⁠3/2⁠ )}.

処理対象となる間隔のリスト: {( ⁠3/2⁠ , 2), (2, 4)}.

最初に削除して処理します。

VAG( x 3 − 7 x + 7, ( ⁠3/2⁠、2))
1 var ← 1 // 2 3 ( x + 1) 3 p ( ⁠の係数のシーケンスにおける符号の変化の数2 x + ⁠3/2⁠/x + 1⁠） = 8 x 3 + 4 x 2 − 4 x − 1
3          戻る( ⁠3/2⁠、2)

隔離間隔のリスト: {(1, ⁠3/2⁠）、（⁠3/2⁠、2)}。

処理する間隔のリスト: {(2, 4)}。

最初に削除して処理します。

VAG( x 3 − 7 x + 7, (2, 4))
1 var ← 0 // ( x + 1) 3 p ( ⁠の係数のシーケンスにおける符号の変化の数4 × +2/x + 1⁠） = 344 x 3 + 376 x 2 + 104 x + 8
2          戻る∅

隔離間隔のリスト: {(1, ⁠3/2⁠）、（⁠3/2⁠、2)}。

処理する間隔のリスト: ∅。

終了した。

したがって、多項式p ( x ) = x ³ − 7 x + 7の2つの正の根は、孤立区間（1、⁠3/2⁠ )と( ⁠3/2⁠ , 2) }。各根は、（例えば）その根が含まれる孤立区間を、端点の差が10 ^{−6未満になるまで二等分することによって近似することができます。この方法に従うと、根は}ρ ₁ = 1.3569およびρ ₂ = 1.69202になります。

• 多項式根の性質
• 根を求めるアルゴリズム
• ヴィエタの公式
• ニュートン法

• Berkakis、Antonis: RealRoots、Sturm 法と VAS を比較する Android デバイス向けの無料アプリ
• https://play.google.com/store/apps/details?id=org.kde.necessitas.berkakis.realroots