割線法

この章の目標

割線法のアルゴリズムを理解し、導関数を使わずにニュートン法に近い超線形収束（$\varphi$ 次）を達成する仕組みを学ぶ。

前提知識

目次

1. 概要

割線法（Secant Method）は、非線形方程式 $f(x)=0$ の根を求める反復法である。ニュートン法の導関数 $f'(x_n)$ を、直近の2点 $(x_{n-1}, f(x_{n-1}))$ と $(x_n, f(x_n))$ を通る割線（secant line）の傾きで置き換える。導関数を陽に計算する必要がないため、$f'$ が求めにくい場合に特に有用である。

2. アルゴリズム

割線法の反復公式

初期値 $x_0, x_1$ を与え、

$$x_{n+1} = x_n - f(x_n)\,\dfrac{x_n - x_{n-1}}{f(x_n) - f(x_{n-1})}, \qquad n = 1, 2, \ldots$$

これはニュートン法の公式で $f'(x_n)$ を差分商 $\dfrac{f(x_n)-f(x_{n-1})}{x_n - x_{n-1}}$ で置き換えたものである。

0 / 0
図1. 割線法の反復過程（$f(x) = x^2 - 2$, 根 $x^* = \sqrt{2}$）。直近の2点 $(x_{n-1}, f(x_{n-1}))$ と $(x_n, f(x_n))$ を結ぶ割線（直線）を引き、それが $x$ 軸と交わる点を次の近似値 $x_{n+1}$ とする。割線は両点を通り $x$ 軸まで延長して描いている。「▶ 自動再生」または「次へ／戻る」で1ステップずつ確認できる。

3. 収束次数

定理（割線法の収束次数）

$f$ が2回連続微分可能で、単根 $x^*$ の十分近くに $x_0, x_1$ をとると、割線法は次数

$$p = \dfrac{1+\sqrt{5}}{2} = \varphi \approx 1.618$$

で収束する。ここで $\varphi$ は黄金比である。

背景を一言で述べると、誤差 $e_n = x_n - x^*$ は $|e_{n+1}| \approx C\,|e_n|^{\varphi}$ を満たし、指数 $\varphi$ は $r^2 = r + 1$ の正の解（黄金比）として現れる。

ニュートン法（2次）と二分法（1次）の中間的な超線形収束であるが、割線法は1回の反復あたりの関数評価が1回（ニュートン法は $f$ と $f'$ の2回）で済む。したがって関数評価あたりの効率で比較すると、割線法の効率指数は $\varphi^1 \approx 1.618$ であり、ニュートン法の $2^{1/2} \approx 1.414$ を上回る。

4. ニュートン法との比較

