数值分析学习笔记--线性方程组的直接解法

三变量的线性系统确定的一组平面

如有疏漏，敬请指正。

对于一个线性方程组，可表示为如下形式

$$Ax=b$$

其中，$A$被称为系数矩阵，$x$是解向量，$b$是系数向量。当且仅当$A$是一个可逆方阵时，线性方程组存在唯一的解。

尽管克莱姆法则给出了线性方程组的公式解，但是由于其运算量过大，不适合在实务中应用。

线性方程组的解法分为直接解法与迭代解法，直接解法没有系统误差，但是对计算机硬件的要求较高。

高斯顺序消元法

高斯消元法的基本思路是通过矩阵的初等变换，把方程组变换为上三角方程组，然后再回代求解。

还有一个算法是Gauss-Jordan消元法，这个方法把线性方程组变换为对角形方程组，直接求解得出结果。

高斯列主元消元法

以下三个命题等价：

• 高斯消元过程可以顺利进行
• 矩阵存在LU分解
• 矩阵的各阶顺序主子式均不为0

而我们已经知道，只要$\mathrm{det} A \neq 0$，方程组$Ax=b$就有解，这揭示了高斯顺序消元法的一部分局限性。

此外，即使高斯消元法能够进行，如果$| a_{kk}^{(k-1)} |$很小，在运算中作分母时会导致数量级的增长和舍入误差的扩散。

解决这个问题的方法是对矩阵作初等变换，使得在运算中作分母的量的绝对值尽可能大。如果在一列中选择按模最大的元素，并将其调到主干方程位置再进行消元，这种方法称为列主元消元法。

对于每一个$k,k=1,2, \cdots ,n-1$，在消元之前选出$\mid a_{kk}^{(k-1)} \mid , \mid a_{k+1,k}^{(k-1)} \mid , \cdots ,\mid a_{nk}^{(k-1)} \mid$中的值最大的元素$a_{mk}^{(k-1)}$，对k行和m行进行交换以后，再进行消元运算。由于$\det A \neq 0$，可证$a_{kk}^{(k-1)},a_{k+1,k}^{(k-1)}, \cdots ,a_{nk}^{(k-1)}$中至少有一个元素不为零，因此列主元消元法总是可行的。

LU分解法

在用直接分解法解方程$Ax=b$时，首先做出分解$A=LU$，那么线性方程组$Ax=b$可以转化为线性方程组$Ly=b$和$Ux=y$，分解以后再求解方程组只要$O(n^2)$的运算量即可解出$x$。

LU分解有多种形式。设$A=LU$，其中L是下三角方阵，U是单位上三角方阵，是为Crout分解，可以看作是$A^T$的Doolittle分解。

当A是正定实方阵时，$A=LDL^T$，其中$L$是单位下三角方阵，$D$是对角方阵，这种分解通常称为$LDL^T$分解。

Doolittle分解

设A的各阶主子式不为零，$A=LU$，其中L是单位下三角阵，U为上三角阵。

$$\begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & & \vdots \\ a_{n1} & a_{n2} & \cdots & a_{nn}\\ \end{bmatrix} = \begin{bmatrix} 1 & & & \\ l_{21} & 1 & & \\ \vdots & \vdots & \ddots & \\ l_{n1} & l_{n2} & \cdots & 1 \\ \end{bmatrix} \begin{bmatrix} u_{11} & u_{12} & \cdots & u_{1n} \\ & u_{22} & \cdots & u_{2n} \\ & & \ddots & \vdots \\ & & & u_{nn} \\ \end{bmatrix}$$

Doolittle分解可以按照如下顺序进行

• 计算U的第一行元素，$u_{1j}=a_{1j},j=1,2, \cdots ,n$
• 计算L的第一列元素，$l_{i1}=\frac{a_{i1}}{u_{11}},i=2,3, \cdots ,n$
• 计算U的第k行元素，$u_{kj}=a_{kj}-\sum_{r=1}^{k-1}l_{kr}u_{rj},j=k,k+1, \cdots ,n$
• 计算L的第k列元素，$l_{ik}=\frac{\left( a_{ik}-\sum_{r=1}^{k-1}l_{ir}u_{rk} \right)}{u_{kk}},i=k+1,k+2, \cdots ,n$

