牛顿法在多项式方程中的应用

介绍

我们这个章节主要针对的是解的近似值，对于$n<5$的n次多项式来说，我们总是可以得到他的解析解，但$5$次以上的方程是不存在解析解的，具体的情况可以在我的github上的抽象代数（群2\wcfcbkj.pdf中找到答案。）但，我们给计算机输入一个方程后，他可以给出一个精度不错的零点，这意味着虽然没有准确的解析解，但我们还是可以通过一些方法得到解的近似值。

在基本的微积分课程上我们学过了线性化近似了，实际上那个我们也叫做牛顿法，它的极限叫微分。它是这样操作的：

• 选择一个靠近解的点$z_0$，设为$s$
• 然后定义$z_1 = z_0 - f(z_0)/f’(z_0)$，并归纳的定义$z_{n+1} = z_n - f(z_n)/f’(z_n)$

这意味着若$z_0$足够靠近根$s$，则序列$\{z_n\}$收敛到$s$

从几何上看，若我们尝试用$s$去近似方程$f(x)=0$，则我们有一个不错的解释。设$(x_0,f(x_0))$是位于函数$y=f(x)$上的点$P$，则函数在$P$上的切线由等式$L(x) = f(x_0)+f’(x_0)(x-x_0)$给出。因此$x_1 = x_0 - f(x_0)/f’(x_0)$。

所以，$x_{n+1}$就是$y= f(x)$在$(x_n,f(x_n))$处 的切线，一般来说这是收敛的，但问题在于。如果序列收敛，它的收敛速度有多快，$x_0$如何足够的接近根$s$，并且为什么这个几何解释在复平面上有效？

不动点迭代

我们给定一个方程$z = g(z)$，则它的解$s$是一个$g$上的不动点。在适当的条件下，近似不动点是可以通过定义$z_{n+1} = g(z_n)$的递归实现，这个过程我们称为不动点迭代。

引理1

令$s$是等式$z = g(z)$的根，对某个解析函数$g$，设$z_0$在圆盘$D(s; r)$中。其中$s$是圆心而$r$是半径。且始终有$\mid g’(z)\mid \leq K$，令$z_1 = g(z_0) $。则$\mid z_1 - s\mid \leq K\mid z_0-s\mid $

证明： 我们记$\mid z_1 - s\mid = \mid g(z_0) - g(s)\mid $，利用复版本上的微积分定理，则

$\begin{aligned} g(z_0) - g(s) = \int^{z_0}_s g'(z)dz \end{aligned}$

我们选择积分路径为$s$到$z_0$的直线，利用$M-L$方程就可以得到了。

定理

令$s$是$z = g(z)$的根，对某个解析函数$g$，设$z_0$在$D(s;r)$中。且始终有$\mid g’(z)\mid \leq K < 1$，定义序列$\{z_n\}$定义为如下递归：$z_{n+1} = g(z_n);n =0,1\cdots$，则$n\to\infty$ 有$\{z_n\} \to s$

证明： 利用上述引理，我们有

$\begin{aligned} \mid z_{n+1}-s\mid \leq K\mid z_n-s\mid \end{aligned}$

因此，利用归纳法，当我们迭代了$n$次之后就可以得到不等式$\mid z_n-s\mid \leq K^n\mid z_0 - s\mid $。由于$K < 1$，这意味着当$n\to\infty$，则$\mid z_{n+1}-s\mid \to 0$，因此$\{z_n\} \to s$

推论

令$s$为等式$z=g(z)$的根，对某个解析函数$g$有$\mid g’(s)\mid < 1$，则这里存在一个形如$D(s;r)$的圆盘使得若$z_0 \in D(s;r)$并且定义$\{z_n\}$是由递归$z_{n+1} = g(z_n)$得到的序列，其中$n=0,1,\cdots$。若$n\to \infty$则 $\{z_n\} \to s $

证明 由于$\mid g’(s)\mid < 1$，则存在一个常数$K$使得$\mid g’(s)\mid < K < 1$。由于$g’$是解析的，则这里存在一个圆盘$D(s;r)$使得$\mid g’(z)\mid < K$

我们令$\epsilon_n = \mid z_n-s\mid $表示第$n$个误差项，那么我们知道在适当的值$z_0$下，误差序列满足不等式

$\begin{aligned} \epsilon_{n+1} \leq K\epsilon_n \end{aligned}$

