19.2.1 线性方程组

考虑线性方程组

$$a_{11}{x}_1+a_{12}{x}_2+\cdots +a_{1n}{x}_n=b_1,$$$$\begin{array}{}\text{(19.25)}& a_{21}{x}_1+a_{22}{x}_2+\cdots +a_{2n}{x}_n=b_2,\end{array}$$

......

$$a_{n1}{x}_1+a_{n2}{x}_2+\cdots +a_{nn}{x}_n=b_n.$$

方程组 (19.25) 可以写成矩阵形式

$$\begin{array}{}\text{(19.26a)}& \mathbf{A}\underset{―}{\mathbf{x}}=\underset{―}{\mathbf{b}}\end{array}$$

其中

$$\begin{array}{}\text{(19.26b)}& \mathbf{A}=\left(\begin{array}{cccc}{a}_{11}& a_{12}& \cdots & a_{1n}\\ a_{21}& a_{22}& \cdots & a_{2n}\\ ⋮& ⋮& & ⋮\\ a_{n1}& a_{n2}& \cdots & a_{nn}\end{array}\right),\underset{―}{\mathbf{b}}=\left(\begin{array}{c}{b}_1,\\ b_2,\\ ⋮\\ b_n\end{array}\right),\underset{―}{\mathbf{x}}=\left(\begin{array}{c}{x}_1,\\ x_2,\\ ⋮\\ x_n\end{array}\right).\end{array}$$

如果矩阵 $\mathbf{A}$ 是 $n$ 阶正定的,则方程组 (19.25) 有唯一解 (参见第 412 页 4.5.2.1,2.). 实际求解方程 (19.25) 时, 主要有如下两类方法:

(1) 直接法 直接法基于元素变换, 据此可以直接得到方程组的解. 主元素选取的技巧 (参见第 412 页 4.5.1.2) 及其方法介绍见第 1242 页 19.2.1.1 至第 1246 页 19.2.1.3.

(2) 迭代法 始于解的初始近似值, 构成近似值的序列收敛到 (19.25) 的解 (参见第 1248 页 19.2.1.4).

19.2.1.1 矩阵的三角分解

1. 高斯消元法的原理

根据元素变换

(1) 交换行;

(2)某一行乘以非零数；

(3) 将某一行乘以非零数加到另一行.

线性方程组 $\mathbf{A}\underset{―}{\mathbf{x}}=\underset{―}{\mathbf{b}}$ 的变换称之为行变换

$$\begin{array}{}\text{(19.27)}& \mathbf{R}\underset{―}{\mathbf{x}}=\underset{―}{\mathbf{c}}\text{,其中 }\mathbf{R}=\left(\begin{array}{ccccc}{r}_{11}& r_{12}& r_{13}& \cdots & r_{1n}\\ & r_{22}& r_{23}& \cdots & r_{2n}\\ & & r_{33}& \cdots & r_{3n}\\ & 0& & \ddots & ⋮\\ & & & & r_{nn}\end{array}\right)\text{. }\end{array}$$

因为上述变换都是等价变换,方程组 $\mathbf{R}\underset{―}{\mathbf{x}}=\underset{―}{\mathbf{c}}$ 与方程组 $\mathbf{A}\underset{―}{\mathbf{x}}=\underset{―}{\mathbf{b}}$ 有相同的解, 从 (19.27) 可得

$$\begin{array}{}\text{(19.28)}& x_n=\frac{c_n}{r_{nn}},x_i=\frac{1}{r_{ii}}\left(c_i-\sum _{k=i+1}^n{r}_{ik}{x}_k\right)\left(i=n-1,n-2,\cdots ,1\right).\end{array}$$

规则 (19.28) 称为向后代换法, 因为 (19.27) 的方程按倒序求解.

变换从 $\mathbf{A}$ 到 $\mathbf{R}$ 经过 $n-1$ 步,所谓消元. 其第一步如下. 这一步将矩阵 $\mathbf{A}$ 变换成 ${\mathbf{A}}_1$ :

