数理解析研究所講究録920 巻 1995 年 115-119

115

12.
近似代数その 1近似多項式の四則演算佐々木建昭 (筑波大数学系)

12.1 はじめに
筆者は 6 年前に近似代数の概念を提唱し$[4,5]$$[1]_{\text{、}}$

共同研究者とともに近似 GCD $[2,3]$ や近似因数分解、多変数代数方程式の近似べき級数解法 $[6,7]$ などの算法を考案してきた。数値計算や応用分野では近似計算は主流をなす計算法であるが、 そこでの近似とは「正確な計算の模擬計算.」. 、すなわち 「近似は精度が高いほど良い」 というものである。 -方、 近似代数では、 多項式や有理式にノルムを定義し、 ノルムが微小な項の不定性の範囲内で代数演算を扱う。 したがって、微小項は小さいほどよいというものではなく、「この程度以下」 というように、場合に応じて規定されるべきものである。近似演算の対象となる多項式を近似多項式と呼ぶ。近似多項式の数係数は近似数である必要はなく (もちろん、 近似数であってもよいが)、ノルムが微小な項の不定性を許容するという意味である。

微小項の不定性を導入した場合、 通常の代数演算の算法を少し修正すれば事足りると思えるが、 実はそうではない。たとえば、従来の因数分解算法は最終的に$Z_{\rho}$上の因数分解に帰着されるから、係数部に $10^{-14}$ 程度の誤差が入り込む (浮動小数の計算がそうである) だけで算法は破綻してしまう。 この例が端的に示すように、 近似代数では従来の代数がそのままでは通用せず、 基礎から作り上げていかねばならない。本稿では、 第–歩として、 近似多項式の四則演算を議論する。

12.2 多項式のノルムと$O$記号

多項式 $P(x)$ の係数の絶対値のなかで最大のものを $P$ のノルムと定義し ‘ $||P||$ と表す。

116

我々は近似代数で、近似の精度として$10^{-2}$と $10^{-4}$ が区別できるような詳細な議論をしたいが、それには積 $G\cdot H$ のノルムの大きさをかなり精度よく評価することが必要である。数の大きさのオーダを表す記号として、 Landau の $O\dot{\text{記}号がよく使われるが_{、}}$ それは極限値として$0$, 有限値,をとるものと定められているので、 近似代数の議論には全く使えない。 さて、多項式
$F$

$G$

$\infty$の3値と $H$ の積をとするとき、 比 $r=||F||/(||G||\cdot||H||)$ は $F$ と $G,$ $H$ によって種々の値をとる。例外的に $r\ll 1$となることはあるが、 $r\gg 1$ となることはなく、多くの場合に嫁よ 1 の周りに分布する。 $r\ll 1$ となる場合、 積 $G\cdot H$ において組織的桁落ち (systematic cancellation) が生じたという$\circ r$の上限を $G$と $H$ に関わらない形で決めることはできるが、 それは –般に近似代数には大きすぎて使えない。 また、の値を–般の場合に精度よく決めるのは理論的に極めて難しい。そこで、多くの場合に$r$が 1 の周りに分布することに注目して、 $||G\cdot H||$ の $||G||\cdot||H||$ からのずれを$r$$\prime r$の値の分布の分散で平均的に評価することにする。 こうすれば、小さい確率で評価値が狂うことはあっても、 平均的には程良い評価値が得られる。
以下では、積 $G\cdot H$ において組織的桁落ちが生じない場合に対して、積のノルム $||G\cdot H||$ はノルムの積 $||G||$ . I $H||$ と同じ程度の大きさであるとし、 それを $O$ 記号で $||G\cdot H||=O(||G||\cdot||H||)$ と表すことにする。組織的桁落ちを考慮すると、 一般には $||G\cdot H||\leq O(||G||\cdot||H||)$ となる。 上述したように、$O$$\mathit{0}$

記号は比$r$の分布の分散と解釈するから、$G$と $H$ の項数に依存することになる。 このように記号を使うことにより、 以下の議論は極めて簡素なものとなる。

12.3 近似の精度$\mathrm{a}\mathrm{c}\mathrm{c}$記号であるとき、 $F$ の精度は多項式$F$の数係数が誤差を含み、誤差の上限が多項式$F$と $G$ が $||F-^{c}||\leq\epsilon$ を満たすとき、 $F$ と $G$ は精度$||F-c||\leq\in\ll 1$

多項式精度$\epsilon$$F_{1},$$F_{r}$$\ldots,$に代数演算$\mathrm{O}\mathrm{p}$$\epsilon\ll 1$$\Leftrightarrow$$\epsilon$$\epsilon$であるという。

で等しいといい、 次のように表す。

$F=G$ (accを施し、その結果が精度$\epsilon$$\in$)

で $G$ に等しいとき、近似演算$\mathrm{O}\mathrm{p}$で $G$ になるといい、次のように表す。

$\mathrm{O}\mathrm{p}(F\iota, \ldots, F_{r})=c$$(\mathrm{a}\mathrm{c}\mathrm{c} \epsilon)$

