introduction

Aujourd'hui, nous allons nous occuper du fléau des étudiants en première année d'algèbre linéaire: la précision de la matrice! Apparemment, cela n'a pas encore de défi, alors c'est parti:

Contribution

• Une matrice symétrique dans n'importe quel format pratique (vous pouvez bien sûr également ne prendre que la partie supérieure ou inférieure de la matrice)$n\times n$ $A$
• Facultativement: la taille de la matrice$n$

Que faire?

Le défi est simple: étant donné une matrice à valeur réelle matrice décide si elle est définie positive en émettant une valeur véridique dans l'affirmative et une valeur de Falsey dans le cas contraire.$n\times n$

Vous pouvez supposer que vos éléments intégrés fonctionnent réellement avec précision et ne doivent donc pas prendre en compte les problèmes numériques qui pourraient conduire à un comportement incorrect si la stratégie / le code "de manière prouvable" devait donner le résultat correct.

Qui gagne?

C'est le code-golf , donc le code le plus court en octets (par langue) gagne!

---

Qu'est-ce qu'une matrice positive définie de toute façon?

Il existe apparemment 6 formulations équivalentes lorsqu'une matrice symétrique est définie positivement. Je vais reproduire les trois plus faciles et vous référer à Wikipedia pour les plus complexes.

• Si alors est défini positif. Cela peut être reformulé comme suit: Si pour chaque vecteur non nul, le produit scalaire (standard) de et est positif, alors est défini positif.$\forall v\in\mathbb R^n\setminus \{0\}: v^T Av>0$$A$
  
  $v$$v$$Av$$A$
