高斯消去法的计算量及应用-《数值计算方法》

高斯消去法是对增广矩阵（A︙b）进行一系列的初等行变换，将系数矩阵A 约化为具有简单形式的矩阵（如上三角形矩阵）的方法。 虽然高斯消去法是一个古老的求解线性方程组的方法，但由它改进得到的选主元的高斯消去法则是目前计算机上常用的求解低阶稠密矩阵方程组的有效方法。

例7.1　用高斯消去法解方程组

第2 步：将方程组（7.2）的第二个方程乘上2 加到第三个方程，消去其中的未知数x2，又得到与原方程组等价的三角形方程组

最后由上述方程组，用回代的方法，即可求得原方程组的解为

若用矩阵来描述消去法的约化过程，即为

这种求解过程，称为具有回代的高斯消去法。

下面讨论求解一般线性方程组的高斯消去法。 设有n 阶线性方程组

方程组（7.4）可用矩阵形式表示

用－mi1乘上方程组（7.4）第一个方程，分别加到第i 个方程上去（i ＝2，…，n），即实施行的初等变换ri←ri－mi1·r1，（i＝2，…，n），消去第2 个方程—第n 个方程的未知数x1，得到方程组（7.4）的等价方程组

记为

其中，式（7.6）中右上角标为（2）的元素为这一步需要计算的元素，计算公式分别为

第k 步：（k ＝1，2，…，n－1）继续上述消去过程，设第1 步—第k－1 步计算已经完成，得到与原方程组等价的方程组

记为(www.xing528.com)

用回代的方法，即可求得式（7.9）的解，计算公式为

①消元计算

第k 步消元（k ＝1，2，…，n－1）

②回代计算

下面讨论高斯消去法的计算量：

1）消元计算：第k 步（k ＝1，2，…，n－1）

①计算乘数：需要作（n－k）次除法运算；

②消元：需作（n－k）2 次乘法运算；

③计算b（k）：需作（n－k）次乘法运算。

于是全部消元计算共需要作次乘除法运算。

次乘除法运算。 当n ＝20 时，T＝3 060，显然比用克莱姆（Cramer）法则所用的乘除法运算次数少得多。 尽管克莱姆法则在理论上十分完美，却完全不适用于在计算机上求解高维方程组。

另外，在线性代数中往往提倡用初等行变换把增广矩阵化为最简形。 例7.1 的求解过程为