Relazione parte 2 Metodi Numerici

Di seguito si riporta il grafico che mostra le soluzioni finali ottenute per diversi valori del parametro di

0

ossia per differenti valori dell’approssimazione iniziale del vettore :

.

Figura 2. Andamento delle soluzioni finali per differenti valori del parametro

3

Com’è possibile osservare dal grafico posto sopra, le soluzioni finali nei casi in cui sia pari a 0 o a 10 sono

molto simili e raggiungono la convergenza senza problemi. Per quanto concerne la soluzione finale nel caso

di = 20 il sistema arriva a convergenza ma in maniera meno accurata rispetto ai primi due casi.

= 50

Per quanto riguarda la soluzione finale del sistema nel caso in cui la soluzione non giunge a

convergenza.

Tali affermazioni si potranno constatare di seguito osservando la tabella riportante le norme di F(x) e i

grafici che mostrano la storia di convergenza della funzione: .

Figura 3. Storia di convergenza del metodo al variare del parametro

α = 0

Risultati per

α = 10

Risultati per α = 20

Risultati per

4 α = 50

Risultati per

Nelle tabelle sopra riportate “it” rappresenta il numero di iterazioni effettuate, “‖‖” è la norma 2 della

k+1 k

x = x + dx,

funzione F, “‖‖” è la norma 2 del passo, ossia mentre l’ultimo termine rappresenta il

rapporto tra la norma 2 appena calcolata di dx e quella dell’iterazione precedente.

= 0

Nel caso di si raggiunge la convergenza con una precisione molto elevata in appena 3 iterazioni: ciò

= 10

‖‖

è osservabile dal valore di associato alla terza iterazione. Per i risultati sono molto simili al

= 20

caso precedente, ma per la convergenza sono necessarie 5 iterazioni. Per la convergenza arriva

comunque in 5 iterazioni, tuttavia i risultati ottenuti hanno una precisione inferiore com’è possibile

osservare dalle tabelle poste sopra.

= 50 = 20,

Per quanto concerne si vede come la soluzione non converga neppure dopo ossia il limite

massimo di iterazioni che era stato impostato in fase iniziale; inoltre anche aumentando tale valore la

soluzione non converge. Dopo la sesta iterazione la soluzione calcolata diverge enormemente, rendendo il

calcolo della soluzione praticamente impossibile.

= 50

La situazione ottenuta per ci fa desumere che il problema oggetto del seguente studio non

soddisfa il teorema di convergenza globale; pertanto il metodo di Newton presenta convergenza locale,

0

ossia converge ad una soluzione solo se il vettore iniziale da cui si parte risulta essere relativamente

vicino al vettore soluzione: infatti al variare del parametro varia il vettore di partenza e in particolare,

all’aumentare di tale parametro il vettore approssimazione iniziale si sposta dalla soluzione finale.

In questo caso non è possibile ricavare in maniera analitica l’errore poiché non abbiamo a disposizione la

soluzione esatta, ma attraverso il rapporto della norma tra i 2 passi (quello corrente e quello precedente) è

possibile controllare l’errore e verificare se la convergenza risulti di tipo quadratico: se tale rapporto è

costante, la convergenza sarà quadratica. 5

Descrizione dello script sistemi lineari = 0.

Per la seguente parte si è scelto di studiare il caso di

Nello script denominato “Motodi_diretti_indiretti” si è risolto il sistema lineare così definito;

) ) ) )

