matrice stochastique

Les exemples de cet article décrivent des matrices aléatoires. Partagez-le avec tout le monde pour votre référence. Les détails sont les suivants :

matrice stochastique

Algorithme de base ---PageRank algorithme de tri [1][2 ], qui implique l'explication et l'application de la théorie des graphes et des chaînes de Markov dans de nombreux articles [3][4][5] , et la phrase la plus critique qui m'a toujours intrigué est "Une matrice stochastique a une valeur propre principale/primaire 1"[3][4][5][6][7][8]. Peut-être que pour ceux qui ont étudié systématiquement la théorie des matrices, elle est très simple et ne vaut pas la peine d’être discutée ou expliquée séparément. Et là, je dois admettre mon ignorance. Bien que j'aie étudié certaines discussions sur les propriétés des matrices en algèbre avancée, je n'ai jamais été exposé à la matrice dite stochastique (Matrice stochastique), encore moins à ses propriétés. J’ai donc essayé de trouver de la littérature pertinente sur Internet, mais les résultats n’étaient pas particulièrement optimaux. Il n’y avait pas d’introduction détaillée aux matrices aléatoires ni de preuve des propriétés associées. Je pense que d'une part, ma technologie de recherche n'est pas encore mature, ou que les mots-clés de recherche sont inexacts, ou qu'il y a un manque d'informations à ce sujet sur Internet. Ici, je voudrais extraire les informations pertinentes que j'ai collectées récemment et trier mes idées pour une utilisation future. C'est également un véritable enregistrement et une supervision de mon propre apprentissage. La matrice aléatoire est en fait un type de matrice non négative (Matrice non négative

Matrice non négative signifie que les éléments de la matrice sont tous non négatifs (

Non négatif). Bien sûr, les matrices non négatives doivent être légèrement distinguées des matrices positives (Matrice positive). Les matrices non négatives sont largement utilisées dans les mathématiques computationnelles, la théorie des graphes, la programmation linéaire, le contrôle automatique et d'autres domaines pour leurs valeurs propres, en particulier la valeur propre maximale (notez que le maximum ici est du point de vue du module ou du concept de valeur absolue). ) Valeur propre maximale), c'est-à-dire que l'estimation de la valeur propre principale (valeur propre principale/primaire) de la matrice est d'une grande importance [9]. La matrice aléatoire est si importante, alors quel type de matrice est une matrice aléatoire ? Si on vous donne au hasard une matrice non négative, comment déterminer s’il s’agit d’une matrice aléatoire ? La matrice stochastique doit en fait être divisée en une matrice stochastique de ligne (

Matrice stochastique de ligne

) et une matrice stochastique de colonne (

Matrice stochastique de colonne

). Une matrice aléatoire en lignes fait référence à une matrice carrée dont la somme en lignes est égale à 1 ; une matrice aléatoire en colonnes est une matrice non négative dont la somme en colonnes est égale à 1. Ensuite, une matrice non négative qui satisfait les sommes de lignes et de colonnes des deux 1 est une matrice stochastique double (Matrice stochastique double), et la matrice identité est une matrice stochastique double. Du point de vue de la recherche, en fait, il suffit d'étudier les propriétés de la matrice de lignes. Après tout, la matrice aléatoire de colonnes n'est que la matrice transposée de la matrice aléatoire de lignes. Par conséquent, la discussion suivante est entièrement basée sur des matrices aléatoires en lignes. Puisque la somme des lignes de la matrice aléatoire A est 1, alors en supposant e=(1,1,...,1), alors le vecteur de transposition e' de e est un vecteur propre de la matrice, correspondant à La valeur propre de A est 1. De cette façon, il reste encore une certaine distance pour prouver que la valeur propre principale de la matrice aléatoire est 1. Supposons que les n valeurs propres de A soient λ(i), où i=1,2,...,n si vous voulez prouver que la propriété est établie, vous devez prouver que |λ(i)|< ; ;=1. Maintenant il existe une valeur propre de 1, il suffit de prouver que les valeurs absolues des autres valeurs propres sont inférieures ou égales à 1. J'ai donc recherché des informations pertinentes et posté un message sur le "Forum doctoral en mathématiques" pour obtenir des conseils. La réponse que j'ai reçue était que je devais le prouver. En gros, je peux utiliser le théorème du disque. Je veux le prouver avec plus de précision, je dois utiliser le

Théorme de Perron-Frobenius

[9][10][11][12]. De nouveaux concepts et méthodes apparaissent les uns après les autres, et il semble qu'une étude systématique des méthodes numériques et de la théorie du calcul numérique soit nécessaire. Les informations trouvées [10] montrent que le rayon spectral de toute matrice n'est pas supérieur à toute norme matricielle induite de la matrice, et la valeur

L1-Norm

de la matrice aléatoire est 1, alors le rayon spectral (est la valeur propre principale de manière équivalente) n'est pas supérieur à 1, et puisque 1 est une valeur propre de A, alors il est impossible d'avoir une valeur propre avec une valeur absolue supérieure à 1 : 1 est bien la valeur propre principale du matrice aléatoire A. Ensuite, la preuve des propriétés ci-dessus est équivalente à la conclusion dans les données de preuve [10]. En fait, "le rayon spectral d'une matrice dans tout domaine complexe n'est pas supérieur à aucune de ses normes induites" n'est qu'une propriété fondamentale des matrices. La preuve spécifique est présentée dans la figure ci-dessous :

D'après les résultats de la preuve ci-dessus, on peut voir que pour toute matrice aléatoire de lignes, son rayon spectral est de 1, cela c'est-à-dire que la valeur propre maximale est 1. Il est prouvé que .

On voit qu'en fait, une petite propriété de la matrice est parfois effectivement un problème difficile pour les personnes qui n'ont pas systématiquement étudié la théorie des matrices. Si vous souhaitez rejoindre l’industrie, vous devez comprendre les règles ; si vous souhaitez vous lancer, vous devez maîtriser le métier.

Le rapport entre la valeur propre principale de la matrice aléatoire et la deuxième plus grande valeur propre est une mesure de base de la vitesse de convergence de la méthode de puissance. Il existe de nombreuses façons de calculer le PageRank, et il existe d'innombrables études à ce sujet. Bien sûr, la plus traditionnelle consiste à utiliser la méthode de la puissance pour déterminer la valeur du PageRank de chaque page Web. rampé dans la base de données. En raison du grand nombre de pages Web, considérer la vitesse de convergence de la méthode de puissance n’est pas une analyse redondante et inutile. L'« écart spectral » (Eigengap) des deux valeurs propres est principalement utilisé pour mesurer la stabilité de la valeur PR obtenue en utilisant la méthode de puissance. De ce point de vue, l’analyse des valeurs propres joue un rôle clé dans la compréhension de l’algorithme du PageRank.

Recommandations associées :

version php de la matrice spirale (de l'intérieur vers l'extérieur)

PHP implémente les caractères N*M Rotation matricielle à 90 degrés

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!