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

Ответ 1

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

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

Ответ 2

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

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

Ответ 3

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

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

Ответ 4

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

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

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

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

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

Ответ 5

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

Ответ 6

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

det(M * M^T)

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

Ответ 7

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

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

Чтобы проверить код python, просто замените mtx на

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

и возвращаемый результат будет выглядеть следующим образом:

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

Тем не менее, у меня есть выход из этого. На этот раз я преобразовал исходный код matalb функции rref в С++. Вы можете запустить matlab и использовать команду type rref для получения исходного кода rref.

Просто обратите внимание, что если вы работаете с каким-то действительно большим значением или действительно маленьким значением, убедитесь, что в С++ используется тип данных long double. В противном случае результат будет усечен и несовместим с результатом matlab.

Я проводил большие симуляции в ns2, и все наблюдаемые результаты звучат. надеюсь, это поможет вам и любому другому, кто связал проблему...

Ответ 8

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

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