线性代数方程组数值解法

即对n阶线性方程组：
$\mathbf{Ax=b}$
的数值解法。其中 $\mathbf{A}=(a_{ij})$ 是n×n矩阵且非奇异。（以下讨论皆以矩阵A可逆为前提）
以下摘录了两类数值方法：

直接法： $\mathbf{Ax=b}\Longleftrightarrow\mathbf{Gx=d}$ 其中G通常是对角矩阵、三角矩阵或者是一些结构简单的矩阵。
迭代法：
$\mathbf{Ax=b}\Longleftrightarrow\mathbf{x=Bx+k}\\建立迭代格式： \\\mathbf{x^{(i+1)}=Bx^{(i)}+k},i=0,1,...,$
迭代收敛。

一.向量范数与矩阵范数

1.1 向量范数

1.1.1 满足三个条件（向量范数公理）

非负性： $\Vert\mathbf{x}\Vert\ge0$ ,且 $\Vert\mathbf{x}\Vert=0\Longleftrightarrow\mathbf{x=0}$ ;
齐次性: $\Vert\alpha\mathbf{x}\Vert=|\alpha|\Vert\mathbf{x}\Vert$ ;
三角不等式: $\Vert\mathbf{x+y}\Vert\le\Vert\mathbf{x}\Vert+\Vert\mathbf{y}\Vert$

1.1.2 常用的向量范数

1范数： $\Vert{\mathbf{x}}\Vert_1=\sum^n_{i=1}|x_i|$ ;
2范数： $\Vert{\mathbf{x}}\Vert_2=(\sum^n_{i=1}|x_i|^2)^{\frac{1}{2}}$ ;
∞范数： $\Vert{\mathbf{x}}\Vert_\infin=\max_{}|x_i|$ ;
p范数： $\Vert{\mathbf{x}}\Vert_p=(\sum^n_{i=1}|x_i|^p)^{\frac{1}{p}}$ ;

1.2 矩阵范数

1.2.1 矩阵范数公理（四个条件）

非负性： $\Vert\mathbf{A}\Vert\ge0$ ,且 $\Vert\mathbf{A}\Vert=0\Longleftrightarrow\mathbf{A=0}$ ;
齐次性: $\Vert\alpha\mathbf{A}\Vert=|\alpha|\Vert\mathbf{A}\Vert$ ;
三角不等式: $\Vert\mathbf{A+B}\Vert\le\Vert\mathbf{A}\Vert+\Vert\mathbf{B}\Vert$
乘法不等式： $\Vert\mathbf{AB}\Vert\le\Vert\mathbf{A}\Vert\Vert\mathbf{B}\Vert$

1.2.2 常用的矩阵从属范数

相容性（对于向量范数与矩阵范数而言）

满足：
$\forall\mathbf{x,A}:\Vert\mathbf{Ax}\Vert_{向量}\le\Vert\mathbf{A}\Vert_{矩阵}\Vert\mathbf{x}\Vert_{向量}$

从属范数

由向量范数定义：
$\Vert{\mathbf{A}}\Vert=max_{\mathbf{\Vert{x}\Vert}=1}\Vert\mathbf{Ax}\Vert=max_{\mathbf{\Vert{x}\Vert}\ne0}\frac{\Vert\mathbf{Ax}\Vert}{\Vert\mathbf{x}\Vert}$
显然满足相容性。

单位矩阵 $\mathbf{I}$ 的的任何一种从属范数 $\mathbf{\Vert{I}\Vert}$ =1。
从属范数一定与所给定的向量范数相容，反之不然。

常见从属范数

1范数： $\Vert{\mathbf{A}}\Vert_1=\max_{1\le j\le{n}}\sum^n_{i=1}|a_{ij}|$ ;(最大的绝对值的列之和)
2范数： $\Vert{\mathbf{A}}\Vert_2=\sqrt{\rho(A^HA)}$ ;
∞范数： $\Vert{\mathbf{x}}\Vert_\infin=\max_{1\le I\le{n}}\sum^n_{J=1}|a_{ij}|$ ;(最大的绝对值的行之和)

其中：

$\mathbf{A^H}$ 是 $\mathbf{A}$ 的共轭转置（即实数不变，虚数取负再转置）。 $\mathbf{A^HA}$ 为对称矩阵。
$\rho(\mathbf{A^HA})=max|\lambda_i|$ 为 $\mathbf{A^HA}$ 的谱半径。
另可通过 $|\lambda\mathbf{I-A^HA}|=0$ 求得特征值。
当A为正规矩阵，即 $\mathbf{A^HA=AA^H}$ 时，有 $\Vert\mathbf{A}\Vert_2=\rho(\mathbf{A})$ 。证明见此：正规矩阵的谱半径等于谱范数
要点：
A是正规阵，必然存在酉阵Q（Q^HQ=QQ^H=I）满足：
Q^HAQ = D ，D为对角阵且每个对角元值为A的特征值。
可以验证：由所给定的向量范数定义出的从属范数满足4条矩阵范数公理。

