Résolution de systèmes d'équations linéaires

Résumé du document

Ce document détaillent les différentes méthodes de résolution de systèmes d'équations linéaires dans R. Ce document s'adresse aux élèves de prépa scientifique et de deug maths/physique.
Les méthodes directes (Cramer, Gauss, Choleski) sont présentées dans une première partie. Ensuite, on étudie les méthodes itératives de résolution : principe, exemples, convergence.

Extraits

[...] + Tnnxn = bn La dernière équation donne xn = bn / Tnn La kéme ligne La résolution est donc immédiate dans ce cas. Nombre d'opérations : nombre d'addition : nombre de multiplication : nombre de division : n au total ( n2 opérations b)Elimination de Gauss et décomposition L.U. La méthode de Gauss s'exécute, en n étapes qui visent à triangulariser progressivement le systèmes linéaires par transformation successives de A. En général :on soustrait ak1/a11 à la kème ligne qui devient alors : (ak1 ak1a1k / a11)x1 + . [...]

[...] b)Décomposition de Choleski d'une matrice symétrique définie positive. Au, u > > 0 Lemme :Si A est hermitienne et admet la décomposition LDU alors elle s'écrit A = LDL* (si A ( Mn, :hermitienne = AT = A si A n'est pas réelle hermitienne = A où = Ex : Dem = et A = LDU donc = LDU Et d'après l'unicité de la décomposition LDU, donc C'est-à-dire ( D est réelle et donc A = LDL* Algorithme de Choleski Il s'adresse à des matrices symétrique définie positive (ou hermitiennes si ( donc toujours régulières. [...]

[...] Donc question :Est ce que la solution calculée peut être considérée comme une bonne approximation de la solution théorique ? Définition norme :soit E un espace vectoriel sur C. Une norme vectoriel est une application de E dans et qui associe à x ( x vérifiant les propriétés E suivantes : - = ( . x ( C Définition norme matricielle :une norme matricielle subordonnée (ou induite ou associée) à une norme vectorielle est une application, de Mn, n ( A ( A Telle que Les normes vectorielles les plus usuelles sont celles de Hölder: Les normes matricielles les plus usuelles sont : Rayon spectral où = max ( valeur propre spec = {ensemble des valeurs propres} Les propriétés d'une norme matricielle = ( . [...]

[...] Démonstration admise. Théorème :Une matrice A régulière appartient Mn, n possède une factorisation LU ssi toutes les matrices principales de A sont régulières. Compte d'opération de LU La phase triangulation requiert n / 2 division n3 1 / 2 multiplication = 2n3 / 3 n3 n / 2 addition La phase résolution requiert 2n2 opérations. Donc la résolution totale ( N ( 2n3 / 3 opérations (pour n grand) Ex : Ordinateur à 100 Mhz avec n = 100 ( N ( 2n3 / 3 ( 6,6 x 105 opérations et cela demande ( 6,6 x 10-3 secondes Méthode de Choleski a)Décomposition LDU. [...]

[...] a)Méthode de Jacobi. On pose M = D = E + F Le calcul de B = M-1N est facile. B = D-1 + = matrice de Jacobi associée à A. Le processus itératif = Bxm + s'écrit alors :xn+1 = D-1 + xm + D-1b est bien sûr diagonale inversible puisque dii ( Soit en fonction des éléments de la matrice A : b)Méthode de Gauss Seidel. On pose M = D E et N = F d'où dans le processus itératif :Mxm+1 = Nxm + b ( xm+1 = Bxm + C (où B = M-1N = F et C = La matrice B = L1 = F = matrice de Gauss Seidel associée à A. [...]