Matrix with nonzero elements on the main diagonal and the diagonals above and below it
線形代数 において 、 三重対角行列 （さんじゅうたいかく）とは、 主対角 成分 、下対角成分 （主対角成分より下の最初の対角成分）、上対角成分（主対角成分より上の最初の対角成分）のみに非零要素を持つ帯行列である。例えば、次の 行列は 三重対角行列 である 。
( 1 4 0 0 3 4 1 0 0 2 3 4 0 0 1 3 ) . {\displaystyle {\begin{pmatrix}1&4&0&0\\3&4&1&0\\0&2&3&4\\0&0&1&3\\\end{pmatrix}}.} 三角行列の行列式はその要素の連続によって与え られる 。 [ 1 ]
対称行列 (またはエルミート行列) を三角形式に直交変換するには、Lanczos アルゴリズムを 使用 し ます 。
プロパティ 三重対角行列は、上ヘッセンベルク行列と下ヘッセンベルク行列の 両方である行列です 。 [2] 特に、三重対角行列は p 個 の 1 行 1 列行列と q 個 の 2 行 2 列行列 の 直和で、 p + q /2 = n — 三重対角行列の次元です。一般的な三重対角行列は必ずしも 対称 または エルミートで はありませんが、線形代数の問題を解くときに生じる多くの三重対角行列はこれらの特性のいずれかを持っています。さらに、実三重対角行列 A がすべての kに対して a k 、 k +1 a k +1、 k > 0 を満たし 、その要素の符号が対称である場合、 基底行列の対角変換によってエルミート行列に 類似します。したがって、その 固有値は 実数です。厳密な不等式を a k , k +1 a k +1, k ≥ 0に置き換えると 、連続性により固有値は依然として実数であることが保証されますが、行列はもはやエルミート行列に相似である必要はありません。 [3]
すべてのn×n 三重対角行列 の 集合 は 3n-2 次元 ベクトル空間 を形成します。
多くの線形代数 アルゴリズムは、対角行列に適用すると 計算量が 大幅に削減され 、この改善は三重対角行列にも同様に適用されることがよくあります。
行列式 n 次の 三重対角行列 A の行列 式 は、3項 再帰関係 から計算できる。 [4] f 1 = | a 1 | = a 1 （つまり 、 f 1は a 1 のみからなる1行1列の行列の行列式 ）と書き、
f n = | a 1 b 1 c 1 a 2 b 2 c 2 ⋱ ⋱ ⋱ ⋱ b n − 1 c n − 1 a n | . {\displaystyle f_{n}={\begin{vmatrix}a_{1}&b_{1}\\c_{1}&a_{2}&b_{2}\\&c_{2}&\ddots &\ddots \\&&\ddots &\ddots &b_{n-1}\\&&&c_{n-1}&a_{n}\end{vmatrix}}.} 数列( f i )は 継続数 と呼ばれ、再帰関係を満たす。
f n = a n f n − 1 − c n − 1 b n − 1 f n − 2 {\displaystyle f_{n}=a_{n}f_{n-1}-c_{n-1}b_{n-1}f_{n-2}} 初期値は f 0 = 1 および f −1 = 0 です。この式を使用して三角行列の行列式を計算するコストは n に対して線形ですが、一般行列の場合は 3 乗になります。
反転 非特異三角行列 Tの 逆 行列
T = ( a 1 b 1 c 1 a 2 b 2 c 2 ⋱ ⋱ ⋱ ⋱ b n − 1 c n − 1 a n ) {\displaystyle T={\begin{pmatrix}a_{1}&b_{1}\\c_{1}&a_{2}&b_{2}\\&c_{2}&\ddots &\ddots \\&&\ddots &\ddots &b_{n-1}\\&&&c_{n-1}&a_{n}\end{pmatrix}}} は次のように与えられる。
( T − 1 ) i j = { ( − 1 ) i + j b i ⋯ b j − 1 θ i − 1 ϕ j + 1 / θ n if i < j θ i − 1 ϕ j + 1 / θ n if i = j ( − 1 ) i + j c j ⋯ c i − 1 θ j − 1 ϕ i + 1 / θ n if i > j {\displaystyle (T^{-1})_{ij}={\begin{cases}(-1)^{i+j}b_{i}\cdots b_{j-1}\theta _{i-1}\phi _{j+1}/\theta _{n}&{\text{ if }}i<j\\\theta _{i-1}\phi _{j+1}/\theta _{n}&{\text{ if }}i=j\\(-1)^{i+j}c_{j}\cdots c_{i-1}\theta _{j-1}\phi _{i+1}/\theta _{n}&{\text{ if }}i>j\\\end{cases}}} ここで θ i は 再帰関係を満たす
θ i = a i θ i − 1 − b i − 1 c i − 1 θ i − 2 i = 2 , 3 , … , n {\displaystyle \theta _{i}=a_{i}\theta _{i-1}-b_{i-1}c_{i-1}\theta _{i-2}\qquad i=2,3,\ldots ,n} 初期条件 θ 0 = 1, θ 1 = a 1 および ϕ i が満たす
ϕ i = a i ϕ i + 1 − b i c i ϕ i + 2 i = n − 1 , … , 1 {\displaystyle \phi _{i}=a_{i}\phi _{i+1}-b_{i}c_{i}\phi _{i+2}\qquad i=n-1,\ldots ,1} 初期条件は ϕ n +1 = 1 および ϕ n = a n です。 [5] [6]
閉形式の解は、すべての対角要素と非対角要素が等しい 対称行列 [7] や テプリッツ行列 [8] などの特殊なケースや、一般的なケースでも 計算できます。 [9] [10]
一般に、三重対角行列の逆行列は半分離行列であり、逆もまた同様である。 [11] 対称三重対角行列の逆行列は、次の形式の 単一対行列（ 生成子表現可能な半分離行列とも呼ばれる）として表すことができる 。[12] [13]
( α 1 − β 1 − β 1 α 2 − β 2 ⋱ ⋱ ⋱ ⋱ ⋱ − β n − 1 − β n − 1 α n ) − 1 = ( a 1 b 1 a 1 b 2 ⋯ a 1 b n a 1 b 2 a 2 b 2 ⋯ a 2 b n ⋮ ⋮ ⋱ ⋮ a 1 b n a 2 b n ⋯ a n b n ) = ( a min ( i , j ) b max ( i , j ) ) {\displaystyle {\begin{pmatrix}\alpha _{1}&-\beta _{1}\\-\beta _{1}&\alpha _{2}&-\beta _{2}\\&\ddots &\ddots &\ddots &\\&&\ddots &\ddots &-\beta _{n-1}\\&&&-\beta _{n-1}&\alpha _{n}\end{pmatrix}}^{-1}={\begin{pmatrix}a_{1}b_{1}&a_{1}b_{2}&\cdots &a_{1}b_{n}\\a_{1}b_{2}&a_{2}b_{2}&\cdots &a_{2}b_{n}\\\vdots &\vdots &\ddots &\vdots \\a_{1}b_{n}&a_{2}b_{n}&\cdots &a_{n}b_{n}\end{pmatrix}}=\left(a_{\min(i,j)}b_{\max(i,j)}\right)}
どこ で { a i = β i ⋯ β n − 1 δ i ⋯ δ n b n b i = β 1 ⋯ β i − 1 d 1 ⋯ d i {\displaystyle {\begin{cases}\displaystyle a_{i}={\frac {\beta _{i}\cdots \beta _{n-1}}{\delta _{i}\cdots \delta _{n}\,b_{n}}}\\\displaystyle b_{i}={\frac {\beta _{1}\cdots \beta _{i-1}}{d_{1}\cdots d_{i}}}\end{cases}}} { d n = α n , d i − 1 = α i − 1 − β i − 1 2 d i , i = n , n − 1 , ⋯ , 2 , δ 1 = α 1 , δ i + 1 = α i + 1 − β i 2 δ i , i = 1 , 2 , ⋯ , n − 1. {\displaystyle {\begin{cases}d_{n}=\alpha _{n},\quad d_{i-1}=\alpha _{i-1}-{\frac {\beta _{i-1}^{2}}{d_{i}}},&i=n,n-1,\cdots ,2,\\\delta _{1}=\alpha _{1},\quad \delta _{i+1}=\alpha _{i+1}-{\frac {\beta _{i}^{2}}{\delta _{i}}},&i=1,2,\cdots ,n-1.\end{cases}}}
線形システムの解 Ax = b の連立方程式は 、 A が三角行列の場合には 三角行列アルゴリズム と呼ばれるガウス消去法の効率的な形で解くことができ 、 O ( n )回の演算を必要とする。 [14] b ∈ R n {\displaystyle b\in \mathbb {R} ^{n}}
固有値 三角行列が テプリッツ行列 でもある場合、その固有値に対する単純な閉形式の解が存在する。すなわち、 [15] [16]
a − 2 b c cos ( k π n + 1 ) , k = 1 , … , n . {\displaystyle a-2{\sqrt {bc}}\cos \left({\frac {k\pi }{n+1}}\right),\qquad k=1,\ldots ,n.} 実 対称 三角行列は実固有値を持ち、対角要素がすべて非ゼロであれば、 すべての固有値は 異なる（単純）である。 [17] 実対称三角行列の固有値を任意の有限精度で数値計算する方法は数多く存在し、通常は サイズ の行列の演算を必要とする が、（並列計算なしで） のみを必要とする高速アルゴリズムも存在する 。 [18] O ( n 2 ) {\displaystyle O(n^{2})} n × n {\displaystyle n\times n} O ( n log n ) {\displaystyle O(n\log n)}
補足として、 非縮 約対称三重対角行列とは、三重対角行列の非ゼロの非対角要素を含む行列であり、固有値は異なるが、固有ベクトルはスケール係数を除いて一意であり、互いに直交している。 [19]
対称三角行列との類似性 非対称 または 非対称 三重対角行列の場合、 相似変換を用いて固有値分解を計算することができる。実三重対角非対称行列が与えられると、
T = ( a 1 b 1 c 1 a 2 b 2 c 2 ⋱ ⋱ ⋱ ⋱ b n − 1 c n − 1 a n ) {\displaystyle T={\begin{pmatrix}a_{1}&b_{1}\\c_{1}&a_{2}&b_{2}\\&c_{2}&\ddots &\ddots \\&&\ddots &\ddots &b_{n-1}\\&&&c_{n-1}&a_{n}\end{pmatrix}}} ここで 、非対角成分の各積が正であると仮定し 、 変換 行列を [20] で定義する。 b i ≠ c i {\displaystyle b_{i}\neq c_{i}} b i c i > 0 {\displaystyle b_{i}c_{i}>0} D {\displaystyle D}
D := diag ( δ 1 , … , δ n ) for δ i := { 1 , i = 1 c i − 1 … c 1 b i − 1 … b 1 , i = 2 , … , n . {\displaystyle D:=\operatorname {diag} (\delta _{1},\dots ,\delta _{n})\quad {\text{for}}\quad \delta _{i}:={\begin{cases}1&,\,i=1\\{\sqrt {\frac {c_{i-1}\dots c_{1}}{b_{i-1}\dots b_{1}}}}&,\,i=2,\dots ,n\,.\end{cases}}} 相似 変換により 対称 三角行列 が得られる : [21] [20] D − 1 T D {\displaystyle D^{-1}TD} J {\displaystyle J}
J := D − 1 T D = ( a 1 sgn b 1 b 1 c 1 sgn b 1 b 1 c 1 a 2 sgn b 2 b 2 c 2 sgn b 2 b 2 c 2 ⋱ ⋱ ⋱ ⋱ sgn b n − 1 b n − 1 c n − 1 sgn b n − 1 b n − 1 c n − 1 a n ) . {\displaystyle J:=D^{-1}TD={\begin{pmatrix}a_{1}&\operatorname {sgn} b_{1}\,{\sqrt {b_{1}c_{1}}}\\\operatorname {sgn} b_{1}\,{\sqrt {b_{1}c_{1}}}&a_{2}&\operatorname {sgn} b_{2}\,{\sqrt {b_{2}c_{2}}}\\&\operatorname {sgn} b_{2}\,{\sqrt {b_{2}c_{2}}}&\ddots &\ddots \\&&\ddots &\ddots &\operatorname {sgn} b_{n-1}\,{\sqrt {b_{n-1}c_{n-1}}}\\&&&\operatorname {sgn} b_{n-1}\,{\sqrt {b_{n-1}c_{n-1}}}&a_{n}\end{pmatrix}}\,.} と は 同じ固有値を持つこと に注意してください。 T {\displaystyle T} J {\displaystyle J}
コンピュータプログラミング 一般行列をヘッセンベルク形式に変換する変換は、エルミート行列を三角形式に変換する。そのため、多くの 固有値アルゴリズムは 、エルミート行列に適用する場合、まず入力のエルミート行列を（対称実）三角形式に変換する。 [22]
三重対角行列は、特殊な 格納方式 を用いることで、一般的な行列よりも効率的に格納することができます。例えば、 LAPACK Fortranパッケージは、 n次 の非対称三重対角行列を 3つの1次元配列に格納します。長さ n の配列の1つには対角要素が含まれ、長さ n − 1の配列の2つには 下対 角要素と 上対角 要素が含まれます。
アプリケーション 1次元拡散方程式または 熱方程式の空間離散化
∂ u ( t , x ) ∂ t = α ∂ 2 u ( t , x ) ∂ x 2 {\displaystyle {\frac {\partial u(t,x)}{\partial t}}=\alpha {\frac {\partial ^{2}u(t,x)}{\partial x^{2}}}} 2次中心 差分 を使用すると、
( ∂ u 1 ( t ) ∂ t ∂ u 2 ( t ) ∂ t ⋮ ∂ u N ( t ) ∂ t ) = α Δ x 2 ( − 2 1 0 … 0 1 − 2 1 ⋱ ⋮ 0 ⋱ ⋱ ⋱ 0 ⋮ 1 − 2 1 0 … 0 1 − 2 ) ( u 1 ( t ) u 2 ( t ) ⋮ u N ( t ) ) {\displaystyle {\begin{pmatrix}{\frac {\partial u_{1}(t)}{\partial t}}\\{\frac {\partial u_{2}(t)}{\partial t}}\\\vdots \\{\frac {\partial u_{N}(t)}{\partial t}}\end{pmatrix}}={\frac {\alpha }{\Delta x^{2}}}{\begin{pmatrix}-2&1&0&\ldots &0\\1&-2&1&\ddots &\vdots \\0&\ddots &\ddots &\ddots &0\\\vdots &&1&-2&1\\0&\ldots &0&1&-2\end{pmatrix}}{\begin{pmatrix}u_{1}(t)\\u_{2}(t)\\\vdots \\u_{N}(t)\\\end{pmatrix}}} 離散化定数 を用いています 。この行列は、 および を有する三角対角行列です 。注: 境界条件は明示的に指定されていませんが、この行列は ノイマン境界条件 （勾配ゼロ）に対応しています。 Δ x {\displaystyle \Delta x} a i = − 2 {\displaystyle a_{i}=-2} b i = c i = 1 {\displaystyle b_{i}=c_{i}=1}
参照
注記 ^ Thomas Muir (1960). 行列式理論に関する論文 . Dover Publications . pp. 516–525. ^ Horn, Roger A.; Johnson, Charles R. (1985). Matrix Analysis . Cambridge University Press. p. 28. ISBN 0521386322 。 ^ ホーン＆ジョンソン、174ページ ^ El-Mikkawy, MEA (2004). 「一般三角行列の逆行列について」. 応用数学と計算 . 150 (3): 669– 679. doi :10.1016/S0096-3003(03)00298-4. ^ Da Fonseca, CM (2007). 「いくつかの三角行列の固有値について」. 計算・応用数学ジャーナル . 200 : 283–286 . doi : 10.1016/j.cam.2005.08.047 . ^ Usmani, RA (1994). 「三角ヤコビ行列の逆行列」. 線形代数とその応用 . 212– 213: 413– 414. doi : 10.1016/0024-3795(94)90414-6 . ^ Hu, GY; O'Connell, RF (1996). 「対称三対角行列の解析的逆行列」. Journal of Physics A: Mathematical and General . 29 (7): 1511. Bibcode :1996JPhA...29.1511H. doi :10.1088/0305-4470/29/7/020. ^ Huang, Y.; McColl, WF (1997). 「一般三角行列の解析的逆行列」. Journal of Physics A: Mathematical and General . 30 (22): 7919. Bibcode :1997JPhA...30.7919H. doi :10.1088/0305-4470/30/22/026. ^ Mallik, RK (2001). 「三重対角行列の逆行列」. 線形代数とその応用 . 325 ( 1–3 ): 109–139 . doi : 10.1016/S0024-3795(00)00262-7 . ^ Kılıç, E. (2008). 「後方連分数による三重対角行列の逆行列の明示的な公式」. 応用数学・計算 . 197 : 345–357 . doi :10.1016/j.amc.2007.07.046. ^ Raf Vandebril、Marc Van Barel、Nicola Mastronardi (2008). 行列計算と半分離行列. 第1巻：線形システム . JHU Press. 定理1.38, p. 41. ISBN 978-0-8018-8714-7 。 ^ Meurant, Gerard (1992). 「対称三対角行列とブロック三対角行列の逆行列に関するレビュー」 . SIAM Journal on Matrix Analysis and Applications . 13 (3): 707– 728. doi :10.1137/0613045. ^ Bossu, Sebastien (2024). 「三対角行列と一対行列、そして2つの一対行列の逆和」. 線形代数とその応用 . 699 : 129–158 . arXiv : 2304.06100 . doi :10.1016/j.laa.2024.06.018. ^ ゴルブ, ジーン・H. ; ヴァン・ローン, チャールズ・F. (1996). 『行列計算』 （第3版）. ジョンズ・ホプキンス大学出版局. ISBN 0-8018-5414-8 。 ^ Noschese, S.; Pasquini, L.; Reichel, L. (2013). 「三角テプリッツ行列：特性と新たな応用」. 数値線形代数とその応用 . 20 (2): 302. doi :10.1002/nla.1811. ^ これは と書くこともできます。 なぜなら 、 Kulkarni, D.; Schmidt, D.; Tsui, SK (1999). "Eigenvalues of tridiagonal pseudo-Toeplitz matrices" (PDF) . Linear Algebra and Its Applications . 297 ( 1– 3): 63– 80. doi :10.1016/S0024-3795(99)00114-7. a + 2 b c cos ( k π / ( n + 1 ) ) {\displaystyle a+2{\sqrt {bc}}\cos(k\pi /{(n+1)})} cos ( x ) = − cos ( π − x ) {\displaystyle \cos(x)=-\cos(\pi -x)} ^ Parlett, BN (1997) [1980]. 対称固有値問題 . 応用数学の古典. 第20巻. SIAM. ISBN 0-89871-402-8 . OCLC 228147822. ^ Coakley, ES; Rokhlin, V. (2012). 「実対称三対角行列のスペクトルを計算するための高速分割統治アルゴリズム」 応用および計算調和解析 . 34 (3): 379– 414. doi : 10.1016/j.acha.2012.06.003 . ^ Dhillon, Inderjit Singh (1997). 対称三角固有値/固有ベクトル問題に対する新しいO(n2)アルゴリズム (PDF) (PhD). カリフォルニア大学バークレー校. p. 8. CSD-97-971, ADA637073. ^ ab Kreer, M. (1994). 「解析的出生・死亡過程：ヒルベルト空間アプローチ」. 確率過程とその応用 . 49 (1): 65– 74. doi :10.1016/0304-4149(94)90112-0. ^ Meurant, Gérard (2008年10月). 「三角行列」 (PDF) – 香港バプティスト大学計算数学研究所経由. ^ Eidelman, Yuli; Gohberg, Israel; Gemignani, Luca (2007-01-01). 「準分離行列のヘッセンベルグ形式と三重対角形式への高速縮約について」. 線形代数とその応用 . 420 (1): 86– 101. doi : 10.1016/j.laa.2006.06.028 . ISSN 0024-3795.
外部リンク LAPACK マニュアルの三角行列と二角行列。 Moawwad El-Mikkawy, Abdelrahman Karawia (2006). 「一般三角行列の逆行列」. 応用数学レター . 19 (8): 712– 720. doi : 10.1016/j.aml.2005.11.012 . 凝縮形式（ヘッセンベルグ形式、三重対角形式、二重対角形式）への簡約化のための高性能アルゴリズム C++ での三角線形システム ソルバー
