各再帰ラウンドで解いている2つの方程式があります。
X = A - inv(B) * Y * inv(B), X = X + A' * inv(B) * A,
私はこのように問題を解決します：
C = inv(B) Y <=> BC = Y、C を解く D = C inv(B) <=> DB = C <=> B'D' = C'、D' を解く
E = inv(B)*A <=> BE = A、E を解きます。
すべての行列は時間の経過とともに変化するため、再帰のたびにこれ (または反転) を行う必要があります。N は通常 1 ～ 10 程度、場合によってはそれ以上ですが、通常はその程度です。B は正定なので、コレスキーを因数分解に使用して、複数の右辺の方程式を解くことができます。
これは、単に B を反転してから行列の乗算を行うよりもはるかに遅いですか、それとも速いですか? 1 つの反転と 3 つの連立一次方程式の解法 (別の方程式もあります) と転置。反転よりも少なくとも数値的に安定していると思いますか？
ありがとう。
まず、すべての行列が nx n の順序であると仮定しましょう。コレスキー分解は、O(n^3/6) 操作で実行できます (n の値が大きい場合)。
B*c(i) = y(i) または L*L'*c(i) = y(i) (コレスキー) を解くと、2*O(n^2/2) または O(n^2) になりますが、 BC=Y を解くことは、これらの方程式の n 個を解くことであり (Y は nxn であるため)、合計で O(n^3) になります。
D' を解くことは明らかにこれに類似しているため、別の O(n^3) になります。
D' を D に転置するのは大まかに O(n^2) ですが、計算は行われず、データを交換するだけです (対角要素はもちろん同じです)。
2 番目の式の BE = A で E を解くことは、もう一度コレスキー分解の後方代入であるため、O(n^3)
A' * E は n^2 * (n mult と n-1 add) で、O(2*n^3 - n^2) です
これを合計すると: O(n^3/6) + 3*O(n^3) + O(n^2) + O(2*n^3 - n^2) ~ O(31*n^3 /6) ~ O(5*n^3) (n の値が大きい場合)
行列の加算/減算を計算していないことに注意してください。ただし、B を反転することにした場合も同じになるため、これは関係ありません。同じ理由で、A から A' もスキップしました。
では、行列の反転にはどれくらいのコストがかかるのでしょうか? では、行列方程式を解きたいと思います。
B * inv(B) = I。これは、i=1..n について B * x(i) = e(i) を解くことと同じです。ここで、e(i) は I の基本単位ベクトルです。これは通常、次のようになります。ガウスの消去法を使用してシステムを三角形の形式に変換します。これには約 O(n^3/3) の操作が必要です。三角測量が行われると、それを解決するために O(n^2/2) 操作が必要になります (後方置換)。しかし、これを n 回実行する必要があり、合計で O(n^4/3) + O(n^3/2) の操作が必要になるため、ご覧のとおり、既に限界を超えています。
ただし、B のコレスキー分解が O(n^3) とわかっている場合に inv(B) を計算すると (L*L'*inv(B) = I を解くことは BE=A を解くことと同じになるため)
O(n^3/6) (B のコレスキー) + O(n^3) (コレスキーで inv(B) を計算) + 4*O(2n^3-n^2) (4 つの行列multiplications) ~ O(9*n^3) これは少し良いですが、それでも悪いです。
したがって、現在のアプローチを維持することをお勧めします。ただし、これは n の値が大きい場合であることに注意してください。n が 100 以上でない限り、それほど重要ではないと思います。