Tag Archives: LU 分解

翻轉 LU 分解

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

Posted in 線性方程, 線性代數專欄 | Tagged , , | Leave a comment

別再算逆矩陣了

本文的閱讀等級:初級 不知道從甚麼時候開始,“三階逆矩陣公式”經常雄踞本站「近期最多人點閱」表單的榜首,每日點閱該文的次數少則幾十,多則上百,下圖是過去一年以來的瀏覽次數統計 (主要的峰值所在的日期大致與台灣高等院校春秋二季期中和期末考試相吻合)。對於所見的逆矩陣風潮,我感到相當困惑:究竟出於甚麼樣的動機眾多年輕讀者願意不辭勞苦求算 (三階) 逆矩陣?如果尋覓逆矩陣公式的行動單純源於人類天生想要探索未知世界的好奇心,那我沒甚麼意見。不過,倘若只因為要解線性方程而計算逆矩陣,我可就忍不住要奉勸諸位:「省點力氣,別再算逆矩陣了!」

Posted in 線性代數專欄, 數值線性代數 | Tagged , , , , | 9 Comments

QR 演算法 (上)

本文的閱讀等級:中級 1920至1930年代,量子力學之矩陣力學 (matrix mechanics) 首次將矩陣理論推向應用領域 (見“海森堡不確定原理的矩陣證明”)。此後,特徵值與特徵向量遂成為線性代數所處理的四個核心問題之一 (見“線性代數的核心問題”)。令 為一個 階實矩陣或複矩陣, 為一特徵值, 為對應的 (非零) 特徵向量,滿足特徵方程 。1940年代,許多數學家和工程師相繼加入特徵值與特徵向量算法的研究行列。最明顯的特徵值算法,即線性代數教科書所述的標準方法,包含二個步驟:先計算 的特徵多項式的係數, , 再求出 的所有根。多項式的求根問題在當時曾經是一個熱門的研究題目。不幸的是,除了小尺寸矩陣 (),運用有限位元的電子計算機實現上述算法最終是一場無可逃避的災難,因為多項式求根在本質上是一個病態問題,根的位置很容易受到多項式係數的微小擾動而發生劇烈改變 (Wilkinson 多項式說明了這種情況,詳見“Power 迭代法”)。然而,在多數的情況下,矩陣的特徵值對於 個元的微小擾動並不敏感。這表示將矩陣 的 個元替換為特徵多項式 的 個係數過度壓縮資料,故而危害特徵值的計算。   既然直接求解特徵多項式的根不可行,研究工作者於是改採其他途徑。他們所考慮的問題形式並非特徵方程 ,而是 Schur 分解定理 (見“矩陣三角化的 Schur 定理”):任一方陣 必可三角化為 ,其中 是一個上三角矩陣, 是一個么正 (unitary) … Continue reading

Posted in 線性代數專欄, 數值線性代數 | Tagged , , , | 3 Comments

利用 LU 分解推導 Lehmer 矩陣的逆矩陣

本文的閱讀等級:初級 Lehmer 矩陣為一 階對稱矩陣 ,其中 Lehmer 矩陣是一種測試矩陣,通常用來評估逆矩陣算法的精確度。逆 Lehmer 矩陣為三對角矩陣 (見“特殊矩陣 (11):三對角矩陣”),並具有一種奇特的性質。令 表示 階 Lehmer 矩陣。對於 ,除了 的 元, 恰為 的 階領先主子陣 (即左上 階分塊)。下面列舉 的 Lehmer 矩陣及其逆矩陣: 透過觀察不太容易歸納出 Lehmer 矩陣的逆矩陣公式,本文用 LU 分解推導逆矩陣 (見“LU 分解”)。對稱矩陣 的 LU 分解可表示為 ,其中 是下三角矩陣且主對角元等於 , 是對角矩陣。若 … Continue reading

Posted in 線性方程, 線性代數專欄 | Tagged , , , | Leave a comment

每週問題 September 16, 2013

這是關於矩陣是否存在 LU 分解的判別問題。 Determine all values of for which has an LU factorization.

Posted in pow 線性方程與矩陣代數, 每週問題 | Tagged | Leave a comment