Crout分解

矩阵$A=LU$的Crout分解形式为

$$\begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & & \vdots \\ a_{n1} & a_{n2} & \cdots & a_{nn}\\ \end{bmatrix} = \begin{bmatrix} l_{11} & & & \\ l_{21} & l_{22} & & \\ \vdots & \vdots & \ddots & \\ l_{n1} & l_{n2} & \cdots & l_{nn} \\ \end{bmatrix} \begin{bmatrix} 1 & u_{12} & \cdots & u_{1n} \\ & 1 & \cdots & u_{2n} \\ & & \ddots & \vdots \\ & & & 1 \\ \end{bmatrix}$$

其中，$L_{k}$的分量形式为

$$l_{ik}=a_{ik}-\sum_{r=1}^{k-1}l_{ir}u_{rk},i=k,k+1, \cdots ,n$$

$U_k$的分量形式为为

$$u_{kj}=\frac{\left( a_{kj}-\sum_{r=1}^{k-1} l_{kr}u_{rj} \right)}{l_{kk}},j=k+1,k+2, \cdots ,n$$

求解特殊线性方程组的方法

追赶法

形如

$$\begin{bmatrix} a_1 & b_1 & & & \\ c_2 & a_2 & b_2 & & \\ & \ddots & \ddots & \ddots & \\ & & c_{n-1} & a_{n-1} & b_{n-1} \\ & & & c_n & a_n \\ \end{bmatrix}$$

的矩阵称为三对角矩阵，追赶法可以用于求解此类方程组。

容易验证L,U具有如下形式

$$\begin{bmatrix} a_1 & b_1 & & & \\ c_2 & a_2 & b_2 & & \\ & \ddots & \ddots & \ddots & \\ & & c_{n-1} & a_{n-1} & b_{n-1} \\ & & & c_n & a_n \\ \end{bmatrix} = \begin{bmatrix} u_1 & & & \\ w_2 & u_2 & & \\ & \ddots & \ddots & \\ & & w_n & u_n \\ \end{bmatrix} \begin{bmatrix} 1 & v_1 & & \\ & 1 & \ddots & \\ & & \ddots & v_{n-1} \\ & & & 1 \\ \end{bmatrix}$$

比较$A=LU$两边元素，可得到$w_i=c_i,i=2,3, \cdots ,n$

若规定$c_1=0$，可得到三角阵分解的计算公式

$$u_k=a_k-c_kv_{k-1}$$ $$v_{k}=\frac{b_k}{u_k}$$

其中$k=1,2, \cdots ,n$

再解线性方程组$Ly=f,Ux=y$

$$y_i=\frac{f_i-c_iy_{i-1}}{u_i},i=1,2, \cdots ,n$$

设

$$v_n=0,x_i=y_i-v_ix_{i+1},i=n,n-1, \cdots ,2,1$$

以上方法被称为追赶法。

$LDL^T$分解

对于对称正定矩阵，常用的方法是$LDL^T$分解。

对$A$作$LDL^T$分解可得

$$A= \begin{bmatrix} 1 & & & \\ l_{21} & 1 & & \\ \vdots & \vdots & \ddots & \\ l_{n1} & l_{n2} & \cdots & 1 \\ \end{bmatrix} \begin{bmatrix} d_1 & & & \\ & d_2 & & \\ & & \ddots & \\ & & & d_n \\ \end{bmatrix} \begin{bmatrix} 1 & l_{12} & \cdots & l_{1n} \\ & 1 & \cdots & l_{2n} \\ & & \ddots & \vdots \\ & & & 1 \\ \end{bmatrix}$$

进行$LDL^T$分解的步骤如下所示

$$d_{k}=a_{kk}-\sum_{r=1}^{k-1} l_{kr}^2d_r$$ $$l_{ik}=\frac{a_{ik}-\sum_{r=1}^{k-1} d_rl_{ir}l_{kr}}{d_k}$$

有$(LDL^T)X=b$，解方程组$Ax=b$可分三步完成

• 解方程组$Lz=b$
• 解方程组$Dy=z$
• 解方程组$L^Tx=y$