Exercise 09

Page 1

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 Sia A∈ Rn×n una matrice simmetrica e definita positiva e si consideri il metodo del gradiente coniugato per risolvere il sistema lineareAx = b : dato x(0), posto r(0) = b− Ax(0) e p(0) = r(0), si calcola x(k+1) = x(k) +αkp(k), r(k+1) = r(k)−αkAp(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’interok≥ 0, si dimostrino le relazioni seguenti : (r(k+1), p(i)) = 0 i = 0,...,k, (p(k+1), Ap(i)) = 0 i = 0,...,k. Occorrerà osservare che per ognim≥ 0, si ha r(m)∈Vm = span{r(0), Ar(0),..., Amr(0)}, p(m)∈Vm. b) Sfruttando quanto trovato al punto precedente, dimostrare che (in aritmetica esatta) il metodo del gradiente coniugato termina al più dopon iterazioni. c) Siano P−1, P−1/2 due matrici simmetriche e definite positive tali cheP−1/2P−1/2 = P−1, e si consideri il seguente sistema precondizionato P−1/2AP−1/2    ˆA P−1/2x   ˆx = P−1/2b   ˆb Applicando il metodo del gradiente coniugato al sistema precondizionatoˆAˆx =ˆb, si derivi il metodo del gradiente coniugato precondizionato per il sistemaAx = b. In particolare, si evidenzino il ruolo del residuo precondizionato z(k) = P −1r(k) e della direzione di discesaw(k) = P −1/2ˆp(k), doveˆp(k) denota la direzione di discesa del gradiente coniugato per il sistemaˆAˆx =ˆb. 1 Esercizio 2 Costruire la matrice A1 = ( 6.8 −2.4 −2.4 8 .2 ) e verificare che ha come autovaloriλ1 = 5, λ2 = 10 e come autovettori v1 = 1 5 ( 4 3 ) , v2 = 1 5 ( −3 4 ) . Costruire il vettore b = ( 4 8 ) e visualizzare la forma quadraticaϕ1(x) = 1 2 ( xTA1x ) −xT bassociata e le…