数理解析研究所講究録920 巻 1995 年 120-124120

13.
近似代数その 21 変数多項式の近似 GCD の–般論
佐々木建昭 (筑波大数学系)
佐々木睦子 (理研情報科学)

13.1 はじめに筆者らは既に、正規な多項式 (定義は後で述べる) に対する近似 GCD の計算法として、ユークリッドの互除法に基づく算法を提案している $[1,2]$ 。この算法で確かに近似 GCD とその精度を計算できるが、 1) 最小精度の近似 GCD をどう計算するか ?
るか ?

$\text{、}$$\text{、}$2) 非正規な多項式の近似 GCD をどう計算すの 2 点が未解決であった。本稿は、 対象を 1 変数に限り、 これらの問題に解答を与えるものである。

13.2 近似 GCD と正規な多項式多項式$P$のノルム$||P||_{\text{、}}$

オーダ記号$O(a)\text{、}$acc 記号、 キャンセル数、組織的桁落ち、次数低下については、論文 [3] あるいは別稿「近似代数その 1: 近似多項式の四則演算」 を参照されたい。

多項式$F$と $G$ が次式を満たすとき、 $D$ を $F$ と $G$ の精度$\epsilon$の近似共通因子という。

$F(x)=D(x)\vec{F}(X)+\delta F(X)$ ,$\max\{||\delta F||/||F||, ||6G||/||G||\}=\epsilon\ll 1$$\{$$G(x)=D(x)\tilde{c}(_{X)\delta}+G(X)$ ,

(1)

121

精度

$\epsilon$を固定したときの近似共通因子の中で次数最大のものを精度

多項式 $P(x)$ の主係数 (leading coefficient) を$1\mathrm{c}(P)$で表す。

$\epsilon$の近似 GCD という。

$|1\mathrm{c}(P)|\simeq||P||$であるとき $P$ を正規(regular) な多項式という。 また、多項式 $F$ と $G$ が $|1\mathrm{c}(F)|\simeq||F||$ かつ $|1\mathrm{c}(G)|\simeq||G||$ を満たすとき$\{F, G\}$は正規であるという。

13.3 規格化剰余列
多項式 $F$ とはノルムが 1 に規格化されているものとする$G$: $||F||=||G||=1$ . 近似 GCD を剰余列で計算する場合、 剰余や商のノルムの大きさにより近似 GCD であるか否かを判定するので、剰余列をうまく規格化しておく必要がある。 ( $P_{1}=F$, 凸 $=G,$$\cdots,$$P.,$$\cdots$) を剰余列とするとき、$A.(x)P_{1}(x)+B:(x)P_{2}(X)=P_{i}(x)$ ,(2)$\{$$\deg(A|)<\deg(P2)-\deg(P.)$ ,を満足する多項式$A_{i}$.

$\deg(B:)<\deg(P_{1})-\deg(P.)$ ,と $B$ が存在する。そこで、と$A_{i}$$B_{1}$

を次のように規格化し、 そのときの剰余列を規格化剰余列 (normalized remainder sequence, 略して NRS) と呼ぶ。
$\max\{||A_{i}||, ||B.||\}=1$(3)$(i=3,4, \ldots)$

上記の規格イヒは論文 [1] におけるものとは異なっていることに注意されたい。論文 [1] における規格化と上記のものとは、 正規多項式に対してはほぼ同じだが、 非正規多項式に対しては大幅に異なる。
論文 [5] では、 剰余列に対して以下の関係式炉成立することが示されている。

$c:P_{1}=-B_{+1}.P_{i}+B_{i}P_{i+1}$,$c:P_{2}=A_{:+}{}_{1}P_{1}-A.P_{i+1}$

この式より、 $||P.+1||/||P.||=\epsilon_{i}\ll 1$ ならば且は $F$ と $G$ の精度$\simeq\epsilon_{i}$$(ci\in \mathrm{C})$(4)の近似 GCD であることが分かる。

13.4 近似 GCD の最小精度
多項式 $F$ と$G$定するとき、 精度の近似 GCD の次数は精度$\epsilon$$\epsilon$を変えれば変わり得る。逆に、近似 GCD の次数を固は無限に小さくはなりえず、 下限値$\epsilon_{c}$が存在する。 この下限値は以下のように規定できる。 ただし、 本稿では簡単のため、組織的桁落ちと次数低下は無視する。 $F,$ $G,$ $D$ を

122$F(x)=fix^{l}+fi-\iota xl-1+\cdots+f_{0}$ ,$\{$$G(x)=\mathit{9}mx^{m}+g_{m-1}xm-1+\cdots+g_{\mathrm{O}}$$D(x)=d_{\mathfrak{n}}x^{\mathfrak{n}}+d_{\mathfrak{n}-1^{X^{\mathfrak{n}-1}}}+\cdots+d_{\mathrm{O}}$(5),,と表す。 $D(x)$ が最小精度の近似 GCD の場合、 (1) より次式を得る。

$G(x)F(x)-F(x)G(X)=0$$\deg(\tilde{G})=m-n,$(acc$\epsilon_{c}$)(6)

ゆえ、 $(l+m-2n+2)\mathrm{x}(l+m-n+1)$ 行列 $W$ を$\deg(\tilde{F})=l-n$.
$f_{l-.1}.$$f_{l}0$$W=|$.

$f_{l-}f\mathrm{o}_{1}$$..$$\cdot.f_{l}...\cdot$

$0$

$fi$

.

$f_{0}0)$fo$f_{0}$$\mathrm{f}\mathrm{i}-1$

$|$

$|$

(7)

$|$

$=$

$g_{m-1}..$.

$g_{m}0$.

$g_{m-1}g_{0}$

$..$

.

$g_{0}0)$$\dot{g}_{m}.$で定義すれば、 (6) は $(l+m-2n+2)$ 個の $(l+m-n+1)$ 次元ベクトル$\mathrm{f}_{m-n},$..

$\mathrm{f}0,$$,$$,$$\mathrm{g}_{l-,l},$$\ldots$, goに対する近似線形従属関係である。 これより次の定理を得る。
定理 13.4.1. 多項式 $F$ と $G$ は次数の近似 GCD の最小精度は canc($n$$\mathrm{f}_{m}.-n$の近似 GCD をもつとする。次数,. ..,ると、 最小精度は不等式で規定できる。)$\mathrm{f}\mathrm{o},$$\mathrm{g}_{l-n},$$\ldots$$n$を固定するとき、 $F$ と$G$, go) で与えられる。 (組織的桁落ちを考慮す口13.5 非正規多項式の NRS多項式$F$と $G$ が正規であれ非正規であれ、 (1) により近似 GCD が定義できる。 $\{F, G\}$ が正規な場合、 規格化剰余列 $(P_{1}, P_{2}, P_{3}, \cdots)$ において $||P_{k}||=O(1),$$||P_{k+1}||\ll 1$となるとき$P_{k}$が精度 $O(||Pk+1||)$ の近似 GCD となる。 この場合、 ||P 矧 が次数最大の近似 GCD となり、 さらに$P_{k+2},$ $P_{k+3},$$\ldots$を計算することにより、 より小さい精度の (したがって小さい次数の) 近似 GCDが計算できる。 しかしながら、 この判定法は非正規な多項式に対しては適用できない。実際、 非正規多項式の場合、剰余列のある要素が近似 GCD になっても、 その次の要素のノルムが低下しないことがほとんどである。
さて、 1 変数多項式 $F(x)$ が正規な場合、 その根は複素平面上で半径が $O(1)$ 以下の円内に分布する。逆に、 非正規な多項式は絶対値が $O(1)$ より大きな根を持つ。 したがって、 $F$ が非正規で絶対値

123が $O(1)$ より大きな根て $(x/\zeta_{1}-1),$$\cdots,$$(x/\zeta_{\lambda}-1)$$F_{I}(x)$であるから、$x$$\zeta_{1}\ldots,$$\zeta_{\lambda}$を持つならば、 $F$ は規格化されている (ノルムが 1) から因子としを持つ。 そこで、 これらの因子の積を $F_{J}(x)$ とすると、$=$$(x/\zeta_{1}-1)\cdots(x/\zeta_{\lambda}-1)$$=$$[1/\zeta_{1}\cdot, .\zeta\lambda]X+\lambda\ldots(-1)\lambda+-1[1/\zeta_{1}+\cdots+1/\zeta\lambda]X+(-1)\lambda$(8)の高次項ほどそのノルムが小さくなることがわかる。

以上より、 $F$ が非正規な場合、 $F$ の項のうちある次数以上のものは次数が高いほどノルムが小さくなる。 したがって、多項式 $F$ と $G$ がどちらも非正規多項式の場合、 除算 $F/G$ では ( $p$ と $G$ の近似共通因子を除く)$F$と $G$ の絶対値最大の根に対応する因子 (に近いもの) が商となり、 その因子が除かれたものが剰余となる。 このことから次のことが主張でき、 それを使って非正規因子を含む近似

GCD を規格化剰余列から計算できる。
(1).

除算式 $P_{-1}.=Q:P$ $+c:P.+1$ において、 商 $Q$ : が正規でれる全ての非正規因子は $F$ と(2)$G$$|(|\gg 1$が非正規ならば、$P_{i+1}$に含まの非正規な近似共通因子である。

規格化剰余 $P_{k-1}$ が近似共通因子でない非正規因子を含み$(x/\zeta-1)P_{k}(x),$$P_{+1}.\cdot$$P_{k}$が近似 GCD の場合、 $P_{k-1}(x)\propto$となるから、 $P_{k-1}/||P_{k-1}||-P_{k}/||P_{k}||=O(1/|\zeta|)$ となる。

13.6 最小精度の近似 GCD の計算法
前章の議論より、 大雑把な精度の近似 GCD については、 その次数と大雑把な形が規格化剰余列の計算から分かる。 しかしながら、 特別な場合を除き、 それは最小精度の近似 GCD ではない。幸いなことに、 近似 GCD の次数が分かれば、 134 の議論より、 最小精度の近似 GCD が以下の手順で計算できる。 まず、$u$と$v$を不定元とし、 次の $(l+m-2n+2)\cross(l+m-2+2)$ 行列 $W$ を作る。

$W=$(9)

この行列の第 2 列以下に対し完全ピボッティング Gauss 消去法で列を消去したとき、ずっと消去を受け続けた行が最後の消去を受けた後に$(H(u, v),$ $rl+m-n$ ’. .. ,$r\mathit{0}$)(10)124となるとする。 このとき、ベクトル $\mathrm{r}=(\Gamma’+m-n’\ldots, r\mathit{0})$ は$||\mathrm{r}||$=\epsilon 。を満たす。 なぜなら、(1) の記号でいえば多項式 $F\delta G-G\delta F$ の係数ベクトルを表し、 しかもの線形結合のノルムを最小にするように決められたゆえ、次数$n$$\mathrm{f}_{m-,1},$$F/\overline{F}$あるいは$G/\tilde{G}$$\mathrm{f}_{0},$$\mathrm{g}_{l-,\iota},$$\cdots$

は, goの近似 GCD の最小精度になるはずだからである。 したがって、 (10) の第–要素 $H(u, v)$ は $\tilde{F}(u)+\tilde{G}(v)$ となる。
れば、 (1) により除算$\cdots,$$\mathrm{r}$$\tilde{F}(x)$と $G(x)$ が決まで最小精度 \epsilon 。の近似 GCD を決定することができる。

13.7 おわりに
本稿の詳細については論文 [5] を参照されたい。 そこでは、 近似 GCD と近接根の関係なども詳述されている。数学的観点からは、精度を固定したときの多項式因子の不定性や多変数多項式の近似因数分解の最小精度なども重要な問題であるが、論文 [4] ではこれらの値がキャンセル数で規定されている。

参考文献[1] T. Sasaki and M-T. Noda, Approximate square-free decomposition and root-finding of ill-conditioned algebraic equations. J.

. Proces., 12 (1989), 159-168.

$\mathrm{I}\mathrm{n}\mathrm{f}$[2] T. Sasaki and M. Sasaki, Analysis of accuracy decreasing in polynomial remainder sequencewith floating-point number coefficients. J.
[3] T. Sas$\mathrm{a}\mathrm{k}\mathrm{i}$. Proces., 12 (1989), 394-403.

$\mathrm{I}\mathrm{n}\mathrm{f}$, A study of approximate polynomials, I–representation and arithmetic-. Japan

J. Indus. Appl. Math., 12 (1995) (in press). (Preprint, Aug. 1993)[4] T. Sasaki, A study of approximate polynomials, II -proerties of approximate divisors -.

Preprint of Univ. Tsukuba, Dec 1994.
[5] T. Sasaki and M. Sasaki, A study of approximate polynomials, III–univariate approximate

GCD -. Preprint of Univ. Tsukuba, Feb. 1995.