数理解析研究所講究録
第 1572 巻 2007 年 82-9382

任意の収束次数をもつ記号的 Newton 法の同時反復公式
照井章 *AKIRA TERUI筑波大学大学院数理物質科学研究科
GRADUATE SCHOOL OF PURE AND APPLIED SCIENCE, UNIVERSITY OF TSUKUBA

Abstract
本稿では, 多変数代数方程式のべき級数根の算法として知られる記号的 Newton 法について, すべてのべき級数根を同時に計算する 2 つの新たな同時反復公式を与える. これらの同時反復公式は, 1 変数代数
方程式の数値算法から得られたものである:1 つは Aberth の公式に基いたもので 3 次収束し, もう 1 つはPad\’e 近似を用いたもので, 任意の収束次数をもつ. 本稿では, 新たな同時反復公式のべき級数根としての収束次数が, もとの数値解法での収束次数に等しいことを示した上で, 同時反復公式の計算量の見積もりと計算例を示す.

1

はじめにを複素数体 上の多変数多項式とし, 主変数 に関してモニックで, 従変数}こ複素数をそれぞれ代入した 1 変数多項式 $F(x, s_{1}, \ldots, s_{l})$ は無平方であるとする. このとき, 代数$F(x,u_{1},\ldots, u_{l})=0$ の, 主変数
方程式に関する根は, 従変数の代数関数となるが, 本稿では, この根をのべき級数 $x=\chi(u_{1}, \ldots, u\iota)$ (以下 「べき級数根」 という) の形で求めることを考える.
$F(x, u_{1}, \ldots, u_{t})$$s_{1}\ldots,$$\mathbb{C}$$x$$\ldots,$$u\iota$$s\iota$$x$$u_{1},$$u_{1},$$\ldots,$$u_{1},$ $\ldots,u\iota$$u_{l}$

以下では, $(u_{1}, \ldots, u_{t})$ および $(s_{1}, \ldots, s_{t})$ をそれぞれ $u$ および

$s$

で表す.

記号的 Newton 法 ([8], [9]) は, このようなべき級数根の算法の一つとして知られるものであるが, その名称が示すとおり, その反復公式は, 1 変数代数方程式の数値解法からもたらされたものである. 1 変数代数方
程式の数値解法には, 1 つの根のみを求める単独反復公式と, すべての根を同時に求める同時反復公式があるが, 1 変数代数方程式の数値解法の歴史は長 \langle [11], 単独反復公式, 同時反復公式ともに, 異なる収束次数をもっさまざまな算法が提案されている.
一方, 記号的 Newton 法においては, 単独反復公式として, 数値解法のいわゆる Newton 法に対応する 2 次
収束の反復公式や, Nourein 法 [10] に対応する任意次数の反復公式 [7] などが知られている. 同時反復公式
としては, Durand-Kerner 法 ([3], [6]) に対応する 2 次収束の反復公式が知られているが, 著者の知る限り,
収束次数が 2 次を超える同時反復公式で文献に掲載されているものは見つかっていない.
本稿では, 記号的 Newton 法の同時反復公式で収束次数が 2 次を超える, 2 つの新たな反復公式を与える.
1 つは数値解法の Aberth の公式に対応するもので, 3 次収束するものであり, もう 1 つは Pad\’e 近似を用いたもので, 数値解法としては櫻井ら ([12], [15]) によって提案されたものであるが, 任意の収束次数をもつ.
本稿では, これら数値解法における反復公式が, 記号的 Newton 法にも直接利用可能であることを示す. さらに, 収束次数に関して, 記号的 Newton 法におけるべき級数としての収束次数が, もとの数値解法の収束次数に一致することを示す.

$r_{t\cdot ruiu\cdot th}$tsukuba. ac. jp

83
本稿では以下の内容を述べる. 第 2 章では, 数値解法と記号的 Newton 法の反復公式について, 本稿で引用する反復公式を復習する. 第 3 章では, 記号的 Newton 法の 3 次収束の同時反復公式を与え, 第 4 章では,同じく任意の収束次数をもつ同時反復公式を与える. 第 5 章では, 実際の算法について議論し, 同時反復公式の計算量の見積もりを与え, 第 6 章では計算例を示す.

2

記号的 Newton 法
本節では, 数値解法, 記号的 Newton 法双方における反復公式と, それらの関連について復習する.

2.1

数値解法における反復公式

複素数体上のモニックな 1 変数多項式 $P(x)$ を次式で定義する.
$P(x)=x^{n}+a_{n-1}x^{n-1}+\cdots+a_{0}x^{0}$,$a_{n-1},$$\ldots,a_{0}\in \mathbb{C}$.

Newton 法は $P(x)$ の 1 つの零点を計算する近似解法としてよく知られている. $P(x)$ の零点に対し,
第$k$

回目の反復による近似値とするとき, 次の近似値$z^{(k+1)}$$z^{(k)}$をは以下の反復公式$z^{(k+1)}=z^{(k)}- \frac{P(z^{(k)})}{P(z^{(k)})}$,(1)で与えられ, 近似値は 2 次収束することが知られている. 同様の解法で, 3 次収束する反復公式$z^{(k+1)}=z^{(k)}- \frac{P(z^{(k)})P’(z^{(k)})}{\{P’(z^{(k)})\}^{2}-\frac{1\wedge}{2}P(z^{(k)})P’’(z^{(k)})}$.

