Как узнать, является ли matrix единственной?

Как мы можем узнать, что matrix 4×4 является единственной или нет?

Можем ли мы это узнать, не увеличивая нашу матрицу с единичной матрицей, а затем выполняем операции с строками?

Итак, как определить, действительно ли matrix является единственной? (В MATLAB, без использования бумажных и карандашных или символических вычислений или ручных операций с строками?) Учебники иногда говорят учащимся использовать определитель, поэтому я начну там.

Теоретически можно просто проверить, равен ли детерминант вашей матрицы нулю. таким образом

M = magic(4) M = 16 2 3 13 5 11 10 8 9 7 6 12 4 14 15 1 det(M) ans = -1.4495e-12 

Как оказалось, эта matrix действительно сингулярна, поэтому существует способ написать строку из M как линейную комбинацию других строк (также верно для столбцов). Но мы получили значение, которое не было точно равным нулю из det , Действительно ли это нуль, и MATLAB просто запутался? Почему это? Символический детерминант действительно равен нулю.

 det(sym(M)) ans = 0 

Как оказалось, вычисление определителя является ужасно неэффективным для больших массивов. Поэтому хорошей альтернативой является использование произведения диагональных элементов конкретной матричной факторизации нашего квадратного массива. Фактически, это то, что MATLAB делает внутри самого det для несимвольных входов.

 [L,U,P] = lu(M) L = 1 0 0 0 0.25 1 0 0 0.3125 0.76852 1 0 0.5625 0.43519 1 1 U = 16 2 3 13 0 13.5 14.25 -2.25 0 0 -1.8889 5.6667 0 0 0 3.5527e-15 P = 1 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 

Посмотрим, что диагональные элементы L являются единицами, но U имеет ненулевые диагональные элементы. И есть хорошие свойства относительно детерминанта произведения матриц, а также определитель верхних или нижних треугольных матриц.

 prod(diag(U)) ans = -1.4495e-12 

Смотрите, что мы получили тот же ответ. Так как факторизация LU достаточно быстрая даже для больших массивов, это хороший способ вычислить определитель. Проблема в том, что она использует арифметику с плавающей запятой. Таким образом, эти диагональные элементы U являются действительными числами с плавающей запятой. Когда мы берем продукт, получаем результат, который не равен нулю. Этот последний элемент был просто немного отличным от нуля.

Есть другие проблемы с det. Например, мы знаем, что матричный глаз (100) чрезвычайно хорошо кондиционирован. В конце концов, это единичная matrix.

 det(eye(100)) ans = 1 

Теперь, если мы умножим матрицу на константу, это НЕ изменяет статус матрицы как единственной. Но что происходит с детерминантом?

 det(.1*eye(100)) ans = 1e-100 

Так ли эта matrix единственная? В конце концов, если det (магия (4)) дает нам 1e-12, то 1e-100 должен соответствовать сингулярной матрице! Но это не так. Еще хуже,

 det(.0001*eye(100)) ans = 0 

Фактически, определитель масштабируется на 0,0001 ^ 100, что в матрице будет 1е-400. По крайней мере, это было бы правдой, если бы Matlab мог бы представлять число, маленькое с использованием double. Он не может этого сделать. Это число будет истощаться. Или же легко, мы можем сделать это переполнение.

 det(10000*eye(100)) ans = Inf 

Ясно, что все эти масштабированные идентичные матрицы одинаково неособы, но det можно сделать, чтобы дать нам любой ответ, который мы хотим видеть! Поэтому мы должны заключить, что вычисление детерминанта – это ужасная вещь, которую нужно сделать с матрицей. Меня не волнует то, что рассказывал вам ваш учебник давно, или то, что сказал вам ваш босс или учитель. Если кто-то сказал вам вычислить детерминант для этой цели, ИСПОЛЬЗУЯ КОМПЬЮТЕР, это был ужасный совет. Период. У детерминантов просто слишком много проблем.

Мы можем делать другие вещи для проверки сингулярности. Лучший инструмент – использовать ранг. Таким образом, если ранг матрицы NxM меньше min (N, M), то matrix является сингулярной. Вот пара тестов:

 rank(M) ans = 3 rank(.0001*eye(100)) ans = 100 

Таким образом, ранг может сказать нам, что магический квадрат 4×4 является единичным, но наша масштабированная идентичная matrix не является единственной. (Хорошо, что ранг может проверять сингулярность неквадратной матрицы.)

