はさみうち法（偽位法）

この章の目標

はさみうち法（Regula Falsi, False Position とも）の原理を理解し、二分法との違い、収束速度の改善、Illinois法などの改良版を学ぶ。

前提知識

目次

1. 定義と原理

Regula Falsi（ラテン語で「偽の規則」の意）は、二分法と同様に $f(a)\cdot f(b) < 0$ を満たす区間 $[a,b]$ から出発するが、区間の中点ではなく線形補間による推定値を次の近似値とする手法である。

基本的な考え方

区間 $[a,b]$ の両端点 $(a, f(a))$ と $(b, f(b))$ を結ぶ直線（割線）が $x$ 軸と交わる点を次の近似値 $c$ とする。$f$ が区間内でおおむね線形であれば、$c$ は根に対して中点より良い近似を与える。

この手法は紀元前のバビロニア数学にまで遡る古い方法であり、中世のアラビア・ヨーロッパの数学者にも広く用いられた。

0 / 0
図1. Regula Falsi の原理（$f(x) = x^3 - x - 2$, 区間 $[1, 2]$）。2点 $(a, f(a))$, $(b, f(b))$ を結ぶ割線と $x$ 軸の交点 $c = \dfrac{a\,f(b) - b\,f(a)}{f(b) - f(a)}$ を次の近似値とし、$f(c)$ と符号の一致する端点を $c$ で置き換えて符号変化の括り区間（下の帯）を保つ。「▶ 自動再生」または「次へ／戻る」で1ステップずつ確認でき、真の根 $x^*$ は収束した最後にのみ表示される。

2. 公式の導出

2点 $(a, f(a))$ と $(b, f(b))$ を通る直線の方程式は

$$y - f(a) = \dfrac{f(b) - f(a)}{b - a}(x - a)$$

である。$y = 0$ とおいて $x$ について解くと、次の近似値 $c$ が得られる。

$$c = \dfrac{a \cdot f(b) - b \cdot f(a)}{f(b) - f(a)}$$

これは $a$ と $b$ の関数値による重み付き平均と解釈できる。$|f(a)|$ が小さければ $c$ は $a$ に近づき、$|f(b)|$ が小さければ $c$ は $b$ に近づく。同値な表現として

$$c = a - f(a) \cdot \dfrac{b - a}{f(b) - f(a)}$$

と書くこともできる。この形は割線法（Secant Method）の公式と同一であるが、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$ 側だけが $1.333 \to 1.463 \to 1.504 \to \cdots$ とゆっくり近づく（停滞）。停滞を崩す改良が次節の Illinois 法である。

3. アルゴリズム

Regula Falsi 法（基本形）

  1. $f(a) \cdot f(b) < 0$ を満たす初期区間 $[a, b]$ を選ぶ。
  2. $c = \dfrac{a \cdot f(b) - b \cdot f(a)}{f(b) - f(a)}$ を計算する。
  3. $|f(c)| < \varepsilon$ または $|b - a| < \delta$ ならば $c$ を根として終了。
  4. $f(a) \cdot f(c) < 0$ ならば $b \leftarrow c$、そうでなければ $a \leftarrow c$ とする。
  5. 反復回数が上限 $N_{\max}$ に達するまで 2--4 を繰り返す。

擬似コードを以下に示す。

function regulaFalsi(f, a, b, tol, maxIter):
    assert f(a) * f(b) < 0
    fa = f(a)
    fb = f(b)
    for i = 1 to maxIter:
        c  = (a * fb - b * fa) / (fb - fa)
        fc = f(c)
        if |fc| < tol:
            return c
        if fa * fc < 0:
            b  = c
            fb = fc
        else:
            a  = c
            fa = fc
    return c

4. 二分法との比較

特性二分法Regula Falsi
次の近似値区間の中点 $(a+b)/2$線形補間 $\dfrac{af(b)-bf(a)}{f(b)-f(a)}$
関数値の利用符号のみ符号と大きさ
収束保証常に保証常に保証
収束速度（理想的な場合）線形（1.0）超線形（~1.618）
停滞の可能性なしあり（片側端点が固定）
区間幅の単調減少保証される保証されない
最悪時の収束速度線形線形以下になりうる

Regula Falsi は関数の傾きの情報を利用するため、$f$ が区間内でおおむね線形な場合は二分法より格段に速い。しかし $f$ が強い凸性をもつ場合は停滞現象（次節参照）が発生し、二分法より遅くなることがある。

5. 停滞問題と Illinois 法

停滞現象

Regula Falsi では、関数が凸（または凹）である場合、片方の端点が何度も更新されずに固定され続ける現象が起こる。これを停滞（stagnation）と呼ぶ。

例えば $f$ が下に凸で $f(a) < 0$, $f(b) > 0$ の場合、割線は曲線の上側を通るため常に根の左側で $x$ 軸と交わり、端点 $b$ が固定されたまま $a$ のみが更新され続ける。区間幅が効率的に縮小しないため、収束が著しく遅くなる。

