Newton法とは

非線形方程式の数値解法の一つ
初期値$x_n$におけるグラフ$f(x)$の接線が$x$軸と交わる点を$x_{n+1}$として解$\alpha$の近似値を求める。

算法

初期値

$x_0$ : 適当な方法で決める

反復手順

$x_{n+1}=x_n-f(x)/f^{\prime}(x)$

停止則

更新量が小さい：$|f(x)/f^{\prime}(x)|<\varepsilon_1$
$f(x_n)$が$0$に近い：$|f(x_n)|<\varepsilon_2$

サンプルコード

$f(x)=x^2-1$ 、初期値 $x_0=3$ としてNewton法を使って解を求めるプログラム。
$f^{\prime}(x)\neq 0$ の確認とかを入れてないガバガバコード

newton_method.c

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

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

double df (double x) {
  return 2*x;
}

double newton_method (double x) {
  double new_x;
  while (1) {
    new_x = x - f(x)/df(x);
    if (fabs(f(x)/df(x)) < 1e-10) break;
    if (fabs(f(new_x)) < 1e-10) break;
    x = new_x;
  }
  return new_x;
}

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

特徴

初期値によって、反復回数が結構変わる。