数值分析(02):线性方程组的解法¶
Gauss 消元法¶
由前置课程线性代数我们业已学过高斯消元法,现在简单复习一下.
初等行变换¶
下面的三种变换称为初等行变换,经过有限次初等行变换的两个方程组同解:
- 交换两行
- 将一行的倍数加在另一行上
- 将某一行乘以一个非零常数
Gauss 消元法的本质¶
Gauss 消元法其实就是加减消元法的一个比较好听的名字.它的本质就是下列3个步骤
- 对当前处理的列,选取一个非零元素(即主元),并通过行变换将该列在主元下方的元素全部变为零
- 逐列重复步骤 1,直至将整个方程化为行阶梯形
- 从最后一行的方程开始,解出\(x_{n}\),逐步向上回代解出方程
Gauss 消元法的算法复杂度¶
正如我们线性代数所学的,我们一般对增广矩阵形式的方程组用 Gauss 消元法,除了处理对象的不同,和我们上述的讲法并无相异.因此,我们现在便可以以矩阵为工具,来尝试分析 Gauss 消元法的复杂度,出于方便起见,我们现在先只考虑方程有唯一解的情况.所有代入步骤都不计时长.我们这里直接给出消元法的步骤公式
\[
\displaystyle \frac{2}{3}n^3 + \frac{1}{2}n^2 - \frac{7}{6}n+2n+1=O(n^{3})
\]
关于具体的计算方法,详见 Timothy Sauer 的教科书