QR法ハウスホルダー行列についてハウスホルダー行列のおさらいから話を始めよう。ハウスホルダー行列とはエルミート性とユニタリー性を兼ね備えた行列だった。主な用途として、たとえばこのハウスホルダー行列により、ある正方行列が対称であれば三重対角行列に,非対称であればヘッセンベルグ行列にそれぞれ変置換することができる。\end{array}\right)\end{eqnarray}またハウスホルダー行列のユニタリー性を利用して、ある行列$A$をユニタリー行列$Q$と上三角行列$R$に分解することができる。これをQR分解という。QRさらには、このQR分解を繰り返すことで、非特異行列$A$の固有値の数値計算をすることができる。このQR法についての概要が本記事の趣旨になる。行列$A$の固有値について|λ_{1}|>|λ_{2}|>...>|λ_{n}|>0が成り立っているものとする。QR法による固有値計算(1)まず$A$をQR分解しよう。これを$A_{0}$とする。...(_{1-1})\\$Q_{0}$,$R_{0}$については以下の通りとなる。...(_{1-1-b})次に$R_{0}$,$Q_{0}$により次のような行列を作る。これを$A_{1}$としよう。この$A_{1}$を$Q_{1}$,$R_{1}$にQR分解する。\\先ほどと同様に$R_{1}$,$Q_{1}$より行列$A_{2}$を作り、これを$Q_{2}$,$R_{2}$にQR分解しよう。R_{1}A_{1}R^{-1}_{1}=R_{1}R_{0}A_{0}R^{-1}_{0}R^{-1}_{1}=\tilde{R_{2}}A_{0}\tilde{R^{-1}_{2}}..._{(1-3-d)}\\がそれぞれ得られる。R_{N-1}Q_{N-1}=R_{N-1}A_{N-1}R^{-1}_{N-1}=...=\tilde{R_{N}}A_{0}\tilde{R^{-1}_{N}}..._{(1-4-c)}\\\end{align}がそれぞれ得られる。この$Q_{t}$について、ユニタリー行列$X_{t}$により、次の関係が成り立つとしよう。※なお、$X_{0}=I$とする。..._{(1-5)}\\(t=0,1,...N-1)式(1-5)を踏まえて$\tilde{Q_{N}}=Q_{0}Q_{1}...Q_{N-1}$を計算すれば、\begin{align}\tilde{Q_{N}}&=Q_{0}Q_{1}...Q_{N-1}\\&=(X^{H}_{0}X_{1})(X^{H}_{1}X_{2})...(X^{H}_{N-1}X_{N})\\&=X^{H}_{0}X_{N}..._{(1-6)}\\\end{align}が得られる。なる行列$\tilde{A}$を利用することで式(1-4-b),式(1-6)より次式が得られる。&=\tilde{Q^{H}_{N}}A_{0}\tilde{Q_{N}}=X^{H}_{N}X_{0}A_{0}X^{H}_{0}X_{N}\\&=X^{H}_{N}\tilde{A}X_{N}..._{(1-8)}\\\end{align}ここで$\tilde{Q_{t}}\tilde{R_{t}}_{(t=0,1,...N)}$について以下のような関係が成り立っていることを確認しておこう。X_{N}\tilde{R_{N}}=\tilde{A^N}X_{0}..._{(1-9)}\\を得ることができる。QR法による固有値計算(2)$\tilde{A}$が正規行列であれば対角化できる。$Z$を非特異行列,$Λ$を$A$の固有値を対角成分にもつ対角行列とすれば、以下の式(2-1)が得られる。\tilde{A}=ZΛZ^{-1}..._{(2-1)}\\さてこの$Z$を次のように$QR$分解しよう。Z=Q_{z}R_{z}..._{(2-2)}\\式(2-1),(2-2)を踏まえれば、Q^{H}_{z}\tilde{A}Q_{z}=R_{z}ΛR^{-1}_{z}..._{(2-3)}\\\begin{align}\tilde{A}^{N}&=(ZΛZ^{-1})^{N}=ZΛ^{N}Z^{-1}\\&=Q_{z}R_{z}Λ^{N}R^{-1}_{z}Q^{H}_{z}..._{(2-4)}\\\end{align}となる。$L$を対角成分がすべて1からなる下三角行列,$U$を上三角行列として、$Z^{H}X_{0}$を式(2-5)のように$LU分解$する。$L$,$Λ^{N}$,$R_{z}$からなる$Ψ_{N}$を式(2-6)のように定める。=R_{z}Λ^{N}LΛ^{-N}R^{-1}_{z}..._{(2-6)}式(2-4),(2-5),(2-6)に基づいて$\tilde{A^{N}}X_{0}$を考えよう。)(R_{z}Λ^{N}U)\\&=Q_{z}Ψ_{N}(R_{z}Λ^{N}U)..._{(2-7)}\\\end{align}が得られる。ここで$Ψ_{N}$に着目しよう。\hat{Q_{N}}=I_{n}$となるようにQR分解する。\hat{Q_{N}}\hat{R_{N}}=I_{n}\\となる。\breve{Q}\breve{R}&=I_{n}..._{(2-9)}\end{align}となる。※$\breve{Q}$をユニタリ行列,$\breve{R}$を上三角行列として以下のように置いた。\begin{align}\breve{Q}&=X^{H}_{N}Q_{z}\hat{Q_{N}}\\\breve{R}&=\hat{R_{N}}R_{z}Λ^{N}U\tilde{R^{-1}_{N}}\end{align}対角成分の絶対値が全て1からなる対角行列のことをユニタリー対角行列という。これを$D_{N}$としよう。Q_{z}\hat{Q_{N}}&=X_{N}D^{H}_{N}..._{(2-10)}\end{align}が成り立つ。Q_{z}\hat{Q_{N}}=Q_{z}..._{(2-11)}が得られる。ここで式(1-8)を思い出してほしい。=X^{H}_{N}\tilde{A}X_{N}..._{(1-8)}\\この式(1-8)について、左から$D_{N}$右から$D^{H}_{N}$をそれぞれかけることで、D_{N}A_{N}D^{H}_{N}=D_{N}X^{H}_{N}\tilde{A}X_{N}D^{H}_{N}..._{(2-12)}\\が得ることができる。D_{N}X^{H}_{N}\tilde{A}X_{N}D^{H}_{N}\\=Q^{H}_{z}\tilde{A}Q_{z}=R_{z}ΛR^{-1}_{z}..._{(2-13)}が成立する。※$R_{z}ΛR^{-1}_{z}$とは以下のような上三角行列である。これを$S$と置こう。\end{array}\right)\end{eqnarray}式(2-13)より$\tilde{A}=Q_{z}SQ^{H}_{z}$となるが、これは$\tilde{A}$のシューア分解に他ならない.つまるところ、QR分解を繰り返すことで、行列$A$は$Q_{z}SQ^{H}_{z}$に収束する。この性質を利用して$A$の固有値の数値解を求めているのがQR法になるわけだ。upLoginユーザーは見つかりませんでした。