( ∙ = −( → −( ∙ = (

+1

= +

Dove è il passo del metodo di Newton rispetto al problema oggetto del seguente studio. Il passaggio che

è stato effettuato nella prima equazione soprastante è servito per poter portare il meno all’interno della

matrice J in modo tale da rendere tale matrice definita positiva e poter usare per la risoluzione del sistema

lineare sopra citato metodi a cui non si sarebbe potuti ricorrere.

Per quanto concerne l’impostazione dei criteri di arresto utili per fermare l’esecuzione dello script in caso

−6

10

di loop o in caso la funzione non converga, si è scelta come tolleranza sulla funzione il valore di ,

mentre come numero massimo di iterazioni si è scelto il valore di 1000 in quanto è stato osservato che per

= 24 tale valore permette la convergenza del metodo ove questa sia possibile.

I calcoli per la definizione delle proprietà della matrice J sono stati svolti all’interno dello script “prop_di_J”.

Le proprietà della matrice stessa risultano essere:

• Matrice tridiagonale.

Figura 4. Forma grafica della matrice J ottenuta mediante il comando spy di Matlab.

• Matrice simmetrica.

• Matrice definita positiva.

• Ben condizionata. 6

Viste le proprietà della matrice, è possibile applicare i metodi diretti ed iterativi riportati di seguito.

Metodi diretti

I metodi diretti consistono nel trasformare un sistema lineare generico in un sistema lineare equivalente,

dotato di una struttura particolare che ne semplifichi la risoluzione. Se non ci fossero errori di

rappresentazione dei dati e di arrotondamento nei calcoli, la soluzione del sistema verrebbe calcolata

esattamente (con un numero stabilito di operazioni). Tali metodi vengono usati per risolvere problemi di

grandezza limitata, dove la matrice è preferibilmente in forma piena.

I metodi diretti sono:

• Metodo di Gauss senza Pivoting;

• Metodo di Gauss con Pivoting Parziale;

• Metodo di Gauss con Pivoting totale;

• Metodo di Cholesky.

Metodi iterativi

Per tali metodi, anche nell’ipotesi di assenza di errori di rappresentazione dei dati e di arrotondamento dei

calcoli, è comunque necessario operare un troncamento del procedimento commettendo un certo errore.

In tali metodi il numero di operazioni non è conosciuto a priori. I metodi iterativi risultano essere più idonei

quando la matrice risulta essere di grande dimensione e memorizzata in forma sparsa, in quanto essi

conservano la sparsità della matrice.

I metodi indiretti sono:

• Jacobi;

• Gauss – Seidel;

• SOR;

• Gradiente coniugato.

Utilizzando i metodi appena elencati si ottengono i seguenti risultati:

Figura 5. Grafico che riporta il numero di iterazioni necessaria ai differenti metodi iterativi per arrivare a

convergenza. Il Metodo del Gradiente coniugato risulta essere quello di gran lunga migliore.

7

Figura 6. Grafico in cui vengono riportati i tempi necessari ad arrivare a convergenza dei vari metodi diretti ed

iterativi utilizzati per la risoluzione del sistema oggetto di studio. Il tempo relativo a Jacobi non identifica la

convergenza del metodo ma il raggiungimento del numero massimo di iterazioni, pari in questo caso a 1000.

La tabella riportata di sopra mostra come il metodo di Jacobi non converga neppure dopo 1000 iterazioni,

numero massimo impostato. I metodi migliori tra quelli diretti sono il metodo di Gauss senza Pivoting, con

Pivoting parziale e Cholesky, mentre il migliore tra quelli indiretti è il metodo pcg, ossia del Gradiente

coniugato. = 5000

Nel caso di tra i metodi indiretti la scelta ricade sul metodo del Gradiente coniugato poiché è

l’unico metodo che arriva a convergenza per dimensioni elevate della matrice e che mantiene una velocità

di esecuzione molto elevata.

Tra i metodi diretti la scelta ricade su Cholesky in quanto è quello che comporta un tempo di calcolo

inferiore quando la matrice è simmetrica e definita positiva.

Scelti quindi i metodi di Cholesky e del Gradiente coniugato, si è deciso di calcolare il passo di Newton

= 5000

inerente al problema differenziale studiato precedentemente per tramite lo script

“Newton_con_metodi”. 8

È stato necessario modificare opportunamente la function di Newton inserendo il metodo pcg per risolvere

il sistema lineare al posto del backslash implementato di base (la function è stata chiamata

“newton_nd_pcg”):

Lo stesso procedimento è stato fatto per l’implementazione di Cholesky all’interno della function di

Newton (in questo caso la function è denominata “newton_nd_chol”):

I risultati sono i seguenti: 9