$$\begin{array}{}\text{(19.29)}& \mathbf{A}=\left(\begin{array}{cccc}{a}_{11}& a_{12}& \cdots & a_{1n}\\ a_{21}& a_{22}& \cdots & a_{2n}\\ a_{31}& a_{32}& \cdots & a_{3n}\\ ⋮& ⋮& & ⋮\\ a_{n1}& a_{n2}& \cdots & a_{nn}\end{array}\right),{\mathbf{A}}_1=\left(\begin{array}{cc}{a}_{11}^{\left(1\right)}& a_{12}^{\left(1\right)}\cdots a_{1n}^{\left(1\right)}\\ 0& a_{22}^{\left(1\right)}\cdots a_{2n}^{\left(1\right)}\\ 0& a_{32}^{\left(1\right)}\cdots a_{3n}^{\left(1\right)}\\ ⋮& ⋮\\ 0& a_{n2}^{\left(1\right)}\cdots a_{nn}^{\left(1\right)}\end{array}\right).\end{array}$$

于是:

(1) 选取 $a_{r1}\ne 0$ (根据 (19.33)). 如果没有, $\mathbf{A}$ 奇异,停止. 否则 $a_{r1}$ 称为主元.

(2) 交换矩阵 $\mathbf{A}$ 的第一行与第 $r$ 行,得到矩阵 $\bar{\mathbf{A}}$ .

(3) 第 $l_{i1}\left(i=2,3,\cdots ,n\right)$ 乘以第一行减去矩阵 $\bar{\mathbf{A}}$ 第 $r$ 行.

于是得到矩阵 ${\mathbf{A}}_1$ ,与之类似得到右端 $b_1$ 的新元素

$$a_{ik}^{\left(1\right)}={\overline{a}}_{ik}-l_{i1}{\overline{a}}_{1k}\text{,其中 }{l}_{i1}=\frac{{\overline{a}}_{i1}}{{\overline{a}}_{11}}\text{,}$$$$\begin{array}{}\text{(19.30)}& b_i^{\left(1\right)}={\overline{b}}_i-l_{i1}{\overline{b}}_1\left(i,k=2,3,\cdots ,n\right).\end{array}$$

子矩阵 ${\mathbf{A}}_1$ (见 (19.29)) 为一个(n - 1, n - 1)矩阵,它可以类似于矩阵 $\mathbf{A}$ 进行处理. 该方法称为高斯消元法或者称为高斯算法 (参见第 417 页 4.5.2.4).

2. 三角分解

高斯消元法的结果可以归结为: 对于每个正规矩阵 $\mathbf{A}$ ,存在一个称为三角分解或者 $LU$ 因子分解,形如

$$\begin{array}{}\text{(19.31)}& \mathbf{PA}=\mathbf{LR}\end{array}$$

其中

$$\mathbf{R}=\left(\begin{array}{ccccc}{r}_{11}& r_{12}& r_{13}& \cdots & r_{1n}\\ & r_{22}& r_{23}& \cdots & r_{2n}\\ & & r_{33}& \cdots & r_{3n}\\ & 0& & \ddots & ⋮\\ & & & & r_{nn}\end{array}\right),\mathbf{L}=\left(\begin{array}{ccccc}1& & & & \\ l_{21}& 1& & 0& \\ l_{31}& l_{32}& 1& & \\ ⋮& ⋮& & \ddots & \\ l_{n1}& l_{n2}& \cdots & l_{n,n-1}& 1\end{array}\right).$$

(19.32)

这里 $\mathbf{R}$ 称为上三角矩阵, $\mathbf{L}$ 称为下三角矩阵, $\mathbf{P}$ 称为置换矩阵. 如果一个置换矩阵的行列交叉处为 1,其他元素都为零,该矩阵称为二次矩阵. 乘积 $\mathbf{PA}$ 导致矩阵 $\mathbf{A}$ 的行变换. 在消元的过程中需要选择主元.

• 用高斯消元法求解方程组

