Principali metodi iterativi

Metodo di Jacobi[modifica | modifica wikitesto]

Divido in tre matrici , dove è la matrice diagonale, la triangolare inferiore stretta (con 0 sulla diagonale principale), triangolare superiore stretta.

Nel caso del metodo di Jacobi con e ( è uguale ad con zeri sulla diagonale principale).

e tenendo conto delle espressioni di e :
Indicando con la matrice d'iterazione del metodo di Jacobi si ha:
e moltiplicando per :
e sostituendo le espressioni ricavate prima:
Considerando la i-esima equazione si ha:

Metodo di Gauss-Seidel[modifica | modifica wikitesto]

In questo caso si pone , invece , e si ricava:

Come prima, moltiplico per la relazione
e ottengo
cioè
Considerando l'equazione i-esima,
Tengo conto che nel prodotto con la triangolare inferiore si utilizzano le informazioni già aggiornate al passo k-esimo, e sopravvivono solo gli elementi con colonne di indice minori di . Nell'altro prodotto invece si utilizzano le informazioni ricavate al passo .

Matrici diagonalmente dominanti e irriducibili[modifica | modifica wikitesto]

Definizione 2.16

Data una matrice dico che:

  1. è diagonalmente dominante in senso stretto per righe se vale
  2. è diagonalmente dominante in senso stretto per colonne se vale
  3. è diagonalmente dominante in senso debole per righe se
    e se esiste almeno un indice tale che
 


Definizione 2.17

si dice riducibile se esiste matrice di permutazione tale che

può essere descritta a blocchi come:
con il primo blocco fatto da righe e l'ultimo da righe.

 

Se sono come sopra, dato il sistema lineare

esso si può riscrivere come:
allora si ottengono le equazioni
e risolvendo prima la seconda e sostituendo poi nella prima ottengo un sistema disaccoppiato.

Esempio 2.11

Considero le matrici

Associamo questa matrice di ordine a un grafo con tre nodi . Per ogni entrata della matrice, quando collego il nodo con il nodo con un arco orientato da a . Ad esempio, quindi traccio un arco che entra ed esce nel nodo 1. Nel caso di questa matrice, posso andare dal nodo 1 al 2 seguendo l'arco orientato tracciato in corrispondenza di , posso andare dal nodo 2 al 3 lungo l'arco tracciato in corrispondenza di , ma non posso andare in nessun modo dal nodo 3 all'1 perché .

Considero invece la matrice

Nel caso della seconda matrice, c'è un cammino chiuso che connette tutti i nodi.

 


Teorema 2.14

Una matrice è irriducibile se e solo se il grafo associato è fortemente connesso ovvero se e solo se esiste un cammino dal nodo al nodo per ogni coppia di nodi .

 

Quindi la prima matrice è riducibile e la seconda non lo è.

Condizioni sufficienti di convergenza[modifica | modifica wikitesto]

Le condizioni sufficienti per la convergenza del metodo di Jacobi sono le seguenti:

  1. è diagonalmente dominante in senso stretto (per righe o colonne)Dim. Sappiamo che
    Nel metodo di Jacobi la matrice di permutazione è
    Se calcolo la norma infinito della matrice di Jacobi , si ha:
    Sfruttando il fatto che è diagonalmente dominante in senso stretto sulle righe, si ha:
    (infatti la somma di ogni riga privata dell'elemento diagonale è minore dell'elemento diagonale)
    quindi
    e il metodo converge.
  2. è diagonalmente dominante in senso debole (per righe o per colonne)
  3. è irriducibile.
Nelle stesse ipotesi converge anche il metodo di Gauss-Seidel, però per questo metodo vale anche la seguente proposizione:
Proposizione 2.5

Data una matrice hermitiana, non singolare il metodo di Gauss-Seidel converge se e solo se è definita positiva.

 
(la fattorizzazione di Cholesky, che determina se una matrice è definita positiva oppure no, è un buon modo per determinare se il metodo di Gauss-Seidel converge o no)
Teorema 2.15

Sia tridiagonale, siano

Se è un autovalore della matrice di iterazione di Jacobi, allora è un autovalore per (matrice di iterazione di Gauss-Seidel). Inoltre, se è un autovalore di , allora è un autovalore di .

 

Allora per le matrici tridiagonali, , allora Gauss-Seidel è convergente se e solo se Jacobi è convergente. Inoltre se Gauss-Seidel converge, ha un tasso di convergenza del doppio rispetto a Jacobi, infatti il tasso asintotico di convergenza è e si ha

(tuttavia non è detto che sia sempre più conveniente usare Gauss-Seidel)

Tasso di convergenza[modifica | modifica wikitesto]

Consideriamo la relazione:

Allora valgono le seguenti definizioni
La definizione di tasso asintotico di convergenza non dipende né dalla norma né dal passo.

Test d'arresto test dell'incremento[modifica | modifica wikitesto]

Si considera la differenza fra un'iterata e la successiva, misurata con una certa norma, e si richiede che il metodo si arresti quando è verificata la condizione

dove è una tolleranza assegnata.
Quindi
Passando alla norma:
Applico il teorema: Se con norma matriciale indotta, allora è non singolare e
Allora, sostituendo l'espressione trovata per nella relazione ottengo:
Quindi
Il test è affidabile tranne nel caso in cui .

Test d'arresto Test del residuo[modifica | modifica wikitesto]

Il residuo è la quantità . Si definisce il residuo al passo k come . Scelta una norma, si impone che la norma del residuo sia minore di , e il metodo si arresta quando questa condizione è verificata.

Sapendo che

allora
allora
Allora l'errore assoluto è controllato bene dal residuo, se il numero di condizionamento non è molto grande.

Il test del residuo è affidabile se il problema non è malcondizionato.

Se invece vogliamo stimare l'errore relativo:

Allora, osserviamo che:
allora
La quantità viene chiamata residuo relativo, se supponiamo se . L'errore relativo viene controllato dal residuo relativo a meno di condizionamento.

Il costo computazionale dell'iterazione è operazioni per iterazione, mentre se la matrice è sparsa il costo è .

 PrecedenteSuccessivo