如果要求解一个数的根，用什么方法比较好呢？我之前看到有人问这个问题，据说是谷歌的一道面试题，标准面试答案是使用二分法去逼近，直到达到规定的限制范围内。
但是其实最好的方法并不是二分法，至少牛顿法就比这种方法更好
牛顿法
首先，选择一个接近函数f(x)零点，计算相应的f(x0)和切线斜率f'(x0)这里
f'表示函数的导数。然后我们计算穿过点并且斜率为
的直线和
轴的交点的
坐标，也就是求如下方程的解：
我们将新求得的点的{}
坐标命名为
，通常
会比
更接近方程
的解。因此我们现在可以利用
开始下一轮迭代。迭代公式可化简为如下所示：x_1
x_{{n+1}}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}
已经证明，如果
是连续的，并且待求的零点f'
是孤立的，那么在零点x
周围存在一个区域，只要初始值x
位于这个邻近区域内，那么牛顿法必定收敛。 并且，如果x_{0}
不为0, 那么牛顿法将具有平方收敛的性能. 粗略的说，这意味着每迭代一次，牛顿法结果的有效数字将增加一倍。f'(x)
实现牛顿法
首先我们需要一个逼近函数，在一个条件下递归的逼近值，这里我选用Scheme去实现，因为它便于进行所谓** first class procedures **
(define tolorance 0.000001)
(define (fixed-point f first-guess)
(define (close-enough? v1 v2)
(< (abs(- v1 v2)) tolorance))
(define (try guess)
(let ((next (f guess)))
(if (close-enough? guess next)
next
(try next))))
(try first-guess))
由上面的介绍可以看到牛顿法有一步是需要求导数，这里我们求不了导数，但是我们可以求微分
(define dx 0.00001)
(define (derive g)
(lambda (x)
(/ (- (g (+ x dx)) (g x))
dx)))
然后实现公式
(define (newton-transform g)
(lambda (x)
(- x (/ (g x) ((deriv g) x)))))
再将公式封装
(define (newtons-method g guess)
(fixed-point (newton-transform g) guess))
最后我们用这个方法来试试求解一元三次方程等于0的值
(newtons-method (cubic a b c) 1)
(define (cube x) (* x x x))
(define (cubic a b c)
(lambda (x)
(+ (cube x) (* a (square x)) (* b x) c)))
这个方法既实现了开根，又能实现一元方程的解。数学的问题，用数学方法去解决还是要好一些。
