黄昏より暗きもの、血の流れより赤きもの

黄昏より暗きもの、血の流れより赤きもの

自分の好きな事を好きなように書いて行きます。

【数値計算】練習のためニュートン法で√2の近似値を求めてみた

ニュートン法とは?

今日は数値計算の練習のため、ニュートン法を実装したのでその様子を紹介したい。ニュートン法とは例えば「二次方程式x^2 = 2の正の解の近似値を求めよ」と言った、方程式の解の近似値を求める時に使われる。具体的な手順は以下の通り。


f:id:program_study:20150411175905p:plain
図はwikipediaより

(1):まず実数x_0を適当に定める。
(2):x=x_0とy=f(x)との交点の座標をP_1とする。このときf(x)の点P_1における接線lを引き、lとx軸との交点をx_2とする。
(3):この操作をn回繰り返し、最終的に得られたx_nを方程式f(x)=0の近似値として採用する。一般的には正の数\epsilonに対し、x_n - x_{x-1} < \epsilonとなるまで計算を繰り返す。

さてここで P_{n} (x_{n},y_{n})における接線lの式は、y - f(x_n) = f'(x_n) (x - x_n)。ここでP_{n+1} (x_{n+1},0)との交点は、

0 - f(x_n) = f'(x_n) (x_{n+1} - x_n)
<=> - \frac{f(x_n)}{f'(x_n)} = x_{n+1} - x_n
x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}

となる。さてf(x) = x^2 - a (aは正の整数)であるとき、方程式f(x) = 0の正の解は x = \sqrt{a} となり、この近似値x_nを考える。さてf'(x) = 2xより

x_{n+1} = x_n - \frac{{x_n}^2 - a}{2x_n}
 = \frac{1}{2}(x_n + \frac{a}{x_n})

とこのように漸化式で表せる。ここで漸化式を使うメリットは1,2,3,4,.....,nと言ったように離散的に値が変化するため、プログラム側の再帰やforループで処理できるようにするためだ。この発想はシンプソンの台形公式を使って、関数f(x)の定積分の近似値を離散的に求めるとき*1にも応用される。


プログラムについて。誤差\epsilonの評価の所で二度関数を呼び出す結果となった。「Newton法による方程式の近似解法(琉球大学)」に依れば、x_nをそのまま引数に取って計算すれば、関数を二度呼び出さずに済んだ事が分かった。

ちなみに実行結果は以下の通り。小数点第3位まではクリアできた。それ以降の精度をどうするべきかが悩み所だ。

プログラムの実行結果

XXXXXX-no-MacBook-Air:Documents XXXXXX$ gcc newton2.c
XXXXXX-no-MacBook-Air:Documents XXXXXX$ ./a.out
1.414214