ニュートン法

二分法では、$\epsilon$を半分ずつにすることで探索の効率を高めました。 より効率を高める方法はあるでしょうか？

$x$が$n$の平方根であるということを、$x$が以下の方程式の解であると言い換えることにしましょう。

$$f(x) = x^2 - n = 0$$

この方程式の近似解が高速に求まれば平方根が得られそうです。

ここで、解$x$に近い$a$を考えましょう。 $f(x) = 0$の解は、$f(x)$の$a$における接線が$y = 0$となる$x = a'$で近似できます。

$f(x)$の$a$における接線の方程式は以下になります。

$$y = 2ax - a^2 - n$$

$y = 0$のとき、$a' = \frac{a^2 + n}{2a}$ です。 このときの$a'$を新たに$a$と置くことで、$a$が徐々に真値$x$に近づいていきます。

この方法は ニュートン法 と呼ばれる非線形方程式の数値解法です。 $x$を n からはじめて、$\epsilon \geq \left| \sqrt{n} - x \right|$となるまで以下の更新を繰り返すことで平方根が得られます。

$$x \leftarrow \frac{x^2 + n}{2x}$$

この更新式は「バビロニア人の方法」と呼ばれる平方根の計算法とも一致します。 平方根の計算において、これらの方法は非常に収束が速い（速く真値に近く）ことが知られています。

二分法では 1 回の繰り返しで誤差が$\frac{1}{2}$になります。 ニュートン法において、近似値$a$から次の近似値$x$が求まったとき、誤差の比は以下のようになります。

$$\frac{x - \sqrt{n}}{a - \sqrt{n}} = \frac{1}{2}\left( 1 - \frac{\sqrt{n}}{a} \right)$$

$a > \sqrt{n}$であるため、この比は必ず$\frac{1}{2}$より小さくなります。 すなわち、比が常に$\frac{1}{2}$である二分法と比較して、ニュートン法の方がより速く収束します。