参考教材：孙志忠, 吴宏伟, 等. 计算方法与实习[M]. 第五版. 南京: 东南大学出版社, 2011:50-84.

线性方程组可以写成矩阵形式 $\mathbf A\vec x=\vec b$

有时也写成增广矩阵形式 $\overline{\mathbf A}=[\mathbf A\vec b]=\begin{bmatrix}
a_{11} & a_{12} & \cdots & a_{1n} & b_1\\
a_{21} & a_{22} & \cdots & a_{2n} & b_2\\
\vdots & \vdots & & \vdots & \vdots\\
a_{n1} & a_{n2} & \cdots & a_{nn} & b_n\\
\end{bmatrix}$

如果矩阵 $\mathbf A$ 是非奇异（$\det\mathbf A\ne0$）的，则方程组有唯一解。并且可用克莱姆(Cramer)法则表示解： $x_i=\frac{D_i}D$ ，其中 $x_i$ 为 $\vec x$ 的第 $i$ 个分量， $D_i$ 是用 $\vec b$ 代替 $\mathbf A$ 的第 $i$ 列后所得矩阵的行列式。

本章始终假设 $\mathbf A$ 为奇异矩阵

消去法

三角方程组的解法

给 $\mathbf U\vec x=\vec y$

其中 $\mathbf U=\begin{bmatrix}
u_{11} & u_{12} & \cdots & u_{1,n-1} & u_{1n}\\
& u_{22} & \cdots & u_{2,n-1} & u_{2n}\\
& & \ddots & \vdots & \vdots\\
& & & u_{n-1,n-1} & u_{n-1,n}\\
& & & & u_{nn}
\end{bmatrix}$

若 $\det\mathbf U\ne0$ ，即 $u_{ii}\ne0$ ，则方程组有唯一解

显然， $x_i=\frac{y_i-\sum_{j=i+1}^nu_{ij}x_j}{u_{ii}} (i:n\rightarrow1)$

这样逆向求 $x_i$ 的过程称为回代过程。

所需乘除法运算次数为 $M_1=\sum_{i=1}^n(n-i+1)=\frac{n(n+1)}2$

所需加减法运算次数为 $S_1=\sum_{i=1}^n(n-1)=\frac{n(n-1)}2$

高斯消去法

算法略

消元过程：

乘除法次数为 $M_2=\frac{n^3}3+\frac{n^2}2-\frac{5n}6$

加减法次数为 $S_2=\frac{n^3}3-\frac n3$

总运算量：

$M=M_1+M_2=\frac{n^3}3+n^2-\frac n3$

$S=S_1+S_2=\frac{n^3}3+\frac{n^2}2-\frac{5n}6$

追赶法

追赶法用来解决一种特殊的线性方程组：

$$\begin{bmatrix} b_1 & c_1\\ a_2 & b_2 & c_2\\ & a_3 & b_3 & c_3\\ && \ddots & \ddots & \ddots\\ &&& a_{n-1} & b_{n-1} & c_{n-1}\\ &&&& a_n & b_n \end{bmatrix} \begin{bmatrix} x_1\\x_2\\x_3\\\vdots\\x_{n-1}\\x_n \end{bmatrix} = \begin{bmatrix} d_1\\d_2\\d_3\\\vdots\\d_{n-1}\\d_n \end{bmatrix}$$

且满足

1. $|b_1|\gt|c_1|\gt0$
2. $|b_i|\ge|a_i|+|c_i|, a_ic_i\ne0$
3. $|b_n|\ge|a_n|\gt0$

则消元过程为

