行列式兩種求值算法的比較

摘 要： 為了實現(xiàn)科技和工程技術(shù)領(lǐng)域中對有限元線性方程組的快速求解，首先需判斷該線性方程組所對應(yīng)的行列式的值是否為零。若該值不為零，則線性方程組有惟一確定的解；否則，線性方程組的解不惟一。利用行列式的基本性質(zhì)、代數(shù)余子式、定理，采用遞歸程序設(shè)計方法，設(shè)計了兩種算法，用以求解行列式的值；并從運算精度和運行效率上比較了這兩種算法，得出了這兩種算法各自的適用環(huán)境。

關(guān)鍵詞： 遞歸程序設(shè)計方法； 行列式算法； 運行效率； 線性方程

中圖分類號： 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

線性代數(shù)是研究有限維線性空間及其線性變換的基本理論，在科學(xué)技術(shù)及工程技術(shù)領(lǐng)域中應(yīng)用十分廣泛。例如，運籌學(xué)中的線性規(guī)劃；設(shè)計集成電路時，對數(shù)百萬電子元件的仿真；機械工程領(lǐng)域復(fù)雜線性方程組的數(shù)值求解；工程測量領(lǐng)域中的測量平差等等。其實質(zhì)是求解n元一次線性方程組。

對于n元一次線性方程組An×nXn×1=Bn×1，若n階方陣A滿秩時，則有X=A-1B。因此，必須首先求解方陣A所對應(yīng)的行列式。若該值非零，則A存在可逆矩陣A-1，此方程組有惟一解；否則方陣A是奇異的，方程組的解不惟一。本文探討了對n階行列式求值的兩種算法，并對這兩種算法進行了比較。

1 基本理論

對于n階行列式A，有：

性質(zhì)1 互換行列式的兩行（列），行列式變號。

性質(zhì)2 把行列式的某一列（行）的各元素乘以同一數(shù)后，加到另一列（行）對應(yīng)的元素上去，行列式不變。

代數(shù)余子式： 在n階行列式A中，把元素aij所在的第i行和第j列劃去后（見圖1），剩下的n-1階行列式叫做元素aij的余子式，記作Mij，記：

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

式中：Aij是元素aij的代數(shù)余子式。

定理1 行列式A的值d等于它的任一行（列）的各元素與其對應(yīng)的代數(shù)余子式乘積之和，即：

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

2 算法分析與設(shè)計

行列式的應(yīng)用十分廣泛，研究行列式的求值算法非常多[1?3]。在一些特殊領(lǐng)域，會產(chǎn)生一些特殊的行列式，如三次樣條插值過程中產(chǎn)生的三對角陣，可采用追趕法求解。但對于普通的行列式，利用行列式的性質(zhì)求解是合理的選擇。下面分析并實現(xiàn)了行列式求值的兩種算法，用以求解行列式。

圖1 代數(shù)余子式

2.1 代數(shù)余子式

根據(jù)定理1所述的代數(shù)余子式法，可計算任意n階行列式的值。為此，可選擇最后一行元素，利用代數(shù)余子式計算行列式的值。

分析[d=j=1naijAij （j=1，2，…，n）]可知，該式具有遞歸函數(shù)的特點，因此可設(shè)計遞歸函數(shù)計算行列式A。為方便分析，采用動態(tài)分配的二維數(shù)組double **p來計算。p表示待計算的行列式，n表示行列式p的階。

算法1：

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

若階數(shù)n=1，返回p[0][0]

double sum = 0； //累加最后一行各元素與其對應(yīng)的代數(shù)余

子式的乘積之和的變量

for（int j = 0 ； j < n ； j++）{//累加最后一行各元素與其對應(yīng)代數(shù)余子式的乘積

動態(tài)生成n行n列的臨時數(shù)組double **p1，用以保存p 中的元素

將n階行列式p的各元素保存在n階行列式p1的對應(yīng)元素中

保存元素p1[n-1][j]的腳標之和至變量pt

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

將ptd所在列右側(cè)的各列元素依次向左移動一列。

動態(tài)生成（n-1）階行列式double **tem

將行列式p1左上角的（n-1）階行列式轉(zhuǎn)存至tem

釋放數(shù)組p1

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

//累加p[n-1][j]與其代數(shù)余子式之積

釋放數(shù)組tem

}

返回該行列式的值sum

}

采用代數(shù)余子式計算行列式，思路清晰，計算簡單，是計算低階行列式的有效方法。

