引言 Intro

线性系统 Linear System

首先介绍一下线性系统 Linear System

或等价的矩阵，就是 $Ax=b$

克拉默法则 Cramer Rule

A 是 $n\times n$ 方阵。若$\begin{array}{rcl} \det(A) &\neq& 0 \end{array}$，则 $Ax=b$ 有唯一解。

其中 $A_i$是把 $A$ 的 第 $i$ 列换成 $b$ 得到的矩阵。

不会有人忘了怎么算行列式（det）吧？往右下方向乘积之和减去往左下方向乘积之和

对于一个$2 \times2$的行列式$\begin{array}{rcl} A &=& \left[ \begin{array}{cc} a & b \\ c & d \end{array} \right] \end{array}$，$\begin{array}{rcl} \det(A) &=& ad-bc \end{array}$

对于一个$3 \times3$的行列式$\begin{array}{rcl} A &=& \left[ \begin{array}{ccc} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{array} \right] \end{array}$，$\begin{array}{rcl} \det(A) &=& a_{11} \left| \begin{array}{cc} a_{22} & a_{23} \\ a_{32} & a_{33} \end{array} \right| – a_{12} \left| \begin{array}{cc} a_{21} & a_{23} \\ a_{31} & a_{33} \end{array} \right| + a_{13} \left| \begin{array}{cc} a_{21} & a_{22} \\ a_{31} & a_{32} \end{array} \right| \\ &=& a_{11}a_{22}a_{33}+a_{12}a_{23}a_{31}+a_{13}a_{21}a_{32}-a_{13}a_{22}a_{31}-a_{11}a_{23}a_{32}-a_{12}a_{21}a_{33}\end{array}$

---

高斯消元法 Gaussian Elimination

定义

高斯消元的目标，就是把一般的 $Ax=b$化成下面三种之一

1. 对角系统
   $\begin{array}{rcl} \left( \begin{array}{cccc} a_{11} & & & \\ & a_{22} & & \\ & & \ddots & \\ & & & a_{nn} \end{array} \right) \left( \begin{array}{c} x_1 \\ x_2 \\ \vdots \\ x_n \end{array} \right) &=& \left( \begin{array}{c} b_1 \\ b_2 \\ \vdots \\ b_n \end{array} \right) \end{array}$ ，$\begin{array}{rcl} x_i &=& b_i/a_{ii} \end{array}$
2. 下三角
   $\begin{array}{rcl} \left( \begin{array}{cccc} a_{11} & & & \\ a_{21} & a_{22} & & \\ \vdots & \vdots & \ddots & \\ a_{n1} & a_{n2} & \cdots & a_{nn} \end{array} \right) \left( \begin{array}{c} x_1 \\ x_2 \\ \vdots \\ x_n \end{array} \right) &=& \left( \begin{array}{c} b_1 \\ b_2 \\ \vdots \\ b_n \end{array} \right) \end{array}$，$\begin{array}{rcl} x_1 &=& b_1/a_{11} \\ x_i &=& \dfrac{b_i-\sum_{j=1}^{i-1}a_{ij}x_j}{a_{ii}}, \qquad i=2,\ldots,n \end{array}$
3. 上三角
   $\begin{array}{rcl} \left( \begin{array}{cccc} a_{11} & a_{12} & \cdots & a_{1n} \\ & a_{22} & \cdots & a_{2n} \\ & & \ddots & \vdots \\ & & & a_{nn} \end{array} \right) \left( \begin{array}{c} x_1 \\ x_2 \\ \vdots \\ x_n \end{array} \right) &=& \left( \begin{array}{c} b_1 \\ b_2 \\ \vdots \\ b_n \end{array} \right) \end{array}$，$\begin{array}{rcl} x_n &=& b_n/a_{nn} \\ x_i &=& \dfrac{b_i-\sum_{j=i+1}^{n}a_{ij}x_j}{a_{ii}}, \qquad i=n-1,\ldots,1 \end{array}$

增广矩阵 Augmented matrix

把 $A$和 $b$拼成 $[A\mid b]$，消元时 $b$ 跟着一起变。

例如

LU 分解

定义

LU 就是把消元过程写成 $A=LU$。这里 $L$ 对角线为 1（单位下三角），$U$ 是消完后的上三角：

例题：求 $A=\displaystyle\left[\begin{array}{cc}1&1\\3&-4\end{array}\right]$的 LU

构造 L 的规则

Lij​(−c) 是单位下三角矩阵，只在 $(i,j)$ 位置放 $-c$。左乘它 = 第 $i$行减 $c$ 倍第 $j$ 行。

例如 $L_{32}(-2)$就是 $\text{Row 3}-2\times\text{Row 2}$：

逆操作把符号反过来：

把几次消元的初等矩阵乘在一起，乘数会原样堆进同一个 $L$

LU 分解

有了 $A=LU$，解 $Ax=b$ 拆成两步三角方程：

