Tag Archives: QR 分解

每週問題 June 19, 2017

證明一個可逆矩陣存在 QR 分解。 Prove that an invertible matrix can be represented in the form , where is an orthogonal matrix and is an upper triangular matrix. Advertisements

Posted in pow 內積空間, 每週問題 | Tagged , | Leave a comment

約束最小平方問題

本文的閱讀等級:中級 令 為一個 階實矩陣,。如果線性方程 是不一致的 (即不存在解),實務的作法是將線性方程問題改為最小平方近似問題: , 其中 是2-範數 (見“向量範數”),即 與 的歐幾里得距離。根據正交原則,最小平方解 滿足正規方程 (normal equation) (見“從線性變換解釋最小平方近似”)。若 ,也就是說 的行向量 (column vector) 構成一個線性獨立集合,則存在唯一的最小平方解 。 如果最小平方解必須滿足某些束縛條件,則稱為約束最小平方問題 (constrained least-squares problem)。本文討論兩種常出現在多種應用場合的約束形式。線性約束最小平方問題是指束縛條件為線性方程[1]: , 其中 是一個 階實矩陣,。正則 (regularized) 最小平方問題限制未知向量的長度必須固定: 。

Posted in 線性代數專欄, 內積空間 | Tagged , , , , | 4 Comments

利用舒爾引理證明可交換矩陣同時可三角化

本文的閱讀等級:中級 令 為一 階兩兩可交換 (commuting) 矩陣集,也就是說任兩矩陣 和 滿足 。以下考慮 。可交換矩陣集 的所有矩陣同時可三角化,具體而言,存在一么正 (unitary) 矩陣 ,,使得 ,,為上三角矩陣 (見“同時可三角化矩陣”)。本文介紹一個利用舒爾引理 (Schur’s lemma) 的證明方法。

Posted in 特徵分析, 線性代數專欄 | Tagged , , , | Leave a comment

極小範數解

本文的閱讀等級:中級 令 為一個 階實矩陣。我們用 代表 的行空間 (值域,column space),即 。請注意, 是 的一個子空間。對於任一 ,線性方程 必定有解。在解集合中,有一個解最為特別,該特解位於 的列空間 (row space),即 的行空間 ,並具有最小的2-範數 (歐氏範數,見“向量範數”),稱為極小範數解 (minimum norm solution),記為 。這篇短文介紹極小範數解的性質與表達式。

Posted in 線性代數專欄, 內積空間 | Tagged , , , , | 11 Comments

QR 演算法 (上)

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

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

分塊矩陣的行列式

本文的閱讀等級:初級 我們知道二階行列式的計算公式為 , 那麼 階分塊矩陣的行列式 是否也有相同的公式?在一般情況下,相應的分塊矩陣的行列式公式並不存在,但如果 或 滿足某些特定條件,則有簡明的計算公式。回顧行列式的標準公式──排列公式 (或稱萊布尼茲公式,見“行列式的運算公式與性質”):若 為一個 階矩陣, , 其中 表示自然排序 的排列 (permutation), 若 經過偶數次換位 (transposition,即交換兩元位置) 可得自然排序, 若 經過奇數次換位可得自然排序。例如,若 ,換位過程如下: 從 經過三次換位得到自然排序,可知 。本文介紹一些常見的分塊矩陣的行列式公式,並使用排列公式、行列式基本性質,以及分塊矩陣乘法運算推導證明。

Posted in 線性代數專欄, 行列式 | Tagged , , | 3 Comments

線代膠囊──正交投影矩陣

本文的閱讀等級:中級 令 階實矩陣 有線性獨立的行向量 (column vector)。如何求得 階正交投影矩陣 ,其值域為 的行空間?   線代箴言:「工欲善其事,必先利其器。」我們先討論正交投影矩陣的性質。這裡面包含兩個子問題:一般的投影矩陣有甚麼性質?加入正交條件後,又多了甚麼性質?投影矩陣 將 維向量 映射至 ,其中 是 的值域 (行空間),而且 經 的再次投影恆定不變 (投影兩次等於投影一次),即 。 因為 是任意向量,可知 ,稱為冪等矩陣 (idempotent matrix)。若 是一正交投影矩陣,投影後的殘量 必定正交於投影子空間 ,其中成員可表示為 (這裡 是一 維向量),於是有 。 因為 和 是任意向量,可知 。但 是對稱矩陣,故 。

Posted in 線性代數專欄, 內積空間 | Tagged , , , , | Leave a comment

線代膠囊──QR 分解

本文的閱讀等級:中級 假設 階實矩陣 有線性獨立的行向量 (column vector)。如何求得 QR 分解 ,其中 階矩陣 的行向量組成單範正交集 (orthonormal set), 為 階上三角矩陣?   將 和 以行向量表示,並以上三角矩陣 聯繫, 即為 。 乘開上式, 。 我們的問題要解出 和 。但這不是一般所見的線性方程組,該怎麼辦呢?

Posted in 線性代數專欄, 內積空間 | Tagged , , | 22 Comments

特殊矩陣 (19):Hessenberg 矩陣

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

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

QR 分解的數值計算方法比較

本文的閱讀等級:中級 QR 分解是數值線性代數中具備多種用途的計算工具,主要應用於線性方程、最小平方法和特徵值問題。常見的 QR 分解的計算方法包括 Householder 變換、Givens 旋轉以及 Gram-Schmidt 正交法。本文先回顧 QR 分解的主要性質,介紹 QR 分解於計算最小平方解的應用,並討論上述三種算法的運算量與數值穩定性。

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