求解线性方程组

$$Ax=b,A\in R^{n\times n},b\in R^n$$

假设 $A$ 非奇异，则方程有唯一解

直接解法：不考虑舍入误差的情况下，在预定的运算次数内求得精确解。如 Gauss 消去法

迭代解法：基于一定的递推格式，产生逼近精确解的近似序列。收敛性

向量范数

• 向量范数
  • 正定性：$|x|\geq 1$
  • 齐次性：$|\lambda x|=|\lambda||x|$
  • 三角不等式：$|x+y|\leq|x|+|y|$
• 常用向量范数
  • $|x|2=(\sum{i=1}^n|x_i|^2)^{\frac{1}{2}}$
  • $|x|1=\sum{i=1}^n|x_i|$
  • $|x|\infty=\max{1\leq i\leq n}|x_i|$
  • $|x|p=(\sum{i=1}^n|x_i|^p)^{\frac{1}{p}}$
  • 对称正定矩阵 $A$, $|x|_A=\sqrt{(Ax,x)}=\sqrt{(x^TAx)}$
• 范数等价：任意两个范数，存在 $C_1,C_2$，$C_1|x|_B\leq |x|_A\leq C_2|x|_B$，则 $|x|_B$ 域 $|x|_A$ 等价
• 定理：$R^n$ 上一切范数等价
• 定理：向量序列 ${x^k}$ 收敛于 $x^$ $\iff$ $\lim_{k\rightarrow\infty}|x^k-x^|=0$

矩阵范数

• 矩阵范数
  • 非负性
  • 齐次性
  • 三角不等式
  • 相容性：$|AB|\leq|A||B|$
• 常用范数
  • 矩阵算子范数：$|\cdot|$ 为向量范数，$|A|=\sum_{x\in R^n,x\neq 0}\frac{|Ax|}{|x|}=\max_{x\in R^n,|x|=1}|Ax|$
  • 列范数：$|A|1=\max{1\leq j\leq n}\sum_{i=1}^n|a_{ij}|$
  • 行范数：$|A|{\infty}\max{1\leq i\leq n}\sum_{j=1}^n|a_{ij}|$
  • $|A|2=\sqrt{\lambda{\max(A^TA)}}=\sqrt{\rho(A^TA)}$，最大特征值
  • Frobenius 范数：$|A|F=\sqrt{\sum{i=1}^n\sum_{j=1}^n|a_{ij}|^2}$
• 定理：任意算子范数范数等价
• 谱半径：$\rho(A)=\max{|\lambda_1|,\cdots,|\lambda_n|}$
• 定理：任意算子范数，$\rho(A)\leq|A|$
• 定理：若 $A$ 对称，则 $|A|_2=\rho(A)$
• 定理：算子范数，$|A|<1$，则 $I+A$ 非奇异且$|(I+A)^{-1}|<\frac{1}{1-|A|}$

扰动分析

• 方程右端扰动影响：$\frac{|\delta x|}{|x|}\leq \text{cond}(A)\frac{|\delta b|}{|b|}$
• $a_{ij}$ 扰动影响：$\frac{|\delta x|}{|x+\delta x|}\leq \text{cond}(A)\frac{|\delta A|}{|A|}$
• 条件数：$\text{cond}(A)=|A||A^{-1}|$
  • $\text{cond}(A){\infty}=|A|{\infty}|A^{-1}|_{\infty}$
  • $\text{cond}(A)_2=|A|_2|A^{-1}|_2$
  • $A$ 对称，$\text{cond}(A)_2=\frac{\max|\lambda|}{\min|\lambda|}$
• 病态：$\text{cond}(A)»1$
• 良态：$\text{cond}(A)$ 较小

直接解法

高斯消元法

• 记 $A^{(1)}=A=(a_{ij}^{(1)})_{n\times n},b^{(1)}=b=(b_1^{(1)},\cdots,b_n^{(1)})^T$
• 消元：将 $A$ 化为上三角矩阵
  • Step 1: $a_{11}^{(1)}\neq 0,m_{i1}=\frac{a_{i1}^{(1)}}{a_{11}^{(1)}},i=2,\cdots,n$, 将增广矩阵第 $i$ 行减去 $m_{i1}\times$ 第一行
  • Step k: $m_{ik}=\frac{a_{ik}^{(k)}}{a_{kk}^{(k)}},i=k+1,\cdots,n$
  • 共进行 $n-1$ 步