特殊矩陣 (19):Hessenberg 矩陣

本文的閱讀等級:中級 令 為一 階矩陣。若 , ,則 稱為上 Hessenberg 矩陣,也就是說, 的主對角下標元 (subdiagonal,即 ) 之下的所有元為零。若 的主對角上標元 (superdiagonal,即 ) 之上的所有元為零,則稱為下 Hessenberg 矩陣。此特殊矩陣因德國工程師黑森貝格 (Karl Adolf Hessenberg) 而得名。見下例, 是上 Hessenberg 矩陣, 是下 Hessenberg 矩陣, 同時是上、下 Hessenberg 矩陣,稱為三對角 (tridiagonal) 矩陣 (見“特殊矩陣 (11):三對角矩陣”): 。 明顯地,對稱 Hessenberg 矩陣必定是三對角矩陣。下 … Continue reading

Posted in 特殊矩陣, 線性代數專欄 | Tagged , , , , , , , | Leave a comment

PA=LU 分解

本文的閱讀等級:中級 令 是一個 階可逆矩陣。LU 分解 是高斯消去法的一種表達形式,下三角矩陣 記錄消元過程使用的乘數,上三角矩陣 儲存約化結果,其中 和 的主對角元分別滿足 和 (見“LU 分解”)。不過,並非每一可逆矩陣都存在 LU 分解。在執行高斯消去法的化簡程序中,若 出現在軸元 (pivot) 位置,即 元,列取代運算便無法消去軸元底下各元,這時標準 LU 分解不復存在。可逆矩陣 的軸元總數 (即 ) 等於 ,透過列交換運算必能獲得一個 (非零) 軸元,所以仍可繼續下一階段的化簡步驟。從實際面來看,縱使未發生「零軸元」的情況 (軸元所在位置為零),為了避免因不當使用消去法而引發災難,部分軸元法 (partial pivoting) 也會適時地交換列 (見“特殊矩陣 (12):對角佔優矩陣”)。見下例 (取自[1]): 。 從 同時包含數值很小和很大的主對角元可知 不具數值穩定性,也就是說,標準 LU … Continue reading

Posted in 線性方程, 線性代數專欄 | Tagged , , , , | 9 Comments

無相互作用的矩陣積

本文的閱讀等級:初級 考慮下列 矩陣: 。 矩陣 共有 種排列方式,因此產生 6 個矩陣積,即 , 其中 未產生 項,我們稱這些矩陣乘積無「相互作用」(interaction)。本文要探討的問題是:無相互作用的矩陣積必須滿足何種矩陣排列規則?

Posted in 線性方程, 線性代數專欄 | Tagged , , , | 2 Comments

Cholesky 分解

本文的閱讀等級:中級 任何一個實對稱正定矩陣 都可唯一分解為 (若 為 Hermitian 正定矩陣,則有 ),其中 是下三角矩陣且主對角元皆為正數。這個分解式稱為 Cholesky 分解,由法國砲兵軍官喬列斯基 (André-Louis Cholesky) 所提出,當初的發明動機是為了解決測地計算問題。喬列斯基本人從未公開發表他的演算法,他於1918年的一場戰事中身亡,之後經口耳相傳,這個卓越的矩陣分解法才逐漸為時人所知。本文從 LU 分解推導 Cholesky 分解,並介紹一個演算法。

Posted in 線性代數專欄, 數值線性代數 | Tagged , , , , | 20 Comments

LU 分解

本文的閱讀等級:初級 令 為一個 階矩陣。LU 分解是指將 表示為兩個 階三角矩陣的乘積 , 其中 是下三角矩陣, 是上三角矩陣,如下例, 。 LU 分解的本質是高斯消去法的一種表達形式,矩陣 記錄消去法化簡 的過程,而矩陣 則儲存化簡結果 (見“高斯消去法”)。LU 分解的外表看似平淡無奇,但它可以用來解線性方程,逆矩陣和計算行列式,堪稱是最具實用價值的矩陣分解式之一。

Posted in 線性方程, 線性代數專欄 | Tagged , , , , | 15 Comments