algorithm - sarrus - ¿Cuál es el mejor algoritmo para encontrar un determinante de una matriz?
metodo de cofactores (4)
Reducción de filas
La forma más sencilla (y no mala) de encontrar el determinante de una matriz nxn es mediante la reducción de filas. Al tener en cuenta algunas reglas simples sobre los determinantes, podemos resolverlo de la siguiente forma:
det ( A ) = α * det ( R ), donde R es la forma escalonada de la fila de la matriz original A , y α es algún coeficiente.
Encontrar el determinante de una matriz en forma escalonada es realmente fácil; Solo encuentras el producto de la diagonal. Resolver el determinante de la matriz original A se reduce a calcular α a medida que encuentra el escalón R de fila.
Lo que necesitas saber
¿Qué es la forma escalonada de la fila?
Vea este link para una definición simple
Nota: No todas las definiciones requieren 1s para las entradas iniciales, y no es necesario para este algoritmo.
Puedes encontrar R usando las operaciones de fila elemental
Intercambiando filas, sumando múltiplos de otra fila, etc.
Deriva α de las propiedades de las operaciones de fila para determinantes
Si B es una matriz obtenida multiplicando una fila de A por alguna constante ß distinta de cero, entonces
det ( B ) = ß * det ( A )
- En otras palabras, puedes esencialmente ''factorizar'' una constante de una fila simplemente tirando de ella por delante del determinante.
Si B es una matriz obtenida intercambiando dos filas de A , entonces
det ( B ) = -det ( A )
- Si intercambias filas, voltea la señal.
Si B es una matriz obtenida agregando un múltiplo de una fila a otra fila en A , entonces
det ( B ) = det ( A )
- El determinante no cambia.
Tenga en cuenta que puede encontrar el determinante, en la mayoría de los casos, solo con la Regla 3 (cuando creo que la diagonal de A no tiene ceros), y en todos los casos con solo las Reglas 2 y 3. La Regla 1 es útil para los humanos que hacen matemáticas. Papel, tratando de evitar fracciones.
Ejemplo
(Hago pasos innecesarios para demostrar cada regla con mayor claridad)
| 2 3 3 1 | A =| 0 4 3 -3 | | 2 -1 -1 -3 | | 0 -4 -3 2 | R 2 <-> R 3 , -α -> α (Rule 2) | 2 3 3 1 | -| 2 -1 -1 -3 | | 0 4 3 -3 | | 0 -4 -3 2 | R 2 - R 1 -> R 2 (Rule 3) | 2 3 3 1 | -| 0 -4 -4 -4 | | 0 4 3 -3 | | 0 -4 -3 2 | R 2 /(-4) -> R 2 , -4α -> α (Rule 1) | 2 3 3 1 | 4| 0 1 1 1 | | 0 4 3 -3 | | 0 -4 -3 2 | R 3 - 4R 2 -> R 3 , R 4 + 4R 2 -> R 4 (Rule 3, applied twice) | 2 3 3 1 | 4| 0 1 1 1 | | 0 0 -1 -7 | | 0 0 1 6 | R 4 + R 3 -> R 3 | 2 3 3 1 | 4| 0 1 1 1 | = 4 ( 2 * 1 * -1 * -1 ) = 8 | 0 0 -1 -7 | | 0 0 0 -1 |
¿Alguien puede decirme cuál es el mejor algoritmo para encontrar el valor determinante de una matriz de tamaño N x N ?
No estoy muy familiarizado con la factorización de LU, pero sé que para obtener L o U, debe hacer que la matriz inicial sea triangular (ya sea triangular superior para U o triangular inferior para L). Sin embargo, una vez que obtenga la matriz en forma triangular para algunos nxn matriz A y asumiendo que la única operación que utiliza su código es Rb - k * Ra, solo puede resolver det (A) = Π T (i, i) de i = 0 a n (es decir, det (A) = T (0,0) x T (1,1) x ... x T (n, n)) para la matriz triangular T. Consulte este enlace para ver de qué estoy hablando acerca de. http://matrix.reshish.com/determinant.php
Si realizó una investigación inicial, probablemente haya encontrado que con N> = 4, el cálculo de un determinante de la matriz se vuelve bastante complejo. Con respecto a los algoritmos, le recomendaría un artículo de Wikipedia sobre los determinantes de Matrix , específicamente la sección "Implementación algorítmica".
Desde mi propia experiencia, puede encontrar fácilmente un algoritmo de descomposición LU o QR en las bibliotecas de matriz existentes, como Alglib . Sin embargo, el algoritmo en sí no es muy simple.
Here hay una extensa discusión.
Hay muchos algoritmos.
Una simple es tomar la descomposición de LU . Entonces, desde
det M = det LU = det L * det U
y tanto L como U son triangulares, el determinante es un producto de los elementos diagonales de L y U Eso es O(n^3) . Existen algoritmos más eficientes.