Glophy Zone Backup

第二章、LU分解 PDF 列印 E-mail
作者 曾正男   
2009/04/24, 週五

2.1 高斯消去法與列運算

在二元一次或是三元一次聯立方程式中,我們使用加減消去法來達到變數縮減的目的。因此,我們可以想像對應於處理係數矩陣,將係數矩陣的某一列乘上一個定值,或是加減到另外一列,以及兩列互換等等運算方式,都不會影響到解本身。透過這樣的過程,我們可以有系統的將一個複雜的矩陣變成比較簡單的形式。在更一般性的線性方程組中,我們將這種依序減少變數個數的方法稱為高斯消去法。這個方法雖然已數學家高斯為名,但是最早的文獻卻是出現在中國漢朝的九章算術當中,被記載的時間大約在公元前150年左右。

列運算有三種形式,我們舉個簡單的例子來說明。給定一個三元一次聯立方程組

 http://glophy.com/images/equation/linear2_1/latex-image-1.png

 我們知道,若(x,y,z)是滿足L1的解,那麼我們將L1乘上非零的k 倍,(x,y,z)依舊滿足L1。因為根據等量除法公理,我們總可以將更改過的L1再除上k 還原成原來的式子。例如,我們將L1乘上-3/2變成下列的方程組,並不會對方程式的解造成改變。

 http://glophy.com/images/equation/linear2_1/latex-image-2.png

因此,第一種列運算就是將某一列的方程式乘上一個非零的元素。

第二種列運算是將一式加到或減到另外一式。例如,我們將上面方程組的L2減掉L1來取代原本的L2,亦即L2-L1->L2。我們得到

 http://glophy.com/images/equation/linear2_1/latex-image-3.png

將一列加減到另外一列,這個動作因為也是可以還原的動作,所以,它不會影響到這個方程組的解。若我們合併第一種列運算和第二種列運算,我們知道,將一列乘上一個常數加減到另外一列,這樣的動作不會改變方程組的解。這裡,我們不強調乘上的常數是否等於0的限制,式由於這樣的動作,等於保持原方程組不變,當然不會影響方程組的解。所以,我們可以從原式跳到

 http://glophy.com/images/equation/linear2_1/latex-image-4.png

利用同樣的方法,我們可以將L3也變成只有兩個變數。

 http://glophy.com/images/equation/linear2_1/latex-image-5.png

我們可以反覆利用這種消去的過程來處理L2和L3式,將L3-4L2->L2得到

 http://glophy.com/images/equation/linear2_1/latex-image-6.png

這樣就得到一個從L1保留三個變數到L3只保留一個變數的變數個數遞減的形式。除了先前介紹三種列運算之外,第四種列運算就是將方程式顯示的順序對調。這麼做當然不會影響方程組的解,當然也可以再次透過對調的方式,將方程組回復到原先的形式。我們把這四種運算方式,稱為線性方程組的列運算。

當線性方程組的未知數個數很龐大時,我們會利用計算機來計算方程組的解。這時候有些符號可以被省略。例如,一開始的原式,在計算機裡可以表示成

 http://glophy.com/images/equation/linear2_1/latex-image-7.png

我們把這樣的矩陣表示稱為增廣矩陣。利用列運算,我們可以將此增廣矩陣轉化為一個上三角矩陣(顧名思義,就是矩陣對角線以下的元素皆為0)。

 http://glophy.com/images/equation/linear2_1/latex-image-8.png

就一般人而言,能將線性方程組轉化為這種上三角的形式,就幾乎等於將答案解出來了。很明顯的最下方的式子是一個一元一次方程式,只要將其求解後,依序往上面一個式子做代換,就可以得到下一個一元一次方程式,進而將每一個未知數的解都求出來。

2.2 LU分解

