« 芽生え | トップページ | 影 »

2015年1月30日 (金)

√2 の話:その17:√2の求め方。ニュートン法:1

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

Newtonmethod
f(x) = x^2 - 2
という曲線上に(Xn, f(Xn))という点を考えます。
この点で曲線に接線を引きます。
接線がx軸と交わる点をXn+1とします。
(Xn+1, f(Xn+1))での接線を引き、x軸と交わる点を・・・
という繰り返しを考えます。
図の中に、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 ←少し長めの値と比べてください。

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

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)。収束 しない場合があるので、反復回数の上限を決めておく必要がある。

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

« 芽生え | トップページ | 影 »

理科おじさん」カテゴリの記事

コメント

コメントを書く

(ウェブ上には掲載しません)

« 芽生え | トップページ | 影 »

2017年9月
          1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
サイト内検索
ココログ最強検索 by 暴想
無料ブログはココログ