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

Ответ 1

Итак, как определить, действительно ли матрица единственная? (В 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

Как оказалось, эта матрица действительно сингулярна, поэтому существует способ написать строку 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) чрезвычайно хорошо кондиционирован. В конце концов, это единичная матрица.

det(eye(100))
ans =
     1

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

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

Итак, эта матрица единственная? В конце концов, если 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), то матрица является сингулярной. Вот пара тестов:

rank(M)
ans =
     3

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

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

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

cond(M)
ans =
    8.148e+16

cond(.0001*eye(100))
ans =
     1

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

Или, мы могли бы использовать 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 может рассказать нам, насколько близка матрица к сингулярности, и если имеется более одного небольшого сингулярного значения, если дает нам информацию о ранге матрицы.

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

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

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

Ответ 2

Рассчитайте ранг и сравните с размерностью. Если ранг ниже размерности, то матрица является особой.

Ответ 3

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

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

Ответ 4

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

Например:

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