はさみうち法（非線形方程式の数値解法）

はさみうち法とは

• 非線形方程式の数値解法の一つ
• 二分法の改良
  • 二分法では、二点の中点を新しい端点としたのに対して、はさみうち法では、二点を結ぶ直線が$x$軸と交わる点を新しい端点とする

算法

初期値

$x_{a_0},x_{b_0}$ : 適当な方法で決める。ただし、$f(x_{a_0})f(x_{b_0})<0$

反復手順

$x_{c_n}=\frac{x_{a_n}f(x_{b_n})-x_{b_n}f(x_{a_n})}{f(x_{b_n})-f(x_{a_n})}$
$f(x_{c_n})f(x_{a_n})<0$ ならば、$x_{a_{n+1}}=x_{a_n}$ $,$ $x_{b_{n+1}}=x_{c_n}$
$f(x_{c_n})f(x_{a_n})>0$ ならば、$x_{a_{n+1}}=x_{c_n}$ $,$ $x_{b_{n+1}}=x_{b_n}$

停止則

$|f(x_c)|<\varepsilon$ のとき反復停止
※$[x_a,x_b]$はゼロに収束しない

サンプルコード

$f(x)=x^2-1$、初期値 $a=0.5,b=2$ としてはさみうち法を使って解を求めるプログラム。
$f(a)f(b)<0$の確認とか入れてないガバガバコード

regula_falsi.c

#include<stdio.h>
#include<math.h>

double f (double x) {
  return x*x-1;
}

double regula_falsi (double a, double b) {
  double c;
  do {
    c = (a*f(b) - b*f(a)) / (f(b) - f(a));
    if (f(c) == 0) { break; }
    if (f(a) * f(c) < 0) { b = c; }
    if (f(a) * f(c) > 0) { a = c; }
  } while (fabs(f(c)) > 1e-10);
  return c;
}

int main (void) {
  double alpha;
  alpha = regula_falsi(0.5, 2);
  printf("%f\n", alpha);
  return 0;
}

実行結果

1.000000

特徴

• 初期値が悪いと二分法より収束が悪い場合がある
• Newton法の初期値を求めるのに適している