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

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

關鍵詞： 遞歸程序設計方法； 行列式算法； 運行效率； 線性方程

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