12.4 従来の除算算法の破綻
多項式$G$と $H$ の精度がそれぞれ$\epsilon c$と $6H$ のとき、和 $G+H$ の精度は $\max\{\epsilon G, 6H\}$ となり、は117

積$G\mathrm{x}H$の精度は $\max\{||c||\epsilon H, ||H||\epsilon c.\}$ となる。和と積の演算は従来の算法で行なえばよい。

ところが、 従来の除算算法は近似多項式に対しては破綻する場合がある。 たとえば、 除多項式 $G$

はノルムが 1 で主係数が小さく、全ての係数に$O(\epsilon)$の誤差が含まれているとしよう。

を $1\mathrm{c}(G)=\eta\ll 1$ とすれば、 主係数の精度は相対的に算算法は$G$$O(\epsilon/\eta)$$|1\mathrm{c}(G)|\cdot|1\mathrm{C}(H)|=0$(acc$\epsilon$の主係数しかない。 $F/G$ に対する従来の除の主係数で $F$ の高次項を割って消去していくものゆえ、合、結果はたちまち誤差だらけとなる。 さらに、 $F=GH$$G$(acc$\epsilon$の精度が不足している場$1\mathrm{c}(G)$) で、$\epsilon<|1\mathrm{c}(G)|,$ $|1\mathrm{C}(H)|\ll 1$) の場合、 $\deg(F)<\deg(G)+\deg(H)$ となってしまう,

これを次数低下 (degree-decreasing) と呼ぶ。 このような場合、従来の除算算法は全く破綻する。

12.5 キャンセル数 (cancel number)
数ベクトル$\mathrm{u}=$$(u_{1}$,$\cdot$..,に対し、 ノルム$u_{n})$を次式で定義する。

$||\mathrm{u}||$$|| \mathrm{u}||=\mathrm{d}\mathrm{e}\mathrm{i}\max\{|u_{1}|, \cdots, |u_{n}|\}$$n$次元の数ベクトル$\mathrm{u}_{1},$$\ldots,$

ただし$\mathrm{u}_{m\text{、}}$$m\leq n_{\text{、}}$

が数$c_{1},$Clul $+\cdots+c_{m}\mathrm{u}_{m}=(0, \ldots, 0)$$\ldots,$に対し次式を満たすとする。

