Mathematical Engineering - Matematica Numerica

Metodi diretti

Divided by topic

IndiceCosto ................................................................................................................................\ ....................................... 1 Fattorizzazione................................................................................................................................\ ......................... 1 Fattorizzazione LU................................................................................................................................\ ................ 1 Esistenza e unicit… della fattorizzazione LU......................................................................................................2 CS per la fattorizzazione LU............................................................................................................................. 2 Fattorizzazione di Cholesky................................................................................................................................\ .. 2 Propriet… matrici................................................................................................................................\ ....................... 2 Dominanza diagonale................................................................................................................................\ ........... 2 CNES - Matrice definita positiva........................................................................................................................... 2 Matrice sparsa................................................................................................................................\ ...................... 3 Matrice tridiagonale................................................................................................................................\ .............. 3 Algoritmi................................................................................................................................\ ....................................3 Forward substitution................................................................................................................................\ ..............3 Backward substitution................................................................................................................................\ ........... 3 Pivoting................................................................................................................................\ ..................................... 4 Per righe................................................................................................................................\ ............................... 4 Per colonne................................................................................................................................\ ........................... 4 Totale................................................................................................................................\ .................................... 4 Stabilit…................................................................................................................................\ ..................................... 4 Numero di condizionamento................................................................................................................................\ . 4 Stabilit… per sistemi lineari................................................................................................................................\ .... 5 Corollario con residuo................................................................................................................................\ ....... 5 Costo �MEG: � Calcolo del determinante: flops �Forward and backward substitution: flops �Decomposizione LU: flops �Decomposizione di Cholesky: flops � Pivoting righe/colonne: n flops �Pivoting totale: flops �Algoritmo di Thomas: flops Fattorizzazione Fattorizzazione LUSia non singolare. Ammette fattorizzazione LU se esistono L matrice triangolare inferiore unitaria e U matrice triangolare superiore tale che . Tutti gli elementi sulla diagonale di U sono non nulli. 1 [L,U,P]=lu(A) Esistenza e unicit� della fattorizzazione LU Sia invertibile. Allora esiste un€unica fattorizzazione LU se e solo se tutti i minori principali superiori sinistri sono non nulli. CS per la fattorizzazione LUSia invertibile. � Se A ‚ una matrice a predominanza diagonale stretta per righe o per colonne, allora ammette un€unica fattorizzazione LU. � Se A ‚ sdp, ammette un€unica fattorizzazione LU. Fattorizzazione di Cholesky flops Sia una matrice simmetrica e definita positiva; allora esiste un€unica matrice triangolare superiore H con elementi diagonali positivi tale che: . [H,p]=chol(A); H^T=chol(A,€lower€)=H€ Propriet… matrici Dominanza diagonale�Per righe: � Per colonne: CNES - Matrice definita positiva Sia A simmetrica. Allora ‚ definita positiva se e solo se una delle due propriet… ‚ soddisfatta: � tutti gli autovalori sono positivi � i minori principali di A sono tutti positivi 2 Matrice sparsaUna matrice ‚ sparsa se il numero di elementi non nulli (NNZ) ‚ circa . Matrice tridiagonaleMatrice sparsa dove solamente gli elementi delle tre diagonali principali possono essere non zero. La fattorizzazione LU mantiene la propriet… di essere sparse. Si utilizza l€algoritmo di Thomas per determinare i coefficienti delle due matrici L e U. alpha(i)=a1 for i=2:n beta(i)=b(i)/(alpha(i-1) alpha(i)=a(i)-beta(i)*c(i-1)end Algoritmi Forward substitution flops Backward substitution flops 3 Pivoting Per righeSe (o molto piccolo), si scambia la k-esima riga con la riga i-esima (dove ) sulla quale ‚ presente (in posizione ) il massimo di . La fattorizzazione diventa: Per colonne Se (o molto piccolo), si scambia la k-esima colonna con la colonna j-esima (dove ) sulla quale ‚ presente (in posizione ) il massimo di . La fattorizzazione diventa: Totale Se (o molto piccolo), si scambia la k-esima riga e la k-esima colonna con la riga i-esima (dove ) e la colonna j-esima (dove ), sulla quale ‚ presente (in posizione ) il massimo di . La fattorizzazione diventa: Stabilit… Sistema perturbato: Numero di condizionamento KA=cond(A,p) Propriet…: � � 4 � � Se A ‚ ortogonale, �Matrice sdp: �Distanza della matrice dall€essere singolare: . Stabilit� per sistemi lineari Siano una matrice non singolare e tali che . Allora se ‚ soluzione di e ‚ soluzione del sistema perturbato , si ha che: Se : Corollario con residuo 5