https://tsujimotter.hatenablog.com/entry/approximation-of-square-roots-and-newton-method

突然ですが、数列の問題について考えたいと思います。

数列の初項を

$x_0 = 2$

として

$\displaystyle x_{n+1} = \frac{1}{2} \left(x_{n} + \frac{2}{x_n}\right) \tag{1}$

という規則で $x_1, x_2, x_3, \ldots$ を順次計算していきます。

このとき、 $x_n$ は $n\to \infty$ で、どのような値に収束するでしょうか。

実際、最初の方を数値計算してみると

$x_0 = 2$

$x_1 = 1.5$

$x_2 = 1.416666667$

$x_3 = 1.414215686$

$x_4 = 1.414213562$

$x_5 = 1.414213562$

というようになり、どこかで見たことのある数に収束します。

この漸化式の背景にある考え方について今日は議論したいと思います。

どこに収束するのか？

実際、 $n\to \infty$ の極限においては、 $\displaystyle x = \lim_{n\to \infty} x_n = \lim_{n\to \infty} x_{n+1}$ であると考えると

$\displaystyle x = \frac{1}{2} \left(x + \frac{2}{x}\right)$

より

$\displaystyle 2x = x + \frac{2}{x}$

移項して両辺に $x$ を掛けると

$\displaystyle x^2 = 2$

となります。

結局、 $x_n > 0$ より

$\displaystyle x = \lim_{n\to \infty} x_n = \sqrt{2}$

であることが分かるというわけです。

より一般に、数列を

$\begin{cases} \displaystyle x_0 > 0 \\ \displaystyle x_{n+1} = \frac{1}{2} \left(x_{n} + \frac{N}{x_n}\right) \end{cases} \tag{2}$

とすると、 $x_n$ は $n\to \infty$ の極限で $\sqrt{N}$ に収束します。

なかなか面白いですね！

テイラー展開を使った平方根の近似

今日はこの背景について考えたいと思うのですが、2通りの方法で考えたいと思います。

一つは、平方根の近似です。

$x$ の絶対値が十分小さい実数値であるとき、

$\displaystyle \sqrt{1 + x} \fallingdotseq 1 + \frac{x}{2} \tag{3}$

と近似できるというものです。

これは、 $(1 + x)^{\alpha}$ の $x = 0$ の周りでのテイラー展開

$\displaystyle (1 + x)^{\alpha} = 1 + \alpha x + \frac{\alpha (\alpha - 1)}{2!} x^2 + \frac{\alpha (\alpha - 1) (\alpha - 2)}{3!} x^3 + \cdots \tag{4}$

において、 $x^2$ 以降を打ち切ったものと思うことができます。正確には $\alpha = 1/2$ の場合です。

この式は、一般化二項展開

$\displaystyle (x + y)^{\alpha} = x^{\alpha} + \alpha x^{\alpha -1}y + \frac{\alpha (\alpha - 1)}{2!} x^{\alpha - 2}y^2 + \frac{\alpha (\alpha - 1) (\alpha - 2)}{3!} x^{\alpha - 3}y^3 + \cdots \tag{5}$

の特殊ケースだと思ってもいいです。

いずれにしても、このような近似だと思うことで、最初の数列の漸化式を得ることができるのでやってみましょう。

まず、 $\sqrt{N}$ の近似として、適当は正の数 $x_0$ を考えましょう。

適当に選んだものであれば、 $x_0$ と $\sqrt{N}$ は一致しないので、これを二乗した $x_0^2, \; N$ の差を $\varepsilon$ とすると

$x_0^2 - N = \varepsilon$

を満たします。

よって

$N = x_0^2 - \varepsilon$

となりますが、この両辺の平方根を取りましょう。

すると

$\begin{align*} \sqrt{N} &= \sqrt{x_0^2 - \varepsilon} \\ &= x_0 \sqrt{1 - \frac{\varepsilon}{x_0^2}} \end{align*}$

となります。ここで、 $|\varepsilon|$ は $x_0^2$ と比べて十分小さいとすると、平方根のテイラー展開の1次近似より

$\begin{align*} \sqrt{N} &= x_0 \sqrt{1 - \frac{\varepsilon}{x_0^2}} \\ & \fallingdotseq x_0 \left(1 - \frac{\varepsilon}{2x_0^2}\right) \\ & = x_0 - \frac{\varepsilon}{2x_0} \end{align*}$

