完全选主元LU分解法

采用完全选主元的另一种LU分解方法是Gauss方法。这种方法将产生2个置换矩阵：一个用于行交换，如在部分选主元中那样；另一个用于列交换。采用这种方法，LU因子满足

P₁AP₂=LU （2.33）

因此，为了对线性方程组Ax=b进行求解，需要采用略微不同的方法。与部分选主元情况相同，置换矩阵P₁左乘线性方程组得

P₁Ax=P₁b=b′ （2.34）

现在，定义一个新的向量z为

x=P₂z （2.35）

然后，将式（2.35）代入到式（2.34）中得

P₁AP₂z=P₁b=b′ （2.36）

LUz=b′

其中，式（2.36）可以通过前代和回代求解出z。一旦求出z，解向量x就可以根据式（2.35）求出。

在全主元方法中，LU分解的每一步，都会对行和列进行交换以使绝对值最大的元素交换到对角元位置。主元从余下的矩阵元素中搜索，包括对角元下面的元素和对角元右面的元素。

全主元策略

（1）在LU分解的第j步，按如下条件选择主元：

|q_jj|=max|q_kl|对k=j，…，n和l=j，…，n （2.37）(www.xing528.com)

（2）交换对应的行并相应地更新A、P和Q。

对A进行LU分解的Gauss算法

（1）将矩阵Q初始化为零矩阵，令j=1；

（2）设令矩阵Q的第j列（矩阵L的第j列），使之等于残余矩阵A（j）的第j列，其中A^（1）=A，即

q_kj=a_kj^（j） 对k=j，…，n （2.38）

（3）如果j=n，则停止。

（4）假定q_jj≠0，设令Q的第j行（U的第j行）为

（5）根据A^（j）产生A^（j+1），即

a_ik^（j+1）=a_ik^（j）-q_ijq_jk 对i=j+1，…，n和k=j+1，…，n （2.40）

（6）设令j=j+1，转到步骤（2）。

Gauss矩阵LU分解算法的乘除法次数与Crout的LU分解算法相同。Crout算法对矩阵A的每个元素只计算1次，而Gauss算法的每一步都要对矩阵A的元素进行更新。Crout算法相比于Gauss算法的一个优点是矩阵A的每个元素只使用一次。由于每个q_jk是a_jk的函数，而a_jk以后再也不会被使用，因此元素q_jk可以覆盖掉元素a_jk。这样，就不需要在内存中存储2个n×n阶矩阵（A和Q），只要存储一个矩阵就够了。

Crout算法和Gauss算法只是众多的LU分解算法中的两种。其他算法还包括Doolittle算法和双因子算法^{[20，26，49]}等。这些算法中的大多数具有相同的乘除法次数，当在传统的串行计算机上实现时，其性能只有微小的差别。但是，当考虑开放内存、存储量和并行计算时，这些算法会有巨大差别。因此，应当明智地选择LU分解的算法，使其适合所应用的场合和所采用的计算机结构。