Tag Archives: QR 演算法

QR 演算法 (上)

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

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

特殊矩陣 (19):Hessenberg 矩陣

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

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

特殊矩陣 (4):Householder 矩陣

本文的閱讀等級:中級 在幾何向量空間 ,鏡射 (reflection) 超平面 (hyperplane) 由單位法向量 決定 (超平面是維數等於 的子空間)。對於任一點 (或向量) ,從空間幾何可推論點 的鏡射為 ,其中 是點 在法向量 的投影量 (見下圖)。將純量 和向量 交換位置,並移除括弧,鏡射點可表示為 。 單位法向量 所定義的超平面的鏡射變換矩陣稱為 Householder 矩陣,如下: , 其中 。(對於 的一般子空間的鏡射矩陣請見“旋轉與鏡射”。)

Posted in 特殊矩陣, 線性代數專欄 | Tagged , , , , , , , , , | 12 Comments