计算方法（三）：线性方程组的解法_综合

文章目录

线性方程组的解法
- 高斯消元法与选主元技巧
- - 三角形方程组及其解法
  - 高斯消元法
  - 列主元消元法
- 三角分解法
- - 矩阵的三角分解
  - （矩阵形式）杜利特尔分解法
  - 解三对角线方程组的追赶法
  - 解对称正定矩阵方程组的平方根法
- 向量和矩阵的范数
- - 向量的范数
  - 矩阵的范数
- 迭代法
- - 雅可比迭代法
  - 高斯-赛德尔迭代法
  - 迭代收敛条件与误差估计
  - 逐次超松弛（SOR）迭代法
- 方程组的状态与解的迭代改善
- - 方程组的状态与矩阵的条件数
  - 方程组近似解可靠性判别法
  - 近似解的迭代改善法
  - 预条件处理方法

线性方程组的解法

高斯消元法与选主元技巧

基本思想：通过初等行变换，将一个方程乘以某个常数，一个方程加上另一个方程的常数倍等，减少方程中的未知数数目，最后化成三角形方程组，从而得到所需要的解。

三角形方程组及其解法

上三角形方程组：
$\begin{cases}a_{11}x_1+a_{12}x_2+\cdots+a_{1n}x_n=b_1\\\ \ \ \ \ \ \ \ \ \ \ \ \ \ a_{22}x_2+\cdots+a_{2n}x_n=b_2\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \cdots \ \ \cdots\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ a_{nn}x_n=b_n\end{cases}$

用回代的方法求解：先从第n个方程求出 $x_n$ ，代入第n-1个方程求出 $x_{n-1}$ ，依次类推，可求出所有的 $x_i$ ：
$\begin{cases}x_n=\frac{b_n}{a_{nn}}\\x_i=\frac{b_i-\sum_{j=i+1}^na_{ij}x_j}{a_{ii}}\end{cases}\\要求a^{(i)}_{ii}\neq0$
类似的，下三角形方程组：
$\begin{cases}a_{11}x_1 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =b_1\\a_{21}x_1+a_{22}x_2 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =b_2\\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \cdots \ \ \cdots \\a_{n1}x_1+a_{n2}x_2+\cdots+a_{nn}x_n=b_n\end{cases}$
用前代的方法求解：先从第1个方程求出 $x_1$ ，代入第2个方程求出 $x_2$ ，依次类推，可求出所有的 $x_i$ ：
$\begin{cases}x_1=\frac{b_1}{a_{11}}\\x_i=\frac{b_i-\sum_{j=1}^{i-1}a_{ij}x_j}{a_{ii}}\end{cases}$
回代法和前代法的计算量都是 $\frac{1}{2}n(n+1)$ 次乘除运算。

高斯消元法

高斯消元法分为两大步：消元和回代