2.2 行列式的基本性質(zhì)

根據(jù)第2.1節(jié)的代數(shù)余子式法，若能利用行列式的性質(zhì)1、性質(zhì)2將n階行列式A（見圖2）化簡為最后一列元素中除ann≠0（若存在），而該列其余元素均為零的形式（見圖3），則可大大減少計算量。此時行列式的值是ann*A（n-1）（n-1），此式仍具有遞歸函數(shù)的特點。算法設(shè)計如算法2所述。

圖2 n階行列式

圖3 變換后的第n列

算法2：

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

若階數(shù)n=1，返回p[0][0]

double result = 1.0； //記錄行列式中行交換的次數(shù)，每交換

一次result = result*（-1）

bool flag = false

//設(shè)置行列式最右邊列中是否存在某個元素不為0

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

若第i行最右邊的元素不等于0，則{

flag = true；

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

交換第i行與第n-1行對應(yīng)的所有元素 進行一次行變換： result *= -1.0；

}

break；

}

}

if（！flag） return 0； //行列式最右側(cè)列的所有元素全為0，則行列式的值為0

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

P[i][n?1]按規(guī)則變換為0（i從0到n-2）

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

計算用p[n-1][n-1]將p[i][n-1]變?yōu)?的比例因子t=p[i][n-1]/p[n-1][n-1]

將第n-1行的各個元素乘以-t，加到第i行的對應(yīng)元素上（注：行列式的值不變，此時行列式具有圖3的形式）。

}

}

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

}

以上兩種算法均采用遞歸思想完成計算[4?6]。對于算法2，可以非常方便地轉(zhuǎn)換為非遞歸算法。兩種算法的運算結(jié)果如圖4所述。

圖4 兩種算法的結(jié)果

3 算法比較

3.1 精度分析

上述兩種算法均可計算n階行列式的值。算法1中，由于運算過程中只有加減法和乘法運算，除非溢出，否則，計算結(jié)果沒有精度損失。算法2中，由于施行了行變換，除了加、減、乘法運算外，還涉及除法運算，因此在計算中有精度損失。

3.2 效率分析

算法2在執(zhí)行過程中，由于所有的運算數(shù)據(jù)均在二維數(shù)組p中，不需要額外的空間開銷。對于n階行列式，其遞歸調(diào)用的次數(shù)為n，適合計算較高階的行列式。實驗表明，在VC 6.0環(huán)境下，若行列式的元素值在[0，9]間，最高可計算252階的行列式（見圖5）。

圖5 算法2所示的高階行列式運算結(jié)果

對于算法1，利用代數(shù)余子式完成計算的過程中，需開辟大量的額外空間，并且大量的內(nèi)存空間只有在相應(yīng)的遞歸調(diào)用結(jié)束后，才能被釋放。

采用算法1，對于n階行列式A，需進行大量的遞歸調(diào)用。對于n階行列式A，設(shè)遞歸調(diào)用的總次數(shù)為an。通過分析，所需完成的遞歸調(diào)用次數(shù)可用數(shù)列an=n·an-1+1 （其中a1=1）進行計算。[an=n?an-1+1]等式兩邊同除以n！，得：

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

根據(jù)上式，當(dāng)n=6時，a6=1 237；當(dāng)n=10時，a10=6 235 301。行列式每增加一階，則遞歸調(diào)用的次數(shù)增加得特別快，函數(shù)調(diào)用的開銷相當(dāng)大。但對于算法2，當(dāng)n=6時，只需遞歸調(diào)用6次，可見算法2的運算速度相當(dāng)快。

4 結(jié) 語

n元一次線性方程有惟一解的充要條件是相對應(yīng)的n階行列式不為零。本文討論了n階行列式求值的兩種算法，并從精度和執(zhí)行效率上進行了分析。算法1在精度上較好，但計算的階數(shù)有限；運算速度上，算法2遠遠高于算法1。因此，若求解低階線性方程組，且要求的計算精度較高，可采用算法1；若求解高階線性方程組，例如，對于測量平差中需要求解高階線性方程組時，可采用算法2。兩種算法計算結(jié)果都很穩(wěn)定，但算法1較算法2更穩(wěn)定，算法2的運算速度遠遠快于算法1。這兩種算法可根據(jù)實際情況選用。

參考文獻

[1] 張新功.行列式的計算方法探討[J].重慶師范大學(xué)學(xué)報：自然科學(xué)版，2011（7）：88?92.

