兩類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 消去法算法復雜性分析