Sistemi Lineari

Matrice non-singolare

Determinante nullo e soluzione unica

Metodo diretto

Numero finito di operazioni

Matrice diagonale: quante operazioni?

n operazioni

Matrice triangolare inferiore

Algoritmo delle sostituzioni in avanti

n² operazioni

Matrice triangolare superiore

Algoritmo delle sostituzioni all’indietro

n² operazioni

Matrice a dominanza diagonale stretta per righe

Gli elementi sulla diagonale principale sono maggiori in valore assoluto della somma di tutti gli altri elementi presenti nelle rispettive righe

Metodo eliminazione Gauss

A → LU

L → Matrice triangolare inferiore → Matrice dei moltiplicatori

U → Metodo → Matrice triangolare superiore → Matrice ridotta a scala

2/3 n³ operazioni

Fattorizzazione LU: incognite e vincoli

n²+n incognite

n vincoli

Elementi diagonali a L → Lii = 1

Fattorizzazione LU: Condizione necessaria e sufficiente

Tutte le sottomatrici principali di A devono essere non-singolari

Fattorizzazione LU: Condizioni sufficienti senza pivoting

• A simmetrica e definita positiva

• A con dominanza diagonale stretta per righe

• A con dominanza diagonale stretta per colonne

Tecnica pivoting per righe

• Definizione matrice di permutazione P ortogonale

• PA = Ã

• MEG alla matrice permutata Ã

Pivoting totale

• Matrice permutazione per righe → P ortogonale → PA

• Matrice permutazione per colonne → Q ortogonale → AQ

• Matrice permutata à = PAQ

Fattorizzazione LU: det(A)

det(A) = det(U)

Scopo del pivoting

• Aumentare elemento pivotale

• Diminuire moltiplicatori

• Diminuire amplificazione errori di arrotondamento macchina

Algoritmo di Thomas: a quali matrici si applica?

• Non-singolari

• n >= 2

• Tridiagonali

Algoritmo di Thomas: quante operazioni?

8n

Fattorizzazione di Cholesky: Condizioni

• A simmetrica

• A definita positiva

Fattorizzazione Cholesky:

Come si definisce A?

Com’è la matrice R?

• A = R^t R

• R triangolare superiore

Fattorizzazione Cholesky: quante operazioni?

n³/3

Raggio spettrale di una matrice

Valore assoluto del massimo autovalore della matrice

Se A è matrice quadrata simmetrica, i suoi autovalori sono reali. Per fare in modo che sia anche definita positiva cosa deve succedere?

Tutti gli autovalori devono essere strettamente positivi

Norma di una matrice: cosa indica?

Quanto la matrice è “potente” nel deformare lo spazio

Matrice singolare

det(A) = 0 → Non ammette inversa

Numero di condizionamento spettrale: Definizione

Rapporto in valori assoluti tra autovalore massimo e quello minimo

Numero di condizionamento: cosa indica in generale?

Amplificazione errore soluzione da perturbazione dati

Numero di condizionamento in norma: Definzione

Prodotto tra norma matrice e norma della sua inversa

Residuo

Misura quanto la soluzione calcolata è coerente con i dati di partenza

Teorema di Wilkinson

Risolvere al computer Ax = b equivale a risolvere in aritmetica esatta (A+dA)x^ = b

Fattore di crescita

Indica quanto i numeri “esplodono” durante i passaggi intermedi dell’eliminazione gaussiana

Se una matrice ha più righe che colonne (m > n), nel calcolo numerico il sistema è…

Impossibile

La soluzione definita nel senso dei minimi quadrati…

Minimizza l’errore della soluzione

La matrice (A^t A) di dimensione m x n è non singolare se…

La matrice A ha rango pieno

rank(A) = min(m,n)

Se A ha rango pieno, allora…

(A^t A) è non-singolare, simmetrica e definita positiva

Fattorizzazione QR:

Sia A matrice a pieno rango di m righe ed n colonne, allora le due matrici Q ed R che si ottengono dalla fattorizzazione come sono?

• Q quadrata ortogonale

• R rettangolare con elementi sotto la diagonale principale nulli

Fattorizzazione QR ridotta:

Sia A matrice a rango pieno di m righe ed n colonne, con m > n. Allora le due sottomatrici Q ed R che si ottengono come sono?

• Q rettangolare con m righe ed n colonne ortonormali

• R triangolare superiore

Metodi iterativi:

Errore e residuo

e(k) = x - x(k)

r(k) = b - Ax(k)

e(k) tende a zero solo se…

B^k tende a zero, verificato per raggio spettrale di B strettamente minore di 1

Metodi iterativi:

Condizione necessaria e sufficiente per la convergenza

Raggio spettrale di B strettamente minore di 1

Metodi decomposizione additiva:

Residuo precondizionato

z(k) = x(k+1) - x(k)

Metodo di Jacobi

P = D

Metodo di Gauss-Seidel

P = D - E

Metodi di Jacobi e Gauss-Seidel:

Condizioni sufficienti

• A simmetrica e definita positiva

• A non-singolare e a dominanza diagonale stretta per righe

• A non-singolare e tridiagonale con tutti gli elementi diagonali non nulli

Metodo di Richardson

x(k+1) = x(k) + @z(k)

Norma energia vettore v

sqrt(v’Av)

Il metodo di Richardson utilizza…

Successioni di parametri reali

Il metodo del gradiente classico converge più rapidamente del metodo del gradiente coniugato

False

Per i metodi iterativi vale ec ~= et

True