（1）将系数矩阵A经过一系列的初等行变换变成右上三角矩阵，其常向量b也同时作相应变换，即
$\left[\begin{matrix}a_{11}& a_{12} & \cdots&a_{1n}&b_1\\a_{21}& a_{22} & \cdots&a_{2n}&b_2\\\vdots&\vdots&&\vdots\\a_{n1}& a_{n2} & \cdots&a_{nn}&b_n\end{matrix}\right]=\left[\begin{matrix}a_{11}^{(1)}& a_{12} ^{(1)}& \cdots&a_{1n}^{(1)}&b_1^{(1)}\\a_{21}^{(1)}& a_{22}^{(1)} & \cdots&a_{2n}^{(1)}&b_2^{(1)}\\\vdots&\vdots&&\vdots\\a_{n1}^{(1)}& a_{n2}^{(1)} & \cdots&a_{nn}^{(1)}&b_n^{(1)}\end{matrix}\right]\rightarrow\left[\begin{matrix}a_{11}^{(1)}& a_{12} ^{(1)}& \cdots&a_{1n}^{(1)}&b_1^{(1)}\\0& a_{22}^{(2)} & \cdots&a_{2n}^{(2)}&b_2^{(2)}\\\vdots&\vdots&&\vdots\\0& a_{n2}^{(2)} & \cdots&a_{nn}^{(2)}&b_n^{(2)}\end{matrix}\right]=\left[\begin{matrix}A^{(2)}&b^{(2)}\end{matrix}\right]$
其中第i行加上第1行的 $m_{i1}$ 倍
$m_{i1}=\frac{a_{i1}^{(1)}}{a_{11}^{(1)}}\\a_{ij}^{(2)}=a_{ij}^{(1)}-m_{i1}a_{1j}^{(1)}\\b_{i}^{(2)}=b_{i}^{(1)}-m_{i1}b_1^{(1)}$
对 $A^{(2)}x=b^{(2)}$ 再进行消元可得
$\left[\begin{matrix}A^{(3)}&b^{(3)}\end{matrix}\right]=\left[\begin{matrix}a_{11}^{(1)}& a_{12} ^{(1)}& a_{13} ^{(1)}&\cdots&a_{1n}^{(1)}&b_1^{(1)}\\0& a_{22}^{(2)} &a_{23} ^{(2)}& \cdots&a_{2n}^{(2)}&b_2^{(2)}\\0&0&a_{33}^{(3)}&\cdots&a_{3n}^{(3)}&b_3^{(3)}\\\vdots&\vdots&\vdots&&\vdots&\vdots\\0&0&a_{n3}^{(3)}&\cdots&a_{nn}^{(3)}&b_n^{(3)}\end{matrix}\right]$
其中第i行加上第2行的 $m_{i2}$ 倍
$m_{i2}=\frac{a_{i2}^{(2)}}{a_{22}^{(2)}}\\a_{ij}^{(3)}=a_{ij}^{(2)}-m_{i2}a_{2j}^{(2)}\\b_{i}^{(3)}=b_{i}^{(2)}-m_{i2}b_2^{(2)}$
重复上述过程，第k次消元时：
$m_{ik}=\frac{a_{ik}^{(k)}}{a_{kk}^{(k)}}\\a_{ij}^{(k+1)}=a_{ij}^{(k)}-m_{ik}a_{kj}^{(k)}\\b_{i}^{(k+1)}=b_{i}^{(k)}-m_{ik}b_k^{(k)}$
得到与 $A x = b$ 同解的方程组： $A^{(k+1)}x=b^{(k+1)},k=1,2,\cdots,n-1$

保证高斯消元法顺利进行的条件：各次主元素 $a_{ii}^{(i)}\neq0$ ，主元 $a_{ii}^{(i)}\neq0$ 的充要条件是主子矩阵 $A_i\neq0$ 非奇异。

定理1：设 $A=[a_{ij}^{(k)}]\in R^{n\times n},b=(b_1^{(1)},b_2^{(1)},\cdots,b_n^{(1)})\in R$ 。若约化主元 $a_{kk}^{(k)}\neq0$ ，则可通过高斯消元法将方程组 $A x = b$ 约化求解，计算公式如下：

（1）消元计算
$m_{ik}=\frac{a_{ik}^{(k)}}{a_{kk}^{(k)}}\\a_{ij}^{(k+1)}=a_{ij}^{(k)}-m_{ik}a_{kj}^{(k)}\\b_{i}^{(k+1)}=b_{i}^{(k)}-m_{ik}b_k^{(k)}$
（2）回代求解
$\begin{cases}x_n={b_n^{(n)}}/{a_{nn}^{(n)}}\\x_i=({b_i^{(i)}-\sum_{j=i+1}^na_{ij}^{(i)}x_j})/{a_{ii}^{(i)}}\end{cases}$

高斯消元法算法分析：

（1）算法的时间复杂度：共需乘除法运算的总数为
$S=\frac{1}{3}n^3+n^2-\frac{1}{3}n=O(n^3)$
（2）算法的空间复杂度：符合原地工作的原则。

（3）数值计算的稳定性：当 $a_{kk}^{(k)}|=0$ ，运算会中断，即使不等于0，但当 $a_{kk}^{(k)}|$ 很小时，一方面会损失精度，另一方面还可能导致商太大使计算产生溢出。所以，高斯消元法对数值计算是不稳定的。

列主元消元法

列主元的思想是： 当变换到第k步时，从第k列 $a_{kk}^{(k)}$ 及以下的各元素中选取绝对值最大者，然后通过行变换将它交换到主元素 $a_{kk}^{(k)}$ 的位置（k,k）上。即选取 $a_{i_kk}^{(k)}$ ，满足： $|a_{i_kk}^{(k)}|=max_{k\leq i\leq n}|a_{ik}^{(k)}|$ ，进行 $k$ 行与 $i_k$ 行互换。

采用列主元的高斯消元法是不影响求解结果的。

但列主元不能保证当前的主元素是同一行（即第k行）中的绝对值最大者，其计算过程还是不稳定的，不适于求解大规模的线性方程组。

