A.5.2 ユークリッドの互除法による Strum 列の生成

多項式 $f(x)\in\mathbb{R}[x]$ が与えられたとき、 $f_0(x)=f(x)$ と $f_1(x)=f'(x)$ から Euclid の互除法を行い、関数列 $f_0(x)$, $f_1(x)$, $\cdots$, $f_\ell(x)$ を作る:

$$f_0(x):= f(x), \quad f_1(x):= f'(x),$$ (A.5)

$$f(x) = q_1(x)f_1(x)-f_2(x), \quad \deg f_{2}(x)<\deg f_{1}(x),$$

$$f_1(x) = q_2(x)f_2(x)-f_3(x), \quad \deg f_{3}(x)<\deg f_{2}(x),$$

$$f_2(x) = q_3(x)f_3(x)-f_4(x), \quad \deg f_{4}(x)<\deg f_{3}(x),$$

$$\vdots$$

$$f_{k-1}(x) = q_{k-1}(x)f_{k}(x)-f_{k+1}(x), \quad \deg f_{k+1}(x)<\deg f_{k}(x),$$ (A.6)

$$\vdots$$

$$f_{\ell-2}(x) = q_{\ell-1}(x)f_{\ell-1}(x)-f_\ell(x), \quad \deg f_{\ell}(x)<\deg f_{\ell-1}(x),$$

$$f_{\ell-1}(x) = q_{\ell}(x)f_\ell(x).$$

(普通の互除法と異なり、 $f_{k-1}(x)$ を $f_{k}(x)$ で割ったときの 普通の剰余 $\times (-1)$ を $f_{k+1}(x)$ とする。)

よく知られているように $f_\ell(x)$ は $f(x)$ と $f'(x)$ の最大公約多項 式であるから、 $f(x)\in\mathbb{R}[x]$ が重根を持たない場合、 $f_\ell(x)\equiv$   定数 ($\ne 0$) となることに注意しよう。 以下この場合に $f(x)=0$ の解 (根) を求めることを考える。 $f(x)$ が重根を持つ場合は $f(x)$ の代わりに $g(x)=f(x)/f_\ell(x)$ を考えることで同様の議論ができる。

証明. まず $f_\ell(x)\equiv$定数 であるから、Strum 列の条件 (3) は満 たされている。次にある $x_0\in [a,b]$, ある $k\in\{0,1,\cdots,\ell-1\}$ に対して

$$f_{k}(x_0)=f_{k+1}(x_0)=0$$

となったとすると、式 (A.8) から $f_{k+2}(x_0)$ 以降の $f_j(x_0)$ もすべて 0 になり、特に $f_\ell(x_0)=0$. これは $f_\ell(x)$ が定数関数 ($\ne 0$) であることに矛盾する。ゆえに Strum 列の条件 (1) が 満たされる。 次にある点 $x_0$, ある $k\in\{1,2,\cdots,\ell-1\}$ に 対して $f_k(x_0)=0$ となったとすると、式 (A.8) から

$$f_{k-1}(x_0)=-f_{k+1}(x_0).$$

ゆえに Strum 列の条件 (2) も満たされる (条件 (3) から上式の値は 0 にな らないことに注意)。 最後に $x_0$ が $f(x)$ の根であるとき、$f(x)$ が重根を持たないという 仮定から $f'(x_0)\ne 0$ で、

$$f'(x_0)f_1(x_0)=f'(x_0)^2>0$$

となり、条件 (4) も満たされる。 $\qedsymbol$ $\qedsymbol$