2024-03-28T09:19:01Z
https://repository.nii.ac.jp/oai
oai:repository.nii.ac.jp:00000355
2022-12-16T07:50:35Z
136
NIIテクニカル・レポート (NII-2001-003J):特異な系に対する共役残差法の収束性について
NII Technical Report (NII-2001-003J):On the Convergence of the Conjugate Residual Method for Singular Systems
速水, 謙
Hayami, Ken
テクニカルレポート
Technical Report
非対称で特異な実行列$ A $を係数行列とする連立一次方程式$ A \bx = \bb $ または最小二乗問題$ {\displaystyle \min_{\bx \in \rn} \| \bb - A \bx \|_2 } $に対して, クリロフ部分空間法に属する反復解法である共役残差法(Conjugate Residual method: CR法)を適用することを考える. このとき, $ R(A)^\perp = \ker A $の場合は, CR法を$ R(A) $と$ \ker A $の成 分に 分離できることを示し, その場合にCR法が任意の$ \bb $と初期近似解$ \bx_0 $に対 して 破綻なく収束するための必要十分条件は, $ A $の対称部$ M(A) $が半定値, かつ$ \rank \, M(A) = \rank A $であることを示し, そのとき最小二乗解が得られ ることを示す. さらに, $ \bx_0 \in R(A) $のときは近似解はノルム最小の最小二乗解(擬逆解)に収 束する. 次に, $ R(A) \oplus \ker A = \rn, $かつ$ \bb \in R(A) $のときに, CR法が任意の初期近似解に対して最小二乗解に破綻することなく収束するための 必要十分条件を導く. 最後に, 上記の二つの場合に相当する常微分方程式の二点境界値問題の差分近似の 例を取り上げる.
Consider applying the Conjugate Residual (CR) method to¡¡systems of linear equations $ A \bx = \bb $ or least squares problems $ {\displaystyle \min_{\bx \in \rn} \| \bb - A \bx \|_2 } $, where $ A \in \rnn $ is singular and nonsymmetric. First, we prove the following. When $ R(A)^\perp = \ker A $, the CR method can be decomposed into the $ R(A) $ and $ \ker A $ components, and the necessary and sufficient condition for the method to converge to the least squares solution without breaking down for arbitrary $ \bb $ and initial approximate solution $ \bx_0 $ is that the symmetric part $ M(A) $ of $ A $ is semi-definite and $ \rank \, M(A) = \rank A $. Furthermore, when $ \bx_0 \in R(A), $ the approximate solution converges to the pseudo inverse solution. Next, for the case when $ R(A) \oplus \ker A = \rn $ and $ \bb \in R(A), $ the necessary and sufficient condition for the CR method to converge to the least squares solution without breaking down for arbitrary $ \bx_0 $, is also derived. Finally, we will give examples corresponding to the above two cases arising in the finite difference discretization of two-point boundary value problems of an ordinary differential equation.
国立情報学研究所
2001-08-03
jpn
departmental bulletin paper
https://doi.org/10.20736/0000000355
https://repository.nii.ac.jp/records/355
10.20736/0000000355
1346-5597
NIIテクニカル・レポート
NII Technical Report
1
34
https://repository.nii.ac.jp/record/355/files/01-003J.pdf
application/pdf
287.1 kB
2015-08-25