2分法は指定した区間内の解は必ず求めるものの,解の収束は遅い.
関数
が連続で微分可能関数であるならば,関数の勾配値を用いることで収束を早めることができる.
解の初期値を
とする.
での関数
の接線は,
となる.この接線が
軸と交差する(
)点は,
を次の近似値として同様の処理を繰り返すことで解に近づいていく.図2はこの手順を示したものである.
この方法をニュートン・ラフソン法(Newton-Raphson method),もしくは単にニュートン法(Newton method)と呼ぶ.
ニュートン法の式は以下となる.
反復回数を多くすると限りなく
の解に近づく.
反復を終了するための収束条件は,
となる.
ニュートン法は2分法と異なり解のある区間でなく初期近似値1つだけを指定するだけでよく,収束も速い.
しかし,
だけでなくその微分値
も必要で,初期値によっては解へ収束しない場合もある.
 |
図2 ニュートン法 |
ニュートン法のコード例を以下に示す.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| |
int newton(double func(const double), double dfunc(const double),
double &x, int &max_iter, double &eps)
{
double f, df, dx;
int k;
for(k = 0; k < max_iter; ++k){
f = func(x);
df = dfunc(x);
x = xn-f/df;
dx = fabs(f/df);
if(dx < eps || fabs(f) < eps){
max_iter = k; eps = dx;
return 1;
}
}
max_iter = k; eps = dx;
return 0;
}
|