行列式两种求值算法的比较

摘 要： 为了实现科技和工程技术领域中对有限元线性方程组的快速求解，首先需判断该线性方程组所对应的行列式的值是否为零。若该值不为零，则线性方程组有惟一确定的解；否则，线性方程组的解不惟一。利用行列式的基本性质、代数余子式、定理，采用递归程序设计方法，设计了两种算法，用以求解行列式的值；并从运算精度和运行效率上比较了这两种算法，得出了这两种算法各自的适用环境。

关键词： 递归程序设计方法； 行列式算法； 运行效率； 线性方程

中图分类号： TN911?34 文献标识码： A 文章编号： 1004?373X（2014）04?0025?03

Comparison between two determinant evaluation algorithms

WEI Hong?chun

（Department of Computer Science， Sichuan University of Arts and Science， Dazhou 635000， China）

Abstract： In order to quickly solve the value offinite element linear equations in the fields of science， technology and engineering， The first step is to judge that the determinants value corresponding to the given linear equations is zero or not. If the value is nonzero， linear equations have only one determinate solution. Otherwise， the answer is not determinate. Two algorithms were designed by using determinant's basic nature， algebraic complement， relevant theorem and recursive programming methods to solve the determinant's value. The two algorithms were compared in calculative accuracy and operational efficiency. The application environment of each algorithm was achieved.

Keywords： recursive programming method； determinant algorithm； operating efficiency； linear equation

线性代数是研究有限维线性空间及其线性变换的基本理论，在科学技术及工程技术领域中应用十分广泛。例如，运筹学中的线性规划；设计集成电路时，对数百万电子元件的仿真；机械工程领域复杂线性方程组的数值求解；工程测量领域中的测量平差等等。其实质是求解n元一次线性方程组。

对于n元一次线性方程组An×nXn×1=Bn×1，若n阶方阵A满秩时，则有X=A-1B。因此，必须首先求解方阵A所对应的行列式。若该值非零，则A存在可逆矩阵A-1，此方程组有惟一解；否则方阵A是奇异的，方程组的解不惟一。本文探讨了对n阶行列式求值的两种算法，并对这两种算法进行了比较。

1 基本理论

对于n阶行列式A，有：

性质1 互换行列式的两行（列），行列式变号。

性质2 把行列式的某一列（行）的各元素乘以同一数后，加到另一列（行）对应的元素上去，行列式不变。

代数余子式： 在n阶行列式A中，把元素aij所在的第i行和第j列划去后（见图1），剩下的n-1阶行列式叫做元素aij的余子式，记作Mij，记：

[Aij=（-1）i+jMij， i=1，2，…，n；j=1，2，…，n]

式中：Aij是元素aij的代数余子式。

定理1 行列式A的值d等于它的任一行（列）的各元素与其对应的代数余子式乘积之和，即：

[d=j=1naijAij， j=1，2，…，n或d=i=1naijAij， i=1，2，…，n]

2 算法分析与设计

行列式的应用十分广泛，研究行列式的求值算法非常多[1?3]。在一些特殊领域，会产生一些特殊的行列式，如三次样条插值过程中产生的三对角阵，可采用追赶法求解。但对于普通的行列式，利用行列式的性质求解是合理的选择。下面分析并实现了行列式求值的两种算法，用以求解行列式。

图1 代数余子式

2.1 代数余子式

根据定理1所述的代数余子式法，可计算任意n阶行列式的值。为此，可选择最后一行元素，利用代数余子式计算行列式的值。

分析[d=j=1naijAij （j=1，2，…，n）]可知，该式具有递归函数的特点，因此可设计递归函数计算行列式A。为方便分析，采用动态分配的二维数组double **p来计算。p表示待计算的行列式，n表示行列式p的阶。

算法1：

