2007年(平成19年)東京大学後期-数学[2] - [別館]球面倶楽部零八式markIISR

2020.09.09記

本問のテーマ

QR法による固有値計算

2019.01.18記

QR法による固有値計算

(i) $A$ のQR分解を $A=QR$ とすると、 $Q=\displaystyle\frac{1}{\sqrt{a^2+b^2}}\begin{pmatrix} a & -b \\ b & a \end{pmatrix}$ となる。

(ii)よって $A$ をQR変換した行列を $B$ とおくと $B=RQ=Q^{-1}AQ$ となる。

(iii) $A$ のQR変換を繰り返し行なって得られる行列の列には極限が存在し、その極限として得られる行列を $D$ とする。

(iv) $A$ の固有値が「実数」で「絶対値が全て異なる」とき、 $D$ は $A$ の固有値を絶対値の大きい順番に並べた「対角行列」になる。

ここで、 $Q'=\begin{pmatrix} a & b \\ -b & a \end{pmatrix}$ とおくと $B=Q'A(Q')^{-1}$ と本問の設定になるので、 $a_n$ の極限は $\begin{pmatrix} 1 & 1 \\ 1 & 2 \end{pmatrix}$ の大きい方の固有値、 $c_n$ の極限は $\begin{pmatrix} 1 & 1 \\ 1 & 2 \end{pmatrix}$ の小さい方の固有値になる。

よって $\displaystyle a_n\to\frac{3+\sqrt{5}}{2}, b_n\to0, c_n\to\frac{3-\sqrt{5}}{2}$ となる。

[大人の解答]
(1) $B^{\top}=B$ だから $B$ は対称行列。 $tr(A)=tr(B),det(A)=det(B)$ 。

(2) $A$ のQR分解から $A=\begin{pmatrix} a & -b \\ b & a \end{pmatrix}\begin{pmatrix} 1 & \alpha \\ 0 & \beta \end{pmatrix}$ と書くことができる。このとき、 $B=\begin{pmatrix} 1 & \alpha \\ 0 & \beta \end{pmatrix}\begin{pmatrix} a & -b \\ b & a \end{pmatrix}$ であるから、 $(r,s)=(1,0)B=(1,\alpha)\begin{pmatrix} a & -b \\ b & a \end{pmatrix}$ となるので、 $r^2+s^2=(1+\alpha^2)(a^2+b^2)\geqq a^2+b^2$

(3) $\begin{pmatrix} 1 & 1 \\ 1 & 2 \end{pmatrix}$ は対角化可能で固有値の絶対値が大きい順に
$\displaystyle \frac{3+\sqrt{5}}{2}, \frac{3-\sqrt{5}}{2}$ であるから、 $\displaystyle a_n\to\frac{3+\sqrt{5}}{2}, b_n\to0, c_n\to\frac{3-\sqrt{5}}{2}$ となる。

[解答]
(1) $B^{\top}=B$ だから $B$ は対称行列。 $tr(A)=tr(B),det(A)=det(B)$ により $r+t=a+c,rt-s^2=ac-b^2$

(2) $\begin{pmatrix} \alpha \\ \beta\end{pmatrix}=\begin{pmatrix} a & b \\ -b & a \end{pmatrix}\begin{pmatrix} b \\ c \end{pmatrix}$ を用いて $A=\begin{pmatrix} a & -b \\ b & a \end{pmatrix}\begin{pmatrix} 1 & \alpha \\ 0 & \beta \end{pmatrix}$ と書くことができる。このとき、 $B=\begin{pmatrix} a & b \\ -b & a \end{pmatrix} \begin{pmatrix} a & -b \\ b & a \end{pmatrix}\begin{pmatrix} 1 & \alpha \\ 0 & \beta \end{pmatrix} \begin{pmatrix} a & b \\ -b & a \end{pmatrix}^{-1} =\begin{pmatrix} 1 & \alpha \\ 0 & \beta \end{pmatrix}\begin{pmatrix} a & -b \\ b & a \end{pmatrix}$ であるから、
$(r,s)=(1,0)B=(1,\alpha)\begin{pmatrix} a & -b \\ b & a \end{pmatrix}$ となるので、
$r^2+s^2=(1+\alpha^2)(a^2+b^2)\geq a^2+b^2$

(3) $A_n=\begin{pmatrix} a_n& b_n \\ b_n & c_n \end{pmatrix}$ とおく。

$\begin{pmatrix} \alpha_{n-1} \\ \beta_{n-1}\end{pmatrix}=\begin{pmatrix} a_{n-1} & b_{n-1} \\ -b_{n-1} & a_{n-1} \end{pmatrix}\begin{pmatrix} b_{n-1} \\ c_{n-1} \end{pmatrix}$ を用いて $A_{n-1}=\begin{pmatrix} a_{n-1} & -b_{n-1} \\ b_{n-1} & a_{n-1} \end{pmatrix}\begin{pmatrix} 1 & \alpha_{n-1} \\ 0 & \beta_{n-1} \end{pmatrix}$ と書くことができる。このとき、 $A_n=\begin{pmatrix} 1 & \alpha_{n-1} \\ 0 & \beta_{n-1} \end{pmatrix}\begin{pmatrix} a_{n-1} & -b_{n-1} \\ b_{n-1} & a_{n-1} \end{pmatrix}$ であるから、(2,1)成分から $b_n=\beta_{n-1}b_{n-1}$ が成立する。

一方、 $1=det(A_0)=det(A_n)=\beta_{n-1}(a_{n-1}^2+b_{n-1}^2)$ であるから、
$\displaystyle b_n=\frac{b_{n-1}}{a_{n-1}^2+b_{n-1}^2}$ である。

ここで(2)より $\displaystyle a_{n-1}^2+b_{n-1}^2\geqq a_0^2+b_0^2=2$ であるから、
$\displaystyle |b_n|\leqq\frac{1}{2}|b_{n-1}|$ となり、 $\displaystyle \lim_{n\to\infty} b_n=0$

$\displaystyle \lim_{n\to\infty} a_n+c_n=\lim_{n\to\infty} tr(A_n)=3$ 、
$\displaystyle \lim_{n\to\infty} a_nc_n=\lim_{n\to\infty}(det(A_n)+b_n^2)=1$ 、
$\displaystyle \lim_{n\to\infty} a_n^2=\lim_{n\to\infty} (a_n^2+b_n^2)\geqq a_0^2+b_0^2=2$
により、 $\displaystyle \lim_{n\to\infty}a_n=\frac{3+\sqrt{5}}{2}, \lim_{n\to\infty}c_n=\frac{3-\sqrt{5}}{2}$ となる。

QR法については
nalab.mind.meiji.ac.jp
を参照のこと。