部分選主元避免除以當前列中比可用元素更小的數,這有助於控制乘子,但消元過程中的每次除法、乘法和減法也都會捨入。計算所得的因子究竟精確分解了甚麼?我們將證明它們精確分解了一個鄰近的已置換矩陣,並說明中間元素增長如何進入誤差界。這是關於因子分解的結論;求解三角方程組還會產生額外算術誤差。
計算算法與假設
設 ,,其元素是已表示的浮點數。在第 列,部分選主元選擇當前列中絕對值最大的活動行,將它與第 行交換,再進行更新
這裏 是第 步行交換後的活動矩陣,。行交換是精確置換。交換行時,這些行此前儲存的乘子也要交換;否則最終的 無法記錄相同的行歷史。令 為各次交換的乘積, 為得到的單位下三角乘子矩陣, 為計算所得主元行組成的上三角矩陣。
假設 (1) 中每次除法、乘法和減法都滿足標準相對模型
且每個計算出的主元非零。排除溢出、下溢或特殊值使 (2) 失效的運算。我們分析實際捨入運行時的主元選擇,而不是另一趟精確算術運行的主元。假設 ,記 。融合乘減並非 (1) 中分別捨入的算法。
定理 2.3.1
(鄰近矩陣的因子分解)
存在實矩陣 ,使得
絕對值和不等號均逐元素理解,右側為普通矩陣乘法。特別地,此界依賴計算所得因子,而不只依賴原始元素。這是對已置換輸入矩陣的向後誤差,尚不是對 最終解的誤差界。
證明
(沿交換和捨入更新追蹤一行)
對固定的最終行 ,沿精確交換向前追溯它的來源。在每次交換時,先前儲存的乘子也隨行交換,保證 對應同一條行歷史。一旦第 行成為主元行,其計算元素 便被固定。因此可以追蹤每個最終元素在該行成為主元之前的更新,而毋須假設物理行號始終不變。
暫時省略指標,(1) 中一次更新具有形式
整理得 。同樣,計算除法給出 。反覆代入,可將 表示為 各項之和,每項乘上若干捨入因子。對於上三角元素,最終項是儲存的 ,其中 ;對於對角線下方元素,最終項是計算出的乘子與主元之積,帶一個除法捨入因子的倒數。先前的行交換已由 P 和 L 記錄。
每項至多包含 個因子:其分子至多有一個乘積捨入因子 ,其餘是先前減法或最終除法產生的倒數 。因此,其合併因子 滿足
下界使用 ;上界使用 和 。因此,對非零的三角乘積項,可寫 ,其中 。從 中減去此式,再用三角不等式即得 (3)。這裏不假設捨入誤差互相獨立。
證明透視
捨入記賬依賴甚麼
證明是帶有兩個容易忽略之約定的記賬。第一,已儲存的乘子與其所在的行一起交換,所以把最終的某一行沿交換逆向追蹤時,總是遇到同一串 和 ;否則 (3) 比較的就是 與錯誤的行歷史。第二,每一項至多帶有 個捨入因子,乘積中至多一個 ,其餘是倒數 ,所以單一常數 同時涵蓋兩個方向;假設 正是保證 為正的條件。論證沒有把誤差當作隨機量,所以 (3) 是針對實際捨入後的主元選擇的最壞情形保證。證明止於因子分解,並不涉及三角求解。
增長對估計的影響
定義 2.3.2
(增長因子)
令 。實際計算過程的增長因子 是所有計算出的活動矩陣或主元行中元素的最大絕對值除以 。
它是實際計算過程的性質,而不是精確算術的性質。
推論 2.3.3
(後向誤差的增長因子形式)
在上述假設下,(3) 中的矩陣 滿足
證明
(估計乘子與主元行)
部分選主元選擇當前列絕對值最大的元素,所以每次除法中的精確商的絕對值不超過一,由 (2) 得 。由 的定義,每個 。 的每個元素是至多 個乘積之和,每個乘積至多為 ,於是由 (3) 得 (4)。
該界可能偏保守,而且增長依賴主元路徑。它說明較大的中間元素為甚麼可能削弱誤差保證;它不表示大增長一定造成大的實際誤差。要把小向後誤差轉化為小向前誤差,還需要問題本身有良好的條件性。
常見錯誤
(三種不同的誤差不能混為一談)
式 (3) 討論計算所得因子對鄰近矩陣的表示有多準確。計算三角方程組也會捨入,所以單憑 (3) 不能認證最終解。最後,即使精確求解了一個鄰近系統,若原系統病態,其解仍可能與原解相差很大。因子分解誤差、求解誤差和問題敏感性是不同的問題。
例子與敏感性反例
例題 2.3.4
(精確算術下的行交換)
對 ,第一個主元為 2,所以
在二進制算術中這些運算精確,故 ;計算出的增長因子為 。定理給出上界,不表示每次運行都會達到它。
例題 2.3.5
(一個被捨入的乘子)
取 。第 列最大的元素是 ,所以 。計算出的乘子為 ,。乘積 是精確的,所以 ,。於是 。由於 且 ,
只有第二行被擾動。(3) 右端在 位置為 ,大於 ,所以該界成立且有餘地。
例題 2.3.6
(部分選主元下的元素增長)
設 ,故 。第 列的元素絕對值都是 ,取第一個作主元。乘子為 ,活動矩陣變成 。其第一列的兩個元素絕對值又都是 ;取第一個作主元,乘子為 ,最後一個元素變成 。因此 、。所有運算都精確,所以 ,但 (),(4) 比 時弱四倍。這個並列的情形說明絕對值相等的元素也可作主元,而且即使沒有乘子的絕對值超過一,也可能出現很大的增長。
反例模式
後向誤差很小而前向誤差很大
一個誘人的說法是:後向誤差很小就保證解準確。令 、,;精確解為 。向量 滿足 ,所以它精確求解了一個數據與給定數據只相差一個隨 趨於零的擾動的方程組。然而 ,相對前向誤差為 。即使因子分解完全精確,也不能使一個接近奇異的問題變得不敏感;修正辦法是把後向誤差與條件數結合起來。此例討論輸入擾動;它並不聲稱 (3) 中的分解一定產生該擾動。
練習與解答
快速檢查
(為甚麼後來的行交換必須連同此前儲存的乘子一起進行?)
想想每一行的歷史。
解答 · 答案
乘子屬於前幾列中的行歷史。不交換它們會破壞最終置換與儲存的 之間的對應關係。
快速檢查
(式 (3) 的 和 有甚麼區別?)
把 (3) 左乘 。
解答 · 答案
擾動的是 ;將 (3) 左乘 ,可知 是 中對 的相應擾動。
快速檢查
(若 ,算法做甚麼,因子分解誤差是多少?)
數一數除法和更新。
解答 · 答案
沒有除法或尾塊更新:對已儲存輸入,、、。
快速檢查
(僅有 是否保證每個右端項的計算解都準確?解釋理由。)
回想三種誤差。
解答 · 答案
不保證。(4) 可以界定因子分解誤差,但三角求解也會捨入,系統還可能敏感;接近奇異的例子說明了求解捨入之前就有敏感性。