読者です 読者をやめる 読者になる 読者になる

Newton法で平方根を求める

これは?

SICPの1.1.7節の「Newton法による平方根」を行うにあたって、再度Newton法を復習した過程。

考え方の流れ

\sqrt{a}= xとする
両辺2乗すれば
a = x^2となる
整理して
x^2 - a = 0
これは
y = f(x) = x^2 - aのグラフのy = 0 を満たすx(ただし、平方根なのでx>0)を求めることに相当する。
今、適当な初期の予測値x_0を用いると
y = f(x_0) = x_0^2 - a
となる。
一方、f(x)の接線の傾きはf'(x) = 2xである。
x_0におけるf(x)の接戦がx軸と交わる点をx_1とすると
傾き = (y軸方向の移動 / x軸方向の移動)
であるから、
2x_0 = \frac{f(x_0)}{x_0 - x_1}
となる。
これをx_1について整理すると
x_1 = \frac{x_0 + \frac{a}{x_0}}{2}
となる。
これを一般化すると
x_{i+1} = \frac{x_i+ \frac{a}{x_i}}{2} (i = 0, 1,...)
となる。
これに従って初期の予測値から、上記の更新式に従って条件を満たすy=f(x)=0を満たすxを求めていく。
実装上は更新の前後で、予測値の変動が閾値以下であれば更新を終了し、その時点での予測値を解とする。