全选主元（简称全主元） ：基本思想是当变换到第k步时，从系数矩阵右下角（n-k-1）阶矩阵中选取绝对值最大的元素，通过行、列变换将它交换到主元素 $a_{kk}^{(k)}$ 的位置（k，k）上。

虽然行交换不影响最后求解的结果，但列交换将会导致最后结果（即解向量）中对应未知数的次序混乱。 必须在选主元过程中记住所进行的一切列交换，以便对最后结果进行恢复。

三角分解法

基本思想：将 $A$ 分解成两个三角形矩阵 $L 、 U$ 的乘积 $A = L U$ ，线性方程组 $A x = b$ 归结为
$\begin{cases}Ly=b\\Ux=y\end{cases}$
这两个方程可以通过前代法和回代法求解。

矩阵的三角分解

常用的矩阵三角分解形式： $A = L U$ ，称为矩阵 $A$ 的 $L U$ 分解。若 $L$ 是单位下三角阵， $U$ 是上三角阵，称为杜利特尔分解；若 $L$ 是下三角阵， $U$ 是单位上三角阵，则称为克劳特分解。

从高斯消元法过程可知，高斯消元法就是对系数矩阵 $A$ 左乘n-1个初等单位下三角矩阵： $A^{(k+1)}=L_kA^{(k)},k=1,2,\cdots,n-1$ ， $m_{ik}=\frac{a_{ik}^{(k)}}{a_{kk}^{(k)}},a_{kk}^{(k)}\neq 0,i=k+1,k+2,\cdots,n$ 。
$L_k=\left[\begin{matrix}1&&&&&\\&\ddots\\&&1\\&&-m_{k+1,k}&1\\&&\vdots&&\ddots\\&&-m_{nk}&&&1\\\end{matrix}\right]\ \ \ \ \ k=1,2,\cdots,n-1$
得：
$A^{(n)}=L_{n-1}L_{n-2}\cdots L_1A\\b^{(n)}=L_{n-1}L_{n-2}\cdots L_1b\\A=(L_1^{-1}L_2^{-1}\cdots L_{n-1}^{-1})A^{(n)}=LU$

其中
$\begin{cases}L=L_1^{-1}L_2^{-1}\cdots L_{n-1}^{-1}\\U=A^{(n)}\end{cases}\\L_k^{-1}=\left[\begin{matrix}1&&&&&\\&\ddots\\&&1\\&&m_{k+1,k}&1\\&&\vdots&&\ddots\\&&m_{nk}&&&1\\\end{matrix}\right]\\L=\left[\begin{matrix}1&&&&&\\m_{21}&1&&&\\m_{31}&m_{32}&\ddots&&\\\vdots&\vdots&\ddots&1&&\\m_{n1}&m_{n2}&&m_{n,n-1}&1\end{matrix}\right]\\U=A^{(n)}=\left[\begin{matrix}a_{11}^{(1)}& a_{12} ^{(1)}& \cdots&a_{1n}^{(1)}\\0& a_{22}^{(2)}& \cdots&a_{2n}^{(2)}\\\vdots&\vdots&&\vdots\\0&0&\cdots&a_{nn}^{(n)}\end{matrix}\right]$
上述的LU分解，被称为杜利特尔（Doolittle）分解。

定理2（矩阵三角分解基本定理）：设 $A\in R^{n\times n}$ ，若 $A$ 的顺序主子式 $det(A_k)\neq0$ ，则存在唯一的杜利特尔分解： $A = L U$ ，其中 $L$ 为单位下三角形矩阵， $U$ 为非奇异的上三角形矩阵。

证明：由定理1和：
$det(A_k)=\left|\begin{matrix}a_{11}& a_{12} & \cdots&a_{1k}\\a_{21}& a_{22} & \cdots&a_{2k}\\\vdots&\vdots&&\vdots\\a_{k1}& a_{k2} & \cdots&a_{kk}\end{matrix}\right|=a_{11}^{(1)}a_{22}^{(2)}\cdots a_{kk}^{(k)}，a_{kk}^{(k)}\neq 0$
可知杜利特尔分解的存在性。

唯一性： 若 $A$ 存在两个杜利特尔分解： $A=L_1U_1,A=L_2U_2$ ，则 $L_1U_1=L_2U_2,L_2^{-1}L_1=U_2U_1^{-1}$ ，由于 $L_2^{-1}L_1$ 是单位上三角形矩阵，可知
$L_2^{-1}L_1=U_2U_1^{-1}=I$
所以， $L_1=L_2,U_1=U_2$ ，得唯一性。