[2] 陳云坤，趙平利.用矩陣分塊探求計算高階行列式的新方法[J].貴州大學(xué)學(xué)報：自然科學(xué)版，2005（8）：227?231.

[3] 楊立英，李成群.n階行列式的計算方法與技巧[J].廣西師范學(xué)院學(xué)報：自然科學(xué)版，2006（3）：98?105.

[4] 屈曉.探討用C語言實現(xiàn)求解行列式[J].電腦知識與技術(shù)，2011（10）：6907?6908.

[5] 黃良斌.用C語言實現(xiàn)解線性方程組的高斯消去法[J].數(shù)學(xué)學(xué)習(xí)與研究，2009（7）：104?105.

[6] 衛(wèi)洪春.COCH圖形的遞歸與非遞歸算法研究[J].計算機與信息技術(shù)，2011（12）：42?46.

子式的乘積之和的變量

for（int j = 0 ； j < n ； j++）{//累加最后一行各元素與其對應(yīng)代數(shù)余子式的乘積

動態(tài)生成n行n列的臨時數(shù)組double **p1，用以保存p 中的元素

將n階行列式p的各元素保存在n階行列式p1的對應(yīng)元素中

保存元素p1[n-1][j]的腳標之和至變量pt

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

將ptd所在列右側(cè)的各列元素依次向左移動一列。

動態(tài)生成（n-1）階行列式double **tem

將行列式p1左上角的（n-1）階行列式轉(zhuǎn)存至tem

釋放數(shù)組p1

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

//累加p[n-1][j]與其代數(shù)余子式之積

釋放數(shù)組tem

}

返回該行列式的值sum

}

采用代數(shù)余子式計算行列式，思路清晰，計算簡單，是計算低階行列式的有效方法。

2.2 行列式的基本性質(zhì)

根據(jù)第2.1節(jié)的代數(shù)余子式法，若能利用行列式的性質(zhì)1、性質(zhì)2將n階行列式A（見圖2）化簡為最后一列元素中除ann≠0（若存在），而該列其余元素均為零的形式（見圖3），則可大大減少計算量。此時行列式的值是ann*A（n-1）（n-1），此式仍具有遞歸函數(shù)的特點。算法設(shè)計如算法2所述。

圖2 n階行列式

圖3 變換后的第n列

算法2：

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

若階數(shù)n=1，返回p[0][0]

double result = 1.0； //記錄行列式中行交換的次數(shù)，每交換

一次result = result*（-1）

bool flag = false

//設(shè)置行列式最右邊列中是否存在某個元素不為0

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

若第i行最右邊的元素不等于0，則{

flag = true；

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

交換第i行與第n-1行對應(yīng)的所有元素 進行一次行變換： result *= -1.0；

}

break；

}

}

if（！flag） return 0； //行列式最右側(cè)列的所有元素全為0，則行列式的值為0

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

P[i][n?1]按規(guī)則變換為0（i從0到n-2）

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

計算用p[n-1][n-1]將p[i][n-1]變?yōu)?的比例因子t=p[i][n-1]/p[n-1][n-1]

將第n-1行的各個元素乘以-t，加到第i行的對應(yīng)元素上（注：行列式的值不變，此時行列式具有圖3的形式）。

}

}

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

}

以上兩種算法均采用遞歸思想完成計算[4?6]。對于算法2，可以非常方便地轉(zhuǎn)換為非遞歸算法。兩種算法的運算結(jié)果如圖4所述。

圖4 兩種算法的結(jié)果

3 算法比較

3.1 精度分析

上述兩種算法均可計算n階行列式的值。算法1中，由于運算過程中只有加減法和乘法運算，除非溢出，否則，計算結(jié)果沒有精度損失。算法2中，由于施行了行變換，除了加、減、乘法運算外，還涉及除法運算，因此在計算中有精度損失。

3.2 效率分析

算法2在執(zhí)行過程中，由于所有的運算數(shù)據(jù)均在二維數(shù)組p中，不需要額外的空間開銷。對于n階行列式，其遞歸調(diào)用的次數(shù)為n，適合計算較高階的行列式。實驗表明，在VC 6.0環(huán)境下，若行列式的元素值在[0，9]間，最高可計算252階的行列式（見圖5）。

圖5 算法2所示的高階行列式運算結(jié)果

