SICP Lite #4

今回で4回目。ようやく1章の終わりが見えてきた感じですが、何となく大事なことが置いてけぼりの感じもしています。

とりあえず、SICPを読む上で、最も難関と言われる数学の話。第1章の主題は、単純な手続きを抽象化する方法を身につけて、汎用な関数を作り上げる、と言うものなので、数学に捕われていると主題を忘れてしまいます。しかし、悲しいことに、ある程度数学を抑えとかないと後半の高階関数による汎用化のところはポイントが抑えられないのも事実。

と言うことで、ごくごく簡単にSICPの中に出てきている数値解析の技法の絵を描いてみました(昨日も書けば良かったんだけど、ホワイトボードのところに行きつけなくて)。

• Binary Search

　言わずと知れた2分探索。別名、挟み撃ち法。直感で分かりやすいんだけど、収束性が良くないので、非線形方程式の解法に使われることはほとんどない。

• Fixed Point

不動点。なぜかSICPでは、不動点がやたらと出てくる(1章だけだったと思うけど)。これの本質は、f(x) = xと言うことで、予測値が解が近づいて行けば、変動量が減るので、解に吸い付くように収束して行くこと。
　SICPの本の中では、square rootの計算に使われていたので、それを絵にしてみた(ちょっと、一部ウソがある)。

　最初の更新式、x(n+1) = k / x(n)だと、解の周りを振動するだけなので、適当な緩和項を付けてやる必要があります。この場合は、x(n+1) = 1/2 * (x(n) + k/x(n))と言うように、平均を取ってやって、移動量を制限してやってます。

• Newton Raphson法

　ニュートン法。解の近似に勾配を利用するので、結構早く収束します。通常、非線形方程式の数値解法と言うとコレ。

と言うことで、下手クソな絵を書いてみたのだけど、これで少し理解の助けになるかな？
冒頭でも書いたけど、この章の主題は抽象化であり、数学的なことではな無いです。なので、色んな形で定義されているsqrtの手続きを並べてみて、どのように抽象化されていっているかを追うのがいいかもしれないですね。