（矩阵形式）杜利特尔分解法

设实矩阵 $A$ 的各阶主子式 $det(A_j)\neq0$ ，则由定理2知，存在唯一的杜利特尔分解： $A = L U$

其中
$L=\left[\begin{matrix}1&&&&\\l_{21}&1&&&\\l_{31}&l_{32}&1&&\\\vdots&\vdots&\ddots&\ddots&\\l_{n1}&l_{n2}&\cdots&l_{n,n-1}&1\end{matrix}\right]\ \ ,U=\left[\begin{matrix}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{matrix}\right]$
由矩阵相等的条件可得：

（1）由 $a_{1i}=u_{1i}$ ，得： $u_{1i}=a_{1i}\ (i=1,2,\cdots,n)$ 。由 $a_{i1}=l_{i1}u_{11}$ ，得： $l_{i1}=a_{i1}/u_{11}\ (i=2,3,\cdots,n)$ 。

（2）由 $a_{2i}=l_{21}u_{1i}+u_{2i}$ ，得： $u_{2i}=a_{2i}-l_{21}u_{1i}(1=2,3,\cdots,n)$ 。由 $a_{i2}=l_{i1}u_{12}+l_{i2}u_{22}$ ，得： $l_{i2}=(a_{i2}-l_{i1}u_{12})/u_{22}(i=3,4,\cdots,n)$ 。

（3）在求出 $U$ 的前k-1行与 $L$ 的前k-1列后， $U$ 的k行、 $L$ 的k列元为：
$u_{ki}=a_{ki}-\sum_{j=1}^{k-1}l_{kj}u_{ji}(i=k,k+1,\cdots,n)\\l_{ik}=(a_{ik}-\sum_{j=1}^{k-1}l_{ij}u_{jk})/u_{kk}(i=k+1,k+2,\cdots,n)$
杜利特尔分解的紧凑格式：定义Q：
$Q=L+U-I=\left[\begin{matrix}u_{11}&u_{12}&\cdots&u_{1k}&\cdots&u_{1n}\\l_{21}&u_{22}&\cdots&u_{2k}&\cdots&u_{2n}\\\vdots&\vdots&&\vdots&&\vdots\\l_{k1}&l_{k2}&\cdots&u_{kk}&\cdots&u_{kn}\\\vdots&\vdots&&\vdots&&\vdots\\l_{n1}&l_{n2}&\cdots&l_{nk}&\cdots&n_{nn}\end{matrix}\right]$
只要求出Q矩阵，便可得到矩阵 $A$ 的三角分解 $L U$ 。

步骤(重要)： $a_{ik}/a_{kk}\rightarrow a_{ik},i=k+1,k+2,\cdots,n,a_{ij}-a_{ik}a_{kj}\rightarrow a_{ij},i=k+1,\cdots,n,j=k+1,\cdots,n$

之后用： $L Y = b, U X = Y$ ，解方程组。

解三对角线方程组的追赶法

$A=\left[\begin{matrix}a_{11}&a_{12}&&&&\\a_{21}&a_{22}&a_{23}&&0&&\\&a_{32}&a_{33}&a_{34}&&\\&&\ddots&\ddots&\ddots&&\\&&0&a_{n-1,n-2}&a_{n-1,n-1}&a_{n-1,n}\\&&&&a_{n,n-1}&a_{nn}\end{matrix}\right]$

称线性方程组 $A x = b$ 为三对角线方程组。

若 $A$ 满足：
$\begin{cases}|a_{11}|>|a_{12}|>0\\|a_{ii}|\geq|a_{i,i-1}|+|a_{i,i+1}|>0,i=2,3,\cdots,n-1\\|a_{nn}|>|a_{n,n-1}|>0\end{cases}$

则称 $A x = b$ 为对角占优的三对角线方程组。