$$\left(\begin{array}{lll}3& 1& 6\\ 2& 1& 3\\ 1& 1& 1\end{array}\right)\left(\begin{array}{l}{x}_1\\ x_2\\ x_3\end{array}\right)=\left(\begin{array}{l}2\\ 7\\ 4\end{array}\right)$$

按图解形式, 系数矩阵与右端列向量可以靠近写在一起 (称为增广矩阵), 计算如下:

$$\left(\mathbf{A},\underset{―}{\mathbf{b}}\right)=\left(\begin{array}{ccc}3& 1& 6\\ 2& 1& 3\\ 1& 1& 1\end{array}\right)\left|\begin{array}{l}2\\ 7\\ 4\end{array}\right|\Rightarrow \left(\begin{array}{ccc}3& 1& 6\\ 2/3& 1& 2\\ 1/3& 2& 1\end{array}\right)=\left(\begin{array}{cccc}3& 1& 6& 2\\ 1/3& -1& 1& 17/3\\ 10/3& -1& 10/3& \end{array}\right)$$$$\Rightarrow \left(\begin{array}{cccc}3& 1& 6& 2\\ 1/3& 2/3& -1& 10/3\\ 2/3& 1/2& -1/2& 4\end{array}\right)$$

即

$$\mathbf{P}=\left(\begin{array}{lll}1& 0& 0\\ 0& 0& 1\\ 0& 1& 0\end{array}\right)\Rightarrow \mathbf{PA}=\left(\begin{array}{lll}3& 1& 6\\ 1& 1& 1\\ 2& 1& 3\end{array}\right)$$$$\mathbf{L}=\left(\begin{array}{ccc}1& 0& 0\\ 1/3& 1& 0\\ 2/3& 1/2& 1\end{array}\right),\mathbf{R}=\left(\begin{array}{ccc}3& 1& 6\\ 0& 2/3& -1\\ 0& 0& -1/2\end{array}\right).$$

在系数矩阵 $\mathbf{A},{\mathbf{A}}_1,{\mathbf{A}}_2$ 中,主元在矩阵中用方框表示,其解为 $x_3=-8,x_2=$ $-7,x_1=19$ .

3. 三角分解的应用

借助于三角分解,求解线性方程组 $\mathbf{A}\underset{―}{\mathbf{x}}=\underset{―}{\mathbf{b}}$ 可以表述为以下三步:

(1) $\mathbf{PA}=\mathbf{LR}$ : 确定三角分解并作代换 $\mathbf{R}\underset{―}{\mathbf{x}}=\underset{―}{\mathbf{c}}$ .

(2) $\mathbf{L}\underset{―}{\mathbf{c}}=\mathbf{P}\underset{―}{\mathbf{b}}$ : 通过向前代换确定辅助变量 $\underset{―}{\mathbf{c}}$ .

(3) $\mathbf{R}\underset{―}{\mathbf{x}}=\underset{―}{\mathbf{c}}$ : 通过向后代换确定解向量 $\underset{―}{\mathbf{x}}$ .

如果如同上例中用增广矩阵 $\left(\mathbf{A},\underset{―}{\mathbf{b}}\right)$ 处理线性方程组,用高斯消元法求解,那么下三角矩阵 $\mathbf{L}$ 并不需要显式得到. 该方法对于左边系数矩阵相同,而右端项不同的多个线性方程组尤为适用.

4. 主元的选取

理论上,矩阵 ${\mathbf{A}}_{k-1}$ 的任意一个第一列的非零元 $a_{i1}^{(k-1)}$ 都可以选为第 $k$ 次消元的主元. 为了改进解的准确性 (减少运行过程中的积累误差), 建议用如下策略.

(1) 对角策略 若有可能, 对角元素被成功选为主元, 即无行变换. 若主对角线元素的绝对值比同一行的其他元素的绝对值大得多, 这种选取可行.

(2) 列主元 在实施第 $k$ 步消元时,选第 $r$ 行使得

$$\begin{array}{}\text{(19.33)}& \left|a_{rk}^{(k-1)}\right|=\underset{i\ge k}{max}\left|a_{ik}^{(k-1)}\right|.\end{array}$$

