ヘッセンベルグ行列

Hessenberg_matrix
線形代数では、ヘッセンベルグ行列は特別な種類の正方行列であり、「ほぼ」三角形です。正確には、上ヘッセンベルグ行列は最初の下対角 の下にゼロのエントリを持ち、下ヘッセンベルグ行列は最初の上対角の上にゼロのエントリを持ちます。カール・ヘッセンベルクにちなんで名付けられました。

コンテンツ
1 定義
1.1 上ヘッセンベルグ行列 1.2 下ヘッセンベルグ行列
2 例
3 コンピュータープログラミング
4 ヘッセンベルグ行列への還元
5 プロパティ
6 ヘッセンベルグ演算子
7 こちらもご覧ください
8 ノート
9 参考文献
10 外部リンク

定義

上ヘッセンベルグ行列
四角n × n
{ ntimes n}

マトリックス あ { A}

は、上ヘッセンベルグ形式または上ヘッセンベルグ行列であると言われます。 a I j 0
{ a_{i，j}=0}

すべてのために I j { i，j}
と I > j + 1
{ i>j+1}
j+1}””> . 上ヘッセンベルグ行列は、すべての下対角要素がゼロでない場合、つまり、a I +
1 私 0
{ a_{i+1，i}neq 0}

すべてのためにI ε {
1 … n− 1 }
{ iin {1，ldots ，n-1}}

.

下ヘッセンベルグ行列
四角n × n
{ ntimes n}

マトリックス あ { A}

転置する場合、下ヘッセンベルグ形式または下ヘッセンベルグ行列であると言われます
{表示スタイル}
は上ヘッセンベルグ行列、または同等の場合 a I j 0
{ a_{i，j}=0}

すべてのために I j { i，j}
と j > I + 1
{ j>i+1}
i+1}””> . 下ヘッセンベルグ行列は、すべての上対角要素がゼロでない場合、つまり、 a I 私+1 0
{ a_{i，i+1}neq 0}

すべてのためにI ε {
1 … n− 1 }
{ iin {1，ldots ，n-1}}

.

例
次の行列を検討してあ =
[ 14 2 3 3 4 1 7 0 2 40 41 42 431 3 ] { A={begin{bmatrix}1&4&2&3\3&4&1&7\0&2&3&4\0&0&1&3\end{bmatrix}}}
B =
[ 12 0 0 5 2 3 0 3 4 20 21 22 231 1 ] { B={begin{bmatrix}1&2&0&0\5&2&3&0\3&4&3&7\5&6&1&1\end{bmatrix}}}
ハ =
[ 12 0 0 5 2 0 0 3 4 20 21 22 231 1 ] { C={begin{bmatrix}1&2&0&0\5&2&0&0\3&4&3&7\5&6&1&1\end{bmatrix}}}

マトリックス あ { A}

上非縮小ヘッセンベルグ行列です。 B { B}

は低次非簡約ヘッセンベルグ行列であり、 ハ { C}

は下ヘッセンベルグ行列ですが、非簡約ではありません。

コンピュータープログラミング
多くの線形代数アルゴリズムは、三角行列に適用した場合に必要な計算量が大幅に少なくなり、この改善は多くの場合、ヘッセンベルグ行列にも引き継がれます。線形代数問題の制約により、一般行列を都合よく三角行列に簡約できない場合は、ヘッセンベルグ形式への簡約が次善の策であることがよく実際、ヘッセンベルグ形式への任意の行列の縮小は、有限数のステップで実現できます (たとえば、ユニタリ相似変換のハウスホルダー変換を介して)。ヘッセンベルグ行列の三角行列へのその後の縮小は、シフトされたQR因子分解などの反復手順によって実現できます。の固有値アルゴリズムでは、ヘッセンベルグ行列は、デフレ ステップと組み合わせた Shifted QR 因子分解によって三角行列にさらに縮小できます。一般行列を直接三角行列に縮小する代わりに、一般行列をヘッセンベルグ行列に縮小してからさらに三角行列に縮小すると、多くの場合、固有値問題のQR アルゴリズムに含まれる演算が節約されます。

