两类Gauss 消去法算法复杂性比较

于妍

（大连外国语大学商学院，辽宁 大连116044）

1 概述

线性方程组是最重要，也是最基本的一类数学模型。自然科学和工程领域的许多问题最终都归结为求解线性方程组，或者问题的求解过程中需要求解线性方程组。求解非奇异线性方程组的Gauss 消去法主要有两种：基于矩阵的初等行变换的方法和基于矩阵的LU 分解的方法。

为了方便后面的说明，我们首先简单描述如下两种方法：

1.1 基于矩阵的初等行变换的求解n 阶线性方程组Ax=b的列主元Gauss 消去法[1-3]，其求解过程分为两步：

1.1.1 构造增广矩阵(A,b)，利用初等行变换将增广矩阵化为矩阵(U,c)，其中U 为上三角矩阵；

1.1.2 利用解上三角形方程组的算法求解Ux=c，进而得到问题的解。

1.2 基于LU 分解的列选主元的Gauss 消去法求解线性方程组[4-6]，其基本步骤如下：

1.2.1 将系数矩阵A 进行列选主元三角分解(LU 分解)：PA=LU，其中L,U 分别为单位下三角矩阵及上三角矩阵；

1.2.2 利用下三角线性方程组的解法求解线性方程组：Ly=Pb；

1.2.3 利用上三角线性方程组的解法求解线性方程组：Ux=y。

2 两类Gauss 消去法算法复杂性分析