翻轉 LU 分解

本文的閱讀等級:初級

愛因斯坦說[1]:「邏輯可以將你由 A 點帶到 B 點,想像則可以帶你到任何地方。」在我想像的翻轉課堂,學生會先在家裡觀看交大出版社發行的線性代數《教學光碟》,沒有購買光碟的學生則到學校圖書館觀看。在教室的時間,學生跟老師一起交流互動,我們經常以問答方式討論課程內容,但學生與老師的角色對調。底下抄錄一段關於 LU 分解的對話,大家可以體驗翻轉課堂的學習情境。

 
老師:一個方陣 A 的 LU 分解 A=LU 記錄高斯消去法的過程與結果,其中 L 是主對角元為 1 的下三角矩陣,U 是上三角矩陣 (見“LU 分解”),例如,

\displaystyle \begin{bmatrix} 1&2\\ 3&4 \end{bmatrix}=\begin{bmatrix} 1&0\\ 3&1 \end{bmatrix}\left[\!\!\begin{array}{cr} 1&2\\ 0&-2 \end{array}\!\!\right]

根據對稱性,方陣應該也存在 UL 分解 A=\tilde{U}\tilde{L},其中 \tilde{U} 是主對角元為 1 的上三角矩陣,\tilde{L} 是下三角矩陣?

學生:是的,上例方陣的 UL 分解為

\displaystyle \begin{bmatrix}1&2\\ 3&4 \end{bmatrix}=\begin{bmatrix}1&\frac{1}{2}\\ 0&1 \end{bmatrix}\left[\!\!\begin{array}{rc} -\frac{1}{2}&0\\3&4 \end{array}\!\!\right]

 
老師:怎麼運用 LU 分解得到 A=\tilde{U}\tilde{L}

學生:令排列 (permutation) 矩陣 P=\begin{bmatrix} 0&1\\ 1&0 \end{bmatrix}P 是反對角 (anti-diagonal) 矩陣,P^T=P^{-1}=P。令 A'=PAP,稱為 A 的翻轉矩陣 (見“矩陣視覺化”)。例如,

\displaystyle A'=PAP=\begin{bmatrix} 0&1\\ 1&0 \end{bmatrix}\begin{bmatrix} 1&2\\ 3&4 \end{bmatrix}\begin{bmatrix} 0&1\\ 1&0 \end{bmatrix}=\begin{bmatrix} 4&3\\ 2&1 \end{bmatrix}

計算 LU 分解 A'=L'U',即 PAP=L'U'。上式等號兩邊左右同乘以 P

\displaystyle A=PL'U'P=(PL'P)(PU'P)=\tilde{U}\tilde{L}

其中 \tilde{U}=PL'P 是上三角矩陣,\tilde{L}=PU'P 是下三角矩陣。用前面的例子展示:

\displaystyle A'=\begin{bmatrix} 4&3\\ 2&1 \end{bmatrix}=\begin{bmatrix} 1&0\\ \frac{1}{2}&1 \end{bmatrix}\left[\!\!\begin{array}{cr} 4&3\\ 0&-\frac{1}{2} \end{array}\!\!\right]=L'U'

可得

\displaystyle \begin{aligned} \tilde{U}&=PL'P=\begin{bmatrix} 0&1\\ 1&0 \end{bmatrix}\begin{bmatrix} 1&0\\ \frac{1}{2}&1 \end{bmatrix}\begin{bmatrix} 0&1\\ 1&0 \end{bmatrix}=\begin{bmatrix} 1&\frac{1}{2}\\ 0&1 \end{bmatrix}\\ \tilde{L}&=PU'P=\begin{bmatrix} 0&1\\ 1&0 \end{bmatrix}\left[\!\!\begin{array}{cr} 4&3\\ 0&-\frac{1}{2} \end{array}\!\!\right]\begin{bmatrix} 0&1\\ 1&0 \end{bmatrix}=\left[\!\!\begin{array}{rc} -\frac{1}{2}&0\\ 3&4 \end{array}\!\!\right]. \end{aligned}

 
老師:如果不透過翻轉矩陣 A',有辦法直接算出 A=\tilde{U}\tilde{L}

學生:你仍然可以使用高斯消去法計算,但要翻轉消元次序。用上例說明,考慮軸元 (pivot) a_{22}=4,利用基本列運算 (elementary row operation) 消去 a_{12}=2,以基本 (elementary) 矩陣乘法表示:

\displaystyle EA=\left[\!\!\begin{array}{cr} 1&-\frac{1}{2}\\ 0&1 \end{array}\!\!\right]\begin{bmatrix} 1&2\\ 3&4 \end{bmatrix}=\left[\!\!\begin{array}{rc} -\frac{1}{2}&0\\ 3&4 \end{array}\!\!\right]=\tilde{L}

左乘 E^{-1},這樣就得到 UL 分解

\displaystyle A=E^{-1}\tilde{L}=\begin{bmatrix}1&\frac{1}{2}\\ 0&1 \end{bmatrix}\left[\!\!\begin{array}{rc} -\frac{1}{2}&0\\ 3&4 \end{array}\!\!\right]=\tilde{U}\tilde{L}

 
老師:如何判斷一個方陣是否存在 UL 分解?

學生:若 n\times n 階可逆矩陣 A 的所有 k\times k 階領先主子陣 A_k 都是可逆的,1\le k\le n,則存在 LU 分解。例如,\det A_1=\det [1]=1\det A_2=\begin{vmatrix} 1&2\\ 3&4 \end{vmatrix}=-2,可知 A 有 LU 分解。翻轉過來,若 n\times n 階可逆矩陣 A 的所有 k\times k 階殿後主子陣 \tilde{A}_k 都是可逆的,則存在 UL 分解。例如,\det \tilde{A}_1=\det[4]=4\det \tilde{A}_2=\begin{vmatrix} 1&2\\ 3&4 \end{vmatrix}=-2,可知 A 有 UL 分解。

 
老師:謝謝,今天討論到此。下次上課的第一個問題是:為甚麼線性代數《教學光碟》沒有顛覆傳統將 LU 分解翻轉成 UL 分解?

 
註解
[1] 原文:Logic will get you from A to B. Imagination will take you everywhere.

This entry was posted in 線性方程, 線性代數專欄 and tagged , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s