(2)

は Halley 法として知られる.

これらの他にも, さまざまな収束次数をもつ反復公式が提案されており, その中でも Nourein 法は [10] は任意の収束次数をもつことが知られている.
一方, $P(x)$ のすべての零点を同時に計算する反復公式を同時反復公式という. 同時反復公式としては, 2次収束の Durand-Kerner 法 ([3], [6]), 3 次収束の Aberth 法 [1] などがよく知られている. $P(x)$ の零点の第$k$回目の近似値$z_{n}^{(k)}$$z_{1}^{(k)},$$\ldots,$に対し,$Q_{k}(x)= \prod_{i=1}^{n}(x-z_{i}^{(k)})$とおく. そして, $i=1,$$\ldots,$$n$に対し, Durand-Kerner 法の反復公式は$z_{i}^{(k+1)}=z_{i}^{(k)}- \frac{P(z_{i}^{(k)})}{Q_{k}(z_{1}^{(k)})}$,(3)

Aberth 法の反復公式は$z^{\dot{(}k+1)}=z_{i}^{(k)}- \frac{P(z_{i}^{(k)})Q_{k}’(z_{i}^{(k)})}{P’(z_{i}^{(k)})Q_{k}’(z_{i}^{(k)})-\frac{1}{2}P(z_{i}^{(k)})Q_{k}’’(z_{i}^{(k)})}$

で, それぞれ与えられる.

(4)

84
2.2

記号的 Newton 法における反復公式

上の多変数多項式とし, 主変数 に関してモニックで, 点に対し, $F(x, s)$ は無平方であるとする. $\deg_{x}F=n$ とし, $S=(u_{1}-s_{1}, \ldots, u\iota-s_{l})$ を多項式イデアルとす$F(x, u)$ を複素数体$\mathbb{C}$$s=(s_{1}, \ldots, s_{I})\in \mathbb{C}^{l}$$x$

は, それぞれ $F$ の に関する 1 階, 2 階, . . の偏導関数を表す.
従変数 $u$ に関する複素数体 上の形式的べき級数環をで表す. 本稿では, 代数方程式 $F(x, u)=0$

る. $F’(x, u),$ $F”(x, u),$$x$$\ldots$$\cdot$$\mathbb{C}$$\mathbb{C}[[u]]$の $x$ に関するべき級数根 $x=\chi(u)\in \mathbb{C}[[u]]$ を求めるものとする.

記号的 Newton 法の反復公式は, 数値解法の反復公式に対応するもので, 数値解法の場合と同様, 1 つのべき級数のみを計算する単独反復公式と, す
べてのべき級数を同時に計算する同時反復公式がある.
まず, 単独反復公式を示す. 1 変数代数方程式 $F(x, s_{1}, \ldots, s_{l})=0$ の 1 つの根を $x=x^{(0)}\in \mathbb{C}$ とすると,
は次式をみたす.

$x^{(0)}$$F(\chi^{(0)}, u)\equiv 0$

べき級数根 $x=\chi(u)$ に対し, 第

$k$

mod

$S$

.

回目の反復による近似根を $\chi^{(k)}(u)$ とするとき, 次のステップの近似根は, 異なる収束次数に対し, それぞれ以下の反復公式により与えられる.
1 次収束の反復公式には$\chi^{(k+1)}(u)$$x^{(k+1)} arrow x^{(k)}-\frac{F(\chi^{(k)},u)}{F(\chi^{(0)},\epsilon)}$mod $S^{k+2}$(5)があり, $F(\chi^{(k+1)}, u)\equiv 0$ mod $S^{k+2}$ をみたす. 一方, 2 次収束, 3 次収束の反復公式としては, それぞれ$x^{(k+1)} arrow\chi^{(k)}-\frac{F(\chi^{(k)}u)}{F(\chi^{(k)}’,u)}$mod$S^{2^{k1}}\perp$,(6)$x^{(k+1)} arrow x^{(k)}-\frac{F(\chi^{(k)},u)F’(\chi^{(k)},u)}{\{F’(\chi^{(k)},u)\}^{2}-\frac{1}{2}F(\chi^{(k)},u)F’(\chi^{(k)},u)}$$mod S^{3^{k+1}}$がある. 式 (6) は $F(\chi^{(k+1)}, u)\equiv 0$,(7)

mod $S^{k+2}$ を, 式 (7) は $F(\chi^{(k+1)}, u)\equiv 0$ modをそれぞれみたす. 式 (6), (7) は, それぞれ数値解法における反復公式 (1), (2) に対応するものである. 式 (7) は, 数値解法
における Nourein 法 [10] に対応するものとして, Kitamoto [7] によって与えられた任意の収束次数をもっ$S^{3^{k+1}}$

反復公式の一例であることを付記しておく.

次に, 同時反復公式を示す. 1 変数代数方程式 $F(x, s)=0$ の根を $x=\chi_{1}^{(0)},$$x_{n}^{(0)}$$x_{1}^{(0)},$$\ldots,$$\chi_{n}^{(0)}\in \mathbb{C}$$\ldots,$とすると,は次式をみたす.
$F(x,u)\equiv(x-\chi_{1}^{(0)})\cdots(x-\chi_{n}^{(0)})$

