最小二乗問題の求解
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/09/10 15:00 UTC 版)
GMRES法では、 ‖ H ~ n y n − e 1 ‖ {\displaystyle \|{\tilde {H}}_{n}y_{n}-e_{1}\|} を最小化するベクトル y n {\displaystyle y_{n}} を見つける必要がある。これはQR分解を計算することで実現できる。すなわち、 Ω n H ~ n = R ~ n . {\displaystyle \Omega _{n}{\tilde {H}}_{n}={\tilde {R}}_{n}.} を満たすn+1次正方直交行列Ωnとn+1×n次上三角行列 R ~ n {\displaystyle {\tilde {R}}_{n}} を計算する。三角行列の行数は列数より1多いので、最下行はすべて零である。したがって、 R n {\displaystyle R_{n}} をn×n次三角行列として、これを R ~ n = [ R n 0 ] , {\displaystyle {\tilde {R}}_{n}={\begin{bmatrix}R_{n}\\0\end{bmatrix}},} と分解することができる。 QR分解は、零の行と1列分の値が異なるだけなので、簡単に更新することができる。つまりhn = (h1n, … hnn)Tとして H ~ n + 1 = [ H ~ n h n 0 h n + 1 , n ] {\displaystyle {\tilde {H}}_{n+1}={\begin{bmatrix}{\tilde {H}}_{n}&h_{n}\\0&h_{n+1,n}\end{bmatrix}}} が成り立つので、 [ Ω n 0 0 1 ] H ~ n + 1 = [ R n r k 0 ρ 0 σ ] {\displaystyle {\begin{bmatrix}\Omega _{n}&0\\0&1\end{bmatrix}}{\tilde {H}}_{n+1}={\begin{bmatrix}R_{n}&r_{k}\\0&\rho \\0&\sigma \end{bmatrix}}} は三角行列に近く、σが0であれば三角行列である。これを更新するためには、: c n = ρ ρ 2 + σ 2 and s n = σ ρ 2 + σ 2 {\displaystyle c_{n}={\frac {\rho }{\sqrt {\rho ^{2}+\sigma ^{2}}}}\quad {\mbox{and}}\quad s_{n}={\frac {\sigma }{\sqrt {\rho ^{2}+\sigma ^{2}}}}} としてギブンス回転 G n = [ I n − 1 0 0 0 c n s n 0 − s n c n ] {\displaystyle G_{n}={\begin{bmatrix}I_{n-1}&0&0\\0&c_{n}&s_{n}\\0&-s_{n}&c_{n}\end{bmatrix}}} を行えばよい。これにより、 Ω n + 1 = G n [ Ω n 0 0 1 ] {\displaystyle \Omega _{n+1}=G_{n}{\begin{bmatrix}\Omega _{n}&0\\0&1\end{bmatrix}}} を得る。 Ω n + 1 H ~ n + 1 = [ R n r n 0 r n n 0 0 ] with r n n = ρ 2 + σ 2 {\displaystyle \Omega _{n+1}{\tilde {H}}_{n+1}={\begin{bmatrix}R_{n}&r_{n}\\0&r_{nn}\\0&0\end{bmatrix}}\quad {\text{with}}\quad r_{nn}={\sqrt {\rho ^{2}+\sigma ^{2}}}} は三角行列である。 QR分解が与えられると、最小化問題は ‖ H ~ n y n − e 1 ‖ = ‖ Ω n ( H ~ n y n − e 1 ) ‖ = ‖ R ~ n y n − Ω n e 1 ‖ {\displaystyle \|{\tilde {H}}_{n}y_{n}-e_{1}\|=\|\Omega _{n}({\tilde {H}}_{n}y_{n}-e_{1})\|=\|{\tilde {R}}_{n}y_{n}-\Omega _{n}e_{1}\|} から容易に解くことができる。実際、gn ∈ Rn、γn ∈ Rとして、ベクトル Ω n e 1 {\displaystyle \Omega _{n}e_{1}} を g ~ n = [ g n γ n ] {\displaystyle {\tilde {g}}_{n}={\begin{bmatrix}g_{n}\\\gamma _{n}\end{bmatrix}}} と表すと、これは ‖ H ~ n y n − e 1 ‖ = ‖ R ~ n y n − Ω n e 1 ‖ = ‖ [ R n 0 ] y − [ g n γ n ] ‖ {\displaystyle \|{\tilde {H}}_{n}y_{n}-e_{1}\|=\|{\tilde {R}}_{n}y_{n}-\Omega _{n}e_{1}\|=\left\|{\begin{bmatrix}R_{n}\\0\end{bmatrix}}y-{\begin{bmatrix}g_{n}\\\gamma _{n}\end{bmatrix}}\right\|} と書ける。これを最小化するベクトルyは y n = R n − 1 g n {\displaystyle y_{n}=R_{n}^{-1}g_{n}} で与えられる。 g n {\displaystyle g_{n}} の更新も容易に行うことができる。
※この「最小二乗問題の求解」の解説は、「GMRES法」の解説の一部です。
「最小二乗問題の求解」を含む「GMRES法」の記事については、「GMRES法」の概要を参照ください。
- 最小二乗問題の求解のページへのリンク
