Sistemi lineari: appunti di analisi numerica

Sistemi lineari Un sistema lineare di m equazioni in n incognite della forma a11x1 + a12x2 + . . . + a1nxn a x + a x + . + a x 21 1 22 2 2n n a x + a32x2 + . . . + a3nxn 31 1 . a m1 x1 + am2 x2 + . . . + amnxn = b1 = b2 = b3 = bm pu essere indicato brevemente come Ax = b, dove o a a12 11 a21 a22 A = a31 a32 . . am1 am2 . . . . . a1n a2n a3n . amn x 1 x2 , x = x 3 . xn b 1 b2 e b= b 3 . bn . 1 Il sistema Ax = b risolubile se il vettore b si pu esprimere e o come combinazione lineare delle colonne della matrice A con coefficienti x1, xn, cio se il vettore b appartiene allo spazio e vettoriale generato dalle colonne di A, Im A. a a 12 11 a22 a21 x + a a 32 31 1 . . an2 an1 b a 1 1n b2 a2n xn = b x + . a 3 3n 2 . . bn ann2 Teorema di Rouch-Capelli Il sistema Ax = b ammette solue zione se e solo rango [A b] = rango [A]. rango di A = dimensione massimo minore nonsingolare di A. 2 se m n ed A di rango m lo spazio delle soluzioni ha e dimensione n - m; se m = n ed A non singolare, il sistema ammette una ed e una sola soluzione: x = A-1b; se m n ed A ha rango n il sistema ha pi equazioni che u incognite ed detto sovradeterminato; ammette soluzione e se e solo se b appartiene allo spazio generato dalle colonne di A. 3 Formula di Cramer Indicando con Ak la matrice che si ottiene sostituendo alla colonna k-esima di A la colonna dei termini noti, le componenti del vettore soluzione sono detAk k = 1, 2, , n detA Calcolo di un determinante di ordine n: (n - 1)n! operazioni soluzione di un sistema di ordine n ( n + 1 det. di ordine n) xk = N = (n - 1n + 1)! N cresce molto rapidamente all'aumentare dell'ordine n della matrice. n = 10 N 3.6108, n = 20 N 1021 Se per eseguire un prodotto ci vogliono 10-9 secondi, per risolvere un sistema lineare di ordine n = 20 con il metodo di Cramer si impegano 1012 secondi, cio 3 104 anni !! e 4 Inversa di una matrice La formula classica 1 A, detA molto onerosa dal punto di vista computazionale, dato che e fa uso della matrice dei complementi algebrici A-1 = A = matrice il cui elemento A(i,j) il determinante della e matrice di ordine (n - 1) che si ottiene eliminando in A la riga j-esima e la colonna i-esima moltiplicato per 1)i+j ) non calcolare mai A-1 con questa formula ! 5 Per avere algoritmi efficienti si devono trovare altre soluzioni, equivalenti dal punto di vista teorico, ma computazionalmente meno onerose. Sistemi triangolari Una matrice si dice triangolare alta o triangolare bassa quando tutti gli elementi al di sotto della diagonale o al di sopra della diagonale sono nulli u u12 . . . u1n 11 0 u22 . . . u2n U = 0 0 . . . u3n . . . . 0 0 . . . unn , L= l11 l21 l31 . ln1 0 l22 l32 . ln2 . 0 . 0 . 0 . . . . . lnn 6 Un sistema lineare in cui la matrice dei coefficienti sia triangolare risolubile se e solo se aii = 0 per i = 1, . . . , n. e Se la matrice dei coefficienti triangolare alta si procede per e sostituzione all'indietro. a11x1 + a12x2 + a22x2+ . . . . . . + a1nxn . . . . . . + a2nxn a33x3 + . . . + a3nxn . annxn Continua »