Mathematical Engineering - Matematica Numerica

Exercise 08

Divided by topic

MATEMATICA NUMERICA A.A. 2018 - 2019 Ingegneria Matematica Prof. A. Quarteroni Prof. A. Manzoni, Dr. I. Fumagalli Esercitazione 8 Metodi iterativi per sistemi lineari (2) Esercizio 1 Si consideri la seguente matrice : A =2 6 6 410 1 2 3 1 101 2 2 3 201 3 2 1 203 7 7 5 e siaAx=bil sistema lineare associato, dove il termine noto è scelto in modo tale che la soluzione esatta siax ex= [1 ;1;1;1]T . a)Vericare se la matriceAè simmetrica, denita positiva e/o a dominanza diagonale stretta. Stabilire, inoltre, se i metodi di Jacobi e Gauss-Seidel applicati al sistema convergano. b)Si calcoli la norma 2 della matrice di iterazioneB Jassociata al metodo di Jacobi, per il sistema dato. Stimare il numero minimo di iterazionikminnecessarie anchè il metodo di Jacobi riduca l'errore iniziale in norma 2 di un fattore"= 10 10 . c)Vericare numericamente il risultato ottenuto al punto precedente, implementando la funzionemyjacobicon rma[xn,iter]=myjacobi(A,b,x0,nmax,toll)e partendo dal vettore iniziale x0 = zeros(4,1). La funzione deve arrestarsi qualora sia raggiunto il numero massimo di iterazioni Nmaxo sia vericato il criterio di arresto : kr( k) k2k bk 2< toll; (1) essendor( k) =bAx( k) ilresiduoassociato allak-esima iterazione. d)Si consideri ora il metodo SOR, x( k+1) i=!a ii0 @bii 1 X j=1a ijx( k+1) jn X j=i+1a ijx( k) j1 A+ (1!)x( k) i; i = 1; : : : ; n; k0:(2) Modicare la funzionemyjacobiper ottenere una funzionemysorche implementi il metodo SOR per la risoluzione del generico sistemaAx=b. Si utilizzi poi la funzione per risolvere lo stesso problema con il metodo di Gauss-Seidel, con una tolleranzatoll= 10 10 : quante iterazioni vengono eettuate ? L'errore relativo è minore del fattore"= 10 10 considerato al punto b) ?1 Esercizio 2 Sia data la seguente matriceA2R10 10 2 6 6 6 6 44 1 0 0: : : 1 41 0: : : 01 41: : : : : : : : : : : : : : : : : : : : :0 01 43 7 7 7 7 5: a)Vericare che essa è simmetrica, denita positiva e a dominanza diagonale stretta. Stabilire inoltrese i metodi di risoluzione iterativi di Jacobi, Gauss-Seidel e SOR per la soluzione del sistemaAx= bsono convergenti. Per quest'ultimo metodo, determinare il valore ottimale! optdel parametro di rilassamento. b)Vericare numericamente che(B GS) = 2 (B J) . Determinare quindi la relazione tra le velocità asin- totiche di convergenza dei due metodi e vericarla sperimentalmente usando le funzionimyjacobie mysorimplementate nell'Esercizio precedente. Si pongab=A *ones(10,1) e si considerix 0= 0. c)Confrontare sperimentalmente la velocità di convergenza asintotica del metodo SOR con parametrodi rilassamento ottimale e del metodo di Gauss-Seidel (corrispondente a SOR con!= 1). Si ponga b=A*ones(10,1) . Che cosa si osserva ? Esercizio 3 Si consideri il problema lineareAx=b, dove la matriceA2Rn n è pentadiagonale : A=2 6 6 6 6 6 6 6 6 6 44 11 1 411 11 411 :::: ::: ::: ::: :: 11 411 11 41 11 43 7 7 7 7 7 7 7 7 7 5; b=2 6 6 6 6 6 6 6 6 6 40 :2 0:2 0:2 : : : 0:2 0:2 0:23 7 7 7 7 7 7 7 7 7 5: (3) Si vuole risolvere tale problema con il metodo di Richardson, soddisfacendo una tolleranza di10 5 , a partire dal vettore soluzione inizialex(0) = [0; : : : ;0]T . a)Utilizzando uno script si creino la matriceA(conn= 50), il termine notobed il vettore soluzione inizialex(0) . b)Si verichi che la matriceAsia simmetrica e denita positiva e se ne calcoli il numero di condiziona- mentosenza utilizzare il comandocond. c)Si implementi la funzionerichardson.min grado di applicare il metodo diRichardson precondizionato nel casostazionarioad un generico sistema lineare. La funzione deve avere la seguente intestazione : [x, k] = richardson(A, b, P, x0, tol, nmax, alpha) doveAè la matrice del sistema lineare,bè il termine noto,Pè il precondizionatore,x0è il vettore iniziale,tolè la tolleranza (per il criterio di arresto del residuo normalizzato),nmaxè il numero massimo di iterazioni edalphaè il valore del parametro di accelerazione. Il metodo si arresta non appena sia vericato il criterio kr( k) kk bk< tol essendor( k) =bAx( k) il residuo associato allak-esima iterazione. In output, la funzione deve restituire l'ultima iterazionex( k) , e il numerokdi iterazioni eettuate.2 d)Si risolva il sistema lineare con il metodo di Richardson stazionario non precondizionato ( P=I), utilizzando i seguenti parametri di accelerazione := 0:2,= 0:33ed= opt= 2 =( min+  max) (parametro di accelerazione ottimale) dove mine  maxsono rispettivamente l'autovalore minimo e l'autovalore massimo della matriceP 1 A. Per ciascun valore disi calcoli il raggio spettrale della matrice di iterazione (IP 1 A) e si risolva il sistema riportando a video il numero di iterazioni eseguite (si suggerisce di utilizzarenmax= 10000). e)Prendendo come esatta la soluzione calcolata col comando n, si calcoli l'errore relativo della soluzione ottenuta con opte si verichi se è in accordo con la teoria. f )Si risolva il sistema lineare con il metodo di Richardson stazionario utilizzando come precondizionatorela matrice triangolare inferiore diAe come parametro di accelerazione= 1(ovvero il metodo di GaussSeidel), riportando a video il numero di iterazioni eseguite. Calcolare il raggio spettrale della matrice di iterazione ed il numero di condizionamento della matriceP 1 A. Si verichi inne che il risultato ottenuto è identico a quello che si otterrebbe utilizzando il metodo di GaussSeidel. g)Si consideri il seguente precondizionatore tridiagonale : P=2 6 6 6 6 6 42 1 1 21 :::: ::: :: 1 21 1 23 7 7 7 7 7 5: (4) Si risolva il sistema lineare con il metodo di Richardson stazionario utilizzando come precondiziona- tore la matriceP, dopo aver vericato che sia simmetrica e denita positiva, e come parametro di accelerazione opt, riportando a video il numero di iterazioni eseguite. Si calcolino il raggio spettrale della matrice di iterazione ed il numero di condizionamento diP 1 A. Esercizio 4 Sia dato il sistema lineareAx=bcon A =2 46 3 0 3 6 4 0 4 63 5;b=2 41 2 33 5 e lo si risolva con il metodo di Richardson stazionario precondizionato con parametro di accelerazione ottimale, in cui il precondizionatore è dato daP = D, essendoDla parte diagonale diA. a)Si verichi cheP 1 Aè simmetrica e denita positiva e si calcoli il parametro di accelerazione ottimale opt. b)Calcolare il fattoreCdi riduzione dell'errore, tale che kx( k+1) xk A Ckx( k) xk A: c)A partire dalla relazione precedente, dimostrare la seguente maggiorazione : kx( k) xk AC k1 Ck x(1) x(0) kA: d)Scegliendo come vettore inizialex(0) = [0;0;0]T , stimare il numero minimo di iterazioni necessarie per avere un errore in normak
k Ache sia più piccolo di 10 8 .3