线性方程组解法

ps 意识到写这个东西比较费时间。。收益比不太高。。所以打算随着自己性子写了。。指此类的只给自己总结看了。。随性有的写一些证明

1_Gauss消去法

简单介绍两种Gauss消去法

顺序Gauss消去法

对于一线性方程组，可将其转化为增广矩阵表示如下：

$\tilde{\boldsymbol{A}}=[\boldsymbol{A}, \boldsymbol{b}]=\left[\begin{array}{cccccc} a_{11} & a_{12} & \cdots & a_{1 n} & \vdots & a_{1, n+1} \\ a_{21} & a_{22} & \cdots & a_{2 n} & \vdots & a_{2, n+1} \\ \vdots & \vdots & & \vdots & \vdots & \vdots \\ a_{n 1} & a_{n 2} & \cdots & a_{n n} & \vdots & a_{n, n+1} \end{array}\right]$

通过不断消元后得到上三角矩阵，再进行回代求解**$x$**

$\tilde{A}\approx\left[\begin{array}{cccccc} a_{11} & a_{12} & \cdots & a_{1 n} & \vdots & a_{1, n+1} \\ 0 & a_{22} & \cdots & a_{2 n} & \vdots & a_{2, n+1} \\ \vdots & \ddots & \ddots & \vdots & \vdots & \vdots \\ 0 & \cdots & 0 & a_{n n} & \vdots & a_{n, n+1} \end{array}\right]$

以上即是顺序$Gauss$消去法的主要内容

其可运行的条件为

定理2.1 其前$n-1$个主元素均不为零的充要条件是系数矩阵的前$n-1$个顺序主子式不为零

列主元的Gauss消去法

相比于顺序Gauss消去法，列主元方法便是多了一步交换操作，在第k次消元前，对增广炬阵$[A^{(k)},b^{(k)}]$做第一种初等行变换（交换两行），将绝对值最大的元素交换到第k行的主对角线位置上。

主要是为了增加数值稳定性，相较于有更好的精度，易知计算量与顺序Gauss消去法相同

定理2.2设方程组的系数矩阵非奇异，则用列主元Gauss消去法求解时，各个列主元均不为零

可见列主元的Gauss消去法的条件也比上述更宽泛，只要求系数矩阵非奇异即可运行

2_直接三角分解法

Doolittle分解法与Crout分解法

易知任意一个矩阵有LU分解使得$A = LU$，其中L是上三角矩阵，U是下三角矩阵

此时对于方程$Ax = y\Rightarrow Ly = b,Ux=y$，两步对比较容易求解的三角矩阵得到$x$,

定理2.3 矩阵A有唯一的Doolittle分解的充要条件是系数矩阵的前$n-1$个顺序主子式不为零

值得一提的是，此分解与Gauss消元基本是等价的只是不同表示

其大体表示如下：

$\boldsymbol{A}=\boldsymbol{L} \boldsymbol{U}=\left[\begin{array}{cccc} 1 & & & \\ l_{21} & 1 & & \\ \vdots & \ddots & \ddots & \\ l_{n 1} & \cdots & l_{n, n-1} & 1 \end{array}\right]\left[\begin{array}{cccc} u_{11} & u_{12} & \cdots & u_{1 n} \\ & u_{22} & \cdots & u_{2 n} \\ & & \ddots & \vdots \\ & & & u_{n n} \end{array}\right]$

而后就可以找到矩阵的分解计算公式

$\begin{cases} k = 1,2,\cdots,n \\ u_{kj} = a_{kj}-\sum\limits_{r=1}^{k-1}l_{kr}u_{rj}\quad(j=k.k+1,\cdots,n) \\ l_{ik} = (a_{ik}-\sum\limits_{r=1}^{k-1}l_{it}u_{tk})/u_{kk}\quad(i=k+1,\cdots,n) \\ \end{cases}$

此外对于Crout分解与Doolittle分解类似，只是一些细节的变化，基本原理相同，此处不多赘述

$\boldsymbol{A}=\tilde{\boldsymbol{L}} \tilde{\boldsymbol{U}}=\left[\begin{array}{ccc} l_{11} & & \\ \vdots & \ddots & \\ & & \\ l_{n 1} & \cdots & l_{n n} \end{array}\right]\left[\begin{array}{cccc} 1 & u_{12} & \cdots & u_{1 n} \\ & \ddots & \ddots & \vdots \\ & & \ddots & u_{n-1, n} \\ & & & 1 \end{array}\right]$

对于分解法同样有对应的列主元法，通过交换主元来实现分解

定理2.4若矩阵A非奇异，则存在置换矩阵Q使得QA可做Doolittle分解$QA = LU$

2.3 矩阵的条件数与病态方程组

2.3.1 矩阵的条件数

• 条件数：对于任何精确的数据，存入计算机中也往往受到限制变为近似数，研究因变量与系数矩阵有了微小变化使得最终解向量的变化相关的量称为矩阵A的条件数

定理2.6 设$A, \ \Delta A\in R^{n\times n},b,\Delta b\in R^n,A$非奇异$，b\not= 0,x$是方程组$Ax=b$的解向量。若有$||A|| < \frac 1{||A^{-1}||}$则

1. 方程组$(A+\Delta A)(x+\Delta x) = b+\Delta b$ 有唯一解$x+\Delta x$

2. 下面估计式成立

   $\frac{||\Delta x||}{||x||}\le\frac{||A||\ ||A^{-1}||}{1-||\Delta A||\ ||A^{-1}||}\big( \frac{||\Delta A||}{||A||} +\frac{||\Delta b||}{||b||} \big)$