设 $A x = b$ 进行LU分解： $A = L U$ ：
$L=\left[\begin{matrix}1&&&&\\l_{21}&1&&&\\0&l_{32}&1&&\\\vdots&\ddots&\ddots&\ddots&\\0&\cdots&0&l_{n,n-1}&1\end{matrix}\right]\ \ ,U=\left[\begin{matrix}u_{11}&a_{12}&0&\cdots&0\\&u_{22}&a_{23}&\cdots&0\\&&\ddots&\ddots\\&&&u_{n-1,n-1}&a_{n-1,n}\\&&&&u_{nn}\end{matrix}\right]$
由矩阵乘法和矩阵相等得
$\begin{cases}u_{11}=a_{11}\\l_{i,i-1}=a_{i,i-1}/u_{i-1,i-1}\\u_{ii}=a_{ii}-l_{i,i-1}a_{i-1,i}\end{cases}\ \ \ \ \ \ (i=2,3,\cdots,n)$
得到LU分解之后，就可通过方程组
$Ly=b\\Ux=y$
得到线性方程组的解
$\begin{cases}y_1=b_1\\y_i=b_i-l_{i,i-1}y_{i-1}\\i=2,3,\cdots,n\end{cases}\ \ \ \ \ \begin{cases}x_n=y_n/u_{nn}\\x_i=({y_i-a_{i,i+1}*x_{i+1}})/{u_{ii}}\ \ \ \ \ i=n-1,n-2,\cdots,1\end{cases}$
上述方法通常称为 “追赶法”。“追”的过程要做4(n-1)次乘除法，“赶”的过程需要做n次乘除法，总计算量：5n-4。

追赶法本质上是没有选主元的高斯消元法，对一般的三对角方程组来说“追赶法”的计算过程是不稳定的。但当三对角方程组中的系数矩阵满足严格对角占优时，“追赶法”不会出现中间结果数量级的巨大增长和舍入误差的严重积累。

解对称正定矩阵方程组的平方根法

平方根法又称楚列斯基（Cholesky）分解法。

定理3：设 $A\in R^{n\times n}$ 是对称正定矩阵，则存在唯一分解（称为楚列斯基分解）：
$A=\tilde{L}\tilde{L}^T$
其中 $\tilde{L}$ 是对角元为正的下三角阵：
$\tilde{L}=\left[\begin{matrix}l_{11}&&&\\l_{21}&l_{22}&&\\\vdots&\vdots&\ddots&\\l_{n1}&l_{n2}&\cdots&l_{nn}\end{matrix}\right]$

用待定系数法确定 $l_{ij}:a_{ij}=\sum_{p=1}^jl_{ip}l_{jp},1\leq j\leq i\leq n$

由 $a_{11}=l_{11}^2$ ，得 $l_{11}=\sqrt{a_{11}}$

由 $a_{i1}=l_{11}l_{i1}$ ，得 $l_{i1}=a_{i1}/l_{11},i=1,2,\cdots,n$

假设已算出 $L$ 的前j-1列元素，由 $a_{jj}=\sum_{k=1}^jl_{jk}^2$

得 $l_{jj}=(a_{jj}-\sum_{k=1}^{j-1}l_{jk}^2)^{1/2}$

再由 $a_{ij}=\sum_{k=1}^{j-1}l_{ik}l_{jk}+l_{ij}l_{jj}$

得 $l_{ij}=(a_{ij}-\sum_{k=1}^{j-1}l_{ik}l_{jk})/l_{jj},i=j+1,\cdots,n;j\neq n$

可求出所有的 $l_{ij}$ 。

向量和矩阵的范数

向量的范数

范数是对函数、向量和矩阵定义的一种度量形式，任何对象的范数值都是一个非负整数。向量范数是度量向量长度的一种定义形式。

定义1：对任一向量 $x\in C^n$ ，称实数 $N (x) = ∣ ∣ x ∣ ∣$ 为向量 $x$ 的范数。||·||满足下列关系式：

正定性（非负性）： $\forall x\in C^n,||x||\geq0,且||x||=0\Leftarrow\Rightarrow x=0$

齐次性： $\forall x\in C^n和\alpha\in C,有||\alpha x||=|\alpha|·||x||$

三角不等式： $\forall x,y\in C^n,||x+y||\leq||x||+||y||$

几个常用的向量范数：

$||x||_1=\sum_{j=1}^n|x_j|$
$||x||_2=(\sum_{j=1}^n|x_j|^2)^{\frac{1}{2}}$
$||x||_\infin=max_{1\leq j\leq n}|x_j|$

分别称为向量 $x$ 的1范数、2范数和 $\infin$ 范数，更一般的，称： $||x||_p=(\sum_{j=1}^n|x_j|^p)^{\frac{1}{p}}$ 为p范数。

矩阵的范数

定义2：对任一矩阵 $A\in C^{n\times n}$ ，称实数 $N (A) = ∣ ∣ A ∣ ∣$ 为矩阵 $A$ 的范数。||·||满足下列关系式：

正定性（非负性）： $\forall A\in C^{n\times n},||A||\geq0,且||A||=0\Leftarrow\Rightarrow A=0$