$$\left\{ \begin{aligned} \beta_1&=b_1 &,&y_1=d_1\\ \beta_i&=b_i-\frac{a_i}{\beta_{i-1}}c_{i-1}&,&y_i=d_i-\frac{a_i}{\beta_{i-1}}c_{i-1} \end{aligned} \right.$$

回代过程为

$$\left\{ \begin{aligned} x_n&=\frac{y_n}{\beta_n}\\ x_i&=\frac{y_i-c_ix_{i+1}}{\beta_i} \end{aligned} \right.$$

共 $5n-4$ 次乘除法运算， $3n-3$ 次加减法运算

列主元高斯消去法

在进行第 $k$ 步消元之前，选出第 $k$ 列中位于对角线及以下元素绝对值中的最大者，交换两行。可以减小误差

矩阵的直接分解及其在解方程组中的应用

矩阵分解的紧凑格式

将方阵 $\mathbf A$ 分解成一个下三角矩阵 $\mathbf L$ 和一个上三角矩阵 $\mathbf U$ 的乘积称为矩阵的三角（因子）分解。

若 $L$ 为单位下三角矩阵（对角元全为 $1$ ），则称为 Doolittle 分解。

若 $U$ 为单位上三角矩阵，则称为 Crout 分解。

若在消元法前进行 $\mathbf{LU}$ 分解，则

$$\begin{aligned} &\mathbf A\vec x=\vec b\\ \Leftrightarrow&(\mathbf{LU})\vec x=\vec b\\ \Leftrightarrow&\mathbf L\vec y=\vec b, \mathbf U\vec x=\vec y \end{aligned}$$ $$\mathbf A=\mathbf{LU}= \begin{bmatrix} 1\\ l_{21} & 1\\ l_{31} & l_{32} & 1\\ \vdots & \vdots & \vdots & \ddots\\ l_{n1} & l_{n2} & l_{n3} & \cdots & 1\\ \end{bmatrix} \begin{bmatrix} u_{11} & u_{12} & u_{13} & \cdots & u_{1n}\\ & u_{22} & u_{23} & \cdots & u_{2n}\\ & & u_{33} & \cdots & u_{3n}\\ & & & \ddots & \vdots\\ & & & & u_{nn}\\ \end{bmatrix}$$ $$\begin{aligned} u_{1j}&=a_{1j}\\ l_{i1}&=\frac{a_{i1}}{u_{11}}\\ u_{kj}&=a_{kj}-\sum_{q=1}^{k-1}l_{kq}u_{qj}\\ l_{ik}&=\frac{a_{ik}-\sum_{q=1}^{k-1}l_{iq}u_{qk}}{u_{kk}}\\ y_1&=b_1\\ y_k&=b_k-\sum_{q=1}^{k-1}l_{kq}y_q \end{aligned}$$

为了便于记忆，可以将 $\mathrm L,\mathrm U$ 元素写在一起，形成紧凑格式：

$$\mathbf A\rightarrow \begin{bmatrix} u_{11} & u_{12} & u_{13} & \cdots & u_{1n}\\ l_{21} & u_{22} & u_{23} & \cdots & u_{2n}\\ l_{31} & l_{32} & u_{33} & \cdots & u_{3n}\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ l_{n1} & l_{n2} & l_{n3} & \cdots & u_{nn}\\ \end{bmatrix}$$

本来矩阵里还有一堆线的，但是 mathjax 不支持这么高级的语法（

平方根法

设 $\mathbf A\in R^{n\times n}$ ，若 $\mathbf A=\mathbf A^T$ ，对任意的 $0\ne \vec x\in R^n$，都有 $\vec x^T\mathbf A\vec x\gt0$ ，则称 $\mathbf A$为对称正定矩阵

设 $\mathbf A$ 对称正定，则有非奇异下三角阵 $\mathbf L$ ，使 $\mathbf A=\mathbf{LL}^T$

此时有：

$$\begin{aligned} l_{11}&=\sqrt{a_{11}}\\ l_{j1}&=\frac{a_{j1}}{l_{11}}\\ l_{kk}&=\sqrt{a_{kk}-\sum_{q=1}^{k-1}l_{kq}^2}\\ l_{jk}&=\frac1{l_{kk}}(a_{jk}-\sum_{q=1}^{k-1}l_{kq}l_{jq}) \end{aligned}$$

优点：

1. 计算量小
2. 稳定，不比先主元

缺点：开方运算

改进平方根法

设 $\mathbf A$ 对称正定，则有非奇异下三角阵 $\mathbf L$ ，使 $\mathbf A=\mathbf{LL}^T=\mathbf{QDL}^T=\mathbf{QU}$ ，其中 $D$ 是三角矩阵

由 $\mathbf{LU}$ 分解公式

$$\begin{aligned} u_{1i}&=a_{1i}\\ l_{i1}&=\frac{a_{i1}}{a_{11}}=\frac{a_{1i}}{a_{11}}=\frac{u_{1i}}{u_{11}}\\ u_{ij}&=a_{ij}-\sum_{q=1}^{i-1}l_{iq}{u_{qj}}=a_{ij}-\sum_{q=1}^{i-1}\frac{u_{qi}u_{qj}}{u_{qq}}\\ l_{ij}&=\frac{u_{ji}}{u_{jj}} \end{aligned}$$

即

$$\begin{bmatrix} u_{11} & u_{12} & \cdots & u_{1n}\\ \frac{u_{12}}{u_{11}} & u_{22} &\cdots & u_{2n}\\ \vdots & \vdots & \ddots & \vdots\\ \frac{u_{1n}}{u_{11}} & \frac{u_{2n}}{u_{22}} & \cdots & u_{nn}\\ \end{bmatrix}$$

优点：

1. 无需计算平方根
2. 计算量与平方根法相比同阶量

列主元三角分解法

设方程组 $\mathbf A\vec x=\vec b$ ，对其增广矩阵作 $LU$ 分解，为了避免用小 $u_{kk}$ 作除数，引入量 $s_i=a_{ik}-\sum_{q=1}^{k-1}l_{iq}u_{qk}, (i=k,k+1,\cdots,n)$

于是 $u_{kk}=s_k$ ， 比较 $|s_i|$ 的大小，取 $\max_{k\le i\le n}|s_i|$ （设为 $s_t$ ）为 $u_{kk}$ 。并交换矩阵的第 $t$ 行和第 $k$ 行，且元素的下标也相应改变。交换时连带 $l$ 也一起交换，交换后 $u_{kk}=s_k$ ， $l_{ik}=\frac{s_i}{s_k}$ 。此时 $|l_{ik}|\le1$ ，可以控制舍入误差的增大。

向量范数和矩阵范数

向量范数

设 $f(\vec x)=|\vec x|$ 是定义在 $R^n$ 上的实函数，如果它满足以下 3 个条件：

1. 非负性：$\forall \vec x\in R^n, |\vec x|\ge0, |\vec x|=0\Leftrightarrow \vec x=0$
2. 奇次性 $\forall c\in R, \forall \vec x\in R^n, |c\vec x|=|c|\times|\vec x|$
3. 三角不等式性 $\forall \vec x,\vec y\in R^n,|\vec x+\vec y|\le|\vec x|+|\vec y|$

则称 $|\cdot|$ 为 $R^n$ 上的向量范数

最常用的是如下三种范数：

1. 向量的 1−范数： $|\vec x|_1=\sum_{i=1}^n|x_i|$
2. 向量的 2−范数： $|\vec x|_2=\sqrt{\sum_{i=1}^nx_i^2}$
3. 向量的 $\infty$−范数： $|\vec x|_\infty=\max_{1\le i\le n}|x_i|$

$|\vec x-\vec y|$ 为 $\vec x$ 和 $\vec y$ 之间的距离

矩阵范数

设 $\mathbf A\in R^{n\times n}$ ， $|\cdot|$ 是 $R^n$ 上的任一向量范数，称 $\max_{|\vec x|=1}|\mathbf A\vec x|$ 为 $\mathbf A$ 的矩阵范数，记做 $|\mathbf A|$

即， $|\mathbf A|=\max_{|\vec x|=1}|\mathbf A\vec x|$

最常用的三种范数：

$$\|\mathbf A\|_1=\max_{\|\vec x\|_1=1}\|\mathbf A\vec x\|_1\\ \|\mathbf A\|_2=\max_{\|\vec x\|_2=1}\|\mathbf A\vec x\|_2\\ \|\mathbf A\|_\infty=\max_{\|\vec x\|_\infty=1}\|\mathbf A\vec x\|_\infty$$

可以证明

$$\|\mathbf A\|_1=\max_{1\le j\le n}\sum_{i=1}^n|A_{ij}|\\ \|\mathbf A\|_2=\sqrt{\rho(\mathbf A^T\mathbf A)}\\ \|\mathbf A\|_\infty=\max_{1\le i\le n}\sum_{j=1}^n|A_{ij}|$$

其中， $\rho$ 为矩阵的谱半径，即 $\rho(B)=\max\{|\lambda|\mid|\lambda\mathrm I-\mathrm B|=0\}$ （最大的特征值绝对值）

性质：

1. 对任意 $\mathbf A\in R^{n\times n}$ ，$|\mathbf A|\ge 0$ 。当且仅当 $\mathbf A = 0$ 时 $|\mathbf A| = 0$
2. 对任意实常数 $c$ 和 $|\mathbf A|\in R^{n\times n}$ ， $|c\mathbf A|=|c|\cdot|\mathbf A|$
3. 对任意 $\mathbf A, \mathbf B\in R^{n\times n}$ ，有 $|\mathbf A+\mathbf B|\le|\mathbf A|+|\mathbf B|$
4. 对任意向量 $x\in R^n$ ， $\mathbf A \in R^{n\times n}$ 有 $|\mathbf A\vec x|\le|\mathbf A||\vec x|$
5. 对任意 $\mathbf A, \mathbf B\in R^{n\times n}$ ，有 $|\mathbf A\mathbf B|\le|\mathbf A||\mathbf B|$

若 $A\in R^{n\times n}$ ，则 $\rho(\mathbf A)\le|A|$ 。即矩阵的任一范数均可作为矩阵特征值的上界

迭代法

迭代法即其收敛性

对于线性方程组 $\mathbf A\vec x=\vec b$ ，将其变成同解方程组 $\vec x=\mathbf B\mathbf x+\vec f$

建立迭代公式 $\vec x^{(k+1)}=\mathbf B\mathbf x^{(k)}+\vec f (k=0,1,2,\cdots)$

给定初始向量 $\vec x^{(0)}$ 后，按此迭代公式德出解向量序列 $\{x^{(k)}\}$

若 $\lim_{k\rightarrow\infty}|\vec x^{(k)}-\vec c|=0$ 则称向量序列 $\{\vec x^{(k)}\}_{k=0}^\infty$ 收敛于 $\vec c$ ， 并记为 $\lim_{k\rightarrow\infty}x^{(k)}=\vec c$

如果向量序列收敛于 $\vec x^*$ ，则 $\vec x^*=\mathbf B\vec x^*+\vec f$

矩阵 $\mathbf B$ 称为迭代矩阵

如果迭代序列收敛，则称迭代法收敛，否则称迭代法发散。

如果 $|\mathbf B|\lt 1$ ，则

1. 方程组有唯一解
2. 任意初始向量均收敛，且 $|\vec x^{(k+1)}-\vec x^*|\le|\mathbf B||\vec x^{(k)}-\vec x^*|$
3. $|\vec x^{(k)}-\vec x^*|\le\frac{|\mathbf B|}{1-|\mathbf B|}|\vec x^{(k)}-\vec x^{(k-1)}|$
4. $|\vec x^{(k)}-\vec x^*|\le\frac{|\mathbf B|^k}{1-|\mathbf B|}|\vec x^{(1)}-\vec x^{(0)}|$

证明略（P72）

给定方程组，则迭代格式对任意初值都收敛的充要条件为 $\rho(\mathbf B)\lt1$

雅可比迭代法

$$x_i^{(k+1)}=\frac1{a_{ii}}\left(b_i-\sum_{1\le j\le n \wedge i\ne j}a_{ij}x_j^{(k)}\right)$$

记

$$\tilde{\mathbf U}= \begin{bmatrix} & a_{12} & \cdots & a_{1n}\\ & & \cdots & a_{2n}\\ & & & \vdots\\ & & &\\ \end{bmatrix}\\ \mathbf D= \begin{bmatrix} a_{11} & & & \\ & a_{22} & & \\ & & \ddots & \\ & & & a_{nn}\\ \end{bmatrix}\\ \tilde{\mathbf L}= \begin{bmatrix} & & & \\ a_{21} & &\\ \vdots & \vdots && \\ a_{n1} & a_{n2} & \cdots & \\ \end{bmatrix}\\$$

$\mathbf A = \tilde{\mathbf U}+\mathbf D+\tilde{\mathbf L}$

则 $\mathbf B =-\mathbf D^{-1}(\tilde{L}+\tilde{U})$ ， $\vec f=\mathbf D^{-1}\vec b$

即

$$\mathbf B=\begin{bmatrix} 0 & -\frac{a_{12}}{a_{11}} & -\frac{a_{13}}{a_{11}} & \cdots & -\frac{a_{1n}}{a_{11}}\\ -\frac{a_{21}}{a_{22}} & 0 & -\frac{a_{23}}{a_{22}} & \cdots & -\frac{a_{2n}}{a_{22}}\\ -\frac{a_{31}}{a_{3n}} & -\frac{a_{32}}{a_{33}} & 0 & \cdots & -\frac{a_{3n}}{a_{33}}\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ -\frac{a_{n1}}{a_{nn}} & -\frac{a_{n2}}{a_{nn}} & -\frac{a_{n3}}{a_{nn}} & \cdots & 0\\ \end{bmatrix}\\ \vec f = \begin{bmatrix} \frac{b_1}{a_{11}}\\ \frac{b_2}{a_{22}}\\ \vdots\\ \frac{b_n}{a_{nn}}\\ \end{bmatrix}$$

高斯-赛德尔迭代法

$$x_i^{(k+1)}=\frac1{a_{ii}}(b_i-\sum_{1\le j\lt i}a_{ij}x_j^{(k+1)}-\sum_{i\lt j\le n}a_{ij}x_j^{(k)})$$

则 $\mathbf B =-(\mathbf D+\tilde{L})^{-1}\tilde{U}$ ， $\vec f=(\mathbf D+\tilde{L})^{-1}\vec b$

对于线性方程组，若

1. $\mathbf A$ 按行或按列为严格对角占优阵，则雅可比迭代法和高斯-赛德尔迭代法均收敛
2. $\mathbf A$ 为对称正定矩阵，则高斯-赛德尔迭代法收敛

逐次超松弛迭代法（ SOR 法）

了解即可，无需掌握。

$$\vec x_i^{(k+1)}=(1-\omega)x^{(k)}_i+\omega\frac1{a_{ii}}\left[b_i-\sum_{j=1}^{i-1}a_{ii}x_j^{(k+1)}-\sum_{j=i+1}^na_{ij}x_j^{k}\right]$$

其中， $\omega$ 是松弛因子，当 $\omega=1$ 时为高斯-赛德尔迭代法

1. SOR 方法对任意 $x^{(0)}$ 都收敛的必要条件是 $0\lt\omega\lt2$
2. 若系数矩阵 $\mathbf A$ 对称正定，则 $0\lt\omega\lt2$ 时 SOR 方法求解 $\mathbf A\vec x=\vec b$ 对任意 $x^{(0)}$ 收敛
3. 若系数矩阵 $\mathbf A$ 按行（或按列）严格对角占优，则 $0\lt\omega\le1$ 时 SOR 方法对任意 $x^{(0)}$ 收敛