連立一次方程式を解くプログラムについて

質問

数値計算の本を見たら必ず載っている連立1次方程式の解法ですが、どのようなタイプの行列でも解くことができるものにはどのような解法があるでしょうか。もちろん、解くことができる範囲でということではあります。その意味でガウスの消去法（ピボット付）になるでしょうか。ガウスの消去法は解き方に基本的な制約はないですね。一方、共役勾配法の説明を見ると"対称正定値行列の場合、..."となっており、その範囲でしか考えていないということでしょうか。そうなるとかなり絞られることになってしまいます。任意の行列は変換して対称正定値に変換できる、ということでもないと思いますが。
有限要素法に関連した連立方程式解法についても書籍1冊分の解説とかありそうですが。高速化のために長い解説があったとしても前提によって使える範囲が狭いものが多いように思えるのですが。よろしくお願いします。

回答No.2

ddtddtddt

#1さんのおっしゃっている「LU分解とかQR分解とかSVDとか...」は、ガウスの消去法を効率良く実行するための技と考えられます。もちろん適用可能な行列に制限はありませんが、既知ベクトルをとりかえただけの、同じ係数行列の連立1次方程式を、繰り返し解くための技と思えます。
　という訳で、本質的にはガウスの消去法と同じです。そこで一言注意を申し上げると、ガウスの消去法ではピボット選択とともにスケーリングを併用する事をお勧めします。
　スケーリングとは、係数行列の各行の絶対値最大の成分で方程式系の各行を割り、係数行列の各行の数値オーダーを揃える前処理です。これを行うと係数行列の各行の絶対値最大は1になり、かなりの悪条件でもピボットの併用で解が非常に安定します。簡単な処理ですし、CPU負担も消去過程に比べたらカスみたいなもんですが(^^)、それより重要なのはピボット選択時の特異行列判定基準を簡単に作れる事です。
　というのは係数行列の最大絶対値は1なので、ピボットの0判定オーダーを、10^(-6)とか10^(-10)とかに簡単に指定できます。自分は10^(-8)をよく使います。

　次に共役勾配法に代表される反復解法ですが、もちろん正定値対称行列（厳密には非負定値対称行列）に限らない方法はいろいろあります。また共役勾配法も、正定値でなくても対称ならOKなようです。さらに対称でなくても（一般行列用に）、双共役勾配法ってのがあるそうです。
　とはいえ、物理的な（工学的な）問題に出てくる係数行列は物理的要請から、ほとんど必ず正定値対称行列なので、#1さんの気持ちはわかるなぁ～(^^)。

　詳しくはこちらをどうぞ。でもたぶん絶版です。図書館で・・・(^^;)。

・行列計算ソフトウェア，小国力編，丸善株式会社，平成3年．

お礼

回答ありがとうございます。その本、実は持っており、5inchのFDが付いていたと思います。もう5inchFDを読みこむドライブはありませんが。あまりにも細かく書いてある本なのでちょっと辟易する面もあるのですが。あと国際的な類書でドンガラの本があったと思います。

回答No.1

f272

> どのようなタイプの行列でも解くことができるものにはどのような解法があるでしょうか。

LU分解とかQR分解とかSVDとか...

> 共役勾配法の説明を見ると"対称正定値行列の場合、..."となっており、その範囲でしか考えていないということでしょうか。

まあ，そうですね。

> そうなるとかなり絞られることになってしまいます。任意の行列は変換して対称正定値に変換できる、ということでもないと思いますが。

解こうと思っている連立方程式がどのようなものかを考えたとき，対称正定値になっていることはよくあります。だから印象としては「かなり絞られる」という気はあまりしないのです。
なお，Ax=bのAが非対称行列でも，AにAの転置行列を掛けると対称正定値になりますよ。だからといって，いつでもこんな変換をするとよいかというとそうでもないのですが...

お礼

回答ありがとうございます。大規模な行列を解く問題は有限要素法であることが多いとすると、どうしても自然と対称正定値になりそうですね。点i,jの距離は点j,iの距離と同じでかつ正の値とか。そういう意味で制約されているわけではないという感じなのかなと思いますが。