Tag Archives: 三對角矩陣

Krylov 子空間法──線性方程的數值解法 (一):Arnoldi 與 Lanczos 算法

本文的閱讀等級:高級 令 為一 階複矩陣, 為一非零向量。向量序列 稱為 Krylov 序列,此序列所生成的子空間稱為 Krylov 子空間 (見“Krylov 子空間法”),記為 。 因為 是有限維空間 的一個子空間,當 不斷增大時,Krylov 序列 最終會是一個線性相關集。設 為最小的正整數使得 ,也就是說 為一個線性獨立集且 。因此,存在唯一數組 滿足 。 定義 次多項式 。 因為 ,我們稱 為 相對於 的最小 (消滅) 多項式 (minimal polynomial)。以下考慮 為可逆矩陣。我們可以斷定 ,否則有 ,即存在次數小於 … 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

線性代數在數值分析的應用 (二):Dirichlet 問題

本文的閱讀等級:中級 在物理學中,等方向均勻介質的一點的溫度變化由熱傳導方程 (heat equation) 所描述[1]: , 其中 是點 於時間 的溫度, 是一正數,稱為熱擴散率 (thermal diffusivity), 是 Laplace 算子 (或稱 Laplacian),定義如下: 。 淺白地說,Laplace 算子度量一點的函數值與其鄰近點的差異。若點 處於穩態,即該點溫度不隨時間改變,則 滿足 Laplace 方程 。如果二階連續可導函數 ( 為一開集) 滿足 Laplace 方程,我們稱之為調和函數 (harmonic function)。本文將探討簡化後的二維 Dirichlet 問題[2]:尋找一調和函數 ,使其在一正方形區域內所有點皆滿足 ,且邊界滿足給定條件 。

Posted in 線性代數專欄, 應用之道 | Tagged , , , , , , , | 2 Comments

實對稱矩陣特徵值變化界定的典型問題

本文的閱讀等級:中級 線性代數所處理的最佳化問題可概分為二大類:一是線性方程 的最小平方近似解問題,即求出 使得誤差平方 具有最小值。內積空間理論導出最佳解須滿足正規方程式 (normal equation) (見“ 從線性變換解釋最小平方近似”)。二是特徵分析推衍的二次型約束最佳化問題,即求單位向量 (unit vector) 使得 有最大值,其中 是實對稱矩陣。二次型 的極值產生條件是特徵方程式 ,極值大小則由 的特徵值決定 (見“二次型與正定矩陣”)。因為這個緣故,二次型約束最佳化也稱為實對稱矩陣的特徵值變化界定,下面我們討論兩個典型問題並說明完整的解法。   問題一 (取自 2012年台大資訊所碩士班入學試題):令 為實數,且 ,求 的最大值。

Posted in 線性代數專欄, 二次型 | Tagged , , , , , | Leave a comment

每週問題 April 16, 2012

本週問題是計算一特殊型態的三對角(tridiagonal)矩陣的行列式。 Pow-April-16-12 參考解答 PowSol-April-16-12

Posted in pow 行列式, 每週問題 | Tagged | Leave a comment

每週問題 December 13, 2010

這是特殊三對角矩陣的行列式計算問題,過程使用差分方程。 Pow-Dec-13-10 參考解答 PowSol-Dec-13-10

Posted in pow 行列式, 每週問題 | Tagged | Leave a comment

線性代數在數值分析的應用 (一):兩點邊值問題

本文的閱讀等級:初級 數值分析 (numerical analysis) 是一門研究連續數學問題演算法的科目,內容包羅萬象,如解非線性方程、解線性或非線性聯立方程組、插值 (interpolation) 與曲線配適 (curve fitting)、數值微分與積分、常微分方程與偏微分方程的數值解、邊值 (boundary-value) 與特徵值 (characteristic-value) 問題等。線性代數和數值分析有極密切的關係,一方面數值分析涵蓋一些數值線性代數問題,另一方面數值分析的部分演算法建立於線性代數之上。本文介紹線性代數在數值分析中的一個簡單應用──將兩點邊值 (two-point boundary-value) 問題轉換為線性聯立方程組的求解問題。

Posted in 線性代數專欄, 應用之道 | Tagged , , , , | Leave a comment

特殊矩陣 (11):三對角矩陣

本文的閱讀等級:初級 如果 階方陣 除了主對角線元以及比主對角線低一列和高一列的對角線之外,其餘皆為零元,我們稱它為三對角 (tridiagonal) 矩陣,也就是說,當 ,;如下例, 三對角矩陣常出現於數值分析問題,本文僅介紹三對角矩陣的幾個基本性質,包括行列式計算、相似變換的應用以及求解線性方程。

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

每週問題 February 15, 2010

本週問題是求一個三對角矩陣的特徵值和特徵向量。 點選問題↓ Pow-Feb-15-10 參考解答↓ PowSol-Feb-15-10

Posted in pow 特徵分析, 每週問題 | Tagged , | 2 Comments