對于算法1，利用代數(shù)余子式完成計算的過程中，需開辟大量的額外空間，并且大量的內(nèi)存空間只有在相應(yīng)的遞歸調(diào)用結(jié)束后，才能被釋放。

采用算法1，對于n階行列式A，需進行大量的遞歸調(diào)用。對于n階行列式A，設(shè)遞歸調(diào)用的總次數(shù)為an。通過分析，所需完成的遞歸調(diào)用次數(shù)可用數(shù)列an=n·an-1+1 （其中a1=1）進行計算。[an=n?an-1+1]等式兩邊同除以n！，得：

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

根據(jù)上式，當(dāng)n=6時，a6=1 237；當(dāng)n=10時，a10=6 235 301。行列式每增加一階，則遞歸調(diào)用的次數(shù)增加得特別快，函數(shù)調(diào)用的開銷相當(dāng)大。但對于算法2，當(dāng)n=6時，只需遞歸調(diào)用6次，可見算法2的運算速度相當(dāng)快。

4 結(jié) 語

n元一次線性方程有惟一解的充要條件是相對應(yīng)的n階行列式不為零。本文討論了n階行列式求值的兩種算法，并從精度和執(zhí)行效率上進行了分析。算法1在精度上較好，但計算的階數(shù)有限；運算速度上，算法2遠遠高于算法1。因此，若求解低階線性方程組，且要求的計算精度較高，可采用算法1；若求解高階線性方程組，例如，對于測量平差中需要求解高階線性方程組時，可采用算法2。兩種算法計算結(jié)果都很穩(wěn)定，但算法1較算法2更穩(wěn)定，算法2的運算速度遠遠快于算法1。這兩種算法可根據(jù)實際情況選用。

參考文獻

[1] 張新功.行列式的計算方法探討[J].重慶師范大學(xué)學(xué)報：自然科學(xué)版，2011（7）：88?92.

[2] 陳云坤，趙平利.用矩陣分塊探求計算高階行列式的新方法[J].貴州大學(xué)學(xué)報：自然科學(xué)版，2005（8）：227?231.

[3] 楊立英，李成群.n階行列式的計算方法與技巧[J].廣西師范學(xué)院學(xué)報：自然科學(xué)版，2006（3）：98?105.

[4] 屈曉.探討用C語言實現(xiàn)求解行列式[J].電腦知識與技術(shù)，2011（10）：6907?6908.

[5] 黃良斌.用C語言實現(xiàn)解線性方程組的高斯消去法[J].數(shù)學(xué)學(xué)習(xí)與研究，2009（7）：104?105.

[6] 衛(wèi)洪春.COCH圖形的遞歸與非遞歸算法研究[J].計算機與信息技術(shù)，2011（12）：42?46.

子式的乘積之和的變量

for（int j = 0 ； j < n ； j++）{//累加最后一行各元素與其對應(yīng)代數(shù)余子式的乘積

動態(tài)生成n行n列的臨時數(shù)組double **p1，用以保存p 中的元素

將n階行列式p的各元素保存在n階行列式p1的對應(yīng)元素中

保存元素p1[n-1][j]的腳標之和至變量pt

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

將ptd所在列右側(cè)的各列元素依次向左移動一列。

動態(tài)生成（n-1）階行列式double **tem

將行列式p1左上角的（n-1）階行列式轉(zhuǎn)存至tem

釋放數(shù)組p1

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

//累加p[n-1][j]與其代數(shù)余子式之積

釋放數(shù)組tem

}

返回該行列式的值sum

}

采用代數(shù)余子式計算行列式，思路清晰，計算簡單，是計算低階行列式的有效方法。

2.2 行列式的基本性質(zhì)

根據(jù)第2.1節(jié)的代數(shù)余子式法，若能利用行列式的性質(zhì)1、性質(zhì)2將n階行列式A（見圖2）化簡為最后一列元素中除ann≠0（若存在），而該列其余元素均為零的形式（見圖3），則可大大減少計算量。此時行列式的值是ann*A（n-1）（n-1），此式仍具有遞歸函數(shù)的特點。算法設(shè)計如算法2所述。

圖2 n階行列式

圖3 變換后的第n列

算法2：

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

若階數(shù)n=1，返回p[0][0]

double result = 1.0； //記錄行列式中行交換的次數(shù)，每交換

一次result = result*（-1）

bool flag = false

//設(shè)置行列式最右邊列中是否存在某個元素不為0

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

