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;
}
特徴
- 初期値によって、反復回数が結構変わる。