2 线性方程组的直接法

高斯消元法

原始的高斯消元法

见 线性代数 / 高斯消元法与初等行变换。

高斯消元法的时间复杂度是 $\mathrm{O}(n^3)$。

高斯消元法中，主对角元需要作为分母参与运算，带来两个问题：

• 主对角元不能为零
• 主对角元为很小的数时，倒数很大。由于浮点运算误差，会产生大数吃小数，产生较大误差。

故在此基础上有了选主元思想，即通过矩阵变换选择最合适的主元进行运算。

列主元高斯消元法

1. 找到第一列中最大元素所在行，将其与第一行交换位置使其成为第一行
2. 使用这个第一行完成第一列的消元
3. 找到第二列中最大元素所在行，将其与第二行交换位置使其成为第二行
4. 使用这个第二行完成第二列的校园
5. 如此循环，直到化为上三角矩阵

矩阵的三角分解