特性ニュートン法割線法
反復公式$x_{n+1}=x_n-\dfrac{f(x_n)}{f'(x_n)}$$x_{n+1}=x_n-f(x_n)\dfrac{x_n-x_{n-1}}{f(x_n)-f(x_{n-1})}$
必要な初期値$x_0$（1個）$x_0, x_1$（2個）
導関数必要不要
収束次数2$\varphi \approx 1.618$
1反復あたりの関数評価2回（$f, f'$）1回（$f$）
効率指数$2^{1/2}\approx 1.414$$\varphi \approx 1.618$
収束保証局所的局所的
0 −4 −8 −12 −16 関数評価回数 log₁₀|誤差| 2 4 6 8 10 ニュートン法 割線法
図2. 関数評価回数あたりの精度（$f(x)=x^2-2$、根 $\sqrt{2}$ の実測収束）。ニュートン法は $x_0=2$ から1反復に2回の関数評価（$f$ と $f'$）、割線法は $x_0=1,\ x_1=2$ から1反復に1回。序盤はニュートン法が先行するが、6評価付近で並び、その後は割線法が逆転する。これは効率指数（割線法 $\varphi \approx 1.618$ > ニュートン法 $2^{1/2} \approx 1.414$）が漸近的に効くためである。

「反復あたり」と「評価あたり」は別物

  • 反復回数あたりでは、収束次数が $2 > \varphi$ なので常にニュートン法が速い。割線法が反復数でニュートン法を上回ることはない。図2の横軸が「関数評価回数」であって反復回数ではない点に注意。
  • 図2の逆転は関数評価あたりの効率を表す。効率指数の比較（$\varphi \approx 1.618 > 2^{1/2} \approx 1.414$）は、$f'$ の計算量が $f$ と同程度という仮定に基づく。
  • 実用上は前提次第で結論が変わる。$f$ の計算量を $1$、$f'$ の計算量を $c$ とすると効率指数は Newton $=2^{1/(1+c)}$・割線法 $=\varphi$ で、両者の境目は $c \approx 0.44$ にある。$f'$ が計算不能、または計算量が大きい場合（$c \gtrsim 0.44$）は割線法が有利（これが割線法を使う主目的）。逆に $f'$ が$f$ より少ない計算量で得られる場合（$c \lesssim 0.44$。自動微分や $f$ の副産物など）はニュートン法が有利。
  • 交差する評価回数（この例では約6回）や序盤の優劣は、関数・初期値・定数に依存し、例ごとに変わる。

5. 偽位置法（Regula Falsi）

偽位置法（Regula Falsi, Method of False Position）は、割線法と二分法を組み合わせた手法である。割線法と同じ反復式を用いるが、常に $f(a_n)\cdot f(b_n) < 0$ を維持する点が異なる。

偽位置法

$f(a_n)\cdot f(b_n) < 0$ を満たす区間 $[a_n, b_n]$ に対し、

$$c_n = a_n - f(a_n)\,\dfrac{b_n - a_n}{f(b_n) - f(a_n)}$$

を計算し、$f(a_n)\cdot f(c_n) < 0$ なら $b_{n+1}=c_n$、そうでなければ $a_{n+1}=c_n$ とする。

収束は保証されるが、一方の端点が固定されやすく、収束が線形に劣化する場合がある。改良版としてIllinois 法やPegasus 法がある。

割線法と Regula Falsi の違い（同じ式・違う点の選び方）

両者とも次の近似値は同じ交点公式 $c = \dfrac{a\,f(b)-b\,f(a)}{f(b)-f(a)}$ で求める。違うのは次の反復に残す2点の選び方だけである。

  • 割線法：常に最新の2点を使う（古い方を無条件で捨てる）。根を挟む保証がなく発散しうるが、最新情報を使うため速い（次数 $\varphi \approx 1.618$）。
  • Regula Falsi：符号が逆の2点（根を挟む組）を残す。同符号になった端点を $c$ で置き換えるため常に根を挟み、収束が保証される。ただし片方の端点が固定され続ける停滞が起こりうる。

同じ $f(x)=x^3-x-2$・初期2点 $1, 2$ では1手目はどちらも $c=1.333$ で同じ。だが割線法は3手目で同符号の2点 $(1.333,\,1.463)$ も使って $1.531 \to \cdots$ と速く根 $1.5214$ に達するのに対し、Regula Falsi は根を挟むため端点 $b=2$ を残し続け、$a$ 側だけがゆっくり近づく（停滞）。

6. よくある質問

Q1. 割線法とは何か

直近の2つの近似値を通る割線と $x$ 軸の交点を次の近似値とする反復法である。導関数の計算が不要であり、差分商による近似と解釈できる。

Q2. 割線法の収束次数は何次か

黄金比 $\varphi = (1+\sqrt{5})/2 \approx 1.618$ であり、超線形収束する。関数評価あたりの効率ではニュートン法を上回る。

Q3. 偽位置法と割線法の違いは何か

偽位置法は $f(a)f(b)<0$ を維持する括り出し法であり収束が保証される。割線法は単に直近の2点を使うため収束保証がないが、一般に収束速度は速い。

7. 参考資料

  • Wikipedia「Secant method」（英語版）
  • Wikipedia「Regula falsi」（英語版）
  • R. L. Burden & J. D. Faires, Numerical Analysis, 10th ed., Cengage, 2016.
  • J. F. Traub, Iterative Methods for the Solution of Equations, Chelsea, 1982.

sangi での実装

この記事のアルゴリズムは sangi の secant_method で利用できる。