Appunti completi di Metodi numerici

Formattazione del testo

ρ(J) valore (in questo caso 0,16), quindi si può notare che è più piccolo Gauss-Seidel, di conseguenza è più veloce e si sa anche di quante volte è più veloce, poiché nella seconda relazione del teorema c'è il quadrato. Bisogna sempre fare molta attenzione a leggere bene i teoremi per capire bene quali informazioni importanti forniscono.

Scelta del parametro ottimale

Si considera una matrice tridiagonale molto semplice che ha 2 sulla diagonale principale e -1 sulle altre due diagonali, quindi è una matrice simmetrica definita positiva. Si può andare a calcolare il raggio spettrale della matrice del SOR al variare di ω, che viene fatto variare tra 0 e 2 come dice la teoria, così facendo si ottiene un andamento di questo tipo:

Da questo grafico si può notare che il raggio spettrale di questa matrice è sempre sotto 1 e ciò è inaccordo con quanto detto prima. Si ha convergenza.

E sapendo che più piccolo è il raggio spettrale più veloce va il metodo, l'ottimale sarà quello che si ha incorrispondenza del punto diminimo dell'andamento (il valore di ω sta sull'asse delle ascisse). In generale, a dipendere dal problema che si ha, il valore di ω ottimale si trova proprio nella zona compresa tra 1 e 2 del relativo asse; questo spiega perché di solito si fa il SOR e cioè proprio perché l'ottimale di solito ricade in questa zona. 134 Questo è un altro esempio con la solita matrice che può essere grande quanto si vuole, partenza con vettore nullo e con una certa tolleranza 10. Non ha importanza il criterio di arresto usato, per tutti e 3 i metodi graficati (Jacobi, Gauss-Seidel e rilassamento) è stato utilizzato lo stesso criterio e la stessa tolleranza. Sull'asse orizzontale sono riportate le iterazioni mentre su quello verticale c'è.

l'errore che si sta monitorando. È un esempio di laboratorio quindi si conosce la soluzione (vettore x), per cui è possibile fare questo grafico per capire. I quadratini rappresentano Jacobi, si può notare che l'errore cala lentamente e ciò significa che il metodo sta andando in convergenza; i triangolini sono Gauss-Seidel e anche in questo caso l'errore cala ma calando più rapidamente rispetto a Jacobi; infine i puntini indicano il SOR con l'ω ottimale (perché è una matrice semplice e si conoscono le formule, altrimenti bisogna fare lo studio di prima), con quest'ultimo metodo l'errore cala molto rapidamente. Quindi con un ω scelto correttamente si può accelerare notevolmente la convergenza. Quello appena descritto è un semplice esempio di laboratorio in quanto nella pratica non si hanno delle tridiagonali e non si riesce a scegliere l'ω ma si deve ragionare di.

esperienza. Questo disegno permette di ragionare, è un esempio preso dalle equazioni differenziali, in orizzontale c'è l'ω che è subito plottato tra 1 e 2 perché di solito è il range che si va ad usare e in verticale c'è il numero di iterazioni. Si può osservare che sono stati svolti i calcoli per tutti gli ω in modo da ottenere questo grafico; a posteriori proprio da questo grafico si può vedere dove si trova l'ω ottimale, perché se si prende quell'ω si ha il minor numero di iterazioni possibile. Però questo è quanto avviene in laboratorio svolgendo degli esercizi ma nella pratica per un caso reale non si fanno di certo tutte le possibili iterazioni e tutti i possibili raggi spettrali o quanto altro, perché quando si deve risolvere un problema si dovrà dichiarare l'ω che si vuole.

135 Per farlo è importante avere l'esperienza sulle

problematiche da affrontare, infatti è stato detto che di solito il range è tra 1 e 2 ma questa è l'esperienza e in base alle diverse esperienze si riescono a inquadrare i problemi e si sa qual è il range.

Dal grafico precedente si può osservare che in corrispondenza di ω=1 si hanno le iterazioni di Gauss-Seidel quindi un qualsiasi ω che permetta di stare sotto a questo numero di iterazioni fa guadagnare, però bisogna anche fare attenzione perché se si assume ω circa uguale a 2 non si guadagna più nulla in quanto il numero di iterazioni cresce. La morale di questo esempio è che se non si sa dov'è l'ω ottimale conviene sottostimarlo, perché se lo si prende più piccolo ci si trova ancora in una zona di guadagno, ma se lo si prende più grande si corre il rischio di cadere nella zona di destra e quindi di avere un maggior numero di iterazioni.

Questo è un

• Un ulteriore esempio è il caso di un'equazione differenziale in cui si conosce la soluzione e si vede come avviene la convergenza.
• Nel caso di ω ottimale si ha una convergenza monotona crescente alla soluzione esatta.
• Se si sottostima ω, la convergenza è sempre così ma più lenta.
• Se si sovrastima ω, si ha un comportamento oscillatorio, con il quale si salta sopra e sotto la soluzione esatta.

Interpretazione:

Bisogna fare attenzione perché quando si legge un libro può succedere di non riconoscere immediatamente il metodo, bisogna leggere con molta calma le formule.

Tornando indietro al Metodo di Gauss-Seidel e in particolare facendo riferimento alla nuova componente, era presente il suo coefficiente, era il termine noto, poi si avevano le componenti che erano già state aggiornate e le componenti vecchie che si dovevano ancora aggiornare, quindi...

Gauss-Seidel sfruttava immediatamente l'aggiornamento delle incognite: Partendo dal Metodo di Gauss-Seidel (dove al posto di "k" però si considererà "k+1"), si può manipolare questa espressione sottraendo da ambo i membri, perché non si può mettere solo a sinistra e non a x(k) destra, ma per scrivere dentro la parentesi quadra si deve aggiungere il termine "in modo x" - x - a(k)(k)i i i che le due si semplificano e quindi resta solo che è presente anche a sinistra e quindi è non cambiato a - x(k)ii in nulla. Allora si può riscrivere l'espressione, ricopiando tutti i termini fino alla prima sommatoria, mentre l'x dovrà (k)i essere messo insieme alla seconda sommatoria, che non partirà più da "i+1" ma da "i", per cui si ottiene: Ciò che si trova a destra è uguale a ciò che si trova a sinistra, per cuil’espressione di destra può essere chiamata semplicemente con una lettera e in particolare la si chiama b - ax residuo. Si era partiti da Gauss-Seidel e sulla base di quanto detto si può scrivere banalmente:
Oppure in forma vettoriale: il nuovo vettore è uguale al vecchio più e quindi Gauss-Seidel non è nient'altro che la somma di due vettori (è stato chiaramente esplicitato chi è il vettore r).
In sostanza, ragionando in questo modo, con il SOR si accorcia o si allunga il vettore o il parametro ω, per cui si fa una somma ragionata, andando a sommare lo scalare ω per il vettore al vecchio vettore r.
Questo ragionamento è utile perché tutti i metodi nuovi dovranno essere scritti in questa forma: nuovo vettore è uguale a quello vecchio più uno scalare che moltiplica dei vettori che di volta in volta saranno di tipo diverso; quindi questi metodi nuovi eall'avanguardia che si utilizzeranno discendono nel ragionamento dai vecchi Gauss-Seidel e SOR. Per fare in dettaglio tutti questi metodi servirebbe un intero corso per cui si farà soltanto un assaggio per capire alcuni concetti, anche perché finora sono stati visti i metodi di base. Solutori per matrici sparse Ax=b Si ha sempre il problema del sistema lineare da risolvere e nelle applicazioni reali si hanno problemi di grandi dimensioni, ad esempio quando si andranno a fare gli elementi finiti si avranno matrici di grandi dimensioni ma che fortunatamente sono sparse, ovvero con pochi elementi non nulli (nell'ordine del 2%), per cui i metodi diretti soffrono del problema del riempimento, ci sono delle varianti sofisticate per cercare di non riempire troppo la memoria ma in ogni caso questo è un difetto dei metodi diretti. Invece per quanto riguarda i metodi iterativi ragionando su Jacobi e su Gauss-Seidel si è capito che di fatto basta memorizzare insimmetriche e/o sparse. Questi metodi sono molto efficienti in termini di memoria e tempo di calcolo. Per quanto riguarda i metodi diretti, il metodo di Gauss o pivoting parziale o totale viene utilizzato quando la matrice non è simmetrica. Questo metodo permette di risolvere il sistema di equazioni lineari in modo diretto e preciso. Se invece la matrice è simmetrica e definita positiva, si può utilizzare il metodo di Cholesky. Questo metodo sfrutta la simmetria della matrice per ridurre il numero di operazioni necessarie e ottenere una soluzione più precisa. Nei metodi iterativi, invece, si memorizzano solo gli elementi non nulli della matrice e si utilizza una moltiplicazione "furba" e veloce. Questi metodi sono particolarmente adatti per risolvere problemi di grandi dimensioni con matrici sparse. In conclusione, i metodi presenti nella colonna degli iterativi sono generalizzazioni dei metodi degli anni '90 che permettono di risolvere problemi complessi con matrici non simmetriche e/o sparse. Questi metodi sono molto efficienti in termini di memoria e tempo di calcolo.

simmetriche. Sono metodi iterativi quindi poca memoria però attenzione perché c'è il criterio di arresto quindi si dovrà decidere quando fermarsi correttamente. Visto che spesso e volentieri si hanno matrici simmetriche definite positive nelle applicazioni, il metodo che si andrà a vedere adesso è il concorrente del Cholesky ed è chiamato il "Gradiente ed è il metodo Coniugato" più veloce. Nella figura è rappresentata una funzione convessa, se si vanno a rappresentare le curve di livello, ovvero se la si affetta con dei piani con z costante si otterranno tutte le curve di livello riportate a destra. Queste funzioni convesse sono importanti perché quando si vanno a cercare dei punti di minimo era facile trovarli, infatti basta fare la derivata prima e uguagliarla a 0, se la funzione è