• 回代：逆次序逐一求出三角方程组的解
  • $x_i=\frac{b_i^{i}-\sum_{j=i+1}a_{ij}^{(i)}x_j}{a_{ii}^{(i)}}$
• 若 $A$ 的所有顺序主子式均不为 $0$，则高斯消元无需换行即可进行

高斯主元素消元法

• 当 $|a_{kk}^{(k)}|=0$ 或出现很小的数时，算法不稳定
• 每次选一列中最大的元素为主元素
• 消元过程
  • 选主元：$|a_{i_kk}^{(k)}|=\max_{k\leq i\leq n}|a_{ik}^{(k)}$
  • 若为零则 $|A|=0$
  • 若 $i_k\neq k$，交换 $i$ 与 $k$
  • 消元

三角分解法

• $A=LU$ (高斯消元为因式分解)
  • $m_{ij}=\frac{a_{ij}}{a_{jj}}$
  • $L_k$: 单位阵的第 $k$ 列 $1$ 下方元素分别为 $-m_{k+1,k},\cdots,-m_{n,k}$
  • $L_k^{-1}$: 下方元素变为 $m_{k+1,k},\cdots,m_{n,k}$
  • $L=\prod_{i=1}^{n-1}L_i^{-1}$
• $A$ 的顺序主子式均不为 $0$ 则 $A$ 的 $LU$ 分解唯一（$L$ 为单位下三角阵）
• $AX=LUX=b\Rightarrow UX=Y,LY=b$
  • $y_i=b_i-\sum_{j=1}^{i-1}l_{ij}y_j,n=1,\cdots,n$
  • $x_i=(y_i-\sum_{j=i+1}^nu_{ij}x_j)/u_{ii},i=n,n-1,\cdots,1$
• Doolittle 分解：单位下三角
  • $A=LU$
  • $u_{ri}=a_{ri}-\sum_{k=1}^{r-1}l_{rk}u_{ki},i=r,r+1,\cdots,n$
  • $l_{ir}=(a_{ir}-\sum_{k=1}^{r-1}l_{ik}u_{kr})/u_{rr},i=r,r+1,\cdots,n$
• Crout 分解：单位上三角
  • $A=\widetilde L\widetilde U$
• LDU 分解
• Cholesky 分解：$A\in\mathbb{R}^{n\times n}$ 为对称正定矩阵，存在非奇异下三角矩阵 $L$ 使得 $A=LL^T$。当 $L$ 的主对角元为正时，分解存在且唯一
  • $A=L_1DL_1^T=(L_1D^{\frac{1}{2}})(L_1D^{\frac{1}{2}})^T=LL^T$
  • $l_{ij}=(a_{ij}-\sum_{k=1}^{j-1}l_{ik}l_{jk})/l_{jj},i\geq j$

追赶法解三对角方程组

• 对角占优条件
  • $|b_1|>|c_1|>0$
  • $|b_i|\geq |a_i|+|c_i|$
  • $|b_n|>|a_n|>0$
• 严格占优条件：$|b_i|>|a_i|+|c_i|$
• 满足（严格）对角占优条件的三对角矩阵 $A$ 可以分解为 $A=LU$，$L$ 主对角线上 $\alpha_i$，主对角线下方一条 $\gamma_i$，单位上三角矩阵 $U$ 主对角线上方一条 $\beta_i$
  • $\alpha_i=b_i-a_i\beta_{i-1}, \alpha_1=b_1$
  • $\beta_i=\frac{c_i}{\alpha_i}$
  • $\gamma_i=a_i$
• 追赶法求解 $Ax=f$
  • 计算 $\beta$
  • （追）解 $Ly=f$：$y_i=\frac{f_i-\alpha_iy_{i-1}}{b_i-a_i\beta_{i-1}},i=2,3,\cdots,n$
  • （赶）解 $Ux=y$：$x_i=y_i-\beta_ix_{i+1},i=n-1,n-2,\cdots,2,1$
