Ensemble des matrices LU-factorisables
dans Algèbre
Bonjour
Un résultat assez commun de l'ensemble des matrices carrées de taille n inversibles est qu'il est dense dans Mn(R). Du coup, lorsqu'on génère aléatoirement des matrices à coefficient réels (chaque coefficient suit une loi uniforme sur un segment), on a une probabilité nulle de tomber sur une matrice non inversible (ou alors corrigez moi).
Bien sûr ça c'est la théorie. Dans la pratique, comme l'ordinateur ne peut représenter qu'un nombre fini de réels, cette probabilité n'est pas nulle.
Mais disons qu'elle est suffisamment faible pour ne pas se soucier, quand on génère aléatoirement des matrices, de vérifier qu'elles sont inversibles (en fait mon but est de créer pleins de systèmes Ax=B de taille n à résoudre).
Et je me demandais : comme la condition pour ma matrice A d'avoir une factorisation LU (d'après wikipédia) porte sur l'inversibilité de sous-matrices, est-ce que l'ensemble des matrices qui possèdent une factorisation LU (et pas PLU !) est dense aussi dans Mn(R) ?
Ca m'éviterai d'avoir à tester cette condition aussi.
Merci pour votre attention.
Un résultat assez commun de l'ensemble des matrices carrées de taille n inversibles est qu'il est dense dans Mn(R). Du coup, lorsqu'on génère aléatoirement des matrices à coefficient réels (chaque coefficient suit une loi uniforme sur un segment), on a une probabilité nulle de tomber sur une matrice non inversible (ou alors corrigez moi).
Bien sûr ça c'est la théorie. Dans la pratique, comme l'ordinateur ne peut représenter qu'un nombre fini de réels, cette probabilité n'est pas nulle.
Mais disons qu'elle est suffisamment faible pour ne pas se soucier, quand on génère aléatoirement des matrices, de vérifier qu'elles sont inversibles (en fait mon but est de créer pleins de systèmes Ax=B de taille n à résoudre).
Et je me demandais : comme la condition pour ma matrice A d'avoir une factorisation LU (d'après wikipédia) porte sur l'inversibilité de sous-matrices, est-ce que l'ensemble des matrices qui possèdent une factorisation LU (et pas PLU !) est dense aussi dans Mn(R) ?
Ca m'éviterai d'avoir à tester cette condition aussi.
Merci pour votre attention.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Du coup d'un point de vue théorique, est-ce que ça implique qu'on n'ait pas la densité ?
Est-ce que tu ne serais pas en train de confondre « dense » et « de mesure pleine » (i.e. dont le complémentaire est de mesure nulle) ? Enfin, là, je te fais un mauvais procès puisque l'ensemble des matrices qui ont une décomposition LU est à la fois dense et de mesure pleine...
Je ne comprends pas ton usage de « du coup ». Si la théorie te dit que l'ensemble des matrices ayant une décomposition LU, tu ne vas pas l'invalider en tirant 10 matrices sur un ordinateur. Ou bien as-tu si peu confiance dans la théorie ?
À part ça, ce que je ferais, c'est utiliser la décomposition LU pour produire des matrices aux petits oignons qui ont l'air quelconques : on forme une matrice $L$ avec une diagonale de $1$, une matrice $U$ avec des coefficients pas trop compliqués et on multiplie, avec éventuellement une matrice de permutation au milieu de temps en temps. On contrôle la difficulté de résolution à la main du problème avec la taille des coefficients diagonaux de $U$.
Pour reprendre les choses dans l'ordre, je génère une matrice A en tirant chacun de ses coefficients de manière indépendante selon une loi uniforme sur un segment [a;b]. Ma question est : est-ce que j'ai une probabilité 1 que A admette une factorisation LU ?
Comme tu l'as suggéré j'ai, vite fait, quantifié et je trouve que, sur 200 matrices de taille 10 avec des coefficients dans [-1;1], 196 avaient une factorisation LU.
Donc cela semble être en contradiction avec l'idée que l'ensemble des matrices admettant une factorisation LU soit de mesure pleine (tu as raison j'avais confondu avec la densité même si j'imagine que mesure pleine => densité).
À moins que la représentation des flottants de python ait un effet d'échantillonnage qui rendent l'événement "la matrice n'admet pas de facto LU" particulièrement courant ?
Pour tester si une matrice a une facto LU, je faisais comme si elle en avait effectivement une a priori, je la calcule (cet algorithme là fonctionne c'est sûr) puis je teste l'égalité A=LU.
Mais pour tester A=LU, puisqu'on a évidemment pas une égalité exacte, je me contentais de la condition "les coefficients de A-LU sont tous inférieurs à 10^(-13) (au signe près)". Mais 10^(-13) est en fait trop petit ! Ton code m'a mis la puce à l'oreille.
En mettant la borne à 10^(-10), je trouve sur 10'000 matrices qu'elles sont toutes factorisables ! Merci !
Et donc comme dis plus haut, il n'est pas nécessaire de tester si la matrice a une facto LU (c'est presque tjrs le cas). Par ailleurs, connais-tu une démo que l'ensemble des matrices admettant une facto LU est bien de mesure pleine ? Ca m'intéresserais d'en voir une.
C'est un fait général que l'ensemble des zéros d'un polynôme non constant à une ou plusieurs variables est de mesure nulle (c'est a fortiori le cas pour les zéros d'une famille finie quelconque de polynômes non nuls). Voici une esquisse de démonstration.
Commençons par montrer que le graphe $\Gamma$ d'une fonction borélienne $f$ de $\R^d$ dans $\R$ (par exemple de classe $C^1$) est de mesure nulle. On se convainc que c'est une partie borélienne de $\R^{d+1}$ puisque c'est l'image réciproque du fermé $\{0\}$ par $(x_1,\dots,x_{d+1})\mapsto x_{d+1}-f(x_1,\dots,x_d)$. La mesure de $\Gamma$ est l'intégrale de sa fonction indicatrice $\mathbf{1}_\Gamma$. Par le théorème de Fubini-Tonelli, c'est aussi \[\int_{\R^{d+1}}\mathbf{1}_{\Gamma}(x_1,\dots,x_{d+1})\mathrm{d}x_1\cdots\mathrm{d}x_{d+1}=\int_{\R^{d}}\left(\int_\R\mathbf{1}_{\Gamma}(x_1,\dots,x_{d+1})\mathrm{d}x_{d+1}\right)\mathrm{d}x_1\cdots\mathrm{d}x_{d}=0,\]puisque l'intégrale entre parenthèses est la fonction indicatrice de l'intersection de $\Gamma$ avec une droite « verticale » $\bigl\{(x_1,\dots,x_d,t),\ t\in\R\bigr\}$, qui est le singleton $\bigl\{f(x_1,\dots,x_d)\bigr\}$.
Soit $P\in\R[X_1,\dots,X_n]$ un polynôme non constant. On s'intéresse à l'ensemble $V(P)$ des $(x_1,\cdots,x_n)$ tels que $P(x_1,\dots,x_n)=0$. Il existe un indice $i$ tel que $\frac{\partial P}{\partial X_i}$ n'est pas le polynôme nul. Pour simplifier les notations, je suppose $i=n$ et je suppose que $n\ge2$ (pour $n=1$, le résultat est évident puisque $V(P)$ est fini). Soit $W=V\bigl(\frac{\partial P}{\partial X_n}\bigr)$ l'ensemble des $(x_1,\cdots,x_n)$ tels que $\frac{\partial P}{\partial X_n}(x_1,\dots,x_n)=0$ et $W^c$ son complémentaire.
Par le théorème des fonctions implicites, pour un point $x$ de l'intersection $V(P)\cap W^c$, il existe un voisinage de $x$ sur lequel $V(P)$ est le graphe d'une fonction $x_n=\varphi(x_1,\dots,x_{n-1})$. L'avant-dernier paragraphe montre que la mesure de l'intersection de $V(P)\cap W^c$ et de ce voisinage est nulle. Il faut se convaincre qu'un nombre dénombrable de ces voisinages suffit pour recouvrir $V(P)\cap W^c$. Ainsi, cette intersection est de mesure nulle.
D'autre part, $V(P)$ est inclus dans la réunion de $V(P)\cap W^c$ et de $W$. Or $W$ est le lieu des zéros d'un polynôme de degré strictement plus petit que $P$ donc on peut mettre en place une récurrence sur le degré pour conclure que la mesure de $W$ est nulle.
Edit : rectification d'une coquille.
Merci encore et bonne continuation !