ヴァンサンの定理

ウィキペディア

ヴァンサンの定理

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/08/29 23:27 UTC 版)

数学において、アレクサンドル・ジョゼフ・イドゥルフ・ヴァンサン（フランス語: 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つのバージョンがある。ヴァンサンによる連分数版 と、AlesinaとGaluzziによる二分法版 である。

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

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

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

Obreschkoffの $S_{\sqrt {3}}$

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

ヴァンサンのアルゴリズムが指数関数的な性質を持つのは、部分商「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）であった。

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

ヴァンサンの定理の復活

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

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

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

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

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

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

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

最後に、理想的な正根の下限は存在しないため、Strzeboński は 2005 年に、 $lb_{computed}>16$

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) の根に対応するものを別々に考える。つまり、それぞれ次のペアを処理する。

$\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\}$

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 p0
                 1/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 p
                 1/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 (p0
                 1/2, (a, m)) ∪ VCA (p
                 1/21, (m, b))
9 else
10        RETURN VCA (p0
                 1/2, (a, m)) ∪ {[m, m]} ∪ VCA (p
                 1/21, (m, b))
11 end

注釈

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

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

多項式 p_orig(x) = x³ − 7x + 7 が与えられ、正根の値の上限 として 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 p0
                 1/2 ← 64x3 − 112x + 56
5 m ← 2
6 p
                 1/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} ：

$\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 p0
                 1/2 ← 64x3 − 448x + 448
5 m ← 1
6 p
                 1/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} ：

$\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} ：

$\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 p0
                 1/2 ← 64x3 + 384x2 − 1024x + 512
5 m ← 
                3/2
6 p
                 1/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} ：

$\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} ：

$\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} ：

$\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 を計算し、(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よりもはるかに遅くなる。
• AlesinaとGaluzziが指摘しているように、このアルゴリズムの Donato Saeli による変種がある p. 189。Saeliは、端点の中点 1/2(a + b) の代わりに、端点のmediantを使用することを提案した。しかし、端点のmediantを使用すると、一般的に「中点」バージョンよりもはるかに遅くなることが示されている。

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

多項式 p(x) = x³ − 7x + 7 が与えられ、正根の値の上限として 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 になる。

関連項目

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

外部リンク

• Berkakis, Antonis: RealRoots, a free App for Android devices to compare Sturm's method and VAS
• https://play.google.com/store/apps/details?id=org.kde.necessitas.berkakis.realroots