ニュートンの反復法#
- 図のように、曲線 $y=f (x)$ において、$f (x_n)$ の位置に接線を引き、x 軸と交わる点を $x_{n+1}$ とする。そして、$f (x_{n+1})$ の位置に接線を引き、x 軸と交わる点を $x_{n+2}$ とする。このプロセスを繰り返す。
- このプロセスにより、交点 $x_{n+m}$ は曲線の零点に無限に近づき、つまり方程式 $f (x) = 0$ の解を得ることができる。
平方根の求め方#
アイデア#
- 関数 $f (x) = x^2 - n$ の零点を求める
- 導関数 $f^{'}(x) = 2x$
- 点 $(x_n, x_n^2-n)$ における接線の方程式は $y - x_n^2 + n = 2x_n (x-x_n)$ であり、つまり $y = 2x_nx - x_n^2 - n$ となる
- したがって、接線と x 軸の交点 $x_{n+1}$ はとなる
- このプロセスを精度が満足できる値が得られるまで繰り返す
コードの実装#
package main
import (
"fmt"
"math"
)
func Sqrt(x float64) float64 {
z := 1.0
for math.Abs(z * z - x) > 1e-12 {
z -= (z * z - x) / (2 * z)
}
return z
}
func main() {
fmt.Println(Sqrt(2))
}
k 次方根の求め方#
アイデア#
コードの実装#
package main
import (
"fmt"
"math"
)
func getRoot(x, k float64) float64 {
z := 1.0
for math.Abs(math.Pow(z, k) - x) > 1e-9 {
z -= z * (1 - x * math.Pow(z, -k)) / k
}
return z
}
func main() {
fmt.Println(getRoot(27, 3))
}
ベンチマーク(二分探索との比較)#
実装とテスト#
// sqrt.go
package sqrt
import "errors"
const EPSILON = 1e-8
var ErrNegativeSqrt = errors.New("負の数の平方根は求められません")
type Float interface {
float64 | float32
}
func abs[T Float](x T) T {
if x < 0 {
return -x
}
return x
}
func SqrtWithNR[T Float](num T) (T, error) {
if num < 0 {
return 0, ErrNegativeSqrt
}
z := T(1.0)
for abs(z*z-num) > EPSILON {
z -= (z*z - num) / (2 * z)
}
return z, nil
}
func SqrtWithBS[T Float](num T) (T, error) {
if num < 0 {
return 0, ErrNegativeSqrt
}
l, r := T(0.0), num
for abs(l*l-num) > EPSILON {
m := (l + r) / 2
if m*m > num {
r = m
} else {
l = m
}
}
return l, nil
}
// sqrt_test.go
package sqrt_test
import (
"math"
"sqrt"
"testing"
)
func TestSqrtWithNR(t *testing.T) {
for i := 0; i < 10; i++ {
num := float64(i)
if z, err := sqrt.SqrtWithNR(num); err != nil {
t.Error(err)
} else if math.Abs(z*z-num) > sqrt.EPSILON {
t.Errorf("%f != %f", z*z, num)
}
}
}
func TestSqrtWithBS(t *testing.T) {
for i := 0; i < 10; i++ {
num := float64(i)
if z, err := sqrt.SqrtWithBS(num); err != nil {
t.Error(err)
} else if math.Abs(z*z-num) > sqrt.EPSILON {
t.Errorf("%f != %f", z*z, num)
}
}
}
func BenchmarkSqrtWithNR(b *testing.B) {
for i := 0; i < b.N; i++ {
sqrt.SqrtWithNR(float64(i))
}
}
func BenchmarkSqrtWithBS(b *testing.B) {
for i := 0; i < b.N; i++ {
sqrt.SqrtWithBS(float64(i))
}
}
テスト結果#
ニュートン法は二分探索法に比べて性能が良いことがわかります!🥰