LU 分解的复杂度（感觉不太重要？）

假设我们有 k 个线性系统 Ax = b1, Ax = b2, · · · , Ax = bk：

但是，不是每个 $A$ 都能 LU。例如左上角的数是 0。

比较 $(1,1)$和 $(2,1)$：$b=0$ 且 $ab=1$，矛盾。所以没有（单位下三角）LU。

从上面我们可知，若 $A$ 的所有顺序主子式（左上角切 $1\times1,\ 2\times2,\ \ldots$的行列式）都不为 0，则不用换行就能高斯成上三角，从而有 LU。

以下面为例，$a_1=0$，因此不能LU

若 $A$ 是列对角占优（每一列对角元的绝对值不小于该列其余绝对值之和），则部分主元 Partial Pivoting（每一步在当前列往下找绝对值最大的数，把它换到对角线上，避免主元太小）时不必换行。

作业

用 Gauss 消元解 $\begin{array}{rcl} \left\{\begin{array}{rcr} x_1+x_2+x_3 &=& 3 \\ 2x_1+x_2+3x_3 &=& 0 \\ -x_1-2x_2+2x_3 &=& -5 \end{array}\right. \end{array}$

答案：

L,A 都是 $5\times 5$。若 $LA$ 相当于：第 1 行减 3 倍第 3 行，第 5 行加 2 倍第 3 行。求 $L$ 和 $L^{-1}$

答案：

用 LU 解$\begin{array}{rcl} \left[ \begin{array}{ccc} 2 & 1 & 2 \\ 4 & 3 & 1 \\ 6 & 1 & 5 \end{array} \right] \left[ \begin{array}{c} x_1 \\ x_2 \\ x_3 \end{array} \right] &=& \left[ \begin{array}{c} 6 \\ 11 \\ 13 \end{array} \right] \end{array}$

$\begin{array}{rcl} A &=& \left[ \begin{array}{cc} {a+1} & 2 \\ 2 & 1 \end{array} \right]\end{array}$何时有 LU？

答案：

使用部分主元的高斯消元法来求解$\begin{array}{rcl} \left\{\begin{array}{rcr} x_1-x_2+3x_3 &=& -3 \\ -x_1-2x_3 &=& 1 \\ 2x_1+2x_2+4x_3 &=& 0 \end{array}\right. \end{array}$

答案：

第一列绝对值最大的在第三行

$$\begin{array}{rcl} \left[ \begin{array}{ccc|c} 1 & -1 & 3 & -3 \\ -1 & 0 & -2 & 1 \\ 2 & 2 & 4 & 0 \end{array} \right] &\xrightarrow{\text{Row 1}\leftrightarrow\text{Row 3}}& \left[ \begin{array}{ccc|c} 2 & 2 & 4 & 0 \\ -1 & 0 & -2 & 1 \\ 1 & -1 & 3 & -3 \end{array} \right] \end{array}$$

$$\begin{array}{rcl} &\xrightarrow{\text{Row 2}+\frac12\times\text{Row 1}}& \left[ \begin{array}{ccc|c} 2 & 2 & 4 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & -1 & 3 & -3 \end{array} \right] \\[1.2em] &\xrightarrow{\text{Row 3}-\frac12\times\text{Row 1}}& \left[ \begin{array}{ccc|c} 2 & 2 & 4 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & -2 & 1 & -3 \end{array} \right] \end{array}$$

第二列绝对值最大的在第三行

$$\begin{array}{rcl} &\xrightarrow{\text{Row 2}\leftrightarrow\text{Row 3}}& \left[ \begin{array}{ccc|c} 2 & 2 & 4 & 0 \\ 0 & -2 & 1 & -3 \\ 0 & 1 & 0 & 1 \end{array} \right] \\[1.2em] &\xrightarrow{\text{Row 3}+\frac12\times\text{Row 2}}& \left[ \begin{array}{ccc|c} 2 & 2 & 4 & 0 \\ 0 & -2 & 1 & -3 \\ 0 & 0 & \frac12 & -\frac12 \end{array} \right] \end{array}$$

回代

$$\begin{array}{rcl} \left[ \begin{array}{c} x_1 \\ x_2 \\ x_3 \end{array} \right] &=& \left[ \begin{array}{c} 1 \\ 1 \\ -1 \end{array} \right] \end{array}$$

---

置换矩阵 Permutation Matrices

置换矩阵是每行每列恰好一个 $1$，其余全是 $0$的矩阵。等价于把单位矩阵阵做若干次换行。

也可以多次相乘

$P_{ij}$​：置换矩阵的逆，把 $I$ 的第 $i$ 行和第 $j$ 行对调。对调两次等于没换，所以

PA=LU 分解法 Factorization

相比于LU，这个相当于多了带换行的功能，要把换过的行记进 $P$

用 $PA=LU$解 $Ax=b$

由于 $PAx=Pb$ ，因此我们可得 $LUx=Pb$：

作业

使用PA = LU解线性方程组$\begin{array}{rcl} \left[ \begin{array}{ccc} 1 & 3 & 2 \\ 6 & 3 & 4 \\ 3 & 1 & 5 \end{array} \right] \left[ \begin{array}{c} x_1 \\ x_2 \\ x_3 \end{array} \right] &=& \left[ \begin{array}{c} 0 \\ 1 \\ 3 \end{array} \right] \end{array}$

使用PA = LU解线性方程组$\begin{array}{rcl} \left[ \begin{array}{cc} 3 & 7 \\ 6 & 1 \end{array} \right] \left[ \begin{array}{c} x_1 \\ x_2 \end{array} \right] &=& \left[ \begin{array}{c} 1 \\ -11 \end{array} \right] \end{array}$

---

迭代法 Iterative Methods（应该不重要？）

引言 Intro

迭代方法与不动点迭代类似。它们从初始猜测值开始，然后在每一步中根据迭代规则对该猜测值进行优化。

我们将会介绍两种迭代法：雅可比法 和 高斯-赛德尔法

雅可比法 Jacobi

把 $A$ 拆成对角 + 严格下三角 + 严格上三角：$\begin{array}{rcl} A &=& D+L+U \end{array}$

由 $Ax=b$可得

这样，我们就能写出雅可比迭代公式

高斯-赛德尔法 Gauss-Seidel’s Method

高斯法和雅可比法很像，区别在于高斯法把新的分量也直接算进去了

$B_G$被称为高斯-赛德尔迭代矩阵

例题

求解下列方程组：$\begin{array}{rcl} \left\{\begin{array}{rcr} 8x_1-3x_2+2x_3 &=& 20 \\ 4x_1+11x_2-x_3 &=& 33 \\ 6x_1+3x_2+12x_3 &=& 36 \end{array}\right. \end{array}$，其精确解为 $[3,2,1]^{T}$

逐次超松弛法 Successive Over-Relaxatio(SOR)

在高斯-赛德尔法的更新方向上多走（或少走）一步，用来加快收敛。

目标是选最好的 $\omega$ 让收敛更快。

• $0<\omega<1$：欠松弛（under-relaxation）
• $\omega>1$：超松弛（over-relaxation）
• $\omega=1$：退回到高斯-赛德尔法

高斯-赛德尔法本身是：

于是我们可以求出修正量

乘上 $\omega$

新的 $x^{k+1}$是当前值 $x^{k}$ 和高斯-赛德尔的加权平均。

---

线性迭代法的收敛性

引言 Intro

方阵 $B$ 的谱半径 spectral radius 是方针特征值的绝对值的最大值。

不会有人忘了什么是特征值吧？求解特征方程 |A − λI|=0 的 λ 即可

若 $\rho(B)<1$，$f$任意，则对任何初值 $x_0$​，迭代$\begin{array}{rcl} x_{k+1} &=& Bx_k+f \end{array}$都收敛。存在唯一 $x^{*}$ 使得

严格对角占优 strictly diagonally dominant

每个对角元的绝对值严格大于同行其余绝对值之和

如果 矩阵 A 严格对角占优 ，那么我们可以得到：

1. $A$ 非奇异；（其对应的行列式值为零且矩阵的秩非满秩）
2. 对任意 $b$、任意初值，雅可比和高斯-赛德尔法都收敛到 $Ax=b$的唯一解。

收敛条件 Convergent Condition

从前面我们可知，解 $Ax=b$ 时，迭代 $x_k=Bx_{k-1}+f$是否收敛，可以通过两步看

1. A 严格对角占优 $\Rightarrow$雅可比和高斯-赛德尔法都收敛
2. ρ(B)<1 则这种迭代收敛，否则不收敛

若某种矩阵范数（PS：没学过线代的我表示又得补课了）满足 $\|B\|=q<1$，则收敛，且

卡汉必要条件 Kahan necessary condition

$A$ 非奇异，若 SOR 对任意初值 $x^{0}$ 都收敛，则必须满足$\begin{array}{rcl} 0 < \omega < 2 \end{array}$

作业

用雅可比和高斯-赛德尔法解 $\begin{array}{rcl} \left\{\begin{array}{rcr} 10x_1-2x_2-2x_3 &=& 1 \\ -2x_1+10x_2-x_3 &=& 0.5 \\ -x_1-2x_2+3x_3 &=& 1 \end{array}\right. \end{array}$

答案：

对 $\begin{array}{rcl} \left\{\begin{array}{rcr} 5x_1+2x_2+x_3 &=& -12 \\ -x_1+4x_2+2x_3 &=& 20 \\ 2x_1-3x_2+10x_3 &=& 3 \end{array}\right. \end{array}$证明雅可比和高斯-赛德尔法都收敛。

答案：$5>2+1$，$4>1+2$，$10>2+3$（严格对角线占优）