double GetValue（double **p，int n）{

若阶数n=1，返回p[0][0]

double sum = 0； //累加最后一行各元素与其对应的代数余

子式的乘积之和的变量

for（int j = 0 ； j < n ； j++）{//累加最后一行各元素与其对应代数余子式的乘积

动态生成n行n列的临时数组double **p1，用以保存p 中的元素

将n阶行列式p的各元素保存在n阶行列式p1的对应元素中

保存元素p1[n-1][j]的脚标之和至变量pt

保存元素p1[n-1][j]至变量ptd

将ptd所在列右侧的各列元素依次向左移动一列。

动态生成（n-1）阶行列式double **tem

将行列式p1左上角的（n-1）阶行列式转存至tem

释放数组p1

sum += ptd * pow（-1，pt） * GetValue（tem，n-1）；

//累加p[n-1][j]与其代数余子式之积

释放数组tem

}

返回该行列式的值sum

}

采用代数余子式计算行列式，思路清晰，计算简单，是计算低阶行列式的有效方法。

2.2 行列式的基本性质

根据第2.1节的代数余子式法，若能利用行列式的性质1、性质2将n阶行列式A（见图2）化简为最后一列元素中除ann≠0（若存在），而该列其余元素均为零的形式（见图3），则可大大减少计算量。此时行列式的值是ann*A（n-1）（n-1），此式仍具有递归函数的特点。算法设计如算法2所述。

图2 n阶行列式

图3 变换后的第n列

算法2：

double GetLineTran（double **p，int n）{

若阶数n=1，返回p[0][0]

double result = 1.0； //记录行列式中行交换的次数，每交换

一次result = result*（-1）

bool flag = false

//设置行列式最右边列中是否存在某个元素不为0

for（i = 0； i < n； i++）{//i表示行号

若第i行最右边的元素不等于0，则{

flag = true；

若i不是最后一行n-1，则{

交换第i行与第n-1行对应的所有元素 进行一次行变换： result *= -1.0；

}

break；

}

}

if（！flag） return 0； //行列式最右侧列的所有元素全为0，则行列式的值为0

for（i = 0； i < n-1； i++）{ // i表示行号，用p[n-1][n-1]将

P[i][n?1]按规则变换为0（i从0到n-2）

若行列式p[i][n-1]≠0，则{

计算用p[n-1][n-1]将p[i][n-1]变为0的比例因子t=p[i][n-1]/p[n-1][n-1]

将第n-1行的各个元素乘以-t，加到第i行的对应元素上（注：行列式的值不变，此时行列式具有图3的形式）。

}

}

return result * p[n-1][n-1] * GetLineTran（p，n-1）；//返加行列式的值

}

以上两种算法均采用递归思想完成计算[4?6]。对于算法2，可以非常方便地转换为非递归算法。两种算法的运算结果如图4所述。

图4 两种算法的结果

3 算法比较

3.1 精度分析

上述两种算法均可计算n阶行列式的值。算法1中，由于运算过程中只有加减法和乘法运算，除非溢出，否则，计算结果没有精度损失。算法2中，由于施行了行变换，除了加、减、乘法运算外，还涉及除法运算，因此在计算中有精度损失。

3.2 效率分析

算法2在执行过程中，由于所有的运算数据均在二维数组p中，不需要额外的空间开销。对于n阶行列式，其递归调用的次数为n，适合计算较高阶的行列式。实验表明，在VC 6.0环境下，若行列式的元素值在[0，9]间，最高可计算252阶的行列式（见图5）。

图5 算法2所示的高阶行列式运算结果

对于算法1，利用代数余子式完成计算的过程中，需开辟大量的额外空间，并且大量的内存空间只有在相应的递归调用结束后，才能被释放。

采用算法1，对于n阶行列式A，需进行大量的递归调用。对于n阶行列式A，设递归调用的总次数为an。通过分析，所需完成的递归调用次数可用数列an=n·an-1+1 （其中a1=1）进行计算。[an=n?an-1+1]等式两边同除以n！，得：

[ann！=an-1（n-1）！+1n！an=n！?i=1n1i！]

根据上式，当n=6时，a6=1 237；当n=10时，a10=6 235 301。行列式每增加一阶，则递归调用的次数增加得特别快，函数调用的开销相当大。但对于算法2，当n=6时，只需递归调用6次，可见算法2的运算速度相当快。

4 结 语

