19.1.2 多项式方程的解

$n$ 次多项式方程具有如下形式:

$$\begin{array}{}\text{(19.11)}& f\left(x\right)=p_n\left(x\right)=a_n{x}^n+a_{n-1}{x}^{n-1}+\cdots +a_{1}x+a_0=0.\end{array}$$

为求有效解需要这些函数值 $p_n\left(x\right)$ 及其导数值的有效计算方法,以及根的位置的初始估计.

19.1.2.1 霍纳格式

1. 实数情况

为通过 $n$ 次多项式 $p_n\left(x\right)$ 的系数得到在 $x=x_0$ 处的根,首先考虑如下分解:

$$\begin{array}{}\text{(19.12)}& p_n\left(x\right)=a_n{x}^n+a_{n-1}{x}^{n-1}+\cdots +a_{1}x+a_0=\left(x-x_0\right)p_{n-1}\left(x\right)+p_n\left(x_0\right),(1\end{array}$$

这里 $p_{n-1}\left(x\right)$ 表示次数为 $n-1$ 次多项式

$$\begin{array}{}\text{(19.13)}& p_{n-1}\left(x\right)=a_{n-1}^{\prime }{x}^{n-1}+a_{n-2}^{\prime }{x}^{n-2}+\cdots +a_1^{\prime }x+a_0^{\prime }.\end{array}$$

递推公式

$$\begin{array}{}\text{(19.14)}& a_{k-1}^{\prime }=x_0{a}_k^{\prime }+a_k\left(k=n,n-1,\cdots ,0;a_n^{\prime }=0;a_{-1}^{\prime }=p_n\left(x_0\right)\right)\end{array}$$

可以根据 (19.12) 对比 $x^k$ 的系数得到 (注意 $a_{n-1}^{\prime }=a_n$ ). 通过这种方法,多项式 $p_{n-1}\left(x\right)$ 的系数 $a_k^{\prime }$ 与值 $p_n\left(x_0\right)$ 可以通过 $p_n\left(x\right)$ 的系数 $a_k$ 确定. 进一步,重复上述 “传统” 的方法,分解多项式 $p_{n-1}\left(x\right)$ 得到 $p_{n-2}\left(x\right)$ ,

$$\begin{array}{}\text{(19.15)}& p_{n-1}\left(x\right)=\left(x-x_0\right)p_{n-2}\left(x\right)+p_{n-1}\left(x_0\right),\end{array}$$

即得到多项式序列 $p_n\left(x\right),p_{n-1}\left(x\right),\cdots ,p_1\left(x\right),p_0\left(x\right)$ . 计算多项式的系数和相应的值可以表示为

$x_0$	$a_n$
		$a_{n-1}$	$a_{n-2}$	...	$a_3$	$a_2$	$a_1$	$a_0$
		$x_0{a}_{n-1}^{\prime }$	$x_0{a}_{n-2}^{\prime }$	...	$x_0{a}_3^{\prime }$	$x_0{a}_2^{\prime }$	$x_0{a}_1^{\prime }$	$x_0{a}_0^{\prime }$
$x_0$	$a_{n-1}^{\prime }$	$a_{n-2}^{\prime }$	$a_{n-3}^{\prime }$	...	$a_2^{\prime }$	$a_1^{\prime }$	$a_0^{\prime }$	$p_n\left(x_0\right)$
		$x_0{a}_{n-2}^{\prime \prime }$	$x_0{a}_{n-3}^{\prime \prime }$	...	$x_0{a}_2^{\prime \prime }$	$x_0{a}_1^{\prime \prime }$	$x_0{a}_0^{\prime \prime }$
$x_0$	$a_{n-2}^{\prime \prime }$	$a_{n-3}^{\prime \prime }$	$a_{n-4}^{\prime \prime }$	...	$a_1^{\prime \prime }$	$a_0^{\prime \prime }$	$p_{n-1}\left(x_0\right)$
	$x_0{a}_0^{(n-1)}$
$x_0$	$a_1^{(n-1)}$	$p_1\left(x_0\right)$
		$a_0^{\left(n\right)}=p_0\left(x_0\right)$

(19.16)

从格式 (19.16) 得到多项式的值 $p_n\left(x_0\right)$ 及其导数值 $p_n^{\left(k\right)}\left(x_0\right)$ 分别为

$$p_n^{\prime }\left(x_0\right)=1!p_{n-1}\left(x_0\right),p_n^{\prime \prime }\left(x_0\right)=2!p_{n-2}\left(x_0\right),\cdots ,p_n^{\left(n\right)}\left(x_0\right)=n!p_0\left(x_0\right).$$

(19.17)

$l{p}_4\left(x\right)=x^4+2x^3-3x^2-7$ . 根据 (19.16) 计算 $p_4\left(x\right)$ 及其导数在 $x_0=2$ 处的值.

可得

$$p_4\left(2\right)=13,$$$$p_4^{\prime }\left(2\right)=44$$$$p_4^{\prime \prime }\left(2\right)=66,$$$$p_4^{\prime \prime \prime }\left(2\right)=60,$$$$p_4^{\left(4\right)}\left(2\right)=24\text{.}$$

注 (1) 多项式 $p_n\left(x\right)$ 可以表述成 $x-x_0$ 的形式,在这个例子中

$$p_4\left(x\right)={(x-2)}^4+10{(x-2)}^3+33{(x-2)}^2+44\left(x-2\right)+13.$$

(2) 霍纳格式也可以用来计算复系数 $a_k$ . 这种情况下我们需要根据 (19.16 分别计算实部和虚部.

2. 复数情况

如果 (19.11) 中的系数 $a_k$ 为实数,则对复数值 $x_0=u_0+\mathrm{i}{v}_0$ 也可计算 $p_n\left(x_0\right)$ . 为说明这一点,对 $p_n\left(x\right)$ 作如下分解.

$$p_n\left(x\right)=a_n{x}^n+a_{n-1}{x}^{n-1}+\cdots +a_{1}x+a_0$$$$\begin{array}{}\text{(19.18a)}& =\left(x^2-px-q\right)\left(a_{n-2}^{\prime }{x}^{n-2}+\cdots +a_0^{\prime }\right)+r_{1}x+r_0,\end{array}$$

其中

$$\begin{array}{}\text{(19.18b)}& x^2-px-q=\left(x-x_0\right)\left(x-{\overline{x}}_0\right)\text{,即}p=2u_0,q=-\left(u_0{}^2+v_0{}^2\right)\text{.}\end{array}$$

于是

$$\begin{array}{}\text{(19.18c)}& p_n\left(x_0\right)=r_{1}x+r_0=\left(r_1{u}_0+r_0\right)+\mathrm{i}{r}_1{v}_0.\end{array}$$

为得到 (19.18a) 科拉茨 (Collatz) 引进所谓双列霍纳格式 (two-row Horner scheme), 其构造如下:(19.18d)

$$\begin{array}{l}q=a_n+2a_n^{\prime }{a}_n^{\prime }{a}_n^{\prime }{a}_n^{\prime }{a}_n^{\prime }{a}_n^{\prime }\end{array}$$

$◼$ $p_4\left(x\right)=x^4+2x^3-3x^2-7$ 在点 $x_0=2-\mathrm{i}$ 处计算 $p_4$ 的值,即由 $p=4,q=-5$ 得到 $p_4\left(x_0\right)=34x_0-87=-19-34\mathrm{i}$ .

$$\begin{array}{rrrr}12& -3& 0& -7\\ -5& -50& -80& \\ 4& 24& 64& \\ 1& 6& 16& 34\\ & & & \end{array}$$

19.1.2.2 根的位置

1. 实根、斯图姆序列

笛卡儿符号法则给出了多项式方程 (19.11) 是否有实根的原始思想.

a) 正实根的个数等于系数序列

$$\begin{array}{}\text{(19.19a)}& a_n,a_{n-1},\cdots ,a_1,a_0\end{array}$$

改变符号的次数, 或扣除一个偶数.

b) 负实根的个数等于系数序列