Мы также можем использовать cond для проверки на числовую особенность. Наименьшее возможное число условий – 1,0, что соответствует очень хорошо выполненной матрице. Большие номера состояний плохие. В двойной точности это означает, что когда число условий больше, чем около 1e15, ваша matrix очень проблематична.

 cond(M) ans = 8.148e+16 cond(.0001*eye(100)) ans = 1 

Фактически, cond считает, что масштабированная идентичная matrix хорошо обусловлена. Большие номера состояний плохие. Для матрицы с двойной точностью число условий, которое находится где-то около 1e15 или около того, указывает на матрицу, которая, вероятно, является числовой единицей. Итак, мы видим, что M явно сингулярно. Опять же, cond способен работать с неквадратичными matrixми.

Или мы могли бы использовать rcond, инструмент, который оценивает обратную величину условия. Это хороший инструмент для действительно больших массивов. Когда rcond дает число, которое находится где-то около eps, WATCH OUT!

 rcond(M) ans = 1.3061e-17 rcond(.0001*eye(100)) ans = 1 

Наконец, для математических передач (таких как я) мы могли бы вытащить SVD. В конце концов, svd – это инструмент, на котором базируются cond и rank. Когда одно или несколько сингулярных значений матрицы малы по сравнению с наибольшим сингулярным значением, снова имеем сингулярность.

 svd(M) ans = 34 17.889 4.4721 4.1728e-16 

Здесь мы рассмотрим, когда сингулярное значение мало по сравнению с наибольшим сингулярным значением матрицы. Приятно, что svd может рассказать нам, насколько близка matrix к сингулярности, и если имеется несколько небольших сингулярных значений, если дает нам информацию о ранге матрицы.

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

НО ПОЖАЛУЙСТА, НЕ ИСПОЛЬЗУЙТЕ ДЕТ! Да, это проявляется в учебниках. Да, может быть, ваш инструктор или ваш босс сказали вам использовать его. Они были просто неправильными, потому что такие инструменты не работают, когда они применяются на компьютере, который использует арифметику с плавающей запятой. И вы просто не хотите вычислять символическую детерминанту, которая будет ужасно неэффективной.

Простите, если это было долгое чтение. Теперь я сойду с моего soapbox.

Вычислите ранг и сравните с размерностью. Если ранг ниже размерности, то matrix является сингулярной.

Самый надежный подход – выполнить разложение сингулярных значений на матрице. Отношение наибольших к наименьшим сингулярным значениям должно быть в пределах некоторой разумной толерантности. Это отношение является номером условия матрицы. При значениях двойной точности вещи становятся очень плавными с двойными значениями точности, когда число условий превышает миллион или более, и это довольно высокий предел. Обратите внимание: если у вас есть SVD, это полезно для многих других вещей, чем просто вычисление номера условия.

Различия в сингулярном значении – это швейцарская арсенал численного анализа; он может быть немного тяжелым, если вы знаете, что matrix не является сингулярной / плохо обусловленной. Но если вы не знаете, это хороший инструмент для изучения. Особенно это касается Matlab, поскольку это встроенный инструмент.

Я бы использовал cond . Это дает вам численную оценку того, насколько близка сингулярная matrix (где Inf – особая matrix).

Например:

 m = randn(4); cond(m) %Well conditioned, usually in the 10's m = diag([1e-6 1 2 1e6]); cond(m) %Less well conditioned, 1e12 m = diag([0 1 2 3]); cond(m) %Singular: Inf 
  • Простой алгоритм пересечения многоугольников
  • Головоломка: найдите самый большой прямоугольник (проблема с максимальным прямоугольником)
  • Как эта побитовая операция проверяет мощность 2?
  • Вычисление среднего арифметического (один тип среднего) в Python
  • 3D-плоскость с наименьшими квадратами
  • Что такое нерекурсивное решение для последовательности, подобной Фибоначчи, в Java?
  • Вычисление ограничивающей frameworks на некотором расстоянии от координаты lat / long в Java
  • Как объединить два целых числа в C
  • Резиновое литье с разной высотой
  • Как вы находите точку на заданном перпендикулярном расстоянии от линии?
  • Как я могу производить многоточечную линейную интерполяцию?
  • Давайте будем гением компьютера.