4

数値オプティマイザーの中間ステップとして、N 個の線形方程式系を解く必要があります。私の知る限り、正確にそうするための合理的に単純なアルゴリズムはO(N ^ 3)です(ただし、O(N ^ 2.8)のような巨大な定数でそれを行うことができる数学論文で恐ろしく複雑なものを見ました)。場合によっては、N が巨大になることがあります。つまり、数千です。

O(N^3) 未満で一次方程式系のまともな近似解を得る良い方法はありますか?

編集：

それがまったく役立つ場合、ここにいくつかの詳細があります。

  1. 私の行列は対称であり、疎ではありません。

  2. これは、ニュートン ラフソンの 2 次導関数行列です。2000 次元の空間で何かを最適化しようとしています。

4

3 に答える 3

3

Jacobi、Gauss-Seidel、cg、GMRES などの反復法があります。

于 2011-02-06T18:03:01.090 に答える
2

対称行列の場合、共役勾配法は実装が簡単で、他のほとんどの反復法（Gauss-Seidel、SORなど）よりも優れています。メインループは、行列とベクトルの乗算と他のいくつかのベクトル演算で構成されます。

動作させたら、前処理を使用して収束をさらに改善できます。

于 2011-02-07T03:54:07.603 に答える
0

はい、それらの係数から取得した行列が疎である場合。たとえば、O(N) で動作する 3 重対角行列がある場合は、"Right lay" (ブルガリア語で、正確な翻訳については不明) の方法があります。まだ O(N^3) であるが、行列が必要な不変条件 (スパース、対角優勢、三角形など) に準拠している場合、信じられないほどの結果を達成する他のアルゴリズムがあります。

不変条件に基づく特定のメソッドに固執している場合、さらに高速化する唯一の方法は、マルチスレッド化することです。

この検索を試してください。

于 2011-02-06T17:59:52.507 に答える