牛顿法(Newton)的应用

1、求解方程

并不是所有的方程都有求根公式,或者求根公式很复杂,导致求解困难。利用牛顿法,可以迭代求解。原理是利用泰勒公式,在 x0x_0 处展开,且展开到一阶,即:
f(x)=f(x0)+(xx0)f(x0)f(x) = f(x_0) + (x - x_0)f'(x_0)
求解方程 f(x)=0f(x) = 0,即:
f(x0)+(xx0)f(x0)=0x=f(x0)f(x0)+x0f(x_0)+ (x - x_0)f'(x_0) = 0\\ x = -\frac {f(x_0)}{f'(x_0)} + x_0
因为这是利用泰勒公式的一阶展开进行求解的,所以通过上述方程求解出的 xx 只是使 f(x)f(x) 的值比 f(x0)f(x_0) 更加接近于0,而并不是完全等于0。如下图所示:
牛顿法(Newton)的应用
于是乎,迭代求解的想法就很自然了,可以进而推出:
xn+1=xnf(xn)f(xn) x_{n+1} = x_n - \frac {f(x_n)}{f'(x_n)}
通过对上式进行迭代,最终必然会在 f(x)=0f(x^*) = 0 的时候收敛,这就是用牛顿法进行方程求解的过程。

2、用于最优化问题

求解方程的问题就是求解 f(x)=0f(x) = 0,而最优化问题就是求解 f(x)f(x) 的极值,也即 f(x)=0f'(x) = 0,为了求解 f(x)=0f'(x) = 0,我们需要把 f(x)f(x) 泰勒展开到 2 阶形式:
f(x)=f(x0+Δx)=f(x0)+f(x0)(xx0)+12f(x0)(xx0)2 \begin{aligned} f(x) &= f(x_0+\Delta x)\\ &= f(x_0) + f'(x_0)(x - x_0) + \frac 12 f''(x_0)(x - x_0)^2 \end{aligned}
对上式进行两边求导之后可以得到:
f(x)=f(x0)+(xx0)f(x0)=0Δx=(xx0)=f(x0)f(x0) f'(x) = f'(x_0)+(x - x_0)f''(x_0) = 0\\ \Delta x = (x - x_0) = -\frac {f'(x_0)}{f''(x_0)}
从而可以得到迭代公式:
xn+1=xn+Δx=xnf(xn)f(xn),n=0,1,... x_{n+1} = x_n + \Delta x = x_n - \frac {f'(x_n)}{f''(x_n)}, \quad n = 0,1,...