Frobenius范数（F范数）

$\Vert\mathbf{A}\Vert_F=(\sum^n_{i=1}\sum^n_{j=1}|a_{ij}|^2)^{\frac{1}{2}}$

二.Gauss消元法

2.1 Gauss消元法

2.2 列选主元素消元法

2.3 全选主元素消元法

三.三角分解法

3.1 LU分解

定理
若A为n阶方阵，且A的所有顺序主子式不等于0，则存在唯一的一个单位下三角矩阵L和一个上三角矩阵U，使A=LU。

3.2 列主元消元法的LU分解

定理
若A非奇异，则一定存在排列矩阵P，使得PA被分解为一个单位下三角阵和一个上三角阵的乘积。
$\mathbf{PAx=Pb}\Longleftrightarrow{\mathbf{LUx=Pb}}$

3.3 杜立特（Doolittle）分解法

设系数矩阵A不需要进行行行交换，且三角分解唯一（所有顺序主子式不为0），则A=LU:
$\mathbf{L}=\begin{bmatrix}1&0&0&...&0\\l_{21}&1&0&...&0\\l_{31}&l_{32}&1&...&0\\.&.&.&.&.\\l_{n1}&l_{n2}&l_{n3}&...&1\end{bmatrix}\\ \mathbf{U}=\begin{bmatrix}u_{11}&u_{12}&u_{13}&...&u_{1n}\\0&u_{22}&u_{23}&...&u_{2n}\\0&0&u_{33}&...&u_{3n}\\ .&.&.&...&.\\0&0&0&...&u_{nn}\end{bmatrix}$
先算第一行、第一列；再顺序向后先行后列计算。
存储可利用原来的系数矩阵A的存储单元。

3.4 Crout分解法

设系数矩阵A不需要进行行行交换，且三角分解唯一（所有顺序主子式不为0），则 $\mathbf{A=\hat{L}\hat{U}}$ :
$\mathbf{\hat{L}}=\begin{bmatrix}l_{11}&0&0&...&0\\l_{21}&l_{22}&0&...&0\\l_{31}&l_{32}&l_{33}&...&0\\.&.&.&.&.\\l_{n1}&l_{n2}&l_{n3}&...&l_{nn}\end{bmatrix}\\ \mathbf{\hat U}=\begin{bmatrix}1&u_{12}&u_{13}&...&u_{1n}\\0&1&u_{23}&...&u_{2n}\\0&0&1&...&u_{3n}\\ .&.&.&...&.\\0&0&0&...&1\end{bmatrix}$
先算第一列、第一行；再顺序向后先列后行计算。
存储可利用原来的系数矩阵A的存储单元。

3.5 Cholesky平方根法

定理
系数矩阵A对称正定，则存在下三角阵L，使得A=LL^T。当限定L的对角元素为正时，这种分解是唯一的。
$\mathbf{A=\bar{L}\bar{L}^T}\\ \mathbf{\bar{L}}=\begin{bmatrix}\bar{l}_{11}&&&&\\\bar{l}_{21}&\bar{l}_{22}&&&\\\bar{l}_{31}&\bar{l}_{32}&\bar{l}_{33}\\...&...&...&...&0\\\bar{l}_{n1}&\bar{l}_{n2}&\bar{l}_{n3}&...&\bar{l}_{nn}\end{bmatrix}$
缺点：需要开根

3.6 改进的Cholesky平方根法

$\mathbf{A={LD}{L}^T}\\ \mathbf{{L}}=\begin{bmatrix}1&&&&\\{l}_{21}&1&&&\\{l}_{31}&{l}_{32}&1\\...&...&...&...&0\\{l}_{n1}&{l}_{n2}&{l}_{n3}&...&1\end{bmatrix}\\ \mathbf{D}=\begin{bmatrix}d_1\\&d_2\\&&...\\&&&&d_n\end{bmatrix}$

3.7 三对角方程组追赶法

Crout分解。

四.矩阵的条件数及误差分析

4.1 条件数

$Cond(\mathbf{A})=\mathbf{\Vert A\Vert\Vert A^{-1}\Vert}\ge1$
特别的，由矩阵二范数定义的条件数为矩阵的谱条件数：
$Cond_2(\mathbf{A})=\mathbf{\Vert A\Vert_2\Vert A^{-1}\Vert_2}$