n元一次线性方程有惟一解的充要条件是相对应的n阶行列式不为零。本文讨论了n阶行列式求值的两种算法，并从精度和执行效率上进行了分析。算法1在精度上较好，但计算的阶数有限；运算速度上，算法2远远高于算法1。因此，若求解低阶线性方程组，且要求的计算精度较高，可采用算法1；若求解高阶线性方程组，例如，对于测量平差中需要求解高阶线性方程组时，可采用算法2。两种算法计算结果都很稳定，但算法1较算法2更稳定，算法2的运算速度远远快于算法1。这两种算法可根据实际情况选用。

参考文献

[1] 张新功.行列式的计算方法探讨[J].重庆师范大学学报：自然科学版，2011（7）：88?92.

[2] 陈云坤，赵平利.用矩阵分块探求计算高阶行列式的新方法[J].贵州大学学报：自然科学版，2005（8）：227?231.

[3] 杨立英，李成群.n阶行列式的计算方法与技巧[J].广西师范学院学报：自然科学版，2006（3）：98?105.

[4] 屈晓.探讨用C语言实现求解行列式[J].电脑知识与技术，2011（10）：6907?6908.

[5] 黄良斌.用C语言实现解线性方程组的高斯消去法[J].数学学习与研究，2009（7）：104?105.

[6] 卫洪春.COCH图形的递归与非递归算法研究[J].计算机与信息技术，2011（12）：42?46.

子式的乘积之和的变量

for（int j = 0 ； j < n ； j++）{//累加最后一行各元素与其对应代数余子式的乘积

动态生成n行n列的临时数组double **p1，用以保存p 中的元素

将n阶行列式p的各元素保存在n阶行列式p1的对应元素中

保存元素p1[n-1][j]的脚标之和至变量pt

保存元素p1[n-1][j]至变量ptd

将ptd所在列右侧的各列元素依次向左移动一列。

动态生成（n-1）阶行列式double **tem

将行列式p1左上角的（n-1）阶行列式转存至tem

释放数组p1

sum += ptd * pow（-1，pt） * GetValue（tem，n-1）；

//累加p[n-1][j]与其代数余子式之积

释放数组tem

}

返回该行列式的值sum

}

采用代数余子式计算行列式，思路清晰，计算简单，是计算低阶行列式的有效方法。

2.2 行列式的基本性质

根据第2.1节的代数余子式法，若能利用行列式的性质1、性质2将n阶行列式A（见图2）化简为最后一列元素中除ann≠0（若存在），而该列其余元素均为零的形式（见图3），则可大大减少计算量。此时行列式的值是ann*A（n-1）（n-1），此式仍具有递归函数的特点。算法设计如算法2所述。

图2 n阶行列式

图3 变换后的第n列

算法2：

double GetLineTran（double **p，int n）{

若阶数n=1，返回p[0][0]

double result = 1.0； //记录行列式中行交换的次数，每交换

一次result = result*（-1）

bool flag = false

//设置行列式最右边列中是否存在某个元素不为0

for（i = 0； i < n； i++）{//i表示行号

若第i行最右边的元素不等于0，则{

flag = true；

若i不是最后一行n-1，则{

交换第i行与第n-1行对应的所有元素 进行一次行变换： result *= -1.0；

}

break；

}

}

if（！flag） return 0； //行列式最右侧列的所有元素全为0，则行列式的值为0

for（i = 0； i < n-1； i++）{ // i表示行号，用p[n-1][n-1]将

P[i][n?1]按规则变换为0（i从0到n-2）

若行列式p[i][n-1]≠0，则{

计算用p[n-1][n-1]将p[i][n-1]变为0的比例因子t=p[i][n-1]/p[n-1][n-1]

将第n-1行的各个元素乘以-t，加到第i行的对应元素上（注：行列式的值不变，此时行列式具有图3的形式）。

}

}

return result * p[n-1][n-1] * GetLineTran（p，n-1）；//返加行列式的值

}

以上两种算法均采用递归思想完成计算[4?6]。对于算法2，可以非常方便地转换为非递归算法。两种算法的运算结果如图4所述。

图4 两种算法的结果

3 算法比较

3.1 精度分析

上述两种算法均可计算n阶行列式的值。算法1中，由于运算过程中只有加减法和乘法运算，除非溢出，否则，计算结果没有精度损失。算法2中，由于施行了行变换，除了加、减、乘法运算外，还涉及除法运算，因此在计算中有精度损失。

