« ツバキ | トップページ | スイレン »

2015年2月 9日 (月)

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

http://yamada-kuebiko.cocolog-nifty.com/blog/cat20846022/index.html
2015年1月30日 (金)「√2 の話:その17:√2の求め方。ニュートン法:1」
↑ここで、こう書きました↓

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

素直で性質の良い関数だとこういう高速が出ます。
2次関数はそういう「たちのよい」関数です。
「たちの悪い関数」ってあるのか?どんな関数なんだろう?・・・

★「性質(たち)の良い」関数というのはこの場合、単調な関数です。
単調増加というのは、
関数 f があって
    x ≦ y ならば f(x) ≦ f(y)
であるとき、fは単調増加であるといいます。
「<」だけの時「狭義」単調増加、「≦」のとき広義単調増加といいます。
単調減少はその逆ですからここでは省きます。

★2次関数、f(x)=x^2 は0以上で単調増加ですね。
f(x)=x^2-2 も同じく。
ですから、ニュートン法を安心して適用してかまいません。
出発点が遠ければ収束までの回数がちょっと増えるかもしれませんが大したことではありません。

★では3次関数は?
f(x)=x^3 なら単調増加ですので、適当に移動して、ニュートン法でx軸との交点の近似値を求めることは問題ありません。
ところが
f(x)=x^3-x
だとどうなるでしょう?
Xxxx
こういうグラフになります。これは
f(x)=x(x-1)(x+1)
となりますので、
解は-1,0,+1
実にシンプル。おそらく誰でも見たことがあるのではないでしょうか?
3次方程式で、解が3つという単純明快な例ですね。

このグラフには極小値と極大値があります。
極小値(1/√3,-2/3√3)≒(0.5774, -0.3849)
極大値(-1/√3,2/3√3)≒(-0.5774, 0.3849)
{これ以降、対称性を利用して、x≧0の場合についてのみ考えます。xが負の領域は対称性で考えてください。}

・極小値をとるx=1/√3以降は、単調増加になりますので、(1/√3)<xの領域ではどこから出発しても「+1」に収束するだろうというのはおそらく間違いのないところでしょう。
・0<x<(1/√3)の領域ではどうでしょう?
単調減少のように見えます。ならば、0へ収束するのではないでしょうか。

★では数学実験に取り掛かりましょう。
↓こんなプログラムを用意しました。
!********************
! ニュートン法
DECLARE EXTERNAL FUNCTION f
DECLARE EXTERNAL FUNCTION g

FOR j = 0.44 TO 0.6 STEP 0.001
   LET x = j
   PRINT j;
   FOR i = 1 TO 20
      LET x1 = x - (f(x)/g(x))
      LET wrk = x   
      LET x = x1
      IF x=wrk THEN
         EXIT FOR
      END IF
   NEXT i
   PRINT i;
   PRINT x
NEXT j
END
!********************
EXTERNAL FUNCTION f(x)
LET f = x*x*x - x
END FUNCTION
!********************
EXTERNAL FUNCTION g(x)
LET g = 3*x*x - 1
END FUNCTION
!********************

★予備的チェックで
0.10≦x≦0.44 では、0に収束しました。
0.58≦x≦0.90 では、1に収束しました。
問題は
0.44≦x≦0.58 の区間なんです。

Newtonunstable
●このグラフで、赤い点は
FOR j = 0.44 TO 0.6 STEP 0.001
として、問題の区間を0.001のステップで調べました。
FOR i = 1 TO 10
ニュートン法の反復は10回までです。
ご覧いただきますと。
赤い点が跳ね回っているのがわかります。
0.44を過ぎるところまでは順調に0に収束していましたが
0.45の手前で-1に収束し
ついで+1に収束し
その後-1に収束しています。
なんだかなぁ。
さらにx=.573 の辺りから極小値を挟んで、暴れまわり、0.58を過ぎたところでやっと落ち着いて1に収束するようになりました。

●ニュートン法の反復回数を増やしてみました。
青い枠線のみで表示されているデータ点は
FOR j = 0.44 TO 0.6 STEP 0.001
FOR i = 1 TO 20
このように、ニュートン法の反復を20回にしてみた結果です。
すると「-1,0,+1」のどれかに収束するようではあります。

