牛顿法

牛顿法

复习go语言基础的时候，看到一个算法题，求特定值的平方根（不使用特定库函数的前提下），常见的方法要么是二分法要么是牛顿法。

二分法比较好理解，这里就不多进行解释了，这篇文章主要是总结一下牛顿法。

牛顿迭代法（Newton's method）又称为牛顿-拉夫逊方法（Newton-Raphson method）

我们想要获取平方根，那么我们就需要求得方程的零值。即f(x)=0,但是多数方程不存在求根公式，因此求精确根非常困难，甚至不可能，从而寻找方程的近似根就显得特别重要。牛顿迭代法就提出利用曲线的切线通过多次迭代来逼近精确值。

具体实现

具体是如何逼近的，我这里就不多进行解释，因为我觉得没有观看具体动画来的直观，所以这里可以随意找一个视频网站简单了解一下是如何一步一步进行逼近的。

下面是相对严谨的数学公式。

假设输入的数是 m，则其实是求一个 x 值，使其满足 x2 = m，令 f(x) = x2 - m ，其实就是求方程 f(x) = 0 的根。那么 f(x) 的导函数是 f'(x) = 2x。

设r是f(x) = 0的根，选取x0作为r初始近似值，过点（x0,f(x0)）做曲线y = f(x)的切线L，L的方程为y = f(x0)+f'(x0)(x-x0)，求出L与x轴交点的横坐标 x1 = x0-f(x0)/f'(x0)，称x1为r的一次近似值。

过点（x1,f(x1)）做曲线y = f(x)的切线，并求该切线与x轴交点的横坐标 x2 = x1-f(x1)/f'(x1)，称x2为r的二次近似值。重复以上过程，得r的近似值序列，其中x(n+1)=x(n)－f(x(n))/f'(x(n))，称为r的n+1次近似值，上式称为牛顿迭代公式。

很乱但没办法，数学公式就是这样难阅读。不过整体逻辑不难理解。

通过上面的推导可以很容易得到迭代公式：X(n+1)=[X(n)+p/Xn]/2

 package main
 ​
 import (
     "fmt"
     "math"
 )
 ​
 // f 是我们要求根的函数
 func f(x float64) float64 {
     return x*x - 2 // 例如：x^2 - 2 = 0 的根是 sqrt(2)
 }
 ​
 // df 是 f 的导数
 func df(x float64) float64 {
     return 2 * x // 导数为 2x
 }
 ​
 // Newton 方法求解方程 f(x) = 0 的根
 func newton(x0 float64, tol float64, maxIter int) float64 {
     x := x0
     for i := 0; i < maxIter; i++ {
         fx := f(x)
         dfx := df(x)
         
         if dfx == 0 {
             fmt.Println("导数为零，无法继续迭代")
             return x
         }
 ​
         xNext := x - fx/dfx
         if math.Abs(xNext-x) < tol {
             return xNext
         }
         x = xNext
     }
     fmt.Println("达到最大迭代次数")
     return x
 }
 ​
 func main() {
     // 初始猜测值
     x0 := 1.0
     // 误差容忍度
     tol := 1e-6
     // 最大迭代次数
     maxIter := 100
 ​
     root := newton(x0, tol, maxIter)
     fmt.Printf("方程的根为: %f\n", root)
 }
 ​

优缺点

需要注意的一点是这个牛顿法是有很明显的优缺点的。

优点

简洁

逻辑不负责，很易懂也很易于实现

收敛快

通常具有二次收敛的特性，意思是当接近根的时候，收敛非常快。

缺点

需要合理的初值

这个算法需要寻找一个合理的初值，不然可能不收敛

导数为零

如果在迭代过程中，导数的值接近零，迭代可能会失效或非常缓慢。