若 $r\ne k$ ,则交换第 $r$ 行与第 $k$ 行. 可证明该策略能使累计舍入误差小一些.

19.2.1.2 对称系数矩阵的楚列斯基方法

在许多情况下,(19.26a) 中的系数矩阵 $\mathbf{A}$ 不仅仅是对称的,而且是正定的,此时相应的二次型 $Q\left(\underset{―}{x}\right)$ 为

$$\begin{array}{}\text{(19.34)}& Q\left(\underset{―}{\mathbf{x}}\right)={\underset{―}{\mathbf{x}}}^{\mathrm{T}}\mathbf{A}\underset{―}{\mathbf{x}}=\sum _{i=1}^n\sum _{k=1}^n{a}_{ik}{x}_i{x}_k>0,\end{array}$$

其中 $\underset{―}{\mathbf{x}}\in {\mathbb{R}}^n,\underset{―}{\mathbf{x}}\ne \mathbf{0}$ . 由于每一个正定矩阵存在唯一个三角分解

$$\begin{array}{}\text{(19.35)}& \mathbf{A}=\mathbf{L}{\mathbf{L}}^{\mathrm{T}}\end{array}$$

其中

$$\begin{array}{}\text{(19.36a)}& \mathbf{L}=\left(\begin{array}{ccccc}{l}_{11}& & & & \\ l_{21}& l_{22}& & 0& \\ l_{31}& l_{32}& l_{33}& & \\ ⋮& ⋮& ⋮& \ddots & \\ l_{n1}& l_{n2}& l_{n3}& \cdots & l_{nn}\end{array}\right),\end{array}$$$$\begin{array}{}\text{(19.36b)}& l_{kk}=\sqrt{a_{kk}^{(k-1)}},l_{ik}=\frac{a_{ik}^{(k-1)}}{l_{kk}}\left(i=k,k+1,\cdots ,n\right);\end{array}$$$$\begin{array}{}\text{(19.36c)}& a_{ij}^{\left(k\right)}=a_{ij}^{(k-1)}-l_{ik}{l}_{jk}\left(i,j=k+1,k+2,\cdots ,n\right).\end{array}$$

相应的线性方程组 $\mathbf{A}\underset{―}{\mathbf{x}}=\underset{―}{\mathbf{b}}$ 的解可用楚列斯基 (Cholesky) 方法通过下列步骤确定:

(1) $\mathbf{A}=\mathbf{L}{\mathbf{L}}^{\mathrm{T}}$ : 确定所谓的楚列斯基分解并作代换 ${\mathbf{L}}^{\mathrm{T}}\underset{―}{\mathbf{x}}=\underset{―}{\mathbf{c}}$ .

(2) $\mathbf{L}\underset{―}{\mathbf{c}}=\underset{―}{\mathbf{b}}$ : 通过向前代换确定辅助变量 $\underset{―}{\mathbf{c}}$ .

(3) ${\mathbf{L}}^{\mathrm{T}}\mathbf{x}=\mathbf{c}$ : 通过向后代换确定解向量 $\mathbf{x}$ .

当 $n$ 较大时,楚列斯基方法的计算量大约是 $\mathbf{LU}$ 分解方法 (参见第 1243 页 (19.31)) 的一半.

19.2.1.3 正交化方法

1. 线性拟合问题

设超定方程组

$$\begin{array}{}\text{(19.37)}& \sum _{k=1}^n{a}_{ik}{x}_k=b_i\left(i=1,2,\cdots ,m;m>n\right)\end{array}$$

的矩阵形式为

$$\begin{array}{}\text{(19.38)}& \mathbf{A}\mathbf{x}=\mathbf{b}.\end{array}$$

若系数矩阵 $\mathbf{A}=\left(a_{ik}\right)$ 为 $\left(m\times n\right)$ ,满秩为 $n$ ,即列是线性无关的. 由于超定方程组通常无解, 考虑所谓的误差方程组代替 (19.37):

