線性代數/主題：計算行列式的速度

線性代數
← 主題：克萊姆法則	主題：計算行列式的速度	主題：射影幾何 →

用於計算行列式的排列展開公式對於證明定理很有用，但使用行操作的方法對於找到大型矩陣的行列式要好得多。我們可以透過考慮計算機演算法設計人員所使用的算術運算次數來使該陳述精確。

演算法的速度是透過找到計算機在輸入資料集大小增長時所花費的時間如何增長來衡量的。例如，如果我們將輸入資料集的大小增加十倍，從一個 $1000$ 行矩陣到一個 $10,000$ 行矩陣，或者從 $10,000$ 到 $100,000$ ？演算法所花費的時間是增加了十倍，還是一百倍，還是一千倍？也就是說，演算法所花費的時間與資料集的大小成正比，還是與該大小的平方成正比，還是與該大小的立方成正比等等？

回想一下用於行列式的排列展開公式。

{\begin{array}{rl}{\begin{vmatrix}t_{1,1}&t_{1,2}&\ldots &t_{1,n}\\t_{2,1}&t_{2,2}&\ldots &t_{2,n}\\&\vdots \\t_{n,1}&t_{n,2}&\ldots &t_{n,n}\end{vmatrix}}&=\displaystyle \sum _{{\text{permutations }}\phi }\!\!\!\!t_{1,\phi (1)}t_{2,\phi (2)}\cdots t_{n,\phi (n)}\left|P_{\phi }\right|\\&={\begin{aligned}&t_{1,\phi _{1}(1)}\cdot t_{2,\phi _{1}(2)}\cdots t_{n,\phi _{1}(n)}\left|P_{\phi _{1}}\right|\\&\quad +t_{1,\phi _{2}(1)}\cdot t_{2,\phi _{2}(2)}\cdots t_{n,\phi _{2}(n)}\left|P_{\phi _{2}}\right|\\&\quad \vdots \\&\quad +t_{1,\phi _{k}(1)}\cdot t_{2,\phi _{k}(2)}\cdots t_{n,\phi _{k}(n)}\left|P_{\phi _{k}}\right|\end{aligned}}\end{array}}

有 $n!=n\cdot (n-1)\cdot (n-2)\cdots 2\cdot 1$ 個不同的 $n$ -排列。對於任何大小的數字 $n$ ，這是一個很大的值；例如，即使 $n$ 只有 $10$ ，那麼展開式有 $10!=3,628,800$ 項，所有這些項都是透過將 $n$ 個條目相乘得到的。這是一個非常大的乘法次數（例如，(Knuth 1988) 認為 $10!$ 步是一個粗略的實際計算極限）。階乘函式的增長速度快於平方函式。它比立方函式、四次方函式或任何多項式函式的增長速度都快。（我們可以透過注意到階乘函式中前兩個因子的乘積為 $n\cdot (n-1)$ ，對於較大的 $n$ ，它近似於 $n^{2}$ ，然後乘以更多因子會使它變得更大。同樣的論點適用於立方函式等等。）因此，一個被程式設計為使用排列展開公式的計算機，它執行的操作次數大於或等於行數的階乘，隨著其輸入資料集的增長，將會花費很長時間。

相比之下，行減少方法所花費的時間並沒有那麼快。這段行減少程式碼片段是用 FORTRAN 語言編寫的。矩陣儲存在 $N\!\times \!N$ 陣列 A 中。對於每個 ROW 從 $1$ 到 $N$ ，程式中未顯示的部分已經找到了主元條目 $A(ROW,COL)$ 。現在程式進行行主元操作。

-PIVINV\cdot \rho _{ROW}+\rho _{i}

(這段程式碼片段僅供說明，不完整。但是，分析包括所有測試和子情況的完成版本會更復雜，但最終結論基本相同。)

PIVINV=1.0/A(ROW,COL) DO 10 I=ROW+1, N DO 20 J=I, N A(I,J)=A(I,J)-PIVINV*A(ROW,J) 20 CONTINUE 10 CONTINUE最外層迴圈（未顯示）遍歷 $N-1$ 行。對於每一行，巢狀的 $I$ 和 $J$ 迴圈（如上圖所示）對位於主元條目下方和右側的 A 中的條目執行算術運算。假設主元位於預期位置，即 $COL=ROW$ 。那麼，在主元下方和右側有 $(N-ROW)^{2}$ 個條目。平均而言，ROW 將是 $N/2$ 。因此，我們估計算術運算將執行約 $(N/2)^{2}$ 次，也就是說，其執行時間與方程數量的平方成正比。考慮到未顯示的外迴圈，我們估計算法的執行時間與方程數量的立方成正比。

找到計算行列式的最快演算法是當前研究的主題。已知的演算法在第二和第三次冪之間執行。

這些速度估計有助於我們瞭解演算法的執行速度。執行時間與資料集大小成正比的演算法速度很快，執行時間與資料集大小的平方成正比的演算法速度較慢，但通常非常實用，而執行時間與資料集大小的立方成正比的演算法對於不太大的輸入資料仍然具有合理的執行速度。但是，執行時間（大於或等於）資料集大小的階乘的演算法對於任何可觀大小的輸入都不實用。

除了這裡討論的兩種方法之外，還有其他方法用於計算行列式。這些超出了我們的範圍。儘管如此，這兩種計算行列式方法的對比表明，儘管在原則上它們給出相同的答案，但在實踐中，我們的目標是選擇速度更快的那個。

練習

大多數這些問題都假定可以訪問計算機。

問題 1

計算機系統生成隨機數（當然，這些只是偽隨機數，因為它們是由演算法生成的，但它們通過了隨機性的許多合理統計測試）。

用隨機數填充一個 $5\!\times \!5$ 陣列（例如，在範圍 $[0..1)$ 中）。看看它是否奇異。重複這個實驗幾次。奇異矩陣是常見的嗎還是罕見的嗎（從這個意義上講）？
計時你的計算機代數系統找到十個 $5\!\times \!5$ 隨機數陣列的行列式。找到每個陣列的平均時間。對 $15\!\times \!15$ 陣列、 $25\!\times \!25$ 陣列和 $35\!\times \!35$ 陣列重複上一步。（請注意，當陣列奇異時，有時可以很快地發現它是奇異的，例如，如果第一行等於第二行。根據你對第一步的回答，你認為奇異系統在你的平均值中起著重要作用嗎？
繪製輸入大小與平均時間的關係圖。