昨日の計算機代数勉強会で代数的実数の実装のために出てきたスツルムの定理、共立出版の数値解析でも近似値の算出に使っており、証明も詳しく載っている。互除法だけではなく3重対角行列の主小行列式がスツルム列をなすことを使って固有値の算出をしたりもしている。
スツルムの定理は直感的にはそんなに難しいことは言ってない。
図の黒線のように根を何個か持つ多項式から始まって紫線のように最終的に根を持たない多項式に至る列がスツルム列だ。
wikipediaに書いてある4.のルールにより、根を持つ点で傾きが正の部分であれば上に、傾きが負であれば下方向にグラフが抜ける。そのため、スツルム列の0番目から1番目において根は左方向に動くことになる。また、2.のルール(wikipediaの記述は間違っているが)のために1番目以降も根はひたすら左に動き続ける。
aでの符号が変わることは、根が1つ区間の左側に抜けて消えたことを意味する。
bでの符号が変わることは、区間の右側から新たな根が混入したことを意味する。
最終的に根がない状態でスツルム列は終わっているので、aの符号の変化からbの符号の変化を引けば、0番目の多項式が何個根を持っていたかわかるという寸法である。
