高斯消去法

高斯消去法 #

本质上就是初等数学中的消元法, 但是规范了求解步骤, 便于编写计算机程序.

基本思路就是先将矩阵消元成上三角矩阵, 再根据最后一行的解依次回代.

乘除运算量: 消元部分 $N_1=\sum\limits_{k=1}^{n-1}[(n-k)^2+2(n-k)]=\dfrac{n^3}{3}+\dfrac{n^2}{2}-\dfrac{5n}{6}$, 回代部分 $N_2=\sum\limits_{k=1}^{n-1}(n-k)=\dfrac{n^2}{2}+\dfrac{n}{2}$, 总共为 $N=\dfrac{1}{3}n^3+n^2-\dfrac 1 3 n$.

使用条件: 要求系数矩阵的秩等于 $n$, 即解唯一, 也就是顺序主子式均不为 $0$.

列主元法 #

在上述消元过程中可能会遇到主元 $a_{k,k}^{(k-1)}=0$, 或者 $|a_{k,k}^{(k-1)}|$ 很小, 那么如果我们以这样的主元进行计算就会导致数量级的剧增 (因为涉及除法)和舍入误差的增长.

为了避免上述问题, 我们在每次选取主元时, 应选择该列绝对值最大的那一行并将其交换至第 $k$ 行再进行消元.

在列主元法中 $|a_{i,k}^{(k-1)}|/|a_{k,k}^{(k-1)}|\leqslant 1$, 这就有利于控制误差的传播, 有较好的数值稳定性.