3.2 效率分析

算法2在执行过程中，由于所有的运算数据均在二维数组p中，不需要额外的空间开销。对于n阶行列式，其递归调用的次数为n，适合计算较高阶的行列式。实验表明，在VC 6.0环境下，若行列式的元素值在[0，9]间，最高可计算252阶的行列式（见图5）。

图5 算法2所示的高阶行列式运算结果

对于算法1，利用代数余子式完成计算的过程中，需开辟大量的额外空间，并且大量的内存空间只有在相应的递归调用结束后，才能被释放。

采用算法1，对于n阶行列式A，需进行大量的递归调用。对于n阶行列式A，设递归调用的总次数为an。通过分析，所需完成的递归调用次数可用数列an=n·an-1+1 （其中a1=1）进行计算。[an=n?an-1+1]等式两边同除以n！，得：

[ann！=an-1（n-1）！+1n！an=n！?i=1n1i！]

根据上式，当n=6时，a6=1 237；当n=10时，a10=6 235 301。行列式每增加一阶，则递归调用的次数增加得特别快，函数调用的开销相当大。但对于算法2，当n=6时，只需递归调用6次，可见算法2的运算速度相当快。

4 结 语

n元一次线性方程有惟一解的充要条件是相对应的n阶行列式不为零。本文讨论了n阶行列式求值的两种算法，并从精度和执行效率上进行了分析。算法1在精度上较好，但计算的阶数有限；运算速度上，算法2远远高于算法1。因此，若求解低阶线性方程组，且要求的计算精度较高，可采用算法1；若求解高阶线性方程组，例如，对于测量平差中需要求解高阶线性方程组时，可采用算法2。两种算法计算结果都很稳定，但算法1较算法2更稳定，算法2的运算速度远远快于算法1。这两种算法可根据实际情况选用。

参考文献

[1] 张新功.行列式的计算方法探讨[J].重庆师范大学学报：自然科学版，2011（7）：88?92.

[2] 陈云坤，赵平利.用矩阵分块探求计算高阶行列式的新方法[J].贵州大学学报：自然科学版，2005（8）：227?231.

[3] 杨立英，李成群.n阶行列式的计算方法与技巧[J].广西师范学院学报：自然科学版，2006（3）：98?105.

[4] 屈晓.探讨用C语言实现求解行列式[J].电脑知识与技术，2011（10）：6907?6908.

[5] 黄良斌.用C语言实现解线性方程组的高斯消去法[J].数学学习与研究，2009（7）：104?105.

[6] 卫洪春.COCH图形的递归与非递归算法研究[J].计算机与信息技术，2011（12）：42?46.

子式的乘积之和的变量

for（int j = 0 ； j < n ； j++）{//累加最后一行各元素与其对应代数余子式的乘积

动态生成n行n列的临时数组double **p1，用以保存p 中的元素

将n阶行列式p的各元素保存在n阶行列式p1的对应元素中

保存元素p1[n-1][j]的脚标之和至变量pt

保存元素p1[n-1][j]至变量ptd

将ptd所在列右侧的各列元素依次向左移动一列。

动态生成（n-1）阶行列式double **tem

将行列式p1左上角的（n-1）阶行列式转存至tem

释放数组p1

sum += ptd * pow（-1，pt） * GetValue（tem，n-1）；

//累加p[n-1][j]与其代数余子式之积

释放数组tem

}

返回该行列式的值sum

}

采用代数余子式计算行列式，思路清晰，计算简单，是计算低阶行列式的有效方法。

2.2 行列式的基本性质

根据第2.1节的代数余子式法，若能利用行列式的性质1、性质2将n阶行列式A（见图2）化简为最后一列元素中除ann≠0（若存在），而该列其余元素均为零的形式（见图3），则可大大减少计算量。此时行列式的值是ann*A（n-1）（n-1），此式仍具有递归函数的特点。算法设计如算法2所述。

图2 n阶行列式

图3 变换后的第n列

算法2：