$$\begin{array}{}\text{(19.39)}& r_i=\sum _{k=1}^n{a}_{ik}{x}_k-b_i\left(i=1,2,\cdots ,m;m>n\right),\end{array}$$

这里 $r_i$ 为残量,使其平方和最小:

$$\begin{array}{}\text{(19.40)}& \sum _{i=1}^m{r}_i^2=\sum _{i=1}^m{[\sum _{k=1}^n{a}_{ik}{x}_k-b_i]}^2=F\left(x_1,x_2,\cdots ,x_n\right)=min!.\end{array}$$

(19.40) 称为线性拟合问题或线性最小二乘问题 (参见第 611 页 6.2.5.5). 使得残量平方和 $F\left(x_1,x_2,\cdots ,x_n\right)$ 最小的必要条件为

$$\begin{array}{}\text{(19.41)}& \frac{\partial F}{\partial x_k}=0\left(k=1,2,\cdots ,n\right).\end{array}$$

于是得到线性方程组

$$\begin{array}{}\text{(19.42)}& {\mathbf{A}}^{\mathrm{T}}\mathbf{A}\underset{―}{\mathbf{x}}={\mathbf{A}}^{\mathrm{T}}\underset{―}{\mathbf{b}}.\end{array}$$

因为方程组 (19.42) 是由 (19.38) 应用高斯最小二乘法得到的 (参见第 611 页 6.2.5.5),所以从 (19.38) 到 (19.42) 的变换称为高斯变换. 因为 $\mathbf{A}$ 是满秩的, ${\mathbf{A}}^{\mathrm{T}}\mathbf{A}$ 为正定的 $\left(n\times n\right)$ 矩阵,所以正规方程 (19.42) 可以由楚列斯基方法数值求解 (参见第 1245 页 19.2.1.2).

若矩阵 ${\mathbf{A}}^{\mathrm{T}}\mathbf{A}$ 的条件数 (见 [19.31]) 过大,数值求解正规方程 (19.42) 有困难, 则其解的相对误差也大. 因此最好用正交化方法数值求解线性拟合问题.

2. 正交化方法

下面是解线性最小二乘问题 (19.40) 的正交化方法基础.

(1) 在正交变换的过程中不改变向量的长度,即向量 $\underset{―}{x}$ 和 $\underset{―}{\tilde{x}}=Q_0\underset{―}{x}$ 有相同的长度, 其中

$$\begin{array}{}\text{(19.43)}& {\mathbf{Q}}_0^{\mathrm{T}}{\mathbf{Q}}_0=\mathbf{E}.\end{array}$$

(2) 对于有最大秩 $n\left(n<m\right)$ 的任意(m, n)矩阵 $\mathbf{A}$ ,存在(m, m)正交矩阵 $\mathbf{Q}$ , 使得

$$\begin{array}{}\text{(19.44)}& \mathbf{A}=\mathbf{Q}\hat{\mathbf{R}}\end{array}$$$$\begin{array}{}\text{(19.45)}& {\mathbf{Q}}^{\mathrm{T}}\mathbf{Q}=\mathbf{E},\hat{\mathbf{R}}=\left(\begin{array}{l}\mathbf{R}\\ \mathbf{O}\end{array}\right)=\left(\begin{array}{cccc}{r}_{11}& r_{12}& \cdots & r_{1n}\\ & r_{22}& \cdots & r_{2n}\\ & & \ddots & ⋮\\ & & & r_{nn}\\ & \cdots & \cdots & \cdots \cdots \cdots \\ & & & \mathbf{O}\end{array}\right).\end{array}$$

这里 $\mathbf{R}$ 为(n, n)上三角矩阵,矩阵 $\mathbf{O}$ 为(m - n, n)零矩阵.

矩阵 $\mathbf{A}$ 的乘积形式 (19.44) 称为矩阵 $\mathbf{A}$ 的 $\mathbf{QR}$ 分解. 因此误差方程 (19.39) 可以转化为等价的方程组

