Go言語 (Tour of Go) で数値解析 〜ニュートン法〜

この記事は数学 Advent Calendar 2015 15日目の記事です。


エウレカでは写真撮影と開発をしてるエンジニアの金子です。

大学時代は数学を専攻しており、現在も最適化理論と統計学の分野を土日に暇を見つけては勉強をしています。今年の5月にも「プログラマのための数学勉強会」にて最適化理論の発表をさせて頂きました。

さて、今回は数学(+Go言語)について書きたいと思います。

Go Tour と ニュートン法

Go言語に少しでも触れたことがある方は Go Tour というページをご存知かと思います。
Goの基本構文から並行処理 (go routine, channel) の使い方まで広く解説しているページです。

この Go Tour の途中にエクササイズとしてニュートン法が出現します。

Rplot01

Tour of Go – #24 Exercise: Loops and Functions

package main

import (
    "fmt"
)

func Sqrt(x float64) float64 {
}

func main() {
    fmt.Println(Sqrt(2))
}

上のコードがPlaygroundに存在します。ここの Sqrt 関数の中身を実装することになります。

Exercise: Loops and Functions
関数とループを使った簡単な練習として、 ニュートン法 を使った平方根の計算を実装してみましょう。
ニュートン法は、開始点 z を選び、以下の式を繰り返すことによって、 Sqrt(x) を近似します:

と、いきなり解説もせずに数式が出てきます。プログラマだったらどんなときでも理由が欲しいですよね。

ニュートン法とは?

ニュートン法とは、別名ニュートン・ラフソン法とも呼ばれている非線形方程式の解を求めるアルゴリズムの一つです。

収束する速さは2次収束のため、高速に解を求めることができるため古くから使用されています。

Screen Shot 2015-12-15 at 4.24.39 PM

ニュートン法の導出

Screen Shot 2015-12-15 at 4.24.39 PM

この数式は、端的に言えば「関数をテイラー展開し、1次近似した式を漸化式として定義し、今回の問題である “平方根が解” となる関数式を当てはめた。」ただ、それだけです。
やっぱり、意味が分からないので順を追って説明させていただきます。

関数の導関数

みなさん、関数の導関数は高校2年生の必修科目だったはずなので、よく知っている式だと思います。

Screen Shot 2015-12-15 at 4.37.10 PM

ここで、上式にある x を h の大きさ(なるべく小さく)分割することを考えます。

Screen Shot 2015-12-15 at 4.37.15 PM

そうすれば、導関数は下式のように表すことができます。

Screen Shot 2015-12-15 at 4.37.19 PM

先ほど定義した大きさ h を刻み幅と考えて1次近似させると

Screen Shot 2015-12-15 at 4.37.23 PM

1次近似式

先ほど得た近似式を変形させると

Screen Shot 2015-12-15 at 4.37.27 PM

となり、この式にて x 軸上となる x を求めることを考える

Screen Shot 2015-12-15 at 4.37.31 PM

これにより、i 番目の x の情報で f(x)=0 となる x の値(i+1 番目)を求めることが可能となった。(ニュートン法)

ニュートン法の公式

つまり、下式。

Screen Shot 2015-12-15 at 4.37.38 PM

ちなみに…

1次導関数と x 軸上との交点という点から考えれば、これは接線方程式が y=0 となる x を求めることとなんら変わり無い

Screen Shot 2015-12-15 at 4.37.43 PM

のとき

Screen Shot 2015-12-15 at 4.37.46 PM

とすれば接線と x 軸との交点が求まる。

つまり、導関数の1次近似は接線方程式となる(というより、1次式にみなしているためである)

平方根が解となる関数

さて、今回の問題の平方根が解となる関数式は、下記で定義される

Screen Shot 2015-12-15 at 4.37.50 PM

この関数の導関数(微分式)は

Screen Shot 2015-12-15 at 4.37.54 PM

である。

以上より、ニュートン法へ平方根が解となる関数を当てはめると

Screen Shot 2015-12-15 at 4.37.58 PM
Go Tourの式に合わせるとすれば、

Screen Shot 2015-12-15 at 4.38.02 PM

と置けば十分である。

Go Tour #24の解答

package main

import (
    "fmt"
)

func Sqrt(x float64) float64 {
    z := 1.0
    for i := 0; i < 10; i++ {
        z = z - (z*z-x)/(2*z)
    }
    return z
}

func main() {
    fmt.Println(Sqrt(2))
}

z := 1.0 の初期値を与え、10回のループで z を更新し、その z を最後に返却することになります。

他の平方根アルゴリズム

有名なところで、高速な平方根のアルゴリズムをオンラインゲームで活用している事例があります。
これはアルゴリズムがメタっぽいですが、事実上高速です。

おわりに

弊社で開催するGo言語の勉強会(GOもくもく会(ごもくかい))にて Go Tour の疑問なども随時お答えできますので、是非ご参加ください!

939e2d63f1e05ec09c4c284a5aa5be86

  • このエントリーをはてなブックマークに追加

エウレカでは、一緒に働いていただける方を絶賛募集中です。募集中の職種はこちらからご確認ください!皆様のエントリーをお待ちしております!

Recommend

Go言語初心者がハマった2つのポイント

デザインレビューやエンジニアとのやりとりに役立つ!デザイナーでも簡単にGitで画像管理する方法