跳到主要内容

中央大学 理工学研究科 情報工学専攻 2024年8月実施 問題III

标签：

Author​

祭音Myyura (co-authored with GPT 6 Astra)

Description​

問題 I は必答。問題 II～V のうち，2 問を選んで解答すること。

つぎの設問に答えよ。

  1. nn 次正方行列のヘッセンベルグ型行列 B=(bij)B=(b_{ij}) とは，3≤i≤n, 1≤j≤i−23\le i\le n,\ 1\le j\le i-2 について，bij=0b_{ij}=0 である行列である。n=5n=5 の例を以下に示す。「∗*」は非零要素を示す。BB が対称行列のときは，右のように三重対角行列である：

    B=(∗∗∗∗∗∗∗∗∗∗0∗∗∗∗00∗∗∗000∗∗),B=(∗∗000∗∗∗000∗∗∗000∗∗∗000∗∗).B=\begin{pmatrix} *&*&*&*&*\\ *&*&*&*&*\\ 0&*&*&*&*\\ 0&0&*&*&*\\ 0&0&0&*&* \end{pmatrix},\qquad B=\begin{pmatrix} *&*&0&0&0\\ *&*&*&0&0\\ 0&*&*&*&0\\ 0&0&*&*&*\\ 0&0&0&*&* \end{pmatrix}.

    nn 次正方行列 AA の固有値を数値計算する場合に，AA の固有値を直接計算するのではなく，まず，nn 次正則正方行列 SS により，ヘッセンベルグ型行列 B=S−1ASB=S^{-1}AS に変換しておき，BB の固有値を計算する手法が知られている。

    この手法において，(i) AA の固有値・固有ベクトルと，BB の固有値・固有ベクトルとの関係を説明し，(ii) 数値計算手法として，このような変換を行う利点について，説明せよ。

  2. nn 次元ベクトル u (≠0)u\ (\ne0) に関するハウスホルダ変換の行列 H(u)H(u) とは，次式で定義される行列である。

    H(u)≡I−2uuTuTuH(u)\equiv I-2\frac{uu^{\mathsf T}}{u^{\mathsf T}u}

    この行列 H(u)H(u) について，H(u)H(u)H(u)H(u) の値を求め，H(u)H(u) の逆行列を求めよ。

  3. 2 個のハウスホルダ変換を用いて，つぎの実対称行列 AA を三重対角行列 B=S−1ASB=S^{-1}AS に変換せよ。係数は有理数で計算し，途中経過も明記すること。

    A=(1122155−225−3−52−2−52)A=\begin{pmatrix} 1&1&2&2\\ 1&5&5&-2\\ 2&5&-3&-5\\ 2&-2&-5&2 \end{pmatrix}

题目描述​

问题 I 必答；问题 II～V 中选答 2 题。回答下列问题。

  1. nn 阶方阵 B=(bij)B=(b_{ij}) 如果满足：对 3≤i≤n, 1≤j≤i−23\le i\le n,\ 1\le j\le i-2，均有 bij=0b_{ij}=0，则称为 Hessenberg 型矩阵。n=5n=5 的例子如下，其中“∗*”表示非零元素。当 BB 为对称矩阵时，它是右侧所示的三对角矩阵：

    B=(∗∗∗∗∗∗∗∗∗∗0∗∗∗∗00∗∗∗000∗∗),B=(∗∗000∗∗∗000∗∗∗000∗∗∗000∗∗).B=\begin{pmatrix} *&*&*&*&*\\ *&*&*&*&*\\ 0&*&*&*&*\\ 0&0&*&*&*\\ 0&0&0&*&* \end{pmatrix},\qquad B=\begin{pmatrix} *&*&0&0&0\\ *&*&*&0&0\\ 0&*&*&*&0\\ 0&0&*&*&*\\ 0&0&0&*&* \end{pmatrix}.

    数值计算 nn 阶方阵 AA 的特征值时，有一种方法不是直接计算 AA 的特征值，而是先用 nn 阶可逆方阵 SS 将其变换成 Hessenberg 型矩阵 B=S−1ASB=S^{-1}AS，再计算 BB 的特征值。

    对该方法，(i) 说明 AA 与 BB 的特征值、特征向量之间的关系；(ii) 说明在数值计算中进行这种变换的优点。

  2. 关于非零 nn 维向量 uu 的 Householder 变换矩阵定义为

    H(u)≡I−2uuTuTu.H(u)\equiv I-2\frac{uu^{\mathsf T}}{u^{\mathsf T}u}.

    求 H(u)H(u)H(u)H(u) 的值及 H(u)H(u) 的逆矩阵。

  3. 使用两次 Householder 变换，将下面的实对称矩阵 AA 变换为三对角矩阵 B=S−1ASB=S^{-1}AS。各系数用有理数计算，并明确写出中间过程。

    A=(1122155−225−3−52−2−52).A=\begin{pmatrix} 1&1&2&2\\ 1&5&5&-2\\ 2&5&-3&-5\\ 2&-2&-5&2 \end{pmatrix}.

Kai​

1. (i) 固有値・固有ベクトルの関係​

相似変換によって特性多項式は変化しない。実際，

