本文的閱讀等級:初級
令 為一個 階矩陣。LU 分解是指將 表示為兩個 階三角矩陣的乘積
,
其中 是下三角矩陣, 是上三角矩陣。見下例,
。
LU 分解的本質是高斯消去法的一種表達形式,矩陣 記錄消去法化簡 的過程,矩陣 則儲存化簡結果 (見“高斯消去法”)。LU 分解的外表看似平淡無奇,但它可以用來解線性方程,逆矩陣與計算行列式,堪稱是最具實用價值的矩陣分解式之一。
高斯消去法
我用一個例子說明如何從高斯消去法推演 LU 分解。考慮底下的線性方程 求解問題:
。
高斯消去法應用於求解線性方程的基本想法十分簡單。在保證不破壞解集合的前提下,運用下述基本列運算 (elementary row operation) 將增廣矩陣 化簡至三角矩陣 (在台灣,橫向稱為列,縱向稱為行。在中國大陸,橫向稱為行,縱向稱為列。):
- 交換:將列 與列 對調,以符號表示為
;
- 伸縮:列 通乘非零常數 ,
;
- 取代:將列 通乘非零常數 的結果加進列 ,
。
取代是主要的化簡工具。列取代運算的目的在消去矩陣的 元,因此乘數 必須滿足 ,如下所示:
。
若 ,我們稱 為軸元 (pivot),乘數等於被消去元除以軸元,。下面僅寫出係數矩陣 的消去過程:
。
令 為列運算最後得到的上三角矩陣, 的主對角元 ,, 即為消去過程所使用的軸元。如果一個 階方陣有完整的 個軸元,亦即 的主對角元皆不為零,則 稱為非奇異 (nonsingular) 矩陣,即可逆 (invertible) 矩陣 (因為線性方程 恆有解)。
LU 分解
高斯消去法可以通過一連串的矩陣乘法來實現。每一個基本列運算等同於左乘一個基本矩陣 (見“特殊矩陣(10):基本矩陣”),而對應列取代的基本矩陣 的 元即為 。上例中,基本矩陣依序是
。
消去程序可用下列矩陣乘法表示:
。
基本矩陣 都是可逆的,且其逆矩陣也是基本矩陣,寫出
,
其中 是下三角矩陣,計算得到
仔細觀察 矩陣可發現一個奇特的現象: 的主對角線下的三個元剛好等於列取代運算的乘數 ,。這不是巧合,而是必然成立。為了保有這個優美的性質,我們決定對 矩陣加入一項新的限制: 的主對角元必須都是 ,稱為單位下三角矩陣 (unitriangular matrix)。利用基本矩陣性質,不難證明單位下三角矩陣的逆矩陣也是一個單位下三角矩陣,同理,單位上三角矩陣的逆矩陣也是一個單位上三角矩陣。
前例 LU 分解的主要結果整理於下。若 是一個 階可逆矩陣且 ,則單位下三角矩陣 和上三角矩陣 具有以下性質:
- 對於 , 且 。
- 是對 執行高斯消去法所得到的結果。
- 的主對角線下各元 ,,記錄所執行的列取代運算的乘數。
下面證明性質 (3)。為方便說明,考慮三階矩陣的 LU 分解:
。
欲消去 主對角線下方的三個元,同時對等號兩側執行列運算,依序是
如此便將 化簡為單位矩陣 ,等號左邊於是等於 。又對等號右邊的 矩陣進行同樣的列運算,這其實就是消去法的運算步驟,結果當然等於上三角矩陣 ,證得等號左邊 與右邊 相等。
存在性
然而,並非任何可逆矩陣都具有 LU 分解形式,例如,。假若 可以寫為
,
則必有 , 是不可逆的,這與 為可逆矩陣的事實相互矛盾。矩陣 之所以不存在 分解的原因在於 占據了 元,但軸元必須不為零才能產生乘數。根據這項觀察,即知可逆矩陣 的 LU 分解存在條件是:列運算過程中, 不得在軸元位置。萬一碰上零軸元的情況,還是有補救辦法,那就是使用列交換運算設法產生其他非零軸元,不過 LU 分解要修改成 , 是排列矩陣。例如,
關於 演算法介紹,請見“PA=LU 分解”。
在不執行消去法的前提下,底下介紹一個判斷可逆矩陣 是否存在 LU 分解的方法。考慮命題:若 階可逆矩陣 有 LU 分解,則 的所有 階領先主子陣 (leading principal submatrix) 都是可逆的。將 LU 分解以分塊矩陣表示為
,
其中 和 是 階分塊。因為 和 同為三角矩陣且包含非零主對角元,兩者皆是可逆的,故 也是可逆的。上例中,方陣 的領先主子陣
,
和 全都是可逆的。此性質的反向陳述可用來判定 是否有 LU 分解:若 的所有領先主子陣 都是可逆的,則存在 LU 分解。證明採用歸納法。若 ,明顯地,若 是可逆的,, 即為 LU 分解式。假設 階領先主子陣 是可逆的並有 LU 分解 ,將 階領先主子陣 表示為 ,其中 和 是 維向量, 是純量。寫出
,
乘開右項,比較等號兩邊可得
。
上式可解出 ,,,就有 ,其中
。
因為 與 是可逆的,故知 也是可逆的,推論 。歸納得知 有 LU 分解 。
唯一性
如果某甲和某乙各自算出滿足上述三個性質的 LU 分解,他們兩人會得到相同的 LU 分解嗎?也就是說,矩陣 的 LU 分解是唯一的嗎?探索這個問題需要運用一些矩陣代數技巧。我們曉得 LU 分解的 主對角元皆為 ,而 則否,兩者呈現「非對稱性」。因為 不等於零, 可進一步分解為
。
令 ,並重新定義上式最右側矩陣為 ,如此一來, 和 的主對角元皆為 (即單位三角矩陣), 也就可以表示為 ,稱作 LDU 分解,如下例,
利用 LDU 分解很容易證明 LU 分解的唯一性。假設 ,,你只要證明 ,, 即可。考慮關係式
。
已知 和 都是可逆的,上式左乘 ,右乘 ,可得
。
以三階矩陣為例,乘開得到下列矩陣型態:
。
比較等號兩側的主對角元得知 ,再比較非主對角元,確認 ,因此斷定 ,,證得 且 。
應用
最後討論 LU 分解的應用。LU 分解不僅僅只是記錄消去過程,它還有一個非常重要的實際用途:LU 分解具備快速求解線性方程 的良好結構。一旦得到了可逆矩陣 的 LU 分解 ,我們大可把 拋棄,將 改為 ,再令 ,原線性方程等價於兩組三角形系統:
接著使用兩次迭代即可得到解。上例中,先以正向迭代解出 ,
再以反向迭代解出 ,
對於 階矩陣 ,LU 分解耗費的乘法運算量大約是 [1],與高斯消去法相同。這個數字其實不算太糟,因為兩個 階方陣相乘就使用了 次運算。另外,正向迭代或反向迭代的運算量都只有 ,遠比 LU 分解來的少。所以,如果只要解出單一線性系統 ,直接用消去法化簡增廣矩陣 和 LU 分解的兩段式解法兩者之間並沒有多大差別,但如果稍後還要解多個係數矩陣相同但常數向量改變的系統 ,LU 分解便能夠派上用場。舉例來說,LU 分解可以用來計算逆矩陣 。將矩陣方程 看成三個線性方程:
,
解出的未知向量 ,, 就是逆矩陣 的三個行向量。
LU 分解還可以用來計算 階行列式。根據矩陣乘積的行列式可乘公式
,
三角矩陣的行列式等於主對角元乘積,因此 ,推論
。
方陣 的行列式即為消去法所得到的上三角矩陣 主對角元之積 (關於其他行列式計算方法的介紹,請見“Chiò 演算法──另類行列式計算法”)。
註解
[1] 引用來源 Gilbert Strang, Introduction to Linear Algebra, fourth edition, Wellesley Cambridge Press, pp 99, 2009.
請問老師,有其他比較快判斷是否可以LU分解的方法嗎? 還是只有軸元為零時不可LU分解?
因為在LU解線性方程那邊,有個有趣的事情: “A要能LU分解”! 為了判斷能不能分解,做完啦啦喳喳運算確認後再來解線性方程AX=b,那直接解線性方程不是比較快?而且有點多此一舉的感覺欸~
答案在第一段末:
LU 分解的本質是高斯消去法的一種表達形式, 矩陣記錄消去法化簡 矩陣的過程,而 矩陣則儲存化簡結果。
而高斯消去法的目的即在解線性方程,那些啦啦喳喳運算是免不掉的。
很精彩的解析,非常感謝!
另外好像有幾處筆誤:
比如:「交換:將列 i 和列 j 對調,以符號表示為」
應該是:
「交換:將行 i 和行 j 對調,以符號表示為」
謝謝。你說的筆誤是個誤會。在台灣,column稱為行,row稱為列。大陸的用法恰巧相反,見
原來是這樣子!又科普了,再次感謝!
我媽問我說為什麼跪著看電腦 真的太神了
快速又不太會發生計算錯誤,謝謝老師~~
HAHA, 我看这个 “行“”列”有些不对劲,原来是大陆和台湾的习惯问题
老师您好,您的文章非常简明扼要,易读,我看了以后马上就明白了。就是有一个地方,因为我是学计算机的所以知道,很乐意和您分享,两个矩阵相乘是可以做到比n^3更低的复杂度的,比如施特拉森演算法 https://zh.wikipedia.org/wiki/%E6%96%BD%E7%89%B9%E6%8B%89%E6%A3%AE%E6%BC%94%E7%AE%97%E6%B3%95
祝您工作愉快。
謝謝分享。我也是學了線性代數多年以後才知這個算法,:
教授您好,存在性證明的倒數第五行是否漏掉了”d-“?
謝謝指正。
另有一處不太能理解,存在性證明的倒數第八行,不就在還沒證明出來的情況下就假設存在LU分解了嗎?因為老師直接寫出了LU分解式。謝謝老師!
這是數學歸納法。假定有LU分解,然後證明有LU分解。
老师您好:
首先非常感谢您花费时间心血建立的这样一个博客,实在获益良多。
然后在读到这一章的时候,对LU分解的存在性有一点疑问:在维基百科中,其对存在性条件的表述为“实际上,如果一个秩为k的矩阵的前k个顺序主子式不为零,那么它就可以进行LU分解,但反之则不然。”
似乎这个条件并一定要求A为可逆矩阵(而在您的文章中,存在性的证明是对于“下面補充一個在不執行消去法的前提下,可逆矩陣 A 是否存在 LU 分解的判斷方法。”)。
于是想请问一下到底A是否要为可逆矩阵呢?
谢谢!
我觉得A不需要是可逆矩阵,LU分解的条件是A若为n阶矩阵,A的1,2,…,n-1阶顺序主子式不为0。如果这样的矩阵A的n阶主子式,即行列式为0,那么它是不可逆的,但是可以LU分解。不知道这样理解对不对
十分感謝教授耐心細緻的講解;
也給出了一些暖心的細節;
謝謝教授