$$\begin{array}{}\text{(19.19b)}& a_0,-a_1,a_2,\cdots ,{(-1)}^n{a}_n\end{array}$$

改变符号的次数, 或扣除一个偶数.

$p_5\left(x\right)=x^5-6x^4+10x^3+13x^2-15x-16$ 有 1 个或者 3 个正根以及 0 个或者 2 个负根. 为了得到给定区间(a, b)内实根的个数,可以用斯图姆 (Sturm) 序列 (参见第 57 页 1.6.3.2,2.). 在计算均匀节点 $x_v=x_0+vh\left(h\text{常数,}v=0,1,2,\cdots \right)$ 上的函数值 $y_v=p_n\left(x_v\right)$ (利用霍纳格式容易执行) 后,可得函数图形和根的位置的好的猜测. 如果 $p_n\left(c\right)$ 和 $p_n\left(d\right)$ 有不同的符号,在 $c$ 与 $d$ 之间至少存在一个实根.

2. 复根

为了在有界复平面区域上限定实数根或者复数根的位置, 考察如下多项式方程, 这是 (19.11) 的简单推广:

$$\begin{array}{}\text{(19.20)}& f^{\ast }\left(x\right)=\left|a_{n-1}\right|r^{n-1}+\left|a_{n-2}\right|r^{n-2}+\cdots +\left|a_1\right|r+\left|a_0\right|=\left|a_n\right|r^n.\end{array}$$

