计算方法（二）：非线性方程求根_综合

文章目录

非线性方程求根
- 二分法
- 迭代法
- - 不动点迭代法（简单迭代法）
  - 迭代法收敛的充分条件
- 牛顿迭代法与弦割法
- - 牛顿迭代公式及其几何意义
  - - 单根情形
  - 牛顿迭代法收敛的充分条件
  - 弦割法（割线法）
- 非线性方程组牛顿迭代法求根
- 迭代法的收敛阶和加速收敛方式
- - - 分析简单迭代法与牛顿迭代法的收敛速度：
    - 迭代加速方法

非线性方程求根

主要讨论单变量非线性方程：
$f(x)=0\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (2.1)$ 的求根问题， $x\in R\ \ ,\ \ f(x)\in C[a,b]$ .

（1）“根在哪里”，即确定根所在的区间，进行根的隔离。

（2）“根的求法”，通过数值方法，近似求解，并保证精度要求。

若 $f(x)\in C[a,b]$ 且 $f (a) f (b) < 0$ ，根据闭区间上连续函数性质可知 $f (x) = 0$ 在 $(a, b)$ 内至少有一个实根，称 $[a, b]$ 为方程（2.1）的有根区间。

二分法

若 $f(x)\in C[a,b]$ 且 $f (a) f (b) < 0$ ，根据连续函数性质可知 $f (x) = 0$ 在 $(a, b)$ 内至少有一个实根 $x^*$ 。

考察有根区间 $[a, b]$ ，取中点 $x_0=\frac{a+b}{2}$ 将区间分为两半。若 $f(x_0)=0$ ，则 $x_0$ 为 $f (x) = 0$ 的实根 $x^*$ 。若 $f(x_0)\neq0$ ，检查 $f(x_0)$ 与 $f (a)$ 是否同号，即不等式：
$f(a)f(x_0)<0$ 是否成立。如果成立，说明所求的根 $x^*$ 在 $x_0$ 的左侧，这时令 $a_1=a,b_1=x_0$ ；否则 $x^*$ 必在 $x_0$ 右侧，这时令 $a_1=x_0,b_1=b$ ，两种情况都能得到一个新的有根区间 $a_1,b_1]$ ，其长度仅为 $[a, b]$ 的一半。

对缩小了的有根区间 $a_1,b_1]$ 用中点 $x_1=\frac{a_1+b_1}{2}$ 再分成两半，然后判断 $x_1$ 是不是根，并用
$f(a)f(x_1)<0$ 是否成立来判断所求的根 $x^*$ 在 $x_1$ 的哪一侧，从而又确定一个新的有根区间 $a_2,b_2]$ ，其长度是 $a_1,b_1]$ 的一半。

如此反复二分下去，可以得出一系列有根区间：
$[a,b]\supset[a_1,b_1]\supset[a_2,b_2]\supset\cdots\supset[a_k,b_k]\supset\cdots$ 其中区间每个区间都是前一个区间的一半，从而 $a_k,b_k]$ 的长度为
$b_k-a_k=\frac{b-a}{2^k}$ 当 $k\rightarrow\infty$ 时，此区间长度趋于零，如果二分过程无限地继续下去，这些区间最终必收缩于一点 $x^*$ ，为所求的根。

每次二分后，取有根区间 $a_n,b_n]$ 的中点 $x_n=\frac{a_n+b_n}{2}$ 作为根的近似值，可以得到一个近似根的序列： $x_0,x_1,x_2,\cdots$ ，该序列必以根 $x^*$ 为极限。

给定一个预定的精度 $\varepsilon$ ，由 $x^*\in [a_n,b_n]$ ，可得
$|x^*-x_n|\leq\frac{1}{2}(b_n-a_n)=\frac{1}{2^{n+1}}(b-a)$ 只要 $n$ 充分大，使得
$\frac{1}{2^{n+1}}(b-a)<\varepsilon\ \ \ \ , \ \ 即\ n>[\ln\frac{b-a}{\varepsilon}/\ln2]$ 就有
$|x^*-x_n|<\varepsilon$ $x_n$ 就是一个满足精度要求的近似根。

注：在实际计算中，若 $f(x_n)|$ 很小： $|f(x_n)|<\delta$ （ $\delta$ 为给定的误差限），则 $x_n$ 就可作为近似根。