將線性方程組表現成矩陣的好處,在於式子和式子之間的列運算,都可以用矩陣的乘法來表示。這樣,就不必繁複的交代什麼式乘上多少然後要代到哪裡的文字描述。那麼,列運算又是如何對應到矩陣的乘法呢?這部份其實非常簡單,只要預備一個大小和A 矩陣列個數相同的單位矩陣(單位矩陣是一個方正,對角線上的值為1 ,其餘元素是0),然後對單位矩陣做想要達成的列運算,然後在將其乘在A 矩陣的左邊,結果就相當於對A 做相同的列運算。

我們以一個3-by-3的矩陣為例,若我們要對

 http://glophy.com/images/equation/linear2_2/latex-image-1.png

這個矩陣的第二列乘上常數2 ,那麼我們先預備一個大小是3-by-3 的單位矩陣,然後將第2 列的元素全部乘上2,然後將這個矩陣乘在A 的左邊,其乘法的解果,就是將A 矩陣的第2 列元素就會乘上該2。例如

 http://glophy.com/images/equation/linear2_2/latex-image-2.png

我們如果要將A 矩陣的第一列加到第二列,我們只要在A 矩陣的左邊乘上經過第一列加到第二列處理的單位矩陣即可。例如

 http://glophy.com/images/equation/linear2_2/latex-image-3.png

同樣地,我們如果要將A 的第一列和第三列互換,我們只要將單位矩陣的第一列和第三列互換,然後將處理過後的矩陣乘在A 的左邊即可。例如

 http://glophy.com/images/equation/linear2_2/latex-image-4.png

上述的三個列運算所對應的經過處理的單位矩陣,我們統稱為基礎矩陣,習慣上我們用Ei來代表做第i 次列運算所使用的基礎矩陣。在這一節一開始我們給了一個三元一次聯立方程式,並且我們使用高斯消去法將這個聯立方程式轉化成變數個數遞減的形式。就這一個例子來說,很巧的我們只用到兩種列運算,就是某一列乘上一個非零的常數以及將一列乘上某個常數再加到另外一列。這兩個列運算所對應的基礎矩陣,正好都是下三角矩陣。我們可以經由簡單的證明得知,一個下三角矩陣乘上另外一個下三角矩陣,可以得到另外一個下三角矩陣。近一步,我們可以再證明,一堆下三角矩陣的乘積等於下三角矩陣。意思是說,如果在做高斯消去法的過程中,都沒有使用到兩列互換的動作,那麼當我們把A 矩陣轉化為一個上三角矩陣U 時,矩陣U必定可以表示成E1*E2*...*Ei*A,其中每一個基礎矩陣都是上三角矩陣。亦即,

 http://glophy.com/images/equation/linear2_2/latex-image-5.png

先前我們介紹列運算時,反覆地提到一件事,就是為了保持方程組的解不變,列運算的過程是可逆的,可以被還原的。換句話說,每一個基礎矩陣,都會有另外一個基礎矩陣作為他的逆矩陣,來還原方才它處理過的動作。 例如

 http://glophy.com/images/equation/linear2_2/latex-image-6.png

的逆矩陣(反矩陣)是

 http://glophy.com/images/equation/linear2_2/latex-image-7.png

以及

 http://glophy.com/images/equation/linear2_2/latex-image-8.png

的反矩陣是

 http://glophy.com/images/equation/linear2_2/latex-image-9.png

我們用Ei-1來代表Ei的反矩陣,並且我們可以觀察到,若Ei是下三角矩陣,那麼Ei-1也是下三角矩陣。另外,兩列互換的基礎矩陣對應的反矩陣正好就是它本身,簡單說,就是換過去,再換回來,就回到原來的樣子。所以,我們可以把基礎矩陣分成兩類,第一類是下三角矩陣,我們改用符號Li來表示,第二類我們用Pi來表示兩列互換的矩陣,並且PiPi=I(習慣上,我們用大寫的I代表單位矩陣)。

回到我們先前所提到的,若做高斯消去法的過程中沒有使用到兩列互換的動作,那麼我們可以把A 矩陣表示為

 http://glophy.com/images/equation/linear2_2/latex-image-10.png

並且

 http://glophy.com/images/equation/linear2_2/latex-image-11.png

