線性代數/主題：高斯消元法的速度

線性代數
← 主題：分析網路	主題：高斯消元法的速度	向量空間 →

我們在這本書中使用高斯消元法來解線性方程組，因為它易於理解，容易證明其正確性，並且速度快。所謂速度快是指，在我們所做的手工計算中，我們只用幾步就得到了答案，只用了幾分鐘。然而，在實踐中解決線性方程組的科學家和工程師必須使用一種足夠快的演算法來處理大型系統，例如 1000 個方程，10,000 個方程，甚至 100,000 個方程。這些系統是在計算機上解決的，因此機器的速度有幫助，但儘管如此，所用演算法的速度仍然是一個主要考慮因素，有時是限制哪些問題可以解決的因素。

演算法的速度通常透過找到解決問題所需的時間隨著輸入資料集中大小的增長而增長的方式來衡量。也就是說，如果我們將輸入資料的規模擴大十倍，例如從 1000 個方程的系統擴大到 10,000 個方程的系統，或者從 10,000 個擴大到 100,000 個，演算法將花費多少時間？所花的時間是增加了十倍，還是一百倍，還是一千倍？演算法所花的時間是否與資料集的大小成正比，還是與該大小的平方成正比，還是與該大小的立方成正比等等？

這是一個在 FORTRAN 計算機語言中實現的高斯消元法程式碼片段。線性方程組的係數儲存在 $N\!\times \!N$ 陣列 A 中，常數儲存在 $N\!\times \!1$ 陣列 B 中。對於從 $1$ 到 $N$ 的每個 ROW，該程式已經找到了主元元素 $A(ROW,COL)$ 。現在它將進行主元變換。

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

(此程式碼片段僅用於說明，並不完整。例如，參見後面關於高斯消元法精度的主題。儘管如此，此片段對於我們的目的已經足夠了，因為對完成版本（包括所有測試和子案例）的分析更復雜，但本質上得到相同的結果。)

PIVINV=1./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
B(J)=B(J)-PIVINV*B(ROW)
10 CONTINUE

最外層的迴圈（未顯示）遍歷 $N-1$ 行。對於這些行中的每一行，顯示的迴圈對 A 中位於主元元素下方和右邊的條目（以及 B 中的條目，但為了簡化分析，我們將不計算這些操作——參見練習）執行算術運算。我們將假設主元是在通常的位置找到的，即 $COL=ROW$ （如上所述，對一般情況的分析更復雜，但本質上得到相同的結果）。這意味著有 $(N-ROW)^{2}$ 個條目需要進行算術運算。平均而言，ROW 將是 $N/2$ 。因此，我們估計上面的巢狀迴圈將執行類似 $(N/2)^{2}$ 次，也就是說，將在與方程數量的平方成正比的時間內執行。考慮到未顯示的最外層迴圈，我們估計該演算法的執行時間與方程數量的立方成正比。

執行時間與資料集大小成正比的演算法速度很快，執行時間與資料集大小的平方成正比的演算法速度較慢，但通常相當可用，執行時間與資料集大小的立方成正比的演算法速度仍然相當合理。

這些速度估計是瞭解演算法平均執行速度的良好方法。然而，也有一些特殊情況，在這些情況下，上面的高斯消元法程式碼執行得特別快，因此可能存在一些關於問題的因素，使其特別適合這種型別的解決方案。

在實踐中，在計算機代數系統或標準包中找到的程式碼實現了高斯消元法的變體，稱為三角分解。要說明這種方法需要矩陣代數的語言，我們將直到第三章才會看到它。儘管如此，上面的程式碼在概念上非常接近通常在應用程式中使用的程式碼。

求解線性方程組所需執行時間已有一些理論上的加速方法。除了高斯消元法以外，還發明瞭其他演算法，其執行時間不是與資料集大小的立方成正比，而是與大約 $2.7$ 次方成正比（這仍然是正在積極研究的領域，因此隨著時間的推移，該指數可能會略微下降）。然而，這些理論上的改進尚未得到廣泛應用，部分原因是這些新方法需要相當大的資料集才能超過高斯消元法（儘管它們在超大型資料集上會勝過高斯消元法，但存在一些啟動開銷，使其無法在實踐中已經解決的系統上更快地執行）。

練習

問題 1

計算機系統允許生成隨機數（當然，這些只是偽隨機數，因為它們是由某種演算法生成的，但所得到的數字序列通過了許多合理的統計檢驗，表明其具有明顯的隨機性）。

用隨機數填充一個 $5\!\times \!5$ 陣列（例如，在 $[0..1)$ 範圍內）。應用高斯消元法以檢視它是否為奇異矩陣。重複該實驗十次。奇異矩陣是常見還是罕見（在這個意義上）？
計時計算機求解十個 $5\!\times \!5$ 隨機數陣列的時間。找到平均時間。（請注意，某些系統可以很快地被發現是奇異的，例如，如果第一行等於第二行。根據第一部分，您是否期望奇異系統在您的平均值中扮演重要角色？
對 $15\!\times \!15$ 陣列重複上一項。
對 $25\!\times \!25$ 陣列重複上一項。
對 $35\!\times \!35$ 陣列重複上一項。
繪製輸入大小與平均時間的關係圖。