二分法的优点是算法简单，且总是收敛的，缺点是事先要确定有根区间，且收敛较慢，且不能用于求复根或偶数重根，一般不单独将其用于求根，只用其求根的一个较好的近似值。

迭代法

不动点迭代法（简单迭代法）

将方程 $f (x) = 0$ 转化为：
$x = g (x)$ 若 $x^*$ 满足 $f(x^*)=0$ ，则 $x^*=g(x^*)$ ，称 $x^*$ 为函数 $g (x)$ 的一个不动点。

选择初始近似值 $x_0$ ，代入得： $x_1=g(x_0)$ 。

反复迭代： $x_{k+1}=g(x_k)$ ， $k=0,1,2,\cdots$ ，称 $g (x)$ 为迭代函数，可得一个迭代序列{ $x_k$ }。

若对于 $x_0\in[a,b]$ ，该迭代序列有极限： $\lim_{k\rightarrow\infty}x_k=x^*$ ，则称迭代法收敛，且 $x^*=g(x^*)$ 为 $g (x)$ 的不动点。若迭代序列发散，则称迭代法发散。

不动点迭代法的基本思想：将隐式方程 $f (x) = 0$ 化为显式的计算公式 $x = g (x)$ ，然后通过迭代，求方程近似根。

迭代法几何意义： 方程 $x = g (x)$ 的求根问题在 $x y$ 平面上就是要确定曲线 $x = g (x)$ 与直线 $y = x$ 的交点 $P^*$ 。

迭代法收敛的充分条件

压缩映照： 在区间[a,b]上定义的函数 $g (x)$ ，若存在常数 $L,0\leq L\leq 1$ ，使得 $\forall x,y\in[a,b]$ ，都有：
$|g(x)-g(y)|\leq L|x-y|$ 则称映照 $g (x)$ 在区间 $[a, b]$ 上是压缩的。

不动点的存在唯一性及误差分析

定理1： 设 $g(x)\in C[a,b]$ 满足以下两个条件：（1）任意 $x\in [a,b]$ ，有 $g(x)\in[a,b]$ ；（2）存在常数 $L,0\leq L\leq 1$ ，使对任意 $x,y\in[a,b]$ ，有
$|g(x)-g(y)|\leq L|x-y|$ 则：（1） $x = g (x)$ 在 $[a, b]$ 上存在唯一实根 $x^*$ ；（2）对任意初值 $x_0\in[a,b]$ ，由 $x_{k+1}=g(x_k)$ 得到的迭代序列 { ${x_k}$ }收敛到 $x = g (x)$ 在 $[a, b]$ 的唯一实根 $x^*$ ，并有误差估计：
$|x^*-x_k|\leq \frac{1}{1-L}|x_{k+1}-x_k|\\|x^*-x_k|\leq\frac{L^k}{1-L}|x_1-x_0|$

证明如下：

先证不动点存在性。
$定义函数:\varphi(x)=g(x)-x\\显然\varphi(x)\in C[a,b]。因为a\leq g(x)\leq b，有\\\varphi(a)=g(a)-a\geq0,\varphi(b)=g(b)-b\leq0\\由连续函数性质可知存在\ x^*\in(a,b),使得 \ \varphi(x^*)=0,即\ g(x^*)=x^*,为不动点$
再证唯一性。
$设\ x_1^*\ 及\ x_2^*\in[a,b]是\ g(x)\ 的两个不同的不动点，则\\|x_1^*-x_2^*|=|g(x_1^*)-g(x_2^*)|\leq L|x_1^*-x_2^*|<|x_1^*-x_2^*|,矛盾$
误差估计：
$|x_k-x^*|=|g(x_{k-1})-g(x^*)|\leq L|x_{k-1}-x^*|\leq \cdots\leq L^k|x_0-x^*|\\|x_{k+1}-x_k|=|g(x_k)-g(x_{k-1})|\leq L|x_k-x_{k-1}|\leq L^k|x_1-x_0|\\于是，对任意正整数\ p,有\\|x_{k+p}-x_k|\leq |x_{k+p}-x_{k+p-1}|+|x_{k+p-1}-x_{k+p-2}|+\cdots+|x_{k+1}-x_k|\leq(L^{k+p-1}+L^{k+p-2}+\cdots +L^k)|x_1-x_0|\\令\ p\rightarrow\infty，注意到\ \lim_{p\rightarrow\infty}x_{k+p}=x^*,可得\\|x^*-x_k|\leq \frac{L^k}{1-L}|x_1-x_0|\\|x_{k+1}-x_k|=|(x^*-x_k)-(x^*-x_{k+1})|\geq|x^*-x_k|-|x^*-x_{k+1}|\geq|x^*-x_k|-L|x^*-x_k|=(1-L)|x^*-x_k|\\|x^*-x_k|\leq\frac{1}{1-L}|x_{k+1}-x_k|$

