少数の定数項のみが変化する場合、大規模な線形方程式系を効率的に解くにはどうすればよいでしょうか。例えば：
私は現在、システム Ax= b を持っています。A の逆数を 1 回計算して行列に格納し、b のエントリが更新されるたびに、行列とベクトルの乗算 A^-1(b) を実行して x を再計算します。
これは、b で更新されるエントリが 2 つしかないため、非効率的です。A-1 は一定のままで、特定の既知の値が b で変化する場合、このシステムを解くより効率的な方法はありますか?
私は uBlas と Eigen を使用していますが、この選択的再計算の問題に対処するソリューションを知りません。ご指導ありがとうございます。
まず、行列の反転を実行せず、代わりにソルバーライブラリを使用します。次に、最初の推測としてイニシャルをライブラリに渡しますx。
ライブラリはLUのようなある種の分解を実行し、それを使用してを計算しますx。反復ソルバーを選択した場合、それはすでに、ソリューションに帰着するためにあなたが説明したことのほとんどを実行しています。それはより悪い推測から始まり、より良い推測を生成します、そしてどんな良いルーチンもプロセスをスピードアップするために最初の推測を取ります。多くの場合、とにかく結果をよく理解しているので、それを利用するのは理にかなっています。
新しいものが古いものにb近い場合、新しいものは古いものに近いはずであり、それは良い初期推測として役立ちます。bxx
問題の線形性を利用できます。
x0 = A_(-1)*b0
x = A_(-1)*b = x0 + A_(-1)*db
ここで、 db は と と の差行列でbありb0、ゼロで埋める必要があります。疎行列に圧縮できます。
Eigen ライブラリには、スパース行列 (乗算、逆数など) 用の優れた関数が多数あります。
まず、逆行列を計算せず、代わりに LU 分解または QR 分解を使用します (LU よりも低速ですが安定しています)。このような分解は、行列のサイズに応じて逆変換よりもパフォーマンスが向上し、通常はより安定しています (特に QR)。
A がわずかに (たとえば、ランク 1 の行列によって) 変更された場合に QR 分解を更新する方法がありますが、B が変更された場合は、新しい b で再度解決する必要があります。これを回避することはできません。これは O(n ^2)。
ただし、右辺 B が固定要素だけ変化する場合、つまり . B' = B + dB と dB が事前にわかっている場合、A dx = dB を一度だけ解くことができ、Ax' = B' の解 x' は x + dX になります。
dB が事前に知られていないが、常にいくつかの dB_i ベクトルの線形結合である場合、A dx_i = dB_i を解くことができますが、そのような dB_i が多数ある場合は、^2 プロセスになります (実際には、これは逆数の計算)...