Как проверить, являются ли m n-размерные векторы линейно независимыми?

Question

Отказ от ответственности
Это не просто вопрос программирования, но большинству программистов рано или поздно приходится иметь дело с математикой (особенно с алгеброй), поэтому я думаю, что ответ может оказаться полезным для кого-то еще в будущем.

Теперь проблема
Я пытаюсь проверить, если m векторов размерности n линейно независимы. Если m == n, вы можете просто построить матрицу, используя векторы, и проверить, является ли определитель! = 0. Но что, если m

Есть подсказки?

---

См. Также эту видеолекцию .

Answer 1

Создайте матрицу векторов (по одной строке на вектор) и выполните Гауссово исключение для этой матрицы. Если какие-либо строки матрицы удаляются, они не являются линейно независимыми.

Тривиальный случай, когда m> n, в этом случае они не могут быть линейно независимыми.

Answer 2

Создайте матрицу M, строки которой являются векторами, и определите ранг M. Если ранг M меньше m (количество векторов), то существует линейная зависимость. В алгоритме определения ранга M вы можете остановить процедуру, как только вы получите один ряд нулей, но выполнение алгоритма до завершения имеет дополнительное преимущество, заключающееся в предоставлении размерности набора векторов. Да, и алгоритм определения ранга M - это просто исключение Гаусса.

Позаботьтесь о численной нестабильности. См. Предупреждение в начале второй главы «Числовые рецепты».

Answer 3

Если m<n, вам придется выполнить с ними некоторую операцию (есть несколько возможностей: исключение Гаусса, ортогонализация и т. Д., Почти любое преобразование, которое можно использовать для решения уравнений), и проверить результат (например . Устранение по Гауссу => нулевая строка или столбец, ортогонализация => нулевой вектор, SVD => нулевое сингулярное число)

Однако учтите, что этот вопрос - плохой вопрос для программиста, и эта проблема - плохая проблема для программы. Это потому, что каждый линейно зависимый набор n<m векторов имеет различный набор линейно независимых векторов поблизости (например, проблема численно нестабильна)

Answer 4

Я работал над этой проблемой в эти дни.

Ранее я нашел несколько алгоритмов, касающихся исключения Гаусса или Гаусса-Иордана, но большинство этих алгоритмов применимы только к квадратной матрице, а не к общей матрице.

Чтобы подать заявку на общую матрицу, один из лучших ответов может быть следующим: http://rosettacode.org/wiki/Reduced_row_echelon_form#MATLAB

Вы можете найти как псевдокод, так и исходный код на разных языках. Что касается меня, я преобразовал исходный код Python в C ++, потому что код C ++, представленный в приведенной выше ссылке, является каким-то сложным и неуместным для реализации в моей имитации.

Надеюсь, это поможет вам, и удачи ^^

Answer 5

Извините, моя ошибка ...

---

Исходный код, приведенный в приведенной выше ссылке, оказывается неверным, по крайней мере, код Python, который я тестировал, и код C ++, который я преобразовал, не генерирует правильный ответ все время. (в то время как для примера в приведенной выше ссылке, результат правильный :) -)

Чтобы проверить код Python, просто замените 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, и все наблюдаемые результаты являются достоверными. надеюсь, что это поможет вам и всем, кто столкнулся с проблемой ...

Answer 6

Еще один способ проверить, что m векторов строк линейно независимы, если поместить их в матрицу M размером mxn, - это вычислить

det(M * M^T)

т.е. определитель квадратной матрицы mxm. Он будет равен нулю тогда и только тогда, когда у M есть несколько зависимых строк. Однако устранение по Гауссу должно быть в целом быстрее.

Answer 7

Если вычислительная мощность не является проблемой, вероятно, лучший способ - найти единичные значения матрицы. В основном вам нужно найти собственные значения M'*M и посмотреть на соотношение наибольшего к наименьшему. Если соотношение не очень большое, векторы независимы.

Answer 8

Очень простой способ, который не самый эффективный в вычислительном отношении, состоит в том, чтобы просто удалять случайные строки до m=n и затем применять детерминантный трюк.

• m < n: удалить строки (сделать векторы короче), пока матрица не станет квадратной, а затем
• m = n: проверьте, является ли определитель 0 (как вы сказали)
• m < n (число векторов больше их длины): они линейно зависимы (всегда).

Причина, короче говоря, в том, что любое решение системы m x n уравнений также является решением системы n x n уравнений (вы пытаетесь решить Av=0). Для лучшего объяснения см. Википедия , которая объясняет это лучше, чем я.