实际迭代计算过程中，有时 $L$ 难以估计，所以，只要相邻两次计算结果的偏差 $x_{k+1}-x_k|$ 足够小，即可保证近似值 $x_k$ 具有足够精度。

由Lagrange中值定理可知，如果 $g(x)\in C^1[a,b]$ ，且对任意 $x\in[a,b]$ ，有 $|g'(x)|\leq L\leq 1$ ，则对 $\forall x,y\in[a,b]$ ，有
$|g(x)-g(y)|=|g'(\xi)(x-y)|\leq L|x-y|,\xi\in(a,b)$ 表明上述定理的条件（2）可用 $g^{'} (x)$ 的性质代替。

注：一般情况下， $L$ 越小，收敛速度越快。

局部收敛性： $g (x)$ 有不动点 $x^*$ ，如果存在 $x^*$ 的某一邻域 $S=\{x||x-x^*|\leq\delta\}$ ，对任意 $x_0\in S$ ，迭代产生的序列 $\{x_k\}\in S$ ，且收敛到 $x^*$ ，则称迭代法局部收敛。

定理2：设 $x^*$ 为 $g (x)$ 的不动点， $g^{'} (x)$ 在 $x^*$ 的某个邻域连续，且 $∣ g^{'} (x) ∣ < 1$ ，则迭代法局部收敛。

证明：由连续函数性质，存在 $L$ 和 $x^*$ 的某个邻域 $S=\{x||x-x^*|\leq\delta\}=[x^*-\delta,x^*+\delta]$ ，对任意 $x\in S$ ，成立：
$|g'(x)|\leq L<1$ 又： $|g(x)-x^*|=|g(x)-g(x^*)|\leq L|x-x^*|\leq|x-x^*|$ 可知，对任意 $x\in S$ ，总有 $g(x)\in S$ 。由定理1知，对任意 $x_0\in S$ ，迭代序列 $\{x_k\}\in S$ ，且收敛到 $x^*$ 。

牛顿迭代法与弦割法

牛顿迭代公式及其几何意义

牛顿法实质上是一种线性化方法。对于单根和重根，收敛速度不同。

设 $f (x)$ 可以表示成 $f(x)=(x-x^*)^mq(x)$ ，且 $q(x^*)\neq0$ ，则称 $x^*$ 为方程 $f (x) = 0$ 的m重根，当m=1时，称 $x^*$ 为方程 $f (x) = 0$ 的单根。

设 $f(x)\in C^m[a,b]$ ，则 $f (x)$ 在内的点 $x^*$ 具有m重根的充要条件是：
$f(x^*)=f'(x^*)=\cdots=f^{(m-1)}(x^*)=0,\ \ \ f^{(m)}(x^*)\neq0$

单根情形

设 $f(x)\in C^{1}(x^*-\delta，x^*+\delta)$ ， $f'(x^*)\neq0$ ，即 $x^*$ 为方程 $f (x) = 0$ 的单根。

