セカント法による求根

セカント法(割線法)は、ニュートン法では微分できることが必要でしたが、その必要はなく一つ前の解との差分から傾きを計算する手法です.ここでは一次元のみ紹介します. セカント法はニュートン法と異なり二次収束がしないため、ニュートン法ほどの収束の速さは保証されませんが、与えられる関数によっては早くなります.

ニュートン法についてはリンク参照

セカント法は下記の更新式を元にして以下の手順で関数がゼロになる変数の値を求めます.(1次元の場合) セカント法の手順 1. 関数\(f(x)\)と解に近い2つの初期値\(x_n, x_{n-1}\)を用意. 2. 過去最新の二つの解とf(x)から傾きを計算し、更新式で新しい\(x_{n+1}\)を計算 3. 2.を必要な精度になるまで繰り返し計算. セカント法の更新式 $$x_{n+1} = x_n - f(x_n)\frac{x_n - x_{n-1}}{f(x_n) - f(x_{n-1})}\\ = \frac{x_{n-1}f(x_n) - x_nf(x_{n-1})}{f(x_n) - f(x_{n-1})}$$ 上記の式はニュートンの更新式 $$x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$$ の\(f'(x_n)\)を $$f'(x_n) \approx \frac{f(x_n)-f(x_{n-1})}{x_n-x_{n-1}}$$ としたものであることが容易にわかります. (ただし、余談ですがセカント法の方が先に使用されていました)