2016-01-22 8 views
5

「ブラックブック」の数値計算法第3版には、線形方程式系を解くためのGauss-Jordanアルゴリズムがあります。その後、LU分解を計算し、それを使って線形方程式を解く(LUdcmp :: solveを参照)。残念なことに、この本は、なぜ、ある方法を別の方法にするのかを説明していない。 2つのアプローチが同等であるか、特定の状況に対してあるメソッドを他のメソッドに優先させる理由がありますか?Gauss-Jordan消去とLU分解

+1

を見つけることができます:https://math.stackexchange.com/questions/266355/necessity-advantage-of-lu-decomposition-over-gaussian-排除 – stephan

+0

私は純粋にアルゴリズム/プログラミングの観点から、数学的な観点からではなく、質問をしています。私の経験は、数学者はしばしば、あるアルゴリズムが他のアルゴリズムより優先されるべき理由を知らないということです。 –

+0

数値の線形代数は、計算科学でよりよく議論されるべきであるhttp://scicomp.stackexchange.com見てください、あなたは非常にknowledgable数値コミュニティを見つけるでしょう。 –

答えて

7

LU分解を使用する利点は、複数のソリューションを計算するために再利用できることです。例えば

あなたが一定のA、多くの異なるb秒間式に

Ax = b 

を解決したい場合は、あなたは一度だけAのLU分解を計算する必要があり、それは各bのために再利用することができます。しかし、ガウス・ジョーダン除去では、それぞれの作業をすべてやり直さなければならないでしょう。b

ガウス・ジョーダン除去はO(n^3)ではなく、LU分解の置換ステップメソッドはO(n^2)としてのみスケーリングされます。したがって、LUケースの場合、高価なO(n^3)ステップを各bに対して1回だけ実行する必要があります。

まさにこの上の注意事項の合理的なセットはたぶん役に立つhere

+0

"したがって、LUの場合は、高価なO(n^3)ステップを各bに対して1回だけ行う必要があります。 - 各Aのために一度ではありませんか? –