べき級数根 $x=\chi_{i}(u)(i=1, \ldots, n)$ に対し, 第

$k$

mod

$S$

.

回目の反復による近似根をそれぞれ$\overline{Q}_{k}(x,u)=(x-\chi_{1}^{(k)}(u))\cdots(x-\chi_{\mathfrak{n}}^{(k)}(u))$$\chi_{i}^{(k)}(u)$

とし,
(8)

とおく. このとき, 次のステップの近似根 $\chi_{i}^{(k+1)}(u)$ は, 具なる収束次数に対し, それぞれ以下の反復公式により与えられる.

1 次収束の反復公式には$x_{i}^{(k+1)} arrow x_{i}^{(k)}-\frac{F(\chi_{i}^{(k)},u)}{Q_{0}(\chi_{i}^{(0)},u)}$

mod $S^{k+2}$(9)があり, $F(\chi_{i}^{(k+1)}, u)\equiv 0$ mod $S^{k+2}$ をみだす. 一方, 2 次収束の反復公式としては$x_{i}^{(k+1)} arrow x_{i}^{(k)}-\frac{F(\chi_{i}^{(k)},u)}{\overline{Q}_{k}(x!^{k)},u)}$があり, $p(x!^{k+1)}, u)\equiv 0$ mod
である [7].

$S^{2^{k+1}}$

mod$S^{2^{k+1}}$(10)をみたす. 式 (10) は数値解法における反復公式 (3) に対応するもの

85
33 次収束の同時反復公式
本節では, 数値解法における Aberth 法 (4) に対応する記号的 Newton 法の同時反復公式 (Algorithm 1)を与える.
$InPut:Algorithm1$.

.
$\bullet$Aberth 法}-\acute 対応する記号的 Newton 法の$F(x,u)$ : べき級数根 $\chi_{1}(u),$$\ldots,$$\chi_{n}(u)$$\Pi\overline{p}$時反復公式をもつ入力多項式で, 次式をみたすもの$F(x, u)=(x-\chi_{1}(u))\cdots(x-\chi_{n}(u))$$S=(u_{1}-s_{1}, \ldots, u\iota-s_{l})$$\{\chi_{1}^{(k)}(u), \ldots, \chi_{n}^{(k)}(u)\}$,: 多項式イデアル,

: 第

$k$

回目の反復で計算されたべき級数根$F(\chi_{i}^{(k)},u)\equiv 0$

mod$\chi_{1}(u),$$\ldots,$$\chi_{n}(u)$で,$S^{3^{k}}$をみたすものの集まり;

Output:$\{\chi_{1}^{(k+1)}(u), \ldots, \chi_{n}^{(k+1)}(u)\}$: 第 $k+1$ 回目の反復で計算されるべき級数根$\chi_{1}(u),$$\ldots$,$\chi_{n}(u)$

の集

;

(11)

まり;

for $i=1$ to$n$

式 (8) により
$x_{i}^{(k+1)}$

do$\overline{Q}_{k}(x, u)$を計算する:

を次式により計算する:$x!^{k+1)} arrow x!^{k)}-F(\chi_{i}^{(k)},u)\overline{Q}_{k}(\chi_{i}^{(k)},u)-\frac{\ovalbox{\tt\small REJECT}_{1}}{2}F(x!^{k)}F(\chi_{i}^{(k)},u)\cdot\overline{Q}_{k}’(\chi_{i}^{(k.)},u)u)\overline{Q}_{k}(\chi_{i}^{(k)},u)$mod$S^{3^{k+1}}$

end for;return$\{\chi_{1}^{(k+1)}(u), \ldots , \chi_{n}^{(k+1)}(u)\}$.

$I$

Algorithm 1 が 3 次収束であることが, 次の定理によって示される.
定理 1$F(x, u),$ $\epsilon=(s_{1)}\ldots, s_{l})\in \mathbb{C}^{l},$ $S=(u_{1}-s_{1}, \ldots, u_{1}-s_{l})$ を上記の通りとする. $F(x, u)=0$ のべき級数を$\chi_{1}(u),$$\ldots,$$\chi_{n}(u)\in \mathbb{C}[[u]]$とし,$F(x, u)=(x-\chi_{1}(u))\cdots(x-\chi_{n}(u))$

をみたすものとする. $x_{i}^{(0)}\in \mathbb{C}(i=1, \ldots, n)$ をそれぞれべき級数$F(x, u)\equiv(x-\chi_{1}^{(0)})\cdots(x-\chi_{n}^{(0)})$をみたすものとする. $k=0,1,2,$$\ldots$$F(x!^{k)},u)\equiv 0$

証明 Terui [14] を参照.

$\blacksquare$modの ‘初期値” とし,$S$に対し, $\chi_{i}^{(k+1)}(u)$ を, それぞれ Algorithm 1 によって与えられるの第 $k+1$ ステップの近似根とする. このとき, $k=0,1,2,$

をみたす.

$\chi_{i}(u)$$\ldots$

mod(12)$\chi_{i}(u)$に対し, $x!^{k)}(u)$ は$S^{3^{k}}$

(13)

86
4

任意の収束次数をもつ同時反復公式
本節では, Pad\’e 近似を用いることにより, 任意の収束次数をもつ記号的 Newton 法の同時反復公式を与える.

