求根算法

在数学和电脑运算中，对于一个已知的从实数集合映射到实数集合，或者从复数集合映射到复数集合的连续函数$f(x)$，搜索变量$x$使得$f(x)=0$（此时，变量$x$称为$f(x)=0$的根、$f(x)$的零点）的算法，称为求根算法。在许多情况下，函数的零点无法被准确计算出，也无法被解析解表示；是故，求根算法在实数集合下只提供一个以浮点数表示的近似解，或者一个足够小的解的存在区间，在复数集合下只提供一个复根的圆盘（输出一个区间或一个圆盘等价于输出一个根的近似值及其误差上限）。

解方程$f(x)=g(x)$与求$f(x)-g(x)$的根是等价的。因此求根算法可以求解任何以连续函数定义的方程。然而，许多情况下，求根算法只能找到方程的某些根，而不能保证所有根都能找到；特别指出，算法未找到根，并不代表方程确实无根。

大多数的数值求根算法都使用叠代法，生成一个以方程的根为极限的收敛数列。它们需要一个或多个根作为叠代的初期值，嗣后每次叠代都生成一个逐步逼近根的值。由于叠代法必须在有限步内终止于某个点，这些方法都只能提供一个根的近似值，而不能提供一个精确解。 许多方法是通过代入上一个叠代值来计算一个辅助方程，从而得出下一个叠代值的。此处所指的辅助方程是指为了使源方程的根是一个定点并使叠代值能更快地收敛到这些定点而设计的一个方程，因此叠代值的极限是这个辅助方程的一个定点。

求根算法的性能是数值分析的研究范畴。一种算法的效率可能大幅度取决于已知点的性质。例如，一部分算法都使用输入函数的导数（此要求函数不但连续，而且可导），而其他算法则能用于任何一个连续函数。在一般情况下，数值算法不能保证找到一个函数的所有根，因此算法未能找到根并不能证明方程无根。然而，对于多项式，存在特定的使用代数学性质以定位根的所在区间（或复根所在的圆盘）的算法，这个区间（或圆盘）足够小以能保证数值算法（例如牛顿法）能收敛到唯一被定位的根。

包围法

包围法是指通过叠代确定根的所在区间，并逐渐缩小其区间长度的算法。当区间变得足够小时，则认为根已经被找到。一般地，包围法以介值定理为基础，且能够求出根的绝对误差上限；而当函数是一个多项式时，还有其它基于施图姆定理或笛卡儿符号法则的方法，能够在一个区间内求出精确的根。

二分法

最简单的求根算法为二分法︰令$f(x)$为一个连续函数，且已知存在区间$[a,b]$满足$f(a)$和$f(b)$符号互异。令$c=(a+b)/2$（区间的中点），则$f(a)$和$f(c)$或$f(c)$和$f(b)$中，必恰有一者符号互异，并将已知根所在区间的长度缩短为一半。对被缩短的区间重复上述步骤，直到找到根。

纵二分法具有强健性，但其只能求得区间内的一个且只有一位精度的解。此外在合适的条件下，亦存在其他能更快求得精确解的方法。

盈不足术法

盈不足术法与二分法相似。异处在于，盈不足术以方式计算出叠代点，

$c={\frac {af(b)-bf(a)}{f(b)-f(a)}}.$

盈不足术法也类似于割线法。异处在于，盈不足术法不保留前两次叠代点，而是在根的两侧各保留一点。 盈不足术法能以较二分法更快的速度求根，且不会如割线法一样发散（不收敛）；但在一些简单实现的情形中可能因为舍入误差而无法收敛。

Ridders法是盈不足术法的一个变形。其使用区间中点的函数值，构造出一个具有相同零点的函数，再用盈不足术法求解之。这个方法维持了一定的强健性外，亦使算法更快收敛。

插值法

许多求根算法通过插值来实现。即，使用上一步计算出的根的多个近似值，借助一个以插值法求出的低次多项式，以逼近一个函数。然后计算多项式的根，并用其作新的函数的根的近似值，重复此流程。

两个函数值可利用插值法求得一个一次多项式，即以一条直线逼近一个函数图像。此乃割线法及盈不足术法的基础。进而，三个函数值可求得一个二次函数，即以一条抛物线逼近一个函数图像。此即Muller法。

叠代法

虽然所有求根算法都通过叠代，但一个叠代的求根算法，通常使用一种特定的叠代类型，包括定义一个辅助函数，应用上一步计算出的根的近似值，求得新的近似值。辅助函数到逹一个定点（到逹所需的精度），即新叠代的近似值充分接近上一个叠代值时，叠代停止。

牛顿法（及类似的以导数为基础的方法）

牛顿法假定函数$f$的导数是连续的。如果起始点距离根太远，牛顿法可能不收敛。然而，其若收敛，速度将较二分法快，且通常为二次收敛。牛顿法也是一种重要的算法，因为它能容易地推广到高维问题。类似牛顿法且有更高次的收敛性的算法为Householder法。具有三次收敛性的Householder法是Halley法。

割线法

将牛顿法中的导数替换为一个差分式，即得到割线法。 这种方法的优点在于不需要计算导数，但其代价是收敛速度较慢（收敛次数约为1.6）。把割线法推广到高维的算法是Broyden法。

逆插值法

对函数$f$进行逆插值，能够避免插值法中出现复数。这种方法称为逆二次插值法。其收敛速度渐近快于割线法；但当叠代离根较远时，逆二次插值法往往表现不佳。

算法组合

Brent法

Brent法是二分法，割线法同逆二次插值法的组合。在每一次叠代，Brent法会决定此三者中何种的效果最好，然后使用该种方法执行一次叠代。此法快捷并强健，故甚流行。

参见

• Broyden法
• 求根算法列表
• 重复度
• 最大公因式
• Graeffe法
• 密码学安全伪随机数生成器，一个特别设计的无法以求根算法求解的函数组。
• 多项式方程组，用求根算法求解多变量问题。
• MPSolve
• GNU科学库

参考文献

脚注

来源

• Press, W. H.; Teukolsky, S. A.; Vetterling, W. T.; Flannery, B. P. Chapter 9. Root Finding and Nonlinear Sets of Equations. Numerical Recipes: The Art of Scientific Computing 3rd. New York: Cambridge University Press. 2007 [2017-08-18]. ISBN 978-0-521-88068-8. （原始内容存档于2011-08-11）. 

外部链接

• GAMS: Roots of polynomials with real coefficients （页面存档备份，存于互联网档案馆）
• Free online polynomial root finder for both real and complex coefficients （页面存档备份，存于互联网档案馆）
• Kehagias, Spyros: RealRoots, a free App for iPhone, iPod Touch and iPad to compare Sturm's method and VAS https://itunes.apple.com/gr/app/realroots/id483609988?mt=8 （页面存档备份，存于互联网档案馆）