algorithm - tiene - matriz inversa definicion

¿Método rápido para verificar si una Matriz es singular?(no invertible, det=0)

Question

¿Cuál es el algoritmo más rápido (un enlace al ejemplo de C o C ++ sería genial) para verificar si una pequeña matriz cuadrada (<16 * 16 elementos) es singular (no invertible, det = 0)?

Answer 1

Estoy de acuerdo con la eliminación gaussiana. http://math.nist.gov/javanumerics/jama/doc/Jama/LUDecomposition.html documenta la descomposición de LU: después de construir la descomposición de LU desde una matriz, puede invocar un método para obtener el determinante. Supongo que al menos vale la pena cronometrar esto para compararlo con un esquema más especializado.

Answer 2

La manera más rápida es, probablemente, codificar una función determinante para cada matriz de tamaño con la que esperas lidiar.

Aquí hay un poco de código psuedo para N = 3, pero si se revisa la fórmula de Leibniz para determinar los determinantes, el patrón debería ser claro para todos los 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
}

Answer 3

La mejor manera es calcular el número de condición mediante SVD y verificar si es mayor a 1 / epsilon, donde épsilon es la precisión de la máquina.

Si permite falsos negativos (es decir, una matriz es defectuosa, pero su algoritmo puede no detectarla), puede utilizar la fórmula máxima (a_ii) / min (a_ii) del artículo de Wikipedia como un proxy para el número de condición, pero usted tiene que calcular primero la descomposición QR (la fórmula se aplica a las matrices triangulares): A = QR con R ortogonal, luego cond (A) = cond (Q). También hay técnicas para calcular el número de condición de Q con O (N) operaciones, pero hay más complejas.