修訂單純形法不用儲存完整表格,但每次更換基底後仍須解線性方程。每次都重新分解基底固然可行;乘積形式更新則展示如何重用之前的計算。本節在精確算術下推導公式,說明運算次序,並區分代數上有效的更新與數值上可靠的實作。
換一列等於矩陣相乘
考慮標準形式的極大化問題 ,設 是可逆基底,其基本變量滿足 。假設非基底列 進入基底的第 個位置,先解
定義 19.1.1
(基底替換的 eta 矩陣)
設 是列已排序的可逆基底,列 取代第 個位置的列,而 滿足 。這次替換的 eta 矩陣 是把單位矩陣的第 列換成 所得的矩陣:
其中 是第 個座標向量。 的第 列是 ,即原來的列;第 列是 。因此 恰好是新基底矩陣。
注意 是有序基底中的位置,未必等於離開變量的標號。
常見錯誤
(以離開變量的標號決定 eta 列)
若有序基底為 而 離開,替換發生在位置 ,所以應把單位矩陣的第 2 列換成 。若因離開變量叫 而換掉第 1 列,乘積 便對應另一個基底:它移走 、保留 ,此後的更新都在解錯誤的方程。
定理 19.1.2
(單次更新及其逆運算)
替換後的基底 可逆,當且僅當 。在此條件下,解 的公式為
解 時先取 的 ,再計算
證明
(行列式與兩種 eta 求解)
除第 列外都是標準座標向量;沿第 列展開可得 ,所以 ,而 可逆當且僅當 。在方程 中,第 行是 ,其他行是 ,得到第一組公式。對 ,除第 行外均為 ,第 行則是 ,代入即得第二組公式。由於 ,各步都可逆。
原始可行主元的比率檢驗選取 的行,故主元非零。步長為零仍可產生有效新基底:離開的基本變量可為零,儘管 為正。反之,若在方向分量為零的位置替換,新矩陣奇異,便不是合法主元。
概念視角代數
逆更新就是表格主元運算
解方程的公式說明 也是 eta 矩陣:它是把單位矩陣第 列換成 的矩陣,其中 ,而對 有 。因此 ;把 作用於整個表格 ,就是把第 行除以 ,再從每個第 行減去新第 行的 倍。這正是對進基列(其當前元素為 )所做的表格主元運算。乘積形式儲存的是這些主元運算,而不是表格本身。
一連串更新
由可逆而已有分解的 開始。若連續主元產生 ,則
命題 19.1.3
(以乘積形式基底求解)
設 可逆, 是主元均非零的 eta 矩陣,因此 可逆。
- 解 :先解 ,再按 依次解 ,取 。
- 解轉置方程 :先解 ,再按 依次解 ,最後解 。
若 ,只需解原始基底方程。
證明
(從左邊逐個剝去因子)
每個因子都可逆: 是假設,每個 的行列式等於其非零主元。對普通方程, 即 ,它成立當且僅當 ,其中 是 的唯一解。假設解了 次之後方程變為 。把左邊寫成 ,它成立當且僅當 ,其中 。經過 步後不再剩下因子,得 。
對轉置方程,。同樣的剝除步驟首先遇到 : 成立當且僅當 ,其中 。繼續消去 ,最後剩下 。
證明透視
為何轉置求解要反序
證明只重複一個步驟:方程最左邊的可逆因子可以用一次求解消去,留下形狀相同、少一個因子的方程。非零主元的假設只在這裏使用;若 ,某一步可能無解或有無窮多解。兩種方程唯一的分別在於乘積的轉置法則:轉置會把因子反序,使 變成最左、 變成最右。論證中沒有任何一步讓因子互相越過,所以 eta 矩陣從不需要交換;而每步消去一個因子,論證在恰好 次求解後結束。
對當前基底,解 可計算約化成本 。考慮進入列時,解 ;再配合 ,便得到原始比率檢驗及約化成本檢驗所需數據。每次基本變量改變, 也須更新,舊價格向量一般不再正確。
常見錯誤
(沿用上一個價格向量)
主元之後, 第 個位置的成本改變了,舊的 不再滿足 。在下面的算例中,第一次更新後基底的價格是 ;把它用於第二個基底 ,得到 ,而不是 。必須用更新後的 重做轉置求解。
算例
例題 19.1.4
(由單位基底開始的兩次替換)
令 、。首先讓 進入位置 1。方向 ,候選比率為 及 ,因此位置 1 離開。新的基本向量是 ,且
再讓 進入。解 得 ;比率分別為 及 ,所以位置 2 離開。於是
新基本向量為 :原第一個基本值減去 ,進入變量的值則為 2。亦可先解 ,再解 ,得到同一結果。直接相乘可核對 。
例題 19.1.5
(以反序轉置求解計算價格)
沿用 ,並設基本成本為 。轉置求解先由 得 、,即 。再解 ,即 、,得 。直接計算亦有 。
假如兩個原單位列的成本均為零,其約化成本都是 ;若沒有其他列,原始可行性及非正約化成本便證明最大值為 。以此成本計算,兩次指定進入列在各自起始基底的約化成本確為正:首次為 3,第一次主元後第二列為 ,其中 是 的解。
反例模式
次序錯誤的更新
對同樣兩個因子,若先把 、再把 作用於 ,得到 ,不是 。用 相乘得到 ,亦不是 。每次單獨求解都正確,也不能因此任意交換矩陣逆的次序。
下一個算例專門處理比率檢驗的邊界情況:方向分量為正而步長為零的主元。
例題 19.1.6
(步長為零而更新仍可逆)
取 、,並讓 進入,故 。候選比率為 及 ,位置 1 以零步長離開。eta 矩陣就是上面的 ,;解 得 、。基底改變了,基本值卻沒有改變,而這個更新是有效的。
改為替換位置 2 在代數上也合法,因為 ,但這忽略了比率檢驗。取 ,解 得 、。新基底可逆卻不可行。非零主元保證得到基底;保持可行性的是比率檢驗。
計算與限制
一個 eta 更新只需儲存主元位置及方向;套用它的工作量與所儲存的非零項數及一次主元運算成正比。方向稀疏時可節省計算,但乘法或求解可能產生填入,過長的更新鏈也會增加工作及儲存。實務中會定期重新分解當前基底,然後丟棄舊更新鏈。適當頻率取決於稀疏性、硬件及數值表現,本節並未證明一個適用所有問題的固定門檻。
公式需要除以 。精確算術下極小的非零主元仍合法,浮點計算時卻可能放大誤差。應檢查殘差 及 ,並在數值軟件中採用合適的縮放、穩定性控制及重新分解。若基底病態,小殘差本身不保證小的前向誤差。精確約化成本的符號和有限主元論證不會自動保留於四捨五入運算;嚴格證書需要另行證明誤差界。
練習
快速檢查
(三階單位矩陣的第 2 列換成 ,所得矩陣為 。分別解 和 。)
以 、 套用更新定理的兩組公式。
解答 · 答案
第一組公式給 、、。轉置方程有 、,以及 。直接代入可核對兩個答案。
快速檢查
(在兩次主元的例子中,第三列為 ,成本為 4。求基底 的方向及約化成本;它可否作為改進極大值的進入列?)
使用已在 算出的價格 。
解答 · 答案
解 得 ,因為 、。因 ,約化成本是 ;從零增加這個變量不能改進當前極大值。
快速檢查
(若 ,能否把可逆基底的第 列換成 而得到另一基底?不用比率檢驗解釋。)
計算替換後矩陣的行列式。
解答 · 答案
不能。替換結果為 ,行列式是 ,故各列線性相關。即使不討論原始比率檢驗,非零主元仍是必要的代數條件。
快速檢查
(求解器把顯示的殘差四捨五入至小數點後六位而得到零,這能證明計算出的基本向量完全準確嗎?)
把顯示數值的捨入與基底的條件數分開考慮。
解答 · 答案
不能。未四捨五入的殘差可能非零。即使殘差確實很小,病態基底也可造成顯著前向誤差。必須控制逆矩陣的作用和捨入誤差,才能把殘差轉成前向誤差界。