det⁡(λI−B)=det⁡(S−1(λI−A)S)=det⁡(λI−A).\begin{aligned} \det(\lambda I-B) &=\det\bigl(S^{-1}(\lambda I-A)S\bigr)\\ &=\det(\lambda I-A). \end{aligned}

したがって A,BA,B の固有値は代数的重複度も含めて一致する。また，

Av=λv⟺B(S−1v)=λ(S−1v).Av=\lambda v\quad\Longleftrightarrow\quad B(S^{-1}v)=\lambda(S^{-1}v).

すなわち，AA の固有ベクトル vv に対応する BB の固有ベクトルは S−1vS^{-1}v であり，BB の固有ベクトル ww からは AA の固有ベクトル SwSw が得られる。

1. (ii) 数値計算上の利点​

ヘッセンベルグ型の零要素の構造を利用すると，固有値を求める QR 反復の 1 回の計算量を，密行列の O(n3)O(n^3) から O(n2)O(n^2) に減らせる。さらに対称行列の場合は三重対角化され，固有値だけを求める三重対角 QR 反復では 1 回の更新を O(n)O(n) で行える。対称三重対角行列の格納も O(n)O(n) 個の要素で済む。

この前処理は一度だけ行えばよく，反復中も構造を保てるため，反復ごとの計算を軽くできる。また，ハウスホルダ変換などにより SS を直交行列に選べば S−1=STS^{-1}=S^{\mathsf T} であり，2 ノルムを保つので，条件の悪い一般の相似変換による誤差の増幅を避けられる。QR 法の計算量と直交相似変換

2. ハウスホルダ行列の二乗と逆行列​

P=uuT/(uTu)P=uu^{\mathsf T}/(u^{\mathsf T}u) とおくと，

P2=u(uTu)uT(uTu)2=P.P^2=\frac{u(u^{\mathsf T}u)u^{\mathsf T}}{(u^{\mathsf T}u)^2}=P.

したがって，

H(u)2=(I−2P)2=I−4P+4P2=I.H(u)^2=(I-2P)^2=I-4P+4P^2=I.

よって，

H(u)H(u)=I,H(u)−1=H(u).\boxed{H(u)H(u)=I,\qquad H(u)^{-1}=H(u)}.

さらに H(u)T=H(u)H(u)^{\mathsf T}=H(u) であるので，実ベクトル uu に対する H(u)H(u) は直交行列でもある。

3. 二段階の三重対角化​

第 1 段階。 第 1 列の下側のベクトル (1,2,2)T(1,2,2)^{\mathsf T} の長さは 33 である。これを (3,0,0)T(3,0,0)^{\mathsf T} に写すため，差 (1,2,2)T−(3,0,0)T=(−2,2,2)T(1,2,2)^{\mathsf T}-(3,0,0)^{\mathsf T}=(-2,2,2)^{\mathsf T} に平行なベクトルを用いる。

u1=(0−111),u_1=\begin{pmatrix}0\\-1\\1\\1\end{pmatrix},
H1=H(u1)=(1000013232302313−23023−2313).H_1=H(u_1)=\begin{pmatrix} 1&0&0&0\\ 0&\frac13&\frac23&\frac23\\ 0&\frac23&\frac13&-\frac23\\ 0&\frac23&-\frac23&\frac13 \end{pmatrix}.

左右から H1H_1 を掛けると，

A(1)=H1AH1=(13003−334039−104−1−2).A^{(1)}=H_1AH_1 =\begin{pmatrix} 1&3&0&0\\ 3&-3&3&4\\ 0&3&9&-1\\ 0&4&-1&-2 \end{pmatrix}.

第 2 段階。 第 2 列の下側の (3,4)T(3,4)^{\mathsf T} の長さは 55。これを (5,0)T(5,0)^{\mathsf T} に写すため，(3,4)T−(5,0)T=(−2,4)T(3,4)^{\mathsf T}-(5,0)^{\mathsf T}=(-2,4)^{\mathsf T} を用いる。

u2=(00−12),u_2=\begin{pmatrix}0\\0\\-1\\2\end{pmatrix},
H2=H(u2)=(100001000035450045−35).H_2=H(u_2)=\begin{pmatrix} 1&0&0&0\\ 0&1&0&0\\ 0&0&\frac35&\frac45\\ 0&0&\frac45&-\frac35 \end{pmatrix}.

第 1，2 座標を固定しているため，既に零になった第 1 行・第 1 列の成分を変えない。したがって，

B=H2A(1)H2=(13003−35005150056).\boxed{B=H_2A^{(1)}H_2 =\begin{pmatrix} 1&3&0&0\\ 3&-3&5&0\\ 0&5&1&5\\ 0&0&5&6 \end{pmatrix}}.

ここで

S=H1H2=(10000131415215023−1323023−215−1115)S=H_1H_2 =\begin{pmatrix} 1&0&0&0\\ 0&\frac13&\frac{14}{15}&\frac2{15}\\ 0&\frac23&-\frac13&\frac23\\ 0&\frac23&-\frac2{15}&-\frac{11}{15} \end{pmatrix}

とすれば，S−1=H2H1=STS^{-1}=H_2H_1=S^{\mathsf T} より B=S−1ASB=S^{-1}AS である。すべての行列要素は有理数で求められている。

Reference​

本页目录