$$r_{11}{x}_1+r_{12}{x}_2+\cdots +r_{1n}{x}_n-{\hat{b}}_1={\hat{r}}_1,$$$$r_{22}{x}_2+\cdots +r_{2n}{x}_n-{\hat{b}}_2={\hat{r}}_2,$$$$\because ⋮⋮=⋮$$$$\begin{array}{}\text{(19.46)}& r_{nn}{x}_n-{\hat{b}}_n={\hat{r}}_n,\end{array}$$$$-{\hat{b}}_{n+1}={\hat{r}}_{n+1},$$$$⋮$$$$-{\hat{b}}_m={\hat{r}}_m.$$

而残量的平方和不变. 由 (19.46) 知,当 ${\hat{r}}_1={\hat{r}}_2=\cdots ={\hat{r}}_n=0$ 时平方和最小,而且最小值等于 ${\hat{r}}_{n+1}$ 到 ${\hat{r}}_m$ 的平方和. 要求的解 $\mathbf{x}$ 则可由向后替换得到

$$\begin{array}{}\text{(19.47)}& \mathbf{R}\underset{―}{\mathbf{x}}={\underset{―}{\hat{\mathbf{b}}}}_0\end{array}$$

其中向量 ${\widehat{\underset{―}{b}}}_0$ 由 (19.46) 的元素 ${\hat{b}}_1,{\hat{b}}_2,\cdots ,{\hat{b}}_n$ 组成.

由 (19.39) 转化为 (19.46) 有两种常用的方法:

(1) 吉文斯 (Givens) 变换.

(2)豪斯霍尔德变换.

矩阵 $\mathbf{A}$ 的 $\mathbf{QR}$ 分解的第一步由旋转得到,其余则由反射得到. 数值程序可见[19.29].

线性最小二乘逼近的实际问题多数用豪斯霍尔德变换求解, 通常会用到系数矩阵 $\mathbf{A}$ 的特殊带状结构.

19.2.1.4 迭代方法

1. 雅可比方法

设线性方程组 (19.25) 的系数矩阵的每个主元 $a_{ii}\left(i=1,2,\cdots ,n\right)$ 都是非零元素. 于是第 $i$ 行的未知量 $x_i$ 可以由下面的迭代法则得到,其中 $\mu$ 为迭代指标

$$x_i^{(\mu +1)}=\frac{b_i}{a_{ii}}-\sum _{\begin{array}{c}k=1\\ \left(k\ne i\right)\end{array}}^n\frac{a_{ik}}{a_{ii}}\left(i=1,2,\cdots ,n\right)$$$$\begin{array}{}\text{(19.48)}& \left(\mu =0,1,2,\cdots ;x_1^{\left(0\right)},x_2^{\left(0\right)},\cdots ,x_n^{\left(0\right)}\text{为给定初值}\right)\text{.}\end{array}$$

公式 (19.48) 称为雅可比方法. 新向量 $x^{(\mu +1)}$ 的各个分量由 $x^{\left(\mu \right)}$ 的分量计算得到. 若至少满足下面的一个条件

$$\begin{array}{}\text{(19.49)}& \underset{k}{max}\sum _{\begin{array}{c}i=1\\ \left(i\ne k\right)\end{array}}^n\left|\frac{a_{ik}}{a_{ii}}\right|<1\end{array}$$

或

$$\begin{array}{}\text{(19.50)}& \underset{i}{max}\sum _{\begin{array}{c}k=1\\ \left(k\ne i\right)\end{array}}^n\left|\frac{a_{ik}}{a_{ii}}\right|<1\end{array}$$

则雅可比迭代对于任意初始向量 ${\mathbf{x}}^{\left(0\right)}$ 收敛.

2. 高斯-塞德尔迭代

若第一分量 $x_1^{(\mu +1)}$ 由雅可比方法计算得到,则该值可以用于计算 $x_2^{(\mu +1)}$ . 可用类似的方法计算后面的分量, 于是得如下迭代公式