设已知方程 $f (x) = 0$ 有近似根 $x_k$ （ $f'(x_k)\neq0$ ），将函数 $f (x)$ 在点 $x_k$ 展开，有：
$f(x)\approx f(x_k)+f'(x_k)(x-x_k)$ 于是方程 $f (x) = 0$ 可以近似表示为：
$f(x_k)+f'(x_k)(x-x_k)=0$ 记其根为 $x_{k+1}$ ，则 $x_{k+1}$ 的计算公式为：
$x_{k+1}=x_k-\frac{f(x_k)}{f'(x_k)},\ \ \ \ k=0,1,\cdots$

牛顿迭代法收敛的充分条件

定理3：设 $f (x)$ 在其零点 $x^*$ 的某邻域 $S=\{x||x-x^*|\leq\delta\}$ 内有二阶连续导数，且 $f'(x^*)\neq0$ （即 $x^*$ 为单根），则牛顿迭代法在 $x^*$ 附近具有局部收敛性。

证明：牛顿迭代法的迭代函数为：
$g(x)=x-\frac{f(x)}{f'(x)}\\g'(x)=1-\frac{[f'(x)]^2-f(x)f''(x)}{[f'(x)]^2}=\frac{f(x)f''(x)}{[f'(x)]^2}$
假定 $x^*$ 是 $f (x)$ 的一个单根，即 $f(x^*)=0$ ， $f'(x^*)\neq0$ ，则由上式知 $g^{'} (x) = 0$ ，于是由定理2得，牛顿迭代法在 $x^*$ 附近具有局部收敛性。

定理4：对方程 $f (x) = 0$ ，若存在区间 $[a, b]$ ，使

（1） $f^{''} (x)$ 在 $[a, b]$ 上连续；

（2） $f (a) f (b) < 0$ ；

（3）对任意 $x\in[a,b]$ ，都有 $f'(x)\neq0$ ；

（4） $f^{''} (x)$ 在 $[a, b]$ 上保号。

则当初值 $x_0\in[a,b]$ 且 $f(x_0)f''(x_0)>0$ 时，牛顿迭代法产生的迭代序列 ${x_k\}$ 收敛于方程 $f (x) = 0$ 在 $[a, b]$ 上的唯一实根 $x^*$ 。

牛顿迭代法的计算步骤：

（1）选定初始近似值 $x_0$ ，计算 $f_0=f(x_0),f'_0=f'(x_0)$

（2）迭代。按公式： $x_1=x_0-{f_0}/{f'_0}$ 迭代一次，得新的近似值 $x_1$ ，计算 $f_1=f(x_1),f'_1=f'(x_1)$ 。

（3）控制。如果 $x_1$ 满足 $|\delta|<\zeta_1$ 或 $|f_1|<\zeta_2$ ，则终止迭代，以 $x_1$ 作为所求的根；否则转（4）。此处 $\zeta_1，\zeta_2$ 是允许误差，而
$\delta=\begin{cases} |x_1-x_0|,\quad 当|x_1|< C时\\\frac{|x_1-x_0|}{|x_1|}, \quad 当|x_1|\geq C时 \end{cases}$ 其中 $C$ 是取绝对误差或相对误差的控制常数，一般可取 $C = 1$ 。

（4）修正。如果迭代次数达到预先指定的次数 $N$ ，或者 $f^{'} = 0$ ，则方法失败；否则以 $x_1,f_1,f'_1)$ 代替 $x_0,f_0,f'_0)$ 转（2）继续迭代。

牛顿法的优点是收敛快，缺点一是每步迭代计算量大，缺点二是初始近似值 $x_0$ 只在根 $x^*$ 附近才能保证收敛。为克服这两个缺点，通常可用下述方法：

（1）简化牛顿法，也称平行弦法，其迭代公式为：
$x_{k+1}=x_k-Cf(x_k),\ \ \ C\neq0,\ \ \ k=0,1,\cdots$ 迭代函数为：
$g (x) = x ? C f (x)$ 若 $∣ g^{'} (x) ∣ = ∣ 1 ? C f^{'} (x) ∣ < 1$ ，即取 $0 < C f^{'} (x) < 2$ ，在根 $x^*$ 附近成立，则迭代法局部收敛。若取 $C=\frac{1}{f'(x_0)}$ ，则称为简化牛顿法，其几何意义是用平行弦与 $x$ 轴交点作为 $x^*$ 的近似。

（2）牛顿下山法。 为了防止迭代发散，对迭代过程附加一项要求，即具有单调性： $f(x_{k+1})|<|f(x_k)|$ 。将牛顿法的计算结果：
$\bar{x}_{k+1}=x_k-\frac{f(x_k)}{f'(x_k)}$ 与前一步的近似值 $x_k$ 适当加权平均作为新的改进值：
$x_{k+1}=\lambda\bar x_{k+1}+(1-\lambda)x_k=x_k-\lambda \frac{f(x_k)}{f'(x_k)}$ 选择下山因子 $\lambda$ 时从 $\lambda=1$ 开始，逐次将 $\lambda$ 减半进行试算，直到能使下降条件满足为止，即满足单调下降性： $f(x_{k+1})|<|f(x_k)|$ 。

弦割法（割线法）

设 $x_k,x_{k-1}$ 是 $f (x) = 0$ 的近似根，利用 $f(x_k),f(x_{k-1})$ 构造一次插值多项式 $p_1(x)$ ，并用 $p_1(x)$ 的根作为 $f (x) = 0$ 的新的近似根 $x_{k+1}$ 。由
$p_1(x)=f(x_k)+\frac{f(x_k)-f(x_{k-1})}{x_k-x_{k-1}}(x-x_k)$ 相当于在 $f (x)$ 曲线上取两点 $x_k,f(x_k)),(x_{k-1},f(x_{k-1}))$ ，过这两点作割线。令 $p_1(x_{k+1})=0$ ，得
$x_{k+1}=x_k-\frac{f(x_k)}{f(x_k)-f(x_{k-1})}(x_k-x_{k-1}),\ \ \ \ k=1,2,\cdots$ 弦割法：牛顿法 $x_{k+1}=x_k-\frac{f(x_k)}{f'(x_k)}$ 中的导数 $f'(x_k)$ 用差商 $\frac{f(x_k)-f(x_{k-1})}{x_k-x_{k-1}}$ 取代的结果。

$x_{k+1}$ 实际上是两点 $x_k,f(x_k)),(x_{k-1},f(x_{k-1}))$ 的割线与 $x$ 轴交点的横坐标。

弦割法避免了求导数，但收敛速度不如牛顿法。

非线性方程组牛顿迭代法求根

考虑方程组 $\begin{cases}f_1(x_1,\cdots,x_n)=0\\\cdots\cdots\cdots\\f_n(x_1,\cdots,x_n)=0 \end{cases}$

其中 $f_1,f_2,\cdots,f_n$ 均为 $(x_1,\cdots,x_n)$ 的多元函数。用向量记号记 $X=(x_1,\cdots,x_n)^T\in R^n,F=(f_1,\cdots,f_n)^T$ ，可以写成
$F (X) = 0$ 若已给出方程的一个近似根 $X^{(k)}=(x_1^{k},\cdots,x_n^{(k)})$ ，将函数 $F (X)$ 的分量 $f_i(x)(i=1,\cdots,n)$ 在 $X^{(k)}$ 用多元函数泰勒展开并取线性部分，可表示为
$F(X)\approx F(X^{(k)})+F'(X^{(k)})(X-X^{(k)})\\令右式等于0：F'(X^{(k)})(X-X^{(k)})=-F(X^{(k)})$ 其中 $F^{'} (X)$ 是 $f_1,f_2,\cdots,f_n$ 的 $n ? n$ 阶雅可比（Jacobi）矩阵：
$F'(X)=\frac{\partial(f_1,f_2,\cdots,f_n)}{\partial(x_1,x_2,\cdots,x_n)}=\left[\begin{matrix}\frac{\partial f_1}{\partial x_1} & \frac{\partial f_1}{\partial x_2} & \cdots&\frac{\partial f_1}{\partial x_n}\\\frac{\partial f_2}{\partial x_1} & \frac{\partial f_2}{\partial x_2} &\cdots&\frac{\partial f_2}{\partial x_n} \\\vdots&\vdots&&\vdots\\\frac{\partial f_n}{\partial x_1} & \frac{\partial f_n}{\partial x_2} &\cdots&\frac{\partial f_n}{\partial x_n}\end{matrix}\right]$ 求解方程组，并记为 $X^{(k+1)}$ ，得
$X^{(k+1)}=X^{(k)}-F'(X^{(k)})^{-1}F(X^{(k)}),\ \ k=0,1,\cdots$

定理5：设 $F (X)$ 的定义域 $D\subset R^n$ ， $X^*\in D$ 满足 $F(X^*)=0$ ，在 $X^*$ 的开邻域 $S_0\subset D$ 上 $F^{'} (X)$ 存在且连续， $F^{'} (X)$ 非奇异，则牛顿法生成的序列{ $X^{(k)}$ }在闭域 $S\subset S_0$ 上超线性收敛于 $X^*$ 。若还存在常数 $L > 0$ ，使 $||F'(X)-F'(X^*)||\leq L*||X-X^*||,\forall X\in S$ ，则{ $X^{(k)}$ } 至少平方收敛。

迭代法的收敛阶和加速收敛方式

定义：设迭代法 $x_{k+1}=g(x_k)$ 收敛于方程 $x = g (x)$ 的根 $x^*$ ，若存在常数 $p(p\geq1)$ 和 $c (c > 0)$ ，使得
$\lim_{k\rightarrow\infty}\frac{|x^*-x_{k+1}|}{|x^*-x_k|^p}=c$
则称该迭代过程是 $p$ 阶收敛的。特别的， $p = 1 (0 < c < 1)$ 时称线性收敛， $p > 1$ 时称超线性收敛， $p = 2$ 时称平方收敛。

迭代法的收敛速度依赖于迭代函数 $g (x)$ 的选取。 收敛阶越高，收敛速度就越快。

定理6：设 $x^*$ 是方程 $x = g (x)$ 的根， $g(x),g'(x),\cdots,g^{(p)}(x)$ 在 $x^*$ 的邻近连续，且 $g'(x^*)=g''(x^*)=\cdots=g^{(p-1)}(x^*)=0,g^{(p)}(x^*)\neq0$ ，则迭代法 $x_{k+1}=g(x_k)$ 在 $x^*$ 邻近是 $p$ 阶收敛的。

特别的，当 $0<|g'(x^*)|<1$ 时，迭代法是线性收敛的；当 $g'(x^*)=0,g''(x^*)\neq0$ ，迭代法是线性收敛的。

证明：由 $g'(x^*)=0$ ，可知迭代法 $x_{k+1}=g(x_k)$ 具有局部收敛性。

将 $g(x_k)$ 在根 $x^*$ 处泰勒展开，有
$g(x_k)=g(x^*)+\frac{g^{(p)}(\xi)}{p!}(x_k-x^*)^p,\ \ \xi在x_k、x^*之间$ 注意到 $g(x_k)=x_{k+1},g(x^*)=x^*$ ，由上式得
$x_{k+1}-x^*=\frac{g^{(p)}(\xi)}{p!}(x_k-x^*)^p\rightarrow\frac{g^{(p)}(x^*)}{p!}(x_k-x^*)^p\ \ \ \ \ \ \ (k\rightarrow\infty)$ 即迭代过程 $x_{k+1}=g(x_k)$ 在 $x^*$ 邻近是 $p$ 阶收敛的。

分析简单迭代法与牛顿迭代法的收敛速度：

简单迭代法：由 $x^*-x_{k+1}=g(x^*)-g(x_k)=g'(\zeta_k)(x^*-x_k)$ ，得
$\lim_{k\rightarrow\infty}\frac{|x^*-x_{k+1}|}{|x^*-x_k|}=\lim_{k\rightarrow\infty}|g'(\zeta_k)|=|g'(x^*)|$ 所以当 $0 < ∣ g^{'} (x) ∣ < 1$ 时，简单迭代法线性收敛。

牛顿迭代法：（1）单根情形： 由 $g(x)=x-\frac{f(x)}{f'(x)}$ ，知
$g'(x)=1-\frac{[f'(x)]^2-f(x)f''(x)}{[f'(x)]^2}=\frac{f(x)f''(x)}{[f'(x)]^2}$ $x^*$ 是 $f (x)$ 的一个单根，即 $f(x^*)=0,f'(x^*)\neq0$ ，则由上式知
$g'(x^*)=0,g''(x^*)=\frac{f''(x^*)}{f'(x^*)}$ 表明牛顿迭代法在零点 $x^*$ 的邻近是平方收敛的。
$\lim_{k\rightarrow\infty}\frac{x_{k+1}-x^*}{(x_k-x^*)^2}=\frac{g''(x^*)}{2}=\frac{f''(x^*)}{2f'(x^*)}$ （2）重根形式： 设 $f(x)=(x-x^*)^mq(x)$ ，整数 $m\geq2,q(x^*)\neq0$ ，则 $x^*$ 为方程 $f (x) = 0$ 的m重根
$g(x)=x-\frac{f(x)}{f'(x)}\\g'(x^*)=\frac{f(x)f''(x)}{[f'(x)]^2}|_{x=x^*}=\frac{m(m-1)(x-x^*)^{2m-2}q(x)+2m(x-x^*)^{2m-1}q'(x)q(x)+(x-x^*)^{2m}q(x)q''(x)}{m^2(x-x^*)^{2m-2}q(x)^2+(x-x^*)^{2m}q'(x)^2+2m(x-x^*)^{2m-1}q(x)q'(x)}|_{x=x^*}\\=\frac{m(m-1)q(x)+2m(x-x^*)q'(x)q(x)+(x-x^*)^2q(x)q''(x)}{m^2q(x)^2+(x-x^*)^2q'(x)^2+2m(x-x^*)q(x)q'(x)}|_{x=x^*}=1-\frac{1}{m}\neq0\ \ ,\ \ |g'(x^*)|<1$ 所以当 $x^*$ 为 $f (x) = 0$ 的 $m(m\geq2)$ 重零点， $f (x)$ 在其零点 $x^*$ 的某邻域内有二阶连续导数，则牛顿法局部线性收敛，为使其仍然二次收敛，需对其修正。

若已知重根数 $m$ ：取 $g(x)=x-m\frac{f(x)}{f'(x)}$ ，可得：
$g'(x^*)=1-m*\frac{[f'(x)]^2-f(x)f''(x)}{[f'(x)]^2}=1-m+m*\frac{f(x)f''(x)}{[f'(x)]^2}=1-m+m*(1-\frac{1}{m})=0$ 则迭代法：
$x_{k+1}=x_k-\frac{mf(x_k)}{f'(x_k)}\ \ ,\ \ k=0,1,\cdots$ 是局部二次收敛的。

若重根数 $m$ 未知： 令 $F(x)=\frac{f(x)}{f'(x)}$ ，若 $x^*$ 是 $f (x) = 0$ 的 $m$ 重根，则
$F(x)=\frac{(x-x^*)^mq(x)}{m(x-x^*)^{m-1}q(x)+(x-x^*)^mq'(x)}=\frac{(x-x^*)q(x)}{mq(x)+(x-x^*)q'(x)}$ 得到 $x^*$ 是 $F (x) = 0$ 的单根，用牛顿法，其迭代函数为：
$g(x)=x-\frac{F(x)}{F'(x)}=x-\frac{\frac{f(x)}{f'(x)}}{\frac{[f'(x)]^2-f(x)f''(x)}{[f'(x)]^2}}=x-\frac{f(x)f'(x)}{[f'(x)]^2-f(x)f''(x)}$ 从而可构造迭代法
$x_{k+1}=x_k-\frac{f(x)f'(x)}{[f'(x)]^2-f(x)f''(x)}\ \ ,\ \ k=0,1,\cdots$ 是二阶收敛的。

迭代加速方法

1、艾特肯（Aitken）加速方法：对于收敛于 $x^*$ 的不动点迭代法 $x_{k+1}=g(x_k)$ ，设 $x_k$ 是根 $x^*$ 的某个近似值，用迭代公式校正一次得：
$x_{k+1}=g(x_k)$ 由微分中值定理得
$x_{k+1}-x^*=g(x_k)-g(x^*)=g'(\zeta)(x_k-x^*)\ \ ,\ \ \zeta介于x_k、x^*之间$ 假定 $g^{'} (x)$ 改变不大，近似去某个近似值 $L$ ，则有
$x_{k+1}-x^*\approx L(x_k-x^*)\tag{1}$ 再进行一次校正，得
$x_{k+2}=g(x_{k+1})\\x_{k+2}-x^*\approx L(x_{k+1}-x^*)$ 与（1）式联立消去未知的 $L$ ，有
$\frac{x^*-x_{k+1}}{x^*-x_k}=\frac{x^*-x_{k+2}}{x^*-x_{k+1}}\\x^*\approx\frac{x_kx_{k+2}-x_{k+1}^2}{x_{k+2}-2x_{k+1}+x_k}=x_k-\frac{(x_{k+1}-x_k)^2}{x_{k+2}-2x_{k+1}+x_k}$ 可用上式右端作为 $x^*$ 的新近似： $\tilde{x}_k=x_k-\frac{(x_{k+1}-x_k)^2}{x_{k+2}-2x_{k+1}+x_k}$ 。这被称为艾特肯（Aitken）加速方法。

2、斯蒂芬森（Steffensen）方法：也称为艾特肯算法，把艾特肯加速技巧与不动点迭代结合，可得： $\begin{cases}y_k=g(x_k)\\z_k=g(y_k)\\x_{k+1}=x_k-\frac{(y_k-x_k)^2}{z_k-2y_k+x_k} \end{cases}\ \ (k=0,1,2,\cdots)$

也可将其写成另一种不动点迭代：
$x_{k+1}=g(x_k)\ \ \ (k=0,1,2,\cdots)\\其中\ \ \ g(x)=x-\frac{(g(x)-x)^2}{g(g(x))-2g(x)+x}$