m n 크기의 벡터가 선형 독립인지 확인하는 방법은 무엇입니까?
https://stackoverflow.com/questions/532029
-
22-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
부인 성명
이것은 엄격하게 프로그래밍 질문이 아니지만 대부분의 프로그래머는 곧 수학 (특히 대수)을 다루어야하므로 그 대답은 미래에 다른 사람에게 유용 할 수 있다고 생각합니다.
이제 문제
치수 N의 M 벡터가 선형 독립인지 확인하려고합니다. m == n이면 벡터를 사용하여 행렬을 만들고 결정자가! = 0인지 확인할 수 있습니다. 그러나 m <n이면 어떻게됩니까?
힌트가 있습니까?
또한보십시오 이 비디오 강의.
해결책
벡터의 매트릭스 (벡터 당 1 열)를 구성하고 가우스 제거 이 매트릭스에. 매트릭스 행이 취소되면 선형 독립적이지 않습니다.
사소한 경우는 m> n,이 경우 선형 독립적 일 수는 없습니다.
다른 팁
매트릭스를 구성하십시오 M 누가 행은 벡터이며 순위를 결정합니다. M. 순위가 있다면 M 보다 적습니다 m (벡터의 수) 그러면 선형 의존성이 있습니다. 알고리즘에서 순위를 결정합니다 M 한 줄의 0 행을 얻 자마자 절차를 중지 할 수 있지만 알고리즘을 완료하기 위해 실행하면 벡터의 스패닝 세트의 치수를 제공하는 Bonanza가 추가되었습니다. 오, 그리고 그리고의 순위를 결정하는 알고리즘 M 단지 가우스 제거입니다.
수치 적 불안정성을 관리하십시오. 수치 레시피에서 2 장의 시작 부분에서 경고를 참조하십시오.
만약에 m<n, 당신은 그들에게 약간의 작업을 수행해야합니다 (가우스 제거, 직교화 등 여러 가지 가능성이 있습니다. 방정식을 해결하는 데 사용할 수있는 거의 모든 변환) 결과를 확인하고 결과를 확인합니다 (예 : Gaussian 제거 => Zero Row 또는 열, 직교화 => 제로 벡터, SVD => Zero Singular Number)
그러나이 질문은 프로그래머가 묻는 것이 나쁜 질문이며,이 문제는 프로그램이 해결하기위한 나쁜 문제입니다. 그것은 모든 선형 종속 세트 때문입니다 n<m 벡터는 근처에 다른 선형 독립 벡터 세트를 가지고 있습니다 (예 : 문제는 수치 적으로 불안정합니다)
나는 요즘이 문제를 해결하고 있습니다.
이전에는 가우시안 또는 가우스-조르단 제거에 관한 알고리즘을 발견했지만 대부분의 알고리즘은 일반 행렬이 아닌 사각 매트릭스에만 적용됩니다.
일반 행렬을 신청하려면 가장 좋은 답변 중 하나는 다음과 같습니다.http://rosettacode.org/wiki/reduced_row_echelon_form#matlab
의사 코드와 소스 코드를 다양한 언어로 찾을 수 있습니다. 나에 관해서는, 파이썬 소스 코드를 C ++로 변환했으며 위의 링크에 제공된 C ++ 코드가 시뮬레이션에서 구현하기가 복잡하고 부적절합니다.
이것이 당신을 도울 수 있기를 바랍니다. 그리고 행운을 빕니다 ^^
컴퓨팅 전력이 문제가되지 않는 경우, 아마도 가장 좋은 방법은 매트릭스의 단일 값을 찾는 것입니다. 기본적으로 고유 값을 찾아야합니다 M'*M 그리고 가장 큰 것보다 가장 작은 비율을보십시오. 비율이 크지 않으면 벡터는 독립적입니다.
M ROW 벡터가 선형 독립인지 확인하는 또 다른 방법은 MXN의 MATRIX M을 넣을 때 계산하는 것입니다.
det(M * M^T)
즉, MXM 사각형 매트릭스의 결정 요인. m에 종속 행이있는 경우에만 0이됩니다. 그러나 가우스 제거는 일반적으로 더 빠르야합니다.
미안해, 내 실수 ...
위의 링크에 제공된 소스 코드는 적어도 내가 테스트 한 Python 코드와 내가 변환 한 C ++ 코드가 항상 정답을 생성하지는 않습니다. (위의 링크의 exmample의 경우 결과가 정확합니다 :) -)
파이썬 코드를 테스트하려면 간단히 교체하십시오 mtx ~와 함께
[30,10,20,0],[60,20,40,0]
그리고 반환 된 결과는 다음과 같습니다.
[1,0,0,0],[0,1,2,0]
그럼에도 불구하고, 나는 이것에서 벗어날 수있는 길을 얻었습니다. 이번에는 Matalb 소스 코드를 변환했습니다. rref C ++에 대한 기능. Matlab을 실행하고 사용할 수 있습니다 type rref 소스 코드를 가져 오려는 명령 rref.
정말 큰 가치 또는 작은 가치로 작업하는 경우 long double C ++의 데이터 유형. 그렇지 않으면 결과가 잘려서 MATLAB 결과와 일치하지 않습니다.
NS2에서 큰 시뮬레이션을 수행하고 있으며 관찰 된 모든 결과가 건전합니다. 이것이 당신과 문제를 암호화 한 다른 사람들에게 도움이되기를 바랍니다 ...
매우 간단한 방법은 가장 계산적으로 효율적이지 않으며 단순히 임의 행을 제거하는 것입니다. m=n 그런 다음 결정적인 트릭을 적용하십시오.
m < n: 행렬이 정사각형이 될 때까지 행을 제거한 다음 행을 제거한 다음m = n: 결정자가 0인지 확인하십시오 (말했듯이)m < n(벡터의 수는 길이보다 큽니다) : 선형 적으로 의존적입니다 (항상).
요컨대, 그 이유는 m x n 방정식은 또한에 대한 해결책입니다 n x n 방정식 시스템 (해결하려고합니다 Av=0). 더 나은 설명은 참조하십시오 위키 백과, 그것은 내가 할 수있는 것보다 더 잘 설명합니다.