double GetLineTran（double **p，int n）{

若阶数n=1，返回p[0][0]

double result = 1.0； //记录行列式中行交换的次数，每交换

一次result = result*（-1）

bool flag = false

//设置行列式最右边列中是否存在某个元素不为0

for（i = 0； i < n； i++）{//i表示行号

若第i行最右边的元素不等于0，则{

flag = true；

若i不是最后一行n-1，则{

交换第i行与第n-1行对应的所有元素 进行一次行变换： result *= -1.0；

}

break；

}

}

if（！flag） return 0； //行列式最右侧列的所有元素全为0，则行列式的值为0

for（i = 0； i < n-1； i++）{ // i表示行号，用p[n-1][n-1]将

P[i][n?1]按规则变换为0（i从0到n-2）

若行列式p[i][n-1]≠0，则{

计算用p[n-1][n-1]将p[i][n-1]变为0的比例因子t=p[i][n-1]/p[n-1][n-1]

将第n-1行的各个元素乘以-t，加到第i行的对应元素上（注：行列式的值不变，此时行列式具有图3的形式）。

}

}

return result * p[n-1][n-1] * GetLineTran（p，n-1）；//返加行列式的值

}

以上两种算法均采用递归思想完成计算[4?6]。对于算法2，可以非常方便地转换为非递归算法。两种算法的运算结果如图4所述。

图4 两种算法的结果

3 算法比较

3.1 精度分析

上述两种算法均可计算n阶行列式的值。算法1中，由于运算过程中只有加减法和乘法运算，除非溢出，否则，计算结果没有精度损失。算法2中，由于施行了行变换，除了加、减、乘法运算外，还涉及除法运算，因此在计算中有精度损失。

3.2 效率分析

算法2在执行过程中，由于所有的运算数据均在二维数组p中，不需要额外的空间开销。对于n阶行列式，其递归调用的次数为n，适合计算较高阶的行列式。实验表明，在VC 6.0环境下，若行列式的元素值在[0，9]间，最高可计算252阶的行列式（见图5）。

图5 算法2所示的高阶行列式运算结果

对于算法1，利用代数余子式完成计算的过程中，需开辟大量的额外空间，并且大量的内存空间只有在相应的递归调用结束后，才能被释放。

采用算法1，对于n阶行列式A，需进行大量的递归调用。对于n阶行列式A，设递归调用的总次数为an。通过分析，所需完成的递归调用次数可用数列an=n·an-1+1 （其中a1=1）进行计算。[an=n?an-1+1]等式两边同除以n！，得：

[ann！=an-1（n-1）！+1n！an=n！?i=1n1i！]

根据上式，当n=6时，a6=1 237；当n=10时，a10=6 235 301。行列式每增加一阶，则递归调用的次数增加得特别快，函数调用的开销相当大。但对于算法2，当n=6时，只需递归调用6次，可见算法2的运算速度相当快。

4 结 语

n元一次线性方程有惟一解的充要条件是相对应的n阶行列式不为零。本文讨论了n阶行列式求值的两种算法，并从精度和执行效率上进行了分析。算法1在精度上较好，但计算的阶数有限；运算速度上，算法2远远高于算法1。因此，若求解低阶线性方程组，且要求的计算精度较高，可采用算法1；若求解高阶线性方程组，例如，对于测量平差中需要求解高阶线性方程组时，可采用算法2。两种算法计算结果都很稳定，但算法1较算法2更稳定，算法2的运算速度远远快于算法1。这两种算法可根据实际情况选用。

参考文献

[1] 张新功.行列式的计算方法探讨[J].重庆师范大学学报：自然科学版，2011（7）：88?92.

[2] 陈云坤，赵平利.用矩阵分块探求计算高阶行列式的新方法[J].贵州大学学报：自然科学版，2005（8）：227?231.

[3] 杨立英，李成群.n阶行列式的计算方法与技巧[J].广西师范学院学报：自然科学版，2006（3）：98?105.

[4] 屈晓.探讨用C语言实现求解行列式[J].电脑知识与技术，2011（10）：6907?6908.

[5] 黄良斌.用C语言实现解线性方程组的高斯消去法[J].数学学习与研究，2009（7）：104?105.

[6] 卫洪春.COCH图形的递归与非递归算法研究[J].计算机与信息技术，2011（12）：42?46.