齐次性： $\forall A\in C^{n\times n}和\alpha\in C,有||\alpha A||=|\alpha|·||A||$

三角不等式： $\forall A,B\in C^{n\times n},||A+ B||\leq||A||+||B||$

矩阵乘法不等式： $\forall A,B\in C^{n\times n},||A B||\leq||A||·||B||$

矩阵、向量乘法的相容性： $||Ax||\leq ||A||·||x||$

称 $||A||_r=max_{x\neq0}\frac{||Ax||_r}{||x||_r}$ 为从属于向量的范数，或称为由向量范数导出的范数，满足矩阵、向量乘法的相容性： $||Ax||_r\leq ||A||_r·||x||_r$

几个常用的矩阵范数：

$||A||_1=max_{1\leq j\leq n}\sum_{i=1}^n|a_{ij}|$
$||A||_2=[\lambda_{max}(A^TA)]^{1/2}$ ， $\lambda_{max}(·)$ 是矩阵的最大特征值
$||A||_{\infin}=max_{1\leq i\leq n}\sum_{j=1}^n|a_{ij}|$
$||A||_F=(\sum_{i=1}^n\sum_{j=1}^n|a_{ij}|^2)^{1/2}$

分别称为矩阵A的1范数（列模）、2范数（谱模）、 $\infin$ 范数（行模）和F范数。

迭代法

求解线性方程组： $A x = b$ ，其中A为非奇异矩阵，b为n元非零向量，将其等价地转化为方程组 $x = B x + f$ 。

选取初始向量 $x^{(0)}=(x_1^{(0)},x_2^{(0)},\cdots,x_n^{(0)})^T$ ，则可构造迭代法：
$x^{(k+1)}=Bx^{(k)}+f$
得到迭代向量序列 ${x^{(k)}\}$ ，其中 $x^{(k)}=(x_1^{(k)},x_2^{(k)},\cdots,x_n^{(k)})^T$ 。若 $x^{(k)}$ 收敛于 $x^*$ ，则： $x^*=Bx^*+f$ 。 $x^*$ 就是方程组的解，称B为迭代矩阵。若迭代序列收敛，则称迭代法收敛，否则发散。

雅可比迭代法

将A分解为：
$A = D ? L ? U$
其中： $D=diag(a_{11},a_{22},\cdots,a_{nn})$ ，
$L=\left[\begin{matrix}0&&&&\\-a_{21}&0&&&\\-a_{31}&-a_{32}&0&&\\\vdots&\vdots&\ddots&\\-a_{n1}&-a_{n2}&\cdots&a_{n,n-1}&0\end{matrix}\right]\ \ \ U=\left[\begin{matrix}0&-a_{12}&-a_{13}&\cdots&-a_{1n}\\&0&-a_{23}&\cdots&-a_{2n}\\&&\ddots&\ddots&\vdots\\&&&0&-a_{n-1,n}\\&&&&0\end{matrix}\right]$
$Ax=b\rightarrow(D-L-U)x=b\rightarrow Dx=(L+U)x+b$ ，可得雅可比迭代公式：
$x^{(k+1)}=B_Jx^{(k)}+f_J,k=0,1,2,\cdots$
其中雅可比迭代矩阵 $B_J=D^{-1}(L+U),f_J=D^{-1}b$

雅可比迭代公式的分量形式：
$x_i^{(k+1)}=\frac{1}{a_{ii}}(b_i-\sum_{j=1,j\neq i}^na_{ij}x_j^{(k)})$

高斯-赛德尔迭代法

由 $(D ? L) x = U x + b$ ，可得高斯-赛德尔（Gauss-Seidel）迭代公式：
$x^{(k+1)}=B_Gx^{(k)}+f_G,k=0,1,2,\cdots$
其中高斯-赛德尔矩阵 $B_G=(D-L)^{-1}U,f_G=(D-L)^{-1}b$

高斯-赛德尔迭代公式的分量形式：
$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)})$
J迭代法与G-S迭代法的收敛范围并不重合，只是部分相交。 也就是说，可能有J迭代法收敛而G-S迭代法发散的情形发生，G-S迭代法并不是总比J迭代法收敛。在都收敛的情况下，也不能保证G-S迭代法比J迭代法收敛快。

迭代收敛条件与误差估计

定义3：设矩阵 $A\in C^{n\times n}$ 的特征值为 $\lambda_1,\lambda_2,\cdots,\lambda_n$ ，称
$\rho(A)=max_{1\leq j\leq n}|\lambda_j|$
为 $A$ 的谱半径。