由於Li-1都是下三角矩陣,其乘積也是,因此A 矩陣可以寫成

 http://glophy.com/images/equation/linear2_2/latex-image-12.png

我們把這樣的分解方式稱為LU分解,這裡的L是指下三角矩陣的意思,U 是指上三角矩陣的意思。當一個線性方程組AX=B 我們把它轉化成LUX=B時,我們令Y=UX,那麼原方程組就變成LY=B。由於L 是一個下三角矩陣,所以對應的第一個式子是一元一次方程式,再來是二元一次,依次類推。所以,我們可以將第一個變數Y1解出來後,帶入第二個式子解出Y2,並且依次將每一個變數都解出來。解出Y 之後,我們再解UX=Y 這個方程組。同樣的,由於U是一個上三角矩陣,所以最後一個方程式是一元一次方程式,我們可以解出Xn然後代入上一個式子解出Xn-1然後再依次解出每一個未知變數。

然而,並不是每一個矩陣都可以這麼順利地不需要使用到兩列互換的列運算便可以完成LU分解。接下來,我們討論需要做列對調時,應該注意的事項。為了保持證明的方便,我們定義Lji為利用i列將j列的第i個元素消為0 的基礎矩陣,lji是Lji對角線外對應僅存非零的元素。Pij是將i 列與j 列互換的基礎矩陣。那麼在一般的情況下處理高斯消去法將A 矩陣轉化成上三角矩陣U 可以寫成

 http://www.glophy.com/images/equation/linear2_2/latex-image-13.png

我們希望的是,若可以把所有的列互換基礎矩陣集合在一起,意思是說,先將A 矩陣的列順序排好,使得接下來只要連續的在A 的左邊乘上下三角矩陣的基礎矩陣,這樣就可以得到

 http://www.glophy.com/images/equation/linear2_2/latex-image-14.png

的簡單形式。那麼Pij和Lij到底能不能互換呢?

答案是不可以的。我們可以隨便舉個例子,就會發現這兩個矩陣乘法是不能互換的。雖然Pij和Lij是不能互換的,但是不代表我們不能將所有的列互換矩陣集合在一起。舉例來說,若我們對A 矩陣做高斯消去法做了以下步驟,使得A 轉化為一個上三角矩陣

 http://www.glophy.com/images/equation/linear2_2/latex-image-15.png

由於做了第二和第三列的對調,因此當我們把P23提前到A 矩陣前面時,對應到第二列和第三列的消去矩陣都需要被更動,並且lij的值都會跟著做改變。亦即

 http://www.glophy.com/images/equation/linear2_2/latex-image-16.png

簡單來說,先排列再消去而得到

http://www.glophy.com/images/equation/linear2_2/latex-image-14.png

這樣的形式是可能的。若我們可以用基礎矩陣的乘積將矩陣A 轉成上三角矩陣,那麼我們就能將A 矩陣做列排序,然後僅用下三角矩陣的基礎矩陣把PA 做LU分解。舉例來說,給定一個A矩陣如下

 http://www.glophy.com/images/equation/linear2_2/latex-image-17.png

由於第一列第一個元素就遇到0 ,使得我們無法利用第一列來消除其他列的第一個元素,因此,我們要做列對調。我們比較下列兩種對調方法。第一

  http://www.glophy.com/images/equation/linear2_2/latex-image-18.png

第二是

 http://www.glophy.com/images/equation/linear2_2/latex-image-19.png

這兩個PA=LU的方法,都成功的將PA矩陣轉化為LU矩陣,對於計算來說,有什麼差別呢?乍看之下,除了排列方式有差別之外,若拿來求解,PAx = Pb,給定任意b,所得到的x都一樣。這樣的結論,都是假設沒有計算誤差的情況。我們知道,電腦無法精確的儲存所有的有理數。因此,在數值計算中,我們必須考慮到誤差對解所造成的影響。假若有一個排列方式,使得計算Ly=Pb時的第一個變數y1就產生誤差,那麼這個誤差就會一直帶到y 的所有變數中,進而再帶到所有Ux=y 的變數中。因此,適當的選擇排列的方式,對於解的穩定性有極大的幫助。

