シュトゥルムの定理

数学において、一変数多項式pのシュトゥルム列は、多項式に対するユークリッドの互除法の変形によってpとその導関数に関連付けられた多項式の列である。シュトゥルムの定理は、区間内に位置するpの異なる実根の数を、区間の境界におけるシュトゥルム列の値の符号の変化の数で表す。これをすべての実数の区間に適用すると、 pの実根の総数が得られる。^[1]

代数学の基本定理は、重複度で数えた複素根の総数を容易に導き出すが、その計算手順は示していない。 シュトゥルムの定理は、異なる実根の数を数え、それらを区間内に配置します。いくつかの根を含む区間を細分化することで、根を任意の小さな区間に分離し、各区間に 1 つの根だけを含めることができます。これにより、最も古い実根分離アルゴリズムと、一変量多項式の 任意精度の根探索アルゴリズムが得られます。

実数上の計算では、シュトゥルムの定理はデカルトの符号規則に基づく他の方法よりも効率が悪い。しかし、この定理はあらゆる実閉体上で機能するため、実数の 第一階理論における決定可能性と量指定子除去の計算複雑性の理論的研究の基礎として残っている。

シュトゥルム列とシュトゥルムの定理は、1829年に定理を発見したジャック・シャルル・フランソワ・シュトゥルムにちなんで名付けられました。 ^[2]

実係数を持つ一変数多項式P ( x )のシュトゥルム連鎖またはシュトゥルム列は、次のような 多項式の列である。 ${\displaystyle P_{0},P_{1},\ldots ,}$

