§4 实根的近似计算
设f(x)为已知连续函数，ξ是方程
f(x)=0
的根，这里方程可以是一般方程（代数方程或超越方程）.在实际问题中都给出了根的范围，例如代数方程
f(x)=a0xn+a1xn－1+L+an－1x+an=0
的根ξ的范围是
|ξ|£1+max{|a1|,|a2|,L,|an|}
因此可以假定方程在区间(a,b)内只有一个根（若有两个根，则将区间的一个端点换为使(x)=0的点）.并由函数的连续性可知，一般来说，在根的附近f(x)是异号的（当(ξ)=0或除外），所以在下面介绍的各种近似计算中，都假定f(a)和f(b)异号.
一、秦九韶法*
秦九韶法基本上是通过逐次试验求根的近似值的方法，试验次数愈多，所得近似值愈接近根的真值.系统地继续这一过程，直至达到预定的有效数字的位数.现举例具体说明这个方法.
例 求方程
f(x)=
(1)
的根到五位有效数字.
应用笛卡尔符号法则可知这个方程有一个正根.由于f(1)＝－11，f(2)＝14，这个正根在(1,2)之间.
现在应用秦九韶法求这个方程的近似根.先设，这里表示1到所求根的距离.应用多项式的泰勒公式(秦九韶法,见§2,一)，得到关于的方程
(2)
其算式为
现在求纯小数的近似值，由于纯小数的三次方或二次方的值更小，可暂舍去方程(2)的头两项而来计算21－11＝0，即＝0.5238….但舍去的两项是正的，这个值显得太大.当＝0.500时，方程(2)的左边各项的和是仍是正数(0.375)，而当＝0.400时，方程(2) 的左边各项的和是负数(－2.056).因此，设,即，再应用多项式的泰勒公式，得到关于h的方程
(3)
其算式为
* 我国古代数学家秦九韶在他所著的<<数书九章>>(1247)，给出一个求代数方程的根近似值
的方法，这个方法一般书上都称为和纳法.实际上和纳在1819年才提出这个方法，比秦九
韶晚五百多年.
现在求小数h的近似值，舍去头两项，求得h＝0.08609….因舍去两个正量，所得的h太大，所以设h＝0.08,即.应用上述方法得到关于的方程
(4)
同上面一样，从方程(4)的后两项求得设,即得到关于的方程
(5)
从后两项求出的近似值=0.0008…,因舍去的都是正量，所以方程(5)的根在0.0008和0.00081之间.
现在把(2),(3),(4),(5),的各个近似值0.4,0.08,0.004,0.0008相加得总和0.4848,然后加到第一次近似值1上，所以方程(1)的根在1.4848与1.48481之间，取五位有效数字为1.4848.
用秦九韶法还能求负的近似值.想求f(x)＝0的一切负实根，可先求 f(－x)的正实根，然后改变符号，即得负实根.
二、二分法
假定f(x)在[a,b]上连续，且f(a)f(b)<0（这里假定f(a)<0,f(b)>0）,取区间[a,b]的中点，若=0，则f(x)=0的根是ξ=.不然，若>0，则令a1=a,b1=；若<0，则令a1=,b1=b.于是形成新区间[a1,b1]，它包含f(x)=0的根ξ（图3.2）.
再取[a1,b1]的中点，若=0，则ξ=.若>0，则令a2=a1,b2=；若<0，则令a2=,b2=b1.于是又形成新区间[a2,b2]，其长度等于，它包含方程f(x)=0的根ξ.…若允许误差ε=，则按这个过程作出区间[a1,b1],
[a2,b2], [a3,b3],L, [an,bn],n=（[x]表示x的整数部分），于是
ξ*=
是方程f(x)=0的近似根，误差不超过
|ξ-ξ*|££
二分法是求实根的近似计算中行之有效的最简单的方法，它只要求函数是连续的，因此它的使用范围很广，并便于在电子计算机上实现.但是它不能求重根，也不能求虚根.
三、迭代法
把方程f(x)=0表成它的等价形式
x=j(x)
或一般地
f1(x)=f2(x)
式中f1(x)是这样一个函数：对任意实数c，能容易算出方程f1(x)=c的精确度很高的实根.如果对任意a£x1£b,a£x2£b，下式成立：
则下面迭代过程是收敛的.
首先从一个近似根x0出发（x0可由图解法粗略估计出），代入方程右边，解方程
f1(x)=f2(x0)
得到第一个近似根x=x1，再解方程
f1(x)=f2(x1)
得到第二个近似根x=x2，L,类似地由第n个近似根xn，解方程
f1(x)=f2(xn)
得到第n+1个近似根x=xn+1，于是得到一系列不同精确度的近似根
x0, x1, x2,L, xn,L
它收敛于方程的根ξ（图3.3）.
收敛速度（即误差消失速度）与an相当，而
a
用
代替x2可加速收敛.式中Dx1=x2－x1为x1的一阶差分，D2x0=Dx1－Dx0为x0的二阶差分.
对于方程x=j(x)，只要j(x)在[a,b]上连续，且q<1，那末，它的根可由
x1=j(x0)
x2=j(x1)
LLLL
xn+1=j(xn)
来接近（图3.4）.
四、牛顿法
1．一般牛顿法
设f(x)在[a,b]上连续，也连续，且¹0,¹0，f(a)f(b)<0（设f(a)<0,f(b)>0），过点(a,f(a))（或点(b,f(b)）)作曲线的切线：
（或）
它和x轴的交点为x=a－（或x=b－）
用迭代公式
xn+1=xn－
并取初始值
x0=
可计算出方程f(x)=0的根的近似值（图3.5）.误差ïx－xnï不超过
一般选取的初始值x0，要满足不等式
2．近似牛顿法
如果不易算出，可改用差商代替，得出近似牛顿法迭代程序：
xn+1=xn
3．逐次压缩牛顿法
求实系数代数方程
f(x)=a0xn+a1xn-1+L+an=0
的单实根时，用牛顿法求出一个实根x0后，可把多项式的次数降低一次，降低次数后的多项式系数bk为
b0=a0
bk=ak+x0bk-1 (k=1,2,L,n－1)
然后，再把求出的实根作为初始近似值，用同法求出再次降低次数的多项式的实根，依此求出全部单实根.
4．牛顿法解非线性方程组
假设非线性方程组
存在一组近似解P0=(x0,y0)，且
可用迭代公式：
xn+1=xn+
yn+1=yn+
式中Pn为点(xn,yn)，Jn为雅可比式J在Pn的值：
五、弦截法（线性插值法）
假设f(x)在[a,b]上连续，,都不变号，且f(a)f(b)<0（这里假定f(a)<0,f(b)>0）.过点(a,f(a))和(b,f(b))的直线是：
(或)
它和x轴的交点是x=a－（或x=b－）.
（a）当>0时，用迭代公式
可求出方程的近似根（图3.6(a)）.
（b）当<0时，用迭代公式
可求出方程f(x)=0的近似根（图3.6(b)）.
六、联合法（牛顿法与弦截法联合使用）
假设f(x)在[a,b]上连续，,都不变号，且f(a)f(b)<0（这里假定f(a)<0,f(b)>0）.
（a）当f(a)与同号时（图3.7(a)），用迭代公式
x1=a
=b
x2=x1
=
LLLLLLL
xn=xn-1
=
可求出方程f(x)=0的近似根.
（b）当f(a)与异号时（图3.7(b)），用迭代公式
x1=a
=b
x2=x1
=
LLLLLLLL
xn=xn-1
=
可求出方程f(x)=0的近似根.
误差或.
七、抛物线法（穆勒法）
求实系数n次方程
f(x)=xn+a1xn-1+L+an=0
(1)
的近似根.
可先求出f(x)=0的一个根x=r，则
f(x)=(x-r)g(x)
=(x－r)(xn－1+b1xn－2+L+bn－1)
式中g(x)是n－1次多项式，然后再求出g(x)的根，依此类推，可以求出f(x)=0的全部实根来.
首先选取x轴上三点：x0,x1,x2,通过曲线y=f(x)上的三点：(x0,f(x0)), (x1,f(x1)),(x2,f(x2))作一抛物线y=P(x)（即拉格朗日插值多项式，见第十七章，§2，三），抛物线与x轴有两个交点，取离x2较近的一点作为x3；再过三点(x1,f(x1)),
(x2,f(x2)), (x3,f(x3))作一抛物线（图3.8中的虚线），它与x轴有两个交点，取离x3较近的一点作为x4L，依此法作出点xi-2, xi-1,
xi，再过三点(xi-2,f(xi-2)),
(xi-1,f(xi-1)),
(xi,f(xi))作一抛物线与x轴有两个交点，取离xi较近的一点作为xi+1，等等.
对于预先给定的允许误差e，当迭代过程进行到
ïxi+1-xiï 时，就取xi+1作为f(x)=0的一个近似根. 由此得到的序列是收敛的.极限值，就是方程f(x)=0的根. 迭代步骤如下： （1）根据经验对上式（1）可取 x0=－1, x1=1, x2=0 作为初始值，于是 f(x0)=(－1)n+(－1)n－1a1+L－an－1+an f(x1)=1+a1+L+an f(x2)=an 或用x=0附近的近似值 f(x0)»an－2－an－1+an f(x1) »an－2+an－1+an f(x2)=an （2）设 li=, di=1+li= gi=f(xi－2)li2 －f(xi-1)lidi +f(xi)li hi=f(xi-2)li2 -f(xi-1)di2 +f(xi)(li+di) 由此根据xi-2, xi-1, xi 计算出li, di, gi, hi，并根据下列公式计算出li+1 li+1= （hi>0，根式取正号；hi<0，根式取负号） 当f(xi-2)=f(xi-1)=f(xi)时，取li+1=1. （3）根据公式 xi+1=li+1(xi－xi-1)+xi 计算出xi+1 八、林士谔—赵访熊法（劈因子法） 由于解二次方程是容易的，因此在求实系数代数方程 f(x)=xn+a1xn－1+L+an－1x+an=0 的复根时，如果找出f(x)的一个二次因子，就等于找到方程的一对复根. 设f(x)的一个近似二次因子（任意选取）为 w (x)=x2+px+q 可用下述方法使它精确化： （1）用w (x)去除f(x)，得到商式Q(x)和余式R(x)，即 f(x)= w (x)Q(x)+R(x) =(x2+px+q)(xn－2+b1xn－3+L+bn－3x+bn－2)+(r1t+r2) 式中商式与余式的系数可用下面的递推公式算出： bk=ak-pbk-1-qbk-2, k=1,2,L,n b-1=0, b0=1 r1=bn-1=an-1-pbn-2-qbn-3 r2=bn+pbn-1=an-qbn-2 （2）用w (x)去除xQ(x)得到余式 R[1](x)=R11x＋R21` 式中R11,R21，由下面的递推公式算出： ck=bn-pck-1-qck-2, k=1,2,L,n-3 c-1=0, c0=1 R11=bn-2-pcn-3-qcn-4 R21=-qcn-3 （3）用w (x)去除Q(x)得到余式 R[2](x)=R12x＋R22` 式中R12,R22，由下面的公式算出： R12=bn-3-pcn-4-qcn-5 R21=bn-2-qcn-4 （4）解二元一次线性方程组 得到u,. （5）修正后的二次式为 w [1](x)=x2+(p+u)x+(q+) 如果它还不够精确，再重复（1）至（5）的步骤进行修正，直到足够精确为止. 林士谔—赵访熊法求实系数代数方程的复根，其优点是避免了复数运算，缺点是程序比较复杂. 九、下降法 对任意实系数超越方程组 (1) 定义目标函数 F(x1,x2,L,xn)= 如果F(x1,x2,L,xn) 具体计算步骤如下： （1）任取一组初始值x1(0),x2(0),L,xn(0)（全不为零），设已按照下述过程计算到第m步得到一组值：x1(m),x2(m),L,xn(m) （2）计算 Fm=F(x1(m),x2(m),L,xn(m)) （3）若Fm [F(x1(m),x2(m),L,xi(m)+Hi,L, xn(m))-F（x1(m),x2(m),L,xn(m)）] Hi=wxi(m) i=1,2,L,n （4）计算 xi(m+1)= xi(m), i=1,2,L,n 式中 得到一组{xi(m+1)}，再重复（2），（3）,（4）的计算.