推 vaakaa :推詳細解說 12/15 05:31
推 candy88257 :感謝!! 12/21 20:56
※ 引述《candy88257 (阿泰斯)》之銘言：
: ※ [本文轉錄自 Mathematica 看板 #1GnQhY8g ]
: 作者: candy88257 (阿泰斯) 看板: Mathematica
: 標題: [問題] 高階矩陣Det怎怪怪的?
: 時間: Mon Dec 10 17:26:56 2012
: 矩陣是12*12的
: 太大了，直接上傳圖檔: http://tinyurl.com/atuf86r
: 以下是Det出來的結果...
: http://tinyurl.com/agv2dwl
: 怎會這樣?
: 矩陣Det出來會是兩多項式相除嘛!?
: 而且12*12矩陣Det怎會變成好幾百次方的多項式?
: 還是說高階矩陣要用啥方法Det比較好!?
: 求高手解惑!!
: 感謝!!
這個例子可能是遇到軟體演算法上的瓶頸了
在計算行列式時，雖然使用直接展開的方式
是不會出現有理式 (兩多項式相除)
但若將行列式的算式直接展開，其演算法的複雜度為 O(n!)，相當耗時
以您所提的 12x12 矩陣而言，若直接展開行列式算式
則要計算 479001600 個多項式的和
而且這 479001600 個多項式，每個均由 12 個小多項式相乘
所以，在軟體的實作上，不會直接將行列式的算式直接展開
而是會利用類似高斯消去法的方式，以降低計算上的複雜度
但由於使用高斯消去法的計算過程中，一定會有兩數相除的運算
所以以原問題中的 12x12 矩陣而言，在過程中一定會出現多項式相除的項
雖然這些式子要組合成行列式時，最後分母的多項式會被消乾淨
但是，以軟體的計算而言，由於過程中已經累積出太大的多項式
(原問題中的好幾百次方的多項式)
最後要組合成行列式時，軟體也不曉得該如何對分子分母作約分
所以就保留了兩個好幾百次方的多項式相除形式作為計算結果
我舉 3x3 矩陣為例子，說明這個討厭的分母是怎麼出現的
[ a b c ]
det [ d e f ]
[ g h i ]
[ a b c ]
[ ]
[ ae-bd af-cd ]
[ 0 ------- ------- ]
= det [ a a ]
[ ]
[ ah-bg ai-cg ]
[ 0 ------- ------- ]
[ a a ]
[ a b c ]
[ ]
[ ae-bd af-cd ]
[ 0 ------- ------- ]
= det [ a a ]
[ ]
[ a[(ae-bd)(ai-cg) - (af-cd)(ah-bg)] ]
[ 0 0 ------------------------------------ ]
[ a^2 (ae-bd) ]
ae-bd a[(ae-bd)(ai-cg) - (af-cd)(ah-bg)]
= a * ------- * ------------------------------------
a a^2 (ae-bd)
雖然上式展開的結果為大家所熟知的 aei + bfg + cdh - afh - bdi - ceg
但 a, b, c, d, e, f, g, h, i 若為多項式
而且最後軟體若對行列式的結果不曉得該如何約分時
那最後分母的 a^3 (ae-bd) 就會被保留下來
(大家有耐性的話，可以試著以相同的方式計算 4x4 矩陣，
更可以體會累積在分母的多項式是如何惱人)
對於這個問題，其實我們已知結果必定為 (12階) 多項式
所以還有一個方式可以處理
就是，直接將軟體所計算的兩個好幾百階的多項式，直接相除
取相除後的商式，丟掉餘式
(餘式的產生為計算過程中，由於浮點運算會有些許的 rounding error
多次計算誤差累積後所產生的)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 122.116.84.29
※ 編輯: mgtsai 來自: 122.116.84.29 (12/14 17:22)