3.5.P5
演習 3.5.5 Lanczos tridiagonalization algorithm（ランチョス三重対角化アルゴリズム）
\( A \in M_n \) と \( x \in \mathbb{C}^n \) が与えられている。次を定義する：
X = [x, Ax, A^2 x, \dots, A^{n-1} x]
列ベクトルの集合 \( X \) はクリロフ列（Krylov sequence）を形成すると言われる。ここで、\( X \) は非特異と仮定する。
(a) \( X^{-1}AX \) が \( A \) の特性多項式に対するコンパニオン行列（companion matrix, 3.3.12）であることを示せ。
A =
\begin{bmatrix}
0 & & & & -a_0 \\
1 & 0 & & & -a_1 \\
& 1 & \ddots & & \vdots \\
& & \ddots & 0 & -a_{n-2} \\
0 & & & 1 & -a_{n-1}
\end{bmatrix} \in M_n
(b) \( R \in M_n \) が任意の非特異上三角行列であり、\( S = X R \) とするとき、\( S^{-1} A S \) が上ヘッセンベルグ行列（upper Hessenberg form）であることを示せ。
(c) \( y \in \mathbb{C}^n \) とし、次を定義する：
Y = [y, A^* y, (A^*)^2 y, \dots, (A^*)^{n-1} y]
ここで \( Y \) は非特異であり、かつ \( Y^* X \) が \( L D U \) と書けるとする。ここで \( L \) は下三角、\( U \) は上三角かつ非特異、\( D \) は対角かつ非特異である。このとき、非特異上三角行列 \( R \) と \( T \) が存在して、\((X R)^{-1} = T^* Y^* \) かつ \( T^* Y^* A X R \) が三重対角かつ \( A \) に相似であることを示せ。
(d) \( A \in M_n \) がエルミート行列（Hermitian）である場合、この考え方を用いて \( A \) に相似な三重対角エルミート行列を生成するアルゴリズムを説明せよ。
ヒント
クリロフ列 \( X=[x,Ax,\dots,A^{n-1}x] \) による基底変換を考えると、\( A \) の作用は「シフト＋最終列」で表され、コンパニオン行列になる。
さらに上三角行列による基底変換はヘッセンベルグ構造を保つ。双対列 \( Y \) を導入して \( Y^*X \) を \( LDU \) 分解することで、三重対角化が得られる。
解答例
(a) \( X=[x,Ax,\dots,A^{n-1}x] \) とする。すると
AX = [Ax,A^2x,\dots,A^n x]
となる。ここで \( A^n x \) は特性多項式 \( \chi_A(t)=t^n+a_{n-1}t^{n-1}+\cdots+a_0 \) を用いて \( A^n x = -a_{n-1}A^{n-1}x - \cdots - a_0 x \) と表される。よって基底 \( X \) に関する表現は
X^{-1}AX =
\begin{bmatrix}
0 & & & & -a_0 \\
1 & 0 & & & -a_1 \\
& 1 & \ddots & & \vdots \\
& & \ddots & 0 & -a_{n-2} \\
0 & & & 1 & -a_{n-1}
\end{bmatrix}
となり、コンパニオン行列である。
(b) \( S=XR \) とすると \( S^{-1}AS = R^{-1}(X^{-1}AX)R \) である。コンパニオン行列は上ヘッセンベルグであり、上三角行列との相似変換でもその構造は保たれる。したがって \( S^{-1}AS \) は上ヘッセンベルグ行列となる。
(c) \( Y=[y,A^*y,\dots,(A^*)^{n-1}y] \) とし、\( Y^*X=LDU \) と分解する。ここで
R = U^{-1}, \quad T = (LD)^{-1}
とおけば \( (XR)^{-1} = R^{-1}X^{-1} = U X^{-1} = T^*Y^* \) が成り立つ。またこの変換により \( T^*Y^* A X R \) は上ヘッセンベルグかつ下ヘッセンベルグとなり、三重対角行列となる。よってこれは \( A \) に相似である。
(d) \( A \) がエルミートのとき、\( y=x \) と取ると \( Y=X \) となる。このとき上記の構成により 直交（ユニタリ）基底が得られ、反復的に
v_{k+1} = Av_k - \alpha_k v_k - \beta_{k-1} v_{k-1}
という3項漸化式で基底を構成できる。このとき得られる行列表現は三重対角エルミート行列となる。これがランチョス三重対角化アルゴリズムである。
行列解析の総本山
総本山の目次📚
記号の意味🔎
コメント