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

多項式 $f(x)\in\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)\DefEq f(x), \quad f_1(x)\DefEq f'(x),$$ (A.1)

$$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.2)

$$\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)$ で割ったときの 普通の剰余の $(-1)$ 倍を $f_{k+1}(x)$ とすることに注意しよう。 そうする理由は以下の (A.3) を成立させるためである。)

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