平方根の近似（ニュートン法）
平方根の近似
$c > 0$とする. $\sqrt{c}$ は次の漸化式で与えられる数列 $\{ a_n\}_n$ で近似できる. $$a_{n+1} =\frac{1}{2}\left(a_n + \frac{c}{a_n}\right)$$
ただし, $a_1 > 0$ とする.
漸化式 $\displaystyle a_{n+1} =\frac{1}{2}\left(a_n + \frac{c}{a_n}\right)$ で与えられる数列 $\{a_n\}$ が $\sqrt{c}$ の近似になっていることを確かめてみよう。
例えば, 漸化式 $\displaystyle a_{n+1} = \frac{1}{2} \left( a_n + \frac{2}{a_n} \right)$, $a_1 = 1$ は $$1, \ \frac{3}{2}, \ \frac{17}{12}, \ \frac{577}{408}, \ \cdots $$ です。これを小数にすると, $1$, $1.5$, $1.416\cdots$, $1.414215 \cdots$, $\cdots $ となり $\sqrt{2}$ に近似していっています！
解説.
方程式 $x^2 = c$ をもとに, 関数 $f(x) = x^2-c$ を定義する. ニュートン法によって, $\sqrt{c}$ に収束する数列 $\{a_n\}$ を以下のように定義しよう.
まず, 漸化式から $a_n>0$ であれば, $a_{n+1}>0$ であることは自明であることに注意しておく. $a_1>0$ であるため, 任意の自然数 $n$ に対して $a_n>0$ である.
初期値 $a_1$ が $\sqrt{c}$ でない場合, $n \geqq 2$ で $a_n$ は $\sqrt{c}$ よりも大きい. なぜならば, $a_n >0$ かつ $\displaystyle \frac{c}{a_n}>0$ であることと, 相加平均・相乗平均の関係より $$\begin{aligned}
a_{n+1} &= \frac{1}{2}\left(a_n + \frac{c}{a_n}\right)\\
& \geqq \frac{1}{2} \cdot 2 \sqrt{a_n \cdot \frac{c}{a_n}} \\
& = \frac{1}{2} \cdot 2 \sqrt{c} \\
& = \sqrt{c}
\end{aligned}$$
等号成立は $a_n=\sqrt{c}$ のときのみであるが, 初期値が $\sqrt{c}$ でない限り, この場合は起こらない.
初期値が $a_1 = \sqrt{c}$ であった場合, $a_n=\sqrt{c}$ の定数列となるため, この場合は既に近似列が得られているとして, 除外する.
したがって, 少なくとも $n \geqq 2$ において, $a_n > \sqrt{c}$ である.
関数 $y=x^2-c$ の $x=a_1$ での接線 $$y = 2a_1(x-a_1) + (a_1^2-c)$$ を考え, その接線と $x$ 軸が交わる点の座標を $a_2$ とする.
$y=0$ として変形すると, $\displaystyle a_{2} =\frac{1}{2}\left(a_1 + \frac{c}{a_1}\right)$ となる.
$c=2$, $a_1=2$ である場合, $y=x^2-2$ の $x=2$ での接線 $y=4(x-2)+2$ が $x$ 軸と交わる点の座標は $(1.5, 0)$ となる. $a_2=1.5$ とする.
初期値が $a_1 < \sqrt{c}$ である場合, $y=x^2-c$ の $x=a_1$ での接線が $x$ 軸と交わる交点を考えると $\sqrt{c}$ よりも大きい位置になる.
この作業を帰納的に繰り返していくと, $\{a_n\}$ は $x=\sqrt{c}$ に右から近づく収束列として定義されることとなる.
$y=x^2-c$ の $x = a_n$ での接線の方程式は $y = 2a_n(x-a_n) + (a_n^2-c)$ である. $y=0$ のときの $0 = 2a_n(x-a_n) + (a_n^2-c)$ を解くと, $\displaystyle x =\frac{1}{2}\left(a_n + \frac{c}{a_n}\right)$ を得る. この $x$ の値を $a_{n+1}$ と定めたため, $$\displaystyle a_{n+1} =\frac{1}{2}\left(a_n + \frac{c}{a_n}\right)$$ という漸化式を得る.
ゆえに, この漸化式で与えられる数列 $\{ a_n \}$ は $\sqrt{c}$ の近似列となっている.
わかり安かった🐙