三對角矩陣
在線性代數中,一個三對角矩陣是矩陣的一種,它「幾乎」是一個對角矩陣。準確來說:一個三對角矩陣的非零系數在主對角線上,或比主對角線低一行的對角線上,或比主對角線高一行的對角線上。
例如,下面的是三對角矩陣:
性質
編輯三對角矩陣是海森堡矩陣。儘管一般的三對角矩陣不一定是對稱或埃爾米特矩陣,許多解線性代數問題時出現的矩陣卻往往有這些性質。進一步如果一個實三對角矩陣 A 滿足 ak,k+1 ak+1,k > 0,所以它元素的符號都為正,從而相似於一個埃爾米特矩陣,這樣特徵值都是實數。後一個推論如果我們將條件 ak,k+1 ak+1,k > 0 換為 ak,k+1 ak+1,k ≥ 0,結論仍然成立。
所有 n × n 三對角矩陣的集合組成一個 3n-2 維向量空間。
許多線性代數算法應用於對角矩陣時所需計算量特別少,這種改進也經常被三對角矩陣繼承。譬如,一個 n 階三對角矩陣 A 的行列式能用continuant的遞歸公式計算:
這裏 是第 k 個主子式,即 是由 A 最開始的 k 行 k 列組成的子矩陣。用此方法計算三對角矩陣所需計算量是線性 n ,然而對於一般的矩陣複雜度是 n 的 3 次方。
計算程序
編輯一個將一般矩陣變成海森堡型的變換,將厄密特矩陣變成三對角矩陣。從而,許多特徵值算法運用到厄密特矩陣上,第一步將輸入的厄密特矩陣變成三對角矩陣。
一個三對角矩陣利用特定的存儲方案比一般矩陣所用的存儲空間也少得多。例如,LAPACK Fortran包將一個 n-維非對稱三對角矩陣存為三個 1-維數列,其中一個長 n 包含對角元素,其它兩個長為 n− 1 包含下對角線和上對角線元素。
三對角矩陣方程 ,能用一種需要 O(n)次操作的特殊的算法解出來(Golub and Van Loan)。
參考文獻
編輯- ^ Thomas Muir. A treatise on the theory of determinants. Dover Publications. 1960: 516–525.
- Roger A. Horn and Charles R. Johnson, 矩陣分析, 劍橋大學出版社,1985. ISBN 0-521-38632-2.
- Gene H. Golub and Charles F. Van Loan, 矩陣計算(3rd), 美國約翰霍普金斯大學., 1996. ISBN 0-8018-5414-8.
- Bianca Beatriz Banagudos, Katherine Guerrero, and Donna Fe Gagaracruz, Mathematics 數學新世紀 Regional Science High School for R-IX, 2008-2009, IV-Quisumbing. ISBN 0-12-345678-9.