停滞現象の図解。凸関数 f(x)=x³−x−2、区間 [1,2] では端点 b が固定されたまま a 側だけが更新され、割線の x 軸交点 c が根 x* へ左側からゆっくり近づく。
図2. 停滞現象の図解（$f(x)=x^3-x-2$, 区間 $[1,2]$）。この凸関数では割線が曲線の上側を通るため常に根の左側で $x$ 軸と交わり、端点 $b$ が固定されたまま $a$ 側だけが更新される。交点 $c_0, c_1, \ldots$ は根 $x^*$ へ左側からゆっくり近づき、区間幅が効率的に縮まらないため収束が著しく遅くなる。

Illinois 法

Illinois 法（Illinois algorithm）は、停滞を検出して固定端点の関数値を半減させることで停滞を回避する改良版である。具体的には、同じ端点が2回連続で保持された場合、その端点の関数値を半分にする。

Illinois 法の原理。固定端点 b の関数値 f(b)=4 を半分の 2 にすると、割線(橙)が下へ傾き、x 軸との交点が普通の Regula Falsi の c(根の左)から c'(根の右)へ移る。これにより b が更新され停滞が解消する。
図3. Illinois 法が停滞を解消する仕組み（$f(x)=x^3-x-2$）。停滞中、普通の Regula Falsi は固定端点 $b$ の点 $(b,\,f(b))$ を使うため割線（灰破線）の交点 $c$ は常に根の左側に落ち、$a$ だけが動く。Illinois 法は $f(b)$ を半分にした点 $(b,\,f(b)/2)$ を使うので割線（橙）が下に傾き、交点 $c'$ が根の右側に移る。すると $f(c')$ の符号が変わって今度は $b$ が更新され、停滞が解消する。

Illinois 法

  1. $f(a) \cdot f(b) < 0$ を満たす初期区間 $[a, b]$ を選ぶ。$\text{side} = 0$ とする。
  2. $c = \dfrac{a \cdot f(b) - b \cdot f(a)}{f(b) - f(a)}$ を計算する。$f(c)$ を求める。
  3. $|f(c)| < \varepsilon$ ならば $c$ を根として終了。
  4. $f(a) \cdot f(c) < 0$ ならば:
    • $b \leftarrow c$, $f(b) \leftarrow f(c)$
    • $\text{side} = -1$（前回も $b$ を更新）ならば $f(a) \leftarrow f(a)/2$
    • $\text{side} = -1$ に設定
  5. そうでなければ:
    • $a \leftarrow c$, $f(a) \leftarrow f(c)$
    • $\text{side} = +1$（前回も $a$ を更新）ならば $f(b) \leftarrow f(b)/2$
    • $\text{side} = +1$ に設定
  6. 反復回数が上限に達するまで 2--5 を繰り返す。

Illinois 法のほかにも、Pegasus 法（$f(b) \cdot f(c) / (f(c) + f(b))$ で重み付け）や Anderson-Bjorck 法（より洗練された重み調整）といった改良手法が存在する。

改良手法の違いは「停滞時の重み」だけ

これらの改良はすべて同じ偽位置法（同じ交点公式・常に根を挟む）であり、違うのは「同じ端点が 2 回続けて残った（＝もう一方が停滞した）とき、その固定端点の関数値に掛ける縮小の重み $g$」だけである。重みが関数値に応じて適応的なほど割線が早く根の反対側へ移り、収束が速くなる。

手法固定端点に掛ける重み $g$収束次数（単根）備考
Regula Falsi（基本）$1$（縮小しない）停滞時は線形に劣化停滞する
Illinois$\dfrac{1}{2}$（固定）$\sqrt[3]{3} \approx 1.442$最も単純
Pegasus$\dfrac{f_2}{f_2 + f_c}$$\approx 1.642$関数値で決まる適応的重み
King（Pegasus 改良）Pegasus の式＋遅い副ステップ除去$\approx 1.839$最速級
Anderson-Björck$1 - \dfrac{f_c}{f_2}$（$\le 0$ なら $\tfrac{1}{2}$）$\approx 1.7$より洗練・堅牢

ここで $f_2$ は停滞端点が記憶している関数値、$f_c$ は今回の $f(c)$。いずれも括り（bracketing）を保つため、純粋な割線法（$\varphi \approx 1.618$ だが発散しうる）と違い収束は必ず保証される。「割線法の速さ＋二分法の安全」を重みの工夫でどこまで両立するかの競争といえる。

6. 収束性

基本的な収束保証

Regula Falsi は二分法と同様、各反復で $f(a)\cdot f(b) < 0$ を維持するため、収束は常に保証される。ただし区間幅の縮小速度については、二分法のような単調な保証はない。

収束次数

