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

Extraits du cours

[...] + 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. [...]

[...] Lemme : - A admet la décomposition LDU ssi elle admet la décomposition LU - La décomposition LDU est unique Dem : 1)Supposons que A = LDU et posons V = DU. Il est claire que V est triangulaire supérieur avec comme diagonale principale les éléments de D donc inversible, par conséquent A = LV. Supposons A = LU. La matrice U qui est triangulaire supérieur et est inversible peut s'écrire U = DV où D est diagonale et est constituée des éléments diagonaux de U. Puis V = D-1U. 2)Unicité :Supposons que A = L1D1U1 = L2D2U2 à finir. [...]

[...] Dem :Supposons qu'il existe deux décomposition de A soient A = L1U1 et A = L2U2. On a donc L1U1 = L2U2 ( U2 = L2-1L1U1 = U1-1U2 = L2-1L1 Or L sont triangulaires inférieures et U triangulaires supérieures par conséquent L2-1L1 et U1-1U2 sont diagonales et vu que L1 et L2 sont à diagonale unité (avec des 1 sur la diagonale principale) alors U1-1U2 = L2- 1L1 = I ( L1 = L2 et U1 = U2 Théorème :Si au cours du processus d'élimination de Gauss, aucun pivot n'est nul alors il existe une décomposition LU. [...]

[...] il faudrait alors au total N ( + opérations. Ex : n = 100 alors N ( Avec un ordinateur moyen fonctionnant à 100 Mhz, on peut réaliser ( 3 x 1015 op / an. 2)Méthode de Gauss Les méthodes directes praticables numérique ramènent la résolution du système à celle d'un système de matrice A plus par exemple : - une matrice orthogonale = At - une matrice triangulaire supérieur ou inférieur a)Résolution d'un système triangulaire. Soit le système Tx = b où T est, par exemple, triangulaire supérieur et régulière (ie det ( On a donc : T11x1 + . [...]