若第i行最右邊的元素不等于0，則{

flag = true；

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

交換第i行與第n-1行對應(yīng)的所有元素 進行一次行變換： result *= -1.0；

}

break；

}

}

if（！flag） return 0； //行列式最右側(cè)列的所有元素全為0，則行列式的值為0

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

P[i][n?1]按規(guī)則變換為0（i從0到n-2）

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

計算用p[n-1][n-1]將p[i][n-1]變?yōu)?的比例因子t=p[i][n-1]/p[n-1][n-1]

將第n-1行的各個元素乘以-t，加到第i行的對應(yīng)元素上（注：行列式的值不變，此時行列式具有圖3的形式）。

}

}

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

}

以上兩種算法均采用遞歸思想完成計算[4?6]。對于算法2，可以非常方便地轉(zhuǎn)換為非遞歸算法。兩種算法的運算結(jié)果如圖4所述。

圖4 兩種算法的結(jié)果

3 算法比較

3.1 精度分析

上述兩種算法均可計算n階行列式的值。算法1中，由于運算過程中只有加減法和乘法運算，除非溢出，否則，計算結(jié)果沒有精度損失。算法2中，由于施行了行變換，除了加、減、乘法運算外，還涉及除法運算，因此在計算中有精度損失。

3.2 效率分析

算法2在執(zhí)行過程中，由于所有的運算數(shù)據(jù)均在二維數(shù)組p中，不需要額外的空間開銷。對于n階行列式，其遞歸調(diào)用的次數(shù)為n，適合計算較高階的行列式。實驗表明，在VC 6.0環(huán)境下，若行列式的元素值在[0，9]間，最高可計算252階的行列式（見圖5）。

圖5 算法2所示的高階行列式運算結(jié)果

對于算法1，利用代數(shù)余子式完成計算的過程中，需開辟大量的額外空間，并且大量的內(nèi)存空間只有在相應(yīng)的遞歸調(diào)用結(jié)束后，才能被釋放。

采用算法1，對于n階行列式A，需進行大量的遞歸調(diào)用。對于n階行列式A，設(shè)遞歸調(diào)用的總次數(shù)為an。通過分析，所需完成的遞歸調(diào)用次數(shù)可用數(shù)列an=n·an-1+1 （其中a1=1）進行計算。[an=n?an-1+1]等式兩邊同除以n！，得：

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

根據(jù)上式，當(dāng)n=6時，a6=1 237；當(dāng)n=10時，a10=6 235 301。行列式每增加一階，則遞歸調(diào)用的次數(shù)增加得特別快，函數(shù)調(diào)用的開銷相當(dāng)大。但對于算法2，當(dāng)n=6時，只需遞歸調(diào)用6次，可見算法2的運算速度相當(dāng)快。

4 結(jié) 語

n元一次線性方程有惟一解的充要條件是相對應(yīng)的n階行列式不為零。本文討論了n階行列式求值的兩種算法，并從精度和執(zhí)行效率上進行了分析。算法1在精度上較好，但計算的階數(shù)有限；運算速度上，算法2遠遠高于算法1。因此，若求解低階線性方程組，且要求的計算精度較高，可采用算法1；若求解高階線性方程組，例如，對于測量平差中需要求解高階線性方程組時，可采用算法2。兩種算法計算結(jié)果都很穩(wěn)定，但算法1較算法2更穩(wěn)定，算法2的運算速度遠遠快于算法1。這兩種算法可根據(jù)實際情況選用。

參考文獻

[1] 張新功.行列式的計算方法探討[J].重慶師范大學(xué)學(xué)報：自然科學(xué)版，2011（7）：88?92.

[2] 陳云坤，趙平利.用矩陣分塊探求計算高階行列式的新方法[J].貴州大學(xué)學(xué)報：自然科學(xué)版，2005（8）：227?231.

[3] 楊立英，李成群.n階行列式的計算方法與技巧[J].廣西師范學(xué)院學(xué)報：自然科學(xué)版，2006（3）：98?105.

[4] 屈曉.探討用C語言實現(xiàn)求解行列式[J].電腦知識與技術(shù)，2011（10）：6907?6908.

[5] 黃良斌.用C語言實現(xiàn)解線性方程組的高斯消去法[J].數(shù)學(xué)學(xué)習(xí)與研究，2009（7）：104?105.

[6] 衛(wèi)洪春.COCH圖形的遞歸與非遞歸算法研究[J].計算機與信息技術(shù)，2011（12）：42?46.