Nell’articolo del mese scorso è stato dato un breve cenno sui metodi iterativi per la risoluzione dei sistemi lineari; in particolare si è visto che questi ultimi si basano sulla scomposizione della matrice A del sistema nella somma di più matrici scelte opportunamente. La soluzione è ottenuta come limite di una successione a sua volta ricavata a partire da una stima inizile fornita dall’utente.
A livello terorico il metodo può essere spiegato come segue: fornita una stima iniziale x0, si calcola la soluzione x1, se questa è esatta il sistema è risolto, in caso contrario si ripete il procedimento per calcolare x2 e si prosegue nello stesso modo finchè non si ottiene la soluzione esatta del sistema. Nella realtà, supponendo di voler costruire un programma che calcola la soluzione di un sistema lineare con un metodo iterativo e supponendo che il sistema in questione si tale da poter ricavare la soluzione esatta solo iterando il procedimento un numero infinito di volte, occorre studiare delle
“regole” che permettano di ottenere una soluzione accettabile (anche se non perfetta) in un numero finito di passi. Tali “regole” sono i cosiddetti TEST DI ARRESTO.
Come si diceva nel numero scorso, la soluzione è da ritenersi accettabile quando l’n-esima iterata, xn, è sufficientemente vicina alla soluzione esatta x, dove il termine “sufficientemente” indica la tolleranza ® fissata dall’utente. In simboli:
Questa condizione non è utilizzabile in pratica in quanto implica la conoscenza a priori della soluzione esatta del sistema; tuttavia e possibile dimostrare che essa equivale a:
oppure a:
dove rk=b-Axk è il residuo k-esimo.
Entrambe le equzioni (2) e (3) possono essere utilizzate come test di arresto in un programma di calcolo, in quanto contengono solo valori calcolati durante il processo iterativo e dunque noti. In particolare l’equazione (2) confronta il valore dell’iterata corrente xn col valore xn-1 calcolato al passo precedente, mentre l’equazione (3) valuta il resto k-esimo.
Dimostriamo ora che xk-xk-1<® implica xk-x<®.
Si è visto che se B è la matrice di iterazione del metodo ed ek=xk-x è l’errore al posto k-esimo vale la relazione ek=Bek-1. Posto poi «=B, la relazione fra le norme degli errori successivi è la seguente:
si può dunque dedurre che:
Questa relazione definisce una maggiorazione dell’errore al passo
(k-1)-esimo, tuttavia unendo la (4) e la (5) è possibile ottenere una stima dell’errore al passo k-esimo in funzione della distanza di xk da xk-1; infatti dalla (4) segue che:
dunque:
xk-xk-1”(1-«)ek-1”(1-«)«-1ek
per tanto risulta:
da cui, se « è sufficientemente distante da 1, segue la tesi.
Dimostriamo ora che la rk”® implica xk-x<®.
Sappiamo che:
sottraendo membro a membro si ottiene:
dunque:
che può anche essere scritta nella forma:
essendo A invertibile.
Passando alle norme e ricordando che C1*C2”C1 C2 si ha che:
dove K(A) è detto il numero di condizionamento della matrice.
Avendo ora a disposizione delle condizioni utilizzabili nella pratica, possiamo costruire un programma per la risoluzione di sistemi lineari con metodi iterativi con la certezza di non entrare in un ciclo infinito.
Di seguito è riportato un programma in C che utilizza i metodi descritti nel precedente numero, per il calcolo della soluzione, e le tecniche sopra descritte, per arrestare il procedimento.
