21

免責事項
これは厳密にはプログラミングに関する質問ではありませんが、ほとんどのプログラマーは遅かれ早かれ数学 (特に代数) を扱わなければならないため、その答えは将来誰かに役立つものになると思います。

今、
私が確認しようとしている問題は、次元 n の m ベクトルが線形独立しているかどうかです。m == n の場合、ベクトルを使用して行列を作成し、行列式が != 0 かどうかを確認できます。しかし、m < n の場合はどうでしょうか。

ヒントはありますか?


このビデオレクチャーも参照してください。

4

8 に答える 8

22

ベクトルの行列 (ベクトルごとに 1 行) を作成し、この行列に対してガウス消去法を実行します。行列の行のいずれかが相殺される場合、それらは線形独立ではありません。

自明なケースは、m > n の場合です。この場合、それらは線形独立ではありません。

于 2009-02-10T12:07:37.000 に答える
7

行がベクトルである行列Mを作成し、 のランクを決定しMます。のランクが(ベクトルの数)Mより小さい場合、線形従属性があります。mランクを決定するアルゴリズムでは、M1 行のゼロを取得したらすぐに手順を停止できますが、アルゴリズムを最後まで実行すると、ベクトルのスパニング セットの次元を提供するという追加のメリットがあります。ああ、ランクを決定するアルゴリズムMは単なるガウス消去法です。

数値の不安定性に注意してください。Numerical Recipes の第 2 章の冒頭にある警告を参照してください。

于 2009-02-10T12:08:36.720 に答える
3

の場合m<n、それらに対して何らかの操作を行う必要があります (複数の可能性があります: ガウス消去、直交化など、方程式を解くために使用できるほぼすべての変換が実行されます)。結果を確認します (例: ガウス消去 => ゼロ)。行または列、直交化 => ゼロ ベクトル、SVD => ゼロ特異数)

ただし、この質問はプログラマーが尋ねるのは悪い質問であり、この問題はプログラムが解決するのは悪い問題であることに注意してください。これは、線形に依存するベクトルのセットごとn<mに、線形に独立したベクトルの異なるセットが近くにあるためです (たとえば、問題が数値的に不安定である)。

于 2009-02-10T12:10:52.627 に答える
2

私は最近この問題に取り組んでいます。

以前、ガウスまたはガウス-ジョーダン除去に関するいくつかのアルゴリズムを見つけましたが、それらのアルゴリズムのほとんどは、一般的な行列ではなく、正方行列にのみ適用されます。

一般的なマトリックスを申請するための最良の答えの1つは、次のとおりです。http: //rosettacode.org/wiki/Reduced_row_echelon_form#MATLAB

擬似コードとソースコードの両方をさまざまな言語で見つけることができます。私の場合、PythonソースコードをC ++に変換したため、上記のリンクで提供されているC ++コードは複雑で、シミュレーションに実装するには不適切です。

これがお役に立てば幸いです^^

于 2010-12-02T12:42:06.067 に答える
1

サイズmxnの行列Mに入れられたときに、m個の行ベクトルが線形独立であることを確認する別の方法は、次のように計算することです。

det(M * M^T)

つまり、mxm正方行列の行列式。Mに従属行がある場合にのみ、ゼロになります。ただし、ガウスの消去法は一般的に高速である必要があります。

于 2009-04-06T17:52:35.370 に答える
1

計算能力が問題にならない場合、おそらく最良の方法は行列の特異値を見つけることです。基本的に、の固有値を見つけM'*Mて、最大値と最小値の比率を調べる必要があります。比率がそれほど大きくない場合、ベクトルは独立しています。

于 2009-02-10T18:11:36.457 に答える
1

すみません、私のミスです...


上記のリンクで提供されているソース コードは正しくないことが判明しました。少なくとも、私がテストした python コードと変換した C++ コードは常に正しい答えを生成するわけではありません。(上記のリンクの例では、結果は正しいです:) -- )

mtx Python コードをテストするには、単純にを次のように置き換えます。

[30,10,20,0],[60,20,40,0]

返される結果は次のようになります。

[1,0,0,0],[0,1,2,0]

それにもかかわらず、私はこれから抜け出す方法を持っています。ちょうど今回、rref 関数の matalb ソース コードを C++ に変換しました。matlab を実行し、type rrefコマンドを使用して のソース コードを取得できますrref

非常に大きな値または非常に小さな値を使用している場合はlong double、c++ でデータ型を使用するようにしてください。そうしないと、結果が切り捨てられ、matlab の結果と一致しなくなります。

私は ns2 で大規模なシミュレーションを行ってきましたが、観察された結果はすべて健全です。これがあなたと問題に遭遇した他の人に役立つことを願っています...

于 2010-12-11T08:04:14.210 に答える