Mathematical Engineering - Matematica Numerica

Exercise 09

Divided by topic

MATEMATICA NUMERICA A.A. 2018 - 2019 Ingegneria Matematica Prof. A. Quarteroni Prof. A. Manzoni, Dr. I. Fumagalli Esercitazione 9 Metodi iterativi per sistemi lineari (2) Esercizio 1 SiaA2Rn n una matrice simmetrica e denita positiva e si consideri il metodo del gradiente coniugato per risolvere il sistema lineareAx=b: datox(0) , postor(0) =bAx(0) ep(0) =r(0) , si calcola x( k+1) =x( k) + kp( k) ; r( k+1) =r( k)  kA p( k) ; p( k+1) =r( k+1)  kp( k) ;con  k=( p( k) ;r( k) )( p( k) ;Ap( k) ); k=( p( k) ;Ar( k+1) )( p( k) ;Ap( k) ): a)Procedendo per induzione sull'interok0, si dimostrino le relazioni seguenti : (r( k+1) ;p( i) ) = 0i= 0; : : : ; k; (p( k+1) ;Ap( i) ) = 0i= 0; : : : ; k: Occorrerà osservare che per ognim0, si ha r( m) 2V m= spanfr(0) ;Ar(0) ; : : : ;Am r(0) g;p( m) 2V m: b)Sfruttando quanto trovato al punto precedente, dimostrare che (in aritmetica esatta) il metodo delgradiente coniugato termina al più doponiterazioni. c)SianoP 1 ;P 1=2 due matrici simmetriche e denite positive tali cheP 1=2 P 1=2 = P 1 , e si consideri il seguentesistema precondizionato P 1=2 AP 1=2 |{z} b AP 1=2 x |{z} b x= P 1=2 b |{z} b b Applicando il metodo del gradiente coniugato al sistema precondizionatob Ab x=b b, si derivi il metodo del gradiente coniugato precondizionato per il sistemaAx=b. In particolare, si evidenzino il ruolo del residuo precondizionatoz( k) = P 1 r( k) e della direzione di discesaw( k) = P 1=2 b p( k) , doveb p( k) denota la direzione di discesa del gradiente coniugato per il sistemab Ab x=b b.1 Esercizio 2 Costruire la matrice A1= 6:82:4 2:4 8:2 e vericare che ha come autovalori 1= 5 , 2= 10 e come autovettori v1=15  4 3 ;v 2=15  3 4 : Costruire il vettoreb= 4 8 e visualizzare la forma quadratica' 1( x) =12 xT A1x
xT bassociata e le corrispondenti linee di livello. Cosa succede alla forma quadratica se si cambia il primo autovalore in 1= 1 ? In particolare, si deniscaA 2= V DVT ;doveV= [v 1; v 2] eD=diag(1;  2) e si consideri la forma quadratica 2( x) =12 xT A2x
xT b. a)Utilizzare il metodo di Richardson stazionario scegliendo= 0:05oppure= 0:24e il metodo del gradiente (o metodo di Richardson dinamico con parametro ottimale) per risolvere il problema di minimizzazione della forma quadratica 2. In entrambi i casi si usi la funzione richardsonfornita, considerando la versione non precondizionata del metodo (P=I). Visualizzare la successione dei punti che si ottiene in ciascuno dei tre casi. (Suggerimento : modicare la funzionerichardson.m creando una nuova funzionemy_richardsonche implementi lo stesso metodo, ma restituisca in uscita la matrice che ha per colonne la successione delle iteratex( k) , e ne riporti il loro graco.) b)Considerare ora il metodo del gradiente precondizionato, indicando conPla matrice di precondizio- namento ; essa deve essere simmetrica e denita positiva, e tale cheP 1 Asia simmetrica e denita positiva. Risolvere con il metodo del gradiente precondizionato il sistema lineare associato alla forma quadratica 2, utilizzando come precondizionatore la matrice P= 1:09120:8587 0:8587 1:5921 ; visualizzare le iterate e confrontarle con quelle calcolate dal metodo del gradiente : cosa si osserva ? c)(*) Risolvere il sistemaP 1 Ax=P 1 bcon il metodo del gradiente è equivalente a risolvere il sistema Ax=bcon il metodo del gradiente precondizionato ? Si confrontino le iterate ottenute al punto precedente con quelle calcolate dal metodo del gradiente nel caso del sistemaP 1 A2x =P 1 b, a cui è possibile associare una nuova forma quadratica prec( x) =12 xT P 1 A2x
xT P 1 b. d)Usando il template fornito, implementare una funzioneconjgrad.mche realizzi il metodo del gradiente coniugato precondizionato, usando un criterio d'arresto basato sul residuo normalizzato. L'intestazione di tale funzione è[x, niter, error, flag] = conjgrad(A, b, x0, maxit, tol, P). e)Analogamente al punto 1, scrivere una nuova funzionemy_conjgradche restituisca restituisca la ma- trice che ha per colonne la successione delle iteratex( k) , e ne riporti il loro graco. Risolvere il sistema lineare associato alla forma quadratica 2con il metodo del gradiente coniugato non precondizionato e visualizzare il percorso seguito nella discesa verso il punto di minimo.2