$f$ が単根 $x^*$ の近傍で $C^2$ 級であるとき、Regula Falsi の漸近的な収束次数は以下のようになる。

  • 停滞なし（両端点が交互に更新）: 超線形収束、次数 $\approx 1.618$（黄金比 $\varphi$）。これは割線法と同じ次数である。
  • 停滞あり: 線形収束に低下する。最悪の場合、二分法より遅くなりうる。
  • Illinois 法: 次数 $\approx 1.442$（$\sqrt[3]{3}$）。停滞が回避されるため安定した超線形収束を示す。

誤差の漸化式

停滞が起きない場合、誤差 $e_n = |c_n - x^*|$ は近似的に

$$e_{n+1} \approx C \cdot e_n \cdot e_{n-1}$$

を満たす（$C$ は $f''(x^*) / (2f'(x^*))$ に依存する定数）。この漸化式から収束次数 $\varphi = (1+\sqrt{5})/2 \approx 1.618$ が導かれる。

7. 計算例

例1: $f(x) = (x-1)(x-2)(x-3)$ の中央の根 $x^* = 2$ を区間 $[1.3, 2.5]$ で求める

$f(1.3) = +0.357$, $f(2.5) = -0.375$ であり、符号が異なるため Regula Falsi を適用できる（区間内の根は $x^* = 2$ のみ）。この区間では曲線に変曲点が含まれ、両端点が交互に更新されるため停滞が起こらない。

$n$$a_n$$b_n$$c_n$$f(c_n)$
01.3000002.5000001.885246+0.113243
11.8852462.5000002.027832−0.027810
21.8852462.0278321.999719+0.000281
31.9997192.0278322.000000$-2.2\times 10^{-7}$

真の根は $x^* = 2$ である。端点 $a$ と $b$ が交互に更新されて停滞が起こらず、わずか3回の反復で約7桁の精度に達する。同じ区間で二分法を4回行っても区間幅は $1.2 / 2^4 = 0.075$（1桁程度）にしか縮まらないことと比べると、線形補間の効果は明確である。

例2: 停滞が発生する場合 — $f(x) = x^{10} - 1$, 区間 $[0, 1.3]$

$f(0) = -1$, $f(1.3) \approx 12.786$ であり、$f$ は区間内で強い凸性をもつ。

基本の Regula Falsi では端点 $b = 1.3$ が固定されたまま、$a$ が $0$ から非常にゆっくりと根 $x^* = 1$ に近づく。$f$ がほぼ平坦な区間が長いため $a$ の更新が極端に遅く、数十回の反復でも十分な精度に達せず、二分法より遅い収束を示す。

一方、Illinois 法を適用すると、固定端点 $b$ の関数値が半減されることで両端が交互に動き始め、約10回の反復で十分な精度が得られる。

8. よくある質問

Q1. Regula Falsi と二分法の違いは何か

二分法は区間の中点を次の近似値とするのに対し、Regula Falsi は区間両端の関数値を結ぶ直線と $x$ 軸の交点を次の近似値とする。関数の傾きの情報を利用するため多くの場合二分法より高速であるが、片側の端点が固定される停滞現象が起こりうる。

Q2. 停滞（stagnation）とは何か

関数が凸（または凹）である場合、Regula Falsi で片方の端点が何度も更新されずに固定され続ける現象である。Illinois 法などの改良手法は、固定された端点の関数値を半分にすることで停滞を回避する。

Q3. 収束次数はいくつか

単根に対し、停滞が起きない理想的な場合は超線形収束（次数 $\approx 1.618$、黄金比）である。停滞が発生すると線形以下に低下する。Illinois 法を用いると次数 $\approx 1.442$ に安定する。

9. 参考資料

  • Wikipedia「はさみうち法」（日本語版）
  • Wikipedia「Regula falsi」（英語版）
  • Wikipedia「Illinois algorithm」（英語版）
  • R. L. Burden & J. D. Faires, Numerical Analysis, 10th ed., Cengage, 2016.
  • W. H. Press et al., Numerical Recipes, 3rd ed., Cambridge, 2007.
  • M. Dowell & P. Jarratt, "The Pegasus method for computing the root of an equation," BIT 12 (1972), 503–508.（Pegasus 法とその収束次数）
  • R. F. King, "An improved Pegasus method for root finding," BIT 13 (1973), 423–427.（King 法＝Pegasus の改良、次数 $\approx 1.839$）
  • R. G. Bartle & D. R. Sherbert, Introduction to Real Analysis, 4th ed., Wiley, 2011.

sangi での実装

本記事の各手法は sangi の求根モジュール (Roots) で利用できる。命名が記事と一部異なる点に注意：

記事の手法sangi の関数備考
Regula Falsi（基本形・停滞しうる）regula_falsi停滞回避なしの基本形
Illinois 法illinois_method重み 1/2 で停滞回避（実用向き）
Pegasus 法king_methodKing-Pegasus（King 1973 は Pegasus の改良版）
Anderson-Björck 法anderson_bjork_methodIllinois 改良型