Tout d'abord une méthode de résolution de système linéaire par un algorithme direct est étudiée, puis une méthode itérative sera utilisée pour déterminer le vecteur propre associé à la plus grande valeur propre d'une matrice. Enfin les groupes générés par un ensemble de permutations seront étudiés.
La décomposition LU consiste à décomposer une matrice \( A \) de taille \( n \times n \) sous la forme \( A=LU \) où \( L \) est une matrice triangulaire inférieure avec des 1 sur la diagonale et \( U \) une matrice triangulaire supérieure. Une fois la décomposition \( A=LU \) d'une matrice connue, il est alors très facile de résoudre le problème linéaire \( A\boldsymbol{x} = \boldsymbol{b} \) en résolvant d'abord \( L\boldsymbol{y} = \boldsymbol{b} \) puis \( U\boldsymbol{x} = \boldsymbol{y} \). L'avantage de la décomposition LU sur l'algorithme de Gauss, par exemple, est qu'une fois la décomposition LU connue, il est possible de résoudre le système linéaire rapidement avec des seconds membres différents.
Vu que \( l_{ik}=0 \) si \( k>i \), nous avons: $$ a_{ij} = \sum_{k=1}^n l_{ik}u_{kj} = l_{ii}u_{ij} + \sum_{k=1}^{i-1} l_{ik}u_{kj} \,, $$ et donc comme \( l_{ii}=1 \): $$ u_{ij} = a_{ij} - \sum_{k=1}^{i-1} l_{ik}u_{kj} \,. $$
D'un autre côté, vu que \( u_{kj}=0 \) si \( k>j \), alors: $$ a_{ij} = \sum_{k=1}^n l_{ik}u_{kj} = l_{ij}u_{jj} + \sum_{k=1}^{j-1} l_{ik}u_{kj} \,, $$ et donc si \( u_{jj}\neq0 \): $$ l_{ij} = \frac{1}{u_{jj}} \left( a_{ij} - \sum_{k=1}^{j-1} l_{ik}u_{kj} \right) \,. $$ Ainsi, si les \( (i-1) \) premières lignes de \( U \) et les \( (i-1) \) premières colonnes de \( L \) sont connues, il est possible de déterminer la \( i \)-ème ligne de \( U \) par: $$ u_{ij} = a_{ij} - \sum_{k=1}^{i-1} l_{ik}u_{kj} \,, \quad j \geq i \,, $$ puis la \( i \)-ème colonne de \( L \) par: $$ l_{ji} = \frac{1}{u_{ii}} \left( a_{ji} - \sum_{k=1}^{i-1} l_{jk}u_{ki} \right) \,, \quad j > i\ \,. $$ Pour que la décomposition LU d'une matrice \( A \) soit possible il faut que les \( u_{ii} \) ne soient jamais nuls. Cela est effectivement le cas lorsque la matrice \( A \) et toutes ses sous-matrices principales sont inversibles.
a) Écrire une fonction LU(A) qui retourne le résultat de la décomposition LU d'une matrice.
b) Donnée la décomposition LU d'une matrice \( A \), écrire une fonction solve(L,U,b) qui résout le système linéaire \( A\boldsymbol{x} = \boldsymbol{b} \).
c) Écrire une fonction LU_inplace(A) qui ne crée pas de nouveaux tableaux pour \( L \) et \( U \) mais modifie \( A \) de sorte que sa partie triangulaire inférieure (sans la diagonale) corresponde à \( L \) et sa partie triangulaire supérieure (avec la diagonale) corresponde à \( U \). Faire également une version solve_inplace prenant en entrée la sortie de LU_inplace et retournant la solution \( \boldsymbol{x} \), sans utiliser de nouveaux tableaux.
d) En utilisant la décomposition LU de la matrice \( A \), écrire une fonction det(A) qui retourne son déterminant.
Le but de cet exercice est de déterminer le vecteur propre d'une matrice associé à la valeur propre de plus grand module, en supposant que celle-ci est unique. Étant donné une matrice réelle \( A \) de taille \( n\times n \) et un vecteur \( \boldsymbol{x}_0\in\mathbb{R}^n \), la suite de vecteurs \( (\boldsymbol{x}_k)_ {k\in\mathbb{N}} \) est définie par: $$ \boldsymbol{x}_{k+1} = \frac{A\boldsymbol{x}_k}{\Vert A\boldsymbol{x}_k\Vert} \,. $$
En supposant par exemple que la matrice \( A \) soit diagonalisable, alors il est possible de montrer que la suite \( (\boldsymbol{x}_k)_ {k\in\mathbb{N}} \) converge à un signe près vers le vecteur propre associé à la plus grande valeur propre de \( A \) en valeur absolue.
La première étape est de remarquer que: $$ \boldsymbol{x}_k = \frac{A^2 \boldsymbol{x}_{k-2}}{\Vert A^2 \boldsymbol{x}_{k-2}\Vert} = \dots = \frac{A^k \boldsymbol{x}_0}{\Vert A^k \boldsymbol{x}_0\Vert} \,. $$ Vu que \( A \) est diagonalisable, soit (\( \boldsymbol{v}_1, \boldsymbol{v}_2, \dots, \boldsymbol{v}_n) \) une base de vecteurs propres de \( A \) associés aux valeurs propres \( \lambda_1, \lambda_2, \dots, \lambda_n \). Sans perte de généralité, on suppose que \( \lambda_1 \) est la valeur propre de plus grand module, c'est-à-dire \( |\lambda_1|>\max(|\lambda_2|,|\lambda_3|,\dots,|\lambda_n|) \). À noter que cela implique que \( \lambda_1 \) est réelle. Le vecteur \( \boldsymbol{x}_0 \) se décompose dans la base: $$ \boldsymbol{x}_0 = \sum_{i=1}^n c_i \boldsymbol{v}_i \,, $$ ainsi en supposant que \( c_1\neq0 \): $$ A^k \boldsymbol{x}_0 = \sum_{i=1}^n c_i \lambda_i^k \boldsymbol{v}_i = c_1 \lambda_1^k \left(\boldsymbol{v}_1 + \sum_{i=2}^n \frac{c_i}{c_1} \left(\frac{\lambda_i}{\lambda_1}\right)^k \boldsymbol{v}_i \right) . $$ Vu que \( |\lambda_1| > |\lambda_i| \) pour \( i\geq2 \), alors: $$ \lim_{k\to\infty}\left(\boldsymbol{v}_1 + \sum_{i=2}^n \frac{c_i}{c_1} \left(\frac{\lambda_i}{\lambda_1}\right)^k \boldsymbol{v}_i \right) = \boldsymbol{v}_1 \,, $$ puisque \( \left|\frac{\lambda_i}{\lambda_1}\right| < 1 \). Par conséquent, $$ \lim_{k\to\infty}\operatorname{sign}{(\lambda_1)}^k \boldsymbol{x}_k = \lim_{k\to\infty} \left(\frac{\lambda_1}{|\lambda_1|}\right)^k \frac{A^k \boldsymbol{x}_0}{\Vert A^k \boldsymbol{x}_0\Vert} = \operatorname{sign}{c_1} \frac{\boldsymbol{v}_1}{\Vert\boldsymbol{v}_1\Vert} \,. $$ En choisissant \( \boldsymbol{x}_0 \) aléatoirement, alors avec probabilité un \( c_1\neq0 \) et donc la suite \( (\boldsymbol{x}_k)_ {k\in\mathbb{N}} \) converge à un signe près vers un vecteur propre normalisé associé à la valeur propre de plus grand module.
a) Définir une fonction puissance(A, x0, k) qui retourne \( \boldsymbol{x}_k \). Avec cette fonction, déterminer le plus grand vecteur propre de la matrice: $$ A = \begin{pmatrix}0.5 & 0.5\\ 0.2 & 0.8 \end{pmatrix} \,. $$
Le plus grand vecteur propre est \( \pm(0.70710678, 0.70710678) \).
b) Déterminer la valeur propre associée au vecteur propre précédent.
Si \( \boldsymbol{v} \) est un vecteur propre normalisé de \( A \), alors la valeur propre associée est donnée par \( \lambda = A\boldsymbol{v}\cdot\boldsymbol{v} \).
c) Écrire un programme permettant de calculer automatiquement la valeur propre de plus grand module et le vecteur propre associé d'une matrice carrée avec une certaine précision donnée.
d) Regarder la documentation de Numpy pour trouver les fonctions permettant de calculer les vecteurs propres et valeurs propres d'une matrice.
e) Comparer la rapidité du code précédent et des fonctions Numpy pour des matrices de tailles \( n\times n \) avec \( n=10,100,1 000 \).
En prenant par exemple des matrices dont les coefficients sont générés aléatoirement dans l'intervalle \( (0,1) \), le théorème de Perron-Frobenius assure l'existence d'une unique valeur propre de module maximal, et celle-ci est positive.
Le but est d'étudier les groupes de permutations en développant des algorithmes pour les caractériser. Un groupe de permutations \( G \subset S_n \) est défini comme étant généré par un certain nombre de permutations: \( G = \langle g_1, g_2,\dots,g_k \rangle \), avec \( g_i\in S_n \) une permutation de l'ensemble \( \{1,2,\dots,n\} \). Une permutation $$ g = \begin{pmatrix}1 & 2 & 3 & 4\\ 4 & 1 & 2 & 3 \end{pmatrix} \,,$$ peut être représentée en python par le tuple g = (0, 4, 1, 2, 3). Le zéro est ajouté afin de se conformer avec l'indexation à partir de zéro de Python et ainsi de simplifier un peu les implémentations. Cela veut simplement dire que le sommet 0 va sur le sommet 0. À noter que cet exercice se prête particulièrement bien à une implémentation orientée objet, et dans ce cas les questions peuvent être adaptées en conséquence.
a) Écrire une fonction product(g1,g2) qui calcule le produit de deux permutations.
b) Écrire une fonction inverse(g) qui calcule l'inverse d'une permutation.
c) Écrire une fonction qui retourne la décomposition d'une permutation sous forme de cycles représentés par une liste du tuples.
d) Écrire une fonction qui retourne la permutation correspondant à une liste de cycles, c'est-à-dire qui fait l'inverse de la fonction précédente.
e) ! En python un groupe \( G = \langle g_1,g_2,\dots,g_k \rangle \) engendré par une famille de permutations, peut être représenté par une liste de permutations G = [g1,g2,...,gk]. Écrire une fonction orbit(G,x) qui retourne l'orbite d'un point \( x\in\{1,2,\dots,n\} \): $$ O_x = Gx = \{gx, g \in G\} \,. $$
Ne pas calculer l'ensemble des éléments du groupe, cela fait une liste beaucoup trop longue. Construire la liste \( (X^0,X^1,\dots,X^N) \) d'ensembles disjoints définie récursivement par \( X^0 = \{x\} \) et \( X^n \) comme l'ensemble des éléments nouveaux de la forme \( g_i y \) avec \( 1 \leq i \leq k \) et \( y\in X^{n-1} \): $$ X^{n}=\left(\bigcup_{i=1}^{k}g_{i}X^{n-1}\right)\setminus\left(\bigcup_{i=1}^{n-1}X^{i}\right) \,. $$
f) !! Définir une fonction stabilizer(G,x) qui retourne le stabilisateur d'un point \( x\in\{1,2,\dots,n\} \): $$ G_x = \{g \in G : g x = x \} \,, $$ sous la forme d'un ensemble de générateurs.
Utiliser le théorème ou lemme de Schreier.