next up previous contents
Next: A.2 Horner 法 Up: A. おもちゃ箱 (その他の方法) Previous: A. おもちゃ箱 (その他の方法)

A.1 平野法

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

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

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

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

室田 一雄, 平野の変形 Newton 法の大域的収束性, 情報処理学会論文誌, Vol.21 (1980), pp.469-474.
で初めて証明された。

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

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

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

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

と展開する。もちろん

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

特に

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

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

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

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

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

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

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

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

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

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


\begin{jlemma}[$\vert\zeta_m\vert$\ が余裕を持って最小ならば関数値は減少する]\up...
... \beta \left\vert p(z^{(\nu)})\right\vert
\end{displaymath}である。
\end{jlemma}

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

$\displaystyle \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$ を求め、

(A.3) $\displaystyle \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]$

とする。


\begin{jtheorem}[室田 1980 --- 平野法の大域的収束性]\upshape
任意の初期値 $z^{(...
...splaymath}ゆえに $\{z^{(\nu)}\}$\ は $p(z)$\ のある根に収束する。
\end{jtheorem}

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


next up previous contents
Next: A.2 Horner 法 Up: A. おもちゃ箱 (その他の方法) Previous: A. おもちゃ箱 (その他の方法)
Masashi Katsurada
平成21年7月9日