牛顿迭代法在重根的情形下只有线性的收敛速，知道重根数的信息或者计算二阶导数都可以解决重根收敛慢的问题，然而这在实际计算中并不方便。因此有学者考虑：将非线性方程求根问题转换为求函数极值得问题，并利用无约束技术中的牛顿法求解。单根情形下雨牛顿法求根等价，重根情形下则得到了一直不需要二阶导数且具有二阶收敛速度的算法。
定理2.1 设x?是f(x)的m(m?1)重零点，则x?是函数
?f2(x) K(x)? （2.5）
f(x??f(x))?f(x)的单重零点，其中??0。
?m?证明 假设f(x)?(x?x)g(x)，其中g(x)?0.
令
S(x)?f(x??f(x))?f(x)， 则
S(x)?(x??f(x)?x?)mg(x??f(x))?(x?x?)mg(x)?[(x?x?)m?m?f(x)(x?x?)m?1?m(m?1)22?f(x)(x?x?)m?2????2??mfm(x)]g(x??f(x))?(x?x?)mg(x)m(m?1)2?(x?x?)3m?2g2(x)????2
?m?(x?x?)2m?1g(x)g(x??f(x))?[2??m(x?x?)mgm(x)]g(x??f(x))?(x?x?)m[g(x??f(x))?g(x)]令
m(m?1)2T(x)?[?x(?x?2
??m(x?x?)mg23m?2)g2x(????)m
m?x(g)]x?(?fx(?)x)?x(gx)??[f(x?g(x))()]由于x?是f(x)的m(m?1)重零点，x?应至少是g(x??f(x))?g(x)的m重零点，因此x应是
?m (x?x)[g(x??f(x))?g(x)]
?的2m重零点，从而T(x)可写成
?2m T(x)?(x?x)H(x)
16
的形式，也就是
(?x?2m)?1gx(gx)??(fx?(x)?)x?(m2Hx) S(x)?m?x由此K(x)可化为
()?(x?x?)g2x() K(x)?
m?(x?x?)2m?1g(x)g(x??f(x))?(x?x?)m2H(x)?????而f(x)?0,g(x)?0，因此g(x??f(x))?0，也就是说x是K(x)单重零点。证
明完毕。
根据定理2.1，为求非线性方程f(x)?0的重根，可以构造形如式（2.5）的
K(x)，利用（1.14）的到迭代格式
xk?1?xk?其中：
M(xk) （2.6） N(xk) M(xk)?f(xk)[f(xk??f(xk))] (2.7)
N(xk)?f?(xk)[2f(xk??f(xk))?f(xk)(1??f?(xk??f(xk)))]?f(xk)f?(xk??f(xk)) (2.8) 当x0充分靠近x时，该迭代格式具有局部二阶收敛速度。 求重根的具体算法为：
输入 初始值x；误差限?；最大迭代次数m及参数?。 输出 近似解或失败信息 步骤1 p0?x0
步骤2 对i?1,2,???,m，作步骤3—4. 步骤3 p?p0?M(p0)，其中M,N形如（2.7），（2.8） N(p0)??步骤4 若p?p0??，则输出，停止，否则p?p0. 步骤5 输出（Method failed )；停止
17
2.2.2 Aitken加速外推下的修正牛顿法求重根重数
当x为重根时，牛顿迭代法线性收敛，如果已知m为根x的重数，则修正牛顿法xk?1?xk?mf(xk)平方收敛，但是根的重数往往是事先未知的，因此如何求?f(xk)??出根的重数成为求出非线性方程重根的一种思路。下面我们给出一种在牛顿迭代法的基础上利用Aitken加速外推给出的一直新的估计根的重数的方法。该方法不用求函数的高阶导数，对于产生的序列只需要简单的四则运算就可以估计根的重数，对于根的较大重数情形也能适用。 在修正的牛顿迭代格式（2.2）的基础上给出 Aitken加速格式： 校正：xk?1?g(xk).
?再校正：xk?1?g(xk?1).
2(x?x)k?1k?1?加速：xk?1?xk?1??. （2.9)
xk?1?2xk?1?xkAitken加速外推格式
设每次迭代飞误差是成比例的减少，即
ek?2ek?1? ek?1ek??设x是非线性方程f(x)?0的精确根，ek?x?xk，则
x??xk?2x??xk?1?? ?
x?xk?1x?xk从上式解出
2xk?xk?2?xk?1 x? （2.10）
xk?2xk?1?xk?2?2?为了减少算术运算，保持数值的稳定性，我们引进的过程 2 ?xk?xk?1?xk,?xk??xk?1??xk.
因此（2.10）即为
18
(?xk)2 x?xk?2 （2.11）
?xk??定理2.2 设非线性方程f(x)?0在其m(m?1)重根x的某个邻域有充分连续导
数。若牛顿迭代格式产生的迭代序列{xk}，则重数 m???xk （x表示对x四舍五入取整）. 2?xk?证明 因为x为非线性方程f(x)?0的m重根，由2.1章节可知牛顿迭代法对m???x??(x),x??(x)，我们有 x重根是收敛的。考虑到k?1k???? x?xk?1??(x)??(xk)???(?)(x?xk) ?介于xk与x之间 （2.12）
x??xk?1???(?)，因为当k??时xk?x?，??x?，所以当式（2.12）可以写作?x?xkk充分大时，我们可以认为
x??xk?11?????(?)??x(?)?1 ? （2.13）
x?xkm从式（2.13）解出
x??xk m? （2.14）
xk?1?xk联立式（2.11）和式（2.14）并消去x，得到 m?证明完毕. 根重数的计算过程
步骤1 给出方程重根的初始近似值 步骤2 牛顿迭代:xk?1?xk?f(xk)，直到连续3次迭代序列{xk}具有单调性； f?(xk)???xk. ?2xk步骤3 取步骤2中连续3次区间单调性的迭代值xk,xk?1,xk?2，计算 ?xk?xk?1?xk,?2xk??xk?1??xk
19
步骤4 代入重数公式m???xk ?2xk2.3 一些其他的求非线性方程重根的方法
针对虚位法在非线性方程求重根时收敛速度太慢，有学者提出了两种改进的虚位法—乘方法和阶乘法在求解非线性方程的重根时可以加快收敛，并且可以方便的在计算机上实现。
1 方法描述 设x?为f(x)的m重根，当x趋近于x?时，f(x)将以x?x?趋近于0.因此采用虚位法时，多是某一端点连续驻留，而另一端点逐步趋近x?，致使收敛趋近不能有效的缩小。Lllinois法和Pegasus法是通过吧连续驻留点的函数值乘以一个缩减因子?来缩小收敛区间的。
乘方法是当某一端点驻留n次时，缩减因子?取某一端点是第一次驻留时，乘方法和阶乘法都是取2 算法描述
（1）非线性方程奇数重根的求解 A 乘方法
输入：初值x1,x2误差限?.
步骤1：计算y1?f(x1)，y2?f(x2)，n?2； 步骤2：计算x?y2?x1?y1?x2；
y2?y1m11，阶乘法则是取。这样当2nn!1，与Lllinois法相当。 2步骤3：如果x?x2?e，输出结果，结束； 步骤4：计算y?f(x)； 步骤5：如果y?y2?0，
则x1?x2,x2?x,y1?y2,y2?y,n?2 否则x2?x,y2?y,??步骤6：返回步骤2。 B. 阶乘法
20
1,y1?y1??,n?n?1； n2