Chapitre 6. Algèbre

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.
— méthode de résolution directe (décomposition LU)
—algorithme in place
— méthode itérative (puissance itérée)
— groupes de permutations
— orbite et stabilisateur
La décomposition LU consiste à décomposer une matrice A de taille n × 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 Ax = b en résolvant d’abord Ly = b puis Ux = 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 lik = 0 si k > i, nous avons :
et donc comme lii = 1 :
D’un autre côté, vu que ukj = 0 si k > j, alors :et donc si ujj ≠ 0 :
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 :
puis la i-ème colonne de L par :
Pour que la décomposition LU d’une matrice A soit possible il faut que le…