数値解析セミナー

過去の記録 ~03/28次回の予定今後の予定 03/29~

開催情報 火曜日 16:30~18:00 数理科学研究科棟(駒場) 002号室
担当者 齊藤宣一、柏原崇人
セミナーURL https://sites.google.com/g.ecc.u-tokyo.ac.jp/utnas-bulletin-board/

2016年05月23日(月)

16:30-18:00   数理科学研究科棟(駒場) 056号室
保國惠一 氏 (筑波大学システム情報系)
最小二乗問題に対する内部反復前処理とその応用 (日本語)
[ 講演概要 ]
大規模最小二乗問題を解くためのクリロフ部分空間法に対する前処理法である、内部反復前処理について議論する。本前処理法は複数反復の定常反復法を用い、正規方程式に対する逐次過緩和法 (SOR法) を用いるものが効率的である。SOR内部反復を用いた左 (右) 前処理付き一般化最小残差法 (BA (AB) -GMRES) 法は、ランク落ちである場合に対しても破綻することなく最小二乗解 (線形方程式の最小ノルム解) を与える。内部反復前処理は従来の不完全行列分解型前処理よりも必要な記憶容量が少なく、悪条件およびランク落ちである最小二乗問題に対してもロバストである。
このような内部反復前処理の応用として取り上げるのは (1) 最小二乗解ベクトル自体のノルムが最小である解 (最小ノルム最小二乗解) を求めるという一般最小二乗問題および (2) 線形計画問題に対する内点法に現れる線形方程式の求解である。(1)では二段階からなる手続きで最小ノルム最小二乗解を計算することができるが、第一段階では最小二乗解、第二段階では線形方程式の最小ノルム解を計算する必要がある。各段階でSOR内部反復前処理付きGMRES法を用いることを提案し、いくつかのテスト問題に対して従来法よりも効率的であることを数値実験で示す。(2)では内点法の反復終盤には解くべき線形方程式が非常に悪条件になる。そこで内部反復前処理を用いることで頑健な求解を実現する。この問題に現れる線形方程式に内部反復前処理を適用するための効率的な定式化を行い、ベンチマーク問題に対する数値実験で従来法に比べて本手法が頑健であることを示す。(2)はYiran Cui氏 (University College London)、土谷隆氏 (政策研究大学院大学) 、および速水謙氏 (国立情報学研究所)との共同研究である。