数值分析笔记（五）线性方程组解法

三角分解法

A的杜利特分解公式如下：
$$\begin{array}{rl}& u_{1j}=a_{1j}(j=1,2,\cdots ,n),\\ & l_{i1}=a_{i1}/u_{11}(i=2,3,\cdots ,n),\\ & u_{kj}=a_{kj}-\sum _{m=1}^{k-1}{l}_{bm}{u}_{mj}\Rightarrow a_{kj}(j=k,k+1,\cdots ,n),\\ & l_{ik}=\left(a_{ik}-\sum _{m=1}^{k-1}{l}_{in}{u}_{mk}\right)/u_{kk}\Rightarrow a_{kk}(i=k+1,k+2,\cdots ,n)\\ & (k=2,3,\cdots ,n).\end{array}$$

楚列斯基分解

对于n阶（n>1）对称正定矩阵，楚列斯基分解$A=L\ast L^T$，是唯一的，即
$$\left(\begin{array}{cccc}{a}_{11}& a_{12}& \cdots & a_{1n}\\ a_{21}& a_{22}& \cdots & a_{2n}\\ ⋮& ⋮& & ⋮\\ a_{n1}& a_{n2}& \cdots & a_m\end{array}\right)=\left(\begin{array}{cccc}{l}_{11}& & & \\ l_{21}& l_{22}& & \\ ⋮& ⋮& \ddots & \\ l_{n1}& l_{n2}& \cdots & l_m\end{array}\right)\left(\begin{array}{cccc}{l}_{11}& l_{21}& \cdots & l_{n1}\\ & l_{22}& \cdots & l_{n2}\\ & & \ddots & ⋮\\ & & & l_m\end{array}\right),$$
且
$$\begin{array}{rl}& \{\begin{array}{llc}{l}_{kk}& =\sqrt{a_{kk}-{\sum }_{m=1}^{k-1}{l}_{km}^2},& \\ l_{ik}& =\left(a_{ik}-{\sum }_{m=1}^{k-1}{l}_{im}{l}_{km}\right)/l_{kk}& (i=k+1,k+2,\cdots ,n)\end{array}\end{array}$$

向量范数
$$\begin{array}{c}\parallel x{\parallel }_1=\sum _{i=1}^n\mid x_i\mid ,\\ \parallel x{\parallel }_2=\sqrt{\sum _{i=1}^n{x}_i^2},\\ \parallel x{\parallel }_{\infty }=\underset{1⩽i⩽n}{\max }\mid x_i\mid ,\end{array}$$
矩阵范数
$$\begin{array}{c}\parallel A{\parallel }_1=\underset{1⩽j⩽n}{\max }\sum _{i=1}^n\mid a_{ij}\mid ,列范数\\ \parallel A{\parallel }_{\infty }=\underset{1⩽i⩽n}{\max }\sum _{j=1}^n\mid a_{ij}\mid ,行函数\\ \parallel A{\parallel }_2=\sqrt{{\lambda }_{\max }(A^{\mathrm{T}}A)},谱范数\\ \parallel A{\parallel }_F=\sqrt{\sum _{i=1}^n\sum _{j=1}^n{a}_{ij}^2}.F-范数\end{array}$$
矩阵A的条件数
$$\mathrm{Cond}(A)=\parallel A^{-1}\parallel \parallel A\parallel$$

简单迭代法

设有n阶线性方程组$Ax=b$，$A$为n阶非奇异矩阵，$Ax=b$等价变形为$x=Bx+g$，给定初始向量$x^{(0)}$可得到
$$x^{(k+1)}=B{x}^{(k)}+g(k=0,1,\cdots )$$
若向量序列收敛，其收敛的向量为原方程组的解。其收敛的充要条件是谱半径$\rho (B)<1$.

如果在计算第$i$个分量$x_i^{(k+1)}$，前面的$i-1$个分量用最新的$x_1^{(k+1)}$，$x_2^{(k+1)}$…，$x_{i-1}^{(k+1)}$

而不是$x_1^{(k)}$，$x_2^{(k)}$，…，$x_{i-1}^{(k)}$，则是简单迭代法对应的高斯-赛德尔迭代法。

当简单迭代法的迭代矩阵$B$满足$\parallel B{\parallel }_1<1$或$\parallel B{\parallel }_{\infty }<1$，对应的对应的高斯-赛德尔迭代法关于任意初始向量收敛。

雅可比迭代法

设有n阶线性方程组$Ax=b$，$A$为n阶非奇异矩阵，且对角元$a_{ii}\ne 0(i=1,2,3,...,n)$

将A如下分解，A=L+D+U，即
$$A=\left(\begin{array}{cccc}0& & & \\ a_{21}& 0& & \\ ⋮& ⋮& \ddots & \\ a_{n1}& a_{n2}& \cdots & 0\end{array}\right)+\left(\begin{array}{cccc}{a}_{11}& & & \\ & a_{22}& & \\ & & \ddots & \\ & & & a_{nn}\end{array}\right)+\left(\begin{array}{cccc}0& a_{12}& \cdots & a_{1n}\\ & 0& \cdots & a_{2n}\\ & & \ddots & ⋮\\ & & & 0\end{array}\right),$$
$Ax=b$等价于$(L+D+U)x=b$,

整理得，
$$x=-D^{-1}\left(L+U\right)x+D^{-1}b$$
记$B_J=-D^{-1}\left(L+U\right),g=D^{-1}b$，则构造公式
$$x^{(k+1)}=B_J{x}^{(k)}+g(k=0,1,\cdot \cdot \cdot )$$
为雅可比迭代法，称
$$B_J=-D^{-1}(L+U)=\left(\begin{array}{cccc}0& -\frac{a_{12}}{a_{11}}& \cdots & -\frac{a_{1n}}{a_{11}}\\ & & & \\ -\frac{a_{21}}{a_{22}}& 0& \cdots & -\frac{a_{2n}}{a_{22}}\\ ⋮& ⋮& \ddots & ⋮\\ & & & \\ -\frac{a_{n1}}{a_{nn}}& -\frac{a_{n2}}{a_{nn}}& \cdots & 0\end{array}\right)$$
为雅可比矩阵。

雅可比迭代法关于任意初始向量$x^{(0)}$收敛的充要条件是$\rho (B_j)<1$.

其对应的高斯-赛德尔迭代法为
$$x^{(k+1)}=-(D+L{)}^{-1}U{x}^{(k)}+(D+L{)}^{-1}b$$
若系数矩阵A严格对角占优，高斯-赛德尔迭代法对于任意初始向量$x^{(0)}$收敛。

若系数矩阵A对称正定，高斯-赛德尔迭代法对于任意初始向量$x^{(0)}$收敛。