$$x_i^{(\mu +1)}=\frac{b_i}{a_{ii}}-\sum _{\begin{array}{c}k=1\\ \left(k\ne i\right)\end{array}}^n\frac{a_{ik}}{a_{ii}}{x}_k^{(\mu +1)}-\sum _{k=i+1}^n\frac{a_{ik}}{a_{ii}}{x}_k^{\left(\mu \right)}\left(i=1,2,\cdots ,n\right)$$$$\begin{array}{}\text{(19.51)}& \left(\mu =0,1,2,\cdots ;x_1^{\left(0\right)},x_2^{\left(0\right)},\cdots ,x_n^{\left(0\right)}\text{为给定初值}\right)\text{.}\end{array}$$

公式 (19.51) 称为高斯-塞德尔 (Gauss-Seidel) 方法. 高斯-塞德尔方法通常比雅可比方法收敛得快, 但其收敛判据更复杂.

$$10x_1-3x_2-4x_3+2x_4=14,$$$$-3x_1+26x_2+5x_3-x_4=22,$$$$-4x_1+5x_2+16x_3+5x_4=17,$$$$2x_1+3x_2-4x_3-12x_4=-20.$$

根据 (19.51) 相应的迭代公式为

$$x_1^{(\mu +1)}=\frac{1}{10}\left(14+3x_2^{\left(\mu \right)}+4x_3^{\left(\mu \right)}-2x_4^{\left(\mu \right)}\right),$$$$x_2^{(\mu +1)}=\frac{1}{26}\left(22+3x_1^{(\mu +1)}-5x_3^{\left(\mu \right)}+x_4^{\left(\mu \right)}\right),$$$$x_3^{(\mu +1)}=\frac{1}{16}\left(17+4x_1^{(\mu +1)}-5x_2^{(\mu +1)}-5x_4^{\left(\mu \right)}\right),$$$$x_4^{(\mu +1)}=\frac{1}{12}\left(-20+2x_1^{(\mu +1)}+3x_2^{(\mu +1)}-4x_3^{(\mu +1)}\right).$$

$x^{\left(0\right)}$	$x^{\left(1\right)}$	$x^{\left(4\right)}$	$x^{\left(5\right)}$	$x$
0	1.4	1.5053	1.5012	1.5
0	1.0077	0.9946	0.9989	1
0	1.0976	0.5059	0.5014	0.5
0	1.7861	1.9976	1.9995	2

3. 松弛法

高斯-塞德尔方法 (19.51) 的迭代公式可以写成修正形式

$$x_i^{(\mu +1)}=x_i^{\left(\mu \right)}+\left(\frac{b_i}{a_{ii}}-\sum _{k=1}^{i-1}\frac{a_{ik}}{a_{ii}}{x}_k^{(\mu +1)}-\sum _{k=i}^n\frac{a_{ik}}{a_{ii}}{x}_k^{\left(\mu \right)}\right),$$

即

$$\begin{array}{}\text{(19.52)}& x_i^{(\mu +1)}=x_i^{\left(\mu \right)}+d_i^{\left(\mu \right)}\left(i=1,2,\cdots ,n;\mu =0,1,2,\cdots \right).\end{array}$$

选取适当的松弛参数 $\omega$ ,将 (19.52) 重新写成如下形式:

$$\begin{array}{}\text{(19.53)}& x_i^{(\mu +1)}=x_i^{\left(\mu \right)}+\omega d_i^{\left(\mu \right)}\left(i=1,2,\cdots ,n;\mu =0,1,2,\cdots \right)\end{array}$$

以提高收敛速度. 可以证明, 仅当

$$\begin{array}{}\text{(19.54)}& 0<\omega <2\end{array}$$

时该方法收敛. 当 $\omega =1$ 时,退回高斯-塞德尔迭代. 当 $\omega >1$ 时,称为超松弛,此时相应的迭代法称为 SOR (逐次超松弛) 方法. 对某些特殊类型的矩阵可确定最优松弛因子.

迭代法用来求解系数矩阵的主对角线元素 $a_{ii}$ 按绝对值比该列或行的其他元素大得多的线性方程组, 或者通过某种方式重排方程组的行可得到这种形式的方程组.