Быстрый метод проверки, является ли Матрица единственной? (не обратимый, det = 0)

Какой самый быстрый алгоритм (ссылка на пример C или C++ была бы классной), чтобы проверить, является ли маленькая квадратная матрица (< 16 * 16 элементов) единственной (необратимой, det = 0)?Быстрый метод проверки, является ли Матрица единственной? (не обратимый, det = 0)

источник

2012-05-31 Vincent

Возможно, гауссово исключение. – nhahtdh

Не уверен, что это самый быстрый, но SVD скажет вам. Если любое из сингулярных значений, найденных SVD, равно 0, то ваша матрица является сингулярной. –

@JustinPeel: LU-декомпозиция будет превосходить SVD для детерминанта, но SVD дает вам больше информации: он сообщает вам, «какие направления» являются сингулярными для матрицы. Во всяком случае, тестирование, если матрица является числовым сингулярным, лучше всего выполнять путем вычисления (привязки) его номера условия, а не путем вычисления детерминанта (детерминант здесь 16-линейный, поэтому небольшие ошибки поднимаются до 16-й степени), поэтому SVD Хорошо, если скорость не является серьезной проблемой. –

Лучший способ - вычислить condition number через SVD и проверить, превышает ли он 1/epsilon, где epsilon - точность машины.

Если вы допустили ложные негативы (т. Е. Матрица неисправна, но ваш алгоритм не может ее обнаружить), вы можете использовать формулу max (a_ii)/min (a_ii) из статьи Википедии в качестве прокси для условия номер, но сначала вы должны сначала вычислить QR-декомпозицию (формула применяется к треугольным матрицам): A = QR с R ортогональным, то cond (A) = cond (Q). Существуют также методы вычисления числа условий Q с операциями O (N), но есть более сложные.

источник

2012-05-31 08:20:01

Используя LAPACK, мы можем использовать DGECON/SGECON для общих/единичных общих матриц или одну из аналогичных подпрограмм для матриц с полезной структурой (полосатой, симметричной и т. Д.). Это использует LU-факторизацию –

-3

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

Вот некоторые псевдо-код для N = 3, но если вы заканчивали The Leibniz formula для определителей шаблон должен быть ясно для всех N.

function is_singular3(matrix) { 
    det = matrix[1][1]*matrix[2][2]*matrix[3][3] 
     - matrix[1][1]*matrix[2][3]*matrix[3][2] 
     - matrix[1][2]*matrix[2][1]*matrix[3][3] 
     + matrix[1][2]*matrix[2][3]*matrix[3][1] 
     + matrix[1][3]*matrix[2][1]*matrix[3][2] 
     - matrix[1][3]*matrix[2][2]*matrix[3][1]; 

    if(det==0) return true 
    else return false 
}

источник

2012-05-31 04:24:35 OneThreeSeven

Проверка эпсилонского расстояния от нуля для матриц с плавающей запятой. – phs

Ему понадобится метапрограмма для генерации формулы жесткого кода. – nhahtdh

Для n = 16 это может быть довольно громоздким для записи. –

Я согласен с методом исключения Гаусса. http://math.nist.gov/javanumerics/jama/doc/Jama/LUDecomposition.html документы LU-декомпозиция - после построения LU-декомпозиции из матрицы вы можете вызвать метод на ней, чтобы получить определитель. Я предполагаю, что это, по крайней мере, стоит того, чтобы сравнить это с какой-либо более специализированной схемой.

источник

2012-05-31 04:32:13 mcdowella

Разложение LU - это * стандартный способ вычисления детерминант. Детерминанты - это просто не стандартный способ проверки дефектности матрицы. –

Быстрый метод проверки, является ли Матрица единственной? (не обратимый, det = 0)

ответ

Смежные вопросы