根据上式可知主要影响因素为$||A||\ ||A^{-1}||$，于是将其定义为条件数$cond(A) = ||A||\ ||A^{-1}||$

2.3.2 病态方程组的求解问题

• 判断线性方程组$Ax=b$是否病态
  1. $|det A|$较小或者，某些行列近似线性相关
  2. 列主元$Gauss$求解方程组时，出现小的列主元$|a_{i_k^k}^{(k)}|<<1$
  3. 分别用$b , \Delta b(\Delta b\ll1)$作为右端向量，结果相差较大
  4. 矩阵的元素数量级相差较大，且无一定规则
• 一般方法
  1. 高精度算术运算：双精度
  2. 平衡方法，同时左乘矩阵

2.4 迭代法

适用：常用与求解大型稀疏线性方程组

基本步骤：构建无限的向量序列，使其极限是方程组的解向量，使用精度控制

一般形式：

将系数矩阵分解为两个矩阵的差，其中N非奇异,

$A = N-P$

代入$Ax=b$中，$Nx = Px+b$即：$x= N^{-1}Px+N^{-1}b$

记作$x = Gx+d$（对应替代）

定理2.7 设有向量序列$\{x^{(k)}\}$和常向量x^*,若对某种范式，有$\{x^{(k)}\}$$\lim\limits_{k\to \infty}||x^{(k)}-x^*|| = 0$则必有$\lim\limits_{k\to \infty}x^{(k)} = x^*$

定理2.8 对任意的向量d，迭代法收敛的充要条件是$\rho(G)<1$其中$\rho(G)$表示矩阵G的谱半径

定理2.9 若矩阵某种范式$||G||<1$，则

1. 方程组的解$x^*$唯一
2. 对于迭代公式，有$\lim\limits_{k\to \infty}x^{(k)} = x^*$，
   且$||x^{(k)}-x^*||<\frac{||G||^k}{1-||G||}||x^{(1)}-x^{(0)}||$,
   $||x^{(k)}-x^*||<\frac{||G||}{1-||G||}||x^{(k)}-x^{(k-1)}||$

2.4.2 $Jabobi$迭代法

若系数矩阵$A$满足条件$a_{ii}\not =0$将$A$分解为三个矩阵$A=D+L+U$

$\boldsymbol{D}=\left[\begin{array}{cccc} a_{11} & & & \\ & a_{22} & & \\ & & \ddots & \\ & & & a_{n n} \end{array}\right], \quad \boldsymbol{L}=\left[\begin{array}{cccc} 0 & & \\ a_{21} & 0 & & \\ \vdots & \ddots & \ddots & \\ a_{n 1} & \cdots & a_{n, n-1} & 0 \end{array}\right], \quad \boldsymbol{U}=\left[\begin{array}{cccc} 0 & a_{12} & \cdots & a_{1 n} \\ & 0 & \ddots & \vdots \\ & & \ddots & a_{n-1 . n} \\ & & & 0 \end{array}\right]$

代入上述的迭代法一般式可得到如下迭代公式

$x^{(k+1)} = -D^{-1}(L+U)x^{(k)}+D^{-1}b$

迭代矩阵为$G = -D^{-1}(L+U)$

引理 若矩阵是主对角线按行或按列严格占优矩阵，则矩阵是非奇异矩阵

证明：

若是严格占优，则满足条件$|a_{ii}|>\sum\limits_{j=1 j\not=i}^n|a_{ij}|$

对于$A = D+L+U = D(I-G)$则根据$A$知$||G||_\infty = \mathop{max}\limits_{1\le i\le n}\sum\limits_{j=1 j\not=i}^n \frac{|a_{ij}|}{|a_{ii}|}<1$

则$G$的谱半径小于1，$I-G$必非奇异，于是系数矩阵$A$非奇异

定理2.12 若系数矩阵是主对角线按行或按列严格占优矩阵，则$Jacobi$迭代法求解必收敛

证明：

假定不收敛，则根据充要条件知迭代矩阵必有一特征值$\mu\ge1$,

则有$det(\mu I-G) = 0\Rightarrow \mu^ndet D^{-1}\cdot det[D+\mu^{-1}(L+U)] = 0$

但若系数矩阵是严格占优矩阵，则$D+\mu^{-1}(L+U)$也严格占优，则根据引理知不是奇异矩阵，并且$D^{-1}$自然非奇异，因此矛盾。

PS 看着有点绕实际上很简单，实例如下

2.4.3 $Gauss-Seidel$迭代法

整体收敛于其他证明与上述类似，形式上的变化为尽量的使用新的迭代的数，即

迭代公式为：$x^{(k+1)} = -(D+L)^{-1}(U)x^{(k)}+(D+L)^{-1}b$

2.4.4 逐次超松弛迭代法

对于系数矩阵A的主对角元素不为零，作如下分解

$A = 1\omega D+L+(1-\frac 1\omega )D+U$

有迭代公式$x^{(k+1)}=-({\frac 1\omega D+L})^{-1}[(1-\frac 1\omega )D+U]x^{(k)}+({\frac 1\omega D+L})^{-1}b$

实松弛因子$\omega >0$,

定理2.19 SOR方法收敛的必要条件为$0<\omega<2$

定理2.20 若系数矩阵是主对角线按行或按列严格占优阵，则用$0<\omega\le1$的SOR方法必收敛

定理2.21 若系数矩阵是正定矩阵，则用$0<\omega <2$的SOR方法必收敛