Introducción
Hoy nos ocuparemos de la ruina de los estudiantes de primer año de álgebra lineal: ¡definición de matriz! Aparentemente, esto aún no tiene un desafío, así que aquí vamos:
Entrada
- A Matriz simétrica en cualquier formato conveniente (por supuesto, también puede tomar la parte superior o inferior de la matriz)
- Opcionalmente: el tamaño de la matriz
¿Qué hacer?
El desafío es simple: dada una matriz de valores reales Matriz decide si es positiva definida al generar un valor verdadero si es así y un valor falso si no.
Puede suponer que sus funciones integradas realmente funcionan con precisión y, por lo tanto, no tiene que tener en cuenta los problemas numéricos que podrían conducir a un comportamiento incorrecto si la estrategia / código "demostrablemente" debe producir el resultado correcto.
¿Quién gana?
Este es el código de golf , por lo que gana el código más corto en bytes (por idioma).
¿Qué es una matriz positiva definida de todos modos?
Aparentemente, hay 6 formulaciones equivalentes de cuándo una matriz simétrica es positiva definida. Reproduciré los tres más fáciles y lo remitiré a Wikipedia para los más complejos.
- Si entonces es positivo-definido. Esto puede reformularse como: si para cada vector distinto de cero el producto de punto (estándar) de y es positivo, entonces es definitivo positivo.
- Deje que sean los valores propios de , si ahora (eso es todo los valores propios son positivos), entonces es positivo-definido. Si no sabe cuáles son los valores propios, le sugiero que use su motor de búsqueda favorito para averiguarlo, porque la explicación (y las estrategias de cálculo necesarias) es demasiado larga para estar contenida en esta publicación.A ∀ i ∈ { 1 , ... , n } : λ i > 0 A
- Si existe la descomposición de Cholesky de , es decir, existe una matriz triangular inferior de modo que entonces es positivo-definido. Tenga en cuenta que esto es equivalente a "falso" de retorno temprano si en algún momento el cálculo de la raíz durante el algoritmo falla debido a un argumento negativo.
Ejemplos
Para una salida veraz
Para salida falsey
(al menos un valor propio es 0 / semi-definido positivo)
(los valores propios tienen signos diferentes / indefinidos)
(todos los valores propios más pequeños que 0 / negativo definido)
(todos los valores propios más pequeños que 0 / negativo definido)
(todos los valores propios más pequeños que 0 / negativo definido)
(tres valores propios positivos, uno negativo / indefinido)
Respuestas:
C, 108 bytes
-1 byte gracias a Logern
-3 bytes gracias a ceilingcat
Pruébalo en línea!
Realiza la eliminación gaussiana y comprueba si todos los elementos diagonales son positivos (criterio de Sylvester). El argumento
n
es el tamaño de la matriz menos uno.fuente
i=0
el bucle for, realiza la llamada recursivaf(M,n-1,0)
y la llamada inicial con 0 como tercer argumento.MATLAB / Octave ,
191712 bytesPruébalo en línea!
La función eig proporciona los valores propios en orden ascendente, por lo que si el primer valor propio es mayor que cero, los otros también lo son.
fuente
f=
al principio: las funciones anónimas generalmente se aceptan como respuestas.8.9219e-17
lugar de 0.Jalea ,
1110 bytesUtiliza el criterio de Sylvester .
Pruébalo en línea!
Cómo funciona
fuente
R , 29 bytes
Pruébalo en línea!
Alternativa usando cholesky:
R ,
3433 bytesPruébalo en línea!
-1 byte gracias a @Giuseppe
fuente
Haskell , 56 bytes
Pruébalo en línea!
Básicamente un puerto de respuesta de nwellnhof . Realiza la eliminación gaussiana y comprueba si los elementos en la diagonal principal son positivos.
Falla la primera salida falsey debido a errores de redondeo, pero teóricamente funcionaría con una precisión infinita.Gracias a la sugerencia de Curtis Bechtel , ahora los resultados son correctos.fuente
inputs :: [[[Rational]]]
para obtener respuestas correctasWolfram Language (Mathematica) , 20 bytes
Pruébalo en línea!
fuente
MATL , 4 bytes
Pruébalo en línea!
[3 -2 2; -2 4 0; 2 0 2]
0
fuente
[1 2 3j]
es FalseyMathematica,
2928 bytesDefinición 2.
fuente
Julia 1.0 , 28 bytes
Pruébalo en línea!
Julia 0.6 , 8 bytes
Pruébalo en línea!
fuente
MATL , 6 bytes
Es posible hacerlo utilizando incluso menos bytes, @Mr. ¡Xcoder logró encontrar una respuesta MATL de 5 bytes !
Explicación
Pruébalo en línea!
fuente
Arce , 33 bytes
(es decir, mis 2 centavos)
fuente
JavaScript (ES6),
99 9588 bytesEl mismo método que la respuesta de nwellnhof . Devoluciones0 0 o 1 .
Pruébalo en línea!
fuente