定理4：矩阵 $A$ 的谱半径不大于矩阵 $A$ 的任一算子范数 $A||_r$ 。

证明：若 $\lambda$ 是矩阵 $A$ 的特征值（即存在非零向量 $x$ 使得： $Ax=\lambda x$ ），则
$|\lambda|·||x||_r=||\lambda x||_r=||Ax||_r\leq ||A||_r·||x||_r\\|\lambda|\leq ||A||_r\\所以，\rho(A)\leq ||A||_r$

由于矩阵范数计算要比矩阵谱半径计算简单得多，所以常用矩阵范数来估计矩阵特征值的上界。

迭代公式收敛的充要条件：

定理8：迭代公式 $x^{(k+1)}=Bx^{(k)}+f$ 对任何初始向量 $x^{(0)}$ 都收敛的充要条件是 $\rho(B)<1$ ；收敛时， $\rho(B)$ 越小，则收敛速度越快。

证明： $x^*$ 为方程的解， $x^*=Bx^*+f$ ，有 $x^{(k)}-x^*=B(x^{(k-1)}-x^*)=B^k(x^{(0)}-x^*),k=1,2,\cdots$ 。所以，迭代公式对任何初始向量 $x^{(0)}$ 都收敛的充要条件是 $B^k\rightarrow0,k\rightarrow\infin$ ，即 $\rho(B)<1$ 。

若存在矩阵范数 $_r$ ，使得 $B||_r<1$ 则由 $\rho(B) ≤||B||_r$ 知，迭代法收敛。

迭代法收敛的充分条件：

定理5：若迭代过程 $x^{(k+1)}=Bx^{(k)}+f$ 中迭代矩阵 $B$ 满足 $B||_r=q<1$ ，则

对任意初始向量 $x^{(0)}$ ，该迭代过程均收敛于方程 $x = B x + f$ 的唯一解 $x^*$

$||x^*-x^{(k)}||_r\leq\frac{1}{1-q}||x^{(k+1)}-x^{(k)}||_r$

$||x^*-x^{(k)}||_r\leq\frac{q^k}{1-q}||x^{(1)}-x^{(0)}||_r$

证明：1.：由 $|\lambda|\leq\rho(B)\leq||B||_r=q<1$ ，得 $det(I-B)\neq0$ ，故方程 $(I ? B) x = f$ 有唯一解 $x^*$ 。

又 $x^*-x^{(k+1)}=(Bx^*+f)-(Bx^{(k)}+f)=B(x^*-x^{(k)})$ ，得
$||x^*-x^{(k+1)}||_r\leq||B||_r||x^*-x^{(k)}||_r=q||x^*-x^{(k)}||_r\\0\leq||x^*-x^{(k)}||_r\leq q^k||x^*-x^{(0)}||_r\\得\ lim_{k\rightarrow\infin}||x^*-x^{(k)}||_r=0\\从而,lim_{k\rightarrow\infin}x^{(k)}=x^*$
2.: $||x^{(k+1)}-x^{(k)}||_r=||(x^*-x^{(k)})-(x^*-x^{(k+1)})||_r\geq||x^*-x^{(k)}||_r-||x^*-x^{(k+1)}||_r\geq||x^*-x^{(k)}||_r-q||x^*-x^{(k)}||_r=(1-q)||x^*-x^{(k)}||_r$

即得：
$||x^*-x^{(k)}||_r\leq\frac{1}{1-q}||x^{(k+1)}-x^{(k)}||_r$
3.: $x^{(k+1)}-x^{(k)}||_r=||Bx^{(k)}+f-Bx^{(k-1)}-f||_r=||Bx^{(k)}-Bx^{(k-1)}||_r=q||x^{(k)}-x^{(k-1)}||_r=q^k||x^{(1)}-x^{(0)}||_r$

即得：
$||x^*-x^{(k)}||_r\leq\frac{q^k}{1-q}||x^{(1)}-x^{(0)}||_r$

雅可比迭代法与高斯-赛德尔迭代法收敛的充分条件:

定理6：若 $A x = b$ 的系数矩阵 $A=(a_{ij})_{n\times n}$ 按行或列严格对角占优，即
$|a_{jj}|>\sum_{j=1,j\neq i}^n|a_{ij}|,i=1,2,\cdots,n\\或:|a_{jj}|>\sum_{i=1,i\neq j}^n|a_{ij}|,j=1,2,\cdots,n$
则方程组有唯一解，且对于任意初始向量，雅可比迭代法和高斯-赛德尔迭代法都收敛。