2.3 相依方程組

應該在國高中的時候,我們會背一個口訣。就是有幾個未知數,就需要幾條方程式。這當然是一個很粗糙的說法。在解線性方程組的時候,若要解出唯一的解,這個口訣是必要的。倘若方程式的個數少於未知數的個數,對線性方程組來說會存在一個系統解,就是我們可以把解表示成與幾個參數有關的式子,當這些參數被確定的時候,對應的解也被確定。

使用高斯消去法解線性方程組的時候,有時會發生這樣的情況,就是某一列方程式會被完全的消除。從列運算的過程來看,我們知道這些可以被消除的方程式他可以寫成其他式子的某個常數乘積的和。舉例來說

 http://glophy.com/images/equation/linear2_3/latex-image-1.png

L3恰巧可以寫成2倍的L2減去L1。因此,當我們運算高斯消去法的時候此方程組可以化減為

 http://glophy.com/images/equation/linear2_3/latex-image-2.png

這時,我們無法從變數最少的式子中,解出變數的答案,像先前的範例一樣,可以透過遞迴地方式,一一把未知數求出來。變數最少的L2中有兩個未知數,我們設定一個參數給其中的一個未知數z,假定z=t, t是任意實數。那麼y = (15-11t)/7,y 變成t 的一個參數表示。接著,我們就可以依序地往前代,讓每一個變數都參數化。以這個例子來說,x = (12+29t)/21。如果我們把x,y,z 的參數表示,寫成

http://glophy.com/images/equation/linear2_3/latex-image-3.png

這就是高中數學的直線參數式。這個表示式代表一個集合,給定一個實數t 就會得到一個點,當t在變化時,對應的點也隨之變化,而這個集合恰好代表一個直線。

我們再回頭看L3這個方程式。由於L3正好可以寫成L1和L2的組合,我們將L3稱為L1和L3的線性組合,並且稱L3與L1, L2相依。簡單說,就是當有L1和L2時,L3可以被L1和L2表示出來。這也代表了L3並未提供L1與L2之外的其他訊息。假設我們有一個n個方程式,n個未知數的線性方程組。如果正好有一個方程式可以寫成其他方程式的線性組合(意思是說有一個方程式被消去了),那麼我們會引進一個參數到解裡面。若有兩個方程式被消去了,那麼我們會引進兩個參數到解裡面。所以,方程式就好像是限制式一樣,方程式越多,就表示解的限制範圍越多,當然解的存在範圍就越小,反之亦然。在線性代數裡面,我們把一個方程組中無法消去的式子的個數,稱為秩(rank)。因此,要引進的參數個數,就是未知數個數減掉rank。

再看看L1和L3這兩個方程式,不論你如何運用列運算來化簡這兩個式子,不會再有任何一個方程式被消滅。這時我們稱這兩個方程式是彼此獨立的。高中的時候我們學過這種三元一次方程式可以代表空間中的平面,不論是原是或是經過處理消去L3的式子,當中的L1與L2都代表空間中的平面,同時我們也學過三元一次方程式未知數前面的係數代表這個平面的法向量。那麼經過列運算之後這些平面的方向改變了,那麼怎麼消都消不去的這個特性,到底是因為什麼沒有改變?

  http://www.glophy.com/images/equation/linear2_3/latex-image-0.jpg(圖一)

高斯消去法中我們使用列運算來轉化係數矩陣使其成為上三角矩陣,方程式裡面對應的向量在空間中是如何變化的?我們假設高斯消去法的過程中沒有用到列對調,並且我們沒有使用某一列乘上一個倍數這個運算,亦即我們只用到將某一列加減到另外一列。我們看圖一,若向量OA是第一個方程式所對應的向量,向量OB是第二個方程式所對應的向量,假若將第一式的係數加到第二式可以將第二式的某個係數給消去,那麼第二式對應的係數會變成向量OC。我們注意到圖一中有一個不變量,就是向量OA與向量OB所張出的平行四邊形面積,和變化後的向量OA與向量OC所張出來的平行四邊形面積相同。不論用多少倍率的向量OA加到向量OB,都無法改變這個事實。請留意,造成這個結果的原因,是因為向量OB有一個垂直於向量OA的分量,而這個分量是無法透過加減向量OA的分量來消去的。垂直是線性代數中一個非常重要的課題,在往後的章節中我們會再詳細說明。