が得られます。 $\varepsilon = x_0^2 - N$ を戻すと

$\displaystyle \sqrt{N} \fallingdotseq x_0 - \frac{x_0^2 - N}{2x_0} \tag{6}$

が得られます。この式は後で重要になるので、式番号をつけておきます。

右辺の計算を進めると

$\displaystyle \begin{align*} \sqrt{N} &\fallingdotseq x_0 - \frac{x_0^2 - N}{2x_0} \\ &= x_0 - \frac{x_0}{2} + \frac{N}{2x_0} \\ &= \frac{1}{2} \left(x_0 + \frac{N}{x_0} \right) \end{align*}$

となり、先ほどの $\sqrt{N}$ に収束する漸化式 $(2)$ が現れました。

実際、

$\displaystyle x_1 = \frac{1}{2} \left(x_0 + \frac{N}{x_0} \right)$

とすれば、 $x_0$ より $x_1$ の方が $\sqrt{N}$ の近似精度が高くなります。

改めて $x_0$ の代わりに $x_1$ として同じ計算を行うことで $x_2 = \frac{1}{2} \left(x_1 + \frac{N}{x_1} \right)$ が得られます。これを続けて行ったものが、式 $(2)$ の漸化式だったというわけですね。

ニュートン法

もう一つ別の見方をしてみましょう。

ニュートン法は、 $f(x) = 0$ という形の方程式の解 $x$ を求めるための方法の一つです。一気に解を求めるのではなく、 $x = x_0$ を適当に置いて、この値を順次 $x_1, x_2, x_3, \ldots$ と更新していくことで、徐々にこの数列を解に近づけていくという方法です。

ニュートン法の解説をするために、具体的に考えたいと思います。今回の場合は、 $x = \sqrt{N}$ を解としたいので、

$\displaystyle f(x) = x^2 - N \tag{7}$

としてニュートン法を適用します。

やりたいことは、 $f(x) = 0$ となる解を求めることです：

ここで、適当に $x_0$ をとります。図では $x_0 = 2$ としています。このときの関数値は $f(x_0)$ です。

$x = x_0$ における接線を求めると

$y = f'(x_0) (x - x_0) + f(x_0) \tag{8}$

となります。接線の傾きが $f'(x_0)$ であり、接点の座標が $(x_0, \; f(x_0))$ であることに注目すると、接線がこの形になることは明らかですね。

この接線と $y = 0$ の直線（ $x$ 軸）の交点の $x$ 座標を次の候補 $x_1$ とするというのが、ニュートン法のポイントです。

式 $(8)$ と $y = 0$ の交点は

$f'(x_0) (x - x_0) + f(x_0) = 0$

より

$\displaystyle x_1 = x_0 - \frac{f(x_0)}{f'(x_0)} \tag{9}$

とできます。

図の例では、 $x_1 = 1.5$ と計算されます。この方が $x_0 = 2$ より、解である $x = \sqrt{2}$ に近いことが分かりますね。

同様に $x = x_1$ における接線を計算すると

$y = f'(x_1) (x - x_1) + f(x_1)$

となります。この接線と $y = 0$ の交点を計算すると

$\displaystyle x_2 = x_1 - \frac{f(x_1)}{f'(x_1)}$

となり、この $x_2$ は先ほどの $x_1$ より解に近づきます。

こんな要領で、 $x_0$ から始めて $x_1, x_2, x_3, \ldots$ と $x$ 座標を更新することで、よりよい解を次々に得ていくという方法がニュートン法です。

一般的な更新式は

$\displaystyle x_{n+1} = x_{n} - \frac{f(x_{n})}{f'(x_{n})} \tag{10}$

となります。

ここで今回の例では $f(x) = x^2 - N$ であったことを思い出すと

$\displaystyle x_{n+1} = x_{n} - \frac{x_{n}^2 - N}{2x_{n}} \tag{11}$

となりますが、これは「平方根のテイラー展開」のときに現れた式 $(6)$ の右辺とまったく一緒であることに注意しましょう。

したがって、同様に計算すると

$\displaystyle \begin{align*} x_{n+1} &= x_{n} - \frac{x_{n}^2 - N}{2x_{n}} \\ &= x_{n} - \frac{x_{n}}{2} + \frac{N}{2x_{n}} \\ &= \frac{x_{n}}{2} + \frac{N}{2x_{n}} \\ &= \frac{1}{2} \left(x_n + \frac{N}{x_{n}} \right) \end{align*}$