若我们选择$K = \frac{1}{2}$，在3或4次迭代后，误差将减少$\frac{1}{10}$。满足上述不等式的迭代方案我们称为线性收敛。获得第$n$个小数位精度所需要的迭代次数大致与$n$成正比。

并且我们发现，收敛的一个重要条件是$\mid g’(s)\mid < 1$。那么有一个问题，我们如何让一个我们熟悉的方程$f(z) =0$可以被重写为一个关于不动点的方程$z = g(z)$。简单的方法就是我们将$z$添加到等式两边，但我们如何在未知解处$s$添加初始条件$\mid g’(s)\mid < 1$呢，答案就是利用一开始我们提出的牛顿法。那么令不动点算法是牛顿法，我们就结束了这个证明。

引理2

若$f$是解析函数且在$z =s$上有一个$k$重零点，再令$g(z) = z-f(z)/f’(z)$。则$g$在$s$处也是可解析的并且$g’(s) = 1-\frac{1}{k}$

证明： 由题设，$f(z) = (z-s)^k h(z)$，其中$h(s)\neq 0$，那么

$\begin{aligned} f(z)/f'(z) = \frac{(z-s)h(z)}{kh(z)+(z-s)h'(z)} \end{aligned}$

因此$f/f’$在$s$是解析的，那么它在$s$处的展开是$\frac{1}{k}(z-s)+a_2(z-s)^2+\cdots$，$g’(z) =\frac{dg}{dz}(z-\frac{f(x)}{f’(x)}) $，利用展开我们就得到了$g’(s) =1- \frac{1}{k}$

定理

令$s$是$f(z)$的根，再令$g(z) = z-f(z)/f’(z)$并且有$g’(s)=0$。并定义$\{z_n\}$是由$z_{n+1} = g(z_n)$递归得到的，其中$n =0,1,\cdots$，则这里存在圆盘$D(s;r)$使得$z_0\in D(s;r)$可以推出$n\to \infty$有$\{z_n\} \to s$

若$f(z)$有一个单根（重数为1）则利用引理2，就有$g’(s) = 1-1/1 = 0$。

引理3

令$s$是$z = g(z)$的根，它对某个解析函数$g$使得$g(s)=0$。设$z_0$在圆盘$D(s;r)$中始终满足

$\begin{aligned} \mid g''(z)\mid \leq M \end{aligned}$

且再令$z_1 =g(z_0)$。则$\mid z_1 -s\mid \leq \frac{1}{2}M\mid z_0-s\mid^2$

证明： 由引理1，我们注意有$z_1-s = g(z_0)-g(s) = \int^{z_0}_s g’(z)dz$，而对于任意位于线$[s,z_0]$上的点$z$，我们可以写为

$\begin{aligned} \mid g'(z)\mid = \mid g'(z)-g'(s)\mid = \mid \int^z_s g''(z)dz\mid \leq M\mid z-s\mid && (2) \end{aligned}$

令$\Delta z = (z_0-s)/n$并写为

$\begin{aligned} \int_s^{z_0}g'(z)dz=\int_s^{s+\Delta z}g'+\int_{s+\Delta z}^{s+2\Delta z}g'+....+\int_{z_0-\Delta z}^{z_0}g' \end{aligned}$

我们应用$M-L$方程在这个方程级数上，并且使用我们一开始（2）得到的估计值表明了$\int^{z_0}_s g’(z)dz$是有界的。那么我们已经得到这个二阶导的积分是$M\mid z-s\mid $，利用引理1，我们把积分的下限放缩到$s$，所以我们实际上有

$\begin{aligned} \int^{z_0}_sg'(z) = M\mid s+\Delta z- s\mid dz +\cdots M\mid s+n\Delta z\mid dz \end{aligned}$

$dz$近似为$\Delta z$，则我们得到

$\begin{aligned} \sum^n_{k=1}Mk(\Delta z)^2 = M\frac{n(n+1)}{2}\frac{\mid z_0-s\mid ^2}{n^2} \end{aligned}$

令$n\to \infty$，就得到我们想要的证明了。

定义 二次收敛

若$\epsilon_n = \mid z_n-s\mid $满足$\epsilon_{n+1} \leq K\epsilon^2_n$，则我们说序列$\{z_n\}$二次收敛到$s$

定理

若$f(z)$在$s$上存在简单根（重数为1），并且$z_0$足够的接近$s$，牛顿法将得到一个二次收敛到$s$的序列。