從上面這個圖例,我們知道一個向量如果具有垂直於其他向量的分量,那麼這個向量就不會被其他向量的線性組合所展開,那麼這個向量必定獨立於其他向量。同理,這樣的向量所對應的方程式,無論如何使用列運算,都無法將它消去。因此,垂直這個概念和方程式的解集合也有很大的關聯。在三元一次聯立方程式中,我們說,若方程式有唯一的解,那麼係數矩陣的行列式值不等於零。我們同時知道,三階的行列式值同時也代表著三個方程式的係數向量所張出來的六面體體積。這樣的概念可以繼續擴充到更高維度的情況,行列式可以定義在更高階的行列式,體積也可以被擴充到更高維度空間的體積。

許多參考書都有介紹到如何計算高階行列式的值,如何降階,以及在什麼樣的條件下,行列式值不為零。我個人對行列式有偏見,總覺得花費這麼大的精神算一個數值出來,在解方程式中它止回答了是否等於零這樣一個訊息,實在不划算。還比不上真正上三角化的過程,從保留多少個消不去的方程式還提供更多的訊息。因此,關於行列式的細節,在此不多描述,請有興趣的讀者自行參考其他書本或網頁。

最後,我們談一下無解的情況。在高斯消去法中,如果我們將係數矩陣的某一行消去了,可是對應增廣矩陣的常數卻不是0 ,這時候就會發生0 乘上某個數卻不為零的情況,當這樣的情況時方程組無解。

2.4 反矩陣

當我們稱一個矩陣為單位矩陣時,表示這個矩陣是方陣,並且除了對角線上的值是1 之外,其餘非對角線上的值皆為零。我們用I 這個符號來表示單位矩陣,有時我們用In來強調它是一個n-by-n 的單位矩陣。當我們利用高斯消去法解Ax=b 時,

http://www.glophy.com/images/equation/linear2_2/latex-image-13.png

若U 的對角線上的元素皆不為零,那麼我們可以利用類似上三角化的過程,倒著做,從U 矩陣的最右下角開始,一一的將U 非對角線上的值給消去,使得U 成為一個對角矩陣。接著我們可以用將某一列乘上一個非零的值這樣的基礎矩陣來調整對角線上的值,使得A 成為一個單位矩陣。意思是說,若經過高斯消去法得到的U 矩陣對角線上的值皆不為零,那麼存在一組基礎矩陣,使得

 http://www.glophy.com/images/equation/linear2_4/latex-image-1.png

這時我們稱這一組基礎矩陣的乘積為

 http://www.glophy.com/images/equation/linear2_4/latex-image-2.png

A-1稱為A 的反矩陣或是逆矩陣。反矩陣的特性為

 http://www.glophy.com/images/equation/linear2_4/latex-image-3.png

換個角度來看,A 矩陣也可以看做是一堆基礎矩陣的乘積

 http://www.glophy.com/images/equation/linear2_4/latex-image-4.png

這樣就更有感覺基礎矩陣的「基礎」啦!

總結一下反矩陣的一些特性,這些特性彼此等價(可以相互推導):

  • 方程組Ax=b 有唯一解
  • A 的行列式值不為零
  • A 的rank 與變數個數相同
  • A 的每一列方程式彼此獨立
  • A=LU其中L與U的對角線值皆不為零
  • A 可以寫成一組基礎矩陣的乘積
  • A的每一個列向量都存在著垂直於其他列的分量
最後更新 ( 2009/04/30, 週四 )
 
< 前一個   下一個 >