4.8 应用*

4.8.1 多项式求根

考虑 $n$ 次多项式

p _ {n} (x) = a _ {n} x ^ {n} + a _ {n - 1} x ^ {n - 1} + \dots + a _ {1} x + a _ {0}. \tag {4.14}

这里假定 $a_{i}$ 都是实数, 且 $a_{n} \neq 0$ . 由代数学基本定理可知, $p_{n}(x)$ 在复数域中有且仅有 $n$ 的零点 (其中重根按重数计).

当 $n = 1$ 时, 可直接求解. 当 $n = 2$ 时, 可以通过求根公式求解. 当 $n = 3$ 时, 也存在相应的求根公式, 但不那么直观, 需要一定的构造技巧才能导出. 当 $n = 4$ 时, 可以从三次方程求根公式中导出相应的求根公式.

而当 $n \geq 5$ 时, Abel 证明了不存在求根公式, 这意味着只能用数值方法 (迭代法) 求解. 从理论上讲, 任何求解非线性方程的迭代法都可以用来计算多项式的零点, 如著名的 Newton 法. 计算出一个零点后, 通过收缩技术, 将原问题转化为 $n - 1$ 多项式零点问题, 然后继续用迭代法求解. 如此不断重复, 直到求出所有的零点. 但由于舍入误差等原因, 对于高次多项式, 随着计算过程的推进, 计算误差会越来越大, 最后的计算结果往往无法令人满意.

在MATLAB中，命令roots可以计算出多项式的所有零点，其使用的方法就是计算矩阵特征值的QR迭代法.

首先将多项式(4.12)转化为首项系数为1的多项式，记为

q _ {n} (x) = x ^ {n} + c _ {n - 1} x ^ {n - 1} + \dots + c _ {1} x + c _ {0}.

多项式 $q_{n}(x)$ 可以看作是某个 $n$ 阶矩阵的特征值多项式，如：

A = \left[ \begin{array}{c c c c} 0 & & & - c _ {0} \\ 1 & 0 & & - c _ {1} \\ & \ddots & \ddots & \vdots \\ & & 1 & - c _ {n - 1} \end{array} \right]. \tag {4.15}

我们称矩阵 $A$ 为 $q_{n}(x)$ 的友矩阵. 这样, 计算多项式 $q_{n}(x)$ 的零点问题就转化为计算 $A$ 的特征值问题.

由于 $A$ 已经是上Hessenberg矩阵，因此隐式QR迭代法的第一步(上Hessenberg化)就不用做了.虽然 $A$ 上三角部分大多是零，而且分布也很有规律，但无论是单位移QR迭代还是双位移QR迭代，经过一步迭代后，这些零元素都会消失，因此总运算量仍然是 $\mathcal{O}(n^3)$

于是, 如何利用 $A$ 的特殊结构, 降低 QR 方法的运算量和存储量, 一直是颇受关注的问题. 最近, 陆续有学者 [5, 14, 24, 137] 提出了快速 QR 方法, 将运算量降为 $\mathcal{O}(n^2)$ , 存储量也降为 $\mathcal{O}(n)$ . 主要思想是将 $A$ 写成一个酉矩阵与秩一矩阵之差:

A = \left[ \begin{array}{c c c c} 0 & & & 1 \\ 1 & 0 & & 0 \\ & \ddots & \ddots & \vdots \\ & & 1 & 0 \end{array} \right] - \left[ \begin{array}{c} c _ {0} + 1 \\ c _ {1} \\ \vdots \\ c _ {n - 1} \end{array} \right] [ 0, 0, \ldots , 1 ] \triangleq U - x y ^ {\mathsf {T}}.

易知, 经过一次 QR 迭代后, 仍可以写成一个酉矩阵与秩一矩阵之差. 基于这种观察, 就可以设计出快速的 QR 迭代法, 详细过程可参见 [5, 14, 24, 137] 或 [152].

4.8.2 Goolge网页排名：PageRank

To be continued ...

4.8_应用

4.8 应用*

4.8.1 多项式求根

4.8.2 Goolge网页排名：PageRank