√２ の話：その１７：√２の求め方。ニュートン法：１

★√２を求める話も終わりに近づいておりまして、今回は有名なニュートン法です。
例によって話は√２、あるいはせいぜい平方根程度に限定します。

f(x) = x^2 - 2
という曲線上に(Xn, f(Xn))という点を考えます。
この点で曲線に接線を引きます。
接線がｘ軸と交わる点をXn+1とします。
(Xn+1, f(Xn+1))での接線を引き、ｘ軸と交わる点を・・・
という繰り返しを考えます。
図の中に、Xn から Xn+1 を求める式を書き込んでおきました。
これを使ってプログラムを作ります。

!********************
! ニュートン法によって平方根を求める
DECLARE EXTERNAL FUNCTION f
DECLARE EXTERNAL FUNCTION g

!1.4142135623730950488016887242097
!1.7320508075688772935274463415059

INPUT PROMPT "n =" :n
IF n >=1 THEN
   LET x = n
ELSE
   LET x = 1
END IF

FOR i = 1 TO 15
   LET x1 = x - (f(x, n)/g(x))
   PRINT i;
   PRINT x1
   PRINT x1*x1
   LET x = x1
NEXT i
END
!********************
EXTERNAL FUNCTION f(x, n)
LET f = x*x - n
END FUNCTION
!********************
EXTERNAL FUNCTION g(x)
LET g = 2*x
END FUNCTION
!********************

★実にシンプルですが、その威力はものすごい。

n =2
1
1.5
2.25

2
1.41666666666667
2.00694444444445

3
1.41421568627451
2.00000600730488

4
1.41421356237469
2.00000000000451

5
1.4142135623731
2.00000000000001

6
1.4142135623731
2.00000000000001

1.4142135623730950488016887242097　←少し長めの値と比べてください。

５回ループを回ったところでもうこの計算精度は満たしてしまいました。
一回ごとに有効桁数が２倍くらい増すんですね。
実にとんでもないスピードです。

http://www.akita-nct.ac.jp/yamamoto/lecture/2005/5E/nonlinear_equation/text/html/node4.html

i+1番目の近似値は、i番目に比べて2乗で精度が良くなるのである。これを、 二次収束と言い、非常に早く解に収束する。例えば、 10^{-3} の精度で近似解が得られ ているとすると、もう一回式(9)を計算するだけで、 10^{-6}程度の精度で近似解が得られるということである。一次収束の二分法よりも、収 束が早いことが分かる。

ニュートン法の特徴をまとめると次のようになる。
長所
    初期値が適当ならば、収束が非常に早い(図 8)。
短所
    初期値が悪いと、収束しない(図9)。収束 しない場合があるので、反復回数の上限を決めておく必要がある。

素直で性質の良い関数だとこういう高速が出ます。
２次関数はそういう「たちのよい」関数です。
「たちの悪い関数」ってあるのか？どんな関数なんだろう？・・・
１０００桁モードでやったらどうなるんだ？など。
いくつかの話が頭の中を往来していまして、まとまらない。
それらは別に稿を改めることにします。