§4  实根的近似计算

设f(x)为已知连续函数，ξ是方程

f(x)=0

的根，这里方程可以是一般方程（代数方程或超越方程）.在实际问题中都给出了根的范围，例如代数方程

f(x)=a₀xⁿ+a₁x^n－1+L+a_n－1x+a_n=0

的根ξ的范围是

|ξ|£1+max{|a₁|,|a₂|,L,|a_n|}

因此可以假定方程在区间(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，则令a₁=a,b₁=；若<0，则令a₁=,b₁=b.于是形成新区间[a₁,b₁]，它包含f(x)=0的根ξ（图3.2）.

再取[a₁,b₁]的中点，若=0，则ξ=.若>0，则令a₂=a₁,b₂=；若<0，则令a₂=,b₂=b₁.于是又形成新区间[a₂,b₂]，其长度等于，它包含方程f(x)=0的根ξ.…若允许误差ε=，则按这个过程作出区间[a₁,b₁], [a₂,b₂], [a₃,b₃],L, [a_n,b_n],n=（[x]表示x的整数部分），于是

ξ^*=

是方程f(x)=0的近似根，误差不超过

|ξ-ξ^*|££

二分法是求实根的近似计算中行之有效的最简单的方法，它只要求函数是连续的，因此它的使用范围很广，并便于在电子计算机上实现.但是它不能求重根，也不能求虚根.

三、迭代法

把方程f(x)=0表成它的等价形式

x=j(x)

或一般地

f₁(x)=f₂(x)

式中f₁(x)是这样一个函数：对任意实数c，能容易算出方程f₁(x)=c的精确度很高的实根.如果对任意a£x₁£b,a£x₂£b，下式成立：

则下面迭代过程是收敛的.

首先从一个近似根x₀出发（x₀可由图解法粗略估计出），代入方程右边，解方程

f₁(x)=f₂(x₀)

得到第一个近似根x=x₁，再解方程

f₁(x)=f₂(x₁)

得到第二个近似根x=x₂，L,类似地由第n个近似根x_n，解方程

f₁(x)=f₂(x_n)

得到第n+1个近似根x=x_n+1，于是得到一系列不同精确度的近似根

x₀,  x₁,  x₂,L, x_n,L

它收敛于方程的根ξ（图3.3）.

收敛速度（即误差消失速度）与aⁿ相当，而

a

用

代替x₂可加速收敛.式中Dx₁=x₂－x₁为x₁的一阶差分，D²x₀=Dx₁－Dx₀为x₀的二阶差分.

对于方程x=j(x)，只要j(x)在[a,b]上连续，且q<1，那末，它的根可由

x₁=j(x₀)

x₂=j(x₁)

LLLL

x_n+1=j(x_n)

来接近（图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－）

用迭代公式

x_n+1=x_n－

并取初始值

x₀=

可计算出方程f(x)=0的根的近似值（图3.5）.误差ïx－x_nï不超过

一般选取的初始值x₀，要满足不等式

2．近似牛顿法

如果不易算出，可改用差商代替，得出近似牛顿法迭代程序：

x_n+1=x_n

3．逐次压缩牛顿法

求实系数代数方程

f(x)=a₀xⁿ+a₁x^n-1+L+a_n=0

的单实根时，用牛顿法求出一个实根x₀后，可把多项式的次数降低一次，降低次数后的多项式系数b_k为

b₀=a₀

b_k=a_k+x₀b_k-1  (k=1,2,L,n－1)

然后，再把求出的实根作为初始近似值，用同法求出再次降低次数的多项式的实根，依此求出全部单实根.

4．牛顿法解非线性方程组

假设非线性方程组

存在一组近似解P₀=(x₀,y₀)，且

可用迭代公式：

x_n+1=x_n+

y_n+1=y_n+

式中P_n为点(x_n,y_n)，J_n为雅可比式J在P_n的值：

五、弦截法（线性插值法）

假设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)），用迭代公式

x₁=a

=b

x₂=x₁

=

LLLLLLL

x_n=x_n-1

=

可求出方程f(x)=0的近似根.

（b）当f(a)与异号时（图3.7(b)），用迭代公式

x₁=a

=b

x₂=x₁

=

LLLLLLLL

x_n=x_n-1

=

可求出方程f(x)=0的近似根.

误差或.

七、抛物线法（穆勒法）

求实系数n次方程

f(x)=xⁿ+a₁x^n-1+L+a_n=0               (1)

的近似根.

可先求出f(x)=0的一个根x=r，则

                      f(x)=(x-r)g(x)

                         =(x－r)(x^n－1+b₁x^n－2+L+b_n－1)

式中g(x)是n－1次多项式，然后再求出g(x)的根，依此类推，可以求出f(x)=0的全部实根来.