定理7：若 $A x = b$ 的系数矩阵 $A=(a_{ij})_{n\times n}$ 为对称正定矩阵，则对任意初始向量，高斯-赛德尔迭代法收敛。

逐次超松弛（SOR）迭代法

逐次超松驰（SOR）迭代法实际上是对高斯-赛德尔迭代法的加权平均，即：
$x_i^{(k+1)}=(1-\omega)x_i^{(k)}+\omega\tilde{x}_i^{(k+1)},i=1,2,\cdots,n\\其中\tilde{x}_i^{(k+1)}为高斯-赛德尔的迭代解:\tilde{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)})$
矩阵形式：
$x^{(k+1)}=B_{\omega}x^{(k)}+f_{\omega},k=0,1,2,\cdots\\其中SOR迭代矩阵：B_{\omega}=(D-\omega L)^{-1}[(1-\omega)D+\omega U],f_{\omega}=\omega(D-\omega L)^{-1}b$
由于 $det(B_{\omega})=det(D-\omega L)^{-1}·det[(1-\omega)D+\omega U]=\frac{1}{a_{11}a_{22}\cdots a_{nn}}·(1-\omega)^na_{11}a_{22}\cdots a_{nn}=(1-\omega)^n$ ，得 $\lambda_1\lambda_2\cdots\lambda_n=det(B_{\omega})=(1-\omega)^n，|1-\omega|^n=|\lambda_1\lambda_2\cdots\lambda_n|\leq (\rho(B_\omega))^n$ ，所以有：

定理9:：若 $A x = b$ 的系数矩阵主对角线上元 $a_{ii}\neq0$ ，则SOR法收敛的必要条件是 $0<\omega<2$ 。

但并不是充分条件：也就是，当 $0<\omega<2$ 时，并不能保证SOR迭代法一定收敛。

实际应用中，可以根据系数矩阵?的性质以及计算的经验来选定合适的松驰因子 $\omega$ ，以加快收敛的速度。

定理10：若系数矩阵 $A$ 是实对称正定矩阵，且松弛因子 $0<\omega<2$ ，则对任意初始向量，SOR迭代法收敛。

定理11：若系数矩阵 $A$ 为弱对角占优矩阵，且为不可约矩阵，则雅可比迭代法、高斯-赛德尔迭代法均收敛。

定理12：若系数矩阵 $A$ 为严格对角占优矩阵（或为弱对角占优不可约矩阵），且 $0<\omega\leq1$ ，则SOR迭代法收敛。

定义4：（收敛速度）称 $R(B)=-ln\rho(B)$ 为迭代法的收敛速度，其中 $B$ 为迭代矩阵。

方程组的状态与解的迭代改善

如果在 $A x = b$ 中的初始数据 $A, b$ 有一个小的扰动，对解的结果有什么影响？

方程组的状态与矩阵的条件数

初始数据 $A, b$ 的微小变化引起了解的很大变化，称这样的方程组为病态方程组。

$b$ 有一个扰动 $\delta b$

设相应方程组的解为 $\tilde{x}(\tilde{x}=x+\delta x)$ ，其中 $x$ 为 $A x = b$ 的精确解。即 $A\tilde{x}=b+\delta b$ ，或 $A(x+\delta x)=b+\delta b$ ， $A\delta x=\delta b，\delta x=A^{-1}\delta b$ ，得
$||\delta x||=||A^{-1}\delta b||\leq||A^{-1}||·||\delta b||$
而 $||b||=||Ax||\leq||A||·||x||$ ，即 $\frac{1}{||x||}\leq \frac{||A||}{||b||}$ 。

所以
$\frac{||\delta x||}{||x||}\leq||A^{-1}||·||A||\frac{||\delta b||}{||b||}$
即：解的相对误差不超过向量 $b$ 的相对误差的 $A^{?1}||·||A||$ 倍。
$A$ 有一个扰动 $\delta A$ （设 $A+\delta A$ 仍可逆）

设相应方程组的解为 $\tilde{x}(\tilde{x}=x+\delta x)$ ，其中 $x$ 为 $A x = b$ 的精确解。即 $(A+\delta A)\tilde{x}=b$ ，或 $(A+\delta A)(x+\delta x)=b$ ， $\delta A(x+\delta x)+A\delta x=0,\delta x=-A^{-1}\delta A(x+\delta x)$