数值分析笔记 4：线性代数方程组数值解法——直接法

上/下三角矩阵的回代/前推、顺序/列主元消去、矩阵三角分解

《应用数值分析》

目录

• 目录
• 4. 线性代数方程组数值解法——直接法
  • 4.1 线性方程组的一般形式/直接法的基本过程
    • 4.1.1 $n$ 阶线性代数方程组的一般形式
    • 4.1.2 上三角方程组与回代过程
    • 4.1.3 下三角方程组与前推过程
  • 4.2 $Gauss$ 消去过程/列主元 $Gauss$ 消去法
    • 4.2.1 $Gauss$ 消去过程
    • 4.2.2 顺序 $Gauss$ 消去法
    • 4.2.3 列主元 $Gauss$ 消去法
  • 4.3 矩阵三角分解：解方程组的直接三角分解法

4. 线性代数方程组数值解法——直接法

4.1 线性方程组的一般形式/直接法的基本过程

4.1.1 $n$ 阶线性代数方程组的一般形式

具有 $n$ 个未知数 $n$ 个方程的 $n$ 阶线性代数方程组的一般形式记为：

$$\begin{cases} a_{11}x_1 + a_{12}x_2 + \cdots + a_{1n}x_n = b_1 \\ a_{21}x_1 + a_{22}x_2 + \cdots + a_{2n}x_n = b_2 \\ \quad \ \vdots \qquad \quad \ \vdots \qquad \qquad \quad \ \ \vdots \quad \quad \ \ \vdots \\ a_{n1}x_1 + a_{n2}x_2 + \cdots + a_{nn}x_n = b_n \end{cases}$$

或写成向量-矩阵形式：

$$\pmb{A}\pmb{x}=\pmb{b}$$

其中，

$$\pmb{A}= \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}, \pmb{x}= \begin{bmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{bmatrix}, \pmb{b} = \begin{bmatrix} b_1 \\ b_2 \\ \vdots \\ b_n \end{bmatrix}.$$

$\pmb{A}$ 称为系数矩阵，$\pmb{x}$ 称为解向量，$\pmb{b}$ 称为右端常数向量。实际应用中，主要处理实数情形的方程组，即 $\pmb{A} \in \pmb{R}^{n \times n}$，$\pmb{b} \in \pmb{R}^n$。

根据 $Grammer$（克兰姆）法则，若系数矩阵 $\pmb{A}$ 非奇异（或者说 $\pmb{A}$ 的行列式值 $\det \pmb{A} \neq 0$），则方程组存在唯一解：

$$x_i = \frac{D_i}{D} \quad (i=1,2,\cdots,n).$$

其中，$D$ 表示 $\pmb{A}$ 对应的行列式值 $\det \pmb{A}$，$D_i$ 表示在 $D$ 中第 $i$ 列用 $\pmb{b}$ 替换。

4.1.2 上三角方程组与回代过程

假如方程组 $\pmb{A}\pmb{x}=\pmb{b}$（$\pmb{A} \in \pmb{R}^{n \times n}$ 非奇异）已被约化为如下形状的上三角方程组：

$$\left \{ \begin{matrix} 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 \\ & & &\ddots & & &\vdots & &\vdots \\ & & & & & &a_{nn}x_n &= &b_n \end{matrix} \right.$$

则通过回代过程可求解：

$$\begin{cases} x_n = b_n / a_{nn} \\ x_i = (b_i - \sum \limits_{j=i+1}^n a_{ij}x_j)/a_{ii} \quad (i=n-1,\cdots,2,1) \end{cases}$$

4.1.3 下三角方程组与前推过程

类似的，假如方程组 $\pmb{A}\pmb{x}=\pmb{b}$（$\pmb{A} \in \pmb{R}^{n \times n}$ 非奇异）已被约化为如下形状的下三角方程组：

$$\left\{\begin{matrix} a_{11}x_1 & & & & & & &= &b_1 \\ a_{21}x_1 &+ &a_{22}x_1 & & & & &= &b_2 \\ \vdots & &\vdots & &\ddots & & & &\vdots \\ a_{n1}x_1 &+ &a_{n2}x_2 &+ &\cdots &+ &a_{nn}x_n &= &b_n \end{matrix}\right.$$

则通过前推过程可求解：

$$\begin{cases} x_1 = b_1 / a_{11} \\ x_i = (b_i - \sum \limits_{j=1}^{i-1} a_{ij}x_j)/a_{ii} \quad (i=2,3,\cdots,n) \end{cases}$$

4.2 $Gauss$ 消去过程/列主元 $Gauss$ 消去法

4.2.1 $Gauss$ 消去过程

待更新

4.2.2 顺序 $Gauss$ 消去法

待更新

4.2.3 列主元 $Gauss$ 消去法

待更新

4.3 矩阵三角分解：解方程组的直接三角分解法

把矩阵 $\pmb{A}$ 分解成两个三角矩阵 $\pmb{L}$ 与 $\pmb{U}$ 的乘积，$\pmb{A}=\pmb{L}\pmb{U}$，消元乘数为：

$$l_{ik}=a_{ik}^{(k)}/a_{kk}^{(k)} \quad (i=k+1,\cdots,n)$$

其中，$\pmb{L}$ 为单位下三角矩阵，$\pmb{U}$ 为上三角矩阵：

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

这样一来，解方程组 $\pmb{A}\pmb{x}=\pmb{b}$ 就转化为解方程组 $\pmb{L}\pmb{U}\pmb{x}=\pmb{b}$。令其中 $\pmb{U}\pmb{x}=\pmb{y}$，则解方程组 $\pmb{L}\pmb{U}\pmb{x}=\pmb{b}$ 又相当于依次解两个三角形方程组：

$$\begin{cases} \pmb{L}\pmb{y}=\pmb{b} \quad \text{(下三角方程组)} \\ \pmb{U}\pmb{x}=\pmb{y} \quad \text{(上三角方程组)} \end{cases}$$

🚩推荐阅读（由hexo文章推荐插件驱动）

• Linux 内核笔记 1：绪论
• Java 笔记 5：集合
• Java 笔记 6：异常、断言和日志
• 5 分钟 Docker 笔记 5：存储
• 读书ing
• 影响力