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

Question

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

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

Какие-нибудь намеки?

---

Смотрите также эта видеолекция.

Answer 1

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

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

Answer 2

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

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

Answer 3

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

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

Answer 4

В эти дни я работал над этой проблемой.

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

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

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

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

Answer 5

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

Answer 6

Другой способ проверить, что m векторов строк линейно независимы, когда они помещены в матрицу M размера mxn, заключается в вычислении

det(M * M^T)

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

Answer 7

Извини, чувак, это моя ошибка...

---

Исходный код, приведенный по приведенной выше ссылке, оказывается неверным, по крайней мере, код 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 8

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

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

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