1D 求根: 非区間法 (Open Methods)

概要

非区間法 (open methods) は 1 点 (または 2 点) の初期値から反復で根に近づける手法。 囲い込みを保証しない代わりに、二次以上の高速な収束が出せる。 収束半径の外から出発すると発散する可能性があるため、初期値の選択が重要。

関連 API: newton_raphson, secant_method / halley_method, schroder_method, king_method, popovski_method。

Newton 法 (Newton-Raphson)

関数を現在点で 1 次 Taylor 展開し、その零点を次の点とする:

$$x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$$

収束

単根 ($f(\alpha) = 0,\ f'(\alpha) \neq 0$) かつ $f \in C^2$ なら、収束半径内の $x_0$ から二次収束:

$$|x_{n+1} - \alpha| \approx \frac{|f''(\alpha)|}{2|f'(\alpha)|} \cdot |x_n - \alpha|^2$$

重根 ($f'(\alpha) = 0$) では線形収束 (収束比 $1 - 1/m$, $m$ は重複度) に劣化する。 この場合 Schröder 法または重複度を明示した変種を使う。

失敗モード

• $f'(x_n) \approx 0$ で発散
• 変曲点をまたぐと振動
• 収束半径外の初期値で別の根 (または無限大) に飛ぶ

sangi の newton_raphson は導関数 $f'$ を呼び出し関数として要求する。 多項式の場合は Polynomial::derivative() で生成でき、Horner 評価で $f, f'$ を 1 パスで計算する。

割線法 (secant)

Newton の $f'(x_n)$ を直前 2 点の差分商で置き換える:

$$x_{n+1} = x_n - f(x_n) \cdot \frac{x_n - x_{n-1}}{f(x_n) - f(x_{n-1})}$$

収束

収束次数: 黄金分割 $\varphi = (1 + \sqrt{5})/2 \approx 1.618$。 Newton (2 次) より遅いが、反復あたりの関数評価は 1 回。 導関数の解析形が得られないとき、または評価が極端に高価なときに有利。

$f(x_n)$ と $f(x_{n-1})$ が非常に近いと差分が桁落ちして発散するので、停滞 (stagnation) 検知が必要。

Halley 法

2 次 Taylor 展開の零点を解いたものに相当する三次収束法:

$$x_{n+1} = x_n - \frac{2 f(x_n) f'(x_n)}{2 f'(x_n)^2 - f(x_n) f''(x_n)}$$

または等価な「修正 Newton」の形:

$$x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} \cdot \frac{1}{1 - \frac{f(x_n) f''(x_n)}{2 f'(x_n)^2}}$$

収束

収束次数: 3 次。誤差が三乗で減るので、Newton の二乗より速い。 反復あたり $f, f', f''$ を評価するので、評価コストが Newton の 1.5 倍未満なら総コストで勝つ。

多項式に Halley を使うときは、Horner 三重展開で $f, f', f''$ を 1 パスで計算できる (sangi の polynomial::laguerre の内部評価と同じパターン)。

Householder 法

Newton 法と Halley 法を一般化した族で、$d$ 階の導関数を用いて$(d+1)$ 次収束を実現する:

$$x_{n+1} = x_n + d \cdot \frac{(1/f)^{(d-1)}(x_n)}{(1/f)^{(d)}(x_n)}$$

• $d = 1$: Newton 法
• $d = 2$: Halley 法
• $d = 3$: 4 次 Householder

高次の Householder は理論的には任意の収束次数を実現するが、$f$ の高階導関数が必要で実装と評価コストが急増する。 実用では $d \leq 3$ が中心。

Schröder 法 (重根対応)

$f$ が重複度 $m$ の根 $\alpha$ を持つ場合、素朴な Newton は線形収束に落ちる。 Schröder 法は反復ステップに $m$ を掛けて二次収束を回復する:

$$x_{n+1} = x_n - m \cdot \frac{f(x_n)}{f'(x_n)}$$

または重複度を陽に使わない別形:

$$x_{n+1} = x_n - \frac{f(x_n) f'(x_n)}{f'(x_n)^2 - f(x_n) f''(x_n)}$$

後者は Halley に似た形だが、重根に対しては Halley と異なり厳密に二次収束する (Halley は重根で次数が下がる)。 sangi の schroder_method はこの 2 番目の形を採用する。

King / Popovski 法 (4 次収束)

$f, f'$ のみを使いつつ、Newton + 1 ステップの修正で4 次収束を実現する手法群。

King 法 (1973)

Newton ステップ $y_n = x_n - f(x_n)/f'(x_n)$ の後、$f(y_n)$ を評価して修正を加える:

$$x_{n+1} = y_n - \frac{f(y_n)}{f'(x_n)} \cdot \frac{f(x_n) + \beta f(y_n)}{f(x_n) + (\beta - 2) f(y_n)}$$

パラメータ $\beta \in \mathbb{R}$ で族をなし、$\beta = 0$ で Ostrowski 法に一致する。

Popovski 法

同じく Newton + 1 ステップ修正の 4 次収束法。King とは修正項の構成が異なり、収束半径や安定性で違いがある。

反復あたりのコスト

King / Popovski は反復ごとに $f$ を 2 回、$f'$ を 1 回評価する (Newton の 3 倍の評価コスト)。 収束次数 4 で、Newton 2 反復分のコスト (4 回評価) より速い場面が多いが、損益分岐は関数評価コストに依存する。

収束基準と 停滞検知

sangi の ConvergenceCriteria<T> は次の 3 種類の判定を統合する:

• 変数収束: $|x_{n+1} - x_n| < \text{tol}_x \cdot (|x_n| + \text{tol}_x)$
• 関数値収束: $|f(x_n)| < \text{tol}_f$
• 区間収束 (bracket 系のみ): $|b - a| < \text{tol}_x$

これに加えて停滞検知:

• $|x_{n+1} - x_n|$ が前ステップから縮まらない
• $|f(x_n)|$ が改善しない
• $f'(x_n)$ が $\epsilon$ オーダーで $0$ に近づく (Newton 系)

これらが検知されたら、RootFindingResult は partial_success を返し、現在の最良近似と推定誤差を含める。 収束しなかったことを呼び出し側に明示することで、ユーザーは別アルゴリズムへフォールバックできる。

許容誤差の選び方

$\text{tol}_x \approx \sqrt{\epsilon_{\text{machine}}}$ (double なら $\approx 10^{-8}$) が経験則。 Newton 系の二次収束では、最後の反復で誤差がほぼ機械精度まで落ちる (誤差の二乗が機械精度を切る) ため、これより厳しい tol_x は意味を成さない。

比較表

導関数が容易に得られるなら Halley、得られないなら King / Popovski か secant、重根を疑うなら Schröder、というのが大まかな指針。

参考文献

• Ostrowski, A. M. (1973). Solution of Equations in Euclidean and Banach Spaces. 3rd ed. Academic Press.
• Traub, J. F. (1964). Iterative Methods for the Solution of Equations. Prentice-Hall.
• King, R. F. (1973). "A family of fourth order methods for nonlinear equations". SIAM Journal on Numerical Analysis, 10(5), 876–879.
• Schröder, E. (1870). "Über unendlich viele Algorithmen zur Auflösung der Gleichungen". Mathematische Annalen, 2, 317–365.