まず, 1 変数多項式の Pad\’e 近似に関する定義を示す.

定義 2

上の 1 変数多項式とし, $P(x),$ $Q(x)$ の次数をそれぞれ $M,$ $N$ とする.
$P(x)$ と $Q(x)$ に対し, 有理関数 $r_{M,N}=P*xxi$ を定める.
に対し, $Q(x_{0})\neq 0$ とし, $F(x)$ を $x=x_{0}$ に$P(x),$ $Q(x)$ を互いに素な複素数体$\mathbb{C}$$x_{0}\in \mathbb{C}$おける Tylor 展開$F(x)=a_{0}+a_{1}(x-x_{0})+a_{2}(x-x_{0})^{2}+\cdots$とする. $r_{M,N}$ が$F(x)Q(x)\equiv P(x)$mod $(x-x_{0})^{M+N+1}$ ,をみたすとき, $r_{M,N}$ を $x=x_{0}$ における $F(x)$ の $[M/N]$ -Pad\’e 近似という. I
上記の定義は, べき級数に対して以下のように拡張できる.
定義 3$P(x, u),$ $Q(x, u)\in \mathbb{C}[x, u]$ を互いに素な多項式とし, $P,$ $Q$ の $x$ に関する次数をそれぞれ $M,$ $N$ とする.
$\chi(u)\in \mathbb{C}[[u]]$を $u$ に関する (有限次もしくは無限次の) べき級数とし, $Q(\chi(u), u)\neq 0$ をみたすものとする. $F(x, u)$ を $x=\chi(u)$ における Taylor 展開$F(x,u)=a_{0}+a_{1}(x-\chi(u))+a_{2}(x-\chi(u))^{2}+\cdots$とする. $r_{M,N}$ が$F(x)Q(x)\equiv P(x)$mod $(x-\chi(u))^{M+N+1}$ ,をみたすとき, $r_{M,N}$ を $x=\chi(u)$ における $F(x)$ の $[M/N]$ -Pad\’e 近似という. I$F(x, u),$ $s=(s_{1}, \ldots, s\iota)\in \mathbb{C}^{l},$ $s=(u_{1}-s_{1}, \ldots, u\iota-s_{t})$ を上記の通りとする. $F(x,u)=0$ のべき級数

根を $\chi_{1}(u),$$\ldots,$$\chi_{n}(u)\in \mathbb{C}[[u]]$とし,$F(x,u)=(x-\chi_{1}(u))\cdots(x-\chi_{n}(u))$

をみたすものとする. また,$Q_{i}^{(k)}(x,u)= \prod_{l=1,\neq i}^{n}(x-\chi_{i}^{(k)}(u))$(14)$P_{i}^{(k)}(x, u)= \frac{F(x,u)}{Q_{1}^{(k)}(x,u)}$(15)

とおき, 有理関数を定義した上で, Pad\’e 近似を用いる同時反復公式を Algorithm 2 に示す.に述べられている Pad\’e 近似の諸性質につ
以下では, Algorithm 2 の正当性と収束次数を示す. 補題$4\triangleleft$

いては Sakurai et al. [12] を参照. それらの駈明中, 数値を変数で表した部分は打ち切りべき級数で置き換えが可能であることを付記しておく. 以下, べき級数根
級数を$\overline{\chi}_{i}$で表す.

$\chi_{i}$を (有限次の) 任意の次数までで打ち切ったべき87
Algorithm 2
Input:.
.

$\bullet$$P$$F(x, u)$ :d\’e 近似を用いた記号的 Newton 法の同時反復公式

べき級数根$\chi_{1}(u),$$\ldots$,$\chi_{n}(u)$をもつ入力多項式で, 次式をみたすもの$F(x,u)=(x-\chi_{1}(u))\cdots(x-\chi_{n}(u))$$S=(u_{1}-s_{1}, \ldots, u\iota-s_{l})$$\{\chi_{1}^{(k)}(u), \ldots,\chi_{n}^{(k)}(u)\}$,: 多項式イデアル,

: 第

$k$

回目の反復で計算されたべき級数根$F(\chi_{i}^{(k)},u)\equiv 0$$\chi_{1}(u),$$\ldots,$$\chi_{n}(u)$で,mod $s^{(m+2)^{k}}$をみたすものの集まり;

Output:$\{\chi_{1}^{(k+1)}(u), |\chi_{\mathfrak{n}}^{(k+1)}(u)\}$;

第 $k+1$ 回目の反復で計算されるべき級数根 $\chi_{1}(u),$$\ldots,$$\chi_{n}(u)$の集

まりfor $i=1$ to

$n$

do

式 (14), (15) により $P_{i}^{(k)}(x, u)$ を求め, $P_{i}^{(k)}(x, u)$ の $x=\chi_{i}^{(k)}(u)$ における $[1/m-1]$ -Pad\’e 近似の分子$R_{1}^{(k)}(x, u)$$x$を計算する;

に関する 1 次方程式 $R_{i}^{(k)}(x, u)=0$ を解き, 解の $S^{(m+2)^{k+1}}$ を法とする剰余を新たなべき級数根$\chi_{1}^{(k+1)}(u)$とする;

end for;.
$\iota\ovalbox{\tt\small
REJECT}$$returnn\{x_{1}^{(k+1)}(u), \ldots, \chi_{n}^{(k+1)}(u)\}$.