ヘッセンベルグ行列への還元
どれでもn × n
{ ntimes n}

行列は、ハウスホルダー変換を使用した相似変換によってヘッセンベルグ行列に変換できます。このような変換の次の手順は、 Garcia & RogerによるA Second Course In Linear Algebraから改作されています。
させて あ { A}

任意の実数または複素数n × n
{ ntimes n}

行列、次にしましょうあ 」
{ A^{prime }}

なる( n− 1 ) × n
{ (n-1)times n}

の部分行列 あ { A}

の最初の行を削除して作成 あ { A}

そしてさせてa 1 」
{ mathbf {a} _{1}^{prime }}

の最初の列になるあ 」
{ A^{prime }}

. を構築する( n− 1 ) ×( n− 1 )
{ (n-1)times (n-1)}

世帯主マトリックス
Ⅴ1 I ( n − 1
) 2 w w ∗ | |
| | w | |
| | 2 { V_{1}=I_{(n-1)}-2{frac {ww^{*}}{||w||^{2}}}}

どこw = { | | a | |
2 e 1 − a a11 =0 | a | |
2 e 1+ a1 ¯ | a1 |x ， a11 ≠ 0 { w={begin{cases}||mathbf {a} _{1}^{prime}||_{2}mathbf {e} _{1}-mathbf {a} _{ 1}^{プライム};;;;;;;;，;;;a_{11}^{プライム}=0\||mathbf {a} _{1}^{prime }||_{2}mathbf {e} _{1}+{frac {overline {a_{11}^{prime }}}{|a_{11}^ {prime }|}}mathbf {x} ;;;，;;;a_{11}^{prime}neq 0\end{cases}}}

この世帯主マトリックスがマッピングされますa 1 」
{ mathbf {a} _{1}^{prime }}
| |
| |a 1 」
| |
| |e 1
{ ||mathbf {a} _{1}^{prime}||mathbf {e} _{1}}

したがって、ブロック行列
う1
[ 10 0Ⅴ 1 ]
{ U_{1}={begin{bmatrix}1&mathbf {0} \mathbf {0} &V_{1}end{bmatrix}}}

マトリックスをマッピングします あ { A}

マトリックスへ
う1
{ U_{1}A}

最初の列の 2 番目のエントリの下にはゼロしかありません。今構築する( n− 2 ) ×( n− 2 )
{ (n-2)times (n-2)}

世帯主マトリックスⅤ 2
{ V_{2}}

と同様の方法でⅤ 1
{ V_{1}}

そのようなⅤ 2
{ V_{2}}

の最初の列をマップしますあ 」 」 { A^{prime prime }}
| |
| |a 1 」 」 | |
| |e 1
{ ||mathbf {a} _{1}^{prime prime }||mathbf {e} _{1}}

、 どこあ 」 」 { A^{prime prime }}

の部分行列ですあ 」
{ A^{prime }}

の最初の行と最初の列を削除することによって構築されますあ 」
{ A^{prime }}

、次にしましょう
う2
[ 10 0 1 0 0Ⅴ 2 ]
{ U_{2}={begin{bmatrix}1&0&0\0&1&0\0&0&V_{2}end{bmatrix}}}

どのマップ
う1
{ U_{1}A}

マトリックスへう 2
う1
{ U_{2}U_{1}A}

サブ対角線の最初と 2 番目のエントリの下にはゼロしかありません。今構築するⅤ 3
{ V_{3}}

その後う 3
{ U_{3}}

同様の方法で、ただしマトリックスに対して あ 」
{ A^{prime prime prime }}

の最初の行と最初の列を削除して作成されたあ 」 」 { A^{prime prime }}

前の手順と同様に進みます。このように合計n − 2
{ n-2}

ステップ。
そのことに気づき、まず k { k}

任意の行n × n
{ ntimes n}

行列は による乗算で不変ですう k ∗
{ U_{k}^{*}}

右から、う k
{ U_{k}}

、したがって、任意の行列は、次の形式の相似変換によって上ヘッセンベルグ行列に変換できます。 う ( n − 2 ) ( …( う 2 ( う1 う 1 ∗ ) う 2∗ ) … ) う( n − 2) ∗ = う( n − 2 ) …う 2 う1 ( う( n − 2 ) …う 2 う 1 ) ∗= う あ う ∗
{ U_{(n-2)}(dots (U_{2}(U_{1}AU_{1}^{*})U_{2}^{*})dots )U_{(n- 2)}^{*}=U_{(n-2)}dots U_{2}U_{1}A(U_{(n-2)}dots U_{2}U_{1})^{* }=UAU^{*}}

.

プロパティ
為にn ε { 1 2 }
{ nin {1，2}}

、それは空虚に真実ですn × n
{ ntimes n}

行列は上ヘッセンベルグと下ヘッセンベルグの両方です。
ヘッセンベルグ行列と三角行列の積もまたヘッセンベルグです。より正確に言えば、 あ { A}

上ヘッセンベルグであり、 T { T}

は上三角なので、あ T
{ AT}
と T あ
{ TA}

上ヘッセンベルクです。
上ヘッセンベルグと下ヘッセンベルグの両方である行列は三重対角行列であり、対称またはエルミート ヘッセンベルグ行列が重要な例です。エルミート行列は、三重対角実対称行列に縮小できます。

ヘッセンベルグ演算子
ヘッセンベルグ演算子は、無限次元のヘッセンベルグ行列です。これは一般に、ヤコビ演算子を、あるドメイン上の2 乗可積分正則関数の空間(つまり、バーグマン空間) の直交多項式系に一般化したものとして発生します。この場合、ヘッセンベルグ演算子は右シフト演算子です。 S { S}

、 によって与えられた
[ Sへ ]( ぜ) = ぜ へ( ぜ ) { (z)=zf(z)}
. ヘッセンベルグ演算子の各主要部分行列の固有値は、その部分行列の特性多項式によって与えられます。これらの多項式はバーグマン多項式と呼ばれ、バーグマン空間の直交多項式の基底を提供します。

こちらもご覧ください
ヘッセンベルク多様体

ノート
^ Horn & Johnson (1985) ， page 28; Stoer & Bulirsch (2002)、251 ページ
^ Biswa Nath Datta (2010) Numerical Linear Algebra and Applications、第 2 版、Society for Industrial and Applied Mathematics (SIAM) ISBN  978-0-89871-685-6、p. 307
^ Horn & Johnson (1985)、35ページ
^ ラモン・ガルシア、ステファン。ホーン、ロジャー (2017)。線形代数の 2 番目のコース。ISBN
 9781107103818.
^ https://www.cs.cornell.edu/~bindel/class/cs6210-f16/lec/2016-10-21.pdf
^ “”LAPACK の計算ルーチン (固有値)”” . sites.science.oregonstate.edu . 2020-05-24取得。

参考文献
ホーン、ロジャー A.; Johnson， Charles R. (1985)， Matrix Analysis ， Cambridge University Press ， ISBN 978-0-521-38632-6.
ストア、ヨーゼフ。Bulirsch， Roland (2002)， Introduction to Numerical Analysis (3rd ed.)， Berlin， New York: Springer-Verlag ， ISBN 978-0-387-95452-3.
WH を押します。テウコルスキー、SA; ベタリング、WT; Flannery， BP (2007)， “”Section 11.6.2. Reduce to Hessenberg Form” ， Numerical Recipes: The Art of Scientific Computing (3rd ed.)， New York: Cambridge University Press， ISBN 978-0-521-88068-8

外部リンク
MathWorld のHessenberg 行列。
PlanetMathのヘッセンベルグ行列。
圧縮 (ヘッセンベルグ、三重対角、二対角) 形式への縮小のための高性能アルゴリズム”