:: Home » Numeri » #13 » MATEMATICA » Sistemi lineari (seconda parte)
1995
25
Nov

Sistemi lineari (seconda parte)

media 2 dopo 1 voti
Commenti () - Page hits: 3200
Metodi per la risoluzione

di sistemi lineari

(2a puntata)


Per proseguire il discorso iniziato il mese scorso, vedremo ora i metodi iterativi che, come già si è detto, sono utilizzati quando la matrice del sistema Ax=b è sparsa, di grandi dimensioni o priva di una struttura particolare. La soluzione del problema è ottenuta come limite di una successione di soluzioni di sistemi più semplici.
Ciò che sta alla base dei metodi iterativi è lo splitting della matrice A: in sostanza si considera A=P-N, dove P è una matrice non singolare. Da ciò segue che se Ax=b è il sistema dato,

(P-N)x=b    (1)

sarà la forma che ci permetterà di esprimere la successione delle soluzioni in forma ricorsiva; infatti, dato il vettore x0, detto stima iniziale, si ricava xk per k"1 risolvendo il seguente sistema:

Pxk+1=Nxk+b    (2)


Ottenuta in questo modo la successione {xk}, si ha che

lim(k"')xk=x    (3)

dove x è la soluzione del sistema Ax=b. In particolare, dalla definizione di limite di una successione si ha che la (3) è verificata quando xk-x<®. Ponendo, infine, ek=xk-x si dice che il metodo è convergente quando ek<®.
Vediamo ora una condizione sufficiente per la convergenza.
Riscrivendo la (1) nella seguente forma

Px=Nx+b    (4)

e sottraendola dalla (2) si ottiene

Pek+1=Nek    (5)

da cui, ponendo B=P-1N, dove B è la matrice di iterazione del metodo, risulta

ek+1=Bk+1ek    (6)


Iterando la (6) si ottiene la relazione

ek+1=Bk+1e0    (7)

dalla quale, sapendo che e0 è il vettore costante che rappresenta l'errore commesso nel dare la stima iniziale della soluzione
(e0=x0-x), si ricava che:
lim(k"')ek+1=

=lim(k"')Bk+1e0=

=e0lim(k"')Bk+1
dunque lim(k"')ek+1=0 se e soltanto se
lim(k"')Bk+1=0.

Questo teorema, però, ci permette di valutare la convergenza del metodo studiando una successione a valori nello spazio n-dimensionale; tuttavia, essendo più semplice lavorare nello spazio reale unidimensionale, può essere utile sapere che:
a. lim(k"')Bk=0
b. «(B)<1
c. lim(k"')Bk+1=0 per qualche
norma matriciale

sono equivalenti. Sfruttando dunque le proprietà (b) e (c) si può ottenere più agevolmente una stima della convergenza di B; infatti, non occorre più valutare il limite di una successione a valori nello spazio reale n-dimensionale ma, nel primo caso, si valuta una disuguaglianza nello spazio reale e nel secondo il limite di una successione dello spazio unidimensionale.
Altra caratteristica della succesione {ek} è che la sua convergenza è tanto più rapida quanto più piccolo è «(B).
Ritornando allo splitting della matrice A occorre specificare che a seconda di come P ed N vengono scelte, si ottengono differenti metodi iterativi, l'applicazione dei quali al sistema Ax=b può portare talora a differenti risultati a causa degli eventuali errori prodotti dal metodo sulla matrice specifica. Supponendo di suddividere gli elementi di A come indicato in figura, vediamo quali possono essere le scelte di P ed N ed i metodi corrispondenti:

1.    P=D    N=-(E+F)
- Metodo di Jacobi




- La componente i-esima dell'iterata
(k+1)-esima è data dalla seguente
relazione

xk+1i=(bi-'(j=1,...,n j"i)aijxkj)/aii


K"0 i=1,...,n


ottenibile esplicitando
xk+1=P-1Nxk+P-1b.
- La matrice di iterazione del metodo è
BJ=-D-1(E+F)
- E' possibile dimostrare che:
condizione sufficiente, ma non necessaria, per la convergenza del metodo è che A sia a dominanza diagonale stretta.
- Questo metodo è anche detto metodo degli spostamenti simultanei in quanto per il calcolo della i-esima componente del vettore xk+1 occorrono tutte le componenti del vettore precedente tranne l'i-esima.
Questo implica che solo dopo aver calcolato tutte le componenti di xk+1 è possibile liberare l'area di memoria contenente xk e l'operazione viene compiuta contemporanemente su tutte le sue componenti.

2.    P=D+E    N=-F
- Metodo di Gauss-Sidel



- La componente i-esima dell'iterata (k+1)-esima è data dalla seguente relazione

xk+1i=(bi-'(j=1,...,i-1)aijxk+1j+


-'(j=i+1,...,n)aijxkj)/aii


K"0 i=1,...,n


- La matrice di iterazione del metodo è BGS=-(D+E)-1F.

- E' possibile dimostrare che:
a. se A è a dominanza diagonale stretta il metodo converge
b. se A è simmetrica e definita positiva il metodo converge (questo, in genere, non si verifica per il metodo di Jacobi)
c. se A è tridiagonale si ha che «(BGS)=«2(BGS) quindi in generale il metodo di Gauss-Sidel converge più velocemente del metodo di Jacobi
- Questo metodo è anche detto metodo degli spostamenti successivi in quanto, per il calcolo di xk+1i, servono le prime i-1 componenti di xk
(si noti che non si utilizzano xk1,...,xkn); questo permette di operare utilizzando un solo vettore nel quale si sostituisce successivamente l'i-esima componente di xk con l'i-esima componente di xk+1.

Elena

 
:: Vota
Vota questo articolo: 1 - 2 - 3 - 4 - 5 (1 = scarso - 5 = ottimo)
 
:: Automatic tags
 
:: Articoli recenti
 
KULT Virtual Press e KULT Underground sono iniziative amatoriali no-profit - per gli e-book e per gli articoli fare riferimento alla sezione Copyright
Webmaster: Marco Giorgini - e-mail: marco @ kultunderground.org - Per segnalazioni o commenti inviare una e-mail a: info @ kultunderground.org
Questo sito è ospitato su server ONE.COM

pagina generata in 150 millisecondi