補題 4 ([12, Lemma. 3])$F(\overline{\chi}_{i}, u)\neq 0$とし, $G_{m}(x, u)$ を$x=\overline{\chi}_{i}(u)$において $1/F(x, u)$ を$x$に関して $m$ 次まで展開した (打ち切り)

Taylor 展開とする:$G_{m}(x, u)= \sum_{i=0}^{m}(\frac{1}{i!})\{(\frac{1}{F})^{(i)}(\overline{\chi}_{i})\}(x-\overline{\chi}_{i})^{i}$

このとき, $1/G_{m}(x, u)$ は$x=\overline{\chi}_{i}(u)$.

における $F(x, u)$ の $x$ に関する $[O/m]$ -Pi\’e 近似である.

この性質は, Pad\’e 近似の “reciprocal covariance” と呼ばれるものである. 2,
$[$

$P$

補題 5([12, Lemma 4])とし, $P_{i}^{(k)}(x, u)$ を式 (15) で定義されるものとする. このとき,$F(\overline{\chi}_{i}, u)\neq 0$の $x$に関する $[1/m-1]$ -Padd 近似の零点$\hat{x}$:は$\hat{\chi}_{i}=\overline{\chi}_{i}+m\{\frac{(\frac{1}{P_{i}^{(k)}(x,u)})^{(m-1)}1_{x=\dot{\overline{\chi}}}}{(\frac{1}{P_{1}^{(k)}(x,u)})^{(m)}1_{x=\overline{\chi}}}\}$

で表される.

$\blacksquare$,$\blacksquare$. 118 .
$]$

$x=\overline{\chi}_{i}(u)$における $F(x, u)$

88
補題 6 ([12, Lemma 5])$F(x, u)$ が$F(x, u)= \frac{x-\chi_{l}(u)}{\varphi(x)}$と表されるものとする. このとき,$x=\overline{\chi}_{i}$,$\varphi(\overline{\chi}_{i}(u))\neq 0$における $F(x, u)$ の

mod$\hat{\chi}_{i}\equiv\overline{\chi}_{i}+\epsilon_{1}-\frac{\varphi^{(m)}(\overline{\chi}_{i})}{m!\varphi(\overline{\chi}_{i})}(\epsilon_{i})^{m+1}$$x$に関する $[1/m-1]$ -Pad\’e 近似の零点$(\epsilon_{i})^{m+2}$,$\hat{\chi}_{i}$は$\epsilon_{i}=\chi_{i}-\overline{\chi}_{i}$をみたす. I定理 7
$F(x, u),$ $\epsilon=(s_{1}, \ldots, s\iota)\in \mathbb{C}^{l},$ $S=(u_{1}-s_{1}, \ldots, u\iota-s_{l})$ を上記の通りとする.
$\chi_{1}(u),$$\ldots,$$\chi_{n}(u)\in \mathbb{C}[[u]]$$F(x, u)=0$ のべき級数をとし,$F(x,u)=(x-\chi_{1}(u))\cdots(x-\chi_{n}(u))$

をみたすものとする. $x!^{0)}\in \mathbb{C}(i=1, \ldots, n)$ をそれぞれべき級数根$F(x,u)\equiv(x-\chi_{1}^{(0)})\cdots(x-\chi_{n}^{(0)})$をみたすものとする. $k=0,1,2,$$\ldots$, に対し,$\chi_{i}^{(k+1)}(u)$の ‘物期値” とし,

mod ,

(16)

$S$

を, それぞれ Algorithm 2 によって与えられるの第 $k+1$ ステップの近似根とする. このとき, $k=0,1,2,$$F(\chi_{i}^{(k)},u)\equiv 0$$\chi_{i}(u)$$\ldots$

mod

に対し,

$\chi_{i}^{(k)}(u)$$\chi_{i}(u)$

は

(17)

$S^{(m+2)^{k}}$をみたす.

証明 Terui [14] を参照. 1

定理 7 より, Algorithm 2 の収束次数は $m+2$ であることがわかる. $m=1$ の場合は Algorithm 1 の収束次数に等しい.

5

実際の算法と計算量の見積もり

本節では, Algorithm 2 の実際の算法について議論するとともに, Algorithm 1 および 2 における計算量の見積もりを行う.
本稿の計算量解析においては, 複素数体上の 次 1 変数多項式の乗算に要する係数演算 (加減乗除) の計
算量を $M(n)$ で表す (この表記は von zur Gathen and Gerhard [4, Definition 826] によるものと同じもの
$n$

である)

. さらに, 従変数に関するべき級数環を係数とする 1 変数多項式環

においては, べき級
数どうしの加減乗除の計算量は乗除算が計算量全体の大半を占めるため, 乗除算の回数のみを計算する. 以$u$$\mathbb{C}[[u]][x]$下では, まず Algorithm 2 における計算量を見積もり, それが Algorithm 1 に適用可能であることを示す.

Algorithm 2 において, 1 次方程式 $R_{i}^{(k)}(x, u)=0$ を$x$について解くが, その解は, 補題 5 により,$\overline{\chi}_{i}+m\{\frac{(\frac{Q_{1}^{(k)}(x,u)}{F(x,u)})^{(m-1)}1_{x\approx\chi^{(k)}(u)}}{(\frac{Q_{i}^{(k)}(x,u)}{F(x,u)})^{(m)}1_{x\simeq x!^{k)}(u)}}\}$