• 算法稳定
• 时间复杂度 $O(6n)$
• 应用：
  • 计算 $|A|$
  • 计算 $A^{-1}$

迭代解法

• 针对大型稀疏矩阵
• 迭代格式 $x=Bx+f$

Jacobi 迭代

• 从第 $k$ 个方程中解出 $x_k$ 构造迭代格式
• $A=D-L-U$，严格上/下三角矩阵 $L,U$
• 迭代格式：$x=D^{-1}(L+U)x+D^{-1}b$

Gauss-Seidel 迭代

• 计算第 $i$ 个分量时，带入第 $i-1$ 个分量的计算结果
• $x_i^{(k+1)}=\frac{1}{a_{ii}}(b_i-\sum_{j=1}^{i-1}a_{ij}x_j^{(k+1)}-\sum_{j=i+1}^na_{ij}x_j^{(k)})$
• $Dx^{(k+1)}=(Lx^{(k+1)}+Ux^{(k)})+b$
• $x^{(k+1)}=(D-L)^{-1}Ux^{(k)}+(D-L)^{-1}b$

收敛性

• $\epsilon^{(k)}=x^{(k)}-x^*$

• $\epsilon^{(k)}=B\epsilon^{(k-1)}=B^k\epsilon^{(0)}$

  • 趋于 $0$：$B^k\rightarrow O$

• $\lim_{k\rightarrow\infty}B^k=O\iff\rho(B)<1$

  • 推论：$\exists|B|<1$ 是收敛的充分条件

• $\epsilon^{(k)}=\sum_{i=1}^nc_i\lambda_i^ku_i,u_i$ 为 $B$ 的线性无关特征向量

  • $|\epsilon^{(k)}|\leq\rho^k(B)\sum_{i=1}^n|c_i||u_i|$
  • $\rho(B)$ 可以衡量收敛速度
  • $|x^{(k)}-x^*|_v\leq\frac{|B|_v}{1-|B|_v}|x^{(k)}-x^{(k-1)}|$

• 严格对角占优：$|a_{ii}>\sum_{j=1,j\neq i}|a_{ij}|$

• 弱对角占优：$|a_{ii}\geq\sum_{j=1,j\neq i}|a_{ij}|$

• 可约矩阵：$\exists$ 排列矩阵 $P$ 使 $P^TAP$ 为

  $$\begin{bmatrix} A_{11} & A_{12} \newline & A_{22}\end{bmatrix}$$

  • 充要条件：$\exists J\subset{1,2,\cdots,n},a_kj=0,k\in J,j\notin J$

• 若 $A$ 严格对角占优或不可约若对角占优矩阵，则 $A$ 是非奇异矩阵

• 若 $A$ 严格对角占优或不可约若对角占优矩阵，则 Jacobi 迭代和 Gauss-Seidel 迭代收敛

超松弛迭代法

• 松弛因子
  • $\omega<1$：低松弛迭代法
  • $\omega>1$：逐次超松弛迭代法（SOR 迭代方法）
  • $\omega=1$：Gauss-Seidel 迭代
• $x_i^{(k+1)}=x_i^{(k)}+\omega(y_i^{(k+1)}-x_i^{(k)})$
• 迭代格式：$x^{(k+1)}=Bx^{(k)}+f$
  • $B=(D-\omega L)^{-1}[(1-\omega)D+\omega U]$
  • $f=\omega(D-\omega L)^{-1}b$
• 收敛必要条件：$0<\omega<2$
• 若 $A$ 对称正定，则收敛充要条件为 $0<\omega<2$

共轭斜量法

• $A$ 为对称正定矩阵
• 算法：
  • 任选初值 $x_0\in\mathbb{R}^n$ 和阈值 $\epsilon>0,r_0=d_0=b-Ax_0$
  • $x_{k+1}=x_k+\alpha_kd_k$
  • $\alpha_k=\frac{(r_k,r_k)}{d_k,Ad_k}$
  • $r_{k+1}=r_k-\alpha_kAd_k$
  • $d_{k+1}=r_{k+1}+\beta_kd_k$
  • $\beta_k=\frac{(r_{k+1},r_{k+1})}{(r_k,r_k)}$