Newton法で平方根を求める - 元データ分析の会社で働いていた人の四方山話

これは？

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

考え方の流れ

$\sqrt{a}= x$ とする
両辺２乗すれば
$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を求めていく。
実装上は更新の前後で、予測値の変動が閾値以下であれば更新を終了し、その時点での予測値を解とする。

参考

素晴らしいイメージ図
http://www.akita-pu.ac.jp/system/elect/comp1/kusakari/japanese/teaching/Programming/2005/note/6/Slide03.html