4.5.3 超定线性方程组

4.5.3.1 超定线性方程组和线性最小二乘问题

1. 超定方程组

考虑具有长方系数矩阵 $\mathbf{A}=\left(a_{ij}\right)\left(i=1,2,\cdots ,m;j=1,2,\cdots ,n;m>n\right)$ 的线性方程组

$$\begin{array}{}\text{(4.187)}& A\underset{―}{x}=\underset{―}{b}.\end{array}$$

矩阵 $\mathbf{A}$ 和右边的向量 $\underset{―}{\mathbf{b}}={(b_1,b_2,\cdots ,b_m)}^{\mathrm{T}}$ 是给定的,向量 $\underset{―}{\mathbf{x}}={(x_1,x_2,\cdots ,x_n)}^{\mathrm{T}}$ 是未知的. 因为 $m>n$ ,所以这个方程组称为超定组. 我们可以讨论解的存在性和唯一性, 并且有时还可用 (例如) 选主元法求解.

2. 线性最小二乘问题

如果 (4.187) 是表示实际问题的数学模型 (即 $\mathbf{A},\underset{―}{\mathbf{b}},\underset{―}{\mathbf{x}}$ 是实的),那么因为测量或其他误差,不可能求出 (4.187) 满足所有方程的精确解. 如果代入任何向量 $\underset{―}{\mathbf{x}}$ ,那么将产生由

$$\begin{array}{}\text{(4.188)}& \underset{―}{\mathbf{r}}=\mathbf{A}\underset{―}{\mathbf{x}}-\underset{―}{\mathbf{b}},\underset{―}{\mathbf{r}}\ne \underset{―}{\mathbf{0}}\end{array}$$

给出的残差向量 $\underset{―}{r}={(r_1,r_2,\cdots ,r_m)}^{\mathrm{T}}$ . 在此情形要确定 $\underset{―}{x}$ 使得残差向量的模尽可能小. 现在设 $\mathbf{A},\underset{―}{\mathbf{b}},\underset{―}{\mathbf{x}}$ 是实的. 如果考虑欧氏模,那么必须有

$$\begin{array}{}\text{(4.189)}& \sum _{i=1}^m{r}_i^2={\underset{―}{\mathbf{r}}}^{\mathrm{T}}\underset{―}{\mathbf{r}}={(\mathbf{A}\underset{―}{\mathbf{x}}-\underset{―}{\mathbf{b}})}^{\mathrm{T}}\left(\mathbf{A}\underset{―}{\mathbf{x}}-\underset{―}{\mathbf{b}}\right)=min,\end{array}$$

即残差平方和必须极小. 高斯就已经有这样的思想. 公式 (4.189) 称为线性最小二乘方问题. 残差向量 $\underset{―}{r}$ 的模 $\parallel \underset{―}{r}\parallel =\sqrt{{\underset{―}{r}}^{\mathrm{T}}\underset{―}{r}}$ 称为残差.

3. 高斯变换

如果残差向量 $\underset{―}{r}$ 与 $\mathbf{A}$ 的每个列正交,那么向量 $\underset{―}{x}$ 是 (4.189) 的解. 这就是

$$\begin{array}{}\text{(4.190)}& {\mathbf{A}}^{\mathrm{T}}\underset{―}{\mathbf{r}}={\mathbf{A}}^{\mathrm{T}}\left(\mathbf{A}\underset{―}{\mathbf{x}}-\underset{―}{\mathbf{b}}\right)=\underset{―}{\mathbf{0}}\text{ 或 }{\mathbf{A}}^{\mathrm{T}}\mathbf{A}\underset{―}{\mathbf{x}}={\mathbf{A}}^{\mathrm{T}}\underset{―}{\mathbf{b}}.\end{array}$$

方程 (4.190) 实际上是系数矩阵是方阵的线性方程组. 将它称为正规方程组. 它的维数为 $n$ . 由 (4.187) 到 (4.190) 的转化称作高斯变换. 矩阵 ${\mathbf{A}}^{\mathrm{T}}\mathbf{A}$ 是对称的.

如果矩阵 $\mathbf{A}$ 的秩为 $n$ (因为 $m>n$ ,所以 $\mathbf{A}$ 的所有列是线性无关的),那么矩阵 ${\mathbf{A}}^{\mathrm{T}}\mathbf{A}$ 是正定的,因而是正则的,即如果 $\mathbf{A}$ 的秩等于未知数的个数,那么正规方程组有唯一解.

4.5.3.2 对最小二乘问题数值解的建议

1. 楚列斯基方法

因为矩阵 ${\mathbf{A}}^{\mathrm{T}}\mathbf{A}$ 是对称的,并且在 $\mathrm{rank}\left(\mathbf{A}\right)=n$ 的情形是正定的,所以为解正规方程组我们可以应用楚列斯基方法 (参见第 1245 页 19.2.1.2). 不幸的是, 这个算法虽然在 “大” 残差 $\parallel \underset{―}{r}\parallel$ 和 “小” 解 $\parallel \underset{―}{x}\parallel$ 的情形实施得还算不错,但在数值上是相当不稳定的.

2. 豪斯霍尔德方法

适用于解最小二乘问题的数值方法是正交化方法,它基于分解 $\mathbf{A}=\mathbf{QR}$ . 特别适用的是豪斯霍尔德方法,其中 $\mathbf{Q}$ 是大小为(m, m)的正交矩阵, $\mathbf{R}$ 是大小为 (m, n)的三角矩阵 (参见第 364 页4.1.2,11.).

3. 正则化问题

在秩亏格情形,即如果 $\mathrm{rank}\left(\mathbf{A}\right)<n$ ,那么正规方程组不再有唯一解,并且正交化方法给出无用的结果. 于是代替 (4.189) 考虑所谓正则化问题:

$$\begin{array}{}\text{(4.191)}& {\underset{―}{\mathbf{r}}}^{\mathrm{T}}\underset{―}{\mathbf{r}}+\alpha {\underset{―}{\mathbf{x}}}^{\mathrm{T}}\underset{―}{\mathbf{x}}=min!,\end{array}$$

这里 $\alpha >0$ 是正则化参数. 对于 (4.191) 的正规方程是

$$\begin{array}{}\text{(4.192)}& \left({\mathbf{A}}^{\mathrm{T}}\mathbf{A}+\alpha \mathbf{I}\right)\underset{―}{\mathbf{x}}={\mathbf{A}}^{\mathrm{T}}\underset{―}{\mathbf{b}}.\end{array}$$

当 $\alpha >0$ 时这个线性方程组的系数矩阵正定并且正则,但选取合适的正则化参数是一个困难的问题 (见 [4.7]).