$c_{m}$(acc$\epsilon$),$\{$$\max\{|c_{1}|, \cdots, |c_{m}|\}=1/\max\{||\mathrm{u}_{1}||, \cdots, ||\mathrm{u}_{m}||\}$

上式を満たすcanc$\epsilon$$(\mathrm{u}\mathrm{l}, \ldots, \mathrm{u}_{m})$のうち、値が最小のものを$\mathrm{u}_{1},$$\ldots,$のキャンセル数 (cancel number) と名付け、$\mathrm{u}_{m}$と表す。上式は近似線形従属関係である。実際、

式が $\epsilon=0$ に対して成立することはないが、$\mathrm{u}_{1},$$\ldots,$.

$\mathrm{u}_{1},$$\ldots,$$\mathrm{u}_{m}$が線形独立な場合、上が微小項を除いて線形従属である場合、 そ$\mathrm{u}_{m}$の微小項の精度で近似的に線形従属関係が成立する。 キャンセル数については次の定理が成立する。
定理 125.1.

する。

$U$$m\leq n$とし、$U$を$n$次元の数ベクトル$\mathrm{u}_{1},$$\ldots,$$\mathrm{u}_{m}$を行とする $m\cross n$ の数値行列とに対し完全ピボッティング Gauss 消去法により列消去を行なった結果を $U’$ とすると、$u_{22}’u\prime 12$$U’=(u_{11}’0$$u_{23}’..$$u_{mn}u_{1n}’u_{2\mathfrak{n}}’,\cdot.\cdot)$.

.

.
$\cdot$$\cdot$$u_{mm}’..$と表される。 このとき canccanc$(\mathrm{u}_{1}, \cdots, \mathrm{u}_{m})$は次式で与えられる。

$( \mathrm{u}\mathrm{l}, \cdots, \mathrm{u}_{m})=\frac{O(||m\mathrm{t}\mathrm{h}\mathrm{r}\mathrm{o}\mathrm{W}.\circ \mathrm{f}U’||)}{\max\{||\mathrm{u}_{1}||,..,||\mathrm{u}m||\}}$.

口

118

12.6 近似多項式の除算算法
多項式 $F,$ $G,$ $H$ の間には $F=GH$ (acc$\epsilon$),$\epsilon\ll 1$なる関係が成立するとし、 $F$ と $G$ を与えて商を計算することを考える。 $F,$ $G,$ $H$ を以下のように表す。

$H$$F(X)=f_{l}xf\iota_{+\iota x}l-1-1+\cdots+f_{0}$,$G(x)=g_{m}x^{m}+g_{m-}1^{X}m-1+\cdots+g\mathrm{o}$ ,$\{$$H(x)=h_{\mathfrak{n}}x^{n}+h_{\mathfrak{n}-1}x^{\mathfrak{n}-\iota}+\cdots+h_{0}$.

本稿では簡単のため、 $F,$ $G,$ $H$ は 1 変数多項式で、 $\deg(F)=\deg(G)+\deg(H)$ のとき (すなわち次数低下が生じないとき) のみを扱うが、 この制限は本質的なものではない。
$n+1$ 個口$l$

次元数ベクトル$\mathrm{g}_{n},$$\cdots,$$\mathrm{g}_{0}$を次のように定める。

$\mathrm{g}_{n}$$=$$(g_{m}, ..., g_{\mathrm{O}}, 0,0, \ldots, 0)$$\mathrm{g}_{\mathfrak{n}-1}$$=$( $0,$$\mathrm{g}_{0}$$=$( $0,0,$$g_{m},$, go,$\ldots$

$0,$

$0$

$\ldots,$)$\{$$\mathrm{f}=(f\downarrow, fi-1, \cdots, f0)$とおくと、 関係式 $F=GH$ (acc$\mathrm{f}-h_{n}\mathrm{g}_{n}$これ\sim 次元ベクトル$\mathrm{f},$$\mathrm{g}_{\mathfrak{n}},$$\cdots,$–.

$\mathrm{g}_{0}$定理 1261. 関係式 $F=GH$ (acc性$\Delta H$$\Delta H)$

は(acc..

) を満たすものである。)

定理 1262. $n+2$ 個の$U=(\mathrm{f}, \mathrm{g}_{n}, \cdots, \mathrm{g}_{0})^{T}$

消去法により$U$.

$U$

$l$

$g_{m},$$\epsilon$$\ldots$, go )) は次のように表せる。

$-h_{\mathrm{O}}\mathrm{g}_{0}=(0,0, \ldots, 0)$(acc$\epsilon$)に対する近似線形従属関係であり、 次の定理が成立する。
$\epsilon$) において、 $||G||=1$ として $G$ を固定した場合、 $H$ の不定$||\Delta H||\leq\epsilon/\mathrm{c}\mathrm{a}\mathrm{n}\mathrm{c}(\mathrm{g}_{\mathfrak{n}}, \cdots, \mathrm{g}_{0})$$\epsilon$$0,$$\ldots,$を満たす。 ( $H$ の不定性$\Delta H$とは $F=GH=G\cdot(H+$$\square$

次品数ベクトル$\mathrm{f},$$\mathrm{g}_{n},$$\cdots,$の第 2 行以下 (すなわち$\mathrm{g}_{0}$$\mathrm{g}_{\mathfrak{n}},$の列消去を行なえば、 $F=GH$ (acc$\epsilon$を行とする $(n+2)\mathrm{x}l$ 行列を$\cdots,$$\mathrm{g}_{0}$$U$とする:) を使い、 完全ピボッティング Gauss) を満たす $H$ を計算できる。

口12.7 おわりに上記の定理の証明は論文 [8] を参照されたい。同論文は、 1 変数のみならず多変数多項式の除算も扱い、 また次数低下が生じる場合の算法も与えている。 さらに、剰余のある除算 $F=GH+R$ (accも扱っている。 この場合も、 商と剰余の不定性はキャンセル数で規定できる。

$\epsilon$)

119

除算における不定性のみならず、因数分解や GCD などの代数演算においても、因子の不定性の上限や演算の最小精度が問題になるが、 それらもキャンセル数で規定できることを論文 [9] は示している。

参考文献[1] 佐々木建昭 : 近似的代数計算、 数理研講究録、 Vol. 676 (1988), 307-319.
[2] 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}$[3] T. Sasaki and M. Sasaki, Analysis of accuracy decreasing in polynomial remainder sequencewith floating-point number coefficients. J.
[4] T. Sas$\mathrm{a}\mathrm{k}\mathrm{i}$. Proces., 12 (1989), 394-403.

$\mathrm{I}\mathrm{n}\mathrm{f}$, M. Suzuki, M. Kol\’ar and M. sas$\mathrm{a}\mathrm{k}\mathrm{i}$, Approximate factorization of multivariate

polynomials and absolute irreducibility testing. Japan J. Indus. Appl. Math., 8 (1991), 357-375.
[5] T. Sasaki, T. Saito and T. Hilano, Analysis of approximate factorization algorithm I. JapanJ. Indus. Appl. Math., 9 (1992), 351-368.
[6] T. Sasaki and F. Kako, Solving multivariate algebraic equation by Hensel construction.
Preprint of Univ. Tsukuba and Nara Women’s Univ., Jan. 1993, 22 pages (submitted).

[7] T. Sas$\mathrm{a}\mathrm{k}\mathrm{i}$, T. Kitamoto and F. Kako, Error analysis of approximate power series roots ofmultivariate algebraic equation. Preprint of Univ. Tsukuba and Nara Women’s Univ., March
1994, 30 pages (submitted).

[8] T. Sasaki, A study of approximate polynomials, I-representation and arithmetic-. Japan

J. Indus. Appl. Math., 12 (1995) (in press).
[9] T. Sasaki, A study of approximate polynomials, II–properties of approximate divisors -.

Preprint of Univ. Tsukuba, Dec. 1994.