0xe3aad

0xe3aad

牛頓法求平方根

牛頓迭代法#

image

  • 如圖,一條曲線 $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}$ 為xn2n2xn\frac {x_n^2 - n} {2x_n}
  • 重複迭代直到得到精度滿意的值

代碼實現#

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 次方根#

思路#

  • xn+1=xnf(xn)f(xn)x_{n+1} = x_{n} - \frac {f(x_n)} {f^{'}(x_n)}
  • xn+1=xnxn(1nxnk)kx_{n+1} = x_n - \frac {x_n(1 - nx_n^{-k})} 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))
}

Benchmark (與二分查找比較)#

實現及其測試#

// 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))
	}
}

測試結果#

image

可以看出牛頓法相比於二分查找,性能要好!🥰

載入中......
此文章數據所有權由區塊鏈加密技術和智能合約保障僅歸創作者所有。