【プログラミング】末尾再帰を使って反復法（ニュートン法）を実装する【Kotlin】

プログラミング Kotlin

wrongwrong163377.hatenablog.com
続きです。
数値解析などで用いる反復法も末尾再帰で書いたほうがシンプルになりました。
ということで、今回は例としてニュートン法を実装します。
ニュートン法の解説はネット上にきちんとしたものが有ると思うので飛ばします。

実装

解説は大体コメントに書きました。
閾値にはFloat.MIN_VALUEを指定していますが、これは計算機的に十分小さな値という意味で指定しています。

import kotlin.math.abs

tailrec fun newton(
    f: (Double)-> Double, //f(x)
    df: (Double)-> Double, //f'(x)
    x: Double, //目的の数値
    eps: Double = Float.MIN_VALUE.toDouble() //閾値、floatの最小非0の値
): Double {
    val xnew = x - f(x) / df(x) //値を計算
    if(abs(xnew - x) < eps) return xnew //閾値を下回れば終了
    return newton(f, df, xnew, eps) //それ以外は末尾再帰
}
使う

f(x) = x^3 - 2として以下のように使います。ただし初期値は収束するなら何でもOKです。

val ans = newton(
    { x -> x * x * x - 2.0 },
    { x -> 3.0 * x * x },
    3.0
)
println("$ans, ${ans * ans * ans}")

これの答えは 2^{\frac{1}{3}}になります。3乗すると大体2になっていることが分かります。

1.2599210498948732, 2.0

汎化

上記ニュートン法の実装では簡単のために漸化式を関数内で実装しましたが、実際には漸化式を渡して貰えば反復法を行うことができます。
漸化式を受け取る形で汎化したものが以下です。

tailrec fun iteration(
    r: (Double)-> Double, //漸化式
    x: Double, //目的の数値
    eps: Double = Float.MIN_VALUE.toDouble() //閾値、floatの最小非0の値
): Double {
    val xnew = r(x)
    if(abs(xnew - x) < eps) return xnew //閾値を下回れば終了
    return iteration(r, xnew, eps) //それ以外は末尾再帰
}

参考記事

ニュートン法の実装と例題は以下の記事を参考にさせていただきました。
qiita.com

2018/12/14追記

無名関数を使っていなかったので修正。