math - 逆行列かコレスキーか？

Question

Aとbが既知 の場合、Ax = bを解くアルゴリズムを開発しています。

これを行うには、 x = A ^-1 bまたはコレスキーを使用する 2 つの方法があります 。det( A ) はゼロかもしれませんが、行列は常に正方正定であることはわかっています。そのようなまれなケースでは、私はそれを無視することができます. しかし、計算の観点と効率からすると、逆行列を作成するのは非効率的ですか?

Answer 1

一般に、常にソルバーを使用する必要があります。実際のソルバーは、逆数を掛けるのと同じくらい速く実行する必要があります。逆行列の計算は、分解を行う場合に比べて非効率的であるだけでなく、逆行列を使用すると、分解/ソルバー アプローチで回避できる精度の問題があります。

対称行列がある場合は、コレスキー分解が妥当な選択です。密接に関連するLDL 分解は、同等の精度を持ち、平方根の必要もありません。

行列が対称でない場合は、コレスキーまたは LDL 分解を使用できません。代わりにLU 分解法を使用してください。

Answer 2

大きな行列の場合、はい、逆は非常に非効率的です。ただし、行列が下三角であるなどの特殊なプロパティにより、逆行列の計算がはるかに簡単になります。

数値解析では、Ax=b の最も典型的な解は、A(LUx=b) の LU 因数分解であり、次に y について Ly = b を、x について Ux = y を解きます。

より安定したアプローチについては、QR 分解の使用を検討してください。ここで、Q は Q^T*Q = I の特殊なプロパティを持っているため、Rx = Q^Tb であり、R は上三角 (前方および後方ソルブではなく 1 つの後方ソルブのみ) LUで）。

行列が対称 (Cholesky) または帯状 (Gauss) であるなど、その他の特別なプロパティにより、特定のソルバーが他のソルバーよりも優れたものになります。

いつものように、計算では浮動小数点エラーに注意してください。

反復ソルバーもシステムを解くための一般的な方法であることを付け加えておきます。Conguate 勾配法が最もよく使用され、疎行列に適しています。Jacobi と Gauss-Seidel は、対角線が優勢でスパースな行列に適しています。