高斯消元法

线性方程组的数值解法主要分为两大类：

直接法
高斯消元法
矩阵分解法
迭代法
雅可比迭代法
高斯-塞尔德迭代法

本节是高斯消元法。基本思想： - 消元过程：通过初等行变换，将原方程组化为同解的上三角方程组（会使求解过程更加简单）。 - 回代过程：从最后一个方程开始，依次向上求解未知数。

基本算法

整体上是计算 $l \to$ 行变换消元 $\to$ 由下到上回代。

构造增广矩阵 $(A \mid b)$：消元过程时针对增广矩阵进行的，千万莫要忘了。
消元：对于第 $k$ 步（$k = 1, 2, \cdots, n-1$）（第 $k$ 步的目标是需要让第 $k$ 行以下的行的第 $k$ 个元素归零）：
若 $a_{kk}^{(k-1)} = 0$，需行交换选主元。（注意，避免$l$ 为零；后面也会将主元素高斯消元来避免 $a^{k-1}_{kk}$过小导致误差放大的问题）
计算比值（乘子），为初等行变换做准备：$l_{ik} = a_{ik}^{(k-1)} / a_{kk}^{(k-1)} \quad (i = k+1, \cdots, n)$。
进行行变换：$\text{第 } i \text{ 行} = \text{第 } i \text{ 行} - l_{ik} \times \text{第 } k \text{ 行}$。$\leftarrow$ 这个是真正的消元过程，前面两步都是做准备
回代：求解上三角方程组（下三角矩阵，从下往上求很简单）：
计算最后一行地一元一次方程求解出第一个分量： $x_n = b_n^{(n-1)} / a_{nn}^{(n-1)}$
把已经已经求解地分量带入到下一个需求解的方程中： $$ \begin{aligned} a_{kk}^{(k-1)}x_k &+ \sum_{j=k+1}^n a_{kj}^{(k-1)} x_j = b_k^{(k-1)} \quad (k=n-1, \cdots, 1) \ x_k &= (b_k^{(k-1)} - \sum_{j=k+1}^n a_{kj}^{(k-1)} x_j) / a_{kk}^{(k-1)} \quad (k=n-1, \cdots, 1) \end{aligned} $$
使用条件和计算量
可行性（定理3.1）：若 $A$ 的顺序主子式均不为零，则所有主元素 $a_{kk}^{(k-1)} \neq 0$，消元过程可进行到底。
计算量：
总乘除法次数：$\frac{1}{3}n^3 + n^2 - \frac{1}{3}n$，为 $O(n^3)$ 量级。
与克莱姆法则对比：高斯消元法计算量远小于克莱姆法则（$n$ 较大时差异巨大）。

主元素高斯消元法

目的：控制计算过程中的舍入误差，防止其传播和扩大，但是其中主要是控制因为 $a^{(k-1)}_{kk}$ 存在误差，而 $l_{ik}=a^{(k-1)}_{ik}/a^{(k-1)}_{kk}$ 会将误差传播和扩大的问题，当选取的主元（分母）相对更大时，能有效控制误差的扩大。
方法：相比于普通的高斯消元法，多了一步主元选择，即在每一步消元前，选取当前列中绝对值最大的元素作为主元（列主元法），把这一行交换到当前对齐的行的最上方。

高斯约旦消元法

即在高斯消元法的消元基础上把系数矩阵化为单位阵，即 $A=I$ ,此时$x = A_{new}x = b_{new}$ ，由此去除了回代部分的麻烦。