Отказ от ответственности
Это не совсем вопрос программирования, но большинству программистов рано или поздно приходится иметь дело с математикой (особенно с алгеброй), поэтому я думаю, что ответ может оказаться полезным для кого-то еще в будущем.
Теперь проблема
Я пытаюсь проверить, являются ли m векторов размерности n линейно независимыми. Если m == n, вы можете просто построить матрицу с помощью векторов и проверить, равен ли детерминант!= 0. Но что, если m < п?
Любые подсказки?
См. также эту видео-лекцию.
Построить матрицу векторов (одна строка на вектор) и выполнить гауссово удаление на этой матрице. Если какая-либо из матричных строк отменяется, они не являются линейно независимыми.
Тривиальный случай, когда m > n, в этом случае они не могут быть линейно независимыми.
Построить матрицу M, строки которой являются векторами и определить ранг M. Если ранг M меньше, чем M (число векторов), то существует линейная зависимость. В алгоритме для определения ранга M вы можете остановить процедуру, как только получите одну строку нулей, но выполнение алгоритма до завершения имеет добавленное преимущество обеспечения размера охватывающего множества векторов. О, и алгоритм определения ранга M является просто гауссовским исключением.
Следите за численной неустойчивостью. См. Предупреждение в начале второй главы в "Численных рецептах".
Если m<n, вам придется выполнить некоторую операцию над ними (существует несколько возможностей: устранение гауссова, ортогонализация и т.д., почти любое преобразование, которое может быть использовано для решения уравнений, будет выполнено) и проверьте результат (например, Гауссово исключение = > нулевая строка или столбец, ортогонализация = > нулевой вектор, SVD = > нулевое сингулярное число)
Однако обратите внимание, что этот вопрос является плохим вопросом для программиста, и эта проблема является плохой проблемой для программы для решения. Это потому, что каждый линейно зависимый набор векторов n<m имеет различный набор линейно независимых векторов поблизости (например, проблема численно неустойчива)
Я работаю над этой проблемой в наши дни.
Раньше я нашел некоторые алгоритмы относительно исключения Гаусса или Гаусса-Йордана, но большинство этих алгоритмов применимо только к квадратной матрице, а не к общей матрице.
Чтобы применить общую матрицу, одним из лучших ответов может быть следующее: http://rosettacode.org/wiki/Reduced_row_echelon_form#MATLAB
Вы можете найти как псевдокод, так и исходный код на разных языках. Что касается меня, я преобразовал исходный код Python в С++, поэтому код С++, указанный в приведенной выше ссылке, как-то сложно и неприемлемо для реализации в моей симуляции.
Надеюсь, это поможет вам, и удачи ^^
Если вычислительная мощность не является проблемой, вероятно, лучший способ - найти сингулярные значения матрицы. В основном вам нужно найти собственные значения M'*M и посмотреть на отношение наибольшего к наименьшему. Если отношение не очень велико, векторы независимы.
Еще один способ проверить, что векторы m строк линейно независимы, если положить в матрицу M размера mxn, это вычислить
det(M * M^T)
то есть. определитель квадратной матрицы mxm. Он будет равен нулю тогда и только тогда, когда M имеет некоторые зависимые строки. Однако гауссовская элиминация должна быть в целом быстрее.
Извините, моя ошибка...
Исходный код, указанный в приведенной выше ссылке, оказывается неправильным, по крайней мере, код 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, и все наблюдаемые результаты звучат. надеюсь, это поможет вам и любому другому, кто связал проблему...
Очень простой способ, который не является наиболее эффективным с точки зрения вычислений, состоит в том, чтобы просто удалить случайные строки до m=n, а затем применить детерминантный трюк.
m < n: удалить строки (сделать векторы короче), пока матрица не станет квадратной, а затемm = n: проверьте, равен ли детерминант 0 (как вы сказали)m < n (число векторов больше их длины): они линейно зависимы (всегда).m x n также является решением системы уравнений n x n (вы пытаетесь решить Av=0). Для лучшего объяснения см. Wikipedia, что объясняет это лучше, чем я могу.