${\displaystyle {\begin{aligned}P_{0}&=P,\\P_{1}&=P',\\P_{i+1}&=-\operatorname {rem} (P_{i-1},P_{i}),\end{aligned}}}$

i ≥ 1の場合、P' はPの導関数であり、 はを で除算した剰余です。 Sturm 数列の長さは最大でPの次数です。 ${\displaystyle \operatorname {rem} (P_{i-1},P_{i})}$${\displaystyle P_{i-1}}$${\displaystyle P_{i}.}$

Pのシュトゥルム列のξにおける符号変化の数は、実数列における符号変化の数（ゼロを無視）である。

${\displaystyle P_{0}(\xi ),P_{1}(\xi ),P_{2}(\xi ),\ldots .}$

この符号変化の数はここではV ( ξ )と表記される。

シュトゥルムの定理は、Pが平方根のない多項式である場合、半開区間[ a、b ]におけるPの異なる実根の数はV ( a )−V ( b )である（ここで、aとbはa < bとなる実数である）。^[1]

この定理は、多項式の+∞における符号をその主係数(つまり、最高次数の項の係数) の符号として定義することで、無限区間に拡張されます。-∞における多項式の符号は、偶数次多項式の場合は主係数の符号となり、奇数次多項式の場合はその反対の符号となります。

非平方自由多項式の場合、aもbもpの倍数根でない場合、V ( a ) − V ( b )はPの異なる実根の数です。

定理の証明は次のとおりです。xの値がaからbに増加するとき、何らかのゼロ( i > 0 ) を通過することがあります。これが発生すると、 の符号変化の数は変化しません。x がの根を通過すると、 の符号変化の数は1 から 0 に減少します。これらは、何らかの符号が変化する可能性があるxの値のみです。 ${\displaystyle P_{i}}$${\displaystyle (P_{i-1},P_{i},P_{i+1})}$${\displaystyle P_{0}=P,}$${\displaystyle (P_{0},P_{1})}$

多項式のある範囲における根の数を求めたいとします。 ${\displaystyle p(x)=x^{4}+x^{3}-x-1}$

${\displaystyle {\begin{aligned}p_{0}(x)&=p(x)=x^{4}+x^{3}-x-1\\p_{1}(x)&=p'(x)=4x^{3}+3x^{2}-1\end{aligned}}}$

p ₀をp ₁で割った余りは、それに-1を掛けたもので、 ${\displaystyle -{\tfrac {3}{16}}x^{2}-{\tfrac {3}{4}}x-{\tfrac {15}{16}};}$

${\displaystyle p_{2}(x)={\tfrac {3}{16}}x^{2}+{\tfrac {3}{4}}x+{\tfrac {15}{16}}}$。

次にp _{1 を}p ₂で割り、余りに-1を掛けると、

${\displaystyle p_{3}(x)=-32x-64}$。

ここでp _{2 を}p ₃で割り、余りに-1を掛けると、

${\displaystyle p_{4}(x)=-{\tfrac {3}{16}}}$。

これは定数なので、これで Sturm シーケンスの計算は終了します。

実根の個数を求めるには、これらの多項式の−∞と∞における符号の列を評価する必要があります。符号の列はそれぞれ(+, −, +, +, −)と(+, +, +, −, −)です。したがって、 ${\displaystyle p_{0}}$

${\displaystyle V(-\infty )-V(+\infty )=3-1=2,}$

ここで、V はシーケンス内の符号の変化の数を表し、p に2 つの実根があることを示します。

これは、p ( x ) が( x ² − 1)( x ² + x + 1)と因数分解できることに注目することで確認できます。ここで、最初の因数は根−1と1 を持ち、2 番目の因数は実根を持ちません。この最後の主張は、二次方程式の公式と、 -∞で符号シーケンス(+、-、​​-)、+∞で(+、+、-)を与える Sturm の定理から生じます。

シュトゥルム数列は 2 つの方向に一般化されています。数列の各多項式を定義するために、シュトゥルムは、前の 2 つの多項式のユークリッド除算の剰余の負数を使用しました。剰余の負数をその積または商で置き換えても、正の定数または多項式の 2 乗で置き換えても、定理は有効です。2 番目の多項式が最初の多項式の導関数ではない数列を考慮することも有用です (以下を参照)。

一般化されたシュトゥルム列は、実係数を持つ多項式の有限列である。

${\displaystyle P_{0},P_{1},\dots ,P_{m}}$

そのような

• 次数は最初の次数より減少します: i = 2, ..., mの場合;${\displaystyle \deg P_{i}<\deg P_{i-1}}$
• ${\displaystyle P_{m}}$実根を持たないか、実根の近くで符号が変化しません。
• 0 < i < mでP _i ( ξ ) = 0かつξが実数である場合、 P _{i −1} ( ξ ) P _{i + 1} ( ξ ) < 0です。

最後の条件は、連続する 2 つの多項式に共通の実根がないことを意味します。特に、多項式に多重実根がない場合 (その場合に限ります)、元の Sturm 列は一般化 Sturm 列です (そうでない場合、その Sturm 列の最初の 2 つの多項式に共通根があります)。

元の Sturm 列をユークリッド除算で計算する場合、 やなど、決して負にならない因数を持つ多項式に遭遇することがあります。この場合、多項式をその商で非負の因数に置き換えて計算を続けると、一般化された Sturm 列が得られます。これは、実根の数を計算するためにも使用できます。これは、 Sturm の定理の証明が依然として適用されるためです (3 番目の条件のため)。これにより計算が簡素化される場合もありますが、xの偶数乗を除いて、このような非負の因数を見つけることは一般に困難です。 ${\displaystyle x^{2}}$${\displaystyle x^{2}+1}$

コンピュータ代数では、考慮される多項式は整数係数を持つか、整数係数を持つように変換される可能性があります。整数係数を持つ多項式の Sturm 列には、通常、係数が整数ではない多項式が含まれます (上記の例を参照)。

有理数での計算を避けるための一般的な方法は、多項式の最大公約数 を計算する際にユークリッド除算を擬似除算に置き換えることです。これは、ユークリッドアルゴリズムの剰余列 を擬似剰余列で置き換えることに相当します。擬似剰余列とは、定数 および が存在する多項式の列で、を で除算した剰余となるものです(擬似剰余列の種類はおよびの選択によって定義されます。通常、はユークリッド除算中に分母を導入しないように選択され、 は結果として得られる剰余 の係数の公約数です。詳細については、 「擬似剰余列」を参照してください)。たとえば、ユークリッドアルゴリズムの剰余列 は、すべてのiに対して となる擬似剰余列であり、多項式の Sturm 列 は、すべてのiに対しておよび となる擬似剰余列です。 ${\displaystyle p_{0},\ldots,p_{k}}$${\displaystyle a_{i}}$${\displaystyle b_{i}}$${\displaystyle b_{i}p_{i+1}}$${\displaystyle a_{i}p_{i-1}}$${\displaystyle p_{i}.}$${\displaystyle a_{i}}$${\displaystyle b_{i};}$${\displaystyle a_{i}}$${\displaystyle b_{i}}$${\displaystyle a_{i}=b_{i}=1}$${\displaystyle a_{i}=1}$${\displaystyle b_{i}=-1}$

さまざまな擬似剰余列が、分母を導入せずに整数係数を持つ多項式の最大公約数を計算するために設計されています (擬似剰余列を参照)。の符号を の符号と反対に選択することで、これらはすべて一般化された Sturm 列にすることができます。これにより、擬似剰余列で Sturm の定理を使用できます。 ${\displaystyle b_{i}}$${\displaystyle a_{i}.}$

実係数を持つ多項式の場合、根の分離とは、各実根に対して、この根を含み他の根を含まない区間を見つけることです。

これは根を見つけるのに役立ち、見つけるべき根の選択を可能にし、ニュートン法などの高速数値アルゴリズムの良い出発点を提供します。また、ニュートン法が区間外で収束した場合、間違った根に収束していることがすぐに推測できるため、結果を証明するのにも役立ちます。

ルート分離は代数的数の計算にも役立ちます。代数的数の計算では、代数的数がルートである多項式と分離区間のペアとして表現するのが一般的な方法です。たとえば、次のように明確に表現できます。${\displaystyle {\sqrt {2}}}$${\displaystyle (x^{2}-2,[0,2]).}$

シュトゥルムの定理は、実根を分離する方法を提供するが、これは（整数係数の多項式の場合）デカルトの符号規則を含む他の方法よりも効率が悪い。しかし、主に理論的な目的、例えば無限小を含む実代数幾何学のアルゴリズムなど、状況によっては有用である。^[3]

実根を分離するには、すべての実根、または関心のある根（多くの場合、典型的な物理的問題では、正の根だけが関心の対象になります）を含む区間から開始し、 と を計算します。この開始区間を定義するために、根のサイズの境界を使用できます（多項式根の性質 § （複素）多項式根の境界 を参照）。次に、の途中でc を選択して、この区間を 2 つに分割します。 の計算により、 との実根の数が与えられ、各サブ区間で同じ操作を繰り返すことができます。この処理中に根を含まない区間に遭遇した場合、考慮する区間のリストからその区間を削除できます。ちょうど 1 つの根を含む区間に遭遇した場合、それは分離区間であるため、分割を停止できます。分離区間のみが残った時点で、この処理は最終的に停止します。 ${\displaystyle (a,b]}$${\displaystyle V(a)}$${\displaystyle V(b).}$${\displaystyle (a,b].}$${\displaystyle V(c)}$${\displaystyle (a,c]}$${\displaystyle (c,b],}$

この分離プロセスは、区間内の実根の数を計算する任意の方法で使用できます。理論的な複雑性分析と実際の経験から、デカルトの符号規則に基づく方法の方が効率的であることがわかっています。したがって、今日では、Sturm シーケンスは根の分離にほとんど使用されていません。

一般化された Sturm 列を使用すると、別の多項式が正 (または負) である多項式の根を、明示的に計算せずに数えることができます。最初の多項式の根の分離区間がわかっている場合は、根のより良い近似値を計算することなしに、最初の多項式のこの特定の根における 2 番目の多項式の符号を見つけることもできます。

P ( x )とQ ( x )を、 PとQに共通根がなく、Pに多重根がないような実係数の 2 つの多項式とします。言い換えると、PとP'  Q は互いに素な多項式です。この制限は、 GCD計算によって一般的なケースをこのケースに簡略化できるため、以降の一般性にはあまり影響しません。また、シュトゥルム シーケンスの計算コストは​​ GCD の計算コストと同じです。

PとP' Qから始まる一般化されたSturm 数列のaにおける符号変化の数をW ( a )で表す。a < b が 2 つの実数である場合、W ( a ) - W ( b )は、 Q ( a ) > 0となる区間にあるPの根の数から、同じ区間にあるQ ( a ) < 0となる根の数を引いた値である。 Sturm の定理で与えられる同じ区間にあるPの根の総数と組み合わせると、 Q ( a ) > 0となるPの根の数と、 Q ( a ) < 0となるPの根の数が得られる。^[1] ${\displaystyle (a,b]}$

• Basu, Saugata; Pollack, Richard ; Roy , ​​Marie-Françoise (2006). 「セクション 2.2.2」。実代数幾何学のアルゴリズム(第 2 版)。Springer。pp . 52–57。ISBN 978-3-540-33098-1。
• スターム、ジャック・シャルル・フランソワ（1829年）。 「数字に関する解決策の記憶」。フェルサック科学紀要。11 : 419–425。
• シルベスター、JJ (1853)。「2 つの有理積分関数の合同関係の理論について。これには、シュトゥルム関数の理論への応用と、最大代数共通測度の理論が含まれます。」Phil. Trans. R. Soc. Lond . 143 : 407–548. doi : 10.1098/rstl.1853.0018 . JSTOR  108572。
• Thomas, Joseph Miller (1941). 「多重根に対するシュトゥルムの定理」. National Mathematics Magazine . 15 (8): 391–394. doi :10.2307/3028551. JSTOR  3028551. MR  0005945.
• Heindel, Lee E. (1971).多項式実数ゼロ判定のための整数演算アルゴリズム. Proc. SYMSAC '71 . p. 415. doi :10.1145/800204.806312. MR  0300434. S2CID  9971778.
• de Moura, Leonardo; Passmore, Grant Olney (2013)。「有理数の実閉無限小および超越拡張における計算」。自動演繹 – CADE-24。コンピュータサイエンスの講義ノート。第 7898 巻。p . 178-192。doi :10.1007/978-3-642-38574-2_12。ISBN 978-3-642-38573-5. S2CID  9308312。
• Panton, Don B.; Verdini, William A. (1981). 「内部収益率の計算に Sturm の定理を適用する Fortran プログラム」J. Financ. Quant. Anal . 16 (3): 381–388. doi :10.2307/2330245. JSTOR  2330245. S2CID  154334522.
• Akritas, Alkiviadis G. (1982). 「Budan と Fourier による一対の定理に関する考察」. Math. Mag . 55 (5): 292–298. doi :10.2307/2690097. JSTOR  2690097. MR  0678195.
• Pedersen, Paul (1991)。「多変量 Sturm 理論」。Mattson, Harold F.、Mora, Teo、Rao, TRN (編)。応用代数、代数アルゴリズム、およびエラー訂正コード、第 9 回国際シンポジウム、AAECC-9、ニューオーリンズ、ルイジアナ州、米国、1991 年 10 月 7 ～ 11 日、議事録。コンピュータ サイエンスの講義ノート。第 539 巻。ベルリン: Springer。pp. 318 ～ 332。doi : 10.1007 /3-540-54522-0_120。ISBN 978-3-540-54522-4. MR  1229329。
• ヤップ、チー（2000）。アルゴリズム代数の基本問題。オックスフォード大学出版局。ISBN 0-19-512516-9。
• Rahman, QI; Schmeisser, G. (2002).多項式の解析理論. ロンドン数学会モノグラフ. 新シリーズ. 第26巻. オックスフォード:オックスフォード大学出版局. ISBN 0-19-853493-0.ZBL1072.30006  。​
• ボーモル、ウィリアム。経済ダイナミクス、第 12 章、第 3 節、「実根に関する定性的な情報」
• DG Hook および PR McAree、「Sturm シーケンスを使用した多項式方程式の実根の括弧付け」、Graphic Gems I (A. Glassner 編)、Academic Press、pp. 416–422、1990 年。