翻轉 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.

Advertisements
本篇發表於 線性方程, 線性代數專欄 並標籤為 , , 。將永久鏈結加入書籤。

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s