(18)

89
のように表され, これにより, べき級数を計算する. そこで, まず$\chi_{i}^{(k+1)}(u)$(19)$\overline{R}_{i}^{(k)}(x, u)=(\frac{Q_{i}^{(k)}(x)u)}{F(x,u)})^{(m-1)}/(\frac{Q_{i}^{(k)}(x)u)}{F(x,u)})^{(m)}$の計算に現われる演算回数を見積もり, ついで, 式 (19) の変数
き級数除算を計算するのに必要な演算回数を見積もる.
最初に,$\overline{R}_{i}^{(k)}(\chi_{i}^{(k)}(u), u)$であることを示し,[14] を参照) .

$x$に $\chi_{i}^{(k)}(u)$ を代入し,$\overline{R}_{i}^{(k)}(\chi_{;}^{(k)}(u), u)$のべの分子および分母がそれぞれ $F(x, u)$ および $Q_{i}^{(k)}(x, u)$ から帰納的に計算可能$\overline{R}_{i}^{(k)}(\chi_{i}^{(k)}(u), u)$の分子および分母それぞれの$\Re g_{8},(\frac{Q_{i}^{(k)}(x,u)}{F(x,u)}I^{(m)}$}しの$m=01,2,$$\ldots\}^{\vee}.*$$\theta*$$x$に関する次数を見積もる (証明は Terui子, オヤをそゎ\epsilon ゎ $N_{m},$$D_{ r\iota}$

とおく. このとき, $m\geq 1$ に対

し, $N_{m}$ と $D_{m}$ はそれぞれ次式で表される.
$N_{m}=N_{m-1}’F(x,u)-mN_{m-1}F’(x,u)$ ,ここに $F’(x, u)$ とつ.

$N_{m}’$$D_{m}=F(x,u)^{m+1}$ .

(20)はそれぞれ $x$ に関する導関数を表す. さらに $\deg_{x}N_{m}=(m+1)(n-1)$ が成り立I

命題 9
式 (19) の$\overline{R}_{i}^{(k)}(x, u)$は$\overline{R}_{i}^{(k)}(x, u)=\frac{\overline{N}_{m}}{\overline{D}_{m}}=\frac{F(x,u)\cdot N_{m-1}}{N_{m}}$で表され,$\overline{N}_{m},\overline{D}_{m}$(21)の次数はそれぞれ$\deg_{x}\overline{N}_{m}=mn+n-m$,$\deg_{x}\overline{D}_{m}=mn+n-m-1$

をみたす. 1
ここで, Algorithm 2 の第回目の反復において, 従変数 $u$ のべき級数の計算に必要な次数は $(m+2)^{k}$ であることに注意する. これにより, 第 回目の反復において, $u$ の打ち切りべき級数の 1 回の乗算に要する複素数係数の乗算回数は $O(M(m^{k}))$ と見積もることができる.
$k$

$k$

$Q_{i}^{(k)}(x, u)$の計算は,の計算には “building uP the subproduct tree” アルゴリズム [4, Algorithm 10.3] を用いる. こ$\mathbb{C}[[u]]$上で高々 $M(n)\lceil\log_{2}(n-1)\rceil$ の演算で行われる. ゆえに, $Q_{i}^{(k)}(x, u)$ の計算に必要な係数の

演算回数は

(22)

$O(M(n)\lceil\log_{2}(n-1)\rceil M(m^{k}))$と見積もることができる.
を式 (21) に代入することにより計算
次に,は, 式 (20) の筋を再帰的に計算し, $N_{m-1}$ とする. 補題 8 により, $N_{j-1}$ の に関する次数は $j(n-1)$ であるので,の計算に要する係数の演算回数は$\overline{R}_{i}^{(k)}(x, u)$$N_{m}$$x$$N_{j}$$O(M(jn)M(m^{k}))$であり, $j=1,$$\ldots,$

$m$

(23)

の範囲でこれらの和をとると$O(( \sum_{j=1}^{m}M(jn))M(m^{k}))$

(%)

90
となる.
$\overline{R}_{i}^{(k)}(x, u)$

の計算は,

$x$

に $\chi_{i}^{(k-1)}(u)$ を代入し, $u$ に関する全次数 $m^{k}$ まで計算する, 本稿では,

この代入の算法として, Horner 法のような $O(M(n))$ の算法を用いることを仮定する (代入の高速算法については, たと
えば van der Hoeven [5] を参照).
の分母および分子の に関する次数は, それぞれ $mn+n-m$ ,$\overline{R}_{i}^{(k)}(x, u)$$x$$mn+n-m-1$ (補題 9) であるので, 分母および分子の代入に要する打ち切りべき級数の乗算回数は $O(mn)$で見積もられる. ゆえに, このときの係数の演算回数は(25)$O(mnM(m^{k}))$で見積もられる. その後,$\overline{R}_{i}^{(k)}(\chi_{i}^{(k)}(u), u)$の分子を分母で割る際のべき級数除算における演算回数は$O(M(m^{k}))$

.

(26)

で見積もられる.

以上により, 式 (22) $-(26)$ から, 第 回目の反復による 1 つのべき級数根の計算に要する係数の演算回数
は, 式 (24) で見積もられることがわかる. Algorithm 2 では合計 個のべき級数根を計算するので, すべてのべき級数根の計算に要する係数の演算回数は
$k$

$n$

$O(n( \sum_{j=1}^{m}M(jn))M(m^{k}))$

.

(27)

で見積もられる. これにより, $S^{(m+2)^{k}}$ を法としてすべてのべき級数根を計算するのに必要な計算量は次の通り見積もることができる.
定理 10

定理 7 にしたがい, $S^{(m+2)^{k}}$ を法として, すべてのべき級数根を計算する際に必要な係数の演算回数は(28)$\sum_{l=1}^{k}O(n(\sum_{j=1}^{m}M(jn))M(m^{l}))$で見積もることができる.

$\blacksquare$

従変数 $u$ が 1 変数 $u$ の場合に, 多項式の乗算法として $M(n)=O(n^{2})$ をみたすような古典算法 (より効率的な算法については, たとえば van der Hoeven [5], Schost [13], およびそれらの参考文献を参照) を用いるものとすると, 計算量を以下の通り見積もることができる.
系 11

定理 7 にしたがい, $S^{(m+2)^{k}}$ を法として, すべてのべき級数根を計算するものとする. 多項式の乗算に古典算
法 $(M(n)=O(n^{2}))$ を用いた場合に必要な係数の演算回数は(29)$O(kn^{3}m^{S+2k})$で見積もることができる.
証明恥 rui [14] を参照. 1

回目までの反復回数に対する表現であるが, に関するべき級数の次数 を用いると, 以下のように表される. 収束次数 $m+2$ に対し, が $P=(m+2)^{k}$ をみたすとすると, 式 (29) は式 (29) の計算量は, 第

$k$

$u$

$P$

$P$

$O((\log_{m+2}p)n^{3}m^{3}p^{2})$

.

(30)

と表される.

Algorithm 1 においては, 式 (11) の最右項における分母, 分子それぞれの次数は, 命題 9 において $m=1$
とおいたものに等しくなるため, 計算量は Algorithm 2 の $m=1$ の場合に等しくなる.

91
6

数値例
本節では, Algorithm2 の $m=2$ (すなわち, 収束次数 4 次) の例を示す.

例1$F(x,y)\in \mathbb{R}[x,y]$を$F(x,y)=x^{3}+(10y-6)x^{2}+(-13y^{2}+11)x+7y^{3}-6$(Kit amoto , Chapter 5]) とおき, 従変数 で生成されるイデアルを $S=(y)$ とおく. ここでは,るすべてのべき級数根 $\chi_{i}(y)(i=1,2,3)$ を$\int 7$$y$mod$F(\chi_{i}(y),y)\equiv 0$

