消元是一連串可逆的方程變換。LU 分解將變換整理成因子,在右端改變時可重用。主元交換增加了一個細節:計算中途方程的次序可能改變。置換要記錄完整次序,已記錄的乘數則要隨它們所描述的行移動。我們將在精確算術下證明非奇異方陣的分解存在,解釋記錄方式,並確定因子何時唯一。
我們需要的分解
定理 4.2.1
(帶置換的 LU 分解)
設 是域 上的非奇異矩陣,。則存在置換矩陣 、單位下三角矩陣 和上三角矩陣 ,使
定義 4.2.2
(單位下三角與置換矩陣的約定)
「單位」指 的對角項全為 1。對非奇異的 , 的對角項均非零。置換矩陣左乘時重新排列各行。若依時間次序的換行是 ,則 :最後做的操作放在最左邊。我們一律使用此約定。有些書以另一個置換寫成 ,應先核對其約定,而非猜測是否要轉置。
反例模式
沒有 LU 分解的可逆矩陣
斷言:每個非奇異矩陣都可寫成 ,其中 是單位下三角、 是上三角。這是假的。非奇異性對非零主元結論及三角方程求解很重要。奇異矩陣也可能有這種形式的分解,但零主元和非唯一性需要另行處理。即使非奇異,也不保證無須換行: 可逆,但第一主元為零。若不換行,它不可能是單位下三角 與上三角 的乘積: 的第一項必為零,因而 的左下項也為零。
為何能找到非零主元
證明
(每一步都有非零主元)
在第 步開始時,假設第 列的對角線下方已消成零,先前主元均非零。目前矩陣可分塊寫成
其中 是可逆的 上三角矩陣。先前所有操作均可逆,故目前矩陣仍非奇異。其行列式為 ,因此右下塊 非奇異。 的第一列不可能全為零,所以第 列在第 行或其下有非零項;可在這些行之間換行,把它移到主元位置。
對實矩陣,部分選主元法在該列尚可選取的項中選絕對值最大者。上述論證保證所選項非零,且所得乘數的絕對值至多為 1。存在性證明只需要選非零項;它並沒有聲稱部分選主元能消除所有數值困難。選好主元後,從下方各行減去適當倍數的主元行。主元行在較早各列的項為零,故這些操作保持先前的零。經過 步得到上三角矩陣,且主元全非零。最後一步也包括在內:其右下塊是非零純量。
記錄方式背後的不變式
證明
(在換行與消元中維持 )
在第 步開始時,保持 ,其中 的首 個主元下方已消成零,而
右下角單位矩陣表示這些行在目前主元列的乘數尚未記錄。起初 、。假設置換 交換第 行或其下的兩行;相對於已處理的行,它可寫為 。因此
新因子 仍是相同形狀的單位下三角矩陣:已記錄的左下塊變成 ,右下恆等塊則保持不變。所以必須交換 中先前已計算各列的對應行,而尚未處理的對角線上的 1 要留在原位。只交換目前 的行而不移動舊乘數,會破壞不變式。
令 ,其中向量 在第 個位置為零,下方各項是新乘數。消元後矩陣為 。由於 ,有 。因此
乘積 仍是單位下三角矩陣,並把新乘數存入第 列。這逐步證明了不變式,也解釋舊乘數為何要移動:它們屬於已換位置的方程,而不是固定附在原矩陣行號上。
證明透視
為何舊乘數必須跟著移動
不變式就是整個證明:每一步都必須令 保持成立。關鍵一步是把換行 寫成 :用 對 作共軛,會把已處理各列中儲存的乘數連同它們所屬的行一起交換,而尾部的單位塊仍是單位矩陣;若只更新 ,等式便會被破壞。非零主元來自尾部塊 的非奇異性,這是對 的假設起作用之處。消元因子 無害,因為 ,乘上它只是把新乘數寫進第 列。過程在 步後完結,因為最後的尾部塊是一個非零純量。
唯一性究竟說甚麼
定理 4.2.3
(固定置換時的唯一性)
對固定的置換矩陣 ,若 非奇異,且 ,其中 為單位下三角、 為上三角,則 且 。
證明
(既是單位下三角又是上三角的矩陣)
對固定的置換 ,假設 ,其中 均為單位下三角, 均為上三角。因 和 可逆, 亦可逆。重排得
左邊是單位下三角,右邊是上三角。同時具有兩種形狀的矩陣必為對角矩陣,而其對角項都必為 1,所以它是 ,即 、。這並不表示置換唯一:不同有效選主元方式可能得到不同 ,進而得到不同因子。若移除 的單位對角規範,即使固定 ,仍可對兩因子作相反的對角縮放。
這個論證亦解釋非零主元的作用。對非奇異的分解,,因此 每個對角項均非零。若 奇異,唯一性證明所需的逆可能不存在,不能不加新假設便沿用結論。
把分解讀成一連串步驟
等式 可以從兩個方向理解。由 開始,先重新排列行得到 ,再透過消元得到 。反方向看, 重建被消去的線性組合,使 還原重新排列後的各行。 或 本身通常都不是 的行置換;乘積次序很重要。
行列式可提供簡潔的額外檢查。由 ,得 ,而 是對角項的乘積。每次換行改變 的符號,卻不改變 是否奇異。此檢查不能取代矩陣乘積:兩個錯誤因子也可能碰巧有正確的行列式。同樣,某個數值例子的選主元方式不能決定所有輸入矩陣的通用置換;置換記錄的是實際進行的操作。
概念視角算法
分解是對 Schur 補的遞歸
以 表示經過一次交換、使主元 之後的 ,並分塊 。則
由於 ,Schur 補 非奇異,同一步驟可再用於它。乘數 構成 的第一列, 是 的第一行。之後在 內的換行會置換這些已記錄的乘數,正如不變式所要求。
換行後如何求解
由 ,方程 等價於 。先用前代求 ,再用回代求 。重排 的同一個 必須用來重排 。由於 是單位下三角, 的對角項非零,兩個三角方程都有唯一解。若有多個右端,只需分解一次,然後對每個新右端依次置換和求解。
檢查應回到原問題:驗證 ,再計算 。只檢查 雖有幫助,但若沒有核對 是否與實際換行一致,一個始終記錯的置換仍可能被掩蓋。在精確算術中零殘差可驗證數值解;在浮點算術中,小殘差的意義需要進一步分析。
例題
例題 4.2.4
(已存乘數之後才換行)
在 上,對
求分解並解 。
解答。 取第一項 2 為主元。第 2、3 行的乘數為 2、3;相減後分別得 、。第二主元為零,故交換第 2、3 行。它們已存的第一列乘數也須交換,變成 3、2。新第二主元下方的項為零,故最後乘數為零。得到
的各行依次是 、、,正是 。又 ,前代得 。回代得 、、。最後 。若舊乘數 2、3 留在原位置, 的第二、三行便不等於 的相應行。
下面的互動圖逐步重播消元,並在每個操作後重新計算 P、L、U 與 PA − LU,讓你看到只有已記錄的乘數隨所屬的行一起移動時,不變式才能在每次換行後保持成立。
每次換行後 PA = LU 仍成立嗎?
重播帶換行的精確消元。每個操作之後,本圖重新計算 P、L、U(工作矩陣)以及差 PA − LU。換行時,L 中已記錄的乘數也必須一併交換。
步驟 0/4: 開始:P = I,L = I,U = A
| 1 | 1 | 0 | 0 |
|---|---|---|---|
| 2 | 0 | 1 | 0 |
| 3 | 0 | 0 | 1 |
| 1 | 1 | 0 | 0 |
|---|---|---|---|
| 2 | 0 | 1 | 0 |
| 3 | 0 | 0 | 1 |
| 1 | 2 | 1 | 3 |
|---|---|---|---|
| 2 | 4 | 2 | 8 |
| 3 | 6 | 7 | 5 |
* 此操作改變的元素
不變式: PA − LU = 0
- 開始:P = I,L = I,U = A
- 第 1 階段:以主元 2 消去第 2 行;乘數 l21 = 2。
- 第 1 階段:以主元 2 消去第 3 行;乘數 l31 = 3。
- 交換第 2 行與第 3 行(第 2 階段);第 1 至 1 列中已記錄的乘數隨之交換。
- 第 2 階段:以主元 4 消去第 3 行;乘數 l32 = 0。
解 Ax = b
請前進到最後一步,查看前代與回代。
- 操作數
- 0/4
- 換行次數
- 0
- 不變式
- PA − LU = 0
- 狀態
- 完成
第 0/4 步:開始:P = I,L = I,U = A PA − LU = 0
為何必須交換已記錄的乘數
換行前 PA = LU,其中 L = [L₁₁ 0; L₂₁ I]。若 S 交換目前階段及其以下的兩行,則 S·PA = (S L S^T)(S U)。S L S^T 仍是單位下三角矩陣:其已記錄的分塊變為 S₂L₂₁,尾部的單位矩陣不變。
所以已處理各列中的乘數必須隨所屬的行移動。若只交換 U 的行而不動 L,則只要被交換的兩行帶有不同的已記錄乘數,(SP)A ≠ LU。
A 的元素為 −9 至 9 的整數,b 的元素為 −30 至 30 的整數,所有運算都是精確的。只有當規則選中第 k 行以外的行時,第 k 階段才換行。零乘數也會列出。對奇異矩陣,重播在找不到主元處停止。
例題 4.2.5
(必須交換的第一主元)
在 上,設 、。求有主元交換的分解並解方程。
解答。 雖然 ,第一主元卻是零。交換第 1、2 行:
此處 ,置換後右端為 。因 ,所以 ;回代給出 及 ,故 。直接相乘得到 。另一個非奇異矩陣可能有多個有效主元選擇,但對此固定 和單位對角規範,上述論證保證因子唯一。
例題 4.2.6
(部分選主元取絕對值最大的元素)
令 、。第一列中絕對值最大的元素是 ,所以交換兩行:,。乘數是 ,其絕對值不超過一;第二行變成 。因此 、, 的兩行是 與 ,所以 。取 ,前代得 ,回代得 ,再由 得 。驗算:。
常見錯誤與細節
常見錯誤
(只交換 的行而不交換已存的乘數)
在第一個例題中,若把乘數 與 留在原位,則 ,而 的各行為 、、。後兩行都不等於 的對應行 與 。
常見錯誤
(忘記對右端項作置換)
在第二個例題中,若用未置換的 解 ,得 ,再得 。但 ,不是 :這相當於把方程的次序弄錯了來解。
習題
快速檢查
(利用第一個例題中的分解,求 。)
記得 ,且 只是一次換行。
解答 · 答案
,而一次換行的 ,所以 。沿第一行直接作餘因子展開得 。
快速檢查
(對 與 ,求 、、 並解 。)
第一主元為零,所以交換兩行。
解答 · 答案
,,。於是 ,故 ,由 得 。驗算:。
快速檢查
(為甚麼沒有單位下三角的 與上三角的 能滿足 ?)
先比較左上角的元素。
解答 · 答案
的 元素是 ,所以 。 元素是 ,但它必須等於 。這個矛盾正是需要換行的原因。