ベクトルを計算したいのですが、
s = ABu、
ここで、s と u は N 次元の複素ベクトル、A は N 行 M 列の複素行列、B は M 行 N 列の複素行列です。A、B、および u の要素が浮動小数点数として表される場合、次の 2 つの方法のうち、精度が高い (有効桁数が多い) のはどれですか?
(1) 最初に B u を計算します。
最初に行列とベクトルの乗算を行います。
y = ブウ
次に、別の行列ベクトル乗算
s = Ay
(2) 最初に AB を計算します。
最初に行列 - 行列の乗算を行い、
C = AB
次に、行列とベクトルの乗算
s = Cu
既知の一般的なルールはありますか?
ちなみに、方法(1)の方が方法(2)よりもはるかに効率的であることは理解しています。
行列とベクトルの乗算は、行列と行列の乗算よりも数値安定性が優れているため、(1) の方法がより正確であると予想されます。
より詳細には、行列とベクトルの乗算には適切な前方および後方誤差限界があります。たとえば、行列とベクトルの乗算 y = B u を使用すると、y の誤差は、単位の丸めの 2n 倍 (標準の倍精度数を使用する場合は 1e-16) に行列の最大数を掛けた B 倍によって制限されます。ベクトル u の最大数。これは前方誤差範囲です。
後方誤差限界は、計算された y が B と u の正確な積ではなく、わずかに異なる行列 B' とベクトル u の正確な積であるということです。B と B' の差は、行列 B の最大数に単位の丸めを掛けた値の 2n 倍に制限されます。
行列-行列乗算の場合、行列-ベクトル乗算の場合と同様の順方向誤差限界がありますが、適切な逆方向誤差限界はありません。
これは一般的な原則です。出力が少ない計算 (行列とベクトルの乗算など) は、出力が多い計算 (行列と行列の計算など) よりも後方安定である可能性が高くなります。
ただし、これが違いを生むかどうかは別のマトリックスです。方法 (2) は、行列-行列積に続く行列-ベクトル積により、後方安定性を回復する可能性があります。また、特定のアプリケーションでは大きな違いがない場合や、実際には方法 (2) の方が正確である場合もあります。
しかし、方法 (1) が確かに高速であり、おそらくより正確な方法であることを考えると、私は間違いなくそのオプションを選びます。
2011 年 9 月 29 日に追加:このトピックに関する私のお気に入りの情報源は Nicholas J. Higham 著、Accuracy and Stability of Numerical Algorithms、SIAM、2002 年です。線形代数。
前方誤差はかなり直感的です。B と u が正しいことがわかっている場合、関心があるのは、計算された積 B u と正確な積との差です。これは、フォワードエラー分析が教えてくれるものです。後方誤差は、行列 B が正しくない場合に発生します (誤差を犯す以前の計算の結果である場合もあれば、最終的には実験誤差またはモデリング誤差に苦しむ測定に起因する場合もあります)。B の誤差が 1e-10 で、乗算の後方誤差がこれよりも小さい、たとえば 1e-11 であるとします。これは、乗算の結果が、アルゴリズムに与えた B に対しては正しくありませんが、元の B に非常に近い別の行列 B に対しては正しいため、正しい B である可能性が同じであることを意味します。あなたがアルゴリズムに与えたB。
フォワード エラー分析とバックワード エラー分析には異なる長所があります。理想的には、アルゴリズムは適切な前方および後方エラー境界を持つ必要がありますが、これはあまり頻繁には発生しません。
アルゴリズムが数値の不正確さを補うために余分な作業を行うように特別に設計されている場合を除いて、優れた経験則は、同じことを計算する 2 つの方法が与えられた場合、作業の少ないアルゴリズムの方が精度が高いということです (結局のところ、丸めが発生する機会が少なくなります)。これは普遍的に当てはまるわけではないため、これらのことについて考える義務がなくなるわけではありませんが、出発点としては適切です。
あなたの場合、たまたま正確です。行列の特定の値についてアプリオリに何も知らずに、方法 (1) を優先する必要があります。（方法（2）がより正確になる特定のケースを構築することは可能ですが、それらは一般的に非常に不自然です）。