スツルムの定理
スツルムの定理(スツルムのていり、英: Sturm's theorem)とは、実係数一変数多項式の任意に指定された実区間に含まれる(重複を含めない)実零点の個数を決定する方法である(扱える区間としては無限区間、半無限区間も含む)。
代数学の基本定理によれば(一般には複素係数の)一変数多項式の重複を込めた複素零点の個数はその多項式の次数に等しいが、スツルムの定理では実係数多項式の実零点の個数を重複を考慮せずに扱っている。
スツルム列
実区間[math][a,b][/math]が与えられたとき、次の4つの条件を満足する実係数をもつ多項式列
- [math] f_0(x),~f_1(x),~f_2(x),~\cdots,~f_L(x)[/math]
は区間[math][a,b][/math]においてスツルム列(スツルム関数列)をなすという。
- 列中にある任意の隣り合う2つの多項式[math]f_k(x)[/math]と[math]f_{k+1}(x)[/math]は、区間[math]x \in [a,b][/math]に於いて共通の零点を持たない。
- 列中にある任意の隣り合う3つの多項式[math]f_{k-1}(x)[/math]、[math]f_k(x)[/math]、[math]f_{k+1}(x)[/math]について、区間[math][a,b][/math]に於ける多項式[math]f_k(x)[/math]の零点[math]z[/math]に対して、その両側の多項式の[math]z[/math]に於ける値の符号は逆になる(つまり[math]z\in[a,b][/math]かつ[math]f_k(z)=0[/math]ならば[math]f_{k-1}(z) f_{k+1}(z)\lt 0[/math]である)。
- 列の最後の多項式[math]f_L(x)[/math]は 区間[math]x \in [a,b][/math]に於いて一定の符号を持つ(つまり[math]f_L(x)[/math]は区間[math]x \in [a,b][/math]に零点を持たない)。
- [math]f_0(x)[/math]の区間[math]x \in [a,b][/math]に於ける任意の零点を[math]z[/math]とすれば、[math]f_0'(z) f_1(z) \gt 0[/math]である。ここで[math]f_0'(x)[/math]は[math]f_0(x)[/math]の導関数を表す。
ユークリッドの互除法によるスツルム列の生成
上の条件を満足するスツルム列の一つとして、多項式[math]f(x)[/math]とその微分[math]f'(x)[/math]について
- [math]f_0(x)=f(x)[/math]
- [math]f_1(x)=f'(x)[/math]
とおき、これにユークリッドの互除法を適用することで得られる多項式列がある:
- [math]\begin{matrix} f_0(x) & = & g_1(x)f_1(x)-f_2(x)\\ f_1(x) & = & g_2(x)f_2(x)-f_3(x)\\ f_2(x) & = & g_3(x)f_3(x)-f_4(x)\\ * & \vdots & \\ f_{l-1}(x) & = & g_l(x)f_l(x)~~~~~~~~~~\\ \end{matrix}[/math]
このとき[math]f_l(x)[/math]は[math]f_0(x)[/math]と[math]f_1(x)[/math]との最大公約数であり、さらに[math]f(x)=0[/math]と[math]f'(x)=0[/math]が共通根をもたない、 すなわち[math]f(x)=0[/math]が単根のみをもつとき、[math]f_l(x)=[/math]定数[math]\ne0[/math]を満足する。
また、3重対角化された対称行列[math]A[/math]からなる行列[math]\lambda I-A[/math]の主小行列式により構成される多項式列や、最高次の係数が正である直交多項式の列も 区間[math][a,b][/math]においてスツルム列をなす。
スツルムの定理
実係数多項式の列[math]f_0(x),f_1(x),f_2(x),\cdots,f_l(x)[/math]は[math]x \in [a,b][/math]でスツルム列をなし、[math]f_0(a)f_0(b)\neq0[/math]であるとする。 このとき、[math]x[/math]を固定して関数値の列
- [math] f_0(x),~f_1(x),~f_2(x),~\cdots,~f_l(x)[/math]
を左から右に見ていったときの符号(正負)の変化の回数を[math]N(x)[/math]とすると、方程式[math]f_0(x)=0[/math]の区間[math][a,b][/math]内における解の個数は
- [math] N(a)-N(b)[/math]
で与えられる。
スツルムの方法
スツルムの定理を用いることで、区間[math][a,b][/math]内に存在する[math]f(x)=0[/math]の実根の個数を求めることができるが、これを利用して区間縮小法により実係数をもつ代数方程式の実数解を求めることができる。
たとえば区間[math][a,b][/math]を2等分して[math][a,(a+b)/2],[(a+b)/2,b][/math]なる二つの区間に分け、各区間における根の個数をスツルムの定理によって求める、という手順を繰り返してしだいに区間を狭くしていく。 そして、一つの根だけが存在する区間を十分に小さくすることで、根の近似値を得ることができる。(二分法)
また、区間[math][a,b][/math]において[math]a[/math]を固定して[math]b[/math]を[math]N(a)-N(b)=1[/math]になるまで小さくし、それから二分法を用いて[math]b-a\le\varepsilon[/math]になるように[math]a,b[/math]の値を近づけることで根の最小値を決定し、そして次に小さい根を決定する、といったように根の近似値を小さい根の方から、あるいは大きい方から得ることもできる。
このように二分法やニュートン法などの求根アルゴリズムを用いてスツルムの定理から根の近似値を求める手法をスツルムの方法という。
実対称行列あるいはエルミート行列の固有値問題においても、指定された実区間にある固有値の個数(重複度を含めた)を求めることにより区間縮小法により固有値の存在範囲の狭めて近似値を求めるスツルムの二分法として応用される。
参考文献
- 高木貞治、「代数学講義(改訂新版)」第3章スツルムの問題,根の計算, 共立出版、1965年(初版は1930年、改訂版は1948年)
- 森正武 『数値解析』 共立出版、2002年2月。ISBN 4-320-01701-3。
- 夏目雄平・小川建吾 『計算物理I』 朝倉書店、2002年3月。ISBN 978-4-254-13713-2。