$x$

に関す

(31)

$y^{16}$をみたすように, に関して 16 次まで計算する.
まず, べき級数根の ‘初期値” $x_{i}^{(0)}\in \mathbb{C}(i=1,2,3)$ を計算する (これらはす) . $F(x,O)=x^{3}-6x^{2}+11x-6=(x-1)(x-2)(x-3)$ より,$y$$\chi_{1}^{(0)}=1$,$\chi_{2}^{(0)}=2$,$F(\chi_{i}^{(0)}, y)\equiv 0$

mod

$y$

をみた

$\chi_{3}^{(0)}=3$

とおく.

第

mod

$k$

回目の反復で計算されるべき級数根を $\chi_{1}^{(k)}(y)(i=1,2,3)$ とおく (これらは $F(\chi_{i}^{(k)}(y), y)\equiv 0$をみたす) . $k=1$ のとき, 式 (14) の, のは次式の通り求まる.

$y^{4^{k}}$$Q_{i}^{(1)}(x$$Q_{1}^{(1)}(x,y)=(x-2)(x-3)$ ,(この後, 補題 8 より, 式 (21) のを法とするべき級数根$\overline{R}^{(1)}$$Q_{2}^{(1)}(x,y)=(x-3)(x-1)$ ,$Q_{3}^{(1)}(x,y)=(x-1)(x-2)$.

が求まるが, 式が複雑なため略す) それから, 式 (18), $(I9)$ により,mod S4 が次式の通り求まる.

$\chi_{i}^{(1)}=\chi_{i}^{(0)}+3\overline{R}_{i}^{(1)}$$\chi_{1}^{(1)}(y)=1-5y+94y^{2}-\frac{4897}{2}y^{3}$,$\chi_{2}^{(1)}(y)=2+40y+1574y^{2}+142447y^{3}$,$\chi_{3}^{(1)}(y)=3-45y-1668y^{2}-\frac{279997}{2}y^{3}$.

次に $k=2$ においては, 式 (14) の $Q_{1}^{(2)}(x, y)$ は次式の通り求まる.
$Q_{1}^{(2)}=x^{2}-5x+6+5(x+6)y+(94x-414)y^{2}- \frac{4897}{2}(x-4)y^{3}-14635487y^{4}$$-45795235y^{5}- \frac{39884732659}{2}y^{6}$,$Q_{2}^{(2)}=x^{2}-4x+3+10(5x-6)y+(1574x-1161)y^{2}+787(181x-182)y^{3}$$+653383 y^{4}-9075761y^{5}+\frac{1371145309}{4}y^{6}$ ,$Q_{3}^{(2)}=x^{2}-3x+2-5(7x-6)y-(1668x-1562)y^{2}-( \frac{279997}{2}x$$-662219y^{4}+9536079y^{5}- \frac{697562959}{2}y^{6}$.

一$133440)y^{3}$$S^{4}$

92(この後, 補題 8 により, 式 (21) のり,$S^{1}6$を法とするべき級数根$\overline{R}_{i}^{(2)}$が求まるが, 式が複雑なため略す) それから, 式 (18), (19) によが次式の通り求まる.
mod$x_{i}^{(2)}=\chi_{i}^{(1)}+3\overline{R}_{i}^{(2)}$$S^{16}$$\chi_{1}^{(2)}(y)=1-5y+94y^{2}-\frac{4897}{2}y^{3}+\frac{152505}{2}y^{4}-2621221y^{5}+\frac{767273351}{8}y^{6}$$+\cdots$,$+ \frac{100142210296459592166377}{128}y^{14}-\frac{4354295547805912691643679}{128}y^{15}$$\chi_{2}^{(2)}(y)=2+40y+1574y^{2}+142447y^{3}+14491818y^{4}+1697595989y^{5}$$+\cdots$$+221776211733469062351693969y^{18}+32865949977819524200641894488y^{14}$$+4909433392594318497883850025622y^{15}$ ,$\chi_{3}^{(2)}(y)=3-45y-1668y^{2}-\frac{279997}{2}y^{3}-\frac{29136141}{2}y^{4}-1694974768y^{5}$$+\cdots$$- \frac{7096838195211192994973459241}{32}y^{13}-\frac{4206841697303109394141754660841}{128}y^{14}$$- \frac{628407469897777219923220111635937}{128}y^{15}$ ;よって, 式 (31) をみたす, すべてのべき級数根雇\emptyset $=\chi_{i}^{(2)}(y)(i=1,2,3)$ が求まった.

7$\blacksquare$まとめ

本稿では, 記号的 Newton 法において, 2 つの新しい同時反復公式を示した: 1 っは Aberth 法の反復公式
を用いる 3 次収束の公式であり, もう 1 つは Pade 近似を用いるもので, 任意の収束次数をもっ. そして, これらの反復公式の計算量を見積もり, 数値例を示した.

理論的な視点からは, 本稿で示したように, 数値解法における他の同時反後公式も, 記号的 Newton 法で必要な性質をみたすことが期待される. これらの同時反復公式の効果的な応用は今後の課題である.

参考文献[1] O. Aberth. Iteration Methods for Finding all Zeros of a Polynomial Simultaneously. Math. Comput.,Vol. 27, pp. 339-344, 1973.

[2] Annie Cuyt and Luc Wuytack. Nonlinear methods in numerical analysis, Vol. 136 of North-Holland
Mathematics Studies. North-Holland Publishing Co., Amsterdam, 1987. Studies in Computational
Mathematics, 1.

[3] E. Durand. Solutions$Num\text{\’{e}}_{7^{}}iques$des \’Equations $Algibr\dot{\tau}ques$, Tome I. Masson, Paris, 1960.

[4] J. von zur Gathen and J. Gerhard. Modem Computer Algebra. Cambridge University Press, Cambridge, 2nd edition, 2003.
[5] Joris van der Hoeven. Relax, but don’t be too lazy. J. Symbolic Comput., Vol. 34, No. 6, pp. 479-542,

2002.

93
[6] I. $0$ . Kerner. Ein Gesamtschrittverfahren zur Berechnung der Nullstellen von Polynomen. Nu$mer$ . Math., Vol. 8, pp. 290-294, 1966.
[7] T. Kitamoto. Hensel construction with an arbitrary degree of convergence. Japan J. Indust. Appl.
Math., Vol. 13, No. 2, pp. 203-215, 1996.
[8] H. T. Kung and J. F. ‘lfraub. All algebraic functions can be computed fast. J. $ACM$, Vol. 25, No. 2,
pp. 245-260, 1978.
[9] J. D. Lipson. Newton’s method: A great algebraic algorithm. In R. D. Jenks, editor, Proc. SYM$SAC’ 7\theta,$ $pp$

. $260-270$ . ACM, 1976.

[10] A.-W. M. Nourein. Root determination by use of Pad\’e approximants. BIT, Vol. 16, No. 3, pp.
291-297, 1976.

[11] V. Y. Pan. Solving a polynomial equation: Some history and recent progress. SIAM Review, Vol. 39,
No. 2, pp. 187-220, 1997.
[12] T. Sakurai, T. Torii, and H. Sugiura. A high-order iterative formula for simultaneous determinationof zeros of a polynomial. J. Comput. Appl. Math., Vol. 38, No. 1-3, pp. 387-397, 1991.

[13] \’Eric Schost. Multivariate power series multiplication. In Proc. ISSAC 2005, pp. $29\succ 300$ . ACM,
New York, 2005.
[14] A. Terui. A simultaneous Newton-Hensel lifting with arbitrary degree of convergence. Preprint ofUniv. of Tsukuba, submitted, 2007.
[15] 桜井鉄也, 鳥居達生, 杉浦洋. 高次収束する代数方程式の全根同時反復解法. 情報処理学会論文誌, Vol. 31,
No. 7, pp. 964-969,1990.