• Soit les valeurs propres de , si maintenant (c'est tout les valeurs propres sont positives) alors est défini de façon positive. Si vous ne savez pas quelles sont les valeurs propres, je vous suggère d'utiliser votre moteur de recherche préféré pour le découvrir, car l'explication (et les stratégies de calcul nécessaires) est trop longue pour être contenue dans cet article.$\lambda_i\quad i\in\{1,\ldots,n\}$A ∀ i ∈ { 1 , … , n } : λ i > 0 A$A$$\forall i\in\{1,\ldots,n\}:\lambda_i>0$$A$
  
• Si la décomposition de Cholesky de existe, c'est-à-dire qu'il existe une matrice triangulaire inférieure telle que alors est défini positif. Notez que cela équivaut à un retour précoce "faux" si à tout moment le calcul de la racine pendant l'algorithme échoue en raison d'un argument négatif.$A$$L$$LL^T=A$$A$

Exemples

Pour une sortie fidèle

$$\begin{pmatrix}1&0&0\\0&1&0\\0&0&1\end{pmatrix}$$

$$\begin{pmatrix}1&0&0&0\\0&2&0&0\\0&0&3&0\\0&0&0&4\end{pmatrix}$$

$$\begin{pmatrix}5&2&-1\\2&1&-1\\-1&-1&3\end{pmatrix}$$

$$\begin{pmatrix}1&-2&2\\-2&5&0\\2&0&30\end{pmatrix}$$

$$\begin{pmatrix}7.15&2.45\\2.45&9.37\end{pmatrix}$$

Pour sortie falsey

(au moins une valeur propre est 0 / semi-définie positive)

$$\begin{pmatrix}3&-2&2\\-2&4&0\\2&0&2\end{pmatrix}$$

(les valeurs propres ont des signes différents / indéfinis)

$$\begin{pmatrix}1&0&0\\0&-1&0\\0&0&1\end{pmatrix}$$

(toutes les valeurs propres inférieures à 0 / définie négative)

$$\begin{pmatrix}-1&0&0\\0&-1&0\\0&0&-1\end{pmatrix}$$

(toutes valeurs propres inférieures à 0 / définies négatives)

$$\begin{pmatrix}-2&3&0\\3&-5&0\\0&0&-1\end{pmatrix}$$

(toutes les valeurs propres inférieures à 0 / définies négatives)

$$\begin{pmatrix}-7.15&-2.45\\-2.45&-9.37\end{pmatrix}$$

(trois valeurs propres positives, une négative / indéfinie)

$$\begin{pmatrix}7.15&2.45&1.23&3.5\\2.45&9.37&2.71&3.14\\1.23&2.71&0&6.2\\3.5&3.14&6.2&0.56\end{pmatrix}$$

C, 108 octets

-1 octet grâce à Logern
-3 octets grâce à plafondcat

f(M,n,i)double**M;{for(i=n*n;i--;)M[i/n][i%n]-=M[n][i%n]*M[i/n][n]/M[n][n];return M[n][n]>0&(!n||f(M,n-1));}

Essayez-le en ligne!

Effectue l'élimination gaussienne et vérifie si tous les éléments diagonaux sont positifs (critère de Sylvester). L'argument nest la taille de la matrice moins un.

MATLAB / Octave , 19 17 12 octets

@(A)eig(A)>0

Essayez-le en ligne!

La fonction eig fournit les valeurs propres par ordre croissant, donc si la première valeur propre est supérieure à zéro, les autres le sont aussi.

Gelée , 11 10 octets

ṖṖ€$ƬÆḊṂ>0

Utilise le critère de Sylvester .

Essayez-le en ligne!

Comment ça fonctionne

ṖṖ€$ƬÆḊṂ>0  Main link. Argument: M (matrix)

   $Ƭ       Do the following until a fixed point is encountered.
Ṗ             Pop; remove the last row of the matrix.
 Ṗ€           Pop each; remove the last entry of each row.
     ÆḊ     Take the determinants of the resulting minors.
       Ṃ    Take the minimum.
        >0  Test if the least determinant is positive, i.e., if all determinants are.

R , 29 octets

function(m)all(eigen(m)$va>0)

Essayez-le en ligne!

---

Alternative utilisant cholesky:

R , 34 33 octets

function(m)is.array(try(chol(m)))

Essayez-le en ligne!

-1 octet grâce à @Giuseppe

Haskell , 56 octets

f((x:y):z)=x>0&&f[zipWith(-)v$map(u/x*)y|u:v<-z]
f[]=1>0

Essayez-le en ligne!

Fondamentalement, un port de réponse de nwellnhof . Effectue l'élimination gaussienne et vérifie si les éléments de la diagonale principale sont positifs.

Échoue la première sortie de falsey en raison d'erreurs d'arrondi, mais cela fonctionnerait théoriquement avec une précision infinie. Grâce à la suggestion de Curtis Bechtel , maintenant les sorties sont toutes correctes.

Wolfram Language (Mathematica) , 20 octets

0<Min@Eigenvalues@#&

Essayez-le en ligne!

MATL , 4 octets

Yv0>

Essayez-le en ligne!

[3 -2 2; -2 4 0; 2 0 2]0$10^{-18}$

Mathematica, 29 28 octets

AllTrue[Eigenvalues@#,#>0&]&

Définition 2.

Julia 1.0 , 28 octets

using LinearAlgebra
isposdef

Essayez-le en ligne!

---

Julia 0,6 , 8 octets

isposdef

Essayez-le en ligne!

MATL , 6 octets

Il est possible de le faire en utilisant encore moins d'octets, @Mr. Xcoder a réussi à trouver une réponse MATL de 5 octets !

YvX<0>

Explication

Yv     compute eigenvalues
  X<   take the minimum
    0> check whether it is greather than zero

Essayez-le en ligne!

Érable , 33 octets

(c'est-à-dire mes 2 cents)

with(LinearAlgebra):
IsDefinite(A)

JavaScript (ES6),  99 95  88 octets

$0$$1$

f=(m,n=0,R=m[n])=>R?f(m,n+1)&R[m.map((r,y)=>y<n&&R.map((v,x)=>r[x]-=v*r[n]/R[n])),n]>0:1

Essayez-le en ligne!