翻看了以前写的使用Newton-Raphson Method求一个数的开方,想到其实也可以用中值定理来实现。 中值定理:f(x)是一个连续性的函数,在[u,v]区间内,当c的值位于f(u)和f(v)之间时,至少存在一个点,满足f(x) = c 当f(u)和f(v)一正一负时,那么在[u,v]之间至少有一个根的存在,这个定理本来就是拿来证明根的存在的,但是其实也可以用来求解根。
Newton-Raphson Method
曲线f(x)
有根c,取曲线上一点$(x_1,f(x_1))$, 过此点的切线交x轴$x_2$,过曲线上$(x_2,f(x_2))$的切线交x轴$x_3$,如此反复得到一个序列 $x_1,x_2,\cdot \cdot \cdot,x_n$ 逼近c值.
过$(x_n,f(x_n))$的切线方程为 $y-f(x_n) = f'(x_n),(x-x_n)$,假设此方程与x轴的交点为$x_{n+1}$, 即有: $0 - f(x_n) = f'(x_n)(x_n+1 - x_n)$, 即$x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$ <Eq. 1>
.
下面利用此法来求一个数的开方。 $f(x) = x^2 - a$ 有根$\sqrt{a}$,
由$f'(x_n) = 2x_n$, 代入式<Eq. 1>
可得$x_{n+1} = (x_n + a/x_n)/2$; 当i -> INF 时, $x_i$ -> $\sqrt{a}$;