★グラフの極小点は(1/√3,-2/3√3)
大体(0.5774,-0.3849)です。
・ですから、極小点を過ぎたところから、解が1に収束する。これはいい。
・ところが、極小点より小さいところで
0.466<x<0.577 位の間で、0を飛び越して、向こう側の解「-1」に収束している。
0.447<x<0.466 あたりでは、-1だったり1だったり、不安定になっています。
0.447より小さいところで安定して0に収束していますね。

★何だかなぁ。
1/√3=0.5774 ですから、ここ(極小値)が一つの境になるのはわかります。
0.447 というのは何なんだ?
1/√5=0.4472 ですので、どうやら、1/√5が境になっているようだ、とは思うのですが。
ここに1/√5が登場する理由は、私の数学力ではわかりません。
1/√5という必然性が見つからなくって。どこから出てくるんだろうな。
でも、出てきちゃったみたいだしなぁ。
というのが観察結果でした。

★どうもこれ「カオス」という現象のようですね。
ウィキペディアから引用↓
http://ja.wikipedia.org/wiki/%E3%82%AB%E3%82%AA%E3%82%B9%E7%90%86%E8%AB%96

初期値鋭敏性
 カオスの定義あるいは特性として第一に挙げられるのが初期値鋭敏性(sensitivity to initial conditions)である[19][20][注釈 1]。これは、同じ系であっても初期状態に極僅かな差があれば、時間発展と共に指数関数的にその差が大きくなる性質である[5]。この性質は軌道不安定性(orbital instability)とも言い換えられることもある[24][25][26]。定量的には、この初期値鋭敏性は、リアプノフ指数、コルモゴロフ-シナイエントロピーなどで評価される[25][27]。
 初期値鋭敏性により極めて小さな差も指数関数的に増大していくので、初期値鋭敏性を有する実在の系の将来を数値実験で予測しようとしても、初期状態(入力値)の測定誤差を無くすことはできないので、長時間後の状態の予測は近似的にも不可能となる[28][25][26]。このような性質は長期予測不能性(long-term unpredictability)[25]や予測不可能性(unpredictablity)[28]などとも呼ばれる。一方で、例えカオスであっても決定論的法則から発生されるものであるため、短時間内であれば有用な予測は可能といえる[29][14]。以上のような性質は、標語的にバタフライ効果(butterfly effect)と呼ばれる。

バタフライ効果というのは↓
http://ja.wikipedia.org/wiki/%E3%83%90%E3%82%BF%E3%83%95%E3%83%A9%E3%82%A4%E5%8A%B9%E6%9E%9C

バタフライ効果(butterfly effect)という表現は、気象学者のエドワード・ローレンツが1972年にアメリカ科学振興協会で行った講演のタイトル"Predictability: Does the Flap of a Butterfly's Wings in Brazil Set Off a Tornado in Texas?"(予測可能性:ブラジルで1匹の蝶がはばたくとテキサスで竜巻が起こるか?)[17]に由来すると考えられている[18][19]。ローレンツによると、ローレンツ自身は初期値鋭敏性の象徴として元々はカモメを使っていたが、この学会の主催者で気象学者のフィリップ・メリリースが蝶に変更したことで、この講演タイトルとなった[20]。蝶の方が儚げで弱そうなものに見えるので、大きなものを生み出し得る小さなものの象徴に最適と判断したのだろうと、ローレンツはこの変更理由を推測している[20][† 1]。

有名ですね。
ニュートン法で解を求めるときに、出発点の微小な違いが結果として大きな帰結を生む、ということのようなのです。
私の実験は、「STEP 0.001」で刻んでいますし、十進15桁で計算を行っています。
これはかなり「荒っぽい」といえますね。
刻み幅をもっとずっと小さくし、1000桁モードなども使って、精細に行ったら、もっと「カオス」的な状況がくっきりと見えてくるのかもしれません。
{それだけの気力がなくってスミマセン}
興味を覚えた方は是非もっと追及してください。

« ツバキ | トップページ | スイレン »

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

コメント

コメントを書く

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

« ツバキ | トップページ | スイレン »

2017年11月
      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 暴想
無料ブログはココログ