A.1 平野法

(この節の内容は全面的に杉原・室田 [17] のつまみ食いである。)

平野法は Newton 法を少し修正したものであるが、 大域的収束性を保証できるという大きな長所がある。1960 年代後半に

• 平野 菅保, 代数方程式の解法および誤差, 第8回プログラミングシンポジウム 報告集, 情報処理学会, 1967.
• B.Dejon and K.Nickel, A never failing fast convergent root-finding algorithm, Constructive Aspects of the Fundamental Theorems of Algebra (B.Dejon and P.Henrici, eds.), John Wiley, New York, 1969, pp.1-35.

によって独立に提案された算法である。

アルゴリズムの解説と収束を保証する定理については、

室田 一雄, 平野の変形 Newton 法の大域的収束性, 情報処理学会論文誌, Vol.21 (1980), pp.469-474.

で初めて証明された。

$$p(z)=\sum_{k=0}^n a_{n-k}z^k$$

$$z^{(\nu+1)}=z^{(\nu)}+\Delta z^{(\nu)}$$   $$\mbox{($\nu=0,1,\cdots$)}$$

$\Delta z^{(\nu)}$ は次のように考えて決める。$p(z)$ を $z^{(\nu)}$ の回 りで

$$p(z^{\nu}+\zeta)=\sum_{k=0}^n c_{n-k}\zeta^{k}$$ (A.1)

と展開する。もちろん

$$c_{n-k}=\frac{p^{(k)}(z^{(\nu)})}{k!}$$   $$\mbox{($k=0,1,\cdots,n$)}$$$$,$$

特に

$$c_n=p(z^{(\nu)}),\quad c_{n-1}=p'(z^{(\nu)})$$

通常の Newton 方では、$z^{(\nu)}$ が根に十分近いことを前提にして、 (A.1) の右辺から $k=0$ と $k=1$ に対応する 項だけを取り出して、

$$p(z^{(\nu)+\zeta})\kinji c_{n-1}\zeta+c_n$$ (A.2)

と近似して、これを 0 にする値

$$\zeta=-\frac{c_n}{c_{n-1}}=-\frac{p(z^{\nu})}{p'(z^{(\nu)})}$$

を修正量としている。 平野法では、

$$p(z^{(\nu)}+\zeta)\kinji c_{n-k}\zeta^{k}+c_n$$   $$\mbox{($k=1,2,\cdots,n$)}$$

という $2$ 項近似を考え、これから定まる

$$\zeta_{k}:= \left(-\frac{c_n}{c_{n-k}}\right)^{1/k}$$   $$\mbox{($c_{n-k}=0$\ のときは $\zeta_k=\infty$\ とおく)}$$

を修正量の候補とし、それらの中で絶対値が最小のもの (これを $\zeta_m$ と 書く) を修正量に採用する。

Proof. 杉原・室田 [17] を見よ。$\qedsymbol$ ARRAY(0x12eca8c) $\qedsymbol$

$z^{(\nu)}$ が根 $\alpha$ の十分良い近似値ならば $m=1$ となる (すなわ ち Newton 法と一致)。さらに $\alpha$ が単根であることを仮定すると、 補題の条件が成り立つ。

$0<\beta<1$, $\lambda>1$ は減速の仕方を決めるパラメーターである。 例えば $\beta=3/4$, $\lambda=2$ とする。

平野法の第 $\nu$ 段の修正量の決定

(1)

$c_k$ ( $k=0,1,2,\cdots,n$) を組み立て除法で計算する。 $\mu := 1$ とおく。

(2)

$\zeta_{k}:=(-\mu c_n/c_{n-k})^{1/k}$ ( $k=1,2,\cdots,n$) とおく。

(3)

$\vert\zeta_{k}\vert$ が最小である $k$ ( $1\le k\le n$) を $m$ とおく。

(4)

$\left\vert p(z^{(\nu)+\zeta_m})\right\vert\le (1-(1-\beta)\mu)\vert c_n\vert$ ならば、 $\Delta z^{(\nu)}:=\zeta_m$ として第 $\nu$ 段を終了し、 そうでなければ $\mu:=\mu/\lambda$ として、(2) に戻る。

(2) における $k$ 乗根の分枝は、 $\vert z^{(\nu)}+\zeta_k\vert$ が最も小さくなるなものを選ぶ。 具体的には $\phi$, $\psi_{k}\in [0,1)$ を

$$\phi=\frac{\arg z^{(\nu)}}{2\pi},\quad \psi_k=\frac{\arg(-c_n/c_{n-k})}{2\pi},\quad$$

で定めて、 $k(1/2-\phi)-\psi_k$ に最も近い整数 $j_k$ を求め、

$$\zeta_k:= \left\vert \mu\frac{c_n}{c_{n-k}} \right\vert^{1/k} \exp \left[ \frac{2\pi i(\psi_k+j_k)}{k} \right]$$ (A.3)

とする。

Proof. 元々は室田 [19] による。杉原・室田 [17] 第5章を見 よ。$\qedsymbol$ ARRAY(0x12e00ec) $\qedsymbol$