通过系统的重复试错,对 (19.20) 的正根决定一个上界 $r_0$ . 于是对 (19.11) 所有的根 $x_k^{\ast }\left(k=1,2,\cdots ,n\right)$ 有

$$\begin{array}{}\text{(19.21)}& \left|x_k^{\ast }\right|\le r_0\end{array}$$$$f\left(x\right)=p_4\left(x\right)=x^4+4.4x^3-20.01x^2-50.12x+29.45=0,f^{\ast }\left(x\right)=4.4r^3+$$

$20.01r^2+50.12r+29.45=r^4$ ,某些试验是

$$r=6:f^{\ast }\left(6\right)=2000.93>1296=r^4,$$$$r=7:f^{\ast }\left(7\right)=2869.98>2401=r^4,$$$$r=8:f^{\ast }\left(8\right)=3963.85<4096=r^4.$$

据此有 $\left|x_k^{\ast }\right|<8\left(k=1,2,3,4\right)$ . 实际上,对于有最大绝对值的根 $x_1^{\ast },-7<x_1^{\ast }<-6$ 成立.

注 为确定带负实部的复根个数, 在电子技术所谓根轨迹理论中发展了一种特别的方法, 该方法可用来检验稳定性 (见 [19.14][19.40]).

19.1.2.3 数值方法

1. 一般方法

在 19.1.1 讨论的方法可用来求多项式方程的实数根. 牛顿法由于其快速收敛性以及函数值 $f\left(x_n\right)$ 与导数值 $f^{\prime }\left(x_n\right)$ 可用霍纳法则容易计算,非常适用于多项式方程. 假设多项式方程 $f\left(x\right)=0$ 的根 $x^{\ast }$ 的近似值 $x_n$ 充分好,则修正项 $\delta =x^{\ast }-x_n$ 可以用不动点方程

$$\begin{array}{}\text{(19.22)}& \delta =\frac{1}{f^{\prime }\left(x_n\right)}\left[f\left(x_n\right)+\frac{1}{2}{f}^{\prime \prime }\left(x_n\right)+\cdots \right]=\phi \left(\delta \right)\end{array}$$

迭代修正

2. 特殊方法

贝尔斯托 (Bairstow) 法常用于求成对的根, 尤其是成对的共轭复根. 该方法类似于霍纳格式 $\left(19.18\mathrm{a}\sim 19.18\mathrm{d}\right)$ ,从求给定多项式的二次因子出发,通过确定系数 $p$ 和 $q$ ,使得线性余项 $r_1$ 和 $r_0$ 的系数等于零 ([19.38],[19.14],[19.40]).

如果需要计算根的绝对值的最大值与最小值, 可以选择使用伯努利方法 (见[19.38]).

格雷费 (Graeffe) 法有某些历史重要性. 它同时给出包括复共轭根在内的所有的根; 然而其计算量非常巨大 ([19.14],[19.40]).