首先选取x轴上三点：x₀,x₁,x₂,通过曲线y=f(x)上的三点：(x₀,f(x₀)), (x₁,f(x₁)),(x₂,f(x₂))作一抛物线y=P(x)（即拉格朗日插值多项式，见第十七章，§2，三），抛物线与x轴有两个交点，取离x₂较近的一点作为x₃；再过三点(x₁,f(x₁)), (x₂,f(x₂)), (x₃,f(x₃))作一抛物线（图3.8中的虚线），它与x轴有两个交点，取离x₃较近的一点作为x₄L，依此法作出点x_i-2, x_i-1, x_i，再过三点(x_i-2,f(x_i-2)), (x_i-1,f(x_i-1)), (x_i,f(x_i))作一抛物线与x轴有两个交点，取离x_i较近的一点作为x_i+1，等等.

对于预先给定的允许误差e，当迭代过程进行到

ïx_i+1-x_iï<e

时，就取x_i+1作为f(x)=0的一个近似根.

由此得到的序列是收敛的.极限值，就是方程f(x)=0的根.

迭代步骤如下：

（1）根据经验对上式（1）可取

x₀=－1,  x₁=1,      x₂=0

作为初始值，于是

f(x₀)=(－1)ⁿ+(－1)^n－1a₁+L－a_n－1+a_n

f(x₁)=1+a₁+L+a_n

f(x₂)=a_n

或用x=0附近的近似值

f(x₀)»a_n－2－a_n－1+a_n

f(x₁) »a_n－2+a_n－1+a_n

f(x₂)=a_n

（2）设

l_i=,     d_i=1+l_i=

g_i=f(x_i－2)l_i² －f(x_i-1)l_id_i +f(x_i)l_i

h_i=f(x_i-2)l_i² -f(x_i-1)d_i² +f(x_i)(l_i+d_i)                         

由此根据x_i-2, x_i-1, x_i 计算出l_i, d_i, g_i, h_i，并根据下列公式计算出l_i+1

l_i+1=

（h_i>0，根式取正号；h_i<0，根式取负号）

当f(x_i-2)=f(x_i-1)=f(x_i)时，取l_i+1=1.

（3）根据公式

x_i+1=l_i+1(x_i－x_i-1)+x_i

计算出x_i+1

八、林士谔—赵访熊法（劈因子法）

由于解二次方程是容易的，因此在求实系数代数方程

f(x)=xⁿ+a₁x^n－1+L+a_n－1x+a_n=0

的复根时，如果找出f(x)的一个二次因子，就等于找到方程的一对复根.

设f(x)的一个近似二次因子（任意选取）为

w (x)=x²+px+q

可用下述方法使它精确化：

（1）用w (x)去除f(x)，得到商式Q(x)和余式R(x)，即

                      f(x)= w (x)Q(x)+R(x)

=(x²+px+q)(x^n－2+b₁x^n－3+L+b_n－3x+b_n－2)+(r₁t+r₂)

式中商式与余式的系数可用下面的递推公式算出：

b_k=a_k-pb_k-1-qb_k-2,  k=1,2,L,n

b_-1=0,    b₀=1

r₁=b_n-1=a_n-1-pb_n-2-qb_n-3

r₂=b_n+pb_n-1=a_n-qb_n-2

（2）用w (x)去除xQ(x)得到余式

R^[1](x)=R₁₁x＋R_21`

式中R₁₁,R₂₁，由下面的递推公式算出：

c_k=b_n-pc_k-1-qc_k-2,  k=1,2,L,n-3

c_-1=0,     c₀=1

R₁₁=b_n-2-pc_n-3-qc_n-4

R₂₁=-qc_n-3

（3）用w (x)去除Q(x)得到余式

R^[2](x)=R₁₂x＋R_22`

式中R₁₂,R₂₂，由下面的公式算出：

R₁₂=b_n-3-pc_n-4-qc_n-5

R₂₁=b_n-2-qc_n-4

（4）解二元一次线性方程组

得到u,.

（5）修正后的二次式为

w ^[1](x)=x²+(p+u)x+(q+)

如果它还不够精确，再重复（1）至（5）的步骤进行修正，直到足够精确为止.

林士谔—赵访熊法求实系数代数方程的复根，其优点是避免了复数运算，缺点是程序比较复杂.

九、下降法

对任意实系数超越方程组

         (1)

定义目标函数

F(x₁,x₂,L,x_n)=

如果F(x₁,x₂,L,x_n)<e（e为在一定精确度下给定的适当小的正数），则认为x₁,x₂,L,x_n为方程组（1）的解.

具体计算步骤如下：

（1）任取一组初始值x₁⁽⁰⁾,x₂⁽⁰⁾,L,x_n⁽⁰⁾（全不为零），设已按照下述过程计算到第m步得到一组值：x₁^(m),x₂^(m),L,x_n^(m)

（2）计算

F_m=F(x₁^(m),x₂^(m),L,x_n^(m))

（3）若F_m<e，则x₁^(m),x₂^(m),L,x_n^(m)是所求的解，否则计算n个偏导数：

[F(x₁^(m),x₂^(m),L,x_i^(m)+H_i,L, x_n^(m))-F（x₁^(m),x₂^(m),L,x_n^(m)）]

H_i=wx_i^(m) i=1,2,L,n

（4）计算

x_i^(m+1)= x_i^(m),      i=1,2,L,n

式中

得到一组{x_i^(m+1)}，再重复（2），（3）,（4）的计算.